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