Часть 15.

Этот результат получен с учетом того, что для векторного аргумента [-4; 4; -4] значение пороговой функции равно [-1; 1; -1 ]. Вычислим значение компонентов вектора X.

После применения пороговой функции получим исходный вектор [1; 1; 1;-1]. Поскольку при обработке этого вектора получается устойчивый результат, может показаться, что мы выявили еще одну пару эталонных векторов. Однако на самом деле рассмотренный пример является дополнением ко второй паре эталонов <Х2, Y2>. Это еще раз подтверждает, что в сети ДАП для каждой пары прототипов ее дополнение тоже является эталоном. Следовательно, в сети ДАП записаны еще два прототипа

Выберем вектор из окрестности одного из эталонов, например Х=[1; -1; 1; -1]. Заметим, что хеммингово расстояние от этого вектора до ближайшего эталона составляет 1. Инициализируем случайным образом вектор Y=[-1;-1;-1]. Вычислим значения нейронов второго слоя сети

Напомним, что по определению пороговой функции, приведенному в конце подраздела 10.6.2, для. Поскольку первый и третий элементы вектора Yt

были инициализированы случайным образом значением -1, то Y=[-1; 1; -1]. Теперь снова вычислим значение X.

Применяя пороговую функцию, получим вектор Х=[1; 1; 1; -1]. Повторяя этот процесс, снова вычислим вектор Y

В результате применения пороговой функции получим Y=[-1; 1;-1]. Этот вектор идентичен предыдущему, следовательно, сеть перешла в устойчивое состояние. Таким образом, после двух проходов по сети ДАП ближайший к Х4 образ совпал с сохраненным в сети эталоном. Точно так же можно восстановить изображение лица или любое другое изображение при отсутствии или искажении части информации. Хеммингово расстояние между исходным вектором Х=[1; -1; 1; -1] и прототипом Х4=[1; 1; 1; -1] равно 1. Поэтому неудивительно, что сеть пришла к состоянию <Х4, Y4>.

В рассмотренном примере обработка данных начиналась с вектора X. Естественно, можно действовать и в обратном направлении, восстанавливая вектор X по исходному вектору Y.

476 Часть IV. Машинное обучение

В работе [Hecht-Nielsen, 1990] приводятся интересные результаты анализа сети ДАП. Там показано, что свойство ортонормальности, необходимое для линейной ассоциативной сети, для сети ДАП является слишком ограничительным. Автор показывает, что для построения сети требуется лишь линейная независимость векторов, чтобы ни один из векторов в пространстве эталонов не представлял собой линейную комбинацию других.

10.6.4. Автоассоциативная память и сети Хопфилда

Нейросетевые архитектуры получили всеобщее признание во многом благодаря исследованиям Джона Хопфилда, физика из Калифорнийского технологического института. Он изучал свойства сходимости сетей на основе принципа минимизации энергии, а также разработал на основе этого принципа семейство нейросетевых архитектур. Как физик Хопфилд рассматривал вопросы устойчивости физических объектов с точки зрения минимизации энергии физической системы. Примером такого подхода является моделирование отжига и охлаждения металлов.

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

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

Матрица весов для автоассоциативной сети, в которой хранится набор эталонных

векторов {X1, Х2 Хn}, создается по правилу

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

Глава 10. Машинное обучение на основе связей 477

Как и при работе с сетью ДАП, матрица весов строится на основе запоминаемых в памяти образов. Продемонстрируем это на простом примере. Рассмотрим три эталонных вектора

Вычислим матрицу весов по формуле

или

Будем использовать пороговую функцию

Сначала проверим результат работы сети для одного из эталонов Х3= [1;1;-1;1;1]. Получаем

а после применения пороговой функции приходим к состоянию [1; 1; -1; 1; 1]. Таким образом, при подаче в сеть этого вектора она сразу же сходится к нему. Это значит, что эталоны сами являются устойчивыми состояниями, или аттракторами.

