算法工程师基础问答（适合对一些基础问题比较迷茫的选手）
有什么面试有疑惑的问题可以提问呀，一起讨论。有理解错的地方请一定帮我指出来呀
这些问题适合于非科班机器学习转行，其中有些题目可能被问到，做个记录。主要适合机器学习方向，nlp方向可以去学习bert，cv有另一些知识的，这些要单独去学习，楼主也不会，这里主要分享一些机器学习方向比较基础的问题。先占个坑
问题预览
1、数据量比较大的时候，svm和lr哪个更快?
2、线性回归和逻辑回归的损失函数?
3、逻辑回归是分类还是回归？
4、逻辑回归总结。
5、过拟合。
6、为什么l1范数更稀疏?7、从gbdt到xgb到lgb
8、boost\bagging\blending\stacking
9、AUC
10、DNN到CNN
1、数据量比较大的时候，svm和lr哪个更快？
如果对工程有一些了解，知道数据量很大的时候经常用lr当baseline，那么就能猜到答案，但面试的时候显然不能直接猜答案的。只是，为什么lr比svm快呢。
首先要明白的是，这两个模型从理论上看训练速度都非常快才对，只是快的原因不一样，实际是这样吗？
svm寻找分类最大间隔，通过引入原函数的对偶形式，将原问题的w,b转化为对偶乘子α的求解。从形式上看，α为0对应了非支持向量，那么样本不起作用，α＞0，才对应了支持向量，又由于支持向量是很稀疏的，那么要优化的α很少才对，因为svm只考虑边界点，那么就一点点乘子的优化看起来应该是训练速度很快？但实际上，在初始状态，学习器是不知道那些样本是支持向量的。smo算法每次选一对乘子优化，固定其他乘子，是一个二次规划问题，选择乘子也是启发式算法，这一步也导致了整个凸优化的svm寻解过程了变成了近凸优化，在乘子的选择上由于初始不知道那些是支持向量，所以乘子不好选择（启发式方法选的是违背kkt条件最大的一对点），实际上你还得去训练那些非支持向量的数据，速度提不起来。最重要的是，虽然，smo算法挺不错，但是这一步怎么并行啊，每次固定了其他乘子优化一对乘子，那就不能并行了呀，整个流程成了一个串行操作，这和gbdt的串行没有区别，xgb的并行不也老老实实一棵树一棵树的训练（类别n>2的gbdt分类可以并行做到n棵树n棵树的训练）。
而且，svm用都用了，不给整个核函数吗？这又是一步较为耗时的操作。
lr就不同了，同样是凸优化的模型，lr只有一个线性组合和sigmoid，梯度下降时，每个样本训练复杂度也就和样本特征维数有关，复杂度是线性的。最为关键的是，lr可以做到样本的并行和w求解的并行。矩阵运算是可以拆解的，AB看作A对B的行操作，也可以看作B对A的列操作，这样矩阵的运算就可以分解为独立的向量操作，轻松实现并行化。另外，lr也可以对数据进行切分后并行化操作，但主要应该还是梯度下降的并行，lr的实际训练速度要比看起来快很多。
2、线性回归和逻辑回归的损失函数?
以前每当问到为什么不用逻辑回归或者逻辑回归的损失函数这一类时，总回答不好。作为一个笔试型选手，有时候表达不出来对的意思，情商不高？问逻辑回归的损失函数，我就答极大似然函数或者logloss。然后面试官问：还有呢？我说没了。然后就没了。
后来有一位面试官问我线性回归和逻辑回归损失函数的对比，我才明白之前的问题没那么简单。。。恰逢我同学也被问道了，决定总结一下。
线性回归用平方损失，逻辑回归用logloss损失，but why?为什么线性回归不用logloss损失，逻辑回归不用平方损失呢？
线性回归当然可以用logloss，逻辑回归也可以用平方损失，甚至只要你喜欢，加啥损失都行，光滑的不光滑的，都可以，只要当y的预测接近y的时候损失函数比较小，远离y则比较大就可以。甚至对于不可导的损失函数，也可以用次梯度优化、坐标下降法等方法进行优化，优化过程只要保证向损失函数减小的方向，优化方法的改变主要改变的就是训练的速度（当然对最终的解也会有轻微影响），特别是凸函数，最终总能收敛到全局最优点。只不过默认线性回归的平方损失和逻辑回归的logloss损失有额外好处。
最大的原因可能是凸性的要求，对于线性回归，使用平方损失，那么整个过程是一个凸优化的过程，可以保证收敛的情况比较好，证明过程的话求一下hessian矩阵看一下正不正定就可以。而逻辑回归，使用logloss是凸函数，使用平方损失则不是凸函数了，容易收敛到局部最优解，证明方法同样可以通过hessian矩阵来。
另外，对线性回归，使用平方损失，那么整个过程等效于参数在正态分布下的极大似然估计。（又多了一点好处，有兴趣的可以看一看线性回归，岭回归，LASSO对应的参数分布假设，算了过几天查查资料推一下吧）。。而且，线性回归在平方损失约束下，都不需要求导，直接使用矩阵的广义逆带进去，求的就是最小二乘解，也就是全局最优解。非常有意思，在平方损失约束下，线性回归求解简单，一步到位，而且还具有物理意义。
那么逻辑回归这个分类模型呢，他用logloss的原因是不是也是类似呢。是的，logloss在逻辑回归里，也是最大似然估计的形式，也是凸优化过程。不仅如此，还是最大熵模型的等价形式（知道这个结论就好，不熟不要挖坑），除此除此之外，还有好处。
交叉熵p(x)log(1/q(x)) 提一个负号，p(x)是y，q(x)是预测的y，即f(x)，这不就是logloss损失ylog(f(x))。f是对x线性组合后的sigmoid函数。那么用logloss就是在优化交叉熵，so 那又如何？
相对熵，又叫KL散度，形式是p(x)log(p(x)/q(x))。展开后是p(x)log(p(x))-p(x)log(q(x))，相对熵的作用就是用来衡量两个分布的差异性，即p(x)==q(x)，相对熵为0最小。在机器学习里，我们首先特征工程，实际上是一个假设空间，我们认为假设空间存在一组解，利用这组解得到最真实的预测情况。首先，这个假设空间的最优解是个固定的分布，优化的过程就是去逼近这个分布，换句话说，p(x)在作为y的真实分布，这里是定分布，而q(x)是我们学习器学出来的，是我们的猜测分布。由于我们要对交叉熵，也就是logloss求导，他等价与对相对熵求导，因为p(x)log(p(x))求导的时候为0没了，剩下的右边就是相对熵。所以我们优化交叉熵就是在优化相对熵，成了。
那么优化相对熵有啥好处，p(x)是真实y分布，q(x)是猜测的分布，我们优化相对熵就是在让两个分布一致，即f(x)作为预测结果更加接近真实的y，物理意义成了。
3、逻辑回归是分类还是回归？
搜一些资料，经常可以搜到，逻辑回归是广义线性回归，所以是回归，用来处理分类任务。逻辑回归还叫对数几率回归，but why？
在学习这玩意的时候，我们往往会说，一个线性组合，套个sigmoid，就是lr。没错，为什么套sigmiod啊？因为sigmoid光滑，因为sigmoid有概率意义，因为sigmoid+logloss凸优化啊。原本神经递质的神经元是01函数，这个函数不太行咱们用sigmoid替代他，所以就行线性回归+sigmoid。说的倒也对，不过光滑的激活函数很多，未必不存在具有更好性质的激活函数呀。
先回答为啥lr是对数几率回归吧。
知乎有相关推导，可以先看一看,就是这么推的，很棒。。。
这就是prml以贝叶斯角度对sigmoid的推导。注意到最大熵模型在sigmoid和logss损失下等价性。
另外，sigmoid对应了条件先验概率p(y|x)伯努利分布(就是两点分布)，softmax就是sigmiod在多分类形式下的表示(对应的是多项分布不是多重二项分布，多重二项分布是二次分布的实验做多次的结果，多项分布是二重分布扩展到***的结果)。
但sigmoid是不是LR的最好形式？不一定，但是sigmoid是推导出来的，而不是说因为sigmoid本身的性质(光滑处处可导单调)而选择的。
4、逻辑回归总结
如果被问道为什么用sigmoid为什么logloss如何求导这些问题不要再说不会了。
推理顺序：
1、sigmoid起源
2、凸函数性质选择logloss损失
3、凸函数下+logloss等价于分布逼近。
4、极大似然估计
5、损失函数设置，得到梯度求导公式
6、由梯度求导可以得到分布式优化。
7、其他性质：最大熵。
sigmoid起源第3小问已经给出了说明，sigmoid函数是假设数据集x是高斯分布，条件概率是p(y|x)是伯努利分布的情形下推导而来的。所以选择了逻辑回归i，我们自然就得到了sigmoid函数，所以sigmoid函数可以看作是一种限制，我们不是选择了sigmoid函数而是LR就需要sidmoid函数。
面试官经常会问的为什么LR不用平方损失呢？首先要明白，LR完全可以用平方损失，只要是损失都可以用，算出梯度直接按流程下降就行，logloss是损失函数中一个非常好的选择，因为由sigmoid+logloss的海森矩阵可以判断出其损失函数是凸函数，但L2损失不满足损失函数是凸函数，这是L2损失在LR中存在的问题，我们不能保证得到的局部最优解是全局最优的。
当使用logloss之后，由于整个优化过程是凸优化，f(x)是凸函数，凸函数+概率满足了jensen不等式的前提条件，LR学习的本质是假设了原本的分布是)
是我们需要去拟合的，但是我们的学习器是设立了新参数
，我们优化的输出是)
，通过新参数去调控我们的分布拟合，使得两个分布更趋近于一致。衡量两个分布用的是KL散度，我们已经有了观测点
，那么我们的目的就是最小化ln(%5Cfrac%7Bp(x_%7Bi%7D)%7D%7Bq(x_%7Bi%7D%7C%5Ctheta)%7D)%7D%3D%5Cfrac%7B1%7D%7BN%7D%5Csum_%7Bi%3D1%7D%5E%7BN%7D%7Bp(x_%7Bi%7D)ln(p(x_%7Bi%7D))%7D-%5Cfrac%7B1%7D%7BN%7D%5Csum_%7Bi%3D1%7D%5E%7BN%7D%7Bp(x_%7Bi%7D)ln(q(x_%7Bi%7D%7C%5Ctheta))%7D%5Cgeq0)
不等式界由jensen不等式给出，最好的情况就是人为构造的拟合分布完全等于现实的分布，当然这是不可能的，因为我们的样本只是真实分布的采样，所以学习器实质上拟合的是数据集的分布。
所以我们可以得到大胆的结论，LR回归就是在拟合真实分布。
另外，从极大似然出发，我们能够推出一模一样的损失函数形式，这就是另一个好处了，这种logloss损失设置就是极大似然的另一种形式。
求导后，由求导的梯度下降式子，你会发现这个梯度是可以并行运算的，要知道，往往样本数量都是很多的，在样本数量很多的情况下，运算速度就显得非常非常重要了，我们自己仿真一下平时的学习器，可能花不了1s，但是大数据下这个速度要求还是很严格的，数据多的情况下我们自己的仿真根本跑不完，这就是LR最实际最大的好处了吧。
至于为什么要大数据呢？这就牵扯到过拟合的问题了。
5、过拟合？
在LR总结这里，提到了我们试图使得学习器学习本质的分布，但是由于我们只有训练集，所以真实情形是我们学习的是训练集的分布，而训练集分布和真实分布的近似情况，是要打一个问号的。
一般被问到如何解决过拟合，我前期倾向于老实作答，但后期就倾向于交流一下自己的想法了。
首先，要想解决过拟合，我们必须得知道什么是过拟合？
一个有意思的例子，我们去识别一片树叶，欠拟合的学习器识别能力很弱，看过去是一片绿，所以把绿色的东西识别成叶子。但是这些叶子可能是在山东采的，假如山东的叶子有个问题，很多都有小锯齿，过拟合的学习器看过去发现这些训练集的叶子的轮廓有很多小锯齿，所以会把绿色的、叶子形状的有锯齿的东西识别成叶子，那些其他地区的比如江苏圆圆的叶子就识别不出来了，这叫过拟合。
这个例子很适合入门理解，但是一点也不深刻。过拟合发生的原因一定是学习器学习能力过强吗？不一定的。
一般能搜到的回答是：过拟合就是训练集误差小测试集误差大的情况。产生的原因主要是数据有噪声，数据量不足或者学习器拟合能力过强。
分析一下，我觉得训练集误差小测试集误差大是过拟合的表现而不是过拟合本身。回到机器学习可行的两个条件，举例数据构建了两个特征，特征1是离散特征，取值[0，1]，特征2是连续性特征，取值0-1。那么我们就有了假设空间，假设空间H是{特征1：0，1；特征2：0-1}。
条件1：假设空间H的size M有限，当N足够大，对假设空间任何一个g,Eout≈Ein。
条件2：算法A从假设空间中，挑选出一个g，使得Ein(g)≈0，则Eout(g)≈0。
这两个条件往往是互相违背的关系，对于过拟合，违背了条件1，但遵从了条件2，当过拟合发生的时候，训练是很容易的，我们很容易随便就找到了一组解，使得训练集误差很小啊，但这个小误差不能迁移到测试集上。
从上面也能推出，如果N无穷大，那么随便找个可以充分训练的复杂模型，都可以获得不错的训练效果，可以直观理解，不管怎么过分的拟合，未知的数据都可以在见过的相似数据找到，对于紧致集，你总能分类出正确的结果。
总结一下过拟合发生的原因：
数据分布不能准确表征真实分布且学习器学习能力强进行了充分地训练(学习器正确学到了训练集数据分布但训练集数据分布有问题)。
因为学习器学习到了它认为的正确分布但这个所谓的数据分布并不能很好的代表真实分布的时候，过拟合才会发生。即数据分布没有泛化性。首先过拟合不应归咎于训练的问题，因为过拟合往往是非常容易训练的，很快的训练集误差就逼近0了，损失函数很小，但训练的目的就是让损失函数尽量小，只不过参数空间有太多的解，每一组解都是让损失函数很小的，当损失函数很小的时候，训练过程完成了，只不过在交叉验证的时候发现可能出现了过拟合。
要解决过拟合，可以去减少模型的复杂度，当数据集不代表真实分布且模型拟合能力不足的时候，是可以炼丹出不错的结果的，随个好的随机种子，但这不是很好的方案。
所以解决过拟合的第一步，就是检验数据集是不是能很好的代表真实分布：
1、检查数据量是不是过小，是不是有代表性。
只有三四个数据没有代表性，但是三四亿个数据可能过于冗余，那么具体需要多少数据呢？过拟合的时候往往是数据不足的时候，此时可以提高数据集的质量，方法就是
1)人工产生新数据或数据扩充
图像的数据扩充可以裁剪，旋转，变色等等。普通数量不足可以用GAN模型生成，数据加小噪声也是一种扩充的方法(没错，这个更像是trick)，过采样(适度)。
2)检查数据泄露
数据泄露是数据集分布不代表真实分布的另一个例子。在标注没出问题的情况下，出现了和label极强相关性的漏泄特征，比如每个样本独一无二的ID号，模型可以直接对每个样本的ID号记录下它的类别，但是这对新数据的泛化能力几乎为0，这是比较极端的数据泄露的例子。另外出现和label独立的特征，也是一种干扰，如果学习器试图把这个参与建模，也是容易过拟合的。
3)结构风险最小化
正则化。正则化对参数增加了限制，让模型不走极端，比如L2约束就不容易出现某个参量过大的情况，L1则是限制了参与运算结果的参数数量。BN层则限制了分布偏移，CNN本身就是DNN的带约束结构。结构风险最小化主要是降低期望风险，主要针对样本有限的情况，因为样本有限的话我们数据集分布不能很好的代表真实分布，那么就需要降低模型的学习能力，因为如果很完整的学习到了训练集的分布，那几乎可以肯定发生了过拟合。
4)trick
早停、dropout。
最后大数据下NN效果很好的原因就是因为数据太多，泛化误差收敛了，NN的拟合能力还是太强了。
6、为什么l1范数更稀疏?
这个问题看到了，很多人脑海中肯定有个图，一个菱形交一个圆，容易交在坐标轴上，所以稀疏。l2是两个圆，交在一起容易交在外面。所以参数偏小。l1范数是菱形约束，在这个菱形的边上，各个点的范数损失一样大，他和原函数平方损失的切点为最优点，而原函数用了平方损失，那么就是以均值为中心的高斯分布，是个圆或者说椭圆。l2是圆形约束，和原函数平方损失组合一起，就是两个圆相切，注意不是相交是相切的那个点。
另一种有趣的解释是l1梯度向0跑，右边-1左边+1，两边都朝着0收敛，但是l1梯度绝对值一直是1，所以容易收敛到0不动，l2越靠近0梯度绝对值越小，容易到0附近不动。
本质上，lasso模型实际上假设了w参数服从拉普拉斯分布先验下的最大后验估计MAP，岭回归则是高斯分布。
对拉普拉斯分布，有
拉普拉斯分布的图像就是在0处有一个高高的凸起，所以从概率上讲，假设w服从拉普拉斯分布，那么最终落在0上的概率很大。假设是高斯分布，那么落在0周围的概率很大，因为高斯分布就是容易落在均值附近。
机器学习里有一个奥卡姆剃刀准则(哲学emm)，就是能简单就不要搞复杂。正则化其实就是让模型变得简单。l1正则的作用就是让部分参数不起作用，部分参数为0。理论上l0正则更适合作稀疏性的工作，但l0是个np难问题，就是多项式时间内解决不出来，需要近似于穷举的问题。l1作为弟弟替代品，代替l0行使权力，让模型因为稀疏而简单。l2范数是约束了某个特征不要作用太大，因为带平方这类函数都对异常点离群点敏感，l2约束就可以让w部分不要值太大，因为参数某个值太大就会让其他参数黯然失色，就好比一个百万富ong和9个学生，平均资产10万一样，不带l2范数，可能就会导致w里某个值过大，对训练数据拟合挺好，但是泛化不行的问题，l2就是让w的各个值的范围压缩到同一水平，所以值都比较小，大家一起起作用。
gbdt是梯度提升树，又叫伪残差树。思想来自boost提升思想，构造相关的低方差基学习器去拟合偏差。残差树是通过真实值到预测值的残差作为下一棵树拟合方向，模型是加性模型，根据每一步的残差拟合一棵树，最后把所有的树求和即可。
梯度提升树的区别就在于残差这一步用损失函数的梯度负方向代替了，模型不再是拟合残差，而是拟合梯度负方向，固定之前的树，新加一棵树。假如损失函数是平方损失，梯度提升树拟合的就是残差，因为0.5残差的平方求导后是残差，所以平方损失的梯度提升树也是拟合的残差。
gbdt用cart回归树去拟合，不用分类树是因为类别没有偏序，不好求导。当然回归变分类挺好变的，如果是二分类可以用阈值，或者类似逻辑回归那样弄个概率意义。多分类用onehot+logloss+softmax用拟合，注意这里对n>2的分类任务，softmax输出的是被划分为每个类的概率，但每个类都要拟合一下。
举个例子，一个样本，10分类任务，onehot后是1 0 0 … 0。然后第一轮造10棵树，第一颗树回归值标准是1，回归的值出来是0.99，然后第二棵到第n棵树是0.1 0.1 ……，注意10棵树是加起不一定是1，因为每棵树是划分的子区间所有样本label的均值。这样softmax之后e^0.99/(e^0.99+e^0.1+e^0.1+……)=0.213。看起来和正确差很多不是么，因为最终10棵树softmax结果很差啊，明明已经预测出0.99了，但是0.99是这棵树对label的onehot的第一个类别预测的回归值，不是概率，softmax后是概率。但是梯度提升树会继续造新的10棵树，然后可能又是10个0.99，0.1，0.1……。假设没有树权重衰减，这时候就是预测概率e^1.98/(e^1.98+e^0.2+e^0.2+……)=0.4，随着树的不断增多，预测会越来越准确。
xgb对gbdt作了一些改进，加了线性回归分类器而不是只有cart回归树，但默认参数还是cart回归。为了能加快并行，xgb对特征进行了预排序，存成了block结构，这种结构具体我不太清楚，只知道排序好存起来就可以直接快速获得切分点增益了，而且可以用启发式贪心算法，找一些百分位作为切分点，这里有两处并行的操作，第一步是遍历节点，树的一层节点可以并行做，因为xgb是按层不加区分的去切分每一个结点，每个结点都会尝试分类，所以构建的是一个非常茂盛的树，既然每个结点都要尝试分裂，就可以对每个结点并行去切分。结点的切分要选择一个特征的一个分裂点切分，这一步可以在特征维度上并行。由于gbdt类基模型相关性，做不把串行树做到并行的，所以并行主要在结点分裂和特征分裂上。不过为了防止过拟合，当分裂的增益小于阈值时，就不分裂了，算是预剪枝了。
另外xgb在损失函数作了二阶展开，而不是gbdt的一阶梯度，在损失函数上+了L1和L2正则。另外对缺失值处理时，往常的做法是人工手动填充一个值，因为分裂无外乎放左子树和右子树，所以在xgb这里会试着帮你把缺失值放左边和右边试一试，如果训练数据没有缺失值，测试集有，这种gap是直接默认把缺失值放在了右边。
lgb应该是现在比赛里表现最好的模型之一了，他主要是训练速度比xgb快太多了，而且lgb可以直接把类别特征通过pandas定义成category，这样就不需要人工onehot了，当然实战两种方法都要试试选个效果更好的。lgb把特征用直方图去预处理，速度比预训练快很多，因为直方图切成左右结点特别好切，一道竖线就成了两个直方图了，找几个百分位试试切割效果就可以切了，速度非常快，虽然理论上会损失精度，但是特征的值分成桶直方图统计进行粗粗的特征切割据说有正则化效果（玄学），学习性能不会损失太多。另外一个和xgb很大的不同在于，甚至和大多数gdbt分裂方式都不同的一点，lgb按最优叶子结点分裂，分裂的树又瘦又长，注意boost算法要求基模型学习能力不要太强，所以lgb参数里有树深的限制，不能设的太深。实战中lgb性能和xgb确实差不太多，但是训练速度差太多了，lgb训练快，更容易调参。
这里分享一个经验，xgb和lgb都有bagging策略，有特征采样，样本采样这些参数，一般特征采样选个合适的不仅训练速度快而且性能也会提高。但是如果是在造特征的这个阶段，采样频率要设为1，不然采样没采到可能就错过了一个不错的特征了。而且作特征处理的话，强特弱特都重要，因为比到最后大家成绩都差不多了，在有几个强特基础上，弱特多了模型一样效果好。
8、boost\bagging\blending\stacking
模型误差=偏差+方差+固定误差
偏差一般是模型训练集的误差反应偏差程度，方差则是模型训练集的扰动情况，如果输入只改变一点点，训练结果变化很大，那么这个模型的方差就很大。固定误差则是训练数据是真实理论值的采样啊什么的导致训练数据不是绝对准确啊什么什么的，我们总有一个误差在这里。
这里要先了解机器学习可行的两个条件，当我们特征构造好之后，特征的所有取值空间构成了假设空间。一般VC维越高，这个假设空间越复杂，VC维越低，假设空间越简单。
模型肯定需要我们训练数据能够反映出真实分布，当样本很少的时候，训练数据太少，填充不了假设空间，导致我们的训练E(in)和真实E(out)相差比较多，那么我们的学习效果一定不会好，测试数据和训练数据产生了很大的gap，当我们训练数据足够多的时候，再加新的数据，你都能从样本集和里找到一个差不多的，这时候训练数据就可用了，所以当训练数据数量趋于无穷的时候，我们的训练集足够反映真实的分布，所以机器学习的可行第一个条件就是训练数据够多。
第二个条件则是我们的学习器充分优化到一个好解，能够去逼近理论的最优解。
当训练数据足够多有什么好处呢？一个最为突出的好处是训练误差和测试误差非常接近，当训练数据无穷大，这两个误差收敛到一起。此时就算我们模型很复杂，我们使劲去拟合，最后模型的效果也不错，因为真实的数据能够在训练数据里找到一个差不多的，这也是为什么大数据情况下模型效果还不错的原因吧。
但我们自己训练的时候，训练数据总不是无穷多的，这时候就要考虑模型复杂度的问题。
训练数据适中，模型复杂度不够的时候，我们的训练误差比较高，因为模型学习不了完整的分布，那么此时就是欠拟合。
训练数据始终，模型复杂度太高的时候，随着训练的进行，由于模型学习到的分布越来越复杂，已经超过了真实的分布，那么就是过拟合了。
举个例子，一片树叶，欠拟合就是学到了一片绿，那么模型见到绿的就认为是叶子。过拟合就是学到了叶子的形状、颜色甚至是锯齿形状、锯齿个数，叶子上的脉络大小长度粗细，对于一片没有锯齿的新叶子，学习器认为这不是叶子，因为没有锯齿。
当然训练数据不足的话是很难学习的很好的，因为数据都反映不了真实的分布。真实的讨论应建立在固定训练规模上和固定模型上。此时若是假设空间大，机器学习可行的第二个条件容易达到，但第一个不行，E(in)和E(out)差的比较多，我们学习器学习到的分布要么训练数据不够反映不了真实的分布，要么本身学不了那么复杂的分布，导致容易欠拟合；若是假设空间小，那么E(in)和E(out)差的比较小，但是优化容易出问题，因为模型太复杂了，参数空间里存在太多组解都可以让训练误差很小，但是分布对不上，第二个条件出了问题。
boost和bagging是怎么做的呢？
个人理解是boost强调提升算法，强调弱模型集成，每个学习器方差比较小，此时处于容易欠拟合状态，那么就一步步拟合出方法，每造一棵树，模型复杂度提高一点，偏差降低一点，最终达到偏差和方差的权衡，(虽然实战中gbdt还是挺容易过拟合的）。
bagging，比如RF，强调每个基模型是高精度树，每棵树深度10层以上甚至不剪枝，保证拟合的准确，此时属于上述第二种情况，优化比较困难，不容易收敛到最好的解，那么RF通过构造数据的多样性，通过数据集的不同、特征的不同，让每棵树学到不同的东西，多样性增多，好而不同。训练集就好比图书馆，RF就好比一群专家，有的专家看图书馆里第一层的书，有的看第二层的书，有的研究数学，有的研究英语，但每个人都是专家，对自己那一亩三分地掌握的很好，最后有人问问题的时候，每个人都回答的自己那一块掌握的内同(过拟合)，但是一群专家的讨论后可能就会得到很不错的结果。
另外在RF中，每个基模型都是独立的，所以特别容易并行化，分类树就投票，回归树就平均。
但现在有这样一个问题，集成学习，数据集用的一样的数据集，基模型用了SVM、决策树、LR和xgb融合，那么这是boost和bagging呢？个人感觉这既是boost也不是bagging，与其说集成学习，更像是模型融合。为什么是融合而不是boost或是bagging呢？
首先，如果是boost，那么此时的低方差模型拟合体现在哪里呢？模型之间的相关性呢？没有体现，更何况还加了xgb本身就是boost的模型作为基模型。
bagging呢？有点像，各个学习器很独立，但是注意到他们训练数据是一样的，没有数据采样和特征采样，不能说成bagging。
特别的，如果是分类，通过投票法做的融合，此时是uniform blending，即每人一票，少数服从多数。uniform的目的是为了减少方差，达到减少过拟合的目的。另外，线性blending常用于回归任务，即每人给一个权值，即加权平均。bleng要求各个学习的结果也是好而不同，这样blending的结果会不错。
这里有个比赛和理论的gap。往常对blending的解释是取大部分做训练，训练出基模型，用切出来的测试集送到基模型里，得到的学习器输出加权出一个较好的结果去拟合测试集的label值。实际比赛的话有些人没有切测试集的这个步骤，而是直接用开源的模型输出好多结果，直接取一些加权情况带进去看分数，为什么这样做的，因为比赛分为AB榜，可以直接去看拟合A榜的结果，来看这个blending的参数好不好，推测隐藏的B榜分数。
stacking比赛的大杀器，其做法非常有意思，把所有模型的训练集的输出当成输入再送进去训练。
搜了一张图，应该很直观了。stack往往和交叉验证一起使用，下图是五折交叉验证，五折后把训练集分成了五份，每一份测试集都是独立的，然后可以训练出五个学习器，把这五份测试集合在一起作为新的测试数据当作第二层的标签，而训练集再通过五个学习器得到五个训练结果，作为输入送进去当作第二层的输入，然后第二层在学习出一个新模型出来。
训练好之后，过来一个新数据，然后被五个基学习器学习出五个标签，当作训练数据在第二层的学习器学习到最终的结果。
直观的看，第二层的学习器相当于对训练的输出结果进行了拟合，好比五个学习器学到了五个结果，第一个学习器在第一段学习的不好，第二个学习器在另一段学习的不好，然后第二层学习器为这些结果做了一个线性变换，映射到最终的结果上，可能就第一段结果上，第二层模型重点考虑了学习器二到五，另一端则是除了2的其他四个。stack的要求是第一层各个学习器都要是学习的很好的结果，差异性越大提升效果越明显，第二层简单一点好，可以预防过拟合，一般stacking不会超过三层。
stacking在比赛里非常非常厉害，但是简历上最好不要对着stacking吹，因为实际工作这个stacking用的应该不多，因为stacking就是用算力在提分数，付出和结果很不成正比，实际中更倾向于简单易用解释性好的模型，所以简历上stacking内容能删就删。
9、AUC
如果是推荐算法工程师，那么AUC一定是常问问题。
首先就是样本正确与否的概念，真正、真负、假正、假负。格式是T/F +P/N。T/F：true or false。P/N：positive or nagative。
T/F是这次的判断是否正确，P/N是这次的判断是什么。
TP正样本正确判断为正样本。 TN负样本正确判断为负样本。
FP负样本错误判断为正样本。 FN正样本错误判断为负样本。
主要使用的两个正确率衡量：
查准率(精确率)，所有被学习器判断为正样本的里面真正的正样本比例。TP/(所有被预测为正的样本)，所以分母是?P，？是T/P，即TP/(TP+FP)。之所以叫精确率是看你预测的正样本结果准不准，因为实际中他是不是正样本是不知道的，但是你预测完之后他可以在所有正样本里面抽样检测出里面多少个正的，用那个正样本数量和采样率和所有被预测为正的总数算的准确率就是在估计这个值。查准率是对预测结果的衡量。
查全率(召回率)，所有的正样本中被判断为正样本的比率。TP/(TP+FN)，分母就是所有正样本数量。之所以叫召回，是对真实正样本而言而不是对预测结果而言，召回就是找吗，所有的正样本被你揪出来了多少，就叫召回率。或者可以从实际业务理解，有问题的叫正样本，也就是我们关心的样本，我们对东西做了出厂检测，有多少被预测数来了，这些就返厂召回了的比率。
就好比参与了答题游戏，你所有回答中答对的比率就是查准率，所有该答对的问题你确实答对的概率，答全了，查全率。
实际中需要两个度量一起起作用，所以才会将二者的调和平均值即为F值衡量。之所以不是精确率越高越好，是因为模型可以将样本尽可能预测为负样本以保证查准率，只对个别有把握的预测为正。召回率则是学习器可以尽可能将样本预测为正样本以保证正样本被正确预测，保证查全率。当模型性能固定的情况下，二者是一个矛盾的关系。
一个好的模型肯定是查准率和查全率都高，但是只要模型固定好，二者就开始矛盾。以LR为例，LR输出可以认为是概率，但一定是0.5为阈值吗？不一定哦，假设LR输出代表的是为1的概率，为正样本，当我们把阈值往上调的时候，此时被分成1样本就越来越严格，被预测为正样本的数量越来越少，查准率提升，查全率下降。
ROC就是以真正率为纵坐标、错正率(代指假正率=1-真负率，真假是分类对错的意思，容易歧义)为横坐标，纵坐标是查全率不是查准率，横纵坐标都是学习器对正负样本的预测能力，而不是查准率那种自身预测好坏的衡量，错正率=1-真负率，所以ROC考虑了正负两类样本。当模型固定后，设置不同的分类阈值，可以画一条曲线，即为ROC曲线。ROC曲线不是由横坐标纵坐标的关系画出来的，而是设置不同的分类阈值，阈值平滑的变动，横纵坐标跟着动，可以画出来一条曲线。当阈值设置为无穷小，此时所有样本分为正，那么正样本都被分为正样本，真正率为1，负样本都被错分为正样本，假正率为1-0为1。随着阈值向上增加，真正率减少，错正率减少。阈值无穷大，所有样本分为负类，真正率为0，错正率为0。图像越往左上，真正率越高，错正率越低，即真负率越高，正负样本都被分类的不错，此时模型性能最好。
AUC就是ROC的曲线下面积，因为曲线越往左上性能越好，此时面积也越大。AUC用来衡量分类器的性能，通过阈值的改动我们能获得多好的正样本分类和负向本分类。
另外AUC值可作为衡量分类器能够将正样本排在负样本前面的概率。因为AUC就是左上凸的程度，越是将正样本排在负样本前面，阈值滑动的时候，越来越多的错分为正的样本被还原为负样本，而真正的正样本排在负样本前面，所以被错分为正的负样本先被改为负样本，而真正的正样本要很靠后才能被分为负样本，直到阈值无穷大，所有样本都分为负样本。将所有的情况考虑一遍取个平均，就是这个概率。这个性质可以很好用来计算AUC。
一次排好序，然后按切割点遍历，得到真正率和假正率，因为每滑动一次切割点，必然要么多个被错分为负类的样本，要么多个被正确纠正的负样本，所有坐标轴要么横着动，要么竖着动，就能画出来一个阶梯状的曲线，就可以得到面积。(但是有时候调整阈值后真正率和假正率不变，原因是多个预测值一样大的情况，一次改多个，就可能出现斜线，此时这种方法就不可用了)而且复杂度也较高，有了AUC作为将正样本排在负样本前面的概率这一概念，就可以用这一概念计算AUC了，统计多少对正样本大于负样本，然后算出这个概率值，此时复杂度肯定是O(N^2)。然后排个序再用rank计算就是Nlog(N)了(排序的复杂度)。
最后ROC画出来之后，我们就能自己考虑如何在给定性能的学习器下取何种阈值去平衡正负样本的分类情况了。另外AUC可以衡量排序性能，因此在推荐里面更常用。虽说AUC可以免疫数据分布变化(主要是ROC曲线不怎么变，这里的数据分布变化指的是正负样本数据数量改变了很多而不是说数据集的先验后验分布改了)，但是负样本较多时AUC算的值其实是偏高的，因为AUC主要针对正样本，但是我们比较的是分类器的优劣，虽然大家算出来的AUC都偏高，但是我们衡量的分类器1的AUC大于2的，就大概率分类器1更好就可以了。这可能是为啥ROC比PR曲线更常用的原因吧。。而且虽然是算面积，AUC的计算可是nlog(n)的复杂度。另外ROC曲线与分布变动不大的前提是正数据或负样本增多了，但是正负样本的分布没变化，数据分布改了，数据集分布没改，所以横纵坐标不变，如果数据集分布改了，预测的结果就不准了，数据集分布一致，该预测是什么还会是预测是什么，该对的还是对，该预测错的还是预测错。假如正样本增多，就相当于把所有正样本复制10份，正样本分对的乘10，分错的乘10，ROC曲线还是那样，分子分母同乘10。
另外AUC可以直接当损失函数用，我就用过。。因为正常损失函数遍历一遍是O(n),n只要不是大到突破天际，nlog(n)复杂度和O(n)不会差太多。
10、DNN到CNN
DNN的结构应该都很熟悉了，由最初的感知机发展而来，每层线性组合后乘上激活函数，对应了神经元的激活与失活，然后传递到下一层。一般认为神经层数层数越高拟合能力越强(一般情况下)，一般DNN指的是全连接神经网络，每一个下一层的输入神经元和全部的前一层的神经元连接到一起。最初单层DNN无法解决异或问题，通过增加层数解决这个问题，然后训练方式是逐层预训练，后来有了BP梯度反向传播。
DNN要注意的几个点：
首先是DNN必须有激活函数，因为如果把激活函数去掉，每一层都是线性组合，那么每一层看一看做矩阵变换，然后多层的矩阵变换可以当做一层的变换，即矩阵练乘可以化作两个矩阵相乘，整个模型只有线性分类能力。
其次，DNN往往不是凸优化，存在着很多的鞍点。由于学习能力比较强，所以容易收敛到局部最优解甚至不是局部最优解的鞍点。机器学习可行的两个条件互为制约，对应过来由于学习器拟合能力过强，一般情况下是样本不足，第一个条件难以满足，对应第二个条件容易满足(优化很容易进行)，由于优化很容易进行，很快的就收敛了，但是收敛的点让训练集误差很小，由于第一个条件不满足，Ein和Eout差得比较多，此时对应的就是过拟合，即训练误差小，测试误差大。
DNN学习能力强参考万能近似定理，只要前馈神经网络有线性组合+挤压性质的激活函数+足够神经元=紧致数据集下的任意连续函数。所以SVM、LR都可以被DNN拟合出来。
挤压指的激活函数的饱和性，sigmoid两端饱和，ReLu虽然单端饱和，但是ReLu可以线性组合出两端饱和的激活函数。紧致集往往是必要的，如果数据集不是紧致集，说能特征做的差，紧致集可以简单的理解为同一类集合距离近，不同类距离远，如果两类你中有我我中有你，那就是非紧致集，容易二类混淆。
DNN的问题在于虽然优化太容易进行了，但是Ein和Eout往往不一致，除非有足够多的训练数据。
CNN就是DNN的一种特例，之前DNN是全连接，CNN改为了局部全连接，而且局部参数共享，就是用了一个小块，在这个小块上线性组合，然后小块的参数记为W，这个W进行滑窗，W参数共享给整个层。
CNN是要求输入有序的，即局部应有关联，假如局部没有关联，强行拟合的话实战效果往往也可以，但是违背了CNN的初衷。这种局部参数共享的方法对应了信号处理里面的时不变性，统计特征与选择的数据起点无关，这种结构非常适合处理信号和图像。假如一幅图，要提取有没有某样物品，物品的位置应该是随机的，所以能检测到物品的小窗通过在图像上的滑动就能提取到物品的位置，这是符合认知的。
CNN配套的卷积层和池化层。卷积层本质上就是局部线性组合，虽然卷积层是滑窗线性组合，但是滑窗比较慢，实现的方法是把滑窗线性组合转换为稀疏大矩阵运算。卷积层既然本身可以当做稀疏大矩阵运算，那么多个不配套激活层的卷积层本质就是线性运算。
池化层就是缩减网络模型和结构，比如2*2最大池化，就是在4个格子中选最大的作为代表。BP过程中梯度在池化层的传递就是如果是最大的池化，就是最大值对应的梯度传递过去，其他的不做处理。平均池化就是所有梯度求平均传递过去。
虽然CNN是DNN的改进，且效果很好，但CNN并不是总能替代DNN，假如输入模型的特征是独立的，那么数据本身不存在这么一个时不变特征，CNN强行局部共享不一定好。CNN可以用于部分的时间特征的任务，但时间不能拉得很长。CNN主要是DNN参数限制并加入了局部结构，在图像领域效果特别好，毕竟CNN就是模仿视觉细胞的特性设计的。
DNN和CNN还有RNN都可以结合使用，本身DNN也有很多东西可以做，比如自编码器，embedding等。不过个人感觉DNN最大的问题就是可解释性了，工作的时候上司可能让你解释DNN的隐藏层结果分析给他听(我的教研室老板也要求了)。
#机器学习##面经##算法工程师#
大疆公司福利 177人发布
查看7道真题和解析
