Bagaimana 20 pertanyaan algoritma AI bekerja?

103

Game online sederhana berisi 20 pertanyaan yang didukung oleh AI yang sangat akurat.

Bagaimana mereka menebak dengan baik?

algorithm artificial-intelligence Daddy Warbox
sumber
Tampaknya itu adalah 20 pertanyaan AI terbaik yang pernah saya lihat sejauh ini. Jika tidak, saya akan menautkan ke salah satu yang lain.
Daddy Warbox
1
Sangat baik. Meskipun Akinator tampaknya menebak jauh lebih intuitif daripada 20q.net, sejauh yang saya tahu. Saya tertarik pada apa yang membuat orang itu secara khusus 'pintar'.
Daddy Warbox
1
Saya tidak tahu hal ini ada secara online. Ia menebak 'kerucut pinus' pada upaya ketiga, yang membuat saya takjub! Mengesankan
Peter Perháč
3
+1 - pasti terkait dengan pemrograman, dan pertanyaan yang bagus.
Adam Davis
@JeffAtwood, artikel mana yang coba Anda tautkan?
antony.trupe

Jawaban:

55

Anda dapat menganggapnya sebagai Algoritma Pencarian Biner. Di setiap iterasi, kami mengajukan pertanyaan, yang seharusnya menghilangkan kira-kira setengah dari kemungkinan pilihan kata. Jika ada total N kata, maka kita bisa mengharapkan jawaban setelah pertanyaan log2 (N).

Dengan 20 pertanyaan, kita harus bisa secara optimal menemukan sebuah kata diantara 2 ^ 20 = 1 juta kata.

Salah satu cara mudah untuk menghilangkan pencilan (jawaban yang salah) mungkin menggunakan sesuatu seperti RANSAC . Ini berarti, alih-alih memperhitungkan semua pertanyaan yang telah dijawab, Anda secara acak memilih subset yang lebih kecil, yang cukup untuk memberi Anda satu jawaban. Sekarang Anda mengulanginya beberapa kali dengan subset pertanyaan acak yang berbeda, sampai Anda melihat bahwa sebagian besar waktu, Anda mendapatkan hasil yang sama. Anda kemudian tahu bahwa Anda memiliki jawaban yang benar.

Tentu saja ini hanyalah salah satu cara dari banyak cara untuk menyelesaikan masalah ini.

Yogi
sumber
4
Program sederhana ini mendemonstrasikan apa yang Anda bicarakan dengan cukup baik. Setelah Anda sampai di sana, Anda dapat mengklik codetautan untuk melihatnya: openbookproject.net/py4fun/animal/animal.html
Noctis Skytower
Apakah AI semacam itu tersedia sebagai layanan? Bagaimana jika saya bisa memberikan semua pertanyaan dan jawaban dan membiarkannya menemukan mereka?
tggagne
Dan apa yang Anda sebut algoritma semacam ini? Apakah itu mempunyai nama?
tggagne
25

Pohon keputusan mendukung aplikasi semacam ini secara langsung. Pohon keputusan biasanya digunakan dalam kecerdasan buatan.

Pohon keputusan adalah pohon biner yang menanyakan pertanyaan "terbaik" pada setiap cabang untuk membedakan antara koleksi yang diwakili oleh anak kiri dan kanannya. Pertanyaan terbaik ditentukan oleh beberapa algoritma pembelajaran yang digunakan pembuat aplikasi 20 pertanyaan untuk membangun pohon. Kemudian, seperti yang ditunjukkan poster lain, pohon sedalam 20 tingkat memberi Anda sejuta hal.

Cara sederhana untuk menentukan pertanyaan "terbaik" di setiap titik adalah mencari properti yang membagi koleksi menjadi dua secara merata. Dengan begitu, saat Anda mendapatkan jawaban ya / tidak untuk pertanyaan tersebut, Anda membuang sekitar setengah dari koleksi di setiap langkah. Dengan cara ini Anda dapat memperkirakan pencarian biner.

Wikipedia memberikan contoh yang lebih lengkap:

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

Dan beberapa latar belakang umum:

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