Теперь проверим следующий вектор, хеммингово расстояние от которого до эталона Хз равно единице. Сеть должна сойтись к этому эталону. Это означает извлечение из памяти образа по частично искаженным данным. Выберем Х= [ 1; 1; 1; 1; 1 ]:

После применения пороговой функции приходим к вектору Х3 = [ 1; 1; -1; 1; 1 ].

Рассмотрим третий пример, выбрав на этот раз вектор, расстояние от которого до ближайшего прототипа равно 2, допустим, Х= [ 1; -1; -1; 1; -1 ]. Не сложно убедиться, что этот вектор находится на расстоянии 2 от вектора Х3, на расстоянии 3 от вектора X1 и 4 от Х2. Вычислим произведение

а после применения пороговой функции получим [ 1; -1; -1; 1; 1]. Это состояние не является устойчивым, поэтому вычислим

[1;-1;-1; 1; 1] * W= [9; -3; -7; 7; 9],

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

478 Часть IV. Машинное обучение

является дополнением к исходному прототипу Х2=[-1; 1; 1; -1; -1 ]. Как и в гетероассоциативной сети ДАП, аттракторами автоассоциативной сети являются как исходные прототипы, так и их дополнения, т.е. в данном случае сеть имеет шесть аттракторов.

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

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

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

При такой архитектуре для получения сети Хопфилда необходимо обеспечить лишь одно дополнительное ограничение. Если wij - это вес связи от узла i к узлу j, то весовые коэффициенты в сети Хопфилда должны удовлетворять условию

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

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

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

Глава 10. Машинное обучение на основе связей 479

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

Учитывая определение функции Н, получим

Поскольку для, то слагаемые, не содержащие хк, можно исключить.

Получим

Учитывая тот факт, что wii=0 и Wij=Wji, приходим к соотношению

Чтобы показать отрицательность АН, рассмотрим два случая. Сначала предположим, что значение хk изменилось с -1 на +1. Тогда множитель в квадратных скобках должен быть положительным. Поскольку, то DН отрицательно. Теперь предположим, что значение хк изменилось с 1 на -1. Тогда по тем же причинам DН отрицательно. Если же xк не изменялось, тои DН= 0.

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

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

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

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

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

480 Часть IV. Машинное обучение

вектору. С этим связано неудобство их использования для реализации контекстно адресуемой памяти. В-третьих, при использовании сетей Хопфилда для решения задач оптимизации не существует общего метода построения отображения ограничений в функцию энергии Хопфилда. И, наконец, существует предельное значение общего количества минимумов энергии, которые можно сохранить в сети и извлечь из нее, и это число нельзя установить точно. Эмпирическое тестирование таких сетей показывает, что количество аттракторов составляет лишь малую часть общего числа узлов в сети. Этот и другие связанные с ним вопросы активно изучаются в работах [Hecht-Nielsen, 1990], [Zurada, 1992] и [Freeman, Skapura, 1991].

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

10.7. Резюме и дополнительная литература

В этой главе были рассмотрены вопросы обучения в сетях связей. В разделе 10.1 они описаны с исторической точки зрения. Для более подробного ознакомления с этими вопросами мы рекомендуем ознакомиться с работами [McCulloch, Pitts, 1943], [Selfridge, 1959], [Shannon, 1948], [Rosenblatt, 1958]. Важно также изучить физиологические модели, особенно предложенные Дональдом Хеббом [Hebb, 1949]. Наука о познании продолжает исследовать взаимосвязи между обучением и структурой мозга. Эти вопросы описаны в [Ballard, 1997], [Franklin, 1995], [Jeannerod, 1997] и [Elman и др., 1996].

За рамками рассмотрения остались многие важные математические и вычислительные аспекты сетей связей, описанные в работах [Hecht-Nielsen, 1990], [Zurada, 1992] и [Freeman, Skapura, 1991].

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

