Часть 9.

how(X), где X - это целевое утверждение Запрос к пользователю: car_starts ? -100.

Запрос к пользователю:turns_over ? why. bad_system(starter_system):-

not car_starts

not turns_over CF = 90

Запрос к пользователю:turns_over ? why. bad_component(starter):-

bad_system(starter_system)

lights(come_on) CF = 50

Запрос к пользователю:turns_over ? why. fix(_0):-

bad_component(starter)

fix(starter, _0) CF = 100

Запрос к пользователю: turns_over ? why.

Возврат к верхушке стека правил. Запрос к пользователю: turns_over ? 85.

Запрос к пользователю: gas_in_carb ? 75.

Запрос к пользователю:tuned_recently ? why. bad_component(timing):-

bad_system(ignition_system)

not tuned_recently CF = 80

Запрос к пользователю:tuned_recently ? how(bad_system(ignition_system)). bad_system(ignition_system) заключение получено с

достоверностью 60.0 Доказательство bad_system(ignition_system) CF= 60.0 :-

not car_starts CF = -100 получено от пользователя

turns_over CF = 85 получено от пользователя

gas_in_carb CF = 75 получено от пользователя Запрос к пользователю:tuned_recently ? -90.

X = 'настроить временные параметры' CF = 48.0

14.7.3. Семантические сети в языке PROLOG

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

Глава 14. Введение в PROLOG 657

В семантической сети, показанной на рис. 14.7, узлы представляют такие объекты, как конкретная канарейка tweety, и классы ostrich (страус), crow (ворона), robin (дрозд), bird (птица) и vertebrate (позвоночное). Отношение isa связывает классы различных уровней иерархии наследования. В этой сети реализованы канонические формы представления данных. Предикат isa (Type, Parent) указывает на то, что объект Туре является подтипом Parent, а предикат hasprop(Object, Property, Value) описывает свойства объектов. Предикат hasprop указывает на то, что объект Object обладает свойством Property со значением Value. При этом Object и Value - это узлы сети, a Property - имя объединяющей их связи.

Рис. 14.7. Фрагмент семантической сети, описывающей птиц и других животных

Фрагмент списка предикатов, описывающих показанную на рис. 14.7 иерархию птиц, имеет вид.

isa(canary, bird).

isa(ostrich, bird).

isa(bird, animal).

isa(opus, penguin).

hasprop(tweety, color, white).

hasprop(canary, color, yellow).

hasprop(bird, travel, fly).

hasprop(ostrich, travel, walk).

hasprop(robin, sound, sing).

hasprop(bird, cover, feathers).

isa (robin, bird), isa(penguin, bird), isa(fish, animal). isa(tweety, canary). hasprop(robin, color, red), hasprop(penguin, color, brown) hasprop(fish, travel, swim). hasprop(penguin, travel, walk) hasprop(canary, sound, sing), hasprop(animal, cover, skin).

Создадим рекурсивный алгоритм поиска, позволяющий определить, обладает ли некий объект семантической сети указанным свойством. Свойства хранятся в сети на самом высо-

658 Часть VI. Языки и технологии программирования для искусственного интеллекта

ком уровне, на котором они истинны. С помощью наследования объект или подкласс приобретает свойства своего суперкласса. Так, свойство fly относится к объекту bird и всем его подклассам. Исключения размещаются на отдельном уровне исключений. Так, страус ostrich и пингвин penguin ходят (walk), но не летают (fly). Предикат hasproperty начинает поиск с конкретного объекта. Если информация напрямую не связана с этим объектом, он переходит по связи isa к суперклассам. Если суперкласса больше не существует, и предикат hasproperty не нашел нужного свойства, поиск завершается неудачей.

hasproperty(Object, Property, Value):-

hasprop(Object, Property, Value), hasproperty(Object, Property, Value) :-

isa(Object, Parent),

hasproperty(Parent, Property, Value).

Предикат hasproperty выполняет поиск в глубину в иерархии наследования. В следующем разделе будет показано, как применять наследование для представления на основе фреймов и реализовывать отношения деревьев и множественного наследования.

14.7.4. Фреймы и схемы в языке PROLOG

Семантические сети можно разбивать на части, добавляя к описаниям узлов дополнительную информацию и обеспечивая тем самым фреймовую структуру. Переопределим рассмотренный в предыдущем подразделе пример с использованием фреймов. Каждый фрейм будет представлять набор отношений семантической сети, а ячейка isa - определять иерархию фреймов (рис. 14.8).

В первой ячейке каждого фрейма содержится имя узла, например, name(tweety) или name (vertebrate). Во второй ячейке определяется отношение наследования между данным узлом и его родителями. Поскольку в нашем примере сеть имеет древовидную структуру, каждый узел содержит лишь одну связь - предикат isa зависит от одного аргумента. В третьей ячейке содержится список свойств, описывающих этот узел. В этом списке можно использовать любые предикаты PROLOG, в том числе flies, feathers или color (brown). В последней ячейке фрейма находится список исключений и принимаемых по умолчанию значений для данного узла. Его элементы тоже могут представлять собой либо отдельные слова, либо предикаты, описывающие свойства.

Рис. 14.8. Фреймы для базы знаний о птицах

Глава 14. Введение в PROLOG

659

На нашем языке фреймов каждый предикат frame связывает имена ячеек, списки свойств и принимаемые по умолчанию значения. Это позволяет различать типы знаний и приписывать им разное поведение в иерархии наследования. Хотя при такой реализации подклассы могут наследовать свойства обоих списков, для конкретных приложений могут оказаться полезными и другие представления. Например, можно наследовать только используемые по умолчанию значения или строить третий список, содержащий свойства самого класса, а не его экземпляров. Такие значения иногда называются значениями класса (class value). Например, можно сделать так, чтобы класс canary определял вид певчей птицы. Это свойство не должно наследоваться подклассами или экземплярами: tweety - не есть вид певчих птиц. Дальнейшее расширение этого примера предлагается выполнить в качестве упражнения в конце этой главы.

Теперь опишем отношения, показанные на рис. 14.8, на языке PROLOG с помощью предиката факта frame с четырьмя аргументами. Для проверки соответствия типов предиката frame, в частности, для проверки того, что в третьей ячейке фрейма содержится список, элементы которого принимают значение из заданного диапазона свойств, можно использовать методы, предложенные в подразделе 14.6.2.

frame(name(bird),

isa(animal),

[travel(flies), feathers],

[ ]) . frame(name(penguin) ,

isa(bird),

[color(brown)],

[travel(walks)]). frame(name(canary),

isa(bird),

[color(yellow), call(sing)],

[size(small)]). frame(name(tweety),

isa(canary),

[ ],

[color(white)]).

Определив для фрейма (рис. 14.8) полное множество описаний и отношений наследования, разработаем процедуры для извлечения свойств из этого представления.

get(Prop, Object) :-

frame(name(Object), _, List_of_properties, _),

member(Prop, List_of_properties). get(Prop, Object) :-

frame(name(Object), _, _, List_of_defaults),

member(Prop, List_of_defaults). get(Prop, Object) :-

frame(name(Object), isa(Parent), _, _),

