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

Question

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

Обратите внимание, что профиль веса движется вместе со мной, в то время как я двигаюсь по последовательности значений.

т.е. каждое значение не имеет собственного веса все время. Моя цель - уменьшить этот вес при прохождении мимо.

Answer 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

... тогда вам не нужно ничего делать, кроме добавления нового элемента * 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

Answer 2

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

Answer 3

Я думаю, вы ищете что-то вроде этого:

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;
}

Answer 4

Я пытался что-то практически кодировать (на Java). Как уже было сказано, ваша цель не достижима. Вы можете рассчитывать только среднее из некоторого числа последних запомненных значений. Если вам не нужно быть точным, вы можете приблизить старые значения. Я попытался сделать это, точно запомнив последние 5 значений, а только старые значения, суммированные с 5 значениями, помня последние 5 сумм. Тогда сложность 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;
    }
}

Answer 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) для многих практических применений) для генерации качественного приближения. Вы можете использовать еще меньше.

Answer 6

Здесь я предполагаю, что вы хотите, чтобы веса составляли 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;
}

Конечно, метод executeWeightFromCounter () в этом случае не должен генерировать веса, сумма которых равна единице. Хитрость заключается в том, что мы усредняем значение путем деления на сумму весов, так что в итоге веса фактически кажутся одному.

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