EM估计(Expectation Maximization Algorithm)

这篇文章实际上是Ng在CS229上一个课程讲座。因为EM估计也很常用,特别是语义SLAM里面,这里根据一些粗浅的理解做一个总结备忘。

EM算法1是分为E(期望)和M(极大)的两步迭代优化算法,主要用于解决数据缺失情况下的概率估计问题。这个数据缺失其实不太好理解,有一个男女生身高的经典例子比较形象2,可以从ML到EM估计分别理解下。

1、极大似然估计(ML)

我们需要调查我们学校的男生和女生的身高分布。 假设你在校园里随便找了100个男生和100个女生。他们共200个人。将他们按照性别划分为两组,然后先统计抽样得到的100个男生的身高。假设他们的身高是服从正态分布的。但是这个分布的均值 \(\mu\) 和方差 \(\sigma^2\) 我们不知道,这两个参数就是我们要估计的。记作 \(\theta=[\mu,\sigma]^T\)。 这是一个典型的极大似然估计问题,我们知道100个男生,100个女生和他们的身高,我们想要估计男生的身高分布均值方差,女生的身高分布均值方差,都可以用极大似然估计来解决。

我们已知的有两个:样本服从的分布模型、随机抽取的样本;我们未知的有一个:模型的参数。根据已知条件,通过极大似然估计,求出未知参数。总的来说:极大似然估计就是用来估计模型参数的统计学方法。

因为我们知道哪个样本是男生哪个样本是女生,所以这一问题就分解成分别估计男生和女生的\(\theta=[\mu,\sigma]^T\)即可。那么以男生为例,设样本集 \(X={x_{1},x_{2},…,x_{N}}\),其中 \(N=100\),概率密度函数 \(p(x_{i}|\theta)\),首先写出似然函数也就是所有男生概率的乘积:

\(l(\theta)=L\left(x_{1}, \cdots, x_{n} ; \theta\right)=\prod_{i=1}^{n} p\left(x_{i} ; \theta\right), \theta \in \Theta \tag{1}\)

通常转为求解对数似然函数:

\(H(\theta)=\ln L(\theta)=\ln \prod_{i=1}^{n} p\left(x_{i} ; \theta\right)=\sum_{i=1}^{n} \ln p\left(x_{i} ; \theta\right) \tag{2}\)

极大似然估计就是求似然函数最大值(或者对数似然函数最小值):

\(\hat{\theta}=\arg \max _{\theta} l(\theta)=\arg \max _{\theta} \prod_{i=1}^{N} p\left(x_{i} | \theta\right) \tag{3}\)

这个极值自然就是通过求导得到:

\(\frac{d l(\theta)}{d \theta}=0\) 或者 \(\frac{d H(\theta)}{d \theta}=\frac{d \ln l(\theta)}{d \theta}=0 \tag{4}\)

特别的,对于正态分布样本 \(N\left(\mu, \sigma^{2}\right)\),其似然函数为:

\(L\left(\mu, \sigma^{2}\right)=\prod_{i=1}^{N} \frac{1}{\sqrt{2 \pi} \sigma} e^{-\frac{\left(x_{i}-\mu\right)^{2}}{2 \sigma^{2}}}=\left(2 \pi \sigma^{2}\right)^{-\frac{n}{2}} e^{-\frac{1}{2 \sigma^{2}} \sum_{l=1}^{n}\left(x_{i}-\mu\right)^{2}} \tag{5}\)

对数为:

\(\ln L\left(\mu, \sigma^{2}\right)=-\frac{n}{2} \ln (2 \pi)-\frac{n}{2} \ln \left(\sigma^{2}\right)-\frac{1}{2 \sigma^{2}} \sum_{i=1}^{n}\left(x_{i}-\mu\right)^{2} \tag{6}\)

求导得方程组:

