Часть 9.

общений, изложенный в [Pearl, 1988], или метод триангуляции клик, предложенный в [Lauritzen и Spiegelhalter, 1988].

Создайте граф байесовской сети доверия для новой области применения (например,

медицинской диагностики, геологоразведки или анализа автомобильных неисправностей). Обратитесь к примерам d-отделения и создайте дерево клик для этой сети.

Создайте дерево клик и объединенное дерево для ситуации, показанной на рис. 8.20.

Ограбление, вандализм и землетрясение - все это может вызвать тревогу в доме.

Существует также мера потенциальной опасности района, где расположен дом.

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

368 Часть ill. Представление и разум в ракурсе искусственного интеллекта

Часть IV

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

Точность - это не истина... - Генри Матисс (Henri Matisse)

Настоящее и будущее являются настоящим с точки зрения будущего и будущим с

точки зрения прошедшего...

- Т. С. Элиот (Т. S. Eliot)

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

последовательности маленьких действий.

- Кристофер Александер (Christopher Alexander)

Символьное, нейросетевое и эмерджентное обучение

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

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

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

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

Если сети связей построены по принципам нервной системы биологических организмов, то аналогами эмерджентных моделей, рассмотренных в главе 11, являются генетические и эволюционные процессы. Генетические алгоритмы начинают свою работу с целой популяции кандидатов на решение проблемы. Решения оцениваются по некоторому критерию, позволяющему отобрать наилучшие. Комбинация таких претендентов составляет новое поколение возможных решений. Таким образом по принципу Дарвина строится последовательность все более точных решений. Этот подход предполагает поиск источника интеллекта в самом процессе развития, который (хотя некоторые это и оспаривают) стал источником самой жизни.

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

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

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

основанное

на символьном

представлении

информации

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

- Джон Лок (John Locke)

Простое созерцание мира ничего не значит. Созерцание переходит в наблюдение,

наблюдение - в осмысление, осмысление - в установление связей, поэтому можно

сказать, что каждый внимательный взгляд в мир является актом теоретизации.

Однако это надо делать сознательно, с долей самокритики, свободой мышления, не

боясь смелых высказываний и иронии.

- Гете (Goethe)

9.0. Введение

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

Обучение играет важную роль в практических применениях искусственного интеллекта. Фейгенбаум (Feigenbaum) и Мак-Кордак (McCorduck) в 1983 году назвали проблему машинного обучения основным препятствием к широкому распространению ин-

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

Герберт Симон (Herbert Simon) определил обучение следующим образом.

"Обучение - это любое изменение в системе, приводящее к улучшению решения задачи при ее повторном предъявлении или к решению другой задачи на основе тех же данных". [Simon, 1983]

Это краткое определение затрагивает множество вопросов, связанных с разработкой обучаемых программ. Обучение подразумевает обобщение на основе опыта. Производительность системы должна повышаться не только при повторном решении одной и той же задачи, но и при решении аналогичных задач из той же предметной области. Поскольку область определения обучающих данных обычно достаточно широка, то обучаемая система зачастую может обработать не все возможные примеры, и этот ограниченный опыт она должна корректно распространить на недостающие примеры. Такая задача индукции (induction) является центральной для обучения. Для большинства задач имеющихся в наличии данных недостаточно, чтобы гарантировать оптимальное обобщение независимо от типа используемого алгоритма. Обучаемые системы должны обобщать информацию эвристически, т.е. отбирать те аспекты, которые вероятнее всего окажутся полезными в будущем. Такой критерий отбора называется индуктивным порогом (inductive bias).

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

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

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

В главе 11 описывается генетическое (genetic learning), или эволюционное, обучение (evolutionary learning). Естественно, наиболее впечатляющим примером обучаемой системы является организм человека или животного, который эволюционировал вместе с окружающим миром. Этот эмерджентный подход к обучению, основанный на адаптации, отражен в генетических алгоритмах, генетическом программировании и исследовании искусственной жизни.

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

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

В разделе 9.1 рассматриваются различные задачи обучения, но посвящена эта глава в основном индуктивному обучению. Индукция (способность обобщения на основе множества примеров) - одна из наиболее фундаментальных задач обучения. Типичной задачей индуктивного обучения является изучение понятий (concept learning), при котором на основе примеров некоторого понятия выводится его определение, позволяющее в будущем корректно распознавать экземпляры такого понятия, как "кот", "детские заболевания" или "удачное вложение акций". В разделах 9.2 и 9.3 рассмотрены два алгоритма концептуальной индукции: поиск в пространстве версий (version space search) и ID3.

