Must rjol toucfi

itt

must nut touch

V.

f triangle )

j f rectangle }**^

must not touch

Рис. 18.5. Развитие гипотез об арке; на каждом этапе текущая гипотеза Н сравнивается со следующим примером Bi+i и вырабатывается очередная, уточненная гипотеза Ещ

416 Часть II. Применение языка Prolog в области искусственного интеллекта

Результатом применения этого правила к гипотезе ;:_: становится новая гипотеза н₂ (см. рис. 18.5). Обратите внимание на то, что в новой гипотезе имеется еще одна связь, must_not_touch (не должны соприкасаться), которая налагает дополнитель­ное ограничение на конструкцию, рассматриваемую как арка. Поэтому можно ут­верждать, что новая гипотеза Н является более конкретной, чем н_:.

Следующий отрицательный пример, приведенный на рис. 18.4, представлен се­мантической сетью Е, на рис. 18.5. Его сопоставление с текущей гипотезой н обна­руживает два различия: две связи support, присутствующие в Н , отсутствуют в Ез. После этого ученик должен выбрать наиболее приемлемое среди следующих трех возможных объяснений.

1. Пример Ез — не арка, поскольку отсутствует левая стойка.

2. Пример Ез — не арка, поскольку отсутствует правая стойка.

3. Пример Ез - не арка, поскольку отсутствуют обе стойки.

В соответствии с этим ученик должен выбрать один из трех возможных способов обновления текущей гипотезы. Предположим, что ученик скорее склонен действо­вать решительно, чем осторожно, поэтому ему больше нравится объяснение 3. Таким образом, ученик принимает предположение, что нужны обе связи support, и поэто­му преобразует две связи support гипотезы н_: в связи must support новой гипоте­зы Н, (см. рис. 18.5). Эту ситуацию отсутствия связей можно обработать с помощью следующего правила типа "условие-действие", которое представляет собой еще одно общее эвристическое правило, касающееся обучения: если

пример - отрицательный и

не содержит отношения Р., который присутствует в текущей гипотезе Н, то

следует включить отношение R в новую гипотезу (добавить в гипотезу Н отношение must_R).

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

Последний пример в этой обучающей последовательности, Е . снова является по­ложительным. Сопоставление соответствующих семантических сетей, Е^ и Н₃, позво­ляет обнаружить различие: верхняя часть в v, является треугольной, а в н₃ — пря­моугольной. Теперь ученик может перенаправить соответствующую связь isa в дан­ной гипотезе с прямоугольника на новый класс объектов - rectangle_or_triangle (прямоугольник или треугольник). Но альтернативная (и более часто применяемая) реакция в обучающейся программе основана на заранее определенной иерархии поня­тий. Предположим, что ученик имеет возможность воспользоваться классификацией понятий, подобной приведенной на рис. 18.6, в качестве априорных знаний о конкрет­ной проблемной области. Обнаружив, что согласно этой классификации и прямоуголь­ник, и треугольник относятся к типу stable poly (устойчивый многоугольник), уче­ник может обновить текущую гипотезу, чтобы получить гипотезу н- (см. рис. 18.5).

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

Глава 18. Машинное обучение

системе будет показана конструкция, приведенная на рис. 18.7, и задан вопрос, к какому классу она относится, то система назовет ее аркой, поскольку эта конструк­ция полностью соответствует окончательному представлению системы об арке, ины­ми словами, гипотезе EU-

/

'" ;. "ё

у,: уде !

Circle

triangle rectangle trapezium u ns table _ triangle hexagonРис. 18.6. Иерархия понятий

hasp art

. ЯШ Жн>Из

support JL support

м

г~~\

у. ; ' J

^*"( melanin }^*^

Рис. 18.7. Слева показан новый объект, справа — его представление. Этот объект соответствует опре­делению понятия арка И,, показанному на рис. 18.S, при условии, что используется иерархия понятий, показанная на рис, 18.6

Ниже приведены некоторые важные выводы, которые можно продемонстрировать на предыдущем примере.

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

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

Часть II. Применение языка Prolog в области искусственного интеллекта

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

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

В предыдущее издание этой книги [12] была включена реализация на языке Prolog программы обучения с помощью реляционных описаний, организованная по принципам, которые рассматриваются в данном разделе. В настоящее издание ука­занная реализация не включена, хотя хорошей иллюстрацией к фундаментальным понятиям машинного обучения может служить программа ARCHES. Дело в том, что некоторые алгоритмы обучения показали себя как намного более эффективные инст­рументальные средства обучения для практических приложений. К ним относятся средства обучения с помощью правил вывода (раздел 18.4) и деревьев решения (раздел 18.5). Мы вернемся к теме обучения с помощью реляционных описаний в следующей главе, где рассматривается инфраструктура индуктивного логического программирования.