СИСТЕМЫ ПОДДЕРЖКИ ИСТИННОСТИ
14 Пересмотр убеждений часто противопоставляется обновлению убеждений (belief update), которое происходит, когда осуществляется пересмотр базы знаний для того, чтобы она отражала какое-то изменение в мире, а не добавление новой информации о неизменном мире. В обновлении убеждений объединяется пересмотр убеждений с рассуждениями о времени и изменениях; процесс обновлений связан также с процессом фильтрации, описанным в главе 15.
В предыдущем разделе было показано, что многие логические выводы, полученные с помощью той или иной системы представления знаний, могут иметь лишь некоторый заданный по умолчанию статус, а не быть абсолютно достоверными. Поэтому некоторые из таких полученных логическим путем фактов неизбежно оказываются ложными и должны быть отброшены на основании новой информации. Этот процесс называется пересмотром убеждений (belief revision)14. Предположим, что база знаний KB содержит высказывание Р (возможно, заключение, сформированное по умолчанию с помощью алгоритма прямого логического вывода, или, возможно, просто неверное утверждение) и требуется выполнить операцию Tell {KB, —iP).
Но для предотвращения возникновения противоречия необходимо вначале выполнить операцию Retract {KB, Р). На первый взгляд в этом нет ничего сложного. Но если на основании Рбыли выведены какие-то дополнительные высказывания и внесены в базу знаний, то возникают проблемы. Например, импликация Р => Q могла использоваться для внесения в базу знаний высказывания Q. Очевидное "решение" (извлечение всех высказываний, которые следуют из Р) неприемлемо, поскольку подобные высказывания могут иметь другие обоснования, помимо Р. Например, если в базе знаний имеются также высказывания Ru R => 0, то 0 в конечном итоге вообще не следует удалять. Системы поддержки истинности, или TMS (Truth Maintenance System), предназначены именно для того, чтобы можно было проще справиться с подобными осложнениями.
Один из очень простых подходов к созданию системы поддержки истинности состоит в том, чтобы следить за порядком, в котором высказывания вводятся в базу знаний, путем присваивания им номеров от Рх до Рп. После того как формируется вызов Retract {KB, Pi), система возвращается к состоянию, непосредственно предшествующему добавлению высказывания Р±, удаляя тем самым и pi} и любые результаты логического вывода, полученные на основании Pi. После этого могут быть снова добавлены высказывания от pi+1 до Рп. Такая организация работы является простой и гарантирует, что база знаний всегда будет оставаться непротиворечивой, но для извлечения Pi требуется извлечение и повторная вставка n-i высказываний, а также отмена и повторное выполнение всех логических выводов, вытекающих из этих высказываний. Для систем, в которые происходит добавление многих фактов (таких как крупные коммерческие базы данных), указанный подход является практически не применимым.
Более эффективный подход состоит в создании системы поддержки истинности на основе обоснований, или системы JTMS (Justification-Based Truth Maintenance System). В системе JTMS к каждому высказыванию в базе знаний прилагается аннотация в виде обоснования, состоящего из множества высказываний, на основании которых было выведено это высказывание. Например, если база знаний уже содержит высказывание Р => 0, то операция Tell (Р) вызовет добавление 0 с обоснованием {Р,Р => ?>}. Вообще говоря, высказывание может иметь любое количество обоснований. Обоснования используются для обеспечения эффективного извлечения. После выполнения вызова Retract (Р) система JTMS удалит такие и только такие высказывания, для которых Р является элементом каждого обоснования. Поэтому, если высказывание Q имеет единственное обоснование {Р, Р => Q], оно будет удалено; если имеет также дополнительное обоснование {Р, Р v я => ?>}, оно также будет удалено; но если, кроме этого, имеет обоснование {R,P v i? => ?>}, оно будет сохранено. Таким образом, время, требуемое для извлечения высказывания Р, зависит только от количества высказываний, полученных на основании Р, а не от количества других высказываний, добавленных после того, как Р было введено в базу знаний.
В системе JTMS предполагается, что высказывания, которые уже когда-то рассматривались, по-видимому, будут рассматриваться снова, поэтому вместо полного удаления из базы знаний некоторого высказывания после того, как оно теряет все обоснования, это высказывание просто отмечается как находящееся вне базы знаний. Если же какое-то последующее утверждение восстанавливает одно из обоснований, то это высказывание снова отмечается как находящееся внутри базы. Благодаря этому система JTMS позволяет сохранить все цепочки логического вывода, которые в ней используются, и не нуждается в повторном выводе высказываний после того, как некоторое обоснование вновь становится действительным.
Кроме успешного исключения из базы знаний неправильной информации, системы поддержки истинности могут также использоваться для ускорения анализа многочисленных гипотетических ситуаций. Предположим, например, что Олимпийский комитет Румынии выбирает площадки для проведения соревнований по плаванию, легкой атлетике и конному спорту для олимпийских игр 2048 года, которые должны проводиться в Румынии. Например, допустим, что первой гипотезой является следующая: Site (Swimming, Pitesti), Site {Athletics, Bucharest) и Site {Equestrian, Arad). В таком случае необходимо провести большой объем рассуждений, чтобы определить логические следствия, а значит и целесообразность этого выбора. Если же вместо этого потребуется рассмотреть вариант Site{Athletics, Sibiu), то такая система TMS позволит избавиться от необходимости начинать всю эту работу с нуля. Вместо этого достаточно будет просто извлечь гипотезу Site (Athletics, Bucharest) и ввести Site (Athletics, Sibiu), после чего система TMS возьмет на себя весь необходимый пересмотр. А цепочки логического вывода, выработанные на основании выбора площадки в Бухаресте, могут повторно использоваться для Сибиу, при условии, что логические заключения остаются теми же самыми.
Особенно эффективное переключение контекста между гипотетическими мирами обеспечивает система поддержки истинности на основе предположения, или ATMS (Assumption-based Truth Maintenance System), которая предназначена именно для этой цели. В системе JTMS средства сопровождения обоснований позволяют быстро переходить от одного состояния к другому, выполнив лишь небольшой объем извлечений и вставок, но в них в любой момент времени представлено только одно состояние. А в системе ATMS представлены все состояния, которые когда-либо рассматривались одновременно. Это означает, что в системе JTMS каждое высказывание обозначается как находящееся вне или внутри базы знаний, тогда как в системе ATMS для каждого высказывания отслеживается, какие предположения могли бы вынудить это высказывание стать истинным. Иными словами, каждое высказывание имеет метку, состоящую из множества множеств предположений. Это высказывание становится истинным только в том случае, если истинными являются все предположения в одном из множеств предположений.
Системы поддержки истинности предоставляют также механизм выработки объяснений. Формально объяснением высказывания Р является такое множество высказываний Е, что из Е следует Р. Если уже известно, что высказывания Е истинны, то Е просто предоставляет достаточную базу для доказательства того, что Р также является таковым. Но объяснения могут также включать предположения — высказывания, в отношении которых неизвестно, являются ли они истинными, но которые были бы достаточными, чтобы доказать истинность Р, если бы они были истинными. Например, некто может не иметь достаточной информации, чтобы доказать, что двигатель его автомобиль не запустится, но обоснованное объяснение может включать предположение, что аккумулятор разряжен. Это позволяет объяснить наблюдаемое неправильное поведение двигателя, в сочетании со знаниями о том, как работает двигатель автомобиля. В большинстве случаев предпочтительным является минимальное объяснение Е\ под этим подразумевается, что не существует строгое подмножество Е, которое также было бы объяснением. Система ATMS может сформировать объяснения для проблемы "двигатель автомобиля не запускается", делая предположения (такие как "в карбюратор попал бензин" или "разряжен аккумулятор") в любом желательном для пользователя порядке, даже если некоторые предположения противоречат друг другу. После этого достаточно посмотреть на метку, предусмотренную для высказывания "двигатель автомобиля не запускается", чтобы ознакомиться с множествами предположений, которыми могло бы оправдываться это высказывание.
Точные алгоритмы, используемые для реализации систем поддержки истинности, являются довольно сложными, и в этой главе они не рассматриваются. Вычислительная сложность задачи поддержки истинности является, по меньшей мере, такой же, какая характерна для пропозиционального логического вывода, т.е. NP-трудной. Поэтому не следует рассчитывать на то, что подход на основе поддержки истинности окажется панацеей. Однако при их продуманном использовании системы TMS могут обеспечить существенное повышение способности логических систем действовать в условиях применения сложных гипотез и вариантов среды.
Эта глава оказалась наиболее подробной по сравнению со всеми предыдущими главами данной книги. Описывая детали того, какие способы используются для представления различных знаний, авторы надеялись дать читателю возможность понять, как создаются реальные базы знаний. Основные идеи, высказанные в этой главе, перечислены ниже.
• Для крупномасштабного представления знаний требуется онтология общего назначения, позволяющая организовать и связать воедино различные специализированные области знаний.
• Онтология общего назначения должна охватывать широкий круг знаний и быть способной, в принципе, представить любую проблемную область.
• В главе описана верхняя онтология, основанная на категориях и исчислении событий. Здесь рассматривались структурированные объекты, время и пространство, изменения, процессы, вещества и убеждения.
• Действия, события и время могут быть представлены либо с помощью ситуационного исчисления, либо с применением более выразительных средств представления, таких как исчисление событий и исчисление флюентных высказываний. Такие представления дают возможность агенту составлять планы с помощью логического вывода.
• Мыслительные состояния агентов могут быть представлены строками, которые описывают их убеждения.
• В главе представлен подробный анализ проблемной области совершения покупок в Internet, исследована общая онтология и показано, как знания проблемной области могут использоваться торговым агентом.
• Описаны системы представления общего назначения, такие как семантические сети и описательные логики, позволяющие организовывать иерархии категорий. С этими системами связана важная форма логического вывода, называемая наследованием, позволяющая определять логическим путем свойства объектов на основании данных об их принадлежности к категориям.
• Предположение о замкнутом мире, будучи реализованным в логических программах, предоставляет простой способ избежать необходимости задавать большие объемы отрицательной информации. Такую информацию проще всего интерпретировать как заданную по умолчанию, которая может быть переопределена с помощью дополнительной информации.
• В целом для предоставления возможности осуществлять формирование рассуждений по умолчанию предназначены немонотонные логики, такие как логика косвенного описания и логика умолчания. Применение программирования множества ответов позволяет ускорить немонотонный логический вывод, во многом аналогично тому, как использование алгоритма WalkSAT ускоряет пропозициональный логический вывод.
• Системы поддержки истинности позволяют эффективно осуществлять обновления и пересмотры баз знаний.