問題タブ [markov]

プログラミング演習として、単語の連鎖に対して任意の長さのマルコフジェネレーターを作成しようとしていますが、修正できないバグを見つけました。マルコフ関数を実行すると、リストインデックスが範囲外になります。

当たり前のことを見落としているような気がしますが、何なのかわかりません。トレースバックは、エラーが41行目にあることを示していwords[-1] = nextWords[random.randint(0, len(nextWords)-1)]ます。

完全なコードは以下のとおりです。インデントが台無しになっている場合は申し訳ありません。

私は鳥の動きの500の観察のシーケンスを持っています。鳥の501番目の動きがどうなるかを予測したいと思います。私はウェブを検索しましたが、これはHMMを使用して実行できると思いますが、そのテーマについての経験はありません。この問題を解決するために使用されるアルゴリズムの手順を誰かが説明できますか？

Rで単純な一次マルコフ連鎖を行いたい。MCMCのようなパッケージがあることは知っているが、それをグラフィカルに表示するパッケージが見つからなかった。これも可能ですか？遷移行列と初期状態が与えられれば、マルコフ連鎖を通る経路を視覚的に見ることができれば素晴らしいでしょう（多分私はこれを手でやらなければなりません...）。

ありがとう。

最近、マルコフ決定プロセス (値の反復を使用)についてよく読んでいますが、それらについて理解することはできません。インターネットや書籍で多くのリソースを見つけましたが、それらはすべて、私の能力には複雑すぎる数式を使用しています。

これは大学での最初の年であるため、Web で提供されている説明や数式は、私には複雑すぎる概念や用語を使用しており、読者が私が聞いたことのない特定のことを知っていると想定していることがわかりました。 .

2Dグリッドで使用したい（壁（達成不可能）、コイン（望ましい）、動く敵（これは絶対に避けなければならない）でいっぱい）。全体的な目標は、敵に触れずにすべてのコインを集めることです。マルコフ決定プロセス ( MDP )を使用して、メイン プレイヤー用の AI を作成したいと考えています。これは部分的にどのように見えるかです (ゲーム関連の側面はここではそれほど重要ではないことに注意してください. MDPの一般的な理解を本当に望んでいます):

私が理解していることから、MDP の無礼な単純化は、MDPが、進む必要がある方向を保持するグリッドを作成できることです (グリッド上の特定の位置から開始して、進む必要がある場所を指す「矢印」のグリッドのようなものです)。 ) 特定の目標を達成し、特定の障害物を回避します。私の状況に特有のことですが、それは、プレイヤーがコインを集めて敵を避けるためにどの方向に行くべきかを知ることができることを意味します.

ここで、MDP用語を使用すると、特定の状態 (グリッド上の位置) に対して特定のポリシー (実行するアクション -> 上、下、右、左) を保持する状態のコレクション (グリッド) を作成することを意味します。 ）。ポリシーは、各状態の「効用」値によって決定されます。この値自体は、そこに到達することが短期的および長期的にどれだけ有益であるかを評価することによって計算されます。

これは正しいです？それとも、私は完全に間違った方向に進んでいますか?

少なくとも、次の式の変数が私の状況で何を表しているか知りたいです。

(Russell & Norvig の本「Artificial Intelligence - A Modern Approach」から引用)

sグリッドからのすべての正方形のリストであり、特定のアクション (上/下/右/左) になることはわかっていaますが、残りはどうですか?

報酬関数と効用関数はどのように実装されますか?

ここからどこから始めればよいかさえわからないので、私の状況に似た基本的なバージョンを非常に遅い方法で実装するための疑似コードを示す簡単なリンクを誰かが知っていれば、本当に素晴らしいことです。

貴重な時間をありがとうございました。

（注：タグを追加/削除するか、何かまたはそのようなものについて詳細を提供する必要がある場合は、コメントで教えてください。）

マルコフ クラスタリング アルゴリズムの詳細については、次の例を参照してください。

http://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf

アルゴリズムを正確に表現したように感じますが、少なくともこのガイドがその入力に対して得ていたのと同じ結果が得られていません.

現在のコードは http://jsfiddle.net/methodin/CtGJ9/にあります。

小さな事実を見逃したのか、それともどこかで微調整が必​​要なだけなのかはわかりませんが、次のようないくつかのバリエーションを試しました。

1. インフレ/膨張のスワップ
2. 精度に基づく等価性のチェック
3. 正規化の削除 (元のガイドでは必要なかったが、MCL の公式ドキュメントにはすべてのパスで行列を正規化するように記載されているため)

これらはすべて同じ結果を返しました - ノードはそれ自体に影響を与えるだけです。

VB でも同様のアルゴリズムの実装を見つけました: http://mcl.codeplex.com/SourceControl/changeset/changes/17748#MCL%2fMCL%2fMatrix.vb

そして、私のコードは、番号付けを除いて一致しているようです（たとえば、600 - 距離）。

これが拡張機能です

これがインフレ関数です

そして最後にメインのパススルー機能

グリッドの世界（エージェントムービーの左、右、上、下）で最適なポリシー（強化学習-マルコフ決定過程）を計算する必要があるタスクがあります。

左の表には、最適値（V *）があります。右の表には、その「最適なポリシー」の公式を使用して取得する方法がわからない解決策（方向）があります。Y = 0.9（割引係数）

そしてここに式があります：

