Uczeń indukcyjny pierwszego rzędu

W uczeniu maszynowym indukcyjny uczeń pierwszego rzędu ( FOIL ) to algorytm uczenia się oparty na regułach.

Tło

Opracowany w 1990 roku przez Rossa Quinlana , FOIL uczy się bezfunkcyjnych klauzul Horna , podzbioru rachunku predykatów pierwszego rzędu . Biorąc pod uwagę pozytywne i negatywne przykłady niektórych koncepcji i zestaw predykatów wiedzy podstawowej , FOIL indukcyjnie generuje definicję logicznego pojęcia lub regułę dla tego pojęcia. Reguła indukowana nie może zawierać żadnych stałych ( color(X,red) staje się color(X,Y), red(Y) ) ani symboli funkcji, ale może dopuszczać zanegowane predykaty; pojęć rekurencyjnych można się również nauczyć.

Podobnie jak algorytm ID3 , FOIL wspina się po wzgórzach, używając metryki opartej na teorii informacji , aby skonstruować regułę obejmującą dane. Jednak w przeciwieństwie do ID3, FOIL wykorzystuje metodę „oddziel i zwyciężaj” zamiast „ dziel i zwyciężaj” , skupiając się na tworzeniu jednej reguły na raz i zbieraniu odkrytych przykładów do następnej iteracji algorytmu. ^{[ potrzebne źródło ]}

Algorytm

Algorytm FOIL wygląda następująco:

Wejście Lista przykładów

Wyjście Reguła w logice predykatów pierwszego rzędu

FOIL(Przykłady)

Niech Pos będzie pozytywnymi przykładami

Niech Pred będzie predykatem do nauczenia

Dopóki Pos będzie puste zrób:

Niech Neg będzie negatywnymi przykładami

Ustaw Body na puste

Call LearnClauseBody

Dodaj Pred ← Treść do reguły

Usuń z Pos wszystkie przykłady, które spełniają Body

Procedura LearnClauseBody

Dopóki Neg nie będzie puste wykonaj:

Wybierz literał L

Połącz L z Body

Usuń z Neg przykłady, które nie spełniają L

Przykład

Załóżmy, że zadaniem FOIL jest nauczenie się pojęcia dziadek(X,Y) na podstawie relacji ojciec(X,Y) i rodzic(X,Y) . Ponadto załóżmy, że nasze obecne Ciało składa się z dziadka(X,Y) ← rodzic(X,Z) . Można to rozszerzyć, łącząc Body z dowolnym literałem Father(X,X) , Father(Y,Z) , parent(U,Y) lub wieloma innymi — aby utworzyć ten literał, algorytm musi wybrać zarówno nazwę predykatu oraz zestaw zmiennych dla predykatu (z których przynajmniej jedna musi być już obecna w niezanegowanym literale klauzuli). Jeśli FOIL rozszerza klauzulę dziadek(X,Y) ← prawda przez połączenie dosłownego rodzica(X,Z) , wprowadza nową zmienną Z . Pozytywne przykłady składają się teraz z tych wartości < X,Y,Z > takich, że dziadek(X,Y) jest prawdziwy, a rodzic(X,Z) jest prawdziwy; negatywne przykłady to te, w których dziadek (X, Y) jest prawdziwy, ale rodzic (X, Z) jest fałszywy.

W następnej iteracji FOIL po dodaniu elementu parent(X,Z) , algorytm rozważy wszystkie kombinacje nazw predykatów i zmiennych, tak aby przynajmniej jedna zmienna w nowym literale była obecna w istniejącej klauzuli. Powoduje to bardzo dużą przestrzeń wyszukiwania. Kilka rozszerzeń teorii FOIL wykazało, że dodatki do podstawowego algorytmu mogą zmniejszyć tę przestrzeń wyszukiwania, czasem drastycznie. ^{[ potrzebne źródło ]}

Rozszerzenia

Algorytm FOCL ( First Order Combined Learner ) rozszerza FOIL na różne sposoby, które wpływają na sposób, w jaki FOCL wybiera literały do testowania podczas rozszerzania klauzuli w trakcie budowy. Dozwolone są ograniczenia przestrzeni poszukiwań, podobnie jak predykaty zdefiniowane na podstawie reguły, a nie zestawu przykładów (nazywane intensjonalnymi ); co najważniejsze, dopuszcza się potencjalnie błędną hipotezę jako wstępne przybliżenie predykatu, którego należy się nauczyć. Głównym celem FOCL jest włączenie metod uczenia się opartego na wyjaśnieniach (EBL) do empirycznych metod FOIL.

Jednak nawet wtedy, gdy FOCL nie dostarcza żadnej dodatkowej wiedzy przez FOIL, wykorzystuje iteracyjną strategię wyszukiwania poszerzającego, podobną do przeszukiwania w głąb : najpierw FOCL próbuje nauczyć się klauzuli, nie wprowadzając żadnych wolnych zmiennych. Jeśli to się nie powiedzie (brak dodatniego wzmocnienia), dozwolona jest jedna dodatkowa wolna zmienna na niepowodzenie, dopóki liczba wolnych zmiennych nie przekroczy maksimum użytego dla dowolnego predykatu.

Ograniczenia

