Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 104
Текст из файла (страница 104)
Например, высказывания ЪИеэ (х, тсеСгеагп) и Ы)гез (у, гсесгеагп) представляют собой переименования по отношению друг к другу, поскольку они отличаются лишь выбором имени переменной, х или у; они имеют одинаковый смысл — все любят мороженое. Листинг 92. Концептуально простой, но очень неэффективный алгоритм прямою логического вывода. В кал(пой итерации ои добавляет к базе знаний кв все атомарные высказывания, которые мо~ут быть выведены за один этап из импликационных высказываний и атомарных высказываний, которые уже находятся в базе знаний ецпссзоп Ров-РС-Азк(кВ, а) гесигпв подстановка или значение ее1зе хприев: КВ, база знаний — множество определенных выражениЙ первого порядка а, запрос — атомарное высказывание 1оса1 чаг1ап1евг пеы, новые высказывания, выводимые в каждой итерации гереас ппсз1 множество пег не пусто пеы г — () Еог васи высказывание г зп КВ цо (Рг Л .. Л Р О Ц) Ч вЂ” Бгацо)асбЕЭЕ-АРаГС(Г) Еог еасоф подстановка В, такая что яц)ээс(В,ргл...лги) Вц)эзе(В,рч'л...лр„') для некоторых рг',...,р„' в базе знаний КВ ь- Вц)ззе(В, о) 1Е выражение П' не является переименованием некоторого высказывания, которое уже находится в КВ, или рассматривается как элемент множества пеы енеп бо добавить гг' к множеству пеы ф < — пп1ЕУ(о', а) зЕ значение ф не представляет собой Еа11 еиеп гессгп ф добавить множество пеы к базе знаний КВ гесигп Еазэе 393 Глава 9.
Логический вывод в логике первого порядка Для иллюстрации работы алгоритма рОГ.-РО-Лэ)с воспользуемся описанной выше задачей доказательства преступления. Импликационными высказываниями являются высказывания, приведенные в уравнениях 9.3, 9.б — 9.8. Требуются следующие две итерации. ° В первой итерации правило 9.3 имеет невыполненные предпосылки. Правило 9.6 выполняется с подстановкой (хуМ,) и добавляется высказывание Яе11э ( Исаа г, и,, Лспо) . Правило 9Д выполняется с подстановкой (хуМ,) и добавляется высказывание Меароп (М,) .
Правило 9.8 выполняется с подстановкой (хгмопо) и добавляется высказывание Лоаг11е(Мопс) . ° На второй итерации правило 9.3 выполняется с подстановкой (х/йсеас, у/м,, зулопо) и добавляется высказывание Огйтзпа1 ( ьгеас) . Сформированное дерево доказательства показано на рис. 9.2. Обратите внимание на то, что в этот момент невозможны какие-либо новые логические выводы, поскольку каждое высказывание, заключение которого можно было бы найти с помощью прямого логического вывода, уже явно содержится в базе знаний кв. Такое состояние базы знаний называется фиксированной точкой (бхед ро1пг) в процессе логического вывода. Фиксированные точки, достигаемые при прямом логическом выводе с использованием определенных выражений первого порядка, аналогичны фиксированным точкам, возникающим при пропозициональном прямом логическом выводе (с.
315); основное различие состоит в том, что фиксированная точка первого порядка может включать атомарные высказывания с квантором всеобщности. Рис. 9.2. Дерево докизательства, сформированное путем прямого логического вывода в примере доказательства преступления. Первоначальные факты показаны на низкнем уровне, факты, выведенные логическим путем в первой итерации, — на среднем уровне, а факт, логически выведенный во второй итерации,— на верхнем уровне Свойства алгоритма РОГ -РО-Ав)с проанализировать несложно. Во-первых, он является непротиворечивым, поскольку каждый этап логического вывода представляет собой применение обобщенного правила отделения, которое само является непротиворечивым. Во-вторых, он является полным применительно к базам знаний 394 Часть Ш. Знания и рассуждения с определенными выражениями; это означает, что он позволяет ответить на любой запрос, ответы на который следуют из базы знаний с определенными выражениями.
Для баз знаний Ра(а!оя, которые не содержат функциональных символов, доказательство полноты является довольно простым. Начнем с подсчета количества возможных фактов, которые могут быть добавлены, определяющего максимальное количество итераций. Допустим, что )г — максимальная арность (количество параметров) любого предиката, р — количество предикатов и и — количество константных символов. Очевидно, что может быть не больше чем рп" различных базовых фактов, поэтому алгоритм должен постичь фиксированной точки именно после стольких итераций.
В таком случае можно применить обоснование приведенного выше утверждения, весьма аналогичное доказательству полноты пропозиционального прямого логического вывода (см. с. 315). Подробные сведения о том, как осуществить переход от пропозициональной полноты к полноте первого порядка, приведены применительно к алгоритму резолюции в разделе 9.5. При его использовании к более общим определенным выражениям с функциональными символами алгоритм Ь'ОГ.-КС-Аэ)с может вырабатывать бесконечно большое количество новых фактов, поэтому необходимо соблюдать исключительную осторожность. Для того случая, в котором из базы знаний следует ответ на высказывание запроса д, необходимо прибегать к использованию теоремы Эрбрана для обеспечения того, чтобы алгоритм мог найти доказательство (случай, касаюшийся резолюции, описан в разделе 9.5).
А если запрос не имеет ответа, то в некоторых случаях может оказаться, что не удается нормально завершить работу данного алгоритма. Например, если база знаний включает аксиомы Пеано: иагыит(0) Чл ))аепит(и) =-> згаеьагп(я(п)) то в результате прямого логического вывода будут добавлены факты ьгасвгии( Я( О ) ), )()асьгшл(я(я(О) ) ), ыасвгшв(я(я(я(О) ) ) ) и тд.
Вообше говоря, избежать возникновения этой проблемы невозможно. Как и в обшем случае логики первого порядка, задача определения того, следуют ли высказывания из базы знаний, сформированной с использованием определенных выражений, является полуразрешимой. Эффективный прямой логический вывод Алгоритм прямого логического вывода, приведенный в листинге 9.2, был спроектирован не с целью обеспечения эффективного функционирования, а, скорее, с целью упрощения его понимания.
Существуют три возможных источника осложнений в его работе. Во-первых, "внутренний цикл'* этого алгоритма предусматривает поиск всех возможных унификаторов, таких, что предпосылка некоторого правила унифицируется с подходящим множеством фактов в базе знаний. Такая операция часто именуется ск согласованием с шаблоном и может оказаться очень дорогостояшей. Во-вторых, в этом алгоритме происходит повторная проверка каждого правила в каждой итерации для определения того, выполняются ли его предпосылки, даже если в базу знаний в каждой итерации вносится лишь очень немного дополнений. В-третьих, этот алгоритм может вырабатывать много фактов, которые не имеют отношения к текущей цели.
Устраним каждый из этих источников неэффективности по очереди. Глава 9. Логический вывод в логике первого порядка 395 Согласование правил с известными фактами Проблема согласования предпосылки правила с фактами, хранящимися в базе знаний, может показаться достаточно простой.
Например, предположим, что требуется применить следующее правило: Мдпв11е(х) ~ Иеароп(х) Для этого необходимо найти все факты, которые согласуются с выражением мбвв11е(х); в базе знаний, индексированной подходящим образом, это можно выполнить за постоянное время в расчете на каждый факт. А теперь рассмотрим правило, подобное следующему: Мдвв11е (х) л Онпв (Мапо, х) =ь Яе11в (Неве, х, Иппп) Найти все объекты, принадлежащие государству Ноуноу, опять-таки можно за постоянное время в расчете на каждый объект; затем мы можем применить к каждому объекту проверку, является ли он ракетой.
Но если в базе знаний содержится много сведений об объектах, принадлежащих государству Ноуноу, и лишь немного данных о ракетах, то было бы лучше вначале найти все ракеты, а затем проверить, какие из них принадлежат Ноуноу. Это — проблема Ъ. упорядочения конъюнктов: поиск упорядочения, позволяющего решать конъюнкты в предпосылке правила таким образом, чтобы общая стоимость решения была минимальной. Как оказалось, задача поиска оптимального упорядочения является )ч(Р-трудной, но имеются хорошие эвристики. Например, эвристика с наиболее ограниченной переменной, применявшаяся при решении задач СВР в главе 5, подсказывает, что необходимо упорядочить конъюнкты так, чтобы вначале проводился поиск ракет, если количество ракет меньше по сравнению с количеством всех известных объектов, принадлежащих государству Ноуноу.
Между процедурами согласования с шаблоном и удовлетворения ограничений действительно существует очень тесная связь. Каждый конъюнкт может рассматриваться как ограничение на содержащиеся в нем переменные; например, Мбвв11е(х) — это унарное ограничение на х. Развивая эту идею, можно прийти к выводу, что о(е суи(ествует возможность представить любую задачу СБР с конечной областью определения как единственное определенное выражение наряду с некоторыми касаюшииися ее базовыми фактами. Рассмотрим приведенную на рис.
5.! задачу раскраски карты, которая снова показана на рис. 9.3, а. Эквивалентная формулировка в виде одного определенного выражения привелена на рис. 9.3, б. Очевидно, что заключение Со1осаЬ1а О можно вывести из этой базы знаний, только если данная задача С5Р имеет решение. А поскольку задачи С5Р, вообще говоря, включают задачи 3-5АТ в качестве частных случаев, на основании этого можно сделать вывод, что св задача согласования определенного выражения с множеством фактов является ИР-трудной.
То, что во внутреннем цикле алгоритма прямого логического вывода приходится решать ХР-трудную задачу согласования, может показаться на первый взгляд довольно неприятным. Тем не менее, есть следующие три фактора, благодаря которым эта проблема предстает немного в лучшем свете. ° Напомним, что большинство правил в базах знаний, применяемых на практике, являются небольшими и простыми (подобно правилам, используемым в примере доказательства преступления), а не большими и сложными (как в формулировке задачи СБР, приведенной на рис. 9.3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