get(Prop, Parent).

Если структура фреймов допускает множественное наследование свойств (см. также раздел 15.12), то в наше представление и стратегию поиска необходимо внести соответствующие изменения. Во-первых, в представлении фрейма аргумент, связанный с предикатом isa, должен содержать список суперклассов данного объекта. Каждый суперкласс этого списка - это родительский класс объекта, указанного в первом аргументе предиката frame. Если opus относится к классу пингвинов penguin и представляет собой персонаж мультфильма (cartoon_char), то это можно представить следующим образом.

660 Часть VI. Языки и технологии программирования для искусственного интеллекта

frame(name(opus),

isa([penguin, cartoon_char]), [color(black)], [ ])•

Теперь проверим свойства объекта opus с помощью возврата по иерархии isa к обоим суперклассам penguin и cartoon_char. Между третьим и четвертым предикатами get в предыдущем примере нужно добавить дополнительное определение.

get(Prop, Object) :-

frame(name(Object), isa(List), _, _), get_multiple(Prop, List).

Предикат get_multiple можно определить следующим образом.

get_multiple(Prop, [Parent|_]) :-

get(Prop, Parent). get_multiple(Prop, [_|Rest]) :-

get_multiple(Prop, Rest).

В этой иерархии свойства класса penguin и его суперклассов будут проверены до начала проверки свойств класса cartoon_char.

И, наконец, с каждой ячейкой фрейма можно связать любую процедуру на языке PROLOG. Имея фреймовое представление для данного примера, в качестве параметра предиката frame можно добавить правило PROLOG или список таких правил. Для этого все правило нужно заключить в скобки, как это делалось при реализации оболочки ex-shell, и включить эту структуру в список аргументов предиката frame. Например, можно разработать список правил отклика для объекта opus, обеспечив для этого персонажа возможность давать различные ответы на разные вопросы.

Этот список правил (где каждое правило заключено в скобки) должен стать параметром предиката frame, определяющим соответствующий ответ в зависимости от значения X, передаваемого фрейму opus. Более сложными примерами могут служить правила управления термостатом или создания графического изображения на основе множества значений. Такие примеры представлены в разделе 15.12, где важную роль в объектно-ориентированном представлении играют связанные с объектами процедуры, зачастую называемые методами.

14.8. Алгоритмы обучения в PROLOG

14.8.1. Поиск в пространстве версий языка PROLOG

В главе 9 описано несколько алгоритмов символьного машинного обучения. В этом и следующем разделах будут реализованы два из них: алгоритмы поиска в пространстве версий (version space search) и обучения на основе пояснения (explanation-based learning). Сами эти алгоритмы описаны в главе 9, а здесь приводится лишь их реализация на языке PROLOG. Такой выбор языка для реализации алгоритмов машинного обучения обусловлен тем, что он очень иллюстративен, поддерживает встроенные механизмы проверки соответствия шаблонам, а его возможности рассуждений на метауровне упрощают построение и работу с новыми представлениями.

Сначала реализуем поиск от частного к общему, а затем - полный двунаправленный алгоритм исключения кандидата. Читателю будут предложены советы по построению

Глава 14. Введение в PROLOG 661

системы поиска в пространстве версий от общего к частному. Эти алгоритмы поиска независимы от используемого представления понятий, если это представление поддерживает соответствующие операции обобщения и специализации. Мы будем использовать представление объектов в виде списков свойств. Например, маленький красный мяч можно описать с помощью следующего списка.

[small, red, ball].

Понятие маленького красного объекта можно описать с помощью списка с переменной. [small, red,X].

Такое представление называется вектором признаков (feature vector). Оно менее выразительно, чем полная логика, поскольку с его помощью нельзя представить класс "всех красных и зеленых мячей". Однако оно упрощает обобщение и обеспечивает строгий индуктивный порог (раздел 9.4). Вектор признаков можно обобщить, подставляя вместо константы переменные. Например, наиболее конкретным обобщением для векторов [small, red, ball] и [small, green, ball] является вектор [small, X, ball]. Этот вектор покрывает каждую из специализаций и является наиболее конкретным из всех таких векторов.

Будем считать, что вектор признаков покрывает другой вектор признаков, если он либо идентичен этому вектору, либо является более общим. Заметим, что в отличие от процедуры унификации отношение покрытия covers асимметрично: существуют значения, для которых X покрывает У, но Y не покрывает X. Например, вектор [X, red, ball] покрывает вектор [large, red, ball], но не наоборот. Определим предикат covers для векторов признаков следующим образом.

covers([], []).

covers([HI|Tl], [H2|T2]) :- %переменные покрывают друг друга

var(Hl), var(H2), covers(Tl, T2) . covers([HI|Tl], [H2|T2]) :- %переменная покрывает константу

var(Hl), atom(H2), covers(Tl, T2). covers([Hi|Tl], [H2|T2]) :- %проверка соответствия констант

atom(Hl), atom(H2), HI = H2,

covers(Tl, T2).

Теперь необходимо определить, является ли один вектор признаков строго более общим, чем другой (т.е. векторы не идентичны). Определим соответствующий предикат

more_general.

more_general(X, Y) :- not(covers(Y, X)), covers(X, Y).

Обобщение векторов признаков реализуется с помощью предиката generalize, зави

сящего от трех аргументов. Первый аргумент- это вектор признаков, представляющий

гипотезу (он может содержать переменные). Второй аргумент- экземпляр, не содержа

щий переменных. Третий аргумент предиката generalize связывается с наиболее кон

кретным обобщением гипотезы, покрывающей данный экземпляр. Предикат generalize

рекурсивно сканирует векторы признаков, сравнивая соответствующие элементы. Если два

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

компонента вектора гипотезы. Если эти элементы не совпадают, то в соответствующую по

зицию результирующего вектора помещается переменная. Обратите внимание на исполь

зование выражения not (Feature\=Inst_prop) во втором определении предиката

обобщения. Это двойное отрицание позволяет проверить, можно ли унифицировать два

атома без реального выполнения процедуры унификации и формирования любого нежела

