Az Akinator egy francia cég által készített számítógépes játék és mobil alkalmazás: Elokence.

Akinator célja egy valós vagy kitalált karakter kitalálása. Ahhoz, hogy kitalálja a játékos által gondolt karaktert, az Akinator egy sor kérdést tesz fel, és a játékos válaszolhat ‘Igen’, ‘Nem tudom’, ‘Nem’, ‘Valószínűleg’ és ‘Valószínűleg’ nem , majd a program meghatározza a legjobb kérdést.

Akinator minden válaszra kiszámítja a játékosnak feltett legjobb kérdést, és végül megtippeli, hogy az adott játékos kire gondol. Ha az első találgatás nem helyes, Akinator folytatja a kérdezést, és így tovább, egészen három találgatásig; az elsőt általában 15-20 kérdés után. Ha a harmadik találgatás sem helyes, a játékosnak fel kell vennie a karaktert egy adatbázisba.

A kérdések kiválasztásához használt algoritmust teljes egészében a fent említett francia cég fejlesztette ki, amelyet titokban tartanak. Viszonylag könnyen lehet azonban olyan cikkeket találni, amelyek leírják, hogyan épült fel az algoritmus, és hogyan használják az Akinatorban. Ebben a cikkben egy egyszerű és szórakoztató módon mutatom meg, hogyan lehet megérteni ezt az algoritmust.

Akinator működése

Egyes cikkek azt állítják, hogy az Akinator döntési fákat, valamint valószínűségi módszereket vagy megerősített tanulást használ. Ez a cikk, a döntési fák két fontos algoritmusára fog összpontosítani; Incremental Induction of Decision Trees 3 (ID3) és ID4.

A döntési fáról bővebb információt a “Fa modellek alapvető fogalmak”

Incremental Induction of Decision Trees 3 (ID3)

Az ID3 algoritmus alapgondolata, hogy egy döntési fát építünk fel egy felülről lefelé irányuló, mohó kereséssel a megadott halmazokon, hogy minden attribútumot teszteljünk a fa minden egyes csomópontján.

Ha jobban meg akarod érteni az ID3-at, lásd a cikket: “Példa: A tisztátalanság kiszámítása az entrópia és a Gini-index segítségével.”

A tanulóhalmaz osztályozásának optimális módjának megtalálásához minimalizálni kell a feltett kérdéseket(azaz minimalizálni a fa mélységét). Ezért szükségünk van valamilyen függvényre, amely mérni tudja, hogy mely kérdések biztosítják a legkiegyensúlyozottabb felosztást. Az információnyereség metrika egy ilyen függvény, vagyis az információnyereség a kezdeti halmaz tisztátalansági mértéke közötti különbség (azaz, amikor még nem volt felosztva) és a felosztott halmaz utáni Impurity Measure súlyozott átlaga között (A “Famodellek alapfogalmai” című korábbi cikkben tanulmányoztuk, hogy a Gini és az entrópia a tisztázatlanság mérőszámai):

Ahol az Entropy(S) az adatok felosztása előtti Impurity értékek, az Entropy(S,X) pedig a felosztás utáni impurity.

Az információnyereségben a faépítés során két fő művelet van:

• A felosztások értékelése minden egyes attribútumra és a legjobb felosztás kiválasztása és,
• A partíciók létrehozása a legjobb felosztás felhasználásával.

Egy nagyon fontos dolog, amit mindig meg kell értenünk, hogy a bonyolultság az egyes attribútumok legjobb felosztásának meghatározásában rejlik, és mint mondjuk korábban, az entrópia vagy a Gini alapján kiszámíthatjuk az információnyereséget.

Az információnyereséget használva tehát az ID3 fában használt algoritmus a következő:

1. Ha minden példány pontosan egy osztályból való, akkor a döntési fa egy válaszcsomópont, amely tartalmazza az osztály nevét.
2. Máskülönben,

(a) Definiáljuk a(legjobb) attribútumot (vagy jellemzőt) a legalacsonyabb Gain-pontszámmal rendelkező attribútumnak (vagy jellemzőnek).

(b) Az a(legjobb) minden egyes V(legjobb,i) értékére növesszünk egy ágat az a(legjobb)-ból az a(legjobb) attribútum V(legjobb,i) értékével rendelkező összes példányból rekurzívan felépített döntési fába.

ID4

Egy másik fontos algoritmus az ID4. Azt állítják, hogy ez az algoritmus elfogad egy új gyakorló példányt, majd frissíti a döntési fát, ami elkerüli a döntési fa újbóli felépítését, amiért egy globális adatstruktúra maradt az eredeti fában.

Az ID4 algoritmus alapvető fa-frissítési eljárását az alábbiakban adjuk meg.

Bemenetek:

kimenet: Egy döntési fa, Egy példány

: A döntési fa

1. Az aktuális csomópontban lévő minden lehetséges tesztattribútumhoz frissítsük a pozitív vagy negatív példányok számát az adott attribútum értékére vonatkozóan a képzési példányban.
2. Ha az aktuális csomópontnál megfigyelt összes példány pozitív (negatív), akkor a döntési fa az aktuális csomópontnál egy válaszcsomópont, amely egy “+” (“-“) jelzést tartalmaz a pozitív (negatív) példány jelzésére.
3. Máskülönben,

(a) Ha az aktuális csomópont egy válaszcsomópont, akkor változtassuk meg egy olyan döntési csomóponttá, amely a legalacsonyabb Gain-pontszámú attribútumtesztet tartalmazza.

(b) Ellenkező esetben, ha az aktuális döntési csomópont olyan attribútumtesztet tartalmaz, amely nem rendelkezik a legalacsonyabb Gain-pontszámmal, akkor

• Változtassuk meg az attribútumtesztet olyanra, amely a legalacsonyabb Gain-pontszámmal rendelkezik.
• Vessük el az összes meglévő alfát a döntési csomópont alatt.

Rekurzívan frissítsük az aktuális döntési csomópont alatti döntési fát az aktuális teszt attribútum értékének a példányleírásban előforduló ága mentén. Növelje az ágat, ha szükséges.

A döntési fáról további információkat ld: “A famodellek alapvető fogalmai “és “Példa: Compute the Impurity using Entropy and Gini Index.”