GMM到Capsules with EM Routing

发布于 2021-01-20  1265 次阅读


前言

几乎全是纯数学推导,这篇文章看懂也让我理解到了在ML或者DL中数学的重要性(文章markdown与latex渲染出现问题,大括号消失了。。)

GMM和EM算法

1.混合模型(Mixture Model)

混合模型是一个可以用来表示在总体分布(distribution)中含有 K 个子分布的概率模型,换句话说,混合模型表示了观测数据在总体中的概率分布,它是一个由 K 个子分布组成的混合分布。混合模型不要求观测数据提供关于子分布的信息,来计算观测数据在总体分布中的概率。

2. 高斯模型

单高斯模型

当样本数据 X 是多维数据(Multivariate)时,高斯分布遵从下方概率密度函数:
$$
N(\boldsymbol{x};\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j)=\frac{1}{(2\pi)^{d/2}(\det\boldsymbol{\Sigma}_j)^{1/2}}\exp\left(-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu}_j)^{\top}\boldsymbol{\Sigma}_j^{-1}(\boldsymbol{x}-\boldsymbol{\mu}_j)\right)
$$
其中,$\mu_j$为数据均值(期望),$\Sigma_j$为协方差(Covariance),d为数据维度。

高斯混合模型

高斯混合模型可以看作是由 K 个单高斯模型组合而成的模型,这 K 个子模型是混合模型的隐变量(Hidden variable)。一般来说,一个混合模型可以使用任何概率分布,这里使用高斯混合d模型是因为高斯分布具备很好的数学性质以及良好的计算性能

对于已有的向量$x_1,…,x_n$,GMM设想这批数据能分为几部分(类别),每部分单独研究,也就是
$$
p(\boldsymbol{x})=\sum\limits_{j=1}^k p(j)p(\boldsymbol{x}|j)\tag{1}
$$
其中$j$代表了类别,取值为$1,2,…,k$,由于$p(j)$跟$x$没关系,因此可以认为它是个常数分布,记$p(j)=π_j$。然后$p(x|j)$就是这个类内的概率分布,因为$x_i$服从高斯分布,而其是多维向量,所以它的概率密度函数为
$$
N(\boldsymbol{x};\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j)=\frac{1}{(2\pi)^{d/2}(\det\boldsymbol{\Sigma}_j)^{1/2}}\exp\left(-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu}_j)^{\top}\boldsymbol{\Sigma}_j^{-1}(\boldsymbol{x}-\boldsymbol{\mu}_j)\right)\tag{2}
$$

现在我们得到模型的基本形式

$$
\begin{aligned}p(\boldsymbol{x})=\sum\limits_{j=1}^k p(&j)\times p(\boldsymbol{x}|j)=\sum\limits_{j=1}^k\pi_j N(\boldsymbol{x};\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j)\\
\downarrow& \qquad\,\,\downarrow\\
\pi_j& \,\,\cdot\,\, N(\boldsymbol{x};\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j)
\end{aligned}\tag{3}
$$

3.求解

首先根据贝叶斯模型得到
$$
p(j|\boldsymbol{x})=\frac{p(\boldsymbol{x}|j)p(j)}{p(\boldsymbol{x})}=\frac{\pi_j N(\boldsymbol{x};\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j)}{\sum\limits_{j=1}^k\pi_j N(\boldsymbol{x};\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j)}\tag{4}
$$

根据正态分布性质得到

$$
\boldsymbol{\mu}_j = \int p(\boldsymbol{x}|j)\boldsymbol{x}d\boldsymbol{x}=\int p(\boldsymbol{x}) \frac{p(j|\boldsymbol{x})}{p(j)}\boldsymbol{x}d\boldsymbol{x}=E\left[\frac{p(j|X)}{p(j)}X\right]\tag{5}
$$

对于离散型随机变量期望定义得到
$$
\boldsymbol{\mu}_j = \frac{1}{n}\sum\limits_{i=1}^n \frac{p(j|\boldsymbol{x}_i)}{p(j)}\boldsymbol{x}_i = \frac{1}{\pi_j n}\sum\limits_{i=1}^np(j|\boldsymbol{x}_i)\boldsymbol{x}_i\tag{6}
$$
对于协方差矩阵,我们得到
$$
\boldsymbol{\Sigma}_j = \frac{1}{\pi_j n}\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)(\boldsymbol{x}_i-\boldsymbol{\mu}_j)(\boldsymbol{x}_i-\boldsymbol{\mu}_j)^{\top}\tag{7}
$$
然后
$$
\pi_j = p(j) = \int p(j|\boldsymbol{x})p(\boldsymbol{x})d\boldsymbol{x}=E\left[p(j|X)\right]\tag{8}
$$
所以
$$
\pi_j = \frac{1}{n}\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)\tag{9}
$$

