Часть 11.

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

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

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

9.5.4. Обоснование по аналогии

Если "чистый" алгоритм EBL обеспечивает лишь дедуктивное обучение, то обоснование по аналогии - это более гибкий метод использования имеющихся знаний. Обоснование по аналогии строится на следующих предпосылках. Если две ситуации сходны в некотором отношении, то весьма вероятно, что они окажутся сходными и в других аспектах. Например, если два дома расположены в одной местности и похожи по архитектуре, то они, скорее всего, имеют одинаковую стоимость. В отличие от доказательств, используемых в алгоритме EBL, метод аналогии не является логически строгим. В этом смысле он подобен индукции. Как замечено в [Russell, 1989] и других работах, аналогия - это вид индукции на основе единственного примера. В примере с домами свойства одного дома прогнозируются на основе информации о втором.

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

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

При участии многочисленных авторов был разработан унифицированный подход к реализации вычислительных моделей обоснования по аналогии [Hall, 1989]; [KedaCabelli, 1988]; [Wolstencroft, 1989]. Обычно этот процесс состоит из следующих этапов.

1. Поиск (retrieval). Зная целевую проблему, необходимо выбрать потенциальный источник аналогии. При этом нужно выделить те свойства цели и источника, которые подтверждают правдоподобие аналогии, а также проиндексировать

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

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

Развитие (уточнение). Обнаружив источник, зачастую следует выделить дополни

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

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

Отображение и логический вывод (mapping and inference). Этот этап предполагает

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

Подтверждение (justification). На этом этапе проверяется корректность отображения. При необходимости его следует модифицировать.

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

Эти этапы реализованы в многочисленных вычислительных моделях обоснования по аналогии. Например, теория структурного отображения (structure mapping theory) [Falkenhainer, 1990], [Falkenhainer и др., 1989], [Gentner, 1983] не только позволяет решить проблему поиска полезных аналогий, но и обеспечивает правдоподобную модель понимания аналогий человеком. Основной вопрос при использовании аналогии заключается в том, как отличить выразительные, глубокие аналогии от поверхностных сравнений. В своей работе Гентнер (Gentner) утверждает, что истинные аналогии должны акцентировать внимание на систематичных, структурных свойствах области определения, а не на малосущественном сходстве. Например, аналогия "атом подобен солнечной системе" глубже, чем "подсолнух напоминает солнце", поскольку первая отражает целую систему взаимосвязей между элементами, движущимися по своим орбитам, а вторая описывает лишь внешнее сходство, состоящее в том, что оба объекта имеют круглую форму и желтый цвет. Это свойство отображения аналогии называется систематичностью (systematicity).

Теория структурного отображения формализует эти рассуждения. Рассмотрим пример аналогии атома и солнечной системы, описанный в [Gentner, 1983] и проиллюстрированный на рис. 9.19. Область определения источника включает предикаты

yellow(sun)

blue(earth)

hotter-than(sun, earth)

causes(more-massive(sun, earth), attract(sun, earth))

causes{attract(sun, earth), revolves-around{earth, sun)).

Область определения цели содержит предикаты

more-massive(nucleus, electron) revolves-around(electron, nucleus).

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

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

Из описания источника исключаются лишние свойства. Поскольку аналогия кон

центрирует внимание на системе отношений, сначала необходимо исключить предикаты, описывающие несущественные свойства источника. В структурном отображении эта процедура формализуется путем исключения из описания источника предикатов с единственным аргументом (унарных предикатов). Это обосновано тем, что предикаты с более высокой арностью, описывающие отношения между несколькими сущностями, содержат систематичную информацию с более высокой степенью вероятности, что и требуется для аналогии. В нашем примере исключаются утверждения, определяющие цвет Солнца и Земли yellow(sun) и blue(earth). Заметим, что в описании источника все еще могут содержаться утверждения, не имеющие значения для аналогии, например, утверждение о том, что Солнце теплее Земли

