逐次計算：平均・分散・移動平均・移動分散

逐次計算（オンラインアルゴリズム）は，前ステップの計算結果と新たに取得したデータから現時点での計算結果を得る方法である．逐次計算により，メモリの節約や計算速度の向上が可能になる．

逐次計算（オンラインアルゴリズム）とは

過去の計算結果と新たに取得したデータを使って，平均や分散をアップデートしていく方法．

つまり，$n$ステップ目で欲しい量を$y_{n}$，新たに得られる量を$x_{n}$とするとき，更新ルールは

\begin{aligned}
y_{n} = f(y_{n-1}, x_{n})
\end{aligned}

となるような関数$f$で表される．

逐次更新では$x_{1},x_{2},\ldots x_{n}$をすべて保持しておく必要はなく，$y_{n-1}$と$x_{n}$を保持しておけば良い．

全データの平均・分散

Welfordのアルゴリズムという．

平均の逐次計算

全データの平均は次の式で表される：

\begin{aligned}
\bar{x}_{n} = \frac{1}{n} \sum_{i=1}^{n} x_{i}
\end{aligned}

これを逐次更新するための式は，

\begin{aligned}
\bar{x}_{n}
&= \frac{(n-1)\bar{x}_{n-1} + x_{n}}{n} \\
&= \bar{x}_{n-1} + \frac{1}{n} (x_{n} - \bar{x}_{n-1})
\end{aligned}

と書けます．

分散の逐次計算

分散は

\begin{aligned}
s_{n}^{2} =\frac{1}{n-1} \sum_{i=1}^{n} (x_{i} - \bar{x}_{n})^{2}
\end{aligned}

で定義される．

逐次計算は$s_{n}$を保持するのではなくて

\begin{aligned}
S_{n} = \sum_{i=1}^{n} (x_{i} - \bar{x}_{n})^{2}
\end{aligned}

を保持しておいて

\begin{aligned}
s_{n}^{2} &= \frac{1}{n-1} S_{n}
\end{aligned}

と計算するほうが使いやすい．実際，$S_{n}$の更新方法は

\begin{aligned}
S_{n}
&= \sum_{i=1}^{n}
\biggl[ (x_{i} - \bar{x}_{n-1}) - (\bar{x}_{n} - \bar{x}_{n-1}) \biggr]^{2} \\
& = \sum_{i=1}^{n-1} + \sum_{i=n} \\
& = \sum_{i=1}^{n-1} (x_{i} - \bar{x}_{n-1})^{2}
- 2(\bar{x}_{n} - \bar{x}_{n-1}) \cdot \cancel{\sum_{i=1}^{n-1} (x_{i} - \bar{x}_{n-1})} \\
& \quad
+(n-1)(\bar{x}_{n} - \bar{x}_{n-1})^{2} \\
& \quad
+ [(x_{n} - \bar{x}_{n-1} ) - (\bar{x}_{n} - \bar{x}_{n-1})]^{2} \\
&= S_{n-1} \\
&\quad
+\frac{n-1}{n^{2}}\biggl[ (x_{n} - \bar{x}_{n-1})^{2} + (n-1) (x_{n} - \bar{x}_{n-1})^{2} \biggr]\\
&= S_{n-1} + \frac{n-1}{n}(x_{n} - \bar{x}_{n-1})^{2} \\
&= S_{n-1} + (x_{n} - \bar{x}_{n-1})(x_{n} - \bar{x}_{n})
\end{aligned}

とシンプルである．ここで，平均の逐次計算式から得られる

\begin{aligned}
& \bar{x}_{n} - \bar{x}_{n-1} = \frac{1}{n} (x_{n} - \bar{x}_{n-1}) \\
& x_{n} - \bar{x}_{n} = \frac{n-1}{n} (x_{n} - \bar{x}_{n-1})
\end{aligned}

を用いた．

$s_{n}^{2} $の更新式に書き直すと

\begin{aligned}
s_{n}^{2}
&= \frac{1}{n-1}S_{n} \\
&= \frac{1}{n-1} \biggl[S_{n-1} + \frac{n-1}{n}(x_{n} - \bar{x}_{n-1})^{2}\biggr] \\
&= \frac{n-2}{n-1}s_{n-1}^{2} + \frac{1}{n}(x_{n} - \bar{x}_{n-1})^{2}
\end{aligned}

となる．

移動平均・移動分散

移動平均・移動分散は，最新の$n$個のデータだけを対象とする量である．

移動平均の逐次計算

移動平均は以下で定義される．

\begin{aligned}
\bar{x}_{m} = \frac{1}{n} \sum_{i=m-n+1}^{m} x_{i}
\end{aligned}

逐次計算では

\begin{aligned}
\bar{x}_{m}
&= (n\bar{x}_{m-1} - x_{m-n} + x_{m}) / n \\
&= \bar{x}_{m-1} + \frac{1}{n} (x_{m} - x_{m-n})
\end{aligned}

と更新できる．

移動分散の逐次計算

移動分散は以下で定義される．

\begin{aligned}
s_{m}^{2} = \frac{1}{n-1} \sum_{i=m-n+1}^{m} (x_{i} - \bar{x}_{m})^{2}
\end{aligned}

逐次計算では

\begin{aligned}
S_{m} = \sum_{i=m-n+1}^{m} (x_{i} - \bar{x}_{m})^{2}
\end{aligned}

を保持して，分散

\begin{aligned}
s_{m}^{2} = \frac{1}{n-1} S_{m}
\end{aligned}

を計算する．

\begin{aligned}
S_{m}
&= (x_{m} - \bar{x}_{m})^{2} - (x_{m-n} - \bar{x}_{m})^{2} \\
&\quad
+ \underbrace{\sum_{i=m-n}^{m-1} \biggl[(x_{i} - \bar{x}_{m-1}) - (\bar{x}_{m} - \bar{x}_{m-1}) \biggr]^{2}}
_{=S_{m-1} - 2(\bar{x}_{m} - \bar{x}_{m-1}) \cancel{\sum_{i=m-n}^{m-1} (x_{i} - \bar{x}_{m-1})} + n(\bar{x}_{m} - \bar{x}_{m-1})^{2} } \\
&= S_{m-1} + n(\bar{x}_{m} - \bar{x}_{m-1})^{2} + (x_{m} - \bar{x}_{m})^{2} - (x_{m-n} - \bar{x}_{m})^{2} \\
&= S_{m-1} + (x_{m} - x_{m-n})(\bar{x}_{m} - \bar{x}_{m-1}) \\
&\quad
+ (x_{m} - x_{m-n})\bigl[(x_{m} - \bar{x}_{m}) + (x_{m-n} - \bar{x}_{m})\bigr] \\
&= S_{m-1} +(x_{m} - x_{m-n})\bigl[(x_{m} - \bar{x}_{m}) + (x_{m-n} - \bar{x}_{m-1})\bigr]
\end{aligned}

まとめ

• 逐次計算を用いると，新しいデータが追加されるたびに統計量を効率的に更新できる．
• 全データを対象とする平均・分散の逐次計算には，Welfordのアルゴリズムが便利．
• 移動平均・移動分散の計算では，過去 $n$個のデータのみを考慮するため，全データの場合とは逐次更新式が異なる．

参考文献

• 経済・ファイナンスのための カルマンフィルター入門 (森平 爽一郎)：3章「逐次推定の考え方」
• Algorithms for calculating variance - Wikipedia
• 平均値と分散の逐次計算(オンラインアルゴリズム) #Python - Qiita