What is This?

このコードはアキネーターのような提案システムをシンプルにして実現します.
しかし、まだ開発中です.

This is code to try to implement something like Akinator.
But still now , under development.

Page : Thothnator Demo

How?

No English Sorry

外部仕様

だいぶシンプルです.

  • ユーザの入力はYes/Noのみ
  • YesとNoが答えにくい問題があることも想定(ただしYes.Noしか選べないことは変わらない.計算上ケアするのみ)
  • 質問の繰り返しによって対象を絞っていく

内部動作

▼仕組み

実際のところ、内部の仕組みについて、未検証な状態です. ただなんとなく動いっているぽく見えるってところです.

全体流れ

全体の流れは以下のように行なっています.

1. 単語リストの確率を元に最もエントロピーの低くなる質問を選択
2. 質問を提示してユーザにYesとNoを選択してもらう
3. 選択に応じて単語リストの確率を更新
4. 特定の単語の確率が0.5を超えたら終了.超えてなければ1へ
以下では、上の1と3についてやや詳しく記述しています.

必要な事前データ

このシステムを動かすには事前に幾らかの情報が必要になります.
質問と回答候補の単語と質問に対する各単語のYesとNoのデータです.
今回以下の情報を持つ構造体を持っています.

  • 質問Q
  • 単語W
  • Yesの回数
  • Noの回数
この構造体の情報から単語Wが答えだった場合に質問Qを受けてYと答える確率とNと答える確率が求められます. $$P(ans=y) = \frac{Y_{num}}{Y_{num} + N_{num}}, P(ans=n) = \frac{N_{num}}{Y_{num} + N_{num}}$$

詳細な計算

内容が合っている自信は全くないですが、念のため書いておきます.

確率の更新

\(W\):単語
\(A\):YesまたはNo
\(Q\):質問. 以下では式が複雑に見えるため、わざと書いていません.
\(QA_{history}\):今までの質問と今までのユーザのYesまたはNo
\(p(W)\) : 単語Wの確率
\(p(A|W,QA_{history})\) : 単語Wと過去のQAhistoryを与えられたときにAと答える確率.ただQAhistoryは実際関係なくp(A|W)です.
\(p(W|A,QA_{history})\) : Aと過去のQAhistoryを与えられたときに単語Wである確率

下記の式を更新しながら\(p(W|A,QA_{history})\)を見て、単語が分かったかどうかを判定します. $$p(W|A,QA_{history}) = \frac{p(A|W, QA_{history})p(W|QA_{history})}{p(A|QA_{history})}$$ ここの左辺の値が各単語の確率です.判定はシンプルに最も確率が高い単語を選べばよいかと思います.確率が1になるまで計算はできないので、どこかで辞める必要があります.複数ある候補がある中で0.5の確率になったものはそこそこ正しいとして判定しました.

その左辺を計算するには、この右辺を当然計算する必要があります. それぞれの意味は以下のようになっています.

\(p(A|W, QA_{history})\):これはあらかじめ調べている値です.前述の通りQAhistoryは関係なく、厳密に書くならp(A|W,Q)です.これはある単語とある質問のときにどのくらいYesと答えるかですが、これは事前データから計算します.
\(p(W|QA_{history})\):一つ前の質問のタイミングで求めた\(p(W|A, QA_{history})\)がこれです.
\(p(A|QA_{history})\):上の二つの分布の値を使って周辺化を行い求めます.
周辺化は $$p(A|QA_{history}) = \int_W p(A|W,QA_{history}) p(W|QA_{history})$$

質問の選択

次に質問の選択です.
ベースの考え方は決定木学習と同じはずです.

質問の選択は、それぞれの質問をしたときに単語の確率分布がどのような分布に変わるかを想定して選びます. 毎回の質問で、ある質問をして回答を得た時に最も候補が少なくなることが理想です. 「最も候補が少なくなった状態」は「エントロピーが低い」ことによって表すことができます. エントロピーはあいまいさの指標であり、もう答えの確信を持っている状態はすなわちエントロピーが低い状態なのです.

エントロピーの式 $$ H = \sum_{i=0}^n - p_i log_2(p_i)$$

例えば

赤の確率が1で青の確率が0で緑の確率が0とした場合エントロピーは0
赤の確率が0.5で青の確率が0.5で緑の確率が0とした場合エントロピーは1
赤の確率が0.3で青の確率が0.3で緑の確率が0.3とした場合エントロピーは1.584

全くあてがつかないほど、値が大きくなっていることがわかるかと思います. これを利用してどの質問をすればより候補を絞れるかの評価をします.
今回は以下のような計算を行えばいいはずです.

$$H(W) = \sum_{i=0}^{n} - p(W|QA_{history}) log(p(W|QA_{history}))$$

もう一つ気にする点は、Yesを選択する場合とNoを選択する場合の両方をケアする必要があることです. そこで、Yesと答える確率とNoと答える確率も考慮して計算をします.

上記のような通常のエントロピーではなく,Yesの場合とNoの場合を考慮した条件付きエントロピーで計算します. 計算の内容としては、それぞれの場合のエントロピーを計算して、加重平均を取るだけです. より詳しくは、情報利得や決定木学習がキーワードになると思いますので、お調べください.

$$H(W|ANS) = \sum_{ans=yes,no}p(ANS=ans) (\sum_{i=0}^{n} - p(W|ans, QA_{history}) log(p(W|ans, QA_{history})))$$

I put on Github.
UrusuLambda's Github
PythonとJavaScriptの両方で実装しました.

Code (Javascript)

そこまで複雑にはしていないですが, コードが汚いので読みにくいかもです.
表示のコードも混じってしまっているので、Pythonの方が何をしたいかがわかるかと思います.

Code (Pythono)

CUIなのでよりシンプルにしています.