Листинг 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)

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

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

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

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

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