Konteks: Saya seorang programmer dengan beberapa (setengah terlupakan) pengalaman dalam statistik dari kursus uni. Baru-baru ini saya menemukan http://akinator.com dan menghabiskan beberapa waktu mencoba membuatnya gagal. Dan siapa yang tidak? :)
Saya telah memutuskan untuk mencari tahu cara kerjanya. Setelah googling dan membaca posting blog terkait dan menambahkan beberapa (terbatas) pengetahuan saya ke dalam campuran yang dihasilkan saya datang dengan model berikut (saya yakin bahwa saya akan menggunakan notasi yang salah, tolong jangan bunuh saya untuk itu):
Ada Subjek (S) dan Pertanyaan (Q). Tujuan prediktor adalah memilih subjek S yang memiliki probabilitas aposterior terbesar untuk menjadi subjek yang dipikirkan pengguna, diberikan pertanyaan dan jawaban yang dikumpulkan sejauh ini.
Biarkan game G menjadi serangkaian pertanyaan yang diajukan dan jawaban diberikan: .
Kemudian prediktor mencari .
Sebelum untuk subyek ( ) bisa saja berapa kali subjek telah ditebak dibagi dengan jumlah total game.
Dengan membuat asumsi bahwa semua jawaban independen, kita dapat menghitung kemungkinan subjek S mengingat permainan G seperti:
Kita dapat menghitung jika kita melacak pertanyaan dan jawaban mana yang diberikan ketika yang digunakan memiliki subjek yang diberikan:
Sekarang, mendefinisikan distribusi probabilitas lebih dari subjek dan ketika kita perlu memilih pertanyaan berikutnya kita harus memilih salah satu yang diharapkan perubahan dalam entropi distribusi ini maksimal:
Saya sudah mencoba mengimplementasikan ini dan berhasil. Tetapi, jelas, ketika jumlah subjek meningkat, kinerja menurun karena kebutuhan untuk menghitung ulang setelah setiap gerakan dan menghitung distribusi diperbarui untuk pemilihan pertanyaan.P ( S | G ∨ { q j , a } )
Saya curiga saya hanya memilih model yang salah, terkendala oleh keterbatasan pengetahuan saya. Atau, mungkin, ada kesalahan dalam matematika. Tolong beri tahu saya: apa yang harus saya ketahui, atau bagaimana mengubah prediktor sehingga dapat mengatasi jutaan subjek dan ribuan pertanyaan?
Jawaban:
Game ini terlihat mirip dengan 20 pertanyaan di http://20q.net , yang menurut laporan pembuatnya didasarkan pada jaringan saraf. Inilah salah satu cara untuk menyusun jaringan seperti itu, mirip dengan jaringan saraf yang dijelaskan dalam vektor deskripsi Konsep dan permainan 20 pertanyaan .
Anda pasti sudah
0/1
merupakanno/yes
jawaban. Awalnya disetel ke0.5
Unit input untuk pertanyaan yang telah dijawab diatur ke 0 atau 1, dan asumsi adalah bahwa jaringan saraf telah dilatih untuk membuat unit output nilai output mendekati 1 untuk pertanyaan yang memiliki jawaban "Ya" diberikan satu set jawaban yang ada.
Pada setiap tahap Anda akan memilih pertanyaan yang
NN
paling tidak pasti tentang, yaitu, unit output yang sesuai dekat0.5
, ajukan pertanyaan, dan atur unit input yang sesuai untuk jawabannya. Pada tahap terakhir Anda memilih unit output dari daftar "pertanyaan terakhir" dengan nilai terdekat1
.Setiap permainan dari 20 pertanyaan memberikan 20 titik data yang dapat Anda gunakan untuk memperbarui
NN
bobot dengan back-propagation, yaitu, Anda memperbarui bobot untuk membuat output dari jaringan saraf saat ini cocok dengan jawaban yang benar mengingat semua pertanyaan sebelumnya diajukan.sumber
Saya tidak berpikir itu benar-benar masalah klasifikasi. 20 pertanyaan sering ditandai sebagai masalah kompresi . Ini sebenarnya lebih cocok dengan bagian terakhir dari pertanyaan Anda di mana Anda berbicara tentang entropi.
Lihat Bab 5.7 ( Google books ) dari
Cover, TM dan Joy, AT (2006) Elemen Teori Informasi
dan juga pengkodean Huffman . Makalah ini saya temukan di arXiv mungkin menarik juga.
Gill, JT dan Wu, W. (2010) "Dua Puluh Pertanyaan Game Selalu Berakhir Dengan Ya" http://arxiv.org/abs/1002.4907
Untuk kesederhanaan, anggap ya / tidak pertanyaan (sedangkan akinator.com memungkinkan memungkinkan, tidak tahu). Asumsikan bahwa setiap subjek yang mungkin (apa yang diketahui oleh akinator.com) dapat diidentifikasi secara unik dengan urutan ya / tidak pertanyaan dan jawaban - pada dasarnya vektor biner.
Pertanyaan-pertanyaan yang (dan jawaban mereka) ditanyakan menentukan partisi ruang subjek secara rekursif. Partisi ini juga sesuai dengan struktur pohon. Vertikal interior pohon sesuai dengan pertanyaan, dan daun sesuai dengan subjek. Kedalaman daun persis jumlah pertanyaan yang diperlukan untuk mengidentifikasi subjek secara unik. Anda dapat (secara sepele) mengidentifikasi setiap subjek yang diketahui dengan mengajukan setiap pertanyaan yang mungkin. Itu tidak menarik karena berpotensi ada ratusan pertanyaan.
Koneksi dengan pengkodean Huffman adalah bahwa ia memberikan cara yang optimal (di bawah model probabilistik tertentu) untuk membangun pohon sehingga kedalaman rata-rata adalah (hampir) minimal. Dengan kata lain, ini memberitahu Anda bagaimana mengatur urutan pertanyaan (membangun pohon) sehingga jumlah pertanyaan yang perlu Anda ajukan rata-rata kecil. Itu menggunakan pendekatan serakah.
Ada, tentu saja, lebih ke akinator.com daripada ini, tetapi ide dasarnya adalah Anda dapat memikirkan masalah dalam hal pohon dan mencoba meminimalkan kedalaman rata-rata daunnya.
sumber