Сеть прямого распространения - одна из наиболее распространенных нейросетевых архитектур. Поэтому в этой главе достаточно много внимания уделялось ее истокам, использованию и развитию. Введение в теорию нейронных сетей, а также информация о вычислительных средствах обучения содержится в двухтомнике [Rumelhart и др., 1986б]. Этому же вопросу посвящена работа [Grossberg, 1988].

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

Большинство разработчиков нейросетевых архитектур описали их в своих работах [Anderson и др., 1977], [Grossberg, 1976, 1988], [Hinton и др., 1986], [Hecht-Nielsen, 1989, 1990], [Hopfield, 1982, 1984], [Kohonen, 1972, 1984], [Kosko, 1988] и [Mead, 1989]. Более

Глава 10. Машинное обучение на основе связей 481

современные подходы, в том числе графические модели, описаны в работах [Jordan, 1999], [Frey, 1998]. Можно порекомендовать и хороший современный учебник [Bishop, 1995].

10.8. Упражнения

Постройте нейрон Мак-Калока-Питтса, вычисляющий функцию логического

следования =>.

Постройте персептронную сеть на языке LISP и реализуйте в ней пример задачи

классификации, описанный в подразделе 10.2.2.

Сгенерируйте свой набор данных, аналогичный представленному в табл. 10.3, и

используйте его для решения задачи классификации.

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

Реализуйте сеть прямого распространения на языке LISP или C++ и используйте ее

для решения задачи "исключающего ИЛИ", описанной в подразделе 10.3.3. Решите

эту задачу с помощью нескольких сетей различной архитектуры, например, сети с

двумя скрытыми узлами без пороговых нейронов. Сравните скорость сходимости

разных сетевых архитектур.

Реализуйте сеть Кохонена на языке LISP или C++ и используйте ее для решения за

дачи классификации данных из табл. 10.3. Сравните полученные результаты с описанными в подразделах 10.2.2 и 10.4.2.

Реализуйте сеть встречного распространения и используйте ее для решения задачи

"исключающего ИЛИ". Сравните полученные результаты с данными для сети прямо

го распространения, приведенными в подразделе 10.3.3. Используйте свою сеть

встречного распространения для разделения классов из табл. 10.3.

С помощью сети прямого распространения решите задачу распознавания десяти рукописных цифр. Для этого можно размещать цифры в сетке размером 4x6. Если фрагмент цифры попадает на данную клетку, присвойте ей значение 1, если нет - значение 0. Этот вектор из двадцати четырех элементов можно использовать в качестве входного вектора сети. Для построения обучающего множества можете воспользоваться и другим подходом. Решите эту же задачу с помощью сети встречного распространения. Сравните полученные результаты.

Выберите входной образ, отличный от использованного в подразделе 10.5.2, и примените метод обучения Хебба без учителя для распознавания этого образа.

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

Вспомните сеть ДАП, описанную в подразделе 10.6.3. Измените пары ассоциаций,

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

10. Опишите различия между сетью ДАП и линейным ассоциатором. Что такое помехи и

как предотвратить их появление?

11. Постройте сеть Хопфилда для решения задачи коммивояжера для десяти городов.

482 Часть IV. Машинное обучение

Машинное обучение

на основе

социальных

и эмерджентных

принципов

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

- Чарльз Дарвин (Charles Darwin), О происхождении видов

Первый закон пророчества:

"Когда признанный пожилой ученый утверждает, что нечто возможно, он почти всегда прав. Если он утверждает, что нечто невозможно, он, вероятнее всего, ошибается."

Второй закон:

"Единственный способ постичь границы возможного - отважиться на небольшой шаг за его пределы."

Третий закон: "Любая достаточно развитая технология неотличима от магии."

- Артур Кларк (Arthur С. Clarke), Профили будущего

11.0. Социальные и эмерджентные модели обучения

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

