20の質問AIアルゴリズムはどのように機能しますか？

Question

eerily正確なAIによって強化された20の質問の簡単なオンラインゲーム。

彼らはどのようにうまくいくと思いますか？

Answer 1

バイナリ検索アルゴリズムと考えることができます。 各繰り返しで、私たちは質問をします。これにより、可能な単語の選択肢のおよそ半分が削除されるはずです。 N個の単語の合計があれば、log2（N）個の質問の後に答えを得ることができる。

20の質問では、2^20 = 100万語の単語を最適に見つけることができます。

アウトライア（間違った回答）を排除する簡単な方法は、おそらくRANSACのようなものを使用することです。これは、答えられたすべての質問を考慮するのではなく、ランダムに小さなサブセットを選ぶということです。これはあなたに1つの答えを与えるのに十分です。今度は、あなたがその時間のほとんどを見るまで、あなたは同じ結果を得ています。あなたは正しい答えがあることを知っています。

もちろん、これはこの問題を解決する多くの方法の単なる1つの方法です。

Answer 2

学習アルゴリズムを使用しています。

k-NNは、これらの1つの良い例です。

Wikipedia: k-Nearest Neighbor Algorithm

Answer 3

私はここでゲームについて読んでお勧めします。特にhttp://en.wikipedia.org/wiki/Twenty_Questions

コンピュータ]セクション：

ゲームは（シャノンのエントロピー 統計によって測定されるような）情報 ことを示唆しています 任意のオブジェクトを識別するために必要な値は約20ビットです。 教えている人の情報 の理論については、 ゲームが例としてよく使われます。数学的には、各 の質問が のオブジェクトの半分を排除するように構成されている場合、20の質問 は、 を2 または1,048,576件の間で区別することができます。 従って、20の質問のための最も有効な 戦略は、 残りの可能性フィールド のフィールドを約半分に分割する質問をすることです。プロセス は、コンピュータサイエンスのバイナリ検索 アルゴリズムに類似しています。

Answer 4

決定木は、この種のアプリケーションを直接サポートします。意思決定木は人工知能でよく使用されます。

決定木は、左右の子で表されるコレクションを区別するために、各ブランチで「最高の」質問をするバイナリツリーです。最良の質問は、20の質問アプリケーションの作成者がツリーを構築するために使用する学習アルゴリズムによって決まります。それから、他のポスターが指摘するように、深さ20レベルの樹木はあなたに何百万ものものを与えます。

各ポイントで「最高の」質問を定義する簡単な方法は、コレクションを最も均等に半分に分割するプロパティを探すことです。そうすることで、その質問にイエス/ノーの回答が得られたら、各ステップで約半分のコレクションを取り除くことができます。この方法でバイナリ検索を近似することができます。

http://en.wikipedia.org/wiki/Decision_tree_learning

そして、いくつかの一般的な背景：

http://en.wikipedia.org/wiki/Decision_tree

Answer 5

それは、 "インターネット上のニューラルネット" としての地位を請求すると、そこに嘘

ウィキペディアは、より完全な例を示しますキー。質問/回答確率を予備の行列に格納する可能性が高い。これらの確率を使用して、決定木アルゴリズムを使用して、次の質問を絞り込むためにどの質問を求めるかを推論することができます。可能な回答の数を数十に減らすか、すでに20の質問に達している場合は、最も可能性の高い回答を読み始めます。

20q.netの本当に興味深い面は、私が知っているほとんどの意思決定ツリーおよびニューラルネットワークのアルゴリズムとは異なり、20qが疎な行列と増分更新をサポートしていることです。

編集：答えはネット上でこの時間全体になっています。発明者のRobin Burgenerは、彼のアルゴリズムを彼の2005 patent filingで詳しく説明しました。