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

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

Синтаксис

Программы абдуктивной логики состоят из трех компонентов: $\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

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

  Grass is wet if it rained.

  Grass is wet if the sprinkler was on.

  The sun was shining.

Сводимые предикаты в $A$ являются «шел дождь» и «работал разбрызгиватель» и являются единственным ограничением целостности в ${\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 описывает (в первом правиле), что E. coli может питаться сахарной лактозой, если она вырабатывает два фермента: пермеазу и галактозидазу. Как и все ферменты, они производятся, если они кодируются экспрессируемым геном (геном) (описанным вторым правилом). Два фермента пермеаза и галактозидаза кодируются двумя генами, lac(y) и lac(z) соответственно (указанными в пятом и шестом правиле программы), в кластере генов (lac(X)) – называемом оперон – проявляется, когда количество (амт) глюкозы низкое, а лактозы высокое или когда они оба находятся на среднем уровне (см. четвертое и пятое правило). Абдуцируемые, 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.

Сводимый (А)

   abducible_predicate(amount).

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

${\begin{cases}\Delta _{1}=\{{\text{amount(lactose, hi), amount(glucose, low)}}\}\\\Delta _{2}=\{{\text{amount(lactose, medium), amount(glucose, medium)}}\}\end{cases}}$

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

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

Рассуждения по умолчанию в ALP

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

Рассмотрим классический пример рассуждения по умолчанию о том, что птица может летать, если нельзя доказать, что птица ненормальна. Вот вариант примера, использующего отрицание как неудачу:

canfly(X) :- bird(X), not(abnormal_flying_bird(X)).
abnormal_flying_bird(X):- wounded(X).
bird(john).
bird(mary).
wounded(john).

Вот тот же пример с использованием сводимого предиката normal_flying_bird(_) с ограничением целостности в ALP:

canfly(X) :- bird(X), normal_flying_bird(X).
false :- normal_flying_bird(X), wounded(X).
bird(john).
bird(mary).
wounded(john).

Сводимый предикат normal_flying_bird(_), противоположно предикату abnormal_flying_bird(_).

Используя похищение в ALP, можно сделать вывод canfly(mary) по предположению normal_flying_bird(mary). Заключение можно сделать на основе предположения, поскольку нельзя показать, что ограничение целостности нарушено, а именно потому, что нельзя показать, что wounded(mary). Напротив, невозможно сделать вывод canfly(john), потому что предположение normal_flying_bird(john) вместе с тем фактом wounded(john) нарушает ограничение целостности. Этот способ рассуждения в ALP имитирует рассуждение с отрицанием как неудачу.

И наоборот, в ALP можно смоделировать похищение, используя отрицание как отказ с семантикой стабильной модели . Это можно сделать, добавив для каждого сводимого предиката p, дополнительный противоположный предикат negp, и пара предложений:

p :- not(negp).
negp :- not(p).

Эта пара предложений имеет две устойчивые модели, одна из которых p, истинно, а другое, в котором negp, это правда. Этот метод моделирования похищения обычно используется при программировании набора ответов для решения проблем с использованием методологии генерации и тестирования .

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

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

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

• $P\cup \Delta \models G$
• $P\cup \Delta \models IC$
• $P\cup \Delta$ является последовательным

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

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

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

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

См. также

• Индуктивное логическое программирование

Ссылки

• Пул, Д.; Гебель, Р.; Алелиюнас, Р. (1987). «Теоретик: система логических рассуждений для ошибок и диагностики» . В Черконе, Ник; МакКалла, Гордон (ред.). Граница знаний: очерки представления знаний . Спрингер. стр. 331–352. ISBN  978-0-387-96557-4 .
• Какас, AC; Манкарелла, П. (1990). «Обобщенные стабильные модели: семантика похищения». В Айелло, LC (ред.). ECAI 90: материалы 9-й Европейской конференции по искусственному интеллекту . Питман. стр. 385–391. ISBN  978-0273088226 .
• Консоль, Л.; Дюпре, Д.Т.; Торассо, П. (1991). «О связи между похищением и дедукцией». Журнал логики и вычислений . 1 (5): 661–690. CiteSeerX   10.1.1.31.9982 . дои : 10.1093/logcom/1.5.661 .
• Какас, AC; Ковальски, РА ; Тони, Ф. (1993). «Абдуктивное логическое программирование». Журнал логики и вычислений . 2 (6): 719–770. CiteSeerX   10.1.1.37.3655 . дои : 10.1093/logcom/2.6.719 .
• Денекер, Марк; Де Шрей, Дэнни (февраль 1998 г.). «SLDNFA: Абдуктивная процедура для программ абдуктивной логики». Журнал логического программирования . 34 (2): 111–167. CiteSeerX   10.1.1.21.6503 . дои : 10.1016/S0743-1066(97)00074-5 .
• Денекер, М.; Какас, AC (июль 2000 г.). «Спецвыпуск: абдуктивное логическое программирование» . Журнал логического программирования . 44 (1–3): 1–4. дои : 10.1016/S0743-1066(99)00078-3 .
• Денекер, М.; Какас, AC (2002). «Похищение в логическом программировании» . В Какасе, AC; Садри, Ф. (ред.). Вычислительная логика: логическое программирование и не только: эссе в честь Роберта А. Ковальски . Конспекты лекций по информатике. Том. 2407. Спрингер. стр. 402–437. ISBN  978-3-540-43959-2 .
• Пул, Д. (1993). «Вероятностное похищение Хорна и байесовские сети» (PDF) . Искусственный интеллект . 64 (1): 81–129. дои : 10.1016/0004-3702(93)90061-F .
• Эспозито, Ф.; Ферилли, С.; Базиль, ТМА; Ди Мауро, Н. (февраль 2007 г.). «Вывод теорий похищения для решения проблемы неполноты обучения первого порядка» (PDF) . Знания и информационные системы . 11 (2): 217–242. дои : 10.1007/s10115-006-0019-5 . S2CID   10699982 . Архивировано из оригинала (PDF) 17 июля 2011 г.

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

• ACLP
• список управления доступом
• СКИФФ
• Асистема