Jak działa algorytm sztucznej inteligencji z 20 pytaniami?

103

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

Jak oni tak dobrze zgadywali?

algorithm artificial-intelligence

— Daddy Warbox
źródło

Wydaje się, że to 20 najlepszych pytań AI, jakie do tej pory widziałem. W przeciwnym razie utworzę link do jednego z pozostałych.

— Daddy Warbox

1

Bardzo dobrze. Chociaż Akinator wydaje się zgadywać znacznie bardziej intuicyjnie niż 20q.net, o ile wiem. Interesuje mnie, co sprawia, że jest on szczególnie „inteligentny”, że tak powiem.

— Daddy Warbox

1

nie miałem pojęcia, że to coś istnieje w Internecie. Ku mojemu zdumieniu odgadł „szyszkę” przy trzeciej próbie! Imponujące

— Peter Perháč

3

+1 - zdecydowanie związane z programowaniem i dobre pytanie.

— Adam Davis

@JeffAtwood Do którego artykułu próbowałeś utworzyć link?

— antony.trupe

55

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.

— Jog
źródło

4

Ten prosty program dość dobrze pokazuje, o czym mówisz. Po dotarciu na miejsce możesz kliknąć codelink, aby go zobaczyć: openbookproject.net/py4fun/animal/animal.html

— Noctis Skytower

Czy tego rodzaju sztuczna inteligencja jest dostępna jako usługa? A jeśli mógłbym udzielić wszystkich pytań i odpowiedzi i pozwolić mu je znaleźć?

— tggagne

A jak nazywasz ten rodzaj algorytmu? Czy ma imię?

— tggagne

25

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

— Nathan Shively-Sanders
źródło

2

+1, chciałbym zauważyć, że był to jeden z komentarzy w artykule Atwooda.

— cgp

1

To prawda, chociaż program Animal w języku BASIC nie ma algorytmu uczącego do określania, których pytań użyć i na jakiej wysokości w drzewie je umieścić. Wydajność przy wyszkolonym drzewie decyzyjnym powinna być znacznie lepsza. (Zgadzam się z komentatorem, że pytania, które otrzymał Atwood, wyglądają bardzo podobnie, jakby zostały wygenerowane przez oryginalny algorytm Animal, a nie przez sieć neuronową.)

— Nathan Shively-Sanders

24

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.

— cgp
źródło

2

To częściowo wyjaśnia. Ale jeśli weźmiesz pod uwagę nieprawidłowe odpowiedzi i ogólną niejednoznaczność, nadal wydaje się to nie być takie proste.

— Daddy Warbox

1

Jeśli spojrzysz na link, zobaczysz, że tak naprawdę nie jest to pytanie typu tak / nie, które może za każdym razem podzielić pole o połowę. Chociaż twoja odpowiedź jest poprawna na 20 pytań, myślę, że odpowiedź Shauna jest dokładniejsza, a prosty algorytm uczenia się najbliższego sąsiada i wystarczająca ilość danych wejściowych użytkownika pozwala uzyskać bardzo dokładne wyniki.

— z -

Ach, prawda, są podobne, ale zdecydowanie najbliższy sąsiad ma więcej sensu.

— cgp

12

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 .

— Cerin
źródło

6

Wykorzystuje algorytm uczenia się.

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

Wikipedia: algorytm k-najbliższego sąsiada

— Shaun Mason
źródło

4

Czy algorytm najbliższego sąsiada to dobry wybór w tym przypadku? Wydawałoby się, że byłoby to zbyt wybaczające błędne odpowiedzi i mogłoby skończyć się z ogromną liczbą wymiarów, z których wiele byłoby pozbawionych danych. (Zakładam użycie odległości Hamminga i jednego wymiaru na pytanie). Drzewo decyzyjne wydaje się bardziej naturalne.

— Kylotan

1

Teoria uczenia się jest poprawną odpowiedzią - nie ma znaczenia, że daje mniej „trafnych” odpowiedzi, ponieważ opiera się na błędach, które wszyscy popełniają, co w rzeczywistości ułatwia zgadywanie.

— Jonathan Plackett

Jak więc pomaga to w zidentyfikowaniu najlepszego pytania, jakie należy zadać?

— Thomas Ahle,