hotter-than{sun, earth).

Отношения отображаются из описания источника в описание цели без изменений.

Могут отличаться лишь параметры этих отношений. В нашем примере для источника и цели отношения revolves-around (вращается вокруг) и more-massive (более массивный) одинаковы. Такой подход используется во многих теориях построения аналогий. Он позволяет сократить число возможных отображений, а так же согласуется с эвристикой о предпочтениях в отображении.

При построении отображения в качестве его фокуса целесообразно выбирать от

ношения более высокого порядка. В нашем примере отношением более высокого

порядка выступает causes, поскольку его аргументами являются другие отношения. Это называется принципом систематичности (systematicity principle).

1. 414

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

Такие правила приводят к отображению

sun ? nucleus earth ? electron.

Расширяя это отображение, приходим к выражениям

causes{more-massive(nucleus, electron), attract(nucleus, electron)) causes(attract(nucleus, electron), revolves-around(electron, nucleus)).

Теория структурного отображения была реализована и протестирована в различных областях определения. Однако она еще далека от полной теории аналогии, поскольку не позволяет решить такую проблему, как поиск источника аналогии. Она подтверждается вычислительным экспериментом и объясняет многие аспекты обоснования по аналогии, свойственного человеку. И, наконец, в этом разделе уже упоминалось обоснование на основе опыта (case-based reasoning), описанное в разделе 7.3. В этом контексте при создании и применении базы полезного опыта важная роль отводится аналогии.

9.6. Обучение без учителя

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

9.6.1. Научная деятельность и обучение без учителя

Одной из первых и наиболее успешных систем, позволяющих "открывать" новые знания, является программа AM [Davis и Lenat, 1982]; [Lenat и Brown, 1984], которая выводит интересные, а иногда и оригинальные, понятия в математике. Эта программа основывается на теории множеств, операциях по созданию новых знаний путем модификации и комбинирования существующих понятий и наборе эвристик для выявления "интересных" понятий. За счет поиска в пространстве математических понятий программа AM "открыла" натуральные числа и несколько важных понятий теории чисел, например, существование простых чисел.

Так, программа AM "открыла" натуральные числа, модифицируя свое представление о "множествах с повторяющимися элементами". К таким множествам относится, например {а, а, b с, с}. При специализации определения такого множества, в котором содержатся только элементы одного типа, возникла аналогия с натуральными числами. Например, множество с повторяющимися элементами {1, 1, 1, 1} соответствует числу 4. Объединение таких множеств соответствует сложению чисел: {1, 1}U{1, 1} = {1, 1, 1, 1} или 2 + 2 = 4. В процессе дальнейшего изучения этого понятия было обнаружено, что умножение - это последовательность операций сложения. С помощью эвристики определения новых операций путем обращения существующих программа AM

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

"открыла" целочисленное деление. Затем было найдено понятие простого числа, имеющего только два делителя (само число и 1).

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

Несмотря на то что программе AM удалось открыть простые числа и несколько других интересных понятий, она не смогла продвинуться дальше элементарной теории чисел. В [Lenat и Brown, 1984] были проанализированы преимущества программы и ее ограничения. Изначально считалось, что основным преимуществом программы являются ее эвристики, однако впоследствии оказалось, что своим успехом программа обязана языку представления математических понятий. Понятия в ней представлены рекурсивными структурами на языке программирования LISP. Поскольку описание основано на удачно спроектированном языке программирования, в определяемом пространстве плотность интересных понятий очень высока. Особенно это проявляется на ранних этапах поиска. При последующем исследовании понятий пространство расширяется по законам комбинаторики, и "доля" интересных понятий в общем пространстве уменьшается. Это наблюдение еще раз подчеркивает связь между представлением и поиском.

