読者です 読者をやめる 読者になる 読者になる

ゆーぶろぐ

ゆーたんです。https://twitter.com/ut_an

akinatorの仕組みについて考えたこと

1年ほど前にakinatorのアルゴリズムについて考察したから、忘れないうちにまとめておく。

各質問に対してその質問を選んだ時に得られる情報量を計算し、その質問を投げかけるという単純なもので、実際には何らかの方法で高速化したほうがよいかもしれない。


質問:1...N
質問nに対する選択肢:1...M(n)
解答:1...L
o[n,m,l]を、「lが解答のとき、質問nに対してmが選ばれる確率」とする。

実行する手順
1. 各解答が正答である確率 a[1]...a[L]を計算する。
2. すべてのnについて、以下のp[n]を計算する。
    q[m] = Σ_l∈A[L] {a[l]*o[n,m,l]}
    p[n] = - Σ_m∈O[M(n)] {q[m]log(q[m])}
3. p[n]が最大となる質問を行い、選択肢を選ばせる。
4. a[1]...a[L]を次の値に更新する。nおよびmは3.で選んだ質問および選択肢とする。
    a[l] = a[l]*o[n,m,l]/q[m]
5. a[1]...a[L]の最大値が望んだ値より大きくなるまで、2.に戻って繰り返す。