\(\left\{\begin{array}{l}{\frac{\partial \ln L\left(\mu, \sigma^{2}\right)}{\partial \mu}=\frac{1}{\sigma^{2}} \sum_{i=1}^{n}\left(x_{i}-\mu\right)} \\ {\frac{\partial \ln L\left(\mu, \sigma^{2}\right)}{\partial \sigma^{2}}=-\frac{n}{2 \sigma^{2}}+\frac{1}{2 \sigma^{4}} \sum_{i=1}^{n}\left(x_{i}-\mu\right)^{2}=0}\end{array}\right. \tag{7}\)

则似然方程的唯一解为:

\(\left\{\begin{array}{l}{\mu^{*}=\overline{x}=\frac{1}{n} \sum_{i=1}^{n} x_{i}} \\ {\sigma^{* 2}=\frac{1}{n} \sum_{i=1}^{n}\left(x_{i}-\overline{x}\right)^{2}}\end{array}\right. \tag{8}\)

这个就是它的最大值点。也就是通过极大似然估计给出的符合当前样本的参数估计。

2、Jensen不等式

对于一个凸函数 \(f(X)\)(凸函数的定义为:对于X为实变量,\(f^{\prime \prime}(x) \geq 0 \text { (for all } x \in \mathbb{R} )\),对于X为向量,),其中X是随机变量则有如下不等式成立:

\(E[f(X)] \geq f(E X) \tag{9}\)

其中等号成立的条件当且仅当\(X=EX\),也就是随机变量为一个常数c:\(X=c\)。

Jensen不等式直观理解可以参见下图:

图中,实线f是凸函数,X是随机变量,有0.5的概率是a,有0.5的概率是b。(就像掷硬币一样)。X的期望值就是a和b的中值了,图中可以看到 \(E[f(X)] \geq f(E X)\) 成立。

对于f是凹函数的情况,则正相反:\(E[f(X)] \leq f(E X)\)。

3、最大期望估计(EM)

对比极大似然估计,EM估计理解起来非常简单,例如对于上述男女生的例子,我们现在有200个男女生的样本,但是我们不知道哪个样本属于男生哪个样本属于女生(信息缺失)。

3.1 EM估计公式推导

样本集 \(X={x_{1},x_{2},…,x_{m}}\),包含 m 个独立的样本;每个样本 \(x_i\) 对应的类别 \(z_i\)  是未知的(即上文中每个样本属于哪个分布是未知的);我们需要估计概率模型 \(p(x,z)\) 的参数 \(\theta\),即需要找到适合的 \(\theta\) 和 \(z\) 让 \(L(\theta)\) 最大。根据上文极大似然估计中的似然函数取对数所得 \(logL(\theta)\),可以得到如下式:

\(\begin{align*} \ell(\theta) &=\sum_{i=1}^{m} \log p(x ; \theta) \tag{10}\\ &=\sum_{i=1}^{m} \log \sum_{z} p(x, z ; \theta) \tag{11}\end{align*}\)

其中第二项 \(z\) 的求和在样本缺失情况下不容易做到。但是如果 \(z\) 的概率确定后,这个求和就很容易了,EM估计就是分成两个步骤来迭代实现了这样一个估计过程。

定义 \(Q_i(z)\) 表示 \(z\) 的概率,显然 \(\sum_{z} Q_{i}(z)=1, Q_{i}(z) \geq 0\)。将上述公式展开:

\(\begin{align*} \sum_{i} \log p\left(x^{(i)} ; \theta\right) &=\sum_{i} \log \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right) \tag{12} \\ &=\sum_{i} \log \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \tag{13} \\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \tag{14}\end{align*}\)

式 (13) 就是分子分母同乘概率 \(Q_i(z)\),但是显然和的对数求导并不好求;式 (14) 根据 Jensen不等式而来,其中 \(f(x)=log(x)\) 是一个凹函数,同时设 \(X=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\),则 \(EX=\sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right)\left[\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\right]\),根据 Jenson 不等式 \(f(EX) \geq E[f(X)]\),则有:

\(\log \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \geq \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \tag{15}\)

再对i求和就得到了我们想要的公式。

根据之前的结论,仅当随机变量为常数时等号成立则有:

\(\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}=c \tag{16}\)

显然 c 与 \(z_i\) 无关,则说明 \(Q_{i}\) 只和 \(p\left(x^{(i)}, z^{(i)} ; \theta\right)\) 有关,我们可以用后者作为前者的概率表达:

\(Q_{i}\left(z^{(i)}\right) \propto p\left(x^{(i)}, z^{(i)} ; \theta\right) \tag{17}\)

则显然可以推导:

\(\begin{align*} Q_{i}\left(z^{(i)}\right) &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{\sum_{z} p\left(x^{(i)}, z ; \theta\right)} \tag{18} \\ &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{p\left(x^{(i)} ; \theta\right)} \tag{19} \\ &=p\left(z^{(i)} | x^{(i)} ; \theta\right) \tag{20} \end{align*} \)

至此,我们推出了在固定其他参数 \(\theta\) 后,\(Q_{i}\left(z^{(i)}\right)\) 的计算公式就是后验概率,解决了 \(Q_{i}\left(z^{(i)}\right)\) 如何选择的问题。这一步就是E步,建立 \(logL(\theta)\) 的下界。接下来的M步,就是在给定 \(Q_{i}\left(z^{(i)}\right)\) 后,调整\(\theta\),去极大化 \(logL(\theta)\) 的下界,是一个典型的极大似然估计过程(在固定 \(Q_{i}\left(z^{(i)}\right)\) 后,下界还可以调整的更大)。

如果继续用上面形象一点的例子就是:

E步:估计出男生和女生的概率分布;

M步:在上述概率分布的前提下,用极大似然估计得到当前最优的参数。

反复迭代直到收敛。

3.2 EM估计的基本步骤

基于以上推导,EM估计的典型迭代步骤如下:

循环重复直到收敛 {

(E-步骤) 对于每一个i,计算概率: \(Q_{\mathrm{i}}\left(z^{(\mathrm{i})}\right) :=p\left(z^{(i)} | x^{(\mathrm{i})} ; \theta\right)\)

(M-步骤) 使用极大似然估计最优参数:\(\theta :=\arg \max _{\theta} \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\)

}

3.3 EM估计有效性的证明

我们需要证明上述的步骤一定可以得到收敛的结果,也就是 \(\ell\left(\theta^{(t)}\right) \leq \ell\left(\theta^{(t+1)}\right)\) 我们整体的极大似然估计在每次迭代后一定单调增加,那么我们一定可以在一定次数的迭代后极大似然估计不再增加也就得到了整个系统的概率最大值的参数估计,这一参数就同时包含了极大似然估计 \(\theta\) 以及缺失的参数 \(z\)。

证明如下:

对于给定 \(\theta^{(t)}\) 我们在 E 步骤选定概率函数如下:

\(Q_{i}^{(t)}\left(z^{(i)}\right) :=p\left(z^{(i)} | x^{(i)} ; \theta^{(t)}\right) \tag{21}\)

根据之前证明,这一概率函数 \(Q_{i}^{(t)}\left(z^{(i)}\right)\) 使得前述公式中的 Jensen 不等式等号成立也就是:

\(\ell\left(\theta^{(t)}\right)=\sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} \tag{22}\)