В разделе 9.4 рассматривается роль индуктивного порога в процессе обучения. Пространство поиска в задачах обучения обычно чрезвычайно велико. Эта проблема сложности усугубляется проблемой выбора наилучшего варианта обобщения на основе обучающих данных. Индуктивный порог используется во всех методах для ограничения пространства возможных обобщений. Алгоритмы из разделов 9.2 и 9.3 основаны на данных. Они не используют априорных знаний об изучаемой предметной области, а определяют главные свойства общего понятия на основе большого количества примеров. Алгоритмы, выполняющие обобщение на базе обучающих данных, называются алгоритмами обучения на основе подобия (similarity-based learning). В отличие от таких методов, человек в процессе обучения может использовать априорные знания о предметной области. Например, для эффективного обучения человеку не требуется большого количества примеров. Зачастую одного примера, аналогии или пространного намека вполне достаточно для формирования общего понятия. Эффективное использование таких знаний повышает результативность обучения и снижает вероятность ошибок. В разделе 9.5 рассматривается обучение на основе объяснения (explanation-based learning), обучение по аналогии и другие приемы, использующие априорные знания для обучения с помощью ограниченного числа примеров.

Алгоритмы, представленные в разделах 9.2-9.5, отличаются друг от друга стратегиями поиска, языками представления и объемом используемых априорных знаний. Однако все они предполагают, что обучающие данные классифицированы. Обучаемой системе сообщается, к какому классу относится данный пример. Такой подход, предполагающий наличие информации о классификации обучающих данных, называется обучением с учителем (supervised learning).

В разделе 9.6 продолжается изучение индуктивных методов обучения. Здесь рассматривается обучение без учителя (unsupervised learning), предполагающее извлечение полезной информации интеллектуальным агентом при отсутствии корректно классифицированных обучающих данных. Основной проблемой обучения без учителя является формирование категорий (category formation), или концептуальная кластеризация (conceptual clustering). Как интеллектуальный агент должен разделить объекты на полезные категории? Как вообще определить, полезна ли эта категория? В этом разделе будут рассмотрены два алгоритма формирования категорий- CLUSTER/2 и СОВ-WEB. И, наконец, в разделе 9.7 представлено обучение с подкреплением (reinforcement learning), при котором агент помещается в среду и получает от нее отклик. Процесс обучения предполагает активную деятельность агента и интерпретацию обратной связи, полученной в ответ на его действия. Обучение с подкреплением отличается от обучения с учите-

Глава 9. Машинное обучение, основанное на символьном представлении... 373

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

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

9.1. Символьное обучение

Алгоритмы обучения можно охарактеризовать с нескольких точек зрения (рис. 9.1).

1. Данные и цели задачи обучения. Одной из основных характеристик обучения является его цель и имеющиеся данные. Например, алгоритмы изучения понятий, описанные в разделах 9.2 и 9.3, начинают свою работу с набора положительных (и зачастую отрицательных) примеров целевого класса. Обучение должно сформировать общее определение, позволяющее в дальнейшем распознавать экземпляры этого класса. В отличие от обучения, основанного на данных, обучение на основе объяснения (раздел 9.5) предполагает извлечение общего знания из каждого обучающего примера и наличие исходной базы знаний о конкретной области определения. Алгоритмы концептуальной кластеризации, описанные в разделе 9.6, иллюстрируют еще один вариант проблемы индукции. Они начинают свою работу с набора неклассифицированных экземпляров. Их задачей является категоризация этих данных, имеющая определенный смысл для обучаемой системы.

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

Примеры - не единственный источник данных для обучения. Человек, например, зачастую обучается на основе высокоуровневых рекомендаций. При изучении программирования преподаватель сообщает своим студентам, что в цикле всегда должно достигаться условие завершения. Этот безусловно корректный совет напрямую неприменим. Его необходимо реализовать в виде конкретных правил управления счетчиками циклов или логических условий на языке программирования. Еще одним типом обучающих данных является аналогия (подраздел 9.5.4), которую необходимо корректно интерпретировать до начала использования. Если преподаватель сообщает студентам, что электричество напоминает воду, студенты должны корректно интерпретировать эту аналогию - электричество распространяется по проводам, как жидкость в водопроводе. Как и для потока жидкости можно измерить количество электричества (силу тока) и его давление в потоке (напряжение). Однако, в отличие от воды, электричество не увлажняет вещи и не помогает мыть руки. Интерпретируя аналогию, следует выявить осмысленное сходство и исключить ложные или несущественные детали.