W przeciwieństwie do FOIL, który nie nakłada ograniczeń na pisanie na swoje zmienne, FOCL używa pisania jako niedrogiego sposobu na włączenie prostej formy podstawowej wiedzy. Na przykład predykat liveAt(X,Y) może mieć typy lifeAt(person, location) . Może być jednak konieczne wprowadzenie dodatkowych predykatów — bez typów nextDoor(X,Y) może określać, czy osoba X i osoba Y mieszkają obok siebie, czy też dwie lokalizacje są obok siebie. W przypadku typów, aby ta funkcjonalność została zachowana, musiałyby istnieć dwa różne predykaty nextDoor(person, person) i nextDoor(location, location) . Jednak ten mechanizm wpisywania eliminuje potrzebę stosowania predykatów, takich jak isPerson(X) lub isLocation(Y) , i nie musi brać pod uwagę lifeAt(A,B) , gdy A i B są zdefiniowane jako zmienne osoby, zmniejszając przestrzeń wyszukiwania. Ponadto wpisywanie może poprawić dokładność wynikowej reguły poprzez wyeliminowanie z rozważań niemożliwych literałów, takich jak lifeAt(A,B) , które mimo wszystko mogą wydawać się mieć wysoki przyrost informacji .

Zamiast implementować trywialne predykaty, takie jak equals(X,X) lub between(X,X,Y) , FOCL wprowadza ukryte ograniczenia dla zmiennych, dodatkowo zmniejszając przestrzeń wyszukiwania. Niektóre predykaty muszą mieć unikalne wszystkie zmienne, inne muszą mieć przemienność ( sąsiednie(X,Y) jest równoważne z „sąsiednimi(Y,X) ”), jeszcze inne mogą wymagać obecności określonej zmiennej w bieżącej klauzuli i wielu innych potencjalnych ograniczeń .

Zasady operacyjne

Reguły operacyjne to te reguły, które są zdefiniowane ekstensywnie lub jako lista krotek, dla których predykat jest prawdziwy. FOIL dopuszcza tylko zasady operacyjne; FOCL rozszerza swoją bazę wiedzy, aby umożliwić kombinacje reguł zwanych regułami nieoperacyjnymi, a także częściowo zdefiniowane lub nieprawidłowe reguły dotyczące odporności. Zezwolenie na częściowe definicje zmniejsza ilość potrzebnej pracy, ponieważ algorytm nie musi generować tych częściowych definicji dla siebie, a nieprawidłowe reguły nie zwiększają znacząco potrzebnej pracy, ponieważ są odrzucane, jeśli nie zostaną ocenione, że zapewniają pozytywny zysk w postaci informacji. Zasady nieoperacyjne są korzystne, ponieważ poszczególne reguły, które łączą, mogą same w sobie nie zapewniać pozyskiwania informacji, ale są przydatne w połączeniu. Jeśli literał, który uzyskał najwięcej informacji w iteracji FOCL, nie działa, jest operacjonalizowany, a jego definicja jest dodawana do klauzuli w trakcie konstruowania.

Wejścia Literał do operacjonalizacji Lista pozytywnych przykładów Lista negatywnych przykładów

Wyjście Literał w postaci operacyjnej

Operacjonalizuj(Literal, Pozytywne przykłady, Negatywne przykłady)

Jeśli Literał jest operacyjny

Zwróć Literał

Inicjalizuj OperacyjneLiterały do pustego zbioru

Dla każdej klauzuli w definicji Literału

Oblicz przyrost informacji klauzuli na przykładach pozytywnych i negatywnych

Dla klauzuli z maksymalnym wzmocnieniem

Dla każdego literału L w klauzuli

Dodaj Operationalize( L , pozytywne przykłady, negatywne przykłady) do OperationalLiterals

Regułą operacyjną może być literał lessThan(X,Y) ; nieoperacyjna reguła może być pomiędzy (X,Y,Z) ← lessThan(X,Y), lessThan(Y,Z) .

Początkowe zasady

Dodanie reguł nieoperacyjnych do bazy wiedzy zwiększa rozmiar przestrzeni, którą musi przeszukiwać FOCL. Zamiast po prostu dostarczać algorytmowi koncepcję docelową (np. dziadek(X,Y) ), algorytm przyjmuje jako dane wejściowe zestaw niedziałających reguł, które sprawdza pod kątem poprawności i operacjonalizuje dla wyuczonej koncepcji. Prawidłowa koncepcja celu wyraźnie poprawi czas i dokładność obliczeń, ale nawet nieprawidłowa koncepcja da algorytmowi podstawę do pracy i poprawy dokładności i czasu.

http://www.csc.liv.ac.uk/~frans/KDD/Software/FOIL_PRM_CPAR/foil.html

Bibliografia _ Uczenie się logicznych definicji z relacji. Uczenie maszynowe, tom 5, numer 3, 1990. [1]
^ Niech Var będzie największą liczbą odrębnych zmiennych dla dowolnej klauzuli w regule R , wyłączając ostatnią koniunkcję. Niech MaxP będzie liczbą predykatów o największej argumentacji MaxA . Wtedy przybliżona liczba węzłów wygenerowanych do nauki R to: NodesSearched ≤ 2 * MaxP * (Var + MaxA – 1) ^MaxA , jak pokazano w Pazzani i Kibler (1992).
^ ^a ^b Michael Pazzani i Dennis Kibler. Użyteczność wiedzy w uczeniu się indukcyjnym. Uczenie maszynowe, tom 9, numer 1, 1992. [2]

[Quinlan1990-1] Bibliografia _ Uczenie się logicznych definicji z relacji. Uczenie maszynowe, tom 5, numer 3, 1990. [1]

[2] Niech Var będzie największą liczbą odrębnych zmiennych dla dowolnej klauzuli w regule R , wyłączając ostatnią koniunkcję. Niech MaxP będzie liczbą predykatów o największej argumentacji MaxA . Wtedy przybliżona liczba węzłów wygenerowanych do nauki R to: NodesSearched ≤ 2 * MaxP * (Var + MaxA – 1) ^MaxA , jak pokazano w Pazzani i Kibler (1992).

[Pazzani-3] Michael Pazzani i Dennis Kibler. Użyteczność wiedzy w uczeniu się indukcyjnym. Uczenie maszynowe, tom 9, numer 1, 1992. [2]