则有如下推导:

\(\begin{align*} \ell\left(\theta^{(t+1)}\right) & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t+1)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} \tag{23} \\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} \tag{24} \\ &=\ell\left(\theta^{(t)}\right) \tag{25} \end{align*}\)

其中式 (23) 与前述 3.1 中的公式推导一样,只是 \(\theta^{(t)}\) 换成了 \(\theta^{(t+1)}\)。式 (24) 是因为 \(\theta^{(t+1)}\) 是对公式 (22) 进行极大似然估计的结果,也就是 \(\theta^{(t+1)}\) 是使得公式中 \(\theta^{(t)}\) 最大的那个值:

\(\theta^{t+1} = \arg \max _{\theta} \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \tag{26}\)

显然用 \(\theta^{(t+1)}\) 代替 \(\theta^{(t)}\) 是递增的。

根据上面的证明,可以知道 \(\ell\left(\theta^{(t)}\right) \leq \ell\left(\theta^{(t+1)}\right)\),那么我们一定能够通过 EM估计得到最优的结果。

如果我们定义:

\(J(Q, \theta)=\sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \tag{27}\)

则EM估计可以看过是J的坐标上升法:,E步固定 \(\theta\),优化 \(Q\),M步固定 \(Q\) 优化 \(\theta\)。

参考资料

1.
Arthur D, Nan L, Donald R. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B. 1977;39(1):1–38.
2.
漫谈 Clustering (番外篇): Expectation Maximization « Free Mind. 漫谈 Clustering (番外篇): Expectation Maximization. http://blog.pluskid.org/?p=81. Accessed May 29, 2019.
3.
EM算法(Expectation Maximization Algorithm)详解. EM算法(Expectation Maximization Algorithm)详解. https://blog.csdn.net/zhihua_oba/article/details/73776553. Accessed May 29, 2019.
4.
Expectation–maximization algorithm. Expectation–maximization algorithm. https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm. Accessed May 29, 2019.
5.
极大似然估计详解. 极大似然估计详解. https://blog.csdn.net/zengxiantao1994/article/details/72787849. Accessed May 29, 2019.
6.
(EM算法)The EM Algorithm – JerryLead – 博客园. (EM算法)The EM Algorithm. https://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html. Accessed May 29, 2019.

论文材料

 

论文笔记:NetVLAD: CNN architecture for weakly supervised place recognition

NetVLAD1是一个较早的使用 CNN 来进行图像检索或者视频检索的工作,后续在此工作的基础上陆续出了很多例如 NetRVLAD、NetFV、NetDBoW 等等的论文,思想都是大同小异。

一、图像检索

VLAD 和 BoW、Fisher Vector 等都是图像检索领域的经典方法,这里仅简介下图像检索和 VLAD 的基本思想。

图像检索(实例搜索)是这样的一个经典问题:

1、我们有一个图像数据库 \(I_i\) 通过函数可以得到每一个图像的特征 \(f(I_i)\);

2、我们有一个待查询图像 \(q\) 通过函数得到它的特征 \(f(q)\);

3、则我们获得的欧氏距离 \(d(q, I) = \parallel  f(q) – f(I)\parallel\) 应该满足越相近的图像 \(d(q, I)\) 越小。

二、VLAD (Vector of Locally Aggregated Descriptors)

而 VLAD (Vector of Locally Aggregated Descriptors)则是图像检索中一个经典方法,也就可以理解为怎么获得上述的 \(f\) 的方法,记为 \(f_{VLAD}\)。通常在传统方法中我们会获得一系列的局部特征(SIFT、SURF、ORB)之类,假设为 N 个 D 维的局部特征(通常 N 可能比较大,而且每幅图特征多少不一,N 可能数量也不一定),我们希望通过这 N*D 维特征获得一个可以表示图像全局 K*D 维特征的方法(通常K是我们指定的数目,例如128维)。VLAD 的主要流程如下:

1、对全部 N*D 维局部特征进行 K-Means 聚类获得 K 个聚类中心,记为 \(C_k\)

2、通过以下公式将 N*D 维局部特征编写为一个全局特征 V,特征向量维数为 K*D,其中 \(k\in K\) \(j\in D\),公式如下:

\(\begin{equation}V(j, k) = \sum_{i=1}^N a_k(x_i) (x_i(j) – c_k(j))\end{equation}\)

其中 \(x_i\) 为第i个局部图像特征,\(c_k\) 为第k个聚类中心,\(x_i\) 和 \(c_k\) 都是 D 维向量。\(a_k(x_i)\) 是一个符号函数,当且仅当 \(x_i\) 属于聚类中心 \(c_k\) 时,\(a_k(x_i)=1\) ,否则 \(a_k(x_i)=0\)。

经过上面对于经典 VLAD 方法的解释,我们可以看出来 \(f_{VLAD}\) 是一个将若干局部特征压缩为一个特定大小全局特征的方法,通过聚类,实现了将特征降维,同时用特征与聚类中心的差值作为新的特征值,在实践中 VLAD 方法具有较好的检索效果。

三、NetVLAD

1、经典 VLAD 公式的可微化

经典 VLAD 方法显然是一个不可导的函数,其中主要不可导的地方在于 \(a_k(x_i)\) 这样一个符号函数,因此为了将 VLAD 变可训练的函数,必须将其变成可微计算。作者将 \(a_k(x_i)\) 平滑化:

\(\bar{a}_k(x_i)=\frac{e^{-\alpha\left \| x_i – c_k \right \|^2}}{\sum_{{k}’}e^{-\alpha\left \| x_i – c_{{k}’} \right \|^2}}\in (0,1)\)

