Как рассчитать итеративно текущее взвешенное среднее значение, чтобы последние значения больше всего веса?

Ответ 1

Сначала немного фона. Если бы мы сохраняли нормальное среднее значение, это было бы следующим:

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)

... тогда вам нужно будет отслеживать общие веса. Вместо того, чтобы делиться на общее количество элементов, вы несете общий вес, добавьте новый элемент & weight, затем разделите его на новый общий вес.

В качестве альтернативы вам не нужно отказываться, как показано ниже: вы можете просто отслеживать продукт временной точки и общий вес в закрытии или объекте и делить его по мере поступления (это может помочь во многом избежать числовая погрешность от сложных ошибок округления).

В 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

Ответ 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;
}

Ответ 3

> Но моя задача состоит в том, чтобы усреднить пересчет каждый раз, когда приходит новое значение, когда старые значения возвращаются в исходное состояние. -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.

Ответ 4

Здесь я предполагаю, что вы хотите, чтобы весы суммировались до 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() в этом случае не должен генерировать весовые коэффициенты, которые суммируются с одним - вот здесь мы заключаем, что мы усредняем путем деления на сумму весов, так что в конце весы фактически кажутся суммой к одному.

Реальным трюком является то, как вы выполняете вычислениеWeightFromCounter(). Например, вы можете просто вернуть счетчик, но, тем не менее, обратите внимание, что последнее взвешенное число не обязательно будет близко к сумме счетчиков, поэтому вы не можете получить точные свойства, которые вы хотите. (Трудно сказать, поскольку, как уже упоминалось, вы оставили довольно открытую проблему.)

Ответ 5

Это слишком долго, чтобы опубликовать комментарий, но может быть полезно знать.

Предположим, что у вас есть: 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), где w(x) - вес для местоположения 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 где c является константой, когда x является весовым значением.

Итак w(x+1) = c*w(x).

То есть каждый вес является кратным предыдущему. Таким образом, веса принимают вид w(x)=m*b^x.

Обратите внимание, что это предполагает, что единственная информация f имеет последнее агрегированное значение. Обратите внимание, что в какой-то момент вы будете сведены к этому случаю, если вы не захотите хранить непостоянный объем данных, представляющих ваш вход. Вы не можете представить бесконечный вектор длины действительных чисел с вещественным числом, но вы можете как-то их аппроксимировать в постоянном конечном объеме хранения. Но это было бы просто приближением.

Хотя я не очень точно это доказал, я пришел к выводу, что то, что вы хотите, невозможно сделать с высокой степенью точности, но вы можете использовать log (n) пространство (что также может быть O (1) для многих практических применений) для получения качественного приближения. Возможно, вы сможете использовать еще меньше.

Ответ 6

Я пытался практически что-то кодировать (на Java). Как уже было сказано, ваша цель не достижима. Вы можете рассчитывать только среднее значение из некоторого количества последних запоминаемых значений. Если вам не нужно быть точным, вы можете приблизиться к старым значениям. Я попытался сделать это, вспомнив последние 5 значений точно и старше, только SUMmed на 5 значений, помня последние 5 SUM. Тогда сложность O (2n) для запоминания последних значений n + n * n. Это очень грубое приближение.

Вы можете изменить размеры массива "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;
    }
}