Новый иммуноподобный алгоритм классификации типа "обучение с учителем" Valis

Размещено на http://www.allbest.ru/

Вычислительный центр РАН

НОВЫЙ ИММУНОПОДОБНЫЙ АЛГОРИТМ КЛАССИФИКАЦИИ ТИПА "ОБУЧЕНИЕ С УЧИТЕЛЕМ" VALIS

П.М. Карпов

Москва

В статье предлагается новый алгоритм классификации, основанный на принципах функционирования иммунной системы. Работа алгоритма рассматривается на примере задач распознавания символов и классификации текстов.

1. Описание системы

Существует множество алгоритмов, основанных на различных метафорах естественной иммунной системы: алгоритмы отрицательного отбора, клональной селекции и другие. Предлагаемая система VALIS (Vote Allocating Immune System - иммунная система с распределением голосов) предназначена для классификации и относится к алгоритмам типа "обучение с учителем". Следуя иммунологической метафоре, каждый образец данных представляет собой антиген. Элементарной структурной единицей искусственной иммунной системы является антитело. Молекулы (антигены и антитела) характеризуются наборами параметров, называющихся их обобщёнными формами. В пространстве обобщённых форм задаётся функция расстояния Distance(Ag,Ab) или близости Affinity(Ag,Ab), количественно определяющая степень взаимодействия между антигеном Ag и антителом Ab. Конкретный вид представления молекул и функции расстояния определяется задачей. Вдобавок к обобщённым формам, антитела (как и антигены) имеют ярлыки классов. Аналогично тому, как естественная иммунная система вырабатывает иммунный ответ на присутствующие антигены, алгоритм должен возвращать ярлык класса в ответ на предъявляемые данные.

При предъявлении системе образца данных производится связывание (binding) некоторых антител с предъявленным антигеном. Связывание количественно определяется весом W=F(Distance(Ag,Ab)) или W=F(Affinity(Ag,Ab)). В этой работе используется пороговая функция: Если Distance(Ag,Ab)<R, W=1 иначе W=0 (Если Affinity(Ag,Ab)>R, W=1 иначе W=0), где R - порог активации (affinity threshold), который может быть глобальным (одинаков для всех антител) или локальным (свой для каждого антитела). В таком случае области связывания антител в пространстве параметров выглядят как гипершары. В качестве F можно использовать и другие функции - например, плавно затухающие вроде
W=Exp(-Distance(Ag,Ab)/R), тогда области связывания не будут иметь чётких границ. В антитело можно добавить параметры, определяющие его форму - в таком случае связывание будет происходить в определяемой этими параметрами области. Наконец, для определения веса связывания вместо использования функции F можно использовать правило k-ближайших, когда связанными с антигеном считаются лишь k ближайших к нему антител.

Табл. 1.

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

2. Алгоритм обучения

1. Создание популяции.

Создать популяцию из антител, присвоить всем антителам случайные параметры и случайные ярлыки классов.

2. Предъявление набора данных и вычисление параметров.

Каждый образец данных из обучающей выборки предъявляется системе. После этого для каждого антитела вычисляются следующие параметры:

Количество связываний - сколько раз происходило связывание данного антитела с антигенами.

Количество правильных ответов - сколько раз в случае связывания ярлык класса антитела совпадал с классом антигена.

Вероятность правильного ответа .

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

Приспособленность (Fitness) каждого антитела

3. Присвоение классов.

Установить ярлык класса каждого антитела по большинству ярлыков классов антигенов, которые были с ним связанны.

4. Репродукция.

Путём мутации или скрещивания создаётся потомков. Параметр имеет смысл скорости обучения. При мутации/скрещивании изменяются все параметры антител, в том числе параметры, отвечающие за связывание.

5. Замена.

Произвести замену худших по приспособленности антител созданными потомками.

6. Если не достигнут критерий остановки - перейти к шагу 2, иначе - конец.

Шаги с 2 по 6 представляют собой одно поколение. В качестве критерия остановки может служить достижение определённой точности классификации, прошествие фиксированного количества поколений или времени.