这里面 \(\alpha\) 是一个正值参数,显然当 \(\alpha\rightarrow \infty \) 时,\(\bar{a}_k(x_i)\) 更趋近于 0 和 1 的两级。

再将 \(-\alpha \left \| x_i – c_k \right \|^2\) 展开,显然 \(e^{-\alpha\left \| x_i \right \|^2}\) 可以被约掉,因此得到:

\(\bar{\alpha}_k(x_i)=\frac{e^{w^T_kx_i+b_k}}{\sum_{{k}’}e^{w^T_{{k}’}+b_{{k}’}}}\)

其中 \(w_k=2\alpha c_k\) ,\(b_k=-\alpha\left \| c_k \right \|^2\),其实仔细观察这个公式,就是一个 softmax。

这样 VLAD 公式就被改写为:

\(\begin{equation}V(j, k) = \sum_{i=1}^N\frac{e^{w^T_kx_i+b_k}}{\sum_{{k}’}e^{w^T_{{k}’}+b_{{k}’}}}(x_i(j) – c_k(j))\end{equation}\)

显然这里面 \(w_k\) 、\(b_k\) 和 \(c_k\) 都是 NetVLAD 需要学习的参数。

2、NetVLAD 通过监督学习获得聚类中心的好处

我们这样将 \(c_k\) 作为学习参数有什么好处呢,论文中用了一幅图进行了直观解释:

传统 VLAD 的中心是聚类出来的,没有监督的标签数据 \(c_k^{VLAD}\) ,在聚类时我们使用了很多图像这些图像的描述符之间没有关系,那么也就很可能把本来不是一个物体的描述符聚为一类,使得我们原本期望的类内描述符都是一个物体的feature不太容易达到。而在使用监督数据进行训练时,我们可以已知图像数据属于同一物体,那么训练时就可以只把属于同一物体的特征聚在一起而把不是的划分到其他类别,这样就可能学习出一个更好的 \(c_k^{NetVLAD}\) 聚类中心,使得最终的特征更有区分度。

3、网络实现

首先,由于是 NN 的方法,我们这里使用 CNN Feature 代替了传统 VLAD 中的 N 个局部描述子,CNN 是一个全局的特征,它的 Feature Map 是 W*H*D 大小,那么类比于我们之前的传统方法 N*D,我们这里 NetVLAD 目标就是将 W*H*D (N=W*H)的特征转换为 K*D 的特征;

其次,我们将整个 NetVLAD 看做一个 pooling layer,它的作用是实现降最终和 VLAD 一样获得我们想要的 K*D 维描述子。

具体实现上,我们就分步骤来做,这部分作者的 PPT 里面有张图非常清晰:

1、实现 \(z_k=w_k^Tx_i+b_k\),也就是公式中的蓝色部分,论文里直接通过一个1×1的卷积来做。这也是1×1卷积的一个应用;

2、实现 \(\sigma_k (z)=\frac{e^{z_k}}{\sum_{{k}’} e^{z_{{k}’}} }\),也就是公式中的黄色部分,如之前所述这实际上就是一个 softmax 公式,论文里直接通过一个 softmax 来做;

3、实现 \(x_i (j)- c_k(j)\),也就是公式中的绿色部分,这部分就是一个减法,直接用一个 VLAD core来做;

4、1~3已经实现了 \(V(j,k)\) 的计算了,后面按照 All about VLAD 论文还要对 \(V(j,k)\) 做两步简单的归一化(这篇论文证明了归一化可以提升检索性能),包括:

1)intra-normalization

这个主要意思是将每一个 VLAD block(也就是每个聚类中心的所有残差)分别作 l2 normalization。

2) l2 normalization

这个是将所有 VLAD 特征一起做 l2 normalization。

四、弱监督训练

1、弱监督数据的获取

在图像检索中,训练通常需要明确的图像到底是哪个物体的标注。而论文针对的领域是地点识别,因此可以利用图片的位置信息,将 Google Street View 的数据作为训练图片,将同一地点、不同视角、不同时间的数据作为同一物体标签进行训练。相对并没有明确的标注图上面都是那个物体,只是说这几幅图中可能看到同样的一个物体,数据比较容易获取。这在机器人领域同样也是可行的。

2、弱监督 triplet ranking loss

我们将整个网络看做一个特征提取函数 \(f_{\theta}\) ,那我们的目标自然就是:对于一个需要检索的图像 \(q\) ,我们有一个数据库 \(I\),我们希望位置最近的图片\(I_{i*}\) 的特征欧氏距离,比其他所有图片\(I_{i}\) 的距离都要小:

\(d_{\theta}(q, I_{i*}) < d_{\theta}(q, I_i)\)

然而理想情况是这样,如刚才小节所述我们实际上不能获取最近的图片 \(I_{i*}\),但我们可以获取相近的图片集合(作为正样本) \(p_{i*}^q\),这些正样本集合一定包含了我们想要的 \(I_{i*}\),但是我们不知道是哪一个;同样,我们也可以获取绝对不可能是同一物体的负样本集合 \(n_j^q\) ,比如远离所选地点的图片。那么我们至少可以期望获得这样的结果:所有正样本集合的特征距离,应该要比负样本集合的特征距离要小:

\(d_{\theta}(q, p_{i}^q) < d_{\theta}(q, n_j^q)\)

并且正样本中距离最近的应该就是我们想要的最近图片:

\(p_{i*}^q=\underset{p_i^q}{argmin}d_{\theta}(q, p_i^q)\)

据此,我们构造如下 loss:

\(L_{\theta}=\underset{j}{\sum}l\left ( \underset{i}{\min} d_{\theta}^2 (q,p_i^q)+m-d_{\theta}^2(q,n_j^q)\right )\)

其中 \(l(x)=max(x,0)\) 也就是所说的 hinge loss,m是一个常量表示我们给负样本设置的 margin。这个 loss 与 triplet loss 是很像的。

3、训练&实现

作者在附录中给出了详细的实现细节,网络提取部分作者使用 VGG-16 但做了一些修改,对于 VLAD 的聚类中心使用 K=64,m=0.1。

训练 lr = 0.001 或 0.0001,优化器 SGD,momentun 0.9,weight decay 0.001,batchsize=4 turples。这里不一一例举。具体还是看作者的代码比较好。

论文下载

1、PDF:NetVLAD: CNN architecture for weakly supervised place recognition

2、PPT:cvpr16_NetVLAD_presentation.pptx

3、Code:

https://github.com/Relja/netvlad (作者的,使用 MatConv 框架)

https://github.com/sitzikbs/netVLAD/blob/master/netVLAD.py (第三方实现,不过只有 VLAD layer 部分)

https://github.com/shamangary/LOUPE_Keras (第三方实现,不过只有 VLAD layer 部分)

参考文献

  1. 1.
    Arandjelovic R, Gronát P, Torii A, Tomás Pajdla, Sivic J. NetVLAD: CNN architecture for weakly supervised place recognition. CoRR. 2015;abs/1511.07247.

Tensorflow C API 从训练到部署:使用 C API 进行预测和部署

前述博文 Tensorflow C++ 从训练到部署(2):简单图的保存、读取与 CMake 编译Tensorflow C++ 从训练到部署(3):使用 Keras 训练和部署 CNN 使用 Tensorflow/Keras 的 Python API 进行训练,并使用 C++ API 进行了预测。由于 C++ API 需要编译 Tensorflow 源码,还是比较麻烦的。而 Tensorflow 官方提供了 C API 编译好的库文件,相对部署上比较容易(直接复制库文件到自己的工程即可),本文将介绍使用 C API 进行预测的方法。对于 Python 训练部分,与前述文章相同不做赘述。

0、系统环境
Ubuntu 16.04
Tensorflow 1.12.0

1、安装依赖
1、GPU 支持安装(可选)
CUDA 9.0
cnDNN 7.x

2、Tensorflow 1.12.0
下载地址:
https://www.tensorflow.org/install/lang_c

其中 1.12.0 的下载地址如下(我这里提供了包含TX2 aarch64在内的几个版本):

TensorFlow C libraryCUDAcuDNNURL
Linux x86_64 CPUxxhttps://pan.baidu.com/s/1FDdXCgtJJlDJP8ziDs6dow
Linux x86_64 GPU9.07.xhttps://pan.baidu.com/s/1qxDntkQ-rcgvp1xxrSKW0w
macOS CPUxxhttps://pan.baidu.com/s/1F6NdNtCxg11P_EpEdsqttA
Linux aarch64 GPU (TX2)9.07.0.5https://pan.baidu.com/s/1mI76203wY9Nd5US4sH5-pg

将库解压到 third_party/libtensorflow 目录。

如果上面的版本都不符合你的需求,你可以参照这篇文章编译你需要的版本。

2、TFUtils 工具类
为了简便起见,我们首先将常用的 C API 封装为

1)文件 utils/TFUtils.hpp:

2)文件 utils/TFUtils.cpp:

3、简单图的读取与预测
在前述文章 Tensorflow C++ 从训练到部署(2):简单图的保存、读取与 CMake 编译 中我们已经介绍了一个 c=a*b 的简单“网络”是如何计算的。

其中 Python 构建网络和预测部分就不重复了,详见该文所述。这里直接给出 C API 的代码:

文件名:simple/load_simple_net_c_api.cc

简单解释一下:

这一行是加载 pb 文件。

这一段是创建两个输入 tensor 以及输入的 ops。注意这里的 CreateTensor 在后面都需要调用 DeleteTensors 进行内存释放。输出的 tensors 还没创建先定义为 nullptr。

这一行是运行网络。

这两行是从输出的 output_tensors 读取数据到一个二维vector const std::vector>,我们这里输出只有 “c” 一个名字,而且只有一个索引 0,因此直接取出 data[0] 就是我们原本想要的输出。

编译运行这一文件,如果没有问题则会得到如下输出:

4、CNN的读取与预测
与刚才小节3相似,CNN网络也是一样的流程,还是以最基本的 fashion_mnist 为例,该网络的训练和保存流程请参考之前的文章。这里我们仅介绍 C API 进行预测的部分。由于我们这里需要读取一幅图并转化成 Tensor 输入网络,我们构造一个简单的函数 Mat2Tensor 实现这一转换:

1)Met2Tensor 部分文件:fashion_mnist/utils/mat2tensor_c_cpi.h

2)网络读取与预测,这部分与刚才的小节3基本一样,就不做解释了:

编译运行这一文件,如果没有问题,则会得到如下输出:

到此,我们就完成了使用 C API 运行 Tensorflow Model 的流程。

本文中的全部代码均已开源:
https://github.com/skylook/tensorflow_cpp

参考文献
[1] https://github.com/Neargye/hello_tf_c_api
[2] https://www.tensorflow.org/api_docs/python/tf/contrib/saved_model/save_keras_model
[3] https://www.tensorflow.org/install/lang_c

[TX2] Tensorflow 1.12.0 在 Jetson TX2 上的编译