Характеристикой алгоритма обучения также является его цель (target). Цель многих алгоритмов - понятие (concept), или общее описание класса объектов. Алгоритмы обучения также могут использовать планы, эвристики решения проблемы или другие формы процедурного знания.

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

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

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

Size(obj1, small) ? color(obj, red) ? shape(obj1, round) size(obj2, large) ? color(obj2, red) ? shape{obj2, round)

Общее понятие "мяч" можно описать так.

size(X, Y) ? color(X, Z) ? shape(X, round)

Тогда любое выражение, удовлетворяющее этому общему определению, представляет мяч.

Глава 9. Машинное обучение, основанное на символьном представлении... 375

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

size(obj1, small) ? color(obj1, red) ? shape(obj1, round)

Если заменить одну константу переменной, получим следующее обобщение.

size(obj1, X) ? color(obj1, red) ? shape(obj1, round) size(obj1, small) ? color(obj1, X) ? shape(obj1, round) size(obj1, small) ? color(obj1, red) ? shape(obj1, X) size(X, small) ? color(X, red) ? shape(X, round)

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

Эвристический поиск. Обучаемые программы должны учитывать направление и

порядок поиска, а также для повышения эффективности поиска использовать

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

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

Size(obj1, small) ? color(obj1, red) ? shape(obj1, round),

обучаемая система выберет его в качестве кандидата на определение понятия. Этот

пример корректно описывает лишь один экземпляр.

Если алгоритму предъявить второй экземпляр этого понятия

size(obj2, large) ? color(obj2, red) ? shape(obj2, round),

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

Size(X, Y) ? color(X, red) ? shape(X, round)

Этот подход изучения понятий на положительных и отрицательных примерах описан в работе Патрика Винстона [Winston, 1975a]. Его программа строит общие определения таких структурных понятий, как арка, описывая их составные части. Обучающие данные - это последовательность положительных и отрицательных примеров понятия. Это примеры структур, удовлетворяющих определенным условиям или почти удовлетворяющих им. "Почти удовлетворительными" считаются экземпляры, для принадлежности к категории которым не хватает одного свойства или отношения. "Почти удовлетворительные" экземпляры позволяют программе выде-

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

лить свойства, которые можно использовать для исключения отрицательных примеров из целевого понятия. На рис. 9.2 показаны положительные примеры и "почти удовлетворительные" экземпляры понятия "арка".

Программа представляет понятия в виде семантической сети (рис. 9.3). Она обучается, уточняя описание кандидата на роль целевого понятия на основе обучающих данных. Программа Винстона уточняет описание кандидата с помощью обобщения и специализации. Обобщение приводит к такому изменению графа, которое обеспечивает соответствие графу новых экземпляров понятия. На рис. 9.3, а показана арка из трех блоков и представляющий ее граф. В следующем обучающем примере (рис. 9.3, б) перекладиной арки служит пирамида, а не блок. Этот пример не соответствует описанию понятия-кандидата. Программа сопоставляет эти графы, пытаясь определить степень их изоморфизма, с помощью имен узлов. После сопоставления графов программа может выявить различия между ними. На рис. 9.3 графы соответствуют друг другу по всем компонентам за исключением верхнего элемента: в первом графе этому элементу соответствует узел brick (блок), а во втором- узел pyramid (пирамида). На рис. 9.3, в показана иерархия обобщения этих понятий. Программа строит обобщенный граф, заменяя соответствующий узел ближайшим общим супертипом для объектов brick и pyramid. В данном примере это polygon (многогранник). В результате получается понятие, представленное графом на рис. 9.3, г.

Глава 9. Машинное обучение, основанное на символьном представлении... 377

"Почти удовлетворительные" примеры отличаются от целевого понятия одним свойством. Для их исключения программа выполняет специализацию описания кандидатов. На рис. 9.4, а представлено описание понятия-кандидата. Оно отличается от "почти удовлетворительного" примера на рис. 9.4, б отношением touch (касается) в последнем описании. Программа строит специализацию графа, добавляя связь must-not-touch (не должно касаться) (рис. 9.4, в). Заметим, что этот алгоритм существенно зависит от близости отрицательных примеров целевому понятию. Определяя единственное отличительное свойство, алгоритм уточняет понятие-кандидат.

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

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

