Листинг 19.4. Формулировка задачи для изучения предиката определения принадлежности к списку

Ь Формулировка задали лля изучения предиката member(X,L) backliteral( member(X,L), [L:listI, iX:item] ), % Фоновый литерал Ч Усовершенствование термов

term.!list, [X|L], [ К:item, L:iist]>. terrat list, [) , [1) .

prolog_predicate( fail). Ч тоновый литерал отсутствует в программе

I на языке Prolog

start_clause ( [ member (X,!,) ] / [ X:item, L:list]).

% Положительные и отрицательные примеры

ess! member! a, [a])) . ех[ member! b, [а_гЬ])).

ex ( member ( d, [з,Ь,с, d, е] ) ) .

пег:! member ! Ь, [а])) .

пех ( member ( d, [а,Ь] ) ) .

пех ( meraber{ f, [a,b, c,d, ej) ) .

460

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

Назначение входных и выходных параметров состоит в следующем. Если какой-либо параметр литерала является входным, то предполагается, что он должен кон­кретизироваться при каждом выполнении этого литерала. Это означает, что если при усовершенствовании предложения такой литерал добавляется к телу предложения, то каждая из его входных переменных должна быть немедленно согласована с неко­торой существующей переменной в предложении. В приведенном выше примере должна быть немедленно согласована с существующей переменной переменная L (также относящаяся к типу "список") при каждом добавлении литерала member (X,L) к предложению. Подобное согласование должно обеспечивать, чтобы входной параметр был конкретизирован ко времени выполнения данного литерала. С другой стороны, выходные параметры могут быть согласованы с другими перемен­ными позднее. Поэтому при усовершенствовании предложения выходные переменные обрабатываются по такому же принципу, как и все переменные в программе M1NIHYPER. Но ограничения на типы исключают возможность согласования пере­менных разных типов. Поэтому переменная X типаitem (элемент) не может быть со­гласована с переменной L типа list (список).

Возможные усовершенствования переменных с преобразованием в структуриро­ванные термы определяются следующим предикатом: terra: Type, Texm, Vars)

Он указывает, что переменная типа Туре в предложении может быть заменена термом Тегт; Vars — это список переменных и их типов, которые встречаются в терме Term. Поэтому в листинге 19.4 предложения

termi; list, [X|L], [ X:itera, L:Iist]). term[list, [],[]).

указывают, что переменная типа list может быть преобразована в процессе усовер­шенствования в терм |Х; jj, где X относится к типу item, a '. — к типу list, или что эта переменная может быть заменена константой [] (без переменных). Во всей данной главе предполагается, что символ ":" введен как инфиксный оператор. В листинге 19.4 предложение start_clause( [ mex.ber<X,L) J / [ X:iteir,, L:list]) .

объявляет форму предложений в начальных гипотезах графа усовершенствования. Каждая начальная гипотеза представляет собой список начальных предложений, ко­личество которых не может превышать некоторого максимального количества (копий). Список начальных гипотез формируется автоматически. Максимальное ко­личество предложений в гипотезе определяется предикатом max_clauses. Он может быть задан пользователем соответствующим образом с учетом специфики задачи обу­чения.

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

1. Согласовать две переменные в предложении, например XI = Х2. Могут быть согласованы только переменные одного и того же типа.

2. Преобразовать в процессе усовершенствования переменную предложения в фо­новый терм. При этом могут использоваться только термы, определенные пре­дикатом term/З, а тип переменной и тип терма должны соответствовать друг другу.

3. Добавить фоновый литерал к предложению. Все входные параметры литерала должны быть согласованы (недетерминированно) с существующими перемен­ными предложения (такого же типа).

Как и в программе MINIHYPER, для усовершенствования гипотезы .-:. в програм­ме HYPER выбирается одно из предложений С. в гипотезе предложение : преоб­разуется в процессе усовершенствования в предложение С и формируется новая ги­потеза Н путем замены предложения С в гипотезе :^; , предложением С. В листин-

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

