作成中のゲームに問題があります。解決策 (または適用する解決策) はわかっていると思いますが、すべての「ピース」がどのように組み合わさるのかがよくわかりません。
ゲームの仕組み:
（から数字推測ゲーム（ひねりを加えた）アルゴリズムにどのようにアプローチしますか?）
ユーザーには価値を持ったアイテムが与えられます（価値は毎日変化し、プログラムは価格の変化を認識します）。例えば
Apple = 1
Pears = 2
Oranges = 3
次に、好きな組み合わせ (リンゴ 100 個、ナシ 20 個、オレンジ 1 個など) を選択する機会が与えられます。コンピューターが取得する唯一の出力は合計値です (この例では、現在 143 ドル)。コンピューターは、プレーヤーが何を持っているかを推測しようとします。当然、最初のターンでは正しく推測することはできません。
Value quantity(day1) value(day1)
Apple 1 100 100
Pears 2 20 40
Orange 3 1 3
Total 121 143
次のターンでは、ユーザーは数字を変更できますが、合計数量の 5% 以内です (または、選択した他のパーセンテージ。ここでは 5% を使用します)。果物の価格は (ランダムに) 変わる可能性があるため、合計値もそれに応じて変わる可能性があります (わかりやすくするために、この例では果物の価格は変更していません)。上記の例を使用すると、ゲームの 2 日目にユーザーは 152 ドルの値を返しますが、3 日目に 164 ドルを返します。次に例を示します。
quantity(day2) %change(day2) value(day2) quantity(day3) %change(day3) value(day3)
104 104 106 106
21 42 23 46
2 6 4 12
127 4.96% 152 133 4.72% 164
*(テーブルが正しく表示されることを願っています。手動で間隔を空ける必要があったので、画面上でだけ発生しているわけではないことを願っています。うまくいかない場合はお知らせください。スクリーンショットをアップロードしてみます)。
時間の経過とともに数量がどうなるかを把握できるかどうかを確認しようとしています (ユーザーが数値を入力し続ける忍耐力があると仮定)。現時点でわかっている唯一の制限は、合計値が 5% を超えてはならないため、現時点では 5% 以内の精度を維持できず、ユーザーは永遠に入力し続けることになります。
これまでに行ったこと:
私は与えられたフルーツの値とフルーツバスケットの合計値をすべて取得し、すべての可能性を示す大きな表を作成しました。すべての可能性のリストができたら、グラフ理論を使用して、考えられる各ソリューションのノードを作成しました。次に、5% 以内の変化であれば、各日のノード間 (たとえば、day1 から day2) にエッジ (リンク) を作成します。次に、エッジ (他のノードへのリンク) のないすべてのノードを削除します。ユーザーがプレイを続けると、パスが行き止まりになったときにパス全体も削除します。これは選択肢を絞り込むので素晴らしいのですが、選択肢をさらに絞り込みたいので行き詰まっています。これは隠れマルコフ問題だが、状態が変化する (上記のように、新しいノードが毎ターン追加され、古い/可能性の低いノードが削除されている) ため、よりトリッキーなバージョンであると聞きました。
** 役に立つなら、Baum-Welch モデル (データのトレーニングに使用) の Python 実装に関する素晴らしい回答 (サンプル コード付き) をここで入手しました:Baum-Welchの実装例**
私が考える必要があること（間違っている可能性があります）:
結果を絞り込んだので、基本的には、絞り込んだ結果ベースに基づいてプログラムが正しいものを予測できるようにしようとしています。これは不可能だと思っていましたが、隠れマルコフモデルで解決できると示唆する人が何人かいます。確率が安定するまで (ユーザーがターンを重ねるごとに改善されるはずです)、データに対して複数の反復処理 (Baum-Welch モデルを使用) を実行できると思います。隠れマルコフモデルは、スペルや手書きをチェックし、エラーが発生するたびに改善することができます (この場合のエラーとは、次のターンで削除されるバスケットをあり得ないものとして選択することです)。
2つの質問:
すべての状態が最初は等しい場合、遷移行列と放出行列をどのように計算すればよいでしょうか? たとえば、すべての状態が等しく発生する可能性があるので、状態が変化する確率を専用にするために何かを使用する必要があります。遷移/放出状態の計算の一部として、エッジの数が最も多いノードに重みを付けるために作成したグラフを使用することを考えていました。これは理にかなっていますか、それとももっと良い方法がありますか?
状態のすべての変更を追跡するにはどうすればよいでしょうか。新しいバスケットが追加され、古いバスケットが削除されると、バスケットを追跡するという問題が発生します。階層的ディリクレ過程隠れマルコフモデル (hdp-hmm) が必要なものだと考えましたが、それをどのように適用すればよいかよくわかりません。
(少しイライラしているように聞こえたらごめんなさい。問題は解決可能であることはわかっていても、何をする必要があるかを概念的に把握できないのは少し難しいです)。
いつものように、お時間をいただきありがとうございます。アドバイスや提案があれば、ぜひお聞かせください。
ベストアンサー1
あなたが言ったように、この問題は HMM で説明できます。基本的に、各時点での真の量となる潜在的または隠れた状態の分布を維持することに関心があります。ただし、既知の HMM で単純に推論を行うのではなく、HMM のパラメータを学習するという問題を混同しているようです。後者の問題がありますが、前者を実行するように設計されたソリューション (Baum-Welch) を採用することを提案しています。つまり、モデルはすでにあるので、それを使用するだけです。
興味深いことに、あなたの問題に対して離散HMMをコーディングすると、グラフ理論のソリューションで説明したものと非常によく似たアルゴリズムが得られます。大きな違いは、あなたのソリューションが何を追跡しているかということです。可能一方、正しい推論アルゴリズムは、ビタビアルゴリズム、何を追跡しますかおそらくドメインに 5% の範囲で重複がある場合、つまり、複数の可能な状態が同じ状態に遷移する可能性がある場合には、違いは明らかです。アルゴリズムによってポイントに 2 つのエッジが追加される場合もありますが、翌日の計算時にそれが影響するかどうかは疑問です (基本的に 2 回カウントされるはずです)。
とにかく、Viterbi アルゴリズムを使用できます。最新の日付での最良の推測のみに関心がある場合は、グラフ理論ソリューションを変更する方法について簡単に説明します。状態間のエッジを維持する代わりに、状態が正しい確率を表す分数を維持します (この分布は、信念状態と呼ばれることがあります)。新しい日ごとに、各バケットをその親の確率で増分することで、信念状態を前方に伝播します (エッジを追加する代わりに、浮動小数点数を追加します)。信念状態が適切に正規化されている (合計が 1 になる) ことも確認する必要があるため、各更新後にその合計で除算するだけです。その後、各状態を観測値によって重み付けできますが、ノイズの多い観測値がないため、すべてのあり得ない状態の確率を 0 に設定してから、再度正規化できます。これで、観測値に基づいて条件付けされた基礎となる量の分布が得られます。
ここでは、概要を伝えるために、統計的な詳細の多くを省略しています。
編集（質問について）：あなたの質問に対する答えは、あなたが何を望んでいるかによって異なります。最近の日ならば、私が説明したようなワンパスアルゴリズムで済ませることができます。しかし、もし正しい分布を毎日後方へのパスも行う必要があります。そのため、前方後方アルゴリズム. 1 ステップ戻ってエッジを削除しようとしているということは、おそらくすべての日の分布が必要なのではないかと思います (当初の想定とは異なります)。もちろん、いわば「未来が過去に情報を提供できる」ように使用できる情報があることに気付いたと思いますが、これがまさに、逆方向パスも実行する必要がある理由です。それほど複雑ではなく、チェーンの最後からまったく同じアルゴリズムを実行するだけです。概要については、videolectures.net の Christopher Bishop の 6 部構成のチュートリアルをご覧ください。
エッジの追加/削除について言及したので、前に説明したアルゴリズムを明確にしておきます。これは単一のフォワードパス用であることに留意してください。数量の可能な順列が合計N個あるとすると、信念状態は次のようになります。まばらなベクトル N 要素長 (v_0 と呼ばれます)。最初のステップでは、合計の観測値を受け取り、すべての可能な値の確率を 1.0 に設定してベクトルを入力し、再度正規化します。次のステップでは、すべて 0 の新しいスパース ベクトル (v_1) を作成し、v_0 のゼロ以外のすべてのエントリを反復処理して、5% 以内の v_1 のすべてのエントリを (v_0 の確率で) 増分します。次に、新しい観測値に従って可能ではない v_1 のすべてのエントリをゼロにして、v_1 を再度正規化し、v_0 を破棄します。これを永遠に繰り返します。v_1 は常に可能性の正しい分布になります。
ちなみに、ノイズの多い観測や非常に大きな状態、連続状態がある場合、状況はこれよりはるかに複雑になる可能性があります。このため、統計的推論に関する文献の一部を読むのはかなり難しく、かなり一般的な内容になっています。