379

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

9.2. Поиск в пространстве версий

Поиск в пространстве версий (version space search) [Mitchell 1978, 1982] иллюстрирует индуктивное обучение как реализацию поиска в пространстве понятий. Поиск в пространстве версий основан на том, что операция обобщения упорядочивает понятия в пространстве поиска. Затем этот порядок используется для выбора направления поиска.

9.2.1. Операция обобщения и пространство понятий

Обобщение и специализация- самые типичные операции при определении пространства понятий. К основным операциям обобщения, применяемым в машинном обучении, относятся следующие.

1. Замена конкретных значений переменными. Например,

color(ball, red)

приводится к виду color(X, red).

2. Исключение условий из конъюнктивных выражений. Так,

shape(X, round) ? size(X, small) ? color(X, red)

сводится к выражению

shape(X, round) ? color(x, red).

3. Добавление в выражение операции дизъюнкции. Например,

shape(X, round) ? size(X, small) ? color(X, red)

приводится к

shape(X, round) ? size(X, small) ? color(X, red) v color(X, blue)).

4. Замена свойства родительским объектом согласно иерархии классов. Если объект

primary_color (основной цвет) является суперклассом для свойства red (красный), то

color(X, red)

заменяется на color(X, primary_color).

Операцию обобщения можно описать в терминах теории множеств. Пусть Р и О - множества предложений, удовлетворяющих выражениям р и q из теории предикатов соответственно. Выражение р является более общим, чем q, если P?Q. В приведенных выше примерах множество предложений, удовлетворяющих выражению color(X, red), включает набор элементов, удовлетворяющих выражению color(ball, red). Аналогично

380

в примере 2 множество круглых и красных объектов является более общим, чем множество маленьких красных и круглых объектов. Заметим, что отношение "более общий" позволяет упорядочить логические предложения в соответствующем пространстве. Это отношение можно обозначить символом ">", т.е. p>q означает, что выражение р является более общим, чем q. Такая систематизация существенно сужает направление поиска, выполняемого алгоритмом обучения.

Это отношение можно описать в терминах покрытия (covering). Если понятие р является более общим, чем понятие q, то говорят, что р покрывает q. Отношение покрытия определяется следующим образом. Пусть р(х) и q(x) - описания, представляющие собой положительные примеры понятия. Другими словами, для объекта х p(x)?positive(x) и q(x)?positive(x). Говорят, что р покрывает q, если q(x)?positive(x) является логическим следствием p(x)?positive(x).

Например, color{X, У) покрывает color{ball, Z), которое, в свою очередь, покрывает color{ball, red). В качестве простого примера рассмотрим множество объектов со следующими свойствами.

Sizes = {large, small) Colors = {red, white, blue} Shapes = {ball, brick, cube}

Sizes = {large, small} Colors = {red, white, blue} Shapes = {ball, brick, cube}

Эти объекты можно представить с помощью предиката obj(Sizes, Colors, Shapes). Операция обобщения, осуществляемая путем замены конкретных значений переменными, определяет пространство, представленное на рис. 9.5. Индуктивное обучение можно рассматривать как поиск в этом пространстве понятия, удовлетворяющего всем обучающим примерам.

9.2.2. Алгоритм исключения кандидата

В этом разделе представлены три алгоритма [Mitchell, 1982] поиска в пространстве понятий. Эти алгоритмы основываются на понятии пространства версий (version space), представляющем собой множество всех описаний понятия, согласующихся с обучающими примерами. Эти алгоритмы работают за счет сужения пространства версий с появлением новых примеров. Первые два алгоритма обеспечивают сужение пространства версий в направлении от частного к общему и от общего к частному соответственно. Третий алгоритм, называемый алгоритмом исключения кандидата (candidate elimination), объединяет оба подхода и реализует двунаправленный поиск.

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

Как и программа Винстона, реализующая обучение на основе структурных описаний, алгоритмы поиска в пространстве версий используют и положительные, и отрицательные примеры целевого понятия. Хотя операцию обобщения можно реализовать только на положительных примерах, отрицательные примеры позволяют предотвратить излишнее обобщение. Изученное понятие должно быть не только общим, чтобы соответствовать всем положительным примерам, но и частным, чтобы исключить все отрицательные. В пространстве, представленном на рис. 9.5, все множество положительных экземпляров покрывается понятием obj(X, Y, Z).