тельного связывания переменных. Определим предикат generalize. Hfl(

662 Часть VI. Языки и технологии программирования для искусственного интеллекта

generalize([], [], []) .

generalize([Feature|Rest], [Inst_prop|Rest_inst],

[Feature|Rest_gen]) :-

not(Feature \= Inst_prop), generalize(Rest, Rest_inst, Rest_gen). generalize([Feature|Rest], [Inst_prop|Rest_inst], [_|Rest_gen]) :-

Feature \= Inst_prop, generalize(Rest, Rest_inst, Rest_gen).

Эти предикаты задают основную операцию для представления векторов признаков. Остальная часть реализации не будет зависеть от конкретного представления и может применяться к различным представлениям и операциям обобщения.

Как было указано в разделе 9.2, поиск от частного к общему в пространстве понятий можно проводить за счет поддержания списка Н гипотез-кандидатов. Гипотезы в Н - это наиболее конкретные понятия, покрывающие все положительные примеры и ни одного отрицательного. Ядром алгоритма является процедура process, зависящая от пяти аргументов. Первый аргумент- это обучающий экземпляр positive (X) или negative (X), указывающий на то, что X является положительным или отрицательным примером. Второй и третий аргументы - это текущий список гипотез и список отрицательных экземпляров. В процессе реализации предикат process связывает четвертый и пятый аргументы с обновленными списками гипотез и отрицательных экземпляров соответственно.

Первое выражение в этом определении инициализирует пустое множество гипотез первым положительным экземпляром. Второе обрабатывает положительные обучающие примеры путем обобщения гипотез-кандидатов для обеспечения покрытия этих примеров. Затем ликвидируется чрезмерное обобщение за счет удаления всех гипотез, которые являются более общими, чем другие, а также гипотез, покрывающих некоторые отрицательные примеры. Третье выражение в этом определении служит для обработки отрицательных примеров за счет удаления любых гипотез, покрывающих эти экземпляры.

process(positive(Instance), [], N, [Instance], N). process(positive(Instance), H, N, Updated_H, N) :-

generalize_set(H, Gen_H, Instance),

delete(X, Gen_H, (member(Y, Gen_H), more_general(X, Y)), Pruned_H),

delete(X, Pruned_H, (member(Y, N),

covers(X, Y)), Updated_H). process(negative(Instance), H, N, Updated_H, [Instance|N]) :-

delete(X, H, covers(X, Instance), Updated_H).

process(Input, H, N, H, N):- %Отслеживание ошибок ввода

Input \= positive(_),

Input \= negative(_),

write("Введите либо положительный пример positive(Instance) либо отрицательный negative(Instance) ')/ nl.

Интересным аспектом этой реализации является предикат delete, представляющий собой обобщение обычного процесса удаления всех повторных вхождений элемента из списка. Один из аргументов этого предиката используется для определения того, какие элементы подлежат удалению из списка. С помощью предиката bagof предикат delete проверяет соответствие своего первого аргумента (который обычно является переменной) каждому элементу второго аргумента (который обязательно должен быть списком). Затем для каждого такого связывания выполняется проверка, указанная с помощью третьего аргумента. Эта проверка представляет собой любую последовательность вызовов целевых утверждений языка PROLOG. Если список элементов таков, что данная проверка завершается

Глава 14. Введение в PROLOG 663

неудачно, то предикат delete исключает этот элемент из результирующего списка. Результат возвращается через последний аргумент. Предикат delete- это прекрасный пример метарассуждений в языке PROLOG. Имея возможность передавать спецификацию элементов, которые требуется удалить из списка, программист тем самым получает общее средство реализации целого спектра операций со списками. Так, предикат delete позволяет определять различные фильтры, используемые в процедуре process, в очень компактной форме. Зададим предикат delete следующим образом.

delete(X, L, Goal, New_L) :-

(bagof(X, (member(X, L), not(Goal)), New_L); New_L = [ ]).

Предикат generalize_set рекурсивно сканирует список гипотез и обобщает каждую из них в соответствии с обучающим примером. При этом предполагается возможность существования нескольких обобщений кандидатов одновременно. На самом деле описанное в разделе 9.2 представление в виде признаков допускает лишь одно наиболее конкретное обобщение. Однако в целом это неверно, поэтому необходимо определить алгоритм для общего случая.

generalize_set([ ], [],_).

generalize_set([Hypothesis|Rest], Updated_H, Instance):-

not(covers(Hypothesis, Instance)),

(bagof(X, generalize(Hypothesis, Instance, X), Updated_head), Updated_head = [ ]) ,

generalize_set(Rest, Updated_rest, Instance),

append(Updated_head, Updated_rest, Updated_H). generalize_set([Hypothesis|Rest], [Hypothesis|Updated_rest], Instance) :-

covers(Hypothesis, Instance),

generalize_set(Rest, Updated_rest, Instance).

Правило specif ic_to_general реализует цикл для считывания и обработки обучающих примеров.

specific_to_general(H, N) :-

write('H='),write(H),nl,write('N='),write(N), nl, write('Введите пример:') ,

read(Instance), process(Instance, H, N, Updated_H, Updated_N), specific_to_general(Updated_H, Updated_N).

Следующий пример иллюстрирует выполнение алгоритма.

?- specific_to_general([], [] ) .

Н = []

N = []

Введите пример: positive([small, red, ball]).

H = [[small, red, ball]]

N = []

Введите пример: negative([large, green, cube]).

H = [[small, red, ball]]

N = [[large, green, cube]]

Введите пример: negative([small, blue, brick]).

H = [[small, red, ball]]

N = [[large, green, cube], [small, blue, brick]]

Введите пример: positive([small, green, ball]).

H = [[small, _66, ball]]

664 Часть VI. Языки и технологии программирования для искусственного интеллекта

N = [[large, green, cube], [small, blue, brick]] Введите пример: positive([large, blue, ball]). H = [[_116, _66, ball]] N = [[small, blue, brick], [large, green, cube]]

Вторая версия алгоритма, описанного в подразделе 9.2.2, выполняет поиск в направлении от общего к частному. В этой версии множество гипотез-кандидатов инициализируется наиболее общим среди возможных понятий. Для представления с помощью вектора признаков - это список переменных. Затем выполняется специализация понятий-кандидатов, предотвращающая покрытие отрицательных примеров. В представлении на основе векторов признаков эта операция сводится к замене переменных константами. При получении нового положительного примера удаляются любые гипотезы-кандидаты, не покрывающие его.

Реализация этого алгоритма во многом аналогична описанной выше реализации поиска от частного к общему, включая использование общего предиката delete для определения различных фильтров для списка понятий-кандидатов.

В системе поиска от общего к частному процедура process будет зависеть от шести параметров. Первые пять соответствуют версии поиска от частного к общему. Первый параметр - это обучающий пример вида positive (Instance) или negative (Instance), второй- список гипотез-кандидатов, включающий наиболее общие гипотезы, не покрывающие отрицательных примеров. Третий параметр - список положительных примеров, используемый для удаления любых слишком специализированных гипотез-кандидатов. Четвертый и пятый параметры - это обновленные списки гипотез и положительных примеров соответственно. Шестой параметр - это список допустимых подстановок переменных для специализации понятий. Для специализации путем подстановки константы вместо переменной следует знать допустимые значения каждого компонента вектора признаков. Эти значения необходимо передавать с помощью шестого параметра предиката process. В рассматриваемом примере векторов [Size, Color, Shape] список типов может иметь вид [[small, medium, large], [red, blue, green], [ball, brick, cube]]. Заметим, что позиция каждого подсписка соответствует компоненту вектора признаков, в котором используются значения этого списка. Например, первый подсписок определяет допустимые значения первого компонента вектора признаков.

Реализацию этого алгоритма предлагается осуществить в качестве упражнения. Для ориентировки приведем результаты работы нашей реализации.

?- general_to_specific([[_,_,_]],[], [[small,medium,large],

[red,blue,green],

[ball, brick, cube]]). H = [[_0, _1, _2]] P = П

Введите пример: positive([small, red, ball]). H = [[_0, _1, _2]] P = [[small, red, ball]]

Введите пример: negative([large, green, cube]). H = [[small, _89, _90], [_79, red, _80],[_69, _70, ball]] P = [[small, red, ball]]

Введите пример: negative([small, blue, brick]). H = [[_79, red, _80],[_69, _70, ball]] P = [[small, red, ball]]

Введите пример: positive([small, green, ball]). H = [[_69, _70, ball]] P = [[small, green, ball], [small, red, ball]]

Глава 14. Введение в PROLOG 665

14.8.2. Алгоритм исключения кандидата

Полный алгоритм исключения кандидата, описанный в подразделе 9.2.2, представляет собой комбинацию двух однонаправленных алгоритмов поиска. Его ядром тоже является предикат process, зависящий от шести аргументов. Первый аргумент- обучающий пример, второй и третий аргументы - G и S - это множества максимально общих и максимально конкретных гипотез соответственно. Четвертый и пятый аргументы соответствуют обновленным версиям этих множеств. Шестой аргумент предиката process содержит список допустимых подстановок для специализации векторов признаков.

Для положительных примеров предикат process выполняет обобщение множества S наиболее конкретных обобщений с целью покрытия этого примера. Затем из S исключаются любые чрезмерно обобщенные элементы. Кроме того, из множества G тоже удаляются все элементы, не обеспечивающие покрытия этого обучающего примера. Интересно отметить, что элемент S является чрезмерно общим, если не существует покрывающих его элементов G. Дело в том, что множество G содержит такие гипотезы-кандидаты, которые, с одной стороны, являются максимально общими, а с другой - не покрывают отрицательных примеров. Для удаления гипотез используется предикат delete.

При поступлении отрицательного примера предикат process выполняет специализацию всех гипотез в G, чтобы исключить этот пример. При этом из S удаляются все кандидаты, покрывающие этот отрицательный пример. Как указывалось выше, специализация векторов признаков сводится к замене переменных константами. Для этого требуется передать список допустимых подстановок в качестве шестого аргумента предиката process. Определение предиката process имеет следующий вид.

process(negative(Instance), G, S, Updated_G, Updated_S, Types) :-delete(X, S, covers(X, Instance), Updated_S), specialize_set(G, Spec_G, Instance, Types), delete(X, Spec_G, (member(Y, Spec_G), more_general(Y, X)),

Pruned_G), delete(X, Pruned_G, (member(Y, Updated_S), not(covers(X, Y))),

Updated_G). process(positive(Instance), G, [], Updated_G, [Instance], _):-

^Инициализация S

delete(X, G, not(covers(X, Instance)), Updated_G). process(positive(Instance), G, S, Updated_G, Updated_S, _) :-delete(X, G, not(covers(X, Instance)), Updated_G), generalize_set(S, Gen_S, Instance),

delete(X, Gen_S, (member(Y, Gen_S), more_general(X, Y)), Pruned_S),

delete(X, Pruned_S, not((member(Y, Updated_G), covers(Y, X))),

Updated_S). process(Input, G, P, G, P, _):-

Input \= positive(_), Input \= negative(_), write('Введите либо положительный positive(Instance) либо отрицательный пример negative(Instance):'), nl.

Предикат generalize_set выполняет обобщение всех элементов множества гипотез-кандидатов с целью покрытия обучающего примера. Его реализация в точности идентична версии, определенной в программе поиска от частного к общему. В качестве пара-

666 Часть VI. Языки и технологии программирования для искусственного интеллекта

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

specialize_set([], [], _, _).

specialize_set([Hypothesis|Rest], Updated_H, Instance, Types):-covers(Hypothesis, Instance),

(bagof(Hypothesis, specialize(Hypothesis, Instance, Types), Updated_head) , Updated_head = []),

specialize_set(Rest, Updated_rest, Instance, Types) :-append(Updated_head, Updated_rest, Updated_H). specialize_set([Hypothesis|Rest],[Hypothesis|Updated_rest], Instance,Types) not(covers(Hypothesis, Instance)),

specialize_set(Rest, Updated_rest, Instance, Types).

Предикат specialize находит среди элементов вектора признаков тот, который является переменной. Он связывает эту переменную с константой, выбираемой им из списка допустимых значений таким образом, чтобы она не соответствовала обучающему примеру. Напомним, что предикат specialize_set вызывает предикат specialize с помощью предиката bagof для получения всех специализаций. При однократном вызове предиката specialize он лишь подставляет константу вместо первой переменной. Использование предиката bagof обеспечивает получение всех специализаций.

specialize([Prop|_], [Inst_prop|_], [Instance_values|_]):-

var(Prop),

member(Prop, Instance_values), Prop \= Inst_prop. specialize([_|Tail], [_|Inst_tail], [_|Types]):-

specialize(Tail, Inst_tail, Types).

Определения предикатов generalize, more_general, covers и delete совпадают с соответствующими определениями этих предикатов в программе поиска от частного к общему. Предикат candidate_elim реализует цикл верхнего уровня, выводит текущие значения множеств G и S, а также вызывает предикат process.

candidate_elim([G], [S], _) :-covers(G, S), covers(S, G), write("целевое понятие: '), write(G),nl. candidate_elim(G, S, Types) :-write('G-'),write(G),nl,write('S='),write(S), nl, write('Введите

пример: '), read(Instance),

process(Instance, G, S, Updated_G, Updated_S, Types), candidate_elim(Updated_G, Updated_S, Types).

В заключение этого раздела представим результаты трассировки алгоритма исключения кандидата. Обратите внимание на инициализацию множеств G и S, а также список допустимых подстановок.

?- candidate_elim([[_,_,_]], [], [[small, medium, large], [red, blue, green],

[ball, brick, cube]]). G= [[_0, _1, _2]] S= []

Глава 14. Введение в PROLOG 667

Введите пример: positive([small, red, ball]).

G= [[_0, _1, _2]]

S= [[small, red, ball]]

Введите пример: negative([large, green, cube]).

G= [[small, _96, _97], [_86, red, _87], [_76, _77, ball]]

S= [[small, red, ball]]

Введите пример: negative([small, blue, brick]).

G= [[_86, red, _87], [_76, _77, ball]]

S= [[small, red, ball]]

Введите пример: positive([small, green, ball]).

G= [[_76, _77, ball]]

S= [[small, _351, ball]]

Введите пример: positive([large, red, ball]).

target concept is: [_76, _77, ball]

yes

14.8.3. Реализация обучения на основе пояснения на языке PROLOG

В этом разделе будет описана реализация на языке PROLOG алгоритма обучения на основе пояснения, изложенного в подразделе 9.4.2. Наша реализация основывается на алгоритме prolog_ebg, предложенном в работе [Kedar-Cabelli и McCarty, 1987], и иллюстрирует возможности унификации в языке PROLOG. Несмотря на то что на многих языках достаточно сложно реализовать алгоритм обучения на основе пояснения, его версия на PROLOG очень проста.

Этот алгоритм не строит структуру пояснения и не поддерживает отдельные множества для подстановок обобщения и специализации, как это описано в разделе 9.4. В нем дерево доказательства для обучающих примеров и обобщенное дерево доказательства строятся одновременно.

В этом примере будут использованы деревья доказательств, аналогичные применяемым в оболочке exshell (подраздел 14.7.2). При выявлении факта в системе prolog_ebg этот факт возвращается как лист дерева доказательства. Доказательство конъюнкции целей представляет собой конъюнкцию доказательств каждой из них. Доказательство цели, требующее построения цепочки правил, представляется в виде (Goal :- Proof), где Proof связывается с деревом доказательства для предпосылок этих правил.

Ядром алгоритма является предикат prolog_ebg. Он зависит от четырех аргументов. Первый из них - это целевое утверждение, доказываемое с помощью обучающего примера. Второй - обобщение цели. Если теория описания области определения допускает доказательство конкретной цели, то третий и четвертый аргументы связываются с деревом доказательства для цели и его обобщения. В частности, при реализации примера из подраздела 9.5.2 нужно вызвать предикат prolog_ebg со следующими аргументами.

prolog_ebg(cup(objl), cup(X), Proof, Gen_proof).

Предполагается, что на языке PROLOG представлена теория описания области определения и обучающий пример из подраздела 9.4.2. При успешном завершении процедуры prolog_ebg параметры Proof и Gen_proof будут связаны с деревьями доказательств, показанными на рис. 9.17.

Процедура prolog_ebg - это простая вариация метаинтерпретатора, описанного в подразделе 14.7.2. Основное отличие состоит в том, что разрешение цели и ее обобщения выполняется параллельно. Еще один интересный аспект алгоритма связан с исполь-

668 Часть VI. Языки и технологии программирования для искусственного интеллекта

зованием предиката duplicate для создания двух версий каждого правила. Первая версия - это правило из теории описания предметной области, а вторая связывает переменные этого правила со значениями из обучающего примера. Определим предикат prolog_ebg.

prolog_ebg(A, GenA, A, GenA) :- clause(A, true). prolog_ebg((А, В), (GenA,GenB), (AProof,BProof), (GenAProof,GenBProof)) :- !,

prolog_ebg(A, GenA, AProof, GenAProof),

prolog_ebg(B, GenB, BProof, GenBProof).

prolog_ebg(A, GenA, (A :- Proof), (GenA :- GenProof)) :-clause(GenA, GenB), duplicate((GenA :- GenB), (A :- B)),

prolog_ebg(B, GenB, Proof, GenProof).

Предикат duplicate основывается на использовании предикатов assert и retract для создания копии выражения PROLOG с новыми переменными.

duplicate(Old, New) :- assert('$marker'(Old)), retract ('$marker'(New)).

Предикат extract_support возвращает последовательность операционных узлов наивысшего уровня согласно определению предиката operational. Он реализует рекурсивный проход по дереву. Рекурсия прекращается при обнаружении узла в дереве доказательства, квалифицируемого как операционный.

extract_support(Proof, Proof) :- operational(Proof). extract_support((A :- _), A) :- operational(A). extract_support((AProof, BProof), (A, B)) :-

extract_support(AProof, A),

extract_support(BProof, B). extract_support((_ :- Proof), B) :- extract_support(Proof, B).

Последним компонентом алгоритма является построение изученного правила на основе предикатов prolog_ebg и extract_support.

ebg(Goal, Gen_goal, (Gen_goal :- Premise)) :-prolog_ebg(Goal, Gen_goal, _, Gen proof). extract_support(Gen_proof, Premise).

Проиллюстрируем выполнение этих предикатов на примере изучения структурных определений чашки из подраздела 9.5.2 [Mitchell и др., 1986]. Сначала опишем теорию предметной области чашек и других физических объектов. Эта теория включает следующие правила.

cup(X) :- liftable(X), holds_liquid(X).

holds_liquid(Z) :- part(Z, W) , concave(W), points_up(W) .

liftable(Y) :- light(У), part(Y, handle).

light(A):- small(A).

light(A):- made_of(A, feathers).

Обучаемой системе также дается следующий пример, о котором известно, что оЬ j 1 - чашка.

small(objl). part(objl, handle), owns(bob, obj1).

Глава 14. Введение в PROLOG 669

part(objl, bottom), part(objl, bowl). points_up(bowl). concave(bowl). color(objl, red).

С помощью критерия операционности определим предикаты, которые можно использовать в правиле.

operational(small(_)). operational(part(_, _)). operational(owns(_, _)). operational(points_up(_)). operational(concave(_)).

Запуск алгоритма для этого примера иллюстрирует поведение этих предикатов.

?- prolog_ebg(cup(objl), cup(X), Proof, Gen_proof).

X = _0,

Proof = cup(objl) :-

((liftable(objl) :-((light(objl) :-

small(objl)), part(objl, handle))), (holds_liquid(objl) :-

(part(obj1, bowl),

concave(bowl), points_up(bowl)))) Gen_prooof = cup(_0) :-((liftable(_O) :-( (light(_0) :-small(_0)), part(_0, handle))) , (holds_liquid(_0) :-(part(_0, _106), concave(_106), points_up(_106)) ) )

Если предикату extract_support передать обобщенное дерево доказательства, полученное после выполнения предиката prolog_ebg, то он возвратит операционные узлы дерева доказательства, упорядоченные слева направо.

?- extract_support((cup(_0) :-((liftable(_0) :-((light(_0) :-small(_0)), part(_0, handle))), (holds_liquid(_0) :-

(part(_0,_106), concave(_106) ,

points_up(_106))))), Premise), _0 = _0, _106 = _1,

Premise = (small(_0),part(_0,handle)),part(_0,_l), concave(_l), points_up(_1)

И, наконец, предикат ebg использует описанные выше процедуры для построения нового правила на основе предъявленного примера.

?- ebg(cup(obj1), сир(Х), Rule). X = _0,

670 Часть VI. Языки и технологии программирования для искусственного интеллекта

Rule = cup(_O) :-

((small(_0), part(_0,handle)),part(_0,_110), concave(_110), points_up(_110))

14.9. Обработка естественного языка на PROLOG

14.9.1. Семантические представления для обработки естественного языка

Благодаря встроенным возможностям поиска и проверки соответствия шаблонам язык PROLOG органично подходит для решения задач обработки естественного языка. Грамматику естественного языка можно описать на PROLOG напрямую, как это будет сделано при описании контекстно-независимой и контекстно-зависимой грамматик в подразделе 14.9.2. На PROLOG легко создать и семантические представления, в чем мы сможем убедиться при описании падежных фреймов в этом разделе. Семантические представления также можно реализовать либо с помощью теории предикатов первого порядка, либо на основе метаинтерпретатора для другого представления, как было предложено в подразделе 14.7.4. И, наконец, семантический вывод, в том числе объединение, ограничение и наследование в концептуальных графах можно напрямую описать на языке PROLOG, в чем читатель сможет убедиться, прочитав подраздел 14.9.3.

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

Концептуальные графы, представленные на рис. 6.11, на языке PROLOG можно описать следующим образом.

bird(X), flies(X).

dog(X), color (X, Y), brown(У).

child(X), parents(X, Y, Z) , father(Y), mother(Z).

Здесь X, Y и Z - переменные, связанные с соответствующими объектами. Как было указано в разделе 14.6, к параметрам можно добавить информацию о типах. С помощью вариации предикатов isa можно также определить иерархию типов.

Падежные фреймы, введенные в подразделе 13.3.2, тоже очень легко построить на языке PROLOG. С каждым глаголом связывается список семантических отношений. Среди них могут быть агенты, инструменты и объекты. Ниже будут рассмотрены примеры для глаголов give (давать) и bite (кусать). Например, глагол give может быть связан с подлежащим, дополнением и непрямым дополнением. Очевидным примером реализации этих структур является английское предложение "John gives Mary the book" (Джон дает Мэри книгу). Применяемые по умолчанию значения можно определить в падежном фрейме, связав их с соответствующими переменными. Например, для глагола bite (кусать) можно определить используемый по умолчанию инструмент - teeth (зубы) - и указать, что инструмент для кусания (teeth) принадлежит агенту. Падежные фреймы для этих двух глаголов могут иметь следующий вид.

verb(give,

[human (Subject),

Глава 14. Введение в PROLOG 671

agent (Subject, give), act_of_giving (give), object (Object, give), inanimate (Object), recipient (Ind_obj, give), human (Ind_obj) ] ).

verb(bite,

[animate (Subject),

agent (Subject, Action), act_of_biting (Action), object (Object, Action), animate (Object), instrument (teeth, Action), part_of (teeth. Subject) ] ).

Логическое программирование предоставляет широкие возможности для построения грамматик и представления семантических значений. Далее на PROLOG будут построены рекурсивные анализаторы, а затем к ним будут добавлены семантические ограничения.

14.9.2. Рекурсивный анализатор на языке PROLOG

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

Sentence^>NounPhrase VerbPhrase, NounPhrasei-^Noun, NounPhrase

Добавим к этим правилам грамматики небольшой словарь.

Article(a), Articled he), Noun(man), Noun(dog), Verb(likes), Verb (bites).

На рис. 14.9 показано дерево грамматического разбора предложения "The man bites the dog", в котором связь and соответствует конъюнкции в правилах грамматики. Эти правила естественным образом описываются на PROLOG. Например, предложение sentence - это именная конструкция nounphrase, за которой следует глагольная конструкция verbphrase.

sentence(Start,End) :- nounphrase(Start, Rest), verbphrase(Rest, End).

Каждое правило на PROLOG зависит от двух параметров, первый из которых представляет собой последовательность слов в форме списка. Правило проверяет, является ли некоторая начальная часть списка допустимой частью речи. Оставшийся суффикс списка должен соответствовать второму параметру, поскольку анализ предложений выполняет-

672 Часть VI. Языки и технологии программирования для искусственного интеллекта

ся слева направо. Если правило описания предложения срабатывает успешно, то второй параметр предиката sentence представляет собой оставшуюся часть предложения, полученную после разбора фраз nounphrase и verbphrase. Если список представляет собой корректное предложение, то в остатке получается пустой список [ ]. Для глагольной и именной конструкции определяются две альтернативные формы описания.

Рис. 14.9. Дерево грамматического разбора И/ИЛИ для предложения "The man bites the dog "

Для простоты само предложение тоже описывается в виде списка [the, man, bites, the, dog]. Список разделяется на составляющие и передается различным грамматическим правилам для проверки синтаксической корректности. Обратите внимание на то, как выполняется проверка соответствия шаблонам для списка в вопросительном предложении. Сначала отбрасывается голова списка или голова со вторым элементом, а предикату передается оставшаяся часть списка и т.д. Предикат utterance в качестве параметра получает подлежащий анализу список и вызывает правило sentence. При этом второй параметр правила инициализируется пустым списком [ ]. Полная грамматика определяется следующим образом.

utterance(X) :- sentence(X, [ ]).

sentence(Start, End) :- nounphrase(Start, Rest), verbphrase(Rest,

End) .

nounphrase([Noun|End], End) :- noun(Noun).

nounphrase([Article, Noun|End], End) :- article(Article),

noun(Noun).

verbphrase([Verb|End], End) :- verb(Verb).

verbphrase([VerbJRest], End) :- verb(Verb), nounphrase(Rest, End).

article(a).

article(the).

noun(man).

noun(dog).

verb(likes).

verb(bites).

Теперь можно проверять корректность построения конкретных предложений.

?- utterance([the, man, bites, the, dog]). Yes

Глава 14. Введение в PROLOG

673

?- utterance([the, man, bites, the]), no

Интерпретатор может также предложить возможные варианты слов для неполных предложениий.

?- utterance([the, man, likes, X]). X = man

X = dog

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

?- utterance(X). [man, likes]

[man, bites] [man, likes, man]

[man, likes, dog] и т.д.

Если пользователь продолжает запрашивать решения, то в результате он получит все возможные корректно сконструированные предложения, которые могут быть сгенерированы на основе заданных правил грамматики и словаря. Заметим, что PROLOG выполняет поиск в глубину слева направо.

Правила грамматики - это спецификация корректных конструкций выражений в данном подмножестве легитимных предложений английского языка. Код на языке PROLOG представляет этот набор логических спецификаций. Интерпретатору передаются запросы об этом наборе. Таким образом, ответом является функция от спецификации и заданного вопроса. В этом состоит основное преимущество вычислений на языке, который сам представляет собой систему доказательства теорем на основе спецификаций. Более подробная информация о PROLOG как системе доказательства теорем приводится в главе 12.

Предыдущий пример можно естественным образом расширить, добавив к нему условия согласованности форм существительного и глагола. Тогда для каждого элемента словаря необходимо указать форму этого слова в единственном и множественном числе, а для предикатов nounphrase и verbphrase ввести дополнительный параметр, отражающий числовую форму number данной фразы. В этом случае существительное в единственном числе должно быть связано с глаголом в форме единственного числа.

Контекстная зависимость существенно повышает мощность грамматики. Приведенная выше версия реализует контекстно-независимую грамматику. Теперь построим контекстно-зависимую грамматику на языке PROLOG (раздел 13.2). В ней сохраняется контекстная информация, необходимая для проверки соответствия формы числа. Такая модификация достигается за счет расширения предыдущего кода.

utterance(X) :- sentence(X, [ ]).

sentence(Start, End) :- nounphrase(Start, Rest, Number), verbphrase(Rest, End, Number).

674 Часть VI. Языки и технологии программирования для искусственного интеллекта

nounphrase([Noun|End] , End, Number) :- noun(Noun, Number). nounphrase([Article, Noun|End], End, Number) :- noun(Noun, Number),

article(Article, Number).

verbphrase([Verb|End], End, Number) :- verb(Verb, Number). verbphrase([Verb|Rest], End, Number) :- verb(Verb, Number),

nounphrase(Rest, End, _) . article(a, singular). article(these, plural). article(the, singular). article(the, plural). noun(man, singular). noun(men, plural). noun(dog, singular). noun(dogs, plural). verb(likes, singular). verbdike, plural). verb(bites, singular). verb(bite, plural).

Теперь снова протестируем предложения.

?- utterance([the, men, like, the, dog]).

yes

?- utterance([the, men, likes, the, dog]).

no

На второй запрос получен отрицательный ответ, поскольку существительное men и глагол likes не согласуются по числу. Если в качестве целевого утверждения ввести

?- utterance([the, men|X]).,

то этот предикат с помощью параметра X вернет все глагольные конструкции, дополняющие фразу "the men...", в которых числовая форма существительных и глаголов будет согласована.

В рассмотренном примере взятые из словаря параметры обеспечивают дополнительную информацию о значениях слов в предложении. Обобщая этот подход, можно построить мощный грамматический анализатор естественного языка. В словарь можно включать все новую и новую информацию о членах предложения, создавая базу знаний о значениях слов английского языка. Например, люди являются одушевленными и социальными объектами, а собаки - одушевленными и несоциальными. Тогда можно добавить новые правила типа "Социальные объекты не кусают одушевленных несоциальных существ". Это позволит исключить предложения типа [the, man, bites, the, dog]. Если же несоциальный объект больше не является одушевленным, то его, конечно же, могут съесть в ресторане.

14.9.3. Рекурсивный анализатор на основе семантических сетей

Теперь расширим множество контекстно-зависимых правил грамматики, включив в него условия семантической согласованности. Это можно сделать, определив для падежных фреймов глаголов соответствующие семантические описания подлежащих и дополнений. Затем ограничим полученные подграфы семантических сетей, обеспечив их взаимную согласованность. Это достигается с помощью таких операций над графами, как объединение и ограничение. Они выполняются для каждой части графа, возвращаемой в качестве дерева разбора.

Глава 14. Введение в PROLOG 675

Сначала представим правила грамматики. Заметим, что предикат самого верхнего уровня utterance возвращает не просто предложение, а граф предложения Sentence_graph. Предикаты компонентов отношений фамматики (nounphrase и verbphrase) вызывают предикат j oin для слияния офаничений соответствующих графов.

utterance(X, Sentence_graph) :-

sentence(X, [ ], Sentence_graph). sentence(Start, End, Sentence_graph) :-

nounphrase(Start, Rest, Subject_graph),

verbphrase(Rest, End, Predicate_graph),

join([agent(Subject_graph)], Predicate_graph, Sentence_graph). nounphrase([Noun | End], End, Noun_phrase_graph) :-

noun(Noun, Noun_phrase_graph). nounphrase([Article, Noun | End], End, Noun_phrase_graph) :-

article(Article),

noun(Noun, Noun_phrase_graph). verbphrase([Verb | End], End, Verb_phrase_graph) :-

verb(Verb, Verb_phrase_graph). verbphrase([Verb | Rest], End, Verb_phrase_graph) :-

verb(Verb, Verb_graph),

nounphrase(Rest, End, Noun_phrase_graph),

join([object(Noun_phrase_graph)], Verb_graph, Verb_phrase_graph).

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

join(X, X, X). join(A, В, С) :-

isframe(A), isframe(B), !,

join_frames(А, В, С, not_joined). join(A, В, С) :-

isframe(A), is_slot((B), !,

join_slot_to_frame(В, А, С). join(A, В, С) :-

isframe(B), is_slot(A), !,

join_slot_to_frame(А, В, С). join(A, В, С) :-

is_slot(A), is_slot(B), !,

join_slots(А, В, С).

Предикат join_frames рекурсивно проверяет соответствие каждой ячейки (свойства) первого фрейма ячейкам второго. Предикат join_slot_to_f rame получает в качестве параметров ячейку и фрейм и находит в этом фрейме ячейки, соответствующие первому параметру. Предикат join_slots проверяет соответствие двух ячеек с учетом иерархии типов.

join_frames([А | В], С, D, ОК) :-

join_slot_to_frame(A, С, Е) , !,

join_frames(В, Е, D, ok). join_frames([ А | В], С, [А | D], ОК) :-

join_frames(В, С, D, ОК), !. join_frames([], A, A, ok).

676 Часть VI. Языки и технологии программирования для искусственного интеллекта

join_slot_to_frame(A, [В | С], [D | С]) :-

join_slots(A, B, D).' join_slot_to_frame(A, [B | C], [B | D]) :-

join_slot_to_frame(A, C, D). join_slots(A, B, D) :-

functor(A, FA, _), functor(B, FB, _),

match_with_inheritance(FA, FB, FN),

argd, A, Value_a) , arg(l, B, Value_b) ,

join(Value_a, Value_b, New_value),

D =.. [FN | [New_value]]. isframe([_ | _]). isframe([ ]). is_slot(A) :- functor(A, _, 1).

И, наконец, создадим словарь, представляющий собой иерархию иерархий, и опишем падежные фреймы для глаголов. В рассматриваемом примере будем использовать простую иерархию, в которой перечислены все корректные специализации. Третьим аргументом предиката match_with_inheritance является общая специализация первых двух. Более жизненная реализация должна содержать граф иерархий, на котором выполняется поиск общих специализаций. Предлагаем читателю выполнить это в качестве упражнения.

match_with_inheritance(X, X, X). match_with_inheritance(dog, animate, dog). match_with_inheritance(animate, dog, dog). match_with_inheritance(man, animate, man). match_with_inheritance(animate, man, man), article(a) . article(the). noun(fido, [dog(fido)]). noun(man, [man(X)]). noun(dog, [dog(X)]).

verb(likes, [action([liking(X)]), agent([animate(X)]), object (animate (Y) ] ) ] ) .

