Системы поддержания истинности и управление знаниями

Введение

Причинное поддержание – это подход к представлению знаний для эффективной обработки выведенной информации, которая явно хранится. Причинное поддержание различает базовые факты, которые могут быть опровергнуты, и выведенные факты. Таким образом, оно отличается от пересмотра убеждений, который в своей базовой форме предполагает, что все факты равнозначны. Причинное поддержание изначально было разработано как техника для реализации решателей задач. Два компонента – система рассуждений и система причинного поддержания – взаимодействуют друг с другом посредством интерфейса. Система рассуждений использует систему причинного поддержания для записи своих выводов и обоснований ("причин") этих выводов. Система рассуждений также информирует систему причинного поддержания о текущих действительных базовых фактах (предположениях). Система причинного поддержания использует эту информацию для вычисления значения истинности сохраненных выведенных фактов и восстановления согласованности в случае возникновения противоречия. Система поддержания истины, или TMS, – это метод представления знаний для представления как убеждений, так и их зависимостей, а также алгоритм, называемый "алгоритмом поддержания истины", который манипулирует и поддерживает эти зависимости. Название "поддержание истины" обусловлено способностью этих систем восстанавливать согласованность. Система поддержания истины поддерживает согласованность между старыми и текущими знаниями в базе знаний (KB) посредством пересмотра. Если текущие утверждения противоречат знаниям в KB, то KB обновляется новыми знаниями. Может случиться, что одни и те же данные снова будут приняты, и предыдущие знания понадобятся в KB. Если предыдущие данные отсутствуют, но могут потребоваться для нового вывода, то их необходимо будет восстановить. Но если предыдущие знания уже были в KB, то повторного поиска не требуется. Использование TMS позволяет избежать такого повторного поиска, отслеживая противоречивые данные с помощью записи зависимостей. Эта запись отражает отмены и добавления, что позволяет механизму вывода (IE) быть в курсе своего текущего набора убеждений. Каждое утверждение, имеющее хотя бы одно обоснование, становится частью текущего набора убеждений. При обнаружении противоречия выявляются утверждения, ответственные за него, и записи соответствующим образом обновляются. Этот процесс называется отслеживанием зависимостей. Алгоритм TMS поддерживает записи в виде сети зависимостей. Каждый узел в сети представляет собой запись в KB (посылку, антецедент или правило вывода и т.д.). Каждая дуга сети представляет собой шаги вывода, посредством которых был получен узел. Посылка – это фундаментальное убеждение, которое считается истинным и не требует обоснования. Совокупность посылок является основой, из которой выводятся обоснования для всех остальных узлов. Существует два типа обоснований для узла: Список поддержки [SL] Условное доказательство (CP). Существует множество видов систем поддержания истины. Два основных типа – поддержание истины в одном контексте и в нескольких контекстах. В системах с одним контекстом согласованность поддерживается между всеми фактами в памяти (KB) и соответствует понятию согласованности, встречающемуся в классической логике. Многоконтекстные системы поддерживают параконсистентность, позволяя согласованности быть релевантной для подмножества фактов в памяти, контекста, в соответствии с историей логического вывода. Это достигается путем маркировки каждого факта или вывода его логической историей. Многоагентные системы поддержания истины выполняют поддержание истины в нескольких хранилищах памяти, часто расположенных на разных машинах. Система поддержания истины, основанная на допущениях де Клеера (ATMS, 1986), использовалась в системах, основанных на KEE на Lisp Machine. Первая многоагентная TMS была создана Мейсоном и Джонсоном. Это была многоконтекстная система. Бриджленд и Хунс создали первую одноконтекстную многоагентную систему.

