Pro ty, kteří ho ještě neznají, je Akinator počítačová hra a mobilní aplikace vytvořená francouzskou společností:
Cílem hry Akinator je uhodnout skutečné nebo fiktivní postavy. Pro uhodnutí postavy, kterou hráč myslí, pokládá Akinator řadu otázek a hráč může odpovídat odpověďmi „Ano“, „Nevím“, „Ne“, „Pravděpodobně“ a „Pravděpodobně“ ne , poté program určí nejlepší otázku.
Pro každou odpověď Akinator vypočítá nejlepší otázku, kterou má hráč položit, a nakonec uvede odhad, na koho tento hráč myslí. Pokud první odhad není správný, Akinátor pokračuje v pokládání otázek a tak dále až do tří odhadů; první je zpravidla po 15-20 otázkách. Pokud ani třetí hádání není správné, je hráč vyzván k doplnění postavy do databáze.
Algoritmus používaný pro výběr otázek byl zcela vyvinut výše zmíněnou francouzskou společností, což bylo utajeno. Je však poměrně snadné najít články, které popisují, jak byl algoritmus sestaven a jak je v Akinatoru použit. V tomto článku vám ukážu jednoduchý a zábavný způsob, jak tento algoritmus pochopit.
Fungování Akinatoru
Některé články deklarují, že Akinator používá rozhodovací stromy, stejně jako pravděpodobnostní metody nebo Reinforcement Learning. Tento článek, se zaměří na dva důležité algoritmy rozhodovacích stromů: Inkrementální indukce rozhodovacích stromů 3 (ID3) a ID4.
Další informace o rozhodovacím stromu naleznete v článku „Základní pojmy stromových modelů“
Inkrementální indukce rozhodovacích stromů 3 (ID3)
Základní myšlenkou algoritmu ID3 je sestavení rozhodovacího stromu pomocí prohledávání shora dolů (greedy search) přes zadané množiny za účelem testování každého atributu v každém uzlu stromu.
Pokud chcete ID3 lépe porozumět, můžete si prohlédnout článek: „Příklad:
Pro nalezení optimálního způsobu klasifikace učící se množiny je třeba minimalizovat počet položených otázek(tj. minimalizovat hloubku stromu). Potřebujeme tedy nějakou funkci, která dokáže změřit, které otázky poskytují nejvyváženější rozdělení. Takovou funkcí je metrika informačního zisku, tj. informační zisk je rozdíl mezi mírou nečistoty výchozí množiny (tj, kdy ještě nebyla rozdělena) a váženým průměrem míry nečistoty po rozdělení množiny (v předchozím článku „Základní pojmy stromových modelů“ jsme studovali, že Gini a Entropie jsou mírami nečistoty):
Kde Entropie(S) jsou hodnoty nečistoty před rozdělením dat a Entropie(S,X) je nečistota po rozdělení.
V informačním zisku jsou při sestavování stromu dvě hlavní operace:
- Vyhodnocení rozdělení pro každý atribut a výběr nejlepšího rozdělení a,
- Vytvoření rozdělení pomocí nejlepšího rozdělení.
Jednou z velmi důležitých věcí, kterou byste měli vždy pochopit, je, že složitost spočívá v určení nejlepšího rozdělení pro každý atribut a jak již bylo řečeno, na základě Entropie nebo Giniho můžeme vypočítat Informační zisk.
Tedy pomocí Informačního zisku je algortihm použitý ve stromu ID3 následující:
- Pokud jsou všechny instance přesně z jedné třídy, pak je rozhodovací strom uzlem odpovědi obsahujícím název této třídy.
- V opačném případě,
(a) Definujte a(best) jako atribut (nebo vlastnost) s nejnižším Gain-score.
(b) Pro každou hodnotu V(best,i) atributu a(best) vyrůstá větev z a(best) do rozhodovacího stromu konstruovaného rekurzivně ze všech těch případů s hodnotou V(best,i) atributu a(best).
ID4
Dalším důležitým algoritmem je ID4. Tvrdí, že tento algoritmus přijímá novou trénovací instanci a poté aktualizuje rozhodovací strom, čímž se vyhne opětovnému sestavování rozhodovacího stromu pro to, že v původním stromu byla zachována globální datová struktura.
Základní postup aktualizace stromu algoritmu ID4 je uveden níže.
vstupy: Rozhodovací strom, Jedna instance
výstup: Rozhodovací strom
- Pro každý možný testovací atribut v aktuálním uzlu aktualizujte počet pozitivních nebo negativních instancí pro hodnotu tohoto atributu v trénovací instanci.
- Jsou-li všechny instance pozorované v aktuálním uzlu kladné (záporné), pak je rozhodovací strom v aktuálním uzlu odpovědním uzlem obsahujícím „+“ („-„) pro označení kladné (záporné) instance.
- V opačném případě,
(a) Je-li aktuální uzel odpovědním uzlem, pak jej změňte na rozhodovací uzel obsahující test atributu s nejnižším Gain-score.
(b) V opačném případě, pokud aktuální rozhodovací uzel obsahuje test atributu, který nemá nejnižší Gain-score, pak
- Změňte test atributu na test s nejnižším Gain-score.
- Zrušte všechny existující podstromy pod rozhodovacím uzlem.
Rekurzivně aktualizujte rozhodovací strom pod aktuálním rozhodovacím uzlem podél větve hodnoty aktuálního testu atributu, která se vyskytuje v popisu instance. V případě potřeby větev zvětšete.
Další informace o rozhodovacím stromu viz: „Základní pojmy modelů stromů“ a „Příklad:
„Výpočet nečistoty pomocí entropie a Giniho indexu“.