close

Вход

Забыли?

вход по аккаунту

?

Solovev

код для вставкиСкачать
Федеральное агенТство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Санкт-петербургский государственный университет
аэрокосмического приборостроения
Н. В. Соловьев
ВВЕДЕНИЕ В СИСТЕМЫ
ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
Учебное пособие
Санкт-Петербург
2008
УДК 007.5
ББК 32.81
С60
Рецензенты:
кафедра технологии программирования СПб ГУИТМО;
доктор технических наук, профессор В. А. Слаев
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Соловьев Н. В.
С60 Введение в системы искусственного интеллекта: учебное пособие / Н. В. Соловьев. – СПб.: ГУАП, 2008. – 104 с.: ил.
ISBN 978-5-8088-0386-2
В учебном пособии рассмотрены теоретические основы построения
систем искусственного интеллекта. Предназначено для студентов направления 230100 «Информатика и вычислительная техника».
УДК 007.5
ББК 32.81
Учебное издание
Соловьев Николай Владимирович
ВВЕДЕНИЕ В СИСТЕМЫ
ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
Учебное пособие
Редактор А. Г. Ларионова
Верстальщик С. Б. Мацапура
Сдано в набор 03.09.08. Подписано к печати 14.10.08.
Формат 60×84 1/16. Бумага офсетная. Печать офсетная.
Усл.-печ. л. 6,0. Уч.-изд. л. 6,5. Тираж 150 экз. Заказ № 523
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
ISBN 978-5-8088-0386-2
© ГУАП, 2008
© Н. В. Соловьев, 2008
Содержание
Предисловие.................................................................... 4
Введение.......................................................................... 5
1. Исчисление высказываний и предикатов.......................... 10
1.1. Гипотеза о физической символьной системе................ 10
1.2. Исчисление высказываний....................................... 11
1.3. Исчисление предикатов........................................... 13
1.4. «Мир блоков»......................................................... 18
1.5. Язык логического программирования........................ 20
2. Поиск в пространстве состояний...................................... 23
2.1. Граф пространства состояний................................... 23
2.2. Алгоритмы поиска с последовательным перебором...... 28
2.3. Эвристические алгоритмы поиска............................. 32
2.4. Язык обработки списков.......................................... 39
3. Распознавание образов................................................... 45
3.1. Описание объектов набором признаков...................... 45
3.2. Метрики пространства признаков............................. 49
3.3. Методы кластеризации............................................ 54
3.4. Построение классификаторов................................... 57
4. Машинное обучение....................................................... 65
5. Нейронные сети............................................................. 69
5.1. Естественные и искусственные нейроны..................... 69
5.2. Топология нейронных сетей..................................... 72
5.3. Алгоритм обратного распространения........................ 76
5.4. Сеть встречного распространения.............................. 80
5.5. Практическая реализация нейронных сетей............... 87
6. Генетические алгоритмы................................................ 90
6.1. Методологическая основа генетических алгоритмов.... 90
6.2. Представление задачи в конъюнктивной нормальной
форме.......................................................................... 93
6.3. Проблемы реализации генетических алгоритмов......... 97
Контрольные вопросы........................................................ 101
Список литературы........................................................... 104
3
Предисловие
При подготовке лекций по дисциплине «Системы искусственного интеллекта», положенных в основу данного пособия, автор в
основном использовал изданный в 2003 году в переводе на русский
язык учебник Д. Ф. Люгера «Искусственный интеллект: стратегии
и методы решения сложных проблем». Ни в коей мере не претендуя на полноту охвата столь обширной темы, предлагаемое Вашему
вниманию пособие является скорее кратким конспектом некоторых
разделов этого фундаментального труда с добавлением материалов
из других источников, перечисленных в списке литературы.
Автор надеется, что пособие окажется полезным для студентов
направления 230100 «Информатика и вычислительная техника»
и специальности 230101 «Вычислительные машины, комплексы,
системы и сети», изучающих дисциплины «Системы искусственного интеллекта», «Теория принятия решений», «Распознавание
образов», а также для студентов родственных специальностей.
4
Введение
Стремительное по историческим меркам развитие вычислительной техники началось во второй половине XX века с громоздких и
медленных электронно-вычислительных машин, помогавших человеку выполнять сложные и трудоемкие, многократно повторяющиеся вычисления. На сегодняшний день трудно назвать область
деятельности, которую в той или иной степени не коснулась бы компьютеризация. Резкое увеличение скорости и объема памяти компьютеров, разнообразие внешних устройств, возможность представить информацию любого вида в цифровой форме привело к тому,
что в последние десятилетия создание систем, обладающих искусственным интеллектом, из абстрактно-философской проблемы перешло в практическую плоскость и вызвало появление нового научного направления – искусственного интеллекта (ИИ).
Прежде чем начать изучение систем, необходимо попытаться определить сам термин «искусственный интеллект» для того, чтобы
выделить круг проблем и областей приложения, рассматриваемых
этой наукой. Можно сказать, что искусственный интеллект – это
область компьютерной науки, занимающаяся автоматизацией разумного или интеллектуального поведения. Тогда системы ИИ – это
компьютерные аппаратно-программные системы, способные решать
интеллектуальные задачи.
Основной недостаток приведенных определений заключается в
использовании таких понятий как «интеллектуальные задачи» и
«разумное поведение», которые, в свою очередь, тоже требуют определения. Причем именно определение термина «разумное поведение» и позволяет очертить круг задач, рассматриваемых в данной
науке. Таким образом, проблема определения искусственного интеллекта сводится к определению интеллекта или разумного поведения
вообще, что само по себе является скорее философской проблемой.
Необходимо учесть, что интеллект представляет собой исключительно сложное явление, которое невозможно полноценно описать с
помощью одной теории. Ученые, исследующие интеллект, вынуждены строить иерархию подходов, описывающих разные уровни интеллекта, – от нейронных сетей до систем понимания естественного
языка, причем все эти подходы объединяет то, что они представляют некие процессы обработки информации. Таким образом, любые
интеллектуальные системы обязательно занимаются обработкой информации, но далеко не каждую систему, обрабатывающую информацию, можно назвать интеллектуальной.
Как известно, в такой строгой науке как математика определение
любого понятия производится с использованием других более общих
5
понятий. Учитывая, что понятие «разум», или «интеллект», является уже достаточно общим, его определение через какие-то другие
понятия представляется трудновыполнимой задачей.
С практической точки зрения, вполне допустимо вместо общего определения интеллекта привести некоторый набор признаков,
наличие которых у объекта позволяет говорить о его способности к
разумной деятельности. Исторически считалось, что только человек обладает высокоразвитым разумом, способным к абстрактному мышлению, выполнению сложных математических операций и
построению логических цепочек, а также к интуиции и творчеству.
Предполагалось, что наличие этих способностей и определяет наличие интеллекта. Однако, хотя на сегодняшний день большинство из
этих действий вполне удовлетворительно выполняют компьютеры,
нельзя сказать, что такие компьютеры уже обладают искусственным
интеллектом.
Еще в 1950 году британский математик Аллан Тьюринг предложил определять наличие интеллекта с помощью теста, в котором
участвуют компьютер с «интеллектуальным» программным обеспечением, человек-имитатор и человек-эксперт. Все они находятся в
разных помещениях и связываются друг с другом посредством терминалов. Эксперт на основании диалога на произвольную тему должен решить, с кем он беседует – с человеком или компьютером. Тьюринг утверждал, что если эксперт не сможет отличить компьютер
от человека, то этот компьютер можно считать разумным. Довольно
быстро специалистами был написан ряд программ, способных вести
диалог на конкретную тему: о погоде, о семье и т. п., – т. е. в какойто мере удовлетворяющих тесту Тьюринга.
Этот тест имеет ряд принципиальных особенностей:
– дает представление об интеллекте как о реакции на некоторый
набор вопросов или, в более широком плане, воздействий;
– исключает рассмотрение природы интеллекта, т. е. необходимость наличия каких-либо конкретных структур, внутренних процессов и самосознания;
– препятствует предвзятости эксперта в пользу человека или компьютера, фокусируя внимание на содержании вопросов и ответов.
Следует отметить, что похожая методика тестирования используется при проверке современных экспертных систем.
Основное возражение против принципиальной возможности построения интеллектуальной программы сводится к тому, что компьютеры могут выполнять только заранее заданные действия, а создать
набор правил поведения в любых ситуациях принципиально невозможно. Действительно, гибкость, позволяющая биологическим
объектам приемлемым образом реагировать на практически беско6
нечное разнообразие ситуаций, является отличительной чертой разумного поведения. Однако современные программы в области ИИ
обладают модульной структурой, причем модули активизируются и
изменяются в зависимости от конкретной ситуации. Например, робот, движущийся к заданной цели по пересеченной местности, выбирает траекторию движения в зависимости от расположения препятствий согласно информации, полученной от различных датчиков.
В последнее время ученые пришли к выводу, что интеллект – это,
в первую очередь, способ обработки информации. В таком случае, не
только человек, но и другие живые существа вполне способны проявлять интеллектуальное поведение. Нобелевский лауреат Герберт
Саймон говорил, что изменчивость поведения, присущая живым существам, определяется скорее сложностью окружающей их среды,
а не сложностью их внутренних «программ». В самом деле, стремящийся как можно быстрее вернуться в колонию муравей, как система, проявляющая разумное поведение по достижению поставленной
цели, очень прост. Наблюдаемая сложность его движения в большей
степени отражает сложность поверхности, по которой муравей вынужден ползти. Отсюда можно сделать важный вывод, что для развития интеллекта необходимо взаимодействие с достаточно богатой
окружающей средой.
Видимо, более подходящим с практической точки зрения определением системы с ИИ будет следующее: интеллектуальная система – это система, способная совершать целенаправленные действия
в изменчивой окружающей среде.
С практической точки зрения, основные задачи систем ИИ состоят в том, чтобы сделать процессы обработки информации с использованием вычислительной техники более эффективными, а также
помочь ученым в понимании принципов, лежащих в основе интеллекта.
Перед разработчиками систем ИИ стоят две фундаментальные
проблемы:
– представление знаний, т. е. разработка эффективных способов
описания свойств и отношений между объектами в некоторой предметной области;
– поиск, т. е. нахождение в пространстве состояний решаемой задачи оптимального в некотором смысле пути к поставленной цели.
В той или иной степени эти задачи приходится решать в любой
области из тех, которые принято относить к ИИ. Более того, именно
возникновение таких проблем при разработке некоторой системы и
позволит отнести ее к разряду систем искусственного интеллекта.
Одними из первых систем, отнесенных к ИИ, являются программы автоматического рассуждения и доказательства теорем. Привле7
кательность таких систем заключается в одновременной строгости
и общности логических построений. Самые разнообразные задачи
можно попытаться решить, представив их исходную информацию
в виде набора логических аксиом и правил вывода, а цель – в виде
теорем, которые нужно доказать. К сожалению, быстро выяснилось,
что действительно сложные, имеющие практическое значение логические системы, управляемые чисто формальными синтаксическими методами поиска, в процессе работы генерируют огромное количество доказуемых теорем, в подавляющем большинстве не относящихся к делу.
Современные программы автоматических рассуждений работают
в интерактивном режиме, предоставляя человеку в процессе работы
разбивать сложную задачу на ряд более простых подзадач и формулировать эвристические правила, существенно ограничивающие область поиска решения данной проблемы.
К ранним системам ИИ относятся и программы ведения логических игр, например шашки, шахматы, крестики-нолики, пятнашки или игра в пятнадцать. С одной стороны, эти игры, несомненно,
являются интеллектуальными, с другой – все они имеют ярко выраженный структурированный характер, так как ведутся с использованием ясных правил, на ограниченном пространстве, в пошаговом
режиме и с полной информацией о сложившейся позиции на каждом
шаге. Такие игры как шашки и шахматы могут порождать практически бесконечные пространства состояний, для поиска в которых
требуются мощные эвристические методы. Их разработка остается
серьезной проблемой и на сегодняшний день, хотя, как известно,
шахматные компьютерные программы успешно конкурируют с чемпионом мира.
Отдельно следует отметить более сложные с точки зрения ИИ
игры, имеющие вероятностный характер, например различные карточные игры, нарды, а также мультиагентные системы, моделирующие игры в реальном времени, например компьютерный футбол, по
которому регулярно проводятся международные соревнования.
Экспертные системы представляют собой одно из используемых
на практике достижений ИИ. Стратегия экспертных систем основана на знаниях человека-эксперта, представленных в форме, которая
позволяет компьютеру применить их при решении похожих проблем
в специализированной предметной области. Основными трудностями при разработке экспертных систем являются: проблема адекватной передачи знаний от эксперта к системе, недостаток гибкости при
выборе стратегии подхода к проблеме, трудности всестороннего тестирования и ограниченность обучения на опыте.
8
Принципиальным отличием экспертных систем от человека является тот факт, что с увеличение объема имеющейся информации
человек, как правило, быстрее находит решение, а скорость работы
экспертной системы в аналогичной ситуации падает. Последнее заставляет усомниться в разумности таких систем.
Еще одно важное направление ИИ – понимание естественного
языка, так как способность применять и понимать естественный
язык является фундаментальным аспектом человеческого интеллекта. Хотя в настоящее время компьютерные программы достигли
заметных успехов в понимании и переводе простых предложений на
ограниченных контекстах, но разработка системы, использующей
языки с гибкостью и общностью, характерной для человеческой
речи, все еще остается за пределами современных методологий.
Дело в том, что понимание естественного языка включает в себя
гораздо больше, чем просто синтаксический разбор предложений и
поиск соответствующих значений в словаре, т. е. фактически подстрочный перевод. Собственно понимание базируется на обширном
знании предмета беседы, идиоматических выражений, используемых в данной области, что позволяет понимать недомолвки и многозначные выражения, характерные для естественной речи.
В последнее десятилетие заметных успехов удалось добиться в
таком разделе ИИ, как робототехника и планирование. Исследования в этой области начались с попыток создать роботов, способных
достигать поставленной цели в изменяющейся окружающей среде.
Планирование предполагает, что робот, умеющий выполнять ряд
элементарных действий и оснащенный датчиками о внешней среде, должен найти такую последовательность этих действий, которая
приведет к достижению поставленной перед ним достаточно общей
цели.
Помимо проблем, связанных с анализом поступающей от различных датчиков информации об изменениях во внешней среде, существенную сложность представляют разработка методов адекватного
описания внешней среды и оптимальное разбиение общей сложной
задачи на более простые частные подзадачи. На сегодняшний день
исследования в области планирования вышли за пределы робототехники и включают в себя координацию любых сложных систем задач
и целей.
Моделирование человеческого сознания средствами ИИ является мощным средством познания для физиологов, психологов, лингвистов, социологов и философов, изучающих как непосредственно
структуру и механизмы работы мозга, так и весь спектр проблем
мышления.
9
1. Исчисление высказываний и предикатов
1.1. Гипотеза о физической символьной системе
Ведущим принципом ранней методологии ИИ является сформулированная Ньюэллом и Саймоном в 1976 году гипотеза о физической символьной системе, которая гласит:
– физически ограниченная система ведет себя соответственно
своим целям, приспосабливаясь к требованиям окружающей среды, проявляя при этом разумное в широком смысле поведение;
– физическая система проявляет разумное поведение тогда и
только тогда, когда она является физической символьной системой;
– достаточность означает, что разумность может быть достигнута каждой правильно организованной физической символьной
системой;
– необходимость означает, что каждый объект, проявляющий
разумность, должен являться физической символьной системой,
т. е. разумное поведение объекта достигается путем физической реализации операций над символьными структурами.
Гипотеза о физической символьной системе привела к использованию символов в качестве средства для описания окружающего
мира, разработке механизмов перебора для нахождения решения
поставленной задачи и независимости системы ИИ от средств реализации. Возможность формализовать символьные модели в виде
языка представления принципиальна для моделирования интеллекта как выполняемой компьютерной программы. Математика
формальных систем позволяет оценить их полноту, непротиворечивость, сложность, а также обсуждать организацию знаний об окружающем мире.
На основании гипотезы о физической символьной системе можно сделать вывод, что интеллектуальная деятельность как человека, так и машины осуществляется с использованием: символьных
шаблонов, предназначенных для описания области определения
задачи; операций над этими шаблонами, позволяющими генерировать возможные решения; поиска решения из числа возможных.
Таким образом, уровень интеллекта в значительной мере определяется структурой системы символов, представляющих знания о
некоторой предметной области.
Очевидно, схема представления знаний должна адекватно выражать всю необходимую информацию, поддерживать эффективное
выполнение конечного программного кода и обеспечивать естест10
венный способ выражения необходимых знаний. Вообще говоря,
задачи ИИ связаны скорее с качественными, а не с количественными проблемами; с логической аргументацией, а не с вычислениями; с организацией больших объемов знаний, а не с реализацией
отдельного алгоритма.
Как следствие, язык представления знаний в ИИ должен обрабатывать знания, выраженные в качественной форме, получать новые
знания из набора фактов и правил, отображать общие принципы и
конкретные ситуации. Такими свойствами в значительной степени
обладает язык исчисления предикатов, основное преимущество которого заключается в четко сформулированной формальной семантике, обоснованности и полноте правил вывода.
1.2. Исчисление высказываний
Исчисление предикатов и исчисление высказываний являются
языками, состоящими из символов и предложений, обладающих
определенной семантикой (значением) и синтаксисом, используя
которые можно представить свойства и отношения в окружающем
мире.
Символы исчисления высказываний – это символы высказываний (P, Q, R, S, …), значения истинности (true, false), логические
связки (∨, ∧, ¬, ≡, →) и скобки, которые используются для группировки символов в подвыражения и управления порядком их оценки и присвоения значений.
Предложения в исчислении высказываний формируются из
символов по следующим правилам:
– каждый символ и значение истинности есть предложение;
– отрицание (¬) предложения есть предложение;
– конъюнкция (∨) или логическое И двух предложений есть
предложение;
– дизъюнкция (∧) или логическое ИЛИ двух предложений есть
предложение;
– эквивалентность (≡) двух предложений есть предложение;
– импликация (→) двух предложений есть предложение.
Следует отметить, что в импликации P→Q, единственной несимметричной связке, элементы называются предпосылкой (P) и
заключением (Q).
Предложение является правильно построенной формулой исчисления высказываний тогда и только тогда, когда оно состоит
из некоторой последовательности допустимых символов согласно
11
установленным правилам, например, ((Р∧Q)→R)≡¬P∨ ¬Q∨R – правильно построенное предложение.
Символы высказываний составляют истинные или ложные утверждения относительно некоторого мира, например, P может означать «идет дождь», а Q – «земля мокрая».
Интерпретация предложения или семантика исчисления высказывания – это утверждение относительно правдивости предложения в некотором мире. Например, утверждение «если идет дождь,
то земля мокрая» можно представить в виде импликации P→Q.
Формально интерпретация набора высказываний – это присвоение значения истинности (T или F) каждому высказыванию, т. е.
отображение предложений на множество {T, F}. Символы T и F используются для того, чтобы отличить результат интерпретации от
символов true и false, которые могут использоваться в предложении.
Значение истинности предложений определяется таблицами
истинности, которые содержат все возможные варианты значения
истинности для элементарных суждений или атомарных формул,
составленных из символов высказываний или элементов. В табл. 1
приведены значения истинности для логических связок.
Таблица 1
P
Q
P∧Q
P∨Q
P≡Q
P→Q
T
T
T
T
T
T
T
F
F
T
F
F
F
T
F
T
F
T
F
F
F
F
T
T
Два выражения в исчислении высказываний эквивалентны,
если они имеют одни и те же значения при всех возможных значениях элементов, составляющих эти выражения. Эта эквивалентность может быть доказана сопоставлением таблиц истинности для
каждого выражения.
Для приведения высказываний к необходимому виду, например
к дизъюнкции конъюнкций, используются известные из булевой
алгебры законы отрицания-отрицания, Моргана, коммутативности, ассоциативности и дистрибутивности для конъюнкций и дизъюнкций, а также отношения эквивалентности для импликаций:
(P∨Q)≡(¬P→Q), P→Q≡(¬Q→¬P).
12
1.3. Исчисление предикатов
В исчислении высказываний каждый элементарный символ
обозначает высказывание некоторой сложности, причем не существует способа получить доступ к компонентам этого суждения. Кроме того, в высказываниях не используются переменные, т. е. элементарные символы являются константами.
Исчисление предикатов предоставляет такие возможности. Например, вместо высказывания P – «всю неделю шел дождь» в исчислении предикатов можно создать предикат погода (X,Y), описывающий отношение между днем недели и погодой, где X – множество дней недели, Y – множество вариантов погоды. Тогда можно
заявить, что для всех значений X и Y≡«дождь» утверждение погода
(X,Y) есть истина, что и будет эквивалентно высказыванию P. Посредством правил вывода и с учетом синтаксиса предикатов можно
изменять выражения исчисления предикатов, обращаясь непосредственно к их компонентам и выводя новые предложения. Таким
образом, исчисление предикатов по сравнению с исчислением высказываний увеличивает гибкость описания окружающего мира.
Алфавит исчисления предикатов состоит из следующих знаков:
букв (русских или английских) как строчных, так и прописных,
цифр и знака подчеркивания. Круглые скобки используются для
правильного построения выражений.
Символы начинаются с буквы, за которой следует последовательность знаков, например, День_недели, погода_вчера, plus.
Символы могут представлять константы, переменные, функции и
предикаты.
Константы соответствуют некоторым объектам или их свойствам из описываемого мира и должны начинаться со строчной буквы или состоять только из цифр.
Переменные обозначают общие классы объектов или свойств и
должны начинаться с прописной буквы. Переменная должна быть
определена на некотором множестве констант, имеющих общее
свойство, например, переменная День_недели определена на множестве {пн, вт, ср, чт, пт, сб, вс}, т. е. может принимать любое
из этих значений. Теоретически область определения переменной
может быть бесконечной.
Функция обозначает отражение одного или нескольких элементов множества, называемого областью определения, в однозначно
определяемый элемент другого множества, называемый областью
значений функции. Функция состоит из символа, начинающегося
со строчной буквы, и заключенного в круглые скобки списка ар13
гументов. Число аргументов определяет арность функции, например, функция погода(День_недели) имеет арность 1, а функция
plus(7,минус_2) – арность 2. Замена функции ее значением называется оцениванием функции. Тогда значение функции plus(7,минус_
2) – целое число 5. Значение функции погода(День_недели) можно
определить, только заменив переменную День_недели константой
из области ее определения, например, если в понедельник шел
дождь, то это значение и будет результатом оценивания функции
погода(День_недели) для День_недели≡пн.
Предикаты указывают на отношение между несколькими объектами в мире, причем количество связанных таким образом объектов определяет арность предиката. Предикаты, подобно функциям, состоят из предикатного символа, начинающегося со строчной
буквы, и заключенного в круглые скобки списка термов. Термом
исчисления предикатов может быть константа, переменная или
функция. Минимальная единица языка исчисления предикатов –
это атомарное предложение или просто атом, представляющее собой предикат некоторой арности, например, друг(иван,петр) или
друг(отец(вася),отец(маша)), причем в последнем случае аргументы предиката являются функциями. Если отец(вася)≡иван, а
отец(маша)≡петр, то после оценки функциональных выражений
приведенные в примере предикаты будут эквивалентны.
Из атомарных предложений можно формировать предложения
или выражения, также являющиеся предикатами, используя те же
логические связки, что и в исчислении высказываний. Составленное таким образом множество термов и предикатов представляет
собой базу знаний, описывающую объекты и их отношения в области определения некоторого мира, текущее состояние которого
вычисляется путем интерпретации предикатов.
Интерпретация предикатов на некоторой области определения
D – это связывание логических объектов из D с каждым термом в
выражении исчисления предикатов согласно следующим правилам:
– каждой константе ставится в соответствие элемент из D;
– каждой переменной ставится в соответствие множество элементов из D, являющееся ее областью определения;
– каждая функция f арности n задает отображение из Dn в D;
– каждый предикат p арности m задает отображение из Dm в
{T, F}.
При таком определении интерпретации для получения значения
предложения нужно присвоить ему значение истинности на данной
14
интерпретации, в результате чего предложение будет отображено
в {T, F}.
Используемые в предложениях переменные относятся к некоторым объектам из своей области определения. Кванторы переменных
ограничивают значения предложения, содержащего переменную.
Квантор существования ∃ указывает, что предложение истинно
хотя бы для одного значения из области определения переменной.
Квантор всеобщности ∀ указывает, что предложение истинно для
всех значений из области определения переменной. Например, высказывания «все любят мороженное» и «У Ивана есть друг» можно
представить соответственно как ∀X любить(X,мороженное) и ∃X
друг(иван,Х), где X – множество людей.
Для указания области действия квантора используются круглые скобки, например, ∀X(p(X)∨ q(Y)→r(X)) указывает, что переменная Х связана квантором всеобщности в предложениях p(X) и
r(X). В исчислении предикатов все выражения должны быть связаны кванторами.
Следует отметить, что квантор всеобщности усложняет вычисление значения истинности предложения, так как необходимо проверить все возможные значения переменной. Если область определения переменной, связанной квантором всеобщности, бесконечна,
то полная проверка истинности путем последовательной подстановки в выражение значений переменной в принципе невозможна, изза чего проблему исчисления предикатов, строго говоря, считают в
общем случае неразрешимой.
Проверка истинности выражений, содержащих связанные
квантором существования переменные с бесконечной областью определения, может вызвать не меньшие сложности, например, если
выражение ложно при всех значениях переменной, то алгоритм
проверки никогда не завершится.
В качестве примера рассмотрим описание семейных отношений согласно библейской генеалогии. Отношения родителей
и детей можно описать набором предикатов: мать(ева,авель);
мать(ева,каин); отец(адам,авель); отец(адам,каин), где имена
являются константами. Для описания в общем виде родительских
и братских отношений можно использовать импликацию атомарных предложений с участием переменных:
∀X∀Y(отец(X,Y)∨ мать(X,Y)→родитель(X,Y));
∀X∀Y∀Z(родитель(X,Y)∧родитель(X,Z)→братья(Y,Z)),
где X={адам,ева}, Y, Z={авель,каин}.
15
Интерпретация путем подстановки соответствующих констант позволяет вывести новое правильное заключение, например,
братья(авель,каин).
Интерпретация должна обеспечивать значение истинности для
всех выражений в базе знаний, а сами выражения должны достаточно детально описывать некоторый мир, предоставляя возможность логически выводить новые корректные выражения из набора
первоначальных выражений по определенным правилам. Именно
эта возможность является достоинством исчисления предикатов.
Выражение Х логически следует из набора выражений S, если
каждая интерпретация, удовлетворяющая S, удовлетворяет и Х,
а правила вывода позволяют определить, когда новое выражение
логически следует из имеющегося набора выражений. Выражение
Х выполнимо, если существует интерпретация, при которой Х≡Т,
в противном случае Х невыполнимо. Если выражение имеет значение Т для всех возможных интерпретаций, то оно называется адекватным.
Правило вывода обосновано, если каждое выражение, полученное в соответствии с этим правилом из множества выражений, логически следует из этого множества. Например, правило отделения
или modus ponens и универсальное инстанцирование – обоснованные правила вывода.
Правило отделения гласит, что если предложения P и P→Q истинны в некоторой интерпретации, то Q в этой интерпретации тоже
истинно. Например, если P означает «идет дождь», а Q – «земля
мокрая», то утверждение «если идет дождь, то земля мокрая» есть
импликация P→Q. При условии, что Р≡Т, т. е. сейчас идет дождь,
получаем набор истинных предложений: P→Q, Р. Применив к ним
правило отделения, получаем, что Q≡T, т. е. можем добавить в набор новый факт – «сейчас земля мокрая».
Правило универсального инстанцирования гласит, что если в истинном предложении любую переменную, стоящую под квантором
всеобщности, заменить соответствующим термом из области ее определения, то результирующее предложение останется истинным.
Например, высказывание «все люди смертны» можно представить
с исчислении предикатов как ∀X(человек(Х)→смертный(Х)), а
утверждение «Сократ – человек», как человек(сократ). Переменная Х в высказывании стоит под знаком квантора всеобщности,
следовательно, согласно правилу универсального инстанцирования, ее можно заменить на любое значение из области определения и, применив правило отделения, получить утверждение
смертный(сократ), т. е. «Сократ – смертен».
16
Следует отметить, что рассуждения, использующие логику исчисления предикатов, основываются на следующих предположениях:
– предложения в базе знаний адекватно и полно описывают
предметную область, т. е. содержат всю необходимую для решения
некоторой задачи информацию;
– предложения в базе знаний не противоречат друг другу.
Создание опирающихся на исчисление предикатов баз знаний
для реального мира сталкивается с существенными трудностями;
так, в экспертных системах предпосылка в импликации часто является целью, а заключение – наблюдаемым состоянием мира. Например, в системе диагностики автомобиля может существовать
утверждение «если двигатель не вращается и фары не горят, то
проблема в аккумуляторе или проводке». Оно напоминает обычное
предикатное выражение, используемое в правиле отделения, но это
не так. Невозможность завести двигатель и зажечь фары не обязательно означает неисправность аккумулятора или проводки. Это
только наиболее вероятная причина наблюдаемого состояния автомобиля. А вот обратное утверждение – истинно, но пользы от него,
с точки зрения экспертной системы, практически нет.
Данный случай является примером абдуктивного рассуждения,
когда из P→Q и Q выводится Р. Абдукция является необоснованным правилом вывода, означающим, что выведенное предложение
не обязательно истинно для каждой интерпретации. Однако это
правило широко применяется во многих экспертных системах, так
как хотя именно неисправности или болезни вызывают, т. е. имплицируют, симптомы, а не наоборот; но диагноз ставится от симптомов к причинам, их вызвавшим.
Для измерения степени доверия к заключению часто вводится
коэффициент уверенности, определяющий вероятность ошибки
для абдуктивного рассуждения. Такой подход позволяет учесть в
правилах меру достоверности данных и проводить нечеткие рассуждения или применять стохастические методы к нечеткому
выводу. Проблему изменения степени доверия в процессе работы
системы решают немонотонные рассуждения, которые делают наиболее обоснованные предположения в условиях неопределенности
информации. Затем выполняется логический вывод на основе этих
предположений, принимаемых за истинные. При изменении меры
доверия к некоторому утверждению производится перепроверка
всех заключений, выведенных с его использованием. Цена такого
подхода – необходимость постоянно отслеживать весь ход рассуждений, основанных на неточных знаниях, с помощью систем подде17
ржки истинности, сохраняющих непротиворечивость базы знаний
в процессе поиска решения поставленной задачи.
1.4. «Мир блоков»
В качестве примера использования исчисления предикатов рассмотрим описание «мира блоков» с целью планировать действия
робота. «Мир блоков» ограничен множеством одинаковых блоков
на поверхности стола и действиями руки робота, который имеет
информацию о координатах расположения блоков на столе. Рука
робота имеет захват, который может схватить свободный блок, т. е.
блок со свободной верхней гранью, и переместить его в любую точку стола или установить на свободный блок.
Состояние мира можно описать следующими предикатами:
– на_столе(Х) – блок Х находится непосредственно на столе;
– на(Х,Y) – блок Х находится на верхней грани блока Y;
– чисто(Х) – верхняя грань блока Х свободна, т. е. блок свободен и может быть захвачен;
– захват(Х) – захват удерживает блок Х;
– пусто( ) – захват свободен.
Тогда «мир блоков», показанный на рис. 1, можно представить
конъюнкцией следующих предикатов: на_столе(b), на_столе(c),
на_столе(e), на(a,b), на(d,e), чисто(a), чисто(c), чисто(d), пусто( ).
Для состояний мира можно составить отношения, позволяющие
проверять их истинность, например:
– ∀X(¬(∃Y)на(Y,X)→чисто(X)) – если не существует блока Y,
находящегося на блоке Х, то блок X свободен;
– ∀X(¬захват(X)→ пусто( )) – если в захвате нет блока, то он
свободен.
Команды робота, воздействующие на состояние мира и приводящие к новому состоянию, можно описать как операторы:
– взять(X) – взять со стола блок Х и держать его в захвате, причем
∀X(взять(Х)→(захват(Х)←(пусто( )∧чисто(Х)∧на_столе(Х));
– поместить(Х) – поместить в некоторую точку стола блок Х,
находящийся в захвате, причем
∀X(поместить(Х)→((пусто(
)∧чисто(Х)∧на_столе(Х)←захват(Х));
– снять(Х,Y) – снять свободный блок Х, стоящий на блоке Y,
причем
18
(∀X∀Y)(снять(Х,Y)→((чисто(Y)∧захват(Х))←
(на(Х,Y)∧чисто(Х)∧пусто( )));
– поставить(Х,Y) – поставить блок Х, находящийся в захвате,
на свободный блок Y, причем (∀X∀Y)(поставить(Х,Y)→
((на(Х,Y)∧чисто(Х)∧пусто( ))←(чисто(Y)∧захват(Х)))
Правило А→(В←С) означает, что из оператора А следует новый
предикат В, если условие С истинно. Во всех предикатах предполагается наличие информации о координатах блоков и возможность
перемещения руки робота в заданную точку.
Используя операторы для изменения «мира блоков», следует
учитывать проблему границ, т. е. сформулировать правила, определяющие предикаты, инвариантные к данному оператору. В наиболее компактной форме каждый оператор можно представить в
виде списков предусловий (П), которым должен удовлетворять мир
блоков для применения оператора, дополнений (Д) к описанию состояния мира и удалений (У) из этого описания, которые являются
результатом применения данного оператора. Эти списки приведены в табл. 2.
Таблица 2
взять(X)
поместить(Х)
снять(Х,Y)
поставить(Х,Y)
П: пусто( )∧чисто(Х)∧на_столе(Х)
Д: захват(Х)
У: пусто( )∧чисто(Х)∧на_столе(Х)
П: захват(Х)
Д: пусто( )∧чисто(Х)∧на_столе(Х)
У: захват(Х)
П: на(Х,Y)∧чисто(Х)∧пусто( )
Д: чисто(Y)∧захват(Х)
У: на(Х,Y)∧чисто(Х)∧пусто( )
П: чисто(Y)∧захват(Х)
Д: на(Х,Y)∧чисто(Х)∧пусто( )
У: чисто(Y)∧захват(Х)
Как видно из табл. 2, списки добавления и вычеркивания обладают некоторой избыточностью, например, предусловия и удаления, описывая аксиомы границ, дублируют друг друга. Однако
преимущество такой избыточности в том, что каждый предикат из
описания состояния, который не упоминается в списках П и У, остается истинным в описании нового состояния.
Используя описание «мира блоков» и правила исчисления предикатов, система управления робота может планировать его действия
для выполнения поставленной задачи. Например, переход от состояния 1 к состоянию 2 (см. рис. 1) может быть выполнен при помощи следующей последовательности операций: снять(a,b), поместить(a),
19
a
b
c
Состояние 1
d
b
e
c
d
e
a
Состояние 2
Рис. 1. «Мир блоков»
взять(b), поставить(b,c), снять(d,e), поставить(d,a). Однако вопрос автоматического поиска этой последовательности относится уже
к проблеме поиска пути в пространстве состояний.
1.5. Язык логического программирования
Среди языков программирования, используемых для компьютерной реализации описаний окружающего мира на основе исчисления предикатов, наибольшее распространение получил язык логического программирования PROLOG (Processing in Logic). Программа, написанная на этом языке, представляет собой набор спецификаций из логики предикатов первого порядка, описывающих
объекты и отношения между ними в предметной области задачи.
Такой набор называется базой данных и может легко пополняться
и модифицироваться при каких-либо изменениях в окружающем
мире. Применение теории предикатов в языке программирования
обеспечивает прозрачный интерфейс и хорошо определенную семантику.
PROLOG относится к классу интерпретируемых языков, работающих в интерактивном режиме. Интерпретатор в диалоговом
режиме ищет ответ на запрос пользователя, касающийся элементов базы данных, выполняя поиск в базе в глубину слева направо
и определяя, является ли данный запрос логическим следствием
содержимого базы данных. Запросы представляют собой шаблоны,
выполненные в том же логическом синтаксисе, что и записи в базе.
Следует отметить, что существуют версии языка, позволяющие
проводить компиляцию набора спецификаций для ускорения выполнения программы.
В качестве примера рассмотрим описание «Мир симпатий и
антипатий Вани, Тани и Оли», используя единственный предикат – любит (кто, что/кого). База данных для такой задачи может
иметь следующий вид:
любит(ваня,таня)
20
любит(таня,оля)
любит(ваня,мороженое)
любит(оля,мороженое)
любит(таня,кофе)
любит(оля,кофе).
После занесения этих записей в базу данных интерпретатору
можно задавать вопросы и получать ответы:
? – любит(ваня,таня); ответ – да
? – любит(оля,Х); ответ – Х = мороженое, Х = кофе
? – любит(ваня,кофе); ответ – нет.
Как видно, при вводе запроса с конкретными значениями термов интерпретатор отвечает да, если находит в базе запись, совпадающую с запросом, или нет, если такая запись отсутствует. В
ответ на запрос с переменной Х выводятся все записи, в которых
подстановка констант из области определения переменной Х приводит к отображению в true.
При обработке запросов язык PROLOG опирается на допущение
о замкнутости мира, которое подразумевает, что любое выражение
считается ложным, если нельзя доказать истинность его отрицания. Это допущение приводит к некоторым трудностям, так как
фактически означает ложность любого факта, который не включен
в базу данных. Например, ответ на запрос ? – любит(ваня, пиво)
будет нет, хотя информация о таком факте просто отсутствует в
базе.
В базу данных языка PROLOG можно записать не только спецификации фактов, но и спецификации правил, описывающих взаимосвязи между фактами путем использования логических операций. В различных диалектах языка PROLOG в качестве условных
обозначений логических операций используются разные символы. В
первом стандарте языка C-PROLOG, разработанном в 1975 – 1980 годах на кафедре искусственного интеллекта университета Эдинбурга Дэвидом Уорреном и Фернандо Перейрой, логическое И (and)
обозначалось запятой, ИЛИ (or) – точкой с запятой, а логическая
импликация – двоеточием с тире. Например, спецификацию, определяющую понятие друзья, как логическую импликацию результата логического И двух термов любит, можно представить с использованием этих обозначений так: друзья(Х,Y): – любит(X,Y),
любит(Y, Z).
Если к набору спецификаций из примера «Мир симпатий и антипатий» добавить правило друзья, то интерпретатору можно задать
вопрос ? – друзья(ваня,оля). В данном случае переменные в правиле соответствуют X = ваня, Y = оля. Вначале интерпретатор ищет
21
значение переменной Z, при которой любит(ваня,Z) истинно. Первая удовлетворяющая этому условию запись – любит (ваня,таня),
т. е. Z = таня. Далее интерпретатор пытается найти запись вида
любит(оля,таня), не находит ее, так как любит(таня,оля) формально не соответствует искомому условию, и возвращается к поиску другого Z в записи любит(ваня,Z). Следующее значение Z, для
которой запись существует в базе данных, мороженое. Дальнейший
поиск записи вида любит(оля,мороженое) заканчивается успехом,
что подтверждает истинность запроса. Таким образом, интерпретатор установил, что Ваня и Оля являются друзьями на почве обоюдной любви к мороженому.
Следует отметить, что, как видно из этого примера, в языке
PROLOG организован поиск в глубину с возвратами, подробно описанный в следующем разделе, причем последовательность просмотра записей определяется их порядком в базе данных.
22
2. Поиск в пространстве состояний
2.1. Граф пространства состояний
Вторым аспектом гипотезы о символьной системе является поиск решения задачи, поставленной перед интеллектуальной системой, среди всех возможных вариантов. Достаточно часто человек
именно так решает проблемы, например, шахматист выбирает наилучший ход или врач рассматривает ряд возможных диагнозов.
Такое поведение лежит в основе метода поиска решения в пространстве состояний.
Наиболее удобно пространство состояний представлять в виде
графа, узлы которого соответствуют различным состояниям окружающего мира или состояниям решаемой задачи, а дуги – допустимым операциям, переводящим мир из одного состояния в
другое, или шагам, выполняемым в процессе решения задачи.
Практически любую задачу можно представить в виде такого графа, выбрав соответствующее описание для состояний и операций.
В таком случае для решения поставленной задачи необходимо найти на графе пространства состояний путь от исходного состояния к
требуемому.
Представление задачи в виде графа пространства состояний позволяет использовать теорию графов как для анализа структуры и
степени сложности задачи, так и для разработки процедуры ее решения.
Швейцарский математик Леонард Эйлер разработал теорию графов для решения «задачи о кенигсбергских мостах». На
рис. 2, а изображена схема расположения города на двух берегах
реки и двух островах, соединенных между собой семью мостами.
Задача: найти такой маршрут обхода города, при котором каждый
мост проходится только один раз. Обозначив берега реки (b1, b2),
острова (o1, o2) и мосты (m1, m2, m3, m4, m5, m6, m7), а также задав предикат соединяет(X,Y,Z), где X,Y – место, т. е. остров или
берег; Z – мост, можно представить систему мостов в терминах
предикатов: cоединяет(о1,о2,m1); cоединяет(о1,b1,m2); cоединяет(о1,b1,m3); cоединяет(о2,b1,m4); cоединяет(о1,b2,m5); cоединяет(о1,b2,m6); cоединяет(о2,b2,m7). Эквивалентное представление
системы мостов в виде графа показано на рис. 2, б.
Чтобы доказать невозможность существования искомого маршрута, Эйлер ввел понятие степени вершины графа, которая равна
числу дуг, соединяющих данную вершину с другими вершинами.
Эйлер показал, что если число вершин нечетной степени не рав23
b1
а)
б)
Берег реки 1
4
3
2
m2
1
Остров 1
Остров 2
o1
Река
5
m4
m3
6
Берег реки 2
7
o2
m1
m6
m7
m5
b2
Рис. 2. Задача о кенигсбергских мостах: а – план города; б – граф представления мостов
но нулю или двум, то маршрут невозможен, так как если вершин
нечетной степени две, то маршрут можно начать в одной из них, а
закончить в другой. Если вершин с нечетной степенью нет, то маршрут должен начинаться и заканчиваться в одной и той же вершине. Из рис. 2, б видно, что данное условие не выполняется, следовательно, искомый маршрут не существует.
Следует отметить, что предикатное представление, описывая отношения между мостами, берегами и островами, не обеспечивает
однозначную связь каждой вершины с дугами и, как следствие, не
позволяет ввести понятие степени вершины. Следовательно, представление окружающего мира в виде графа повышает информативность по сравнению с предикатным представлением.
Напомним некоторые понятия теории графов. Граф – это множество вершин или узлов N1, N2, …, Nn и дуг или ребер, соединяющих некоторые пары вершин. На графе состояний каждая вершина
именована, а если имена двух вершин совпадают, то они считаются
одинаковыми.
Дуги графа обычно идентифицируются именами вершин, которые они соединяют, т. е. обозначаются упорядоченной парой вершин, например (N2, N3). Дуга может иметь собственную метку,
характеризующую данную дугу, например расстояние между узлами транспортной сети. Если каждой дуге приписано направление,
то граф называется ориентированным, а пара вершин, соединяемых направленной дугой, называются соответственно родителем
и потомком. У одной вершины-родителя может быть несколько
вершин-потомков, которые называются братьями. Вершина, не
24
имеющая потомков, называется концевой. Вершина, не имеющая
предков, называется корнем, а граф с такой вершиной – корневым
графом.
Упорядоченная последовательность вершин (N1, N2, …, Nn), где
каждая пара (Ni, Ni+1) является дугой, называется путем длины
n–1 от вершины N1 к вершине Nn. Если путь включает какую-то
промежуточную вершину более одного раза, то путь содержит петлю. Две вершины называются связанными, если существует путь,
содержащий эти вершины. Если в графе для каждой пары вершин
существует единственный путь, то такой граф называется деревом
и, как следствие, не содержит петель. В корневом дереве каждая
вершина имеет единственного родителя. Пример корневого дерева – каталог файловой системы.
Пространство состояний задачи представляется четырьмя множествами:
– множество вершин графа N, определяющих возможные состояния задачи, возникающие в процессе ее решения;
– множество дуг между вершинами A, соответствующих возможным шагам в процессе решения задачи;
– множество начальных состояний задачи S;
– множество целевых состояний D.
Целевые состояния описываются набором некоторых измеряемых свойств состояний, встречающихся в процессе поиска, например выигрышной комбинацией, или набором некоторых свойств
путей, например стоимостью перемещения по дугам.
Допустимым считается любой путь из вершины множества S в
вершину множества D. Следует отметить, что множества S и D являются подмножествами множества N.
Одна из сложностей, возникающих при разработке алгоритма
поиска допустимого пути на графе состояний, состоит в том, что
одно и то же состояние может быть достигнуто разными путями,
что может привести к возникновению петель. В результате возникает проблема выбора оптимального в некотором смысле пути. Например, граф пространства состояний игры в «крестики-нолики»
корневой, так как имеет одно начальное состояние. Он не является
деревом, поскольку очевидно, что некоторые состояния могут быть
достигнуты разными путями, и не имеет петель – все дуги ориентированные и направлены от корневых вершин к потомкам. Такие
графы часто встречаются при поиске в пространстве состояний.
Граф пространства состояний игры «8-головоломка» или игры
в «пятнашки» (рис. 3) тоже корневой, но, в отличие от предыдущего, может иметь циклы. Цель игры – для начальной расстанов25
1
1
3
7 2
6
5
2
Влево
Вверх
4
8
Вниз
Вправо
3
1
4
3
1
4
3
1
4
8
6
7
6
2
5
8
7
4
6
58 7
6
7
5
8
2
5
2
5
Вверх
8
Влево
Вниз
3
2
Вправо
4
4
3
1
4
3
1
4
3
1
4
3
1
7
6
5
7
6
7
8
6
7
8
6
5
8
2
8
2
5
2
5
2
Рис. 3. Фрагмент пространства состояний игры в «пятнашки»
ки фишек с номерами от 1 до 8 найти такую последовательность их
перемещения на пустое место, в результате которой фишки займут
заданное положение, например по возрастанию номеров слева направо и сверху вниз. Полное число возможных состояний достаточно велико (8!=40320), если учитывать симметричные отражения.
Заметим, что определение очередного хода значительно удобнее
задавать перемещением пустой клетки в одно из допустимых положений, как это показано на рис. 3.
Следует отметить, что полное пространство состояний этой игры
распадается на два несвязанных подграфа одинакового размера, из
чего следует, что половина состояний недостижима из любой заданной начальной вершины.
Для «мира блоков», описанного в предыдущем разделе, тоже
может быть сформирован граф пространства состояний, фрагмент
которого показан на рис. 4. Вершины графа соответствуют возможным состояниям «мира блоков». Дуги графа помечены операциями, которые могут быть выполнены в состоянии, соответствующем
родительской вершине. Планирование операций, которые необходимо выполнить для получения требуемого расположения блоков,
можно представить как поиск пути на графе возможных состояний
от текущего расположения блоков к целевому расположению.
26
a
b
Снять (a,b)
b
d
c
e
Взять (c)
a
d
a
c
e
b
Поставить (a,c)
c
Снять (d,e)
d
a
d
e
b
c
Поставить (a,d)
e
Поместить (a)
a
b
a
d
c
e
d
b
c
e
d
a
b
c
e
Рис. 4. Фрагмент графа пространства состояний «мира блоков»
Примером задачи, в которой цель задается свойством пути, является «задача коммивояжера», заключающаяся в том, что необходимо найти кратчайший путь, соединяющий все вершины некоторого графа. Вершины этого графа – пункты, которые должен
посетить коммивояжер, например города. Помеченные дуги – возможность непосредственного перемещения между этими пунктами,
например длина пути между городами в километрах. Такой граф
для шести городов представлен на рис. 5, а и на рис. 5, б – фрагмент
графа состояний задачи при условии, что начальный пункт – A.
Любой маршрут удобно представить последовательностью пунктов назначения, например в произвольном порядке (A, B, E, C, F,
D), и его длиной. Полное число вершин графа состояний составляет
N!, где N – число пунктов назначения (6!=720), при условии, что
коммивояжер не должен возвращаться в исходный пункт и каждый пункт имеет непосредственную связь со всеми другими пунктами. В данном случае целью является не некоторое состояние в
пространстве поиска, а нахождение на графе состояний пути минимальной длины, что в принципе требует полного перебора всех состояний. Однако с ростом N число вершин графа состояний растет
так быстро, что прямой перебор всех возможных вариантов становится неосуществимым.
27
B
а)
12
0
11
28
10
A
33
17
С
25
4
31
13
B
D
21
A
б)
C
C
D
E
D
F
E
17
30
24
F
12
E
D
E
F
E
F
D
F
D
F
83
E
76
F
94
D
82
96
E
E
D
91
Рис. 5. Задача коммивояжера: а – граф возможных путей между городами; б – фрагмент графа пространства состояний
Задача коммивояжера используется на практике, в том числе
обеспечивает решение проблемы разводки электронных схем, задачи рентгеновской кристаллографии и маршрутизации при производстве СБИС.
2.2. Алгоритмы поиска с последовательным перебором
Поиск в пространстве состояний можно вести как в прямом
направлении, т. е. от исходных данных к цели, так и в обратном
направлении. При прямом поиске к исходному состоянию задачи
применяются возможные операции, приводящие к другим состояниям, причем процесс продолжается до получения требуемого состояния. При обратном поиске анализируются операции, которые
могут привести к заданному состоянию, в результате чего получается множество промежуточных целей. Процесс повторяется, пока
не будет получено состояние, соответствующие исходному состоянию задачи.
Например, необходимо определить: является ли человек А прямым потомком человека В при условии, что полные генеалогические деревья для A и В известны. Прямой поиск на таком графе
требует просматривать всех потомков В до тех пор, пока не будет
найден А. Если считать, что в генеалогическом дереве существует
10 поколений и каждая семья имеет в среднем трех детей, то при
прямом поиске потребуется просмотреть до 310 вершин. При обрат28
ном поиске потребуется просмотреть не более 210 вершин, так как
каждый человек имеет только прямых двух предков.
Процесс поиска от цели может быть более эффективен, чем прямой поиск, в тех случаях, когда цель поиска явно сформулирована,
имеется большое число правил, позволяющих эффективно ограничить множество возможных ветвей на каждом шаге, исходные
данные приведены не полностью и могут добавляться в процессе решения задачи. Например, при диагностике болезни, как правило, в
начальный момент имеются результаты далеко не всех возможных
анализов и тестов. Рассматривая возможные диагнозы в качестве
целей, можно проводить поиск в обратном направлении, получая
необходимые анализы в зависимости от выбранной гипотезы о диагнозе для его подтверждения или отмены.
Любой поиск в пространстве состояний основан на алгоритме
поиска с возвратами, который заключается в том, что в процессе
поиска последовательно генерируются новые возможные состояния и формируются три списка состояний:
– список еще не рассмотренных состояний, для того чтобы можно было вернуться к любому из них;
– список просмотренных состояний, для того чтобы исключить
их повторный просмотр;
– список узлов текущего просматриваемого пути, который возвращается в качестве результата поиска при достижении цели.
Каждое новое состояние, сгенерированное в процессе поиска,
проверяется на вхождение в эти списки для предотвращения зацикливания.
Алгоритм поиска с возвратами запускается из начального состояния и следует по некоторому пути до тех пор, пока не будет достигнуто целевое состояние или концевая вершина графа состояний.
В последнем случае алгоритм возвращается в какую-либо из пройденных вершин и просматривает ее вершины-братья, спускаясь по
одной из ветвей.
Существует две возможные стратегии определения порядка просмотра вершин-потомков: поиск в глубину и поиск в ширину, а также основанный на сочетании этих стратегий метод итерационного
заглубления.
При поиске в глубину необходимо сформировать всех потомков
текущего состояния и затем рассматривать одного из них как следующее состояние. Если дальнейшие потомки не найдены, то рассматриваются вершины-братья. Например, на графе состояний,
показанном на рис. 6, последовательность просмотра вершин при
условии, что цель – состояние U и очередность просмотра вершин29
A
C
B
E
F
K
L
S
T
M
D
H I
G
N
O
P
J
Q
R
U
Рис. 6. Граф, иллюстрирующий алгоритмы поиска
братьев соответствует порядку их генерации (т. е. по алфавиту) будет следующая: A, B, E, K, S, L, T, F, M, C, G, N, H, O, P, U.
Как видно из алгоритма, поиск в глубину не гарантирует нахождение кратчайшего пути от начального состояния к цели. Его следует использовать, если известно, что путь к цели будет длинным,
так как поиск в глубину не будет тратить время на просмотр большого количества близких к начальному состояний. Однако он может затеряться в глубинах графа, пропуская более короткие пути
к цели, или застрять на не ведущем к цели длинном пути. Поиск
в глубину эффективен для графов с высокой степенью связности,
поскольку он не требует запоминания всех узлов каждого уровня.
В этом случае степень использования пространства состояний является линейной функцией длины пути.
Поиск в ширину формирует всех потомков для всех имеющихся
на текущем уровне вершин и просматривает их. Если цель не достигнута, то формируется следующий уровень вершин. Например,
для графа на рис. 6 последовательность просмотра вершин при поиске в ширину будет следующая: A, B, C, D, E, F, G, H, I, J, K, L,
M, N, O, P, Q, R, S, T, U.
Из алгоритма видно, что поиск в ширину гарантирует нахождение кратчайшего пути от начального состояния к цели. Его следует
использовать при низком коэффициенте ветвления, так как если
состояния имеют высокое среднее число потомков, то экспоненциальный характер зависимости числа узлов графа от числа уровней
приводит к недопустимому увеличению пространства состояний.
Метод итерационного заглубления заключается в последовательном увеличении глубины поиска на единицу на каждой итерации.
30
На первом шаге глубина поиска – один уровень, т. е. просматриваются все возможные состояния, являющиеся непосредственными
потомками начального состояния. Если цель не найдена, то выполняется следующий шаг с предельной глубиной поиска 2 и т.д. На
каждой итерации алгоритм выполняет поиск в глубину с учетом текущего предельного числа уровней. Например, для графа на рис. 6
последовательность просмотра вершин при поиске с итерационным
заглублением будет следующая: A, B, C, D, E, K, L, F, M, G, N, H,
O, P, I, Q, J, R, S, T, U. Как видно, последовательность просмотра
вершин отличается от последовательности их просмотра при поиске в ширину, хотя и в том и в другом подходе цель достигается после просмотра всех узлов.
В процессе поиска узлы просматриваются по уровням, поэтому поиск с итерационным заглублением гарантирует нахождение
кратчайшего пути от начального состояния к цели.
Все описанные методы поиска представляют собой итерационные, т. е. пошаговые, процессы, причем на каждом шаге необходимо проверять принадлежность нового состояния одному из списков
для исключения зацикливания. Наиболее эффективным и компактным алгоритмом, решающим эту задачу, является рекурсивный
алгоритм.
Процедура проверки принадлежности элемента списку рекурсивным методом заключается в следующем:
function member(item, list) of Boolean; // item – проверяемый элемент, list – список
begin
if список пуст then return False
else
if item = первый элемент списка then return True
else
begin
tail:= список после удаления первого элемента;
return member(item,tail) // рекурсия
end
end.
Рекурсия представляет собой эффективный инструмент для управления массивами данных, имеющих неопределенный размер,
например списками, стеками, графами. Любая итерационная процедура может быть реализована рекурсивно, следовательно, рекурсивные по своей природе алгоритмы поиска на графе пространства
состояний целесообразно реализовывать рекурсивно. Например,
31
рекурсивная форма алгоритма поиска в глубину имеет следующий
вид:
function depth_search(current_state) of Boolean; // current_state –
текущий узел графа состояний; список closed – глобальная переменная
begin
if current_state = целевое состояние then return True;
добавить current_state в список closed;
while current_state имеет непроверенные потомки
begin
child:= следующий непроверенный потомок current_state;
if child не член списка closed then
if depth_search(child) = True then return True // рекурсия
end;
return False // граф исчерпан
end.
Данный алгоритм рассматривает потомков текущего состояния
по одному, для каждого из них рекурсивно находятся и рассматриваются потомки, причем процесс продолжается до тех пор, пока не
будет найдено целевое состояние или просмотрен весь граф.
2.3. Эвристические алгоритмы поиска
На первый взгляд, рассмотренные выше исчерпывающие методы поиска, т. е. последовательный перебор всех возможных путей
на графе до тех пор, пока не будет найден искомый путь, достаточно
продуктивны. Однако, во-первых, такой подход трудно назвать интеллектуальным, а во-вторых, огромный размер пространства состояний для большинства практических задач делает этот подход
неприемлемым с практической точки зрения. Например, игре в
шахматы соответствует около 10120 различных состояний игровой
доски. Формирование графа таких размеров, и тем более поиск в
нем выигрышной последовательности ходов выходит за рамки возможностей любого компьютера, размеры и время работы которого
должны быть ограничены.
Для выбора подходящего направления движения на графе состояний интеллектуальные системы, использующие для решения
поставленной перед ними задачи метод поиска в пространстве состояний, применяют набор направляющих правил или эвристик.
Следует иметь в виду, что эвристики не абсолютно надежны, так
как основываются на опыте и знаниях о природе задачи. Эвристический алгоритм может привести к субоптимальному решению
32
или даже не найти решение вообще, причем это ограничение носит
принципиальный характер и не может быть полностью устранено
улучшением алгоритма поиска.
Таким образом, представление задачи в виде поиска в пространстве состояний обеспечивает формализацию процесса решения, а
эвристики вносят в этот формализм интеллектуальную составляющую. Эвристику приходится использовать в двух случаях:
– когда проблема не имеет точного решения в связи с неопределенностью в постановке задачи или в исходных данных (например,
медицинская диагностика или система технического зрения);
– когда задача имеет точное решение, но стоимость его поиска
неприемлема из-за размеров пространства состояний, например, в
игровых задачах рост пространства состояний с увеличением числа
анализируемых ходов носит экспоненциальный характер.
Разработка алгоритмов для эвристического поиска и сегодня остается одним из основных объектов исследования в области искусственного интеллекта. Эвристические алгоритмы включают в себя
вычисление некоторой оценки для точки в пространстве состояний
и использование этой оценки или меры для выбора следующего
шага в процессе поиска решения.
Выбор эвристики во многом зависит от конкретной задачи, например, для поиска наилучшего хода в игре «крестики-нолики»
можно использовать следующий алгоритм. Для каждого возможного хода подсчитать число потенциально выигрышных линий
(на рис. 7 показаны выигрышные линии при первом ходе), после
чего выбрать в качестве наилучшего ход с максимальным числом.
Согласно такой эвристике, наилучший первый ход – центральная
клетка, что совпадает с общеизвестной стратегией.
Приведенная эвристика является примером стратегии, основанной на поиске экстремума, при которой для дальнейшего поиска
Х
Х
Х
Рис. 7. Потенциально выигрышные линии при первом ходе в игре «крестики-нолики» с учетом симметрии пространства состояний
33
выбирается наилучший потомок, а его братья из дальнейшего рассмотрения исключаются, причем если оценка всех потомков ниже,
чем текущее состояние, то алгоритм останавливается. Основная
проблема таких алгоритмов – это остановка при достижении локального максимума функции оценки узлов. Например, если при
игре в «пятнашки» в качестве оценки позиции используется число
правильно расположенных фишек, то ход, ухудшающий текущую
позицию, не будет признан лучшим. Хотя часто для передвижения
фишки в нужную позицию необходимо временно сдвинуть правильно стоящую фишку.
«Жадный» алгоритм поиска использует список нерассмотренных состояний, присваивая каждому его члену некоторую оценку.
При выборе следующего шага алгоритм сортирует список нерассмотренных состояний по уменьшению или увеличению оценки,
формируя приоритетную очередь, и выбирает рассматриваемый
узел из начала очереди.
В качестве примера приведено дерево пространства состояний
с оценками узлов, сгенерированными в процессе поиска (рис. 8).
Если целью является состояние U, причем сортировка списка нерассмотренных состояний производится по уменьшению, то последовательность шагов с учетом состава списков нерассмотренных
(open) и рассмотренных (closed) узлов будет следующая.
1. Оценка начального состояния А; open: A-5; closed: пусто.
2. Для A формируются и оцениваются потомки (B, C, D); open:
B-4, C-4, D-6; closed: A.
3. Для B формируются и оцениваются потомки (E, F); open: C-4,
E-5, F-5, D-6; closed: B, A.
A5
E6
K
S
F5
L
T
D6
C4
B4
M
H3
G4
N
I
J
Q
O2
P3
U2
Рис. 8. Эвристический поиск «жадным» алгоритмом
34
R
4. Для C формируются и оцениваются потомки (G, H); open: Н-3,
G-4, E-5, F-5, D-6; closed: С, B, A.
5. Для H формируются и оцениваются потомки (O, P); open: O-2,
Р-3, G-4, E-5, F-5, D-6; closed: Н, С, B, A.
6. Для O потомков нет и цель не достигнута, выбирается узел P
из очереди; open: Р-3, G-4, E-5, F-5, D-6; closed: O, Н, С, B, A.
7. Для P формируется и оценивается потомок (U); open: U-2, G-4,
E-5, F-5, D-6; closed: P, O, Н, С, B, A.
8. Для U – цель достигнута.
Из приведенного примера видно, что «жадный» алгоритм, вопервых, позволяет выходить из тупикового состояния (узел O), а
во-вторых, стремится прийти к цели кратчайшим путем (путь алгоритма при просмотре узлов показан на рис. 8 жирными стрелками).
Основной недостаток «жадного» алгоритма – выбор следующего
шага только на основе некоторой оценки всех возможных шагов,
без оценки возможных последующих состояний, что может привести к получению неоптимального решения. Например, в случае
поиска решения «задачи коммивояжера», граф которой представлен на рис. 5, в качестве оценки можно принять расстояние от выбранного на текущем шаге города до еще не пройденных городов.
В таком случае «жадный» алгоритм выбирает в качестве следующего шага город, расстояние до которого минимально. Очевидно, результат применения этого алгоритма будет следующий: A – B – D –
F – E – C длина маршрута (85), что явно не является маршрутом,
минимальным по длине. Основная причина неудачи «жадного»
алгоритма при поиске решения в «задаче коммивояжера» заключается в отсутствии в данном случае описания цели в пространстве
состояний.
Более гибкая стратегия поиска используется в минимаксном
алгоритме, применяемом в играх с двумя участниками, каждый
из которых стремится к победе и имеет одинаковую информацию
о текущем состоянии игры. Метод минимакса основан на предположении, что на каждом шаге противник выбирает наилучший из
возможных ходов.
В данном алгоритме противников принято называть MIN и
MAX, причем MAX – игрок, стремящийся выиграть, т. е. максимизировать свое преимущество, а MIN – его противник, стремящийся
соответственно минимизировать преимущество своего соперника,
т. е. достичь наихудшего для MAX состояния.
В качестве примера приведем игру «Ним», пространство состояний которой можно сформировать в полном объеме. В начале игры
35
на стол перед двумя участниками выкладывается кучка из некоторого числа фишек. Игрок, делающий первый ход, должен разделить
эту кучку на две неравные части. Следующий игрок должен также
разделить одну из уже имеющихся кучек. Проигрывает тот, кто не
может сделать хода, т. е. ни одна из имеющихся на столе кучек не
может быть разделена на неравные части. Пример пространства
состояний для игры «Ним» с семью фишками приведен на рис. 9.
Каждый уровень пространства состояний помечен именем игрока,
выполняющего очередной ход (в примере первый ход делает MIN,
т. е. противник). Каждой конечной вершине графа присвоено значение 1, если победитель MAX, или 0, если победитель MIN, что
является оценками конечных состояний. В процессе реализации
минимаксного алгоритма эти значения передаются снизу вверх по
графу согласно следующим правилам:
– если родительский узел относится к уровню MAX, то ему присваивается максимальное значение из значений его потомков;
– если родительский узел относится к уровню MIN, то ему присваивается минимальное значение из значений его потомков.
В результате с каждым состоянием связывается значение, показывающее наилучшее состояние, которое игрок MAX может до7
MIN
1
1
1
6 1
1
5 2
4 3
MAX
1
0
5 1 1
1
0
3 2 2
4 2 1
3 3 1
MIN
1
0
4 1 1 1
0
3 2 1 1
2 2 2 1
MAX
0
1
3  1  1 1  1
2  2  1 1  1
MIN
MAX
0
2  1  1  1 1  1
Рис. 9. Пространство состояний для игры в «Ним» с применением минимаксного алгоритма
36
стичь, если игрок MIN будет выбирать наилучшее продолжение из
данного состояния. На рис. 9 показаны значения узлов, полученные в результате применения минимаксного алгоритма. Жирные
стрелки демонстрируют последовательность выигрышных ходов.
Очевидно, что в «Ним» игрок, делающий первый ход, может выиграть, только если его противник сделает ошибочный ход.
В более сложных играх построить полный граф пространства
состояний невозможно. В таком случае для выбора наилучшего из
всех возможных на данный момент ходов строится семейство графов с фиксированной глубиной поиска, причем число графов равно
числу возможных ходов, а каждый граф состоит из всех возможных состояний до заданной глубины. Далее для каждого графа
производится оценка конечных узлов, которые передаются корневой вершине согласно приведенным выше правилам. В качестве наилучшего выбирается тот ход, оценка которого максимальна.
Эвристика, основанная на минимаксном алгоритме, интегрирует
отдельные оценки состояний на заданной глубине в значение, которое присваивается родительскому состоянию. На рис. 10 показан
граф некоторого пространства состояний глубиной три с оценками
концевых вершин и значениями остальных вершин, полученными
по минимаксному алгоритму.
Из сказанного выше следует, что минимаксный алгоритм фактически реализует просмотр в ширину, не выполняя оценок состояний на промежуточных уровнях, причем требует двух проходов
по области поиска. На первом проходе (вниз) формируется полное
дерево состояний на заданную глубину, где и применяется эвристическая оценка. На втором проходе (вверх) происходит последовательное присвоение этих оценок узлам, вплоть до корневой вершины графа. Сократить число рассматриваемых узлов позволяет
алгоритм альфа-бета-усечения, являющийся расширением минимаксного алгоритма.
3
MIN
MAX
MIN
3 C
3
MAX
3
9
0
A
3
2
0
7
2
6
2 3 5 9 0 7 4 2 1 5 6
Минимаксный алгоритм
3
2 3 5
E
2
0 D
B 0
2
0
2
1
Алгоритм альфабетаусечения
Рис. 10. Оценка пространства состояний различными алгоритмами
37
Идея алгоритма альфа-бета-усечения заключается в том, что
вместо формирования полного графа состояний следует выполнить
поиск в глубину до заданного уровня и вычислить эвристические
оценки для состояний этого уровня. Если эти узлы уровня MIN,
то максимальное из этих значений передается предыдущему родительскому состоянию, т. е. на уровень MAX, и далее на уровень
MIN, как граничное значение бета. Затем алгоритм опускается к
потомкам этого уровня, игнорируя те состояния, оценка которых
больше или равна данному значению бета. Аналогичные процедуры выполняются на уровне MAX для вычисления максимального
уровня отсечения альфа. Алгоритм прекращает просмотр состояний на промежуточном уровне, если для узла уровня MIN значение
бета меньше или равно значению альфа любого из его предков MAX,
а для узла уровня MAX значение альфа больше или равно значению
бета любого из его предков MIN. Таким образом, значение альфа,
связанное с узлами MAX, никогда не уменьшается, а значение бета,
связанное с узлами MIN, никогда не увеличивается. В результате
из рассмотрения могут быть исключены как отдельные узлы, так и
целые поддеревья, что значительно сужает область поиска, причем
поиск производится за один проход.
На рис. 10 приведен результат применения алгоритма альфабета-усечения (состояния без числовых меток не оценивались, отсеченные ребра помечены). Для узла А β = 3, т. е. оценка узла А будет не больше чем 3. Тогда узел В является β-усеченным, так как
5 > 3. Для узла С α = 3, т. е. оценка узла С будет не меньше чем 3.
Тогда узел D является α-усеченным, так как 0 < 3. Узел Е тоже αусеченный, так как 2 < 3. Как видно из рис. 10, результат оценки
корневой вершины с применением алгоритма альфа-бета-усечения
совпадает с результатом оценки минимаксным алгоритмом, но количество просмотренных вершин значительно меньше.
Из анализа приведенных выше алгоритмов можно сделать вывод, что разработка хорошей эвристики – сложная эмпирическая
проблема, требующая учета возможно большей информации об
особенностях конкретной задачи как при вычислении оценки состояний, так и при выборе последовательности просмотра узлов.
Разработчик вынужден искать оптимальное сочетание количества просматриваемых узлов и сложности вычисления их оценки.
Сложная эвристика, учитывающая множество различных факторов, позволяет сократить число просматриваемых состояний, но
объем необходимых при этом вычислений может привести к таким
же временным затратам, как и более простая эвристика с увеличенной глубиной поиска.
38
2.4. Язык обработки списков
Среди языков программирования, используемых для компьютерной реализации методов поиска на графе пространства состояний, широкое распространение получил язык обработки списков
LISP (Lisp Processing), который был предложен Джоном Маккарти
в конце 50-х годов и предназначался в первую очередь для символьных вычислений. Язык LISP построен на теории рекурсивных функций, основным структурным блоком программ и данных в нем
является список.
Изначально LISP был компактным языком, состоящим из процедур формирования и обработки списков, позволяющим определять новые функции для работы со списками, проверять равенства
и оценивать выражения. Единственными средствами управления
данными были рекурсия и условные операторы. Развиваясь, язык
стал поддерживать все большее число встроенных функций для
работы со списками как со связанными структурами указателей,
что, во-первых, освободило программиста от необходимости явно
управлять указателями и реализовывать операции над ними, а вовторых, привело к появлению многочисленных диалектов, один из
которых – Common LISP – был принят в 1983 году в качестве стандарта языка.
Синтаксическими элементами языка программирования LISP
являются символьные выражения или s-выражения, в виде которых представляются и программы, и данные. S-выражение может
быть или списком, или атомом. Атомы – это базовые единицы
языка, включающие числа и символы, а список – это последовательность атомов или других списков, разделенных пробелами и
заключенных в скобки. Например, (1 2 3 4), (a (b c) (d (e f))), (+ 14
5). Отметим, что последний пример интерпретируется в LISP как
операция сложения в префиксной форме записи. Аргументы функции сами могут быть списками, к примеру, выражение (– (+ 3 4) 7)
представляет собой композицию функций и интерпретируется так:
«вычесть 7 из результата сложения 3 и 4».
В стандарт LISP включен полный спектр арифметических функций, функции организации циклов, работы со списками, выполнения ввода-вывода данных и многие другие. Новые функции определяются с помощью стандартной функции defun, первым аргументом которой является имя определяемой функции, вторым –
список ее формальных параметров, а остальные – s-выражения,
составляющие тело новой функции. Например, (defun square (x) (*
x x)) определяет функцию x2. После определения новую функцию
39
можно использовать как любую другую функцию языка, в том числе и для построения новых функций. Например, функцию вычисления длины гипотенузы прямоугольного треугольника можно определить как (defun hypotenuse (x y) (sqrt (+ (square x) (square y)))),
где sqrt – стандартная функция LISP.
В приведенном ниже примере используются еще несколько функций и специальных обозначений из стандарта языка.
Функция quote или апостроф (‘) зависит от одного аргумента и
возвращает его без изменений. Например, (+ 1 3) → 4, а ‘(+ 1 3) →
(+ 1 3).
Функция list принимает любое количество аргументов и строит
на их основе список. Например, (list (+1 3) (+3 4)) → (4 7), а (list
‘(+ 1) (+3 4)) → (+ 1 7).
Параметрами функции cons являются два s-выражения, которые оцениваются функцией. В результате возвращается список,
первым элементом которого является значение первого параметра,
а хвостом – значение второго. Например, (cons 1 ‘(2 3 4)) → (1 2 3 4),
a (cons ‘(1 2) ‘(3 4)) → ((1 2) 3 4).
Функция nth получает в качестве аргументов номер и список,
а возвращает элемент списка с указанным номером, причем нумерация элементов начинается с нуля, например, (nth 2 (a b c d)) →
c, a (nth 2 ((a 1) (b 2) (c 3) (d 4))) → (c 3). Если элемент с указанным
номером отсутствует, то выводится пустой список, обозначаемый
служебным словом nil, которое является одновременно и атомом,
и s-списком.
Функция member определяет принадлежность s-выражения
списку и возвращает nil, если это выражение не является элементом списка, или список, содержащий s-выражение в качестве
первого аргумента. Например, (member 4 ‘(1 2 3 4 5 6)) → (4 5 6), a
(member 4 ‘(1 2 3)) → nil.
Функция cond реализует ветвление. Аргументом этой функции
является множество пар списков «условие – действие». Например,
функцию «абсолютная величина» можно определить так: (defun
abs_value(x) (cond((< x 0)(–x))(t x))). Здесь атом t – служебное слово,
которому всегда соответствует истина. В качестве условий оператора cond можно использовать любые оцениваемые s-выражения.
Существуют и стандартные функции, возвращающие логическое
значение t или nil в зависимости от результата сравнения: =, >,
>=, <, <=, null. Последняя функция получает в качестве аргумента
список и возвращает t, если он пуст.
40
Функция equal возвращает значение «истина», т. е. t, если два
списка, полученных в качестве аргументов, синтаксически идентичны. В противном случае возвращается nil.
Функция not зависит от одного аргумента и возвращает t, если
этот аргумент равен nil, и nil – в противном случае. Функции and и
or могут иметь любое число аргументов и ведут себя так же, как и
соответствующие им логические операторы. Это означает, что функция and возвращает значение последнего аргумента или nil, если
один из аргументов имеет значение nil, а функция or возвращает
значение первого отличного от nil аргумента или nil, если все аргументы имеют это значение.
Существует изоморфное соответствие между списками и деревьями, что открывает широкие возможности по применению списков
для представления любой древовидной структуры, в том числе и дерева поиска в пространстве состояний. Простейшим способом построения соответствия между списком и деревом является создание
для каждого списка узла без метки, потомками которого являются
элементы списка. В результате атомарные элементы становятся
листовыми узлами дерева, а самый внешний список – его корнем.
Задачи искусственного интеллекта требуют обработки больших
объемов знаний о предметной области, причем используемые для
представления этих знаний иерархические структуры данных достаточно сложны. Поскольку LISP легко позволяет определять
новые функции для работы с символьными списками путем рекурсивной обработки, он является одним из лучших языков для реализации систем ИИ.
В качестве примера можно рассмотреть поиск решения известной «задачи о переправе через реку» с использование возможностей LISP. Задача формулируется следующим образом. Фермеру
(farmer) нужно с помощью лодки переправить волка (wolf), козу
(goat) и капусту (cabbage) с западного (w) берега на восточный (e)
берег реки. Лодка одновременно может перевозить не более двух
пассажиров, один из которых сам фермер. Если волк останется на
берегу с козой, то он ее съест. Если коза останется на берегу с капустой, то она ее съест. В присутствии фермера поедание невозможно.
Состояние задачи (state) можно представить списком из четырех
элементов, каждый из которых обозначает берег, на котором находятся соответственно человек, волк, коза и капуста. Например,
список (e w e w) означает, что человек и коза находятся на восточном берегу, а волк и капуста – на западном.
Процесс поиска решения на графе состояний представлен на
рис. 11. Здесь используется алгоритм поиска в глубину с возвра41
wwww
eeww
ewww
ewew
ewwe
wwew
wwww
eeew
ewew
weew
wwew
eeww
eeew
wwwe
weww
eewe
weww
wewe
eewe
eeee
ewee
wwee
wwew
ewwe
ewee
wwwe
Рис. 11. Поиск решения задачи о переправе в пространстве состояний
тами и проверкой возможности существования сгенерированного
состояния. Для исключения зацикливания формируются списки
исследованных состояний.
Как видно из рис. 11, существует практически единственная
последовательность действий фермера, приводящая к нужному результату:
– фермер перевозит на восточный берег козу и возвращается
один;
– перевозит волка или капусту и возвращается с козой;
– если на западном берегу осталась капуста, то перевозит ее,
если волк – то его;
– возвращается за оставшейся козой и перевозит ее.
Базовыми функциями, определяющими состояние списка, являются конструктор make_state и четыре функции доступа farmer_
side, wolf_side, goat_side, cabbage_side, которые можно определить
как:
(defun make_state (f w g c) (list f w g c))
(defun farmer_side (state) (nth 0 state))
42
(defun wolf_side (state) (nth 1 state))
(defun goat_side (state) (nth 2 state))
(defun cabbage_side (state) (nth 3 state))
Функция opposite, возвращающая местоположение, противоположное исходному, имеет вид
(defun opposite (side) (cond ((equal side ‘e) ‘w) ((equal side ‘w) ‘e))))
Функция safe, проверяющая состояние на возможность «опасных» позиций, когда фермер находится на противоположном берегу от козы и капусты или от волка и козы, возвращает состояние без
изменений, если оно безопасно, и nil в противоположном случае.
Функция имеет вид
(defun safe (state) cond
((and (equal (goat_side state) (wolf_side state)) // волк съест
козу //
(not (equal (farmer_side state) (wolf_side state)))) nil)
((and (equal (goat_side state) (cabbage_side state)) // коза съест
капусту //
(not (equal (farmer_side state) (goat_side state)))) nil)
(t state)))
Функция safe используется при определении четырех функций
возможных переходов:
(defun farmer_takes_self (state) (safe (make_state (opposite (farmer_
side state))
(wolf_side state) (goat_side state) (cabbage_side state))))
(defun farmer_takes_wolf (state) (cond ((equal (farmer_side state)
(wolf_side state))
(safe (make_state (opposite (farmer_side state)) opposite (wolf_side
state))
(goat_side state) (cabbage_side state)))) (t nil)))
(defun farmer_takes_goat (state) (cond ((equal (farmer_side state)
(goat_side state))
(safe (make_state (opposite (farmer_side state)) (wolf_side state)
(opposite (goat_side state)) (cabbage_side state)))) (t nil)))
(defun farmer_takes_cabbage (state) (cond ((equal (farmer_side state)
(cabbage_side state))
(safe (make_state (opposite (farmer_side state)) (wolf_side state)
(goat_side state)
(opposite (cabbage_side state))))) (t nil)))
Функция path реализует поиск с возвратами в пространстве состояний и одновременно генерирует эти состояния путем рекурсивных вызовов. Для предотвращения попадания в замкнутые циклы
используется список просмотренных состояний been_list. Для про43
верки отсутствия текущего состояния в списке используется функция member. Последовательность состояний, приводящая к цели
(goal), находится в списке been_list, причем в обратном порядке.
Для инверсии этого списка используется функция reverse:
(defun path (state goal been_list) (cond ((null state) nil)
((equal state goal) reverse (cons state been_list))) ((not (member
state been_list))
(or (path (farmer_takes_self state) goal (cons state been_list))
(path (farmer_takes_wolf state) goal (cons state been_list))
(path (farmer_takes_goat state) goal (cons state been_list))
(path (farmer_takes_cabbage state) goal (cons state been_
list))))))
Для вызывающей функции solve_fwgc параметрами являются
начальное и целевое состояния, причем been_list при первом вызове функции path присвоено значение nil:
(defun solve_fwgc (state goal) (path state goal nil)
Следует отметить, что в LISP программисту приходится реализовывать стратегию поиска в явном виде, однако данный недостаток компенсируется возможностью наглядного представления «поведения» программы в процессе поиска решения в пространстве
состояний.
44
3. Распознавание образов
3.1. Описание объектов набором признаков
Одним из важнейших направлений ИИ является создание систем распознавания. Методы распознавания находят широкое применение в экспертных системах, в робототехнике, в системах идентификации и контроля доступа, а также являются необходимым
элементом эвристического поиска решений, позволяя провести
ранжирование возможных состояний.
Длительное время вопросы распознавания рассматривались человеком лишь с позиций методов биологии и психологии, причем
целью изучения являлись в основном качественные характеристики, не позволяющие вскрыть и точно описать соответствующий
механизм принятия решений. Появление кибернетики позволило
ввести в изучение психологического процесса распознавания образов, лежащего в основе принятия любых решений, количественные
методы, что открыло принципиально новые возможности в исследовании и проектировании систем распознавания.
Исторически сложилось так, что многие задачи распознавания,
например распознавание текста, устной речи, оценка авиационной
ситуации в районе аэропорта авиадиспетчером, распознавание посадочной полосы летчиком в сложных условиях и т. п., человек,
как правило, решает достаточно быстро и эффективно. Примечательно, что в процессе такой деятельности число принимаемых решений по результатам распознавания ситуаций конечно, а число
состояний внешней среды, оцениваемых в процессе распознавания
и собственно приводящих к принятию решения, может быть бесконечным. Например, машинистка, печатающая под диктовку, из
практически бесчисленного множества вариантов произношения
одного и того же звука выбирает только один, ударяя по соответствующей клавише пишущей машинки. В результате она безошибочно печатает слова, независимо от их искажения при устном произнесении.
К принятию такого конечного числа решений человек подготовлен всем своим жизненным опытом. Попытка автоматизации процессов, необходимым элементом которых является распознавание,
привела к тому, что, прежде всего, были созданы автоматы, способные реагировать на множество изменений характеристик внешней
среды некоторым ограниченным числом рациональных решений
(реакций) исполнительных органов этих автоматов. Например,
автомат, управляющий технологическим процессом выпуска ка45
кой-либо продукции, реагирует на случайные изменения качества
продукции путем регулирования количества той или иной компоненты исходного материала, режима работы и т. п., но только при
достижении определенного уровня этих изменений. То есть, реакция осуществляется не на любое изменение, а на их множество,
превышающее некоторый порог.
Основными целями замены человека в системах, требующих
распознавания, являются:
– освобождение человека от однообразных или опасных операций;
– повышение качества выполняемых работ;
– повышение скорости решения задач.
В течение достаточно продолжительного времени проблема
распознавания привлекает внимание специалистов в области прикладной математики и информатики. Следует отметить работы
Р. Фишера, выполненные в 20-х годах и приведшие к формированию дискриминантного анализа как одного из разделов теории и
практики распознавания. В 50 – 60-е годы ХХ века на основе теории статистических решений были найдены алгоритмы, обеспечивающие отнесение нового объекта к одному из заданных классов.
В рамках кибернетики начало формироваться новое научное направление, связанное с разработкой теоретических основ и практической реализацией систем распознавания объектов, явлений,
процессов. Новая научная дисциплина получила название «Распознавание образов».
Таким образом, базой для решения задач отнесения объектов
или явлений к тому или иному классу послужили результаты классической теории статистических решений. На ее основе были построены алгоритмы, обеспечивающие по экспериментальным измерениям параметров (признаков), характеризующих объект (образ),
а также по некоторым априорным данным, описывающим классы,
определение конкретного класса, к которому следует отнести распознаваемый образ.
В последующем математический аппарат теории распознавания
образов расширился за счет применения разделов прикладной математики, теории информации, методов алгебры логики, математического программирования и системотехники.
Упорядоченный набор признаков, описывающих объект при
его распознавании, называется вектором признаков или образом
объекта. Можно сказать, что образ – это информационная модель
объекта, позволяющая отличить его от других объектов в процессе
распознавания.
46
Разработчикам системы распознавания необходимо решить ряд
достаточно трудных задач. Вначале следует определить полный перечень признаков, характеризующих объекты, для распознавания
которых разрабатывается система.
Главное в решении этой задачи – найти все возможные признаки, характеризующие существо распознаваемых объектов. Любые
ограничения, любая неполнота могут привести к ошибкам или
даже полной невозможности правильной классификации объектов.
Выбор признаков – сугубо эвристическая операция, зависящая от
изобретательности разработчика, так как не существует способов
их автоматической генерации.
Все возможные признаки могут быть разделены на детерминированные, вероятностные, логические и структурные.
Детерминированные признаки – это такие характеристики образов, которые имеют конкретные и постоянные числовые значения.
Примером детерминированных признаков являются сведенные в
единую таблицу технические характеристики компьютеров. Следует отметить, что при таком представлении число характеристик
по каждому компьютеру одинаково.
Числовые значения признаков по каждому из образов можно
интерпретировать как координаты точек, представляющих эти образы в многомерном пространстве признаков.
Необходимо иметь в виду, что в задачах распознавания с детерминированными признаками ошибки измерения этих признаков
не играют роли, если точность измерений признака значительно
выше, чем различие этого признака у образов, отнесенных к разным классам.
Очевидно, что в системе, использующей только детерминированные признаки, распознавание производится путем сравнения полученных значений признаков распознаваемого образа с имеющимися значениями признаков уже классифицированных образов.
Вероятностные признаки – это характеристики образа, носящие
случайный характер. Отличаются эти признаки тем, что в силу
случайности соответствующей величины признак одного класса
может принимать значения из области значений других классов.
Если это условие не выполняется, то признак следует считать детерминированным.
Для того чтобы можно было в условиях случайности говорить
о возможности распознавания, следует потребовать, чтобы вероятности наблюдения значений признака в своем классе были как
можно больше, чем в других. В противном случае эффективность
такого признака недостаточна для достоверного решения, и сле47
дует искать другие признаки, имеющие большую разделительную
способность.
Как известно из теории вероятностей, случайная величина характеризуется законом распределения вероятностей, который определяется функцией распределения случайной величины Fab(x),
т. е. вероятностью нахождения случайной величины x в диапазоне
a÷b, или плотностью распределения вероятностей (ПРВ) p(x), коb
∫
торые связаны следующим образом: Fab (x) = p(x)dx. В частности,
a
ПРВ нормального или гауссова закона распределения имеет вид
−
1
p(x) =
e
σ 2π
( x − m) 2
2σ 2
, где σ – среднеквадратическое отклонение x;
m – математическое ожидание или среднее значение случайной величины x.
Логические признаки – это характеристики образа, представленные в бинарном виде (0 или 1), т. е. не имеющие количественного выражения, являющиеся качественными суждениями о наличии
либо отсутствии некоторых свойств у данного образа. К логическим
признакам можно отнести также такие признаки, у которых важна
не величина, а лишь факт попадания или непопадания этой величины в некоторый заданный интервал.
Структурные признаки обязаны своим появлением проблеме
распознавания изображений и представляют собой непроизводные, т. е. элементарные, не производимые из других элементарных
признаков элементы или примитивы изображения объекта распознавания.
Следует отметить, что традиционно для описания изображений
используются его разложения в ряды по ортогональным функциям, например ряды Фурье, полиномы Эрмита, Лежандра, Чебышева, разложения Карунена – Лоэва. Однако преимущества структурного описания в отличие от разложений состоят в том, что оно понятнее для человека, решающего задачу распознавания объекта по
его изображению, более приемлемо для компьютерной реализации
системы распознавания, менее трудоемко в вычислительном плане
и лишено потерь информации, свойственных разложениям.
Отличающиеся объекты могут состоять из одинаковых непроизводных элементов. Введение правил комбинирования, определяющих способы построения различных объектов из ограниченного
числа непроизводных элементов, позволяет получить описание
разнообразных объектов.
48
Для описания какого-либо объекта непроизводные элементы
объединяются в цепочки (предложения) по своему, характерному
только для этого объекта, набору правил. В результате связей из
непроизводных элементов (структурных признаков) образуется образ, аналогично тому, как предложения языка строятся путем соединения слов, в свою очередь состоящих из букв, что аналогично
синтаксису естественного языка. Отсюда структурные признаки
носят еще название лингвистических или синтаксических.
3.2. Метрики пространства признаков
При разработке системы распознавания используется некоторое
множество образов, признаки которых известны. Такое множество
принято называть обучающим. После выбора признаков возникает
необходимость классификации образов из обучающего множества
и составление априорного алфавита классов. Если число классов
заранее известно и известна принадлежность классам образов из
обучающего множества, то решение поставленной задачи тривиально.
Однако иногда возникает необходимость разбиения совокупности образов на несколько групп, причем число групп не обязательно
известно. Например, классификация различных видов бабочек в
биологии или классификация языков Новой Гвинеи в лингвистике.
Задача разделения предъявленных образов по нескольким группам
называется кластеризацией, а каждую полученную группу часто
называют кластером. Существуют разные математические методы
и подходы к решению задачи кластеризации, например рекурсивное слияние, кластеризация по k средним, цепная развертка, кластеризация с фиксированным порогом и др.
Важнейшую роль как в кластеризации, так и в собственно распознавании играет выбранная метрика, т. е. определение понятия
меры близости или расстояния между образами, между образом и
кластером, а также между кластерами. При разном выборе метрики естественно возникают разные варианты кластеризации. В свою
очередь, выбор метрики во многом зависит от характера признаков.
Чаще всего мера близости определяется выбранной метрикой
пространства признаков, хотя существуют и неметрические меры
близости образов, например расстояние Хаусдорфа, мера Танимото. Разработанный метод вычисления расстояния dlp между точками l и p в пространстве признаков должен обеспечивать выполнение следующих аксиом:
49
– симметричность расстояния (dlp = dpl);
– правило треугольника (dlh + dhp >= dlp);
– положительность расстояния (dlp >= 0, причем dlp = 0, только
если l = p).
Для одномерных детерминированных векторов (вектор состоит
из одного признака) dlp=|xl–xp|, где xl, xp – значения признака для
образов l и p.
Расстояние между точкой p и кластером l для одного вероятност(x p − ml ) 2
,
ного признака можно найти по расстоянию Фишера d F =
Dl
где ml и Dl – статистические характеристики кластера l (математическое ожидание и дисперсия признака).
Расстояние между кластерами p и l по одному вероятностному
(ml − m p ) 2
.
признаку можно вычислить по критерию Фишера Flp =
Dl + D p
В алгоритмах кластеризации и распознавания образов, характеризующихся детерминированными признаками, в качестве меры
близости между точками X и Y в пространстве признаков, описываемыми векторами X и Y, можно использовать как обычное евклидово расстояние d(X, Y) =
∑ (xi − yi ) 2 , так и расстояние Минь-
i =1,n
ковского, позволяющее учитывать важность i-го признака весовым
коэффициентом ci d(X, Y) =
∑ ci (xi − yi ) 2 .
i =1,n
Расстояние Махаланобиса позволяет определить расстояние
между образом X и кластером g в пространстве вероятностных признаков dM = (X–mg)Covg–1(X–mg)T, где mg – вектор математических
ожиданий; Covg–1 – обратная ковариационная матрица для кластера g. Элементы ковариационной матрицы определяются по векторам признаков эталонных образов, относящихся к данному кластеру, следующим образом:
N
 D11 D12 ... D1n   D = 1
(x il − mi ) 2
ii
D
 
1
N
−
...
D
D
l =1
22
2n :
,
Cov =  21

N
... ... ...  
1
 ...
(x − mi )(x jl − m j )
 D =
 Dn1 Dn2 ... Dnn   ij N − 1 l =1 il
где i, j=1, …, n – индексы номеров компонент вектора признаков;
N – число образов, составляющих данный кластер; xil – значение
i-го признака l-го образа; mi – математическое ожидание i-й компоненты вектора признаков; Dii – дисперсия i-го признака; Dij – коэф-
∑
∑
50
фициент ковариации i-го и j-го признаков. Обратная ковариационная матрица существует только при условии N > n.
Аналогично можно определить и расстояние между кластерами
в пространстве вероятностных признаков при условии, что их ковариационные матрицы совпадают или достаточно близки.
В алгоритмах кластеризации и распознавания, использующих
вероятностные признаки, в качестве меры близости часто используется риск, связанный с решением о принадлежности объекта к
классу Wj (j =1, 2,..., K), описываемый платежной матрицей вида
C11 C12
C21 C22
...
...
C K1 C K2
... C1K
... C2K
. Здесь на главной диагонали расположены
... ...
... C KK
потери при правильных решениях, которые обычно принимаются
как Сjj = 0 или Cjj < 0. По обеим сторонам от главной диагонали стоят потери при ошибочных решениях.
Если вектор признаков распознаваемого образа X, то риск,
связанный с принятием решения о принадлежности этого образа к классу Wg, когда на самом деле он может принадлежать любому другому Wj-му классу, наиболее целесообразно определять
как среднее значение потерь, стоящих в g-м столбце платежной матрицы. Тогда этот средний риск можно представить как
R(Wg / X) =
K
∑ C jg P(Wj / X),
j =1
где P(Wj/X) – апостериорная вероят-
ность того, что образ X принадлежит Wj.
При описании классов вероятностными признаками P(Wj/X) опp j (X / Wj ) Pj
, где Pj – апределяется по формуле Байеса: P(Wj / X) =
p(X)
риорная вероятность появления образа, относящегося к классу Wj;
p(X/Wj) – условная вероятность появления образа X в классе Wj;
p(X) – плотность распределения вероятности вектора признаков X
по всем классам.
Далее приводится пример использования в качестве меры близости риска, связанного с решением о принадлежности распознаваемого объекта к некоторому классу. Пусть имеются вектор признаков
X, состоящий из одного компонента – веса человека, разделенного
на четыре диапазона (A – недостаточный вес, B – норма, C – превышение, D – избыточный вес), и два класса W (W=0 – у человека нет
гипертонии, W=1 – есть). Результаты обследования 100 человек
51
приведены в табл. 3. Необходимо по значению признака X отнести
образ к одному из двух классов с минимальным риском ошибки.
Таблица 3
X (вес)
W=0 (здоров)
W=1 (болен)
A
20
19
1
B
30
27
3
C
40
30
10
D
10
2
8
Всего
100
78
22
Вероятность появления образа, принадлежащего классу W:
P(W=1) = 22/100; P(W=0)=78/ 100. Вероятность наличия признака
X у образа, принадлежащего классу W: P(X/W), т. е. P(A/0)=19/78.
Вероятность появления конкретного значения признака:
P(X) =
K
∑ P(X / Wj )P(Wj ),
т. е. P(A) = P(A/0)*P(0) + P(A/1)*P(1) =
j =1
= 19/78*78/100 + 1/22*22/100 = 20/100, что следует из таблицы
результатов исследований. Вероятность принадлежности образа
P(X / W ) P(W )
классу W при наличии признака X: P(W / X) =
, т. е.
P(X)
P(0/A) = [P(A/0) * P(0)]/P(A) = (19/78 * 78/100) / (20/100) = 19/20.
Результаты вычисления остальных вероятностей, а также суммарных рисков при разных значениях стоимости потерь сведены
в табл. 4.
Таблица 4
P(X)
P(X/0)
P(X/1)
P(0/X)
P(1/X)
R(0/X)
R(1/X)
R(0/X)
R(1/X)
A
20/100
19/78
1/22
19/20
1/20
0,025
0,475
0,04
0,019
B
30/100
27/78
3/22
27/30
3/30
0,05
0,45
0,08
0,18
C
40/100
30/78
10/22
30/40
10/40
0,125
0,375
0,2
0,15
D
10/100
2/78
8/22
2/10
8/10
0,4
0,1
0,64
0,04
Всего
1
1
1
С10=0,5
С01=0,5
С10=0,8
С01=0,2
Риск ошибки при отнесении образа, принадлежащего классу
W=0, с X=A к другим классам, т. е. отнесение его к классу W=1:
R(0/A)=С10*P(1/A).
Пусть риск здорового человека отнести к больному равен риску
больного человека отнести к здоровому, т. е. С10 = С01 =0,5. Тогда к
52
классу W=1 (человек болен), согласно принятой мере близости, относятся только образы с X=D. Если риск ошибки разный (С10=0,2;
С01=0,8), т. е. лучше отнести к больным здорового, чем пропустить
больного, то к больным будут отнесены образы с X = С и D.
Если количество образов в кластере недостаточно для достоверного определения его статистических характеристик, то в качестве
меры близости между образом X и кластером можно использовать
среднеквадратическое значение расстояний от образа X до множества образов W(Y1, …, YN), составляющих данный кластер, т. е.
d(X, W ) =
N
1
d 2 (X, Yl ), где N – число образов в кластере W.
N l =1
∑
Аналогично и расстояние между двумя кластерами при отсутствии статистических характеристик можно определить как среднеквадратическое значение расстояний между каждым образом одного класса и каждым образом другого класса.
Для алгоритмов кластеризации и распознавания, основанных
на логических признаках, в качестве меры близости используется расстояние Хемминга d(X, Y) =
n
∑ xi ⊕ yi,
где ⊕  – сложение по
i =1
mod 2 элементов векторов X и Y, которые могут принимать только
значения {0, 1}. Очевидно, расстояние Хемминга есть сумма признаков, значения которых у образов X и Y не совпадают.
В качестве меры близости можно использовать и угол между векторами признаков X и Y, т. е. d(X, Y) = arccos
XY T
, где
X Y
n


X , Y  – нормы соответствующих векторов  X =
x i2 . Функ

i =1


ция достигает максимума, когда направления векторов совпадают.
Данная мера близости позволяет эффективно классифицировать
образ при проявлении элементами каждого класса тенденции располагаться вдоль некоторой оси в пространстве признаков, а также
при достаточном расстоянии классов как друг от друга, так и от начала координат.
Неметрической мерой близости для образов, описываемых
логическими признаками, является мера Танимото d(X,Y) =
XY T
=
. Здесь числитель характеризует число совT
XX − XY T + YY T
падающих единичных признаков у сравниваемых образов, а зна-
∑
53
менатель – общее число единичных признаков, которыми обладают эти образы. Мера Танимото широко применяется в информационном поиске, классификации болезней, животных или растений.
Если классы в пространстве признаков представляют собой
сложные по форме и частично перекрывающиеся структуры, то в
качестве меры близости двух множеств часто используется метрика Хаусдорфа, которая определяется следующим образом. Пусть
в некотором пространстве определено расстояние между точками, описываемыми векторами X и Y, – d(X, Y). Тогда расстояние
от точки X до множества точек W d(X,W) определяется как минимальное значение из множества расстояний d(X, Y) для всех Y из
W. Расстояние от множества Wx, состоящего из точек X, до множества Wy, состоящего из точек Y, d′(Wx , Wy ) определяется как
максимальное значение из множества расстояний d(X, Wy) для
всех X из Wx. Расстояние d(Wx , Wy ) между множествами Wx и Wy
определяется как максимальное из двух расстояний – от Wx до Wy
и от Wy до Wx, которые в общем случае могут и не совпадать, т. е.
d(Wx , Wy ) = max(d′(Wx , Wy ), d′(Wy, Wx )) . Таким образом, два множества в метрике Хаусдорфа находятся на расстоянии d0, если и
только если для любой точки из первого множества в ее окрестности d0 содержится хотя бы одна точка второго множества и то же самое справедливо для второго множества.
Для алгоритмов, основанных на структурных или лингвистических признаках, понятие меры близости более специфично. С учетом
того, что каждый класс описывается совокупностью предложений,
характеризующих структурные особенности образов соответствующих классов, распознавание неизвестного образа осуществляется
идентификацией предложения, описывающего этот образ, с одним
из предложений в составе описания какого-либо класса. В данном
случае под идентификацией может подразумеваться поиск наибольшего сходства предложения, описывающего распознаваемый
образ, с предложениями из наборов описания каждого класса.
3.3. Методы кластеризации
После выбора меры близости можно приступать к кластеризации имеющихся образов по какому-либо алгоритму.
Алгоритм кластеризации рекурсивным слиянием достаточно
прост. Вначале каждый образ считается отдельным классом, далее
вычисляется расстояние между всеми кластерами, т. е. формируется квадратная, диагонально-симметричная таблица расстояний,
54
строки и столбцы которой – имеющиеся кластеры. На каждом шаге
сливаются два самых близких кластера, после чего размер таблицы
уменьшается и вычисляются новые расстояния между кластерами.
Процесс прекращается, когда достигнуто заранее заданное число
кластеров или расстояние между ближайшими кластерами больше заранее заданного максимально допустимого. Данный метод
требует многократных вычислений расстояний, изменяющихся на
каждом шаге, что может стать достаточно трудоемкой задачей при
большом количестве образов.
При кластеризации по k средним заранее задается требуемое
число кластеров – k и на первом шаге в пространстве признаков
произвольно выбирается положение k центров кластеров, не обязательно совпадающих с какими-либо образами. Далее на каждом
шаге, во-первых, каждый образ относится к тому кластеру, расстояние до центра которого для него минимально, а во-вторых, после
распределения всех образов по кластерам производится перерасчет
положения центров кластеров. Процесс продолжается до тех пор,
пока не стабилизируется состав кластеров. Цель – минимизировать суммарное расстояние от центров кластеров до отнесенных к
ним образов по всем кластерам. Возможно схождение процесса к
локальному минимуму, а также отсутствие образов в некоторых
кластерах, но, изменяя число кластеров и сравнивая результаты,
можно найти подходящее число кластеров.
Если в качестве метрики пространства признаков используется
метрика Хаусдорфа, то для кластеризации образов можно применить метод цепной развертки.
На первом этапе цепной развертки в качестве исходного берется
любой образ из предъявленной совокупности, ему приписывается
номер 1 и расстояние 0. Затем просматриваются все оставшиеся
образы. Выбирается образ, расстояние от которого до исходного
элемента минимально. Ему присваивается номер 2 и расстояние,
равное расстоянию до исходного образа. Затем среди оставшихся
ищется образ, расстояние от которого до уже отмеченного множества из двух элементов минимально, и т. д. – всегда на очередном
шаге выбирается образ, расстояние от которого до уже пронумерованных образов, как расстояние до множества, минимально,
ему приписывается очередной номер и это расстояние. Процедура
повторяется, пока все образы не будут пронумерованы. В результате все множество образов будет выстроено в некотором порядке, и
каждому образу приписано некоторое число – расстояние до предшествующего множества.
55
На следующем этапе производится разделение полученного
множества на несколько кластеров так, чтобы выполнялись следующие условия:
– расстояние между любыми образами, входящими в разные
кластеры, должно быть больше некоторого заданного расстояния d0;
– для любой пары образов из одного кластера (t1, t2) можно найти такую цепочку образов (o1=t1, o2, …, on=t2) из того же кластера, что для любого i (i<n) расстояние между соседними образами
d(oi,oi+1) ≤ d0.
Для выполнения этих условий достаточно просмотреть все приписанные образам расстояния и пометить те образы, у которых
d > d0. Пусть будут помечены образы с номерами N1, N2, ..., Nk.
Тогда к первому кластеру следует отнести все образы с номерами
меньше N1, ко второму – все образы с номерами от N1 до N2 и т. д.
В результате будет сформировано k кластеров.
После процедуры цепной развертки можно легко проводить
анализ полученной совокупности кластеров, например, при каких значениях порога d0 возникают разные варианты кластеризации, как эти варианты соотносятся между собой и многое другое.
Необходимо отметить, что данная процедура требует 0,5N( N − 1)
операций вычисления расстояния между образами, если всего имеется N образов, что требует значительных временных затрат. Как
правило, более быстрый результат можно получить кластеризацией с фиксированным порогом, которая является модификацией
описанного выше метода.
В начале кластеризации с фиксированным порогом берется любой образ и ему присваивается принадлежность к первому кластеру.
К данному кластеру присоединяются все образы, принадлежность
которых к какому-либо кластеру еще не установлена и расстояние
от которых до исходного образа меньше порога d0. Затем для каждого из присоединенных образов данная процедура повторяется.
После того как к первому кластеру больше нельзя отнести ни одного образа, среди оставшихся в качестве исходного образа для второго кластера берется произвольный образ. Процедура повторяется
до тех пор, пока не будут исчерпаны все образы. В худшем случае
и здесь при наличии N образов потребуется 0,5N(N–1) процедур
вычисления расстояния, но в наилучшем случае будет выполнено
всего N процедур.
56
3.4. Построение классификаторов
Следующий важный этап в процессе разработки системы распознавания – разработка априорного словаря признаков. Располагая
полным перечнем признаков и априорным алфавитом классов, полученных в результате решения первой и второй задач, необходимо
провести анализ возможностей измерения признаков или расчета
их по данным измерений, а также оценить их информативность для
обеспечения требуемой эффективности распознавания. Косвенно
информативность отдельного признака для каждой пары классов
можно оценить по критерию Фишера. Информативность признака
можно считать низкой, если критерий Фишера имеет недостаточные значения для всех пар классов.
Однако какой набор признаков распознавания получился в результате – хороший или плохой, можно понять, только выполнив
испытания системы распознавания в целом и оценив эффективность распознавания. Но системы распознавания на данном этапе
разработки еще не существует. Выходом из создавшегося положения является создание на данном этапе математической модели
системы, которая и используется для реализации последовательных приближений к желаемому результату.
После формирования набора признаков необходимо выполнить описание классов из априорного алфавита на языке априорного словаря признаков. Априорное описание классов – наиболее
трудоемкая из задач в процессе создания системы распознавания,
требующая глубокого изучения свойств объектов распознавания.
В результате каждому классу необходимо поставить в соответствие
числовые параметры детерминированных и вероятностных признаков, значения логических признаков и предложения, составленные
из структурных признаков-примитивов. Значения этих параметров можно получить в результате обработки данных, полученных
в ходе специально поставленных экспериментов; математического
моделирования; извлечения необходимой информации из литературных источников.
Если признаки распознаваемых образов детерминированные, то
описанием класса может быть точка в многомерном пространстве
признаков из априорного словаря, сумма расстояний которой от точек, представляющих образы данного класса, минимальна.
Если распределение образов, представляемых числовыми значениями их признаков, по областям соответствующего пространства
вероятностное, то для описания классов необходимо определить
57
характеристики этих распределений. К таким характеристикам
относятся:
– функция ПРВ pi(x1, x2, ..., xn), где x1, ..., xn – вероятностные
признаки, i – номер класса;
– априорная вероятность Pi того, что образ, случайно выбранный
из общей совокупности, окажется принадлежащим к i-му классу.
Статистические характеристики можно определить по экспериментальным статистическим данным, путем теоретического вывода или моделированием.
Если признаки распознавания – структурные, то описанием
каждого класса должен быть набор предложений, т. е. цепочек из
непроизводных элементов с правилами соединения. В таком случае
каждое из предложений класса является характеристикой структурных особенностей образов этого класса.
Важнейшим этапом разработки системы распознавания является выбор алгоритма классификации, обеспечивающего отнесение
распознаваемого образа к соответствующему классу.
Один из подходов к решению данной задачи заключается в разбиении пространства значений признаков распознавания на области D1, D2, ..., Dn, соответствующие классам, причем разбиение
должно быть выполнено таким образом, чтобы обеспечить минимум ошибки распознавания. В таком случае результатом классификации является отнесение образа, имеющего вектор признаков
X=(x1, x2, ..., xn) (точка в n-мерном пространстве), к g-му классу,
если указанная точка лежит в соответствующей классу области
признаков Dg.
Разбиение пространства признаков можно представлять как
построение разделяющих функций Sg(X) между множествами признаков Dg, принадлежащих разным классам. Эти функции должны обладать следующим свойством: если образ, имеющий вектор
признаков X, фактически относится к g-му классу, то Sg(X) > Sj(X)
для всех j≠g. Отсюда легко определить выражение разделяющей
границы между областями Dg и Dk, соответствующими g-му и k-му
классам: Sg(X) – Sk(X) = 0. Очевидно, что форма границы зависит
от вида разделяющих функций и в линейном случае представляет
собой гиперплоскость в многомерном пространстве признаков.
В простейшем случае разделения двух классов по одному признаку разделяющая их граница в одномерном пространстве признаков
превращается на признаковой оси в точку, положение которой для
вероятностного признака, согласно байесовской стратегии, позволяющей обеспечить минимизацию среднего риска или стоимости
потерь, находится следующим образом.
58
Пусть требуется произвести разделение образов на два класса W1
и W2 по одному вероятностному признаку х. Тогда вектор признаков каждого образа состоит из одного элемента, а описания классов
представляют собой функции условной плотности распределения
вероятности значений признака p1(x), p2(x) для классов W1 и W2
соответственно.
Пусть кроме p1(x) и p2(x) известны априорные вероятности появления образов разных классов Р1, Р2 и матрица стоимости потерь
c 
c
C =  11 12 , где с11, с22 – потери при правильных решениях; с12
c
c
 21 22 
и с21 – потери при ошибочной классификации, когда образ, относящийся к первому классу, ошибочно распознан как образ, относящийся ко второму классу, и, соответственно, наоборот. Первый
случай называется ошибкой первого рода, а второй – ошибкой второго рода.
Условная вероятность ошибки первого рода определяется как
∞
Q1 =
∫ p1(x)dx.
x0
Соответственно условная вероятность ошибки второго рода
Q2 =
x0
∫ p2 (x)dx,
где х0 – пороговое значение признака, т. е. образ
−∞
распознается как относящийся к первому классу, если для него
х < x0, и образ распознается как относящийся ко второму классу
в противном случае. Графическое представление условных вероятностей и порогового значения признака показано на рис. 12.
Байесовский классификатор минимизирует потери при распознавании R, которые можно оценить как R=P1c11(1–Q1)+P1c12Q1+
+ P2c22 (1 − Q2 ) + P2c21Q2.
p (x)
p 1(x)
p2 (x)
Область ошибочного
распознавания
x0
x
Рис. 12.Функции условной плотности распределения вероятности значений признака для двух классов
59
Чтобы найти минимум функции R от х, необходимо подставить в нее выражения для Q1 и Q2, взять производную по х и
dR
приравнять ее к нулю, положив х=х0:
= P1[c11 p1(x 0 ) −
dx x =x0
−c12 p1(x 0 )] + P2 [c21 p2 (x 0 ) − c22 p2 (x 0 )] = 0.
Откуда
p2 (x 0 ) P1(c12 − c11)
=
= λ 0, где λ0 – пороговое значение
p1(x 0 ) P2 (c21 − c22 )
p2 (x)
, обеспечивающее миниp1(x)
мальные потери при классификации.
Конкретные значения априорных вероятностей Р1, Р2 и элементов матрицы стоимости потерь определяют отношение условных
плотностей распределения при пороговом значении признака. Так,
для Р1=Р2, с11=с22 и с12=с21 λ0=1, т. е. пороговое значение x0 соответствует абсциссе точки пересечения функций p1(x) и p2(x) (см.
рис. 12). При нормальном законе распределения для p1(x), p2(x) с
равными среднеквадратическими отклонениями σ и математичесm + m2
кими ожиданиями m1, m2 соответственно x 0 = 1
.
2
Другой подход к проблеме классификации образов основывается на сравнении значений той или иной меры близости или сходства распознаваемого образа с каждым классом. Если значение выбранной меры близости L(X, W) данного образа X с каким-либо g-м
классом, описываемым множеством свойств Wg, достигает экстремума относительно ее значений по другим K классам для данного
коэффициента правдоподобия λ(x) =
образа, т. е. L(X, Wg ) = extr L(X, Wk ), то принимается решение о
k =1,K
принадлежности этого образа g-му классу.
В простейшем случае одномерного пространства статистических признаков при наличии всего двух классов хорошие результаты дает применение расстояния Фишера в качестве меры близости.
Данная мера позволяет классифицировать распознаваемый образ
даже при совпадении математических ожиданий классов, отличающихся только дисперсией. Графическая иллюстрация такого случая (рис. 13) показывает, что, согласно расстоянию Фишера, распознаваемый образ следует отнести к классу, имеющему большую
дисперсию.
В принципе разработкой алгоритма классификации заканчивается создание системы распознавания, однако на практике процесс
разработки является итерационным приближением к максимально
60
p(x)
(x − m1 )2 (x − m2 )2
<
D1
D2
p 2 (x)
p1 (x)
m1 , m2
x
x
Рис. 13. Классификация образа по расстоянию Фишера
возможной эффективности распознавания. В этом ряду последовательных приближений главную роль играют признаки распознавания, так как от эффективности их набора зависит эффективность
системы в целом. В процессе совершенствования системы указанный набор пополняется, а неинформативные признаки исключаются. В некоторых случаях может возникнуть необходимость изменения алгоритма классификации, что в свою очередь приведет
к существенному изменению словаря признаков, а, возможно, и
алфавита классов.
В сложных задачах распознавания образов требуется учитывать
большое количество различных признаков, причем определение
значения каждого из них может быть достаточно трудоемкой задачей, а полное сравнение неизвестного вектора признаков со многими векторами признаков эталонов может потребовать много времени. Например, в системе медицинской диагностики количество
возможных диагнозов исчисляется тысячами, а в качестве признаков используются результаты различных лабораторных анализов,
число которых может достигать нескольких десятков, причем многие из них требуют проведения сложных, длительных и дорогостоящих, а иногда и болезненных процедур. Для таких систем становится актуальной задача выбора последовательности определения
признаков.
Использование дерева решений позволяет совместить процесс
определения значений признаков с классификацией распознаваемого образа за счет выбора на каждом шаге наиболее информативного признака. С каждым узлом дерева решений связана функция
выбора, которая определяет, какой дочерний узел следует обрабатывать далее. Каждый листовой узел связан с конкретным классом. Если процедура обхода дерева достигает листа, то неизвест61
ный образ считается принадлежащим тому классу, который связан
с данным листом.
В качестве примера построения дерева решений рассмотрим распознавание рукописных цифр на основе следующих структурных
признаков:
– число замкнутых областей (озера);
– число незамкнутых областей (заливы);
– расположение залива (в верхней или нижней части изображения цифры);
– направление открытой части залива (четыре стороны).
Например, цифра «8» характеризуется двумя озерами, а цифра
«5» – заливом вверху, открытым вправо, и заливом внизу, открытым влево. В табл. 5 приведены указанные признаки для всех десяти цифр. Конечно, признаки не учитывают всех особенностей рукописных цифр, например, «четверка» может иметь вместо залива
озеро, но для демонстрации работы дерева решений приведенных
признаков достаточно. На рис. 14 показано дерево решений, позволяющее однозначно классифицировать цифры. На каждом шаге
определяется признак и в зависимости от его значения выбирается
соответствующая ветвь, что позволяет изменять порядок определения значений признаков в зависимости от распознаваемой цифры.
Таблица 5
Цифра
0
1
2
3
4
5
6
7
8
9
Число озер Число заливов Расположение заливов
1
–
–
–
–
–
1
–
2
1
–
1
2
2
1
2
1
–
–
1
–
Верх
Верх, низ
Верх, низ
Верх
Верх, низ
Верх
–
–
низ
Направление
–
Вниз
Влево, вправо
Влево, влево,
вверх
Вправо, влево
Вправо
–
–
влево
В системах распознавания, предназначенных для решения практических задач, используются сотни признаков, десятки классов и
тысячи эталонных образов, причем для любого набора эталонных
образов и признаков может быть построено более одного дерева решений. В таких случаях выбор признаков, дающих наилучшее, согласно некоторому критерию, дерево решений, становится актуальной задачей. В качестве критерия можно использовать стоимость
62
Один залив вверху
да
123456
нет
Число озер
0
1
0
12345
Залив внизу
6
14
да
нет
4
1
7
да
нет
Открыт вверх
7890
Число озер
235
Нижний вправо
да
35
Верхний вправо
2
1
90
Залив внизу
да
нет
9
0
8
нет
2
нет
да
5
3
Рис. 14. Дерево решений для распознавания по структурным признакам
определения значений признаков или минимальное число уровней
дерева решений. Существуют методы автоматического построения
дерева решений по значениям признаков эталонных образов, например на основе энтропии.
Энтропия множества событий x={x1, x2, …, xn}, где xi – отдельное событие, равна H(x) = −
n
∑
i =1
j =1,m
pi log 2 pi , где pi – вероятность
события xi. Энтропию можно интерпретировать как «среднюю
неопределенность источника информации». Теория информации
позволяет измерить информативность события через энтропию.
В частности, информативность I(W/x) переменной класса W с возможными значениями {w1, w2, …, wK} по отношению к переменной
признака x с возможными значениями {x1, x2, …, xN} определяK N
p(W = wi / x = x j )
p(W = wi / x = x j )log 2
, где
ется как I(W / x) =
p(W = wi ) p(x = x j )
i =1 j =1
p(W=wi) – вероятность появления класса W, имеющего значение
wi; p(x=xj) – вероятность появления признака x, имеющего значение xj; p(W=wi/x=xj) – совместная вероятность класса W=wi и переменной x=xj. Эти априорные вероятности можно оценить по частоте соответствующих событий в эталонных образах.
∑∑
63
Рассмотрим простейший пример определения наиболее информативного признака из трех бинарных признаков {x, y, z} для четырех образов, относящихся к двум классам W {I, II} (табл.) 6.
Класс I наблюдается в двух из четырех образов, следовательно:
p(W=I) = 2/4 = 0,5. Признак x=1 наблюдается у трех эталонов, следовательно: p(x=1) = 3/4 = 0,75. Признак x=1 наблюдается у двух
эталонов, относящихся к классу W=I, следовательно: p(W=I/x=1)=
= 2/4 = 0,5. Информативность признака x:
I(W / x) = p(W = I/ x = 1)log 2
+ p(W = II/ x = 0)log 2
= 0,5log 2
p(W = I/ x = 1)
+ ... +
p(W = I) p(x = 1)
p(W = II/ x = 0)
=
p(W = II) p(x = 0)
0,5
0,25
0,25
+ 0 + 0,25log 2
+ 0,25log 2
= 0,311.
0,5 ⋅ 0,75
0,5 ⋅ 0,25
0,5 ⋅ 0,75
Таблица 6
Эталон
x
y
z
W
1
2
3
4
1
1
0
1
1
1
0
0
1
0
1
0
I
I
II
II
Аналогично определяется информативность признака y (I×
×(W/y) = 1,0 ) и z (I(W/z) = 0), т. е. наиболее информативен признак
y, которого вполне достаточно для классификации имеющихся образов.
На каждом шаге создания дерева решений в качестве анализируемого признака используется наиболее информативный признак, и
разделение множества эталонных образов на подмножества производится по данному признаку в данном узле дерева. Формирование
дерева заканчивается, когда множество эталонных образов полностью разделяется, т. е. число листьев дерева становится равным
числу классов.
64
4. Машинное обучение
Способность к обучению является характерным свойством любой системы, обладающей интеллектом. Герберт Симон в 1983 году
определил обучение следующим образом: «Обучение – это любое
изменение в системе, приводящее к улучшению решения задачи
при ее повторном предъявлении или к решению другой задачи на
основе тех же данных».
Обучение предполагает некоторое обобщение на основе опыта, т. е.
производительность системы должна возрастать при решении аналогичных задач из той же предметной области. В большинстве случаев
обучаемая система не может обработать все возможные задачи, следовательно, она должна корректно распространить полученный опыт
на похожие задачи, что приводит к необходимости индуктивного
обучения и, как следствие, к проблеме индуктивного порога. Вообще
говоря, индукция как способность обобщения на основе множества
частных случаев – одна из фундаментальных задач обучения. Типичной задачей индуктивного обучения является формирование понятий, позволяющее корректно относить отдельные объекты к тому
или иному понятию. Близкие задачи приходится решать и в такой
области искусственного интеллекта как распознавание образов.
В индуктивном обучении обучающие данные являются лишь
подмножеством всех возможных экземпляров. Обоснование ограничения на размер обучающего множества и выбор конкретных
экземпляров, типичных для формируемого представления, в общем случае является сложной эвристической задачей. Основная
проблема заключается в том, что на любом множестве обучающих
примеров можно построить неограниченное количество обобщений, большинство из которых окажутся или неадекватными, или
бессмысленными. Использование индуктивных порогов и априорных знаний о предмете обучения позволяет формировать обобщения, имеющие практическое значение.
Возможны два подхода к обучению – обучение с учителем и обучение с подкреплением (самообучение). В первом подходе система
получает от учителя инструкции, определяющие ее действия в тех
или иных случаях, т. е. настройка системы производится явным
образом самим обучающим. Например, метод оценки узлов графа
пространства состояний формируется на основе знаний и опыта
эксперта. Результат работы системы во многом зависит от адекватности этой оценки.
При самообучении система получает только исходные данные и
оценку результата ее действий. Настройка системы происходит в
65
автоматическом режиме и учитель не знает ее результатов заранее.
Например, в самообучающуюся программу для игры в «крестикинолики» первоначально не закладывается методика оценки качества возможных ходов в заданной позиции, т. е. перед началом обучения все возможные ходы равновероятны. По результатам игры
производится перераспределение вероятностей выбора возможных
ходов, т. е. происходит подкрепление «правильных» ходов. Если
программа выиграла, то повышается вероятность всех сделанных
ходов, а если программа проиграла, то вероятность всех ходов
уменьшается. Если игра закончилась вничью, то вероятности ходов
не изменяются. В результате многократных повторений программа
улучшает качество игры и начинает в каждой ситуации выбирать
наиболее правильный ход.
Особенности рассмотренной программы заключаются в следующем:
– разработчик программы не знает выигрышной стратегии и закладывает в программу только правила игры и алгоритм изменения оценки возможных ходов;
– в процессе работы программа изменяет вероятности выбора
ходов в зависимости от результатов игры, т. е. предсказать ее ход
практически невозможно;
– применение данного метода к более сложным играм вызывает
существенные трудности, так как с усложнением игры во многом
исчезает явная зависимость между конкретным ходом и результатом всей игры.
Обучение с подкреплением основано на формировании оценок
возможных действий, в результате выполнения которых вознаграждение максимально. Система не получает явных инструкций,
но на основе собственного опыта узнает, какие действия приводят
к наибольшему вознаграждению. Таким образом, обучение с подкреплением определяется действиями интеллектуальной системы
в окружающей среде и откликом этой среды, причем в процессе
обучения система, с одной стороны, опирается на полученные ранее
знания об окружающей среде, а с другой – самостоятельно исследует еще не известную часть этой среды, что принципиально отличает
данный метод от обучения с учителем.
Алгоритм обучения с подкреплением включает в себя четыре основных компонента:
– π – политику выполнения действий в зависимости от состояния, т. е. функцию отображения пространства состояний в пространство возможных действий;
66
– r – функцию вознаграждения, которая в момент времени t
зависит от состояния задачи s и действия a в предыдущий момент
времени, т. е. определяет отображение пары «состояние-действие»
в меру вознаграждения, характеризующую степень эффективности
данного действия для достижения цели;
– функцию ценности V, определяющую ценность состояния s
при использовании политики π; т. е. величину вознаграждения, на
которое может рассчитывать система, продолжая действовать из
этого состояния;
– модель внешней среды, т. е. механизм реализации существенных аспектов поведения внешней среды.
Различие между функцией вознаграждения r и функцией ценности V заключается в том, что функция r определяет текущую
эффективность пары «состояние-действие», а функция V задает
значение состояния среды в перспективе. Оно определяется как на
основе качества текущего состояния среды, так и на основе качества состояний, вероятно последующих за данным, т. е. вознаграждения, получаемого при переходе в эти состояния. Например, пара
«состояние-действие» может приводить к низкому текущему вознаграждению, но иметь высокую ценность, так как за ней обычно
следуют состояния с высоким вознаграждением.
Низкая ценность соответствует состояниям, не приводящим к
успешному решению задачи, чего нельзя сказать о вознаграждении.
Однако без функции вознаграждения нельзя определить значение
ценности состояния. Фактически вознаграждение предоставляется непосредственно внешней средой и определяется результатом
решения поставленной перед системой задачи. Ценность состояния может многократно изменяться на основе полученного опыта,
причем наиболее сложным моментом в обучении с подкреплением
является создание метода эффективного определения ценности.
Рассмотрим один из возможных алгоритмов определения ценности состояния – метод временных разностей – на примере игры
«крестики-нолики».
В начале необходимо создать таблицу, в которой каждому возможному состоянию игры соответствует число, определяющее ценность состояния, т. е. оценку текущей вероятности победы, если
игра начинается с этого состояния. Например, 1 – состояния, приводящие к победе, 0 – состояния, приводящие к ничьей или поражению, и 0,5 – неизвестные позиции (первоначально все состояния,
кроме конечных, инициализируются значением 0,5). Эта таблица
используется для выработки стратегии победы, при которой ничья
или победа соперника рассматриваются как поражение. Во время
67
игры из всех возможных ходов выбирается тот, который имеет наибольшую ценность.
В процессе многократного повторения игры с противником значения функции ценности состояний будут меняться, отражая вероятность принадлежности данного состояния к победному. Для
этого ценность каждого выбранного состояния V′ определяется как
функция от ценности следующего выбранного состояния и результата игры, т. е. V′(sn)=V(sn)+c(V(sn+1)–V(sn)), где sn – состояние в
момент времени n, а sn+1 – состояние в момент времени n+1; с – шаговый множитель.
Отметим, что с увеличением числа сыгранных партий целесообразно уменьшать множитель с для того, чтобы обеспечить сходимость функции ценности для каждого состояния к значению вероятности победы при игре с данным противником. Целесообразно
также при вычислении ценности учитывать «обесценивание» вознаграждения по мере удаления текущего состояния от цели.
68
5. Нейронные сети
5.1. Естественные и искусственные нейроны
Рассмотренные в предыдущих разделах подходы к решению
задач ИИ базируются на гипотезе о физической символьной системе, т. е. используют явные представления знаний об окружающем
мире и детально разработанные алгоритмы поиска в пространстве
состояний. Другая точка зрения на проблему создания систем, обладающих ИИ, состоит в том, что их построение должно опираться
на изучение механизмов естественного мышления и анализ данных
о способах формирования разумного поведения человека, причем
это построение должно осуществляться прежде всего как воспроизведение техническими средствами принципов и конкретных особенностей функционирования биологических объектов. Развитие
этого направления базируется на математической интерпретации
деятельности нервной системы во главе с мозгом человека и реализуется в виде нейронных сетей на базе нейроподобного элемента –
аналога нейрона.
Мозг является, пожалуй, самой сложной из известных на сегодняшний день систем переработки информации. Достаточно сказать, что в нем содержится около 100 млрд нейронов, каждый из
которых имеет в среднем 10 тыс. связей. При этом мозг чрезвычайно надежен – ежедневно погибает большое количество нейронов, а
мозг продолжает функционировать. Обработка огромных объемов
информации осуществляется мозгом очень быстро, за доли секунды, несмотря на то, что нейрон является медленнодействующим
элементом со временем реакции не менее нескольких миллисекунд.
Пока не слишком понятно, как мозгу удается получить столь
впечатляющее сочетание надежности и быстродействия. Современной наукой довольно хорошо изучена структура и функции отдельных нейронов, имеются данные об организации внутренних и
внешних связей между нейронами некоторых структурных образований мозга, и совсем мало известно об участии различных структур в процессах переработки информации.
Нервные клетки, или нейроны, представляют собой особый вид
клеток в живых организмах, обладающих электрической активностью, основное назначение которых заключается в оперативном
управлении организмом. Нейрон (рис. 15) имеет тело (сому), дерево входов (дендриты) и выходов (аксон и его окончания). Сома, как
правило, имеет поперечный размер в несколько десятков микрон.
69
Синапс
Аксон
Тело клетки
Дендрит
Рис. 15. Схема биологического нейрона
Длина дендритов может достигать 1 мм, дендриты сильно ветвятся,
пронизывая сравнительно большое пространство в окрестности нейрона. Длина аксона может достигать сотен миллиметров. На соме и
на дендритах располагаются окончания аксонов, идущих от других
нервных клеток, причем каждое такое окончание имеет вид утолщения, называемого синаптической бляшкой, или синапсом. Поперечные размеры синапса, как правило, не превышают нескольких
микрон, чаще всего эти размеры составляют около 1 мкм.
Входные сигналы дендритного дерева взвешиваются и суммируются в соме, причем если результат не превышает некоторого порога, то выходной сигнал не формируется вовсе – нейрон «не срабатывает». Выходной сигнал проходит по ветвям аксона и достигает
синапсов, которые соединяют аксоны с дендритными деревьями
других нейронов. Через синапсы сигнал трансформируется в новый
входной сигнал для смежных нейронов. Этот входной сигнал может
быть положительным и отрицательным, т. е. возбуждающим или
тормозящим, в зависимости от вида синапсов. Величина входного сигнала, генерируемого синапсом, может быть различной даже
при одинаковой величине сигнала, приходящего в синапс. Эти различия определяются эффективностью или весом синапса, причем
синаптический вес может изменяться в процессе функционирования синапса. Многие ученые считают такое изменение нейрофизиологическим коррелятом, т. е. следом памяти. В таком случае роль
механизмов молекулярной памяти заключается в долговременном
закреплении этих следов.
Нейроны можно разбить на три большие группы: рецепторные,
промежуточные и эффекторные. Рецепторные нейроны обеспечивают ввод в мозг сенсорной информации. Они трансформируют сигналы, поступающие на органы чувств (оптические сигналы в сетчатке глаза, акустические в ушной улитке или обонятельные в хе70
морецепторах носа), в последовательность электрических импульсов своих аксонов. Эффекторные нейроны передают приходящие
на них сигналы исполнительным органам. На конце их аксонов
имеются специальные синаптические соединения с исполнительными органами, например мышцами, где возбуждение нейронов
трансформируется в сокращения мышц. Промежуточные нейроны
осуществляют обработку информации, получаемой от рецепторов,
и формируют управляющие сигналы для эффекторов. Именно они
образуют центральную нервную систему.
В основу искусственных нейронных сетей положены следующие
свойства естественных нейронных сетей:
– нейрон является простым обрабатывающим элементом;
– очень большое число нейронов участвует в обработке информации;
– один нейрон связан с большим числом других нейронов;
– связи между нейронами изменяются по весу;
– обработка информации идет параллельно.
На каждый включенный в нейронную сеть искусственный нейрон (рис. 16) поступает вектор входных сигналов x=(x1, …, хn),
представляющий собой выходные сигналы других нейронов сети,
которые соответствуют сигналам, поступающим в синапсы биологических нейронов. Каждый входной сигнал умножается на соответствующий элемент вектора весовых коэффициентов w=(w1,
…, wn). Взвешенные весовыми коэффициентами входные сигналы
поступают на блок суммирования, соответствующий телу клетки,
где их суммирование и определяет уровень возбуждения нейрона s:
s=
n
∑ wixi или в векторной форме: s=wxT. Отметим, что являющийi =1
ся аналогом эффективности синапса весовой коэффициент имеет
положительное значение для возбуждающих и отрицательное значение – для тормозящих связей.
x1 w1
x2 w2
.......
∑
s
f
y
xn wn
Рис. 16. Схема искусственного нейрона
71
а)
y
б)
1
y
1
0,5
θ
0
s
0
s
Рис. 17. Функции возбуждения нейронов: а – бинарная; б – сигмоидальная
Выходной сигнал нейрона у определяется путем пропускания
уровня возбуждения s через нелинейную функцию f: y=f(s–θ), где
θ – некоторое постоянное смещение, являющееся аналогом порога
биологического нейрона. Обычно в качестве функции f используются простейшие нелинейные функции:
{
– бинарная y =
1, s ≥ θ
(рис. 17, а);
0, s < θ
– сигмоидальная y = 1 (1 + e −(s −θ) ) (рис. 17, б).
Поведение искусственного нейрона в сети зависит как от значения весовых параметров, так и от функции возбуждения. Нейроны
с сигмоидальным возбуждением имеют больше сходства с реальными нейронами, чем нейроны с пороговым возбуждением, но любой
из этих типов можно рассматривать лишь как приближение к биологическому нейрону.
5.2. Топология нейронных сетей
Нейронная сеть представляет собой совокупность большого числа нейронов, топология соединения которых зависит от типа сети.
Чтобы создать нейронную сеть для решения какой-либо конкретной задачи, необходимо выбрать способ соединения нейронов друг
с другом и соответствующим образом подобрать значения весовых
параметров на этих связях, причем возможность влияния одного
нейрона на другой определяется установленными соединениями, а
степень влияния определяет вес соединения.
В искусственной нейронной сети пренебрегают многими известными характеристиками биологического прототипа, которые некоторые исследователи считают критическими. Например, в ней
не учитывается пространственно-временная нелинейность суммирования, которая особенно проявляется для сигналов, приходящих по возбуждающим и тормозящим синапсам, различного рода
72
временные задержки, эффекты синхронизации и частотной модуляции и т. п. Несмотря на это нейронные сети, простроенные на
основе таких простых элементов, демонстрируют ассоциативные
свойства, напоминающие свойства биологических систем.
Теоретические основы нейронных сетей были заложены в начале 40-х годов, когда У. Мак-Каллок и У. Питтс сформулировали
основные положения теории деятельности головного мозга. Ими
была разработана модель нейрона как простейшего процессорного элемента, выполняющего вычисление переходной функции от
скалярного произведения вектора входных сигналов и вектора весовых коэффициентов, предложена конструкция сети таких нейронов для выполнения логических и арифметических операций и
сделано основополагающее предположение о том, что такая сеть
способна обучаться, распознавать образы, обобщать полученную
информацию.
В модели МакКаллока – Питтса нейроны имеют два состояния –
0 или 1 и бинарную функцию перехода. Каждый нейрон в сети
определяет взвешенную сумму состояний всех других нейронов и
сравнивает ее с порогом, чтобы определить свое собственное состояние. На рис. 18 представлены одиночные нейроны с тремя входами
и соответствующими весовыми коэффициентами для вычисления
логических функций И и ИЛИ. Пороговое значение – 0, т. е. нейрон «не срабатывает», если уровень возбуждения меньше нуля.
Основной недостаток модели МакКаллока – Питтса состоит в
том, что бинарная функция перехода не предоставляет нейронной
сети достаточную гибкость при обучении и настройке на заданную
задачу. Если значение вычисленного скалярного произведения
даже незначительно не достигает заданного порога, то выходной
сигнал не формируется вовсе, т. е. нейрон «не срабатывает». В результате теряется интенсивность выходного сигнала данного нейрона и, следовательно, формируется невысокое значение уровня на
взвешенных входах в следующем слое нейронов.
Дальнейшее развитие теория нейронных сетей получила благодаря Френсису Розенблату, добавившему в 1958 году в модель
x2 +1
1 –1
x1 +x2–1
^
1 –2
^
^
^
x2 +1 x +x –2
1
2
x1 x2
x1 x2 –1
^
x1 +1
x1 +1
(x1 x2 ) –
x1 x2 x1 x2 +1 (x x ) –1 x1+2x 2
1 2
1
^
–1
Рис. 18. Вычисление логических функций с помощью нейронов
73
МакКаллока – Питтса способность связей к модификации, что сделало нейронную сеть обучаемой. Эта модель была названа персептроном. Первоначально персептрон представлял собой однослойную
структуру с жесткой пороговой функцией и бинарными или многозначными входами. Персептрон применялся для решения задачи
автоматической классификации образов, которая в общем случае
состоит в разделении пространства признаков между заданным
количеством классов. Значения признаков распознаваемого образа подаются на входы персептрона, а значения выходов обученного персептрона должны соответствовать классу, к которому относится распознаваемый образ. Первые персептроны были способны
распознавать некоторые буквы латинского алфавита. Пример однослойной сети с m входами и тремя выходами, позволяющей распознавать соответственно три класса образов, приведен на рис. 19.
В процессе обучения персептрону последовательно предъявляются образы из обучающего множества, каждый из которых
представляет собой вектор активностей входных сигналов X вместе с желаемым вектором активностей выходных сигналов сети Y.
Обучение заключается в таком изменении весовых коэффициентов
wij, которое приводит в итоге к максимуму правильного распознавания. Если после предъявления очередного образа из обучающего
множества выходы системы срабатывают правильно, то весовые
коэффициенты связей не изменяются, а если неправильно, то весовым коэффициентам дается небольшое приращение в сторону
улучшения распознавания. В результате такой процедуры, относяВыходной
вектор Y
Входной
вектор X
x1
x2
w 11
I1
N1
w 12
N2
I2
w 13
w m1
xm
w m3
Im
Рис. 19. Однослойная нейронная сеть
74
y1
N3
y2
yn
щейся к классу методов обучения с учителем, получаются значения весов, минимизирующие среднюю ошибку на всем обучающем
множестве образов.
Серьезным недостатком персептрона является то, что не всегда
существует такая комбинация весовых коэффициентов, при которой имеющееся множество образов будет распознаваться. Например, невозможно подобрать весовые коэффициенты персептрона
для реализации логической функции «исключающего ИЛИ» (сложение по модулю два). Причина этого недостатка состоит в том,
что однослойный персептрон реализует только линейную разделяющую поверхность в пространстве признаков. Однако лишь небольшое количество задач предполагает линейную разделимость
пространства признаков. Выходом из этого положения является
использование многослойного персептрона, способного строить
ломаную границу между распознаваемыми образами, но в таком
случае возникает проблема слабой формализации метода обучения
персептрона. На рис. 18 представлен вариант двуслойной сети из
трех нейронов, реализующей логическую операцию сложения по
модулю два.
В 70-е годы интерес к нейронным сетям значительно упал, однако работы по их исследованию продолжались. Был предложен ряд
интересных разработок, например когнитрон, способный хорошо
распознавать достаточно сложные образы независимо от поворота
и изменения масштаба изображения. Автором когнитрона является японский ученый И. Фукушима.
Начало современному математическому моделированию многослойных нейронных сетей положено в 1982 году работами Хопфилда, в которых была разработана математическая модель ассоциативной памяти на нейронной сети и введена функция вычислительной энергии нейронной сети. Показано, что для однослойной нейронной сети со связями типа «все на всех» характерна сходимость
к одной из конечного множества равновесных точек, которые являются локальными минимумами функции энергии, содержащей
в себе всю структуру взаимосвязей в сети. Привлекательность подхода Хопфилда состоит в том, что нейронная сеть для конкретной
задачи может быть запрограммирована без обучающих итераций,
так как веса связей вычисляются на основании вида функции энергии, сконструированной для этой задачи.
Развитием модели Хопфилда для решения комбинаторных оптимизационных задач и задач ИИ является машина Больцмана,
предложенная и исследованная Джефери Е. Хинтоном и Р. Земелом. В ней каждое состояние сети характеризуется определенным
75
значением функции консенсуса, являющейся аналогом функции
энергии. Максимум функции консенсуса и соответствует оптимальному решению задачи, однако, следует признать, что проблема представления функции энергии или консенсуса является не
менее сложной, чем разработка эффективного алгоритма обучения
многослойной нейронной сети.
В многослойных нейронных сетях связи между собой имеют
только соседние слои, при этом каждый нейрон предыдущего слоя
связан со всеми нейронами последующего слоя. Нейроны обычно
имеют сигмоидальную функцию возбуждения. Первый слой нейронов называется входным и содержит число нейронов, соответствующее двоичному представлению вектора признаков распознаваемых образов. Последний слой нейронов называется выходным и
содержит столько нейронов, сколько классов образов распознается.
Между входным и выходным слоями располагается один или более
скрытых слоев. Определение числа скрытых слоев и числа нейронов в каждом слое для конкретной задачи производится эвристическими методами.
Предположим, что необходимо научить нейронную сеть распознавать рукописные цифры. Можно воспользоваться матрицей из
256 сенсоров, каждый из которых регистрирует присутствие или
отсутствие чернильного пятнышка в пределах маленькой площадки – фрагмента одной цифры. В таком случае для сети потребуется
256 входных нейронов, 10 выходных нейронов (по одному на каждую возможную цифру) и некоторое количество скрытых нейронов. Для каждой цифры, регистрируемой сенсорами, сеть должна
генерировать высокую активность в соответствующем выходном
нейроне и низкую в остальных выходных нейронах.
В процессе обучения системе предъявляется изображение цифры и сравнивается действительная активность на 10 выходных
нейронах с желаемой активностью, затем подсчитывается ошибка
между действительным и желаемым выходом, после чего вес каждой связи изменяется так, чтобы уменьшить ошибку. Описанный
цикл повторяется со многими различными написаниями каждой
цифры до тех пор, пока сеть не научится правильно распознавать
все возможные изображения.
5.3. Алгоритм обратного распространения
Основной проблемой при проектировании многослойных нейронных сетей является разработка алгоритма изменения весовых
коэффициентов. Например, можно изменять каждый вес на вели76
чину, пропорциональную скорости, с которой изменяется ошибка
по мере изменения веса. Эту величину, называемую производной
ошибки по весу и обозначаемую EW, в общем случае вычислить достаточно сложно. Один из способов вычисления EW заключается в
том, чтобы изменить вес на очень маленькую величину и посмотреть, как изменится ошибка. Однако этот метод малоэффективен,
поскольку требует отдельных вариаций для каждого из многих весов.
В 1974 году Поль Дж. Вербос изобрел значительно более эффективную процедуру для вычисления EW, известную теперь как алгоритм обратного распространения (back propagation algorithm). Этот
алгоритм стал одним из наиболее важных инструментов в обучении
нейронных сетей.
Алгоритм обратного распространения проще всего понять, когда все нейроны сети линейны. Алгоритм вычисляет каждую EW,
сначала вычисляя EA – скорость, с которой изменяется ошибка
при изменении уровня активности нейрона. Для выходных нейронов EA является просто разностью между действительным и
желаемым выходом. Чтобы вычислить EA для скрытого нейрона
в слое, непосредственно предшествующем выходному слою, сначала идентифицируются все веса между этим скрытым нейроном
и выходными нейронами, с которыми соединен данный скрытый
нейрон. Затем эти веса умножаются на величины EA для этих выходных нейронов, а полученные произведения складываются. Эта
сумма и равна EA для данного скрытого нейрона. Вычислив EA для
всех нейронов скрытого слоя, прилегающего к выходному, можно
аналогичным образом рассчитать EA и для других слоев, перемещаясь в направлении, обратном тому, в котором активность нейронов распространяется по сети. Отсюда и название алгоритма обратного распространения. После того как значение EA для нейрона
вычислено, подсчитать EW для каждой входной связи нейрона уже
несложно. Величина EW является произведением EA и активности
во входной цепи.
Для нелинейных нейронов алгоритм обратного распространения
включает дополнительный шаг – перед очередным перемещением
в обратном направлении EA необходимо преобразовать в EI – скорость, с которой изменяется ошибка по мере изменения суммарного входа нейрона.
Математически алгоритм обратного распространения можно
представить следующей последовательностью шагов. После того
как активности всех выходных нейронов определены в соответствии с имеющимися на данный момент весовыми коэффициентами
77
всех нейронов сети и вектором входных сигналов, полная ошибка
k
∑ (y j − d j ) 2, где yj, dj – соответственно
сети вычисляется как E = 0,5
j =1
имеющийся и желаемый уровни активности j-го нейрона в верхнем
слое; k – число нейронов. Значение EAj выходного нейрона опредеdE
= y j − d j.
ляется как EA j =
dy j
На втором шаге вычисляется, насколько быстро изменяется
ошибка по мере изменения суммарного входа, получаемого выходным нейроном. Эта величина (EI) есть результат первого шага,
умноженный на скорость изменения выходного нейрона при измеdy j
dE dE dy j
нении его суммарного входа, т. е. EI j =
=
= EA j
. Для
ds j dy j ds j
ds j
dy j
нейронов с сигмоидальной функцией возбуждения
= y j (1 − y j ).
ds j
На третьем шаге вычисляется скорость изменения ошибки при
изменении веса на i-й входной связи j-го выходного нейрона. Эта
dE dE ds j
величина (EWij) есть EWij =
=
= EI j yi .
dwij ds j dxij
На четвертом – ключевом шаге вычисляется скорость изменения ошибки при изменении активности нейрона из предыдущего
слоя (EAi). Так как изменение активности нейрона из предыдущего
слоя влияет на активности всех выходных нейронов, с которыми
он связан, то для определения суммарного воздействия на ошибку
необходимо сложить все эти воздействия на выходные нейроны:
dE
dE ds j
EAi =
=
= EI jwij .
dxi
j ds j dx ij
j
Пользуясь последовательно шагами 2 и 4, можно преобразовать
величины EA одного слоя нейронов в EA предыдущего слоя вплоть
до начального слоя. Зная EA для нейрона, можно воспользоваться
шагами 2 и 3,чтобы вычислить EW на его выходных связях.
Алгоритм обратного распространения продемонстрировал значительную эффективность при обучении нейронных сетей со многими слоями решению широкого класса задач, в которых отношения между входом и выходом нелинейны, а количество обучающих данных велико. Такие сети вполне способны распознавать
рукописные цифры, предсказывать изменения валютного курса и
оптимизировать химические процессы, идентифицировать переро-
∑
78
∑
дившиеся предраковые клетки в анализируемых образцах ткани
и регулировать положение зеркал в телескопах, чтобы исключить
атмосферные искажения.
Р. Андерсен из Массачусетского технологического института и
Д. Зипсер из Калифорнийского университета в Сан-Диего показали, что алгоритм обратного распространения представляет собой
весьма эффективный инструмент для понимания функций некоторых нейронов в коре головного мозга. Применив алгоритм обратного распространения, они научили нейронную сеть реагировать на
зрительные стимулы, после чего обнаружили, что реакция скрытых нейронов удивительно схожа с реакцией реальных нейронов,
выполняющих преобразование зрительной информации, поступающей от сетчатки, в форму, необходимую для более глубоких областей мозга, перерабатывающих зрительную информацию.
Алгоритм обратного распространения оказался достаточно хорош при создании представлений о распознаваемом образе в скрытых нейронах сети и показал эффективность процедур обучения
нейронных сетей, основанных на постепенном изменении весовых
коэффициентов входных сигналов нейронов с целью уменьшить
ошибки. Ранее многие ученые полагали, что подобные методы окажутся безнадежными, поскольку должны неизбежно приводить к
локально оптимальным, но в более широком масштабе – ошибочным решениям. Например, сеть для распознавания цифр может
устойчиво сходиться к набору весов, при котором она будет путать
единицы с семерками, хотя и существует набор весов, позволяющий различать эти цифры наряду с другими. Из-за опасений подобного рода распространилось убеждение, что процедура обучения
представляет практический интерес только в том случае, если она
гарантирует сходимость к глобально оптимальному решению. Успешное использование метода обратного распространения показало, что для многих задач глобальная сходимость не является необходимым условием достижения вполне приемлемых результатов.
Следует отметить, что с биологической точки зрения, как подобие работы головного мозга, метод обратного распространения
представляется не слишком убедительным. Наиболее очевидная
трудность заключается в том, что информация должна проходить
по тем же самым связям в обратном направлении, от каждого последующего уровня к предыдущему. Ясно, что в реальных нейронах
этого не происходит. Однако в мозге существует множество путей,
ведущих от следующих слоев нервных клеток к предыдущим, и эти
пути могут использоваться для передачи информации, необходимой для обучения.
79
Серьезную проблему представляет собой и падение быстродействия алгоритма обратного распространения по мере возрастания
размеров сети. Время, требующееся для вычисления производных
от ошибки по весам на заданном тренировочном примере, пропорционально размерам сети, поскольку объем вычислений пропорционален количеству весов. Однако более крупные сети требуют
большего количества тренировочных примеров, и им приходится
модифицировать веса большее число раз. Следовательно, время
обучения растет значительно быстрее, чем размеры сети.
Еще одна существенная проблема метода обратного распространения заключается в том, что такая нейронная сеть требует учителя, предоставляющего желаемый выход для каждого тренировочного примера. Если сеть сталкивается с большим набором сочетаний сигналов, но не имеет никакой информации о том, что с ними
следует делать, то очевидно, что перед ней нет четко поставленной
задачи. Тем не менее, исследователи разработали несколько универсальных, неконтролируемых процедур, которые могут правильно регулировать весовые параметры сети. Все эти процедуры имеют
два общих качества: они оперируют, явно или неявно, с некоторым
понятием качества представления и работают, изменяя веса, чтобы повысить качество представления, вырабатываемого скрытыми
нейронами.
5.4. Сеть встречного распространения
Значительными преимуществами перед сетью, обучающейся по
алгоритму обратного распространения, обладает сеть встречного
распространения, процесс обучения которой представляет собой
комбинацию метода обучения Кохонена с методом обучения с учителем Гроссберга и функционирует подобно столу справок, способному к обобщению.
В процессе обучения входные векторы ассоциируются с соответствующими выходными векторами. Эти векторы могут быть
двоичными, состоящими из нулей и единиц, или непрерывными.
Когда сеть обучена, приложение входного вектора приводит к требуемому выходному вектору. Обобщающая способность сети позволяет получать правильный выход даже при приложении входного
вектора, который является неполным или слегка неверным. Это
позволяет использовать данную сеть для распознавания образов,
восстановления информации и усиления сигналов.
Структура сети встречного распространения, состоящая из трех
слоев нейронов, показана на рис. 20.
80
Входной
вектор X
w11
x1
I1
x2
K1
w12
v 11
v 21
K2
I2
wm1
xm
V1
W1
Im
Входной
слой
G1
Выходной
вектор Y
y1
G2
y2
w1n
wmn
Kn
v np
Слой
Кохонена
Gp
yn
Слой
Гроссберга
Рис. 20. Сеть встречного распространения
Нейроны входного или нулевого слоя, показанные кружками,
служат лишь точками разветвления входного вектора и не выполняют вычислений. Число нейронов в нулевом слое равно размерности входного вектора. Каждый нейрон нулевого слоя соединен с
каждым нейроном первого слоя, называемого слоем Кохонена, отдельной связью с весом wmn. Эти веса в целом рассматриваются как
матрица весов W. Аналогично, каждый нейрон в слое Кохонена
соединен с каждым нейроном в выходном слое, называемом слоем
Гроссберга, отдельной связью с весом vnp. Эти веса образуют матрицу весов V. Число нейронов в слое Гроссберга равно размерности
выходного вектора Y.
Как и другие сети, сеть встречного распространения функционирует в двух режимах: в рабочем режиме, при котором принимается
входной вектор Х и выдается выходной вектор Y, и в режиме обучения, при котором подается входной вектор и веса корректируются,
чтобы получить требуемый выходной вектор.
В рабочем режиме слой Кохонена функционирует по алгоритму
«победитель забирает все», т. е. для данного входного вектора один
и только один нейрон Кохонена выдает на выходе логическую единицу, все остальные выдают ноль. Нейроны Кохонена можно воспринимать как набор электрических лампочек, соединенных так,
что для любого входного вектора загорается только одна из них,
причем число нейронов в слое Кохонена не обязательно совпадает
с числом возможных входных векторов, что позволяет проводить
обобщение схожих в некотором смысле входных векторов.
81
Ассоциированное с каждым нейроном Кохонена множество весов соединяет его с каждым входом. Например, нейрон Кохонена
K1 имеет веса w11, w21, …, wm1, составляющие весовой вектор W1
(см. рис. 20). Они соединяются через входной слой с входными сигналами х1, x2, …, xm, составляющими входной вектор X. Подобно
нейронам других нейронных сетей, выход каждого нейрона Кохонена является просто суммой взвешенных входов. В векторной записи S = WX, где S – вектор уровней возбуждения нейронов слоя
Кохонена. Нейрон Кохонена с максимальным возбуждением является «победителем». Его выход равен единице, у остальных он равен нулю.
Слой Гроссберга функционирует в сходной манере. Выход его
нейрона является взвешенной суммой выходов k1, k2,..., kn слоя Кохонена, образующих вектор K. Например, нейрон слоя Гроссберга
G1 имеет веса v11, v21, …, vm1, составляющие весовой вектор V1 (см.
рис. 20). В векторной записи Y = VK, где Y – выходной вектор слоя
Гроссберга. Фактически каждый нейрон слоя Гроссберга лишь выдает величину веса, который связывает этот нейрон с единственным ненулевым нейроном Кохонена.
В результате обучения слой Кохонена классифицирует входные
векторы в группы схожих по значениям признаков. Это достигается с помощью такой подстройки весов слоя Кохонена, что близкие
входные векторы активируют один и тот же нейрон данного слоя.
Затем задачей слоя Гроссберга является получение требуемых выходов.
Обучение Кохонена является самообучением, протекающим
без учителя. Поэтому трудно, да и не нужно предсказывать, какой
именно нейрон Кохонена будет активироваться для заданного входного вектора. Необходимо лишь гарантировать, чтобы в результате
обучения разделялись несхожие входные векторы.
Весьма желательно, хотя и не обязательно, нормализовать входные векторы перед тем, как предъявлять их сети. Это выполняется
с помощью деления каждой компоненты входного вектора на длину вектора, которая находится извлечением квадратного корня из
суммы квадратов компонент вектора. В результате входной вектор
превращается в единичный вектор с тем же самым направлением,
т. е. в вектор единичной длины в n-мерном пространстве признаков,
а каждый входной вектор графически можно представить стрелкой, оканчивающейся на поверхности единичной гиперсферы.
При обучении слоя Кохонена на вход подается входной вектор и
вычисляются его скалярные произведения с векторами весов, связанными со всеми нейронами Кохонена. Нейрон с максимальным
82
значением скалярного произведения объявляется «победителем»,
и его веса подстраиваются. Так как скалярное произведение, используемое для вычисления вектора S, является мерой сходства
между входным вектором и вектором весов, то процесс обучения
состоит в выборе нейрона Кохонена с весовым вектором, наиболее
близким к входному вектору, и дальнейшем приближении весового вектора к входному. В результате сеть самоорганизуется таким
образом, что данный нейрон Кохонена имеет максимальный выход
для данного входного вектора. Уравнение, описывающее процесс
обучения, имеет следующий вид: wн = wс + α(x – wс), где wн – новое значение веса, соединяющего входную компоненту х вектора
X с выигравшим нейроном; wс – предыдущее значение этого веса;
α – коэффициент скорости обучения, который может варьироваться в процессе обучения.
Каждый вес, связанный с выигравшим нейроном Кохонена, изменяется пропорционально разности между его величиной и величиной входа, к которому он присоединен. Направление изменения
минимизирует разность между весом и его входом. На рис. 21 этот
процесс показан геометрически в двумерном виде. Сначала находится вектор X–Wс, для этого проводится отрезок из конца W в
конец X. Затем этот вектор укорачивается умножением его на скалярную величину α, меньшую единицы, в результате чего получается вектор изменения ∆ . Окончательно новый весовой вектор Wн
является отрезком, направленным из начала координат в конец
вектора ∆ . Отсюда можно видеть, что эффект обучения состоит во
вращении весового вектора в направлении входного вектора без существенного изменения его длины.
Переменная α является коэффициентом скорости обучения, который вначале обычно равен ~ 0,7 и может постепенно уменьшатьα (X–Wc ) = ∆
Wc
X– Wc
Wн
X– входной вектор
Рис. 21. Вращение весового вектора в процессе обучения
83
ся в процессе обучения. Это позволяет делать большие начальные
шаги для быстрого грубого обучения и меньшие шаги при подходе
к окончательной величине.
Если бы с каждым нейроном Кохонена ассоциировался один
входной вектор, то слой Кохонена мог бы быть обучен с помощью одного вычисления весов, так как веса нейрона-«победителя» просто
приравнивались бы к компонентам обучающего вектора (α=1). Как
правило, обучающее множество включает много сходных между
собой входных векторов, и сеть должна быть обучена активировать
один и тот же нейрон Кохонена для каждого из них. В таком случае
веса каждого нейрона должны получаться усреднением входных
векторов, которые должны его активировать. Постепенное уменьшение величины α уменьшает воздействие каждого обучающего
шага, так что окончательное значение будет средней величиной от
входных векторов, на которых происходит обучение. Таким образом, веса, ассоциированные с нейроном, примут значение вблизи
«центра» входных векторов, для которых данный нейрон является
«победителем».
Всем весам сети перед началом обучения следует придать начальные значения. Общепринятой практикой при работе с нейронными сетями является присваивание весам небольших случайных
значений (рандомизация весов). При обучении слоя Кохонена случайно выбранные весовые векторы следует нормализовать. Окончательные значения весовых векторов после обучения совпадают с
нормализованными входными векторами, следовательно, нормализация перед началом обучения приближает весовые векторы к
их окончательным значениям, сокращая, таким образом, обучающий процесс.
Рандомизация весов слоя Кохонена может породить серьезные
проблемы при обучении, так как в результате ее весовые векторы
распределяются равномерно по поверхности гиперсферы. Из-за
того, что входные векторы, как правило, распределены неравномерно и имеют тенденцию группироваться на относительно малой
части поверхности гиперсферы, большинство весовых векторов будут так удалены от любого входного вектора, что они никогда не
будут давать наилучшего соответствия. Эти нейроны Кохонена будут всегда иметь нулевой выход и окажутся бесполезными. Более
того, оставшихся весов, дающих наилучшие соответствия, может
оказаться слишком мало, чтобы разделить входные векторы на
классы, которые расположены близко друг к другу на поверхности
гиперсферы.
84
Допустим, что имеется несколько множеств входных векторов,
все множества сходные, но должны быть разделены на различные
классы. Сеть должна быть обучена активировать отдельный нейрон
Кохонена для каждого класса. Если начальная плотность весовых
векторов в окрестности обучающих векторов слишком мала, то может оказаться невозможным разделить сходные классы из-за того,
что не будет достаточного количества весовых векторов в интересующей нас окрестности, чтобы приписать по одному из них каждому
классу входных векторов.
Наоборот, если несколько входных векторов получены незначительными изменениями из одного и того же образца и должны быть
объединены в один класс, то они должны включать один и тот же
нейрон Кохонена. Если же плотность весовых векторов очень высока вблизи группы слегка различных входных векторов, то каждый
входной вектор может активировать отдельный нейрон Кохонена.
Это не является катастрофой, так как слой Гроссберга может отобразить различные нейроны Кохонена в один и тот же выход, но это
расточительная трата нейронов Кохонена.
Наиболее желательное решение состоит в том, чтобы распределять весовые векторы в соответствии с плотностью входных векторов, которые должны быть разделены, помещая тем самым больше
весовых векторов в окрестности большого числа входных векторов.
На практике это невыполнимо, однако существует несколько методов приближенного достижения тех же целей.
Одно из решений, известное под названием метода выпуклой
комбинации, состоит в том, что все веса приравниваются одной и
1
, где п – число входов и, следовательно,
той же величине wi =
n
число компонент каждого весового вектора. Благодаря этому все
весовые векторы совпадают и имеют единичную длину.
Каждой же компоненте входа Х придается значение
1− α
, где п – число входов. В начале α очень мало, вследсx i = αx i +
n
твие чего все входные векторы имеют длину, близкую к 1 , и
n
почти совпадают с векторами весов. В процессе обучения сети α
постепенно возрастает, приближаясь к единице. Это позволяет разделять входные векторы и окончательно приписывает им их истинные значения. Весовые векторы отслеживают один или небольшую
группу входных векторов и в конце обучения дают требуемую картину выходов. Метод выпуклой комбинации хорошо работает, но
замедляет процесс обучения, так как весовые векторы подстраива85
ются к изменяющейся цели. Другой подход состоит в добавлении
шума к входным векторам. Тем самым они подвергаются случайным изменениям, схватывая, в конце концов, весовой вектор. Этот
метод также работоспособен, но еще более медленен, чем метод выпуклой комбинации.
Третий метод начинает со случайных весов, но на начальной стадии обучающего процесса подстраивает все веса, а не только связанные с выигравшим нейроном Кохонена. Тем самым весовые векторы перемещаются ближе к области входных векторов. В процессе
обучения коррекция весов начинает производиться лишь для ближайших к «победителю» нейронов Кохонена. Этот радиус коррекции постепенно уменьшается, так что, в конце концов, корректируются только веса, связанные с выигравшим нейроном Кохонена.
Еще один метод наделяет каждый нейрон Кохонена «чувством
справедливости». Если он становится «победителем» чаще своей
законной доли времени (примерно 1/k, где k – число нейронов Кохонена), он временно увеличивает свой порог, что уменьшает его
шансы на выигрыш, давая тем самым возможность обучаться и
другим нейронам.
Во многих приложениях точность результата существенно зависит от распределения весов. К сожалению, эффективность различных решений исчерпывающим образом не оценена и остается
проблемой.
Настройка нейронов слоя Гроссберга фактически сводится к
последовательной установке значений весов тех связей, которые
связывают нейроны слоя с единственным ненулевым в данный момент нейроном Кохонена, соответствующим входному вектору X,
так, чтобы на выходе сети встречного распространения получить
требуемый вектор Y.
Рассмотрим простой пример создания сети встречного распространения для хранения и восстановления частично искаженной
информации. Пусть нам необходимо сохранять два 6-элементных
вектора с бинарными значениями элементов следующего вида:
X1=(1,1,1,0,0,0) и X2=(0,0,0,1,1,1). Число нейронов нулевого слоя
равно числу элементов входного вектора (m=6), число нейронов слоя
Кохонена равно числу различаемых входных векторов (n=2), число нейронов слоя Гроссберга в данном случае равно числу элементов входного вектора (p=6). Установим первоначальную настройку
весовых коэффициентов первого нейрона слоя Кохонена: w11=0,1;
w21=0,2; w31=0,3; w41=0,4; w51=0,5; w61=0,6; а второго нейрона –
w12=0,6; w22=0,5; w32=0,4; w42=0,3; w52=0,2; w62=0,1. Подадим на
вход вектор X1 и получим значения S1=0,6; S2=1,5; т. е. «победи86
тель» – второй нейрон. Изменим вектор весовых коэффициентов
этого нейрона так, что Wн2= Wс2+1,0(X1–Wc2): w12=1,0; w22=1,0;
w32=1,0; w42=0,0; w52=0,0; w62=0,0. Подадим на вход вектор X2
и получим значения S1=1,5, S2=0,0, т. е. «победитель» – первый
нейрон. Изменим вектор весовых коэффициентов этого нейрона:
w11=0,0; w21=0,0; w31=0,0; w41=1,0; w51=1,0; w61=1,0. На этом настройка слоя Кохонена закончена. Настройка слоя Гроссберга в
данном случае заключается в установлении таких весовых коэффициентов, чтобы выходной вектор совпадал с соответствующим ему
входным вектором, т. е. v21=0,0; v21=0,0; v31=0,0; v41=1,0; v51=1,0;
v61=1,0; v12=1,0; v22=1,0; v32=1,0; v42=0,0; v52=0,0; v62=0,0. Настроенная таким образом сеть выдает на выходе правильный вектор
даже при незначительных ошибках во входном векторе, например,
если во входном векторе одна единица ошибочно заменена на нуль
или наоборот, то на выходе будет получен исправленный вектор, в
чем можно убедиться, подставив соответствующие входные векторы в настроенную выше сеть.
5.5. Практическая реализация нейронных сетей
Нейронные сети могут быть реализованы двумя путями: первый – программная модель, второй – аппаратная. На современном
рынке изделия, основанные на использовании нейронных сетей,
сначала появились в виде нейроплат. В качестве типичного примера
можно назвать плату МВ 86232 японской фирмы Fujitsu. На плате
размещены процессор цифровой обработки сигналов и оперативная
память емкостью 4 Мбайт, что позволяет использовать такую плату
для реализации сети, содержащей до тысячи нейронов.
Основными коммерческими аппаратными изделиями на основе нейронных сетей являются нейроБИС. В настоящее время выпускаются более 20 типов нейроБИС, параметры которых порой
различаются на несколько порядков. Среди них – модель ETANN
фирмы Intel. Эта БИС, выполненная по микронной технологии, является реализацией сети с 64 тыс. нейронов и 10 240 синапсами. Ее
цена 2 000 $. К более дешевым нейроБИС (41 $) относится модель
MD 1 220 фирмы Micro Devices (8 нейронов и 120 синапсов).
Большинство сегодняшних нейрокомпьютеров представляют
собой просто персональный компьютер или рабочую станцию, в состав которых входит дополнительная нейроплата. К их числу относятся, например, компьютеры серии FMR фирмы Fujitsu. Такие
системы имеют бесспорное право на существование, поскольку их
возможностей вполне достаточно для разработки новых алгорит87
мов и решения большого числа прикладных задач на основе технологии нейросетей.
Однако наибольший интерес представляют специализированные
нейрокомпьютеры, реализующие принципы нейронных сетей на
аппаратном уровне. Типичными представителями таких систем являются компьютеры семейства Mark фирмы TRW. Модель Mark III
представляет собой рабочую станцию, содержащую до 15 процессоров семейства Motorola 68000 с математическими сопроцессорами.
Все процессоры объединены шиной VME. Архитектура системы,
поддерживающая до 65 тыс. виртуальных процессорных нейронов
с более чем 1 млн настраиваемых соединений, позволяет обрабатывать до 450 тыс. соединений/с. Mark IV – это однопроцессорный
суперкомпьютер с конвейерной архитектурой. Он поддерживает до
236 тыс. виртуальных процессорных нейронов, что позволяет обрабатывать до 5 млн соединений/с. Компьютеры семейства Mark имеют общую программную оболочку ANSE (Artificial Neural System
Environment), обеспечивающую программную совместимость моделей. Фирма TRW предлагает также пакет Mark II – программный
эмулятор нейронной сети.
Другой интересной моделью является нейрокомпьютер NETSIM,
созданный фирмой Texas Instruments на базе разработок Кембриджского университета. Его топология представляет собой трехмерную решетку стандартных вычислительных узлов на базе процессоров 80188, а производительность достигает 450 млн соединений/с. Компьютер NETSIM используется для моделирования сети
Хопфилда – Кохонена и алгоритма обратного распространения.
Фирма Computer Recognitiion Systems (CRS) продает серию нейрокомпьютеров WIZARD/CRS 1000, предназначенных для обработки видеоизображений. Размер входного изображения 512×512
пикселей. Модель CRS 1000 уже нашла применение в промышленных системах автоматического контроля.
Чтобы применение нейронной сети было оправдано и она могла
бы решить поставленную задачу, последняя должна обладать следующими признаками:
– отсутствует алгоритм или не известны принципы решения задачи, но накоплено достаточное число примеров;
– проблема характеризуется большими объемами входной информации;
– данные неполны или избыточны, зашумлены, частично противоречивы.
Таким образом, нейронные сети хорошо подходят для распознавания образов и решения задач классификации, оптимизации и
88
прогнозирования. Ниже приведен перечень возможных промышленных применений нейронных сетей, на базе которых либо уже
созданы коммерческие продукты, либо реализованы демонстрационные прототипы.
Банки и страховые компании: автоматическое считывание чеков и финансовых документов, проверка достоверности подписей,
оценка риска для займов, прогнозирование изменений экономических показателей.
Административное обслуживание: автоматическое считывание
документов, автоматическое распознавание штриховых кодов.
Нефтяная и химическая промышленность: анализ геологической информации, идентификация неисправностей оборудования,
разведка залежей минералов по данным аэрофотосъемок, анализ
составов примесей, управление процессами.
Военное дело и аэронавтика: разделение, идентификация, локализация, устранение шума, интерпретация звуковых сигналов,
обработка звуковых сигналов, распознавание целей, идентификация и локализация источников радарных сигналов, обобщение информации и прогнозирование развития ситуации, автоматическое
пилотирование.
Промышленное производство: управление манипуляторами,
адаптивная робототехника, обнаружение неисправностей, управление качеством, управление процессами.
Биомедицинская промышленность: анализ рентгенограмм, обнаружение отклонений в ЭКГ.
Телевидение и связь: адаптивное управление сетью связи, сжатие и восстановление изображения.
Служба безопасности: распознавание лиц, голосов, отпечатков
пальцев.
Представленный перечень далеко не полон. Ежемесячно средства массовой информации сообщают о новых коммерческих продуктах на базе нейронных сетей. Так, фирма LIAC выпускает аппаратуру для контроля качества воды. Нейросистемы фирмы SAIC
находят пластиковые бомбы в багаже авиапассажиров. Специалисты инвестиционного банка Citicomp (Лондон) с помощью программного нейропакета делают краткосрочные прогнозы колебаний
курсов валют.
89
6. Генетические алгоритмы
6.1. Методологическая основа генетических алгоритмов
Подобно нейронным сетям, генетические или эволюционные
алгоритмы основываются на свойствах биологических систем и их
популяций. В рамках такого подхода поиск решения некоторой интеллектуальной задачи рассматривается как конкуренция внутри
популяции между эволюционирующими кандидатами на роль решения. Каждое возможное решение-кандидат оценивается согласно критерию отбора. По результатам оценки определяется, будет
ли этот экземпляр участвовать в следующем поколении решений.
Затем с помощью операций, аналогичных трансформации генотипа в процессе биологического воспроизводства, создается новое поколение решений-кандидатов.
Методологическая основа генетических алгоритмов базируется на гипотезе селекции, которая в самом общем виде может быть
сформулирована так: чем выше приспособленность особи, тем
выше вероятность того, что в потомстве, полученном с ее участием, признаки, определяющие приспособленность, будут выражены
еще сильнее. Поскольку генетические алгоритмы имеют дело с популяциями постоянной численности, особую актуальность наравне
с критериями отбора родительских особей приобретают критерии
отбора особей на удаление из популяции. Чаще всего особи, обладающие низкой приспособленностью, не только не участвуют в генерации нового поколения, а удаляются из популяции на текущем
дискретном шаге эволюции.
В самом общем виде генетический алгоритм можно представить
следующим образом.
Пусть Р(t) – поколение особей, т. е. решений-кандидатов хit
в момент времени t: Р(t)= (х1t, х2t, ..., хпt). В момент времени t=0
инициализируется популяция Р(0). Далее циклически на каждом
шаге t вычисляется значение критерия качества для каждого члена популяции P(t), на основе значений критерия качества из P(t)
выбирается нужное число родительских особей и с помощью генетических операций создается следующее поколение, после чего, с
учетом значений критерия качества, особи популяции P(t) заменяются их потомками, и цикл повторяется. Процесс завершается после получения особи (решения) с требуемыми характеристиками.
Конкретные реализации генетических алгоритмов могут отличаться в зависимости от задачи. Какое процентное соотношение
особей выживает в следующем поколении? Сколько особей участ90
вует в скрещивании? Как часто и к кому применяются генетические операторы?
Процедуру замены особей популяции P(t) можно реализовать
простейшим образом, заменив фиксированное процентное соотношение слабейших кандидатов сильнейшими из полученных на данном шаге потомков. Более сложный подход состоит в упорядочении
популяции согласно критерию качества и удалении особей с учетом вероятности, обратно пропорциональной значению критерия
качества. Такой алгоритм замены известен под многими именами,
в том числе как метод Монте-Карло (Monte-Carlo), правило рулетки
(roulette wheel) или алгоритм отбора пропорционально критерию
качества (fitness proportionate selection). В этих алгоритмах существует шанс удаления самых «сильных» особей популяции, хотя вероятность их исключения очень низка. Преимущество применения
данного подхода в генетических алгоритмах состоит в возможности сохранения некоторых «слабых» особей, которые в дальнейшем
могут внести свой вклад в получение более «сильных» потомков.
Кандидатов на решение задачи, т. е. особей популяции, можно
описывать с помощью обычных битовых строк, хотя в генетических алгоритмах существуют и более сложные принципы представления особей. Предположим, что необходимо с помощью генетического алгоритма научиться классифицировать строки, состоящие из
единиц и нулей. В такой задаче популяцию битовых строк можно
описывать с помощью шаблона, состоящего из символов 1, 0 и #,
последний из которых может соответствовать как 1, так и 0. Следовательно, шаблон 1##00##1 представляет все восьмибитовые
строки, начинающиеся, заканчивающиеся 1 и содержащие в середине строки два нуля подряд.
При работе генетического алгоритма популяция кандидатов
Р(0) некоторым образом инициализируется. Обычно инициализация выполняется с помощью датчика случайных чисел. Для оценки решений-кандидатов вводится критерий качества f(хit), определяющий меру соответствия каждого кандидата в момент времени t.
Так, при классификации мерой соответствия кандидатов является
процентное соотношение правильных ответов на множестве обучающих примеров. При таком критерии качества каждому решениюf (x it )
кандидату соответствует значение
, где т(Р, t) – среднее знаm( P, t)
чение критерия качества для всех членов популяции. Обычно мера
соответствия изменяется во времени, поэтому критерий качества
может быть функцией от стадии решения всей проблемы или f(хit).
91
После анализа каждого кандидата выбираются пары для рекомбинации. При этом используются генетические операторы, в результате выполнения которых новые решения получаются путем
комбинации свойств родителей. Как и в естественном процессе эволюции, степень участия в репродуктивном процессе для каждого
кандидата определяется значением критерия качества: кандидаты
с более высоким значением критерия качества участвуют в процессе воспроизводства с более высокой вероятностью. Как уже отмечалось, выбор осуществляется на основе вероятностных законов,
когда слабые члены популяции имеют меньшую вероятность воспроизводства, однако такая возможность не исключается. Выживание некоторых слабейших особей имеет большое значение для
развития популяции, поскольку они могут содержать некоторые
важные компоненты решения, которые могут извлекаться при воспроизводстве, например фрагмент битовой строки.
Существует множество генетических операторов получения
потомства, обладающего свойствами своих родителей. Наиболее
типичный из них называется скрещиванием (crossover). При скрещивании два решения-кандидата делятся на несколько частей и
обмениваются этими частями, результатом становятся два новых
кандидата. Например, пусть входными данными для операции
скрещивания являются шаблоны битовых строк длины 8 следующего вида: 11#0101# и #110#0#1. Эти строки делятся на две равные части, после чего формируются два потомка, содержащих по
одному сегменту каждого из родителей, причем правая половина
одного родителя соединяется с левой половиной другого родителя. В рассматриваемом примере родители делятся на такие части:
11#0 | 101# и #110 | #0#1, а потомки имеют вид 11#0#0#1 и
#110101#. Заметим, что родители могут разбиваться в любой точке, которую можно выбирать и изменять случайным образом в ходе
решения задачи.
Если целевой класс – набор всех восьмибитовых строк, которые
начинаются и заканчиваются единицей, а искомое решение – шаблон, позволяющий выявлять такие строки, то обе родительские
строки подходят достаточно хорошо. Однако первый их потомок
гораздо точнее соответствует критерию качества, чем любой из родителей, так как с помощью этого шаблона не будет пропущена ни
одна из нужных строк. Заметим также, что его «собрат» гораздо
хуже, чем любой из родителей, поэтому эта особь, скорее всего, будет исключена из популяции.
Мутация (mutation) – это еще один важный генетический оператор. Она состоит в случайном выборе кандидата и случайном изме92
нении некоторых его свойств. Например, мутация может состоять
в случайном выборе бита в шаблоне и изменении его значения на
1, 0 или #. Значение мутации состоит в возможном восполнении
важных компонентов решения, отсутствующих в исходной популяции. Если в рассмотренном выше примере ни один из членов исходной популяции не содержит 1 в первой позиции, то в процессе
скрещивания нельзя получить потомка, обладающего этим свойством. Значение первого бита может измениться лишь вследствие
мутации. Этой цели можно также достичь с помощью другого генетического оператора – инверсии (inversion).
Работа генетического алгоритма продолжается до тех пор, пока
не будет достигнуто условие его завершения, например, для одного
или нескольких кандидатов значение критерия качества не превысит некоторого порога.
6.2. Представление задачи
в конъюнктивной нормальной форме
Основными проблемами при разработке генетического алгоритма для решения интеллектуальной задачи являются вопросы
представления пространства состояний задачи в терминах кодирования особей и выбор критериев качества особей. Во-первых, не все
задачи естественно и легко описать на уровне битового представления. Во-вторых, генетические операторы должны предотвращать
появление нежелательных взаимоотношений внутри популяции,
например, обязаны обеспечивать присутствие и уникальность всех
городов в маршруте коммивояжера. Кроме этого, следует учитывать взаимосвязи между значением критерия качества для различных состояний и методом кодирования, выбранным для данной задачи.
Одним из способов описания задачи является конъюнктивная
нормальная форма (КНФ) представления. Описание в КНФ – это
представление выражения в виде последовательности операторов,
связанных отношением И (&). Каждый из этих операторов должен
представлять собой дизъюнктивное выражение, определяемое отношением ИЛИ (∨ ), или литерал. Например, для литералов а, b,
с, d, е и f выражение (a∨c) & (a∨c∨e) & (b∨c∨d∨e) & (a∨b∨c) &
(e∨f) (“а» – это инверсия а) является КНФ. Это выражение представляет собой конъюнкцию пяти операторов, каждый из которых
является дизъюнкцией двух или нескольких литералов.
Представимость в конъюнктивной нормальной форме означает существование таких логических значений (1 или 0 либо true и
93
false) для каждого из шести литералов, при которых КНФ-выражение принимает значение true. Несложно проверить, что для доказательства представимости рассмотренного выше выражения в
конъюнктивной нормальной форме достаточно присвоить значение
false литералам a, b и е. Еще одно решение обеспечивается присвоением литералу е значения false, а с – true.
Естественным представлением особи в задаче с КНФ-описанием является последовательность из шести битов, каждый из которых представляет значение одного из шести литералов а, b, с, d, е
и f. Например, выражение 101010 означает, что литералы а, с и е
принимают значение true, a b, d и f – false. Для такой комбинации
значений литералов приведенное выше выражение принимает значение false. В процессе выполнения генетических операторов над
особями популяции требуется получить потомка, для которого
КНФ-выражение является истинным, т. е. в результате выполнения каждого генетического оператора должна получаться битовая
строка, которая может рассматриваться как кандидат на решение
задачи. Таким свойством обладают все рассмотренные до сих пор
генетические операторы. Например, в результате скрещивания и
мутации получаются битовые строки, которые могут стать решением задачи. Обмен (exchange), т. е. перемена мест двух произвольных битов, тоже обеспечивает получение возможного решения.
Как видно, данное представление особей в задаче с КНФ-описанием
является очень полезным.
Однако выбор критерия качества для популяции битовых строк
как потенциальных решений достаточно сложен. Задача считается
решенной, если найдена комбинация битов, при которой КНФ-выражение принимает значение true, причем КНФ-выражение представляет собой конъюнкцию пяти операторов, т. е. для получения
искомого решения все пять операторов должны иметь значение
true. Тогда можно определить рейтинг решения по шкале от 0 до 5
в зависимости от количества операторов, принимающих значение
true. Например, следующие особи будут иметь рейтинг: 110010 –
рейтинг 1, 010010 – рейтинг 2, 010011 – рейтинг 3, 001011 – рейтинг 5. Последняя особь и является решением. Такой генетический
алгоритм обеспечивает разумный подход к решению КНФ-проблемы, причем одним из важнейших свойств этого подхода является
неявный параллелизм, обеспечиваемый за счет одновременной обработки целой популяции решений. Этому представлению естественным образом соответствуют генетические операторы.
Более сложным является представление в виде генетического
алгоритма «задачи коммивояжера» – классической тестовой зада94
чи для систем ИИ, описанной в разд. 1. Одним из способов поиска минимального пути является генерирование и оценка всех возможных перестановок из N элементов в списке городов. Поэтому
представление особи и генетические операторы должны обеспечить
возможность получения этих перестановок.
Основная сложность состоит в выборе представления для маршрута посещения городов и подборе подходящих генетических
операторов. В то же время выбор критерия качества особи в данном
случае достаточно прост – это длина пути, т. е. чем короче маршрут, тем лучше.
Возможно несколько представлений маршрута как отдельной
особи. Пусть необходимо посетить девять городов 1, 2,..., 9, тогда
путь можно представить упорядоченным списком из девяти целых
чисел. Если представить порядковый номер каждого города четырехбитной строкой: 0001, 0010,..., 1001, то выражение 0001 0010
0011 0100 0101 0110 0111 1000 1001 представляет последовательность посещения городов по возрастанию их порядковых номеров
(пробелы в этом выражении поставлены только для простоты восприятия).
Далеко не все генетические операторы можно использовать при
данном описании особи. При скрещивании некоторые города могут
выпасть из последовательности, другие встретятся в ней дважды
или будут получены номера несуществующих городов, т. е. скрещивание использовать нельзя. То же можно сказать и про мутацию. Предположим, что крайний слева бит в обозначении шестого
города изменится на 1. Тогда полученное число 1110 будет соответствовать порядковому номеру 14, который не входит в допустимый
перечень городов. Обмен городов является допустимой операцией,
только когда он производится четырехбитными блоками, иначе полученная особь может не являться маршрутом.
Если проигнорировать битовое представление и присвоить городам обычные порядковые номера 1, 2,..., 9, то путь между этими
городами будет представлять собой некоторую последовательность
девяти цифр. В этом случае мутация как случайный обмен двух городов в маршруте будет допустимой операцией, но скрещивание попрежнему окажется бесполезным. Обмен фрагментов маршрута на
другие фрагменты того же пути либо любой оператор, меняющий
местами номера городов маршрута без удаления, добавления или
дублирования городов, окажется достаточно эффективным. Однако при таких подходах невозможно обеспечить сочетание лучших
родительских свойств в потомке, так как его требуется формировать на основе двух родителей.
95
Некоторые исследователи разработали операторы скрещивания,
устраняющие эти проблемы и позволяющие работать с упорядоченным списком посещаемых городов, например оператор упорядоченного скрещивания (order crossover). В нем потомок строится путем
выбора подпоследовательности городов в пути одного из родителей,
причем сохраняется относительный порядок городов другого родителя.
Сначала выбираются две точки сечения, обозначенные символом |, которые случайным образом устанавливаются в одних и тех
же позициях каждого из родителей. Например, если для двух родителей p1 и р2 точки сечения располагаются после 3-го и 7-го городов:
р1=(192|4657|83), р2=(459| 1876|23), то два потомка с1 и с2 получаются следующим образом. Сначала для каждого из потомков копируются фрагменты строк родителей, расположенные между точками
сечения: с1=(ххх|4657|хх), с2=(ХХХ| 1876| хх). Затем после второй
точки сечения одного из родителей помещаются города, соответствующие другому родителю, с сохранением порядка их следования,
при этом уже имеющиеся города пропускаются. При достижении
конца строки операция продолжается сначала. Так, последовательность подстановки городов из р2 имеет вид 234591876. Поскольку
города 4, 6, 5 и 7 не учитываются, так как они уже входят в состав
первого потомка, получается укороченный ряд 23918, который и
подставляется в cl с сохранением порядка следования этих городов в р2: с1=(239|4657|18). Аналогично получается второй потомок
с2=(392|1876|45).
Алгоритм упорядоченного скрещивания гарантирует однократное посещение всех городов, так как фрагменты пути передаются
от одного родителя р1 потомку cl, при этом порядок посещения городов наследуется и от другого родителя р2. Такой подход основан
на интуитивном предположении о том, что порядок обхода городов
играет важную роль в поиске кратчайшего пути, поэтому информация о порядке следования сохраняется для потомков.
Операция мутации в данном случае сводится к перемене мест
двух городов в рамках одного маршрута, что вполне допустимо.
Такой оператор мутации можно применять и для фрагмента пути,
например, выбрав фрагмент трех городов и поместив его в новое
случайно выбранное положение.
Инвертирование фрагмента маршрута тоже может дать хороший
результат. Например, путь с1=(239|4657|18) после инвертирования
его средней части примет вид с1=(239|7564|18).
96
6.3. Проблемы реализации генетических алгоритмов
Приведенные примеры демонстрируют характерные для генетических алгоритмов проблемы, связанные с представлением
данных, определением операторов и выбором критерия качества.
Представление данных должно соответствовать используемым генетическим операторам. Если, как в КНФ-задаче, используется
битовое представление, то для получения новых особей популяции
наиболее эффективны такие традиционные генетические операторы, как скрещивание и мутация. В задаче коммивояжера битовое
представление данных не подходит, а при определении операторов
мутации и скрещивания для каждого потомка необходимо отслеживать присутствие в маршруте всех городов при однократном посещении каждого из них.
Еще одна проблема реализации генетических операторов состоит в том, что существенная информация должна передаваться
следующему поколению особей. Если эта информация, как в КНФзадаче, связана со значением истинности, то в результате выполнения генетических операторов это свойство должно сохраняться
в следующем поколении. В задаче коммивояжера критичной является последовательность городов в маршруте, поэтому потомкам
должны передаваться фрагменты этой информации. Для обеспечения такого наследования свойств необходимо соответствующим
образом выбрать способ представления данных и генетические операторы в каждой конкретной задаче.
«Хороший» способ представления данных во многом определяет эффективность генетического алгоритма. Пусть необходимо из
множества цифр выделять цифры 6, 7, 8 и 9. Естественным представлением, обеспечивающим сортировку данных, является обычное целочисленное описание, поскольку среди десяти цифр каждая
следующая на 1 больше предыдущей, но при переходе к двоичному
описанию эта естественность исчезает. Из битового представления
цифр 6, 7, 8 и 9 (0110 0111 1000 1001) видно, что 6 и 7, а также 8
и 9 отличаются друг от друга на один бит, но 7 и 8 не имеют между
собой ничего общего. Такое представление данных может вызвать
большие проблемы при решении задач, требующих систематизации образов. Использование кодов Грея, в которых каждое число
отличается от своих соседей ровно на один бит, позволяет сделать
переходы между состояниями при реализации генетических операторов более естественными и гладкими.
Важным источником эффективности генетических алгоритмов является неявный параллелизм эволюционных операторов.
97
В отличие от поиска в пространстве состояний, в данном случае
операции на каждом шаге развития популяции выполняются параллельно для всех особей. Ограничивая репродуктивные свойства
слабых особей, генетические алгоритмы приводят к исключению
не только данной особи, но и всех ее потомков. Например, если
строка 101#0##1 отброшена в процессе работы алгоритма, то она
уже не сможет породить строки вида 101#. Вероятностный характер процесса исключения особей из популяции оставляет даже плохим особям шанс оставаться в популяции и вносить свой вклад в
формирование последующих поколений.
Работу генетического алгоритма можно представить как процесс поиска решения, при котором множество особей (решенийкандидатов) сходится к точкам экстремума в пространстве поиска. На рис. 22 горизонтальная ось представляет возможные точки
в пространстве решений, а по вертикали показано качество этих
решений. Точки на кривой – это члены текущей популяции решений-кандидатов, полученные при работе генетического алгоритма.
Изначально решения равномерно распределялись в пространстве
поиска (рис. 22, а). После нескольких итераций они группируются
в областях, соответствующих наиболее высокому качеству решения (рис. 22, б).
Представление генетического алгоритма как алгоритма поиска
экстремума неявно предполагает перемещение по поверхности, определяемой критерием качества, на которой существуют локальные максимумы и минимумы. Неэффективный выбор представления и генетических операторов для конкретной задачи приводит
к нарушению непрерывности этой поверхности, что существенно
усложнит работу алгоритма.
Качество
а) решения
Пространство поиска
Качество
б) решения
Пространство поиска
Рис. 22.Генетический алгоритм как параллельный поиск экстремума:
а – исходное пространство поиска; б – пространство поиска после n поколений
98
В работе Холланда, опубликованной в 1975 году, вводится понятие схемы как общего шаблона и строительного блока особи.
Схема – это шаблон битовых строк, описываемый символами 1,
0 и #. Например, схема 10##01 представляет семейство шестибитовых строк, начинающихся с фрагмента 10 и завершающихся
символами 01. Поскольку центральный фрагмент ## описывает
четыре возможные комбинации битов: 00, 01, 10, 11, то вся схема
представляет четыре битовые строки, состоящие из 1 и 0. Традиционно считается, что каждая схема описывает гиперплоскость.
В этом примере данная гиперплоскость пересекает множество всех
возможных шестибитовых представлений. Центральным моментом традиционной теории генетических алгоритмов является утверждение, что подобные схемы являются строительными блоками
семейств особей. Генетические операторы скрещивания и мутации
оперируют такими схемами в процессе создания новых особей. По
Холланду, для повышения производительности в некоторой среде
адаптивная система должна идентифицировать, проверить и реализовать некоторые структурные свойства, формализуемые с помощью схем.
Анализ схем Холланда предполагает, что алгоритм выбора по
критерию качества сводится к поиску подмножеств в пространстве
поиска, наилучшим образом удовлетворяющих данному критерию. Следовательно, эти подмножества описываются схемами, для
которых значение критерия качества выше среднего. При выполнении генетических операторов скрещивания строительные блоки
с высоким показателем качества складываются вместе и формируют «улучшенные» строки. Мутации позволяют гарантировать, что
генетические особенности не будут утеряны в процессе поиска, т. е.
эти операторы обеспечивают переход к новым областям поверхности поиска. Таким образом, генетические алгоритмы можно рассматривать как некое обобщение процесса поиска с сохранением
важных генетических свойств. Холланд изначально анализировал
генетические алгоритмы на битовом уровне. Более современные
работы распространяют результаты этого анализа на другие схемы
представления.
Существенным отличием генетических алгоритмов от эвристического поиска в пространстве состояний является отсутствие
необходимости анализа степени соответствия текущего и целевого состояний. Такая информация учитывается в алгоритмах, требующих оценки «усилий» для перехода из текущего состояния в
целевое, а при работе генетических алгоритмов каждое поколение
особей оценивается критерием качества. Не требуется и строгая
99
систематизация последующих состояний, как при поиске в пространстве состояний, так как генетические операторы на каждом
шаге формируют поколение особей, каждая из которых может внести свой вклад в получение новых возможных решений.
Расширение области применения генетических алгоритмов для
решения прикладных задач и математического моделирования повышает интерес к осмыслению их теоретических основ, требующих
ответа на следующие вопросы.
• Можно ли охарактеризовать типы задач, для которых генетические алгоритмы работают наиболее эффективно?
• Для каких типов задач они работают плохо?
• Что означает высокая и низкая эффективность генетического
алгоритма для решения некоторого типа задач?
• Существуют ли законы, описывающие поведение генетических алгоритмов на макроуровне, например, можно ли спрогнозировать изменения значений критерия качества для элементов популяции?
• Существует ли способ описать результаты таких различных
генетических операторов, как скрещивание, мутация, инвертирование и т. д.?
• При каких условиях (для каких задач и генетических операторов) генетические алгоритмы работают лучше, чем традиционные
методы поиска?
В теоретическом осмыслении генетических алгоритмов пока
еще больше открытых вопросов, чем приемлемых ответов. Тем не
менее, с момента появления генетических алгоритмов исследователи пытаются сформулировать общие принципы их работы.
100
Контрольные вопросы
Введение.
1. Что представляет собой тест Тьюринга?
2. Сравните различные определения интеллектуальных систем.
3. Какие проблемы необходимо решить при разработке системы
ИИ?
4. Перечислите основные области применения интеллектуальных систем.
Раздел 1.
1. В чем значение гипотезы о физической символьной системе?
2. Как производится интерпретация набора высказываний?
3. Дайте определение предиката.
4. В чем преимущества исчисления предикатов перед исчислением высказываний?
5. Приведите примеры оценивания функций.
6. Что показывают кванторы существования и всеобщности?
7. В чем заключается правило отделения?
8. Приведите пример применения правила инстанцирования.
9. Что такое абдуктивное рассуждение?
10. В чем состоят трудности применения высказывания предикатов в интеллектуальных системах?
11. Какой язык программирования основан на исчислении предикатов первого порядка?
12. В каком порядке происходит поиск предикатов в базе данных языка PROLOG?
Раздел 2.
1. Какое решение задачи о кенигсбергских мостах предложил
Эйлер?
2. Приведите определения понятий «граф», «ориентированный
граф», «корневой граф», «путь», «дерево».
3. Как пространство состояний представляется в виде графа?
4. Приведите примеры задания цели.
5. В чем заключается алгоритм поиска с возвратами?
6. Получение какого результата гарантируется при поиске в ширину?
7. Приведите пример рекурсивного алгоритма.
8. Почему при поиске решения на графе состояний необходимо
применять эвристические методы?
9. Приведите пример работы «жадного» алгоритма.
10. В чем преимущество минимаксного алгоритма по сравнению
с «жадным»?
101
11. Поясните основную идею алгоритма альфа-бета-усечения.
12. Что является основным синтаксическим элементом языка
LISP?
13. Как в языке LISP задаются новые функции?
14. С помощью какой функции производится управление процессом ветвления?
15. Приведите пример представления дерева состояний в виде
списка.
Раздел 3.
1. Какой смысл вкладывается в понятие «распознавание»?
2. На каком разделе математики в основном базируются методы
классификации объектов?
3. Приведите классификацию признаков.
4. Что означает термин «кластеризация образов»?
5. Какие меры близости используются при распознавании?
6. Когда можно использовать расстояние Махаланобиса?
7. Где используется платежная матрица?
8. Как определяется степень близости двух множеств в метрике
Хаусдорфа?
9. В чем разница между алгоритмами кластеризации слиянием
и по k средним?
10. Какая метрика применяется при кластеризации методом
цепной развертки?
11. Поясните работу алгоритма кластеризации с фиксированным порогом.
12. Какие связи существуют между способом описания класса и
видом его признаков?
13. Как производится разбиение пространства признаков на области, соответствующие классам?
14. Как решается проблема выбора последовательности определения признаков?
15. Приведите пример вычисления информативности признаков
по энтропии?
Раздел 4.
1. Дайте определение понятию «обучение».
2. В чем состоят отличия методов обучения с учителем и без учителя?
3. Поясните принцип работы алгоритма с подкреплением.
4. Приведите пример алгоритма определения ценности состояния.
102
Раздел 5.
1. Сравните структуры биологического и искусственного нейронов.
2. Какие функции используются для определения уровня возбуждения нейрона?
3. Опишите нейронную сеть МакКаллока – Питтса?
4. В чем основной недостаток персептрона?
5. Как устроены многослойные сети, в чем сложность их настройки?
6. Опишите алгоритм обратного распространения.
7. Из каких слоев состоит сеть обратного распространения?
8. Как производится настройка нейронов слоя Кохонена?
9. Перечислите методы первоначальной установки весов слоя
Кохонена?
10. Приведите пример настройки сети для хранения информации.
11. Какие нейрокомпьютеры Вам известны?
12. В каких областях применение нейронных сетей наиболее
перспективно?
Раздел 6.
1. Сформулируйте принцип работы генетического алгоритма.
2. Какая последовательность операций выполняется на каждом
шаге генетического алгоритма?
3. Какие проблемы необходимо решить при создании генетического алгоритма?
4. Опишите способ битового представления данных.
5. Перечислите и опишите принцип действия генетических операторов.
6. Приведите пример КНФ-представления данных.
7. Какие проблемы возникают при решении «задачи коммивояжера» генетическим алгоритмом? Как они решаются?
8. Опишите генетический алгоритм как параллельный поиск
экстремума.
9. В чем состоят преимущества и недостатки генетических алгоритмов?
10. Какие вопросы в теории генетических алгоритмов еще требуют ответа?
103
Список литературы
1. Люгер Д. Ф. Искусственный интеллект: стратегии и методы решения сложных проблем: пер. с англ. / Д. Ф. Люггер. М.: Вильямс,
2003. 864 с.
2. Ту Д. Принципы распознавания образов: пер. с англ. / Д. Ту,
Р. Гонсалес. М.: Мир, 1978. 411 с.
3. Марр Д. Зрение: Информационный подход к изучению представления и обработки зрительных образов: пер. с англ. / Д. Марр.
М.: Радио и связь, 1987. 400 с.
4. Искусственный интеллект: справочник / под ред. Э. В. Попова. М.: Радио и связь, 1990. 464 с.
5. Братко И. Программирование на языке Пролог для искусственного интеллекта: пер. с англ. / И. Братко. М.: Мир, 1990. 560 с.
6. Тей А. Логический подход к искусственному интеллекту: пер.
с франц. / А. Тей, П. Грибомон, Ж. Луи и др. М.: Мир, 1990. 432 с.
7. Левин Р. Практическое введение в технологию искусственного
интеллекта и экспертных систем: пер. с англ. / Р. Левин, Д. Ранг,
Б. Эделсон. М.: Финансы и статистика, 1990. 239 с.
8. Джексон П. Введение в экспертные системы: пер. с англ. /
П. Джексон. М.: Вильямс, 2001. 624 с.
9. Кухарев Г. А. Биометрические системы: методы и средства
идентификации личности человека / Г. А. Кухарев. СПб.: Политехника, 2001. 240 с.
10. Форсайт Д. Компьютерное зрение: современный подход: пер.
с англ. / Д. Форсайт, Ж. Понс. М.: Вильямс, 2004. 928 с.
11. Гонсалес Р. Цифровая обработка изображений: пер. с англ. /
Р. Гонсалес, Р. Вудс. М.: Техносфера, 2005. 1072 с.
12. Калан Р. Основные концепции нейронных сетей: пер.
с англ. / Р. Калан. М.: Вильямс, 2001. 470 с.
13. Хайкин С. Нейронные сети: пер. с англ. / С. Хайкин. М.: Вильямс, 2006. 1104 с.
14. Искусственный интеллект: теория и практика. http//www.
iskint.ru
15. Институт систем информатики им. А. П. Ершова СО РАН.
http//www.iis.nsk.su
16. Все об экспертных системах. http//www.expertsys.ru
104
Документ
Категория
Без категории
Просмотров
12
Размер файла
1 434 Кб
Теги
soloveva
1/--страниц
Пожаловаться на содержимое документа