10

短いバージョン：実現のリストによって与えられる2つの確率変数を最も効率的に表現して追加する方法は？

やや長いバージョン： ワークプロジェクトの場合、それぞれが値のリストによって与えられるいくつかの確率変数を追加する必要があります。たとえば、ランドの実現。var。Aは{1,2,3}であり、Bの実現は{1,6,7}です。したがって、私が必要としているのは、A + Bの分布、つまり{1 + 5,1 + 6,1 + 7,2 + 5,2 + 6,2 + 7,3 + 5,3 + 6,3 + 7 }。そして、さまざまな確率変数（C、D、...）に対して、この種の加算を数回行う必要があります（この加算数をCOUNTと表記します。COUNTは720に達する可能性があります）。

問題： Aの各実現とBの各実現を合計するこの愚かなアルゴリズムを使用すると、COUNTでは複雑さが指数関数的になります。したがって、各rvが3つの値で与えられる場合、COUNT=720の計算量は3^720〜3.36xe ^ 343であり、計算するのに私たちの日々の終わりまで続きます:)実際にはそれは言うまでもありません人生では、各rvの長さは5000以上になります。

ソリューション： 1 /最初の解決策は、丸めに問題がないという事実を使用することです。つまり、実現の整数値を使用します。このように、私は各rvをベクトルとして表すことができ、実現に対応するインデックスでは、値は1になります（rvがこの実現を1回持つ場合）。したがって、rv Aと0から10までのインデックスが付けられた実現のベクトルの場合、Aを表すベクトルは[0,1,1,1,0,0,0 ...]になり、Bの表現は[0、 0,0,0,0,1,1,1,0,0,10]。ここで、これらのベクトルを調べてA + Bを作成し、上記と同じことを行います（Aの各実現とBの各実現を合計し、同じベクトル構造にコード化して、ベクトルの長さを2次複雑にします）。このアプローチの利点は、複雑さが制限されることです。このアプローチの問題は、実際のアプリケーションでは、Aの実現が[-50000、

2 /配列を短くするには、ハッシュマップを使用できます。これにより、理論スパンの重要な部分[-50K、 50K]は決して実現されません。ただし、ますます多くの確率変数の合計を続けると、実現の数は指数関数的に増加しますが、スパンは直線的にしか増加しないため、スパン内の数の密度は時間の経過とともに増加します。そして、これはハッシュマップの利点を殺してしまいます。

したがって、問題は、この問題を効率的に行うにはどうすればよいかということです。このソリューションは、すべての分布が経験的に与えられ、通常の分布とは異なり、式が役に立たず、シミュレートすることしかできない電力取引でVaRを計算するために必要です。

数学を使用することは、私たちの部門の半分として最初の選択肢と見なされていました。数学者です。ただし、追加するディストリビューションの動作は悪く、COUNT=720は極端です。より可能性が高いのは、毎日のVaRにCOUNT=24を使用することです。追加する分布の悪い振る舞いを考慮に入れると、COUNT = 24の場合、中心極限定理はあまり厳密には成り立たなくなります（SUM（A1、A2、...、A24）の分布は通常に近くなりません）。考えられるリスクを計算しているので、できるだけ正確な数値を取得したいと思います。

使用目的は次のとおりです。ある操作から1時間ごとにcasflowが発生します。1時間のキャッシュフローの分布はrvAです。次の1時間は、rv Bなどです。そしてあなたの質問は、99％のケースで最大の損失は何ですか？したがって、これらの24時間のそれぞれのキャッシュフローをモデル化し、これらのキャッシュフローを確率変数として追加して、1日全体の総キャスフローの分布を取得します。次に、0.01分位数を取得します。

4

4 に答える 4

1

プログラムによるソリューションを無視すると、データセットが大きくなるにつれて、追加の総数を大幅に減らすことができます。

Wそれぞれが3つの要素を持つ4つのグループ、、、およびを定義するとX、独自の数学によって、これは多数の操作につながります。YZ

  • W + X=>9回の操作
  • （W + X）+ Y=>27回の操作
  • （W + X + Y）+ Z=>81回の操作
  • 合計：117回の操作

ただし、「追加」操作の厳密に順序付けられた定義を想定して、2つのセット{a,b}が{c,d}常に結果になるようにすると{a+c,a+d,b+c,b+d}、操作は結合法則になります。これは、次のことができることを意味します。

  • W + X=>9回の操作
  • Y + Z=>9回の操作
  • （W + X）+（Y + Z）=>81回の操作
  • 合計：99回の操作

これは、単純なケースでは、18回の操作の節約になります。上記を3人のメンバーからなる6つのグループに拡張すると、操作の総数を1089から837に減らすことができ、ほぼ20％節約できます。この改善は、データが多いほど顕著になります（セットまたは要素が多いほど、節約量が増えます）。

さらに、これにより、並列化の問題が発生します。処理するグループが200ある場合は、最初に100ペアを並列に組み合わせ、次に50ペアまたは結果、次に25などを組み合わせることができます。これにより、高度な並列処理が可能になります。はるかに優れたパフォーマンスが得られるはずです。（たとえば、並列追加ごとCOUNTに2倍に増やすことができるため、最大10の並列操作で720セットが追加されます。）

私はこれについてまったく専門家ではありませんが、一般的なGPUの並列処理機能を使用する場合は理想的な問題のように思われます。私の理解では、CUDAのようなものは、これらすべての計算を並列処理するという短い作業を行います。

編集：あなたの本当の質問が「あなたの最大の損失は何ですか」であるなら、これははるかに簡単な問題です。最終セットのすべての値が各「コンポーネント」セットの1つの値の合計であるとすると、通常、最大の損失は、各コンポーネントセットの最小値を組み合わせることによって求められます。これらの低い値（セットごとに1つの値）を見つけることははるかに簡単な作業であり、その場合、その限られた値のセットを合計するだけで済みます。

于 2012-10-24T09:04:33.943 に答える
1

追加全体を行うために必要なパスの数を減らして、最終的なリストを含むすべてのリストに対して1つのパスに減らすようにしてください。

追加の総数を減らすことはできないと思います。

さらに、必要に応じて、並列アルゴリズムとマルチスレッドを検討する必要があります。

この時点で、ほとんどのプロセッサは、適切な指示（SSE）があれば、追加を並行して実行できます。これにより、追加が何倍も速くなります（複雑さの問題の解決策にはなりません）。

于 2012-10-24T08:36:08.923 に答える
1

あなたがあなたの質問で言ったように、あなたは正確な答えを得るために非常に多くの計算を必要とするでしょう。だからそれは起こらないだろう。

ただし、ランダムな値を扱っているので、問題にいくつかの数学を適用することは可能です。これらすべての追加の結果は、正規分布に近いものになりませんか？たとえば、1つのサイコロを振ることを検討してください。それぞれの数字は等しい確率を持っているので、実現は正規分布に従いません（実際、彼らはおそらくそうです、先週BBC4でそれについてのプログラムがあり、宝くじのボールがそれらの外観に正規分布を持っていることを示しました）。ただし、2つのサイコロを振って合計すると、実現は正規分布に従います。したがって、計算結果は正規分布に近似するため、特定の入力セットの平均値とシグマ値を見つけることが問題になると思います。

当然の質問があると思いますが、それが結果の用途ですか？結果がどのように使用されるかを知ることは、結果がどのように作成されるかについての決定に役立ちます。

于 2012-10-24T08:39:08.017 に答える
0

基本的に2つの方法があります。近似的なものと正確なもの...

近似法は、多くのサンプリングによって確率変数の合計をモデル化します。基本的に、確率変数Aを使用Bして、各rvからランダムに50K回サンプリングし、サンプリングされた値を追加し（ここでは、SSEが大いに役立ちます）、の分布がありA+Bます。これは数学者がMathematicaでこれを行う方法です。

正確な方法は、Dan Puzeyが提案したもの、つまり各rvの密度のごく一部のみを合計するものを利用します。次の「密度」を持つ確率変数があるとしましょう（簡単にするために、各値は同じ尤度です）。

A = {-5,-3,-2}
B = {+0,+1,+2}
C = {+7,+8,+9}

の合計A+B+Cは

{2,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,8,8,8,9}

分布全体を正確に知りたい場合は、Aの各要素をBの各要素と合計し、次にこの合計の各要素をCの各要素と合計する以外に選択肢はありません。ただし、99％のVaRのみが必要な場合この合計の、つまりこの合計の1％パーセンタイルの場合、の最小要素を合計するだけで済みA,B,Cます。

より正確には、nA,nB,nC各分布から最小の要素を取得します。決定するnA,nB,nCには、最初にこれらを1に設定しましょう。nA次に、 ifを1つ増やしますA[nA] = min( A[nA], B[nB], C[nC])（A,B,Cソートされていることを考慮して）。このようにして、（互いに）合計しなければならないnA, nB, nC最小の要素を取得し、X番目に小さい合計（Xは1％に合計の合計の組み合わせ数を掛けたもの、つまり3 * 3 *）を取得できます。 A,B,C3の場合A,B,C）。これは、増加を停止するタイミングも示します。>XのnA,nB,nC場合は停止します。nA*nB*nC

ただし、このように、同じ冗長性を再度実行しています。つまりA+B+C、1％パーセンタイルの左側の分布全体を計算しています。A+B+Cただし、これでも、ディストロ全体を計算するよりもはるかに短くなります。しかし、与えられたVaR数をexacltyに伝えるための単純な反復アルゴリズムが必要だと思いますO(a*b)。ここaで、は追加されbたrvの数であり、は各rvの密度の要素の最大数です。

私が正しいかどうかについてのコメントをいただければ幸いです。

于 2012-10-30T09:13:14.053 に答える