Miesiąc: styczeń 2022

Druga główna rodzina algorytmów wnioskowania logicznego używa łańcuchów wstecznych na określonych klauzulach. Algorytmy te działają wstecz od celu, łącząc reguły, aby znaleźć znane fakty, które wspierają dowód.

Algorytm wiązania wstecznego

Poniżej mamy algorytm tworzenia łańcucha wstecznego dla klauzul określonych. FOL-BC-ASK(KB,goal) zostanie udowodnione, jeśli baza wiedzy zawiera regułę postaci lhs=> cel , gdzie lhs (lewa strona) jest listą spójników. Fakt atomowy, taki jak American(West), jest uważany za klauzulę, której lhs jest pustą listą. Teraz zapytanie zawierające zmienne można udowodnić na wiele sposobów. Na przykład zapytanie Person(x) można udowodnić za pomocą podstawienia {x/John} oraz {x/Richard}. Dlatego implementujemy FOL-BC-ASK jako generator – funkcję, która zwraca wiele razy, za każdym razem dając jeden możliwy wynik

Tworzenie łańcuchów wstecznych jest rodzajem przeszukiwania AND/OR — część OR, ponieważ zapytanie o cel może być udowodnione przez dowolną regułę w bazie wiedzy, oraz część AND, ponieważ wszystkie spójniki w lhs klauzuli muszą zostać udowodnione. FOL-BC-OR działa, pobierając wszystkie klauzule, które mogą ujednolicić się z celem, standaryzując zmienne w klauzuli jako zupełnie nowe zmienne, a następnie, jeśli prawa strona klauzuli rzeczywiście ujednolicają się z celem, udowadniając każdą koniunkcję w lewą stronę, używając FOL-BC-AND. Ta funkcja działa, udowadniając każdą z koniunkcji po kolei, śledząc skumulowane podstawienie w miarę postępu. Rysunek to drzewo dowodowe dla wyprowadzenia Criominal(West) ze zdań (9.3) do (9.10).

Łańcuch wsteczny, jak to opisaliśmy, jest wyraźnie algorytmem wyszukiwania w głąb. Oznacza to, że jego wymagania przestrzenne są liniowe w rozmiarze dowodu. Oznacza to również, że łańcuch wsteczny (w przeciwieństwie do łańcucha do przodu) ma problemy z powtarzającymi się stanami i niekompletnością. Pomimo tych ograniczeń łączenie wsteczne okazało się popularne i skuteczne w językach programowania logicznego.

Innym źródłem nieefektywności jest to, że łańcuchowanie w przód sprawia, że ​​wszystkie dopuszczalne wnioskowania oparte są na znanych faktach, nawet jeśli są one nieistotne dla celu. W naszym przykładzie kryminalnym nie było reguł pozwalających na wyciąganie nieistotnych wniosków. Ale gdyby istniało wiele zasad opisujących zwyczaje żywieniowe Amerykanów lub komponenty i ceny pocisków, wówczas FOL-FC-ASK wyciągnąłby nieistotne wnioski. Jednym ze sposobów uniknięcia wyciągania nieistotnych wniosków jest użycie łańcucha wstecznego, jak opisano w Sekcji 9.4 . Innym sposobem jest ograniczenie łańcucha w przód do wybranego podzbioru reguł, jak w PL-FC-ENTAILS? . Trzecie podejście pojawiło się w dziedzinie dedukcyjnych baz danych, które są bazami danych o dużej skali, podobnie jak relacyjne bazy danych, ale które wykorzystują łańcuchowanie w przód jako standardowe narzędzie wnioskowania, a nie zapytania SQL. Chodzi o to, aby przepisać zestaw reguł, korzystając z informacji z celu, tak aby podczas wnioskowania w przód brane były pod uwagę tylko odpowiednie powiązania zmiennych — te należące do tak zwanego zestawu magicznego. Na przykład, jeśli celem jest Criminal(West) , reguła kończąca Criminal(x) zostanie przepisana tak, aby zawierała dodatkową koniunkcję, która ogranicza wartość x :