Эмерджентные, или проявляющиеся, модели (emergent model) обучения имитируют наиболее элегантную и мощную форму адаптации - эволюцию форм жизни растительного и животного мира. Как отметил Чарльз Дарвин, нет "границ этой энергии, которая медленно, но верно адаптирует каждое создание к самым сложным жизненным отноше­ниям". В процессе простого варьирования некоторых свойств наиболее жизнеспособных поколений и выборочного отсева менее удачных экземпляров повышаются адаптацион­ные способности и проявляются отличия между особями популяции. Эволюция и зарож­дение новых свойств происходят в популяциях материальных особей, которые действу­ют друг на друга и подвергаются внешнему воздействию. Таким образом, необходимость отбора исходит не только из внешней среды, но и от взаимодействия между членами по­пуляции. Экосистема включает множество членов, кумулятивное поведение которых формирует оставшуюся часть популяции и формируется под ее воздействием.

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

Генетический алгоритм решения задачи включает три стадии, первая из которых предполагает представление отдельных потенциальных решений в специальном виде, удобном для выполнения эволюционных операций изменения и отбора. Зачастую таким представлением являются обычные битовые строки. На второй стадии реализуются скрещивание и мутации, присущие биологическим формам жизни, в результате которых появляется новое поколение особей с рекомбинированными свойствами своих родителей. И наконец на основе некоторого критерия отбора (fitness function) выбираются "лучшие" формы жизни, т.е. наиболее точно соответствующие решению данной пробле­мы. Эти особи отбираются для выживания и воспроизведения, т.е. для формирования но­вого поколения потенциальных решений. В конечном счете некоторое поколение особей и станет решением исходной задачи.

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

Примеры обучения, представляющего собой социальное взаимодействие с целью выживания, можно найти в таких играх, как "Жизнь". Эта игра изначально была разработа­на математиком Джоном Хортоном Конвеем (John Horton Conway) и представлена ши­рокой общественности Мартином Гарднером в журнале "Scientific American" в 1970 и 1971 годах. В этой игре рождение, жизнь и смерть особей - это функция их собственно­го состояния и состояния их ближайших соседей. Обычно для определения игры доста­точно небольшого количества правил - трех или четырех. Как показали эксперименты с игрой "Жизнь", несмотря на эту простоту, в ее рамках могут эволюционировать чрезвы­чайно сложные структуры, в том числе многоклеточные организмы, имеющие функцию саморепликации [Poundstone, 1985].

484 Часть IV. Машинное обучение

Один из важных подходов к искусственной жизни (artificial life) состоит в моделировании условий биологической эволюции за счет взаимодействия конечных автоматов, заданных наборами состояний и правил перехода. Эти автоматы могут принимать ин­формацию из внешней среды, в частности, от ближайших соседей. Правила переходов содержат инструкции по рождению, продолжению жизни и смерти. Если популяция та­ких автоматов свободно действует в своей предметной области, и ее особи могут взаи­модействовать как параллельные асинхронные агенты, то иногда можно наблюдать эво­люцию практически независимых "форм жизни".

Можно привести еще один пример. В работах [Brooks, 1986, 1987] описаны простые роботы, действующие как автономные агенты, способные решать задачи в лабораторных условиях. При этом центральный алгоритм управления отсутствует, а кооперация отдельных особей становится артефактом распределенного и автономного поведения каж­дого из них. Сообщество ученых, работающих в области искусственной жизни, регуляр­но проводит конференции и выпускает журнал, на страницах которого обсуждаются но­вейшие результаты в этой области [Langton, 1995].

В разделе 11.1 вводятся эволюционные модели и описываются генетические алгоритмы (genetic algorithm) [Holland, 1975] - подход к обучению на основе параллелизма, общего взаимодействия и, как правило, битового представления. В разделе 11.2 пред­ставлены системы классификации (classifier system) и генетического программирования (genetic programming) - сравнительно новые области исследования, в которых методо­логия генетических алгоритмов применяется для решения более сложных задач, в част­ности, для построения и уточнения наборов правил вывода [Holland и др., 1986], а также для создания и настройки компьютерных программ [Koza, 1992]. В разделе 11.3 пред­ставлена методология искусственной жизни [Langton, 1995]. Этот раздел начинается со знакомства с игрой "Жизнь". В завершение раздела приводится пример "эмерджентного поведения", описанный в [Crutchfield и Mitchell, 1995].

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

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

