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

Обучение способности распознавать в мире блоков конструкции и, в частности, арки было впервые рассмотрено как проблемная область обучения Уикстоном [169] в его ранней работе по машинному обучению. Эта область рассматривается в данной главе для иллюстрации некоторых важных механизмов, касающихся обучения. Применяемая здесь трактовка в основном (хотя и не полностью) опирается на про­грамму Уинстона, называемую ARCHES.

LTD

I 1

Арка

Не арка

 

D D

Не арка

 

U

Арка

Рис. 18.4. Последовательность при­меров и контрпримеров для изуче­ния понятия арки

Программу ARCHES можно использовать для изучения понятия арки на приме­рах (рис. 18.4). Приведенные здесь примеры обрабатываются последовательно, и ученик постепенно обновляет текущую гипотезу, касающуюся понятия арки. В слу­чае, показанном на рис. 18.4, гипотеза (т.е. окончательное понимание учеником, что такое арка), сформулированная после обработки учеником всех четырех примеров, может неформально выглядеть примерно так, как описано ниже.

1. Арка состоит из трех частей; предположим, что они обозначены как postl (стойка 1), post2 (стойка 2) и lintel (перекладина).

2. Стойки postl и post2 имеют прямоугольную форму, а перекладина lintel может иметь более сложную форму, например многоугольную (этот вывод мо­жет быть сделан на основании примеров 1 и 4 на рис. 18.4).

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

3. Стойки postl и post2 не должны соприкасаться (к этому выводу можно прийти на основании отрицательного примера 2).

4. Стойки postl и post2 должны поддерживать перекладину lintel (это следу­ет из отрицательного примера 3).

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

Для изучения понятия С с использованием заданной последовательности приме­ров Ei, E₂,..., Е_п (где Ei должен быть положительным примером С) необходимо вы­полнить перечисленные ниже действия.

1. Принять Е_г в качестве начальной гипотезы Н_: о понятии С.

2. Обработать все оставшиеся примеры, при этом для каждого примера Ei (i = 2, 3,...) выполнить следующее.

 

2.1. Сопоставить текущую гипотезу Щ-i с Ei; допустим, что результатом сопос­тавления является некоторое описание D различий между Hi-i и Ei.

2.2. Доработать гипотезу Hi--, с учетом описания D, а также того, является ли Ei положительным или отрицательным примером С; результатом этого ста­новится уточненная гипотеза н_;, касающаяся С.

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

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

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

Второй пример (граф Е₂ на рис. 18.5) представляет собой отрицательный пример арки. Сопоставить Е₂ с Hi несложно. Поскольку обе сети очень похожи, можно легко установить соответствие между узлами и связями в Hi и Е₂. Результат сопоставления показывает различие D между Hi и Е₂. Различие состоит в том, что в Е есть еще одно отношение, touch. Поскольку в этом состоит единственное различие, система прихо­дит к выводу, что именно по этой причине Е не является аркой. После этого система обновляет текущую гипотезу Н_ь применяя следующий общий эвристический прин­цип обучения:

если

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

содержит отношение R, который не принадлежит к текущей гипотезе Н, то

запретить применение отношения R в гипотезе Н (ввести в гипотезу Н отношение must_not_R).

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

has part

 

Touch

haspait