机器学习、深度学习基础问题

1.梯度下降法，牛顿法，拟牛顿法的原理？

梯度下降法
3.3.1 梯度下降法的代数方式描述
（1）先决条件：确认优化模型的假设函数和损失函数；
（2）算法相关参数初始化：主要是初始化参数，算法终止距离以及步长。在没有任何先验知识的时候，可以将所有的参数初始化为0，将步长初始化为1.在调优时再优化；
（3）算法过程：
Step1.确定当前位置的损失函数的梯度；
Step2.用步长乘以损失函数的梯度，得到当前位置下降的距离；
Step3.确定是否所有的参数，梯度下降的距离都小于阈值，如果是则算法终止，当前所有的参数即为最终结果，否则进入步骤4；
Step 4.更新所有的参数，对于每一个参数，其更新表达式如下，更新完毕后继续转入步骤1

当前点的梯度方向是由所有的样本决定的。

梯度下降法只用了一阶导数；牛顿法用了一阶导数和二阶导数（海赛矩阵）。

参考牛顿法与拟牛顿法
假设优化函数f(x)f(x)的极小值x∗，那么在x∗处，f′(x)的值应该为 0. 所以我们用牛顿法就是为了找到 f′(x)==0的x∗值。

在牛顿法中，由于需要计算Hesse matrix的逆Hk′，当维度比较大的时候需要很大的计算量。所以在拟牛顿法中，主要就是寻找一个矩阵Gk，用来替换Hk′

2.LR 和 SVM 的异同？

相同点：
1.（用途）LR和SVM本身都是分类算法，而且都是二分类。
2.（线性）如果不考虑核函数，LR和SVM都是线性分类算法，也就是说他们的分类决策面都是线性的。
3.（监督）LR和SVM都是监督学习算法。
4.（判别）LR和SVM都是判别模型。

不同点：
1.损失函数不同：一个算的是概率，一个算的是距离。

逻辑回归方法基于概率理论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值.

支持向量机基于几何间隔最大化原理，认为存在最大几何间隔的分类面为最优分类面。这里减去1就是引入了软间隔。
2.对数据的依赖不同：支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局.
3.使用核函数：在解决非线性问题时，支持向量机采用核函数的机制，而LR通常不采用核函数的方法。
4.自带正则项：**SVM的损失函数就自带正则！！！（损失函数中的1/2||w||^2项），这就是为什么SVM是结构风险最小化算法的原因！！！而LR必须另外在损失函数上添加正则项！！！

LR，SVM 和感知机的区别？

感知机的目标函数：

1.感知机->SVM。感知机要求线性可分。感知机只要找到可分超平面就停了，不会继续优化。而SVM是寻找最大间隔（点到分类超平面的间隔）。
2.感知机->LR。感知机相当于一个阶跃函数，不光滑。所以在 LR 中引入sigmoid函数。

3.如何理解 F1 和 AUC?什么时候使用哪个指标？

F1 对应的是查准率和查全率，有PR曲线，AUC对应ROC曲线。在二分类问题中，什么时候使用哪个评价指标呢？
·在信息检索中，常用 F1 指标。
·在CTR（点击通过率）预测中，常用 AUC 指标。
F1是在确定阈值的时候，判断查准率和查全率。AUC侧重对样本进行排序，使得正样本以更大的概率排在负样本的前面。

4.各种融合方式的原理、优缺点？

模型融合的要素是“好而不同”。
·好！每个单模型的准确率都要超过0.5，如果单模型的准确率比0.5还要低，那么融合之后只会使结果更差。
·不同！单模型之间尽量相互独立。

实际上，集成学习方法主要分成两大类：一种是单模型之间存在很强的依赖关系、必须串行生成的序列化方法，比如boosting方法。一种是单模型之间没有很强的依赖关系，可以并行处理。比如bagging 和随机森林。

Boosting采用的是串行的学习机制：
1.先从初始的训练集中训练出一个学习器。
2.再根据学习器的表现调整样本分布 ，对于出错的样本赋予更大的权重，特别照顾。
3.基于调整后的样本分布学习下一个学习器，如此反复，不断提升效果。
从偏差-方差分解的角度来讲，Boosting 方法主要是关注降低偏差。

Bagging采用的是并行的学习机制：
1.每个模型基于不同的训练集合进行训练，这样尽量增加每个单模型的差异性。
2.对于所有的模型进行平均或者其他融合。

随机森林：
随机森林是在bagging的基础上，引入了随机选择属性（特征）。
从偏差-方差分解的角度来讲，Bagging 和随机森林主要关注降低方差。
随机森林的缺点：对于不同取值属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。在小的数据集或者低维度的数据中不能产生较好的分类。

