今年的ILSVRC的DET和LOC比赛都被MSRA拔得头筹,其中DET的mean AP比第二名高了近9%,研究工作有两篇论文:

  • Deep Residual Learning for Image Recognition
  • Instance-aware Semantic Segmentation via Multi-task Network Cascades

PS.因为实习和学校里的事情,好久没认真研究论文,写论文笔记了

首先看Residual Network ## Motivation - Degradation problem: Training Error increases with the network gets deeper - If the added layers can be constructed as identity mappings,a deeper model should produce no higher training error than its shallower counterpart 如果我们增加层数之后可以做到全等映射的话,那么对于更深的网络,training error不可能比shallow的更高,我们知道单隐层的神经网络是可以无限逼近任何一个非线性函数的,因此训练全等映射是可行的。

作者指出,比起重头开始训练一个全等映射,我们尝试在原始输入上添加一个小的扰动(噪声),通过将扰动最小化让它逼近0来做到全等映射更加容易一些,这也就是residual learning的概念

Deep Residual Learning

我们把degradation问题视作一个优化问题,为了解决这个问题,作者将原先的层与层之间的映射转化成两部分: * 与输入相同的Identity mapping * 输入与原先输出部分的残余Residual mapping 体现在神经网络的结构上如下图: Residual building

这个概念是整篇文章的核心,图中x表示输入,$ H(x) = F(x) + x\(, 式中\)H\(就是原先的mapping函数,\) F$和x分别代表Residual mapping和Identity mapping.该结构不仅仅适用于全连接层,卷积层同样也适用。

图中identity映射部分叫做shortcut,这里我们可以不加参数使其完全等于输入x,或者我们也可以添加权重使identity变为projection,将identity转化为projection的做法主要是为了解决经过卷积层后输入与输出维度不同的问题。

同时我们注意到如果是identity全等映射,那么这里没有任何需要训练的参数,因此一个block的参数数量与普通的神经网络相同,这对于训练速度是非常大的帮助。

Advantages of Residual Learning

  • Easy to optimize, converge fast
  • Small number of parameters
  • Accuracy gains from greatly increased depth 笔者认为Residual learning最大的好处在于降低了设计deep neural network网络结构的难度,过去在设计网络时我们很难想象当网络达到几十层甚至上百层之后对网络的性能会有多大的负面影响,因此为了避免非常深的网络,转而通过增加网络宽度,或者引入其他的算法来改进网络结构,但是引入residual之后,仅仅是将网络加深却能得到非常好的效果,可以预见到16年的CV必然会有非常大的突破

笔者个人猜测:可能引入residual之后原先的优化问题中local minimal会少很多,使得优化过程更加容易到达global minimal或者比较好的local minimal,同时residual部分的值都非常小,因此相对而言在BP过程中梯度不会小到接近vanish的状态。 同时这里有一个细节,训练时并没有使用dropout来避免过拟合,但是最后结果也令人非常满意

Details

Shortcut Options

前面提到过identity部分可以转化为projection,作者在这里给出了三种方案: * (A) zero-padding shortcuts are used for increasing dimensions * (B) projec- tion shortcuts are used for increasing dimensions, and other shortcuts are identity * (C) all shortcuts are projections. 实验结果证明三种方案都能提升效果,但是C引入了更多的参数,而实际效果并没有比A和B好多少,但是训练时间和成本却高得多,因此前两种方案比较可行。

Layer Responses

实验过程中经过观察发现residual部分的输出值缺失非常接近0,验证了开头的设想,同时增加网络深度之后,residual的值变得更小,说明了这样的网络结构能很好地解决degredation的问题 Layer_response

总体而言文章通过实验验证experimental insight不多,但是使用了非常浅显易懂的方式成功解决了深度神经网络的热点问题,对于deep learning而言着实是非常大的进步。值得注意的是related work中提到了highway network,与本文的思想非常接近,有空又得读了……


下面是第二篇Instance-aware Semantic Segmentation via Multi-task Network Cascades ## Multi-task Network Cascades abstract中就已经提到三个网络级联构成一个新的框架 instance-aware semantic segmentation task can be decomposed into three sub-tasks

  • Differentiating instances —— Bounding box indicating instances
  • Estimating masks —— pixel-level mask
  • Categorizing objects —— category-wise label cascades

三个子任务共享卷积网络的feature,但是后面的任务接受feature和前一个任务的输出作为输入。 整个框架其实是首先用bounding box框出instance(类似于RPN),之后在每个bounding box中生成pixel wise的mask,最后给每个instance分类

本文中使用了ResNet来提取feature

  • Regressing Box-level Instances 做法类似于RPN,给定一副图像输出含有instance的bbox,稍有不同的是本文中使用了\(1\times1\) 的convolutional layer做box regression和object classifying

  • Regressing Mask-level Instances 借助Fast RCNN中的Roi pooling,在第二阶段对每个ROI生成相同维度的feature,后面再接两个fc层,一个降维到256,另一个做pixel-wise regression,

值得一提的是到这一步Loss function需要修改,由于第二部的结果依赖于第一步的输出,因此该步骤的Loss function为: \[L_2 = L_2(M(\theta) | B(\theta))\]

\(B(\theta))\)表示第一阶段用于生成bounding box的参数,M()表示用于生成mask的参数

  • Categorizing Instances 到了第三步,我们接收第二步的feature对每个mask重新计算feature: \[\mathcal F_i^{Mask}(\theta) = \mathcal F_i^{RoI}(\theta) \cdot M_i(\theta)\]

\(M_i(\theta)\)表示第二步输出的mask,\(\mathcal F_i^{RoI}\)就是经过RoI pooling的feature map,做点乘得到Mask的feature,后面接两个4096维的fc层,这被称为mask-based pathway, 类似的对RoI pooling输出的feature也做相同的处理,即box-based pathway, 这两个pathway的输出连接起来feed到softmax中进行分类

同样,第三阶段的Loss function计算公式为: \[L_3 = L_3(C(\theta) | M(\theta), B(\theta))\]

Training Method

整个网络结构梳理完毕,三个阶段的Loss function相加就可以得到总的损失函数,但是由于参数之间的依赖性,BP的时候第一阶段Bounding box的梯度传播是个比较大的难题。

对比Fast RCNN, 用Selective Search生成的RoI在训练网络时是固定的,并且又不能像RPN那样直接对bbox regression的Loss做反向传播(因为bbox只是中间过程的输出而已),为此作者提出可以求导的RoI Warping Layers来将残差传递给bounding box层。

replace the RoI pooling layer with a RoI warping layer followed by a maxpooling layer

RoI Warping Layer

Crops a feature map region and warps it into a target size by interpolation 显然,在RoI pooling层前面添加一层warping layer, 每个RoI都被crop和warp到固定size(在本文中大小为28 \(\times\) 28),转化方法如下: \[ \mathcal {F_{i}^{RoI}}_{(u^\prime,v^\prime)} = \sum_{(u,v)}^{W \times H} G(u,v;u^\prime, v^\prime|B_i) \mathcal F_(u,v)\]

式中\((u,v)\)以及\((u^\prime, v^\prime)\)分别表示warp之前和warp之后feature map的元素位置,函数G是长度和宽度两个方向的双线性插值函数乘积,如此一来,Bounding box阶段的参数导数计算如下:

\[{\partial L_2 \over {\partial B_i}}= {\partial L_2 \over {\partial \mathcal F_i^{RoI}}} {\partial G \over \partial B_i} \mathcal F\]

More Stages

At stage three, ddd 4(N+1)-d fc layer for regression class-wise bounding boxes, train the bbox regression jointly with classifier.

At inference step, extend three stages to five stages 利用第三步的结果(bounding box)再运行一次相同的Mask predict和classification的过程,实验结果证明精度上升

  • First run entire 3-stage network and obtain regressed boxes on stage 3, consider these boxes as new proposals
  • Perform stage2 and stage3 again and the whole procedure becomes 5-stage cascading five_stage

Contributions

  • Joint training for semantic segmentation and object detection
  • Combination of the basic concept of state-of-the-art models(FCN, Fast RCNN, RPN, Spatial Transformation Network) and improvements of Fast RCNN and RPN

online judge对于提升编程能力有非常大的帮助,在2015年年初的时候笔者接触到了OJ,由于本身基础比较薄弱,因此在许多人眼里的“刷”OJ,对我而言变成了“啃”OJ

相信许多同学和笔者一样是在强烈的危机感驱使下开始刷题的,但是无论出发点是什么,对基本算法和数据结构的掌握对于一个从事技术的人而言是重中之重,笔者在学习machine learning时发现在做research之前首先得达到一个programmer的高度,实习的时候亦有这样的感受,coding skill体现的不仅仅是你严谨的逻辑,更体现了解决和分析问题的能力,其重要性不言而喻。Leetcode上面的每道题都值得仔细推敲和分析,并且温故而知新才是好的学习习惯

我的leetcode心得与体会: 从15年5月刷到11月,中间暂停了将近两个月,速度上而言完全不算快,从200多题按照题号往回刷,明显感觉题号小的题偏基础一点,因此现在感觉按照从小到大的顺序或者按照分类来做题是比较科学的做法,有点不同的是笔者全程用python刷题,c++ stl用的不是很熟。

  • 刚开始的时候觉得特别虐,一道题如果没有思路的话会想很久,由于笔者强迫症症状比较严重,不到万不得已不看答案,所以刚开始的几天特别痛苦,基本一道medium都会想很久(hard更是难上加难),记得一道dungeon game卡了我两天还做错了……
  • 其实如果对于基本的算法框架比较熟悉的话很快就能有思路,像Number of Islands这样的题目第一反应就应该是dfs,所以我开始尝试理清一些基本的算法框架,如dfs,bfs,dp,递归和回溯等等,并且从别人的代码中总结一些框架性的方法
  • 另外除了算法之外一些基本的数据结构也必须熟悉,如堆栈、链表、二叉树等等,但是这些数据结构相关的题解法基本比较固定
  • 最难以捉摸的题型是数组与字符串,leetcode上数组的题目占的比重最大,在笔者看来数组不能被归为一个类别,因为题目跨度很大,基本会涉及dfs、dp、hashtable、sort等等,还有许多比较独有的解题方法,如trapping rain water和Best Time to Buy and Sell Stock一系列等等
  • 做完题AC之后应该注意一下自己的耗时,多分析一下自己的时间复杂度和空间复杂度,如果比较低效并且没有什么好的优化方案的话建议去看看discuss里面的解法,有许多巧妙的解法可以开阔思路
  • 随着时间的推移,编程会逐渐变成习惯,并且可以明显的感觉到自己的归纳和推理能力有很大的提升,现在看到一道题基本都会有比较直观的解法,如果确定了用什么算法解,那么基本的代码框架其实也已经出来了,但是说到底leetcode考察的是对算法的熟悉程度和动手能力,你写的代码在实际工作中并不一定会用到,写代码更多的是培养良好的编程习惯。
  • 刷leetcode免不了有一点“应试”的感觉,其实国内的许多面试或者笔试题大同小异,基本面试官问的题目如果和刷过的题目有交集的话相信自己会胸有成竹,而就算是一道完全新的题目其实也不太可能偏离基本的算法,展现自己解决问题和代码实现的能力才是最重要的。

