問題タブ [montecarlo]

次のプロパティを持つデータ構造が必要になることがよくあります。

• O(n) の n 個のオブジェクトの配列で初期化できます。
• O（1）でランダムな要素を取得できます。この操作の後、選択された要素は構造から削除されます。(交換なし)
• O(p) で p 個の「置換なしの選択」操作を元に戻すことができます
• O(log(n)) の構造から特定のオブジェクトを (たとえば id で) 削除できます。
• 現在構造体にあるオブジェクトの配列を O(n) で取得できます。

他のアクション (挿入など) の複雑さ (または可能性) は問題ではありません。複雑さに加えて、n の数が少ない場合にも効率的である必要があります。

そのような構造を実装するためのガイドラインを誰か教えてもらえますか? 私は現在、上記のすべてのプロパティを持つ構造を実装していますが、要素の選択は過去の選択回数 d で O(d) を取ります (「まだ選択されていない」かどうかを明示的にチェックするため)。O(1) でのピッキングを可能にする構造を理解することはできますが、これらは他の操作の少なくとも 1 つでより複雑です。

ところで: 上記の O(1) は、複雑さが以前に選択された要素とは無関係であり、合計の要素とは無関係であることを意味することに注意してください。

*モンテカルロ アルゴリズム (n 個の要素の「セット」から p 個のランダムな要素を繰り返し選択する)。

time はシード空間のサイズを効果的に縮小するため、乱数生成のシードとして安全ではないことを理解しています。

しかし、私はセキュリティを気にしないと言います。たとえば、カード ゲームのモンテカルロ シミュレーションを行っているとします。ただし、可能な限り真のランダム性に近づけることに気を配っています。シードとしての時間は出力のランダム性に影響しますか? この場合、PRNG の選択はシードよりも重要だと思います。

XML データから自分のデータを辞書形式に整理しようとしています。これは、モンテカルロ シミュレーションの実行に使用されます。

XML のいくつかのエントリがどのように見えるかの例を次に示します。

私の現在のデータセットには 2 つの変数しかなく、型は 3 つのうちの 1 つまたは可能な 4 つの離散型にすることができます。2 つの変数をハード コーディングすることは問題ではありませんが、より多くの変数を持つデータの処理を開始し、このプロセスを自動化したいと考えています。私の目標は、この XML データをディクショナリに自動的にインポートして、配列のタイトルと変数をハードコーディングすることなく、後でさらに操作できるようにすることです。

ここに私が持っているものがあります:

KeyError @ thisList = masterDictionary[thisKey] を取得しています

また、xml の他の要素を処理するクラスを作成しようとしています。

次に、次のような値で値を確認できますか?

ありとあらゆる助けをいただければ幸いです

アップデート

助けてくれてありがとうジョン。インデントの問題は私のずさんさです。スタックに投稿するのは初めてで、コピー/貼り付けがうまくいきませんでした。else: の後の部分は、実際には for ループの一部になるようにインデントされており、コードではクラスが 4 つのスペースでインデントされています。大文字の規則を念頭に置いておきます。あなたの提案は実際に機能し、コマンドを使用するようになりました：

収量:

これらは実際に私の 2 つの変数であり、値は上部にリストされている xml と同期します。

更新 2

さて、私はこれを理解したと思っていましたが、再び不注意でした.問題を完全に修正していなかったことが判明しました. 前のソリューションでは、すべてのデータを 2 つのディクショナリ キーに書き込むことになり、2 つの異なるディクショナリ キーに割り当てられたすべてのデータの 2 つの等しいリストが作成されました。アイデアは、XML から一致する辞書キーに個別のデータ セットを割り当てることです。現在のコードは次のとおりです。

入力すると：

結果は両方のキー ('stock' と 'inflation') で同じです。

XML ファイルには、stock タグが付けられた 27 個のアイテムと、inflation でタグ付けされた 29 個のアイテムがあります。辞書キーに割り当てられた各リストをループ内の特定のデータのみをプルするにはどうすればよいですか?

更新 3

2 つのループで動作するようですが、1 つのループで動作しない理由と方法がわかりません。私はこれを誤って管理しました：

