Абдуктивное логическое программирование - Abductive logic programming

Абдуктивное логическое программирование ( ALP ) - это высокоуровневый фреймворк для представления знаний, который можно использовать для декларативного решения проблем на основе абдуктивного мышления . Он расширяет обычное логическое программирование , позволяя не полностью определять некоторые предикаты, объявляя их как сокращаемые предикаты. Решение проблем осуществляется путем вывода гипотез на основе этих абдуктивных предикатов (абдуктивных гипотез) как решений проблем, которые необходимо решить. Эти проблемы могут быть либо наблюдениями, которые необходимо объяснить (как в классическом абдукции), либо целями, которые необходимо достичь (как в нормальном логическом программировании ). Его можно использовать для решения задач диагностики, планирования , естественного языка и машинного обучения . Он также использовался для интерпретации отрицания как неудачи как формы абдуктивного рассуждения.

Синтаксис

Программы абдуктивной логики состоят из трех компонентов : ${\ displaystyle \ langle P, A, IC \ rangle,}$

• P - это логическая программа точно такой же формы, что и в логическом программировании.
• A - это набор имен предикатов, называемых сокращаемыми предикатами.
• IC - это набор классических формул первого порядка.

Обычно логическая программа P не содержит предложений, заголовок (или заключение) которых относится к сокращаемому предикату. (Это ограничение может быть сделано без потери общности.) Также на практике во многих случаях ограничения целостности в IC часто ограничиваются формой отказов, т. Е. Пунктами формы:

   false:- A1,...,An, not B1, ..., not Bm.

Такое ограничение означает, что невозможно, чтобы все A1, ..., An были истинными, и в то же время все B1, ..., Bm были ложными.

Неформальный смысл и решение проблем

Пункты в P определяют набор невыводимых предикатов и посредством этого предоставляют описание (или модель) предметной области. Ограничения целостности в IC определяют общие свойства проблемной области, которые необходимо соблюдать при любом решении проблемы.

Проблема G , которая выражает либо наблюдение, которое необходимо объяснить, либо желаемую цель, представлена ​​сочетанием положительных и отрицательных (NAF) литералов. Такие задачи решаются путем вычисления «абдуктивное объяснения» из G .

Абдуктивное объяснение проблемы G - это набор положительных (а иногда и отрицательных) основных экземпляров сводимых предикатов, так что, когда они добавляются в логическую программу P, проблема G и ограничения целостности IC выполняются. Таким образом, абдуктивные объяснения расширяют логическую программу P путем добавления полных или частичных определений абдуктивных предикатов. Таким образом, абдуктивные объяснения формируют решения проблемы в соответствии с описанием проблемной области в P и IC. Расширение или завершение описания проблемы, данное абдуктивными объяснениями, дает новую информацию, которая до сих пор не содержалась в решении проблемы. Критерии качества , чтобы предпочесть одно решение над другим, часто выражается с помощью ограничений целостности, могут быть применены , чтобы выбрать конкретные абдуктивного объяснения проблемы G .

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

Следующие два примера, написанные простым структурированным английским языком, а не строгим синтаксисом ALP, иллюстрируют понятие абдуктивного объяснения в ALP и его отношение к решению проблем.

Пример 1

Программа абдуктивной логики содержит следующие предложения: ${\ displaystyle \ langle P, A, {\ mathit {IC}} \ rangle}$${\ displaystyle P}$

  Grass is wet if it rained.

  Grass is wet if the sprinkler was on.

  The sun was shining.

Приводимые предикаты в : "шел дождь" и "спринклер был включен ", а единственное ограничение целостности в следующем : ${\ displaystyle A}$${\ displaystyle {\ mathit {IC}}}$

  false if it rained and the sun was shining.

Наблюдение, что трава мокрая, имеет два возможных объяснения: «шел дождь» и «разбрызгиватель был включен», которые влекут за собой наблюдение. Однако только второе возможное объяснение, «спринклер был включен», удовлетворяет ограничению целостности.

Пример 2

Рассмотрим программу абдуктивной логики, состоящую из следующих (упрощенных) предложений:

  X is a citizen if X is born in the USA.

  X is a citizen if X is born outside the USA and X is a resident of the USA and X is naturalized.

  X is a citizen if X is born outside the USA and Y is the mother of X and Y is a citizen and X is registered.

  Mary is the mother of John.

  Mary is a citizen.

вместе с пятью сокращаемыми предикатами «родился в США», «родился за пределами США», «является резидентом США», «натурализован» и «зарегистрирован» и ограничением целостности:

  false if John is a resident of the USA.

У цели «Джон - гражданин» есть два решения по поводу похищения, одно из которых - «Джон родился в США», второе - «Джон родился за пределами США» и «Джон зарегистрирован». Потенциальное решение стать гражданином по месту жительства и натурализации не удается, потому что оно нарушает ограничение целостности.

Более сложный пример, который также написан с использованием более формального синтаксиса ALP, следующий.

Пример 3