re 19.5 показана последовательность усовершенствований при изучении предиката member.

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

member[Xl,Ll). member(X2,L2).

t Усовершенствовать герм Ll = [X3|L3] member(Xl, [X3|L3]). member(X2,L2) .

4- Согласовать XI = X3 member(Xl, [Xl|L3]) . member(X2,L2).

I Усовершенствовать терм L2 = [X4[L4] member (XI, [XI iL3J ) . member(X2, [X4IL4]).

ir Ввести либерал member (X5, 1-5) и согласовать входные параметры L5 ~ L4 member(Xl, [X1IL3]). member (X2, [X4IL4]) :- member <x5_rL4t,

l Согласовать Х2 = X5 member(XI, [X1IL3]) . гаеяЬегЮ, [X4|L4]> :- member <X2,L4>.

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

Такой оператор усовершенствования предназначен для выработки наименее кон­кретных уточнений (Least Specific Specialization •— LSS). Уточнение И гипотезы Н_с называется наименее конкретным, если не существует других уточнений гипотезы более общих, чем Н. Но в действительности рассматриваемый оператор усовер­шенствования позволяет лишь приблизиться к LSS. Этот оператор усовершенствова­ния позволяет достичь I-SS только в условиях того ограничения, что количество предложений в гипотезе после усовершенствования остается тем же самым. Без этого ограничения оператор LSS должен был бы увеличивать количество предложений в гипотезе. Это может привести к созданию оператора усовершенствования, не совсем приемлемого с точки зрения практики из-за его вычислительной сложности, по­скольку при его использовании количество предложений в усовершенствованной ги­потезе может стать очень большим. Но ограничение, предусмотренное в данной про­грамме, которое требует сохранения неизменного количества предложений в гипотезе после ее усовершенствования, является не слишком жестким. Если для решения требуется формирование гипотезы с большим количеством предложений, то такая гипотеза может быть выработана из другой начальной гипотезы, которая имеет дос­таточное количество предложений.

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

Поиск

Поиск начинается с множества начальных гипотез. Оно представляет собой мно­жество всех возможных мультимножеств определяемых пользователем начальных предложений, вплоть до некоторого максимального количества предложений в гипо­тезе. Как правило, в начальной гипотезе появляется несколько копий одного и того же начального предложения. Типичное начальное предложение представляет собой нечто довольно общее и нейтральное, такое как conc( LI, L2, L3). В процессе по­иска граф усовершенствования рассматривается как дерево (если к одной и той же гипотезе ведет несколько путей, то в дереве появляется несколько копий этой гипо­тезы). Поиск начинается с нескольких начальных гипотез, которые становятся кор­нями несвязанных друг с другом деревьев поиска. Поэтому, строго говоря, простран­ство поиска представляет собой не дерево, а лее.

Программа HYPER выполняет поиск по заданному критерию с использованием функции оценки Cost (Hypothesis), в которой учитывается размер гипотезы (как описано ниже), а также ее точность по отношению к заданным примерам. Стоимость гипотезы Н определяется с помощью следующей простой формулы: Cost HI = мл * SizeJH) + w₂ * MegCover(H>

где NegCover(H) — количество отрицательных примеров, охватываемых гипотезой Н, Определение "гипотеза Н охватывает пример Е" трактуется в рамках осторожной интерпретации ответа Answer в предикате prove. В этой формуле н и ■.■:. обозначают весовые коэффициенты. Размер гипотезы определяется как взвешенная сумма коли­чества литералов и количества переменных в гипотезе следующим образом: Size£H> = Ь * количество^л_и*ералоь(Н> + к, * количество_переменныа (н)

В коде программы HYPER, приведенном в этой главе, фактически используются следующие значения весовых коэффициентов: w_: -- 1, w₂ = 1С, ki = 10, к₂ = 1. Это соответствует приведенной ниже формуле.

Cost(H> - количество_переменных(Н) + 10 * количество_лктералов (Н) + 10 * HegCover(H)

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