Глава 9. Машинное обучение, основанное на символьном представлении... 381

Рис. 9.5. Пространство понятий

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

Begin

Инициализировать S первым положительным обучающим примером;

N - множество всех отрицательных примеров.

Для каждого положительного примера р, Begin

Для каждого s, принадлежащего S, не удовлетворяющего примеру р, заменить S минимальным более общим понятием, удовлетворяющим примеру р; Удалить из S все гипотезы, более общие, чем некоторые

другие гипотезы из S; Удалить из S все гипотезы, удовлетворяющие рассмотренному

ранее отрицательному примеру из N; End;

Для каждого отрицательного примера n Begin

Удалить все экземпляры S, удовлетворяющие n; Добавить n в множество N для проверки последующих

гипотез на предмет излишнего обобщения; End; End

382

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

В алгоритме поиска от частного к общему используется множество гипотез S, элементами которого являются кандидаты на определение понятия. Чтобы избежать излишнего обобщения, эти определения-кандидаты формируются как максимально конкретные обобщения (maximally specific generalization) исходных обучающих данных. Понятие с является максимально конкретным, если оно покрывает все положительные примеры, не удовлетворяет ни одному отрицательному, и для любого другого понятия c' покрывающего все положительные примеры, с' ? с. На рис. 9.7 представлен пример применения этого алгоритма к пространству версий из рис. 9.5. В подразделе 14.8.1 алгоритм поиска в пространстве версий от частного к общему реализован на языке PROLOG.

Рис. 9.7. Поиск от частного к общему в пространстве версий при изучении понятия "ball"

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

Глава 9. Машинное обучение, основанное на символьном представлении...

383

Begin

Инициализировать G наиболее общим понятием в пространстве;

Р содержит все положительные примеры

Для каждого отрицательного примера n Begin Для каждого g, принадлежащего G, удовлетворяющего примеру n, заменить

g его наиболее общей специализацией,

не удовлетворяющей примеру n; Удалить из G все гипотезы, более частные, чем некоторые

другие гипотезы из G; Удалить из G все гипотезы, не удовлетворяющие

некоторым примерам из Р; End;

Для каждого положительного примера р

Begin

Удалить из G все гипотезы, не удовлетворяющие р;

Добавить р в множество Р;

End; End

Рис. 9.8. Поиск от общего к частному в пространстве версий при изучении понятия «ball»

На рис. 9.8 показан пример применения этого алгоритма к пространству версий из рис. 9.5. В этом примере алгоритм использует базовые знания о том, что свойство size (размер) может принимать значения {large, small}, свойство color (цвет) - значения {red, white, blue}, а свойство shape (форма)- {ball, brick, cube}. Эти знания играют важную роль при формировании понятий путем замены конкретных значений переменными.

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

Алгоритм исключения кандидата объединяет оба подхода и обеспечивает двунаправленный поиск, который дает множество преимуществ для обучаемой системы. Алгоритм поддерживает два множества понятий-кандидатов: G - множество максимально общих понятий-кандидатов, a S - множество максимально конкретных. В процессе работы алгоритма специализация множества G и обобщение множества S выполняется до тех пор, пока они не сойдутся к целевому понятию. Алгоритм имеет следующий вид.

Begin

Инициализировать G наиболее общим понятием в пространстве;

Инициализировать S первым положительным обучающим примером;

Для каждого положительного примера р Begin

Удалить все элементы G, не удовлетворяющие примеру р; Для каждого s принадлежащего S, не удовлетворяющего примеру р, заменить

S наиболее частным обобщением,

удовлетворяющим примеру р; Удалить из S все гипотезы, более общие, чем некоторые

другие гипотезы из S; Удалить из S все гипотезы, более общие, чем некоторые

гипотезы из G; End;

Для каждого нового отрицательного примера n Begin

Удалить все элементы S, удовлетворяющие n. Для каждого g принадлежащего G, удовлетворяющего примеру n, заменить

g его наиболее общей специализацией,

не удовлетворяющей примеру n; Удалить из G все гипотезы, более частные, чем некоторые

другие гипотезы из G; Удалить из G все гипотезы, более частные, чем

некоторые гипотезы из S; End;

Если G=S и оба множества содержат по одному элементу,

значит, найдено единственное понятие, удовлетворяющее

всем данным; Если G и S пусты, значит, не существует понятия, покрывающего

все положительные примеры и не удовлетворяющего

отрицательным; End

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

Глава 9. Машинное обучение, основанное на символьном представлении... 385

Рис. 9.9. Изучение понятия "red ball" с помощью алгоритма исключения кандидата

Объединение двух направлений поиска в одном алгоритме обеспечивает несколько преимуществ. Множества G и S содержат обобщенную информацию об отрицательных и положительных примерах соответственно, что устраняет необходимость хранения этих примеров. Например, после обобщения множества S с целью покрытия очередного положительного примера множество G используется для исключения из S понятий, покрывающих отрицательные примеры. Поскольку G - это множество максимально общих понятий, не удовлетворяющих ни одному из отрицательных примеров, то элемент множества S, более общий, чем любой элемент из G, должен удовлетворять некоторым отрицательным примерам. Аналогично, поскольку S - это множество максимально конкретных обобщений, покрывающих все положительные примеры, то любой новый элемент G, более частный, чем элемент S, не покрывает некоторые положительные экземпляры, и его необходимо исключить.

На рис. 9.10 показано абстрактное представление алгоритма исключения кандидата. Символом "+" обозначены положительные обучающие примеры, а символом "-" - отрицательные. Во внутреннем круге заключены все известные положительные примеры, покрываемые понятиями S. Внешний круг соответствует множеству G; любые примеры за его пределами являются отрицательными. Затененная часть изображения содержит целевое понятие, а также другие его определения, которые могут оказаться либо слишком общими либо слишком частными (отмечены символом "?"). В процессе работы алгоритма внешняя окружность "сжимается", чтобы исключить отрицательные экземпляры386

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

а внутренняя - "расширяется" для включения новых положительных примеров. В итоге оба процесса сходятся к единому целевому понятию. Алгоритм исключения кандидата позволяет определить, когда найдено единственно возможное описание целевого понятия. Если множества S и G содержат одно и то же понятие, значит, алгоритм завершился успешно. Если G и S пусты, значит, не существует понятия, удовлетворяющего всем положительным примерам и ни одному отрицательному. Это может произойти в случае противоречивости данных или при условии неудачного выбора языка представления (подраздел 9.2.4).

Рис. 9.10. Изменение множеств G и S в процессе работы алгоритма исключения кандидата

Интересным свойством алгоритма исключения кандидата является его инкрементальность. Инкрементальные алгоритмы обучения предполагают поочередную обработку обучающих примеров и формирование удовлетворительного, хотя, возможно, и неполного, обобщения после предъявления каждого из экземпляров. В отличие от них алгоритмы пакетной обработки (например, ЮЗ из раздела 9.3) требуют наличия всех обучающих примеров до начала обучения. Множества G и S в процессе работы алгоритма исключения кандидата сужают множество потенциальных понятий: если с - целевое понятие, то для всех geG и seS g>c>s. Любое понятие, более общее, чем некоторое понятие из G, будет покрывать отрицательные примеры; любое понятие, более частное, чем некоторое понятие из S, не покрывает некоторые положительные примеры. Это означает, что множества G и S охватывают набор приемлемых понятий.

В следующем разделе эти рассуждения будут проиллюстрированы на примере программы, использующей метод исключения кандидата для изучения эвристик поиска. Программа LEX [Mitchell и др., 1983] обучается эвристикам для решения задач символьного интегрирования. Эта программа не только демонстрирует использование множеств G и S для определения частных понятий, но и иллюстрирует такие вопросы, как сложность задач многошагового обучения и взаимоотношения между компонентами обучения и решения проблемы в сложной системе.

Глава 9. Машинное обучение, основанное на символьном представлении...

387

9.2.3. Программа LEX: индуктивное изучение эвристик поиска

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

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

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

Если состояние текущей задачи удовлетворяет условию Р, значит, нужно применить операцию О с ограничением В.

Например, типичной эвристикой для программы LEX является следующая.

Если состояние текущей задачи удовлетворяет условию

значит, нужно применить операцию ОР2 с обозначениями

Здесь эвристика предполагает интегрирование по частям для вычисления интеграла от произведения х и некоторой трансцендентной (т.е. тригонометрической) функции от x.

