机器学习算法推导

前言

经常在论文中看到一些熟悉又陌生的算法名，例如EM，例如GMM，HMM等等，这些算法好像都是知道个大概，但是要我自己去实现，感觉总是这里缺先验那里缺先验，不能完整地复述出来，就是不是自己的东西，有必要像矩阵求导那样，推导一个完整的式子来。

期望最大化算法

英文原名：Expectation-Maximization，缩写名：EM

问题描述

给定某个概率分布$\mathcal{X}$的系列观测值$X(\theta)$，其中$\theta$是某个未知的，需要被优化的参数，现假设待观测值$Z~\mathcal{X}$，参数估计要求算法使得似然函数$L(\theta;X)$取得最大值。即使得在出现观测值$X$的概率最大：

$$L(\theta;X)=p(X|\theta)=\sum\limits_{z\in\mathcal{Z}}p(X,Z|\theta)z$$

算法核心

由于不能直接得到隐变量$\theta$的值，且随机变量$Z$的分布情况也未知，不能直接使用求导等方式求最值，可通过迭代求解。EM只是提供了一个计算的框架，而没有给出最优化的具体方法，这需要使用最优化的理论来解决之。

期望最大化算法就分为两步：期望+最大化

求解期望

直接使用期望的定义式求出在当前似然函数$L(X,Z|\theta)$情况下的数学期望

$$\displaystyle E_{Z\sim\mathcal{X}(\theta)}[p(X,Z|\theta)]$$

使用中，通常遇到高斯分布的随机变量，因此为了简化上述表示，且不影响最值的位置，可求对数期望：

$$\displaystyle E_{Z\sim\mathcal{X}(\theta)}[\ln p(X,Z|\theta)]$$

最大化期望

在当前（对数）期望表达式已知的情况下，在$\theta$的定义域内，使用搜索算法找到一个最优解，使得：

$$\displaystyle \~\theta=\argmax_{\theta}E_{Z\sim\mathcal{X}(\theta)}[p(X,Z|\theta)]$$

然后用这个搜索得到的最优$\~\theta$代替之前分布参数$\theta$，获得新的参数分布：

$$\theta:=\~\theta$$

然后重新计算期望，并进行下一步迭代。

使用小结

本算法有一点强化学习的味道，表演家得到结果，评论家对表演结果作出评价，然后从最好的表演结果中选择一个作为下一次表演的基准，使模型能够作出最佳的表演行为（最大化期望）。

应用实例推导

高斯混合模型GMM是期望最大化算法的直接应用，其问题描述为：

现有一线性组合的高斯叠加模型$G(X)=\sum\limits_{k=1}^{K}\lambda_kN(\mu_k,\sigma_k)$，通过先验知识和前期观测操作得到了一系列观测数据集$\{x_i\}$，常见的一种情况是，在高斯分布类别数目$K$已知的情况下，求解各项高斯分布函数的参数。

另一种可能的情况是，当分布类别数目尚不明确的情况下，如何设计方法，使求解得到的高斯混合模型在期望意义下最佳？

留作习题，晚上回去推导一下。

双目立体视觉

这玩意在运动物体成像中也有应用，被称为homography estimation，即同质性估计，是一种计算机视觉中的基础问题，用于计算两个平面之间的映射关系，常用于计算相机的运动轨迹，或者计算两个平面之间的变换关系。

双目系统极线几何关系

如下图，对极几何关系是双目系统中最为重要的几何关系之一。

首先介绍几个基本的概念：

基本概念

1. 基线：两个相机的光心之间的距离，图中的$O_1O_2$；
2. 极点：两个相机的光心在另一个相机的成像平面上的投影点，图中的$e_1,e_2$；
3. 极平面：两个相机的光心和空间点P所在的平面，图中的$O_1O_2P$；
4. 极线：极平面与图像平面的交线，图中的$l_1,l_2$；
5. 极平面簇：基线随空间点P变化所形成的平面簇，所有的极平面相交于基线。