最后有一点:如果你不是oj爱好者,那么费尽心思去刷很多题并不是必要途径,“质”比“量”更加重要,没有必要非得把所有题全部刷个好几遍,能从自己做过的题中总结出属于自己的方法在笔者看来才是最重要的,毕竟刷题只是手段不是目标,能培养自己推理思维和逻辑性才是在以后的学习工作中起到真正的关键作用。

最后贴下自己的战果,最近更新了好多付费题,加之最近忙其他事因此没有来得及跟上。img

理解SVM原理一直是一个比较难的问题,因为牵涉到的数学知识比较多,网上SVM相关的资料非常多,但大部分的教程中的推导都大同小异,笔者认为July的SVM的三层境界和pluskid的支持向量机系列博文都是非常好的入门资源,多数的参考资料多多少少都照搬了许多Andrew NG的Machine Learning讲义内容,可惜的是笔者翻来覆去看了好几遍还是不能融会贯通,特别是当推导到对偶问题与KKT条件时,看来看去还是一头雾水,因此本文将结合Convex Optimization一书从纯数学的角度对于SVM推导过程中的优化问题进行详细的阐述,文中如有不妥当不严密之处烦请告知,谢谢

Lagrange对偶函数

首先我们定义优化问题:transformation

我们称这个问题为原始问题(primal problem),对于这样的优化问题,相信之前学习过Lagrange乘数法的话会比较熟悉,但是与一般问题不同的是上面的问题包含不等式约束,这里我们先放一放, 首先写出目标函数L: \[L(x,\lambda,\upsilon) = f_0(x) + \sum_{i=1}^m (\alpha_if_i(x)) + \sum_{j=1}^p(\beta_jh_j(x))\]

该函数在Convex Optimization一书中被称为Lagrangian,式中\(\alpha\)\(\beta\)是Lagrange乘子(我们假设alpha大于0),显然Lagrangian函数是关于x,\(\alpha\)\(\beta\)的函数

