稀疏贝叶斯学习 3

FSBL 快速贝叶斯学习算法

前面已经求得的 $$\boxed{\begin{array}{r}\mathcal{L}(\mathbf{t}|{\sigma }^2,\mathbf{\alpha })=-\frac{1}{2}\log |{\sigma }^2\mathbf{I}+\mathbf{\Phi }{\mathbf{\Lambda }}_{\alpha }{\mathbf{\Phi }}^{\mathrm{T}}|-\frac{1}{2}{\mathbf{t}}^{\mathrm{T}}({\sigma }^2\mathbf{I}+\mathbf{\Phi }{\mathbf{\Lambda }}_{\alpha }{\mathbf{\Phi }}^{\mathrm{T}}{)}^{-1}\mathbf{t}\end{array}}$$

$$\boxed{\begin{array}{rl}{\mathbf{\Sigma }}_w^{-1}& =\frac{1}{{\sigma }^2}{\mathbf{\Phi }}^{\mathrm{T}}\mathbf{\Phi }+{\mathbf{\Lambda }}_{\alpha }^{-1}\\ {\mathbf{\mu }}_w& ={\sigma }^{-2}{\mathbf{\Sigma }}_w{\mathbf{\Phi }}^{\mathrm{T}}\mathbf{t}\end{array}}$$

稀疏贝叶斯学习过程如下： $$\begin{array}{rl}{\alpha }_i^{\text{new}}& =\frac{{\gamma }_i}{{\mu }_i^2}\\ ({\sigma }^2{)}^{\text{new}}& =\frac{\Vert \mathbf{t}-\mathbf{\Phi }{\mathbf{\mu }}_w{\Vert }^2}{N-{\sum }_i{\gamma }_i}\\ {\gamma }_i& =1-[{\mathbf{\Sigma }}_w{]}_{i,i}\cdot {\alpha }_i\end{array}$$ 实际操作中，$\mathbf{\alpha }$ 中大部分元素将变得很大，这在迭代更新过程中会引入较大的运算量，如果仅仅将无限大的元素停止更新不删除，导致的（ill-conditioned） $\mathbf{\Sigma }$ 矩阵来更新 $\mathbf{\alpha }$ 将毫无意义。

上一节中得到的对数，为 $$\begin{array}{r}\mathcal{L}(\mathbf{t}|{\sigma }^2,\mathbf{\alpha })=-\frac{N}{2}\log (2\pi )-\frac{1}{2}\log |{\mathbf{\Sigma }}_t|-\frac{1}{2}{\mathbf{t}}^{\mathrm{T}}{\mathbf{\Sigma }}_t^{-1}\mathbf{t}\end{array}$$ 其中 ${\mathbf{\Sigma }}_t={\sigma }^2\mathbf{I}+\mathbf{\Phi }{\mathbf{\Lambda }}_{\alpha }{\mathbf{\Phi }}^{\mathrm{T}}$，令 $\mathbf{C}={\mathbf{\Sigma }}_t$，以及 ${\mathbf{A}}^{-1}={\mathbf{\Lambda }}_{\alpha }$。

重新整理得到 $$\boxed{\begin{array}{r}\mathcal{L}(\mathbf{t}|{\sigma }^2,\mathbf{\alpha })=-\frac{1}{2}[N\log (2\pi )+\log \left|\mathbf{C}\right|+{\mathbf{t}}^{\mathrm{T}}{\mathbf{C}}^{-1}\mathbf{t}]\end{array}}$$ 其中，$\mathbf{C}={\sigma }^2\mathbf{I}+\mathbf{\Phi }{\mathbf{A}}^{-1}{\mathbf{\Phi }}^{\mathrm{T}}$。

为了减小运算量，我们做以下分解：

