Pentru cei care nu-l cunosc încă, Akinator este un joc pe calculator și o aplicație mobilă creată de o companie franceză: Elokence.

Obiectivul lui Akinator este de a ghici un personaj real sau fictiv. Pentru a ghici personajul la care se gândește jucătorul, Akinator pune o serie de întrebări, iar jucătorul poate răspunde cu „Da”, „Nu știu”, „Nu”, „Probabil” și „Probabil” nu , apoi programul determină cea mai bună întrebare.

Pentru fiecare răspuns, Akinator calculează cea mai bună întrebare pe care să o adreseze jucătorului și, în final, oferă o presupunere cu privire la cine se gândește acest jucător. Dacă prima presupunere nu este corectă, Akinator continuă să pună întrebări, și așa mai departe până la trei presupuneri; prima fiind, în general, după 15-20 de întrebări. Dacă nici la a treia ghicire nu este corectă, jucătorului i se cere să adauge personajul într-o bază de date.

Algoritmul folosit pentru selectarea întrebărilor a fost dezvoltat în totalitate de compania franceză menționată mai sus, care a fost ținut secret. Cu toate acestea, este relativ ușor de găsit articole care descriu cum a fost construit algoritmul și cum este folosit în Akinator. În acest articol, vă voi arăta un mod simplu și distractiv de a înțelege acest algoritm.

Akinator Working

Câteva articole declară că Akinator folosește Decision Trees, precum și metode probabilistice sau Reinforcement Learning. Acest articol, se va concentra pe doi algoritmi importanți ai arborelui de decizie; Incremental Induction of Decision Trees 3 (ID3) și ID4.

Pentru mai multe informații despre arborele de decizie, consultați articolul „Tree Models Fundamental Concepts”

Incremental Induction of Decision Trees 3 (ID3)

Ideea de bază a algoritmului ID3 este de a construi un arbore de decizie folosind o căutare de sus în jos, lacomă, prin seturile date pentru a testa fiecare atribut pe fiecare nod al arborelui.

Dacă doriți să înțelegeți mai bine ID3, puteți vedea articolul: „Example: Calcularea impurității utilizând Entropia și indicele Gini.”

.

Pentru a găsi o modalitate optimă de clasificare a unui set de învățare, este necesar să se minimizeze întrebările puse(adică să se minimizeze adâncimea arborelui). Astfel, avem nevoie de o funcție care să măsoare care întrebări oferă cea mai echilibrată divizare. Metrica câștigului de informație este o astfel de funcție, adică câștigul de informație este diferența dintre măsura de impuritate a setului inițial (de ex, atunci când acesta nu a fost încă divizat) și media ponderată a măsurii de impuritate după divizarea setului (în articolul anterior „Tree Models Fundamental Concepts” am studiat că Gini și Entropia sunt măsuri ale impurității):

Unde Entropie(S) reprezintă valorile Impurității înainte de divizarea datelor și Entropie(S,X) reprezintă Impuritatea după divizare.

În Information Gain, există două operațiuni principale în timpul construirii arborelui:

• Evaluarea diviziunilor pentru fiecare atribut și selectarea celei mai bune diviziuni și,
• Crearea partițiilor folosind cea mai bună diviziune.

Un lucru foarte important pe care trebuie să-l înțelegeți întotdeauna este că complexitatea constă în determinarea celei mai bune diviziuni pentru fiecare atribut și, așa cum am mai spus, pe baza Entropiei sau a lui Gini, putem calcula câștigul de informație.

În consecință, folosind câștigul de informație, algoritmul utilizat în arborele ID3 este următorul:

1. Dacă toate instanțele aparțin exact unei clase, atunci arborele de decizie este un nod de răspuns care conține numele acelei clase.
2. În caz contrar,

(a) Se definește a(best) ca fiind atributul (sau caracteristica) cu cel mai mic scor Gain-score.

(b) Pentru fiecare valoare V(best,i) a lui a(best), creșteți o ramură de la a(best) la un arbore de decizie construit recursiv din toate instanțele cu valoarea V(best,i) a atributului a(best).

ID4

Un alt algoritm important este ID4. Ei susțin că acest algoritm acceptă o nouă instanță de instruire și apoi actualizează arborele de decizie, ceea ce evită reconstruirea arborelui de decizie pentru că în arborele original a fost păstrată o structură globală de date.

Procedura de bază a algoritmului ID4 de actualizare a arborelui este prezentată mai jos.

Intrări: Un arbore de decizie, o instanță

sursă: Un arbore de decizie

1. Pentru fiecare atribut de testare posibil la nodul curent, se actualizează numărul de instanțe pozitive sau negative pentru valoarea acelui atribut în instanța de instruire.
2. Dacă toate instanțele observate la nodul curent sunt pozitive (negative), atunci arborele de decizie la nodul curent este un nod de răspuns care conține un „+” („-„) pentru a indica o instanță pozitivă (negativă).
3. În caz contrar,

(a) Dacă nodul curent este un nod de răspuns, atunci schimbați-l într-un nod de decizie care conține un test de atribut cu cel mai mic scor Gain-score.

(b) În caz contrar, dacă nodul de decizie curent conține un test de atribut care nu are cel mai mic scor Gain-score, atunci

• Schimbă testul de atribut cu unul care are cel mai mic scor Gain-score.
• Anulează toate subarborele existente sub nodul de decizie.

Actualizează recursiv arborele de decizie sub nodul de decizie curent de-a lungul ramurii valorii atributului test curent care apare în descrierea instanței. Creșteți ramura, dacă este necesar.

Pentru mai multe informații despre arborele de decizie, consultați: „Tree Models Fundamental Concepts „și „Example: Compute the Impurity using Entropy and Gini Index.”