14

加重平均を計算する反復アルゴリズムを実装したいと考えています。特定の重みの法則は重要ではありませんが、最新の値では 1 に近く、最も古い値では 0 に近いはずです。

アルゴリズムは反復的でなければなりません。つまり、以前のすべての値を覚えておくべきではありません。最新の値と、平均、合計、カウントなどの以前の値など、過去に関する集計情報のみを知っている必要があります。

出来ますか？

たとえば、次のアルゴリズムは次のようになります。

void iterate(double value) {
   sum *= 0.99;
   sum += value;
   count++;
   avg = sum / count;
}

それは指数関数的に減少する重みを与えますが、これは良くないかもしれません。体重を段階的に減らすことは可能ですか？

編集1

計量法の要件は次のとおりです。

1) 体重は過去に減少する 2) 平均または特徴的な持続時間があるため、この持続時間の古い値は新しい値よりもはるかに重要ではありません 3) この持続時間を設定できるはずです

編集2

以下が必要です。が最初のv_i値であるv_1とします。また、w_i重みがあるとします。しかし、w_0最後です。

したがって、最初の値が来た後、最初の平均があります

 a_1 = v_1 * w_0

2 番目の値 v_2 が来た後、私は平均を持っている必要があります

 a_2 = v_1 * w_1 + v_2 * w_0

私が持つべき次の価値で

 a_3 = v_1 * w_2 + v_2 * w_1 + v_3 * w_0

値のシーケンスに沿って移動している間、体重プロファイルは私と一緒に移動していることに注意してください。

つまり、各値には常に独自の重みがあるわけではありません。私の目標は、過去に行くときにこの重量を下げることです.

4

8 に答える 8

28

最初に少し背景を。通常の平均を維持していた場合、次のようになります。

average(a) = 11
average(a,b) = (average(a)+b)/2
average(a,b,c) = (average(a,b)*2 + c)/3
average(a,b,c,d) = (average(a,b,c)*3 + d)/4

ここでわかるように、これは「オンライン」アルゴリズムであり、データの断片を追跡するだけで済みます: 1) 平均の合計数、および 2) 平均自体。次に、平均を合計で除算し、新しい数値を追加して、新しい合計で割ります。

加重平均は少し異なります。加重平均の種類によって異なります。たとえば、次のように定義したとします。

weightedAverage(a,wa, b,wb, c,wc, ..., z,wz) = a*wa + b*wb + c*wc + ... + w*wz
 or
weightedAverage(elements, weights) = elements·weights

...その後、新しい element*weight を追加する以外に何もする必要はありません! ただし、確率からの期待値に似た加重平均を定義した場合:

weightedAverage(elements,weights) = elements·weights / sum(weights)

...次に、総重量を追跡する必要があります。要素の総数で除算する代わりに、総重量で除算し、新しい要素*重量を追加してから、新しい総重量で除算します。

または、以下に示すように、元に戻す必要はありません: 一時的なドット積とクロージャーまたはオブジェクトの総重量を追跡し、結果として分割することができます (これは、数値の不正確さを回避するのに大いに役立ちます)複合丸め誤差)。

Python では、次のようになります。

def makeAverager():
    dotProduct = 0
    totalWeight = 0

    def averager(newValue, weight):
        nonlocal dotProduct,totalWeight

        dotProduct += newValue*weight
        totalWeight += weight
        return dotProduct/totalWeight

    return averager

デモ：

>>> averager = makeAverager()
>>> [averager(value,w) for value,w in [(100,0.2), (50,0.5), (100,0.1)]]
[100.0, 64.28571428571429, 68.75]
>>> averager(10,1.1)
34.73684210526316
>>> averager(10,1.1)
25.666666666666668
>>> averager(30,2.0)
27.4
于 2012-03-28T21:51:57.270 に答える
5

>しかし、私の仕事は、新しい値が到着するたびに平均を再計算し、古い値を再重み付けすることです。–OP

非常に単純な重み付けスキームであっても、あなたのタスクはほとんどの場合不可能です。

