3. Представление

Вид материала

Обзор

Содержание 19.4. Работа со множеством контекстов 19.4.1. Отслеживание истинности предположений, основанное на анализе допущений Рис. 19.3. Решетка сред Рис. 19.4. Решетка сред, в которой выделен несовместный контекст "Если в карбюраторе имеется избыток топлива, то бензин не может отсутствовать в баке". Предположим также, что в модели имеется обоснование "Если свечи влажные, то бензин не может отсутствовать в баке". Рис. 19.5. Решетка сред, в которой узлы, имеющие непустые списки ярлыков, заштрихованы Ярлык является совместимым, если любая среда, включенная в список, является непротиворечивой. 19.4.2. Использование систем отслеживания истинности предположений для диагностирования на основе моделей 3) В устройстве имеется единственный отказ. В системе отслеживания истинности предположений используется несколько стратегий управления обработкой пространства кандидатов, сохранение в системе просмотренной цепочки логического вывода, что позволяет исключить ее повторный просмотр. Рис. 19.6. Решетка сред, представляющая пространство кандидатов. Несовместные контексты выделены утолщенным контуром, а минималь

Подобный материал:

• Вопросы к экзамену по курсу " ЭВМ и периферийные устройства" для групп К2-121, -122,, 75.03kb.
• И представление налоговой отчетности, 357.06kb.
• И представление налоговой отчетности, 394.07kb.
• Дать детям представление о речевом этикете, как о правилах поведения в различных ситуациях;, 241.98kb.
• Дать общее представление о витаминах, познакомить учащихся с их классификацией, представителями, 180.08kb.
• Урок Окружающий мир 2 класс умк «Перспективная начальная школа», 44.76kb.
• Задачи:; развивать обобщенное представление о казахстанцах; сформировать представление, 49.53kb.
• Урок 57 Источники права Цель, 56.46kb.
• Вопросы для подготовки к экзамену по архитектуре ЭВМ, 79.1kb.
• Отчет об оказании юридических услуг за 20 г. Представляют, 89.3kb.

^

19.4. Работа со множеством контекстов

Те системы отслеживания истинности предположений, которые мы рассматривали в предыдущих разделах, работали с единственной непротиворечивой моделью мира. Однако иногда возникает необходимость строить логический вывод в контексте разных моделей гипотетических миров, которые могут совпадать, а могут и не совпадать с реальностью (см. главу 17). Например, при решении задачи диагностирования часто бывает полезно предположить, что возникла какая-то ошибка, и выдвинуть предположение на основе какого-нибудь допущения, а затем посмотреть, не подтверждается ли оно имеющимися фактами. Особенно уместна такая стратегия в ситуации, когда результаты наблюдений дают пищу для множества конкурирующих гипотез и скорее всего потребуется какая-либо комбинация гипотез, чтобы объяснить всю совокупность наблюдений. Другая область применения, в которой потребуется рассмотреть несколько вариантов модели мира, — проектирование. Вот тут-то уж точно потребуется несколько гипотетических "миров", чтобы представить разные варианты конструкции, удовлетворяющей заданным ограничениям

^

19.4.1. Отслеживание истинности предположений, основанное на анализе допущений

В системах отслеживания истинности предположений, основанных на анализе допущений {assumption-based truth-maintenance system), программа имеет дело с несколькими отличающимися контекстами, которые принято называть средами обитания (environments) [De Kleer, 1986]. Удобнее всего представить себе среду обитания как взгляд на мир через призму определенных допущений. Можно считать, что модель мира, которая использовалась в предыдущих разделах, характеризуется пустым множеством допущений. Все прочие среды, имеющие непустое множество допущений, представляют модели гипотетических миров.

В системах отслеживания истинности предположений, основанных на допущениях, различные варианты сред обитания можно организовать в виде решетки, поскольку допущения носят инкрементальный характер. Модель, показанная на рис. 19.3, представляет на самом нижнем уровне автомобиль, в котором не горит свет и который не удается завести. На более верхнем уровне решетки находятся гипотетические миры, в которых сделаны некоторые допущения о неисправностях в автомобиле, например разряжена аккумуляторная батарея. На еще более высоком уровне можно комбинировать сделанные допущения. Обратите внимание — чем выше мы поднимаемся "по ступеням решетки", тем более специфическими становятся гипотетические миры в том смысле, что мы характеризуем их все полнее.

