まだ知らない人のために説明すると、アキネイターはフランスの会社が作ったコンピュータゲームとモバイルアプリです。
Akinator の目標は、実在または架空の人物を推測することです。 プレイヤーは「はい」「わかりません」「いいえ」「たぶん」「たぶん」で答え、 プログラムが最適な質問を決定します。
それぞれの答えに対して、Akinatorはプレイヤーに尋ねるべき最適な質問を計算し、最後にこのプレイヤーが誰のことを考えているか推測を行う。 最初の推測が正しくなければ、Akinatorは質問を続け、そうして最大3つの推測をする;最初のものは、一般的に15〜20の質問の後にある。 3回目も正解でない場合、プレイヤーはそのキャラクターをデータベースに追加するよう求められる。
問題の選択に使われるアルゴリズムは、前述のフランス企業が完全に開発し、秘密にしている。 しかし、このアルゴリズムがどのように構築され、Akinatorでどのように使用されているかを説明した記事は比較的容易に見つけることができる。 この記事では、このアルゴリズムを簡単に楽しく理解する方法を紹介します。
Akinator Working
いくつかの記事では、Akinatorは決定木だけでなく、確率的手法や強化学習を使っていると書かれています。 今回は決定木の中でも重要なアルゴリズムである決定木のインクリメンタルインダクション3（ID3）とID4について紹介する。
決定木の詳細については、記事「木モデルの基本概念」
Incremental Induction of Decision Trees 3 (ID3)
ID3 アルゴリズムの基本概念は、木の各ノードで各属性をテストし、与えられたセットを通してトップダウン、欲深い検索を使って決定木を構築することである。
ID3 をよりよく理解したい場合は、記事を参照してください。 “例” を参照してください。
学習セットを分類する最適な方法を見つけるために、質問された問題を最小限にする必要があります（つまり、木の深さを最小限にする）。 したがって、どの質問が最もバランスのとれた分割を提供するかを測定できる関数が必要である。 情報利得はそのような関数である。つまり、情報利得は初期集合の不純物測定値（すなわち、, 前回の記事「木モデルの基本概念」では、ジニとエントロピーが不純度の尺度であることを学びました）。
Entropy(S) はデータ分割前のImpurity値、Entropy(S,X) は分割後の不純度である。
Information Gainでは、ツリー構築の際に、
- 各属性の分割の評価と最適な分割の選択、および
- 最適分割によるパーティションの作成の2つの主要作業がある。
常に理解しておくべき非常に重要なことは、複雑さは各属性の最適な分割を決定することにあり、前述のように、エントロピーまたはジニに基づいて、情報利益を計算することができるということです。
したがって、情報利得を使用して、ID3 ツリーで使用されるアルゴリズムは次のとおりです。
- すべてのインスタンスが正確に 1 つのクラスからある場合、決定木はそのクラス名を含む回答ノードとなります。
- そうでなければ、
(a) a(best)を最も低いゲインスコアを持つ属性（または特徴）として定義する。
(b) a(best) の各値 V(best,i) について、属性 a(best) の値 V(best,i) を持つすべてのインスタンスから再帰的に構築される決定木に a(best) から枝を伸ばす。
ID4
もうひとつの重要なアルゴリズムは ID4 である。 彼らはこのアルゴリズムが新しい学習インスタンスを受け入れ、決定木を更新することで、元の木に保持されているグローバルなデータ構造のために決定木を再構築することを回避できると主張している。
ID4アルゴリズムの木更新の基本手順を以下に示す。 決定木、1つのインスタンス
output: 決定木
- 現在のノードで可能な各テスト属性について、学習インスタンスでその属性の値に対する正または負のインスタンスのカウントを更新します。
- 現在のノードで観察されたすべてのインスタンスが正（負）である場合、現在のノードでの決定木は、正（負）インスタンスを示すために「＋」（「-」）を含む回答ノードである。
- そうでなければ、
（a） 現在のノードが回答ノードであれば、最も低いゲインが付いた属性テストを含む決定ノードへそれを変更します。
(b) そうでない場合、現在の決定ノードが最低のゲインスコアを持っていない属性テストを含んでいれば、
- 属性テストを最低のゲインスコアを持つものに変更する。
- 決定ノード以下のすべての既存のサブツリーを破棄する。
インスタンス記述で発生する現在のテスト属性の値の枝に沿って現在の決定ノード以下の決定ツリーを再帰的に更新する。
決定木の詳細については、「決定木」を参照してください。 「ツリーモデルの基本概念」、「例: 例：エントロピーとジニ指数を使用して不純物を計算する」
を参照してください。