Fakt, że Magic(West) jest również dodany do KB. W ten sposób, nawet jeśli baza wiedzy zawiera fakty dotyczące milionów Amerykanów, tylko pułkownik West będzie brany pod uwagę podczas procesu wnioskowania naprzód. Kompletny proces definiowania zestawów magicznych i przepisywania bazy wiedzy jest zbyt skomplikowany, aby można było się tu zajmować, ale podstawową ideą jest wykonanie pewnego rodzaju „ogólnego” wnioskowania wstecznego od celu, aby ustalić, które powiązania zmiennych muszą być ograniczone . Podejście zestawów magicznych można zatem traktować jako rodzaj hybrydy między wnioskowaniem postępującym a przetwarzaniem wstępnym wstecznym.

Kiedy pokazaliśmy, jak działa łańcuchowanie do przodu na przykładzie przestępstwa, oszukaliśmy. W szczególności pominęliśmy niektóre dopasowania reguł wykonane przez algorytm. Na przykład w drugiej iteracji reguła

dopasowania przeciwko Missile(M1) i oczywiście wniosek Weapon(M1) jest już znana, więc nic się nie dzieje. Takiego nadmiarowego dopasowania reguł można uniknąć, jeśli poczynimy następującą obserwację: Każdy nowy fakt wywnioskowany w iteracji t musi być wyprowadzony z co najmniej jednego nowego faktu wywnioskowanego w iteracji t-1 . Jest to prawdą, ponieważ każde wnioskowanie, które nie wymaga nowego faktu z iteracji t-1, mogło zostać wykonane już w iteracji t-1. Ta obserwacja prowadzi naturalnie do przyrostowego algorytmu łańcucha do przodu, w którym podczas iteracji sprawdzamy regułę tylko wtedy, gdy jej założenie zawiera koniunkcję pi, która łączy się z faktem p’i nowo wywnioskowanym w iteracji t-1 . Krok dopasowywania reguły naprawia następnie pi, aby pasowało do p’i , ale pozwala innym koniunkcjom reguły dopasować się do faktów z dowolnej poprzedniej iteracji. Algorytm ten generuje dokładnie te same fakty w każdej iteracji, co algorytm na rysunku 9.3, ale jest znacznie bardziej wydajny. Dzięki odpowiedniemu indeksowaniu łatwo jest zidentyfikować wszystkie reguły, które mogą zostać wywołane przez dany fakt, a wiele rzeczywistych systemów działa w trybie „aktualizacji”, w którym łańcuchowanie w przód następuje następnego nowego faktu. Zazwyczaj tylko niewielka część reguł w bazie wiedzy jest faktycznie uruchamiana przez dodanie danego faktu. Oznacza to, że wielokrotne konstruowanie dopasowań częściowych, które mają pewne niezadowalające w odpowiedzi na każde TELL. Wnioskowania przepływają kaskadowo przez zbiór reguł, aż do osiągnięcia ustalonego punktu, a następnie proces rozpoczyna się od nowa dla przesłanki, wymaga wiele zbędnej pracy. Nasz przykład przestępstwa jest raczej zbyt mały, aby to skutecznie pokazać, ale zauważ, że częściowe dopasowanie jest konstruowane w pierwszej iteracji między regułą

i faktem American(West). To częściowe dopasowanie jest następnie odrzucane i odbudowywane w drugiej iteracji (gdy reguła się powiedzie). Lepiej byłoby zachować i stopniowo uzupełniać częściowe dopasowania w miarę pojawiania się nowych faktów, niż je odrzucać. Algorytm Rete jako pierwszy rozwiązał ten problem. Algorytm wstępnie przetwarza zestaw reguł w bazie wiedzy w celu zbudowania sieci przepływu danych, w której każdy węzeł jest literałem z założenia reguły. Powiązania zmiennych przepływają przez sieć i są odfiltrowywane, gdy nie pasują do literału. Jeśli dwa literały w regule mają wspólną zmienną — na przykład Sells(x,y,z) Λ Hostile(z) w przykładzie przestępstwa — wówczas powiązania z każdego literału są filtrowane przez węzeł równości. Powiązanie zmiennej osiągające węzeł dla literału n-argumentowego, takiego jak Sells(x,y,z), może wymagać oczekiwania na ustanowienie powiązań dla innych zmiennych, zanim proces będzie mógł być kontynuowany. W dowolnym momencie stan sieci Rete przechwytuje wszystkie częściowe dopasowania reguł, unikając dużej ilości przeliczeń.

