Voor degenen die het nog niet kennen, Akinator is een computerspel en mobiele app gemaakt door het Franse bedrijf: Elokence.

Het doel van Akinator is om een echt of een fictief personage te raden. Om het personage te raden dat de speler in gedachten heeft, stelt Akinator een reeks vragen en de speler kan antwoorden met ‘Ja’, ‘Weet niet’, ‘Nee’, ‘Waarschijnlijk’ en ‘Waarschijnlijk’ niet , waarna het programma bepaalt wat de beste vraag is.

Voor elk antwoord berekent Akinator de beste vraag om aan de speler te stellen en geeft hij ten slotte een gokje naar wie deze speler aan het denken is. Als de eerste gok niet juist is, gaat Akinator door met vragen stellen, en zo verder tot drie keer raden; de eerste gok wordt meestal na 15-20 vragen gedaan. Is de derde gok nog steeds niet juist, dan wordt de speler gevraagd het personage in een database op te nemen.

Het algoritme dat voor de selectie van de vragen wordt gebruikt, is geheel ontwikkeld door het hierboven genoemde Franse bedrijf, dat geheim is gehouden. Het is echter relatief eenvoudig om artikelen te vinden die beschrijven hoe het algoritme tot stand is gekomen en hoe het in Akinator wordt gebruikt. In dit artikel, zal ik u een eenvoudige en leuke manier om dit algoritme te begrijpen.

Akinator Werken

Sommige artikelen verklaren dat Akinator Decision Trees gebruiken, evenals Probabilistische Methoden of Reinforcement Learning. Dit artikel, zal zich richten op twee belangrijke algoritme van Decision Tree; Incremental Induction of Decision Trees 3 (ID3) en ID4.

Voor meer informatie over de Beslisboom, zie het artikel “Tree Models Fundamental Concepts”

Incremental Induction of Decision Trees 3 (ID3)

Het basisidee van het ID3-algoritme is om een Beslisboom te bouwen met behulp van een top-down, greedy-zoekopdracht door de gegeven sets om elk attribuut op elk knooppunt van de boom te testen.

Als u ID3 beter wilt begrijpen, kunt u het artikel lezen: “Voorbeeld: Bereken de onzuiverheid met Entropie en Gini-index.”

Om een optimale manier te vinden om een leerset te classificeren, is het noodzakelijk om de gestelde vragen te minimaliseren (d.w.z. de diepte van de boom te minimaliseren). We hebben dus een functie nodig die kan meten welke vragen de meest evenwichtige splitsing opleveren. De Information Gain metriek is zo’n functie, dat wil zeggen, Information Gain is het verschil tussen de Onzuiverheidsmaat van de initiële verzameling (d.w.z, wanneer die nog niet gesplitst is) en het gewogen gemiddelde van de onzuiverheidsmaat na de gesplitste verzameling (In het vorige artikel “Tree Models Fundamental Concepts” hebben wij bestudeerd dat Gini en Entropy maatstaven van onzuiverheid zijn):

Waarbij Entropy(S) de onzuiverheidswaarden is vóór het splitsen van de gegevens en Entropy(S,X) de onzuiverheid na de splitsing.

In Information Gain zijn er twee belangrijke bewerkingen tijdens het maken van de boom:

• Evaluatie van de splitsingen voor elk attribuut en selectie van de beste splitsing en,
• Schepping van partities met behulp van de beste splitsing.

Een zeer belangrijk ding dat u altijd moet begrijpen is dat de complexiteit ligt in het bepalen van de beste splitsing voor elk attribuut en zoals gezegd kunnen we op basis van Entropie of Gini de informatiewinst berekenen.

Het algoritme dat in de ID3-boom wordt gebruikt, is als volgt:

1. Als alle gevallen tot precies één klasse behoren, is de beslissingsboom een antwoordknooppunt dat de naam van die klasse bevat.
2. anders,

(a) Definieer a(best) als een attribuut (of kenmerk) met de laagste Gain-score.

(b) Laat voor elke waarde V(best,i) van a(best) een tak groeien van a(best) naar een beslissingsboom die recursief is geconstrueerd uit alle gevallen met waarde V(best,i) van kenmerk a(best).

ID4

Een ander belangrijk algoritme is ID4. Zij stellen dat dit algoritme een nieuwe trainingsinstantie accepteert en vervolgens de beslissingsboom bijwerkt, waardoor wordt vermeden dat de beslissingsboom opnieuw moet worden opgebouwd, omdat in de oorspronkelijke boom een globale gegevensstructuur is bewaard.

De basisprocedure voor het bijwerken van de boom door het ID4-algoritme wordt hieronder gegeven.

inputs: Een beslissingsboom, Een instantie

output: Een beslissingsboom

1. Voor elk mogelijk testattribuut op het huidige knooppunt, werkt u het aantal positieve of negatieve gevallen bij voor de waarde van dat attribuut in de opleidingsinstantie.
2. Als alle gevallen die bij het huidige knooppunt zijn waargenomen, positief (negatief) zijn, dan is de beslisboom bij het huidige knooppunt een antwoordknooppunt met een “+” (“-“) om een positieve (negatieve) instantie aan te geven.
3. anders,

(a) Als het huidige knooppunt een antwoordknooppunt is, verander het dan in een beslissingsknooppunt met een attribuuttest met de laagste Gain-score.

(b) Anders, als het huidige beslissingsknooppunt een attribuuttest bevat die niet de laagste Gain-score heeft, dan

• Verander de attribuuttest in een met de laagste Gain-score.
• Gooi alle bestaande sub-bomen onder het beslissingsknooppunt weg.

Bewerk de beslisboom onder het huidige beslissingsknooppunt opnieuw langs de tak van de waarde van het huidige testattribuut die in de beschrijving van de instantie voorkomt. Laat de tak indien nodig groeien.

Voor meer informatie over Beslisboom zie: “Tree Models Fundamental Concepts “en “Example: Bereken de Onzuiverheid met Entropie en Gini Index.”