所以，从上面的分析来看：
（1）bagging和随机森林能够降低方差，具有很强的防止过拟合能力，所以一般来说bagging比较稳定，都会比单模型更好一点，就算数据中的噪声比较大。
（2）boosting 可能表现会特别好，因为它的拟合能力很强。但是也可能比单模型还要差，如果噪声很大，boost方式主要减小偏差，很容易就过拟合，造成效果比单模型还要差。
上面boosting， bagging，随机森林都可以学到多个模型。关于模型最后集成，可以采用平均加权，也可以所有模型相加，也可以学习第二层模型进行集成。Stacking就是学习第二层模型进行集成的一种方式。

5.L1正则为什么能让系数产生0？L2的特点呢？

首先在没有加上正则项的之后，我们假设函数是一个凸函数（至少在局部这里是凸的），那么loss的等高线就像一个椭圆形。这是后加上正则项，我们就需要同时衡量loss函数与正则函数的一个和，使他们最小。画出正则函数的等高线，那么他们相交的地方就是最优解所在位置。
L1正则是对模型中各个参数的绝对值之和进行约束，L1的约束函数是不光滑的，我们的任务就是在L受约束的条件下找到原本损失函数的最小值。这个L约束就像一个有很多突出角的形状，那么他和损失函数的交点很有可能就落在突出的角的地方，刚好那地方的权值就是0。
和L1一样，但是 L2的约束面是一个圆。L2会让权值尽可能的小，从而防止过拟合。一般来说，权值比较小的模型比较简单，能够适应不同的数据集。假设模型参数很大，那么只要数据稍微偏移一下，结果就会产生很大的变化；相反，如果参数都比较小，那么数据偏移了，结果其实不会产生太大的变，也就是“抗扰动能力强。”

6.L1 怎么求导？L1 怎么处理 0 点不可导的情形？

对于 Relu 激活函数，在0点处，一般直接设定它的导数为 0 就好了。
对于 L1，采用 近端梯度下降（PGD）算法来求解，见《西瓜书》253页，看不懂。

7.生成模型和判别模型？

生成方法：生成模型先计算联合概率p(Y,X)然后通过贝叶斯公式转化为条件概率。 由数据学习联合概率密度分布函数 P（X,Y）[=P(X|y)P(y)],然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型。
生成模型：P(Y|X)=P(XY)/P(X)=P(X|Y)P(Y)/P(X)。
以朴素贝叶斯在文本分类中为例：
Step 1.首先要计算先验概率P(Y)，就是统计文本的类别分布。
Step 2.P(X|Y)=P(x1|Y)P(x2|Y)…表示这个类别中出现这些词的概率。
Step 3.采用贝叶斯公式推算出当文档由这些词构成时，属于每个类别的概率。
比如常见的生成模型有：朴素贝叶斯、隐马尔可夫模型、高斯混合模型等。

但是在判别模型中，并不需要知道先验分布。
判别方法：由数据直接学习决策函数 Y = f（X），或者由条件分布概率 P（Y|X）作为预测模型，即判别模型。
比如常见的判别模型有：感知机、K近邻、SVM、决策树等。（线性判别分析（LDA）、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场 ）
以决策树为例，直接就是根据特征的分布，计算出分裂位置进行判别。

8.说说TensorFlow 框架的计算流程，他和其他深度学习框架有什么区别？

TensorFlow 是一种采用数据流图的计算框架。图中的节点表示的是一些矩阵操作，比如矩阵乘法，矩阵拼接，相加，求max等；图中的边表示这些矩阵的一个流向。
一般来说，我们第一步先要构建一个网络模型，也就是定义好一个graph。定义好graph以后，就已经确定了这个模型的输入输出。第二步使启动图，输入数据进行计算。TensorFlow会根据我们定义好的损失函数进行梯度计算，不断更新网络中的权值参数。
1)在上面的过程中，有个比较烦的地方就是我们在输入之前，必须完整地定义好模型，包括网络结构和优化操作等等。等到开始计算以后，TensorFlow不支持我们再去修改这个图。这样就带来一些麻烦，比如我在进行embedding的优化中，开始的时候我不想更新embedding，等迭代到一定epoch的时候，我再开始对embedding进行fine-tune。这时候我没办法在训练了几轮后，把embedding从untrainable改成trainable，所以只能定义两个优化器，一个优化器对embedding进行优化，另一个优化器不对embedding进行优化。但是在pytorch中，我们可以随时把trainable改成untrainable，所以这也是TensorFlow不够灵活的地方。
2)从难易程度上来讲，TensorFlow的学习要比其他一些框架难一些，比如和keras，pytorch相比。我觉得TensorFlow是比较底层的一个框架，很多东西都要自己定义，比如写一个卷积层，你需要自己定义权值矩阵；写一个全连接层，你也要定义权值矩阵和偏置向量。但是在keras，pytorch中这些实现都非常简单，就是写好输入输出维度大小就行了。但是比较底层的好处就是你可以很容易地根据自己的想法来定义网络结构。而想在 caffe 中，你要想改一下网络结构，就得修改 C++ 源码。
3)从速度来讲，我没有跑过对比，但是觉得TensorFlow在计算速度上还可以，只是在数据读取上速度比较差。TensorFlow的数据读取比较麻烦，我一般是先打包成 tfrecord 文件，然后再进行读取。当样本数很多的时候，比如几百万张图片的时候，单纯打包tfrecord在我们服务器上就要几个小时，如果没有固态硬盘，可能需要好几天。然后在读取的时候速度也非常慢，训练过程中，几乎有一半的时间是在读取数据。TensorFlow有几个image处理的函数，非常非常慢。

