Содержание к диссертации
Введение
ГЛАВА 1. Общая постановка задачи и метод кодирования предикатов 15
1.1.Общая постановка задачи 15
1.1.1. Общая формулировка 15
1.1.2. Структура алгоритма распознавания 16
1.2.Общий принцип кодирования предикатов 19
1.3.Создание покрытия класса и критерий оптимальности 22
ІАОбработка неизвестных значений признаков 24
1.4.1. Осторожный подход 24
1.4.2. Жадный подход 24
1.5.Расширение границ предиката 25
1.6.0сновные результаты и выводы по главе 1 26
ГЛАВА 2. Структура генетического алгоритма и его адаптация к особенностям задачи 27
2.1.Введение в теорию генетических алгоритмов 27
2.1.1. Оператор селекции 29
2.1.2. Оператор кроссовера 31
2.1.3. Оператор мутации 33
2.1.4. Оператор отбора 33
2.1.5. Старт и завершение ГА 34
2.1.6. Типы генетических алгоритмов 34
2.2.Применение ГА к решению поставленной задачи 39
2.3.Фундаментальная теорема ГА 40
2.4.Исследование характерных особенностей задачи 45
2.4.1. Оценка количества локальных экстремумов задачи 46
2.5. Исследование операторов ГА и их применимости при решении поставленной задачи 51
2.5.1. Оператор кроссовера 52
2.5.1.1. Вероятность сохранения шаблона 53
2.5.1.2. Метод кроссовера, учитывающий взаимное расположение объектов обучающей выборки 55
2.5.1.3. Экспериментальное сравнение различных механизмов кроссовера 58
2.5.2. Размер популяции 62
2.5.3. Вероятность мутации 63
2.5.4. Критерий остановки ГА 63
2.5.4.1. ЭСС-критерий остановки ГА 66
2.5.4.2. Экспериментальное подтверждение адекватности авторского критерия остановки 66
2.6.Основные результаты и выводы по главе 2 74
ГЛАВА 3. Описание алгоритма распознавания 76
3.1.Вычисление оценок за классы 76
3.1.1. Вычисление оценок «по принадлежности снаружи» 77
3.1.2. Вычисление оценок «по частичной принадлежности 78
3.1.2.1. Роль порогового значения 78
3.2.Решающее правило 79
3.2.1. Решающее правило 1 79
3.2.2. Решающее правило 2 79
3.2.3. Тестирование РП1 на задачах распознавания 80
3.2.4. Тестирование РП2 на задачах распознавания 86
3.2.5. Сравнительный анализ РШ и РП2 87
3.3.Основные результаты и выводы по главе 3 88
ГЛАВА 4. Программная реализация алгоритмов и оптимизация затрат машинного времени. оценка сложности алгоритмов 89
4.1. Программная реализация 89
4.2. Оценка сложности алгоритмов 93
4.2.1. Оценка вычислительной сложности обучения 94
4.2.1.1. Экспериментальное подтверждение оценки сложности обучения 99
4.2.2. Оценка вычислительной сложности распознавания 101
4.3.Метод дробления выборки 102
4.4. Основные результаты и выводы по главе 4 105
ГЛАВА 5. Тестирование разработанных методов на прикладных задачах из области распознавания образов 106
5.1.Тестовые задачи 106
5.1.1. Модельная задача 1 106
5.1.2. Модельная задача 2 107
5.1.3. Модельная задача 3 108
5.1.4. Опознавание кредитных карт 109
5.1.5. Распознавание радиосигналов ПО
5.1.6. Распознавание фоновых изображений ПО
5.1.7. Диагностика космической техники 111
5.1.8. Распознавание сортов вин 111
5.1.9. Распознавание изображений автомобилей 112
5.1.10. Диагностика рака груди 112
5.2.Сравнение с другими методами 113
5.2.1. Перечень методов для сравнения 113
5.2.2. Результаты вычислений 116
5.2.3. Модельная задача 2 116
5.2.4. Модельная задача 3 118
5.2.5. Прочие прикладные задачи 119
5.2.6. Прогнозирование типа кристаллической решетки неорганических соединений 121
5.3.Основные результаты и выводы по главе 5 122
Заключение 126
Список использованной литературы
- Структура алгоритма распознавания
- Исследование операторов ГА и их применимости при решении поставленной задачи
- Вычисление оценок «по частичной принадлежности
- Оценка вычислительной сложности обучения
Введение к работе
Распознавание образов - это часть кибернетики, занимающаяся
классификацией объектов при условиях, что информация о классах, к
которым объекты могут быть причислены, задается наличием априорных
или статистических данных. В стандартной постановке объекты
распознавания имеют векторное выражение в некотором пространстве
вещественных чисел ограниченной размерности.
Длительное время вопросы распознавания рассматривались человеком лишь с позиций методов биологии и психологии. При этом целью изучения являлись в основном качественные характеристики, не позволяющие вскрыть и точно описать соответствующий механизм. И только кибернетика позволила ввести в изучение психологического процесса распознавания образов, лежащего в основе принятия любых решений, количественные методы, что открыло принципиально новые возможности в исследовании и проектировании автоматических систем распознавания.
В течение достаточно продолжительного времени проблема распознавания привлекала внимание специалистов в области прикладной математики, а затем и информатики. Так можно, в частности, отметить работы Р.Фишера, выполненные в 20-х годах и приведшие к формированию дискриминантного анализа, как одного из разделов теории и практики распознавания. В 40-х годах А.Н.Колмогоровым и А.Я.Хинчиным поставлена задача о разделении смеси двух распределений. Наиболее плодотворными явились 50-60-е годы XX века. В это время на основе массы работ появилась теория статистических решений. В результате были найдены алгоритмы, обеспечивающие отнесение нового объекта к одному из заданных классов, что явилось началом планомерного научного поиска и практических разработок. В рамках кибернетики начало
формироваться новое научное направление, связанное с разработкой теоретических основ и практической реализации устройств, а затем и систем, предназначенных для распознавания объектов, явлений, процессов. Это направление и получило название «распознавание образов».
К настоящему времени разработано несколько основных направлений в теории распознавания, объединяющих сотни конкретных алгоритмов и методов. В качестве таковых следует отметить перцептрон Розенблата [24], метод потенциальных функций [1], статистические модели распознавания [в, 34], модели распознавания, основанные на построении кусочно-линейных (или более сложных) разделяющих поверхностей в признаковом пространстве [3, 23], алгоритмы, основанные на построении решающих деревьев [5, 22, 31], структурные (лингвистические) методы [33], модели частичной прецедентности [2, 4, 10, 11], алгебраический подход [10], нейросетевые алгоритмы [39], основанные на теории нечетких множеств методы [40], и другие. Основанные на различных идеях, гипотезах и принципах, а также их сочетаниях, они имеют свои достоинства и недостатки, различные требования к исходным данным, ограничения на области применения.
Рассматривается задача создания распознающих алгоритмов, основанных на поиске логических закономерностей объектов, представленных в виде параллелепипедов в n-мерном признаковом пространстве, создания процедур голосования по этим закономерностям, а также некоторые смежные вопросы анализа данных. Кроме того, проводится всесторонний анализ применения генетических алгоритмов различных типов, дается представление об оптимальном конструировании генетических алгоритмов, наиболее приспособленных для решения задач представленного рода.
В данной работе приводится демонстрация эффективности разработанных алгоритмов обучения и распознавания, доказывается обоснованность использования ГА в качестве оптимизационного метода в обучении по логическим закономерностям, а также проводится поиск и исследование закономерностей, связывающих параметры задачи и параметры генетического алгоритма, которые обеспечивали бы наилучшую сходимость последнего при решении задач рассматриваемого рода.
Одной из основных проблем, с которыми можно столкнуться при решении задачи поиска логических закономерностей в признаковом пространстве, является исключительно большое количество локальных экстремумов задачи, а также специфическое распределение значений критерия оптимальности на области определения. Это накладывает определенные ограничения и дополнительные требования на методы решения таких задач. Данный вопрос с разных сторон проанализирован в работе и предложены соответствующие изменения в генетические операторы и схему кодирования, позволяющие обойти возникающие сложности.
Проведенные эксперименты на таблицах данных, взятых из реальных, прикладных задач распознавания образов [12,14], показали высокое качество предложенного метода по сравнению с другими алгоритмами распознавания [12, 84, 85]. Представленные в работе методы могут быть применены и в решении задач, традиционно решаемых численными методами, таких как прогнозирование поведения речных систем, вычислительных сетей, свойств химических соединений [14,16,17, 29].
Данная задача является актуальной вследствие повышенного интереса в научной среде к методам интеллектуального анализа данных: кластеризации, классификации, прогноза и т.д. Растущие потребности
прикладных наук, а также электронной промышленности требуют решения все большего количества задач данного типа. Построение надежных алгоритмов классификации позволяет решать такие важные задачи как распознавание изображений и рукописных шрифтов, распознавание болезней по медико-диагностическим данным, распознавание типов радиосигналов для радиотелескопов, прогнозирование свойств химических соединений, проектирование алгоритмов для сенсорных систем, создание спам-фильтров для почтовых клиентов и многие другие.
Цель работы и задачи исследования. Целью данной диссертационной работы является разработка и исследование генетических алгоритмов обучения в моделях вычисления оценок, обоснование эффективности данного подхода, а также создание новых решающих правил распознавания.
Методы исследований. В работе использованы методы теории множеств, теории алгоритмов, теории генетического поиска, теории оптимизации, теории вероятности и математической статистики.
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях и семинарах:
Математические Методы Распознавания Образов ММРО-11 (Пущино 2003);
7th International Conference on Pattern Recognition and Image Analysis PRIA-7 (St. Petersburg, Russian Federation 2004);
Научные конференции МФТИ (Долгопрудный, 2005-2006);
Технологии Microsoft в теории и практике программирования (Москва, 2005);
6th WSEAS Int. Conf. on Applied Computer Science ACS06 (Tenerife, Canary Islands, Spain 2006);
Научные семинары кафедр вычислительной математики и информатики МФТИ (Долгопрудный, 2003-2007);
Научные семинары отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного центра РАН (Москва, 2004-2007).
Публикации
По теме диссертации опубликовано 8 работ, в том числе одна из списка изданий, рекомендованного ВАК РФ.
Кратко изложим основное содержание работы.
В первой главе приводится общая постановка задачи распознавания образов по прецедентам. Вводятся понятия логической закономерности, критерия оптимальности, допустимого предиката. Описывается общая схема процесса классификации с учителем. В п. 1.2 представлено некоторое подмножество множества параллелепипедов в признаковом пространстве, на котором предлагается в дальнейшем проводить поиск логических закономерностей. Показано, что при некоторых ограничениях на вид критерия оптимальности, данное сужение области поиска не ведет к потере оптимальных решений. В п. 1.3 представлена модификация критерия оптимальности предикатов, позволяющая создавать полное покрытие класса оптимальными предикатами за ограниченное количество итераций. Суть модификации заключается в том, что критерий оптимальности предиката приравнивается к нулю, если предикат не содержит ни одного объекта, не вошедшего в ранее найденные предикаты. В п. 1.4 описывается процесс обработки неизвестных значений признаков на основе жадного подхода. Считается, что точка с неизвестным значением признака принадлежит любому отрезку либо интервалу. Кроме того, отрезок либо интервал, одним из концов которого является точка с
неизвестным значением, автоматически расширяется до всей предметной оси.
Во второй главе дается обзор генетических операторов и наиболее известных современных имплементаций ГА. Представлена схема работы генетического алгоритма. Представлены функции кодирования и декодирования, связывающие пространство предикатов с бинарным пространством размерности N, где N - число объектов в рассматриваемом классе. Данные функции позволяют проводить поиск оптимальных предикатов посредством генетического поиска глобального экстремума целевой функции, определенной в бинарном пространстве. В п. 2.4 дан обзор характерных особенностей рассматриваемой задачи, а также дана теоретическая оценка количества локальных экстремумов для определенного подкласса задач. Приводится сравнение экспериментальных результатов и теоретической оценки количества локальных экстремумов. В п. 2.5.2.1 предлагается новый метод кроссовера, учитывающий взаимное расположение объектов друг относительно друга и осуществляющий скрещивание хромосом по вероятностным правилам, основанным на расстояниях между объектами выборки. Предложены механизмы автоматического выбора размера популяции и коэффициента мутации в зависимости от параметров задачи. В п. 2.5.4 предложен комплексный критерий остановки ГА. В отличие от «стандартных» критериев остановки, завершающих работу ГА после выполнения определенного количества итераций либо после выполнения некоторого числа итераций без улучшения лучшей ЦФ популяции, предложенный критерий адаптируется к конкретной задаче. Это позволяет сократить количество итераций для простых, малоэкстремальных задач и повысить при решении сложных.
Третья глава посвящена описанию процедуры распознавания. Описан процесс вычисления оценок за классы и голосования по оценкам.
Предложено 2 новых метода вычисления оценок за классы. Согласно первому из предложенных методов, при проверке вхождения объекта в предикат некоторого класса, следует создать на основе данного объекта и предиката расширенный предикат и проверить, является ли он допустимым. Второй предложенный метод оценки производит расчет общего количества признаковых интервалов предиката, которым удовлетворяет распознаваемый объект. Данное число учитывается в расчете общей оценки, если оно превышает некоторое пороговое значение.
Предложено два новых решающих правила, учитывающих сразу три оценки за классы - «традиционную» оценку, учитывающую количество вхождений распознаваемого объекта в предикаты, а также две предложенные в работе оценки. Тестирование на прикладных задачах показало, что каждое из решающих правил работает существенно лучше, чем метод простого голосования по любой отдельно взятой оценке за класс. Кроме того, представленные решающие правила обладают некоторым набором достоинств и недостатков друг относительно друга, определяющимися условиями задачи.
Четвертая глава содержит детали программной реализации предложенных алгоритмов. Алгоритмы реализованы автором в программе «Genesis» на языке Фортран-95, а также в качестве модуля в программном комплексе «Recognition» на языке Visual C++ 6.0. Программа «Genesis» позволяет пользователю строить генетический алгоритм, варьируя типы генетических операторов, а также все значимые параметры ГА. Кроме того, включена возможность построения новых решающих правил на основе оценок за классы. Дана спецификация форматов входных данных.
Также в четвертой главе проведен теоретический анализ вычислительной сложности алгоритмов обучения и распознавания. Полученные оценки сравнивались с экспериментальными данными.
Для уменьшения затрат машинного времени при решении задач с большим числом объектов N предложен метод дробления выборки. Предлагается вместо единичного процесса обучения на выборке размера N проводить многократное обучение на случайных подвыборках фиксированного размера. Дана теоретическая оценка необходимого количества повторов обучения и итоговая оценка вычислительной сложности подобного метода.
В пятой главе представлены результаты тестирования разработанных методов на прикладных задачах из области распознавания образов. Дан сравнительный анализ качества распознавания для авторского метода и для методов распознавания, реализованных в программном комплексе «Recognition». Большинство из представленных к сравнению методов основаны на широко известных «классических» методах классификации - К ближайших соседей, линейный дискриминант Фишера, алгоритм вычисления оценок, перцептрон Розенблата и проч. Практически на всех представленных прикладных задачах авторский метод дал стабильно высокие результаты, а для некоторых задач результаты распознавания авторским методом оказались наилучшими среди представленных алгоритмов.
Научная новизна работы заключается в следующем:
Для процесса обучения в моделях вычисления оценок предложен новый способ представления логических закономерностей.
Разработан алгоритм генетического поиска экстремума критерия оптимальности предикатов. Исследована роль параметров генетического алгоритма при решении данной задачи.
Для генетического алгоритма создана новая модель кроссовера, учитывающая особенности взаимного расположения объектов обучающей выборки.
Для задач с неразличимыми классами получена теоретическая оценка количества локальных экстремумов критерия оптимальности.
Разработаны новые типы оценок объекта за классы и построены решающие правила для этих оценок.
Практическая ценность работы заключается в том, что предложенные математические модели и алгоритмы могут быть успешно применены для решения задач классификации и прогнозирования. С помощью разработанного автором программного комплекса были получены решения многих прикладных задач, в частности задачи прогнозирования типа кристаллической решетки неорганических соединений. Эти результаты могут быть в дальнейшем использованы при создании новых химических соединений для микроэлектронной промышленности. Данный программный комплекс используется в учебном процессе кафедры информатики Московского физико-технического института в качестве демонстрационного пособия по предмету «Методы анализа данных и распознавания».
Личный вклад:
Постановка задач диссертационного исследования выполнена автором совместно с А.С. Холодовым и В.В. Рязановым.
Разработка процедуры кодирования и генетического поиска логических закономерностей проведена автором.
Теоретическая оценка количества локальных экстремумов задачи поиска логических закономерностей получена автором.
Стратегия кроссовера, учитывающая взаимное расположение объектов выборки, разработана и протестирована автором.
Новые способы получения оценки объекта за классы, а также соответствующие решающие правила разработаны и протестированы автором.
6. Решение задачи прогнозирования типа кристаллической решетки неорганических соединений получено автором с помощью представленных в диссертационной работе алгоритмов. Постановка задачи принадлежит Н.Н.Киселевой.
Основные положения, выносимые на защиту:
Процедура кодирования и генетического поиска логических закономерностей в признаковом пространстве.
Теоретическая оценка количества локальных экстремумов задачи поиска логических закономерностей для выборок с неразличимыми классами.
Новая стратегия кроссовера, выполняющая процедуру скрещивания с учетом взаимного расположения объектов выборки друг относительно друга.
Способы построения оценок объекта за классы и основанные на данных оценках решающие правила.
Результаты решения задачи прогнозирования типа кристаллической решетки неорганических соединений.
Автор выражает глубокую благодарность научному руководителю, члену-корреспонденту РАН, доктору физико-математических наук профессору А.С. Холодову, а также научному консультанту, доктору физико-математических наук профессору В.В. Рязанову за помощь в написании работы, ценные советы, замечания и доброжелательную критику.
Структура алгоритма распознавания
Для каждого допустимого предиката Pi класса Кл можно построить единственный набор объектов обучающей выборки i={ kV k2 " km} кіЄ Л УДОвлетвоРЯЮЩИЙ СЛЄДУЮЩИМ УСЛОВИЯМ (особо отметим, что данный набор объектов обучения может быть пустым): \fkt{kvk2,..,km) Pi{Sk) = V Фактически, этот набор представляет собой список тех объектов класса Кл, которые находятся внутри параллелепипеда, соответствующего предикату Рг Каждому предикату соответствует единственный набор объектов, удовлетворяющий (1.5). Далее, каждому набору объектов обучающей выборки i = rkv k2 "- km} kie A можно поставить в соответствие предикат PN(S) = giP(clj,cj,Xj),j=\2,...,n, построенный следующим образом: в качестве верхних и нижних границ cl.,cj по каждому признаку возьмем соответственно наибольшее и наименьшее значение данного признака, взятое по всем объектам набора N TO есть: c)=Min(X;) с?=Мах(х;) (1.6)
Данную проекцию доопределим для пустого набора N,={0}, ему соответствует предикат Р0, который по определению не выполняется ни в одной точке признакового пространства. Для каждого допустимого предиката Р класса Кх найдется предикат Р такой, что Р удовлетворяет условиям (1.6) и наборы Ni объектов класса Кл, на которых выполняются предикаты Р и Р соответственно, идентичны. Таким образом, если критерий оптимальности р предиката зависит только от набора объектов, на которых выполняется предикат (p = (p iS/.S eK Py:1 ,c2 ,S\=\\ (что, в частности, верно для стандартного критерия оптимальности (1.4), то для любого предиката типа (1.3) найдется предикат типа (1.6) с тем же значением критерия оптимальности.
В дальнейшем предлагается рассматривать только множество предикатов, удовлетворяющих условию (1.6) для некоторого набора объектов, дополненное предикатом Р0 [15]. Назовем это множество G.
Если положить количество объектов обучения в классе Кя за Мл, то набор объектов Nt можно взаимно однозначным образом представить в виде бинарного вектора размерности Мя, где на k - й позиции стоит "1", если объект Sk є Nj и "О", если Sk Nt. Таким образом можно построить проекцию (функцию декодирования): f:Z-+G (1.7) из пространства бинарных векторов длины А/д (пространство представлений) в пространство предикатов типа (1.6). Очевидно, что для каждого объекта Р є G существует представление Н( е 1 такое что Функцию кодирования g:G l (1.8) определим следующим образом - значением функции кодирования от предиката является бинарный вектор, на і-и позиции которого стоит "1", если объект Р(,.) = 1 и "О", если Р(,) = 0. При этом верно следующее: /( (ф (1-9)
На рис. 1.2 показан принцип построения предикатов, впервые сформулированный в [15]. Точками обозначены объекты рассматриваемого класса, крестиками - объекты остальных классов. На рис. 1.3 изображены объекты двух классов, причем объекты первого класса пронумерованы, что позволяет проводить расчет функции кодирования и декодирования. Значением функции кодирования от изображенного на рис. 1.3 предиката будет являться бинарная строка fill 110], а сам изображеный предикат будет являться значением функции декодирования от строк (111110), (110110),(111010),(110010).
Каждый предикат типа (1.6) можно записать в виде бинарной строки, длина которой равна количеству объектов в рассматриваемом классе. «Истина» в п—ой ячейке строки означает, что п-ый объект входит в набор N; =\Sj «ложь» - что не входит. (Примечание: если объект не входит в набор Nt, это не означает, что он не может находиться внутри предиката, построенного на наборе N;).
Предположим, что существует некоторый набор предикатов Gx={Pl\ класса Кя. Назовем набор Gx покрытием класса Кл, если для каждого объекта обучающей выборки St є Кл верно следующее: 3i:PJS) = l, то есть каждый объект обучающей выборки, принадлелажий классу Кл, содержится хотя бы в одном предикате из покрытия Gx. При создании покрытия Gx введем нумерацию предикатов, составляющих покрытие и переопределим критерий оптимальности (1.4) следующим образом [15]: р(Р,( , ?,х))= :SjeKvPi(c\c2,Sj) = l}\,ecJw 3/ :V/ /- .(c1,c2,5 y.)=l,P/(c1,c2, ) = 0,M//a4e (1.10) р(І)(( , ?,х)) = 0 Условие (1.10) означает, что значение критерия оптимальности предиката равно значению стандартного критерия оптимальности (1.4), если предикат содержит хотя бы 1 объект, не содержащийся в ранее найденных предикатах данного покрытия и равно нулю в противном случае. Когда на каждом из объектов класса Кх будет будет выполняться хотя бы один из найденных предикатов, покрытие класса считается созданным и алгоритм обучения переходит к следующему классу.
Исследование операторов ГА и их применимости при решении поставленной задачи
Генетический алгоритм как динамическая система обладает сильной зависимостью скорости сходимости к решению от выбранных параметров. К тому же, свои ограничения и корректировки вносят особенности рассматриваемой задачи, рассмотренные в п. 2.4. В рамках данной работы была исследована зависимость скорости сходимости и точности результатов ГА от следующих параметров и свойств: коэффициент мутации, размер популяции, вероятность скрещивания, тип процедуры селекции, тип кроссовера, наличие или отсутствие отбора, вид ценовой функции, размер промежуточной (дочерней) популяции при наличии процедуры отбора и т.д. Основываясь на проведенных исследованиях, можно уверенно строить генетические алгоритмы для решения задач рассматриваемого класса, обеспечивающие высокую скорость и точность на самом широком круге практических задач. 2.5.1 Оператор кроссовера
Оператор скрещивания (оператор кроссовера, ОК) является основным оператором в генетическом алгоритме (ГА) и используется для получения хромосом потомков путем рекомбинации родительских хромосом. Одним из главных аргументов в пользу использования этого оператора является возможность рекомбинации параметров решений, представленных различными особями. В терминах гипотезы о строительных блоках (building blocks hypothesis) [54], посредством кроссовера осуществляется поиск новых строительных блоков и смешивание уже существующих. В большинстве ГА используются наиболее простые варианты кроссовера с количеством точек разрыва 1 или 2. Как правило, этот выбор базируется на эмпирических и теоретических соображениях ранних работ в области ГА ([47, 58]). Однако впоследствии
ряд основанных на эмпирических данных работ показал, что для некоторых задач может быть выгодным использование большего количества точек разрыва ([52, 81]). Также неожиданным (с традиционной точки зрения на ГА как природный механизм) для исследователей оказался тот факт, что для некоторых задач предпочтительным является использование однородного кроссовера [81]. В работах [80, 81] был проведен анализ дизруптивной способности различных типов кроссовера, а в [48] представлены эмпирические результаты, согласно которым размер популяции ГА существенно влияет на предпочтительность того или иного типа кроссовера. Для приведенного в статье класса задач при малых популяциях (до 50) более предпочтительным был однородный кроссовер, а при больших размерах популяции - двухточечный. 2.5.1.1 Вероятность сохранения шаблона
Согласно [49] вероятность сохранения в результате рекомбинации шаблона Я порядка к длины Z, определяется следующим рекуррентным соотношением:
Де Йонгом для учета вероятности скрещивания родительских хромосом с совпадающими разрядами в определяющих позициях шаблона. Обозначим множество из к определяющих позиций шаблона Я через К, а подмножество этих позиций через X, тогда можно вычислить Cks следующим образом [49]: deX deK-X deK где peq{d) вероятность того, что обе родительские хромосомы имеют одинаковые разряды в определяющей позиции d. При дополнительном условии, что \/deК:peq(d) = peq, соответствующему началу эволюционного поиска, когда разряды в каждой позиции хромосомы принимают различные значения с одинаковой вероятностью, имеем: См =/?J + р " -/? . В частности, для бинарных хромосом при к = 2: C2tS=2peg-Peq2=0.75
Вероятность, что некоторый генетический оператор разрушит некоторый шаблон в хромосоме, называется дизруптивностью оператора и является одной из его важнейших характеристик.
Несмотря на то, что к настоящему времени предложено множество операторов скрещивания [38], наиболее часто используются «классические» 1-, 2-, и-точечный [47] и однородный ОК [81]. Однако, эти операторы не лишены недостатков. В частности, недостатками 1, 2 и 72-точечного ОК являются: - Зависимость вероятности сохранения шаблона длины Z, от длины хромосомы L (зависимость от величины отношения -!-) [49].
Зависимость обуславливается наличием позиционной неопределенности (positional bias) [51] известной также как неопределенность расстояния (length bias) [49]. - Зависимость результата скрещивания от порядка следования параметров в хромосоме, что весьма актуально в условиях рассматриваемой задачи, когда закодированные в хромосоме параметры имеют различный вес при вычислении ЦФ. Кроме того, взаимное расположение в хромосоме генов со значением «true» играет исключительно важную роль, так как наличие или отсутствие одного такого гена может определять разницу между хромосомой с наивысшей ЦФ в популяции и хромосомой с ЦФ=0. 2.5.1.2 Метод кроссовера, учитывающий взаимное расположение объектов обучающей выборки
В данной работе предложен и исследован новый метод кроссовера, который позволяет учитывать особенности задачи, а именно попарную взаимосвязь различных генов хромосомы, которая определяется взаимным расположением двух объектов обучающей выборки и расположением чужих объектов относительно них.
Основная предложенная идея заключается в следующем - каждый раз при процедуре кроссовера хромосомы меняются не просто случайными участками, а некоторой группой объектов, которые в признаковом пространстве располагаются близко друг от друга. Попробуем пояснить терминологию данного предложения. Пусть известны расстояния между каждой парой объектов обучающей выборки р (X,Y) = px(Y) = pr(X).
Вычисление оценок «по частичной принадлежности
После большого количества экспериментов в процессе исследования эмпирически установлено, что наилучшим порядком приоритетов следует считать (в порядке убывания приоритета) G\G\G2 . Каноническая оценка
G1 является наиболее надежной и традиционно применяется в алгоритмах распознавания, однако дает достаточно высокий процент отказов ввиду того, что найденные предикаты могут покрывать далеко не все признаковое пространство, кроме того, один объект контрольной выборки может попасть в одинаковое количество предикатов разных классов. Оценка G1 также обладает высокой степенью надежности, однако, на ряде многопараметрических задач с наличием неизвестных значений признаков поведение данной оценки непредсказуемо. Оценка G3 на широком ряде задач дает наилучшие результаты и почти никогда не дает отказов от распознавания, однако ввиду слабого теоретического обоснования данной оценки на данный момент ее приоритет в решающем правиле не является наивысшим.
Ниже приводятся примеры использования предложенного решающего правила на искусственных и практических задачах распознавания. В качестве порогового значения оценки 3 типа бралось
Решающее правило 2 (РП2) имеет как свои достоинства по сравнению с решающим правилом 1 (РП1), так и недостатки. Среди достоинств решающего правила можно отметить следующие: - РП2 учитывает всю информацию, содержащуюся в оценках трех типов за различные классы, в то время как РП1 часто игнорирует значения некоторых из оценок. Это может проявляться в задачах с тремя и более классами. Приведем пример. Пусть G1 (S) = (Oil) ("отказ"), G2(S) = (oy2l) ("3 класс"), G (S) = (y2 Оо)("1 класс"). Согласно РП1 объект принадлежит 1 классу. Тем не менее, если взглянуть на общий вид оценок, 2 метода из 3-х высказались против первого класса, и такое решение является наименее логичным. РП2 в данном случае относит объект к 3 классу.
Посредством скользящего контроля значения коэффициентов а могут быть адаптированы для решения конкретной задачи, в то время как РП1 в этом плане является более жестким и не содержит степеней свободы кроме позиций приоритета. РП2 в сравнении с РП1 также обладает несколькими недостатками: - РП1 отличается гораздо большей надежностью в случаях, когда один из типов оценки G],Gf,Gf теряет адекватность ввиду особенностей задачи.
Такое может случаться в задачах с количеством классов 3 и более, для которых количество объектов в разных классах существенно отличается (в разы и десятки раз).
В случае, когда все 3 метода оценки G\G2,G3 относят объект к различным классам, РП2 может отнести объект к некоторому новому классу, за который, в случае отдельного голосования по оценкам трех типов, не было бы подано ни одного голоса. 3.3 Основные результаты и выводы по главе 3
1. Предложены 2 новых метода построения оценки объекта за класс. Первый из предложенных методов оценивает на допустимость наименьший предикат, который включает в себя распознаваемый объект и предикат, созданный в процессе обучения. Второй из предложенных методов оценивает объект на основании количества признаковых ограничений, по которым распознаваемый объект удовлетворяет предикатам некоторого класса.
2. Предложены решающие правила, определяющие к какому классу относить распознаваемый объект на основании различных оценок объекта за классы. Проведены многочисленные эксперименты, продемонстрировавшие качество и надежность разработанных решающих правил и оценок на различных задачах. Показано, что оба решающих правила существенно превоходят канонический алгоритм голосования по оценкам (3.1).
Оценка вычислительной сложности обучения
Как было показано в приведенных выше примерах, рост машинного времени, необходимого для выполнения процесса обучения, настолько резко зависит от объема обучающей выборки, что уже при значениях N, близких к тысяче, затраты машинного времени становятся неадекватно большими и требуется поиск средств, способных ускорить работу алгоритма. Для этого предлагается использовать следующий описанный ниже прием.
Суть метода дробления выборки такова: вместо выполнения одного процесса обучения на выборке размера N алгоритм проходит процесс обучения S раз на подвыборках обучающей выборки размера Ns. Каждый раз подвыборка обучающей выборки определяется заново случайным образом, но так, чтобы доля объектов, принадлежащих разным классам, сохранялась. Объединение результатов каждого из запусков процесса обучения, представленных в виде наборов предикатов, является, таким образом, общим результатом обучения. При распознавании объектов учитываются все из найденных в запусках предикатов.
Произведем оценку необходимого количества запусков при заданном размере подвыборки Ns, при которых вероятность, что каждый из объектов обучающей выборки хотя бы раз войдет в одну из подвыборок, составит некоторое доверительное значение r\. Положим /л за отношение размера обучающей выборки к размеру подвыборки. Очевидно, вероятность для некоторого объекта не войти в некоторую выборку равна Pl=l-M (4.6) Вероятность для объекта не войти во все выборки, таким образом, ps = (l-M)S (4.7) При /л D S можно использовать следующую оценку:
Отсюда получим выражение для вероятности, что какой-то один объект войдет хотя бы в одну выборку и для вероятности того, что каждый объект войдет хотя бы в одну выборку: g l-cxp(-juS) (4.9) \N gN l-cxp(-juS)] Подставив в (4.9) значение доверительной вероятности и учитывая, что 1JU 1, можно произвести следующие выкладки: \VN , , иП-яІ/лЦ-я) ( Х-тЛ «exp (4.10) N l-exp(-//5) = (l-(l-7)) =(1-(1-7)) 1-/7 Учитывая, что величина —TT -Q 1, выразим из (4.10) искомую величину S ( 1- N 1-/7 =Iln 1-ехр S = --\n (4.11) li fl-7 N )) [N ) и
Формула (4.11) дает необходимое количество повторов процесса обучения на подвыборках обучающей выборки, при которых можно утверждать, что с вероятностью rj каждый объект обучающей выборки вошел в одну из подвыборок. Оценим, какой суммарный выигрыш во времени счета даст предложенный метод для N=1000 и для N = 10000 с размером подвыборки Ns =100. Будем полагать далее, что rj - 0.9.
Первый случай. Общее количество машинных операций, согласно оценке (4.5) при N=1000 будет порядка 25000Л075. При использовании алгоритма дробления выборки с ju = — общее количество операций для единичного процесса обучения составит 25000И05, а оценка (4.11) даст количество повторов 5 = 101п (10000) = 401nl0 « 80, итого общее время счета сократится примерно в 4 раза. Второй случай. Общее количество машинных операций, согласно оценке (4.5) при N=10000 будет порядка 250001010. При использовании алгоритма дробления выборки с ju = j — общее количество операций для единичного процесса обучения составит 2500CQ05, а оценка (4.11) даст количество повторов S = 1001n(l00000) = 5001nl0 1000, итого общее время счета сократится примерно в 100 раз.
В качестве иллюстрации работы метода дробления выборки была взята широко известная задача распознавания, связанная с установкой режимов работы радиаторов Шаттла [87]. Данные для задачи получены Jason Catlett of Basser Department of Computer Science, University of Sydney, N.S.W., Australia.
Задача содержит 7 классов (режимов работы), причем 80% объектов относятся к первому классу. Отделимость классов очень высокая и доходит практически до 100%. Каждый объект описывается 9-ю вещественнозначными признаками. В обучающей выборке содержится 43500 объектов, в контрольной выборке содержится 14500 объектов. В связи с исключительно высокой отделимостью классов для оценки количества операций следует применять оценку (4.4) с а = 0. При размере подвыборки 100 для одного запуска процесса обучения имеем, согласно (4.4), Г = О(150ЭЗ2) = О(107) операций. Количество повторов 5, = 4351п(4.35 106)«5000.
Похожие диссертации на Разработка и исследование генетических алгоритмов обучения в моделях вычисления оценок
