昨天下午在小刘的鼓励下拖着颤抖的双手接受了海康威视的offer， 半个小时之后滴滴的面试官向我发起了面试邀约， 我笑着拒绝了。 那一刻突然有一种悲壮之感涌上心头。 我的秋招就这样结束了， 再也不会有什么改变的机会了。 平台也好， 薪资也好， 好像我都不是特别满意。 但是又没有拿到很满意的。 逛到牛客逛到offershow上清一色的劝退价，总是有点意难平。 小刘拿到了腾讯sp拿到了拼多多的ssp， 相形见绌下又觉得自己事业上挺失败的。 回想起一路走过来的， 持续了两个半月的秋招，又觉得自己似乎涅槃重生了般。

我的秋招开始的很早， 因为实习的早所以八月初就回来了。 第一个面试电话是腾讯打来的。 还记得面完了之后状态变成复试之后心里的欣慰， 觉得自己的能力是可以被得到肯定的。 随后学长帮我内推的京东也很幸运的过了。 那个时候应该觉得想要的offer都会有吧。 随后虽然网易游戏和伏羲的简历没过， 拼多多和头条笔试挂了， 我还是觉得只是运气不够好。直到腾讯一面面完一个星期之后简历被释放我也还在安慰自己， 机会还有很多， 简历也有被捞起来的机会。 8月13号我接到了阿里巴巴的第一个电话， 面的很一般但是还是过了。 8月17号情人节那天收到了阿里巴巴的第二个电话，是个leader但面的还行，也过了。 8月20号收到了阿里巴巴三面， 也与面试官相聊甚欢， 最后面试官对我说最近两天就会给我安排下一面。 也是在8月20号这天我收到了京东的口头offer。 故事写到这里是不是看起来都很圆满， 可是转折总是发生在最猝不及防的地方。

8月26号小刘收到了阿里的hr面， hr也对他前面几面的表现表示了肯定。 还在等待四面技术面的我突然意识到是我自己的面试凉了， 这让一开始无比想去阿里的我受到了极大的打击。 好在前一天笔试的头条通过了， 如果能去头条也总是好的吧， 当时的我是这么想的。 9月1号早上起得很早， 把写满了满满一整本的知识点又拿出来一点一点背着， 把剑指offer上刷过很多遍的题再次刷着。 然后下午没有让我等的就开始面试了， 一面面的不太好但是过了， 二面因为手撕代码表现不够好， 挂了。 听到hr打电话给我说对不起同学你可能和我们的岗位不适合， 当时就没崩住眼泪都流下来了。 我开始认真的反思自己， 对自己的能力评价突然降到谷底。 coding不行， 没有论文， 没有比赛， 被刷的我就应该心服口服。 那一天小刘拿到了阿里巴巴计算平台事业部的意向书。 他一直在安慰我， 我心中的不甘和无力感却没有减少一分。 小刘说他已经拿到了阿里， 我去杭州就好了。 头条不是很重要， 那些个杭州的公司更重要一些。 我擦干眼泪， 决定好好准备接下来网易的笔试。 可能当时我身上被贴了心想事不成的符咒吧， 在9月7号也就是网易笔试前一天， 我的简历状态变成了-简历筛选未通过， 未。通。过。 真的是不知道该怨自己还是怨社会， 就觉得被拒绝的自己一点申诉的权利也没有。 从这一天开始， 所有我想去的公司全以失败告终。 我也终于心如死灰的决定， 那就跟着有阿里offer的小刘去杭州， 吧。 即使在杭州已经没有更好的选择。

接下来的一周整个人都是濒临崩溃的。 好在13号那天收到了招银的面试通知， 14号收到了海康威视和百度的面试通知。 我心里默念不能被打倒， 还要去认真对待这些我投过了简历的公司。 15号的海康面的很顺利， 接下来的招银和搜狗面的也顺利。 百度的二面挂了， 难过了一小会但也想明白了， 被挂了这么多次的我也许硬实力上是有所欠缺的， 总归达不到这些大公司的要求。 中秋节之后没有面试的我就一直每天刷牛客等海康威视的状态， 同时又开始和小刘一起打王者荣耀， 期间收到了招银网络科技的offer但因为薪资低就拒绝了。 在9月30号早上收到了海康威视的意向书。 小刘很开心， 小刘觉得我终于有一个在杭州的， 薪资不错， 平台也还行的offer了， 我就能和他一起去杭州了。 拿到海康威视意向书的我还抱有着小小的幻想过了三面的我可能会有一个sp offer， 期待着谈薪资的那天。

那一天很快就到了， 当hr说我的薪资是白菜的时候， 真的是有点失望。 当时还跟小刘吐槽觉得自己很无力， 最后兜兜转转去了一个不那么想去的公司拿着不那么满意的薪资。 当时小刘反问一句， 你有别的选择吗。 我哑口无言了， 是， 我没有别的选择。 小刘有阿里腾讯头条拼多多网易， 小刘可以用很多很多标准去评价他的offer， 是否核心， 薪资高不高， 平台大不大， leader好不好。 可是我不行啊！ 我只有一个技术一般口碑一般还在深圳的京东， 还有就是加班严重不是互联网公司薪资还不够的海康。微博和搜狗因为我想去杭州都没有拿到offer， 蘑菇街还在继续备胎。 我可以选什么呢， 在抱怨自己offer薪资或者加班多的时候， 其实是不是也默认了因为能力不够所以我只能有这样的选择。 在一个月以前我就跟我所有理想的公司全说了拜拜， 现在这样的结果不也是意料之中的吗？ 如果我想要更有资本的去追求我想要的薪资和工作环境， 我只有在接下来的日子里积累我的资本， 提升自己的能力。 这样才能在未来选择工作的时候， 有哪怕多一点点的主动权。

恩，秋招告诉我，谋事在人成事在天。 还有， 你从来都不是最优秀的那个。

折腾了两个多月， 我艰难又痛苦的找工作之旅也终于是结束了。 有时间来沉淀一下自己。 过去的半年， 在科研上的造化基本为0. 我所做的也就只有找实习+实习+找工作无缝衔接。 想想挺无奈的， 研究生也就这么三年时间， 大半年可能都没有认真好好看论文， 好好的长远的为我的未来学点东西。 终于工作着挣扎着过了这么久都主动或被动的结束了这一切， 还是想给过去的半年的日子做一个小结。

实习前的准备工作

大概研二下学期第三个星期开始就突然觉得自己需要开始准备找实习了， 但自己又很怂觉得自己能力不够不敢投简历。 直到早投的小伙伴都直接收到offer了我才开始准备投。 刚开始投简历的时候想的很好， 就想要去做图像算法相关的工作， 是大厂就好。 当时我还没有一个非常完整的图像项目经历， 由于之前半年一心想着发论文导致自己在图像这块也没有足够深入的了解。 小伙伴帮我内推了优图和百度金融， 在没有准备好的时候就去面试了， 草草背一下面经的结果直接导致优图挂了， 滴滴的内推也挂了， 只有百度水水的面试过了。 拿到百度之后还觉得很开心， 想着和导师商量着能早点过去。 最后以帮老师写三个星期论文为交换准备在四月底去北京。

第一次去实习， 我很多事情考虑的很少。 租房直接给别人打钱都没验房， 学生证身份证等材料也是提前一天才准备的。 虽然傻乎乎的但是运气很好， 还是一切都顺利了。4月23号坐上了去北京的火车， 收拾了需要住三个月的房子， 开始了北漂的日子。

实习中

实习的日子现在想起来是过的挺舒服的。 自己在的部门不是百度的核心部门， 也不涉及到很多业务。 每天早上9点半都是自己第一个来， 晚上8点就能走。 都是最早一个回到家的， 想想也是轻松自在。 要说有点不足的是， 可能做的事情跟我想象的并不一样。 我以为自己可以做金融风控方面的算法应用， 最后却被分到了基础平台部门， 被迫去学spark相关的东西。 记得刚开始每天都和小刘语音到深夜， 一点一点构建起自己玩的大数据知识体系， mapreduce， rdd， 各种不同的算子操作， 各种job， action。 一点一点理清脉络之后才终于对分布式编程有了一点点感觉。 奈何还是基础不够， 在遇到问题的时候大多数时间还是小刘帮我解决的。 真的幸好有小刘在， 不然我的实习之路真的会走的很艰难。 在上手之后就会觉得其实过得还是挺自在， 写代码也开始得心应手了起来。 可能大部分时间我也都在自己学习划划水， 但总算我也能有自己的一点价值了。 但是在实习的过程中还是会有难受的时候， 由于百度金融刚刚拆分， 很多业务以及技术支持都再重组阶段， 所以我们工作的需求都是一天一个样。 刚刚背井离乡来北京实习的我总是心比天高， 想要学到很多东西， 吸取大量养分； 可是我们小组可能很难满足我， 这也是我之后没有留下的原因之一吧。

但其实实习中遇到的小伙伴真的是很nice的。 可爱的曼曼， 刚来的时候就我们俩妹纸， 也一直相依为命的走过了三个月； 同为实习生的千鹤，平台各方面都帮了我很多； 务实的昊哥， 24k纯技术宅男， 在技术上教会了我很多； 还有我的mentor正文， 虽然后期没有与我有过多交流， 但还是感谢经常的会给我提供帮助。 还有其他小伙伴， 我们在一起度过了3个月， 没有多么轰轰烈烈同甘共苦的时刻， 但总是相识相交一场， 想起来心里总是泛起温暖。

实习尾声

实习结束前3天小刘就来北京找我了。 实习期间虽然大体上没有太大的波折和困难， 但每次到晚上和小刘语音视频的时候， 总是空落落的。 尤其在刚去北京那会儿， 生活用品没买齐全， 同事全不认识， 总是觉得自己被忽略孤零零。 幸好吧小刘每天都会安慰我鼓励我度过了很难熬的时期。 真正到了要离职的时候其实对于百度的不舍也没有那么多， 反而想到可以不用小刘分开就觉得很幸福。 在北京的日子， 给小刘改简历， 聊未来我们要投递的公司， 聊对未来的各种畅想。 除此之外我还带着他吃好吃的， 去颐和园， 去百度大厦， 去那些曾经我告诉过他的我一个人走过的地方。 小刘真的很温柔又美好， 在北京的那几天就想着呀， 以后毕业了能每天都这样的话， 多好。

真好啊， 来的时候只有我一个人， 走的时候有小刘陪着我了。 当时有着百度实习经历的我信心满满的剑指蚂蚁金服， 没有实习（并不）的小刘还在担心能不能拿到网易。 现在想想还真有点讽刺呀， 我们都不知道未来等着我们的是什么。

最近开始研究对视频进行行为识别，了解到目前state-of-art的方法都是基于iDT(improved dense trajectories)[1]的。基本思路分两种，一种是手动提取特征（Handcraft feature）然后对特征进行编码，然后分类的过程，还有一种是利用卷积神经网络提取特征，这里的网络一般分为以单个的视频帧表象的形式存在的空域网络，以及包含连续视频帧的堆叠光流位移场来描述视频帧之间的运动的时域网络， 但这种基于深度特征的方法在加入了iDT之后效果也能得到明显提升[2]。 这里我先研究手动提取iDT特征后进行Fisher vector编码的过程，并把Fisher Vector 与 BoV(Bag of Visual words)进行特征编码的过程进行了对比。

BoV

BOV解决的是提取SIFT特征之后，特征数据量太多而无法快速计算相似度的问题。如果是用聚类算法对这些SIFT特征矢量数据进行聚类，然后用聚类中的一个簇代表BOV中的一个视觉词，将同一幅图像的SIFT矢量映射到视觉词序列生成码本，这样每一幅图像只用一个码本矢量来描述，这样计算相似度时效率就大大提高了。

