Граф усовершенствования

Теперь рассмотрим, каким образом может быть сформирована полная и совмести­мая гипотеза для задачи обучения, приведенной в листинге 19.1. Мы можем начать с некоторой слишком общей гипотезы, которая является полной {охватывает все по­ложительные примеры), но несовместимой (она является несовместимой в том смыс­ле, что не охватывает лишь положительные примеры, т.е. охватывает также отрица­тельные примеры). Подобная гипотеза должна быть усовершенствована таким образом, чтобы она сохранила спою полноту и стала совместимой. Этого можно достичь путем поиска в пространстве возможных гипотез и их усовершенствований. При каждом усо­вершенствовании берется гипотеза:-:. и вырабатывается более конкретная гипотеза Н_;, такая, что П. охватывает подмножество случаев, охватываемых гипотезой П_;.

Подобное пространство гипотез и их усовершенствований называется графом усо­вершенствования. На рис. 19.1 показана часть такого графа усовершенствования для задачи обучения, приведенной в листинге 19.1. Узлы в этом графе соответствуют гипо­тезам, а дуги между гипотезами соответствуют усовершенствованиям. Между гипоте­зами Hi и 1Ь имеется ориентированная дуга, если ][. является усовершенствованием Hi.

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

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

1. Оператор усовершенствования, который будет вырабатывать усовершенство­вания гипотез (такой оператор определяет граф усовершенствования).

2. Процедура поиска для выполнения поиска.

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

1. Согласование двух переменных в предложении.

2. Добавление фонового литерала к телу предложения.

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

h»»_d вид lite r(X).

hafi_dauglitar[ X):- hos_dnughter(X)! male(Y). femole(Y).

has_daughter(X):-parent) Y, Z).

I

i

hasdaughter! X):- htis,daught0r(X)! -j, vi fcnuilo(Y), parent{5, T).

has_daughter(X):-parent(X, Z).

\

has_daughter(X):-parent! X, 2), fema!e(U).

I

has^daughtert X) :- parent) X, Z), female(Z).

Рис. 19.1. Часть графа усовершенствования для задачи обучения, приве­денной е листинге, 19,1. На этой схеме не показано много других воз­можных усовершенствовании

Примером усовершенствования первого типа является следующее предложение: has_daughter{X):- parent(Y,z>.

Это предложение путем усовершенствования преобразуется в предложение has_daughter!x);- parent tx, Z).

в котором выполнено согласование X=Y. Примером усовершенствования второго типа является операция, в результате которой предложение has_daughter(X).

путем усовершенствования преобразуется в следующее предложение: has_daughter (X):- parent(Y,2).

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

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

Может также рассматриваться еще один тип усовершенствования, который преду­сматривает замену переменных структурированными терма ми. Например, предложение member! xl, ГД!:- member! XI, L3).

может быть преобразовано в процессе усовершенствования в следующее предложение:

member! XI, [Х2 | L2)):- member (Xl, L3).

Глава 19. Индуктивное логическое программирование

Е результате усовершенствования переменная L1 преобразована в структуру [Х2 | L2]. Для простоты в программе MINIHYPER, разрабатываемой в этом разде­ле, не предусмотрена возможность решать задачи, для которых требуются структу­рированные термы. Отложим введение этого средства до следующего раздела, в кото­ром разрабатывается более сложная программа HYPER,

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