Отслеживание зависимостей - Система отслеживания истинности предположений

В главе 15 рассказывалось о том, что в экспертной системе VT для фиксации зависимостей между решениями, принимаемыми в процессе проектирования, используется сеть зависимостей. В такой сети узлы соответствуют присвоению значений конструктивным параметрам, причем между узлами существуют два вида связей-- связи содействия (contributes-to) и связи принуждения (constrains). Узел А содействует узлу В, если значение параметра А появляется в результате вычисления значения В, а узел А принуждает узел В, если значение параметра A запрещает параметру В принимать определенные значения. В дальнейшем для некоторой формализации изложения будем обозначать узлы прописными буквами, а строчными-- значения соответствующих параметров. Например, значение, присваиваемое узлу (параметру) А в какой-либо момент времени, будем обозначать как а.

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

Пусть, например, в сети имеются узлы А и М. Узел А представляет ускорение некоторой детали механизма, а М -- массу этой детали. Оба узла, А и М, содействуют узлу F, который представляет силу, действующую на деталь. Более того, учитывая знакомую всем со школьной скамьи формулу f= та, узлы А и М также и принуждают узел F, поскольку если а и т известны, то значение f определяется этой формулой и не может быть произвольным, т. е. если а - 2 и от = 3, то мы можем присвоить узлу F только значение f= 6. Если же этому узлу уже ранее было присвоено значение f= 7, то сеть переходит в состояние противоречия.

Формула f= та играет роль принудительного ограничения для сети, описанной в этом примере. Если все ограничения в сети удовлетворяются, то она пребывает в состоянии релаксации. Рассмотрим варианты сетей, представленные на рис. 19.1. Сеть а) находится в промежуточном состоянии, поскольку узлу F не присвоено какого-либо определенного значения, сеть б) находится в состоянии релаксации, а сеть в) -- в состоянии противоречия.

Строго говоря, термин "релаксация" относится к сети, а не к теории13. Но сеть есть не что иное, как только представление определенной теории, например сеть а) является представлением теории

F= mа

Т=3

А = 2,

В которой формула f= та играет роль принудительного ограничения. Сеть б) представляет теорию

F= mа

Т=3

А = 2

F=6,

Которая находится в состоянии релаксации по отношению к ограничению f= та, а сеть в) представляет противоречивую теорию

F= mа

Т=-3

А = 2

F=7.

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

А

Б

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

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

    (1) Монотонный пересмотр (monotonic revision). Это самый простой метод, при котором программа принимает информацию о новых фактах и вычисляет, как эти факты могут повлиять на имеющееся представление, чтобы оно перешло в результате в состояние релаксации. При этом предполагается учитывать "важные" последствия, хотя определить, какие последствия важные, а какие не очень, зависит от уровня интеллектуальности программы. Например, к важным скорее будет отнесен вывод q из р и (рq), чем вывод (pvq) из q. "Монотонным" этот способ пересмотра называется по той причине, что правдоподобность допущений в результате его применения по крайней мере не уменьшается. (2) Немонотонный пересмотр (nonmonotonic revision). Иногда бывает желательно "взять назад" принятые ранее допущения и урезать сделанные на их основе заключения. Если я вижу вас за рулем "Мерседеса", то первое предположение -- что он ваш собственный, а следовательно, вы, мягко говоря, человек не бедный. Но если через некоторое время я узнаю, что вы его, пользуясь терминологией Гека Финна, "позаимствовали", то я должен буду отбросить не только предположение, что он ваш собственный, но и предположение о вашем богатстве. (3) Немонотонное обоснование (nonmonotonic justification). Дальнейшее усложнение метода происходит в тех программах, в которых определенные предположения полагаются истинными в том случае, когда нет никаких явных свидетельств против такого предположения. Например, программа может предполагать, что все студенты малообеспечены. Отказ от такого предположения в отношении определенного студента выполняется в программе только в том случае, если на лицо явные признаки более чем среднего материального благополучия. Здесь именно отсутствие информации, противоречащей первоначальному допущению, а не наличие подтверждающей информации является обоснованием его правдоподобия. (4) Гипотетическое суждение (hypothetical reasoning). В программе можно сначала принять во внимание определенные предположения, а затем посмотреть, что из них следует. Далее из этих предположений можно отобрать правдоподобные допущения. Таким образом, в этом способе предполагается формировать рассуждения в разных мирах, т. е. в таких состояниях представления о реальной области знаний, которые могут соответствовать или не соответствовать реальности. Отслеживание множества теорий такого вида требует определенных дополнительных ресурсов по сравнению с методами, предполагающими исследование единственной теории.

