我想实现一个迭代算法，它计算加权平均值。比权重定律无关紧要，但对于最新值，它应该接近 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
请注意，重量曲线与我一起移动，而我则沿着值序列移动。
即每个值并不总是有自己的权重。我的目标是在过去时减轻这个体重。
首先介绍一下背景。如果我们保持正常平均值，它将是这样的：
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
> 但我的任务是每次新值到达时重新计算平均值，并重新加权旧值。
您的任务几乎总是不可能完成的，即使使用非常简单的加权方案也是如此。
您要求使用 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。
我想你正在寻找这样的东西：
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;
}
在这里，我假设您希望权重总和为 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((。例如，您可以简单地返回计数器本身，但请注意，最后一个加权数字不一定接近计数器的总和，因此您最终可能不会得到您想要的确切属性。(很难说，因为如前所述，你留下了一个相当悬而未决的问题。
这太长了，无法在评论中发布，但了解这一点可能会有所帮助。
假设您有： 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, ..., 0 z 位于某个位置 x 的位置
如果我们没有任何"额外"存储空间，那么f(z*w(x))=z*w(x + 1)位置 x 的权重w(x)。
重新排列等式，w(x + 1) = f(z*w(x))/z .好吧，对于常量 x，w(x + 1)最好是常数，所以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当c是权重值时x是一个常数。
所以w(x+1) = c*w(x).
也就是说，每个权重都是前一个权重的倍数。因此，权重的形式为 w(x)=m*b^x .
请注意，这假定f拥有的唯一信息是最后一个聚合值。请注意，在某些时候，除非您愿意存储代表输入的非恒定数据量，否则您将沦为这种情况。你不能用实数表示实数的无限长度向量，但你可以在恒定的有限存储量中以某种方式近似它们。但这只是一个近似值。
虽然我没有严格证明，但我的结论是，你想要的不可能以高精度完成，但你可以使用 log(n( 空间(在许多实际应用中也可能是 O(1((来生成高质量的近似值。您可能可以使用更少。
我试图实际编写一些东西(用Java(。正如已经说过的，你的目标无法实现。您只能从上次记住的某个数量的值中计算平均值。如果不需要精确，则可以近似较旧的值。我试图通过准确记住最后 5 个值和仅旧值相加 5 个值来记住最后 5 个 SUM，记住最后 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;
}
}
无记忆解决方案是根据先前平均值和新值的加权组合计算新平均值：
average = (1 - P) * average + P * value
其中 P 是经验常数，0 <= P <= 1
扩展提供：
average = sum i (weight[i] * value[i])
其中值 [0] 是最新值，并且
weight[i] = P * (1 - P) ^ i
当 P 较低时，历史值的权重更高。
P 越接近 1，它收敛到新值的速度就越快。
当 P = 1 时，它是一个常规赋值，并忽略以前的值。
如果你想最大化价值的贡献[N]，最大化
weight[N] = P * (1 - P) ^ N
其中 0 <= P <= 1
我发现重量[N]在以下情况下最大化
P = 1 / (N + 1)
(加权和(指数平均值与不同的有效窗口大小 (N( 组合在一起，以获得所需的权重。使用更指数的方式更详细地定义您的体重概况。(更多的指数意味着存储和计算更多的值，所以这里是权衡(