对于每一组\(\alpha\)\(\beta\),我们在\(f(x)\)的定义域上求取Lagrangian的下确界,产生的新的函数表达式如下: \[g(\alpha,\beta) = \mathop{inf} \limits_{x\in D}L(x,\alpha,\beta) = \mathop{inf}_{x\in D}(f_0(x)+\sum_{i=1}^m (\alpha_if_i(x)) + \sum_{j=1}^p(\beta_jh_j(x))\] \(g(alpha,beta)\)这个函数就称为Lagrange对偶函数

那么对偶函数有什么用呢?

从定义上看,对偶函数定义了原问题所有可行解的下界,因为对于任何一个可行解\(\mathop{x}^\sim\),无论\(\alpha\)\(\beta\)的值为多少,Lagrangian后面两项的和不会大于0,所以\(Lagrangian(\mathop{x}^\sim)\) 的值一定小于等于\(f(\mathop{x}^\sim)\),而对偶函数又是Lagrangian的下确界,所以我们有:

\[g(\alpha,\beta) \leq p^*\]

这里\(p^*\)表示原始问题的任一可行解

Lagrange对偶函数与共轭函数的关系

清楚对偶函数的定义之后,我们继续介绍共轭函数的概念,之所以需要了解这个概念的原因是因为共轭函数拥有一个非常优秀的性质:无论原函数是否是凸函数,共轭函数一定是凸函数

首先需要弄清楚共轭函数的定义: \[f^*(y) = \mathop {sup}_{x\in \bf{dom} \, f} (y^{T}x-f(x)) \] 共轭函数由两部分组成,首先是线性函数\(y^Tx\), 该函数的斜率是自变量y,另一部分就是原函数在x上的值,因此共轭函数求的对于一个固定的斜率y,求线性函数\(y^Tx\)和原函数的差值的上确界。

我们可以大致猜测共轭函数的性质,由于共轭函数其实隐含着求最大值的目的,因此我们可以简单地把它看作求极值问题,那么显然对函数直接求导可以得出共轭函数在某个特定输入y处的函数值,即

\[y = f^{'}(x)\]

得出x与y的关系\(x = {f^{'}}^{-1}(y)\),再把上式带入到\(y^{T}x-f(x)\)就可以求出解析式了。

由于共轭函数凹凸性的优势是的它在优化问题中非常有优势,下一步我们看共轭函数与Lagrange对偶函数的关系,假设原问题的约束条件为线性函数(SVM的函数间隔约束显然也是线性约束):transformation

由对偶函数的定义我们有:

\[g(\alpha,\beta) = \mathop{inf} \limits_{x}(f_0(x)+\sum_{i=1}^m (\alpha_if_i(x)) + \sum_{j=1}^p(\beta_jh_j(x)) = -b^{T}\alpha-d^{T}\beta+\mathop{inf} \limits_{x}(f_0(x)+(A^{T}\alpha+C^{T}\beta)^{T}x)=-b^{T}\alpha-d^{T}\beta-{f_0}^*(-A^{T}\alpha-C^{T}\beta)\]

我们成功地从对偶问题中找到了共轭函数,因此对于仅有线性约束条件的优化问题而言对偶函数也一定是凸的

Lagrange对偶问题

我们已经知道了对偶函数的优良性质(当然约束条件要求是线性函数),如果我们能想办法将对偶函数用到原始问题的求解上,那么就能够方便地求出最后的解,因此这里我们引入对偶问题

对偶问题的数学表达如下:transformation 前面讲过对偶函数定义了原始问题可行解的下界,那么对偶问题的目标就是试图从找到这些下界的最大值,当然我们前面已经假设\(\alpha\)必须大于零。这也是为什么在许多SVM教程中对偶函数被定义为\(max \, min\, L(x)\)的原因

弱对偶与强对偶

由于对偶函数的保证了凹凸性,所以对偶问题的求解非常方便,我们把对偶问题的解记为\(d^*\),有我们之前的结论有: \[d^{*} \leq p^{*}\] 上面的式子揭示了对偶问题的特性,称为弱对偶

如果我们能把不等号转变为等号,那么原始问题的解就求出来了,同时如果\(d^{\*} = p^{\*}\),那么弱对偶就变成了强对偶。

一般情况下强对偶的要求比较苛刻,仅在某些条件下强对偶才成立,最常见的就是Slater条件,但是Slater条件要求原问题是convex的,因此这里到了最关键的一步:利用KKT条件

KKT条件

KKT条件在convex optimizaiton中的描述如下:

We now assume that the functions f0, . . . , fm, h1, . . . , hp are differentiable (and therefore have open domains), but we make no assumptions yet about convexity.

KKT conditions for nonconvex problems

As above, let x⋆ and (λ⋆,ν⋆) be any primal and dual optimal points with zero duality gap. Since x⋆ minimizes L(x, λ⋆, ν⋆) over x, it follows that its gradient must vanish at x⋆, i.e.,

dualty gap的意思是原问题解\(p^*\)和对偶问题解\(d^*\)的差值,显然强对偶情况下差值为0,按照Lagrange乘数法的思想,Lagrangian函数在\(x^*\)处的导数为0

\[\nabla f_0(x^*) + \sum_{i=1}^mDf_i(x^*)^T\alpha_{i}^{*} + \sum_{i=1}^p\beta_{i}^{*}\nabla h_i(x^*) = 0\]

式中\(Df_i(x^*)\)表示的是约束函数\(f_i\)\(x^*\)处的导数,从上式中我们可以推导出KKT条件(偷懒直接上图):

当然这里要求\(f_i\)为凸函数,\(h_i\)为线性函数(仿射)且两者均可导,函数\(f_i\)\(h_i\)分别表示不等式约束和等式约束,前两个式子是原始问题的要求,图中\(\lambda\)\(\upsilon\)对应前面的\(\alpha\)\(\beta\),我们关注第三和第四个式子,结合SVM我们可以发现如果Lagrange乘子\(\lambda\)大于0,那么对应的不等约束变为等式约束,对应支持向量的情况,如果\(\lambda\)等于0,那么对\(f_i\)的值没有要求,对应非支持向量的情况。

同时KKT条件也说明了我们为什么在前面定义Lagrangian时要求\(\alpha\)大于等于0的原因。

笔者在看其他教程时一直不明白第三第四个式子从哪里推导出来的,书中好像没有给出严密的证明和推导,但是给出了一种非常直观的interpretation——物理学中的弹簧问题

简单而言就是两个滑块由三个弹簧链接,并且位于两堵墙中间,求平衡状态下使整个系统的能量最小的\(x_1\),\(x_2\) 首先求能量函数为:

\[f_0(x_1,x_2) = \frac 1 2 k_1 {x_1}^2 + \frac 1 2 k_2(x_2-x_1)^2 + \frac 1 2 k_3(l-x_2)^2\]

从图中我们可以看出一些基本的约束条件(两堵墙中间要有足够的空间,滑块之间不能重叠): \(\frac w 2 - x_1 \leq 0\), \(w + x_1 + x_2\), \(\frac w 2 - l + x_2 \leq 0\)

因此我们得到了原始的优化问题,假设Lagrange乘子分别为\(\lambda1\),\(\lambda2\),\(\lambda3\),那么由KKT条件我们有(对应第三第四个式子)

\(\lambda_i \geq 0\)

\(\lambda_1(w/2-x_1)=0\), \(\lambda_2(w-x_2+x_1)=0\), \(\lambda_3(w/2-l+x_2)=0\)

同时由于在解的位置梯度为0,我们有:

另一方面,由于系统处于平衡状态,滑块一定是受力平衡的,我们对滑块进行受力分析:

transformation 动手写一下受力平衡方程就可以发现与上面的梯度为0的式子是一样的,说明了Lagrange乘子可以看作是题目中滑块受到的反作用力,KKT条件与平衡状态的受力分析殊途同归

这个例子说明了KKT条件是对于原始问题另一角度的解读,如果我们的优化问题存在一个“平衡状态”的话,那么我们可以通过解对偶问题来获得原始问题的解

推广到SVM,如果支持向量确定的话那么相当于给出了“平衡状态”,我们可以直接求解对偶问题来求分割超平面,而当我们获得训练集的时候其实支持向量已经确定了(当然可能需要核函数映射)。

参考文献

[1] Boyd S, Vandenberghe L. Convex optimization[M]. Cambridge university press, 2004.

[2] http://www.duzelong.com/wordpress/201507/archives1023/

系统调用exec

上一步中我们完成了子进程的创建,但是子进程还没有开始运行自己的程序,因此在这一步子进程开始执行新的可执行程序,在进行详细介绍之前,借用书中的例子,我们调用fork创建子进程,fork在返回时会给父进程和子进程返回不同的值,因此两个进程通过该返回值判断自己是父进程还是子进程。 child_parent

execve的基本流程

注意到子进程中调用了execve(),其函数声明如下:

int execve(const char *filename, char *const argv[], char *const envp[]);

其中第一个参数表示执行的程序路径,第二个参数argv表示程序的参数,envp表示子进程的执行环境,即上下文。 首先介绍下execve()的基本流程:

  1. 首先将程序路径指针从用户空间拷贝到系统空间,这其中的过程比较复杂,考虑到该字符串可能非常长,为了不占用系统堆栈,系统会分配一个物理页面作为缓冲区,之后从用户空间拷贝字符串
  2. 第一步可以看作执行文件之前的预处理,之后execve通过调用do_execve执行主体部分工作:打开可执行文件并进行加载,值得注意的是加载时Linux内核定义了linux_binprm结构体来保存加载时所需的参数和字段
  3. 打开文件之后,函数开始解析每个参数,这里的参数也位于用户堆栈,因此采用与第一步相同的方式加载到内核空间,因此每有一个参数就会新建一个页面缓冲区,在拷贝参数的同时调用count()对参数计数,需要注意的是argv[0]永远是可执行文件的路径,每个可执行文件的参数数量等于传入的参数数量加一
  4. 第三步中虽然打开了文件,但是此时系统还不知道文件的格式,这里提点题外话,Linux中文件的前128个字节包含了该文件的属性信息,因此不像windows那样,Linux并不通过后缀名判断文件格式,我们可以通过file命令判断文件的类型。
  5. 最后把程序执行的参数和运行环境,从用户空间拷贝到系统空间中,由bprm统一管理

完成以上步骤的预处理之后我们执行目标文件的加载工作,首先运行search_binary_handler来寻找与目标文件类型对应的处理工具handler,不同的handler构成一个数组format,函数会遍历整个数组查找对应的handler,当找不到时去查看目标文件的第2、3个字节通过request_module()尝试读入相应的handler

加载目标文件的代码框架如下:

    for (try=0; try<2; try++){//尝试两次,第一次找不到handler之后尝试安装handler再试一次
        for (fmt = formats ; fmt ; fmt = fmt->next) {//遍历format数组
                调用load_binary
                if(load_binary不成功){ 
                    尝试下一个handler
                }
                //load_binary成功
                装载目标文件直接运行
                ret=运行返回结果
                if(ret >=0){
                    //说明找到了对应的handler
                    执行目标文件
                    }
                if(ret不为0且不是-ENOEXEC){
                    //说明找到了handler但出现其他错误,直接退出
                    }
                //ret=ENOEXEC说明handler与文件类型不匹配
            }
        //内层循环结束
        if(ret为-ENOEXEC){ //说明handler对不上号
            读取目标文件第2、3字节生成bitfmt模块并读入
                再次遍历format
            }
        }

从上面的代码分析中可以看出关键在于load_binary的内部机制,这也是目标文件的加载核心代码

书中以a.out作为可执行文件的例子说明load_library的装载和执行的过程,旧版本的Linux系统内核编译输出a.out格式的可执行文件,如centos和redhat等,而比较新的系统如ubuntu等已经使用elf格式

目标文件的装载和投入运行(a.out格式为例)

解析目标文件格式

前面说过在不同类型的目标文件对应不同的handler,各个handler都存在format数组中,下面的数据结构对应的就是a.out的handler

static struct linux_binfmt aout_format = {
    NULL, THIS_MODULE, load_aout_binary, load_aout_library, aout_core_dump, PAGE_SIZ
};

该结构体中load_aout_binary负责a.out格式的目标文件的装载和运行,我们看这个函数的开头部分: load_aout_binary 回忆一下bprm中包含了装载所需要的参数,其中就包括文件类型,代码里面ex变量是一个exec数据结构,该结构中包含着文件的MagicNumber, 这里需要介绍一下MagicNumber的概念:

MagicNumber本身是一种编码,也可以是字符,a.out文件格式一共有四种MagicNumber:ZMAGIC、OMAGIC、QMAGIC和NMAGIC

如果找不到与ex变量中匹配的magic number,那么说明该文件不是a.out格式。如果匹配到了magic number,那么我们可以获取目标文件的正文位置。但是在这之前还需要做一些检查,如PCB中对于数据最大空间的限制等,如果这些检查都通过,子进程这时可以放弃用户空间,因为需要拷贝的内容已经都在内核空间了

flush_old_exec清空用户空间

完成用户空间内容到系统空间的复制之后load_aout_binary执行flush_old_exec函数,首先处理信号处理表,如果子进程在这时与父进程共享一个信号处理表的话,需要将该表复制给子进程。

前面我们提到子进程可能共享父进程的用户空间,同样程序也只需要检查用户空间的共享计数,如果父进程独占用户空间,那么需要释放子进程mm_struct数据结构下面的所有页面,调用exec_mmap函数放弃父进程的用户空间。

然而我们fork创建进程时先拷贝了父进程用户空间的所有数据结构,却又在这里释放了所有空间,为什么这么大费周章呢,所以我们需要vfork作为fork的补充,我们调用vfor就不需要拷贝这些用户空间,vfork仅复制父进程的系统堆栈空间和PCB,且与父进程共享用户空间,因此这两个函数的实现不同点在于sys_vfork多了两个标志位指示子进程通过指针共享还是复制父进程的用户空间。

但是共享的情形下会出现一个问题:前面我们提到过Copy on Write, 子进程的页面访问权限设置为只读,只有当子进程需要写页面时才在页面异常处理程序为子进程复制物理页面,在共享状态下,子进程写页面会影响父进程,因此绝对不能让两个进程同时在内核态运行,所以Linux系统在创建子进程之后让父进程进入睡眠状态,等待子进程运行结束之后唤醒或者调用exit()退出,来避免这个问题。

唤醒和睡眠通过信号量的操作来实现,唤醒操作mm_release的代码如下: mm_release 通过上面的分析,我们可以得出如果子进程与父进程共享用户空间,那么其实也就没有释放用户空间这一说了,但此时需要为子进程分配一个mm_struct数据结构以及页面目录,以便于为子进程建立自己的用户空间,之后切换到新的用户空间。

到这里为止,当前进程的用户空间与父进程完全独立,可以唤醒父进程,并更新父进程用户空间的共享计数。

值得注意的是作者又详细介绍了PCB中的mm与active_mm指针的细节,mm指向用户空间,如果本进程是内核线程,那么mm为空,但是该进程被调用时要求active_mm不能为空,所以在调度时内核将其设置为在其之前运行的某个进程的active_mm,在运行时又将这个指针设置为0。

对于一般进程而言,mm不为空,因此我们不使用active_mm,我们调用mmdrop释放active_mm,递减其共享计数。

释放继承下来的用户空间之后,子进程的用户空间变为空,如果子进程原来只是一个线程的话,它的PCB会被挂入由其父进程为首的“线程组”队列,然而调用execve之后,子进程变成了真正意义上的进程,因此需要调用de_thread从线程组中脱离出来。同时由于子进程生成了独立的信号处理表,那么这个时候需要更新父进程信号处理表的共享计数,如果为0那么就释放。

这里需要介绍一下信号处理表的具体内容,基本与中断向量表类似,但不同的是,信号处理表中的每一项又对各种信号的预设响应,由于上面一步我们已经将内核线程的用户空间置为0并把它变为进程,我们需要将原来指向用户空间服务程序的表项更改为SIG_DFL,即默认预设值。

最后处理已打开的文件,PCB中有专门保存已打开文件信息的变量,同时还包含一个位图用来指示哪些文件在执行新的程序时应关闭的信息。所以flush_old_files最后一步工作就是根据这个位图关闭这些文件,并将该位图清0。一般情况下进程的头三个文件分别指stdin,stdout以及stderr,这三个文件不应关闭,而其他应该关闭。

子进程用户空间分配

Flush_old_exec函数返回之后,子进程与父进程之间已经完全独立,但是子进程的用户空间依旧为空,现在load_aout_binary函数将对mm_struct结构中的变量进行初始化并分配存储空间。

熟悉可执行目标文件格式的读者知道,目标文件的映像分为text、data及bss三段,分别用来存储指令、已初始化的全局变量和未初始化的全局变量。mm_struct为每个段都设置了start和end指针,程序映像的正文从text段开始,这里我们需要回顾一下之前讲到的magic number,当magic number为OMAGIC时,说明该文件中的可执行代码并不是纯代码,对这类文件分配空间时首先为text和data段合在一起分配空间,之后再把这两部分从文件中读进来,对于bss段只需要分配空间就可以。

除了OMAGIC之外的其他三种均为纯代码,这类代码在执行时不会改变,其data段的内容也不会改变,因此内核将可执行文件映射到用户空间中,之后是一些比较细节的工作,如果文件系统提供mmap,则需要将已打开的文件映射到虚存空间,此时检查text段与data段与页面大小对齐,如果不满足以上条件则分配空间并将text段与data段读入到用户空间,如果满足条件则直接映射。

至此,text段与data段的装载全部完成,下面就是bss段和堆栈段了。

接下来load_aout_binary函数通过set_brk函数为bss段分配空间并建立页面映射,接着在用户空间的堆栈顶部建立一个虚存空间,将执行参数以及进程上下文所占的物理页面与此空间建立映射。

用户空间中最高地址为堆栈区,堆栈区的顶部为一个数组,数组中每个元素都是一个页面,我们知道一般程序默认有两个参数,参数列表argv与参数数量argc,还有一个隐含的之前提到的上下文参数envp,该参数也是execve的参数之一,用户堆栈中从一开始就是设置好这三项数据,并将这些参数复制到用户空间的顶端。这些工作由create_aout_tables函数完成。

在这里作者又提出了一个问题,如果我们要从用户空间读取某个变量到内核空间,那么我们应该使用get_user 函数,我们来看一下get_user的函数声明: get_user 首先get_user是一个宏定义,用于从用户空间读取简单类型的变量,如一个字节,短整数和长整数,那么为什么要用x而不是x的地址呢? get_user中实际调用的是__get_user_x这个汇编函数,该函数只有一条汇编指令,该指令执行以下操作:

  1. eax寄存器和ret绑定
  2. edx寄存器与x绑定
  3. 以上两个寄存器作为__get_user_x的输出
  4. ptr指针存入eax寄存器 我们结合__get_user_x看,可以发现__ret_gu中存着用户空间的变量地址,122行的代码表示考虑到符号原因,我们要强制对x做类型转换,所以不得不使用变量,最后get_user返回ptr的值

因此实际的赋值过程只是寄存器操作,这也就是我们不使用变量地址的原因。

从create_aout_tables返回之后,堆栈顶端的参数已经准备好,这里只剩下最后一步start_thread的工作就是保留保存上下文,当进程从系统调用返回时,这些数值会恢复到CPU的各个寄存器中。

至此,可执行代码的装载已经完成,do_execve在调用search_binary_handler之后也结束了。

本日志将详细介绍Linux系统中进程从创建到执行过程中的细节,包括:子进程地址空间的分配、子进程代码和数据的构成、子进程与父进程之间的交互以及堆栈的设置

概述

在开始介绍之前,需要有一些基础的操作系统知识,主要包括:

  • Linux系统的内存管理框架,Linux地址映射,页(段)式存储管理
  • 进程与线程的定义以及两者在Linux系统中的区别
  • 进程的映像结构布局

Process_Image Linux系统中进程的创建分为两步:首先从父进程“派生”出一个子进程,之后子进程通过系统调用execve()执行目标程序。 在正式开始进程创建的过程之前,我们首先要了解一下Linux系统与进程密切相关的数据结构,如PCB的数据结构task_struct(后面直接用PCB表示task_struct结构),以及虚拟内存的描述符mm,这些会为之后的代码阅读与理解提供很大的便利。

Linux中的PCB数据结构task_struct

作为进程的管理单元,task_struct结构包含相当多的成员变量,基本可以分为状态、性质、资源和组织等几大类,我们重点关注几个与进程创建相关的成员变量:

  • binfmt——应用程序的文件格式,与进程加载可执行文件相关
  • user——指向一个user_struct数据结构,代表这该进程所属的用户,创建进程do_fork时需要用到
  • rlim——表示内核对进程资源的使用限制,同样在创建时需要用到
  • pgrp——当前进程的运行上下文,在进程调度执行时至关重要
  • mm——内存描述符,代表进程所拥有的地址空间,其结构示意图如下: mm_struct 共分四个段:代码段、数据段、堆和栈,进程创建时对mm_struct的复制是重点。

mm_struct结构中有一个虚拟内存的基本管理单元vm_area_struct,这些单元通过指针的方式形成一个链表,并用来存储mm_struct中的虚拟内存的地址信息。

  • file_struct files*——这是一个file_struct类型,它指向进程打开的文件信息
  • fs_struct fs*——记录与进程相关的文件系统信息

下面这张图能很好地展示task_struct相关数据结构的关系task_struct

Linux系统的内存映射与系统调用mmap

Linux中进程创建与执行离不开内存空间的申请与释放,存储管理的细节不多叙述,但是我们需要了解一些Linux系统如何申请及释放空间的知识,我们主要关注两个系统调用brk与mmap。之前对于Linux系统中内存、虚拟地址空间和物理页面的概念不太清晰,因此在这复习一下这些基础知识:

  • Linux采用页式存储管理(将4kb连续的物理存储空间作为一个页面)
  • 操作系统内核将虚拟地址与物理内存进行映射来达到操作内存的目的
  • Linux使用2层地址映射方式(虽然很多书中写的是3层映射,但这只是逻辑上,在实现时本质还是2层映射),通过页面目录及页面表将虚拟地址映射到物理页面上,因此如果我们尝试对没有映射的地址空间进行写操作的话会引发缺页异常。

brk负责动态地向内核申请和释放空间,从进程的映像布局中我们可以看出堆向上增长,每申请一次空间,我们就将这个动态分配区的底部向上推,每释放一次就将底部向下移,brk的实现sys_brk函数接收一个参数brk,该参数正是用来描述新的边界地址。内核将新的边界地址与旧的边界地址进行比较就可以知道需要释放还是分配空间。

从上面的几点可以总结出,Linux在申请内存时的主要步骤

申请:检查进程地址空间和想要申请的空间之间的合法性(检查高端地址是否会出现冲突),如果合法则分配适当的虚拟内存区间同时建立映射,建立映射包括写页面表和页目录。
释放:检查释放的页面是否已建立映射,如果是则解除页面映射表中相应的表项,同时释放内存页面,如果我们想要释放的内存空间也没有进行映射,就可以直接跳过解除映射这一步

而mmap函数为一个以打开的文件映射到进程的用户空间,使得进程可以像访问内存一样访问文件,在进程执行execve时内核会将可执行程序映射到当前进程的用户空间,其底层实现都在文件系统中,这部分与进程关系不大。

注意我们在申请与释放内存空间时,都会对进程的基本内存管理单元构成的数据结构进行插入或者删除操作,这些基本单元可能以链表的形式组织,也可能以AVL的形式组织,这些结构都保存在PCB中,因此我们需要遍历这些结构一一处理

Linux进程创建

Linux系统中提供三种创建进程的方式,fork/clone/vfork,三者的不同在于fork完全复制父进程的所有资源,子进程可以看作父进程的镜像,而clone则相对灵活一些,用户可以将资源有选择地复制给子进程,vfork是后来增加的系统调用,强制将除了PCB和系统堆栈以外的资源通过指针复制。从复制的数据量角度来说vfork ()<=clone()<=fork()

需要注意的是父进程的全局变量以及代码不会被复制到子进程中,而是通过只读的形式共享,但无论使用哪种方式创建进程,子进程都需要调用execve执行可执行程序。 child_parent

子进程的创建在do_fork函数中,这个函数会接收多个参数,这些参数的主要目的在于:

  1. 控制子进程要创建独立的空间还是与父进程通过指针共享资源
  2. 控制子进程向父进程发出通知的信号

当以上这些控制参数设置完成之后,通过alloc_task_struct函数为子进程分配两个连续物理页面,低端用作PCB,高端用作系统空间。之后直接开始复制父进程的PCB(task_struct)数据结构。

复制PCB

在复制PCB这一部分作者提到了PCB中两个重要字段,一个是指向该进程拥有者的指针user,这个指针指向的数据结构为user_struct,包含了该user的信息,这些信息里有一个计数器__count,用来统计这个user拥有多少个进程,这个计数器在后面execve()函数中会用到,对释放页面起到关键作用。

另一个字段是rlim,它限制了进程可以占用的资源数量和用户可以拥有的进程数量,因此如果到达上限的话该用户就无法新建进程了,这个字段决定了后面execve函数中执行可执行文件。

每个进程除了拥有者之外还有一个执行域,执行域与操作系统有关,Unix的每个变种都对应一个执行域,Linux也有自己对应的执行域,介绍执行域的原因是因为它和动态链接库有着紧密的关系,只要某个域中还有进程在执行,那么这个域对应的动态链接库就不能拆除。

每个进程执行的程序也属于某种格式,这些格式有不同的驱动模块负责,而这些模块都是动态加载的,有关这些部分在execve部分会详细介绍

之后调用get_pid函数进行PID的复制,前面提到的参数中有一个用来控制子进程是否与父进程共用一个进程号。之后完成各种信息量以及进程创建时间的初始化,至此为止PCB的复制就基本完成了

复制已打开的文件

系统调用copy_files函数复制已打开的文件控制结构,同样我们需要按照do_fork的输入参数决定是否需要与父进程共享已打开的文件。所有与终端设备相联系的三个文件:stdin,stdout和stderr都是预先打开的。

如果我们设置子进程与父进程共享文件的话,就将当前进程的file_struct结构中的共享计数加一,如果需要复制,那么调用kmem_cache_alloc函数为子进程分配一个files_struct结构,再进行复制,files_struct结构有三个重要的成员,其中一个是位图close_on_exec_init,用于初始化那些在执行exec时需要关闭的文件,另一个是open_fds_init,用于初始化描述文件,第三个是文件数组fd_array,这三个成员都是固定大小的,如果需要打开的文件数量超过这个大小则必须另外分配空间。

直观上看共享模式操作简单,但是父子进程在操作自己打开的文件同时其实也在操作对方的文件,因此这就带来了问题,复制模式就不会有这样的问题,父子进程互不干扰。

复制文件系统信息

大家都知道操作系统中文件都有操作权限,因此每个进程在创建的时候我们除了要复制打开的文件之外,还需要复制父进程的与文件系统相关的信息,这些信息中比较典型的就是文件的操作权限, 另外还有进程的根目录root,当前工作目录等。这里有一点需要注意的是我们仅复制fs_struct数据结构,对于其成员数据结构并不进行深层的复制,因此这些成员数据结构还是共享模式状态,需要增加共享计数。 接着处理用于进程间通信的信号,进程可以为各种信号设置信号处理程序,其PCB中的指针sig就指向signal_struct数据结构: signal_struct 注意到其中有一个count变量,说明子进程可以通过指针共享这个信号表,只需要将共享计数加一就可以了

用户空间继承

PCB中的指针mm指向用户空间mm_struct结构,当子进程通过复制模式继承父进程的用户空间时,不像之前的fs_struct仅复制外层结构,而是需要进入该结构复制其成员,主要复制的就是vm_area_struct虚拟内存的管理单元和页面映射表了,这里我们可以看一下负责复制mm_struct的函数dup_mmap的代码 dup_mmap dup_mmap2 函数的主题在于这个for循环当中,我们遍历当前进程mm指针的每块虚拟内存,新建一块内容空间tmp,并将其独占(变为临界资源),之后把tmp的vm_mm指向当前进程的mm字段,递增共享计数,155到169针对打开文件的处理,之后完成页面的复制,copy_page_range是一个非常关键的函数,其代码比较长,这里主要讲一下函数的执行过程

我们依旧对页面的目录项进行遍历,Linux的地址映射分为三部分,除了页目录和页面表之外还增加了一个中间目录,但其实i386的处理器依旧按照两层映射的结构,所以中间层基本就是全等映射,相当于对输入没有做转换直接输出。 我们主要关心父进程页面表,根据表项的内容决定具体操作:

  1. 表项内容全0,说明页面尚未设立,不需要做任何事
  2. 表项最低位为0,说明映射已经建立但页面不在内存中,通过swap_duplicate递增共享计数,之后将此表项复制到子进程的页面表中
  3. 映射已建立,但是物理页面不是有效的内存页面,由于有些物理页面在外部设备上,其地址是总线地址不是内容页面,不消耗动态分配的内存页面
  4. 需要从父进程复制的可写页面,这应该是最常见的情景了,然而此时我们并不新分配一个内存页面再复制父进程的页面中内容,内核仅仅通过指针来共享这个页面,这就是Linux的精妙之处,其实我们并不知道复制玩页面后子进程会不会使用这个页面,所以我们引入一种成为“copy on write”的技术,先通过复制页面表项共享这个页面,当有任何一个进程需要写操作时再进行分配和复制,分离子进程和父进程的页面,具体做法如下:
    • 设置父进程的页面表项为写保护
    • 子进程复制该页面表项 这样两个进程的页面都设置为只读,因此当有进程尝试写这个页面时会引发一个异常,到这时在异常处理程序中执行分配和复制,这样依赖使得页面的复制变得相当快捷,当然这值适用子进程以复制模式进行页面继承的情况,如果在共享模式下根本用不到这样的技术

当我们继承完用户空间之后,所有的有条件复制基本已经处理完,我们回顾一下vfork和fork的区别,fork调用do_fork时所有的控制参数均为0,即我们“复制”了所有的资源,但是vfork仅仅复制PCB,因此copy_mm函数不会执行,因此此时创建的实际上是一个线程。

系统空间继承

之前我们分配了两个页面,用于存储PCB的低端页面已经分配完毕,现在开始复制系统空间堆栈。我们调用copy_thread完成这个任务。copy_thread的代码如下:copy_thread 系统堆栈的内容包含了父进程从通过系统调用进入系统空间开始到进入copy_thread的过程,而子进程返回时需要这些信息,但是不能完全照搬,因为返回时我们要区分是哪个进程返回的。我们已经知道当进程通过系统调用进入内核态时,我们需要保存CPU上下文,pt_regs就是用来存储寄存器内容的数据结构,在创建pt_reg时参考下图: pt_reg 首先我们已经有指向子进程PCB的指针p,同时我们也知道p指向两个连续的物理页面,因此我们可以得到这两个页面的顶端THREAD_SIZE+(unsigned long)p,之后将其转换为struct pt_regs*,再减一就指向了子进程系统堆栈的pt_regs结构。

得到子进程的pt_regs之后,先将当前进程的上下文复制给子进程,再将eax置为0,当子进程被调度返回时返回值就为eax的值,除此之外还需要将结构中的esp置为参数esp,它决定了进程在用户空间的堆栈位置。在fork中该参数来自父进程上下文的esp寄存器。

注意到PCB一个重要的成员thread,它也是一个数据结构,里面记录着进程切换时的系统堆栈指针,返回地址等关键信息。因此复制这个thread时子进程需要相应修改返回地址,我们之前已经获取到子进程上下文的地址,此时我们将这个地址赋给该指针,使得子进程看上去像之前被切换了一样。

此时内核空间的继承也已经完成,最后只需要设置执行域、设置本进程页面可以被换出以及与父进程通信时的信号。此外PCB中的counter字段指的是进程的运行时间配额,这里我们将父进程的时间配额分一半给子进程,如果我们使用vfork创建线程,那么需要在PCB中将子线程加入父进程的线程组。最后把子进程的PCB链入内核的进程队列,至此新进程的创建全部完成并且已经挂入可运行进程的队列接受调度。

这里需要注意的一点是当调用vfork时,子进程与父进程共享用户空间,那么当子进程创建完成之后如果两个进程都进入用户态运行,那么将导致两个进程操作一个用户空间,所以我们必须避免这样的情况,Linux在子进程创建完之后将父进程在一个信号量上执行down操作,让父进程睡眠,并且子进程执行execve直到结束再唤醒父进程。

自从deep learning成为研究热点之后,为了解决不同种类的问题,神经网络的结构愈发复杂起来,面对图像信息的提取与图像特征的学习,CNN已经成为众多神经网络的佼佼者,由于CNN与普通网络的区别,训练的BP算法也需要进行相应的调整,为此笔者查阅了一些资料,现将CNN的BP算法整理如下:

Features of CNN

Convolution layer

卷积层引入了卷积核的概念,输出向量可以理解为是卷积核与输入向量卷积产生的结果,因此并不是全连接的关系,在这里我们可以回忆一下卷积运算的定义:卷积是通过两个函数f和g生成另一个函数的计算方法,其计算公式为:

\[(f*g)[n] = \sum_{m=-\infty}^\infty f[n-m] \times g[m]\]

直观一点就是将函数f绕y轴翻转从左向右平移,计算f与g的重叠部分的面积,如下图(Wiki)img

因此在CNN的卷积运算中,我们可以认为将卷积核翻转后在原始图像上进行滑动,计算重叠部分的elementwise的乘积并求和,用数学公式表达就是: \[x_j^l = f(\sum_{i \in M_j} x_i^{l-1} * k_{ij}^l + b_j^l)\]

式中j表示第j个feature map,l表示第l层,\(M_j\)表示原图像与卷积和的重叠部分,在这里仅仅因为完整性才加上j,为了理解卷积层的反向传播,我们假设feature map只有一个,即卷积核的数量为1

Pooling layer

池化层比卷积层来得简单,无论是MaxPooling还是Average Pooling我们很容易找到输入与输出向量的关系,需要注意的是对于MaxPooling,计算最大值的同时需要记住该最大值的下标,因为在反向传播时需要用到该下标。

BackPropagation

按照BP算法的流程, 我们只要知道这一节中我们假设BP算法已经反向传播到最后一个全连接层,记为\(\delta^l\)

Pooling layer

先从比较简单的池化层入手,注意到输入向量在经过池化层之后,假设原始图像尺寸为\(H\*W\), 窗口尺寸为d,且窗口滑动不重叠,则输出向量的尺寸为: \[H*W -> Ceil(H/d) * Ceil(W/d)\]

由于Pooling层没有权值矩阵参与运算,仅仅是压缩了原始向量的尺寸,因此在进行反向传播时,也只需要将残差delta“放大”到原来的大小就可以了,pooling的数学表达式及其偏导关系为:

\[g(x)= \begin{cases}\sum_{k=1}^mx_k \over m, \ & {\partial g \over \partial x} = {1 \over m } \ mean \ pooling \cr max(x) & {\partial g \over \partial x} = {\begin{cases} 1 &if \ x_j = max(x) \cr 0 &otherwise \ max \ pooling \end{cases}} \end{cases}\]

pooling的BP算法,看上去复杂其实原理非常简单,我们只需要进行一步上采样upsampling的操作:

  • maxpooling:将输出向量的每个元素扩展成d*d的矩阵,前向传播时记录的下标所对应的元素为该元素的值,其他置为0
  • meanpooling:只需要将矩阵中元素都置为该元素的值就可以了

我们把上采样记作\(up(x)\),因此残差在经过pooling层时,可以简单地计算上一层残差为

\[\delta^{l} = f^{'}(u_j^l \circ up(\delta_j^{l+1}))\]

式中\(f\)表示pooling层后接的激活函数,\(u\)表示该\(f\)的输入,但是很多的CNN架构中Pooling层中这一项为1,\(\circ\)指elementwise乘法

Convolution layer

其实在卷积层我们也用到了池化压缩的思想,但是卷积层有卷积核,相当于全连接层的权值矩阵,因此我们可以类比fc层的残差计算方法:

\[\delta^{l-1} = (W^T \delta^{l}) * f^{'}(u^{l-1})\]

卷积层不像全连接层那样输入与输出之间每两个元素都有联系,前向传播时对于输出向量中的每个元素,在输入向量中与之相关联的元素只有d*d个,即卷积窗口的大小,我们很容易通过下图看出对应关系:kernel

因此反向传播时,我们也只需要考虑部分的对应关系,为了简单我们以一维向量的卷积为例:img

\[\delta_n^{l-1} = {\partial J \over \partial x_n} = {\partial J \over \partial y}{\partial y \over \partial x_n} = \sum_{i=1}^{|w|} {\partial J \over \partial y_{n-i+1}}{\partial y_{n-i+1} \over {\partial x_n}} = \sum_{i=1}^{|w|} {\delta_{n-i+1}^{l}w_i} = (\delta^{l}*flip(w))[n]\]

式中w代表卷积核的参数,上式的结果可以简化为:

\[\delta^{l-1} = \delta^{l} * flip(w)\] 这里我们忽略了激活函数\(f\),可以看出该公式与全连接层的公式十分类似,式中flip表示翻转,意思是在反向传播时需要将卷积核进行翻转

这里其实有一个trick,在标准的卷积运算中定义了翻转因此在反向传播时我们也对应进行翻转,但是在实际训练时我们不进行翻转的话,在BP过程中就不需要翻转回来 事实上,由于卷积层训练的就是卷积核的参数,因此我们不翻转同样可以训练,而且可以简化计算过程

残差的反向传播已经完成,下面就是通过残差计算偏导了,全连接层在计算偏导时只需要将后一层的残差向量乘以前面一层的对应元素即可,但是卷积核的滑动窗口特性,实际参与计算的元素要多一些,所以我们需要修改一下:

\[{\partial J \over \partial {k_{ij}^{l}}} = \sum_{u,v} ({\delta_{j}^{l}}_{uv}(p_{i}^{l-1})_{uv})\]

式中p表示的是原输入向量中与卷积核元素\(k_{ij}\)相乘的元素,如下图所示:kernel_partial

假设步长为2,那么\(p_i\)指的就是图中红色的部分,如果步长设置为1,那么\(p_i\)指的就是图像中阴影加粗的部分

Conclusion

经过分析我们可以得出CNN的反向传播其实也有规律可循,关键是需要了解BP算法的原理,这是理清任何使用BP算法进行优化求解的神经网络的基本,抓住两个点:反向传播其实是将输出层作为输入层计算各层残差的过程,把握好各层的性质理解起来就比较容易了。

Reference

Bouvrie J. Notes on convolutional neural networks[J]. 2006.

http://www.slideshare.net/kuwajima/cnnbp

Computer Systems: Linking

《深入理解计算机系统》中Linking这一章对编译过程中链接器的作用做了非常详尽的介绍,对于程序员而言可能在算法、数据结构以及编程语言上花的时间比较多,然而对于计算机如何将代码编译为可执行文件的过程缺乏系统的了解,然而如果需要了解Linux下程序完整的编译执行过程,阅读本书的相关章节是十分必要的,笔记比较长所以分成两部分

基本概念

Linking的定义:将各种代码和数据部分收集起来并组合成一个单一文件的过程,要理解这句话的含义首先需要明白GNU系统的一般编译流程:compile

当然链接这一步并不一定要在程序编译时进行,Linking操作的对象是已经编译完成的目标文件,输出的结果就是可执行文件,链接器在整个编译过程中起到以下两个作用:

1.解析.o文件将符号引用与定义联系起来
2.为指令与变量分配运行时地址

可重定位目标文件

要了解链接器的工作原理首先需要清楚它的输入文件,.o文件

在弄清可重定位目标文件的内容之前,一些平时不好的习惯可能会引发概念上的混淆 比如在Linux上编译程序时,我们可能会执行这样的指令:

gcc -o *main.o* -I(dirs for header files) -l(paths for libraries)

之后可以直接在控制台执行./main.o,这样看来我们似乎直接执行了可重定位目标文件,然而这条指令中的.o文件是编译程序输出的最后结果,也就是说我们把可执行文件的名字命名成了main.o,而实际上汇编器生成的.o文件位于tmp目录下,因此在实际写程序时最好把文件的名字区分开,以免混淆。

文件格式

书中可重定位目标文件的文件内容非常繁杂,简单而言该文件分为许多的section,每个section都包含了,总结下来分为以下三类

1.存储机器指令与全局变量(如.text, .data, .bss)
2.存储指令与变量的位置相关信息(即重定位信息, 如.rel.text, rel.data)
3.存储函数与变量的各种属性(.symtab)

需要注意的是链接器仅仅考虑全局变量,函数中的局部变量由栈管理

符号表.symtab

符号

从程序员的角度看符号是一个个的变量名和函数名,而对于链接器而言只是一些字符串而已,因此在这里被称作符号,符号表包含了原文件中各个符号(函数和变量)的信息,有一种符号不在链接器的管理范围之内,符号表不包含对应于本地非静态程序变量的符号,因为这些符号也由栈管理

需要注意的是当变量名前面指定了static关键字之后,无论该变量定义在函数内部还是外部,都会存储在.o文件的符号表中,对于函数也同样如此。

符号表的格式

如果从数据库的角度看,符号表可以看作是一张普通的关系表,每个符号及其相关属性都可以被看作是一个元祖,整张表中包含的属性包括:

符号的偏移量(存储格式为int型,可以理解为下标)
符号的地址
符号的类型(数据或者是函数)
符号的大小
 

书中给出的例子非常清楚,以main.o为例,基本的格式如下图:symtab

附上源码:

/* main.c */ 
void swap();

int buf[2] = {1,2}

int main(){
    swap();
    return 0;
}

符号解析

全局变量解析

之前提到链接器的作用之一就是解析.o文件,其实主要解析的就是符号表中的符号,实际上链接器在这一步所做的工作是将原文件出现的变量的引用和符号表中的符号定义联系起来

如果符号的定义就在原文件中,那么链接器可以直接联系引用和定义,但是如果符号不是定义在原文件中,链接器假设该符号定义在其他某个模块中,同时如果出现多个文件同时定义相同变量的情况,比如一个文件中声明全局变量,另一个文件定义全局变量

  • 强符号:已初始化的函数及变量
  • 弱符号:未初始化的函数及变量

当出现多个同名的全局变量时,链接器遵循以下三个标准进行解析: * 不允许有多个强符号 * 如果有一个强符号和多个弱符号,那么选择强符号 * 如果有多个弱符号,那么从这些弱符号中任意选择一个

简单而言链接器不允许多重定义,并且会优先连接变量定义的位置

通过对符号解析部分的介绍我们也明白了为什么写程序时不鼓励定义太多的全局变量的原因,当程序架构比较大,每个人分别编写自己的模块时,很容易发生全局变量的定义冲突,而且编译器不会报这样的错误,因为已经涉及到代码整合时的程序逻辑层面的错误而不是编程语言规范的错误。

与静态库连接

在阅读此章节之前我认为静态库在编译时进行链接,而动态链接库在运行时进行链接,这种理解其实并不正确,这两种库的不同之处不在链接的时机而在于它们构成和设计思想

静态库

由于标准函数会被广泛使用,如果在编译时直接生成这些函数的代码不仅增加编译器的工作量,同时当这些函数更新时也难以维护编译器,如果为每个函数都生成一个.o文件,那么我们需要写很冗长的链接命令,同时也会消耗多余的存储空间,费时也费力。

静态库可以很好地解决链接这些“常用函数”的问题,一个静态库以一种称为存档的特殊文件格式存放在磁盘中,可以理解为是一组.o文件的集合。

直观上讲,当我们需要链接某个函数时,我们只需要链接该静态库中的对应模块,即该函数对应的.o文件就可以了,因此静态库只需要向链接器提供每个模块的大小和位置就可以了。

对于自己原先的对于静态库的理解,当编译时添加-static参数后,链接器会生成一个完全链接的可执行目标文件,也就是在编译时进行链接,这样生成的可执行文件可以直接在内存中执行,因此链接的时机和链接的库的类型其实并无多大关系

使用静态库解析引用

回到符号解析,之前介绍了解析符号时,符号定义在原文件中的情况,那么如果符号定义在静态库中怎么进行链接呢?

首先链接器会按顺序扫描.o文件和静态链接库,在扫描过程中链接器会维护一个.o文件的集合E, 一个未解析的符号集合U,以及一个在输入文件中已定义的符号集合D,链接时按照以下流程进行链接:compile

按照笔者理解U和D可以认为是两个数组,U用来存储未匹配到定义的符号,而D存储已定义的符号,而E用来存储所有输入文件中链接器对符号的解析结果

需要注意的链接器只会链接在U中的符号,由于链接器是按顺序扫描的,因此如果符号的定义出现在引用之前并且引用后再也没有出现该符号的定义,那么就会出现扫描结束后U不为空的情况,导致链接出错

重定位

完成符号解析之后,代码节与数据节的大小就已经确定,之前提到链接器的第二个作用就是分配运行时地址,重定位的目的是为了让CPU知道符号在存储器中的位置,因此重定位分为两步:

1.将所有输入模块的同类型节(如data节)合并,并将运行时的地址赋给这些合并后的“聚合节”,同时赋给输入模块的每个节
2.修改代码节和数据节中对每个符号的引用,使得他们指向正确的地址

这样写可能还是不够清晰,简单而言第一步为每个节分配运行时地址,而第二步为节中每个指令或数据分配运行时地址,而为了给指令与数据分配地址,我们需要明白重定位条目的概念

`重定位条目`

在介绍可重定向目标文件的内容时提到过有section负责存储重定位信息,如代码的重定位信息在.rel.text中,数据的重定位信息在.rel.data中,这两个张表告诉链接器需要修改的引用在节中的什么位置以及重定位的类型(如何修改引用的地址),表中每一项就是一个重定位条目,当链接器找到节中的符号后根据重定位类型计算该符号运行时地址。

书中介绍了两种重定位的类型:PC相对引用与绝对引用

PC相对引用

相对引用使用基地址加偏移量的方式寻址,基地址存储在程序计数器PC中,所以我们只需要计算出偏移量,CPU就可以找到该指令或者数据的运行时地址了,假设我们已经知道了节的存储器地址和符号的运行时地址,计算方式如下:

计算swap在节中的地址 refptr = s+r.offset
计算引用swap的指令地址: refaddr = ADDR(s) + r.offset
计算偏移量  *refptr = ADDR(r.symbol) + *refptr - refaddr

书中给的例子比较难懂,首先抛开那个 *refptr不看, 参考书3.6节的内容,在进行PC相对寻址时,目标跳转地址就是例子中swap函数的地址,而链接器需要修改的就是引用swap的指令的目标编码,这两者之间的关系为:

目标编码 = 目标跳转地址 - PC

因此在求目标编码时,实际的目标跳转地址等于swap的地址:0x80483c8,从3.6节的例子中我们可以看出PC的值是在当前指令的地址基础上+4,即当前指令的后面一条指令,因此实际上原式等于

目标编码 = 目标跳转地址 - (当前指令地址+4)

当前指令自然是引用swap的指令地址,该地址可以用节基地址加偏移的方式求得:

引用swap的指令地址 = 节基地址 + 引用偏移 

绝对引用

绝对引用理解起来就容易许多,修改引用时直接把值修改为目标跳转地址和初始值的和,CPU会直接通过该引用内的值查找对应的数据

按照书中的例子,bufp0需要重定位指向数组buf的首地址,又由于原本.data节中的重定位条目中的初始值为0,所以直接把buf数组的首地址赋给bufp0即可。由于重定位的对象是指针,因此该过程类似于为指针赋值的过程。

Computer Systems: Linking

《深入理解计算机系统》中Linking这一章对编译过程中链接器的作用做了非常详尽的介绍,对于程序员而言可能在算法、数据结构以及编程语言上花的时间比较多,然而对于计算机如何将代码编译为可执行文件的过程缺乏系统的了解,然而如果需要了解Linux下程序完整的编译执行过程,阅读本书的相关章节是十分必要的,笔记比较长所以分成两部分

可执行目标文件

可执行目标文件与前面提到的可重定向目标文件最大的区别在于,可执行目标文件必须将文件中的节映射到存储器中的段中,同时它还定义了一个.init函数用来初始化代码,由于可执行目标文件可以直接运行,因此该文件中不包含重定向信息

可执行目标文件的加载

将可执行目标文件中的代码和数据复制到存储器的过程称为加载,存储器映像为程序分配了的数据空间(包括堆栈)以及用来存储数据和代码的段,基本结构如下:

最上方是用户栈,主要用来存储局部变量等
下面的存储器区域用来存储共享库
再下面是堆空间(malloc时就会分配这部分空间)
最后是可执行文件中的数据和代码段

比较令我印象深刻的是这一章节介绍了C程序的启动细节,当加载器完成代码和数据段的加载后:

加载器跳转到程序入口点,即符号_start的地址,在该地址启动代码
调用.text和.init的初始化例程,启动代码调用atexit例程,该程序包含原程序正常终止时应该调用的程序
之后运行原程序中的main函数执行我们的C代码
最后exit函数调用_exit返回

从启动例程的伪代码中就可以看出main函数在C程序中必须出现,这也就是为什么我们把main函数称为程序入口的原因

对于习题7.5中第二个问题,无论直接调用exit还是使用return,抑或是什么都不写,最后都会调用_exit程序把控制返回给操作系统

动态链接共享库

静态库虽然能很好地管理大量公共函数的链接问题,但是如果有多个程序同时引用了一个函数,函数会被复制多份,显然这会占用多余的内存空间,因此共享库被设计来解决函数代码重复复制的问题

按照书上的说法,在运行时共享库可以加载到任意的存储器地址并和存储器中的程序链接起来,这个过程也被称为动态链接,有专门的动态链接器完成此任务,共享库独立于应用程序,因此在链接时链接器不会拷贝动态链接库中的代码和数据

在加载时,如果需要链接动态链接库,那么加载器会把控制权转交给动态链接器,动态链接器会执行如下重定位流程:

1.重定位每个动态链接库的文本和数据到存储器段
2.重定位可执行目标文件中的符号和引用

那么如何做到让多个进程共享一块存储器中的库代码呢?

书中介绍了编译库代码,使得链接器不需要修改代码就可以在任何地址加载和执行,相当于预先把库代码编译完成后,这里我们可以看出动态链接库与静态链接库的一个重要的不同点:动态链接库不需要链接器进行重定位,但是按照之前几节的说法,如果我们需要调用外部定义的数据或者函数,那么如何找到对应的地址呢?

书中提到了关键的一个事实:无论我们在存储器的何处加载目标模块,数据段总是被分配成紧随在代码段的后面这意味着如果代码段和数据段的长度固定,那么我们始终可以通过相对寻址找到我们需要的数据或指令。

全局偏移量表GOT

由于动态链接库中的代码不会编译到可执行目标文件中,因此我们需要给可执行目标文件一定的信息让加载起能够找到动态链接库的代码,因此引入GOT和PLT两张表,分别用来记录在这个目标模块中引用的全局变量和外部定义函数。

  • 通过GOT引用全局变量: 当程序需要引用某个全局变量时:

    首先将PC的值移到寄存器中
    接着通过变量在GOT中的偏移找到存有该变量地址的条目
    最后通过条目中提供的全局地址找到该变量

从C/C++程序员的角度而言,这相当于进行两次寻址,第一次找到全局变量的地址,第二次找到该变量,GOT就是一张提供了各变量地址的表 类似地,当程序需要调用某个外部函数时,同样执行上述的步骤

值得注意的是为了防止每次调用动态链接库的数据或函数时都要重复上述的步骤,编译器使用了一种称为“延迟绑定”的技术

过程链接表PLT

介绍延迟绑定之前,首先需要介绍过程链接表的概念,书中没有详细说明PLT存储的内容,因此我查阅了一些资料:

过程链接表用于把位置独立的函数调用重定向到绝对位置。PLT中的每个条目为本程序要调用的函数提供一个入口,PLT 的第1个入口PLT[0] 是一段访问动态链接器的特殊代码。程序对PLT入口的第1次访问都转到了PLT[0]

当第一次过程调用发生时,最后总会跳转到PLT[0]中,PLT[0]包含跳转到动态链接器的信息,待完成符号解析后,将符号的实际地址存入相应的GOT项,这样以后调用函数时可直接跳到实际的函数地址,不必再执行符号解析函数。延迟绑定指的就是在第一次引用动态链接库的指令时,通过PLT和GOT两张表寻找运行时的指令地址,之后修改GOT项的内容使得后面的调用不再需要重复相同的步骤。

Linux用一个全局的库映射信息结构struct link_map链表来管理和控制所有动态库的加载,动态库的加载过程实际上是映射库文件到内存中,并填充库映射信息结构添加到链表中的过程。觉得这部分书中讲得也不够清楚,还是有点似懂非懂。

但是读完动态链接的部分之后,觉得动态链接与链接的定义其实有点出入,按照本章开头的定义,链接强调组合成为单一文件,然而动态链接的本质却是通过间接的方式寻找调用的数据和代码,链接器在链接动态库时紧紧拷贝重定位和符号表信息,并不参与真正的链接过程,因此我认为链接与动态链接是两个并列的概念

总结

总的来说,综合符号解析静态库链接动态链接,一个完整的链接过程如下图:whole_process

总体而言链接的重点在于重定位与两类链接库的链接原理,理清这些概念之后整个链接的过程就比较清晰了。

在开始阅读Blob之前,需要预先了解Caffe的架构与protobuf,否则看代码的时候容易一头雾水

Caffe基本架构

对于任何一个网络而言,Caffe主要用4个类来构造网络:

  • BLob:存储数据,blob既可以存储网络的权重,在进行训练时修改的其实就是每个blob实例
  • Layer:构成网络的基础单元,无论是卷积层,pooling层还是全连接层等等都是从这个类派生出来的
  • Net:定义一个网络的架构,当我们把网络中每一层都建立完之后,通过Net类来搭建整个网络
  • Solver:用来训练网络的类,例如SGD就在这部分实现

Protobuf

在理清基本架构之后可能有人会问:一个网络需要那么多参数,且每个参数的数据类型不尽相同,如何解决这个问题呢?

Protobuf就是用来解决此类问题的,我们只需要像写配置文件一样把网络中每一层的参数设置好(当然配置文件必须按照一定的格式),protobuf会自动生成代码,用来解析“配置文件”中的参数结构体,代码中包括了对参数的设置、读取和序列化等等操作 另外当网络训练完成之后,存储时也使用了protobuf进行处理,把Net转化为多个Message对象进行存储

Caffe代码中参数初始化和参数操作都是基于protobuf完成,只需要定义网络参数,不再需要考虑如何把参数传递给应用程序的问题了,protobuf会帮你完成~

Blob

Blob本身其实没有特别多的内容,作为Caffe中数据的基础单元,我们可以简单地吧Blob理解成一个容器,里面存储的是多维向量及其相关的信息

首先看Blob.hpp:

Blob()
 : data_(), diff_(), count_(0), capacity_(0) {}
   

构造函数中初始化了4个对象,data_表示Blob中的数据,diff_表示反向传播时的误差,count_表示数据当前的维度(因为可以reshape),而capacity_表示数据最大的维度

接下来在Blob.cpp里主要包含了实例的初始化和reshape函数,值得注意的是如果blob中存储的是网络的参数(如全连接层和卷积层的kernel),那么Blob提供update函数用来更新自己的参数。

void Blob<Dtype>::Update() {                                                                                                                                  
  // We will perform update based on where the data is located.                                                                                               
  switch (data_->head()) {                                                                                                                                    
  case SyncedMemory::HEAD_AT_CPU:                                                                                                                             
    // perform computation on CPU                                                                                                                             
    caffe_axpy<Dtype>(count_, Dtype(-1),                                                                                                                      
      static_cast<const Dtype*>(diff_->cpu_data()),                                                                                                         
      static_cast<Dtype*>(data_->mutable_cpu_data()));                                                                                                      
    break;                                                                                                                                                    
  case SyncedMemory::HEAD_AT_GPU:                                                                                                                             
  case SyncedMemory::SYNCED:                                                                                                                                  
  #ifndef CPU_ONLY                                                                                                                                              
  // perform computation on GPU                                                                                                                             
  caffe_gpu_axpy<Dtype>(count_, Dtype(-1),                                                                                                                  
      static_cast<const Dtype*>(diff_->gpu_data()),                                                                                                         
      static_cast<Dtype*>(data_->mutable_gpu_data()));                                                                                                      
  #else                                                                                                                                                         
  NO_GPU;                                                                                                                                                   
  #endif                                                                                                                                                        
  break;                                                                                                                                                    
  default:                                                                                                                                                    
    LOG(FATAL) << "Syncedmem not initialized.";                                                                                                               
  }                                                                                                                                                           
}                            

代码中包含了GPU和CPU两种实现,其实核心就是caffe_gpu_axpy那一句更新参数

Layer

对Blob有了一定了解之后可以看Layer了,事实上Layer是caffe架构中内容最多的部分,我们在写配置文件的时候其实都是在组合layer构成一个网络,很多运算操作在caffe中都是以layer的形式存在的,如argmax和elementwise运算等等.许多对caffe的扩展其实也是继承Layer层重新定义了具有新功能的层

layer的工作模式类似数学中的函数概念,给定一个输入(bottom blobs),layer内部完成自己的功能,返回一个输出(top blobs)

caffe中的layer分两种,common layer和vision layer: - data_layers.hpp中声明了神经网络与输入数据之间的交互层,如导入/导出hdf5数据,从图像中导入数据等等 - common_layers.hpp中声明了许多常用的包含基础功能(flatten, softmax等)的层 - vision_layers.hpp中主要包含对针对图像处理的层(convolutional, pooling等) - neuron_layers.hpp中主要包含与神经元的定义与操作相关的层(dropout,ReLu等) - loss_layers.hpp中主要包含了计算网络Loss的层,除了我们常见的softmax loss之外还包括了比较常用多euclidean loss, hinge loss等等 看了下vision layer中居然还包含了SPPnet这种处理image scale的层,除此之外还有deconvolution layer,确实是很给力啊

caffe还提供了layer_factory供我们快速实现自己的layer

所有的Layer层都包含Forward和Backward的函数,这两个函数包含了整个layer的计算功能,对于开发者而言如果想实现自己的layer,其实主要就是完成这两个函数逻辑

具体的某一种Layer的代码解析不在本文的范畴里,以后会另开blog详细描述常用的layer代码实现

Net

Net中包含了对整个网络的操作实现,在看源代码之前笔者只想到了设置learning_rate、 weight_decay和迭代次数等等功能,以及控制Forward和Backward等,然而事实上caffe提供了许多非常有用的函数,如在RCNN training中提到的share weights功能,使得你可以直接使用预先训练好的网络参数进行初始化,这也是为什么在caffe的example中我们可以直接通过命令行对imagenet训练出来的网络进行fine-tuning的原因

Solver

相对而言solver的实现比较简单,创建solver对象时我们只需要关注优化算法就可以了,caffe目前提供三种梯度下降的方法: - SGD(momentum) - NesterRov - Adagrad

这篇日志主要用来整合近几年在ImageNet竞赛中获得较高成绩的CNN网络相关论文的笔记,因为思想都是基于CNN,在实际训练网络或者网络结构上有创新的地方,因此就统一写成一篇文档了,实验结果部分就省略了,主要集中在文章亮点的地方,一共有4篇相关的论文(Alexnet, GoogleNet, VGGnet和OverFeat),会保持长期更新。

caffe的example中给出了Alexnet和GoogleNet的模型,熟悉caffe的话可以直接看对应的depoly.prototxt,比较直观

AlexNet

Architecture

Alexnet是ILSVRC2012的冠军,网络结构比较深但是很有规律,关于这篇论文有许多在实际train网络时候的一些比较有用的trick,AlexNet的训练过程如下:

  • rescale the image such that the shorter side is of length 256, and crop the centeral 256*256 patch from the resulting image 先rescale后crop的方式处理图像scale的问题
  • 5个卷积层3个pooling 层,且神经元的激活函数使用的是ReLu,降低计算量
  • Training on multiple GPUs,现在看来GPU并不是非常好,但是多GPU并行计算
  • LRN(Local Response Normalization) Normalization 笔者认为这是本文的亮点,虽然ReLu不需要输入normalization但是引入LRN可以提升1.4%至1.2%的准确率,简单来说就是对ReLu层的输出进行归一化,归一化公式如下: \[b_{x,y}^{i} = a_{x,y}^{i}/(k+\alpha\sum_{j=max(0,i-n/2)}^{min(N-1,i+n/2)}(a_{x,y}^j)^2)\] 其中i和j表示第i/j个卷积的kernel,而a表示ReLu的输出,b表示归一化后的结果

    注:caffe的LRN层实现中提供两种Normalization的方式:通道内归一化和通道间归一化,这个在caffe源码笔记中会详细讲解
  • Overlapping Pooling 传统的pooling方式将feature map分成独立的grid每个grid进行pooling,而本文中采用滑动窗口的方式,每次滑动的stride小于窗口的大小,实验证明,这样的方法能提升0.4%-0.3%的准确率

整体网络结构直接上图:AlexNet

Training Details

Data Augmentation

笔者认为这一部分内容在工业界相当有用,Deep learning需要大量的数据,而当数据集不够充足的时候如何做好数据增量十分关键,同时还能减少overfitting

文中介绍了两种方法:

  • generating image translations and horizontal reflections(截取部分图像和镜像翻转)
  • alter the intensities of the RGB channels(借助PCA改变RGB通道的像素值)

Dropout

Dropout有专门的文献介绍,简单来说就是每次Forward的时候神经元以某概率输出0,这样在BP的时候该神经元的权重也不会更改

GoogleNet

GoogleNet以及其复杂的网络结构而闻名,ILSVRC2014的冠军,一共22层的网络看上去复杂但依旧有规律可循,文章中主要的亮点在于Inception结构

Motivation

单纯加深网络会导致过拟合问题出现,且由于90%的计算量集中在最后的全连接层,为了降低计算量,文中提出了将全连接层替换为稀疏连接层。

Architecture

Inception Module是构成整个GoogleNet的关键组件,其主要思想就是用密集的组件来逼近稀疏的卷积网络结构

Naive Inception结构如下图,假设每个Inception视作一个部件component,Inception在接收上一层的结果后,用不同尺寸的卷积层(1*1,3*3,5*5)和pooling层并行计算结果,将每层的结果合并起来,最后经过一个滤波器进行分组

但是会带来一个问题:即使是一个合适数量的卷积,也会因为大量的滤波而变得特别expensive。经过pooling层输出的合并,最终可能会导致数量级增大不可避免。处理效率不高导致计算崩溃。

因此改进方案是:在需要大量计算的地方进行降维。压缩信息以聚合。1*1卷积不仅用来降维,还用来引入非线性特性。

GoogleNet

GoogleNet

GoogleNet

比较有趣的地方是网络中有三个softmax分类器,文中作者提到对于浅层网络而言,中间网络产生的特征非常有辨识力,在这些层中增加一些额外的分类器能增加BP的梯度同时提供额外的正则化,每3个Inception module会增加一个Softmax分类器。在训练过程中,损失会根据权重叠加,而在测试时丢弃。

Training的时候使用了AlexNet中的trick

Insights

  • approximating the expected optimal sparse structure by readily available dense building blocks is a viable method for improving neural net- works for computer vision.(虽然增加了计算量但是能显著提高分类的准确率)
  • For both classification and detection, it is expected that similar quality of result can be achieved by much more ex- pensive non-Inception-type networks of similar depth and width.(没有使用bounding box regression,说明Inception同样适用于detection和localization的task)

VGG net

VGG Net是ILSCVRC2014 classification的第二名,localization的第一名,网络结构上比其他网络都要来得复杂(实验过程中卷积层最多有16个),但是文章中对如何构造复杂网络和训练网络的描述非常详尽,相信对research会有很多帮助

Network Configuration

Training

网络的training借鉴了AlexNet在训练中使用的方法,同样是momentum SGD+dropout,处理图像尺寸的方法相同,做数据增量的方法也相同,但是由于一共有5个网络需要训练,且网络深度依次递增,因此在参数初始化时作者提出:

最简单的网络使用随机初始化,而后面的网络中最前面的4个卷积层与最后3个全连接层参数用先前网络的参数初始化,其他层使用随机初始化,这种首先训练简单网络,随后使用其参数来初始化复杂网络的训练方法是一种非常合理且高效的方式

值得一提的是文中对比了7*7的卷积层与三个3*3的卷积层之间的对比,相比较而言多个小的卷积层级联能在引入更多的linear rectify之外同时还能降低卷积层参数的数量。

整个训练过程如下:

  • Classification
    • 设计结构复杂度依次递增的网络
    • 在Image size的处理上,作者提出single-scale和multi-scale的方法, single-scale的方法与AlexNet相同,先resize后crop,multi-scale的方法类似于随机采样,每次rescale之前在一个固定区间内(如[256,512])选取一个scale,这样每个图像的尺寸就不同了,但是怎么处理feature长度不同的问题作者似乎没有说明
    • 每次训练新的网络之前用之前网络的参数进行初始化以加快收敛速度
  • Localization
    • Training Localization的方法与classification相同,只不过用的是Euclidean Loss

Testing

在testing阶段,网络接收图像数据之前首先需要把图像rescale到固定大小,作者称之为test scale,之后首先通过fc层计算,我们把fc层看作一个卷积窗口为1*1的卷积层,得到的feature map维度与object类别相同。

这样做的好处是对比首先crop再通过卷积计算feature map的做法,直接通过fc层计算可以减少许多重复的卷积计算量,crop出来的图像之间必然会有重叠的部分,这些重叠部分增加了测试时卷积的计算量,但是笔者认为既然在训练时使用crop来做数据增量,测试时用crop可以增加网络输出的置信度(每个crop输出分类结果,这个结果甚至可以用来做类似bagging的训练),如果面对实时性要求比较高的情况,对整张图片应用fc层是比较可行的方法。

OverFeat

OverFeat最出彩的地方在于使用一个CNN解决Classfication、Localization和Detection的任务,以及Sliding Window和CNN的结合,每个任务使用的神经网络不同之处只在最后的分类器,大牛Yann LeCun的文章

网络结构的前五层与Alexnet相同,Alexnet的网络结构已经成为feature extraction的经典结构了,如下图所示: OverFeat

Multiscale training

训练时大多数人都会碰到Multiscale的问题,本文中作者提出在pooling时引入偏移量的方法,具体过程如下图 Pooling 按照笔者理解,原始的3*3pooling的起始位置为(0,1,2),其实就是使用stride步长为1的pooling层,之后按照原始stride进行分组,得到多个分组的pooling向量之后使用滑动窗口的方式得到feature map,重新将原先分组的结果合并成一个向量作为整张图片的feature map,无论图像的尺寸多大,使用stride为1的pooling层能最大程度上保持原始信息,并且分组之后每一个feature map向量长度保持一致。

Sliding Window

训练CNN时要求输入图像的大小固定,但是如果输入的图像尺寸比原先大怎么办呢?对于一个训练好的CNN来说,卷积核的大小和数量以及每一层feature map的个数是固定的,但是feature map的大小是可以改变的。

当测试样本和训练样本大小相同时,CNN最后一层的每一个节点分别输出一个0~1的实数,代表测试样本属于某一类的概率;当测试样本比训练样本大时,CNN最后一层每一个节点的输出为一个矩阵,矩阵中的每一个元素表示对应的图像块属于某一类的概率,其结果相当于通过滑动窗口从图像中进行采样,然后分别对采样到的图像块进行操作 Sliding

Localization

将原先classification网络的最后一层softmax替换为Bounding box回归: 最后一个pooling层输出的feature map通过两个全连接层映射到一个输出层,输出被看作一个由4维向量构成的矩阵,每个向量对应了原始图像某一块区域中的object的bounding box的位置,之后开始合并各个区域中的bounding box直到两个bounding box之间的match score足够大。

值得注意的是这个regression网络对于每一个object类别都会输出一个bounding box,前面一节中提到的classification的网络会输出图像分类的概率值,于是每一类的bounding box都会对应一个置信度,在合并之后网络会输出一个置信度,这个置信度就是原先所有class置信度的最大值,因此完成合并之后网络的输出是一个带有最大confidence的bounding box

Detection

物体检测的方法其实就是结合了classification以及localization,但是文中没有给出具体的训练细节,笔者认为与Localization非常相似,因为直观上只要根据置信度删选Localization输出的bounding box,之后取每一个图像块中置信度最大bounding box就可以了,可以看出相对于RCNN的做法,OverFeat比较暴力一些,对每块图像区域都会输出1000类的预测结果,其计算量想必也不小