9

log-sum-exp問題を研究しています。対数として保存されている数値のリストがあり、これを合計して対数に保存したいと考えています。

素朴なアルゴリズムは

def naive(listOfLogs):
    return math.log10(sum(10**x for x in listOfLogs))

以下を含む多くの Web サイト: C での logsumexp の実装? および http://machineintelligence.tumblr.com/post/4998477107/ を使用することをお勧めします

def recommend(listOfLogs):
    maxLog = max(listOfLogs)
    return maxLog + math.log10(sum(10**(x-maxLog) for x in listOfLogs))

別名

def recommend(listOfLogs):
    maxLog = max(listOfLogs)
    return maxLog + naive((x-maxLog) for x in listOfLogs)

私が理解できないのは、推奨されるアルゴリズムが優れている場合、なぜそれを再帰的に呼び出す必要があるのですか? それはさらに多くの利益をもたらすでしょうか？

def recursive(listOfLogs):
    maxLog = max(listOfLogs)
    return maxLog + recursive((x-maxLog) for x in listOfLogs)

この計算をより数値的に安定させるための他のトリックはありますか？

4

3 に答える 3

11

他の人のためのいくつかの背景: 次のタイプの式を直接計算している場合

ln( exp(x_1) + exp(x_2) + ... )

次の 2 種類の問題が発生する可能性があります。

  • exp(x_i)オーバーフローする (x_iが大きすぎる) 可能性があり、合計できない数値になる
  • exp(x_i)アンダーフローする (x_iが小さすぎる) 可能性があり、その結果、ゼロが大量に発生します

すべての値が大きい場合、またはすべて小さい場合は、一部で割っての外側にexp(const)追加して、同じ値を得ることができます。したがって、正しい を選択できれば、値をある範囲にシフトして、オーバーフロー/アンダーフローを防ぐことができます。constlnconst

OPの質問は、なぜmax(x_i)他の値ではなくこのconstを選択するのですか? この計算を再帰的に実行して、各サブセットから最大値を選択し、対数を繰り返し計算してみませんか?

答え:関係ないからです。

理由？x_1 = 10大きくx_2 = -10て小さいとしましょう。(これらの数値はそれほど大きくありませんよね?) 式

ln( exp(10) + exp(-10) )

10 に非常に近い値が得られます。信じられない場合は、試してみてください。実際、一般に、ある特定のものが他のすべてよりもはるかに大きい場合、ln( exp(x_1) + exp(x_2) + ... )非常に近くなります。(余談ですが、この関数形式では、漸近的に、実際には一連の数値から数学的に最大値を選択できます。)max(x_i)x_i

したがって、他の値ではなく最大値を選択する理由は、値が小さいほど結果にほとんど影響しないためです。それらがアンダーフローした場合、それらは小さすぎて合計に影響を与えません。これは、最大の数とそれに近いものによって支配されるためです。計算用語では、小さい数値の寄与は、を計算した後にulp未満になりlnます。したがって、いずれにせよ最終結果で失われる場合、より小さい値の式を再帰的に計算する時間を無駄にする理由はありません。

これを実装することについて本当に熱心になりたい場合はexp(max(x_i) - some_constant)、オーバーフローとアンダーフローの両方を回避するために、結果の値を 1 の周りに「中央」にするために割る必要があります。これにより、結果の精度が数桁高くなる可能性があります。しかし、オーバーフローを回避することは、アンダーフローを回避することよりもはるかに重要です。前者は結果を決定し、後者は結果を決定しないため、この方法で行う方がはるかに簡単です。

于 2013-03-07T18:03:05.830 に答える
2

定義したように、recursive関数は決して終了しません。これ((x-maxlog) for x in listOfLogs)は、 と同じ数の要素がまだあるためlistOfLogsです。

これは、パフォーマンスや精度に大きな影響を与えることなく（非再帰バージョンと比較して）、簡単に修正できるとは思いません。

于 2013-03-07T17:36:52.037 に答える
2

再帰的に行うのは本当に良いことではありません。問題は、有限精度の算術演算が答えをノイズで圧倒しないようにしたいということだけです。最大値を単独で処理することにより、ジャンクの最も重要なコンポーネントが通過することが保証されるため、最終的な回答でジャンクを小さく保つことができます。

稚拙な説明で申し訳ありません。自分でいくつかの数字を試してみてください (最初に適切なリストは [1E-5,1E25,1E-5] かもしれません)。

于 2013-03-07T16:05:47.820 に答える