极线约束

称图中$p_2$极点与极线$l_1$满足对极关系，同理可称图中的$p_1$极点和极线$l_2$满足对极关系。在双目立体视觉中，极点不能与极点形成对应，而只能与极线对应，由此引出了极线约束的概念。极线约束是指，极点所对应的极点必定在对极线上。该约束关系极大了减少了搜索的范围，从而提高了立体视觉算法效率。约束方程如下：

$$\displaystyle \left\{ \begin{aligned} s_l\mathbf{p_l=H_lP}\\ s_r\mathbf{p_r=H_rP} \end{aligned} \right.$$

式中，$\mathbf{H_l,H_r}$是左右两个相机的内外参矩阵之乘积，即变换矩阵，可得：

$$\displaystyle \mathbf{H_l=K_l[R_l|t_l]}\triangleq[\mathbf{M}_l|\mathbf{m}_l]\\ \mathbf{H_r=K_r[R_r|t_r]}\triangleq[\mathbf{M}_r|\mathbf{m}_r]$$

利用中间量$\mathbf{P}=[X,Y,Z,1]^\mathrm{T}=[\mathbf{P}_{XYZ}^\mathrm{T},1]$消元，可得：

$$\begin{aligned} &(s_l\mathbf{p_l}-\mathbf{m}_l)\mathbf{M}_l^{-1}&=(s_r\mathbf{p_r}-\mathbf{m}_r)\mathbf{M}_r^{-1}\\ &\implies s_r\mathbf{p}_r-s_l\mathbf{M_rM_l^{-1}p_l}&=\mathbf{m_r-M_rM_l^{-1}m_l} \end{aligned}$$

上式即为极线约束的第一种形式，可根据图像坐标$\mathbf{p_1,p_2}$的齐次化消去尺度因子$s_l,s_r$。经过齐次化后，可以得到第二种形式，以下为推导过程：

记上式右边的向量为$\mathbf{m}$，则根据齐次向量相等关系（即向量与自己的向量积为0），对左式向量积$\mathbf{m}$，可得：

$$\begin{aligned} &\mathbf{m}\times(s_r\mathbf{p_r}-s_l\mathbf{M_rM_l^{-1}p_l})&=0\\ &\implies \mathbf{m}\times\mathbf{p_r}&=\mathbf{m}\times s\mathbf{M_rM_l^{-1}p_l} \end{aligned}$$

可见左式得到的结果是一个向量，且这个向量必定与$\mathbf{p}_r$正交，因此，其与$\mathbf{p}_r$的内积为0，即：

$$\begin{aligned} &\mathbf{p_r^\mathrm{T}m}\times\mathbf{p_r}&=\mathbf{p_r^\mathrm{T}m}\times s\mathbf{M_rM_l^{-1}p_l}\\ &\implies\mathbf{p_r^\mathrm{T}m}\times s\mathbf{M_rM_l^{-1}p_l}&=0\\ &\implies\mathbf{p_r^\mathrm{T}m}\times\mathbf{M_rM_l^{-1}p_l}&=0 \end{aligned}$$

可见消元完成的结果，可以写为二次型的形式，本质上该式是极平面方程的表达式，即：

$$\mathbf{p_r^\mathrm{T}}\mathbf{Fp_l}=0$$

两者的对极线关系可以非常明显地写出：

$$l_2=\mathbf{Fp_l}\longleftrightarrow p_l\\ l_1=\mathbf{F^\mathrm{T}p_r}\longleftrightarrow p_r$$

约束方程

本部分参考文献 Determining the Epipolar Geometry and its Uncertainty: A Review。
下面推导矩阵$\mathbf{F}$的具体形式，从上式中可以看出，该矩阵只与左右两个摄像机的内参数和两者摆放的相对位置（结构参数），进一步地，选取左相机图像坐标系为参考坐标系，则可以将两个相机的成像方程写为：

$$\begin{aligned} \mathbf{H_l}=\mathbf{A_l[I|0]}\\ \mathbf{H_r}=\mathbf{A_r[R|t]} \end{aligned}$$

则成像结果为：

$$\left\{\begin{aligned} s_r\mathbf{p}_r&=\mathbf{A_rRP_{XYZ}+A_rt}\\ s_l\mathbf{p}_l&=\mathbf{A_lP_{XYZ}} \end{aligned}\right.$$

注意到这里的$\mathbf{R}$是一个$4\times3$的矩阵，其中每列是正交的，因此其不是方阵，对上述方程作变形可得：

$$\left\{\begin{aligned} s_r\mathbf{A_r^{-1}p}_r-\mathbf{t}&=\mathbf{RP_{XYZ}}\\ s_l\mathbf{RA_l^{-1}p}_l&=\mathbf{RP_{XYZ}} \end{aligned}\right.\\ \implies s_r\mathbf{A_r^{-1}p}_r-s_l\mathbf{RA_l^{-1}p}_l=\mathbf{t}$$

同理，对左式向量积右式使得上式归零，可得：

$$\begin{aligned} [\mathbf{t}]_\times (\mathbf{A_r^{-1}p}_r-s\mathbf{RA_l^{-1}p}_l)=0 \end{aligned}$$

然后，内积括号里面的第一项，使得前一项归零，从而消去尺度因子$s$，可得：

$$\mathbf{p_r^\mathrm{T}A_r^\mathrm{-T}[t]_\times RA_l^\mathrm{-1}p_l}=0$$

从而得到《机器视觉》（张广军著）书上111页，或者论文中第163页公式（1）的结果式，称该结果为共平面约束，所得矩阵$\mathbf{F=A_r^\mathrm{-T}[t]_\times RA_l^\mathrm{-1}}$称为基本矩阵。此式即为三角测量、双目视觉中最重要的约束公式。

U-Net

这是在图像检测领域的一种轻量级FCN（全卷积fully convolution networks）网络，快速出定位结果。文献名：U-Net: Convolutional Networks for Biomedical Image Segmentation，作者：Olaf Ronneberger, Philipp Fischer, Thomas Brox，发表于2015年的MICCAI会议上。

网络结构

U-Net开创了对称型的纯卷积网络，其关键的设计思想在于，输入与输出的拼接，能够完成直接在输入图像上的运算和分割，从而省去了传统卷积神经网络的全连接层，原始文献的结构如图：

其中两步重要的计算，如下采样down-sampling和上采样up-sampling分别指代使得图像尺寸变小和变大的两种操作。下采样多使用池化操作，而上采样使用反卷积或者插值操作。

下采样

本文的下采样使用的是$2\times 2$最大池化，步长为2，即每隔两个像素，通过选取对应的$2\times2$的范围内像素的最大值，将其作为池化结果的一个像素。经过池化操作后的图像面积将减小为原始面积的四分之一。

上采样

本文使用的上采样是反卷积算法，原文称up convolution，又称转置卷积transpose convolution或者Deconvolution。从原理上来讲，卷积是图像与某个卷积核的移动乘积，可以通过重排卷积核，将移动乘积通过矩阵乘法实现，这也是当前卷积方法的主流操作。反卷积则是将这个重排后的卷积核进行一次转置（实际上不一定是对原始的卷积核，反卷积和卷积的核的参数不是共享的），然后完成矩阵乘法并变形为输出的结果，本质上，相当于将待卷积的图像填充为需要的形状，并进行卷积，从而得到需要的输出形状。如下图所示：

另一种方法是插值法。即在像素格子内，根据位置关系，使用双线性插值、最近邻插值等方式，扩大对应的图像面积，图像插值的结果将使得图像面积增大为原始面积的四倍。

拼接

U-Net的另一个重要特点是随时将输入图像和输入端特征图与输出结果进行拼接，保证输出信息始终多于输入信息，从面能够得到有效的输出结果。