Еще одной причиной, обусловившей невозможность получения дальнейших впечатляющих результатов на основе первых достижений программы AM, является ее неспособность "учиться учиться". В процессе приобретения математических знаний она не выводит новых эвристик. Следовательно, качество поиска снижается с увеличением математической сложности задач. В этом смысле программа никогда не достигнет глубокого понимания математики. Эта проблема впоследствии была решена в программе EVRISKO, которая способна обучиться новым эвристикам [Lenat, 1983].

Проблема автоматического обучения исследовалась во многих программах. В программе IL [Sims, 1987] для "открытия" новых математических понятий использованы различные приемы обучения, в том числе методы автоматического доказательства теорем и обучения на основе объяснения (раздел 9.5). Автоматический вывод целочисленных последовательностей описан также в [Cotton и др., 2000].

В программе BACON [Langley и др., 1987] разработаны и реализованы математические модели формирования количественных научных закономерностей. Например, на основе данных об удаленности планет от Солнца и периоде их вращения по орбитам система BACON повторно "открыла" законы Кеплера о движении планет. С помощью вычислительной модели реализации открытий человека в различных предметных областях, BACON обеспечила полезные средства и методологию исследования процессов научной деятельности человека. В системе SCAVENGER [Stubblefield, 1995], [Stubblefield, 1996] применен вариант алгоритма ШЗ для повышения способности формирования полезных аналогий. В работе [Shrager и Langley, 1990] описано множество других самообучающихся систем.

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

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

блемой обучения без учителя, при решении которой был достигнут серьезный прогресс, является изучение категорий. В [Lakoff, 1987] сделано предположение о том, что категоризация - это основа человеческого познания: высокоуровневые теоретические знания зависят от способности систематизировать конкретный опыт в логически согласованной классификационной иерархии. Большая часть знаний человека относится к категориям объектов, например к лошадям, а не к отдельно взятой конкретной лошади, например, Росинанту или Боливару. В работе [Nordhausen и Langley, 1990] отмечено, что формирование категорий - основа единой теории научных исследований. При исследовании процессов химических реакций ученые основывались на известной классификации соединений по таким категориям, как "кислота" и "щелочь".

В следующем разделе рассматривается концептуальная кластеризация (conceptual clustering) - проблема формирования полезных категорий на основе неклассифицированных данных.

9.6.2. Концептуальная кластеризация

Для решения задачи кластеризации (clustering problem) требуются набор неклассифицированных объектов и средства измерения подобия объектов. Целью кластеризации является организация объектов в классы, удовлетворяющие некоторому стандарту качества, например на основе максимального сходства объектов каждого класса.

Числовая таксономия (numeric taxonomy) - один из первых подходов к решению задач кластеризации. Числовые методы основываются на представлении объектов с помощью набора свойств, каждое из которых может принимать некоторое числовое значение. При наличии корректной метрики подобия каждый объект (вектор из п значений признаков) можно рассматривать как точку в л-мерном пространстве. Мерой сходства двух объектов можно считать расстояние между ними в этом пространстве.

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

Проверяются все пары объектов, выбирается пара с максимальной степенью подобия, которая и становится кластером.

Определяются свойства кластера как некоторые функции свойств элементов

(например, среднее значение), и компоненты объектов заменяются этими значениями признаков.

Этот процесс повторяется до тех пор, пока все объекты не будут отнесены к одному кластеру.

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

по методу максимального правдоподобия (maximum likelihood density estimation). Это

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

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

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

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

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

objecf1={small, red, rubber, ball}, object2={small, blue, rubber, ball}, object3={large, black, wooden, ball},

то можно ввести метрику подобия

similarity(object1, object2) = 3/4.

similarity(object1, objects) = similarity(object2, object3) = 1/4

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

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

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

{X | X, которые избирались на пост генерального секретаря ООН}

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

Концептуальная кластеризация (conceptual clustering) позволяет решить эти проблемы за счет использования методов машинного обучения для создания общих определений понятий и применения базовых знаний при формировании этих категорий. Хорошим примером реализации этого подхода является система CLUSTER/2 [Michalski и Stepp, 1983]. В ней для представления категорий используются базовые знания в форме языковых порогов.

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

Выбрать к опорных объектов из множества существующих. Это можно сделать с

помощью генератора случайных чисел.

Для каждого опорного объекта, используя его в качестве положительного примера,

а все остальные - в качестве отрицательных, создать наиболее общее

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

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

Классифицировать все объекты в соответствии с этими описаниями. Заменить каждое максимально общее определение максимально конкретным, покрывающим

все объекты этой категории. При этом снижается вероятность перекрытия классов

при классификации новых, неизвестных ранее объектов.

Классы могут перекрываться даже для объектов обучающего множества. В систему CLUSTER/2 включен алгоритм настройки перекрывающихся определений.

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

класса. Метрика расстояния может напоминать описанную выше метрику подобия.

Используя эти центральные элементы в качестве опорных, повторить пункты 1-5.

Алгоритм завершается после формирования приемлемых кластеров. Типичной мерой качества является сложность общих описаний классов. Например, согласно

принципу "бритвы Оккама" следует отдавать предпочтение кластерам с синтаксически простыми определениями, т.е. с малым числом конъюнктов.

Если кластеры неприемлемы, но в течение нескольких итераций не наблюдается

никаких улучшений, выберите новые опорные объекты, ближайшие к границе кластеров , а не к его центру. :

Этапы работы алгоритма CLUSTER/2 показаны на рис. 9.20.

9.6.3. Программа СОВ-WEB и структурные таксономические знания

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

419

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

Например, если бы человеческие категории на самом деле определялись необходимыми и достаточными условиями принадлежности, мы не смогли бы отличить степень этой принадлежности. Однако психологи отмечают важное значение прототипов в человеческих категориях [Rosch, 1978]. Например, для человека малиновка- более типичный пример птицы, чем курица, а дуб - более типичный пример дерева, чем пальма (как минимум, в северных широтах).

Эти рассуждения подтверждаются теорией семейного сходства (family resemblance theory), которая гласит, что категории определяются сложной системой сходства между элементами, а не необходимыми и достаточными условиями принадлежности членов [Wittgenstein, 1953]. При такой категоризации может не существовать свойств, общих для всех элементов класса. В работе [Wittgenstein, 1953] приводится пример категории "игра": не все игры предполагают наличие двух или нескольких игроков (например, компьютерные игры), не для всех игр четко сформулированы правила (например, для детских), и не все игры предполагают соревнование, подобно перетягиванию каната. Тем не менее эта категория хорошо определена и недвусмысленна.

Человеческие категории также отличаются от большинства формальных иерархий наследования (глава 8) тем, что не все уровни человеческой таксономии одинаково важны. Психологам удалось продемонстрировать существование категорий базового уровня (base-level category) [Rosch, 1978]. Базовая категория- это классификация, которая чаще всего используется для описания объектов в терминах, изученных с раннего детства, на уровне, в некотором смысле охватывающем наиболее фундаментальные свойства объекта. Например, категория "стул" является более базовой, чем любое ее обобщение, в частности, "мебель", или любая ее специализация, например, "офисный стул". "Машина" - это более базовая категория, чем "седан" или "транспортное средство".

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

Эти проблемы учтены в системе COB-WEB [Fisher, 1987]. Не претендуя на звание модели человеческого познания, эта система учитывает категории базового уровня и степень принадлежности элемента соответствующей категории. Кроме того, в программе COBWEB реализован инкрементальный алгоритм обучения, не требующий представления всех обучающих примеров до начала обучения. Во многих приложениях обучаемая система получает данные со временем. В этом случае она должна строить полезные определения понятий на основе исходных данных и обновлять эти описания с появлением новой информации. В системе COBWEB также

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

решена проблема определения корректного числа кластеров. В программе CLUSTER/2 формируется изначально заданное число категорий. Пользователь может изменять это число, однако такой подход нельзя назвать гибким. В системе COBWEB для определения количества кластеров, глубины иерархии и принадлежности категории новых экземпляров используется глобальная метрика качества.

