机器学习面试知识点

最近一直在准备面试，本来自我感觉还是比较良好的，面试几轮下来发现自己的严重不足，主要是机器学习方面的实践不够，理论也不扎实，对于应届生来讲，实践经验缺少很正常，毕竟毕设课题就那么多，刻下自己没有多动手，就会造成很多方法没有付诸于实践，这个时候，个人感觉理论就十分重要了，至少，在面试官提问时，能够懂得他提问的是什么，然后把自己所了解的知道的都说出来。

这篇文章主要讲机器学习的相关知识点，都是自己课下的一些总结，我也是外行自学，有什么意见和错误，还望大家提出和指正。

首先说一下机器学习，模式识别和深度学习，其实心里一直对他们三者的关系有些模糊，直到有一次面试被问到，结果完全傻眼。

其实模式识别出现的是最早的，早期的模式识别是在传统的图像处理上加上一些滤波，边缘识别等算法，从而使系统看起来比较智能，例如对于数字的识别，目前我们所说的模式识别主要应用于语音识别系统，图像识别，生物信号等等，严格来讲，模式识别只是一个早期出现的古老术语，它与机器学习并没有很大的区别，比如现在归纳为机器学习算法的决策树，其实也是一种模式识别算法，个人觉得，两者的区别在于出现时间，当然还有机器学习算法的分类。
这篇文章可以让大家对三者的关系有一个大概的了解：机器学习，模式识别和深度学习的关系

下面来说机器学习（Machine Learning ），顾名思义，就是使机器拥有能够学习的能力，从实践意义上来讲，机器学习就是利用已有的一些数据，对新来的数据进行分类。

机器学习可以分为有监督学习和无监督学习，如何区分这两者呢，简单来讲就是有一堆数据，如果他们有标签，比如男女，好坏，那么我可以让机器根据标签进行学习，获得一种模型，等再有新的数据出现，则可以根据以往的经验自动进行分类。 这种方法属于有监督学习，就是训练集有输入有输出，有标记。 可是有的时候我们很难对一些数据进行明确的分类，或者这个数据的分类有很多因素关联，无法人工进行统一的区分，这个时候就要用到无监督的机器学习，即机器根据数据自己进行分类学习，然后等待新的数据过来。所以无监督的机器学习就是对没有概念标记的训练样本进行学习，以发现训练样本集中的结构性只是，从而方便对新的数据进行分类。

下面介绍几种机器学习的算法：

有监督的： 

1.回归算法
回归算法是试图采用对误差的衡量来探索变量之间关系的一类算法。主要包括1.线性回归，即如何拟合出一条直线来匹配所有数据，这里可以用到的是最小二乘法，如果返回的值是数值（如房价），则为数据算法；  2. 在线性回归上加sigmoid函数后，就是逻辑回归，逻辑回归属于分类算法，返回的值是是否属于这一类，如肿瘤的良性和恶性，因此，分类算法的而缺点是，其对数据的分类线大部分是线性的，表达能力不足。
这里说一下，我对分类和回归的理解，如果对于数据的划分结果是离散的，如男女，良性恶性，天气好坏等等，则称之为分类；如果对于数据的划分结果是连续的，如一条线，则称之为回归，在上面的逻辑回归其实也就是分类。

2. 神经网络
神经网络是根据生物学里神经元之间信号传递的方式为启发，进行的一些列运算，主要分为单层神经网络，也叫做感知机；两层神经网络，也叫做多层感知机，以及多层神经网络，也就是深度学习。神经网络的发展比较曲折，具体的过程及讲解可以参考此文：十分详细且易懂的神经网络讲解。
神经网络主要包括输入层，隐藏层（中间层），和输出层，对神经网络的分类主要是根据其隐藏层的个数进行划分。这里主要从上文中剪切三幅图像，一边日后更快地复习神经网络。

神经网络早年发展很好，后因为其训练耗时太久，且总是得到局部最优解，后来逐渐被冷落，随着SVM的出现，随之彻底被抛弃。 这里有一点面试的时候有被问到，就是你觉得早年神经网络被淘汰的原因。

