Пример реального мира Объединения в Логике первого порядка?
Я знаю, что это - только часть вопроса о программировании, но в данный момент, я делаю определенное логическое программирование. Одной вещью, которую я все еще не понимаю правильно, является Объединение в Логике первого порядка.
Я прочитал статью Wikipedia, и более или менее ясно, что цель ищет слово, которое объединяет два предложения... Существуют также примеры в этой статье, но я просто не понимаю, почему это должно быть полезно. Кто-либо может дать пример с объектами реального мира вместо A, B, C, и т.д.? Я надеюсь, что это поможет мне понять.Спасибо
3 ответа
Если вы смотрите на реальные примеры, где унификация используется и полезна, взгляните на основанные на унификации грамматики, которые используются в компьютерной лингвистике, например HPSG и LFG. На первый взгляд это выглядит как еще одна разновидность объединения, но на самом деле это одно и то же.
Основанная на унификации грамматика может рассматриваться как CFG (контекстно-свободная грамматика), в которой продукция расширяется за счет унификации. Каждый термин в CGF получает AVM (матрицу значений атрибутов), которая представляет собой направленный ациклический граф функций и значений. Идея здесь чем-то похожа на атрибутные грамматики, используемые в компиляторах.
Представьте себе эту игрушечную грамматику:
S -> NP VP
NP -> Kim
NP -> The cats
VP -> V NP
V -> see
V -> sees
У нас здесь в соглашении есть небольшая избыточная генерация:
* Кошки видят Ким [S [NP The cats] [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 ]
В нашей расширенной игрушечной грамматике "Kim see the cats" отклоняется, потому что NP и VP не будут объединяться, имея различное значение для свойства AGR. При синтаксическом разборе мы объединяем AVM вместе и, следовательно, очень сильно получаем выразительность, что упрощает грамматическим инженерам написание грамматик. Обычно UBG с широким охватом имеет порядка сотни правил, в то время как эквивалентные CFG, которые могут не существовать, CFG с унификацией являются полными по Тьюрингу, будут иметь правила в количестве тысяч или более.
Логическое программирование, AFAIK, в значительной степени объединение. Вы предоставляете интерпретатору инструкцию, и интерпретатор пытается объединить ее с тем, что он знает как «истина», то есть с чем-то, что находится в его базе данных.
например.
cat(tom) :- true.
Утверждает, что Том - кот.
Затем вы можете запросить
?- cat(X).
, и пролог вернет
X = tom
Пролог просматривает свою базу данных и пытается объединить предоставленный вами оператор ( cat (X) ) с фактом, который он уже «знает». В этом случае он находит cat (tom) и, таким образом, может сказать вам, что X = tom .
Спасибо за подробные ответы. Теперь я действительно понял. Однако я хотел бы записать здесь пример, который я нашел в книге Стюарта Рассела и Питера Норвига «Искусственный интеллект: современный подход», на тот случай, если кто-то снова задаст тот же вопрос. Я думаю, что в этом ответе используется очень практичный подход:
Правила снятого вывода требуют нахождения замены, которые делают разные логические выражения выглядят одинаково. Этот процесс называется объединением и является ключевым компонентом всего первого порядка алгоритмы вывода. UNIFY алгоритм занимает два предложения и возвращает объединитель для них, если один существуют.
Давайте посмотрим на несколько примеров того, как UNIFY должны вести себя хорошо. Предположим, у нас есть query Knows (John, x): кем Джон знать? Некоторые ответы на этот запрос могут можно найти, найдя все предложения в база знаний, объединяющая Знает (Джон, 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 не может принять ценности Джона и Елизавета заодно.