Введение в обучающиеся системы классификаторов

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

1. Простая система классификаторов

По Холланду [Holland, 1975] необучаемая система классификаторов состоит из четырех главных компонент:

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

В любой момент времени список сообщений может иметь ноль или больше сообщений. Каждое сообщение имеет одинаковую простую структуру и состоит из строки фиксированной длины L и алфавита A_msg, например бинарного. Использование такой структуры делает очень удобным сравнения условий классификаторов с входными сообщениями на предмет их совпадения.

Список классификаторов состоит из множества классификаторов, имеющих следующую форму:

Все условия составляют условную часть классификатора. При n=1 классификатор называется одно-условным; при n>1 - много-условным. Алфавит условия совпадает с алфавитом сообщений и имеет дополнительно символ "#" (don't care), означающий, что символ может быть любым из алфавита A_msg.

Например, для алфавита A_cond={0,1,#} результаты сравнения могут выглядеть следующим образом:

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

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

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

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

Основной цикл системы классификаторов:

1. Добавить сообщения, полученные с помощью входного интерфейса в список входных сообщений.
2. Сравнить все сообщения в списке сообщений с условными частями всех классификаторов, и запомнить все те классификаторы, у которых произошло совпадение.
3. Создать новые сообщения, активизировав, совпавшие классификаторы, т.е. выполнить действия классификаторов.
4. Полученные сообщение "пропустить" через выходной интерфейс.
5. Заменить содержимое списка входных сообщений новыми сообщениями.
6. Перейти к шагу 1.

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

2. Обучающаяся система классификаторов

Основные дополнения, введенные в системы классификаторов для обеспечения их обучаемости, выглядят следующим образом:

1. Активация классификатора зависит от некоторых параметров, которые изменяются в процессе накопления опыта.
2. Изменять содержимое множества классификаторов: удалять классификаторы, добавлять новые классификаторы или изменять их условные части или действия.

Рис. 1. Классическая система классификаторов Холланда [Holland, 1984]

2.1. Накопление опыта

Каждый классификатор имеет силу (strength), показывающую его текущую полезность в системе. Сила изменяется в процессе накопления опыта.

Иногда используется специфичность (specificity) классификаторов. Специфичность - количество не "#" символов в условной части, разделенной на ее длину. Специфичность используется при ставках в алгоритме пожарной команды. Классификатор тем больше специфичный, чем меньше у него символов "#". Значение специфичности изменяется от 0 до 1 и высчитывается по формуле:

где L - длина условной части классификатора; W - количество символов "#" в условии.

2.2. Алгоритм пожарной бригады

Алгоритм пожарников (Bucket-Brigade) был впервые предложен Холландом. Основан он на упрощенной модели экономики. Алгоритм состоит из двух основных компонентов: аукциона (auction) и расчетной палаты (clearing house).

Когда условные части классификаторов совпадают с входным сообщением, они посылают свои сообщения не напрямую, а после аукциона. На аукционе классификаторы делают ставку (bid) пропорционально своей силе. Классификатор, сделавший большую ставку, имеет предпочтение (bid competition) для выигрыша перед другими классификаторами.

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

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

В работе [Wilson, 1987] было показано, что количество итераций, необходимых для обучения цепочки классификаторов размера n на 90 процентов, вычисляется по формуле:

где C_bid - коэффициент ставки в аукционе, изменяющайся от 0.1 до 0.4.

2.3. Генетические алгоритмы

Поскольку алгоритм пожарной команды изменяет только силы классификаторов, то качество системы сильно зависит от начально сформированной популяции. Для устранения этого недостатка используются генетические алгоритмы (discovery algorithms, genetic algorithms).

Простой генетический алгоритм (ГА) работает следующим образом:

1. Выбрать классификаторы пропорционально их силе с помощью, например, пропорционального колеса рулетки.
2. Применить генетические операторы (мутация и скрещивание) для их изменения. Наиболее важным является оператор скрещивания (crossover).
3. Выбрать классификаторы для замены с помощью, например, инверсионного колеса рулетки, и заменить эти классификаторы классификаторами, полученными на шаге 2.

Генетические алгоритмы должны применяться очень редко, например, один раз в тысячу итераций, или при стабилизации сил классификаторов в популяции. Это дает алгоритму пожарной команды время подстроить силы классификаторов, после чего они могут быть использованы ГА.

2.4. Процедура покрытия

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

Процедура покрытия работает следующим образом:

1. Берется входное сообщение, и с определенной вероятностью его некоторые символы заменяются на символ "#" (don't care).
2. Затем ищется в популяции слабый классификатор с помощью, например, инверсионного колеса рулетки, и заменяется на новый.