$$\begin{array}{rl}\mathbf{C}& ={\sigma }^2\mathbf{I}+\mathbf{\Phi }{\mathbf{A}}^{-1}{\mathbf{\Phi }}^{\mathrm{T}}\\ & ={\sigma }^2\mathbf{I}+\sum _{m\ne i}{\alpha }_m^{-1}{\mathbf{\varphi }}_m{\mathbf{\varphi }}_m^{\mathrm{T}}+{\alpha }_i^{-1}{\mathbf{\varphi }}_i{\mathbf{\varphi }}_i^{\mathrm{T}}\\ & ={\mathbf{C}}_{-i}+{\alpha }_i^{-1}{\mathbf{\varphi }}_i{\mathbf{\varphi }}_i^{\mathrm{T}}\end{array}$$ 其中 ${\mathbf{C}}_{-i}$ 为 $\mathbf{C}$ 去掉基向量 $i$ 贡献后的结果。给定 $\mathcal{L}(\mathbf{t}|{\sigma }^2,\mathbf{\alpha })$ 中的行列式计算（大名鼎鼎的 The Matrix Determinant Lemma 定理来啦）为 $$\begin{array}{rl}\left|\mathbf{C}\right|& =|{\mathbf{C}}_{-i}+{\alpha }_i^{-1}{\mathbf{\varphi }}_i{\mathbf{\varphi }}_i^{\mathrm{T}}|\\ & =\left|{\mathbf{C}}_{-i}\right|\cdot |1+{\alpha }_i^{-1}{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i|\end{array}$$ 那么接下来去计算逆矩阵，利用 $$(\mathbf{P}+\rho \mathbf{a}{\mathbf{a}}^H{)}^{-1}={\mathbf{P}}^{-1}-\rho {\mathbf{P}}^{-1}\mathbf{a}(1+\rho {\mathbf{a}}^H{\mathbf{P}}^{-1}\mathbf{a}{)}^{-1}{\mathbf{a}}^H{\mathbf{P}}^{-1}$$ 因此可以得到 $$\begin{array}{rl}{\mathbf{C}}^{-1}& =({\mathbf{C}}_{-i}+{\alpha }_i^{-1}{\mathbf{\varphi }}_i{\mathbf{\varphi }}_i^{\mathrm{T}}{)}^{-1}\\ & ={\mathbf{C}}_{-i}^{-1}-{\alpha }_i^{-1}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i(1+{\alpha }_i^{-1}{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i{)}^{-1}{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}\\ & ={\mathbf{C}}_{-i}^{-1}-\frac{{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}}{{\alpha }_i+{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i}\end{array}$$ 于是令 $1+{\alpha }_i^{-1}{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i={\alpha }_i^{-1}({\alpha }_i+{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i)$， $\mathcal{L}(\mathbf{\alpha })$ 可以写为 $$\begin{array}{rl}\mathcal{L}(\mathbf{\alpha })& =-\frac{1}{2}[N\log (2\pi )+\log |\mathbf{C}|+{\mathbf{t}}^{\mathrm{T}}{\mathbf{C}}^{-1}\mathbf{t}]\\ & =-\frac{1}{2}[N\log (2\pi )+\log |{\mathbf{C}}_{-i}|+\log (1+{\alpha }_i^{-1}{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i)+{\mathbf{t}}^{\mathrm{T}}({\mathbf{C}}_{-i}^{-1}-\frac{{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}}{{\alpha }_i+{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i}\left)\mathbf{t}\right]\\ & =-\frac{1}{2}[N\log (2\pi )+\log |{\mathbf{C}}_{-i}|-\log {\alpha }_i+\log ({\alpha }_i+{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i)+{\mathbf{t}}^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}\mathbf{t}-\frac{{\mathbf{t}}^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}\mathbf{t}}{{\alpha }_i+{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i}]\\ & =-\frac{1}{2}[N\log (2\pi )+\log |{\mathbf{C}}_{-i}|-\log {\alpha }_i+\log ({\alpha }_i+{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i)+{\mathbf{t}}^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}\mathbf{t}-\frac{({\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}\mathbf{t}{)}^2}{{\alpha }_i+{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i}]\end{array}$$ 我们令 $$\begin{array}{rl}{s}_i& ={\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}{\mathbf{\varphi }}_i\\ q_i& ={\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}\mathbf{t}\end{array}$$ 从而 $\mathcal{L}(\mathbf{\alpha })$ 可以写为 $$\begin{array}{rl}\mathcal{L}(\mathbf{\alpha })& =-\frac{1}{2}[N\log (2\pi )+\log |{\mathbf{C}}_{-i}|+{\mathbf{t}}^{\mathrm{T}}{\mathbf{C}}_{-i}^{-1}\mathbf{t}-\log {\alpha }_i+\log ({\alpha }_i+s_i)-\frac{q_i^2}{{\alpha }_i+s_i}]\\ & =\mathcal{L}({\mathbf{\alpha }}_{-i})+\frac{1}{2}[\log {\alpha }_i-\log ({\alpha }_i+s_i)+\frac{q_i^2}{{\alpha }_i+s_i}]\\ & =\mathcal{L}({\mathbf{\alpha }}_{-i})+\ell ({\alpha }_i)\end{array}$$

其中两个常数系数：

稀疏系数 $s_i$ 可以被视为衡量基向量 ${\mathbf{\varphi }}_i$ 与模型中已经存在的 ${\mathbf{\varphi }}_i$ 重叠的程度。质量系数 $q_i$ 是 ${\mathbf{\varphi }}_i$ 与不包括该向量的模型误差对齐的一种度量，是衡量 ${\mathbf{\varphi }}_i$ 增加 $\mathcal{L}(\mathbf{\alpha })$ 的效果。

上面的分析（求导，通分，令分子为 0，注意结果应该是合理的方差取值范围）表明 $\mathcal{L}(\mathbf{\alpha })$ 相对于 ${\alpha }_i$ 具有唯一的最大值：

$$\begin{array}{rl}{\alpha }_i& =\frac{s_i^2}{q_i^2-s_i},q_i^2>s_i\\ {\alpha }_i& =\infty ,q_i^2\le s_i\end{array}$$

通过迭代过程，计算所有的基向量 ${\mathbf{\varphi }}_i$ 对应的 $s_i$ 和 $q_i$，更新参数向量 $\mathbf{\alpha }$，总结基于快速 RVM 的贝叶算法如下：

1） 对于稀疏回归问题，初始化 ${\sigma }^2$。

2） 初始化一个基向量 ${\mathbf{\varphi }}_i$，根据 $${\alpha }_i=\frac{s_i^2}{q_i^2-s_i},q_i^2>s_i$$ 这时候初始化的 $\mathbf{C}={\sigma }^2\mathbf{I}+{\alpha }_i^{-1}{\mathbf{\varphi }}_i{\mathbf{\varphi }}_i^{\mathrm{T}}$，因此 ${\mathbf{C}}_{-i}={\sigma }^2\mathbf{I}\to {\mathbf{C}}_{-i}^{-1}={\sigma }^{-2}\mathbf{I}$。使超参数 $$\begin{array}{rl}{\alpha }_i& =\frac{s_i^2}{q_i^2-s_i}=\frac{\Vert {\sigma }^{-2}{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{\varphi }}_i{\Vert }^2}{\Vert {\sigma }^{-2}{\mathbf{\varphi }}_i^{\mathrm{T}}\mathbf{t}{\Vert }^2-{\sigma }^{-2}{\mathbf{\varphi }}_i^{\mathrm{T}}{\mathbf{\varphi }}_i}\\ & =\frac{\Vert {\mathbf{\varphi }}_i{\Vert }^2}{\Vert {\mathbf{\varphi }}_i^{\mathrm{T}}\mathbf{t}{\Vert }^2/\Vert {\mathbf{\varphi }}_i{\Vert }^2-{\sigma }^2}\end{array}$$ 其他 ${\alpha }_m$ 理论上为无穷大。

3）显示计算初始化的均值 $\mathbf{\mu }$ 和方差 $\mathbf{\Sigma }$（最初是标量）： $$\begin{array}{rl}\mathbf{\Sigma }& =[{\sigma }^{-2}{\mathbf{\Phi }}^{\mathrm{T}}\mathbf{\Phi }+\mathbf{A}{]}^{-1}\\ \mathbf{\mu }& ={\sigma }^{-2}\mathbf{\Sigma }{\mathbf{\Phi }}^{\mathrm{T}}\mathbf{t}\end{array}$$ 连同一起初始化其他基向量 ${\mathbf{\varphi }}_m$ 以及对应的 $s_m$ 和 $q_m$。

4）从具有 $M$ 个基向量的全部集合中选择候选基 ${\mathbf{\varphi }}_i$。

5）计算 ${\theta }_i=q_i^2-s_i$：

如果 ${\theta }_i>0$ 且 ${\alpha }_i<\infty$，更新估计 ${\alpha }_i$。如果 ${\theta }_i>0$ 且 ${\alpha }_i=\infty$，添加基向量 ${\mathbf{\varphi }}_i$ 并更新估计 ${\alpha }_i$。如果 ${\theta }_i\le 0$ 且 ${\alpha }_i<\infty$，删除基向量 ${\mathbf{\varphi }}_i$ 并设置 ${\alpha }_i=\infty$。

6） 估计噪声水平，更新其方差值 $${\sigma }^2=\frac{\Vert \mathbf{t}-\mathbf{\Phi }\mathbf{\mu }{\Vert }^2}{N-{\sum }_i{\gamma }_i}=\frac{\Vert \mathbf{t}-\mathbf{\Phi }\mathbf{\mu }{\Vert }^2}{N-M+{\sum }_m{\alpha }_m[\mathbf{\Sigma }{]}_{m,m}}$$

7）再次更新均值 $\mathbf{\mu }$ 和方差 $\mathbf{\Sigma }$，及所有的 $s_m$ 和 $q_m$。

8）判断是否收敛，收敛则算法结束，否则转到步骤（4）继续迭代。