Пусть Р( t) - поколение решений-кандидатов xt в момент времени t

В общем виде генетический алгоритм можно представить следующим образом.

procedure genetic algorithm;

begin

установить f: = 0;

инициализировать популяцию P(t); while не достигнуто условие завершения

Глава 11. Машинное обучение на основе социальных и эмерджентных принципов 485

begin

вычислить значение критерия качества для каждого члена популяции P(t) ;

на основе значений критерия качества выбрать из P(t) нужное число членов;

создать следующее поколение с помощью генетических операций; заменить с учетом значений критерия качества особей популяции P(t) их потомками; установить время t:=t+1 end end.

Этот алгоритм отражает основные принципы генетического обучения. Его конкретные реализации могут отличаться в зависимости от задачи. Какое процентное соотноше­ние особей выживает в следующем поколении? Сколько особей участвуют в скрещива­нии? Как часто и к кому применяются генетические операторы? Процедуру "заменить особей популяции P(t)" можно реализовать простейшим образом, заменив фиксиро­ванное процентное соотношение слабейших кандидатов. Более сложный подход со­стоит в упорядочении популяции согласно критерию качества и удалении особей с учетом вероятности, обратно пропорциональной значению критерия качества. Такую меру можно использовать для выбора исключаемых особей. И хотя для наилучших особей популяции вероятность их исключения очень низка, все же существует шанс удаления самых "сильных" особей популяции. Преимущество этой схемы состоит в возможности сохранения некоторых "слабых" особей, которые в дальнейшем могут внести свой вклад в получение более точного решения. Такой алгоритм замены извес­тен под многими именами, в том числе как метод Монте-Карло (Monte-Carlo), прави­ло рулетки (roulette wheel) или алгоритм отбора пропорционально критерию качест­ва (fitness proportionate selection).

Несмотря на то что в подразделе 11.1.3 вводится более сложный принцип представления, при изучении генетических алгоритмов решение задачи будем описывать с помо­щью обычных битовых строк. Предположим, что необходимо с помощью генетического алгоритма научиться классифицировать строки, состоящие из единиц и нулей. В такой задаче популяцию битовых строк можно описывать с помощью шаблона, состоящего из 1, 0 и символов #, которые могут соответствовать как 1, так и 0. Следовательно, шаблон 1##00##1 представляет все восьмибитовые строки, начинающиеся, заканчивающиеся 1 и содержащие в середине строки два нуля подряд.

При работе генетического алгоритма популяция кандидатов Р(0) некоторым образом инициализируется. Обычно инициализация выполняется с помощью датчика случайных чисел. Для оценки решений-кандидатов вводится критерий качества f{xt), определяющий меру соответствия каждого кандидата в момент времени г. При классификации ме­рой соответствия кандидатов является процентное соотношение правильных ответов на множестве обучающих примеров. При таком критерии качества каждому решению-кандидату соответствует значение

f(xt)/m(P,t)

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

486 Часть IV. Машинное обучение

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

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

(crossover). При скрещивании два решения-кандидата делятся на несколько частей и обмениваются этими частя­ми, результатом становятся два новых кандидата. На рис. 11.1 показана операция скрещивания шаблонов бито­вых строк длины 8. Эти строки делятся на две равные час­ти, после чего формируются два потомка, содержащих по одному сегменту каждого из родителей. Заметим, что раз­биение родительских особей на две равные части - это достаточно произвольный выбор. Решения-кандидаты мо­гут разбиваться в любой точке, которую можно выбирать и изменять случайным образом в ходе решения задачи.

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

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

