Статистика очень важная и нужная наука, некоторые утверждения о мире вокруг подтвержить или опровергнуть можно только после многократного повторения эксперимента. К примеру, подтвердить тот факт, что при бросании игральной кости с одинаковой вероятностью выпадает любая из ее граней, можно только очень много раз бросив эту игральную кость, записав результаты и подсчитав, сколько раз какая грань выпадала.
Эта характеристика называется распределением вероятностей, но мы начнем с более простых вещей. Базовая характеристика - среднее значение (говорим о математическом ожидании, есть и другие средние, которые сегодня не в фокусе нашего внимания).
Расчет среднего значения онлайн
Математическое ожидание случайной величины X (x_1, x_2, ..., x_n) определяется очень просто: m_n = (x_1 + x_2 + ... + x_n)/n. Проблема, о которой статья, здесь пока не стоит очень остро, в один проход по данным мы можем посчитать среднее значение по формуле-определению. Но что если мы хотим посчитать среднее "на лету" при поступлении данных извне? Что если не хотим хранить большой объем данных и забывать старые, просто актуализируя среднее значение?
Концепция до удивительности проста: мы пытаемся просто понять, чем отличаются среднее значение n элементов и среднее значение n+1 элементов. Пусть старое среднее называется m_n (определено выше), а новое тогда определим так:
m_{n+1} = (x_1 + x_2 + ... + x_n + x_{n+1})/(n+1).
Нужно в новом среднем выделить старое среднее. Для этого домножим правую часть на величину n/n и разобьем дробь на две части по числителю:
m_{n+1} = (x_1 + x_2 + ... + x_n)n/(n(n+1)) + (x_{n+1})/(n+1).
Здесь явно присутствует m_n, заменим соответствующее выражение:
m_{n+1} = m_n * n / (n+1) + (x_{n+1})/(n+1)
и вынесем общую часть за скобки:
m_{n+1} = (m_n * n + x_{n+1})/(n+1).
Теперь добавим и отнимем в числителе слагаемое m_n:
m_{n+1} = (m_n * (n+1) - m_n + x_{n+1})/(n+1),
а теперь разобьем дробь по числителю на две части и введем замену Dold = x_{n+1} - m_n:
m_{n+1} = m_n + Dold/(n+1).
Дополнительный приятный момент в том, что метод подсчета среднего значения онлайн лучше метода подсчета среднего по определению в смысле устойчивости (смотрите, например, работу "Numerically stable, scalable formulas for parallel and online computation of higher-order multivariate central moments with arbitrary weights" в google scholar).
Расчет среднеквадратичного отклонения (дисперсии) онлайн
Но особенный практический интерес онлайн алгоритмы приобретают, если мы хотим посчитать статистические моменты высших порядков. Например, среднеквадратичное отклонение по определению (для i = 1, 2, ..., n) можно найти так:
d_n = Σ(x_i - m_n)^2 / n,
а это означает, что до расчета среднеквадратичного отклонения нам нужно посчитать среднее. То есть, придется делать два прохода по ряду данных. Так что +1 аргумент в пользу онлайн алгоритмов.
Для обеспечения устойчивости вычислений сначала нужно считать отдельно сумму квадратов отклонений случайной величины
s_n = Σ(x_i - m_n)^2 = Σx_i^2 - n * m_n^2,
тогда на следующем шаге (для i = 1, 2, ..., n+1):
s_{n+1} = Σ(x_i - m_{n+1})^2 = Σx_i^2 - (n+1) * m_{n+1}^2.
Определим, чем отличаются новая и старая суммы "в лоб":
ds = s_{n+1} - s_n = Σ_{i=1}^{n+1} x_i^2 - (n+1) * m_{n+1}^2 - Σ_{i=1}^{n} x_i^2 + n * m_n^2.
В этом выражении суммы почти совпадают, отличаются одним слагаемым, то есть, можем перейти к следующему:
ds = x_{n+1}^2 - (n+1) * m_{n+1}^2 + n * m_n^2.
Дальше нужно немного попреобразовывать эту формулу, используя ранее выведенные соотношения, в результате можно получить следующее:
ds = (x_{n+1} - m_n)(x_{n+1} - m_{n+1}) = Dold * Dnew,
где Dold = x_{n+1} - m_n, а Dnew = x_{n+1} - m_{n+1}.
Сумма квадратов тогда итеративно изменяется следующим образом:
s_{n+1} = s_{n} + ds,
а дисперсия находится в любой нужный момент по формуле:
d_{n+1} = s_{n+1}/(n+1)
Заключение
В целом здесь разобраны очень известные и давно известные алгоритмы, но пусть будет, кому нужно, под рукой и на Дзене. Мне нужно было точно убедиться в корректности опубликованных в интернете и предложенных ИИ алгоритмов, так что было целесообразно сделать пошаговый вывод.
Источники
1. Статья на Википедии об онлайн-алгоритмах вычисления статистических моментов: https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance.