Must rjol toucfi

itt

must nut touch

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). Мы вернемся к теме обучения с помощью реляционных описаний в следующей главе, где рассматривается инфраструктура индуктивного логического программирования.