verb(bites, [action([biting(Y)]), agent([dog(X)]), object (animate(Z)])]).

Теперь проанализируем несколько предложений и выведем граф Sentence_graph.

?- utterance([the, man, likes, the, dog], X).

X= [actionf[liking(_54)]), agent([man(_23)]), object([dog(_52)])]. ?- utterance([fido, likes, the, man], X). X= [action([liking(_62)]), agent([dog(fido)]), object ( [man (_70) ])] .

?- utterance([the, man, bites, fido], Z) . no

В первом предложении утверждается, что некоторый человек, имя которого неизвестно, любит безымянную собаку. Последнее предложение, несмотря на свою синтаксическую корректность, не удовлетворяет семантическим ограничениям, поскольку агентом глагола bites должна быть собака. Во втором предложении конкретная собака Фидо любит безымянного человека. В последнем примере проверим, может ли Фидо укусить безымянного человека.

?- utterance([fido, bites, the, man], X). X= [action([biting(_12)]), agent([dog(fido)]), object ( [man (_17) ])] .

Глава 14. Введение в PROLOG 677

Этот анализатор можно расширять во многих интересных направлениях, в частности, добавить к нему прилагательные, наречия и вводные фразы, либо позволить использовать сложные предложения. Эти добавления нужно включить в граф предложения. Каждый элемент словаря может иметь несколько значений, допустимых только при соблюдении некоторых общих требований к предложению. Дополнительные примеры приводятся в перечне упражнений.

