Klasifikasi Akinator.com dan Naive Bayes

12

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

Kemudian prediktor mencari .P(S|G)=P(G|S)P(S)P(G)

Sebelum untuk subyek ( ) bisa saja berapa kali subjek telah ditebak dibagi dengan jumlah total game.P(S)

Dengan membuat asumsi bahwa semua jawaban independen, kita dapat menghitung kemungkinan subjek S mengingat permainan G seperti:

P(G|S)=i=1..nP({qi,ai}|S)

Kita dapat menghitung jika kita melacak pertanyaan dan jawaban mana yang diberikan ketika yang digunakan memiliki subjek yang diberikan: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

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:P(S|G)

argmaxj(H[P(S|G)]a=yes,no,maybe...H[P(S|G{qj,a})]

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 } )P(S|G)P(S|G{qj,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?

Mahir
sumber
4
Saya ragu itu adalah Naif Bayes, bukan pohon keputusan diperpanjang setiap kali gagal mengenali seseorang.
1
Bukankah pohon keputusan seperti itu terlalu sulit untuk diperbarui? Plus, saya tidak melihat cara mudah untuk menjelaskan jawaban yang secara tidak sengaja salah / jujur ​​dan kesalahan tetap pada akhirnya dengan pohon keputusan
ADEpt
5
Sepertinya reinkarnasi dari 20-pertanyaan penjebak berusia 20 tahun, sekarang di 20q.net . Berikut ini penjelasan populer cara kerjanya mentalfloss.com/blogs/archives/13725
Yaroslav Bulatov
5
Maaf, tapi saya pikir menggunakan "kecerdasan buatan" dan "jaringan saraf" tanpa konteks apa pun dianggap sebagai penjelasan. Dan saya tidak bisa melihat bagaimana orang dapat menggunakan neural net untuk hal semacam ini - apa yang akan menjadi fungsi output, misalnya?
ADEpt
Hai @ADEpt, Sudah lama sejak pertanyaan itu diajukan, tetapi bisakah Anda membagikan kode sumber untuk implementasi yang Anda lakukan di sana?
prikha

Jawaban:

10

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

  1. Sejumlah pertanyaan tetap, dengan beberapa pertanyaan ditandai sebagai pertanyaan "final".
  2. Satu unit input per pertanyaan, di mana 0/1merupakan no/yesjawaban. Awalnya disetel ke0.5
  3. Satu unit output per pertanyaan, sigmoid dimasukkan ke dalam kisaran 0..1
  4. Lapisan tersembunyi yang menghubungkan semua unit input ke semua unit output.

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 NNpaling tidak pasti tentang, yaitu, unit output yang sesuai dekat 0.5, ajukan pertanyaan, dan atur unit input yang sesuai untuk jawabannya. Pada tahap terakhir Anda memilih unit output dari daftar "pertanyaan terakhir" dengan nilai terdekat 1.

Setiap permainan dari 20 pertanyaan memberikan 20 titik data yang dapat Anda gunakan untuk memperbarui NNbobot 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.

Yaroslav Bulatov
sumber
7

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.

vqv
sumber
Itu awal yang baik, tapi saya pikir ada lebih banyak masalah. Misalnya: bagaimana mereka mendapatkan jawaban atas pertanyaan? Agaknya mereka menggunakan jawaban yang diberikan oleh pemain sebelumnya (masalah pembelajaran penguatan), dalam hal ini kita menghadapi tradeoff memilih pertanyaan yang (a) memecahkan masalah untuk pemain saat ini, dan (b) memberikan informasi untuk pemain masa depan.
Simon Byrne
Pada pandangan pertama, kemampuan untuk menggambar analogi antara 20 pertanyaan dan pengkodean Huffman bergantung pada kemampuan untuk bertanya "rentang pertanyaan". Artinya, alih-alih "Apakah karakter Anda pernah ke luar angkasa?" kami mengajukan pertanyaan "selimut" seperti "Apakah dia pernah ke luar angkasa, atau laki-laki, atau botak, atau berada di film, atau ... (100500 pilihan lain)?" Apakah saya benar? Jika demikian, maka saya mungkin harus mengedit pertanyaan saya untuk memperjelas bahwa saya tertarik pada varietas "tanyakan satu per satu"
ADEpt
Plus, sebagian besar artikel yang menggunakan kode Huffman sebagai model untuk 20 pertanyaan, menyiratkan bahwa penanya bebas untuk membuat pertanyaan sendiri, yang pada dasarnya bermuara pada "Apakah bit dalam codeword untuk objek adalah "? Namun, dalam kasus saya (atau, lebih tepatnya, kasus akinator.com) set pertanyaan sudah ditentukan sebelumnya, dan itu (jelas) tidak ada hubungannya dengan kata sandi Huffman. Saat ini saya tidak dapat melihat bagaimana melakukan transisi dari pertanyaan saya ke kode Huffman. Mungkin Anda bisa menguraikan? 0i0
ADEpt
@vqv: Re: "Saya tidak berpikir itu benar-benar masalah klasifikasi. 20 pertanyaan sering ditandai sebagai masalah kompresi." Tidakkah inferensi statistik dan kompresi informasi terkait langsung / masalah yang sama?
Yang
@Yang Apakah Anda mengacu pada argumen Jorma Rissannen? Inferensi statistik dan kompresi informasi keduanya menggunakan model probabilistik untuk menggambarkan ketidakpastian, namun perspektif mereka dan mereka jika para peneliti di daerah tersebut umumnya sangat berbeda. Yang ingin saya katakan di atas adalah bahwa 20 pertanyaan dapat lebih dirumuskan secara alami sebagai masalah kompresi (khususnya, pengkodean sumber) daripada masalah klasifikasi. ... berlanjut di bawah ini
vqv