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

Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Февраль 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Синтаксис

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

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

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

   false: - A1, ..., An, а не B1, ..., не Bm.

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

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

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

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

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

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

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

Пример 1

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

  Трава мокрая если шел дождь.
  Трава мокрая если спринклер был включен.
  Солнце светило.

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

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

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

Пример 2

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

  X - гражданин если X родился в США.
  X - гражданин если X родился за пределами США и X - житель США и X натурализован.
  X - гражданин если X родился за пределами США и Y - мать X и Y гражданин и X зарегистрирован.
  Мэри - мать Джона.
  Мэри - гражданка.

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

  ложный если Джон - житель США.

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

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

Пример 3

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

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

   подача(лактоза) :- делать(пермеаза), делать(галактозидаза).   делать(Фермент) :- код(Ген, Фермент), выражать(Ген).   выражать(лак(Икс)) :- количество(глюкоза, низкий), количество(лактоза, Здравствуй).   выражать(лак(Икс)) :- количество(глюкоза, средний), количество(лактоза, средний).   код(лак(у), пермеаза).   код(лак(z), галактозидаза).   температура(низкий) :- количество(глюкоза, низкий).

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

   ложный :- количество(S, V1), количество(S, V2), V1 ≠ V2.

Abducibles (A)

   abducible_predicate(количество).

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

${displaystyle {egin {case} Delta _ {1} = {{ext {количество (лактоза, привет), количество (глюкоза, низкий)}}} Delta _ {2} = {{ext {количество (лактоза, средний) , количество (глюкоза, среда)}}} конец {случаи}}}$

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

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

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

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

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

• ${displaystyle Pcup Delta models G}$
• ${displaystyle Pcup Delta models IC}$
• ${displaystyle Pcup Delta}$ является последовательный

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

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

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

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

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

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

Примечания

Рекомендации

внешняя ссылка

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