系统环境
Ubuntu 16.04
Jetpack 3.2.1 on TX2 [Link](with CUDA 9.0 cuDNN 7.0.5)

1、编译准备
1)配置环境

2)安装依赖
Java

Bazel (Tensorflow 使用 Bazel 0.15 编译,因此这里下载 0.15.2 版本,详情参见这里)

2、编译 Tensorflow
1)下载源码
运行如下命令下载 tensorflow 1.12.0 版本源码:

2)修改源码
为了在 TX2 上编译通过,需要 apply this patch
具体说明如下:

2.1)打开文件:tensorflow-1.12.0/tensorflow/contrib/lite/kernels/internal/BUILD
查找:

修改成:

2.2)打开文件:tensorflow-1.12.0/third_party/aws.BUILD
查找:

修改成:

3)编译配置

其中会提示若干选项,请参考如下进行选择:

3)编译
由于 TX2 上面内存只有 8G,因此编译 C Lib 时需要限制内存使用不超过8G,如果直接按照官方的方式是会报错的,当然你也可以设置 swap 来解决。我这里直接设置为4G,你可以根据需要进行调整,但是最好不要超过8G:

这一过程大约需要5、6个小时,如果最后提示编译成功,则会在如下目录生成 libtensorflow.tar.gz 文件
bazel-bin/tensorflow/tools/lib_package/libtensorflow.tar.gz

至此就完成了 TX2 上 Tensorflow 版本的编译。

下面是包含 TX2 在内的几个常用 Tensorflow C Lib 地址,不想编译的直接下载我这里的网盘文件即可:

TensorFlow C libraryCUDAcuDNNURL
Linux x86_64 CPUxxhttps://pan.baidu.com/s/1FDdXCgtJJlDJP8ziDs6dow
Linux x86_64 GPU9.07.xhttps://pan.baidu.com/s/1qxDntkQ-rcgvp1xxrSKW0w
macOS CPUxxhttps://pan.baidu.com/s/1F6NdNtCxg11P_EpEdsqttA
Linux aarch64 GPU (TX2)9.07.0.5https://pan.baidu.com/s/1mI76203wY9Nd5US4sH5-pg

参考文献
[1] https://github.com/tensorflow/tensorflow/blob/master/tensorflow/tools/lib_package/README.md
[2] https://jkjung-avt.github.io/build-tensorflow-1.8.0/
[3] https://github.com/peterlee0127/tensorflow-nvJetson

Deep Local Feature 文章 & 数据收集

在 SLAM 中 Local Feature 的提取和匹配是一个比较重要的内容,近些年有很多相关的使用 Deep Learning 学习局部描述子的工作,这里做一下相关文章和代码收集。后续如有精力会进行速度和性能比较。

文章收集

文章会议PDF代码
GeoDesc: Learning Local Descriptors by Integrating Geometry ConstraintsECCV 2018PDFCode
DELF: DEep Local FeaturesCVPR 2018PDFCode
LF-Net: Learning Local Features from ImagesNIPS 2018PDFCode
AffNet: Repeatability Is Not Enough: Learning Discriminative Affine Regions via DiscriminabilityECCV 2018PDFCode
SuperPoint: Self-Supervised Interest Point Detection and DescriptionCVPR 2018PDFCode
DeepCD: Learning Deep Complementary Descriptors for Patch RepresentationsICCV 2017PDFCode
HardNet: Working hard to know your neighbor's margins: Local descriptor learning lossNIPS 2017PDFCode
TFeat: shallow convolutional patch descriptorBMVC 2016PDFCode
LIFT: Learned Invariant Feature TransformECCV 2016PDFCode

数据收集

数据集名称下载地址
Phototourhttp://phototour.cs.washington.edu/patches/default.htm
HPatcheshttps://github.com/hpatches/hpatches-dataset

Tensorflow C++ 从训练到部署(3):使用 Keras 训练和部署 CNN

在上一篇文章中我们并没有去训练一个真正的网络和解决一个实际问题,我们所做的是构建了一个 c = a * b 的计算图,并用 python 进行了保存和 c++ 进行了读取,这一保存和读取中也仅包含图的结构并没有相关参数。本篇文章中我们进一步以 Tensorflow 官方的 Fashion MNIST 为例,完成一个简单的分类问题。本文前面 Keras 训练模型以及转化到 Tensorflow 格式部分与之前一篇博客(Keras 转换成 Tensorflow 模型格式并使用)基本一致。本文主要包含:
1)Python:Fashion MNIST 数据集
2)Python:使用 Keras 定义 CNN 模型、训练并保存
3)Python:转换 Keras 模型到 Tensorflow 格式并保存
4)Python:使用 Tensorflow Python API 加载模型并预测
5)C++:使用 Tensorflow C++ API 加载模型并预测

0、系统环境
Ubuntu 16.04
Tensorflow 1.12.0 (安装详见官网,本文环境使用 pip 方式安装)

1、Fashion MNIST 数据集
1)数据简介
Fashion-MNIST [1] 是一个替代MNIST手写数字集的图像数据集。 它是由Zalando(一家德国的时尚科技公司)旗下的研究部门提供。其涵盖了来自10种类别的共7万个不同商品的正面图片。Fashion-MNIST的大小、格式和训练集/测试集划分与原始的MNIST完全一致。60000/10000的训练测试数据划分,28×28的灰度图片。你可以直接用它来测试你的机器学习和深度学习算法性能,且不需要改动任何的代码 [11]。

典型的 Fashion-MNITST 数据是这样的,其中每三行表示一个类别:
fashion-mnist-sprite

