Första ordningens induktiv inlärare

Inom maskininlärning är första ordningens induktiva inlärare ( FOIL ) en regelbaserad inlärningsalgoritm .

Bakgrund

, som utvecklades 1990 av Ross Quinlan , lär sig funktionsfria Horn-satser , en delmängd av första ordningens predikatkalkyl . Givet positiva och negativa exempel på något begrepp och en uppsättning bakgrundskunskapspredikat genererar FOIL induktivt en logisk begreppsdefinition eller regel för begreppet. Den inducerade regeln får inte involvera några konstanter ( färg(X,röd) blir färg(X,Y), röd(Y) ) eller funktionssymboler, men kan tillåta negerade predikat; rekursiva begrepp är också inlärbara.

Liksom ID3-algoritmen klättrar FOIL-backen med hjälp av ett mått baserat på informationsteori för att konstruera en regel som täcker data. Till skillnad från ID3 använder FOIL dock en separat-och-erövra-metod snarare än divide-and-conquer , med fokus på att skapa en regel i taget och samla in oupptäckta exempel för nästa iteration av algoritmen.

Algoritm

FOIL-algoritmen är som följer:

Indata Lista med exempel

Utdataregel i första ordningens predikatlogik

FOIL(Exempel)

Låt Pos vara de positiva exemplen

Låt Pred vara predikatet som ska läras

Tills Pos är tomt gör:

Låt Neg vara de negativa exemplen

Sätt Kropp till tom

Ring LearnClauseBody

Lägg till Pred ← Brödtext till regeln

Ta bort från Pos alla exempel som uppfyller Body

Procedur LearnClauseBody

Tills Neg är tom gör:

Välj en bokstavlig L

Sammanfoga L till Body

Ta bort från Neg exempel som inte uppfyller L

Exempel

Antag att FOILs uppgift är att lära sig begreppet farfar(X,Y) givet relationerna far(X,Y) och förälder(X,Y) . Anta dessutom att vår nuvarande kropp består av farfar(X,Y) ← förälder(X,Z) . Detta kan utökas genom att sammanfoga Kropp med någon av bokstavstexterna fader(X,X) , far(Y,Z) , förälder(U,Y) eller många andra – för att skapa denna bokstav måste algoritmen välja både ett predikatnamn och en uppsättning variabler för predikatet (av vilka åtminstone en måste vara närvarande redan i en ogegerad bokstav i satsen). Om FOIL utökar en sats grandfather(X,Y) ← true genom att sammanfoga den bokstavliga föräldern(X,Z) , introducerar den den nya variabeln Z . Positiva exempel består nu av dessa värden < X,Y,Z > så att farfar(X,Y) är sant och förälder(X,Z) är sant; negativa exempel är de där farfar(X,Y) är sant men förälder(X,Z) är falskt.

Vid nästa iteration av FOIL efter att parent(X,Z) har lagts till, kommer algoritmen att överväga alla kombinationer av predikatnamn och variabler så att minst en variabel i den nya literalen finns i den befintliga satsen. Detta resulterar i ett mycket stort sökutrymme. Flera förlängningar av FOIL-teorin har visat att tillägg till den grundläggande algoritmen kan minska detta sökutrymme, ibland drastiskt.

Tillägg

FOCL - algoritmen ( First Order Combined Learner ) utökar FOIL på en mängd olika sätt, vilket påverkar hur FOCL väljer bokstaver att testa samtidigt som en klausul under konstruktion utökas. Restriktioner på sökutrymmet är tillåtna, liksom predikat som är definierade på en regel snarare än på en uppsättning exempel (kallade intensionalpredikat ); viktigast av allt är en potentiellt felaktig hypotes tillåten som en initial approximation till det predikat som ska läras in. Huvudmålet med FOCL är att införliva metoderna för förklaringsbaserat lärande (EBL) i de empiriska metoderna för FOIL.