Reason maintenance is a knowledge representation approach to efficient handling of inferred information that is explicitly stored. Reason maintenance distinguishes between base facts, which can be defeated, and derived facts. As such it differs from belief revision which, in its basic form, assumes that all facts are equally important. Reason maintenance was originally developed as a technique for implementing problem solvers. two components—a reasoner and a reason maintenance system—communicate with each other via an interface. The reasoner uses the reason maintenance system to record its inferences and justifications of ("reasons" for) the inferences. The reasoner also informs the reason maintenance system which are the currently valid base facts (assumptions). The reason maintenance system uses the information to compute the truth value of the stored derived facts and to restore consistency if an inconsistency is derived. A truth maintenance system, or TMS, is a knowledge representation method for representing both beliefs and their dependencies and an algorithm called the "truth maintenance algorithm" that manipulates and maintains the dependencies. The name truth maintenance is due to the ability of these systems to restore consistency. A truth maintenance system maintains consistency between old believed knowledge and current believed knowledge in the knowledge base (KB) through revision. If the current believed statements contradict the knowledge in the KB, then the KB is updated with the new knowledge. It may happen that the same data will again be believed, and the previous knowledge will be required in the KB. If the previous data are not present, but may be required for new inference. But if the previous knowledge was in the KB, then no retracing of the same knowledge is needed. The use of TMS avoids such retracing; it keeps track of the contradictory data with the help of a dependency record. This record reflects the retractions and additions which makes the inference engine (IE) aware of its current belief set. Each statement having at least one valid justification is made a part of the current belief set. When a contradiction is found, the statement(s) responsible for the contradiction are identified and the records are appropriately updated. This process is called dependency directed backtracking. The TMS algorithm maintains the records in the form of a dependency network. Each node in the network is an entry in the KB (a premise, antecedent, or inference rule etc.) Each arc of the network represent the inference steps through which the node was derived. A premise is a fundamental belief which is assumed to be true. They do not need justifications. The set of premises are the basis from which justifications for all other nodes will be derived. There are two types of justification for a node. They are:

Support list [SL]
Conditional proof (CP)

Many kinds of truth maintenance systems exist. Two major types are single context and multi context truth maintenance. In single context systems, consistency is maintained among all facts in memory (KB) and relates to the notion of consistency found in classical logic. Multi context systems support paraconsistency by allowing consistency to be relevant to a subset of facts in memory, a context, according to the history of logical inference. This is achieved by tagging each fact or deduction with its logical history. Multi agent truth maintenance systems perform truth maintenance across multiple memories, often located on different machines. de Kleer's assumption based truth maintenance system (ATMS, 1986) was utilized in systems based upon KEE on the Lisp Machine. The first multi agent TMS was created by Mason and Johnson. It was a multi context system. Bridgeland and Huhns created the first single context multi agent system.

Другие ссылки

Бриджленд, Д. М. и Хунс, М. Н., Распределенное поддержание истинности. Материалы AAAI–90: Восьмой национальной конференции по искусственному интеллекту, 1990. J. de Kleer (1986). TMS, основанное на предположениях. Искусственный интеллект, 28:127–162. J. Doyle. Система поддержания истинности. ИИ. Т. 12. № 3, с. 251–272. 1979. U. Junker и K. Konolige (1990). Вычисление расширений автоэпистемической и логики по умолчанию с использованием системы поддержания истинности. В материалах Восьмой национальной конференции по искусственному интеллекту (AAAI'90), стр. 278–283. MIT Press. Mason, C. и Johnson, R. DATMS: Фреймворк для рассуждений, основанных на предположениях, в "Распределенном искусственном интеллекте", т. 2, Morgan Kaufmann Publishers, Inc., 1989. D. A. McAllester. Трехзначная система поддержания. Массачусетский технологический институт, Лаборатория искусственного интеллекта. AI Memo 473. 1978. G. M. Provan (1988). Анализ сложности систем поддержания истинности, основанных на предположениях. В B. Smith и G. Kelleher (ред.), Системы поддержания рассуждений и их применение, стр. 98–113. Ellis Horwood, Нью-Йорк. G. M. Provan (1990). Вычислительная сложность систем поддержания истинности в нескольких контекстах. В материалах Девятой Европейской конференции по искусственному интеллекту (ECAI'90), стр. 522–527. R. Reiter и J. de Kleer (1987). Основы систем поддержания истинности, основанных на предположениях: предварительный отчет. В материалах Шестой национальной конференции по искусственному интеллекту (AAAI'87), стр. 183–188. PDF.