Менее формально, алгоритм можно описать так: каждое антитело отвечает за классификацию в некоторой локальной области. Антитела, имеющие большую вероятность правильного ответа, имеют большую приспособленность. Но чтобы избежать сходимости всей популяции в одну область с максимумом приспособленности, подобно генетическому алгоритму с нишированием [Dick, 2005] вводится разделение ресурсов - как только в одной области скапливается большое количество антител, коэффициент разделения падает и другие области становятся более выгодными с точки зрения приспособленности. Этот механизм заставляет систему полностью исследовать пространство параметров. Но в отличие от ГА, целью является получение популяции антител, коллективно решающих общую задачу.

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

Рис. 1. Белый, серый и чёрный цвета соответствуют трём классам точек на плоскости.

Слева направо: начальная популяция антител, популяция через 20, 200 поколений, настоящее расположение классов.

Для репродукции можно использовать различные стратегии выбора родителей, например селекцию, пропорциональную приспособленности (fitness proportional selection). Это приводит к тому, что в областях большей приспособленности начинает скапливаться большее количество антител, что ведёт к уменьшению приспособленности в этой области и к скорейшему выравниванию значений приспособленности в разных областях - то есть более быстрому исследованию пространства параметров.

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

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

Статистический режим: схему голосования можно расширить, введя для каждого антитела нормированную на единичную сумму гистограмму классов вместо одного ярлыка класса. На шаге "Присвоение классов" она обновляется с учётом классов всех связанных антигенов. Значением корректности при связывании с антигеном является значение гистограммы для его класса. При голосовании антитело прибавляет всю свою гистограмму к гистограмме голосов. Такой подход может увеличить точность классификации, но несколько теряет в наглядности.

3. Тестовая задача - распознавание символов

В качестве тестовой задачи было использовано распознавание цифр от 0 до 9.

Символы в антигенах центрировались путём совмещения центра масс с геометрическим центром области (это не является особым упрощением в пользу ИИС, так как эквивалентно модифицированному правилу вычисления расстояния Антиген-Антитело, при котором центрируется массив антитела). Задача осложнялась тем, что каждый символ подвергался случайному масштабированию от 90 до 110 процентов по линейным размерам, и случайному повороту в пределах ±15 градусов. В отличии от "игрушечной" задачи по распознаванию [De Castro et al., 2000], в которой каждому классу соответствует один образец данных, для успешного распознавания системе необходимо выполнить обобщение основываясь на различных образцах символов с разными масштабами и поворотами. Ниже приводится график точности классификации, полученный в результате пробного запуска системы. иммунный символ текст обучение

Табл. 2.

Через 1000 поколений обучение было продолжено с уменьшенной скоростью обучения и увеличенным количеством предъявляемых антигенов в течение ещё 1000 поколений. Такое изменение параметров было произведено с целью экономии времени в начале и уменьшения случайных флуктуаций состояния системы в конце - замена большого количества антител за поколение и маленькая статистика отрицательно влияют на стабильность. Финальная точность классификации составила 99%.

Рис. 2. Обучение системы - распознавание символов (серый - мгновенные, чёрный - средние значения).

По результатам запуска можно сделать следующие замечания:

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

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

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

Не смотря на то, что в системе нигде напрямую не используются данные об антигенах (например, в отличие от CLONALG [De Castro et al., 2000], при репликации не отдаётся предпочтение антителам, близким к каким-либо антигенам), система смогла произвести эффективные антитела, что говорит о более тонком поведении, чем стохастический направленный поиск.

Был выработан оригинальный способ распознавания: антитела визуально не похожи на распознаваемые символы и имеют хаотический вид (Рис. 3). Даже после усреднения массивов антител одного класса, узнать символы можно лишь с трудом (Рис. 4).

Результат не является тривиальным: если создать случайную выборку из 300 образцов распознаваемых символов и осуществлять распознавание по классу ближайшего соседа, точность классификации оказывается меньше (98%).

Распределённая память: классификация имеет коллективный характер, поэтому удаление отдельных антител не влияет на функционирование системы в целом. Неплохая точность обеспечивалась даже после удаления 80% случайных антител (Рис. 5).

Рис. 3. Пример распознавания символа. Справа от антигена приведено несколько связанных антител.