В отличие от рассмотренных ранее алгоритмов, в системе COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, p(fi=Vij|ck) - это условная вероятность, с которой свойство f, принимает значение vij, если объект относится к категории ск.

На рис. 9.21 показана система классификации программы COBWEB, приведенная в работе [Gennari и др., 1989]. Это пример категоризации четырех одноклеточных организмов, изображенных в нижней части рисунка. Каждый класс определяется значениями следующих свойств: цвет, количество хвостов и ядер. Например, к категории СЗ относятся объекты, имеющие по 2 хвоста и ядра с вероятностью 1,0, и светлые с вероятностью 0,5.

Как видно из рис. 9.21, для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. Это важно как для категоризации новых экземпляров, так и для изменения структуры категорий для более полного соответствия свойствам их элементов. Поскольку в системе COBWEB реализован инкрементальный алгоритм обучения, она не разделяет эти операции. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility) [Gluck и Corter, 1985]. Критерий полезности категории был определен при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

\fi=vij).

Значения суммируются по всем категориям ск, всем свойствам fi и всем значениям свойств Vij. Значение p(fi=vij|ck) называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство fi- принимает значение Vij, относится к категории ск. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина p(ck|fi=vij) называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории ск свойство fi принимает значение vij. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение p(fi=vij) - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

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

Рис. 9.21. Кластеризация четырех одноклеточных организмов в системе COBWEB

Алгоритм COBWEB имеет следующий вид.

cobweb (Node, Instance)

Begin

if узел Node - это лист, then begin

создать два дочерних узла L1 и L2 для узла Node; задать для узла L1 те же вероятности, что и для узла Node; инициализировать вероятности для узла L2 соответствующими значениями объекта Instance;

422

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

добавить Instance к Node, обновив вероятности для узла Node ;

end

else begin

добавить Instance к Node, обновив вероятности для узла

Node ; для каждого дочернего узла С узла Node

вычислить полезность категории при отнесении

экземпляра Instance к категории С; пусть S1 - значение полезности для наилучшей

классификации Сх; пусть S2 - значение для второй наилучшей

классификации С2 ; пусть S3 - значение полезности для отнесения

экземпляра к новой категории;

пусть S4 - значение для слияния С1 и С2 в одну категорию; пусть S5 - значение для разделения C1 (замены

дочерними категориями); end

if S1 - наилучшее значение,

then cobweb(C1, Instance) %отнести экземпляр к С1

else, if S3- наилучшее значение,

then инициализировать вероятности для новой

категории значениями Instance else, if Si _ наилучшее значение, then begin

пусть Ст - результат слияния С1 и С2; cobweb(Cm, Instance) end

else, if S3 _ наилучший результат, then Begin

разделить С1; cobweb(Сm, Instance) end; end

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

Отнесение экземпляра к наилучшей из существующих категорий.

Добавление новой категории, содержащей единственный экземпляр.

Слияние двух существующих категорий в одну новую с добавлением в нее этого

экземпляра.

Разбиение существующей категории на две и отнесение экземпляра к лучшей из

вновь созданных категорий.

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

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

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

Рис 9.22 Слияние и разбиение узлов

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

9.7. Обучение с подкреплением

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

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

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

9.7.1. Компоненты обучения с подкреплением

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

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

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

Многие проблемно-ориентированные алгоритмы, описанные ранее в этой книге, включая алгоритмы планирования, методы принятия решений или алгоритмы поиска, можно рассматривать в контексте обучения с подкреплением. Например, можно создать план с помощью телео-реактивного контроллера (раздел 7.4), а затем оценить его на основе алгоритма обучения с подкреплением. По существу, в алгоритме обучения с подкреплением DYNA-Q [Sutton, 1990, 1991] модельное обучение объединено с планированием и действием. Такое обучение с подкреплением обеспечивает метод оценки как плана, так и модели, а также их полезности для решения задач в сложной среде.

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

