Sille, jotka eivät vielä tiedä sitä, Akinator on ranskalaisen yrityksen luoma tietokonepeli ja mobiilisovellus: Elokence.
Akinatorin tavoitteena on arvata todellinen tai kuvitteellinen hahmo. Arvatakseen pelaajan ajatteleman hahmon Akinator kysyy sarjan kysymyksiä ja pelaaja voi vastata ’Kyllä’, ’En tiedä’, ’Ei’, ’Todennäköisesti’ ja ’Todennäköisesti’ ei , sitten ohjelma määrittää parhaan kysymyksen.
Kullekin vastaukselle Akinator laskee parhaan kysymyksen, jonka voi kysyä pelaajalta, ja lopuksi antaa arvauksen siitä, ketä tämä pelaaja ajattelee. Jos ensimmäinen arvaus ei ole oikea, Akinator jatkaa kysymysten esittämistä, ja niin edelleen aina kolmeen arvaukseen asti; ensimmäinen arvaus on yleensä 15-20 kysymyksen jälkeen. Jos kolmas arvaus ei vieläkään pidä paikkaansa, pelaajaa pyydetään lisäämään hahmo tietokantaan.
Kysymysten valinnassa käytetty algoritmi on täysin edellä mainitun ranskalaisen yhtiön kehittämä, ja se on pidetty salassa. On kuitenkin suhteellisen helppo löytää artikkeleita, joissa kuvataan, miten algoritmi on rakennettu ja miten sitä käytetään Akinatorissa. Tässä artikkelissa näytän yksinkertaisen ja hauskan tavan ymmärtää tätä algoritmia.
Akinatorin toiminta
Joissain artikkeleissa ilmoitetaan, että Akinator käyttää päätöspuita sekä probabilistisia menetelmiä tai vahvistusoppimista. Tässä artikkelissa keskitytään kahteen tärkeään päätöspuualgoritmiin; Incremental Induction of Decision Trees 3 (ID3) ja ID4.
Lisätietoa päätöksentekopuusta löytyy artikkelista ”Puumallien peruskäsitteet”
Inkremental Induction of Decision Trees 3 (ID3)
ID3-algoritmin perusidea on rakentaa päätöksentekopuu käyttämällä ylhäältä alaspäin suuntautuvaa ahnetta hakua annettujen joukkojen läpi kunkin attribuutin testaamiseksi puun jokaisessa solmussa.
Jos haluat ymmärtää paremmin ID3:a, voit tutustua artikkeliin: ”Esimerkki: Impurityn laskeminen entropian ja Gini-indeksin avulla.”
Jotta voidaan löytää optimaalinen tapa luokitella oppimisjoukko, on minimoitava esitetyt kysymykset(eli minimoitava puun syvyys). Tarvitaan siis jokin funktio, jolla voidaan mitata, mitkä kysymykset tuottavat tasapainoisimman jaon. Informaatiovoiton metriikka on tällainen funktio, eli informaatiovoitto on alkuperäisen joukon epäpuhtausmitan erotus (ts, kun sitä ei ole vielä jaettu) ja epäpuhtausmitan painotetun keskiarvon välillä sen jälkeen, kun joukko on jaettu (edellisessä artikkelissa ”Puumallien peruskäsitteet” olemme tutkineet, että Gini ja entropia ovat epäpuhtauden mittareita):
Jossa Entropy(S) on epäpuhtausarvot ennen datan jakamista ja Entropy(S,X) on epäpuhtausarvot jakamisen jälkeen.
Information Gain -menetelmässä puun muodostamisen aikana on kaksi pääoperaatiota:
- Hajautusten arviointi kullekin attribuutille ja parhaan hajautuksen valinta ja,
- Osioiden luominen käyttäen parasta hajautusta.
Yksi erittäin tärkeä asia, joka on aina ymmärrettävä, on se, että monimutkaisuus piilee parhaan jaon määrittämisessä kullekin attribuutille, ja kuten sanottu, entropian tai Ginin perusteella voidaan laskea informaatiovoitto.
Siten Information Gainin avulla ID3-puussa käytetty algortihm on seuraava:
- Jos kaikki instanssit ovat täsmälleen yhdestä luokasta, niin päätöspuussa on vastaussolmu, joka sisältää kyseisen luokan nimen.
- Muussa tapauksessa,
(a) Määritellään a(paras) attribuutiksi (tai ominaisuudeksi), jolla on pienin Gain-score.
(b) Kasvatetaan jokaiselle a(paras):n arvolle V(paras,i) haara a(paras):sta päätöspuuhun, joka rakennetaan rekursiivisesti kaikista niistä tapauksista, joissa attribuutin a(paras) arvo V(paras,i) on.
ID4
Toinen tärkeä algoritmi on ID4. He väittävät, että tämä algoritmi hyväksyy uuden harjoitusinstanssin ja päivittää sen jälkeen päätöspuun, jolloin vältetään päätöspuun uudelleenrakentaminen, sillä globaali tietorakenne on säilytetty alkuperäisessä puussa.
PERUS ID4-algoritmin puun päivitysproseduuri on esitetty alla.
syötteet: Päätöksentekopuu, Yksi instanssi
tulos:
- Päivitetään kunkin nykyisen solmun mahdollisen testiattribuutin osalta positiivisten tai negatiivisten instanssien lukumäärä kyseisen attribuutin arvolle harjoitusinstanssissa.
- Jos kaikki nykyisessä solmussa havaitut instanssit ovat positiivisia (negatiivisia), niin päätöspuu nykyisessä solmussa on vastaussolmu, joka sisältää ”+” (”-”) merkitsemään positiivista (negatiivista) instanssia.
- Muussa tapauksessa,
(a) Jos nykyinen solmu on vastaussolmu, niin vaihda se päätöksentekosolmuksi, joka sisältää pienimmän vahvistusarvopistemäärän (Gain-pistemäärän) omaavan attribuutin.
(b) Muussa tapauksessa, jos nykyinen päätöksentekosolmu sisältää attribuuttitestin, jolla ei ole pienintä Gain-pistemäärää, niin
- Vaihda attribuuttitesti attribuuttitestiksi, jolla on pienin Gain-pistemäärä.
- Hävitä kaikki olemassa olevat alipuut päätöksentekosolmun alapuolella.
Päivitä nykyisen päätöksentekosolmun alapuolella oleva päätöspuu rekursiivisesti nykyisen testin ominaisuustestin arvoa vastaavaa haaraa pitkin, joka esiintyy esiintymiskuvauksessa. Kasvata haaraa tarvittaessa.
Lisätietoja päätöspuusta ks: ”Puumallien peruskäsitteet ”ja ”Esimerkki: Compute the Impurity using Entropy and Gini Index.”