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

在第二个值 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

...那么除了添加新元素*重量之外，您无需执行任何操作！但是，如果您将加权平均值定义为类似于概率的预期值：

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] 之类的常量权重：这等效于在线平均算法，您不希望使用这种算法，因为旧值没有被“重新加权”。
  • 先前答案的相对权重不会改变。例如，您可以对 进行权重[8,4,2,1]，并添加一个具有任意权重的新元素，例如...+[1]，但是您必须将所有先前的元素都增加相同的乘法因子，例如[16,8,4,2]+[1]。因此，在每一步中，您都添加了一个新的任意权重，以及一个新的对过去的任意重新缩放，因此您有 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

在这里，我假设您希望权重总和为 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。

真正的诀窍是你如何计算weightFromCounter()。例如，您可以简单地返回计数器本身，但请注意，最后一个加权数字不一定会接近计数器的总和，因此您最终可能不会得到您想要的确切属性。（这很难说，因为如前所述，你留下了一个相当悬而未决的问题。）

于 2012-03-28T21:45:13.020 回答
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]

这当然有可能v[n..0]是0, ..., 0, z, 0, ..., 0z 在某个位置 x 的位置。

如果我们没有任何“额外”存储，那么位置 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)/cwherec是一个常数。

所以，f(x)=c*x哪里c是一个常数，什么时候x是一个权重值。

所以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 回答
0

您可以将（加权和）指数均值与不同的有效窗口大小（N）结合起来，以获得所需的权重。使用更多指数方法来更详细地定义您的体重曲线。（更多的指数意味着存储和计算更多的值，所以这里是权衡）

于 2019-12-19T13:24:44.967 回答
0

一种无记忆的解决方案是根据先前平均值和新值的加权组合计算新平均值：

average = (1 - P) * average + P * value

其中 P 是经验常数，0 <= P <= 1

扩展给出：

average = sum i (weight[i] * value[i])

其中 value[0] 是最新的值，并且

weight[i] = P * (1 - P) ^ i

当 P 较低时，历史值的权重较高。

P 越接近 1，它收敛到新值的速度就越快。

当 P = 1 时，它是一个常规赋值并忽略以前的值。

如果要最大化value[N]的贡献，最大化

weight[N] = P * (1 - P) ^ N

其中 0 <= P <= 1

我发现 weight[N] 最大化时

P = 1 / (N + 1)
于 2021-07-25T12:35:31.117 回答