§ 6.4. Эволюционная адаптация структуры решающих правил

Проблема принятия оптимального решения в ситуации X сводится к синтезу решающего правила связывающего ситуацию и решение:

Простейшей задачей принятия решений является задача о распознавании (классификации) двух образов, в которой где 0 и 1 являются именами различаемых образов (классов). Рассмотрим эту проблему с точки зрения эволюционной адаптации [62].

Задача обучения распознаванию образов заключается в построении оптимального решающего правила из некоторого априорно выбранного класса функций, определяющего структуру решающего правила. Если структура выбрана удачно, то в результате обучения возможно построить хорошее решающее правило. Однако обычно имеющейся априорной информации

оказывается недостаточно для правильного выбора структуры решающего правила, поэтому построенное таким образом решающее правило может значительно отличаться от требуемого, рационального (не говоря уже об оптимальном).

В связи с этим возникает важная проблема адаптации структуры решающего правила к конкретной задаче распознавания. Для ее решения необходимо в процесс обучения ввести процедуру поиска оптимальной структуры решающего правила, т. е. сочетать процесс обучения решающего правила с оптимизацией его структуры.

6.4.1. Постановка задачи

Задача обучения классификации объектов, как известно, заключается в построении в процессе обучения решающего правила вида

где X — -мерный вектор, описывающий распознаваемый объект; В и С — множества, соответствующие двум различаемым классам объектов (объекты класса В имеют имя «1», а класса С — имя

Выражение (6.4.2) реализует в -мерном пространстве признаков разделяющую поверхность для всех объектов множества . Однако для определения решающего правила используется только некоторое подмножество объектов из В и С, составляющее конечную обучающую последовательность длины Поэтому задача обучения классификации обычно представляется как задача аппроксимации заранее неизвестной разделяющей поверхности другой поверхностью, достаточно близкой к первой, но построенной на базе конечной обучающей последовательности.

Один из наиболее распространенных подходов к решению этой задачи заключается в представлении искомой разделяющей функции в виде разложения в ряд по некоторой системе функций выбираемой однократно из априорно заданного класса Искомое решающее правило в этом случае описывается выражением

где

Система функций определяет структуру правила — вектор его весов, а через обозначено скалярное произведение векторов V и

Задача построения оптимального решающего правила заключается в определении параметров V таким образом, чтобы обеспечить наилучшую аппроксимацию действительной разделяющей поверхности, т. е. эффективно приблизить искомое правило (6.4.3) к действительному (6.4.2).

Обозначим через эмпирический риск (число ошибок на обучающей последовательности) искомого решающего правила Тогда задачу наилучшей аппроксимации можно рассматривать как задачу минимизации эмпирического риска по параметрам V в процессе обучения при неизменной, априорно выбранной структуре Ф, т. е.

где — евклидово пространство размерности результат решения задачи. Решение (6.4.5) и есть обучение.

Для решения этой задачи разработаны многочисленные алгоритмы обучения. Общая блок-схема такого обучения приведена на рис. 6.4.1. В зависимости от выбора системы функций схема может описывать метод потенциальных функций [13], классический перцептрон [199] и др.

Однако во многих конкретных задачах имеющиеся априорные соображения либо оказываются недостаточными для правильного выбора системы функций либо отсутствуют. В таких случаях естественно адаптировать структуру Ф решающего правила в процессе обучения. Тогда оптимальное решающее правило, обеспечивающее наилучшую аппроксимацию, будет определяться из условия минимума функционала эмпирического риска при вариации структуры решающего правила:

Блок-схема этой процедуры приведена на рис. 6.4.2.

Рис. 6.4.1. Блок-схема обучения решающего правила при заданной структуре.

Рис. 6.4.2. Блок-схема обучения с адаптацией структуры решающего правила.

Для решения такой задачи удобно представить систему функции Ф в виде

где Ф — заданная система функций, вектор, кодирующий структуру этой системы. Тогда задачу адаптации структуры решающего правила можно сформулировать как задачу отыскания оптимальной структуры в процессе обучения:

где — множество допустимых структур. Ввиду обилия допустимых структур решение задачи адаптации целесообразно производить методами случайного поиска. (Заметим, что возможна и параметризация структуры перцептрона, которая была успешно использована в работе [176], где для этого применялась процедура многомерной линейной экстраполяции [186].)