Не всегда можно делать произвольные допущения. Например, нельзя объединить допущения {p,q} и {—p,r}, поскольку такая комбинация будет противоречивой. Более того, хотя само множество допущений может и не быть антагонистическим, определенные комбинации допущений могут привести к противоречию, если принять во внимание и другую имеющуюся в нашем распоряжении информацию.

Предположим, что наша модель неисправного автомобиля содержит информацию о том, что одновременно не может случиться так, чтобы и карбюратор не работал из-за избытка топлива, и в баке отсутствовал бензин. Следовательно, в том варианте среды, в котором сделано допущение "в баке отсутствует бензин", не может присутствовать допущение "избыток топлива в карбюраторе". Такое логическое заключение образует контекст среды — множество высказываний, производных от сделанных допущений, и фактов, имеющихся в исходной модели мира. Например, мы можем оказаться в ситуации, представленной схематически на рис. 19.4. Здесь среда, образованная в результате объединения двух допущений, должна быть исключена из рассмотрения, поскольку ее контекст становится несовместимым (nogood).

^

Рис. 19.3. Решетка сред

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

В системах отслеживания истинности предположений, основанных на анализе допущений, такие зависимости называются обоснованиями (justification). Конечно, такая вольная трактовка термина "обоснование" вносит некоторую неоднозначность в изложение материала (ранее мы придавали этому термину несколько другой смысл), но дело в том, что обоснование в тех системах, которые рассматриваются в данном разделе, играет роль, отличную от обоснований в простых системах отслеживания истинности, анализированных Мак-Аллестером и Дойлом. В тех системах обоснования формировались программой в результате распространения принуждений и связывались с узлами сети зависимостей, которые представляли высказывания.

^

Рис. 19.4. Решетка сред, в которой выделен несовместный контекст

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

На рис. 19.4 отрицание высказывания "Нет бензина в баке" существует в среде, в которой сделано допущение "Избыток топлива в карбюраторе", причем в модели имеется обоснование, которое гласит примерно следующее:

^

"Если в карбюраторе имеется избыток топлива, то бензин не может отсутствовать в баке".

Теперь интересующее нас высказывание будет "по наследству" истинно и в несовместимом контексте, но такая среда не представляет интереса для этого высказывания и, следовательно, в список ярлыка не включается.

^

Предположим также, что в модели имеется обоснование

"Если свечи влажные, то бензин не может отсутствовать в баке".

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

^

Рис. 19.5. Решетка сред, в которой узлы, имеющие непустые списки ярлыков, заштрихованы

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

Таким образом, из всего сказанного выше вытекает, что основная забота системы отслеживания истинности предположений, основанной, на анализе допущений, состоит в формировании списка сред для узлов высказываний. Такой список может быть созвучным (sound), завершенным (complete), совместимым (consistent) или минимальным (minimal) ярлыком. В эти термины вкладывается следующий смысл.

Ярлык является созвучным, если высказывание, к которому он относится, является производным от каждой среды, включенной в этот ярлык, т.е. оно имеет статус включено в контексте каждой такой среды.

Ярлык является завершенным, если любая непротиворечивая среда, в которой имеет место соответствующее высказывание, либо присутствует в списке, либо образована включением дополнительных допущений в ту среду, которая присутствует в списке.

^

Ярлык является совместимым, если любая среда, включенная в список, является непротиворечивой.

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

Если узел высказывания в сети имеет пустой ярлык, это означает, что высказывание не является производным ни от какого совместимого множества допущений. Другими словами, это высказывание не может быть истинным ни при каких совместимых комбинациях допущений. Например, ярлык узла, соответствующего высказыванию "отсутствует бензин в баке и влажные свечи", будет иметь пустой список.

^

19.4.2. Использование систем отслеживания истинности предположений для диагностирования на основе моделей

Выше, в главах 11 и 12, были рассмотрены экспертные диагностические системы, в которых использовался метод эвристической классификации. Этот метод предполагает, что большая часть знаний представлена в виде эвристических правил, связывающих абстрактные категории данных (типичные симптомы) с абстрактными категориями решений (типичные неисправности). Такая форма представления знаний иногда называется "поверхностной", поскольку знания не содержат информации о причинных связях между симптомами и неисправностями (теорию функционирования диагностируемого объекта — машины или живого организма), а отражают только эмпирический опыт. Информация о причинно-следственных связях, определяющих поведение и свойства диагностируемого объекта, принято называть "глубинным" знанием.