Fashion-MNIST 与 MNIST 同样有 10 个类别,不过并不是 0-9 的 10 个数字,它的类别如下:

screenshot-from-2018-09-25-11-50-54

我们使用过以前的 MNIST 数据集都知道,随便弄个很简单的网络,就可以轻轻松松刷出 99% 以上的分数了,即使传统方法也很容易达到高分。所以 MNIST 手写数字识别由于过于简单,作为一个基本的实验数据已经没有什么意义了。Tensorflow 和很多深度学习框架现在的入门数据也都推荐 Fashion MNIST。

2)数据读取
其实 Keras 为我们提供了简单的接口可以一键下载 Fashion-MNIST 数据并且读取:

不过由于天朝网络的原因,我并不推荐这种方式,建议直接下载到本地读取。我这里将数据直接存到 data/fashion 目录下。
百度网盘下载:
https://pan.baidu.com/s/19zZqU5tSwZyY780z8Y8_VA

读取数据代码如下(保存为:utils/mnist_reader.py):

2、使用 Keras 定义 CNN 模型、训练并保存
下面的代码中我们定义了一个非常简单的 CNN 网络,结构图如下:
model

我们使用这一网络进行训练并且保存为 Keras 标准的 h5 格式。这一部分代码比较基础,就不做过多解释了。

Keras 模型定义和训练代码如下(保存为:train.py):

如果你的运行没有问题则会看到类似如下输出:

同时在 models/ 文件夹下保存了 fashion_mnist.h5 文件,这一文件包含了模型的结构和参数。

3、转换 Keras 模型到 Tensorflow 格式并保存
这一环节我们使用 keras_to_tensorflow [2] 转换工具进行模型转换,其实这个工具原理很简单,首先用 Keras 读取 .h5 模型文件,然后用 tensorflow 的 convert_variables_to_constants 函数将所有变量转换成常量,最后再 write_graph 就是一个包含了网络以及参数值的 .pb 文件了。

具体代码参见(原始代码中可以传入输出 node 数量和名字并使用 identity 生成新的 tensor,我这里稍作修改,直接读取 Keras 的 outputs 的操作名,最后会输出原始 inputs 和 outputs 的名字供后面使用):

Tensorflow 模型转换代码(保存为:utils/keras_to_tensorflow.py)

我们执行如下命令转换 Keras 模型到 Tensorflow 的 pb 格式:

如果你的运行无误的话则会显示如下信息并生成 models/fashion_mnist.h5.pb 这个就是转换过来的 Tensorflow 格式:

这里面也告知了你模型输入和输出的 Tensor 名字,这两个信息很重要我们后面会用到。

4、使用 Tensorflow Python API 加载模型并预测
我们使用标准的 Tensorflow Low-Level API 加载和预测代码如下(保存为:load_predict.py)

这段代码中前面同样是读取 Fashion MNIST 数据集,与训练代码一样。部分代码说明如下:

读取 pb 模型文件:

获取当前的计算图:

获取输出的 Tensor:

可以看到除了之前我们给出的输出 Tensor 名称 output_class/Softmax 外,我们还需要加上一个索引 :0。关于这一问题的解释可以参见 [12]。我们这里简单来理解,”output_class/Softmax” 是指定了一个 Operation 的名字,对应最后 Softmax 层,大部分层的输出都是一个 Tensor,不过也有可能一个层产生多个输出 Tensor,因此我们这里需要指定是哪个输出。通常对于一个输出的时候就是用 :0 指定,对于 Input 也是同理。

执行计算图并打印输出结果,其中 feed_dict={‘input_image_input:0’: test_images} 将 test_images 作为输入传入网络:

执行整个代码:

如果运行没有问题则可以看到如下结果:

与之前我们使用 Keras 的 predict 接口结果对比,是一样的,说明我们转换后的模型无误。

关于 Keras 转换成 Tensorflow 模型和预测的步骤就到这里。完整示例可以参见:
https://github.com/skylook/tensorflow_cpp

5、使用 Tensorflow C++ API 加载模型并预测
1)使用 C++ 转换 OpenCV 的 Mat 到 Tensor
Tensor 要求输入的是归一化的 float32 格式图片,实际我们使用如下代码来完成 OpenCV Mat 到 Tensor 的转换(保存为:utils/mat2tensor.h)

这段代码比较简单,就是声明一个 {1, img.size().height, img.size().width, img.channels()} 的单个 Tensor,将地址直接赋给 fake_mat,然后使用 OpenCV 把图片转成 float32 格式,声明的 Tensor 自然也就转成了 float32 格式。最后是根据输入 normal 因子进行归一化。这一归一化方法和之前训练时一致。

2)使用 C++ 调用 pb 模型并预测
与前面的文章类似,我们参考 Python 调用 pb 模型及预测接口使用 C++ API 调用之前转换的模型并预测代码如下(保存为:load_predict.cpp):

如果编译运行没有问题的话,会输出如下结果:

输入和调用模型与之前的博客基本一致,这里解释下输出部分:

这里 flat_inner_dims 的 API 官方说明如下:
screenshot-from-2018-10-15-18-57-02

表示将按照指定类型 T 和指定维度 NDIMS 的 Eigen::TensorMap 输出,需要说明的是这一 T 和 NDMS 维度必须与模型中实际输出类型一致,否则运行时会报错。TensorMap 相当于 Tensor 的一个引用,其内存地址并不像 Tensor 一样是自己创建与释放的,因此没有 resize 等操作,其他使用方法与 Tensor 类似。关于 Eigen::Tensor 使用说明参见 [6] 和 [7]。

