A new guy dedicates to computer vision, especially object detection, pose estimation.

模型构建

最近 SE-net, Non-local, GLoRe, GC-net, 的出现，我们开始更多的通过显式的约束来构建网络结构。其实这种通过显式的约束来构建模型的方式，例如通过显式的可变性模块构建空间关系的 Deformable conv.

仿射变换（全局模式，局部模式）

其实在构建网络的时候，我们有很多显式的约束，例如图像空间中物体的仿射变换：

• 多尺度
• 旋转
• 平移

在网络中多尺度，可以被不同大小的卷积核近似模仿，而最近的trident-net，用了共享权值的多尺度网络更合理的解决了多尺度问题。并且最近的octava conv slow-fast 也可以看作一种不同尺度的建模。可变性卷积可以看作是图像空间的仿射变换的拆分。

语义相关性

在构建网络中除了我们关注物体的空间表现形式。我们往往还会关心图像中物体的相互关系，或者是不通层次的语义之间的关系，或者同一层次语义之间关系。那么这里我们就引出了三个我们想要建模的概念：

• 图像中语义的空间关系
• 同一层次的语义之间的关系
• 不同层次的语义之间的关系

这里我们定义一些符号 $f \in R^{c \ast h \ast w}$ 的三维的向量，这里我们对这个原始特征进行变形为 $nf \in R^{c \ast hw}$.
那么图像内部的空间关系的构建，也是是我们所说的 non-local net, 通过枚举图像中所有空间位置之间的相互关系，对相关的特征进行聚合，获得最终的特征表达。大致可以表示为：
$$ff=nf \ast softmax_{c=1}(nf^T \ast nf) +nf$$

