Программа MINIHYPER

Теперь мы можем приступить к написанию нашей первой программы 1LP, Гипо-тезы удобнее всего представлять в виде списка предложений следующим образом: Hypothesis = [ Clausel, Claused, ... ]

Каждое предложение представляется в виде списка литералов (головы предложе­ния, за которым следуют литералы тела) и списка переменных в предложении, как показано ниже.

Clause ■ [Head, BodyLitecall, BodyLiteral2, ...]/[ Varl, Var2 , ... ]

Например, в соответствии с этим соглашением гипотеза

pred{X,Y) :- parent (X, Y) .

pred(X,z) :- parent (x, Y), pred(Y,Z}.

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

[[predJXX., YD., parent(XI,¥1) ] / [XI,YI], Ipred (X2, Z2J , parent 1X2, Y2) , pred(Y2,Z2) ] / [X2,Y2,Z2] ]

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

Для того чтобы проверить, охватывает ли гипотеза некоторый примпр, требуется интерпретатор типа Prolog для гипотез, представленных, как описано выше. Для этого определим следующий предикат: prove! Goal, Hypothesis, Answer)

Этот предикат для заданной цели Goal и гипотезы Hypothesis находит ответ Answer, указывающий, можно ли вывести цель Goal логически из гипотезы Hypothesis. По сути, данный предикат должен предпринимать попытки доказать истинность Goal на основании гипотезы Hypothesis по принципу, аналогичному самому интерпретатору Prolog. Задача разработки такой программы относится к об­ласти метапрограммирования, которое рассматривается более подробно в главе 23, В данном случае особая сложность состоит в том, что необходимо избежать опасности возникновения бесконечных циклов. Применяемый оператор усовершенствования вполне может вырабатывать рекурсивные предложения, подобные следующему:

[ р[Х), р(Х} ]

Такое предложение соответствует предложению р(Х) :- р(Х), Это может при­вести к бесконечному циклу. Необходимо добиться того, чтобы предикат prove не был восприимчивым к таким циклам. Проще всего этого можно достичь, ограничив длину доказательств. Если в процессе доказательства цели Goal количество вызовов предикатов достигает заданного предела, то процедура prove прекращает свою рабо­ту, не сформировав окончательного ответа. Таким образом, параметр Answer преди­ката prove может иметь перечисленные ниже возможные значения,



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


• Answer = yes. Цель Goal была логически выведена из гипотезы Hypothesis в пределах длины доказательства.

• Answer = no. Очевидно, что цель Goal невозможно вывести логически из ги­потезы Hypothesis, даже если данный предел будет увеличен.

• Answer = maybe. Поиск доказательства был прекращен в связи с тем, что дос­тигнуто значение максимальной длины доказательства D.

Случай "Answer = maybe" может соответствовать любому из перечисленных ни­же трех вариантов, если цель Goal выполнялась с помощью стандартного интерпре­татора.

1. Стандартный интерпретатор Prolog (без ограничения длины доказательства) вошел в бесконечный цикл.

2. Стандартный интерпретатор Prolog мог бы в конечном итоге найти доказатель­ство, длина которого превышает предел D.

3. Стандартный интерпретатор Prolog мог бы определить на каком-то этапе дока­зательства, длина которого превышает D, что этот вариант логического вывода оканчивается неудачей. Поэтому он должен был бы перейти по методу перебо­ра с возвратами к другому варианту и в этом случае либо найти доказательство {длина которого может оказаться меньше чем D), либо не достичь цели, либо войти в бесконечный цикл.

Код предиката prove приведен в листинге 19.2. Предел длины доказательства за­дается с помощью следующего предиката:

raax_pEOof_length( D)

Значение D по умолчанию установлено равным 6, но может быть откорректирова­но в зависимости от конкретной задачи обучения. Вызовы фоновых предикатов (объявленных с помощью предиката prolog_predicate) передаются стандартному интерпретатору Prolog и поэтому не вносят свой вклад в увеличение длины доказа­тельства. Таким образом, учитываются только вызовы целевых предикатов, которые определены в гипотезе.

Листинг 19.2.Интерпретатор гипотез, позволяющий избежать циклов

% Интерпретатор гипотез

% prove; Goal, Hypo, Answ):

* Answ = yes, если цель Goal можно логически вывести из гипотезы Hypo

% не Оольше, чем за D шагов

% Answ = no, если цель Goal нельзя вывести логическим путем

% Answ = maybe, если поиск заканчивается безрезультатно после D шагов

prove( Goal, Hypo, Answer) :-max_procf_len.gth; D) ,

prove; Goal, Hypo, D, RestD),
(RestD >= 0, Answer = yes % Доказано

RestD < 0, !, Answer - maybe % Возможно, что доказательство существует,

% но пока ситуация напоминает бесконечный цикл ) .

prove! Goal, _, no) . % В противном случае цепь Goal определенно

% нельзя доказать

%prove( Goal, Hyp, MaxD, RestD):

-ь MaxD - допустимая длина доказательства, RestD - длина, "оставшаяся % неиспользованной" после доказательства; учитываются только шаги % доказательства, в которых используется гипотеза Hyp

prove [ G, К, D, D) :-

D < 0, !. I Длина доказательства превышена


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



prove ((],_, D, D) :- ! .

prove! [Gl | Gs] , Hypo, DO, D] : - ! , prove( Gl, Hypo, DO, Dl>, prove ! Gs, Hypo, Dl, D) .

prove! G, _, D, D) :-

prologjpredicate( G) , % Фоновый предикат иа языке Prolog?

call( G) , % Вызвать фоновый предикат

prove { G, Hyp, DO, D) : -

DO =< 0, \r Dis D0-1 h Доказательство- слишком длинное

Dl is DO-1, % Оставшаяся длина доказательства

member ( Clause/Vars, Hyp), % Одно из предложений в гипотезе Hyp

eopy_term< Clause, [Head | Body] ), r Переименовать переменные в предложении
G - Head, % Согласовать голову предложения с целью

prove ( Eody, Hyp, Dl, D). % Доказать G с помощью предложения Clause

Эта обучающаяся программа реагирует на случаи "maybe", как говорится, "осторожно" (так принято характеризовать данный способ организации работы про­граммы), т.е. осуществляется осторожная интерпрстация,поскольку в ней исполь­зуется описанный ниже подход.

1. Если проводится доказательство положительного примера, то случай "maybe"
трактуется как утверждение, что "данный пример не охвачен".

2. Если проводится доказательство отрицательного примера, то случай "maybe"
трактуется как отрицание утверждения, что этот отрицательный пример "не
охвачен". Иными словами, считается, что он все еще охвачен.

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

Остальная часть программы MINIHYPER приведена в листинге 19.3. В этой про­грамме определены предикаты, описанные ниже.