För dem som inte känner till det ännu är Akinator ett datorspel och en mobilapp som skapats av ett franskt företag:
Akinators mål är att gissa en verklig eller fiktiv karaktär. För att gissa vilken karaktär spelaren tänker ställer Akinator en rad frågor och spelaren kan svara med ”Ja”, ”Vet inte”, ”Nej”, ”Förmodligen” och ”Förmodligen” inte , sedan bestämmer programmet den bästa frågan.
För varje svar beräknar Akinator den bästa frågan att ställa till spelaren och ger slutligen en gissning om vem denna spelare tänker på. Om den första gissningen inte är korrekt fortsätter Akinator att ställa frågor, och så vidare upp till tre gissningar; den första gissningen sker vanligtvis efter 15-20 frågor. Om den tredje gissningen fortfarande inte är korrekt ombeds spelaren att lägga till karaktären i en databas.
Algoritmen som används för att välja frågor har utvecklats helt och hållet av det franska företaget som nämns ovan, vilket har hållits hemligt. Det är dock relativt lätt att hitta artiklar som beskriver hur algoritmen byggdes upp och hur den används i Akinator. I den här artikeln kommer jag att visa dig ett enkelt och roligt sätt att förstå denna algoritm.
Akinator arbetar
En del artiklar förklarar att Akinator använder sig av beslutsträd, liksom sannolikhetsmetoder eller förstärkningsinlärning. Den här artikeln kommer att fokusera på två viktiga algoritmer för beslutsträd: Incremental Induction of Decision Trees 3 (ID3) och ID4.
För mer information om beslutsträd, se artikeln ”Tree Models Fundamental Concepts”
Incremental Induction of Decision Trees 3 (ID3)
Den grundläggande idén med ID3-algoritmen är att bygga upp ett beslutsträd med hjälp av en topp-och-dunkledning, girig sökning genom de givna uppsättningarna för att testa varje attribut på varje nod i trädet.
Om du vill förstå ID3 bättre kan du läsa artikeln: ”Exempel:
För att hitta ett optimalt sätt att klassificera en inlärningsuppsättning måste man minimera antalet frågor som ställs (dvs. minimera trädets djup). Därför behöver vi någon funktion som kan mäta vilka frågor som ger den mest balanserade uppdelningen. Informationsvinstmåttet är en sådan funktion, det vill säga informationsvinsten är skillnaden mellan orenhetsmåttet för den ursprungliga uppsättningen (dvs, när den ännu inte har delats upp) och det viktade genomsnittet av orosmåttet efter den delade uppsättningen (i den tidigare artikeln ”Tree Models Fundamental Concepts” har vi studerat att Gini och Entropy är mått på orenhet):
Varvid Entropy(S) är orenhetsvärdena före uppdelningen av data och Entropy(S,X) är orenheten efter uppdelningen.
I Information Gain finns det två huvudsakliga operationer under trädbyggandet:
- Utvärdering av uppdelningar för varje attribut och val av den bästa uppdelningen och,
- Skapande av partitioner med hjälp av den bästa uppdelningen.
En mycket viktig sak som du alltid bör förstå är att komplexiteten ligger i att bestämma den bästa uppdelningen för varje attribut och som sagt, baserat på entropi eller Gini, kan vi beräkna informationsvinsten.
Den algoritm som används i ID3-trädet är följande:
- Om alla instanser tillhör exakt en klass är beslutsträdet en svarsnod som innehåller det klassnamnet.
- I annat fall
(a) Definiera a(bäst) som ett attribut (eller funktion) med lägst Gain-score.
(b) För varje värde V(bäst,i) för a(bäst), odla en gren från a(bäst) till ett beslutsträd som konstrueras rekursivt från alla de instanser som har värdet V(bäst,i) för attributet a(bäst).
ID4
En annan viktig algoritm är ID4. De hävdar att denna algoritm accepterar en ny träningsinstans och uppdaterar sedan beslutsträdet, vilket gör att man undviker att bygga om beslutsträdet för att en global datastruktur har behållits i det ursprungliga trädet.
Den grundläggande proceduren för uppdatering av ID4-algoritmens träd anges nedan.
inmatningar: Ett beslutsträd, en instans
utmatning: Ett beslutsträd
- För varje möjligt testattribut i den aktuella noden uppdateras antalet positiva eller negativa instanser för värdet av det attributet i träningsinstansen.
- Om alla instanser som observeras vid den aktuella noden är positiva (negativa) är beslutsträdet vid den aktuella noden en svarsnod som innehåller ett ”+” (”-”) för att indikera en positiv (negativ) instans.
- I annat fall,
(a) Om den aktuella noden är en svarsnod ändras den till en beslutsnod som innehåller ett testattribut med det lägsta Gain-score.
(b) I annat fall, om den aktuella beslutsnoden innehåller ett attributtest som inte har det lägsta Gain-score, då
- Ändra attributtestet till ett med det lägsta Gain-score.
- Klipp bort alla existerande underträd under beslutsnoden.
Rekursivt uppdatera beslutsträdet under den aktuella beslutsnoden längs förgreningen av värdet på det aktuella testattributet som förekommer i exempelbeskrivningen. Växer grenen vid behov.
För mer information om beslutsträd se: ”Trädmodeller Grundläggande begrepp” och ”Exempel: