「20の質問」AIアルゴリズムはどのように機能しますか？
1. 序章
友達と一緒にプレイできる最もシンプルなパーティーゲームの1つは、「GuessWho？」です。 各プレイヤーは有名人の名前が書かれた紙を受け取り、それを読まずに額に置きます。
その後、「はい」または「いいえ」でしか答えられない質問をして、自分の性格を推測するように努める必要があります。 一部のバリエーションには、オブジェクトと特定のスコアカウントシステムが含まれる場合があります。
また、モバイルアプリやウェブサイトを使用して、このゲームをより現代的な方法でプレイすることもできます。
このチュートリアルでは、アルゴリズムと学習戦略を使用して主題（目的語または人）を推測しようとする20の質問ゲームに焦点を当てます。
2. 歴史的背景
多くの古いものと同様に、このゲームの正確な作成日を定義または見つけることは困難です。 しかし、それが音声ゲームとして人気を博し、19世紀にニューイングランドで広まったことを私たちは知っています。
もともと、ゲームを始めるために使用された質問は、「それは動物、野菜、または鉱物ですか？」でした。 このゲームをとても有名にしたのは、ルール、スキルのシンプルさ、そして練習の必要がないことでした。 誰でもさまざまなレベルの専門知識で遊ぶことができます。
2.1. クイズショー
このゲームは、カナダ、ハンガリー、ノルウェーなどのさまざまな国のテレビやラジオで人気になりました。
ラジオでは、リスナーは主題の名前を送信していましたが、放送局は後でそれを推測しようとしました。
彼らがゲームに精通し、経験を積むにつれて、より少ない質問で可能な答えを絞り込む能力が毎回向上したことを強調する必要があります。 これは、プログラマーが後でアルゴリズムを使用して複製しようとした人間の行動です。
2.2. 人工知能アプローチ
1988年に、 Robin Burgener は、20の質問ゲームを実装するためのコンピューターアプローチに取り組み始めました。
このバージョンでは、コンピューターは、20のはいまたはいいえの質問の後で、プレーヤーが何を考えているかを推測しようとしました。 また、最初の推測が間違っていた場合に備えて、5つの追加の質問を使用することもできます。
著者は、彼の戦略のために特許を登録しました。これは、入力（質問への回答）と出力（ターゲットオブジェクト）を接続する重みを持つオブジェクトごとのマトリックスで構成されていました。 2番目のモードがありますが、簡単にするために、最初のアプローチに制限します。
次のステップでは、各回答に与えられた重みを考慮してオブジェクトがランク付けされます。
また、「通常」、「時々」、「たぶん」などの回答の選択肢が増える可能性があり、回答ごとにそれぞれの重みを割り当てることができます。
各ゲームをプレイした後に学習できるオンラインバージョンをプレイできるため、プレイヤーが1つの質問に誤って答えた後でも、正しく推測できます。
3. 理論的背景
ソフトウェアが答えを正しく推測する方法に飛び込む前に、この問題を解決するために最もよく使用される戦略の1つと、コンピュータサイエンスの他の多くの戦略の基本を理解する必要があります。決定木です。
パラメータを学習し、目的の目標を達成するために使用されるアプローチを考慮して、メソッドをパラメトリックまたはノンパラメトリックに分類できます。
パラメトリック推定では、入力空間全体を考慮してパラメーターを学習し、すべてのトレーニングデータを考慮してモデルを構築します。
一方、ノンパラメトリックアプローチでは、入力空間がより小さな領域に分割されます。 次に、各地域について、その地域のトレーニングデータのみを使用してローカルモデルが計算されます。
3.1. デシジョンツリー
デシジョンツリーは、分割統治戦略を使用するノンパラメトリック階層モデルです。 回帰と分類の両方に使用できます。
教師あり学習では、決定木を使用して領域に再帰分割を適用し、領域をより小さな領域に分割します。 このモデルには、決定ノードとターミナルリーフの2種類の要素があります。
実行された各決定には関数が含まれ、この関数の出力はブランチにラベルを付けます。 したがって、ルートノードから開始し、決定ノードを反復処理して、各ブランチに移動するかどうかを計算する必要があります。
リーフノードに到達するまで、これを再帰的に実行します。 リーフノードに到達すると、そのリーフに書き込まれた値が出力と見なされます。
正方形と円を含む架空のデータセットを検討すると、対応する決定木があります。このツリーでは、楕円形のノードが決定ノードであり、長方形が葉のノードです。
決定木をノンパラメトリックモデルと見なすためのもう1つの強力な議論は、ツリー構造やクラス密度は学習フェーズで定義され、問題の複雑さに依存するため、それらを推定しないという事実です。
3.2. 分類木
決定木に複数のラベルがある場合、それを分類ツリーと呼びます。すべてのブランチについて、すべての要素がブランチは同じクラスに適合します。
ノードがあることを考えると、はこのノードに到達する要素の数を表します。 クラスに属するその要素の1つです。 ノードでのクラスの確率を計算すると、次のようになります。
(1)
私たちがノードにいることを考えると、すべてが0または1に等しい場合、このノードは純粋であると見なされます。 したがって、すべての要素がクラスに属するか、いずれも属さないかのいずれかです。
このため、葉に達したので分割プロセスを停止する必要があります。 に等しいすべての要素は、ラベルを受け取る必要があります。
しかし、ノードが純粋であると見なされる要件を満たしていない場合、どのようにして不純物を分類できますか？ まず、情報理論におけるエントロピーの概念を理解する必要があります。
3.3. エントロピ
1986年にQuinlanが定義したのように、情報理論のエントロピーは、インスタンスのクラスコードをエンコードするために必要なビット数の測定値です。 この記事の冒頭から使用している表記法に従って、エントロピーを計算するための方程式を定義できます。
(2)
次の例では、問題に2つのクラスしかないことを前提としています。 最初のシナリオでは、とがあります。
この場合、すべてのインスタンスがに属しているため、エントロピーは0になります。 何も送信しないので、少しも必要ありません。
しかし、今、私たちが持っているとしましょう。 このシナリオでは、同じように発生する可能性が高いため、使用されているクラスを識別するために1ビットが必要です。
クラスが2に等しい場合のみを評価します。 それでも、クラス間で確率が等しい場合は、より複雑なアプリケーションに一般化できます。
(3)
この式を使用して、問題のあるすべてのクラスをエンコードするために必要なビット数を定義できます。
4. 例
前述の方法は高精度を達成できますが、20の質問の課題を解決するためにさまざまなアプローチを使用できます。
さまざまな戦略を組み合わせて、モデルの改善を試みることもできます。
4.1. 二十の質問ゲームの決定木
このシナリオでは、いくつかのオプションから正しいラベルを見つけようとしているため、分類ツリーがあります。
この場合、葉は私たちが推測しようとしているオブジェクトまたは人物になり、枝は1つの葉につながった特徴、つまり定義された質問への回答を表します。
デシジョンツリーの概念を理解するために、ゲームのより単純なバージョンを考えてみましょう。このバージョンでは、犬、猫、ニンジン、フォークの4つの答えしかありません。
100％の精度でゲームをプレイするには、いくつの質問が必要ですか？
質問を2つだけ慎重に選択すると、答えを正しく推測できます。
前の例は、2つの質問だけを使用して、4つの単語の中から単語を見つけることができるゲームの小さいバージョンの最適なソリューションを示しています。
セクション3.3で説明したことを考慮して、問題を数学的に定義しましょう。 単語の選択肢があれば、必要な質問の数を計算できます。
(4)
しかし、質問の数がわかれば、正しく推測できるさまざまな単語の数を定義できます。
(5)
したがって、20の質問ゲームでは、次のようになります。
(6)
たった20の質問で、100万を超えるさまざまな主題を特定でき、このアプリケーションに決定木を使用することの有効性を示しています。
この計算の最も重要な側面の1つは、4語の選択肢がある例に示されているように、回答を絞り込むことができる最適な質問のセットが必要であることを再度強調する必要があります。
この最適な質問のセットは、いくつかの学習戦略を使用することで達成できます。 理想的には、各質問は可能な答えを半分に分割し、主題を分離する主な特徴を見つけます。
したがって、プログラムがプレイされた各ゲームを記録し、どの質問が最良の結果をもたらすかを学習したことを考慮すると、学習ツリーは二分探索として機能します。
4.2. ランダムサンプルコンセンサス（RANSAC）
デシジョンツリーアプローチとともに、モデルに別の戦略を追加できます。 すべての質問ではなく、20の回答済み質問のサブセットをランダムに選択し、どの回答が出力として提供されるかを確認するRANSAC戦略を採用することで、間違った回答を排除できます。
異なるサブセットを使用してこれを数回行い、すべてのサブセットで答えが同じであるかどうかを確認します。
これは、RANSACが外れ値の検出方法であり、間違った答えが最終出力での影響を減らすため、プレーヤーからの間違った答えが結果に影響を与えるのを防ぐのに役立ちます。
5. 結論
この記事では、決定木と呼ばれるノンパラメトリックモデルを使用して20の質問ゲームを実装する方法について説明しました。
この構造により、多くの回帰および分類の問題を解決できます。 また、質問の数に応じて到達できるクラスの数を予測する方法と、戦略を組み合わせてより高い精度を達成する方法を数学的に証明しました。
