增量计算——方差与协方差

增量计算——方差(Variance)

在给定\(N\)个样本\(\begin{bmatrix}x_1 & x_2 & \cdots & x_N\end{bmatrix}^T\)的方差计算如下: \[ s_N^2=\frac{1}{N}\sum_{i=1}^{N}{\left(\,x_i-\bar{x}_N\right)^2} \]

如果我们令 \[ \mathbf{1}_N=[\underbrace{1, 1, \dotsc, 1}_{N\text{ times}}]^T \] 表示一个全1矢量,且 \[ \tilde{\mathbf{x}}_N=\mathbf{x}_N-\bar{x}_N\mathbf{1}_N \] 表示原样本减去均值后的残差值,那么方差就可以简化表示如下: \[ s_N^2=\tilde{\mathbf{x}}_N^T\tilde{\mathbf{x}}_N\left/{N}\right. \] 举例来说: \[ \tilde{\mathbf{x}}_5 =\begin{bmatrix}48 \\ 29 \\ 46 \\ 57 \\ 34\end{bmatrix} - \left(\bar{x}_5=\frac{214}{5}\right)\times \begin{bmatrix}1 \\ 1 \\ 1 \\ 1 \\ 1\end{bmatrix} =\begin{bmatrix}26\,/\,5 \\ -69\,/\,5 \\ 16\,/\,5 \\ 71\,/\,5 \\ -44\,/\,5\end{bmatrix} \\ s_5^2 =\frac{\tilde{\mathbf{x}}_5^T\tilde{\mathbf{x}}_5}{5} =\frac{2534}{25} \]

如果要是将简化形式展开计算,那么就能得到一个有益于增量计算的表达方式: \[ \begin{aligned} \tilde{\mathbf{x}}_N^T\tilde{\mathbf{x}}_N\left/{N}\right.&=\left(\mathbf{x}_N-\bar{x}_N\mathbf{1}_N\right)^T\left(\mathbf{x}_N-\bar{x}_N\mathbf{1}_N\right)\left/N\right. \\ &=\left(\mathbf{x}_N^T\mathbf{x}_N - N\bar{x}_N^2\right)\left/N\right. \\ s_N^2&=\mathbf{x}_N^T\mathbf{x}_N\left/N\right. - \bar{x}_N^2 \end{aligned} \] 例如下式可以证明结果正确 \[ s_5^2 =\frac{\mathbf{x}_5^T\mathbf{x}_5=9666}{5}-\left(\frac{214}{5}\right)^2=\frac{2534}{25} \] 那么,如果有新的元素\(x_{N+1}\)在流数据中到达时,方差就可以增量更新了: \[ \begin{aligned} s_{N+1}^2&=\frac{\tilde{\mathbf{x}}_{N+1}^T\tilde{\mathbf{x}}_{N+1}}{N+1}\\ &=\frac{\left(\mathbf{x}_{N+1}-\bar{x}_{N+1}\mathbf{1}_{N+1}\right)^T\left(\mathbf{x}_{N+1}-\bar{x}_{N+1}\mathbf{1}_{N+1}\right)}{N+1}\\ &=\frac{\mathbf{x}_{N+1}^T\mathbf{x}_{N+1}-\left(N+1\right)\:\bar{x}_{N+1}^2}{N+1}\\ &=\frac{\mathbf{x}_N^T\mathbf{x}_N+x_{N+1}^2-\left(N+1\right)\:\bar{x}_{N+1}^2}{N+1}\\ &=\frac{\mathbf{x}_N^T\mathbf{x}_N+x_{N+1}^2}{N+1}-\bar{x}_{N+1}^2\\ \end{aligned} \]

例如:

\[ s_6^2=\frac{\mathbf{x}_N^T\mathbf{x}_N+x_{N+1}^2 =9666+66^2}{6}-\left(\frac{140}{3}\right)^2=\frac{1433}{9} \] 又因为 \[ \mathbf{x}_N^T\mathbf{x}_N=\sum_{i=1}^{N}{x_i^2} \] 所以在计算过程中只需要记录(1)累加平方和(2)均值 这两个变量就行了。


增量计算——协方差

考虑一对向量 \[ \begin{aligned} \mathbf{x}&=\left[x_1, x_2, \dotsc, x_N\right]^T\\ \mathbf{y}&=\left[y_1, y_2, \dotsc, y_N\right]^T \end{aligned} \] 均值 \[ \bar{x}_N=\Sigma_N\mathbf{x}_N\left/N\right.,\;\; \bar{y}_N=\Sigma_N\mathbf{y}_N\left/N\right. \]

残差 \[ \tilde{\mathbf{x}}_N=\mathbf{x}_N-\bar{x}_N\mathbf{1}_N,\;\; \tilde{\mathbf{y}}_N=\mathbf{y}_N-\bar{y}_N\mathbf{1}_N \]

考虑外积 \[ \begin{bmatrix} \tilde{\mathbf{x}}_N^T \\ \tilde{\mathbf{y}}_N^T \end{bmatrix} \begin{bmatrix} \tilde{\mathbf{x}}_N & \tilde{\mathbf{y}}_N \end{bmatrix} = \begin{bmatrix} \tilde{\mathbf{x}}_N^T\tilde{\mathbf{x}}_N & \tilde{\mathbf{x}}_N^T\tilde{\mathbf{y}}_N \\ \tilde{\mathbf{y}}_N^T\tilde{\mathbf{x}}_N & \tilde{\mathbf{y}}_N^T\tilde{\mathbf{y}}_N \end{bmatrix} \]

那么有 \[ S_N^2= \frac{1}{N} \begin{bmatrix} \tilde{\mathbf{x}}_N^T\tilde{\mathbf{x}}_N & \tilde{\mathbf{x}}_N^T\tilde{\mathbf{y}}_N \\ \tilde{\mathbf{y}}_N^T\tilde{\mathbf{x}}_N & \tilde{\mathbf{y}}_N^T\tilde{\mathbf{y}}_N \end{bmatrix} \]

上式中每一项都可以根据增量方差的公式进行增量计算,那么用总体样本的协方差转换成样本协方差的无偏估计,先乘\(N\) 再除以\(N-1\),那么有:

\[ \Sigma_N^2= \frac{1}{N-1} \begin{bmatrix} \tilde{\mathbf{x}}_N^T\tilde{\mathbf{x}}_N & \tilde{\mathbf{x}}_N^T\tilde{\mathbf{y}}_N \\ \tilde{\mathbf{y}}_N^T\tilde{\mathbf{x}}_N & \tilde{\mathbf{y}}_N^T\tilde{\mathbf{y}}_N \end{bmatrix}= \frac{N S_N^2}{N-1} \]

ref: Incremental Covariance