Приведенная ниже программа абдуктивной логики описывает простую модель метаболизма лактозы бактерии E. coli. Программа P описывает (в своем первом правиле), что кишечная палочка может питаться сахарной лактозой, если она вырабатывает два фермента - пермеазу и галактозидазу. Как и все ферменты, они создаются, если они кодируются геном (геном), который экспрессируется (описывается вторым правилом). Два фермента пермеазы и галактозидазы кодируются двумя генами, lac (y) и lac (z) соответственно (указанные в пятом и шестом правиле программы), в кластере генов (lac (X)), называемом оперон - это выражается, когда количество (amt) глюкозы низкое, а лактозы высокое, или когда они оба находятся на среднем уровне (см. четвертое и пятое правило). Приводимые, A , объявляют все основные экземпляры предикатов "количество" допустимыми. Это отражает то, что в модели количества различных веществ в любой момент времени неизвестны. Это неполная информация, которую нужно определять в каждом проблемном случае. Ограничения целостности, IC , утверждают, что количество любого вещества (S) может принимать только одно значение.

Знание предметной области (P)

   feed(lactose) :- make(permease), make(galactosidase).
   make(Enzyme) :- code(Gene, Enzyme), express(Gene).
   express(lac(X)) :- amount(glucose, low), amount(lactose, hi).
   express(lac(X)) :- amount(glucose, medium), amount(lactose, medium).
   code(lac(y), permease).
   code(lac(z), galactosidase).
   temperature(low) :- amount(glucose, low).

Ограничения целостности (IC)

   false :- amount(S, V1), amount(S, V2), V1 ≠ V2.

Приводимые (A)

   abducible_predicate(amount).

Задача - цель . Это может возникнуть либо как наблюдение, которое нужно объяснить, либо как состояние дел, которое должно быть достигнуто путем нахождения плана. У этой цели есть два похищающих объяснения: ${\ displaystyle G = {\ text {корм (лактоза)}}}$

${\ displaystyle {\ begin {cases} \ Delta _ {1} = \ {{\ text {количество (лактоза, привет), количество (глюкоза, низкий)}} \} \\\ Delta _ {2} = \ { {\ text {количество (лактоза, среда), количество (глюкоза, среда)}} \} \ end {case}}}$

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

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

Формальная семантика

Формальная семантика центрального понятия абдуктивного объяснения в ALP может быть определена следующим образом.

При наличии абдуктивной логической программы абдуктивное объяснение проблемы представляет собой набор основных атомов на абдуктивных предикатах, таких что: ${\ displaystyle \ langle P, A, {\ mathit {IC}} \ rangle}$${\ displaystyle G}$${\ displaystyle \ Delta}$

• ${\ displaystyle P \ cup \ Delta \ models G}$
• ${\ Displaystyle P \ cup \ Delta \ models IC}$
• ${\ displaystyle P \ cup \ Delta}$это соответствует

Это определение оставляет открытым выбор базовой семантики логического программирования, посредством которой мы даем точное значение отношения следования и понятие согласованности программ (расширенной) логики. Любая из различных семантик логического программирования, такая как завершение, стабильная или хорошо обоснованная семантика, может (и использовалась на практике) давать разные понятия абдуктивных объяснений и, следовательно, разные формы структур ALP. ${\ displaystyle \ models}$

В приведенном выше определении делается особый взгляд на формализацию роли ограничений целостности как ограничений на возможные абдуктивные решения. Это требует, чтобы они были вызваны логической программой, расширенной абдуктивным решением, что означает, что в любой модели расширенной логической программы (которую можно представить себе как заданный последующий мир ) требования ограничений целостности удовлетворяются. В некоторых случаях это может быть излишне сильным, и более слабое требование согласованности, а именно согласованность, может быть достаточным, что означает, что существует по крайней мере одна модель (возможный последующий мир) расширенной программы, в которой выполняются ограничения целостности. На практике во многих случаях эти два способа формализации роли ограничений целостности совпадают, поскольку логическая программа и ее расширения всегда имеют уникальную модель. Многие из систем ALP используют представление следования ограничений целостности, поскольку это может быть легко реализовано без необходимости в каких-либо дополнительных специализированных процедурах для удовлетворения ограничений целостности, поскольку это представление обрабатывает ограничения таким же образом, как и цель задачи. Во многих практических случаях третье условие в этом формальном определении абдуктивного объяснения в ALP либо тривиально выполняется, либо оно содержится во втором условии за счет использования определенных ограничений целостности, которые фиксируют согласованность. ${\ displaystyle {\ mathit {IC}}}$${\ displaystyle \ Delta}$${\ displaystyle P \ cup {\ mathit {IC}} \ cup \ Delta}$

Реализация и системы

Большинство реализаций ALP расширяют основанную на разрешении SLD вычислительную модель логического программирования. ALP также может быть реализован посредством его связи с программированием набора ответов (ASP), где могут использоваться системы ASP. Примерами систем первого подхода являются ACLP, A-system, CIFF, SCIFF, ABDUAL и ProLogICA.

Смотрите также

• Абдуктивное рассуждение
• Программирование набора ответов
• Индуктивное логическое программирование
• Отрицание как неудача
• Аргументация

Примечания

использованная литература

внешние ссылки

• ACLP
• ACL
• SCIFF
• Система