O（1）メモリを使用して、重み付けスキームを変更して平均を生成するよう求めています。たとえば、{ values·weights1、(values+[newValue2])·weights2、(values+[newValue2,newValue3])·weights3、...} は新しい値として渡され、ほぼ任意に変化する重みシーケンスがあります。これは、単射性のために不可能です。数値を一緒にマージすると、大量の情報が失われます。たとえば、重みベクトルがあったとしても、元の値ベクトルを復元することはできませんでした。逆もまた同様です。これを回避できると私が考えることができるケースは2つだけです。

  • [2,2,2,...2] などの一定の重み: これは、古い値が「再重み付け」されていないため、不要なオンライン平均化アルゴリズムと同等です。
  • 以前の回答の相対的な重みは変わりません。たとえば、 の重みを実行し[8,4,2,1]、 のような任意の重みを持つ新しい要素を追加することもできますが、 のように同じ乗法係数で...+[1]以前の要素をすべて増やす必要があります。したがって、各ステップで、新しい任意の重みと過去の新しい任意の再スケーリングを追加しているため、2 つの自由度があります (内積を正規化する必要がある場合は 1 つだけです)。得られる重みベクトルは次のようになります。[16,8,4,2]+[1]

 

[w0]
[w0*(s1), w1]
[w0*(s1*s2), w1*(s2), w2]
[w0*(s1*s2*s3), w1*(s2*s3), w2*(s3), w3]
...

したがって、そのように見える重み付けスキームはすべて機能します（重みの合計によって正規化されたものを保持する必要がある場合を除きます。その場合、新しい平均を新しい合計で割る必要があります。これは、O のみを保持することで計算できます） （1）メモリ）。以前の平均値に新しい値を掛けるだけsで (ドット積を暗黙のうちに重みに分配します)、新しい値を追加し+w*newValueます。

于 2012-03-29T21:27:15.800 に答える
2

私はあなたがこのようなものを探していると思います:

void iterate(double value) {
    count++;

    weight = max(0, 1 - (count / 1000));

    avg = ( avg * total_weight * (count - 1)  + weight * value) / (total_weight * (count - 1) + weight)
    total_weight += weight;
}
于 2012-03-28T21:12:45.137 に答える
1

これはコメントに投稿するには長すぎますが、知っておくと便利な場合があります。

