Инкрементный прямой логический вывод
Когда авторы демонстрировали в предыдущем разделе на примере доказательства преступления, как действует прямой логический вывод, они немного схитрили; в частности, не показали некоторые из согласований с правилами, выполняемые алгоритмом, приведенным в листинге 9.2. Например, во второй итерации правило
Missile (х) => Weapon (х)
согласуется с фактом Missile (Mi) (еще раз), и, безусловно, при этом ничего не происходит, поскольку заключение Weapon (Мг) уже известно. Таких излишних согласований с правилами можно избежать, сделав следующее наблюдение: каждый новый факт, выведенный в итерации t, должен быть получен по меньшей мере из одного нового факта, выведенного в итерации t-1. Это наблюдение соответствует истине, поскольку любой логический вывод, который не требовал нового факта из итерации t-1, уже мог быть выполнен в итерации t-1.
Такое наблюдение приводит естественным образом к созданию алгоритма инкре-ментного прямого логического вывода, в котором в итерации t проверка правила происходит, только если его предпосылка включает конъюнкт pi5 который унифицируется с фактом Pi1, вновь выведенным в итерации t-1. Затем на этапе согласования с правилом значение Pi фиксируется для согласования с р±', но при этом допускается, чтобы остальные конъюнкты в правиле согласовывались с фактами из любой предыдущей итерации. Этот алгоритм в каждой итерации вырабатывает точно такие же факты, как и алгоритм, приведенный в листинге 9.2, но является гораздо более эффективным.
При использовании подходящей индексации можно легко выявить все правила, которые могут быть активизированы любым конкретным фактом. И действительно, многие реальные системы действуют в режиме "обновления", при котором прямой логический вывод происходит в ответ на каждый новый факт, сообщенный системе с помощью операции Tell. Операции логического вывода каскадно распространяются через множество правил до тех пор, пока не достигается фиксированная точка, а затем процесс начинается снова, вслед за поступлением каждого нового факта.
Как правило, в результате добавления каждого конкретного факта в действительности активизируется лишь небольшая доля правил в базе знаний. Это означает, что при повторном конструировании частичных согласований с правилами, имеющими некоторые невыполненные предпосылки, выполняется существенный объем ненужной работы. Рассматриваемый здесь пример доказательства преступления слишком мал, чтобы на нем можно было наглядно показать такую ситуацию, но следует отметить, что частичное согласование конструируется в первой итерации между следующим правилом:
American (х) л Weapon(y) л Sells (х, у, z) л Hostile(z) => Criminal (х)
и фактом American (West). Затем это частичное согласование отбрасывается и снова формируется во второй итерации (в которой данное правило согласуется успешно). Было бы лучше сохранять и постепенно дополнять частичные согласования по мере поступления новых фактов, а не отбрасывать их.
В rete-алгоритме3 была впервые предпринята серьезная попытка решить эту проблему. Алгоритм предусматривает предварительную обработку множества правил в базе знаний для формирования своего рода сети потока данных (называемой rete-сетью), в которой каждый узел представляет собой литерал из предпосылки какого-либо правила. По этой сети распространяются операции связывания переменных и останавливаются после того, как в них не удается выполнить согласование с каким-то литералом. Если в двух литералах некоторого правила совместно используется какая-то переменная (например, Sells(х,у, z) л Hostlle(z) в примере доказательства преступления), то варианты связывания из каждого литерала пропускаются через узел проверки равенства. Процессу связывания переменных, достигших узла n-арного литерала, такого как Sells (х, у, z), может потребоваться перейти в состояние ожидания того, что будут определены связывания для других переменных, прежде чем он сможет продолжаться. В любой конкретный момент времени состояние rete-сети охватывает все частичные согласования с правилами, что позволяет избежать большого объема повторных вычислений.
Не только сами rete-сети, но и различные их усовершенствования стали ключевым компонентом так называемых продукционных систем, которые принадлежат к числу самых первых систем прямого логического вывода, получивших широкое распространение4. В частности, с использованием архитектуры продукционной системы была создана система Хсоп (которая первоначально называлась R1) [1026]. Система Хсоп содержала несколько тысяч правил и предназначалась для проектирования конфигураций компьютерных компонентов для заказчиков Digital Equipment Corporation. Ее создание было одним из первых очевидных успешных коммерческих проектов в развивающейся области экспертных систем. На основе той же базовой технологии, которая была реализована на языке общего назначения Ops-5, было также создано много других подобных систем.
Кроме того, продукционные системы широко применяются в когнитивных архитектурах (т.е. моделях человеческого мышления), в таких как ACT [31] и Soar [880]. В подобных системах "рабочая память" системы моделирует кратковременную память человека, а продукции образуют часть долговременной памяти. В каждом цикле функционирования происходит согласование продукций с фактами из рабочей памяти. Продукции, условия которых выполнены, могут добавлять или удалять факты в рабочей памяти. В отличие от типичных ситуаций с большим объемом данных, наблюдаемых в базах данных, продукционные системы часто содержат много правил и относительно немного фактов. При использовании технологии согласования, оптимизированной должным образом, некоторые современные системы могут оперировать в реальном времени больше чем с миллионом правил.
Не относящиеся к делу факты
Последний источник неэффективности прямого логического вывода, по-видимому, свойствен самому этому подходу и также возникает в контексте пропозициональной логики (см. раздел 7.5). Прямой логический вывод предусматривает выполнение всех допустимых этапов логического вывода на основе всех известных фактов, даже если они не относятся к рассматриваемой цели. В примере доказательства преступления не было правил, способных приводить к заключениям, не относящимся к делу, поэтому такое отсутствие направленности не вызывало каких-либо проблем. В других случаях (например, если бы в базу знаний было внесено несколько правил с описанием кулинарных предпочтений американцев и цен на ракеты) алгоритм FOL-FC-Ask вырабатывал бы много нерелевантных заключений.
Один из способов предотвращения формирования нерелевантных заключений состоит в использовании обратного логического вывода, как описано в разделе 9.4. Еще одно, второе решение состоит в том, чтобы ограничить прямой логический вывод избранным подмножеством правил; этот подход обсуждался в контексте пропозициональной логики. Третий подход сформировался в сообществе пользователей дедуктивных баз данных, для которых прямой логический вывод является стандартным инструментальным средством. Идея этого подхода состоит в том, чтобы перезаписывать множество правил с использованием информации из цели так, что в процессе прямого логического вывода рассматриваются только релевантные связывания переменных (принадлежащие к так называемому магическому множеству). Например, если целью является Criminal (West), то правило, приводящее к заключению Criminal (х), может быть перезаписано для включения дополнительного конъюнкта, ограничивающего значение х, следующим образом:
Magic (х) л American (х) л Weapon (у) л Sells{x,y,z) л Hostile(z) => Criminal(х)
Факт Magic (West) также добавляется в базу знаний. Благодаря этому в процессе прямого логического вывода будет рассматриваться только факт о полковнике Уэсте, даже если база знаний содержит факты о миллионах американцев. Полный процесс определения магических множеств и перезаписи базы знаний является слишком сложным для того, чтобы мы могли заняться в этой главе его описанием, но основная идея состоит в том, что выполняется своего рода "универсальный" обратный логический вывод от цели для выяснения того, какие связывания переменных нужно будет ограничивать. Поэтому подход с использованием магических множеств может рассматриваться как гибридный между прямым логическим выводом и обратной предварительной обработкой.