具体来说BoV特征编码主要是下面的步骤：

1. 对训练集中的M副图像进行预处理并提取SIFT特征，假设一共提取N个特征。
2. 用K-means对提取的N个SIFT特征进行聚类， K个聚类的中心词被选为视觉词。
3. 计算每一幅图像的每一个SIFT特征到这K个视觉词的距离，并将其映射到距离最近的视觉词中（即将该视觉词的对应词频+1）。
4. 3里得到每幅图像与视觉词序列相对应的词频矢量之后，对词频向量进行l1归一化。

Fisher Vector

Fisher Vector（FV）是一种类似于BOV词袋模型的一种编码方式, FV采用混合高斯模型（GMM）构建码本，但是FV不只是存储视觉词典的在一幅图像中出现的频率，并且FV还统计视觉词典与局部特征（如SIFT）的差异。Fisher Vector本质上是用似然函数的梯度vector来表达一幅图像，这个梯度向量的物理意义就是表达了参数往哪个方向修正才能最佳拟合数据。

FV的步骤如下:

1. 首先从图片上提取出特征描述子（如SIFT特征），假设每个描述子是D维的。
2. 令这些特征描述子符合K个高斯分布的线性组合（即混合高斯分布），并训练出GMM参数,系数$w_i$,均值$\mu_i^d$以及方差$\sigma_i^d$。
3. 求出该图片（用其特征描述子表示）在某GMM下的概率函数 $p(\mathbf{X}|\lambda)=\prod_{t=1}^{T}p(x_t|\lambda)$,并可以写出其似然函数
   $\mathcal{L}(\mathbf{X}|\lambda)=\sum_{t=1}^{T}p(x_t|\lambda)$。
4. 用似然函数的梯度vector来表达这幅图像，即$\frac{\partial\mathcal{L}(\mathbf{X}|\lambda)}{\partial w_i}$， $\frac{\partial\mathcal{L}(\mathbf{X}|\lambda)}{\partial \mu_i^d}$ 及 $\frac{\partial\mathcal{L}(\mathbf{X}|\lambda)}{\partial \sigma_i^d}$。这样就把长度不一的图片特征向量转化为长度相等了。
5. 最后一步通过计算fisher matrix的对角线期望[3]来进行特征向量的归一化,归一化的向量也被称为Fisher kernel，可以用来计算两个点在某个空间内的距离，可直接用于SVM分类中。

FisherVector相对于BOV的优势在于，BOV得到的是一个及其稀疏的向量，由于BOV只关注了关键词的数量信息，这是一个0阶的统计信息；FisherVector并不稀疏，同时，除了0阶信息，Fisher Vector还包含了1阶(期望)信息、2阶(方差信息)，因此FisherVector可以更加充分地表示一幅图片。

参考文献

1. Wang H, Schmid C. Action Recognition with Improved Trajectories[C]// IEEE International Conference on Computer Vision. IEEE, 2014:3551-3558.
2. Wang L, Qiao Y, Tang X. Action recognition with trajectory-pooled deep-convolutional descriptors[J]. 2015:4305-4314.
3. 【CV知识学习】Fisher Vector

上周被老师派去了上海交大进行了为期一周的summer school，学习的主题是“算法谱图论”。 由于去之前也没有提前准备图论的知识，上课的过程显得有些被动。万幸是研一还是认真上过矩阵论，也接触过了一些算法，所以勉强能够跟上整个课程的节奏：基本概念还是知道了个大概，但是证明的细节我也确实没有去深究了。这里把我一周学习的内容做一个小结。

算法谱图论是什么

wiki给出的解释是：“In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. ” 孙老师给我们讲的是，算法谱图论旨在用代数与几何的方法来表示“图”这个数据结构并探究图的内在特征。具体来说算法谱图论需要一些关于矩阵的基础，包括特征值，特征向量，矩阵多项式等；除此之外对解析几何也有一定要求，解析几何部分的内容可以将算法直观化。

算法谱图论的基本内容

从7月25日到7月29日，我们每天上午下午各上两个小时课,一共就是上了十节课，学习的内容的涉及面也比较广。总结下可能主要涉及到相关概念，谱性质与谱聚类和谱稀疏这三个大块来讲的。

相关概念