Методы первой из перечисленных категорий довольно тривиальны: нужно добавить в имеющуюся теорию новую информацию и некоторые дополнительные факты, которые необходимы, чтобы перевести новую теорию в состояние релаксации по отношению к имеющимся ограничениям. Простой метод, демонстрирующий реализацию второй из перечисленных категорий, мы рассмотрим в следующем разделе, а в разделах 19.3 и 19.4 рассмотрим методы третьей и четвертой категорий.

Запись информации о связях. Программой на языке CLIPS несложно проиллюстрировать простую процедуру записи зависимостей между данными в продукционной системе с прямой цепочкой вывода. Если в рабочей памяти имеются только два типа выражений -- выражения импликации типа "Р имплицирует Q" и атомы, такие как "Р" и "Q", -- то можно зафиксировать зависимости между элементами рабочей памяти в виде извлеченных из них характеристик влияния. Объекты литералов имеют поля support, в которых записывается, какие выражения используются для вывода этих литералов. Может оказаться так, что некоторые литералы не имеют соответствующих выражений, поскольку представляют собой предположения, формируемые при инициализации рабочей памяти на основе конструкций def facts. В поле support таких литералов устанавливается значение -1. И литералы, и выражения импликации имеют нумерованные идентификаторы, которые позволяют отслеживать их состояние посредством специальных списков.

ШАБЛОНЫ

Литерал - атомарное высказывание,

    (deftemplate literal (field id (type INTEGER)) (field atom (type SYMBOL)) (multifield support (type INTEGER) (default -1))

| )

Условие является импликацией в форме

;; "Р имплицирует Q", где "P" является левой частью правила

;; (left-hand side = Ihs),

;; "Q" - правой частью

;; (right-hand side = rhs).

    (deftemplate conditional (field Id (type INTEGER)) (multifield Ihs (type SYMBOL)) (multifield rhs (type SYMBOL)) )

;; Нам понадобится индекс в рабочей памяти, чтобы

;; можно было присваивать идентификаторы новым

;; производным высказываниям, (deftemplate index

(field no (type INTEGER)) )

;; Исходная модель мира. (deffacts model

    (conditional (id 0) (Ihs P) (rhs Q); (literal (id 1) (atom P)) )

;; ПРАВИЛА

;; Присвоить значение индекса очередному идентификатору,

    (defrule init ?F <- (initial-fact) (literal (id? n)) (not (literal (id? m&;:{> ?M? N)))) => (assert (index (no (+ ?N 1)))) (retract? F) )

;; Применить правило modus ponens, чтобы можно было

;; вывести "Q" из "Р" и "Р имплицирует Q", формируя

;; указатели на "Р" и "Р имплицирует Q" в попе

;; support литерала "Q". (defrule mp? I <- (index (no? N))

    (conditional (id? C) (Ihs $?X) (rhs $?Y)) (literal (id? A) (atom $?X)) (not (literal (atom $?Y))) (assert (literal (id? N) (atom $?Y) (support? C?A))) (modify? I (no (+ ?N 1)))

Эта примитивная программа имеет дело только с условными выражениями и атомами. Например, нельзя, используя правило modus fallens (см. главу 8), вывести "не Р" из "Р имплицирует Q" и "не Q".

Похожие статьи




Отслеживание зависимостей - Система отслеживания истинности предположений

Предыдущая | Следующая