Akinator.com i klasyfikator Naive Bayes

Kontekst: Jestem programistą z pewnym (na wpół zapomnianym) doświadczeniem w statystyce z kursów uni. Niedawno natknąłem się na http://akinator.com i spędziłem trochę czasu próbując sprawić, by zawiodła. A kto nie był? :)

Postanowiłem dowiedzieć się, jak to może działać. Po przejrzeniu Google'a i przeczytaniu pokrewnych postów na blogu i dodaniu części mojej (ograniczonej) wiedzy do powstałej mieszanki, wpadłem na następujący model (jestem pewien, że użyję niewłaściwej notacji, proszę nie zabijaj mnie za to):

Istnieją tematy (S) i pytania (Q). Celem predyktora jest wybór podmiotu S, który ma największe prawdopodobieństwo bycia podmiotem, o którym myśli użytkownik, biorąc pod uwagę zebrane do tej pory pytania i odpowiedzi.

Niech gra G będzie zestawem zadanych pytań i udzielonych odpowiedzi: .$\{q_1, a_1\}, \{q_2, a_2\} ... \{q_n, a_n\}$

Następnie predyktor szuka .$P(S|G) = \frac{P(G|S) * P(S)}{P(G)}$

Wcześniej dla przedmiotów ( ) może być tylko liczba odgadnięć podmiotu podzielona przez całkowitą liczbę gier.$P(S)$

Zakładając, że wszystkie odpowiedzi są niezależne, możemy obliczyć prawdopodobieństwo podmiotu S, biorąc pod uwagę grę G:

$P(G|S) = \prod_{i=1..n} P(\{q_i, a_i\} | S)$

Możemy obliczyć jeśli będziemy śledzić, które pytania i odpowiedzi zostały udzielone, gdy użyte zostały chociaż w danym temacie:$P(\{q_i, a_i\} | S)$

$P({q, a} | S) = \frac{answer\ a\ was\ given\ to\ question\ q\ in\ the\ game\ when\ S\ was\ the\ subject}{number\ of\ times\ q\ was\ asked\ in\ the\ games\ involving\ S}$

Teraz definiuje rozkład prawdopodobieństwa między podmiotami i kiedy musimy wybrać następne pytanie, musimy wybrać to, dla którego oczekiwana zmiana w entropii tego rozkładu jest maksymalna:$P(S|G)$

$argmax_j (H[P(S|G)] - \sum_{a=yes,no,maybe...} H[P(S|G \vee \{q_j, a\})]$

Próbowałem to zaimplementować i działa. Ale, oczywiście, wraz ze wzrostem liczby pacjentów, wydajność spada ze względu na konieczność ponownego obliczenia po każdym ruchu i obliczenia zaktualizowanego rozkładu dla wybór pytania.$P(S|G)$$P(S|G \vee \{q_j, a\})$

Podejrzewam, że po prostu wybrałem niewłaściwy model, będąc ograniczonym ograniczeniami mojej wiedzy. A może w matematyce jest błąd. Proszę, oświeć mnie: z czym powinienem się zapoznać lub jak zmienić predyktor, aby mógł poradzić sobie z milionami tematów i tysiącami pytań?

Ta gra wygląda podobnie do 20 pytań pod adresem http://20q.net , które według twórcy są oparte na sieci neuronowej. Oto jeden ze sposobów ustrukturyzowania takiej sieci, podobny do sieci neuronowej opisanej w wektorach opisu koncepcji i grze 20 pytań .

Miałbyś

1. Stała liczba pytań, niektóre z nich oznaczone jako „ostateczne”.
2. Jedna jednostka wejściowa na pytanie, gdzie 0/1reprezentuje no/yesodpowiedź. Początkowo ustawiony na0.5
3. Jedna jednostka wyjściowa na pytanie, sigmoid spłaszczony do zakresu 0..1
4. Ukryta warstwa łącząca wszystkie jednostki wejściowe ze wszystkimi jednostkami wyjściowymi.

Jednostki wejściowe dla pytań, na które udzielono odpowiedzi, są ustawione na 0 lub 1, a założeniem jest, że sieć neuronowa została przeszkolona, ​​aby wartości wyjściowe jednostek wyjściowych były bliskie 1 dla pytań, na które odpowiedź „Tak”, biorąc pod uwagę zestaw istniejących odpowiedzi.

Na każdym etapie należy wybrać pytanie, które NNjest najmniej pewne, tzn . Że odpowiednia jednostka wyjściowa jest blisko 0.5, zadać pytanie i ustawić odpowiednią jednostkę wejściową na odpowiedź. Na ostatnim etapie wybierasz jednostkę wyjściową z listy „ostatnich pytań” o wartości najbliższej 1.

Każda gra składająca się z 20 pytań daje 20 punktów danych, których możesz użyć do aktualizacji NNwag z propagacją wsteczną , tj. Aktualizujesz wagi tak, aby wyjścia bieżącej sieci neuronowej były zgodne z prawdziwą odpowiedzią na wszystkie poprzednie pytania.

Nie sądzę, że to naprawdę problem z klasyfikacją. 20 pytań jest często określanych jako problem kompresji . To faktycznie lepiej pasuje do ostatniej części pytania, w której mówisz o entropii.

Zobacz rozdział 5.7 ( Książki Google ) z

Cover, TM and Joy, AT (2006) Elementy teorii informacji

a także kodowanie Huffmana . Artykuł, który znalazłem na arXiv, może być również interesujący.

Gill, JT i Wu, W. (2010) „Dwadzieścia pytań Gry zawsze kończą się na Tak” http://arxiv.org/abs/1002.4907

Dla uproszczenia załóżmy pytania tak / nie (podczas gdy akinator.com pozwala, może nie wiem). Załóżmy, że każdy możliwy podmiot (co wie akinator.com) można jednoznacznie zidentyfikować za pomocą sekwencji pytań i odpowiedzi typu tak / nie - zasadniczo wektora binarnego.

Pytania (i odpowiedzi na nie) definiują rekurencyjny podział przestrzeni podmiotów. Podział ten odpowiada również strukturze drzewa. Wewnętrzne wierzchołki drzewa odpowiadają pytaniom, a liście odpowiadają podmiotom. Głębokość liści jest dokładnie liczbą pytań wymaganych do jednoznacznej identyfikacji przedmiotu. Możesz (trywialnie) zidentyfikować każdy znany temat, zadając każde możliwe pytanie. To nie jest interesujące, ponieważ potencjalnie są setki pytań.

Połączenie z kodowaniem Huffmana polega na tym, że daje on optymalny sposób (w ramach określonego modelu probabilistycznego) do budowy drzewa, tak aby średnia głębokość była (prawie) minimalna. Innymi słowy, mówi ci, jak ułożyć sekwencję pytań (zbudować drzewo), aby liczba pytań, które musisz zadać, jest średnio niewielka. Używa chciwego podejścia.

Oczywiście na stronie akinator.com jest coś więcej, ale podstawową ideą jest to, że możesz myśleć o problemie w kategoriach drzewa i próbować zminimalizować średnią głębokość jego liści.