Sieci Rete i różne ich ulepszenia były kluczowym elementem tak zwanych systemów produkcyjnych, które były jednymi z najwcześniejszych systemów łańcucha w przód, które były szeroko stosowane. System XCON (pierwotnie nazywany R1) został zbudowany w oparciu o architekturę systemu produkcyjnego. XCON zawierał kilka tysięcy reguł projektowania konfiguracji komponentów komputerowych dla klientów Digital Equipment Corporation. Był to jeden z pierwszych wyraźnych sukcesów komercyjnych w powstającej dziedzinie systemów eksperckich. Wiele innych podobnych systemów zostało zbudowanych przy użyciu tej samej podstawowej technologii, która została zaimplementowana w języku ogólnego przeznaczenia OPS-5. Systemy produkcyjne są również popularne w architekturach kognitywnych – czyli modelach ludzkiego rozumowania – takich jak ACT i SOAR. W takich systemach „pamięć robocza” systemu modeluje ludzką pamięć krótkotrwałą, a wytwory są częścią pamięci długotrwałej. W każdym cyklu operacji produkcje są dopasowywane do pamięci roboczej faktów. Produkcja, której warunki są spełnione, może dodawać lub usuwać fakty z pamięci roboczej. W przeciwieństwie do typowej sytuacji w bazach danych, systemy produkcyjne często mają wiele reguł i stosunkowo niewiele faktów. Dzięki odpowiednio zoptymalizowanej technologii dopasowywania, systemy mogą działać w czasie rzeczywistym z dziesiątkami milionów reguł.

Algorytm łączenia do przodu został zaprojektowany z myślą o łatwości zrozumienia, a nie wydajności. Istnieją trzy źródła nieefektywności. Po pierwsze, wewnętrzna pętla algorytmu próbuje dopasować każdą regułę do każdego faktu w bazie wiedzy. Po drugie, algorytm ponownie sprawdza każdą regułę w każdej iteracji, nawet jeśli w bazie wiedzy wprowadzono bardzo niewiele dodatków. Po trzecie, algorytm może generować wiele faktów, które są nieistotne dla celu. Po kolei zajmujemy się każdą z tych kwestii.

Dopasowywanie reguł do znanych faktów

Problem dopasowania przesłanki przepisu do stanu faktycznego w bazie wiedzy może wydawać się dość prosty. Załóżmy na przykład, że chcemy zastosować regułę

Następnie musimy znaleźć wszystkie fakty, które łączą się z Missile(x) ; w odpowiednio zindeksowanej bazie wiedzy można to zrobić w stałym czasie na fakt. Rozważmy teraz regułę, taką jak

Ponownie możemy znaleźć wszystkie obiekty posiadane przez Nono w stałym czasie na obiekt; wtedy dla każdego obiektu moglibyśmy sprawdzić, czy jest to pocisk. Jeśli jednak baza wiedzy zawiera wiele obiektów należących do Nono i bardzo mało pocisków, to lepiej najpierw znaleźć wszystkie pociski, a następnie sprawdzić, czy należą one do Nono. To jest problem porządkowania koniunkcji: znajdź kolejność, aby rozwiązać przesłankę reguły tak, aby zminimalizować całkowity koszt. Okazuje się, że znalezienie optymalnej kolejności jest NP-trudne, ale dostępne są dobre heurystyki. Na przykład heurystyka minimalnych pozostałych wartości (MRV) zastosowana dla CSP w rozdziale 6 sugerowałaby nakazanie koniunkcjom wyszukiwania pocisków w pierwszej kolejności, jeśli jest ich mniej niż obiektów należących do Nono. Związek między tym dopasowaniem wzorca a spełnieniem ograniczeń jest w rzeczywistości bardzo bliski. Możemy zobaczyć każdą koniunkcję jako ograniczenie na zmiennych, które zawiera — na przykład Missile(x) jest ograniczeniem jednoargumentowym na . Rozszerzając tę ​​ideę, możemy wyrazić każdy CSP o skończonej domenie jako pojedynczą klauzulę określoną wraz z pewnymi powiązanymi faktami podstawowymi. Rozważ problem kolorowania mapy pokazany na rysunku (a).

Równoważne sformułowanie w postaci pojedynczego zdania określonego przedstawiono na rysunku (b). Oczywiście wniosek Colorable() można wywnioskować tylko wtedy, gdy dostawca CSP ma rozwiązanie. Ponieważ dostawcy usług internetowych na ogół uwzględniają problemy 3-SAT jako przypadki specjalne, możemy stwierdzić, że dopasowanie określonej klauzuli do zestawu faktów jest NP-trudne.

