6

この問題のルールは、実際に GLn のサブセットを見ているため、かなり具体的です 。行ベクトルと列ベクトルが特定の形式を持っている必要があります (これらのベクトルを有効と呼びます。以下の例を参照してください)。ルールは次のとおりです。

  1. 長さ n の有効な非ゼロ ベクトルを一様に無作為に選択できます。

  2. 有効な vector が与えられると、関数 を使用して、v1, v2, ..., vkそれらが形成する部分列が有効な vector のプレフィックスであるかどうか (たとえば[v1_1 v2_1 ... vk_1]、有効な vector の最初の k エントリとして発生するかどうか) を判断できますisPrefix。

  3. 有効なベクトル v1、v2、...、vk が与えられた場合、関数 を使用してそれらが線形従属であるかどうかを判断できますareIndependent。

目標は、GLn のこのサブセットから均一にランダムにサンプリングすることです。失敗する素朴な解決策は次のとおりです。

    Step 1: Select a valid v1 uniformly at random. 
            If isPrefix(v1) then Go to Step 2.
            Otherwise repeat Step 1.

    Step 2: Select a valid v2 uniformly at random. 
            If areIndependent(v1,v2) & isPrefix(v1,v2), then go to Step 3. 
            Otherwise, repeat Step 2.

    ...

    Step n: Select a valid vn uniformly at random. 
            If areIndependent(v1,v2,...,vn) & isPrefix(v1,v2,...,vn), then END. 
            Otherwise, repeat Step n.

areIndependent(v1,v2,...,vk) & isPrefix(v1,v2,...,vk)この解決策の問題点は、正しく戻る可能性があまり高くないイベントで無限ループに陥る可能性TRUEがあることですが、この k タプルを線形に独立した有効な n タプルに完成させる方法がないことです。これの一般的な例は、TRUEk=n-1である一意の有効なベクトルvnがあるが、このベクトルは前の n-1 ベクトルから独立していない場合です。isPrefix(v1,v2,...,vn)

したがって、このループに陥っている場合は、1 つまたは 2 つのステップをバックアップするために何らかの方法で追加する必要がありますが、いつループするかは必ずしもわかりません。私はこれらの線に沿った解決策を探しています:有効なベクトルの分布に依存する可能性のある明示的な関数でステップ k が何度も失敗した場合は、ステップ k-1 に戻ります (または、さらに明示的な方法で)。f(k)f

提案、コメント、参照などは大歓迎です! ありがとう！

例:

私は実際に、サンプリングの進め方に関する一般的な参考資料またはガイドラインを探しています。これを実行したい有効なベクトルの例がいくつかありますが、すべての例をリストして SO コミュニティに解決策をハッシュしてもらうよりも、最終的には自分で実行できる方が役に立ちます。ただし、具体的に、関連する難しさの感覚をつかむために、ここに 1 つの例を示します。

交互符号行列: ベクトルは、そのエントリがすべて 0、-1、1 であり、ゼロ以外のエントリが 1 と -1 の間で交互に繰り返され、エントリの合計が 1 である場合に有効です。たとえば、すべての順列行列は有効なベクトルで構成されます。 、および以下も含まれます。

 0  1  0
 1 -1  1
 0  1  0

Distinct Entries : ベクトルは、別個のエントリを持つ場合に有効です。この条件は列だけでなく行にも適用されるため、これは特に厄介です。

これを見てくれたすべての人々に再び感謝します！

4

1 に答える 1

3

マルコフ連鎖モンテカルロ アルゴリズム ( http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm ) に移行する必要があるのではないかと思いますが、必ずしも速度のためではありませんが、ランダム サンプルが適切に分散されていることを確認してください。 .

ランダム サンプリングの 1 つの定義は、列の元の分布からランダムに行列を生成し、有効なものだけを保持した場合と同じ分布を生成することです。

ツリーからアイテムを生成し、すべてのノードが同じ次数を持っていない場合、葉は同じ確率で訪問されません。2 つの非リーフ ノードを持つ単純なツリーを考えてみましょう。そのうちの 1 つは単一のリーフの子を持ち、もう 1 つは 100 万のリーフの子を持ちます。ルートから下に移動してサンプリングし、各ノードでランダムな選択を行う場合、単一のリーフの子は、100 万の兄弟を持つセットの特定のリーフよりも頻繁にアクセスされます。

上記の無限ループに陥ったため、子ノードを持たないノードが存在するケースが見つかりました。葉がまったくあると仮定すると、ノードの次数がすべて同じではないツリーがあります。

さまざまな有効性ルールに対してさまざまなアプローチをコーディングする必要が生じる可能性があり、マルコフ連鎖が「焼き付き」、かなりランダムになるまでにかかる時間を心配する必要があります。後の点から 1 つの (一種の) 例外があります。特定の構成がランダムに選択された可能性を排除するためにテール確率を計算しようとしている場合、そのポイントからマルコフ連鎖を開始できます。帰無仮説の下では、そのポイントはすでにランダムに選択されているため、生成された値はすべて、その開始点よりも大きな統計値を持っています。何か怪しいことが起こっています。

于 2011-05-17T18:23:41.670 に答える