Мутация (mutation) - это еще один важный генетический оператор. Она состоит в случайном выборе кандидата и случайном изменении некоторых его свойств. Например, мутация может состоять в случайном выборе бита в шаблоне и изменении его значения с 1 на 0 или #. Значение мутации состоит в возможном восполнении важных компонентов решения, отсутст­вующих в исходной популяции. Если в рассмотренном выше примере ни один из членов ис­ходной популяции не содержит 1 в первой позиции, то в процессе скрещивания нельзя полу­чить потомка, обладающего этим свойством. Значение первого бита может измениться лишь вследствие мутации. Этой цели можно также достичь с помощью другого генетического опе­ратора - инверсии (inversion), которая будет описана в подразделе 11.1.3.

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

Глава 11. Машинное обучение на основе социальных и эмерджентных принципов 487

11.1.3. Два примера: описание задачи в конъюнктивной нормальной форме и задача коммивояжера

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

Описание проблемы в конъюнктивной нормальной форме

Описание в конъюнктивной нормальной форме (КНФ) - это представление выражения в виде последовательности операторов, связанных отношением И (л). Каждый из этих операторов должен представлять собой дизъюнктивное выражение, определяемое отношением ИЛИ (v), или литерал. Например, для литералов a, b,c,d,e и f выражение

является конъюнктивной нормальной формой. Это выражение представляет собой конъюнкцию пяти операторов, каждый из которых является дизъюнкцией двух или нескольких литералов. Понятия предложения и его представления были введены в главе 2. Там же обсуждались вопросы представления в конъюнктивной нормальной форме и предлагался метод сокращения числа операторов в КНФ. В разделе 12.2 будет приведено доказательство теоремы о разрешении.

Представимость в конъюнктивной нормальной форме означает существование таких логических значений (1 или 0 либо true и false) для каждого из шести литералов, при которых КНФ-выражение принимает значение true. Несложно проверить, что для доказательства представимости рассмотренного выше выражения в конъюнктивной нормальной форме достаточно присвоить значение false литералам a, b и е. Еще одно решение обеспечивается присвоением литералу е значения false, а с - true.

Естественным представлением данных для задачи КНФ-описания является последовательность из шести битов, каждый из которых представляет значение одного из шести

литералов a,b,c,d,e и f. Таким образом, выражение

10 10 10 |

означает, что литералы а, с и е принимают значение true, a to, d и f- false. Для такой комбинации значений литералов приведенное выше выражение принимает значение false. Читатель может самостоятельно подобрать такие значения литералов, при которых общее выражение истинно.

В процессе выполнения генетических операторов требуется получить потомка, для которого КНФ-выражение является истинным. Следовательно, в результате выполнения каждого генетического оператора должна получаться битовая строка, которая может рассматриваться как кандидат на роль решения задачи. Этим свойством обладают все рассмотренные до сих пор генетические операторы. В частности, в результате скрещивания и мутации получаются битовые строки, которые могут стать решением задачи. Менее типичные операторы, такие как инвертирование (inversion) (изменение порядка следования битов в шестибитовой строке на обратный) или обмен (exchange) (перемена мест двух произвольных битов), тоже обеспе­чивают получение кандидата на роль решения КНФ-проблемы. С этой точки зрения трудно обеспечить более удачное представление данных в задаче КНФ.

488 Часть IV. Машинное обучение

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

Однако существует множество вариантов. Следует отметить, что полное КНФ-выражение представляет собой конъюнкцию пяти операторов. Поэтому можно определить рейтинг решения по шкале от 0 до 5 в зависимости от количества операторов, принимающих значение true. Тогда каждому из образов можно сопоставить соответствующий рейтинг:

1 1 0 0 1 0 - рейтинг 1, О 1 0 0 1 0 - рейтинг 2,

1 0 0 1 1 - рейтинг 3,

0 1 0 1 1 - рейтинг 5,

