Induktiivinen logiikkaohjelmointi

Induktiivinen logiikkaohjelmointi (ILP)  on koneoppimisen haara, joka käyttää logiikkaohjelmointia esimerkkien, taustatiedon ja hypoteesien esittämiseen. Saatuaan kuvaukset jo tunnetusta taustatiedosta ja joukon esimerkkejä, jotka on esitetty loogisena faktapohjana, ILP-järjestelmä pystyy generoimaan hypoteesien muodossa loogisen ohjelman, joka selittää kaikki positiiviset esimerkit, mutta ei yhtään negatiivista.

Kaava: positiiviset esimerkit + negatiiviset esimerkit + taustatiedot => hypoteesit

Termiä induktiivinen logiikkaohjelmointi käytettiin ensimmäisen kerran Stephen Muggletonin artikkelissa vuonna 1991. Termiä "induktiivinen" käytetään tässä filosofisessa (teorian ehdotus havaittujen tosiasioiden selittämiseksi), eikä matemaattisessa (joukon jäsenten ominaisuuden osoittamisessa) merkityksessä.

ILP-ongelma

Tehtävänä on löytää taustatiedon kannalta täydellinen ja johdonmukainen määritelmä kohdepredikaatille.

"Hypoteesi selittää esimerkkejä" tarkoittaa:

Prologin säännöt

Tyypillisesti ILP-toteutukset tehdään Prologissa . Lisäesimerkin ymmärtämiseksi muistakaamme, kuinka säännöt on järjestetty tällä ohjelmointikielellä.

Siinä sääntö on implikaatio, esimerkiksi: has_son(X):-parent(X,Y), !woman(Y). (X:llä on poika, jos X on Y:n vanhempi ja Y ei ole nainen) Säännön pää on implikaation johtopäätös. Säännön runko on implikaatioiden lähettäminen ("," literaalien konjunktio). Literaali on Prologin atomikaava tai sen negaatio. Jos on useita sääntöjä samalla päällä, ne voidaan yhdistää yhdeksi yhdistämällä niiden vartalot disjunktioon ";"

Hypoteesien tarkentaminen

Hypoteesin tarkentaminen on iteratiivinen prosessi: Otetaan yleisempi hypoteesi H1, joka selittää kaikki "+"-esimerkit ja jotkut "-"-esimerkit. Se on tarkennettu selittämään vähemmän "-"-esimerkkejä. Tulos: Hypoteesi H2, joka selittää vain osan H1:llä selitetyistä esimerkeistä

Tapoja tarkentaa hypoteeseja:

Muuttujien tunnistaminen

Se oli:

has_tytär ( X ) :- vanhempi ( Y , Z ).

Se tuli:

has_tytär ( X ) : - vanhempi ( X , Z )

Taustapredikaatin lisääminen runkoon

Se oli:

has_tytär ( X ) :-.

Se tuli:

has_tytär ( X ) :- vanhempi ( Y , Z ).

Esimerkki

Oletetaan, että meillä on perhettä koskevia tosiasioita:

mies ( John ). mies ( bill ). mies ( paul ). vanhempi ( John , Kate ). vanhempi ( mary , kate ). vanhempi ( bill , paul ). vanhempi ( kate , paul ). nainen ( mary ). nainen ( kate ).

Tämän tehtävän taustatiedot ovat predikaatit "vanhempi", "mies" ja "nainen":

vanhempi ( X , Y ) mies ( X ) nainen ( X )

Haluamme opettaa ILP-järjestelmälle predikaatin "on tytär". Määritellään se kohdepredikaatiksi:

has_tytär ( X )

Tälle predikaatille positiivisia esimerkkejä olisivat:

on_tytär ( mary ) on_tytär ( john )

Negatiivisia esimerkkejä:

has_tytär ( bill ) has_tytär ( kate ) has_tytär ( paul )

Harjoittelun ensimmäisessä vaiheessa meillä on vain yksi mahdollisimman yleinen hypoteesi:

has_tytär ( X ).

Se on triviaalisti järjestetty - se kattaa kaikki esimerkit (toimii mille tahansa X:lle). Mutta on selvää, että joissakin esimerkeissä se antaa väärän tuloksen - esimerkiksi tietokannassa on niitä, joilla ei ole tytärtä (nämä ovat Bill, Kate ja Paul). Siten hypoteesi on täydellinen (kattaa kaikki "+"-esimerkit), mutta epäjohdonmukainen (kattaa joitain "-"-esimerkkejä).

Aloitetaan hypoteesin tarkentaminen. Koska emme voi tunnistaa muuttujia - niitä on vain yksi - käytämme toista menetelmää - taustapredikaatin lisäämistä runkoon. Saamme 3 hypoteesia:

has_tytär ( X ):- mies ( Y ). has_tytär ( X ):- nainen ( Y ). has_tytär ( X ):- vanhempi ( Y , Z ).

Nyt voit käyttää yhtä tapaa tarkentaa hypoteeseja ja tunnistaa muuttujat (eli korvata Y X:llä). Saamme:

has_tytär ( X ):- mies ( X ). has_tytär ( X ):- nainen ( X ). has_tytär ( X ):- vanhempi ( X , Z ).

Ensimmäinen tuloksena olevista hypoteeseista on: "X:llä on tytär, jos X on mies." Hänellä on vastaesimerkki Mariasta, jolla on tytär, mutta hän ei ole mies. Joten tässä puun oksa on katkaistu: hypoteesi on jo epätäydellinen (ei kata Mariaa, jolla on tytär) ja epäjohdonmukainen (kattaa esimerkit "Bill" ja "Paul", joilla ei ole tyttäriä). Samoin se on hypoteesin "X:llä on tytär, jos X on nainen" tapauksessa.

Ainoa haara, joka johtaa oikeaan hypoteesiin, on oikealla puolella oleva tarkennusketju, mukaan lukien emopredikaatti. Tuloksena saamme hypoteesin:

has_tytär ( X ):- vanhempi ( X , Z ), nainen ( Z ).

Hän on täydellinen ja yhteinen.


Ominaisuudet

  • Opetetaan rekursiivisia käsitteitä, kuten "jälkeläinen".
  • Monipredikaattioppiminen (usean predikaatin samanaikainen oppiminen, jossa yksi predikaatti määritellään toisella)

Haitat

  • Sinun on määritettävä manuaalisesti muuttujien lukumäärä ja tyyppi kohdepredikaatissa
  • Korkea laskennallinen monimutkaisuus ( NP-täydellinen ongelma ). Literaalien lisääminen lisää muuttujien määrää predikaatissa. Mikä tahansa muuttujien osajoukko voidaan tunnistaa keskenään, mikä lisää välittömästi eksponentiaalista monimutkaisuutta.

Heuristiikka

Mahdolliset rajoitukset aikakulujen vähentämiseksi:

  • Suurimman hakusyvyyden rajoitus
  • Predikaattirungon literaalien enimmäismäärän rajoitus
  • "Hypoteesikustannus"-parametrin käyttöönotto: Kustannus(H) = muuttujien_määrä(H) + 10*kirjaimien_määrä(H) + 10*NegCover(H)

ILP:n soveltamisala

Kirjallisuus

  • Ivan Bratko. Tekoälyalgoritmit kielellä PROLOG = Prolog Programming For Artificial Intelligence. - M . : "Williams" , 2004. - S. 640. - ISBN 0-201-40375-7 .