理论上,我们需要求解(4),(6),(7),(9)构成的一个巨大的方程组,但这样是难以操作的,因此我们可以迭代求解,得到迭代EM算法:

$$
\text{EM算法1}:
\begin{aligned}
&p(j|\boldsymbol{x}_i) \leftarrow \frac{\pi_j N(\boldsymbol{x}_i;\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j)}{\sum\limits_{j=1}^k\pi_j N(\boldsymbol{x}_i;\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j)}\\
&\boldsymbol{\mu}_j \leftarrow \frac{1}{\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)}\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)\boldsymbol{x}_i\\
&\boldsymbol{\Sigma}_j \leftarrow \frac{1}{\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)}\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)(\boldsymbol{x}_i-\boldsymbol{\mu}_j)(\boldsymbol{x}_i-\boldsymbol{\mu}_j)^{\top}\\
&\pi_j \leftarrow \frac{1}{n}\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)
\end{aligned}
$$

上述迭代过程先将(9)式作了恒等变换然后代入(6),(7)式。在上述迭代过程中,第一式称为EE步,后三式称为MM步,整个算法就叫做EM算法

在Capsule中实际上使用了一种更加简单的GMM形式,认为各个分量是独立的,(2)式就变为

$$
N(\boldsymbol{x};\boldsymbol{\mu}_j,\boldsymbol{\sigma}^2_j)=\prod_{l=1}^d\frac{1}{\sqrt{2\pi}\sigma_j^{l}}\exp\left(-\frac{1}{2(\sigma_j^{l})^2}(x^{l}-\mu_j^{l})^2\right)\tag{10}
$$

而迭代过程也有所简化:

$$
\text{EM算法2}:\begin{aligned}
&p(j|\boldsymbol{x}_i) \leftarrow \frac{\pi_j N(\boldsymbol{x}_i;\boldsymbol{\mu}_j,\boldsymbol{\sigma}^2_j)}{\sum\limits_{j=1}^k\pi_j N(\boldsymbol{x}_i;\boldsymbol{\mu}_j,\boldsymbol{\sigma}^2_j)}\\
&\boldsymbol{\mu}_j \leftarrow \frac{1}{\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)}\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)\boldsymbol{x}_i\\
&\boldsymbol{\sigma}^2_j \leftarrow \frac{1}{\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)}\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)(\boldsymbol{x}_i-\boldsymbol{\mu}_j)^2\,[\text{逐位平方}]\\
&\pi_j \leftarrow \frac{1}{n}\sum\limits_{i=1}^n p(j|\boldsymbol{x}_i)
\end{aligned}
$$

Capsules with EM Routing

首先,我们用一个矩阵$P_i$来表示第$l$层的Capsule,这一层共有$n$个Capsule,也就是$i=1,…,n$;用矩阵$M_j$来表示第$l+1$层的Capsule,这一层共有$k$个Capsule,也就是聚为$k$类,$j=1,…,k$。论文中Capsule的矩阵是$4×4$的,称之为Pose矩阵。然后呢,就可以开始GMM的过程了,在做GMM的时候,又把矩阵当成向量了,所以在EM路由那里,$P_i$就是向量,即$d=16$。整个过程用的是简化版的GMM,也就是把协方差矩阵约定为一个对角阵

所以根据前面的讨论,可以得到新的动态路由算法
$$
\text{新动态路由1}:\begin{aligned}
&p_{ij} \leftarrow N(\boldsymbol{P}_i;\boldsymbol{\mu}_j,\boldsymbol{\sigma}^2_j)\\
&R_{ij} \leftarrow \frac{\pi_j p_{ij} }{\sum\limits_{j=1}^k\pi_j p_{ij} },\,\,r_{ij}\leftarrow \frac{R_{ij}}{\sum\limits_{i=1}^n R_{ij}}\\
&\boldsymbol{M}_j \leftarrow \sum\limits_{i=1}^n r_{ij}\boldsymbol{P}_i\\
&\boldsymbol{\sigma}^2_j \leftarrow \sum\limits_{i=1}^n r_{ij}(\boldsymbol{P}_i-\boldsymbol{M}_j)^2\\
&\pi_j \leftarrow \frac{1}{n}\sum\limits_{i=1}^n R_{ij}
\end{aligned}
$$
动态路由的思想都是将l+1层的Capsule作为l层Capsule的聚类中心

在这篇文章中Capsule的模长已经没法衡量特征的显著性了,那么就只好多加一个标量$a$来作为该Capsule的显著性。所以,这篇论文中的Capsule,实际上是“一个矩阵 + 一个标量”,这个标量被论文称为“激活值”,

