Реальный пример объединения в логике первого порядка? - PullRequest
Новая
       38

Реальный пример объединения в логике первого порядка?

6 голосов
/ 03 июня 2010

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

Я прочитал статью в Википедии , и более или менее ясно, что целью является поиск термина, объединяющего два предложения ... В этой статье также есть примеры, но я просто не понимаю указать, почему это должно быть полезно. Кто-нибудь может привести пример с объектами реального мира вместо A, B, C и т. Д.? Я надеюсь, что это поможет мне понять. Спасибо

Ответы [ 3 ]

5 голосов
/ 03 июня 2010

Спасибо вам за эти подробные ответы.Теперь я действительно понимаю это.Однако я хотел бы привести здесь пример, который я нашел в книге «Искусственный интеллект: современный подход» Стюарта Рассела и Питера Норвига, если кто-то снова ищет тот же вопрос.Я думаю, что в этом ответе используется очень практичный подход:

Поднятые правила вывода требуют поиска подстановок, которые делают разные логические выражения одинаковыми.Этот процесс называется унификацией и является ключевым компонентом всех алгоритмов логического вывода первого порядка.Алгоритм UNIFY берет два предложения и возвращает для них унификатор, если он существует.

Давайте рассмотрим несколько примеров того, как UNIFY должен себя вести.Предположим, у нас есть запрос Знает (Джон, х): кого знает Джон?Некоторые ответы на этот запрос можно найти, найдя все предложения в базе знаний, которые объединяются с Knows (John, x).Вот результаты объединения с четырьмя различными предложениями, которые могут быть в базе знаний: 

UNIFY(Knows(John, x), Knows(John, Jane)) = {x/Jane}
UNIFY(Knows(John, x), Knows(y, Bill)) = {x/Bill, y/John}
UNIFY(Knows(John, x), Knows(y, Mother(y))) = {y/John, x/Mother(John)}
UNIFY(Knows(John, x), Knows(x, Elisabeth)) = fail

Последнее объединение не удается, потому что x не может принимать значения Джона и Элизабет одновременновремя.

2 голосов
/ 03 июня 2010

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

Грамматику, основанную на унификации, можно рассматривать как CFG (контекстно-свободную грамматику), в которой производство расширяется с помощью унификации. Каждый член в CGF получает AVM (матрицу значений атрибутов), которая представляет собой ориентированный ациклический граф признаков и значений. Идея здесь сродни грамматике атрибутов, используемой в компиляторах.

Представьте себе эту игрушечную грамматику: 

 S -> NP VP  
 NP -> Kim  
 NP -> The cats  
 VP -> V NP  
 V -> see  
 V -> sees

У нас есть небольшое превышение в соглашении:

* Кошки видят Ким [S [NP Коты] [VP [V видит] [NP Kim]]]

Чтобы исправить это, мы могли бы уточнить CFG, включив в него понятие соглашения: 

 S -> NP_sg VP_sg  
 S -> NP_sg VP_pl  
 NP_sg -> Kim  
 NP_pl -> The cats  
 VP_sg -> V_sg NP_sg  
 VP_sg -> V_sg NP_pl  
 V_sg -> sees  
 V_pl -> see  
 VP_pl -> V_pl NP_pl  
 VP_pl -> V_pl NP_sg

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

 S -> NP VP , C = A unified with B.  
 NP -> kim /[ AGR sg ]. We mark Kim as being singular   
 NP -> The cats / [ AGR pl ]  
 VP[ AGR #1 ] -> V [ AGR #1 ] NP

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

 V -> See / [ AGR pl ]  
 V -> Sees / [ AGR sg ]

С нашей расширенной грамматикой игрушек «Ким смотри на кошек» отклоняется, потому что NP и VP не будут объединяться, имея другое значение для своей функции AGR. Когда мы анализируем, мы объединяем AVM вместе, и поэтому получаем большую выразительность, облегчая грамматическим инженерам писать грамматики. Обычно UBG с широким охватом имеет порядок сотен правил, в то время как эквивалентные CFG, которые могут не существовать, CFG с унификацией являются полными по Тьюрингу, будут иметь правила в количестве тысяч и более.

Подробнее см. HPSG и биогаз .

1 голос
/ 03 июня 2010

Логическое программирование, AFAIK, почти все объединение. Вы предоставляете утверждение интерпретатору, и интерпретатор пытается объединить его с чем-то, что, как он знает, является «истинным», то есть чем-то, что находится в его базе данных.

, например 

cat(tom) :- true.

Утверждает, что Том кот.

Тогда вы можете запросить 

?- cat(X).

и пролог вернется 

 X = tom

Пролог просматривает свою базу данных и пытается объединить предоставленную вами инструкцию (cat(X)) с фактом, который он уже «знает». В этом случае он находит cat(tom) и, таким образом, может сказать вам, что X=tom.

...