Może wydawać się dość przygnębiające, że łączenie w przód ma problem z NP-trudnym dopasowaniem w wewnętrznej pętli. Są trzy sposoby na pocieszenie:

* Możemy sobie przypomnieć, że większość reguł w rzeczywistych bazach wiedzy jest raczej małych i prostych (jak reguły w naszym przykładzie przestępstwa) niż dużych i złożonych (jak sformułowanie CSP na rysunku 9.5). W świecie baz danych powszechne jest założenie, że zarówno rozmiary reguł, jak i arności predykatów są ograniczone przez stałą i martwienie się tylko o złożoność danych — to znaczy złożoność wnioskowania jako funkcję liczby faktów podstawowych w bazę wiedzy. Łatwo wykazać, że złożoność danych w łańcuchu do przodu jest wielomianowa, a nie wykładnicza.

* Możemy rozważyć podklasy reguł, dla których dopasowanie jest efektywne. Zasadniczo każda klauzula Datalog może być postrzegana jako definiująca CSP, więc dopasowanie będzie wykonalne tylko wtedy, gdy odpowiedni CSP jest wykonalny. Część 6 opisuje kilka wykonalnych rodzin dostawcy usług internetowych. Na przykład, jeśli wykres ograniczeń (graf, którego węzły są zmiennymi, a łącza są ograniczeniami) tworzy drzewo, CSP można rozwiązać w czasie liniowym. Dokładnie ten sam wynik dotyczy dopasowania reguł. Na przykład, jeśli usuniemy Australię Południową z mapy , otrzymaną klauzulą ​​jest

co odpowiada zredukowanemu CSP pokazanemu na Rysunek 6.12 na stronie 201. Algorytmy rozwiązywania CSP o strukturze drzewa można zastosować bezpośrednio do problemu dopasowania reguł.

* Możemy spróbować wyeliminować nadmiarowe próby dopasowywania reguł w algorytmie łańcucha do przodu, jak opisano poniżej.

Poniżej przedstawiono prosty algorytm wnioskowania łańcuchowego w przód. Wychodząc od znanych faktów uruchamia wszystkie reguły, których przesłanki są spełnione, dodając ich wnioski do znanych faktów. Proces jest powtarzany do momentu uzyskania odpowiedzi na zapytanie (zakładając, że wymagana jest tylko jedna odpowiedź) lub nie zostaną dodane żadne nowe fakty. Zauważ, że fakt nie jest „nowy”, jeśli jest tylko zmianą nazwy znanego faktu – zdanie jest zmianą nazwy innego, jeśli są one identyczne z wyjątkiem nazw zmiennych. Na przykład Likes(x,IceCream) i Likes(y,IceCream) są wzajemnymi zmianami nazw. Obaj mają na myśli to samo: „Każdy lubi lody”.

Używamy naszego problemu przestępczości, aby zilustrować FOL-FC-ASK. Zdania implikacyjne dostępne do tworzenia łańcuchów to (9,3), (9,6), (9,7) i (9,8). Wymagane są dwie iteracje:

* W pierwszej iteracji reguła (9.3) ma niezaspokojone przesłanki.

Reguła (9.6) jest spełniona z {x/M₁} i Sells(West,M₁,Nono) jest dodawana.

Reguła (9.7) jest spełniona z {x/M₁} i Weapon(M₁) została dodana.

Reguła (9.8) jest spełniona z {x/Nono}  i Hostile(Nono) została dodana.

* W drugiej iteracji reguła (9.3) jest spełniona z {x/West, y/M₁, , z/Nano} , i dodaje się wnioskowanie Criminal(West). Rysunek przedstawia wygenerowane drzewo dowodowe.

Zauważ, że w tym momencie nie są możliwe żadne nowe wnioskowania, ponieważ każde zdanie, które może zostać zakończone przez łańcuchowanie w przód, jest już wyraźnie zawarte w KB. Taka baza wiedzy nazywana jest stałym punktem procesu wnioskowania. Punkty stałe osiągnięte przez łańcuchowanie w przód z klauzulami określonymi pierwszego rzędu są podobne do tych dla łańcuchów zdaniowych w przód; zasadnicza różnica polega na tym, że punkt stały pierwszego rzędu może zawierać uniwersalnie kwantyfikowalne zdania atomowe.