следовательно, эта комбинация является решением. Такой генетический алгоритм обеспечивает разумный подход к решению КНФ-проблемы. Одним из важнейших свойств этого под­хода является неявный параллелизм, обеспечиваемый за счет одновременной обработки це­лой популяции решений. Этому представлению естественным образом соответствуют генети­ческие операторы. И, наконец, поиск решения выполняется по принципу "разделяй и властвуй", поскольку решение задачи делится на несколько элементов. В упражнениях к этой главе читателю будет предложено рассмотреть другие аспекты этой проблемы.

Задача коммивояжера

Задача коммивояжера - это классический пример тестовой задачи для методов искусственного интеллекта и компьютерных наук вообще. Впервые она упоминалась в раз­деле 3.1 при описании графов. Пространство состояний этой задачи для N городов вклю­чает /V! возможных состояний. Было показано, что эта задача является NP-полной, по­этому для ее решения предлагалось множество различных эвристических подходов. Формулировка задачи достаточно проста.

Коммивояжеру требуется посетить N городов. Для каждой пары городов по маршруту следования установлена стоимость (например расстояние). Требуется найти путь минимальной стоимости, который начинается из некоторого города, обеспечивает посещение остальных городов ровно по одному разу и возврат в точку отправления.

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

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

Рассмотрим несколько очевидных представлений, которые имеют достаточно сложные последствия. Предположим, необходимо посетить девять городов 1, 2, ..., 9. Тогда путь

Глава 11. Машинное обучение на основе социальных и эмерджентных принципов 489

можно представить упорядоченным списком из девяти целых. Представим порядковый но­мер каждого города строкой из четырех битов: 0001,0010,..., 1001. Тогда выражение

0001 0010 0011 0100 0101 0110 0111 1000 1001

представляет последовательность посещения городов по возрастанию их порядковых номеров. Пробелы в этом выражении поставлены только для простоты восприятия. Ка­кие генетические операторы можно использовать для решения этой задачи? Скрещивание однозначно не подходит, поскольку получаемая в результате строка, скорее всего, не будет представлять собой путь, при котором каждый город посещается только один раз. Действительно, при скрещивании некоторые города выпадут из последовательности, а другие встретятся в ней дважды. Что можно сказать о мутации? Предположим, что край­ний слева бит в обозначении шестого города ОНО изменится на 1. Тогда полученное число 1110 будет соответствовать порядковому номеру 14, который не входит в допус­тимый перечень городов. Инвертирование городов в выражении пути в данном случае является допустимой операцией, однако достаточно ли ее для получения необходимого решения? Одним из способов поиска минимального пути является генерирование и оценка всех возможных перестановок из N элементов в списке городов. Поэтому генети­ческие операторы должны обеспечить возможность получения этих перестановок.

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

Многие исследователи [Davis, 1985], [Oliver и др., 1987] разработали операторы скрещивания, устраняющие эти проблемы и позволяющие работать с упорядоченным списком посещаемых городов. Например, в работе [Davis, 1985] определен оператор, получивший название упорядоченного скрещивания (order crossover). Допустим, имеется девять городов 1,2,..., 9, порядок следования которых представляет очередность их посещения.

В процессе упорядоченного скрещивания потомок строится путем выбора подпоследовательности городов в пути одного из родителей. В нем также сохраняется относительный порядок городов другого родителя. Сначала выбираются две точки сечния, обозначенные символом |, которые случайным образом устанавливаются в одних и тех же позициях каждого из родителей. Местоположение точек сечения выбирается слу­чайным образом, однако для каждого из родителей эти точки совпадают. Например, если для двух родителей р 1 и р2 точки сечения располагаются после 3-го и 7-го городов

р1=(192|4657|83), р2=(459|1876|23),

то два потомка с1 и с2 получаются следующим образом. Сначала для каждого из потомков копируются фрагменты строк родителей, расположенные между точками сечения.

с1=(ххх|4657|хх), с2=(ххх|1876|хх).

490 Часть IV. Машинное обучение

Смотрите здесь купить мебель в кредит в Краснодаре.