t - дискретный момент времени в процессе решения задачи;

s, - состояние задачи в момент времени f, которое зависит от st-1 и at-1

а, - действие в момент времени f, зависящее от st;

rt, - вознаграждение в момент времени f, зависящее от st-1 и at-1;

п - политика выполнения действий в зависимости от состояния, т.е. отображение из

пространства состояний в пространство действий;

п - оптимальная политика;

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

V - функция ценности, т.е. v?(s) - это ценность состояния s при использовании политики я.

В подразделе 9.7.2 при постоянной политике я описан метод временных разностей (temporal difference learning) для изучения V на основе s.

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

Функция вознаграждения (reward function) r, задает отношение состояние-цель для данной задачи в момент времени f. Она определяет отображение каждого действия, или, более точно, каждой пары "состояние-отклик", в меру вознаграждения, определяющую степень эффективности этого действия для достижения цели. В процессе обучения с подкреплением перед агентом ставится цель максимизации общего вознаграждения, получаемого в результате решения задачи.

Функция стоимости, или ценности (value function), V- это свойство каждого состояния среды, определяющее величину вознаграждения, на которое может рассчитывать система, продолжая действовать из этого состояния. Если функция вознаграждения определяет сиюминутную эффективность пары "состояние-отклик", то функция ценности задает долговременную перспективность состояния среды. Значение состояния определяется как на основе его внутреннего качества, так и на основе качества состояний, вероятно, последующих за данным, т.е. вознаграждения, получаемого при переходе в эти состояния. Например, пара "состояние-действие" может приводить к низкому сиюминутному вознаграждению, но иметь высокую ценность, поскольку за ней обычно следуют другие состояния с высоким вознаграждением. Низкая ценность соответствует состояниям, не приводящим к успешному решению задачи.

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

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

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

9.7.2. Пример: снова "крестики-нолики"

Проиллюстрируем алгоритм обучения с подкреплением на примере игры "крестики-нолики". Этот пример уже рассматривался в главе 4. Он же использован в [Sutton и Barto, 1998] для иллюстрации обучения с подкреплением. Целесообразно сравнить обучение с подкреплением с другими подходами, например минимаксным, и разграничить их.

Напомним, что "крестики-нолики" - это игра для двух человек, которые по очереди расставляют свои метки X и О в сетке, размером 3x3 (см. рис. II.V). Побеждает игрок, первым составивший ряд из трех меток либо по горизонтали, либо по вертикали, либо по диагонали. Как известно читателю из раздела 4.3, при наличии полной информации о планах оппонента эта игра всегда завершается вничью. Однако при использовании обучения с подкреплением можно получить более интересный результат. В этом разделе будет показано, как можно разгадать планы соперника и выработать политику, позволяющую максимизировать свое преимущество. Эта политика эволюционирует при изменении стиля игры соперника и строится на использовании модели.

Во-первых, необходимо создать таблицу, в которой каждому возможному состоянию игры соответствует одно число. Эти числа, определяющие ценность состояния, отражают текущую оценку вероятности победы, если игра начинается с этого состояния. Они будут использованы для выработки стратегии чистой победы, при которой победа соперника или ничья рассматриваются как поражение. Такой подход позволяет сконцентрироваться на победе, и этим он отличается от рассмотренной в разделе 4.3 модели, предполагающей 3 возможных исхода: победа, поражение и ничья. Это действительно важное отличие. В обучении с подкреплением учитывается поведение реального соперника, а не полная информация о действиях некоего идеализированного оппонента. В таблице значения ценности нужно проинициализировать следующим образом: 1 - для тех состояний, которые приводят к победе, 0 - для приводящих к поражению или ничьей и 0,5 - для всех остальных неизвестных позиций. Это соответствует 50% вероятности победы для этих состояний.

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

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

V(sn)=V(sn)+c(V(sn+1)-V(sn)).

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

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