14.10. Резюме и дополнительная литература

В таких традиционных языках программирования, как FORTRAN и С, логика описания задачи и управление выполнением алгоритма решения неразрывно связаны друг с другом. Программа на таком языке - это просто последовательность действий, выполняемых для получения ответа. Такие языки называются процедурными (procedural). В PROLOG логика описания задачи отделена от ее выполнения. Как следует из глав 5-7, на это существует множество причин.

Не стоит и говорить, что PROLOG еще не достиг состояния полного совершенства. Однако уже сейчас можно показать, что логическое программирование, реализуемое на языке PROLOG, обладает некоторыми преимуществами непроцедурной семантики. Рассмотрим пример декларативной природы PROLOG. Возьмем предикат append.

append([ ], L, L) .

append([X|T], L, [X|NL]) :- append(T, L, NL).

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

?- append([a, b, с], [d, e], Y). Y = [а, Ь, с, d, e]

Выполнение предиката append не рекурсивно по хвосту, поскольку конкретные значения переменных достигаются после успешного завершения рекурсивного вызова. Следовательно, после завершения рекурсивного вызова X располагается в голове списка [X | NL]. Для этого каждый вызов необходимо записывать в стек PROLOG. Рассмотрим следующий пример трассировки.

append([ ], L, L).

append([Х|Т], L, [X|NL]) :- append(T, L, NL).