Диагностирование, основанное на моделях анализируемых объектов, использует не столько эмпирический опыт эксперта, сколько более или менее полную и непротиворечивую теорию корректного поведения этих объектов. Идея состоит в том, чтобы, располагая на входе данными о наблюдаемых отклонениях в поведении, высказать предположение об одном или нескольких возмущениях в описании системы, которые могли бы объяснить эти отклонения.

Очевидные преимущества подхода, при котором сначала принимаются во внимание знания о принципах поведения объекта, а уже затем эмпирические знания, состоят в следующем.

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

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

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

Прототипом подобного рода диагностических экспертных систем можно считать программу DART [Genesereth, 1984]. Хотя предметной областью, для которой предназначалась эта программа, является анализ цифровых схем, но использованные в ней язык представления знаний и механизм логического вывода более или менее независимы от этой предметной области. Для представления описания конструкции диагностируемого устройства используются формализм исчисления предикатов и форма доказательства теорем, с помощью которых формируются множества "подозрительных" компонентов и тестов, призванных подтвердить или опровергнуть гипотезы о причинах неисправностей. Метод решения проблем, использованный в DART, опирается на три упрощающих допущения.

(1) Предполагается, что связи между компонентами функционируют правильно, и задача состоит в том, чтобы отыскать те компоненты, неисправность которых может объяснить наблюдаемые симптомы неправильной работы устройства.

(2) Отказы не носят случайного во времени характера, т.е. все компоненты в процессе выполнения диагностических тестов работают стабильно (правильно или неправильно — это уже другой вопрос).

^

(3) В устройстве имеется единственный отказ.

Каждое из этих предположений, конечно же, очень ограничивает возможность практического применения системы, но в работе [De Kleer and Williams, 1987] было показано, что использование систем отслеживания истинности предположений, основанных на анализе допущений, поможет снять третье из перечисленных ограничений. Это было продемонстрировано в программе GDE (General Diagnostic Engine — система диагностирования общего назначения).

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

Как было показано ранее в этом же разделе, методы отслеживания истинности предположений, основанные на анализе допущений, имеют дело с решеткой сред — альтернативных состояний модели мира, которые согласуются с некоторой теорией, но используют при этом отличающиеся допущения. В диагностических приложениях такой неявной теорией является описание диагностируемого устройства, а альтернативные состояния модели мира характеризуются различными комбинациями отказавших компонентов устройства. Если устройство состоит из п компонентов, то теоретически может существовать 2" комбинаций отказов компонентов. Решетка вариантов сред является перечислимым множеством присоединений: элемент с наименьшим номером соответствует отсутствию отказов в компонентах, а элемент с наибольшим номером — отказу всех компонентов устройства. Каждая такая среда называется кандидатом, т.е. гипотезой о том, что именно произошло в неисправном устройстве. Вся решетка сред при такой постановке проблемы будет представлять собой пространство кандидатов.

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

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

В качестве простого примера рассмотрим решетку сред, представленную на рис. 19.6. В этой решетке C1, C2 и СЗ— компоненты анализируемого устройства. Пусть S — множество наблюдаемых проявлений ненормальной работы этого устройства. Предположим, нам известно, что если наблюдается множество проявлений S, то С1 и С2 не могут быть исправными одновременно, а также С1 и СЗ. Тогда можно выделить среды, помеченные на схеме решетки значками 0, С2 и СЗ (они выделены на схеме как несовместные). Каждая из этих сред имеет какое-либо запрещенное сочетание исправных компонентов. Все другие среды являются кандидатами в пространстве гипотез, но очевидно, что минимальные множества среди них — (С1} и {С2, СЗ}.

^

В системе отслеживания истинности предположений используется несколько стратегий управления обработкой пространства кандидатов, например:

стратегия, основанная на предоставлении преимущества тем гипотезам, которые поясняются проще всего; поиск решения начинается с минимальных по объему (количеству элементов) конфликтных множеств;

^

сохранение в системе просмотренной цепочки логического вывода, что позволяет исключить ее повторный просмотр.

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

^

Рис. 19.6. Решетка сред, представляющая пространство кандидатов. Несовместные контексты выделены утолщенным контуром, а минимальные кандидаты заштрихованы