FOL-FC-ASK jest łatwy do analizy. Po pierwsze, jest to dźwięk, ponieważ każde wnioskowanie jest tylko zastosowaniem Generalized Modus Ponens, którym jest dźwięk. Po drugie, jest kompletny dla baz wiedzy o klauzulach określonych; oznacza to, że odpowiada na każde zapytanie, którego odpowiedzi wynikają z dowolnej bazy wiedzy zawierającej klauzule określone. W przypadku baz wiedzy Datalog, które nie zawierają symboli funkcji, dowód kompletności jest dość łatwy. Zaczynamy od policzenia liczby możliwych faktów, które można dodać, co określa maksymalną liczbę iteracji. Niech będzie maksymalną arnością (liczbą argumentów) dowolnego predykatu, liczbą predykatów i liczbą stałych symboli. Najwyraźniej nie może być więcej niż pn^k wyraźne fakty podstawowe, więc po tylu iteracjach algorytm musiał osiągnąć ustalony punkt. Następnie możemy przedstawić argument bardzo podobny do dowodu zupełności dla zdania naprzód. Szczegóły, jak dokonać przejścia od kompletności zdaniowej do zupełności pierwszego rzędu, podano dla algorytmu rozwiązywania.

W przypadku ogólnych klauzul określonych z symbolami funkcji, FOL-FC-ASK może generować nieskończenie wiele nowych faktów, więc musimy być bardziej ostrożni. W przypadku, gdy pociąga za sobą odpowiedź na zdanie zapytania, musimy odwołać się do twierdzenia Herbranda (str. 282), aby ustalić, że algorytm znajdzie dowód. (Patrz rozdział 9.5 w sprawie rozwiązania). Jeśli na zapytanie nie ma odpowiedzi, w niektórych przypadkach algorytm może się nie zakończyć. Na przykład, jeśli baza wiedzy zawiera aksjomaty Peano

następnie łańcuchowanie w przód dodaje NatNum(S(0)) , NatNum(S(0))) , NatNum(S(0)))) i tak dalej. Ten problem jest generalnie nieunikniony. Podobnie jak w przypadku ogólnej logiki pierwszego rzędu, wywodzenie z określonymi klauzulami jest częściowo rozstrzygalne.

Zdania określone pierwszego rzędu to alternatywy literałów, z których dokładnie jeden jest dodatni. Oznacza to, że zdanie określone jest albo atomowe, albo jest implikacją, której poprzednikiem jest koniunkcja literałów dodatnich, a następstwem jest pojedynczy literał dodatni. Kwantyfikatory egzystencjalne są niedozwolone, a kwantyfikatory uniwersalne są pozostawione niejawne: jeśli widzisz w zdaniu określonym, oznacza to, że istnieje kwantyfikator niejawny  . Typowa klauzula ostateczna pierwszego rzędu wygląda tak:

ale literały King(John) i Greedy(x)także liczą się jako zdania określone. Literały pierwszego rzędu może zawierać zmienne, więc Greedy(y) jest interpretowane jako „wszyscy są chciwi” (uniwersalny kwantyfikator jest ukryty). Załóżmy, że zdania określone będą działać w reprezentowaniu następującego problemu:

Prawo mówi, że dla Amerykanina przestępstwem jest sprzedawanie broni wrogim narodom. Kraj Nono, wróg Ameryki, ma kilka pocisków, a wszystkie jego pociski zostały mu sprzedane przez pułkownika Westa, który jest Amerykaninem.

Najpierw przedstawimy te fakty jako zdania określone pierwszego rzędu:

„…sprzedawanie broni wrogim narodom przez Amerykanina jest przestępstwem”:

(9.3)

„Nono … ma kilka pocisków”. Zdanie jest przekształcane w dwa zdania określone przez egzystencjalną instancję, wprowadzając nową stałą M₁ :

(9.4)

(9.5)

„Wszystkie jej pociski zostały mu sprzedane przez pułkownika Westa”:

(9.6)

Musimy również wiedzieć, że pociski to broń:

(9.7)

musimy wiedzieć, że wróg Ameryki jest uważany za „wrogiego”:

(9.8)

„West który jest Amerykaninem…”:

American(West) (9.9)

„Kraj Nono, wróg Ameryki… ”: „Kraj Nono, wróg Ameryki… ”:

(9.10)

