たなっちのメモ

ロボットとWebサービスを触ってたハッカソン好きの地方工業大学生。最近は機械学習とコンパイラ、OS開発をこっそり勉強中。時間と余裕とモチベがあったら書く予定（？）。

LINE Bot でアキネーターを実装した（理論編）

仕組みが気になったので
LINE Bot でアキネーターを再現してみました．
需要があるかわかりませんが
まとめておきます．

まえがき

最近，疫病が流行ってて何かと物騒ですが
いかがお過ごしでしょうか．
私は卒論の提出・発表が無事に終了しまして，
晴れて学部卒業です．

先日プロ研でLINEbotのハンズオンとハッカソンが開催されました．
私は裏方仕事とハッカソンの審査員での参加でした．
後輩たちが企画・運営をこなしていて大変感心しました．

せっかくみんなで LINE Bot を開発する機会なので
私も何か作ることにしました．
LINE Bot の機能をガンガン使うというよりは
以前からやりたかったアキネーターの実装をすることにしました．

場の空気的にお披露目することはなかったんですがね．

今回は実装に取り掛かる前に設計を入念にやってみました．
というのも，卒論提出前にそんなことを本気でやってる場合じゃなかったのと
年明け直後に PC が故障して修理に出していたので
そうせざるを得なかったのですがね．

アキネーターとは

アキネーターとは何ぞやという方もいらっしゃると思われますので
軽く説明をしておきます．

アキネーターというのは
ユーザが思い浮かべている人物などを
簡単な質問に「はい」or「いいえ」と
回答することよって絞り込んで当ててくるゲーム(？)です．
いわゆるエキスパートシステムですね．

ブラウザ上でも遊べるみたいなのでやってみてください．

また，単に当てるだけじゃなくて
不正解だった場合に正解を尋ねたりなど，
自ら知識を蓄えていく機能も備わっています．

しかし，本家のソースコードやアルゴリズムが公開されていないので
その仕組みは謎に包まれています．

提案アルゴリズム

どうすれば本家の動作が再現できるのかを考えた結果，
以下のような方針で実装することにしました．

前提

アキネーターのデータベースには「男性？」とか「実在する？」などといった
質問が多数格納されています．
そして「ユーザが思い浮かべたもの」の候補はそれぞれ，
各質問に対する答えを持っています.

ややこしいので「ユーザが思い浮かべたもの」およびその候補を『Solution(s)』，
「ある Solution についての，ある質問に対する回答」を『Feature(s)』と呼びます．
表に示すと下のようになります．

Solution プログラミング言語？ 日本生まれ？
英語 × ×
日本語 × ○
Python ○ ×
Ruby ○ ○

(日本語が日本生まれなのかという議論は置いといて)
○とか×とかそれぞれが
Feature の値となります．

ユーザが質問に対して答えることで、
ゲームは進行していきます．
ここで，質問に対するユーザの回答を
Answer(s)とします.

Answersの中身は表に示すと下のようになります．

\ プログラミング言語？ 日本生まれ？
Answers ○ ×

Solution の絞り込み

質問を繰り返しながら Solution を絞り込むために
各 Solution と Answers の特徴を比較します．

計算のために

○ =>  1
× => -1

とすると，

\ Q_1 Q_2 Q_3 ... Q_n
Solution 1 -1 1 ... -1
Answers 1 -1 -1 ... -1

こんな感じになります．
ここで，同じ質問に対する値(Feature) をそれぞれ掛け算したときに，
答えが一致すれば正，そうでなければ負になります．
また，それらを合算したときの値が正であれば
全体として近い特徴を持っていることがわかります．

つまり，Solution と Answer をベクトルと見立てると
内積を計算する要領で
特徴の一致度を計算することができます．

s = ( 1 -1  1 ... -1)
a = ( 1 -1 -1 ... -1)

s・a > 0 であれば，s と a は近い特徴を持つと言える．

今回の実装では
全ての Solutions について Answers との内積を計算して
結果が 0 以上になるものを候補とするように実装しました．
(厳密にはもう少し効率化していますが．)

効率よく質問を投げる

データベースにある質問に全て答えてから当てられるより，
じわじわと核心に迫るような質問をされてから当てられた方が
プレイする側としてはワクワクしますよね．
ということで
効率よく質問を投げかけるため
二分探索の要領で次の質問を選択するようにしました．

どういうことかというと，
例えば「それは Python ですか？」という質問があったとして
それに「はい」と答えたら Solution は 「Python」 で確定できますが
逆に「いいえ」だった場合，候補から外れるのは「Python」のみです．
当然，確率的にも「いいえ」と回答されることの方が多く
あまり効率的ではありません．

今回の実装では，
Solution の候補の中で
「はい」と「いいえ」が
だいたい半分に分かれるような質問をすることで
問答ごとに候補の数を約半分に削っていくようにしました．
この辺が二分探索に似ているのではと思います．

計算の仕方としては
表の縦のラインの値を合算して
合計が最も0に近いものが，
次に投げる質問として選ばれます．

\ Q_1 Q_2 Q_3 Q_4
Solution1 1 -1 1 -1
Solution2 1 -1 -1 -1
Solution3 -1 -1 -1 -1
Solution4 1 -1 1 1

上の表だと Q3 が該当します．

まとめ

これならいけるんやないかと思いました．

もっとランダムフォレストやら何やらの
機械学習チックなものを期待してたんですが
そんな大層なアルゴリズムを使わずともできそうです．
というか，できました．

実は，本家には無い弱点があるのですが
それはまた次回書きます．

余談

需要あるかなあ．
今回は（）← をあんまり使ってない気がする．

Visit my Home page.