9.CNN的原理？CNN 为什么要选用max_pooling，各种pooling方式的优势是什么？

convolutional层的作用：
每一个卷积层由多个卷积核组成，每个卷积核可以看做是一个固定的滤波矩阵。这个矩阵不断地滑动跟图像做内积（逐个元素相乘再求和），这就是卷积的操作。
在卷积层中，有几个主要的概念：
（1）卷积核大小，也就是这个滤波器的大小，滤波器越大，则这个视野越大，但是计算量也大很多。一般来说，都会使用多个小的卷积核来替换一个大的卷积核。
（2）深度，也就是滤波矩阵的个数。在CNN中，一般都是通过pooling操作慢慢减小每层的特征矩阵大小，然后不断加大深度。
（3）步长stride：每次滑动步数，滑动步数越大，则冗余越少，但是可能丢失的信息越多。
（4）padding：主要是为了方便从初始位置以步长为单位可以刚好滑倒末尾位置。

和全连接相比，卷积层通过权值共享极大地减少了参数。卷积层归根结底还是为了提取特征，通过多个滤波矩阵，能够学习到很好的高层特征，不断优化预测结果。


pooling层的作用：
（1）引入不变性。这种不变性包括translation(平移)，rotation(旋转)，scale(尺度)。比如max_pooling，取了一个区域的中最大的特征值，不管这个值在这区域中的哪个位置。
（2）减少下一层的输入，从而减少网络参数。由于参数减少，模型泛化能力增强，进而减少过拟合。
（3）在 TextCNN 中，还可以通过 pooling 操作得到定长特征。一般TextCNN都不会做padding，所以不同大小的核卷积得到的向量长度是不一样的，通过pooling操作，可以把它们转换到一样的长度，然后再输入下一层。
（4）在文本中，max pooling 有类似提取关键词的作用。
各种不同的pooling:mean-pooling，max-pooling和Stochastic-pooling三种。
mean-pooling，即对邻域内特征点只求平均，max-pooling，即对邻域内特征点取最大。

根据相关理论，特征提取的误差主要来自两个方面：
（1）邻域大小受限造成的估计值方差增大；
（2）卷积层参数误差造成估计均值的偏移。


·mean-pooling能减小第一种误差，更多的保留图像的背景信息;
·max-pooling能减小第二种误差，更多的保留纹理信息。
·Stochastic-pooling则介于两者之间，通过对像素点按照数值大小赋予概率，再按照概率进行亚采样，在平均意义上，与mean-pooling近似，在局部意义上，则服从max-pooling的准则。

10.Hash表的实现要素，构造映射函数一般用什么方法？

Hash 表中有 key-value 两部分，我们根据 key 来算出value存放的位置，这样就能在O(1)的时间内找到 value.缺点是空间复杂度比较大。
Hash 表基于哈希函数来实现，但是会存在哈希冲突的问题。所以理解 Hash 表主要理解两个内容：（1）哈希函数怎么实现？（2）怎么处理哈希冲突。
一个好的哈希函数能够使计算出来的值比较均匀地分布在Hash表中，即尽可能地减少Hash冲突。常用的哈希函数方法有：
·直接地址法：对于关键字 key 是整型数值，直接利用关键字计算哈希地址：H(k) = ak + b (a,b 为常量)
·数字分析法：每个关键字由几位数字组成，从中提取数字分布比较均匀的若干位作为哈希地址。
·平方取中法：首先对关键字计算平方，然后取中间某几位作为哈希地址。平方后，中间的几位数字和原始key值中多位的值都有关系，所以它会使哈希地址的分布更加均匀，减少冲突。
·除留余数法：H(k) = k % p， 其中p是一个不大于哈希表长度的正整数 p.一般p选择为比较大的质数。除留余数法计算简单，效果一般也比较好，是最常用的散列函数方法。

hash冲突是不可能避免的，常用的解决hash冲突的方法有：
·线性探测/平方探测/随机探测：把散列表看做一个环形表，当发生冲突时，向下一个地址进行探测。
·链地址法（拉链法）：每一个hash地址存一个链表。公共溢出法：用一个列表存储溢出的部分，当发生冲突时，到溢出表中顺序查找。这种方式没有拉链法好，一是不知道溢出的多少，需要定义一个溢出表浪费空间；二是在溢出表中顺序查找速度比在链中查找慢。