Nathan Shively-Sanders
sumber
2
+1, saya perhatikan itu adalah salah satu komentar di artikel Atwood.
cgp
1
Benar, meskipun program BASIC, Animal tidak memiliki algoritme pelatihan untuk menentukan pertanyaan mana yang akan digunakan dan seberapa tinggi pohon untuk meletakkannya. Kinerja dengan pohon keputusan yang terlatih harus jauh lebih baik. (Saya setuju dengan pemberi komentar bahwa pertanyaan yang didapat Atwood terlihat sangat mirip dengan yang dihasilkan oleh algoritme Hewan asli dan bukan oleh jaringan saraf.)
Nathan Shively-Sanders
24

Saya merekomendasikan membaca tentang permainan di sini: http://en.wikipedia.org/wiki/Twenty_Questions

Khususnya bagian Komputer:

Permainan ini menyarankan bahwa informasi (yang diukur dengan statistik entropi Shannon) yang diperlukan untuk mengidentifikasi objek sewenang-wenang adalah sekitar 20 bit. Permainan ini sering dijadikan contoh ketika mengajar orang tentang teori informasi. Secara matematis, jika setiap pertanyaan disusun untuk menghilangkan separuh objek, 20 pertanyaan akan memungkinkan penanya untuk membedakan antara 2 20 atau 1.048.576 subjek. Oleh karena itu, strategi paling efektif untuk Dua Puluh Pertanyaan adalah mengajukan pertanyaan yang akan membagi bidang kemungkinan yang tersisa kira-kira menjadi dua setiap kali. Prosesnya dianalogikan dengan algoritma pencarian biner dalam ilmu komputer.

cgp
sumber
2
Itu menjelaskan sebagian darinya. Tetapi ketika Anda mempertimbangkan jawaban yang salah dan ambiguitas umum, itu masih tampak tidak begitu mudah.
Daddy Warbox
1
Jika Anda melihat tautannya, Anda akan melihat bahwa ini sebenarnya bukan pertanyaan ya / tidak yang dapat membagi bidang dengan setengah setiap kali. Meskipun jawaban Anda benar untuk 20 pertanyaan, saya pikir jawaban Shaun lebih akurat, algoritma pembelajaran tetangga terdekat yang sederhana, dan masukan pengguna yang cukup, memungkinkan beberapa hasil yang sangat akurat.
z -
Ah, benar, mereka mirip, tapi yang pasti tetangga terdekat lebih masuk akal.
cgp
12

Ia menyebut dirinya sebagai "jaringan saraf di internet", dan di situlah letak kuncinya. Kemungkinan menyimpan probabilitas pertanyaan / jawaban dalam matriks cadangan. Menggunakan probabilitas tersebut, ia dapat menggunakan algoritme pohon keputusan untuk menyimpulkan pertanyaan mana yang akan ditanyakan yang paling baik mempersempit pertanyaan berikutnya. Setelah mempersempit jumlah kemungkinan jawaban menjadi beberapa lusin, atau jika sudah mencapai 20 pertanyaan, maka kemungkinan besar akan mulai membaca.

Aspek yang benar-benar menarik dari 20q.net adalah tidak seperti kebanyakan pohon keputusan dan algoritme jaringan saraf yang saya ketahui, 20q mendukung matriks renggang dan pembaruan tambahan.

Edit: Ternyata jawabannya sudah ada di internet selama ini. Robin Burgener, sang penemu, menjelaskan algoritmanya secara detail dalam pengajuan paten tahun 2005 .

Cerin
sumber
6

Ini menggunakan algoritma pembelajaran.

k-NN adalah contoh bagus dari salah satunya.

Wikipedia: Algoritma Tetangga Terdekat

Shaun Mason
sumber
4
Apakah algoritme tetangga terdekat merupakan pilihan yang baik dalam kasus ini? Tampaknya akan terlalu memaafkan jawaban yang salah, dan bisa berakhir dengan sejumlah besar dimensi, banyak di antaranya tanpa data. (Saya mengasumsikan penggunaan jarak hamming, dan satu dimensi per pertanyaan.) Pohon keputusan tampaknya lebih cocok secara alami.
Kylotan
1
Teori belajar adalah jawaban yang benar - tidak masalah memberikan jawaban yang kurang 'akurat' karena didasarkan pada kesalahan yang cenderung dilakukan setiap orang, yang sebenarnya membuatnya lebih baik dalam menebak.
Jonathan Plackett
Jadi, bagaimana ini membantu mengidentifikasi pertanyaan terbaik untuk ditanyakan?
Thomas Ahle