其中 tensorflow::TTypes::Tensor 与 Eigen::TensorMap, Eigen::Aligned> 其实是等价的,因此上面那一行也可以替换成:

到这里我们就完整介绍了一个 CNN 网络从 Keras 训练、转成 Tensorflow 格式到 C++ 部署的基本流程。

本文完整代码参见 Github:
https://github.com/skylook/tensorflow_cpp

参考文献
[1] https://www.tensorflow.org/tutorials/keras/basic_classification
[2] https://medium.com/tensorflow/hello-deep-learning-fashion-mnist-with-keras-50fcff8cd74a
[3] https://github.com/zalandoresearch/fashion-mnist
[4] https://zhuanlan.zhihu.com/p/30985013
[5] https://github.com/ADozois/proc_deep_detector
[6] http://eigen.tuxfamily.org/index.php?title=Tensor_support
[7] https://github.com/PX4/eigen/blob/master/unsupported/Eigen/CXX11/src/Tensor/README.md
[8] https://www.tensorflow.org/api_docs/cc/class/tensorflow/tensor

Tensorflow C++ 从训练到部署系列文章目录

Tensorflow C++ 从训练到部署(3):使用 Keras 训练和部署 CNN
Tensorflow C++ 从训练到部署(2):简单图的保存、读取与 CMake 编译
Tensorflow C++ 从训练到部署(1):环境搭建

Keras 转换成 Tensorflow 模型格式并使用

Tensorflow 官方已经集成了 Keras 作为自己推荐的 High-Level API,Keras 的确使用非常方便,而且代码美观简洁,不像 Tensorflow 那样有很多形式化的代码。对于我们进行快速原型和实验是非常有帮助的。然而在一些场合我们可能需要混合使用 Keras 和 Tensorflow 定义模型或者保存模型的操作,这时就需要一些转换了。

系统环境
Ubuntu 16.04
Tensorflow 1.10.1 (内置:Keras 2.1.6-tf)

1、Fashion MNIST 数据集
1)数据简介
Fashion-MNIST [1] 是一个替代MNIST手写数字集的图像数据集。 它是由Zalando(一家德国的时尚科技公司)旗下的研究部门提供。其涵盖了来自10种类别的共7万个不同商品的正面图片。Fashion-MNIST的大小、格式和训练集/测试集划分与原始的MNIST完全一致。60000/10000的训练测试数据划分,28×28的灰度图片。你可以直接用它来测试你的机器学习和深度学习算法性能,且不需要改动任何的代码 [11]。

典型的 Fashion-MNITST 数据是这样的,其中每三行表示一个类别:
fashion-mnist-sprite

Fashion-MNIST 与 MNIST 同样有 10 个类别,不过并不是 0-9 的 10 个数字,它的类别如下:

screenshot-from-2018-09-25-11-50-54

我们使用过以前的 MNIST 数据集都知道,随便弄个很简单的网络,就可以轻轻松松刷出 99% 以上的分数了,即使传统方法也很容易达到高分。所以 MNIST 手写数字识别由于过于简单,作为一个基本的实验数据已经没有什么意义了。Tensorflow 和很多深度学习框架现在的入门数据也都推荐 Fashion MNIST。

2)数据读取
其实 Keras 为我们提供了简单的接口可以一键下载 Fashion-MNIST 数据并且读取:

不过由于天朝网络的原因,我并不推荐这种方式,建议直接下载到本地读取。我这里将数据直接存到 data/fashion 目录下。
百度网盘下载:
https://pan.baidu.com/s/19zZqU5tSwZyY780z8Y8_VA

读取数据代码如下(保存为:utils/mnist_reader.py):

2、使用 Keras 定义 CNN 模型并保存
下面的代码中我们定义了一个非常简单的 CNN 网络,结构图如下:
model

我们使用这一网络进行训练并且保存为 Keras 标准的 h5 格式。这一部分代码比较基础,就不做过多解释了。

Keras 模型定义和训练代码如下(保存为:train.py):

如果你的运行没有问题则会看到类似如下输出:

同时在 models/ 文件夹下保存了 fashion_mnist.h5 文件,这一文件包含了模型的结构和参数。

3、转换 Keras 模型到 Tensorflow 格式并保存
这一环节我们使用 keras_to_tensorflow [2] 转换工具进行模型转换,其实这个工具原理很简单,首先用 Keras 读取 .h5 模型文件,然后用 tensorflow 的 convert_variables_to_constants 函数将所有变量转换成常量,最后再 write_graph 就是一个包含了网络以及参数值的 .pb 文件了。

具体代码参见(原始代码中可以传入输出 node 数量和名字并使用 identity 生成新的 tensor,我这里稍作修改,直接读取 Keras 的 outputs 的操作名,最后会输出原始 inputs 和 outputs 的名字供后面使用):

Tensorflow 模型转换代码(保存为:utils/keras_to_tensorflow.py)

我们执行如下命令转换 Keras 模型到 Tensorflow 的 pb 格式:

如果你的运行无误的话则会显示如下信息并生成 models/fashion_mnist.h5.pb 这个就是转换过来的 Tensorflow 格式:

这里面也告知了你模型输入和输出的 Tensor 名字,这两个信息很重要我们后面会用到。

4、使用 Tensorflow 加载模型并预测
我们使用标准的 Tensorflow Low-Level API 加载和预测代码如下(保存为:load_predict.py)

这段代码中前面同样是读取 Fashion MNIST 数据集,与训练代码一样。部分代码说明如下:

读取 pb 模型文件:

获取当前的计算图: