Jak działa algorytm sztucznej inteligencji z 20 pytaniami?

Proste gry online zawierające 20 pytań, obsługiwane przez niesamowicie dokładną sztuczną inteligencję.

Jak oni tak dobrze zgadywali?

Możesz myśleć o tym jako o algorytmie wyszukiwania binarnego. W każdej iteracji zadajemy pytanie, które powinno wyeliminować mniej więcej połowę możliwych wyborów słów. Jeśli w sumie jest N słów, możemy spodziewać się odpowiedzi po pytaniach log2 (N).

Przy pytaniu 20 optymalnie powinniśmy być w stanie znaleźć słowo wśród 2 ^ 20 = 1 milion słów.

Prostym sposobem na wyeliminowanie wartości odstających (błędnych odpowiedzi) byłoby prawdopodobnie użycie czegoś takiego jak RANSAC . Oznaczałoby to, że zamiast brać pod uwagę wszystkie pytania, na które udzielono odpowiedzi, losowo wybierasz mniejszy podzbiór, który wystarczy, aby udzielić Ci jednej odpowiedzi. Teraz powtórz to kilka razy z różnymi losowymi podzbiorami pytań, aż zobaczysz, że przez większość czasu uzyskujesz ten sam wynik. wiesz, że masz właściwą odpowiedź.

Oczywiście jest to tylko jeden z wielu sposobów rozwiązania tego problemu.

Drzewo decyzyjne bezpośrednio obsługuje tego rodzaju aplikacje. Drzewa decyzyjne są powszechnie używane w sztucznej inteligencji.

Drzewo decyzyjne to drzewo binarne, które zadaje „najlepsze” pytanie w każdej gałęzi, aby rozróżnić kolekcje reprezentowane przez jej lewe i prawe dziecko. Najlepsze pytanie jest określane przez algorytm uczenia się, którego twórcy aplikacji 20 pytań używają do budowania drzewa. Następnie, jak wskazują inne plakaty, drzewo na głębokości 20 poziomów daje milion rzeczy.

Prostym sposobem na zdefiniowanie „najlepszego” pytania w każdym punkcie jest wyszukanie właściwości, która w najbardziej równomierny sposób dzieli zbiór na połowę. W ten sposób, gdy otrzymasz odpowiedź tak / nie na to pytanie, pozbędziesz się około połowy kolekcji na każdym kroku. W ten sposób możesz przybliżać wyszukiwanie binarne.

Wikipedia podaje pełniejszy przykład:

http://en.wikipedia.org/wiki/Decision_tree_learning

I kilka ogólnych informacji:

http://en.wikipedia.org/wiki/Decision_tree

Polecam poczytać o grze tutaj: http://en.wikipedia.org/wiki/Twenty_Questions

W szczególności sekcja Komputery:

Gra sugeruje, że informacja (mierzona statystyką entropii Shannona) wymagana do zidentyfikowania dowolnego obiektu ma około 20 bitów. Gra jest często używana jako przykład podczas nauczania teorii informacji. Matematycznie, jeśli struktura każdego pytania eliminuje połowę obiektów, 20 pytań pozwoli pytającemu na rozróżnienie między 2 ²⁰ a 1 048 576 przedmiotów. W związku z tym najskuteczniejszą strategią w przypadku dwudziestu pytań jest zadawanie pytań, które za każdym razem podzielą pole pozostałych możliwości mniej więcej na pół. Proces jest analogiczny do binarnego algorytmu wyszukiwania w informatyce.

Rachuje się jako „sieć neuronowa w Internecie” i na tym polega klucz. Prawdopodobnie przechowuje prawdopodobieństwa pytania / odpowiedzi w zapasowej macierzy. Korzystając z tych prawdopodobieństw, jest w stanie użyć algorytmu drzewa decyzyjnego, aby wydedukować, które pytanie zadać, aby najlepiej zawęzić następne pytanie. Gdy zawęzi liczbę możliwych odpowiedzi do kilkudziesięciu, lub jeśli osiągnie już 20 pytań, wtedy najprawdopodobniej zacznie odczytywać.

Naprawdę intrygującym aspektem 20q.net jest to, że w przeciwieństwie do większości znanych mi algorytmów drzew decyzyjnych i sieci neuronowych, 20q obsługuje rzadką macierz i aktualizacje przyrostowe.

Edycja: Okazuje się, że przez cały czas odpowiedź była w sieci. Robin Burgener, wynalazca, szczegółowo opisał swój algorytm w zgłoszeniu patentowym z 2005 roku .

Wykorzystuje algorytm uczenia się.

k-NN jest dobrym przykładem jednego z nich.

Wikipedia: algorytm k-najbliższego sąsiada