那SE_net描述的同一层次的语义相关性，或者也可以认为是注意力机制：
$$ff= \Theta (\max_{c=1}(nf) \times f$$
这里的 $\Theta$ 对通道之间的关系进行建模，以此获得更重要的通道。

在GC-net中，空间的约束并不是non-local，因为non-local的计算量是非常大的，尤其是当特征图的特别大的时候，所以在GC中可以看作一种自注意力机制，有点像CAM之类的东西，并没有对图像中内部关系进行建模。但是这样做的好处就是有效的降低了计算量。

其实在分类问题中，我们应该更深入的思考问题，空间的相关性，和特征的相关性怎样才能更好的被建模。

• 建模什么样的空间相关性？
• 语义之间的相关性怎么建模？被用来干什么？

空间的相关性，被用来做什么?

在视频的理解过程中，空间的相关性一般被用来对相邻帧内部的物体的相关性进行建模的，类似轨迹聚类这种。但是在图像的分类中，空间聚类被用来干什么。从可变性卷积，我们看一看到空间的相关性，很多时候是物体的共生性，也就是同一个物体的不同的part之间的共生性，或者是其他更多语义上的共生性，这种共生性在语义上可能并不具有non-local中的特征相似性。所以对这种建模，更好的方式进行建模。

语义之间的相关性怎么建模？被用来干什么？

在SE_net中，使用的 $\Theta$ 是对通道之间的相关性进行建模的，可是这个相关性是什么呢？ 其实并没有很好的回答。那么怎么才能更好的理解这种相关性呢？

同一层次的语义之间的关系，我最先想到的就是 GRAM matrix, bilinear pooling，style transfer中使用作为图像的有效表达。大致可以表示为：
$$ff=nf \ast nf^T$$
这里很好的保存了不同通道之间的相关性，这个和non-local看着十分相似。

假设 1. 相关性大特征对分类更加有效，相当于对细小特征空间的细分，所以应该加强这部分的特征。

假设 2. 相关性大的特征影响了空间的分布，我们应该使得空间更加的均匀，所以应该抑制。

那么我们有了相关性，有了语义的相关性，和两个假设我们应该怎么对这些特征进行建模呢？

$$ff= sigmoid(\Phi \sum_{c=1}(nf \ast nf^T)) \times f$$

或者是
$$ff= (1-sigmoid(\Phi \sum_{c=1}(nf \ast nf^T))) \times f$$

有效性的问题是遏制Gram矩阵模块化的最主要的问题，计算量很大，但是我们可以通过降低resolution来提高效率。

起源

当很多的概念放在一起的时候，我们一般会怎么看待这些语义呢？很多时候我们并不关系这些语义之间是否有关系，或者说语义之间的关系并不需要我们作为一种监督信号或者是学习规则加入到整个模型中。例如在物体识别中，我们并不关心语义之间的关系，而是建立一个统一的模型。虽然我们最终的特征中蕴含了这种语义的结构信息，但是这还是不够明显的。怎么去显式的表示这种语义的结构，并能很好的去运用它，这就是我的目的。

物体模型

在物体的模型中，尤其是部件模型，是对语义建模的最好的显式表达。从DPM开始的星型结构模型等一系列的工作，我们可以很好的感受，概念之间的结构化关系，而这种结构化关系又很好的辅助了任务的完成。还有 and-or图，这种语义结构构建规则，在很多方面已经得到了很好的应用。

上下文

随着深度模型的不断发展，而深度模型通过简单的卷积结构并不能很好的利用深度特征。而上下文，也就是特征中空间相关的特征的推理，并不能有效的被卷积建模。所以在这个过程需要显式的规则（机制）的约束，才能更有效的建模上下文信息。

注意力

除了上下文，注意力可以看作是上下文的另一个代名词。注意力在最开始的时候是强调不通过模态之间的关联性的，但是随着注意力机制被广泛运用在不同的领域，自注意力在单一任务中被大量使用。其实，自注意力可以说是一种上下文建模的机制。

多任务学习

多任务学习，就是将不同的任务融合如统一的一个框架。而任务之间的关系决定了这些任务能不能融合，应该怎么融合。

多监督

同一个任务，为了使得模型获得更好的结构，我们通常会迭代的优化。而对于有监督的学习，我们通常会设计更多的监督信号去使得这个模型能逐步的缩小误差。或者我们加入的监督信号并不是一样的，这样能使得模型更好的学习目标。

在这些问题中，语义的结构是至关重要的。无论是以显式的监督信号，还是以规则的方式，都对最终的任务起到重要的影响因素。

constrain

就像我们往常一样，我们这里从一个最实际的例子来进行切入。本文的行文主要是借鉴 Tibshirani 的 lasso 的那篇论文进行介绍的。

回归问题在计算机视觉这个领域是非常非常重要的一个问题。对于一个实际应用的问题，如何设计 loss function 可以说是对问题很好的阐述。而我们最常使用的回归函数主要是：
（1）最小均方，
（2） logistic 回归。本文这里主要从最小均方误差进行切入。

还有就是这里并不着重介绍如何去设计一个损失函数，这里主要是关注一个问题的约束项，也可以说是正则项。需要注意的是，这里要把约束和先验好好地区分一下。大致目的已经阐述完了，我们下面开始进入正题吧。

OLS估计

OLS 估计，也就是 ordinary least square 估计。为了很好的阐述这个问题，我们来定义一下这个问题吧。给定一个$Y$回归子（我们可以认为是数据的标签，或是待表示的数据），一个数据（或是一组基，码本，聚类中心等）$X$，我们需要最小化这个问题：
\begin{equation}\label{OLS}
\beta=argmin_\beta || Y - \beta X ||_F^2
\end{equation}

这就是原始的最小均方估计的形式了，这个问题是有解析解的，这里我们使用$\beta^0$来表示。
\begin{equation}\label{beta0}
\beta^0=(X^T X)^{-1} Y X^T
\end{equation}

但是问题不能简简单的就这么解决了，毕竟问题往往不像是看起来这么简单。

第一个问题：prediction accuracy这里主要涉及的问题就很多了。首先是数据的问题，数据很可能是一个非常相关的（可以说是低秩的），还有就是噪声的问题。还有就是 OLS 通常具有很小的偏置却又很大的方差，也就是我们所说的 overfitting 。

第二个问题：interpretation问题学习到的参数通常是 dense 的，就是说，一个回归子需要很多参数的作用，这样就很难解释到底是在这个问题中起到更重要的作用。利用我们的直觉，我们一般也会认为只有少量的变量才会起到很重要的作用。

before lasso

根据这些问题，前人做了一些列的改进，还有一些问题的重新阐述，定义。下面我们先介绍 lasso 诞生之前的一些解决方案：
（1）subset selection
（2）ridge regression
（3）non negative garotte

subset selection

这个问题来源于矩阵的表示：怎么用原始矩阵中的一些列来表示原来的矩阵，使得误差最小。下面我们用公式可以表示为：
\begin{equation}\label{ss}
A \prod = (A_1 A_2)
\end{equation}

这里的$\prod$是一个置换矩阵，什么意思呢？就是说，我们从原始矩阵中选取一些列组合成矩阵$A_1$，剩下的组合成矩阵$A_2$。然后我们最小化函数：
\begin{equation}\label{ss2}
|| A_1 z - A_2 ||_F^2
\end{equation}

这里我还没有看完就不细说了，不过这个通过数据本身的特性，来进行数据的选取，可以用来 unsupervised feature selection 。

但是这个算法还是存在很多问题的： subset selection 很好的的为模型提供了解释性，但是由于是知识从原来的矩阵选取一个一些列，也就是扔掉一些列，这即使得选取的过程造成这个模型的不鲁棒，同时还降低了预测精度。

ridge regression

这个使我们最熟悉不过的东西了，几乎可以说是无处不在。这个在避免模型过拟合时，最常使用了。那我们就来看看为什么这个会避免过拟合。根据我的习惯，我们还是从函数来看：
\begin{equation}
\begin{split}\label{ridre}
\beta &= argmin_\beta ||Y - \beta X ||_F^2\\
&subject to:\sum ||\beta_j || \leq t
\end{split}
\end{equation}
一般我们还会写作：
\begin{equation}\label{rigre2}
\beta = argmin_\beta ||Y - \beta X ||_F^2 + \lambda || \beta ||
\end{equation}

如果我们使用拉格朗日乘子法，可以发现这两问题是等价的，但是这里肯定是在$t$在某个条件下等价的，这里就不在这里一一赘述了。

PS ：为了表示方面我们这里假设$X$矩阵是规范正交矩阵，也就是说$X^T X = I$对于实际中，这个也是能获取的，例如降维的时候，我们使用 PCA 获取的就是正交基。也就是说之前的$$\beta^0 = Y X^T $$。

那么经过二范数的约束的岭回归的解和原来的 OLS 的解之间有什么关系呢？下面我们给出 Tibshirani 给出的结果：
\begin{equation}\label{ridge-ols}
\beta^2_j=\left( \frac{1}{1+\lambda}\right)\beta^0
\end{equation}

如下图：

The parameters in ridge regression is linearly scaling the OLS

我们可以看到这个问题对参数有了很好的抑制，但是这里的参数还是很 dense 的，因为这里实现了一个缩放的功能，还是不能提供一个很 easily 的解释性。

non negative garotte

这也是比较陌生的东西，因为这个比一般的回归多了一些参数，估计这也是不受大众欢迎的原因吧。那这个东西就近是什么东西呢。来看一下定义吧。
\begin{equation}
\begin{split}\label{garotte}
\beta &= argmin_\beta ||Y - C \beta^0 X ||_F^2\\
&subject to:C_j \geq 0 \sum C_j \leq t
\end{split}
\end{equation}

这里可以看做是对原有的参数的一些缩放，这里可以起到一些参数的抑制的作用。那这里的参数和之前的参数有什么关系呢？

\begin{equation}\label{ridgess-ols}
\beta^g_j=\left( 1-\frac{\lambda}{||\beta^0||}\right)^+\beta^0
\end{equation}

如下图：

The parameters in garotte regression is nonlinearly scaling the OLS

这个抑制已经很接近 lasso ，那我们来看看最后，但是由于这个$C$即取决于原始参数的方向，还取决于其大小，这样的结果是不是很理想的。

lasso

lasso 其实是 least absolute shrinkage and selection operator 。就是字面意思了。问题可以简单的定义为：
\begin{equation}
\begin{split}\label{lassoeq}
\beta &= argmin_\beta ||Y - \beta X ||_F^2\\
&subject to:\sum |\beta_j | \leq t
\end{split}
\end{equation}

这里的参数和之前的参数有什么关系呢？
\begin{equation}\label{l-ols}
\beta^l=sign(\beta^0)(|\beta^0|-\lambda)^+
\end{equation}

如图所示：

The parameters in lasso regression is nonlinearly scaling the OLS

这个就可以很容易的看出这个这个的抑制效果比之前的几种方法都好。

下面我们来证明一下这个$\beta^1$和$\beta^0$之间的关系。由于一范数存在没有单数的点，所以这里我们要给出几个定义。

Definition.1 （subgradient;subdifferential）对于在$p$ 维欧式空间中的凸开子集$\mathcal{U}$上定义的实值函数$f:\mathcal{U}\rightarrow \mathbb{R}$，一个$p$ 维向量$v$称为$f$在点$x_0 \in \mathcal{U}$处的$subgradient$，对于任意的$x \in \mathcal{U}$，满足：
$$ f(x) - f(x_0) \geq v \cdot (x- x_0)$$
由在点$x_0$出所在的$subgradient$所组成的集合称为$x_0$处的$subdifferential$，记作$\partial f(x_0)$。

这里我们讨论的是凸函数，一范数的情况下，我们来看一个简单地一维的情况$f(x)=|x|$，在$x=0$这个点的$subgradient$在$[-1,+1]$这个区间里。

根据这个概念，我们来定义一个全局最优的新定义：

Definition.2（condition for global minimizer）点$x_0$是凸函数$f$的一个全局最小点，当且仅当$0 \in \partial f(x_0)$。

既然做了这么多的铺垫，那我们就开始我们的证明。

首先我们来回忆一下我们的在最小二乘的时候的解是$\beta^0=Y X^T$。由于是一范数我们来分情况证明这个问题吧：

（1）$gradient$存在，也就是说这一点$\overline{\beta}_j \neq 0$:

\begin{equation}\label{r1}
\frac{\partial f(x_0)}{\partial \beta_j} \big |_{\overline{\beta}_j}=0
\end{equation}

也就是说：

\begin{equation}\label{r2}
-2(Y X^T - X^T X \overline{\beta})_j+\lambda sign(\overline{\beta}_j)=0
\end{equation}

然后根据我们之前的正交化的工作，我们可以得到：

\begin{equation}\label{r3}
\overline{\beta}_j=\beta_j^0-\frac{\lambda}{2}sign(\overline{\beta}_j)
\end{equation}

根据这个公式，我们可以很容易的证明一个现象，那就是$\overline{\beta}_j$和$\beta_j^0$是同号的。也就是说：

\begin{equation}\label{r4}
\overline{\beta}_j=sign(\beta_j^0)\left(|\beta_j^0|-\frac{\lambda}{2}\right)=sign(\beta_j^0)|\overline{\beta}_j|
\end{equation}

然后呢，我们就可以得到一个很直观的结果：

\begin{equation}\label{r5}
|\beta_j^0|-\frac{\lambda}{2}=|\overline{\beta_j^0}| \geq 0
\end{equation}

所以呢，在梯度存在的情况下，我们得到的是这样的的结果：

\begin{equation}\label{r6}
\overline{\beta}_j=sign(\beta_j^0)\left( |\beta_j^0 | -\frac{\lambda}{2} \right)_+
\end{equation}

（2）$gradient$不存在，这个时候$\overline{\beta}_j=0$：

这个时候我们就可以用到我们之前的那两个定义了：
\begin{equation}\label{rr6}
\begin{split}
0&=\overline{\beta}_j=\partial f(x_0)={-2(Y X^T -X^T X \overline{\beta})_j+\lambda e:e \in[-1,+1]}\\
&={2\overline{\beta}_j-2\beta_j^0+\lambda e:e\in[-1,+1]}
\end{split}
\end{equation}

然后我们还知道$\overline{\beta}_j=0$，
于是乎：

\begin{equation}\label{r7}
|\beta_j^0|=\frac{\lambda}{2}|e_0| \leq \frac{\lambda}{2} e_0\in[-1,+1]
\end{equation}

然后我们把这两部分统一起来就得到了上面我们我们的所画的图。

Norm ball

下面我们用一个很直观的形式来讲解这些之间的问题。那就是 Donoho 大牛提出了一个很有趣的东西： Norm ball 。其实就是范数的等高线。那我们就来看看这个等高线到底长什么样子呢？

L4,L2,L1,L0.5 Norm ball

Donoho 给了我们一个直观的方式去选着我们需要的约束，为什么这个说，如果我们在这里显式的给出能量函数的等高线，就会一目了然了。我在这里就简要介绍这些问题吧。但是我们通过观测得到一些结论

L1 和 L0.5 范数的图像是具有“尖”的，而且这些“尖”位于坐标轴上，也就是说具有这种性质的是具有稀疏性约束的。$[0,1]$之间的范数都具有稀疏性，现在也有人在研究这些范数，这里就不一一给出了。

L2 范数是不具有上面的性质的，因为这个 Norm ball 是极致光滑的，用一个很形象的描述就是这个范数不偏向任何一方，各个分量的比值只和能量函数的中心有关。

还有就是 L4 范数，这个范数可以看到和 L1 范数有个可以说是相反的约束，这个范数更希望这个分量是均匀，也就是每一个分量尽可能的差不多。

PS： 这里我就不列文献了$>. <$。

RBM

RBM 也就是 Restricted Boltzmann Machine ，这个概念由来已久了。我是在《人工神经网络》课上对这个有了一些了解。这个问题之前我知道，是来源于 DBN 的 pretrain 和 DBMs 。在深度学习中， RBM 可以说是具有很强的推动作用，记得上《模式识别》课时，老师在讲到深度神经网络使用 BP 算法的时候出现 Gradient vanish ，导致深度的网络是无法训练的， RBM 的可以说是作为训练 DBN 的救世主的形象出现的，通过 RBM 进行 pretrain 可以有效的解决 Gradient vanish 的问题。所以说这个 RBM 是个很重要的概念，那我们来看看这个东西吧。

Structure

RBM structure

玻尔兹曼机是一个双层的，层间是一个全连的结构，层内也是全连的结构，但是这个是一个很复杂的结构。秉着简化模型的理念，就出现了限制玻尔兹曼机，限制就是去掉层内部的链接，简化了之后的模型看起来就很想我们常见的神经网络的模型。如上图所示，我们可以看出这个结构和我们所接触的前馈的神经网络还是有所不同的，因为层间的链接是一个无向边，也就是说这是一个对传的网络结构。

我认为去掉层内之间的链接，就使得，这个模型不在 model 一个观测里面各个特征之间的关系，而是 model 观测和观测之间的关系，所以这个模型可以看作是无监督的特征的提取。

但是我们还有走的稍微深入一点，来追根溯源一下，这个模型本来是来自什么地方呢。

Dynamic system

这个问题可以追溯到动态系统那个地方去，为什么这么说呢？其实我也不知道，《人工神经网络》课上老师告诉我的。所以我们就用动态系统，或者暂时把自己当做是控制系的学生来看看这个问题吧。

第一个重要的理论是 lyapunov function ，这个函数可以说是动态系统的一个最重要的指标了。为什么这么说呢？因为这个函数定义了一个动态系统稳定的条件。下面我们就来看看到底是怎么定义的吧。

对于一个动态系统，我们都可以定义一个能量函数$\mathcal{U}$，如果一个系统：
$$\frac{\partial \mathcal{U}}{ \partial t } \leq 0$$

我们就说这个系统是稳定的，也就是说在经过一段时间后这个是同会收敛到稳定状态。这里需要注意的是这里的是能量函数对时间的导数，这里描述的是一个动态的变化的量之间的关系。

但是我们要用我们机器学习的观点来看这个问题，一般我们搞出一个模型，是必要伴随着参数学习的过程。也就是说，我们的模型变化的是参数，是参数在随着时间在变化，那我们怎么把上面的问题迁移到我们的问题上呢？数学上对这个已经有很好的办法了那就是链式求导法：
$$\frac{\partial \mathcal{U}}{ \partial t } =\frac{\partial \mathcal{U}}{ \partial \omega } \frac{\partial \omega}{ \partial t } \leq 0 $$。

这样我们就很好的对应到我们学习的过程中了，$\frac{\partial \mathcal{U}}{ \partial \omega }$是我们设计的能量函数对参数的固有导数，$\frac{\partial \omega}{ \partial t }$是我们学习过程中参数的变化过程。

知道了这么多了，我们来 specialized 这个模型到 RBM 。

Prove the stability of RBM

第一步，我们来定义 RBM 的能量函数：
$$\mathcal{U}=-\sum_{j \in \mathbb{V}}a_j v_j - \sum_{i \in \mathbb{H}} b_i h_i -\sum_{i \in \mathbb{H},j \in \mathbb{V}}v_j w_{ji} h_i$$

下面我们就来 证明这个系统的稳定性。 PS ：这里用到的参数更新的公式来至于 Hinton 老爷子关于 RBM 的文章。

（1）让我们来看第一个参数$b$:
\begin{equation}\label{st}
\begin{split}
\frac{\partial \mathcal{U}}{ \partial a_j } & =-v_j^k \
\frac{\partial a_j}{ \partial t } & =v_j^k-v_j^{k+1}\
\frac{\partial \mathcal{U}}{ \partial t } & = \frac{\partial \mathcal{U}}{ \partial a_j } \frac{\partial a_j}{ \partial t }
=-v_j^k(v_j^k-v_j^{k+1})
\end{split}
\end{equation}

那我们就讨论一下这个东西到底是不是小于等于0的。首先需要知道的是这个网络是二值的网络，也就是说 v,h 的取值是在 { 1,0} 的。所以：

1.$v_j^k=0$，这个我们可以很轻松的得到：

$$\frac{\partial \mathcal{U}}{ \partial t } =\frac{\partial \mathcal{U}}{ \partial a_j } \frac{\partial a_j}{ \partial t }=0(0-v_j^{k+1})=0 \leq 0$$

2.$v_j^k=1$，然后，无论$v_j^{k+1}$取什么值，$v_j^k-v_j^{k+1} \geq 0$，同样我们也就知道了：

$$\frac{\partial \mathcal{U}}{ \partial t } =\frac{\partial \mathcal{U}}{ \partial a_j } \frac{\partial a_j}{ \partial t }=-1(v_j^k-v_j^{k+1}) \leq 0$$

同理，我们可以证明$\frac{\partial \mathcal{U}}{ \partial b_j } \frac{\partial b_j}{ \partial t }$和$\frac{\partial \mathcal{U}}{ \partial w_{ji} } \frac{\partial w_{ji}}{ \partial t }$都是满足之前我们定义的稳定性的条件的。

既然我们知道了这个系统的稳定性了，那我们就转换一下身份吧，不要再用动态系统的观点来看这个问题了。下面我们将从概率的角度来看这个问题。

Why it call Boltzmann?

这个我记得，我上物理课的时候，听说了波尔兹曼分布这个东西。感觉就是一个和一个系统的能量有关的概率问题。那我们就定义一下在这里的概率分布：
\begin{equation}\label{blz}
P(v,h)=\frac{1}{\mathcal{Z}} e^{-\mathcal{U}}
\end{equation}

由于这里涉及的是概率的问题，所以毫无疑问是要归一化的$\mathcal{Z}$就是归一化因子。
\begin{equation}\label{zz}
\mathcal{Z}=\sum_{v,h}e^{-\mathcal{U}}
\end{equation}

用概率的观点来看问题，一切就变得奇怪起来了。以前，我们知道了$v$就可以根据非线性变换就可以得到$h$了，但是现在不是这样了，我们根据概率$P(h=1 \mid v)$来得到$h$。所以我就说，一切变得奇怪起来了。

既然是要按照一定的概率来更新，那我们就得知道这个概率到底是什么呢？好吗，那我们来推导一下：
\begin{equation}\label{w3}
\begin{split}
P(h_i=1 \mid v)
&= P(h_i=1 \mid h_{-i},v) \\
& =\frac{P(h_i=1 , h_{-i},v)}{P(h_{-i},v)}\\
&=\frac{P(h_i=1 , h_{-i},v)}{P(h_i=1 , h_{-i},v) + P(h_i=0 , h_{-i},v)}\\
&=\frac{\frac{1}{\mathcal{Z}}e^{\mathcal{H}_{-i} +(b_i+\sum_j v_j w_{ji})}}
{\frac{1}{\mathcal{Z}}e^{ \mathcal{H}_{-i}+(b_i+\sum_j v_j w_{ji})}+\frac{1}{\mathcal{Z}}e^{ \mathcal{H}_{-i}+0}}\\
&=\frac{1}{1+e^{-(b_i+\sum_j v_j w_{ji})}}\\
&=sigmoid(b_i+\sum_j v_j w_{ji})
\end{split}
\end{equation}

其中：
\begin{equation}\label{w5}
\mathcal{H}_{-i}=\sum_{j \in \mathbb{V}}a_j v_j + \sum_{i \in \mathbb{H}-h_i} b_i h_i +\sum_{i \in \mathbb{H}-h_i,j \in \mathbb{V}}v_j w_{ji} h_i
\end{equation}

同理可证：
\begin{equation}\label{w4}
P(v_j=1 \mid h)=sigmoid(a_j + \sum_i w_{ji}h_i)
\end{equation}

写了这么多，感觉跟饶了一大圈又回到了原点一样。多眼熟的 sigmoid 函数，但是在这里是不一样的，这里是不一样的，这里的输出不是 sigmoid 的输出，这里的 sigmoid 代表的是输出为1的概率，输出到底是什么呢？这样牵扯概率的更新，一下子就与众不同了。

Loss function

但是我们这里并不是关注的礼盒概率分布$P(v,h)$，我们关注的是$P(v)$这个边缘概率分布，换句话说，这个$P(v)$才是我们的 Loss function 。我们在这就不证明了，直接给我结果：
\begin{equation}\label{7}
P(v)=\sum_h P(v,h)=\frac{1}{\mathcal{Z}} \prod_{j \in \mathbb{V}}e^{a_j v_j} \prod_{i \in \mathbb{H}}(1+e^{b_i + \sum_{j \in \mathbb{V}}v_j w_{ji}})
\end{equation}

但是我们并不喜欢这样连乘的损失函数，我们希望是求和式，这里就对$P(v)$取对数：
\begin{equation}\label{8}
\mathcal{L}(\omega)=\ln P(v) =\sum_{j \in \mathbb{V}} e^{a_j v_j} + \sum_{i \in \mathbb{H}} \ln(1 + e^{b_i + \sum_{j \in \mathbb{V}} v_j w_{ji}})-\ln (\mathcal{Z})
\end{equation}

根据梯度下降法：
$$\omega^k =\omega^{k-1}+ \eta\frac{\partial \mathcal{L}(\omega)}{\partial \omega}$$

我们就可以得到我们想要的各个参数的梯度变化值，这里就不一一证明了：
\begin{equation}\label{9}
\frac{\partial \mathcal{L}(\omega)}{\partial w_{ji}}=P(h_i=1 \mid v)v_j-\sum_{j \in \mathbb{V}} P(v)P(h_i=1 \mid v) v_j
\end{equation}

\begin{equation}\label{l9}
\frac{\partial \mathcal{L}(\omega)}{\partial a_j}=v_j-\sum_{j \in \mathbb{V}} P(v) v_j
\end{equation}

\begin{equation}\label{l99}
\frac{\partial \mathcal{L}(\omega)}{\partial b_i}=P(h_i=1 \mid v)-\sum_{j \in \mathbb{V}} P(v)P(h_i=1 \mid v)
\end{equation}

看到这个梯度我们就可以使用梯度下降法来进行学习了，但是麻烦的问题来了这个梯度里面有一个$\sum\limits_{j \in \mathbb{V}}$这一项，显然对于我们来说，这个是不好计算的，因为我们不知道$v$的分布。那怎么办呢？运用很直观的办法，那就是$MCMC$采样来进行估计，但是这里收敛速度是十分重要的，因为$MCMC$可能在很多步的转移之后才会$burn in$。
怎么才能得到更加有效的算法呢？我们使用 RBM 去拟合训练数据的分布，那我们是不是可以以训练数据为起点，这样可以更好的达到 RBM 的分布。

基于这个想法，咱们还是来看 Hinton 老爷子的 contrast divergence 算法吧！

Contrast Divergence

这就是大名鼎鼎的 CD 算法了！这里基于之前的假设，以样本$v^0$为初始点,然后在使用 Gibbs 采样$k$ 次得到$v^k$，最后之前的公式就变成了：

\begin{equation}\label{10}
\frac{\partial \mathcal{L}(\omega)}{\partial w_{ji}} \approx P(h_i=1 \mid v^0)v_j^0- P(h_i=1 \mid v^k) v_j^k
\end{equation}

\begin{equation}\label{11}
\frac{\partial \mathcal{L}(\omega)}{\partial a_j} \approx v_j^0- v_j^k
\end{equation}

\begin{equation}\label{12}
\frac{\partial \mathcal{L}(\omega)}{\partial b_i}\approx P(h_i=1 \mid v^0)-P(h_i=1 \mid v^k)
\end{equation}

然后一切就迎刃而解了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

\begin{algorithm}
    \caption{Contrast Divergence}
    \begin{algorithmic}[1] %每行显示行号
        \Require k,s,RBM(w,a,b)
        \Ensure $\Delta w,\Delta a ,\Delta b$
        \State initialized:$\Delta w=0,\Delta a=0 ,\Delta b=0$
        \Function {GetGradient}{$\Delta w,\Delta a ,\Delta b$}
          \While{$v \in \mathbb{V}$ }
            \State $v^0=v$
            \While{$t \in \{0,1...k-1\}$}
                \State $h^t = $ \Call{sample\\_h\\_given\\_v}{$v^t,RBM(w,a,b)$}
                \State $v^{t+1}=$ \Call{sample\\_v\\_given\\_h}{$h^t,RBM(w,a,b)$}
            \EndWhile

            \While{$i \in \mathbb{H},j \in \mathbb{V}$}
                \State $\Delta w\_{ji}=\Delta w\_{ji}+[P(h\_i=1 \mid v^0) v\_j^0-P(h\_i=1 \mid v^k) v\_j^k]$
                \State $\Delta a\_j =\Delta a\_j +[v\_j^0-v\_j^k]$
                \State $\Delta b\_i= \Delta b\_i + [P(h\_i=1 \mid v^0)-P(h\_i=1 \mid v^k)]$
            \EndWhile
           \EndWhile
          \EndFunction

        \Function{sample\\_h\\_given\\_v}{$v,RBM(w,a,b)$}
            \While{$i \in \mathbb{H}$}
                \State $Produce a random r\_i \in [0,1]$
                \If{$P\_i^v > r\_i$}
                    \State $h\_i=1$
                \Else
                    \State $h\_i=0$
                \EndIf
            \EndWhile
        \EndFunction
        \Function{sample\\_v\\_given\\_h}{$h,RBM(w,a,b)$}
                      \While{$j \in \mathbb{V}$}
                \State $Produce a random r\_j \in [0,1]$
                \If{$P\_j^h > r\_j$}
                    \State $v\_j=1$
                \Else
                    \State $v\_j=0$
                \EndIf
            \EndWhile
        \EndFunction

    \end{algorithmic}
\end{algorithm}

PGM

我们首先讲讲概率图模型吧。作为建模的最主要的工具，不知道是不是不太好啊。个人观点是： Model based 学习方法才是更合理的，为什么这样说呢。首先呢，我们希望的是解释性，是对某些事物，某些现象做出合理的解释。那什么是解释性呢？这里我们可以说是一种因果关系，就是说一个属性和另一个属性，一个时间和另一个事件之间的因果关系。这种关系，我认为是一种基于人的认知的，也就是说机器不会有的。那 Model free 的学习方法在学习什么呢？我认为这种模型在学习一种相关性，也就是说，一个时间和另一个事件的相关性，是正相关还是负相关。我们都知道相关性不等于因果性。但是某种意义上，这两个关系也有很强的关系，使得很难区分。首先机器是没有办法区分的，因为因果性不是简简单单的相关性加上时间序，因果性需要更强的物理意义，物理意义有很难直接跨过认为建模来在机器中直接产生。所以我倾向于 Model based 学习方法。

PGM ，就是 probabilistic graphical models 的简称，中文翻译作概率图模型。这个基础理论由来已久了吧，经过人们的不断地完善，这个理论已经趋于成熟。我也是参看了 Daphne Kollar 的《概率图模型：原理和技术》（中译版），对概率图模型有了一个初步的认识。图模型，这个我们在离散数学中经常提到的概念，在这里变成了可以一种抽象工具。可以抽象一个事件的各个部件之间的关系，可以抽象一个问题的前因后果，甚至可以抽象整个世界的运转（说的有点夸张，不过确实是有很大用处）。我知道的一些大牛，例如 Micheal Jordan，Bishop 对这个领域都是做出了很大的贡献吧。在概率图模型中最重要的就是独立性假设，这个东西应该硕士贯穿始终的东西吧，之所以概率图模型能抽象简化问题，就是因为这个独立性假设，这些是人类知识，或者说是对事物观察的体现吧。下面，先简要介绍一下有向图网络，在介绍无向图网络，这个其中就有条件随机场。

贝叶斯网络

这里我们知识粗略的介绍一下关于贝叶斯网络的东西，给大家一个 intuitive inspection 就可以了，具体的还是要看国语概率图模型的教材。一个直观的感觉还是比较好说的，毕竟这个东西本来就是来对现实世界中发生的事件进行建模的，所以我们很容易直观的理解为什么这样建模。下面还是以一些教材上的例子来给我们以一个直观的感觉吧。

例子：一个学生的高考成绩，和课程老师的推荐信。而，课程老师的推荐信主要是以来该学生的课程成绩，上过那么多课的我们也应该知道，课程成绩，主要依赖课程的难易程度和学生的智力，而高考成绩我们一般只依赖智力。

这个例子我们可以看出，处处充满了假设和简化，很显然的就像课程成绩肯定还依赖我们的努力程度等等。但是我们是抽象模型，简化模型的，所以我们忽略这些次要因素（也不能说是次要因素，使我们不关心的因素），而里面的因果关系充满了我们对事物的认知。根据上面的假设，我们就可以建立一个贝叶斯网络了。

Bayes network for students finding jobs

这个图模型就很好的对例子中的描述进行了建模，我们可以很清楚的看到各个元素之间的独立性和因果性。既然事物之间的关系知道了，我们该怎么对这些关系量化呢？（这也是参数学习的本源吧）首先我们要明确的一个问题是，这个世界是概率的世界，一切事物的关系都是概率的，我们不能精确的量化之间的关系，我们只能用概率来描述这种关系的强弱。图中，我们可以看到没有父节点的节点，我们是要知道其先验概率的，这个问题中，我们要知道一个课程难易程度的概率，还有一个人智力高下的概率，这些都是统计上的。然后我们就要对剩下的因果关系进行建模了，在概率中，我们是使用条件概率来进行建模的。虽然在概率论中，条件概率并没有实际的因果性。但是这里我们赋予它因果性。下面我们给出这个例子的一些参数：

\begin{array}{|c|c|}
\hline
d^0 & d^1 \\
\hline
0.6 & 0.4 \\
\hline
\end{array}

$ p(d) $

\begin{array}{|c|c|}
\hline
i^0 & i^1 \\
\hline
0.7 & 0.3 \\
\hline
\end{array}

$p(i) $

\begin{array}{|c|c|c|}
\hline
& s^0 & s^1 \\
\hline
i^0 &0.95 & 0.05 \\
\hline
i^1 &0.2 & 0.8\\
\hline
\end{array}

$p(s|i) $

\begin{array}{|c|c|c|c|}
\hline
& g^1 & g^2 & g^3 \\
\hline
i^0,d^0 &0.3 & 0.4 & 0.3 \\
\hline
i^0,d^1 &0.05 & 0.25 & 0.7 \\
\hline
i^1,d^0 &0.9 & 0.08 & 0.02 \\
\hline
i^1,d^1 &0.5 & 0.3 & 0.2 \\
\hline
\end{array}

$ p(g \mid i,d) $

\begin{array}{|c|c|c|}
\hline
& l^0 & l^1 \\
\hline
g^1 & 0.1 & 0.9 \\
\hline
g^2 & 0.4 & 0.6 \\
\hline
g^3 & 0.99 & 0.01 \\
\hline
\end{array}

$p(i \mid g) $

根据独立性分解，我们可以得到因子图：

I-map

这样一分解，一切问题就变得简单了，本来47个变量现在一下变得很少了，而联合概率我们就可以写成：
\begin{equation}\label{1}
p(i,d,g,s,l)=p(i)p(d)p(g \mid i,d)p(s \mid i)p(l \mid g)
\end{equation}

马尔科夫网

之前说的是一些有向图，现在我们来讨论无向图。 PGM 这本书里说的主要是有些模型，我们无法使用有向图来，或者说我们无法确切的知道两个事件的因果关系。还有一个问题就是独立性条件有向图很难满足的。例如我们看图

Markov network

这个图很好的保证了 $p(a \perp c \mid b,d)$ 和 $p(b \perp d \mid a,c)$ ，但是有向图中就很难同时满足这两个条件。无向图和有向图同样十分重要的一个环节就是，因子图分解。在无向图中每一个完备子图（最大完全子图）就是一个因子图。如上图所示，我们可以看到虚线框起来的就是一个因子图。每一个因子和之前有向图的因子是非常相似的。然后联合概率就可以转化成：

\begin{equation}\label{mk}
p(a,b,c,d)=\frac{1}{\mathcal{Z}} \phi_1(D_1) \times \phi_2 (D_2) \times \cdots \cdots \times \phi_n (D_n)
\end{equation}

其中 $\mathcal{Z}$ 是划分函数：
\begin{equation}\label{pf}
\mathcal{Z}=\sum_{a,b,c,d}\phi_1(D_1) \times \phi_2 (D_2) \times \cdots \cdots \times \phi_n (D_n)
\end{equation}

这是一个很简单的例子，这里就不在深入的讲解了。我们所熟悉的，成对马尔科夫网（特别像四邻域或者八邻域的图像结构），伊辛模型和玻尔兹曼机，条件随机场等都是无向图模型里面的模板。这里只是作为了解，如果大家感兴趣可以看教材，还有很多论文。

Sequential data

我们这里关注的是 sequential data 一些问题，比如序列标注，分割等问题。这个问题初始来源于自然语言处理领域，后来图像领域作语义分割的人把这个迁移过来，效果非常好。而现在，作语义分割的基本都是使用条件随机场，这个已经成了必备的知识的，而先进的深度学习的技术只是作为这个框架的一部分来进行刻画的。好了既然这么重要，我们就从这个自然语言序列标注开始慢慢讲起吧！

HMM

一个隐马尔科夫模型是一个五元组 ${X,Y,\pi ,A,B}$ , $Y$ 表示的是隐含变量， $X$ 表示的是观测， $\pi$ 表示的是初始概率， $A$ 表示的是状态之间的转移矩阵， $B$ 表示的是状态和观测之间的关系，根据这个我们就可以定义一个隐马尔可夫模型了。隐马尔可夫模型其实是动态贝叶斯网络（ dynamic bayes network ）的的一个最简单的特例。

在序列标注领域，隐马尔科夫模型可以说是一个非常非常重要的角色。我们还是惯常使用一个经典的例子来解释这个问题（一个到处都能找到的例子）。

例子，一个人想知道另一个城市的天气，但是他不能直接观测到，他知道他朋友的每天的活动，怎么获取当地的天气？

下面我们假设，他知道几天前的某一天的天气的概率，而天气这里分为 *Y={sunny,cloudy rainy}*，朋友的活动有 *X={tennis,hiking,home}*，天气之间的变换是有一定的规律的，朋友的活动和天气也有很大的关系。

\begin{array}{|c|c|c|c|}
\hline
& sunny &cloudy &rainy \\ \hline
\pi & 0.5 &0.3 &0.2 \\
\hline
\end{array}

$\pi $

\begin{array}{|c|c|c|c|}
\hline
& sunny &cloudy &rainy \\ \hline
sunny & 0.6 &0.3 &0.1 \\ \hline
cloudy & 0.2 &0.3 &0.5 \\ \hline
rainy & 0.3 &0.4 &0.3 \\
\hline
\end{array}

$A$

\begin{array}{|c|c|c|c|}
\hline
& tennis &hiking &home \\ \hline
sunny & 0.2 &0.4 &0.4 \\ \hline
cloudy & 0.6 &0.3 &0.1 \\ \hline
rainy & 0.1 &0.2 &0.7 \\
\hline
\end{array}

$B$

这里需要注意的是每一行的概率，也就是条件概率的和为一。

根据这个我们可以得到一个状态转移图，也就是自动机。

automatic for HMM

但是我们关心的是时序上的关系，也就是说未来的通过一系列的过去的观测来推算过去的天气，这样把这个自动机变成一个时序上模型

HMM
根据这个时序模型，加上之前的一些知识，我们可以知道：
\begin{equation}\label{hme}
p(x,y\mid \theta)= p(y_1) \prod_{i} p(y_i \mid y_{i-1})p(x_i \mid y_i)
\end{equation}

这里的 $x_i,y_i$ 都是一个变量，也就是之前的 X,Y 在时序上的体现，他们的取值就是之前所表示的，之间的状态转移概率，和状态与观测之间的条件概率都是之前我们定义的。这个是什么意思呢。我们可以认为我们观测到了朋友这四天的活动情况， ${x_1,x_2,x_3,x_4}$ ，来计算这四天的天气状况$ {y_1,y_2,y_3,y_4} $。 当然，我们也可以换另外一个问题，已知这个模型，这四天朋友 ${x_1,x_2,x_3,x_4}$ 的概率是多少？ 这是两个完全不同的问题，一个是求在这个模型下，产生这个观测的最可能的状态是什么。一个是求这个模型对这个观测的适应程度。解决不同的问题，我们会有不同的算法。到这里我相信各位已经有了一个比较直观的了解了。下面我们看看对于不同的问题，我们应该使用什么算法。

前向算法

前向算法就是评估一个模型对已有观测的适应性的。什么意思呢？就是说，我给定一个模型的算有参数，现在来了观测，问这个模型产生这个观测的概率是多少呢？这个应该就是模型的适应性吧。用公式表示就是：
\begin{equation}\label{qian}
p(x \mid \theta)=\sum_y p(x,y \mid \theta)
\end{equation}

当然我们可以枚举算有的状态序列，这个规模是以状态个数为底，以时序长度没指数的大小，现在这个随着时序的增加会非常大，这个不是我们想要的结果，我们希望希望能快速的计算出这个结果，这就是前向算法了。前向算法有效地利用之前状态的的信息，可以看做是一种类似于动态规划的过程。下面我们展开这个 HMM 来看，在给定一个观测时，状态之间的关系如下图所示：

All pathes at this observation

这里面的每一条路径都可以产生我们的观测，我们这个问题就是求所有的路径的和，也就是所有的状态序列产生这个观测的和。最暴力的办法当然就是枚举每一个路径，然后求和就可以了。但是我们观察，这里是有子结构的：

sub-structure in the pathes

这个子结构可以使我们很有效的计算这个和。下面我们给出具体的计算公式：

（1）当 $t=1$ 时；

\begin{equation}\label{t1}
\alpha_t(i)=\pi(i) B(i,j)
\end{equation}

这里我们用到的就是初始概率了这里的 $\alpha_t(i)$ 表示在 $t$ 时刻，观测 $y_t=j$ 由状态 $x_t=i$ 产生的概率，这里是枚举了之前的算有的状态。

（2）当 $t =1,2,…n$ 时：

\begin{equation}\label{t2}
\alpha_t(i)=B(i,j)\sum_{k}\alpha_{t-1}(k) A(k,i)
\end{equation}

而我们想要求的 $p(x\mid \theta)$ 在这里就变成了：
\begin{equation}\label{qianx}
p(x\mid \theta)=\sum_{i}\alpha_n(i)
\end{equation}

这样我们看到之前的时间复杂度 $\mathcal{O}(N^T)$ 一下子就变成了 $\mathcal{O}(N^2 T)$ 。

维特比算法（Viterbi algorithm）

上面讲到了前向算法，但是平时我们使用最多的并不是衡量一个隐马尔可夫模型的适应性，而是在一个给定的马尔可夫模型中，找到一组观测对应的最可能的状态。这个可以看做是解码的过程。怎么快捷有效的解码这个才是我们最关心的。当然我们也可以像之前，我们所说的那样穷举状态空间来进行求解，显然我们并不像这么做。那怎么办呢？

之前我们发现了路径中的子结构，那这个问题是否也使用这个子结构呢？如果使用该怎么求解呢？

我们来看一下实例图：

The optimal path

如果所示，该路径是最优路径也就是说，这个路径的概率是最大的，如果这个路径的概率是最大的也就是 $\max_i v_n(i)$ ，那么如果这个最终的节点是最大的，在这条路上的每一个节点都应该是当前最大的。所以这个也可以使用之前的子结构，不过要作稍微的改动。

1）当 $t=1$ 时；

\begin{equation}\label{v1}
v_t(i)=\pi(i) B(i,j)
\end{equation}

这里的初始的节点的值是没有什么变化的。

（2）当 $t =1,2,…n$ 时：

\begin{equation}\label{v2}
v_t(i)=\max_k B(i,j)v_{t-1}(k) A(k,i)
\end{equation}
这里每一步都求之前的最大值，但是我们要知道这个最大值是来自哪一个节点，所以得定义一个结构来记录每一步指向的父节点：
\begin{equation}\label{v3}
p_t(i)=\arg \max_k B(i,j)v_{t-1}(k) A(k,i)
\end{equation}

而我们想要求的 $\max p(x\mid y, \theta)$ 在这里就变成了：
\begin{equation}\label{vetbi}
\max p(x\mid y,\theta)=max_{i} v_n(i)
\end{equation}

然后我们可以回溯的 $p_t$ 这个表来获取，我们求得的最大概率的状态序列。

前向后向算法

但是事实情况是这样的，我们大部分情况是很难知道模型的参数。就是初始概率，转移概率还有条件概率，我们是很难知道的。一般情况，我们知道的都是经过一段时间的观测，得到状态和观测对。我们需要通过学习来获得整个模型的参数。那问题就来了，这个模型我该怎么训练呢？怎么回去这一大对概率呢？

总是有牛人提出一些有效地办法来解决问题，这就是大名鼎鼎的前向- 后向算法，之前我们已经大致知道了前向算法，下面我们来介绍一下后向算法吧。

后向算法

后向算法和前向算法是很相似的，但是后向算法是从后面向前计算的。前向算法就是计算某一个状态确定，之前的所有状态能产生对应的观测对的概率，而后向算法正好相反，计算的是一个状态固定，之后的所有状态产生对应的观测的概率。具体的计算过程就是：

（1）当 $t=n$ 时，

\begin{equation}\label{ba}
\beta_t(i)=1
\end{equation}

（2）当 $t=n-1,….1$ 时：
\begin{equation}\label{bb}
\beta_t(i)=B(i,j) \sum_k A(i,k) \beta_{t+1}(k)
\end{equation}

这里的观测是 $y_t=j$ ，这样我们就可以递归的计算整个时序图的后向结果了。

下面我们还是简单提一下，其实这个前向-后向算法可以说是大名鼎鼎的 EM 算法的一个特例。这话可不是我说的，是发明 EM 算法的人说的，虽然这个前向后向算法的提出是要比 EM 算法早的，但是 Dempster 在它的论文里就是这样么说的，后来还有大牛 Jelinek 说就是这样的。那我们就信了吧。 EM 算法就不多说了，我们大致知道了这是一个的待求解的过程就可以了。下面我们来看看这个算法的具体流程吧。

之前我们已经通过前向算法，后向算法，获得了相应的 $\alpha,\beta $，我们先来定义一个概率来表示某一时刻是由某个特定的状态产生其对应观测：
\begin{equation}\label{gamma}
\gamma_t(i)=p(y_t=i \mid x,\theta)=\frac{p(y_t=i,x \mid \theta)}{p(x \mid \theta)}
\end{equation}

然后联想到之前的定义，我们可以很容易的得到：

\begin{equation}\label{gamma1}
\gamma_t(i)=\frac{\alpha_t(i) \beta_t(i)}{\sum_i \alpha_t(i) \beta_t(i)}
\end{equation}

现在我们知道某一个时刻的状态的概率了，那我们肯定还要知道两个时刻之间状态转移的概率，这个概率有那么点抽象，我们来看看一个形象的解释吧。

Forward-Backward algorithm

看到上图，我们大致就可以定义一个在某一时刻，某一状态转移到另一状态的概率：

\begin{equation}\label{xi}
\xi_t(i,j)=p(y_t=i,y_(t=1)=j \mid x,\theta)=\frac{p(y_t=i,y_{t+1}=j,x \mid \theta)}{p(x \mid \theta)}
\end{equation}

根据上图，我们就可以得出：
\begin{equation}\label{xi2}
\xi_t(i,j)=\frac{\alpha_t(i) A(i,j) B(j,x_{t+1}) \beta_{t+1}(j)}{\sum_i \sum_j \alpha_t(i) A(i,j) B(j,x_{t+1}) \beta_{t+1}(j)}
\end{equation}

上面这两个参数是有关系的：
\begin{equation}\label{gux}
\gamma_t(i)=\sum_j \xi_t(i,j)
\end{equation}

我们求了这么几个参数，但是这些参数到底是什么意思呢？下面我们解释一下：
$\sum_t \gamma_t(i)$ 表示状态 $i$ 的所有转出数，
$\sum_t \xi_t(i,j)$ 表示状态 $i$ 转移到状态 $j$ 的数目。

既然知道了这个，我们就可以得到，我们更新后的 $\pi,A,B$ 了。
\begin{equation}\label{pi}
\pi(i)=\gamma_1(i)
\end{equation}

\begin{equation}\label{a}
A(i,j)=\frac{\sum_t \xi_t(i,j)}{\sum_t \gamma_t(i)}
\end{equation}

\begin{equation}\label{b}
B(i,v_k)\frac{\sum_{t \ S.t. x=v_k } \gamma_t(i)}{\sum_t \gamma_t(i)}
\end{equation}

然后我们就可以迭代求解了，因为之前我们求解 $\alpha,\beta$ 都用到了 $\pi,A,B$ 。这样就可以求得局部最优解了。

到这里 HMM 就告一段落了，对于 HMM 一些应用，我们基本上都知道例如。

最大熵原理马尔科夫模型

这里的模型主要是：

Max entropy hidden markov network

这里就是最大熵原理加上隐马模型。这里主要关注的是最大熵原理的对偶问题和最大熵模型的极大似然解是一样。这里用到了改进的迭代尺度法，都为条件随机场建立了良好的基础。

条件随机场

条件随机场，是 Laffety 在2001年提出的，这个可以说是在序列标注领域是一个很大的进步。 Laffety 分析了之前模型面临的问题：（1）最重要的问题就是之前的模型都是产生式模型，也就是说之前的算法都是对联合概率分布进行建模的，也就是说之前的算法要对所有的观测进行建模，显然这个是很困难的，因为这个是基本不太可能的。（2）还有一个问题就是，标记偏置问题，因为不同的状态的出度的是不一致的，然后因为局部归一化导致这个标记偏置了。

然后作者说了一大堆别的模型的缺点提出了条件随机场，首先确定的是条件随机场是一个判别式模型，他是在给定一组输入变量，输出变量构成马尔科夫随机场的这么一个模型。 Laffety 最先提出来的是链式条件随机场，那我们就从链式条件随机场讲起吧。

定义:条件随机场
设 $X$ 和 $Y$ 是随机变量， $p(Y \mid X)$ 是在给定 $X$ 的条件下 $Y $ 的条件概率分布，若随机变量 $Y$ 构成一个无向图 $G={V,E}$ 表示的马尔科夫随机场，即
$$P(Y_v \mid X,Y_w,w \neq v)=p(Y_v \mid X,Y_w,w \sim v) $$
对任意的节点成立，则称条件概率分布 $p(Y \mid X)$ 为条件对机场。

需要注意的是这里的 $Y_v,Y_w$ 表示的是节点 $v,w$ 对应的随机变量。 $w \sim v$ 表示这两个节点右有边链接。

根据这个，我们给出线性链式条件随机场：

定义：线性链式条件随机场
设 $X=(X_1,X_2,…,X_n),Y=(Y_1,Y_2,…,Y_n)$ 均是线性链表示的随机变量序列，若在给定 $X$ 的条件下 $Y$ 的条件概率分布 $p(Y \mid X)$ 构成的条件随机场满足：

$P(Y_i \mid X,Y_1,Y_2,…,Y_{i-1},Y_{i+1},…,Y_n)=p(Y_i \mid X,Y_{i-1},Y_{i+1})$

则称 $P(Y \mid X)$ 是线性链式条件随机场。

下面我们来看一下这个用图怎么表示：

Chain conditional random field
这个跟之前的隐马尔可夫模型和最大熵马尔可夫模型都有了很到的区别，首先就是这是一个判别式模型，是在最大化特定的观测下的状态序列概率，也就是条件概率，而且状态之间变成了马尔科夫随机场，也不再是之前的动态贝叶斯网络。这些都符合作者对问题的分析，和改正。观测序列的结构这里没有给出，因为这个是和数据有很大关系的，可以说是基于应用的，不同的数据可能会有不同的结构。

下面我们着重来看一下这个模型是怎么参数化的。

条件随机场的参数化

我们有了之前的定义，加上我们对马尔科夫网的了解，我们大致知道，怎么去因子化一个马尔科夫网，然后怎么用吉布斯能量去表示一个一个网络的能量。下面我们给出一个条件随机场的因子化的定理：

定理：线性链式条件随机场的参数化
设 $P(Y \mid X)$ 为线性链式条件随机场，则在随机变量 $X$ 取值为 $x$ 的条件下。随机变量 $Y$ 取值为 $y$ 的条件规律具体如下：
$$p(y \mid x)=\frac{1}{\mathcal{Z}(x)} \exp \left(\sum_{i,k} \lambda_k t_k (y_{i-1},y_i,x,i)+\sum_{i,l} \mu_l s_l(y_i,x,i)\right)$$
其中：
$$\mathcal{Z}(x)=\sum_y \exp \left(\sum_{i,k} \lambda_k t_k (y_{i-1},y_i,x,i)+\sum_{i,l} \mu_l s_l(y_i,x,i)\right)$$

这个公式里面 $t_k,s_l$ 是特征函数， $\lambda_k,\mu_l$ 是对应的权值， $\mathcal{Z}(x)$ 是归一化因子，求和是在所有的输出序列上进行的，这个可能就是避免标签偏置的过程，不在是局部归一化，而采用全局的归一化。

-

但是这个参数化之后，看着还是满复杂的，我们想把那两个项简化成一个同一的表达形式，以便于后面的理解。我们这里首先来同一符号，之前的特征函数我们这里都是用 $f_k$ 表示，那么这里的特征函数的个数就是之前的和 $K=K_1+K_2$ ：

\begin{equation}\label{fddtd}
f_k(y_{i-1},y_i,x,i)=
\begin{cases}
t_k(y_{i-1},y_i,x,i),&k=1,2,…,K_1 \\
s_l(y_i,x,i), & k=K_1+l;l=1,2…,K_2
\end{cases}
\end{equation}

之前我们也看到，参数只和特征函数函数的个数有关，和参数的个数是没有关系的，而且我们关心的也是求和之后的结果，所以我们可以先对特征函数求和：
\begin{equation}\label{f}
f_k(y,x)=\sum_{i=1}^nf_k(y_{i-1},y_i,x,i),k=1,2,…,K
\end{equation}

这样这个特征函数就可以写成一个列向量的形式了，参数同样也可以写成列向量的形式：

\begin{equation}\label{wttk}
w_k=
\begin{cases}
\lambda_k, &k=1,2,…,K_1 \\
\mu_l, &k=K_1+l;l=1,2…,K_2
\end{cases}
\end{equation}

然后我们用列向量来表示特征值和参数：
$$w=(w_1,w_2,…,w_K)^T$$
$$F(y,x)=(f_1(y,x),f_2(y,x),…,f_K(y,x))$$

写成了向量的形式，计算起来就很简单了，下面我们给出之前的公式一个向量形式的表示：
\begin{equation}\label{fw}
p_w(y \mid x)=\frac{1}{\mathcal{Z}_w(x)} \exp (w \cdot F(y,x))
\end{equation}

\begin{equation}\label{ftw}
\mathcal{Z}_w(x)=\sum_y \exp (w \cdot F(y,x))
\end{equation}

-

下面还有一种我们比较喜欢，另一种形式的简化，之前的都是对节点进行求和，然和写成列向量的形式，现在我们对特征函数求和，这样每个求和之后的结果都是一个 $\mid y \mid * \mid y \mid$ 的矩阵，这样使用起来是非常简单的。之前我们对 $y$ 求和，但是显示中，我们关注的是时序数据，也就是安，我们之前 HMM 中提出那样，每一个时序片之间，我们也可以枚举 $y$ 的状态，形成一个链路图。

Time spread form

我们想知道每一堆联通节点之间，所有状态取值之间的链接权值，以便我们在解码的时候找到最大概率的路径，即在给定观测下的最优状态序列。既然了解了这个大致是什么原理，那我们来看一下，具体是怎么定义的吧。

我们来定义一个矩阵形式的 $M_i(x)$ 表示在时序 $i$ 时， $i-1$ 所有状态取值到该时刻所有状态取值的一个转移概率矩阵（这个类似我们之前在 $HMM$ 中定义的转移矩阵 $A \bigodot (1_{1*3} \bigotimes B(i,x_i)$ ，不过这里的转移矩阵是可以随时序变化的）。
\begin{equation}\label{tm}
M_i(x)=[M_i(y_{i-1},y_i \mid x)]_{\mid y \mid * \mid y \mid}
\end{equation}

\begin{equation}\label{mi}
M_i(y_{i-1},y_i \mid x)=\exp \left(\sum_k w_k f_k(y_{i-1},y_i,x,i)\right)
\end{equation}

这里之前的概率，我们就可以写成：
\begin{equation}\label{pw2}
p_w(y \mid x)=\frac{1}{\mathcal{Z}_w(x)} \prod_i M_i(y_{i-1},y_i \mid x)
\end{equation}

这里的归一化因子就是：
\begin{equation}\label{guiyi}
\mathcal{Z}_w(x) =\sum \bigotimes_i M_i(x)
\end{equation}

说了这么多，我们都没有谈到概率，都没有谈到在给定观测，某一状态取特定值的概率是多少？两个特定状态之间的转移概率是多少？这些到这里，我们都没有给出，在条件随机场中，我们并没有刻意的去生命某个概率到底是什么，但是，应不应该有和隐马尔可夫模型相似的参数。下面我们来看到底会不会有呢？

概率的计算

这里的概率计算并不是可以直接得到概率，但是我们引入和隐马一样的计算方式，来计算在给定观测下的概率参数。

前向-后向算法

这里还是沿用之前的符号 $\alpha_i(x)$ 表示在 $i$ 时刻的前向结果， $\beta_i(x)$ 表示 $i$ 时刻的后向结果。

这里需要注意的是 $\alpha_0(x)$ 的取值，因为这个是我们认为加入的节点，所以，这个并没有什么意义，但是这个也要是向量形式，只是这里的向量是在某一个节点为1就可以了，之后的递推关系是;
\begin{equation}\label{alpha}
\alpha_i^T(x)=\alpha_{i-1}^T M_i(x)
\end{equation}

同样的 $\beta_0(x)$ 也是需要注意一下，因为这里她也是没什么意思的，只要是在每一停止位置为1就可以了，其他的都为零，其递推关系如下：
\begin{equation}\label{beta}
\beta_i(x)=M_{i+1}(x) \beta_{i+1}(x)
\end{equation}

这里同样有之前，我们定义的那个关系：
\begin{equation}\label{gx}
\mathcal{Z}(x)=\alpha_n^T \cdot \mathbf{1}=\mathbf{1}^T \cdot \beta_1^T(x)
\end{equation}

下面我们进入到正题，就真个模型的该理财的计算，包括一些统计量的获取。

\begin{equation}\label{pypx}
p(Y_i=y_i \mid x)=\frac{\alpha_i^T(y_i\mid x) \beta_i(y_i \mid x)}{\mathcal{Z}(x)}
\end{equation}

\begin{equation}\label{pyx}
p(Y_{i-1}=y_{i-1},Y_i=y_i \mid x)=\frac{\alpha_{i-1}^T(y_{i-1}\mid x) M_i(y_{i-1},Y_i\mid x) \beta_i(y_i \mid x)}{\mathcal{Z}(x)}
\end{equation}

这里面 $\alpha_i^T(y_i\mid x)$ 代表之前定意的 $\alpha_i^T(x)$ 这个向量的一个取值，以此类推，后向的结果也是这个样子的。

这里需要注意的是，这个归一化是全局的，之前隐马尔科夫模型中这个地方的归一化是局部的。

这里我们还要引入特征函数 $f_k$ 关于条件概率的期望的计算：
\begin{equation}\label{wfjjk}
\begin{split}
\mathbb{E}_{p(y \mid x)}[f_k] & =\sum_y p(y \mid x) f_k(y,x) \\
& = \sum_i \sum_{y_{i-1},y_i} f_k(y_{i-1},y_i,x,i) \frac{\alpha_{i-1}^T(y_{i-1}\mid x) M_i(y_{i-1},Y_i\mid x) \beta_i(y_i \mid x)}{\mathcal{Z}(x)}
\end{split}
\end{equation}

如果引入经验分布 $\widetilde{p}(x)$ ，那关于联合概率的期望：

\begin{equation}\label{wfk}
\begin{split}
\mathbb{E}_{p(y ,x)}[f_k] & =\sum_{x,y} p(y , x) f_k(y,x) \\
& =\sum_x \widetilde{p}(x) \sum_i \sum_{y_{i-1},y_i} f_k(y_{i-1},y_i,x,i) \frac{\alpha_{i-1}^T(y_{i-1}\mid x) M_i(y_{i-1},Y_i\mid x) \beta_i(y_i \mid x)}{\mathcal{Z}(x)}
\end{split}
\end{equation}

到这我们大概就知道怎么计算概率，期望什么的了。具体过程就是，来个一个观测，我们前向扫描一遍计算出 $\alpha_i(x)$ ，然后在通过一个后向扫描计算出 $\beta_i(x)$ ，然后根据上面的公式，我们就可以计算出我们想要的概率，和期望了。

学习算法

我们比较关注的还是，怎么学习一个模型的参数，也就是说，给定一系列的状态观测序列，我们希望找到最合适的模型来对这个进行建模，这里主要涉及的参数就是每一个特征函数对应的 $w_k$ 。既然知道了目的，那我们需要重要有个损失函数吧。

这里是根据和最大熵原理一样定义一个对数似然函数，通过极大化对数似然函数来获得我们参数。
\begin{equation}\label{lw9}
\mathcal{L}(w)=\mathcal{L}_{\widetilde{p}}(p_w)= \log \prod_{x,y} p_w(y \mid x)^{\widetilde{p}(x,y)}=\sum_{x,y} \widetilde{p}(x,y) \log p_w(y \mid x)
\end{equation}

根据之前的定义，我们可以把这个函数化解为：

\begin{equation}\label{ljw}
\begin{split}
\mathcal{L}(w) & =\sum_{x,y} \widetilde{p}(x,y) \log p_w(y \mid x) \\
& =\sum_{x,y}\left[ \widetilde{p}(x,y)\sum_k w_k f_k(y,x) -\widetilde{p}(x,y) \log \mathcal{Z}_w(x) \right]\\
& = \sum_{x,y} \sum_k w_k f_k(y,x) - \sum_x \log \mathcal{Z}_w(x)
\end{split}
\end{equation}

这里推导的过程在最大熵原理中都有介绍，我在这里就不赘述了。我们要学习的是 $w_k$ ，我们使用的都是梯度上升的办法，这里给出\textcolor{red}{改进的迭代尺度法}中，每一个参数 $w_k$ 的变化率 $\delta_k$ 的计算方式：

（1） $k \in [1,K_1]$
\begin{equation}\label{tp}
\begin{split}
\mathbb{E}_{\widetilde{p}}[t_k] & =\sum_{x,y} \widetilde{p}(x,y)\sum_i t_k(y_{i-1},y_i,x,i) \
& =\sum_{x,y}\widetilde{p}(x) p(y \mid x) \sum_i t_k(y_{i-1},y_i,x,i) \exp (\delta_k T(x,y))
\end{split}
\end{equation}

（1） $k=K_1+l \in [K_1 +1,K]$
\begin{equation}\label{tp1}
\begin{split}
\mathbb{E}_{\widetilde{p}}[s_l] & =\sum_{x,y} \widetilde{p}(x,y)\sum_i s_l(y_{i-1},y_i,x,i) \
& =\sum_{x,y}\widetilde{p}(x) p(y \mid x) \sum_i s_l(y_{i-1},y_i,x,i) \exp (\delta_k T(x,y))
\end{split}
\end{equation}

这里的 $T(x,y)$ 就是所有的特征总和：
\begin{equation}\label{tr}
T(x,y)=\sum_k f_k(x,y)=\sum_k \sum_i f_k(y_{i-1},y_i,x,i)
\end{equation}

根据上面的两个公式，我们可以求得所有的 $\delta_k$ ，然后根据梯度上升的办法：
\begin{equation}\label{tidu}
w_k =w_k+\delta_k
\end{equation}
直到收敛。

之前的算法的 $T(x,y)$ 用一个常数代替，只要在保证
\begin{equation}\label{s}
\forall(x,y) S-T(x,y) \geq 0
\end{equation}

这里的改进使用的是 $\max_y T(x,y)$ 。

到这里，我们就大致知道，怎么参数学习的了，但是问题还有一个就是我们在这里只给出了 $\delta_k$ 的求解方程，并没有给怎么求解，一些求解的细节这里也没有。因为求解的算法比较多，这里就不在一一赘述了，主要有拟牛顿法（BFGS）等，这里就不说了，详情请看李航老师的《统计学习方法》。

学习算法，我们已经给出了，下面我们来看看条件随机场是怎么预测的吧。

条件随机场的预测

预测就是在给定观测的情况下，获得割爱率最大化时的状态序列，形式化的表示就是：
\begin{equation}\label{yuce}
\begin{split}
y* & =\arg \max_y p_w(y \mid x) \
& =\arg \max_y \frac{\exp (w \cdot F(y,x))}{\mathcal{Z}_w(x)} \
& =\arg \max_y (w \cdot F(x,y))
\end{split}
\end{equation}

这里我们可以参考，之前的一个简化方式 $M_i(x)$ 来进行计算，但是这里直接计算指数上的结果，所有这里没有直接使用,而是使用类似的办法。当然这里的核心还是 Viterbi 算法。

上面的公式我们可以改写一下，因为上面的公式中没有涉及到实训问题，这样我们就没办法使用维特比算法了，我们要把上面的目标返程改写为，具有时序的形式；
\begin{equation}\label{shixu}
\max_y \sum_i w \cdot F_i(y_{i-1},y_i,x)
\end{equation}
这里的 $F_i(y_{i-1},y_i,x)$ 表示的是：
\begin{equation}\label{fs}
F_i(y_{i-1},y_i,x)=(f_1(y_{i-1},y_i,x,i),f_2(y_{i-1},y_i,x,i),…,f_K(y_{i-1},y_i,x,i))^T
\end{equation}

然后我们就可以使用维特比算法了，我们还是沿用之前的记号 $v_i(j)$ 表示在 i 时刻的状态取值是 $j$ 的值， $p_i(j)$ 来记录之后递归时的路径。

（1）当 $i=1$ ：

\begin{equation}\label{v001}
v_i(j)=w \cdot F_1(y_0=start,y_i=j,x)
\end{equation}

（2）当 $i=2,..,n$ 时：

\begin{equation}\label{v8}
v_i(j)=\max_{1 \leq l \leq \mid y \mid }[v_{i-1}(l) + w \cdot F_1(y_{i-1}=l,y_i=j,x)]
\end{equation}

\begin{equation}\label{v200}
p_i(j)=\arg \max_{1 \leq l \leq \mid y \mid }[v_{i-1}(l) + w \cdot F_1(y_{i-1}=l,y_i=j,x)]
\end{equation}

这样我们就可以求出最终的结果了：
\begin{equation}\label{vf}
\max_y \sum_i w \cdot F_i(y_{i-1},y_i,x)=\max_{1 \leq l \leq \mid y \mid } v_n(l)
\end{equation}

相应的状态序列，就可以直接回溯 $p_n$ 就可以了。

整个条件随机场就告一段落了。有一个网站是这方面很全的，crf这上面有很多资料，可以关注。还有就是李航老师的《统计学习方法》，还有[hmm]](http://www.52nlp.cn/hmm-learn-best-practices-one-introduction)，还有就是 Lafferty 的原始论文。图像这边最早的是 Xuming He 的”Multiscale Conditional Random Fields for Image Labeling”，还有 Plath的”Multi-class image segmentation using Conditional Random Fields and Global Classfication” 。这个之后要好好看看，看看这个东西是怎么应用的。

Lenet5

MNIST

要说 Lenet ，那我们就不得不说说 MNIST 数据集。这个手写数字的数据集是非常常用的数据集之一了。在这个数据及上的手写数字识别的比赛，发展到目前已经算是基本解决了。但是发展的历程还是值得一看的。我们就看一下 LeCun 他的工作的历程吧。 LeCun 在这个数据集上尝试了很多的方法，从 1-layer neural network ， K-nearest neighbors + Distance method 再到 PCA ， SVM ， Multi-layers neural network 最后提出了 Convolutional neural network 。 是一个很值得思考的过程，但是在每一分项中，他都没有达到最好的的成绩，有点前人栽树，后人乘凉的味道。

具体的数据集我就不再这里介绍了，感兴趣的可以去 LeCun 的主页上可以找到相关的信息。 LeCun 也是在这个模型上，完成了商用的首写数字识别系统，具体的可以参考 LeCun 98年发表的那个 Gradient-based learning applied to document recognition ，不过那篇文章是个 Sequential handwriting number recognition ，所以是在卷积神经网络前面接了一个 HMM 作为序列的分割和拼接。我们并不关注前端的 HMM ，我们这里只关注我们感兴趣的 CNN 。

下面的章节我们主要参考的是这里的教程，还有 Jake Bouvrie 的“ Notes on Convolutional Neural Networks
”。

motivation

卷积神经网络和之前的神经网络最大的区别，应该是有三点：

卷积神经网络特征

1.Receptive field：局部感受野，主要描述的是，输出不再是空间无关的了。每一个输出是有一定的空间意义的，然后根据 Hubel,Wiesel 对人脑的链接的研究，提出每一个输出只和输入的相对应的空间位置的一个邻域内部的输入有关的。这个观点非常适合具有局部特性的数据的处理，例如图像数据。

2.Shared weights：共享权值，这个说的是每个输出所对应的权值是相同的，但是每一个空间位置是由多个输出（多个 Kernels ）组成的。这个我们直观来理解就是，用一个边缘检测的例子，我们用不同方向（对应多个核）的滤波器进行全图（对应共享权值）的滤波，然后综合各个滤波的结果得到我们想要的边缘。

3.Pooling：池化，关于池化，是有很多种形式的，最主要的形式就是 MAX pooling ，就是在一个邻域里面取最大值。因为实在一个邻域里面取最大值，所以起到了的降维的作用。这个同时还会得到一个更好的效果，那就是 invariance 。

Lenet

说了这么多，让我们来看一个实例吧：

网络结构

我们先来看一下这个网络的结构吧。这是一个7层的神经网络，输入的是一个32x32 的灰度图， S 表示的是下采样层， C 表示的是卷积层， F 表示的是全连接层。根据上图，我们可以很清楚的看到，第一层是一个卷积层，其包含6 个5x5的卷积核，参数个数156，也就是说这里的输出有6 个28x28 的特征图。第二层是一个下采样层，这里的下采样策略都是 MEAN pooling ，采样窗的大小都是2x2，参数个数是12个（一个特征图对应两个参数），所以这里的输出就变成了6 个14x14 的特征图。第三层是一个卷积层，但是这里涉及到一个问题，那就是上一层有6 个特征图，而这一层，我们有16 个5x5 的卷积核，也就是说我们应该得到16 个特征图，那我们怎么建立这6 个输入和16 个输出的关系呢。显然，我们是不想输出的每一个特征图都和之前的特征图链接的（我觉得这里可能是想保持空间特异性的，当然也不排除只是为了计算复杂性）。那 LeCun 是怎么定义这之间的链接的呢？

现在我们搞清楚了第二层和第三层是怎么连接的，这里的参数个数是6x（3x25+1）+9x（4x25+1）+6x25+1）=1516，第三层的输出是16 个10x10 的特征图，下面我们接着看第四层。第四层是一个下采样层，采样策略和采样窗的大小都与之前的采样层是一样，所以输出的结果是16 个5x5 的特征图。然后第五层还是一个卷积层（这里也可以看做是一个全连接层，当且仅当输入的特征图的大小和卷积核一样大的时候。）但是按照 LeCun 关于参数的计算，这里的参数是120x（16x25+1）= 48120，也就是说这里没有任何的权值共享，每一个输出对应的所有输入的参数都不一样这样才能保证参数是48120。第六层也是全连接层，输入是120，输出时84，所以参数是84x （120+1）=10164，最后一层就是输出了，这里的实处是10，也就是说这里训练的参数是（84+1）x10=850.

好了，这样整个结构就基本整明白了。下面我们开始介绍这个卷积神将网络的训练。

Forward pass

为了方便，我们用$u^l$表示第$l$层的输出，最后输出层的输出，我们使用$t$ 表示，这里我们使用的激活函数
$$f(\cdot)=sigmoid(\cdot)$$
我们用$\star$ 代表卷积。好了那我们来看一下卷积层和下采样层，全连接层都是怎么计算的。
对于卷积层，我们的计算过程是：
$$u_i^l=W_i^l \star x^{l-1}+b_i^l,~~~i\in~|F.map|$$
然后输出是:
$$x_i^l=f(u_i^l)$$
但是中间的卷积层是由多个输入特征图的，所以之前的公式应该变成：
$$u_i^l=\sum_{j \in M_i} x_j^{l-1}*k_{ji}^l +b_i^l$$
这里的$M_i$表示的是所选取的输入特征图。

对于下采样层我们的计算公式是：

$$u_i^l=\beta_i^l down(x_i^{l-1})+b_i^l,~~~i\in~|F.map|$$

对于全连接层，就和之前的神经网络是一样的：
$$ u^l=W^l \cdot x^{l-1}+b^l $$

然后我们使用的损失函数是：
\begin{equation}\label{6}
E^N=\frac{1}{2}\sum_{n=1}^{N}\sum_{k=1}^{c}(t_k^n-y_k^n)^2
\end{equation}

这个就是前向的过程了，下面我们重点关注反向传播的过程。

Backpropagation pass

让我们先回顾一下原来的人工神经网络里面的反向传播算法是什么样子的。

首先我们定义了一个灵敏度（也就是对偏置的导数）：
\begin{equation}\label{7}
\frac{\partial E}{\partial b}=\frac{\partial E}{\partial u} \frac{\partial u}{\partial b}=\delta
\end{equation}

然后我们还能给出本层的灵敏度和上一层的灵敏度之间的关系（这个对于编程是很有用的）：
\begin{equation}\label{8}
\delta^l=(W^{l+1})^T\delta^{l+1} \circ f’(u^l)
\end{equation}

然后这些都知道了，由于是反向传播，我们从最上层，开始的，所以只要知道最上层的灵敏度：
\begin{equation}\label{9}
\delta^L=f’(u^L) \circ (y^n-t^n)
\end{equation}

这就相当于，我们知道了每一层偏置的导数，然后我们就很容易得到关于$w$的导数：
\begin{equation}\label{19}
\frac{\partial E}{\partial W^t}=x^{l-1}(\delta ^l)^T
\end{equation}

这样我们就可以使用梯度下降法进行反向传播的求解了。但是这个是不能直接应用到卷积神经网络的，主要是因为这里有卷积层的卷积操作和下采样层的下采样函数，这个都是不是那么容易求导的，我们要作相应的改动才可以。

BP for CNN

反向传播，那我们就从全链接开始吧。全连接层，和之前的反向传播算法的求解过程是一样的。所以就不在这里一一赘述了。下面，我们主要讲一下，卷积层和下采样层是怎么求解的吧。

（1）卷积层：

先让我们回去一下之前的卷积层的操作：
\begin{equation}\label{10}
x_j^l=f\left ( \sum_{i \in M_j} x_i^{l-1}*k_{ij}^l +b_j^l\right )
\end{equation}

由于上一层是下采样层，所以上一层的灵敏度因子是不够的。所以我们不能直接的使用之前的灵敏度之间的关系来获取这一层的灵敏度。这里要引入一个上采样的过程，也就是把上一层的一个灵敏度扩充为2*2 的灵敏度，具体的函数是：
\begin{equation}\label{11}
up(x)=x \otimes 1_{n \times n}
\end{equation}

这里的$\otimes$ 是$kronecker$ 乘积的意思，在$Matlab$中，我们可以使用$repmat$函数。我们上采样完了，就可以计算这一层的灵敏度了：
\begin{equation}\label{12}
\delta_j^l=\beta _j^{l+1}\left( f’(u_j^l) \circ up(\delta_j^{l+1})\right)
\end{equation}

这个就是pooling惹的祸啊！下面还有更大的麻烦呢，那就是共享权值的结果，因为这里的$b_j,k_{ij}$ 都是共享的，换句话说，这里的参数训练是和整张的特征图都是相关的，而不是仅仅和输出的一个节点有关，那我们该怎么办呢？求和吧，少年！
\begin{equation}\label{13}
\frac{\partial E}{\partial b_j^l}=\sum_{u,v}(\delta_j^l)_{uv}
\end{equation}
\begin{equation}\label{18}
\frac{\partial E}{\partial k_{ij}^l}=\sum_{u,v}(\delta_j^l)_{uv}(p_i^{l-1})_{uv}
\end{equation}

需要注意的是这里的$p_i^{l-1}$ 是之前卷积的时候，与卷积核相乘的块的\emph{转置}（这就是局部感受野惹的祸啊），这个公式计算起来可能并不是那么容易，但是Jake Bouvrie 给出了对应的$Matlab$ 公式：
$$ \frac{\partial E}{\partial k_{ij}^l}=rot180\big(conv2(x_i^{l-1},rot180(\delta_j^l),’valid’)\big)$$

这样，这一块我们就基本了解了，下面我们来看看下采样层吧。

（2）下采样层：

我们还是先回顾一下之前的计算公式：
\begin{equation}\label{14}
x_j^l=f\left( \beta_j^l down(x_j^{l-1}) +b_j^l \right)
\end{equation}
这里的下采样是一个求均值的过程。

这一个地方的灵敏度是最不好计算的，因为上一层是一个卷机层，而且这里一个特征图只有两个参数，也就是说，整张特征图都共享这两个参数。这里给出一个公式：
\begin{equation}\label{17}
\delta_j^l=f’(u_j^l) \circ \sum_{u,v}(\delta_j^{l+1})_{uv}(k_j^{l+1})_{uv}
\end{equation}
Jake Bouvrie 给出了对应的$Matlab$ 公式：

$$ \delta_j^l=f’(u_j^l)\circ conv2(x_j^{l+1},rot180(k_j^{l+1}), ‘full’)$$

给出了灵敏度因子，一切就变得好计算了：

\begin{equation}\label{15}
\frac{\partial E}{\partial b_j^l}=\sum_{u,v}(\delta_j^l)_{uv}
\end{equation}

\begin{equation}\label{16}
\frac{\partial E}{\partial \beta_j^l}=\sum_{u,v}(\delta_j^l \circ d_j^l)_{uv}
\end{equation}
这里需要注意的是，因为是下采样层，所以计算$\beta$ 的导数的时候，还是会涉及到下采样$d_j^l=down(x_j^{l-1})$，这样就基本解释清楚了。