あなたが持っているとしましょう:( これを略してw_0*v_n + ... w_n*v_0呼びます）w[0..n]*v[n..0]

次のステップは次のとおりです:( w_0*v_n1 + ... w_n1*v_0これはw[0..n1]*v[n1..0]略して）

これは、から計算する方法が必要であることを意味しw[1..n1]*v[n..0]ますw[0..n]*v[n..0]。

zがxの位置にある可能性v[n..0]は確かにあります。0, ..., 0, z, 0, ..., 0

'extra'ストレージがない場合、場所xの重みはf(z*w(x))=z*w(x + 1)どこになりますか。w(x)

方程式を並べ替えると、w(x + 1) = f(z*w(x))/z。ええと、w(x + 1)定数xに対しては一定であるf(z*w(x))/z方がよいので、一定である方がよいでしょう。したがって、伝播fさせる必要がありますz-つまり、f(z*w(x)) = z*f(w(x))。

しかし、ここでも問題があります。z（任意の数である可能性がある）がを介して伝播できる場合fは、w(x)確かに可能であることに注意してください。だからf(z*w(x)) = w(x)*f(z)。したがってf(w(x)) = w(x)/f(z)。ただし、定数の場合x、w(x)は定数であるため、定数f(w(x))でもある方がよいでしょう。w(x)は一定なので、一定であるf(z)方がよいでしょうw(x)/f(z)。したがってf(w(x)) = w(x)/c、cは定数です。

したがって、は定数f(x)=c*xであり、は重み値です。cx

だからw(x+1) = c*w(x)。

つまり、各重みは前の重みの倍数です。したがって、重みはの形式を取りますw(x)=m*b^x。

fこれは、情報が最後に集計された値のみであることを前提としていることに注意してください。入力を表す一定量ではないデータを保存する意思がない限り、ある時点でこのケースに限定されることに注意してください。実数の無限の長さのベクトルを実数で表すことはできませんが、一定の有限量のストレージで何らかの方法でそれらを近似することはできます。しかし、これは単なる概算にすぎません。

厳密には証明していませんが、あなたが望むことを高精度で行うことは不可能であるというのが私の結論ですが、log（n）スペース（O（1）の場合もあります）を使用できる可能性があります多くの実用的なアプリケーションの場合）品質近似を生成します。あなたはさらに少なく使うことができるかもしれません。

于 2012-03-29T23:01:03.577 に答える
1

私は実際に何かを（Javaで）コーディングしようとしました。言われているように、あなたの目標は達成できません。最後に記憶されたいくつかの値からの平均しかカウントできません。正確である必要がない場合は、古い値を概算できます。最後の5つの値を正確に記憶し、古い値は5つの値だけを合計して、最後の5つのSUMを記憶することでそれをやろうとしました。次に、最後の n+n*n 値を記憶するための複雑さは O(2n) です。これは非常に大まかな概算です。

「lastValues」と「lasAggregatedSums」の配列サイズは必要に応じて変更できます。最後の値のグラフを表示しようとしているこの ascii-art 画像を参照してください。最初の列 (古いデータ) が (個別ではなく) 集計値として記憶され、最も古い 5 つの値のみが個別に記憶されていることが示されています。

values:
            #####
            #####       #####        #
      ##### #####       #####        #  #
      ##### ##### ##### #####       ## ##
      ##### ##### ##### ##### ##### #####
time: --->

課題 1 : 私の例では重みをカウントしませんが、「lastAggregatedSums」の重みを適切に追加することは問題ではないと思います。唯一の問題は、古い値の重みを低くしたい場合は、配列が回転しているため、より難しく、配列メンバーのどの重みを知るのは簡単ではありません。アルゴリズムを変更して、回転する代わりに配列内の値を常に「シフト」することができますか? その後、重みを追加することは問題になりません。

課題 2 : 配列は 0 の値で初期化され、十分な値を受け取っていない場合でも、それらの値は最初から平均にカウントされます。アルゴリズムを長時間実行している場合は、最初にしばらく学習していることを気にしないでしょう。もしそうなら、あなたは修正を投稿することができます;-)

public class AverageCounter {
    private float[] lastValues = new float[5];
    private float[] lastAggregatedSums = new float[5];
    private int valIdx = 0;
    private int aggValIdx = 0;
    private float avg;

    public void add(float value) {
        lastValues[valIdx++] = value;
        if(valIdx == lastValues.length) {
            // count average of last values and save into the aggregated array.
            float sum = 0;
            for(float v: lastValues) {sum += v;}
            lastAggregatedSums[aggValIdx++] = sum;
            if(aggValIdx >= lastAggregatedSums.length) {
                // rotate aggregated values index
                aggValIdx = 0;
            }
            valIdx = 0;
        }
        float sum = 0;
        for(float v: lastValues) {sum += v;}
        for(float v: lastAggregatedSums) {sum += v;}
        avg = sum / (lastValues.length + lastAggregatedSums.length * lastValues.length);
    }

    public float getAvg() {
        return avg;
    }
}
于 2014-01-21T15:59:27.030 に答える
1

ここでは、重みの合計を 1 にしたいと仮定しています。将来変更せずに相対的な重みを生成できる限り、この動作を模倣するソリューションになる可能性があります。

つまり、重みをシーケンス{s_0, s_1, s_2, ..., s_n, ...}として定義し、入力をシーケンスとして定義したとします{i_0, i_1, i_2, ..., i_n}。

次の形式を検討してくださいsum(s_0*i_0 + s_1*i_1 + s_2*i_2 + ... + s_n*i_n) / sum(s_0 + s_1 + s_2 + ... + s_n)。いくつかの集計カウンターを使用して、これを増分的に計算することは自明に可能であることに注意してください。

int counter = 0;
double numerator = 0;
double denominator = 0;

void addValue(double val)
{
    double weight = calculateWeightFromCounter(counter);
    numerator += weight * val;
    denominator += weight;
}

double getAverage()
{
    if (denominator == 0.0) return 0.0;
    return numerator / denominator;
}

もちろん、この場合の calculateWeightFromCounter() は、合計が 1 になる重みを生成するべきではありません。ここでの秘訣は、重みの合計で除算して平均を計算し、最終的に重みの合計が実質的に 1 になるようにすることです。

本当の秘訣は、calculateWeightFromCounter() の実行方法です。たとえば、単純にカウンター自体を返すこともできますが、最後に加重された数値が必ずしもカウンターの合計に近いとは限らないため、必要な正確なプロパティが得られない可能性があることに注意してください。（前述のように、かなり未解決の問題を残しているため、言うのは難しいです。）

于 2012-03-28T21:45:13.020 に答える