Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 105
Текст из файла (страница 105)
В мире пользователей 396 Часть П1. Знания и рассуждения баз данных принято считать, что размеры правил и арности предикатов не превышают некоторого постоянного значения, и принимать во внимание только Ъ. сложность данных, т.е. сложность логического вывода как функции от количества базовых фактов в базе данных. Можно легко показать, что обусловленная данными сложность в прямом логическом выводе определяется полиномиальной зависимостью. Р)) (ша, и)) л 0$(уга, за) л 01В (и), 9) л Оф(ай за) л Рф(9, пзш) л 09) (9, за) л Ру((пзв, и) л 0)(((пззг за) л Ру) (и за) ~ Со(огаЫе() РЯ(Яед, В!це) 0)(((Кед, бгееп) 09) (Сгееп, Кед) 0$(бгееп, В)ие) Рф(В(ие, Кед) РЯ(В)ие, бгееп) Рис.
9.3. Иллюстрация связи между процессами согласования с шаблоном и удовлетворения ограничений: граф ограничений для раскрашивания карты Австралии (см. рис. 5. 1) (а); задача СИР раскрашивания карты, представлентт в виде единственного определенного выражения (б). Обратите вничание на пю, что области определенцн переменных заданы неявно с помощью констант, приведенных в базовых фактах для предиката )зь ЕЕ ° Могут рассматриваться подклассы правил, для которых согласование является наиболее эффективным.
По сути, каждое выражение на языке Па)а)оя может рассматриваться как определяющее некоторую задачу СИР, поэтому согласование будет осуществимым только тогда, когда соответствующая задача СБР является разрешимой. Некоторые разрешимые семейства задач СЗР описаны в главе 5. Например, если граф ограничений (граф, узлами которого являются переменные, а дугами — ограничения) образует дерево, то задача СЯР может быть решена за линейное время.
Точно такой же результат остается в силе для согласования с правилами. Например, если из карты, приведенной на рис. 9.3, будет удален узел Бл, относящийся к Южной Австралии, то результирующее выражение примет следуюший вид: гззЕЕ)ыа,пе) л )ЗхЕЕ)пс,гг) л ПЗЕЕ)о,паы) л ))1ЕЕ)паы, г) ~ Со1окаЬ1е1) что соответствует сокрашенной задаче СБР, показанной на рис. 5.7. Для решения задачи согласования с правилами могут непосредственно применяться алгоритмы решения задач СИР с древовидной структурой. ° Можно приложить определенные усилия по устранению излишних попыток согласования с правилами в алгоритме прямого логического вывода, что является темой следующего раздела. 397 Глава 9.
Логический вывод в логике первого порядка Инкрементный прямой логический вывод Когда авторы демонстрировали в предыдущем разделе на примере доказательства преступления, как действует прямой логический вывод, они немного схитрили; в частности, не показали некоторые из согласований с правилами, выполняемые алгоритмом, приведенным в листинге 9.2. Например, во второй итерации правило Мдяя11е(х) ~ меяроп (х) согласуется с фактом )чу яя11е ()ч, ) (еще раз), и, безусловно, при этом ничего не происходит, поскольку заключение (ееароп ()ч,) уже известно. Таких излишних согласований с правилами можно избежать, сделав следующее наблюдение: св камсдый новый факт, выведенный в итерации е, должен оьопь получен по меньшей мере из одного нового факта, выведенного в итерации с-1. Это наблюдение соответствует истине, поскольку любой логический вывод, который не требовал нового факта из итерации г-1, уже мог быть выполнен в итерации г-1.
Такое наблюдение приводит естественным образом к созданию алгоритма инкрементного прямого логического вывода, в котором в итерации Г проверка правила происходит, только если его предпосылка включает конъюнкт р„который унифицируется с фактом р, ', вновь выведенным в итерации г-1. Затем на этапе согласования с правилом значение р, фиксируется для согласования с р, ', но при этом допускается, чтобы остальные конъюнкты в правиле согласовывались с фактами из любой предыдущей итерации.
Этот алгоритм в каждой итерации вырабатывает точно такие же факты, как и алп)- ритм, приведенный в листинге 9.2, но является гораздо более эффективным. При использовании подходящей индексации можно легко выявить все правила, которые могут быть активизированы любым конкретным фактом. И действительно, многие реальные системы действуют в режиме "обновления", при котором прямой логический вывод происходит в ответ на каждый новый факт, сообщенный системе с помощью операции те11.
Операции логического вывода каскадно распространяются через множество правил до тех пор, пока не достигается фиксированная точка, а затем процесс начинается снова, вслед за поступлением каждого нового факта. Как правило, в результате добавления каждого конкретного факта в действительности активизируется лишь небольшая до ьч правил в базе знаний. Это означает, что при повторном конструировании частичных согласований с правилами, имею~ними некоторые невыполненные предпосылки, выполняется существенный объем ненужной работы.
Рассматриваемый здесь пример доказательства преступления слишком мал, чтобы на нем можно было наглядно показать такую ситуацию, но следует отметить, что частичное согласование конструируется в первой итерации между следующим правилом: лмекдсап(х) л (ееароп(у) л ве11я(х,у, г) л нояе11е(я) =ь сядтзпа1(х) и фактом Атехйпап(иеяг). Затем это частичное согласование отбрасывается и снова формируется во второй итерации (в которой данное правило согласуется успешно). Было бы лучше сохранять и постепенно дополнять частичные согласования по мере поступления новых фактов, а не отбрасывать их.
В гк ге(е-алгоритме' была впервые предпринята серьезная попытка решить эту проблему. Алгоритм предусматривает предварительную обработку множества пра- ' Здесь ю(е — латинское слово, которое переводится как сеть и читается по-русски "реть", а по-английски — "рити". Часть В Е Знания и рассуждения вил в базе знаний для формирования своего рода сети потока данных (называемой ге(е-сетью), в которой каждый узел представляет собой литерал из предпосылки какого-либо правила.
По этой сети распространяются операции связывания переменных и останавливаются после того, как в них не удается выполнить согласование с каким-то литералом. Если в двух литералах некоторого правила совместно используется какая-то переменная (например, Яе22е(х,у, а) д ноес51е(з) в примере доказательства преступления), то варианты связывания из каждого литерала пропускаются через узел проверки равенства. Процессу связывания переменных, достигших узла и-арного литерала, такого как 5е22е(х,у, а), может потребоваться перейти в состояние ожидания того, что будут определены связывания для других переменных, прежде чем он сможет продолжаться.
В любой конкретный момент времени состояние ге(е-сети охватывает все частичные согласования с правилами, что позволяет избежать большого объема повторных вычислений. Не только сами ге(е-сети, но и различные их усовершенствования стали ключевым компонентом так называемых 'ех продукционных систем, которые принадлежат к числу самых первых систем прямого логического вывода, получивших широкое распространение5 В частности, с использованием архитектуры продукционной системы была создана система Хсоп (которая первоначально называлась В1) [1026[.
Система Хсоп содержала несколько тысяч правил и предназначалась для проектирования конфигураций компьютерных компонентов для заказчиков 018!(а! Е((ц!ртеп( Согрога(!оп. Ее создание было одним из первых очевидных успешных коммерческих проектов в развиваюгцейся области экспертных систем. На основе той же базовой технологии, которая была реализована на языке общего назначения Орз-5, было также создано много других подобных систем. Кроме того, продукционные системы широко применяются в ск когнитивных архитектурах (т.е. моделях человеческого мышления), в таких как АСТ [31[ и 5оаг [880). В подобных системах "рабочая память" системы моделирует кратковременную память человека, а продукции образуют часть долговременной памяти.
В каждом цикле функционирования происходит согласование продукций с фактами из рабочей памяти. Продукции, условия которых выполнены, могут добавлять или удалять факты в рабочей памяти. В отличие от типичных ситуаций с большим объемом данных, наблюдаемых в базах данных, продукционные системы часто содержат много правил и относительно немного фактов. При использовании технологии согласования, оптимизированной должным образом, некоторые современные системы могут оперировать в реальном времени болъше чем с миллионом правил.
Не относящиеся к делу факты Последний источник неэффективности прямого логического вывода, повидимому, свойствен самому этому подходу и также возникает в контексте пропозициональной логики (см. раздел 7.5). Прямой логический вывод предусматривает выполнение всех допустимых этапов логического вывода на основе всех известных фактов, даже если они не относятся к рассматриваемой цели. В примере доказательства преступления не было правил, способных приводить к заключениям, не относящимся к делу, поэтому такое отсутствие направленности не вызывало каких-либо проблем.
В других случаях (например, если бы в базу знаний было внесено несколь- " Слово иродукния в названии ирокукнионнвя система обозначает правило "условие-действие". 399 Глава 9. Логический вывод в логике первого порядка ко правил с описанием кулинарных предпочтений американцев и цен на ракеты) алгоритм Рот,-уС-Аэ)с вырабатывал бы много нерелевантных заключений. Один из способов предотвращения формирования нерелевантных заключений состоит в использовании обратного логического вывода, как описано в разделе 9.4. Еше одно, второе решение состоит в том, чтобы ограничить прямой логический вывод избранным подмножеством правил; этот подход обсуждался в контексте пропозициональной логики. Третий подход сформировался в сообшестве пользователей дедуктивных баз данных, для которых прямой логический вывод является стандартным инструментальным средством.
Идея этого подхода состоит в том, чтобы перезаписывать множество правил с использованием информации нз цели так, что в процессе прямого логического вывода рассматриваются только релевантные связывания переменных (принадлежашие к так называемому Ъ.магическому множеству). Например, если целью является Спгтйпа1 (иеас), то правило, приводящее к заключению Схутупа1(х), может быть перезаписано для включения дополнительного конъюнкта, ограничиваюшего значение х, следующим образом: Над1с(х) л Лтегдсап(х) л (аеароп(у) л яе11а(х,у, а) л наас11е(х) ~ сх1тдпа1(х) Факт )чаду с ( й)еа с ) также добавляется в базу знаний. Благодаря этому в процессе прямого логического вывода будет рассматриваться только факт о полковнике Уэсте, даже если база знаний содержит факты о миллионах американцев.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