Även när ingen ytterligare kunskap tillhandahålls till FOCL över FOIL, använder den dock en iterativ breddad sökstrategi som liknar djup-först-sökning : först försöker FOCL lära sig en klausul genom att inte introducera några fria variabler. Om detta misslyckas (ingen positiv förstärkning) tillåts ytterligare en fri variabel per misslyckande tills antalet fria variabler överskrider det maximala som används för ett predikat.

Begränsningar

Till skillnad från FOIL, som inte sätter skrivbegränsningar på sina variabler, använder FOCL skrivning som ett billigt sätt att införliva en enkel form av bakgrundskunskap. Till exempel kan ett predikat livesAt(X,Y) ha typer livesAt(person, location) . Ytterligare predikat kan dock behöva införas – utan typer nextDoor(X,Y) avgöra om person X och person Y bor granne med varandra, eller om två platser är grannar med varandra. Med typer skulle två olika predikat nextDoor(person, person) och nextDoor(plats, plats) behöva existera för att denna funktionalitet ska bibehållas. Den här skrivmekanismen eliminerar dock behovet av predikat som isPerson(X) eller isLocation(Y) och behöver inte beakta livesAt(A,B) när A och B definieras som personvariabler, vilket minskar sökutrymmet. Dessutom kan skrivning förbättra noggrannheten hos den resulterande regeln genom att ta bort omöjliga bokstaver som livesAt(A,B) som ändå kan tyckas ha en hög informationsvinst .

Istället för att implementera triviala predikat som lika(X,X) eller between(X,X,Y) introducerar FOCL implicita begränsningar för variabler, vilket ytterligare minskar sökutrymmet. Vissa predikat måste ha alla variabler unika, andra måste ha kommutativitet ( intilliggande(X,Y) är ekvivalent med intilliggande(Y,X) ), ytterligare andra kan kräva att en viss variabel finns i den aktuella satsen och många andra potentiella begränsningar .

Driftsregler

Operativa regler är de regler som definieras extensionellt eller som en lista över tupler för vilka ett predikat är sant. FOIL tillåter endast operativa regler; FOCL utökar sin kunskapsbas för att tillåta kombinationer av regler som kallas icke-operativa regler såväl som delvis definierade eller felaktiga regler för robusthet. Att tillåta partiella definitioner minskar mängden arbete som behövs eftersom algoritmen inte behöver generera dessa deldefinitioner för sig själv, och de felaktiga reglerna ökar inte nämnvärt det arbete som behövs eftersom de kasseras om de inte bedöms ge positiv informationsvinst. Icke-operativa regler är fördelaktiga eftersom de individuella reglerna som de kombinerar kanske inte ger informationsvinst på egen hand, men är användbara när de tas i kombination. Om en bokstavlig med mest informationsvinst i en iteration av FOCL är icke-operativ, operationaliseras den och dess definition läggs till i satsen under konstruktion.

Inmatningar Literal som ska operationaliseras, Lista över positiva exempel, Lista över negativa exempel

Output Literal i operationell form

Operationalize(Literal, Positiva exempel, Negativa exempel)

Om Literal är operationell

Returnera Literal

Initiera OperationalLiterals till den tomma uppsättningen

För varje sats i definitionen av Literal

Beräkna informationsvinst för satsen över Positiva exempel och Negativa exempel

För satsen med maximal förstärkning

För varje bokstavlig L i satsen

Lägg till Operationalize( L , Positiva exempel, Negativa exempel) till OperationalLiterals

En operativ regel kan vara den bokstavliga lessThan(X,Y) ; en icke-operativ regel kan vara mellan(X,Y,Z) ← lessThan(X,Y), lessThan(Y,Z) .

Inledande regler

Tillägget av icke-operativa regler till kunskapsbasen ökar storleken på det utrymme som FOCL måste söka. Istället för att bara förse algoritmen med ett målkoncept (t.ex. farfar(X,Y) ), tar algoritmen som indata en uppsättning icke-operativa regler som den testar för korrekthet och operationaliserar för sitt inlärda koncept. Ett korrekt målkoncept kommer klart att förbättra beräkningstid och noggrannhet, men även ett felaktigt koncept kommer att ge algoritmen en grund att arbeta utifrån och förbättra noggrannheten och tiden.

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