Tak się składa, że ta baza wiedzy jest bazą wiedzy Datalog: Datalog to język składający się z określonych klauzul pierwszego rzędu bez symboli funkcji. Datalog otrzymuje swoją nazwę, ponieważ może reprezentować typ instrukcji wykonywanych w relacyjnych bazach danych. Brak symboli funkcji znacznie ułatwia wnioskowanie.

Wcześniej pokazaliśmy algorytm łańcucha do przodu dla baz wiedzy zdań określonych zdań. Tutaj rozszerzamy ten pomysł, aby objąć zdania określone pierwszego rzędu. Oczywiście istnieje kilka zdań logicznych, których nie można sformułować jako zdania określonego, a zatem nie można ich obsłużyć w tym podejściu. Ale zasady formy Antecedent =>  Consequent są wystarczające, aby objąć szeroką gamę interesujących systemów rzeczywistych.

U podstaw funkcji TELL, ASK i ASKVARS używanych do informowania i sprawdzania bazy wiedzy są bardziej prymitywne funkcje STORE i FETCH. STORE(s) przechowuje zdanie s w bazie wiedzy, a FETCH(q) zwraca wszystkie unifikatory w taki sposób, że zapytanie q łączy się z pewnym zdaniem w bazie wiedzy. Problem, którego użyliśmy do zilustrowania unifikacji – znajdowanie wszystkich faktów, które się z nimi łączą Knows(John,s) — jest przykładem FETCHING. Najprostszym sposobem na zaimplementowanie STORE i FETCH jest przechowywanie wszystkich faktów na jednej długiej liście i ujednolicenie każdego zapytania względem każdego elementu listy. Taki proces jest nieefektywny, ale działa. Pozostała część tej sekcji przedstawia sposoby zwiększenia wydajności pobierania. Możemy zwiększyć wydajność FETCH, zapewniając, że próby ujednolicenia są podejmowane tylko w przypadku zdań, które mają pewną szansę na ujednolicenie. Na przykład nie ma sensu próbować unifikować Knows(John,x) z Brother (Richard, John). Takich unifikacji możemy uniknąć, indeksując fakty w bazie wiedzy. Prosty schemat zwany indeksowaniem predykatów umieszcza wszystkie fakty Knows w jednym pojemniku, a wszystkie fakty Brothers w drugim. Segmety można przechowywać w tabeli mieszającej, aby zapewnić wydajny dostęp.

Indeksowanie predykatów jest przydatne, gdy istnieje wiele symboli predykatów, ale tylko kilka klauzul dla każdego symbolu. Czasami jednak predykat zawiera wiele klauzul. Załóżmy na przykład, że organy podatkowe chcą śledzić, kto kogo zatrudnia, używając predykatu Employs(x,y) . Byłby to bardzo duży segment z być może milionami pracodawców i dziesiątkami milionów pracowników. Odpowiedź na zapytanie, takie jak Employs(x,Richard)  z indeksowaniem predykatów, wymagałaby przeskanowania całego zasobnika. W przypadku tego konkretnego zapytania pomocne byłoby, gdyby fakty były indeksowane zarówno według predykatu, jak i drugiego argumentu, być może przy użyciu połączonego klucza tablicy mieszającej. Następnie moglibyśmy po prostu skonstruować klucz z zapytania i pobrać dokładnie te fakty, które łączą się z zapytaniem. W przypadku innych zapytań, takich jak Employs(IBM,y), musielibyśmy zindeksować fakty, łącząc predykat z pierwszym argumentem. Dlatego fakty mogą być przechowywane pod wieloma kluczami indeksu, dzięki czemu są natychmiast dostępne dla różnych zapytań, z którymi mogą się ujednolicić. Mając dane zdanie, które ma być zapisane, możliwe jest skonstruowanie indeksów dla wszystkich możliwych zapytań, które się z nim ujednolicają. W rzeczywistości Employs(IBM,Richard) są zapytaniami

Zapytania te tworzą sieć subsumpcji, jak pokazano na rysunku (a). Krata ma kilka ciekawych właściwości. Potomek dowolnego węzła w sieci jest uzyskiwany od rodzica przez pojedyncze podstawienie; a „najwyższy” wspólny potomek dowolnych dwóch węzłów jest wynikiem zastosowania ich najbardziej ogólnego unifikatora. Zdanie z powtarzającymi się stałymi ma nieco inną siatkę, jak pokazano na rysunku (b). Chociaż symbole funkcyjne nie są pokazane na rysunku, one również mogą być włączone do struktury sieci.

W przypadku predykatów z niewielką liczbą argumentów dobrym kompromisem jest utworzenie indeksu dla każdego punktu w sieci subsumpcji. Wymaga to trochę więcej pracy w czasie przechowywania, ale przyspiesza czas wyszukiwania. Jednak w przypadku predykatu  z n argumentami krata zawiera O(2ⁿ) węzłów. Jeśli symbole funkcji są dozwolone, liczba węzłów jest również wykładnicza w rozmiarze terminów w zdaniu, które mają być przechowywane. Może to prowadzić do ogromnej liczby indeksów. Musimy jakoś ograniczyć indeksy do tych, które prawdopodobnie będą często używane w zapytaniach; w przeciwnym razie zmarnujemy więcej czasu na tworzenie indeksów, niż zaoszczędzimy na ich posiadaniu. Moglibyśmy przyjąć ustaloną politykę, taką jak utrzymywanie indeksów tylko na kluczach składających się z predykatu i jednego argumentu. Albo moglibyśmy nauczyć się polityki adaptacyjnej, która tworzy indeksy, aby sprostać wymaganiom zadawanych zapytań. W przypadku komercyjnych baz danych, w których fakty liczą się w miliardach, problem był przedmiotem intensywnych badań, rozwoju technologii i ciągłej optymalizacji.

Reguły wnioskowania zniesionego wymagają znalezienia podstawień, które sprawiają, że różne wyrażenia logiczne wyglądają identycznie. Proces ten nazywa się unifikacją i jest kluczowym elementem wszystkich algorytmów wnioskowania pierwszego rzędu. Algorytm UNIFY pobiera dwa zdania i zwraca dla nich unifikator (podstawienie), jeśli taki istnieje:

Przyjrzyjmy się kilku przykładom zachowania UNIFY. Załóżmy, że mamy pytanie AskVar s(Knows(John,x)): kogo zna Jan? Odpowiedzi na to zapytanie można znaleźć, wyszukując wszystkie zdania w bazie wiedzy, które są ujednolicone z Knows(John,x) . Oto wyniki unifikacji z czterema różnymi zdaniami, które mogą znajdować się w bazie wiedzy:

Ostatnia unifikacja nie udaje się, ponieważ x nie może przyjąć wartości John i Elizabeth jednocześnie. A teraz pamiętaj, że Knows(x,Elizabeth) oznacza to „Wszyscy znają Elżbietę”, więc powinniśmy być w stanie wywnioskować, że John zna Elżbietę. Problem pojawia się tylko dlatego, że dwa zdania używają tej samej nazwy zmiennej, x . Problemu można uniknąć, standaryzując jedno z dwóch ujednoliconych zdań, co oznacza zmianę nazw jego zmiennych, aby uniknąć kolizji nazw. Na przykład możemy zmienić nazwę x w Knows(x,Elizabeth) (nowa nazwa zmiennej) bez zmiany jej znaczenia. Teraz zjednoczenie będzie działać:

Jest jeszcze jedna komplikacja: powiedzieliśmy, że UNIFY powinien zwrócić podstawienie, które sprawia, że oba argumenty wyglądają tak samo. Ale takich unifikatorów może być więcej niż jeden. Na przykład UNIFY(Knows(John, x), Knows(x,y)) może zwrócić {y/John,x/z} lub może zwrócić {y/John,x/John,z/John} . Pierwszy unifikator daje Knows(John,z) w wyniku unifikacji, podczas gdy drugi daje Knows(John,John) . Drugi wynik można było uzyskać z pierwszego przez dodatkowe podstawienie {z/John}; mówimy, że pierwszy unifikator jest bardziej ogólny niż drugi, ponieważ nakłada mniej ograniczeń na wartości zmiennych. Każda unifikowalna para wyrażeń ma jeden najbardziej ogólny unifikator (MGU), który jest unikalny aż do zmiany nazwy i podstawienia zmiennych. Na przykład {x/John} i {y/John} są uważane za równoważne, podobnie jak {x/John,y/John} i {x/John,y/z}.

