For dem, der ikke kender det endnu, er Akinator et computerspil og en mobilapp, der er skabt af et fransk firma:
Akinators mål er at gætte en virkelig eller fiktiv figur. For at gætte den karakter, som spilleren tænker, stiller Akinator en række spørgsmål, og spilleren kan svare med ‘Ja’, ‘Ved ikke’, ‘Nej’, ‘Sandsynligvis’ og ‘Sandsynligvis’ ikke , hvorefter programmet bestemmer det bedste spørgsmål.
For hvert svar beregner Akinator det bedste spørgsmål at stille spilleren og giver til sidst et gæt på, hvem denne spiller tænker på. Hvis det første gæt ikke er korrekt, fortsætter Akinator med at stille spørgsmål, og så videre op til tre gæt; det første gæt kommer som regel efter 15-20 spørgsmål. Hvis det tredje gæt stadig ikke er korrekt, bliver spilleren bedt om at tilføje karakteren i en database.
Algoritmen, der anvendes til udvælgelse af spørgsmål, er helt udviklet af det ovennævnte franske selskab, som er blevet holdt hemmeligt. Det er dog relativt let at finde artikler, der beskriver, hvordan algoritmen blev bygget op, og hvordan den bruges i Akinator. I denne artikel vil jeg vise dig en enkel og sjov måde at forstå denne algoritme på.
Akinator arbejder
Nogle artikler erklærer, at Akinator bruger beslutningstræer, samt probabilistiske metoder eller forstærkningslæring. Denne artikel vil fokusere på to vigtige algoritmer for beslutningstræer; Incremental Induction of Decision Trees 3 (ID3) og ID4.
For mere information om beslutningstræet, se artiklen “Tree Models Fundamental Concepts”
Incremental Induction of Decision Trees 3 (ID3)
Den grundlæggende idé med ID3-algoritmen er at opbygge et beslutningstræ ved hjælp af en top-down, greedy søgning gennem de givne sæt for at teste hver attribut på hver enkelt knude i træet.
Hvis du ønsker at forstå ID3 bedre, kan du se artiklen: “Eksempel: For at finde en optimal måde at klassificere et læringssæt på, er det nødvendigt at minimere de stillede spørgsmål(dvs. minimere træets dybde). Vi har således brug for en funktion, der kan måle, hvilke spørgsmål der giver den mest afbalancerede opdeling. Informationsgevinst-metrikken er en sådan funktion, dvs. informationsgevinst er forskellen mellem det oprindelige datasætets urenhedsmåling (dvs, når den endnu ikke er blevet opdelt) og det vægtede gennemsnit af urenhedsmålingerne efter opdelingen (i den tidligere artikel “Tree Models Fundamental Concepts” har vi undersøgt, at Gini og Entropy er mål for urenhed):
Hvor Entropi(S) er urenhedsværdierne før opsplitning af dataene og Entropi(S,X) er urenheden efter opsplitningen.
I Information Gain er der to hovedoperationer under træopbygningen:
Evaluering af opdelinger for hver attribut og udvælgelse af den bedste opdeling og,
Oprettelse af partitioner ved hjælp af den bedste opdeling.
En meget vigtig ting, som man altid bør forstå, er, at kompleksiteten ligger i at bestemme den bedste opdeling for hver attribut, og som sagt kan vi på grundlag af Entropi eller Gini beregne informationsgevinsten.
Herfor er den algortihm, der anvendes i ID3-træet ved hjælp af Informationsgevinst, følgende:
Hvis alle forekomsterne er fra præcis én klasse, så er beslutningstræet en svarknude, der indeholder dette klassens navn.
I modsat fald,
(a) Definer a(bedst) som en attribut (eller egenskab) med den laveste Gain-score.
(b) For hver værdi V(bedst,i) af a(bedst) dyrkes en gren fra a(bedst) til et beslutningstræ, der er konstrueret rekursivt ud fra alle de tilfælde med værdien V(bedst,i) af attributten a(bedst).
ID4
En anden vigtig algoritme er ID4. De hævder, at denne algoritme accepterer en ny træningsinstans og derefter opdaterer beslutningstræet, hvilket undgår at genopbygge beslutningstræet for at en global datastruktur er blevet bevaret i det oprindelige træ.
Den grundlæggende ID4-algoritme tree-update procedure er givet nedenfor.
inputs: Et beslutningstræ, en instans
output: Et beslutningstræ
For hver mulig testattribut ved det aktuelle knudepunkt opdateres antallet af positive eller negative tilfælde for værdien af den pågældende attribut i træningsinstansen.
Hvis alle de observerede forekomster ved den aktuelle knude er positive (negative), er beslutningstræet ved den aktuelle knude en svarknude, der indeholder et “+” (“-“) for at angive en positiv (negativ) forekomst.
I modsat fald,
(a) Hvis den aktuelle knude er en svarknude, ændres den til en beslutningsknude, der indeholder en attributprøve med den laveste Gain-score.
(b) Hvis den aktuelle beslutningsknude ellers indeholder en attributprøve, der ikke har den laveste Gain-score, så
ændrer du attributprøven til en attributprøve med den laveste Gain-score.
Kasserer alle eksisterende undertræer under beslutningsknuden.
Rekursivt opdaterer du beslutningstræet under den aktuelle beslutningsknude langs den gren af værdien af den aktuelle testattribut, der forekommer i instansbeskrivelsen. Vækst af grenen, hvis det er nødvendigt.
For flere oplysninger om beslutningstræ se: “Træmodeller Grundlæggende begreber “og “Eksempel:
: “Eksempel: Beregn urenheden ved hjælp af entropi og Gini-indeks”
