機能要件
最初のステップは、「機能が似ているプログラム」という言葉が実際に何を意味するかを理解することです。 少し考えた後、次の要件を強調しました。
- プログラムをトレーニングする必要があります。 プログラムに数十万個の文字を認識させるように教えることはできないことは明らかです。 理論的にはこれは可能ですが、より美しいソリューションを探します。 このアプローチの明らかな代替手段は、ユーザーの応答を使用して外出先で学習することです。 これは私たちのプログラムができる必要があります。
- プログラムは間違いを許すべきです。 明らかに、いくつかの質問への回答に関するユーザーの意見は大きく異なります。 簡単な例：必死の同性愛嫌悪者と単純な男がブラッドピットを作ります。 「あなたのキャラクターはセクシーですか？」という質問に対して、前者は否定的に答える可能性が高く、ほとんどの人はそうしません。 ただし、このわずかな不一致は、プログラムが真実を見つけるのを妨げるものではありません。
- プログラムは賢明に質問を選択する必要があります。 尋ねる質問を決定する多くの戦略があります。 たとえば、すべての質問をすることができます（それだけです）。 ランダムな質問をすることはできますが、その場合でも、答えは非常に長い時間をかけなければなりません。 そして、答えるときにできるだけ多くの情報を見つけるために、次の質問を選択することができます。 それが私たちがやろうとしていることです。
アルゴリズム
間違いを許さなかったなら、望んでいたことを達成するのは非常に簡単です。 たとえば、内部頂点が質問に対応し、シートが回答に対応する質問に対する回答のツリーを保存することが可能です。 ゲームのプロセスは、ルートからシートの1つへの下降のように見えます。 ただし、このアルゴリズムはエラーの許しに対処しません。 はい、ツリーバランシングの問題が発生します。
ある意味で、ツリーは非常に「機械的」、「機械的」なプレイ方法であり、わずかな不正確さに対して非常に不安定です。 しかし、合理的な人がプレイするようにプレイする必要があります。 確率論に多少なりとも精通している人は、それがいわゆるベイジアン解釈とそれに基づくベイジアンアプローチを持っていることを知っているべきです。 このアプローチの基礎は、確率変数の分布を使用した知識の記述であり、その後、有名なベイズ公式を使用した観測に基づいて、事前知識から事後知識に変換されます。 さらに、このアプローチは、不確実性の場合に対する論理の古典代数の唯一の一般化です（これは、たとえばここで読むことができます ）。 これは多くの科学者をベイジアンアプローチが合理的思考の標準であるという考えに導きます。 まあ、これだけが必要です。 それをタスクに適用してみましょう。
ベイジアンモデル
したがって、ベイズの公式を思い出してください：P（A | B）= P（B | A）P（A）/ P（B）。 そして今、言葉で。 イベントBが正確に発生したという条件で、イベントAが発生した確率を評価する必要があると仮定します（つまり、それを観察することが保証されています。そのため、Bはしばしば観察と呼ばれます）。 ベイズの公式によれば、この確率は他の2つの積に比例します。 それらの最初のP（B | A）は尤度と呼ばれ、Aが発生した場合にイベントBが発生する確率を示します。2番目の因子P（A）は、イベントAのいわゆる先験的確率 、つまり確率です。原則として（Bに関係なく）発生すること。 実際、この確率は、何が起こったのかを知る前にAについて知っていた情報を反映しています。式の分母には値P（B）も含まれていますが、この場合、これは単に正規化係数の役割を果たし、無視できます。
質問のゲームのコンテキストでこの式を使用するのは非常に簡単です。 Aiが「あなたがオブジェクトiを推測した」という形式のイベントであると仮定しましょう。ここで、iはSpockまたはVirgin Maryのいずれかです。 BはAiについての観測であるため、Bが質問への回答で構成されていると仮定するのは自然です。 ここに表示される唯一のオプションは、共同イベントの形式でBを提示することです。「Answer A1、...が質問Q1に回答され、Akが質問Qkに回答されました。」 次に、P（Ai | B）は、オブジェクトiについて、自分が作成された確率を示します（ユーザーがk個の質問に答えたという事実を考慮して）。 これはまさに私たちが興味を持っている価値です。 P（Ai | B）の最大値を持つオブジェクトを選択すると、P（Ai | B）の値が十分に大きい場合、それを推測として使用することができます。
先験的確率P（Ai）は、k = 0の場合のP（Ai | B）の特殊なケースと見なすことができます。 言い換えれば、質問が行われておらず、何もわからないという条件で、プレーヤーがオブジェクトiを作成した確率です。 一方では、すべてのオブジェクトにP（Ai）を等しくすることが可能です。 それは正直です。 一方、バラク・オバマはおそらくホールデン・コールフィールドよりもはるかに頻繁に推測されるでしょう。 したがって、ceteris paribus （つまり、オブジェクトを区別できない場合）、Obamaを選択する必要があります。 したがって、P（Ai）の自然な推定値は、Xが作成されたときのゲーム数とそれらの合計数の比率になります。
P（B | Ai）の尤度も便利な解釈になります。 最初に、1つの小さなトリックを使用する必要があります-条件Aiの質問に対する回答の条件付き独立性を仮定するため（多少粗雑ですが、非常に便利な単純化）。 ロシア語に翻訳すると、これは、仮定により、確率P（B | Ai）は確率P（Bj | Ai）の積（jによる）として記述できることを意味します。 この場合のP（Bj | Ai）は、非表示オブジェクトiで質問AjがAjによって回答された回数と、非表示オブジェクトiで質問Qjが質問された回数の比率になります。 ゼロおよび不確実な確率を避けるために、最初に、各質問に対して、各回答オプションが一度与えられたことをさらに考慮することを提案します。 つまり、質問Qjがオブジェクトiについて一度も質問されていない場合、P（Bj | Ai）は1 / Njに等しくなります。ここで、Njは質問Qj（私は、同じものを使用し、同じ4つの可能な答え：「はい」、「いいえ」、「わからない」、「質問は意味がありません」）。
小計を要約します。 質問/回答のペアのセットと、質問に対するこれらの回答でこのエンティティが構成されている可能性のあるエンティティを表示する簡単な式を見つけました。 新しい質問に答えた後、データベース内のすべてのオブジェクトについてこの確率を再計算すると、現時点でどのオブジェクトが隠しオブジェクトに似ているかを確認できます。 さらに、モデルのトレーニングは非常に簡単に実装されます。データベースに関する各エンティティの情報を保存する必要があります。それは、そのモデルに関する質問の種類と、各タイプのユーザーからの回答の数です。 各ゲームの後、この情報はユーザーの応答に基づいて更新できます。 また、データベース内の人の「人気」を考慮するには、その人が構成された回数を保存する必要があります。
質問、情報、エントロピーの選択
さて、残っているのは質問するのが最善の質問を理解することです。 当然、より多くの情報を提供する質問をする必要があります。 しかし、どういうわけかこの情報を測定できますか？ はい、そうです。 これを行うには、 情報エントロピーの概念を使用できます。 大まかに言えば、理解できることですが、情報エントロピーは、ランダム変数の分布の特性です（ビット単位の情報のように測定されます）。これは、このランダム変数がどのような値を取るか確信が持てないことを示しています。 たとえば、確率変数が0.99の確率で1の値を取り、0.01の確率で0の値をとる場合、そのような分布のエントロピーはゼロに非常に近くなります。 たとえば、確率変数が値0.5と等しい確率で値0と1をとる場合（頭または尾）、そのような確率変数のエントロピーは1ビットに等しくなります（これは正確に不確実性を排除するために取得する必要がある情報の量です）。
さて、毎回質問を選択しましょう。その答えは、分布P（Ai | B）のエントロピーを減少させます。これは、プレイヤーが誰を構成したかを正確に把握する責任があります。 ここで、別の問題がすぐに発生します。一般的に言えば、同じ質問に対する異なる答えは、異なる方法でエントロピーを減らすことができます。 どうする？ エントロピーの予想される減少が最大になる質問を見つけることが提案されています。 予想されるエントロピーの減少は、質問をすると「平均」エントロピーがどれだけ減少するかを示しています。 ここでテキストの段落をさらに記述しないために、この値を計算できる式を示します。 希望する人は、なぜそれがそのように見えるのか簡単に理解できます。 そのため、量H [P（Ai | B、<Qj、Yes>）] P（<Qj、Yes>）+ ... + H [P（Ai | B、<Qj、 No>）] P（<Qj、No>）は最小です。 ここで、H [P]は確率分布Pのエントロピーを示し、「<Qj、Ans>」を通じてイベント「Ansは質問Qjに回答します」を示します。 P（<Qj、Ans>）の値は、すべての既知のオブジェクトにより、 合計確率の式によって簡単に見つけることができます。 つまり、P（<Qj、Ans>）= sum（i）P（<Qj、Ans> | Ai）P（Ai | B）です。
このアプローチにより、最も重要なことに焦点を当てて、無関係な問題を非常に迅速に破棄できることがわかります。 ある意味では、この方法は確率的設定における「半分」の方法の一般化です。 以下のビデオで、それらがどのように連携するかを見ることができます。
まとめ
この短い記事の情報が皆さんにとって興味深いものになったことを願っています。 実際、まず第一に、この記事では、形式化が不十分な問題を解決する際の（最も単純ではあるが）数学の力に注意を向けるべきです。 あなたのプログラムで確率論と情報理論にベイズのアプローチを使用すると、それらをより合理的にすることができますが、同時により人道的になります:)