Algorytm obliczania większości ogólnych unifikatorów pokazano poniżej. Proces jest prosty: rekursywnie eksploruj dwa wyrażenia jednocześnie „obok siebie”, budując po drodze unifikację, ale nie powiedzie się, jeśli dwa odpowiadające sobie punkty w strukturach nie pasują. Jest jeden kosztowny krok: dopasowując zmienną do złożonego terminu, należy sprawdzić, czy sama zmienna występuje wewnątrz terminu; jeśli tak, dopasowanie nie powiedzie się, ponieważ nie można skonstruować spójnego unifikatora. Na przykład S(x) nie można się zunifikować z S(S(x)) . To tak zwane sprawdzanie występowania powoduje, że złożoność całego algorytmu jest kwadratowa względem rozmiaru ujednoliconych wyrażeń. Niektóre systemy, w tym wiele systemów programowania logicznego, po prostu pomijają kontrolę wystąpienia i obciążają użytkownika, aby uniknąć w rezultacie nierozsądnych wniosków. Inne systemy wykorzystują bardziej złożone algorytmy unifikacji o złożoności czasu liniowego.

Bystrooki czytelnik zauważy, że podejście propozycjonalizacji generuje wiele niepotrzebnych egzemplarzy uniwersalnie kwantyfikowalnych zdań. Wolelibyśmy mieć podejście, które wykorzystuje tylko jedną zasadę, rozumowanie {x/John}, które rozwiązuje pytanie Evil(x) w następujący sposób: biorąc pod uwagę zasadę, że chciwi królowie są źli, znajdź x takich, x którzy są królami i x są chciwi, a następnie wywnioskuj, że x to jest złe. Mówiąc bardziej ogólnie, jeśli jest jakieś podstawienie θ, które sprawia, że każda z koniunkcji przesłanki implikacji jest identyczna ze zdaniami już w bazie wiedzy, to możemy stwierdzić wniosek implikacji po zastosowaniu θ . W tym przypadku podstawienie θ = {x/John} osiąga ten cel. Załóżmy teraz, że zamiast wiedzieć Greedy(John) , wiemy, że wszyscy są chciwi:

Wtedy chcielibyśmy jeszcze móc tak stwierdzić,Evil(John) bo wiemy, że Jan jest królem (dane), a Jan jest chciwy (bo wszyscy są chciwi). To, czego potrzebujemy, aby to zadziałało, to znalezienie podstawienia zarówno dla zmiennych w zdaniu implikacyjnym, jak i zmiennych w zdaniach znajdujących się w bazie wiedzy. W tym przypadku zastosowanie podstawienia {x/John, y/John} do przesłanek implikacyjnych King(x) i Greedy(x) i zdań bazy wiedzy King(John) i Greedy(y)  sprawi, że będą one identyczne. W ten sposób możemy wywnioskować konsekwencję implikacji. Ten proces wnioskowania można uchwycić jako pojedynczą regułę wnioskowania, którą nazywamy Generalized Modus Ponens: Dla zdań atomowych p_i, p_i’ , i  q , gdzie istnieje podstawienie θ takie, że , SUBST(θ,p_i’) = SUBST(θ,p_i) dla wszystkich  i

Zasada ta ma n+1 przesłanek: n zdań atomowych p_i‘ i jedna implikacja. Wniosek jest wynikiem zastosowania podstawienia θ do następnika q. Dla naszego przykładu:

Łatwo wykazać, że Generalized Modus Ponens jest zasadą zdrowego wnioskowania. Po pierwsze obserwujemy, że dla każdego zdania (którego zmienne są uważane za uniwersalnie kwantyfikowalne) i dla każdego podstawienia θ ,

jest prawdziwe przez Uniwersalną Instancję. Dotyczy to w szczególności a, które spełnia warunki zasady uogólnionego modus ponens. Tak więc z p₁’ … p_n’  możemy wywnioskować

a z implikacji p₁ Λ … p_n => q możemy wywnioskować

Teraz θ w Generalized Modus Ponens jest zdefiniowany tak, że   , dla wszystkich i ; dlatego pierwsze z tych dwóch zdań dokładnie odpowiada przesłance drugiego. Stąd SUBST(θ,q) następuje Modus Ponens.

Generalized Modus Ponens to podniesiona wersja Modus Ponens – przenosi Modus Ponens z podstawowej (bez zmiennych) logiki zdań na logikę pierwszego rzędu. W dalszej części tego rozdziału zobaczymy, że możemy opracować podniesione wersje algorytmów łączenia w przód, wstecz i rozwiązywania . Kluczową zaletą reguł wnioskowania zniesionego nad propozycjonalizacją jest to, że dokonują one tylko tych podstawień, które są wymagane, aby umożliwić kontynuację określonych wnioskowań.