还有一个跟深度学习相关的问题也在此陈述，即图像处理为什么会需要CNN系列算法，或者为什么CNN会在图像处理领域广泛应用。

这个问题主要就是问CNN的优点， 总计来讲主要是两点：1. 稀疏连接。 假设该学习网络有n层，并且假设每层都有五个神经元，所谓的稀疏连接就是第m层的每个神经元仅仅是由第m-1层的3个神经元计算得出，同理第m+1层的每个神经元都是由第m层的3个神经元计算得出，就是CNN网络里的非全连接层，这样做的好处就是首先减少了计算量，同时又使得所求得的结果是全局解； 2. 权值共享。在隐藏层中，同一个特征映射所对应的权值相同，通过共享权值，为我们可以不用计算神经元在隐藏层中的具体位置，让我们更有效地提取特征，同时也大大地减少了计算量，使得神经网络更加快速。

还有另一个涉及到CNN的面试题就是卷积层和pooling层各自的作用，为什么需要pooling层，个人觉得，卷积主要是对特征进行提取，pooling主要是进行特征映射。

更详细的关于CNN的具体结构和优点，大家参考此文：深度解析CNN

3. SVM 支持向量机
SVM通过更加严格的优化条件获得比逻辑回归更好的分界线；与高斯核的结合将低维空间映射到高维空间（在算法中有证明从低维度到高维度的映射不会带来计算复杂性）。SVM最后的计算是要选择使得间隙最大的函数作为分割平面，即 M = 2/sqrt（w*w）其中 w是分割线wx+b=1或-1的系数。

SVM不太容易产生过拟合，因为一是函数中会加入惩罚函数，防止模型对错误进行学习，二是 min||w||^2 类似于最小二乘法，可以让函数更加平滑。（在维度特别大的时候，可以用线性核或径向核，若使用sigmoid核，则SVM变成一个包含隐层的多层感知机；软间隔优化有一阶软间隔和二阶软间隔，目前解支持向量机的算法包括两种：1.求解原问题，2 求解其对偶问题）

4. KNN  （写到这儿的我表示好累~~）
  KNN全名K-Nearest Neighbor，是相对简单的一种机器学习算法，属于分类算法，已知几组数据及其标签，则对未知数据进行分类。 该方法的主要思路是：如果一个样本在特征空间的最相似的（最邻近的）的k个样本都属于某一个类别，则该样本也属于此类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。该方法的主要技术原理是欧几里德定理，也就是射影定理。详细的KNN步骤看此文。

下面写几个无监督学习算法，无监督算法分为聚类算法和降维算法。

1. 聚类算法：计算种群中的距离，根据距离的远近将数据划分为多个族群。最典型的算法就是k-means算法。
k-means 算法利用数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。k-means算法的计算步骤如下： 
1. 随机在源数据中选取K 个种子点；
2.然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群；
3. 移动种子点到属于他的“点群”的中心；
4.然后重复第2）和第3）步，直到，种子点没有移动；

这里说一下k-means和KNN，两者都是计算距离，但是KNN算法中所有数据都是分好类的，而kmeans算法中的数据无标签，对于计算机来讲，并不知道他们是如何分类的，并且都是哪一类，仅仅是都过距离的计算来达到最终分簇的效果。更详细的k-means算法，看这里！

2. 降维算法
降维算法的原理就是：当我们对数据进行分类时，有时候数据量过于庞大，导致计算复杂，这时候可以考录减少数据量，在所有的数据中，有些数据之间存在一定的联系，我们可以称之为线性相关，这些数据如果用于计算会有些冗余，因此，将一些线性相关的数据用一组向量表示，舍弃多余的数据，这样就达到了降维的目的。降维算法可以从数学上证明，从高维压缩到低维的过程中，最大程度的保留了数据的信息。
典型的降维算法是：PCA算法， 即主成分分析法。将原来变量重新组合成一组互相无关的几组综合变量，同时根据实际需要。从中取出几个较少的综合变量，并且使取出的这几个变量尽可能多的反映原来变量的信息，这种方法就是主成分分析法。