Язык представления понятий в программе LEX состоит из символов, изображенных на рис. 9.11. Заметим, что эти символы представлены в виде иерархии обобщения, где каждый символ соответствует всем своим потомкам в этой иерархии. Обобщение выражений выполняется путем замены символа его предшественником в иерархии обобщения.

Программа LEX может изменить обозначение cos на trig. Тогда выражение примет вид

Например, рассмотрим выражение

Кроме того, можно заменить число 3 символом к, представляющим любое целое число

На рис. 9.12 представлено пространство версий для ОР2, определенное этими обобщениями.

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

Глава 9. Машинное обучение, основанное на символьном представлении... 389

Программа LEX состоит из 4 компонентов.

1.Компонент обобщения, использующий для поиска эвристик метод исключения кандидата.

Компонент решения задачи, вычисляющий решение.

Компонент критики, извлекающий положительные и отрицательные примеры в

процессе решения задачи.

Генератор задач, формирующий новые задачи-кандидаты.

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

Модуль решения задачи строит дерево поиска при решении задачи интегрирования. В программе процессорное время, отводимое на решение задачи, ограничено. При этом для решения задачи используется алгоритм поиска по первому наилучшему совпадению со специально разработанными эвристиками. Интересно, что в качестве частных определений эвристики в программе LEX используются множества G и S. Если для данного состояния можно применить несколько операций, выбирается та, которая больше всего соответствует этому состоянию. Степень соответствия определяется как процентное соотношение всех понятий, расположенных в пределах G и S, удовлетворяющих текущему состоянию. Поскольку вычислительные затраты на проверку всех понятий-кандидатов могут оказаться значительными, степень соответствия в программе определяется через процентное соотношение элементов G и S, удовлетворяющих данному состоянию. Заметим, что с уточнением эвристик производительность системы LEX значительно повышается.

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

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

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

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

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

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

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

9.2.4. Обсуждение алгоритма исключения кандидата

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

Обучение на основе поиска, подобно другим задачам поиска, связано с операциями в некоторых пространствах. Поскольку алгоритм исключения кандидата реализует поиск в ширину, он может оказаться неэффективным. Если специфика задачи такова, что множества G и S интенсивно увеличиваются, возможно, следует выработать эвристики для исключения состояний из этих множеств на основе лучевого поиска (beam search) (см. главу 4).

Еще один подход к решению этой проблемы, описанный в разделе 9.4, предполагает использование индуктивного порога для дальнейшего уменьшения размера пространства понятий. Такие пороги вносят ограничения в язык представления понятий. В программе LEX порог создан с помощью иерархии обобщения понятий. Язык представления понятий в этой программе достаточно строг, чтобы обеспечить формирование множества эффективных эвристик и уменьшить пространство понятий до "обозримых размеров". Применение порогов позволяет упростить пространство понятий, но может привести к неспособности системы адекватно представить изучаемые понятия. Следовательно, метод исключения кандидата не сойдется к целевому понятию, а множества G и S окажутся пустыми. В этом состоит противоречие между выразительностью и эффективностью обучения.

Глава 9. Машинное обучение, основанное на символьном представлении... 391

Неудачное завершение алгоритма может также быть вызвано шумом или противоречивостью обучающих данных. Задача обучения на зашумленных данных очень важна для реальных приложений, в которых данные могут быть неполными или противоречивыми. Алгоритм исключения кандидата нельзя назвать устойчивым к шуму. Даже один неверно классифицированный обучающий пример может сделать алгоритм расходящимся. Одним из решений этой проблемы является использование нескольких множеств G и S. Помимо пространства версий, полученного для всех обучающих примеров, создаются дополнительные пространства на основе всех примеров за исключением одного, двух экземпляров и т.д. Если алгоритм не сходится для исходных множеств G и S, его проверяют на "усеченных" множествах, в надежде, что они окажутся согласованными. К сожалению, такой подход слишком неэффективен для практического использования.

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

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

9.3. Индуктивный алгоритм построения дерева решений ID3

Алгоритм ID3 [Quinlan, 1986a] подобно методу исключения кандидата обеспечивает изучение понятий на примерах. Особый интерес представляют способ хранения полученных знаний, подход к управлению сложностью, эвристика для выбора понятий-кандидатов и возможности обработки зашумленных данных. В алгоритме ID3 понятия представляются в виде дерева решений (decision tree). Такое представление позволяет классифицировать объект путем проверки значения определенных свойств.

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

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

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

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