Всего связано 17 антител с правильным классом, 3 с неправильным. Большинством голосов антиген классифицируется как цифра 6.

Рис. 4. Усреднённые массивы антител одного класса.

Рис. 5. Устойчивость к удалению антител.

4. Тестовая задача - классификация текстов

Вторая тестовая задача состояла в определении языка программирования по части исходного кода.

Табл. 3.

Рис. 6. Обучение системы - классификация текстов (серый - мгновенные, чёрный - средние значения).

В результате была достигнута точность 96%. Система выработала антитела, соответствующие характерным конструкциям языков.

Примеры антител, соответствующих различным языкам (по результатам нескольких запусков) - в таблице 4. #10 и #13 являются символами начала новой строки.

Табл. 4.

На этом примере видны преимущества схемы с изменяемыми областями связывания: пороги активации различных полученных антител могли отличаться в 15 раз. Связанной особенностью является существование в популяции антител существенно различающихся «размеров» (в смысле общего количества связываемых антигенов). Использование правила k-ближайших не приводило к адекватному обучению - средняя точность составляла не более 35%.

5. Сравнение с AIRS и другими системами

Существует не так много иммунологических алгоритмов классификации типа "обучение с учителем", один из наиболее известных - AIRS [Watkins et al., 2002].

В AIRS нет различия между представлением антигена и антитела: оба описываются вектором в одном пространстве параметров. Принципиальным отличием VALIS является в общем случае различное представление антигенов и антител. Это придаёт системе очень большую гибкость - в приведённом выше примере классификация осуществлялась без каких-либо преобразований входных текстов в вектора. Отсутствие необходимости подобных преобразований так же является преимуществом над искусственными нейронными сетями.

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

Суммарное количество антител после обучения AIRS очень велико - примерно половина размера обучающей выборки. Популяция антител VALIS имеет фиксированный размер. В приведённом выше примере с распознаванием символов каждый распознаваемый символ, предъявляемый системе, генерировался заново при помощи случайного масштабирования и поворота, то есть полный размер обучающей выборки был ограничен лишь дискретностью представления символов. Тем не менее, система справилась с задачей при размере популяции в 300 антител, что говорит об очень высокой степени обобщения.

В отличие от AIRS и вариантов CLONALG [Brownlee, 2005] [Garain et al., 2006], в которых классификация осуществляется по правилу k-ближайших, что никак не влияет на обучение, способ классификации является неотъемлемой частью VALIS. Применение правила независимого голосования, основанного на весах связывания более понятно с биологической точки зрения - правило k-ближайших требует глобального взаимодействия антител (сортировка по степени соответствия антигену), чего не происходит в естественной иммунной системе. Применение антител переменного размера схоже с V-детектором [Ji et al., 2004]. Но так как V-детектор является алгоритмом отрицательного отбора, он позволяет осуществлять лишь бинарную классификацию свой-чужой (self-nonself).

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

Заключение

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

Список литературы

1. [Brownlee, 2005] Jason Brownlee. Clonal selection theory and Clonalg : the clonal selection classification algorithm (CSCA) // Technical Report, Swinburne University of Technology, January 2005

2. [De Castro et al., 2000] De Castro L. N. & Von Zuben F. J. The Clonal Selection Algorithm with Engineering Applications // GECCO'00 Workshop Proceedings, 2000.

3. [Dick, 2005] Grant Dick. A Comparison of Localised and Global Niching Methods // SIRC 2005 - The 17th Annual Colloquium of the Spatial Information Research Centre, 2005.

4. [Garain et al., 2006] Garain U., Chakraborty M. P., and Dasgupta D. Recognition of handwritten Indic script digits using clonal selection algorithm // 5th Int. Conf. on Artificial Immune Systems (ICARIS), 2006

5. [Ji et al., 2004] Ji Zhou, Dasgupta Dipankar. Real-Valued Negative Selection Algorithm with Variable-Sized Detectors // GECCO 2004

6. [Watkins et al., 2002] Watkins A., Timmis J.. Artificial immune recognition system (AIRS): Revisions and refinements // Proceedings of the 1st International Conference on Artificial Immune Systems (ICARIS).

Размещено на Allbest.ru