したがって、誰かがその式の使用方法を知っている場合は、解決策（これらの矢印）を取得するために、助けてください。

編集：このページには問題の説明全体があります： http ： //webdocs.cs.ualberta.ca/~sutton/book/ebook/node35.html報酬：状態A（列2、行1）の後に次の報酬が続きます+10で状態A'に遷移し、状態B（列4、行1）の後に+5の報酬が続き、状態B'に遷移します。あなたは動くことができます：上、下、左、右。グリッドの外に移動したり、同じ場所に留まったりすることはできません。

次の特徴を持つ Python で反復マルコフ決定プロセス (MDP)エージェントを考案しようとしています。

• 観測可能な状態
  • DPによって行われたクエリタイプの移動に応答するための状態空間を予約することにより、潜在的な「不明」状態を処理します（t + 1の状態は、前のクエリを識別します[または前の移動がクエリではなかった場合はゼロ]および埋め込み結果ベクトル) このスペースは固定長になるまで 0 でパディングされ、クエリの応答 (データ長は異なる場合があります) に関係なく状態フレームを整列させます。
• すべての状態で常に利用できるとは限らないアクション
• 報酬関数は時間の経過とともに変化する可能性があります
• ポリシーの収束は段階的であり、移動ごとにのみ計算される必要があります

したがって、基本的な考え方は、MDP が現在の確率モデルを使用して T で最善の推定最適化された移動を行う必要があるということです (そして、その移動は確率論的であるため、可能性のあるランダム性を意味する確率的であることが予想されます)、T+1 での新しい入力状態を報酬と結合します。 T での前の動きからモデルを再評価します。報酬が調整されたり、利用可能なアクションが変更されたりする可能性があるため、収束は永続的であってはなりません。

私が知りたいのは、この種のことをすでに実行できる（または適切なカスタマイズでサポートする可能性がある）現在のPythonライブラリ（WindozeとLinuxの間で環境を変更する必要があるため、できればクロスプラットフォーム）があるかどうかです。 say 報酬メソッドを独自のもので再定義できるようにするサポート)。

オンラインの移動ごとの MDP 学習に関する情報はかなり不足しています。私が見つけることができる MDP のほとんどの使用は、ポリシー全体を前処理ステップとして解決することに重点を置いているようです。

次のパラメータが与えられます。

• λ = (A、B、π)。
• A = 状態遷移行列
• A = { a[i][j] } = { P(t での状態 q[i] | t+1 での状態 q[j]) },
• B = 観測行列と
• π = 初期分布。

下の文は正しいですか？(λ と A の関係を明確にする):

a[i][j] = P(t での状態 q[i] | t+1 での状態 q[j]) =P(t での状態 q[i] | t+1 での状態 q[j]、λ )

助けてください！

そこで、楽しみのために、約 75 文字の暗号文と、メッセージが 3 文字 (私の先生のイニシャル) で署名されたベビーベッドが与えられた、以前の大学の課題を再訪することにしました。

私がやったこと：

1. ベビーベッドの一部またはすべてが含まれているものに結果を絞り込みました.
2. 次に、(1) の結果の小さなサブセットに対して文字頻度分析を開始しました。

ここでのタスクは、いくつかの言語認識ソフトウェアを作成することになりますが、最初に対処する必要のある問題がいくつかあります。すべてのローター設定 (タイプ、初期位置) をブルート フォースすることを選択したので、ベビーベッドの一部またはすべてを含む結果のエントリには、プラグボードから交換された文字がまだいくつかあります。

私の次の動きは、2 つの行列を作成し、コーパスをダイジェストすることであることを知っています。最初の行列では、集計を行うだけです。最初の文字が A の場合、最初の行列では、行 0 になり、増加する列は、A の直後の文字であり、B であるとします。次に、B に移動し、次の文字が U であることを確認します。そのため、行 B に移動して列 U のエントリを増やします。コーパス全体を消化した後、確率を 2 番目の行列に入れます。

2 番目のマトリックスを使用して、スコア値をセンテンス全体に割り当て、出力をスコアリングして結果をさらに絞り込む手段を手に入れることができたので、メッセージを見つけることは、非常に小さな干し草の山からピンを見つけるのと同じくらい簡単なはずです。

今、私はPythonでこれを行っています.charをintにキャストする方が良いかどうか、最小のchar 'A'を減算してからそれをインデックスとして使用する方が良いかどうか、またはdictとeveryを使用する必要があるかどうかを知りたいと思いました.文字は int 値に対応するため、マトリックス内の位置のインデックスを見つけると、次のようになりますLetterTally[dict['A']][dict['B']]。

キャスト減算メソッドは次のようになります。

これら 2 つの異なる方法のうち、どちらが高速でしょうか?

マルコフ方程式の観点から情報エントロピーについて考えてきました。

H = -SUM(p(i)lg(p(i))、ここで、lg は 2 を底とする対数です。

これは、すべての選択 i の確率が等しいと仮定しています。しかし、与えられた選択肢のセットの確率が等しくない場合はどうなるでしょうか? たとえば、StackExchange に 20 のサイトがあり、ユーザーが StackOverflow 以外の StackExchange サイトにアクセスする確率が p(i) であるとします。しかし、ユーザーが StackExchange にアクセスする確率は p(i) の 5 倍です。

この場合マルコフ方程式は成り立たないのでしょうか? それとも、私が気付いていない高度なマルコフのバリエーションがありますか?