$G = (V,E)$表示一个有$n$个顶点和$m$条边的无向图。 $u$顶点的邻居节点集合用$N(u)$表示，它的度（degree）为 $d_u=|N(u)|$.对于集合$S\subseteq V$,用$vol(S) = \sum_{u \in S}d_u$,特别的，$vol(G) = \sum_{u \in V[G]} d_u$. 令$D \in \mathbb{R}^{n \times n}$为一个对角矩阵，其中的每一个对角元素$D_{u,u} = d_u$。图G的邻接矩阵A定义为:如果点u与点v相连则$A{u,v} = 1$，否则$A{u,v}=0$`。而G的拉普拉斯矩阵表示为$L= D - A$，$A$为G的邻接矩阵。正则化的拉普拉斯矩阵表示为$\mathcal{L} = D^{-\frac{1}{2}}LD^{-\frac{1}{2}} = I - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$。

图中的随机游走表现为一系列的点$v_0,v_1...,v_l...,v_n$. $v_0$已经固定而每一个$v_i$均匀的从$v_{i-1}$的邻居节点中选取。图上的随机游走是马尔科夫链一个特殊的例子，图上的随机游走有时间对称性和可逆性，这意味着从一个方向上或是另一个方向上穿过给定路径的概率之间有关系。

谱性质

cheeger常数与cheeger不等式

一个d-regular图中某个节点集$S \subseteq V$,令$h_G(S)= \frac{|\partial S|}{|S|}$,其中$\partial S= { (x,y) \in E(G): x \in S, y \in V(G)\S } $。cheeger常数定义为$h(G) = \min_S h_G(S)$。从概率的角度看，这正是随机选取一个节点集$S$中顶点的边，那么边的‘扩展’到节点集$S$外的概率。使用拉普拉斯矩阵的第二小特征值$\lambda_2$可以将图的cheeger常数进行限定，具体说来可表示为cheeger不等式:

Cheeger常数为正当且仅当G是完全图(connected graph),cheeger常数是值很小的正数表明该图存在一个”瓶颈”。考虑一个环形网络入图2所示,这个环的节点顺时针编号为1,2,3…顶点集和边的集合可以表示为：

令$S$为这个连环链路中的$ \left \lfloor \frac{N}{2} \right \rfloor$个点，即：

当N趋近于$\infty$时，$\frac{|\partial S|}{|S|}$趋近于0。事实上，小的Cheeger常数就表示整个图会因为某一个点而影响整个性能。这个环形网络如果有一个节点崩掉了，那整个网络都不能互相通信了，这是我们不愿意发生的。

谱扩展

扩展图(expand graph)是一系列有高可扩展性的稀疏图。由于稀疏性意味着更少的建造成本，高的可扩展性意味着高的连通性，所以扩展图的技术最开始被应用到低成本通信网络的构造。
构造扩展图的基本思想就是利用两个图之间顶点，边和度的关系来让新的图尽可能拥有原始图的特征。孙老师上课的时候提到了两种构造图的方法：置换积（Replacement Product）和之子积（Zig-Zag Product）.对于有$N$个定点，$M$条边，$D$度的大图$G$和$n$个定点，$m$条边，$d$度的小图$H$，用置换积构造的图会有$N \times n$个定点，$ M \times m $条边，$D$度；而用之子积构造的图会有$N \times D$个定点，$d^2$度，$M-1$条边。总体来说，置换积的度仅取决于小图的度，它可以用来在不丢失图的连通性的条件下减小图的度，而之子积继承了大图的大小，继承了小图的度，而扩展性则综合了大图和小图的特性，所以之子积可以用来建立具有有界度和良好扩张性质的大图。

谱聚类和谱稀疏

谱聚类和谱稀疏是孙老师最后讲的两个部分，这两块在很多方面都有应用，而且也是现在的研究热点。

一个网络中聚类之间的连通率（conductance）往往可以评判网络之间的通信性能。（原句是Clusters of low conductance in networks appearing in practice usually capture the notation of community），寻找聚类的算法也经常被应用到通信检测和网络分析等方面。K聚类问题就是把一个图分为K部分，每一部分的cheeger 常数（conductance）都很小。谱聚类算法利用了图的割(cut)与图正则化拉普拉斯矩阵的特征向量的关系，即结构定理(The Structure Theorem )。

稀疏图(sparse graph)表示边的数量和点的数量几乎成正比的图。由于大部分算法在稀疏图上运行的时间更少，同时稀疏图也更节省存储空间，所以将一个图G转换为特征相似的稀疏图H是有必要的。 Spielman-Srivastava算法可以通过特定概率来采样原图的边，从而得到稀疏图，但这种方式计算复杂度相对较大。除此之外，孙老师所在的组最近也提出了线性时间的谱稀疏算法。

算法谱图论的应用

总的来说，算法谱图论其实就是就是研究图上的一些代数或是几何特性，所以只要某个object可以用graph来表示出来，那么就可以用算法谱图论的一些算法来解决问题。具体来说可能有下面几个方面：

• 图像分割(Image segementation)，用cheeger常数可以算出图的最小割，从而得到相应的分割线，但是这个分割可能并不理想。
• PageRank 通过将网络中网页之前互联的关系表示成邻接矩阵，可以用矩阵的特征来获得链接的排序。
• 网络通信 前面提到的扩展图与图的分割，涉及到建造优性能网络的问题。
• 社交网络 通过将人与人之间的互联关系建模，对用户进行基于某种特性的分类。(graph clusting)
• 数据集合并 用谱扩展(Construction of Expander Graphs)的方法可以在较短时间内将来源不同的数据集合成新的数据集。

学习体会

这次学习的最大体会就是，千万不要高估了自己，有好多比你聪明得多的人比你还要努力。在上交的室友是个大四的妹子，可是去年就已经发了一篇A类的论文还是best paper award，才大四已经在准备托福要研究生毕业出国了。还有上课时坐在前面的一群复旦的妹子，长得好看不说，一下课就在讨论上课的内容，关键是讨论的东西我还不怎么能听得懂（T.T），有一种我的大学四年是不是白学了的感觉~ 诚然，数学功底和英语功底在做研究这个方面至关重要，但是最重要的还是与优秀的人交流。如果只是呆在华科，与实验室的学长比，或是跟选同一门课的同学比（没错我说的就是软件无线电课），可能我是会有一些优越感。呆在一个自我感觉良好的地方未必是好事，久而久之毕竟会消磨你的斗志和上进心。在下半年再给自己立一个flag，在自己的研究方向阅读大量文献并思考提出问题，与文章作者进行email交流并有所收获。嗯，愿自己变得更优秀。

暑假到了，狠下决心开始啃之前一直可望而不可即的大部头《PRML》。这本PRML主要从贝叶斯的角度将机器学习的众多知识点串联在一起，优点在于知识比较系统，由浅入深循序渐进，但是很多细节推导的步骤不严谨，对于微积分，概率论和矩阵论知识不够扎实的我也忽略了很多公式部分（=。=）。本打算是一口气看完再来写读后感，但还是觉得这本书内容很多也比较复杂，不及时总结巩固可能就忘记了。所以大概花了20天断断续续的看完了前四章，准备小结一下然后把课后习题都做完。前四章是对后面具体理论方法的支撑，阐述了贝叶斯理论并用贝叶斯的思想解释了线性回归器和分类器。第一章是概念性的介绍，举出的”多项式拟合”的例子也贯穿了后面几章。第二章讲的是概率分布，提到了二项分布，多项分布，高斯分布以及可以把前面几种都统一起来的指数族分布，第三章和第四章分别讲了线性回归模型和线性分类模型。

从“概率”说起

PRML的第二章是概率分布。这一章的知识几乎应用后面每一章中，极其重要。主要包括二项分布，多项分布，高斯分布，以及一统这几个分布的指数族分布。二项分布和多项分布对应于后面章节的二分类和多分类问题。由于对于一个实值向量，使熵取得最大值的分部是高斯分布，而一组随机变量之和的概率分布随着和式中项的数量的增加而逐渐趋向高斯分布(中心极限定理)，因此高斯分布除了应用在最直观的回归问题上，也坐稳了几乎各个问题的核心部分。除此之外，二项分布和多项分布就是给定某一类时出现观测集的概率，高斯分布则是真实数据为条件，出现了观测数据（观测数据有噪声）的概率。

如果只关注现有采集数据的分析属于频率学家的观点，这样的观点在贝叶斯学派们看来简直是有因噎废食的嫌疑：如果只抛1次硬币，恰好是正面，就说硬币做手脚了岂不是贻笑大方（过拟合问题）？频率学家说只要你的观测的数据集足够大，这种过拟合的问题就可以被避免。但是，世界上有很多数据是无法大量获取的，也是无法做大量实验得到的。贝叶斯学派认为已有的知识是可以拿来使用的，这样就能解决数据量的问题。 书中分别引入了三种分布各自的先验分布，如二项分布对应的先验分布为beta分布，多项分布对应的先验分布为direclet分布，高斯分布为多参数模型比较复杂，它根据不同的假设得到的先验分布有高斯分布，gamma分布以及多维下的Gaussian-wishart分布。这些分布的后验分布与先验分布形式完全一样，只是参数有所不同。在后面很多章解决的具体问题中，都是几乎使用这两种观点下的概率分布建立概率模型。

当然贝叶斯学派的先验分布被频率学派广为诟病的是：贝叶斯学派引入的先验分布并不是真正的经验知识，甚至为了数学上的方便，强行给了形式化的先验分布。这样的先验分布没有任何价值，反而污染了现有的观测数据。于是大家为了解决这个问题又不想带来过拟合问题，开始探索无先验信息分布。

线性回归模型

建立线性模型之后，注意线性模型是将样本的自变量在新的映射空间的值，即初始变量的基函数输出做线性组合得到输出值。输出值本质上和样本的因变量target值其实是没有关系的。引入了t=f(y)关系，在回归问题上，我们习惯使用了示性函数t=f(y)将空间输出值与样本的target的值认为是相同的，这样在预测的时候，将待预测的输入变量输入到线性模型中得到的值就可以认为是预测的输出变量。更重要的是，这种示性函数会保持整个模型的线性性质，会带来极大方便。接下来假设观测值存在随机噪声，认为服从高斯分布，建立起似然函数，最大化似然函数得到模型参数（ML）。最大化似然函数会带来过拟合问题，引入先验分布，得到最大后验分布（MAP）。而最大后验分布中又有一些超参数无法很好的确定，所以又引入贝叶斯回归。这里由于都是线性函数，高斯分布的性质反复使用，就可以得到解析解。先验分布引入的时候又会引入超参，超参的选取又引来争议，于是对超参的求解带来了证据近似的迭代方法。

最大似然法（ML）

假设目标变量t由确定的函数y(x,w)给出，这个函数被附加了高斯噪声，即

其中$\epsilon$是一个零均值的高斯随机变量，精度（方差的倒数）为$\beta$,因此:

如果假设一个平方损失函数，那么对于$x$的一个新值，最优的预测由目标变量的条件均值给出。在公式(1)给出的高斯条件分布下，条件均值为：

考虑一个输入数据集$X={x_1, …,x_N}$,对应的目标值为$\mathbf{t}={t_1,…t_N}$。假设这些数据点是独立从分布(1)中抽取的，那么可以得到下面的似然函数表达式：

其中$y(\mathbf{x},\mathbf{w}) = \sum_{j=0}^{M-1}w_j\Phi_j(x) =\mathbf{w}^T\mathbf{\Phi(x)} $
取似然函数的对数，我们有:

平方和误差函数的定义为：

写出似然函数之后，可以用最大似然的方法确定$w$与$\beta$。对于$w$的最大值，在条件高斯噪声分布的情况下，线性模型的似然函数最大化等价于平方和误差函数的最小化。 上述似然函数的梯度为：

令这个梯度为0，可得:

这被称为最小平方问题的规范方程(normal equation)。这里$\mathbf{\Phi}$是一个$N \times M$的矩阵，它的元素$\mathbf{\Phi}_{nj} = \Phi_j(x_n)$。

关于噪声精度参数$\beta$最大化似然函数，结果为：

因此噪声精度的倒数由目标值在回归函数周围的残留方差给出。

最大后验(MAP)

对于最大似然法，数据规模不够时很容易出现过拟合，由贝叶斯定理:

我们引入多项式系数$w$上的先验分布，我们下面的高斯分布：

其中$\alpha$是分布的精度，M+1是对于M阶多项式的向量$\mathbf{w}$的总数。假定$\mathbf{w}$服从这个先验分布后，可以通过寻找最可能$\mathbf{w}$的值来确定后验分布。最大化后验概率就是最小化下式：

其实质就是为误差函数添加了正则化项来控制过拟合。令$\lambda = \frac{\alpha}{\beta}$,其中$\lambda$称为正则化系数。令误差函数关于$\mathbf{w}$的梯度等于零，我们得到：$\mathbf{w}_{MAP} = (\lambda\mathbf{I} + \mathbf{\Phi}^T\mathbf{\Phi})^{-1}\mathbf{\Phi}^T\mathbf{t}$。

如果假设$\mathbf{w}$的先验概率服从高斯分布，则相当于加了一个L2 正则项；如果假设$\mathbf{w}$服从拉普拉斯分布，则相当于加了一个L1正则项。L1正则化会导致参数值变为0，但是L2却只会使得参数值减小。在机器学习中也将L2正则称为weight decay。

贝叶斯线性回归

利用上面提到的极大似然法来训练模型时，如果数据集的规模是有限的，会导致严重的过拟合问题。如果通过限制基函数的数量来避免过拟合，就会限制模型描述数据中有趣且重要规律的灵活性。虽然引入正则化可以控制具有各参数的模型过拟合问题，但是$\lambda$的值是不好确定的。过拟合现象是最大似然方法一个不好的性质，但是当我们在使用贝叶斯方法对参数进行求和或者积分时，过拟合现象不会出现。贝叶斯与最大似然估计，最大后验估计不同之处在于它得到的是测试数据在整个空间上的一个概率分布，而不单纯是一个点估计。它的精髓就在于这个加权积分：考虑到了参数的所有情况，并且加以不同的权重（后验分布的值），自然就避免了过拟合。此外，很多情况下比起单纯的点估计，我们更需要一个分布来获得更多的信息。

先引入模型参数w的先验概率分布。现在这个阶段，我们把噪声精度参数$\beta$当做已知常数。由于似然函数是$p(t|w)$是$w$的二次指数形式，于是对应的先验分布为高斯分布，均值为$\mathbf{0}$,协方差为$\alpha^{-1}I$,假定先验分布为：

由于共轭高斯先验分布的选择，后验分布也将是高斯分布。

由高斯边缘分布与条件分布的关系可得：

后验概率分布的对数由对数似然函数与先验的对数求和的方式得到。它是w的函数，形式为:

我们可以看到，这个式子与MAP的后验概率分布一样，但是在MAP方法中需要对$\mathbf{w}$求导得出使后验概率最大的$\mathbf{w}$的值，而在贝叶斯线性回归中，则不是得到一个确定的$\mathbf{w}$的值，而是计算$\mathbf{w}$的分布。

我们用得到的$\mathbf{w}$的分布来预测$t$的值，即计算出预测分布(predictive distribution):

其中$\mathbf{t}$是训练数据的目标变量组成的向量。目标变量的条件概率分布$p(t|\mathbf{w},\beta)$由公式（1）给出，后验分布由(2)给出。预测函数涉及到两个高斯函数的卷积，所以预测分布的形式可以写为:

其中预测分布的方差$\sigma_N^2(\mathbf{x})$为：

公式(2.3.8)第一项表示数据中的噪声，第二项反映了参数$w$关联的不确定性。 当额外的数据点被观
测到的时候，后验概率分布会变窄，公式(3)第二项在N趋近于无穷大时会趋近于0。

在实际中，除了少数情况（比如先验和似然函数都是高斯分布），预测分布的形式一般都很复杂，公式(2.3.6)的积分是积不出来的。这时候就要采取一些近似方法，近似方法又分为两大类：简化复杂的预测分布，然后就能算出积分的解析形式了。具体方法有变分推断，Laplace近似等。这类方法的特点是人算起来困难，机器跑起来快。用采样的方法搞定后验分布。具体方法有Gibbs采样，MCMC采样等。人算起来简单，但是机器跑起来慢。采样方法还有一个好处，就是精度非常高。

线性分类模型

同样是线性模型，但是在分类问题上，模型的输出值是连续的，因为基函数连续，且是线性组合，模型输出值仍是连续的，而分类问题样本的target值是离散的。于是这之间就不能使用示性函数了。强行仍使用空间输出值就是最小平方法和Fisher线性判别函数法（后者是前者的一个特例），设置阈值进行二值离散化（+1， -1）感知机算法。生成式概率模型和判别式模型采用的是logistics 回归函数。强行使用原来的空间输出值带来的问题就是，分类问题原本只关心对错（正反例），这里变成了五十步笑百步的问题，对离群点缺乏robust。设置二值离散化问题是缺乏连续性（指的是误差函数不能始终朝着好的方向进行）。而logistics回归函数连续性较好，本质上也是二项分布和多项分布相关。但是除了最小平方法，其他方法都引入了非线性函数，导致整个大模型线性性质被破坏。无论是MLE和MAP，其结果都不是高斯分布，在判别式概率模型时进行优化的方法就变成了梯度下降法迭代求解，因为它没有解析解了。在预测分布时，后验分布已不再是高斯分布，为了使用高斯分布的性质，对其使用了laplace近似，将其近似成高斯分布，当然还有其他的近似了。

判别函数

判别函数是一个以向量x为输入，把它分配到K个类别中的某一个类别（记作$C_k$）的函数。线性判别函数最简单的形式是输入向量的线性函数，即:

其中$\mathbf{w}$被称为权向量(weight)，$w_0$被称为偏置(bias)。如果是二分类问题，对于一个输入向量$\mathbf{x}$，如果$y(\mathbf{x})\geq 0$,则它被分到$C_1$中，否则被分到$C_2$中。决策边界由$y(\mathbf{x})=0$确定。对于多分类问题，引入一个K类判别函数:

对于点$x$, 如果对于所有的$j\neq k$都有$y_k(\mathbf{x}) > y_j \mathbf{x}$就把他分到$C_k$。下面介绍三种学习线性判别函数参数的方法，分别是最小平方法，Fisher线性判别函数以及感知机算法。

最小平方法

将公式（4）写成向量形式:

其中$\tilde{\mathbf{W}}$是一个矩阵，第k列由D+1维向量$\tilde{wk} = (w{k0}, w_k^T)^T$组成，$\tilde{\mathbf{x}}$是对应的增广矩阵的输入向量$(1,x^T)^T$。一个新的输入x被分配到输出$y_k = \tilde{w_k^T}\tilde{x}$最大的类别中。

现在通过最小化平方和误差函数来确定参数矩阵$\tilde{\mathbf{W}}$,考虑训练数据集${\mathbf{x_n},\mathbf{t_n}}$,然后定义一个矩阵$\mathbf{T}$,它的第n行是向量$\mathbf{t}_n^T$,还定义了矩阵$\tilde{\mathbf{X}}$，它的第n行是向量$\tilde{x}_n^T$,这样，平方函数可以表示为：

令上式关于$\tilde{\mathbf{W}}$的倒数为0，得到关于$\tilde{\mathbf{W}}$的解为$\tilde{\mathbf{W}}=(\tilde{\mathbf{X}}^T \tilde{\mathbf{X}})^{-1}\tilde{\mathbf{X}}\mathbf{T}$
根据$\tilde{\mathbf{W}}$这样我们可以得到判别函数。

最小平方法对于判别函数的参数给出了精确的解析解，单即使作为一个判别函数，他仍然有很严重的问题。最小平方解对于离群点缺少鲁棒性，除此之外，在多分类问题上，即使是线性可分的数据集用最小平方判别函数也不能得到很好的结果。如下图3.1，左边是最小平方法对应的分类结果，右边是逻辑回归对应的结果，可以看到最小平方法的决策边界非常差。

Fisher线性判别函数

这里只讨论二分类的Fisher线性判别函数。我们可以从维度降低的⾓度考察线性分类模型。考虑二分类的情形。假设我们有一个D维入向量x，然后使用下式投影到一维:

如果我们在$y$上设置一个阈值，然后把$y\geq -w_0$的样本分为$C_1$类，把其余样本分为$C_2$类，就得到了标准的线性分类器。通常来说，向一维投影会造成相当多的信息丢
失，因此在原始的D维空间能够完美地分离开的样本可能在⼀维空间中会相互重叠。但是，通过调整权向量w，我们可以选择让类别之间分开最大的一个投影。
考虑一个二分类问题，其中$C_1$类中有$N_1$个点，$C_2$类中有$N_2$个点，两类的均值向量为:

其中$m_k = \mathbf{w}^T\mathbf{m}_k$

最简单的度量类别之间分开程度的⽅式就是类别均值投影之后的距离,这种思想可能会带来两个问题，增大$w$可以使表达式无限大，类间可能会存在较大重叠。为了解决第一个问题，我们规定$\sum_i w_i^2=1$;针对第二个问题，Fisher提出一种思想是，最大化一个函数，这个函数能够让类均值的投影分开得较大，同时让每个类别内部的⽅差较小，从而最小化了类别的重叠。其中类内方差定义为:

其中$y_n = \mathbf{w}^T\mathbf{x}_n$。Fisher准则根据类间方差和类内方差的比值来定义，误差函数为:$J(\mathbf{w}) = \frac{(m_2- m_1)^2}{s_1^2 + s_2^2}$
可以将上式重写为:

其中$S_B$是类间(between-class)协方差矩阵，形式为:

$S_W$是类内（within-class）协方差矩阵，形式为:

对$J(w)$求导得，$J(w)$取得最大值的条件是:

由于我们不关心$w$的值只关心$w$的方向,我们有:

如果选择了一个阈值$y_0$，是的$y(\mathbf{x}) \geq y_0$时把数据点分到$C_1$,否则把数据点分到$C_2$。可以使用高斯概率分布对类条件概率密度$p(y|C_k)$建模，然后使用最大似然方法找到高斯分布的参数值。

感知机算法

感知器算法对应于一个二分类模型，这份模型中输入$x$首先使用一个固定的非线性变换得到一个特征向量$\Phi(x)$，这个特征向量被用于构造一个一般的线性模型，形式为:

其中非线性激活函数f(\cdot)是一个阶梯函数，形式为:

在感知器算法中，更方便的用$t = +1$表示$C_1$,用$t = -1$表示$C_2$。
如果使用误分类模式的总数作为误差函数来确定参数$w$会带来很多问题，因为误差函数会称为$w$的分段常函数，从而当当决策边界移过某个数据点时，这个函数不连续变化。因此我们考虑另外一个误差函数，被称为感知器准则：

其中$\Phi_n = \Phi(x_n)$和$M$表示所有误分类模式的集合。某个特定的误分类模式对于误差函数的贡献
是$w$空间中模式被误分类的区域中w的线性函数，而在正确分类的区域，误差函数等于零。总的误差函数因此是分段线性的。

对这个误差函数使用随机梯度下降算法。这样权向量的变化为:

其中$\eta$是学习率参数，$\tau$表示运行次数。

生成模型

对于每个类别$C_k$,独立地确定类条件密度$p(x|C_k)$。这是一个推断问题。然后，推断先验概率$p(C_k)$。之后利用贝叶斯定理:

求出后验概率$p(C_k|x)$。
如果我们具体化了类条件概率$p(x|C_k)$参数化的函数形式，就能使用最大似然法确定参数的值以及先验类概率。这里先对二分类的情况进行建模，假设每个类别都有一个高斯类条件概率密度，且协方差矩阵相同。我们假设有一个数据集{x_n, t_n },其中$n = 1,…,N$，这里用$t_n$= 0或者1来表示分类结果为$C_1$或$C_2$。把先验概率记作$p(C_1)=\pi$,从而$p(C_2) = 1 -\pi$，对于一个来自类别$C_1$的数据点$x_n$,有：

对于类别$C_2$:

所以似然函数为:

其中$\mathbf{t}=(t_1,…,t_N)^T$
取似然函数的对数，令其关于$\pi$的导数为0,可得:

$\pi$的最大似然估计就是类别C1的点所占的比例, 与两类的情况相同，在多类的情形中，类别$C_K$的先验概率估计为这个类别的数据点数量占训练集总数据的比例。
令似然函数对数关于$\mu_1$的导数为0，整理可得:

对应的$\mu_2$的结果为:

可以发现$\mu_1$和$\mu_2$分别是属于类别$C_1$和$C_2$输入向量$x_n$的均值。

最后考虑协方差矩阵$\sum$的最大似然解，选出似然函数中与$\sum$相关的项，令其关于$\sum$的导数为0，可以得到$\sum = S$,其中:

它表⽰对一个与两类都有关系的协方差矩阵求加权平均。

判别模型

除了生成模型之外，另一种方法是显示的使用一般的线性模型的函数形式，然后使用最大似然法直接确定他的参数。判别式方法的.个优点是通常有更少的可调节参数需要确定，并且预测表现也会提升，尤其是当类条件概率密度的假设没有很好地近似真实的分布的时候。
在一些一般的假设条件下，类别$C_1$的后验概率可以写成作用在特征向量$\Phi$的线性函数上的logistic sigmoid函数的形式，即：$p(C_1|\Phi) = y(\Phi) = \sigma(w^T\Phi)$且$p(C_2|\Phi) = 1-p(C_1|\Phi)$，这里$\sigma(\cdot)$是logistic sigmoid 函数。这个模型称为logistic回归，是一个分类模型而不是回归模型。
与上一节提到的用最大似然法调节高斯类条件概率密度的方法，逻辑回归需要的参数明显更少，这是它的优势之一。利用最大似然方法来确定logistic回归模型的参数。很容易推导出:

对于一个数据集 ${\Phi_n, t_n}$ ,其中$t\subset{0,1},\Phi_n = \Phi(x_n)$且$n = 1,...,N$,似然函数可以写为:

参考文献

1. PRML阅读笔记
2. 【机器学习算法系列之二】浅析Logistic Regression
3. 如何通俗地解释贝叶斯线性回归的基本原理？- 李文哲的回答
4. 贝叶斯思想以及与最大似然估计、最大后验估计的区别 - 江湖小妞 - 博客园
5. 生成模型与判别模型 - zouxy09的专栏

cs231n的第二次作业因为各种课以及考试中断了很久，在一切结束后接上来总是有种力不从心的感觉。assignment 2 涉及到的知识点太多了，神经网络中的各种tricks，sgd加速，batch normalization，drop out等。神经网络以及卷积神经网络各层的前向传播以及后向传播。涉及到传播的可能需要复杂的公式推导以及扎实的python编程基础，所以做起来还是很头疼，但是前面的各种tricks也是让我涨姿势了~ 这里就把最优化的一些知识点小结一下。

梯度下降法

梯度下降法先随机给出参数的一组值，然后更新参数，使每次更新后的结构都能够让损失函数变小，最终达到最小。在梯度下降法中，目标函数其实可以看做是参数的函数，因为给出了样本输入和输出值后，目标函数就只剩下参数部分了，这时可以把参数看做是自变量，则目标函数变成参数的函数。

SGD

批量梯度下降法在更新每一个参数时，都需要所有的训练样本，所以训练过程会随着样本数量的加大而变得异常的缓慢，所以提出了随机梯度下降（SGD）算法。SGD就是每一次迭代计算mini-batch的梯度，然后对参数进行更新。

其中 $\eta$是学习率，$g_t$是梯度

随机梯度下降与传统的梯度下降相比，随机梯度下降法收敛速度速度更快，但是也更容易收敛到局部最优点。除此之外学习率的设置也会极大的影响最终结果。

Momentum

momentum是模拟物理里动量的概念，积累之前的动量来替代真正的梯度。公式如下：

其中$\mu$是动量因子，作用是通过历史搜索方向的积累，消除相继搜索方向中相反的方向，而一致的方向则相互累加。
与普通的SGD相比，下降初期由于使用上一次参数更新，下降方向一致，乘上较大的$\mu$能够进行很好的加速;而下降中后期时，在局部最小值来回震荡的时候，$gradient\to0$，$\mu$使得更新幅度增大，跳出陷阱。总而言之，momentum项能够在相关方向加速SGD，抑制振荡，从而加快收敛。

Nesterov

将momentum方法的公式展开得：

可以看出，$m_{t-1}$并没有直接改变当前梯度$g_t$，所以Nesterov的改进就是让之前的动量直接影响当前的动量。即：

所以，加上nesterov项后，梯度在大的跳跃后，进行计算对当前梯度进行校正。momentum方法在红色圆圈点通过得到的动量和梯度放下来得到梯度下降的step，而Nesterov则是在预估出actual step之后再对梯度的方向进行计算和校正。（图片引自cs231n Lecture Notes）

momentum项和nesterov项都是为了使梯度更新更加灵活，对不同情况有针对性。但是这两种方法和SGD一样都需要人工设置学习率，接下来的几种方法可以自适应学习率。

Adagrad

adagrad其实是对学习率进行了一个约束：

此处，对gt从1到t进行一个递推形成一个约束项regularizer，$-\frac{1}{\sqrt{\sum{r=1}^t(g_r)^2+\epsilon}}$，$\epsilon$用来保证分母非0。

前期当$g_t$较小时，regularizer较大，能放大梯度，而后期$g_t$较大，能约束梯度。Adagrad方法仍需设置一个全局学习率，而$\eta$设置过大也会使regularize过于敏感，对梯度调节太大。

RMSprop

为了解决Adagrad方法后期学习率消失的问题。与Adadelta中计算所有梯度的均方和不同的是，Rprop将之前所有$g_t$的期望和与当前的$g_t$作了一个加权平均：

RMSprop的学习率按照梯度的均方和呈指数衰减。Hinton提出$\gamma$设为0.9，$\eta$设为0.001s此算法效果较好。

Adam

Adam(Adaptive Moment Estimation)本质上是带有动量项的RMSprop，它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。公式如下：

其中，$m_t$，$n_t$分别是对梯度的一阶矩估计和二阶矩估计，可以看作对期望$E|g_t|$，$E|g_t^2|$的估计；$\hat{m_t}$，$\hat{n_t}$是对$m_t$，$n_t$的校正，这样可以近似为对期望的无偏估计。 可以看出，直接对梯度的矩估计对内存没有额外的要求，而且可以根据梯度进行动态调整，而$-\frac{\hat{m_t}}{\sqrt{\hat{n_t}}+\epsilon}$对学习率形成一个动态约束，而且有明确的范围。

Adam方法结合了Adagrad善于处理稀疏梯度和RMSprop善于处理非平稳目标的优点，为不同的参数计算不同的自适应学习率。

Batch Normalization

前面提到梯度下降中为了加速收敛，以及避免陷入局部最优一些方法。 在参考文献[3]中提出了Batch Normalization， 它解决了反向传播过程中的梯度问题（梯度消失和爆炸），同时使得不同scale的 权重$w$ 整体更新步调更一致，从而克服深度神经网络难以训练的弊病。

统计机器学习中的一个经典假设是“源空间（source domain）和目标空间（target domain）的数据分布（distribution）是一致的”。因此我们需要对输入数据进行归一化的处理。但是不同的网络层具有不同的特点，如果简单的将每一层都归一化就会失去不同卷积层的区分性。于是[3]中提出了变换重构，引入了参数$\gamma$,$\beta$:

引入这两个参数之后可以使网络学习会服从原始网络的特征分布。（图片引自[3]）

训练过程如：

具体说来，在神经网络训练时遇到收敛速度很慢，或梯度爆炸等无法训练的状况时可以尝试BN来解决。另外，在一般使用情况下也可以加入BN来加快训练速度，提高模型精度。

牛顿法与拟牛顿法

除了梯度下降法，牛顿法也是机器学习中用的比较多的一种优化算法。牛顿法的基本思想是利用迭代点处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小值。牛顿法的速度相当快，而且能高度逼近最优值。

牛顿法

牛顿法主要有两个应用方向，目标函数最优化求解以及方程的求根，这两个应用方面都主要是针对f(x)为非线性函数的情况。在机器学习最优化的领域中用到的是前一种。牛顿法的核心思想是对函数进行泰勒展开。

对f(x)进行二阶泰勒公式展开：

此时，将非线性优化问题 min f(x) 近似为为二次函数的最优化求解问题：

对于上式的求解，即二次函数（抛物线函数）求最小值，对函数求导：

从本质上来讲，最优化求解问题的迭代形式都是： ${x_{k+1}}={x_k}-kf’(x_k)$，其中k为系数，$f’(x_k)$为函数的梯度（即函数值上升的方向），那么$-f’(x_k)$为下降的方向，最优化问题的标准形式是：求目标函数最小值，只要每次迭代沿着下降的方向迭代那么将逐渐达到最优，而牛顿将每次迭代的步长定为：$1/f’’({x_k})$。

如果这里的x是一个向量， $f’’({x_k})(x-{x_k})$应该写成：${(x-{x_k})^T}f’’(x_k)(x-{x_k})$，$f’’(x-x_k)$为Hessian矩阵。

拟牛顿法

牛顿法是二阶收敛，虽然收敛速度快但是由于计算过程中需要求解目标的二次偏导数，计算复杂度较大。而且有时目标函数的海森矩阵无法保持正定，从而使牛顿法失效。为了克服这两个问题，人们提出了”拟牛顿法”。这个方法的基本思想是：不用二阶偏导数而构造出可以近似海森矩阵（或海森矩阵逆）的正定矩阵，在“拟牛顿”的条件下优化目标函数，不同的构造方法就产生的不同的拟牛顿法。

在介绍几种拟牛顿算法之前，先引出“拟牛顿条件”。设经过$k+1$次迭代后得到$x{k+1}$，此时将目标函数$f(x)$在$x{k+1}$附近作泰勒展开，取二次近似得：

对上式两边同时作用一个梯度算子$\bigtriangledown$,可得：

取$x=x_k$并整理，可得:

令: $s_k = x_{k+1}- x_k, y_k = g_{k+1} - g_k$
则可得:$y_k \approx H_{k+1}\cdot s_k$或者$s_k\approx H_{k+1}^{-1} \cdot y_k$

DFP 算法

DFP是UI早的拟牛顿法，该算法的核心是:通过迭代的方法，对$H_{k+1}^{-1}$（记为$D_{k+1}$）做近似，迭代格式为：

其中$D_0$通常取为单位矩阵$I$,为了构造一个正定对称的$\Delta D$，将$\Delta D$待定为

其中
$\alpha = \frac{1}{s_k^Ty_k}$, $\beta=-\frac{1}{y_k^TD_ky_k}$
我们构造出的校正矩阵

BFGS 算法

与DFP算法相比，BFGS算法性能更佳，目前它已成为了求解无约束非线性优化问题最常用的方法之一。BFGS算法已有较完善的局部收敛理论。

BFGS算法中核心公式的推导过程与DFP完全类似，只是互换了$s_k$与$y_k$的位置。BFGS算法直接逼近海森矩阵，即$B_k \approx H_k$,设迭代格式为

其中的$B_0$也常取为单位矩阵$I$,将$\Delta B_k$待定为：

其中
$\alpha = \frac{1}{y_k^T}$, $\beta = -\frac{1}{s_k^T B_ks_k}$得到了如下校正矩阵

如果要用$\Delta D_k$来替换$\Delta B_k$，则上式可改为:

L-BFGS 算法

在BFGS算法中，需要用到一个$N \times N$的矩阵，当$N$很大时，计算机需要耗费很大资源。L-BFGS就是为了这个解决这个问题。 它对BFGS算法进行了近似，其基本思想是：不再存储完整的矩阵$D_k$，而是计算过程中的最新$m$个向量序列${s_i}$,${y_i}$,需要矩阵$D_k$时，利用向量序列{s_i}与{y_i}计算来代替。

具体来说,为了实现迭代式

记$\rho_k = \frac{1}{y_k^T}$, $V_k = I- \rho_ky_ks^T_k $，L-BFGS算法流程可描述如下[7]：

参考文献

1. 深度学习最全优化方法总结比较（SGD，Adagrad，Adadelta，Adam，Adamax，Nadam）
2. An overview of gradient descent optimization algorithms
3. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
4. 深度学习中 Batch Normalization为什么效果好？魏秀参的回答
5. Batch Normalization 学习笔记 - hjimce
6. 牛顿法与拟牛顿法学习笔记（一）牛顿法
7. Limited-memory BFGS - Wikipedia

最近开始上斯坦福大学cs231n的公开课。其实上学期已经过了一遍cs224d了，当时看的是无字幕的视频，感觉收获并不是特别大，可能是由于学习的时候断断续续很多实现的细节还是没有理解。这次学习cs231n就只是看了课程网站上的lecture note，跟着写了写作业。cs231n的内容涉及到机器学习中的多种算法以及 cnn/rnn等多种神经网络，之后的作业也还都比较有趣。现在写了第一周的作业，主要涉及到了几种分类算法，在这里小结一下。

knn算法

一般来说，knn作为无监督学习(unsupervised learning)可以作聚类，这里把knn作为监督学习(supervised learning)，将CIFAR-10 dataset中的图片作为训练集和测试集，将测试集中的每一张图片与训练集中的每一张比对，选出最相似的k张，这k个label中出现次数最多的就是测试集的判定分类结果。

L1与L2距离

为了计算两张图片之间的差距，把数据集中的32 32 3的原始图片延展成一个一维向量，共有32 32 3维特征。
对于测试集与训练集的距离计算，有两种方式，L1距离与L2距离。

L1距离：

L2距离：

基于L1距离的knn分类算法在CIFAR-10上的准确率可以达到38.6%，而基于L2距离的knn分类器准确率则为35.4%。对于L2距离而言，由于距离之间的差有平方，L2在距离差异较大时会产生更大的分歧。

knn分类的优缺点

• knn的优点在于，算法非常简单直观，不需要额外的训练时间。
• 缺点在于虽然缺少了训练过程，但是分类的测试时间非常长。且在每次做分类过程中都要与所有的训练数据比较，空间复杂度也很大。在图像分类中，由于维度特别高所以knn也使用不多。

线性分类器

为了解决knn算法中出现的时间和空间开销太大的问题，这里提出了线性分类器。线性分类器分为两个部分，首先是一个得分函数将输入的原始数据映射到每一个分类label的得分，第二部分是一个可以量化预测得分和真实分类的损失函数。

利用线性分类器进行分类的具体步骤如下：

• 首先进行数据的预处理，一般来说在机器学习中输入特征总是会被归一化（在图像的情况下，每个像素就是一个特征）。具体来说每个像素都要减去所有像素的平均值，之后再缩放这些特征，使得所有特征的取值范围都在[-1,1]。
• 在进行计算时，可以将x向量增加一维并全置1，相应的把对应的权重矩阵W也增加一维，这样原本的W，b两个参数就可以变为一个参数。
• 在通过得分函数计算出了每个变量分在每一个类的得分之后，得分最高的就应该是预测的分类结果。

上面提到的是测试分类的过程，训练的过程就是通过大量的训练数据集不断调整W与b，使得其能有最好的分类结果。而W和b的调整标准就在于loss function，loss function在预测结果与真实结果最为接近时值最小，通过最优化算法（梯度下降，牛顿法/拟牛顿法）通过每次迭代loss function的函数值来更新W,b的值，使得在训练结束之后得到的W和b能较好反映图像的特征。下面提到的SVM与Softmax实质上就是两个不同的loss function。

SVM loss

这里的SVM与cs229等其他机器学习中提到的复杂SVM算法有一定区别，它采用SVM核心的hinge loss，没有讨论svm中涉及到的kernel,dual以及SMO算法。 SVM loss 希望每个图像正确分类的得分比不正确分类的得分高得至少一个固定Δ。

具体来说，对于第i个例子，我们给出了图像的特征（即像素）与正确分类的标签。得分函数利用输入的像素计算的分类得分。第i个训练数据多分类SVM的损失可以表示为：

从下图也可以看出，svm的loss希望分类正确的得分比分类错误的得分至少高Δ，如果没有做到，那么损失将会累积。

这里的Δ的取值一般为1，其实Δ的变化可能就是使W与b成倍放大和缩小，而不会对分类结果有很大影响。

Softmax loss

softmax分类器是逻辑回归分类的一般情况。与SVM的loss相比，softmax将对分类得分有一个更直观的概率解释。得分函数不变，但是我们会用log概率处理这些得分并把svm中的hinge loss变为cross-entropy loss（交叉熵损失）：

Softmax函数的一般形式为, 它的输入为任意的实数向量，输出和输入相同维度向量，其中每一个数都在0与1之间且相加的和为1.从上式可以看出，当分类正确的得分越大，分类错误的得分越小，损失就越接近于0。这里借助了概率论中交叉熵的思想。

在实现softmax算法时，为了计算的稳定性，通常令输入的实数向量中每个值都减去该向量中的最大值，因为：

分析与比较

• Softmax loss function的输出可以看作是分类的概率，而SVM的输出结果没有含义，但是softmax得到的分类概率与正则化参数λ有关。（后面将会提到正则化）
• 与Softmax相比，SVM有”局部目的性”(local objective)。 对SVM而言，只要正确结果的得分比错误结果大Δ，那么loss将会为0.如 [10, -100, -100] 与 [10, 9, 9]两个得分（第一个为正确分类结果），SVM产生的loss是一样的，而Softmax则永远不会对分类结果“感到满意”,即Loss永远不会为0。它希望分类正确的得分越大越好，分类错误的得分越小越好。这样的特性也使SVM与Softmax分别有不同的应用领域。

神经网络

神经网络模型

神经网络是由很多神经元结合在一起，一个神经元把很多的输入x1,x2,x3… 以及截距+1（偏置）作为输入.与SVM和softmax相似的，这里也有一个得分函数将输入映射到一个得分，z = Wx+b。之后再用一个激活函数f将得分z作一个非线性的变换，然后输出。这里的非线性函数有很多种选择，tanh,sigmoid,reLu都是常见的激活函数。

神经网络就是将许多个单一“神经元”联结在一起，这样，一个“神经元”的输出就可以是另一个“神经元”的输入。例如，下图就是一个简单的神经网络：

我们使用圆圈来表示神经网络的输入，标上“ +1”的圆圈被称为偏置节点，也就是截距项。神经网络最左边的一层叫做输入层，最右的一层叫做输出层（本例中，输出层只有一个节点）。中间所有节点组成的一层叫做隐藏层，因为我们不能在训练样本集中观测到它们的值。同时可以看到，以上神经网络的例子中有3个输入单元（偏置单元不计在内），3个隐藏单元及一个输出单元。

一般我们用用来表示网络的层数,表示第 l 层第 i 单元的激活值（输出值）,我们用 表示第 l层第 i 单元输入加权和（包括偏置单元),f
表示激活函数。整个神经网络可以表示为：

求解这个网络，即是通过大量已经标记号的数据（x,y），获取最合适的权重矩阵W与b，使得能得到最好的分类结果。下面提到的反向传播算法就是神经网络的训练算法。

反向传播算法

反向传播（Backpropagation）是“误差反向传播”的简称，是一种与最优化方法（如梯度下降法）结合使用的，用来训练人工神经网络的常见方法。该方法计算对网络中所有权重计算损失函数的梯度。这个梯度会反馈给最优化方法，用来更新权值以最小化损失函数。
反向传播要求有对每个输入值想得到的已知输出，来计算损失函数梯度。因此，它通常被认为是一种监督式学习方法，虽然它也用在一些无监督网络（如自动编码器）中。它是多层前馈网络的Delta规则的推广，可以用链式法则对每层迭代计算梯度。反向传播要求人工神经元（或“节点”）的激励函数可微。

由于神经网络的loss function不是一个凸函数，所以有可能会收敛到局部最优解，但是通常情况下反向传播的结果都不错。另外，在进行反向传播算法前要将参数进行随机初始化，而不是全部置为0。如果所有参数都用相同的值作为初始值，那么所有隐藏层单元最终会得到与输入值有关的、相同的函数随机初始化的目的是使对称失效。

反向传播算法可表示为以下几个步骤：

1. 进行前馈传导计算，利用前向传导公式，得到直到输出层 的激活值。
2. 对输出层（第 层），计算：
3. 对于 , 2 的各层，计算：
4. 计算最终需要的偏导数值：
   

分类中的其他问题

正则化

引入正则化的原因在于，我们想要得到的权重矩阵W是不唯一的。如果W变为原来的2倍得到的分类效果理论上是一样的，但是相应的Loss却相差两倍。我们想要在Loss function上加上一项来移除对于W的模糊性，这一项称为正则惩罚 R(W). 最普遍的L2正则惩罚是权重矩阵W中所有项的平方和：

修改后的Loss function变为：

除了L2正则项，还有L1正则项，但L2正则项更倾向于所有的权重变得更加分散，即最后的得分是所有特征综合的结果。正则化参数λ可以通过验证集选取。

最优化算法

在我们构造出了相应的score function和loss function之后，下一步就希望能通过在训练集中评估loss function得到的预测结果和真实结果的差来更新score function中W和b值。 最优化算法就是根据每次得到的预测loss来对W和b中元素值进行调整，从而使模型有更好的分类结果的过程。

最优化中最经常使用的是梯度下降法，其核心思想就是用微积分或数值分析的知识计算出loss function关于W和b的梯度，然后逐渐让W和b沿着求出的梯度方向下降，直到最后loss趋向于一个稳定值。

梯度下降法在很多实例中可以取得不错的结果，但是它要求loss function是一个凸函数，否则可能会收敛到局部最优解。梯度下降法有如下几个要点：

• 由于每次都把所有的数据计算一次loss计算开销太大了，所以经常采用随机梯度计算的方法，把数据分成很多batch，每次只是计算每个batch的loss。
• α的值可以通过验证集确定
• 无法用微积分直接计算梯度时，可以用数值计算的方法得到梯度。

  validation sets

对于knn算法中的k，线性分类器中的正则项系数λ以及学习速率α，这些参数都对最后的训练结果有极大的影响。我们在确定了分类模型之后，需要找到最好的超参数（Hyperparameter）从而在测试集中得到最高的准确率。

之所以不能用测试集（test set）来获取超参数，有两个原因。当我们使用原本的测试集我们可能对于某一些超参数可以获得很好的分类准确率，但是当我们的模型被应用到其他的数据时结果也许就不佳。这种情况就说明测试集过拟合了。还有一个原因是，如果用测试集来训练的到超参数，其实也就把测试集当做了训练集，所以在测试集上得到的结果并不能很准确的反映模型的好坏，所以这里我们引进了验证数据集（Validation sets）。一般来说，我们把所有标记过的数据分为测试集，训练集，验证集三个部分，三个部分的比例为7:2:1.

特征提取

对于线性分类器而言，如果把RGB原图压缩成一个一维向量，那么输入的维度就太大了。所以在做图像分类之前，一般都要先提取特征。 特征提取是图象处理中的一个初级运算，它检查每个像素来确定该像素是否代表一个特征。假如它是一个更大的算法的一部分，那么这个算法一般只检查图像的特征区域。作为特征提取的一个前提运算，输入图像一般通过高斯模糊核在尺度空间中被平滑。图像特征一般分为颜色特征和纹理特征。

在cs231n的作业中，对输入的CIFAR-10图片提取了hog特征，方向梯度直方图（Histogram of Oriented Gradient, HOG）特征是一种在计算机视觉和图像处理中用来进行物体检测的特征描述子。它通过计算和统计图像局部区域的梯度方向直方图来构成特征。

参考文献

1. ulfdl
2. cs231n-image classification notes
3. cs231n linear classification
4. cs231n optimization notes

说起来想学python技术也有很久很久了。在大四python初入门时就觉得想爬啥就爬啥，一键保存所有图片掌握全世界的感觉真是太酷了。这次在完成了实验室项目和图像课的课程项目之后，想抽出来时间好好学习一下爬虫技术，一方面可以练练自己python代码的能力，另外也想玩转爬虫神器走上人生巅峰。本着这样的目标，我花了大概十天的时间写了一个爬取电影票价格的代码，当然撸代码能力有限代码并没有写的那么优雅，不过感觉自己还是进步了不少。

爬虫技术与Python

网络爬虫（又被称为网页蜘蛛，网络机器人，在FOAF社区中间，更经常的称为网页追逐者），是一种按照一定的规则，自动地抓取万维网信息的程序或者脚本。另外一些不常使用的名字还有蚂蚁、自动索引、模拟程序或者蠕虫。（摘自百度百科）简单的来说，爬虫就是获取浏览器中打开的html页面中你需要的信息，整个过程又分为获取页面，提取信息，存储信息三个部分。其实也就是在模拟输入url到浏览器返回页面的过程，即以下四个步骤：

• 查找域名对应的IP地址。
• 向IP对应的服务器发送请求。
• 服务器响应请求，发回网页内容。
• 浏览器解析网页内容

之所以要用python来爬虫，当然是因为“人生苦短，我用Python”，python里涉及到许多获取网络信息的模块，最基础的urllib/urllib2，requestes等，另外python中也可以方便的利用正则表达式匹配各种有用信息。下面简单说说爬虫技术中核心的要素。以下内容参考：PythonSpiderNotes。

基本抓取

抓取大多数情况属于get请求，即直接从对方服务器上获取数据。此外，对于带有查询字段的url，get请求一般会将来请求的数据附在url之后，以?分割url和传输数据，多个参数用&连接。

登录处理

有一些网站需要用特定的用户名和密码登陆了之后才能获取网页信息。这里登陆处理有两种方式：利用表单登录和利用session登录。

• 使用表单登陆属于post请求，即先向服务器发送表单数据，服务器再将返回的cookie存入本地。
• 使用cookie登陆，服务器会认为你是一个已登陆的用户，所以就会返回给你一个已登陆的内容。因此，需要验证码的情况可以使用带验证码登陆的cookie解决。

关于反爬虫

现在有很多网站都采取了反爬虫机制，有几种方式可以避免IP被block掉。

• 使用代理，通过维护代理池来限制IP地址情况。
• 每爬取几条信息就让系统sleep一段时间
• 利用headers伪装成浏览器

多线程抓取

多线程爬虫可以提高爬虫的效率，scrapy与pyspider等框架都可以直接利用多线程。

几个常用的包

这里我只写我在项目里接触到的一些包，还有其他的包在之后用到了再在这里更新。

urllib与urllib2与re

urllib与urllib2两个模块可以访问网络上的文件。通过一个简单的函数调用就可以把几乎任何的URL所指向的东西作为程序的输入。urllib与urllib2两个模块的功能差不多，但是如果需要使用HTTP验证或是cookie，或是要为自己的协议编写扩展程序，那么urllib2会是更好的选择。

1
2
3

request = urllib2.Request(url,headers = headers)
response = urllib2.urlopen(request)
content = response.read().decode('utf-8')

这段代码得到的content是一个很长的字符串，其中的内容就是url对应的html页面。在得到了html内容的字符串，可以利用正则表达式提取content内容中感兴趣的部分。

1
2

pattern = re.compile('reqgular expression',re.S)
items = re.findall(pattern,content)

requests与beautifulsoup

用urllib2还是比较繁琐，不仅需要好几行代码来获得content，由于url错误会抛出异常，用到urllib2的时候需要手动捕捉异常，这时requests神器就应运而生，一句话，哦不一行代码就可以搞定urllib十行代码才能搞定的。除此之外，requests中添加报头，使用代理和session都是很容易的。requests的文档在这里。

1

content = requests.get(url).content

beautifulsoup可以将网页编变成结构化数据，免去了利用正则表达式来匹配数据的繁琐。具体来说，beautifulsoup里每一个标签都可以作为节点，而属性的名字和值作为字典的key和value。这样访问数据就变得很方便优雅和pythonic。除此之外，在bs中查询某个元素也十分的方便，利用find_all（）方法可以通过xpath/css选择器/类名等来定位元素。下面是一个简单的构造bs对象并查找节点的例子。

1
2
3

html = requests.get(taobao_url,headers = headers).content.decode('utf-8')
soup = BeautifulSoup(html,'html.parser')
items = soup.find_all('div',attrs={'class':"tab-movie-list"})

bs4的文档在这里。

phantomjs与selenium

爬取静态页面可能用上面的工具就够了，然而网页上很多内容是通过js加载的，利用urllib或是requests只能得到静态显示的页面，一些动态加载的数据无法获取。这里可能就需要用到selenium与phantomjs两个神器了。

• PhantomJS是一个无界面的,可脚本编程的WebKit浏览器引擎。它原生支持多种web 标准：DOM 操作，CSS选择器，JSON，Canvas 以及SVG。它可以像浏览器一样渲染js页面。
• Selenium 是自动化测试工具。它支持各种浏览器，包括 Chrome，Safari，Firefox 等主流界面式浏览器，如果你在这些浏览器里面安装一个 Selenium 的插件，那么便可以方便地实现Web界面的测试。

如果将PhantomJS和Selenium结合在一起，那么就可以用一个快速方便的浏览器解析动态页面，再用Selenium来进行拖拽，点击，输入等自动操作，这样你想要的信息就可以轻松获取啦~ 下面是我用到的用这两个工具定位元素的小段代码：

1
2
3
4

driver = webdriver.PhantomJS()  
   driver.get(url)
   time.sleep(1)
   dateItems = driver.find_elements_by_xpath("//div[@class='dates clearfix J-dates']/a")

由于js执行时需要时间的，所以不管是在渲染页面或是进行其他点击操作时，可能需要sleep一段时间来等待js的渲染。除了Selenium自带的通过xpath/css/class定位元素的功能以及点击，拖拽等功能，webdriver还可以直接用driver.execute_script（）方法来执行js语句。phantomjs的文档在这里,selenium的文档在这里。

实战：爬取电影票

上面的一些知识都是我在实际写代码的碰到问题解决问题然后收获的知识点。一开始写爬虫其实就是平时特别喜欢看电影，想找到一个平台的票价是最低的。结果我很幸运的发现了MovieTickets项目，这是一个用js爬虫的电影票价项目，我用到了这个项目中的架构开始撸起了我自己的python代码。主要想法就是先上 淘宝/美团/点评/格瓦拉 爬取最近上映的电影信息，然后在上这四个平台爬取相应位置（我爬取的是洪山区）的电影院信息，最后根据不同平台对应的电影和电影院信息查询到相关的票价信息。爬取的信息用mangodb存储，前端用flask框架展示了爬取的电影票价信息。

思路还是比较简单，但是过程中我也踩了不少坑。

• 不同平台中电影的名字和电影院的名字有时候会有差异，电影的名字主要就是大小写，转换一下问题不大，但是电影院的名字差别就有点大。我想到了两个解决方案：用去掉了范围信息（如XX市XX区）的位置信息来匹配，还有就是用动态规划的字符串相似度
  方法来匹配。两种方法的结果都没有特别好。最后还是手动自己补充了一些电影院和对应ID。
• 爬取电影票的时候，当时因为老爬取上映不久的速激8，一爬应该一百多条数据了，然后IP经常被block了，突然出现找不到元素整个人懵逼，各种检查才发现是反爬虫机制让我掉坑了。这里一定要注意爬了一条数据就给他sleep一下。嗯，爬虫与反爬虫的斗争永无止境。
• 在MovieTickets项目中是定时爬取电影票价，全部存在mangodb中，等访问url时再搜索出相应条目显示。我这里只是在项目刚run的时候从网上爬取了电影和电影院的信息，存储在了mangodb中，然后点击一个电影+电影院链接之后再去爬取对应的票价信息，这样会导致响应很慢，也不够工程化。可是这个定时爬取我觉得实现起来可能还有点难度，所以暂时就放弃。：）

最后，我的项目在这里。在三月底立下的四月写一篇博客的flag实现了，也算是又get了一项技能。接下来的计划是更深入了解SVM/DB/NN/LR等机器学习算法，scikit-learn源码解读与应用。

最近一段时间已知忙着赶图像分析与理解的项目，在三个星期内强行接触了CNN,MRF,Caffe,openCV在内的很多东西。
现在项目已经完全结束了，反而有点怀念看论文写代码的日子～希望能用这篇博文将我这段时间的工作作一个整理，
也方便我之后写报告。

问题描述

• 深度估计是从2D图片中得到深度信息，深度估计主要分为两种形式：从单个的单目图像中获得深度信息，从一系列
  不同角度的单目图像中得到深度信息。在这个项目中我用到的方式主要是第一种。

• 平面检测的目标是识别2D图像中属于同一个平面的一部分。

• 深度估计和平面检测的工作结合起来可以有很多应用，例如3D重建，场景理解，机器人技术以及SLAM
  （Simutaneous Localization And Mapping）问题。

深度估计

1. 利用MRF(马尔科夫随机场)建模

这里介绍的是参考文献[1]中提到的一种方法，之后同一波人写的论文包括[2],[3]等都是用到了相似的方式。关于这相关的project还有一个网站Make 3D,这个项目在[3]中有较多介绍，这个网站里也有一些关于3D重建所需要的数据集。

 a.特征提取

作者表示，人类之所以可以很清楚的从单个的单目图像中获取深度信息，是因为用到了纹理变化，纹理梯度还有颜色等“单目线索”。所以只要我们从图片中提取了这些特征，并且有监督的让机器去学习它，那么就可以让机器从单幅的单目图像中获得深度信息。

在这篇文章中，作者把一张图分割成很多patch，然后估计每一个patch的深度。而对于这些patch，有”绝对”和“相对”两对特征。绝对特征用了纹理变化，纹理梯度和雾霾信息。这里用到了9个3*3的Law’s Mask，6个方向的梯度filter，两个颜色通道（YCbCr颜色空间中的Cb和Cr一共十七个模板。而能量

(k=1,2)
计算了模板和原图像卷积后的L1与L2距离当做是最初的34个特征向量。除此之外，为了更好的捕捉到全局的信息，在这34个特征向量的基础上还加上了三个不同尺度的四邻域mask。三个不同尺度的四领域机上4个列特征所以特征向量一共的维数是19*34=646维。为了表示相对深度，作者为17个特征中的每一个feature vector计算了10个bin的直方图。

 b.概率模型

为了表示相邻patch之间的深度关系，这里用到了MRF。除此之外，还对不同尺度邻域间的相互影响进行了建模。

这里d表示不同尺度的目标像素与四邻域的均值，x表示的是上节获得的特征向量，而方差σ则与则与第i个patch与第j个patch的相对深度成正比，具体说来：
，其中参数u的目的是使σ与d(i)-d(j)的平方更为接近。

 c.小结

这篇paper用到了在图像分析领域用的比较多的MRF模型来更好的表示图像中邻域之间的关系。而且除了一般使用的高斯MRF模型，还提出了拉普拉斯的MRF建模方式。这两种模型都有各适用之处。作者最后提出这种模型在分析相对深度比绝对深度效果好，绝对深度最多能够估计到81m。不得不提这篇在05年出的论文实验的performance已经非常好了，在CNN还没出来之前这种方式应该是业内很流行的。要说缺点，可能就是特征太多，参数也多，我真的是看了好几遍才看明白。= =|||。本来很想把MRF这种方式自己实现一遍都已经在网上下好数据集了，看着这么多要提取的特征又望而却步了（哭泣脸）。

2. 利用CNN（卷积神经网络）

12年CNN开始流行起来之后，似乎无论是分类还是回归都可以用CNN搞定，这篇用CNN估计深度的论文也出现的正是时候。利用AlexNet得到粗粒度的深度图再自己训练一个三层的神经网络得到细节部分工作量看起来也并不是特别大，当然不出意料的也得到了state-of-art的结果。[4]

a.网络结构

这张图片就很清楚的说明了整个网络的结构，上面是把AlexNet的前五层拿出来，然后后面套了两个全连接层，得到了一个很coarse的深度图，只能看出一些模糊的特征。为了让它更清楚的表示局部特征，把原图再通过一个三层的神经网络训练，得到一些局部特征。最后与上面的coarse深度图结合一下，就可以得到最终的深度图。

b.Loss function

为了评判得到的depth map与groud truth之间的差异，这篇paper运用了下面的误差函数：

其中y表示的是通过神经网络得到的预测值，而y*表示的是真实值，这个式子化简之后得：

其实表示的就是每一个点的局部误差之和减去整张图片的整体误差，可以看做是一个归一化的处理。

c.小结

根据最后的实验结果，无论是室内的数据集NYU Depth还是室外的数据集KITTI这种方式都全面吊打make 3D。只要涉及到基于特征的分类或者回归，现在CNN似乎都处于王者地位。唯一的缺点可能就是训练的时间长吧。

3. 代码实现

最开始看的就是CNN那一篇，当时为我们实验室没有GPU而焦虑烦躁了很久很久。之后上github发现有这篇论文的重现代码，于是我开始撸起袖子一点一点装caffe，opencv,从零开始接触这些，居然发现还挺顺利的，都被自己感动了。严格的说起来，这一个部分的代码不算是我实现的,我只是一个搬运工。但是为了能将代码运行成功我也是费了相当大的功夫的。

我们项目里用到的是github博主已经训练好的caffemodel，这个model是在NYU的训练集上训练的，也就是说我如果直接拿来用几乎是只符合室内的:( …这里的test script就是将输入图片resize成固定的大小，然后用吧input扔进训练好的模型就可以得到output了。

1
2
3
4

input = loadImage(imagename, 3, WIDTH, HEIGHT)
input *= 255
input -= 127
output = testNet(net, input)

ps：我发现原来这篇NIPS 2014的paper有项目网站,而且其中还有source code~是在theano框架下写的，weights也在里面！我决定安装一波theano再做一次实验。

平面检测

在做完深度估计之后，思考了蛮久深度估计和平面检测的共同之处。看了[5]之后才发现利用深度信息3D重建之后要探测平面就容易了很多。深度估计和平面检测结合起来在机器人技术，场景理解等方面都有所应用。

1. 利用深度信息与超像素算法

这篇论文([5])看了很多遍，前面一部分是按照前面提到的MRF模型得到了深度信息，后面一个部分则是用重建后的3D点和超像素算法判断共面。论文中用到的超像素算法是[6]，这是一个基于图的贪心聚类算法，实现比较简单，但是年代比较久远。在经过了一番调研之后，我决定利用PAMI 2012中一片论文[7]提到的SLIC方法来做过分割，这个方法的核心思想是利用颜色和位置的距离信息作KNN聚类。

a.超像素算法SLIC

SLIC 即simple linear iterative clustering。分簇的依据是像素之间的颜色相似性与邻近性。其中颜色相
似性的度量因子是lab 颜色空间的L2 范数，颜色邻近性的度量因子是图像二维坐标空间xy。因而综合的度量因子
是[labxy]五维空间。下面所述的距离度量因子由下式计算得到：

其中Ns与Nc分别是距离与颜色的权重。

算法思路是对种子坐标为中心的2S*2S范围内所有像素，求这些像素到种子坐标像素的距离度量因子dist，相邻簇之间的重叠区域像素按照距离最小的种子编号（BlockIndex）标记。整幅图像扫描一遍之后，每个像素点都对应一个BlockIndex，相同BlockIndex 的像素属于同一个簇。接下来进入迭代，对上一次划分的每一个簇，求出每一个簇的labxy 均值，作为新的簇心（种子），按照上述规则重新标记，当迭代一定次数之后，分簇结果基本不发生改变即划分完成，迭代结束。（这里摘自SLIC图像超像素分割算法解析）

b.平面估计

在获取了超像素分割的cluster，以及通过获取的深度信息重建了3D坐标之后，就可以来进行平面估计了。主要分三步：

1. 对于过分割的每一个cluster，根据cluster中的3D点拟合出一个平面并求出一个法向量
2. 根据超像素分割的结果建立一个邻接矩阵判断BlockIndex之间是否相邻
3. 根据BFS算法遍历邻接矩阵，通过每个cluster拟合平面法向量的夹角余弦来判断相邻cluster之间是否共面。

主要流程是这样，其中拟合平面的部分我用到了SVD降维的方法，即求出取样点的协方差矩阵，对角化后最小的特征值对应的特征向量就是平面的法向量。

c.小结

这一部分算法还是很好理解的，看懂算法我基本上就可以开始撸代码了。这个算法的优点在于简单，直观，但是缺点在于有很多参数影响（SLIC的参数，夹角余弦共面的阈值），而且这种方法是极其依赖于深度图的效果（我们组做presentation的时候老师说就是因为深度图不够好所以结果差强人意）。下面提到的方法比较复杂，但是实现的效果也会好一些。

2. RVM+MRF建模

这个方法出自[8].这个paper我觉得可读性真的是不太好，读了几遍才总算是把它的方法给看明白了，核心思想和NIPS 2005深度估计那篇paper类似，提取特征，马尔科夫建模得到每个像素点是否处于平面区域以及每个平面的方向，之后又用滑动窗口再去检测那些不同方向之间重叠的区域的具体方向，这样就能得到一个比较准确的结果。

a.平面评估

这篇paper提到的Depth Estimation的方法主要出自[9],通过这种方式可以粗略估计独立区域的方向。

首先提取特征，这里主要用Gaussian descriptor提取了纹理和颜色特征，具体说来纹理体征用到12个bin的梯度直方图，而颜色特征则是用到了20个bin的红绿蓝三通道的密度直方图。由于得到的特征维度太大，所以利用bag of words的方法把这些特征KNN聚类减少维度（Bag-of-words model）。为了合并得到的纹理和颜色两个词典，用NOMF（Non-negative matrix factorization）将两个文档矩阵合并起来。最后对于图像的每一个区域根据提取的特征词典创建空域图，而空域图Sa，Sb的相似度也是之后作回归和分类的基础。

在得到了相似度ρ之后，可以用一个基于ρ的核函数

来进行RVM（Relevance vector machine）进行回归得到角度值以及进行二值分类得到它是否为一个平面。

b.平面检测

前面的RVM只能做到平面的评估，在边缘细节方面的方向估计可能还不够精确。所以来要用MRF建模对上一步中得到的结果进一步改进。

首先用sweep window在整张图像上滑动，对于那些显著特性（over-lapping area）的点，把这些点作为圆心，利用周围的点的特性来判断圆心的点是否为平面以及角度。利用多组半径做实验，取中位数得到的属于平面的概率ri,以及它的方向di。

之后利用MRF进行建模，对于是否为平面只需做二值分类，而方向判定则转换为属于一张图中有限平面之一，其中ri和di用的是sweep window得到的结果，n表示图像中每一个可能的平面对应的方向。

c.小结

最后这个实验得到的结果是，88%对是否为平面的判断是正确的，而对于角度有18.3°的误差，此外，这种方法对于检测小区域的效果比较差。总体说来，这里的平面检测没有用到重构得到的3D坐标，直接用2D坐标建模，应该比之前的方式实现起来更容易。但是这里用了两个模型一共三次，RVM+MRF+RVM，而且篇paper的整个算法流程真的讲的很难明白。对于用如此复杂的方式得到一个并不算好的结果，我对这种方法是不喜欢的。

3. 代码实现

这里用到的是前面一篇paper的方式，slic算法+BFS遍历+共面判断，实现起来也不复杂。在验收的时候老师问我在重建了3D点之后为什么不用ransac，当时回答没有想到，但是现在细细想想，我觉得在一个重建的3D图里用ransac应该只能检测出一个最大的平面（就我理解ransac应该是整张图符合一个模型，而使outliner尽可能少），如果需要多个平面应该要提前分割对每一块去拟合平面。这样想想我还是没有办法用一个尽可能简单清晰的方式用ransac得到这种算法的效果。
在这边列几个函数，首先是多个3D点拟合平面的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def fit_plane(samples):
 """
 To fit a plane according to a series of 3D points
 Args: 
     samples
 Returns: 
     norm_vec: the normal vector of the fitted plane
 """
 centroid = np.mean(samples, axis=0)
 for i in range(samples.shape[0]):
     samples[i] = samples[i] - centroid
 cov = np.dot(np.transpose(samples),samples)
 U,s,V = np.linalg.svd(cov)
 norm_vec = V[2][:]
 return norm_vec

然后是BFS遍历的部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

for i in range(seg_num): #begin BFS
	if(visited[i]==False):
		visited[i] = True
		qNode.append(i)
		while(len(qNode)!=0):
			current = qNode.pop(0)
			for j in range(seg_num):
				if(adj_matrix[current][j]!=0 and visited[j]==False):
					visited[j] = True
					qNode.append(j)
					sample1 = get_samples(idx_clusters,current,sample_num,depth)
					sample2 = get_samples(idx_clusters,j,sample_num,depth)
					if(is_coplanar(sample1,sample2)):
						root[j] = root[current] #end BFS

网站建设

网站建设其实是项目一开始没有考虑到的。一刚开始我就只是git clone了两个项目SLIC-Superpixels（in C++)和Depth-estimation(in python)，在SLIC算法之中增加了[5]这篇paper的实现。也就是说核心算法部分用到了python和C++两种语言。本来觉得能跑出结果就很好了，可是在验收的前一周突然又想到可以做一个demo展示一下，不然还有一个星期的时间很浪费。最后大胆的决定用python将plane-detection的部分完全重构一遍，最后用Django框架写一个前端页面与后台可以连接起来。

1. Django简介

Django是一个开放源代码的Web应用框架，由Python写成。采用了MVC的框架模式，即模型M，视图V和控制器C。利用Django开发可以省去很多web开发的麻烦，程序员可以专注于写应用而不用去造轮子。并且它是开源且免费的。（Django Overview）

2. view与template

关于django我了解的不多，也主要是现学现卖了。这里我的项目主要用到了template和view方面的知识，简单的说一下我用到的功能，如需更系统学习django可以访问django Documentation.

view负责的是对视图的渲染，一个页面中有一个内容是动态的，不是静态写在html中而是要需要一定的操作（譬如从数据库中提取，或是经过一定处理）才能够展现在静态页面里的。访问了一个views.py中的函数就相当于提前把要在页面上显示的内容准备一下，之后再返回一个已经写好的html页面，并把html中相关的动态内容替换成处理后的内容。在本项目中，Views.py中的 get pic 函数调用了 get depth 与 get_ plane 两个函数得到了所需要的深度图和平面检测图，并以一定的名称保存到本地。

template负责的是展示的页面，我的项目中有一个demo.html页面负责选择图片上传，还有一个show_pic.html的页面负责展示原图，深度图，两种不同形式的平面检测图。具体参见我们的Demo Video这两个页面放在新建的template文件夹中。

除此之外，还要在url.py里进行配置，这一步主要是将在浏览器地址栏中输入的url与views.py中渲染页面的函数对应起来。

这一部分详细见 Part3:Views and templates.

3. 代码实现

处理图片之后显示的代码在views.py中的get pic 函数中，在get _depth 与get plane 两个函数中都把处理过后的图片保存下来了。

1
2
3
4
5
6
7
8
9
10
11
12

def get_pic(request):
if request.method=='POST':
	try:
		image = request.FILES['image']
		img = Image.open(image)
		filepath='media/origin.png'
		img.save(filepath)
		get_depth(filepath)
		get_planar('media/img.png','media/depth.png')
		return render_to_response('show_pic.html',{'image':'/media/test.png'})
	except Exception,e:
		return HttpResponse(e)

小结

前前后后大概花了三个星期来完成这个项目，又花了三天的时间码完这篇1w字的技术博客真是满满的成就感啊~这个项目的源码在这里，我们的项目网站在这里。说起来我对机器学习和深度学习也并没有很了解，关于深度估计和平面检测这块我也是第一次接触，上文中很多提到的方法可能有错误或者不足，也希望大家能指出来。接下来自己想学习部分在python爬虫 / tensorflow写深度学习。立个flag吧，四月份还会写一篇技术博客。加油！

参考文献

1. Learning Depth from Single Monocular Images, Ashutosh Saxena, Sung H. Chung, Andrew Y. Ng. NIPS 2005.
2. 3-D Depth Reconstruction from a Single Still Image, Ashutosh Saxena, Sung H. Chung, Andrew Y. Ng. In IJCV 2007.
3. Make3D: Learning 3D Scene Structure from a Single Still Image, Ashutosh Saxena, Min Sun, Andrew Y. Ng. IEEE Transactions of Pattern Analysis and Machine Intelligence (PAMI), vol. 30, no. 5, pp 824-840, 2009.
4. Depth Map Prediction from a Single Image using a Multi-Scale Deep Network.(Nips 2014)
5. Accurate 3D ground plane estimation from a single image(ICRA 2009)
6. Efficient Graph-Based Image Segmentation,IJCV 2004,MIT
7. SLIC Superpixels Compared to State-of-the-art Superpixel Methods, IEEE Transactions on Pattern Analysis and Machine Intelligence
8. Detecting planes and estimating their orientation from a single image, In Proc. of BMVC 2011.

冬天的阳光总是显得特别的温暖。转眼又到了一年的最后一天，坐在家里的落地窗旁边就好像很久很久以前那样。2017年意味着我就要23岁了，时间会仓促的让我忘记原本深刻的一切。所以在这样一个慵懒的午后想要记录些东西来缅怀即将过去的22岁的日子。

2016上半年是大四的最后一个学期，主要任务是毕业设计+毕业。说起来也是有点惭愧，对于毕业设计我其实没有全心全意的投入。一方面是当时实验室有一些其他的任务，另外到后期确实对我的毕业设计没有什么兴趣了。在那段时间看过很多编程方面的书，深入理解计算机系统，Java编程思想以及Android入门等等，当时很坚定的觉得自己会成为一个程序员，所以疯狂的给自己修炼各种程序员的基本功。虽然可惜的是由于没有经常做项目所以很多内容现在记得也不太清了，但是我相信对于软件工程的理解我还是更上了一部台阶。完成毕业设计之后就是为毕业做的各种准备了。毕业旅行，毕业照和毕业局，每多经历一点就会多一点伤感。以至于在下半年心情不好的时候就会拿出来翻翻毕业照或者把自己毕业的花絮照P成表情包，怀念着大家在一起的日子。

2016的暑假也是非常特别的暑假。和以前的小伙伴们搬到了韵苑4栋，离实验室更近了呢（笑）。记得这个暑假好像上帝都为我们的离别而感到难过，一直不停的下雨。我晚上一般会很早回寝室，一边喝着冰柠檬水一边追着1988和W两个世界，晚上会经常跑操场或是森林公园。暑假其实收获挺多，中了一篇会议论文虽然是并不重要的会议但也是一个小小的鼓励，花了三周的时间修改了网站的需求也彻底让我丧失了对Java Web开发的兴趣，中间还有一周去了北京出差，到中关村软件园的时候突然对我的未来满是憧憬。最后两周放假就跟一群小迷妹一样守着奥运会对张继科马龙傅园慧等花痴不已。在全民都对女排姑娘们拍手叫好的时候，我的暑假也走到了尾声。

在实验室年终总结报告的时候，我说自己这半个学期没有什么收获，但现在仔细想想，其实研究生的第一个学期还是意义重大的。意识到自己对java web与Android开发都没有兴趣而发现了机器学习的新大陆，瞬间觉得大四一年努力的方向都错了。上了机器学习的公开课，看了很多篇CV和NLP的paper也认真的完成了多媒体课和数据挖掘课的作业（虽然最后分数比较心酸），也许过程比较曲折但是我最终发现自己还是对数学统计和算法比较感兴趣（啊哦你的兴趣总在变这样真的好嘛）。现在对于ML的理解也许还不够深入，但我相信一个好的开始就意味着未来不会太糟。这个学期还加入了SSP，接触了单反相机。虽然离专业摄影师差的很远，但是发现一个自己感兴趣的东西并且可以在这个方面有所提高，会让我感觉很兴奋。

这一年还有很多特别的事，比如被电信诈骗了一笔钱（哭泣脸），被偷了一辆电动车，戴上了一直以来都不敢戴的牙套并做好了单身两年的准备（其实并没有，捂脸），还有去张家界以论文第一作者的身份开会顺便吃吃吃玩玩玩。好好坏坏都如人饮水冷暖自知，不能否认的是比起22岁的我与以前相比多了一份作为大人的成熟。

前几天去亲戚家吃饭，舅妈说我变瘦了也变美了（害羞脸）。说起来去年这一年确实有很多人夸过我漂亮（我就是要当真啊哈哈哈），也许是因为坚持锻炼好像身材也变好了不少。记得2016年开年就跟室友说今年会脱单，然而flag还是没有实现。当然是有过自我怀疑的，特别是周围的同学都以光速脱单的时候，幸运的是当我发现自我怀疑会让自己陷入负能量循环的时候，我及时跳了出来。我还有许多要努力的地方，cs229作业还是不怎么会做，tensor flow的代码还是看不懂，羽毛球还是不会打，上个学期给自己买的书还没有看。与其为自己不能掌握的事情难过，不如好好为自己的未来投资。（话是这么说不过我还是很想天上掉下个蓝票滴╭(╯^╰)╮）关于2017的flag已经立了，最后只想说，愿自己的努力不被生活辜负。加油。