1回のループでそれを実現するために多数の順列を試しましたが、うまくいきませんでした。両方のキーにリストされているすべてのデータを取得できます-すべてのデータの同一の配列(あまり役に立ちません)、またはデータは両方のキーの2つの異なる配列に正しくソートされますが、最後の単一のデータエントリのみです(ループはそれ自体を上書きします)毎回、配列内のエントリは 1 つだけになります)。

誰かが次のことを行うための最良の方法をアドバイスしてもらえますか?

3 つの変数 (X、Y、Z) と 4 つのグループ (1、2、3、4) が​​あります。私は SPSS で判別関数分析を使用して、既知のグループ化されたデータのグループ メンバーシップを予測し、将来のグループ化されていないデータで使用しています。

理想的には、データのサブセットの数を増やしてランダムにサンプリングし、目的の正しい分類パーセンテージに到達するために必要な観測数を確認できるようにしたいと考えています。

ただし、これが難しい場合があることは理解しています。したがって、私は手段のためにこれを行うことを検討しています。

たとえば、変数 X のグループ 1 の平均が 141 であるとします。この平均は、2000 の観測値から計算された可能性があります。ただし、平均が 700 回の観測で発生した場合もあります。私のデータの平均レベルがいくつの観察/ケースで計算できるようにしたいと考えています。たとえば、おそらく 10 回の観測から始めて、これをランダムに 50 回または 100 回繰り返し、その後 20 回の観測に増やします....などです。

これは一種のモンテカルロ テストであることは理解しています。SPSS 15、17、18 と Excel にアクセスできます。minitab 15 & 16 と amos17 にもアクセスでき、「R」をダウンロードしましたが、これらに慣れていません。私の経験はSPSSとExcelです。私は SPSS Modified でいくつかの構文を試しました。

誰かが助けてくれることを願っています。

読んでくれてありがとう。

アンディ

では、ロボット ルンバ (素敵な掃除機) に、特定の部屋での位置を認識させたいと思います。つまり、部屋の地図があり、ロボットがどこかに配置されており、その場所を短時間で知る必要があるということです。多くのアルゴリズムを見てきましたが、最も関連性の高いアルゴリズムは、宇宙でのロボットの位置を特定するための MCL (モンテカルロ アルゴリズム) でした。私たちには大きすぎて、どこから始めればいいのかわからないのではないかと心配しています。MATLAB でコードを書きたいと思います。したがって、コードを見つけることができる場所を誰かが知っている場合は、大いに感謝します。私たちはこのアルゴリズムについて心を開いています。そのため、より優れたアルゴリズムや機能する可能性のあるものがあれば、それは素晴らしいことです。それは、私たちがそれを書いている言語に当てはまります。

ありがとう。リロン。

この記事の冒頭で説明したアルゴリズムを複製しようとするプログラムを作成しています。

http://www-stat.stanford.edu/~cgates/PERSI/papers/MCMCRev.pdf

F は char から char への関数です。Pl(f) がその関数の「妥当性」尺度であると仮定します。アルゴリズムは次のとおりです。

関数の予備的な推測から始めて、たとえば f と、新しい関数 f* を作成します。

• Pl(f) を計算します。
• f が 2 つのシンボルに割り当てる値をランダムに転置して、f* に変更します。
• Pl(f*) を計算します。これが Pl(f) より大きい場合は、f* を受け入れます。
• そうでない場合は、Pl(f)/Pl(f*) コインを 1 枚投げます。表が出たら、f* を受け入れます。
• コイントスで裏が出た場合は、f にとどまります。

次のコードを使用してこれを実装しています。私はc#を使用していますが、誰にとってもやや単純化しようとしました。これに関するより良いフォーラムがあれば、私に知らせてください。

私の質問は基本的に、これがそのアルゴリズムを実装するための最適なアプローチのように見えるかどうかです。この方法を実装しているにもかかわらず、極大値/極小値で動けなくなっているようです。

編集- これは基本的に Transpose() メソッドの背後にあるものです。候補関数が特定の char -> char 変換を調べるために使用する << char, char >> 型の辞書/ハッシュ テーブルを使用します。そのため、転置メソッドは、関数の動作を指示するディクショナリ内の 2 つの値を単純に交換します。

基になる辞書を使用する候補関数は、基本的に次のとおりであることに注意してください。

そして、これは Pl(f) を計算する関数です:

モンテカルロ法と進化的アルゴリズムの関係は? 一見すると、それらは複雑な問題を解決するために使用される、無関係なシミュレーション方法のように見えます。それぞれどの種類の問題に最適ですか? 彼らは同じ一連の問題を解決できますか? 2つの関係は何ですか（もしあれば）？

次のクラスは、非常に大きな文字列（テキストの小説全体）を解析し、それをタプルとして格納される連続する4文字の文字列に分割します。次に、計算に基づいて各タプルに確率を割り当てることができます。私はこれをモンテカルロ/遺伝的アルゴリズムの一部として使用して、構文のみに基づいて言語を認識するようにプログラムをトレーニングしています（文字の遷移のみ）。

これを行うより速い方法があるかどうか疑問に思います。任意の4文字のタプルの確率を調べるのに約400msかかります。関連するメソッド_Probablity（）は、クラスの最後にあります。

これは、私の別の投稿に関連する計算集約型の問題です。関数の妥当性を計算するためのアルゴリズム/モンテカルロ法

最終的には、これらの値を4Dマトリックスに保存したいと思います。しかし、アルファベットに26文字あることを考えると、これは非常に大きな作業になります。（26x26x26x26）。小説の最初の15000文字だけを取ると、パフォーマンスは1トン向上しますが、私のデータはそれほど有用ではありません。

テキスト'source'を解析するメソッドは次のとおりです。

そして、これが_Probabilityメソッドです。

編集-私は物事を片付けるためにもっと詳細を提供しています、

1）厳密に言えば、私はこれまで英語しか扱っていませんが、異なるアルファベットを考慮する必要があるのは事実です。現在、このペーパーで説明されているものと同様に、プログラムで英語のみを認識したいと考えています。http ://www-stat.stanford.edu/~cgates/PERSI/papers/MCMCRev.pdf

2）n <= 4の文字のnタプルの確率を計算しています。たとえば、文字列「that」の合計確率を計算する場合、これらの独立したタプルに分解して、それぞれの確率を計算します。個別に最初に：

[t] [h]

[t] [h] [a]

[それ]

[t] [h]が最も重みが与えられ、次に[t] [h] [a]、次に[t] [h][a][t]が与えられます。私は4文字のタプルを単一のユニットとして見ているだけではないので、テキスト内の[t] [h][a][t]のインスタンスを合計数で割ることはできません。次の4タプルの。

各4タプルに割り当てられた値は、テキストに適合しすぎることはありません。これは、偶然にも多くの実際の英語の単語がテキストに表示されない可能性があり、不釣り合いに低いスコアを取得するべきではないためです。1次の文字遷移（2タプル）を強調すると、この問題が改善されます。3タプルに移動してから、4タプルで計算を調整します。

私は、メモリの浪費である同一のタプルを繰り返すのではなく、テキスト内でタプルが発生する頻度のカウントを単純に集計する辞書を思いつきました（Vilxが提案したものと同様）。これにより、ルックアップあたり約400ミリ秒から約40ミリ秒になりました。これは、かなり大きな改善です。しかし、私はまだ他の提案のいくつかを調べる必要があります。

モンテカルロを使用して R^5 ハイパーキューブを統合する MATLAB コードを作成する必要があります。ジェネリック関数があるときに機能する基本的なアルゴリズムがあります。しかし、統合する必要がある機能は次のとおりです。

∫dA

A は R^5 の要素です。

∫f(x)dA があれば、私のアルゴリズムはうまくいくと思います。

アルゴリズムは次のとおりです。

ループ内で何回も (数百万回以上) 呼び出す計算関数を持つモンテカルロ シミュレータがあります。これを高速化するために、シミュレーターへの複数の並列スレッド呼び出しに分割したいと思います。すなわち。合計 100 万回実行したい場合は、おそらく 4 ～ 250,000 回の実行に分割して、すべて並行して実行します。各スレッドが同じ変数名を使用している場合、衝突がないようにこれを処理するにはどうすればよいですか? 異なる名前の変数を使用して、シミュレーターの 4 つの個別のバージョンを作成する必要がありますか?

Python スレッド モジュールを使用したバージョンの作成を開始しましたが、変数に関する問題がまだあることは確かです。

助言がありますか？

御時間ありがとうございます。

カイル