?- append([a, b, c] , [d, e] , Y) .

try match 1, fail [a, b, c]*[ ]

match 2, X is a, T is [b, c], L is [d, e], call append([b, c], [d, e] , NL)

try match 1, fail [b, c]*[ ]

match 2, X is b, T is [c], L is [d, e], call append([c], [d, e] , NL)

try match 1, fail [c]*[ ]

match 2, X is c, T is [ ], L is [d,e], call append{[ ], [d, e] , NL)

678 Часть VI. Языки и технологии программирования для искусственного интеллекта

match 1, L is [d, e] (for BOTH parameters), yes

NL] is [c, d, e] NL] is [b, c, d, e]

yes, N is [d, e] , [X yes, NL is [c, d, e] , [X

yes, NL is [b, c, d, e] , [x|NL] is [a, b, c, d, e]

Y = [a, b, c, d, e] , yes

В большинстве алгоритмов PROLOG параметры предикатов можно разделить на "входные" и "выходные", поскольку в большинстве определений предполагается, что при вызове предиката некоторые параметры должны быть связаны, а другие- нет. Но это не обязательно так. На самом деле параметры в PROLOG вообще не делятся на входные и выходные. Код на PROLOG - это просто набор спецификаций истинных утверждений или описание логики ситуации. В частности, предикат append задает такое отношение между тремя списками, при котором третий список является результатом вставки первого в начало второго.

Чтобы проиллюстрировать это утверждение, рассмотрим разные варианты использования предиката append.

?- append([a, b], [с], [a, b, с]).

yes

?- append([a], [с], [a, b, с]).

по

?- append(X, [b, с], [а, Ь, с]).

X = [а]

?- append(X, Y, [а, Ь, с]).

х = [ ]

Y = [а, Ь, с]

X = [а]

Y = [Ь, с]

X = [а, Ь]

Y = [С]

X = [а, Ь, с]

Y = [ ]

В последнем запросе PROLOG возвращает все списки X и Y, которые в результате конкатенации дают список [ а, b, с ] - всего четыре пары списков. Как было указано выше, append - это описание логики отношения между тремя списками. Результат работы интерпретатора зависит от запроса.

Решение задач на основе множества спецификаций корректных отношений в данной предметной области в сочетании с работой системы доказательства теорем связано со многими интересными и важными аспектами. Такое средство находит свое применение в столь разнообразных областях знаний, как понимание естественного языка, обработка баз данных, написание компиляторов и машинное обучение. Работу интерпретатора PROLOG нельзя до конца осмыслить без осознания понятий из области доказательства теорем резолюции, особенно процесса опровержения хорновских дизъюнктов, описанного в главе 12.

PROLOG - это язык программирования общего назначения. В связи с ограниченностью объема книги в этой главе были опущены его многочисленные важные аспекты. Любознательному читателю автор рекомендует познакомиться со многими замечатель-

Глава 14. Введение в PROLOG 679

ными книгами, в том числе [Clocksin и Mellish, 1984], [Maier и Warren, 1988], [Sterling и Shapiro, 1986], [O'Keefe, 1990], [VanLe, 1993], [Lucas, 1996] или [Ross, 1989]. В работах [King, 1991], [Gazdar и Mellish, 1989] описано применение языка PROLOG во многих важных приложениях теории искусственного интеллекта.

Более полное описание типов PROLOG, а также предложения по созданию алгоритмов проверки соответствия типов приводятся в [Mycroft и O'Keefe, 1984]. Применение стеков правил и деревьев доказательств при разработке экспертных систем описано в [Sterling и Shapiro, 1986].

Во многих книгах рассматриваются вопросы построения таких представлений искусственного интеллекта, как семантические сети, фреймы и объекты [Walker и др., 1987], [Malpas, 1987].

Средства представления языка PROLOG настолько органично подходят для решения задач понимания естественного языка, что PROLOG часто используют для моделирования таких языков. Первый интерпретатор PROLOG был разработан для анализа французского языка на основе грамматики метаморфоз (metamorphosis grammar) [Colmerauer, 1975]. В [Pereira и Warren, 1980] создана грамматика определенных дизъюнктов (definite clause grammar). Свой вклад в развитие этой области исследований внесли работы [Dahl, 1977], [Dahl и McCord, 1983], [McCord, 1982], [McCord, 1986], [Sowa, 1984], [Walker и др., 1987].

Интеллектуальные корни языка PROLOG уходят к теоретическим принципам использования логики для описания задач. В этой области автор особенно рекомендует книги [Kowalski, 1979a, 19796].

Неослабевающий интерес вызывают и другие, отличные от PROLOG, среды логического программирования. К ним относятся параллельные языки логического программирования [Shapiro, 1987]. В [Nadathur и Tong, 1999] описан Lambda-PROLOG - язык логического программирования более высокого уровня. В работе [Hill и Lloyd, 1994] предложен язык Goedel, а в [Somogyi и др., 1995] - язык Mercury. Goedel и Mercury - две относительно новые среды декларативного логического программирования.

14.11. Упражнения

Создайте на языке PROLOG реляционную базу данных. Представьте кортежи данных в

виде фактов, а ограничения - в виде правил. В качестве примеров можно рассмотреть

базу данных товаров в универмаге или записей о сотрудниках в отделе кадров.

Напишите на языке PROLOG программу, решающую задачу Вирта "I am my own

grandfather" (Я - мой собственный дедушка) (глава 2, упражнение 12).

Напишите на PROLOG программу проверки принадлежности элемента списку. Что

произойдет, если элемент не принадлежит списку? Дополните эту спецификацию та

ким образом, чтобы она позволяла разбивать список на элементы.

Разработайте на PROLOG программу unique (Bag, Set), которой передается па

раметр Bag (список, который может содержать повторяющиеся элементы), а она

возвращает параметр Set (множество без повторяющихся элементов).

Напишите на PROLOG программу вычисления количества элементов в списке

(список в списке считается одним элементом). Разработайте программу подсчета

атомов в списке (вычисления количества элементов во всех подсписках). Совет:

можно воспользоваться несколькими метапредикатами типа atom ().

680 Часть VI. Языки и технологии программирования для искусственного интеллекта