Akinator.com i klasyfikator Naive Bayes

12

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: .{q1,a1},{q2,a2}...{qn,an}

Następnie predyktor szuka .P(S|G)=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)=i=1..nP({qi,ai}|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({qi,ai}|S)

P(q,a|S)=answer a was given to question q in the game when S was the subjectnumber 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)

argmaxj(H[P(S|G)]a=yes,no,maybe...H[P(S|G{qj,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{qj,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ń?

Adept
źródło
4
Wątpię, czy jest to Naiwny Bayes, a raczej drzewo decyzyjne przedłużane za każdym razem, gdy kogoś nie rozpozna.
1
Czy takie drzewo decyzyjne nie byłoby zbyt nieporęczne do aktualizacji? Poza tym nie widzę łatwego sposobu na wyjaśnienie przypadkowo błędnych / uczciwych pomyłek, a mimo to nadal mam rację dzięki drzewu decyzyjnemu
ADEP
5
Wygląda jak reinkarnacja dwudziestoletniego zgadywacza z 20 pytaniami, teraz na 20q.net . Oto popularne wyjaśnienie, jak to działa mentalfloss.com/blogs/archives/13725
Jarosław
5
Przepraszam, ale myślę, że użycie „sztucznej inteligencji” i „sieci neuronowych” bez żadnego kontekstu trudno jest wyjaśnić. I nie widzę, jak można użyć sieci neuronowej do tego rodzaju rzeczy - na przykład, jaka byłaby funkcja wyjściowa?
ADEP
Cześć @ ADEpt, minęło już trochę czasu od pytania, ale czy możesz udostępnić kod źródłowy dla implementacji, którą tam miałeś?
prikha

Odpowiedzi:

10

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.

Jarosław Bułatow
źródło
7

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.

vqv
źródło
To dobry początek, ale myślę, że w tym problemie jest coś więcej. Na przykład: w jaki sposób uzyskują odpowiedzi na pytania? Przypuszczalnie wykorzystują odpowiedzi udzielone przez poprzednich graczy (problem uczenia się przez wzmocnienie), w którym to przypadku mamy do czynienia z wyborem pytania, które (a) rozwiązuje problem dla obecnego gracza i (b) zapewnia informacje dla przyszłych graczy.
Simon Byrne,
Na pierwszy rzut oka możliwość narysowania analogii między 20 pytaniami a kodowaniem Huffmana zależy od umiejętności zadawania „pytań o zakres”. Oznacza to, że zamiast „Czy byłeś kiedyś w kosmosie?” zadajemy pytania „ogólne”, takie jak: „Czy kiedykolwiek był w kosmosie, czy jest mężczyzną, czy jest łysy, czy był w filmie, albo ... (100500 innych opcji)?” Czy mam rację? Jeśli tak, to prawdopodobnie powinienem edytować moje pytanie, aby wyjaśnić, że interesuje mnie odmiana „pytaj jeden po drugim”
ADEP
Ponadto większość artykułów, które używają kodów Huffmana jako modelu dla 20 pytań, sugeruje, że pytający może tworzyć własne pytania, które w istocie sprowadzają się do „Czy bit w słowie kodowym dla obiektu wynosi ”? Jednak w moim przypadku (a raczej w przypadku akinator.com) zestaw pytań jest predefiniowany i (oczywiście) nie ma nic wspólnego ze słowami kodowymi Huffmana. W tej chwili nie widzę, jak przejść z mojego pytania do kodów Huffmana. Być może mógłbyś opracować? 0i0
ADEP
@vqv: Re: „Nie sądzę, że to naprawdę problem z klasyfikacją. 20 pytań jest często określanych jako problem z kompresją”. Czy wnioskowanie statystyczne i kompresja informacji nie są bezpośrednio powiązane / ten sam problem?
Yang,
@Yang Czy odnosisz się do argumentu Jormy Rissannen? Wnioskowanie statystyczne i kompresja informacji wykorzystują modele probabilistyczne do opisywania niepewności, jednak ich perspektywy i perspektywy, jeśli badacze w tych obszarach są zasadniczo bardzo różni. Mam na myśli to, że 20 pytań można w bardziej naturalny sposób sformułować jako problem kompresji (konkretnie kodowania źródłowego), a nie problem klasyfikacji. …
Ciąg