Листинг 19.8. Изучение предиката path, предназначенного для поиска пути в графе

% Изучение предиката path[StartNode,GoalNode,Path), предназначенного % для поиска пути в графе

Ь Ориентированный граф

link ta,b).

11ПК ^а f o^ -

link(b,с) -link(b,d). link(d,e >.

backliteral(link[X,Y), [ X:item], [ Y:item]). backliteral(path{X, i, L), [ X:item], [ Y:item, L:list]).

term£ list, [X|L], [ X:item, L:list]}. termt list, [], []).

prolog_predicate(link(X,Y)}.

start_clause([ path{X,Y,L)] / [X: item,Y;item,L:list] >.

'i Примеры

ex(path(a, a, [a]}).

ex(path(b, b, [b])).

ex{ path) e, e, [el)).

ex( path{ f, f, [f] )).

ex ( path{ a, c, [a,c]) }.

ex< path(b, e, [b,d,e))).

ex(path{ a, e, [a,b,d,*])).

Ш>. [b])). [b,b]]). [e,d])). [a,b,c])}

next path(a, a,

next path(a, a,

next path (a, a,

next patht e, d,

nex< path (a, d,

U path (a, e, (a])). nex(patht a, c, [a,c,a,c]) next patht a, d, Ea,d])).

Последняя строка в логически выведенном определении может на первый взгляд показаться неожиданной, но в данном контексте она фактически эквивалентна ожи­даемому значению path (В, С, [В|Е] I. Для получения последнего варианта требуется, чтобы количество этапов усовершенствования было на единицу меньше. Тот факт, что в этом процессе поиска было усовершенствовано только 35 гипотез, может пока­заться довольно удивительным, если принять во внимание следующие факты. Глу­бина усовершенствования приведенной выше гипотезы path, обнаруженной в про­цессе поиска, равна 12, а результаты оценки показывают, что размер дерева усовер­шенствования на этой глубине превышает 10'" гипотез! Но фактически выполнен поиск лишь в очень небольшой части этого пространства. Такие результаты можно объяснить тем, что в данном случае требования к полноте гипотезы ограничивают поиск особенно эффективно.

Изучение предиката, предназначенного для сортировки по методу вставки

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

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

ей типичной постановки задачи в области машинного обучения. Для того чтобы обу­чение было наиболее эффективным, мы должны передать программе обучения на­столько качественное представление задачи, насколько это возможно, включая фоно­вые знания. Это неизбежно требует от пользователя размышлений по поводу воз­можных решений. В данном случае, в котором рассматривается поиск алгоритма сортировки, задача обучения была бы очень сложной без подобного полезного опре­деления фоновых знаний. Но даже в этом случае оказывается, что рассматриваемая задача является наиболее сложной среди всех проведенных до сих пор эксперимен­тов. Код, показанный в листинге 19.9, требует дополнительных комментариев. Дело в том, что в терме sort(Ll,L2) параметр L1, согласно принятому предположению, должен быть конкретизирован, тогда как L2 — это выходной параметр, который конкретизируется после вызова на выполнение процедуры sort. Для того чтобы ло­гически выведенная процедура sort могла действовать при неконкретизированном параметре L2, один из примеров задан следующим образом:

ех([ sort ([c, a, b ], L), L = [a,b,c] ]).

Листинг 19.9. Изучение процедуры сортировки по методу вставки

% Изучение процедуры сортировки

backliteraK sort (L, S), [L:list], [S:list]).

backliteraK insert_sorted(X, Ll, L2), [X:item, Ll:list], [L2:list]).

termf list, [X | L], [X:item, L: 1ist]). termf list, [], []).

prolog_predicate(insert_sorted(x, lo, l)). prolog_predicate (x=y).

start_clause([sort (L1,L2) ] / [Ll:list, L2:1ist]).

ex(sort ([], [])).

ex(sort ([a], [a])).

]). % Второй параметр процедуры sort % неконкретизирован!