作为Capsule的显著程度,$a_j$最直接的选择应该就是$π_j$,因为$l+1$层的Capsule就是聚类中心而$π_j$就代表着这个类的概率

但是未选择的原因有一点(类似yolo的输出并不需要归一化)

  1. $π_j$是归一化的,而我们希望得到的只不过是特征本身的显著程度,而不是跟其他特征相比后的相对显著程度
  2. 作者还考虑了信息熵的改变,所以没有直接选用$π_j$

$a_j$的计算如下
$$
a_j=logistic\left(\lambda\left(\beta_a-\beta_u\sum\limits_i R_{ij}-\sum\limits_h cost_j^h\right)\right)\tag{11}
$$
其中信息熵就是
$$
\begin{aligned}cost_j^h =& - \int p(\boldsymbol{x}|j)\ln p(\boldsymbol{x}|j)d\boldsymbol{x}\\
=& - \frac{1}{p(j)}\int p(j|\boldsymbol{x})p(\boldsymbol{x})\ln p(\boldsymbol{x}|j)d\boldsymbol{x}\\
=&- \frac{1}{p(j)} E\left[p(j|\boldsymbol{x})\ln p(\boldsymbol{x}|j)\right]\\
=&-\frac{1}{n\pi_j}\sum\limits_{i=1}^n R_{ij}\ln p_{ij}\\
=&-\frac{1}{\sum\limits_{i=1}^n R_{ij}}\sum\limits_{i=1}^n R_{ij}\ln p_{ij}\\
=&-\sum\limits_{i=1}^n r_{ij}\ln p_{ij}\end{aligned}\tag{12}
$$
$(11)$中$β_a$,$β_u$通过反向传播优化,而$λ$则随着训练过程慢慢增大

作者使用$a_j$替换掉$\pi_j$,得到新的路由计算
$$
\text{新动态路由2}:\begin{aligned}
&p_{ij} \leftarrow N(\boldsymbol{P}_i;\boldsymbol{\mu}_j,\boldsymbol{\sigma}^2_j)\\
&R_{ij} \leftarrow \frac{a_j p_{ij} }{\sum\limits_{j=1}^k a_j p_{ij} },\,\,r_{ij}\leftarrow \frac{R_{ij}}{\sum\limits_{i=1}^n R_{ij}}\\
&\boldsymbol{M}_j \leftarrow \sum\limits_{i=1}^n r_{ij}\boldsymbol{P}_i\\
&\boldsymbol{\sigma}^2_j \leftarrow \sum\limits_{i=1}^n r_{ij}(\boldsymbol{P}_i-\boldsymbol{M}_j)^2\\
& cost_j \leftarrow \left(\beta_u+\sum\limits_{l=1}^d \ln \boldsymbol{\sigma}_j^l \right)\sum\limits_i r_{ij} \\
& a_j \leftarrow sigmoid\left( \lambda \left(\beta_a - cost_j\right)\right)
\end{aligned}
$$

随后作者将上一层的激活值插入到$r_{ij}$

$$
\text{新动态路由3}:\begin{aligned}
&p_{ij} \leftarrow N(\boldsymbol{P}_i;\boldsymbol{\mu}_j,\boldsymbol{\sigma}^2_j)\\
&R_{ij} \leftarrow \frac{a_j p_{ij} }{\sum\limits_{j=1}^k a_j p_{ij} },\,\,r_{ij}\leftarrow \frac{a_i R_{ij}}{\sum\limits_{i=1}^n a_i R_{ij}}\\
&\boldsymbol{M}_j \leftarrow \sum\limits_{i=1}^n r_{ij}\boldsymbol{P}_i\\
&\boldsymbol{\sigma}^2_j \leftarrow \sum\limits_{i=1}^n r_{ij}(\boldsymbol{P}_i-\boldsymbol{M}_j)^2\\
& cost_j \leftarrow \left(\beta_u+\sum\limits_{l=1}^d \ln \boldsymbol{\sigma}_j^l \right)\sum\limits_i r_{ij} \\
& a_j \leftarrow sigmoid\left( \lambda \left(\beta_a - cost_j\right)\right)
\end{aligned}
$$

到这里其实这篇论文的数学推导也就止步于此了,接下来是一些恒等变换比如相乘视觉不变矩阵等等,不再赘述

自我思考

虽然Hinton大佬在2020发表演讲说之前的论文都是错的(笑),但是这种削弱了反向传播而应用聚类的思想是值得借鉴的,在他的最新的篇中使用了Transformer,提到了一个很有意思的概念:Coincidence Fitering,指出了现在的CNN的问题并没有很好的利用--偶然性过滤,但是Transformer的注意力机制中体现出了偶然性过滤,继续思考叭。