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

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

Синтаксис

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

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

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

 ложно:- A1,...,An, а не B1, ..., а не 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$ следующие предложения:

 Трава мокрая,  если  шел дождь. 

  Трава мокрая  , если  был включен разбрызгиватель. 

  Солнце светило.
 

Сводимые предикаты в $A$ являются «шел дождь» и «работал разбрызгиватель» и являются единственным ограничением целостности в ${\mathit {IC}}$ является:

 ложь,  если  шел дождь и светило солнце.
 

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

Пример 2

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

 X является гражданином  , если  X родился в США. 

  X является гражданином  , если  X родился за пределами США  ,  X является резидентом США  и  X натурализован. 

  X является гражданином  , если  X родился за пределами США  и  Y является матерью X  , а  Y является гражданином  и  X зарегистрирован. 

  Мэри — мать Джона. 

  Мэри является гражданкой.
 

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

 false  , если  Джон проживает в США.
 

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

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

Пример 3

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

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

   корма  (  лактоза  )   :-   делают  (  пермеаза  ),   делают  (  галактозидаза  ). 
     сделать  (  Фермент  )   : -   закодировать  (  Ген  ,   Фермент  ),   выразить  (  Ген  ). 
     экспресс  (  лак  (  Х  ))   :-   количество  (  глюкоза  ,   низкий  ),   количество  (  лактоза  ,   привет  ). 
     экспресс  (  lac  (  X  ))   :-   количество  (  глюкоза  ,   среда  ),   количество  (  лактоза  ,   среда  ). 
     код  (  лак  (  у  ),   пермеаза  ). 
     код  (  lac  (  z  ),   галактозидаза  ). 
     температура  (  низкая  )   :-   количество  (  глюкоза  ,   низкая  ). 

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

   ложь   :-   сумма  (  S  ,   V1  ),   сумма  (  S  ,   V2  ),   V1   ≠   V2  . 

Отводящие предметы (А)

   abducible_predicate  (  сумма  ). 

Цель проблемы – $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 может имитировать отрицание как сбой в обычном логическом программировании.

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

может летать  (  X  )   :-   птица  (  X  ),   а не  (  ненормальная_летающая_ птица  (  X  )). 
  ненормальная_летающая_птица  (  X  ):-   раненая  (  X  ). 
  птица  (  Джон  ). 
  птица  (  Мэри  ). 
  ранен  (  Джон  ). 

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

может летать  (  X  )   :-   птица  (  X  ),   нормальная_летающая_ птица  (  X  ). 
  ложь   : -   нормальная_летающая_птица  (  X  ),   раненая  (  X  ). 
  птица  (  Джон  ). 
  птица  (  Мэри  ). 
  ранен  (  Джон  ). 

Сводимый предикат 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, истинно, а другое, в котором 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
• список управления доступом
• СКИФФ
• Система