Теперь мы можем приступить к написанию нашей первой программы 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 D is 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. В этой программе определены предикаты, описанные ниже.