ex([ sort ([c,a,b], L), L = [a,b,c]

ex(sort ([b,a,c], [a,b,c])).

ex(sort ([c,d,b,e,a], [a,b,c,d,e])).

ex(sort([a,d,c,b], [a,b,c,d])).

nex (sort([], [a])).

nex(sort ([a,b], [a])).

nex(sort([a,c], [b,c])).

nex (sort ([b,a,d,c], [b,a,d,c])).

nex(sort([a,c,b], [a,c,b])).

nex(sort([], [b,c,d])).

insert sorted(x, L, _):- % "Защитное" предложение: проверка конкретизации

% параметров var(X),!, fail

var (L),!, fail

L = [Y|_], var (Y),!, fail.

insert_sorted(X, [], [X]):-!.

insert_sorted(X, [Y | L], [X,Y | L]):-

X @< Y,!. % Терм X "лексикографически предшествует" терму Y

insert_sorted(X, [Y I Li, [Y I Ll]):-insert_sorted (x, l, Ll).

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

Это позволяет обеспечить возможность вызова процедуры sort с неконкретизиро-ванкым значением L, так, чтобы sort сформировала (а не просто распознала!) резуль­тат L и только после этого проверила его правильность. Необходимо также соблюдать осторожность при определении фонового предиката insert_sorted(X,Ll_p L2), чтобы можно было обеспечить конкретизацию параметров в соответствии с ожидаемым (например, X не является переменной). Полученные результаты приведены ниже.

Hypotheses generated: 3708 hypotheses refined: 2Ё4 To be refined: 448

sort ([],[]). sort[[ft IB],D);-sort(B,C),

insert_sorted(A,C,D).

Изучение предиката, позволяющего распознать конструкцию арки

Эта задача обучения аналогична задаче реляционного обучения, описанной в главе 18, в которой в качестве примеров применяются конструкции, выполненные из бло­ков (рис. 19.2), и существует иерархия между типами блоков (которая определяется предикатом а ко [X, Y) — Y представляет собой разновидность (ако — a kind of) X; это отношение аналогично показанному на рис. 18.6). Примеры описывают конструкции, состоящие иа трех блоков. Первые два блока из трех определяют стойки арки, а тре­тий блок определяет перекрытие. Поэтому одним из положительных примеров явля­ется crch(al,bl, cl), где а', Ы и с] — прямоугольные блоки, cl опирается на &1 и Ы, а между al и Ы ме определено отношение touch (соприкасается). Блоки а2, Ь2 и с2 образуют отрицательный пример (пех (а2,Ь2, c2J), поскольку блок с.2 не опи­рается на а2 и Ь2. Блоки а5, Ь5 и с5 образуют еще один отрицательный пример, по­скольку с: не соответствует определению "устойчивого многоугольного блока". Опре­деление задачи обучения распознаванию арки приведено в листинге 19.10. Фоновые предикаты в этом листинге включают также отрицание (not), которое применено к предикатам touch/2 и support/2. Такой фоновый предикат, как обычно, выполня­ется непосредственно интерпретатором Prolog по принципу отрицания как недости­жения цели. В отличие от рис. 18.4, на рис. 19.2 количество отрицательных приме­ров увеличено для ограничения возможности выбора совместимых гипотез. Результат обучения приведен ниже.

Ij

Al

ы

ь>

С2

 

 

сД			с4			\	с5	/
	аЗ	ЬЗ			а4		Ь4		»5	Ь5

Рис. 19.2. Мир блоков с двумя положительными и тремя от­рицательными примерами арки. Блоки al, Ы и cl показыва­ют один положительный пример, а блоки а4, Ы и ей — вто­рой. Один из отрииатслъныхпримеров показывают блоки а2, Ь2 и с2

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

Hypotheses generated: 368 Hypotheses refined: 10 To be refined: 151

arch {R_r В _r Cl: -support(B,C), not touch(A,B), support(A,C), isa{C, stable_pcly)

Арка состоит из стоек А, В и перекладины С

С опирается на В

А и Б не соприкасаются

С опирается на А

С - устойчивый многоугольный блок