PCA的简要计算过程

还有，就是面试也问到了PCA的主要步骤；

体外话：

最小二乘法：

以一元线性模型为例，监督学习中如果预测的变量是离散的，我们称其为分类，如果预测的变量是连续的，我们称之为回归。

对于一元线性回归模型，假设从总体中获得了n组观察值：(x1,y1),(x2,y2)….(xn,yn),对于平面中的n个点，可以使用无数条曲线进行拟合，选择最佳拟合曲线的标准是可以确定为：使总的拟合误差（即总残差）达到最小。

所以最小二乘法的原则：残差平方和最小。

样本回归模型：

则，

其中ei为样本(xi,yi)的误差。

那么平方损失函数就是：

为了确定a0,a1，使得拟合误差最小，则应分别关于a0,a1求偏导求极值。

 

接下来写一下我关于SIFT的笔记

SIFT是用于检测局部特征的算法。

首先说一下什么是局部特征。局部特征就是图像或在视觉领域内有别于其周围的地方。局部特征通常是描述一块区域，使其具有高分辨度；局部特征的好坏直接决定着后面的的识别和分类是否会得到一个好的结果。

SIFT算法通过求一幅图中的特征点及其有关的scale和orientation的描述子得到特征图并进行特征点匹配。SIFT具有尺度不变性，即改变图片的大小也依然可以进行特征点匹配，和旋转不变性，几遍改变图像的角度，图像亮度或拍摄视角，仍能够得到很好地效果。

SIFT的步骤：

1. 构建尺度空间，模拟图像数据的多尺度特性；

所谓尺度空间的构建就是建立图像金字塔，对于一幅图像I 建立其在不同尺度（scale）的图像，也称为一个子八度，第一个子八度的图像大小为原图像，第二个子八度的图像大小便是原图像的四分之一，以此类推，这样构建的目的是为了保证图像在不同尺度即不同大小下都可以找到特征点，从而保证了SIFT算法的尺度不变性。（注意做笔记，考点， 哈哈。。。）

如上图所示，总共有两个塔，0塔和1塔，即i=0或1； 每个塔都有5层，即s=5. 0塔和1塔的关系是降采样，即如果0塔的大小是原图片大小，那么1塔就是原图的四分之一，长宽个缩小一半； 每个塔里的每层图片之间的关系是拉普拉斯变换，直观上来看就是越往上，图片越模糊。

2. 寻找尺度空间上的极值点，并以此作为关键点。

将图像中的每一个采样点跟与它相邻的26个点进行比较，如果它的值是这个图像比较域内的最大值或最小值，则将其作为特征点。然后去掉不好的点，即DOG局部曲率不对称的点。

3. 利用关键点邻域像素的梯度方向分布特性为每一个关键点指定方向参数，使其具有旋转不变性。

具体做法是：在以关键点为中心的邻域窗口内进行采样，并用直方图统计每个邻域像素的方向，直方图的横坐标是像素点相对于关键点的角度位置，纵坐标是像素点的梯度方向值，选取直方图中的峰值作为关键点的方向，然后将坐标轴旋转为关键点的方向，并对每一个关键点产生128个数据，即形成一个128维的特征向量，将特征向量进行归一化处理，可以进一步防止光照变化的影响。

4. 根据描述子进行匹配

当两幅图像的SIFT特征向量生成后，我们采用关键点特征向量的欧式距离作为两幅图像中关键点的相似性判定度量。即取图像1 中的讴歌关键点，并找出其余图像2中欧式距离最近的前两个关键点在这两个关键点中，如果 最静距离/次近距离 的大小小于某个阈值，则接受这一匹配。

自此，就完成了SIFT的特征点匹配。

这里需要注意的面试问题是SIFT的尺度不变性和旋转不变性是如何达到的。 上文中都有提啦~为了方便大家的理解，附上大神的SIFT特征提取，很详细的讲解。