Dla tych, którzy jeszcze nie wiedzą, Akinator jest grą komputerową i aplikacją mobilną stworzoną przez francuską firmę: Elokence.

Celem Akinatora jest odgadnięcie prawdziwej lub fikcyjnej postaci. Aby odgadnąć postać, o której myśli gracz, Akinator zadaje serię pytań, na które gracz może odpowiedzieć „Tak”, „Nie wiem”, „Nie”, „Prawdopodobnie” i „Prawdopodobnie” nie, a następnie program określa najlepsze pytanie.

Dla każdej odpowiedzi Akinator oblicza najlepsze pytanie, jakie można zadać graczowi, a na koniec zgaduje, o kim ten gracz myśli. Jeśli pierwsza odpowiedź nie jest poprawna, Akinator kontynuuje zadawanie pytań, i tak dalej aż do trzech odpowiedzi; pierwsza z nich jest zazwyczaj po 15-20 pytaniach. Jeśli trzecie odgadnięcie nadal nie jest poprawne, gracz jest proszony o dodanie postaci do bazy danych.

Algorytm używany do wyboru pytań został całkowicie opracowany przez wspomnianą wyżej francuską firmę, co zostało utrzymane w tajemnicy. Jednak stosunkowo łatwo można znaleźć artykuły, które opisują jak ten algorytm został zbudowany i jak jest wykorzystywany w Akinatorze. W tym artykule, pokażę Ci prosty i przyjemny sposób na zrozumienie tego algorytmu.

Akinator działa

Niektóre artykuły deklarują, że Akinator używa Drzew Decyzyjnych, jak również Metod Probabilistycznych czy Reinforcement Learning. W tym artykule, skupimy się na dwóch ważnych algorytmach drzew decyzyjnych; Incremental Induction of Decision Trees 3 (ID3) oraz ID4.

Więcej informacji na temat drzew decyzyjnych można znaleźć w artykule „Modele drzew – podstawowe pojęcia”

Inkrementalna indukcja drzew decyzyjnych 3 (ID3)

Podstawową ideą algorytmu ID3 jest zbudowanie drzewa decyzyjnego za pomocą odgórnego, zachłannego przeszukiwania podanych zbiorów w celu przetestowania każdego atrybutu w każdym węźle drzewa.

Jeśli chcesz lepiej zrozumieć ID3, możesz zobaczyć artykuł: „Example: Compute the Impurity using Entropy and Gini Index.”

.

Aby znaleźć optymalny sposób klasyfikacji zbioru uczącego, konieczne jest zminimalizowanie zadawanych pytań (tj. zminimalizowanie głębokości drzewa). Potrzebujemy więc funkcji, która może zmierzyć, które pytania zapewniają najbardziej zrównoważony podział. Metryka Information Gain jest taką funkcją, to znaczy, Information Gain jest różnicą pomiędzy miarą nieczystości początkowego zbioru (tzn, gdy nie został on jeszcze podzielony) a średnią ważoną miarą nieczystości po podziale zbioru (w poprzednim artykule „Modele drzew podstawowe pojęcia” dowiedzieliśmy się, że Gini i Entropia są miarami nieczystości):

Gdzie Entropia(S) to wartości nieczystości przed podziałem danych, a Entropia(S,X) to nieczystość po podziale.

W Information Gain, istnieją dwie główne operacje podczas budowania drzewa:

• Ocena podziałów dla każdego atrybutu i wybór najlepszego podziału oraz,
• Tworzenie partycji przy użyciu najlepszego podziału.

Jedną bardzo ważną rzeczą, którą zawsze należy zrozumieć jest to, że złożoność polega na określeniu najlepszego podziału dla każdego atrybutu i jak powiedziano wcześniej, na podstawie Entropii lub Giniego, możemy obliczyć Zysk Informacyjny.

Stąd, używając Information Gain, algortihm używany w drzewie ID3 jest następujący:

1. Jeśli wszystkie instancje są z dokładnie jednej klasy, wtedy drzewo decyzyjne jest węzłem odpowiedzi zawierającym nazwę tej klasy.
2. W przeciwnym razie,

(a) Zdefiniuj a(best) jako atrybut (lub cechę) o najniższym Gain-score.

(b) Dla każdej wartości V(best,i) atrybutu a(best), rozwiń gałąź od a(best) do drzewa decyzyjnego skonstruowanego rekurencyjnie ze wszystkich instancji z wartością V(best,i) atrybutu a(best).

ID4

Innym ważnym algorytmem jest ID4. Twierdzą oni, że algorytm ten przyjmuje nową instancję szkoleniową, a następnie aktualizuje drzewo decyzyjne, co pozwala uniknąć przebudowy drzewa decyzyjnego dla tego, że globalna struktura danych została zachowana w oryginalnym drzewie.

Podstawowa procedura aktualizacji drzewa algorytmu ID4 jest podana poniżej.

wejścia: Drzewo decyzyjne, Jedna instancja

Wyjścia: A decision tree

1. Dla każdego możliwego atrybutu testowego w bieżącym węźle, zaktualizuj liczbę pozytywnych lub negatywnych instancji dla wartości tego atrybutu w instancji treningowej.
2. Jeśli wszystkie instancje obserwowane w bieżącym węźle są pozytywne (negatywne), to drzewo decyzyjne w bieżącym węźle jest węzłem odpowiedzi zawierającym znak „+” („-„) oznaczający pozytywną (negatywną) instancję.
3. W przeciwnym razie,

(a) Jeśli bieżący węzeł jest węzłem odpowiedzi, to zmień go na węzeł decyzyjny zawierający test atrybutu o najniższym Gain-score.

(b) W przeciwnym razie, jeśli bieżący węzeł decyzyjny zawiera test atrybutu, który nie ma najniższego Gain-score, to

• Zmień test atrybutu na taki, który ma najniższy Gain-score.
• Odrzuć wszystkie istniejące poddrzewa poniżej węzła decyzyjnego.

Recursywnie zaktualizuj drzewo decyzyjne poniżej bieżącego węzła decyzyjnego wzdłuż gałęzi wartości bieżącego atrybutu testu, który występuje w opisie instancji. Rozwijaj gałąź, jeśli to konieczne.

Więcej informacji o Drzewie decyzyjnym zobacz: „Modele drzew podstawowe pojęcia „oraz „Przykład: Compute the Impurity using Entropy and Gini Index.”