深度学习（机器学习）算法面试(一)

秒速五厘米 2022-03-18 08:07 1448阅读 0赞

**1.请简要介绍下SVM。**

SVM，全称是support vector machine，中文名叫支持向量机。SVM是一个面向数据的分类算法，它的目标是为确定一个分类超平面，从而将不同的数据分隔开。  
扩展：  
支持向量机学习方法包括构建由简至繁的模型：线性可分支持向量机、线性支持向量机及非线性支持向量机。当训练数据线性可分时，通过硬间隔最大化，学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

**2. 请简要介绍下Tensorflow的计算图**

Tensorflow是一个通过计算图的形式来表述计算的编程系统，计算图也叫数据流图，可以把计算图看做是一种有向图，Tensorflow中的每一个计算都是计算图上的一个节点，而节点之间的边描述了计算之间的依赖关系。

**3. 请问GBDT和XGBoost的区别是什么？**  
[https://xijunlee.github.io/2017/06/03/集成学习总结/][https_xijunlee.github.io_2017_06_03]  
XGBoost类似于GBDT的优化版，不论是精度还是效率上都有了提升。与GBDT相比，具体的优点有：  
1.损失函数是用泰勒展式二项逼近，而不是像GBDT里的就是一阶导数；  
2.对树的结构进行了正则化约束，防止模型过度复杂，降低了过拟合的可能性；  
3.节点分裂的方式不同，GBDT是用的基尼系数，XGBoost是经过优化推导后的

**4.在k-means或kNN，我们是用欧氏距离来计算最近的邻居之间的距离。为什么不用曼哈顿距离？**

曼哈顿距离只计算水平或垂直距离，有维度的限制。另一方面，欧氏距离可用于任何空间的距离计算问题。因为，数据点可以存在于任何空间，欧氏距离是更可行的选择。例如：想象一下国际象棋棋盘，象或车所做的移动是由曼哈顿距离计算的，因为它们是在各自的水平和垂直方向做的运动。  
**5关于LR**

Logistic回归又称Logistic回归分析，主要在流行病学中应用较多，比较常用的情形是探索某疾病的危险因素，根据危险因素预测某疾病发生的概率

**LR和SVM的联系与区别？**

1、LR和SVM都可以处理分类问题，且一般都用于处理线性二分类问题（在改进的情况下可以处理多分类问题）  
2、两个方法都可以增加不同的正则化项，如L1、L2等等。所以在很多实验中，两种算法的结果是很接近的。  
区别：  
1、LR是参数模型，SVM是非参数模型。  
2、从目标函数来看，区别在于逻辑回归采用的是Logistical Loss，SVM采用的是hinge loss.这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重。  
3、SVM的处理方法是只考虑Support Vectors，也就是和分类最相关的少数点，去学习分类器。而逻辑回归通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重。  
4、逻辑回归相对来说模型更简单，好理解，特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些，SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。  
5、Logic 能做的 SVM能做，但可能在准确率上有问题，SVM能做的Logic有的做不了。

**LR与线性回归的区别与联系？**

逻辑回归和线性回归首先都是广义的线性回归，  
其次经典线性模型的优化目标函数是最小二乘，而逻辑回归则是似然函数，  
另外线性回归在整个实数域范围内进行预测，敏感度一致，而分类范围，需要在\[0,1\]。逻辑回归就是一种减小预测范围，将预测值限定为\[0,1\]间的一种回归模型，因而对于这类问题来说，逻辑回归的鲁棒性比线性回归的要好。  
逻辑回归的模型本质上是一个线性回归模型，逻辑回归都是以线性回归为理论支持的。但线性回归模型无法做到sigmoid的非线性形式，sigmoid可以轻松处理0/1分类问题。

**1.为什么XGBoost要用泰勒展开，优势在哪里？**

XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得二阶倒数形式, 可以在不选定损失函数具体形式的情况下用于算法优化分析.本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了XGBoost的适用性。  
12.XGBoost如何寻找最优特征？是又放回还是无放回的呢？  
@AntZ：XGBoost在训练的过程中给出各个特征的评分，从而表明每个特征对模型训练的重要性.。XGBoost利用梯度优化模型算法, 样本是不放回的(想象一个样本连续重复抽出,梯度来回踏步会不会高兴)。但XGBoost支持子采样, 也就是每轮计算可以不使用全部样本。

**13.谈谈判别式模型和生成式模型？**

判别方法：由数据直接学习决策函数 Y = f（X），或者由条件分布概率 P（Y|X）作为预测模型，即判别模型。  
生成方法：由数据学习联合概率密度分布函数 P（X,Y）,然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型。  
由生成模型可以得到判别模型，但由判别模型得不到生成模型。  
常见的判别模型有：K近邻、SVM、决策树、感知机、线性判别分析（LDA）、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场  
常见的生成模型有：朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型（LDA）、限制玻尔兹曼机

**16. CNN最成功的应用是在CV，那为什么NLP和Speech的很多问题也可以用CNN解出来？为什么AlphaGo里也用了CNN？这几个不相关的问题的相似性在哪里？CNN通过什么手段抓住了这个共性？**

以上几个不相关问题的相关性在于，都存在局部与整体的关系，由低层次的特征经过组合，组成高层次的特征，并且得到不同特征之间的空间相关性。如下图：低层NN抓住此共性的手段主要有四个：局部连接／权值共享／池化操作／多层次结构。  
局部连接使网络可以提取数据的局部特征；权值共享大大降低了网络的训练难度，一个Filter只提取一个特征，在整个图片（或者语音／文本） 中进行卷积；池化操作与多层次结构一起，实现了数据的降维，将低层次的局部特征组合成为较高层次的特征，从而对整个图片进行表示次的直线／曲线等特征，组合成为不同的形状，最后得到汽车的表示

**机器学习中，为何要经常对数据做归一化？**

**.请简要说说一个完整机器学习项目的流程。**

1 抽象成数学问题  
明确问题是进行机器学习的第一步。机器学习的训练过程通常都是一件非常耗时的事情，胡乱尝试时间成本是非常高的。  
这里的抽象成数学问题，指的我们明确我们可以获得什么样的数据，目标是一个分类还是回归或者是聚类的问题，如果都不是的话，如果划归为其中的某类问题。  
2 获取数据  
数据决定了机器学习结果的上限，而算法只是尽可能逼近这个上限。  
数据要有代表性，否则必然会过拟合。  
而且对于分类问题，数据偏斜不能过于严重，不同类别的数据数量不要有数个数量级的差距。  
而且还要对数据的量级有一个评估，多少个样本，多少个特征，可以估算出其对内存的消耗程度，判断训练过程中内存是否能够放得下。如果放不下就得考虑改进算法或者使用一些降维的技巧了。如果数据量实在太大，那就要考虑分布式了。  
3 特征预处理与特征选择  
良好的数据要能够提取出良好的特征才能真正发挥效力。  
特征预处理、数据清洗是很关键的步骤，往往能够使得算法的效果和性能得到显著提高。归一化、离散化、因子化、缺失值处理、去除共线性等，数据挖掘过程中很多时间就花在它们上面。这些工作简单可复制，收益稳定可预期，是机器学习的基础必备步骤。  
筛选出显著特征、摒弃非显著特征，需要机器学习工程师反复理解业务。这对很多结果有决定性的影响。特征选择好了，非常简单的算法也能得出良好、稳定的结果。这需要运用特征有效性分析的相关技术，如相关系数、卡方检验、平均互信息、条件熵、后验概率、逻辑回归权重等方法。  
4 训练模型与调优  
直到这一步才用到我们上面说的算法进行训练。现在很多算法都能够封装成黑盒供人使用。但是真正考验水平的是调整这些算法的（超）参数，使得结果变得更加优良。这需要我们对算法的原理有深入的理解。理解越深入，就越能发现问题的症结，提出良好的调优方案。  
5 模型诊断

如何确定模型调优的方向与思路呢？这就需要对模型进行诊断的技术。  
过拟合、欠拟合 判断是模型诊断中至关重要的一步。常见的方法如交叉验证，绘制学习曲线等。过拟合的基本调优思路是增加数据量，降低模型复杂度。欠拟合的基本调优思路是提高特征数量和质量，增加模型复杂度。  
误差分析 也是机器学习至关重要的步骤。通过观察误差样本，全面分析误差产生误差的原因:是参数的问题还是算法选择的问题，是特征的问题还是数据本身的问题……  
诊断后的模型需要进行调优，调优后的新模型需要重新进行诊断，这是一个反复迭代不断逼近的过程，需要不断地尝试， 进而达到最优状态。  
6 模型融合  
一般来说，模型融合后都能使得效果有一定提升。而且效果很好。  
工程上，主要提升算法准确度的方法是分别在模型的前端（特征清洗和预处理，不同的采样模式）与后端（模型融合）上下功夫。因为他们比较标准可复制，效果比较稳定。而直接调参的工作不会很多，毕竟大量数据训练起来太慢了，而且效果难以保证。  
7 上线运行  
这一部分内容主要跟工程实现的相关性比较大。工程上是结果导向，模型在线上运行的效果直接决定模型的成败。 不单纯包括其准确程度、误差等情况，还包括其运行的速度(时间复杂度)、资源消耗程度（空间复杂度）、稳定性是否可接受。

**26.如何解决梯度消失和梯度膨胀？**  
（1）梯度消失：  
根据链式法则，如果每一层神经元对上一层的输出的偏导乘上权重结果都小于1的话，那么即使这个结果是0.99，在经过足够多层传播之后，误差对输入层的偏导会趋于0。  
可以采用ReLU激活函数有效的解决梯度消失的情况。  
（2）梯度膨胀：  
根据链式法则，如果每一层神经元对上一层的输出的偏导乘上权重结果都大于1的话，在经过足够多层传播之后，误差对输入层的偏导会趋于无穷大。  
可以通过激活函数来解决

**CRF，HMM(隐马模型)，MEMM(最大熵隐马模型)都常用来做序列标注的建模。**  
隐马模型一个最大的缺点就是由于其输出独立性假设，导致其不能考虑上下文的特征，限制了特征的选择。  
最大熵隐马模型则解决了隐马的问题，可以任意选择特征，但由于其在每一节点都要进行归一化，所以只能找到局部的最优值，同时也带来了标记偏见的问题，即凡是训练语料中未出现的情况全都忽略掉。  
条件随机场则很好的解决了这一问题，他并不在每一个节点进行归一化，而是所有特征进行全局归一化，因此可以求得全局的最优值。

**了解正则化么？**

正则化是针对过拟合而提出的，以为在求解模型最优的是一般优化最小的经验风险，现在在该经验风险上加入模型复杂度这一项（正则化项是模型参数向量的范数），并使用一个rate比率来权衡模型复杂度与以往经验风险的权重，如果模型复杂度越高，结构化的经验风险会越大，现在的目标就变为了结构经验风险的最优化，可以防止模型训练过度复杂，有效的降低过拟合的风险。

**协方差和相关性有什么区别？**

相关性是协方差的标准化格式。协方差本身很难做比较。例如：如果我们计算工资（$）和年龄（岁）的协方差，因为这两个变量有不同的度量，所以我们会得到不能做比较的不同的协方差。为了解决这个问题，我们计算相关性来得到一个介于-1和1之间的值，就可以忽略它们各自不同的度量。

**线性分类器与非线性分类器的区别以及优劣。**

如果模型是参数的线性函数，并且存在线性分类面，那么就是线性分类器，否则不是。  
常见的线性分类器有：LR,贝叶斯分类，单层感知机、线性回归。  
常见的非线性分类器：决策树、RF、GBDT、多层感知机。  
SVM两种都有(看线性核还是高斯核)。  
线性分类器速度快、编程方便，但是可能拟合效果不会很好。  
非线性分类器编程复杂，但是效果拟合能力强

**哪些机器学习算法不需要做归一化处理？**

概率模型不需要归一化，因为它们不关心变量的值，而是关心变量的分布和变量之间的条件概率，如决策树、RF。而像Adaboost、GBDT、XGBoost、SVM、LR、KNN、KMeans之类的最优化问题就需要归一化。

**KMeans**

本算法的时间复杂度：O(tkmn)，其中，t为迭代次数，k为簇的数目，m为记录数，n为维数；  
空间复杂度：O((m+k)n)，其中，k为簇的数目，m为记录数，n为维数  
K-menas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tkmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。  
1、聚类中心的个数K 需要事先给定，但在实际中这个 K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适；  
2、Kmeans需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。（可以使用K-means++算法来解决）

**输入图片大小为200×200，**  
依次经过一层卷积（kernel size 5×5，padding 1，stride 2），pooling（kernel size 3×3，padding 0，stride 1），又一层卷积（kernel size 3×3，padding 1，stride 1）之后，输出特征图大小为：（）  
卷积向下取整，池化向上取整。  
本题 （200-5+2*1）/2+1 为99.5，取99  
（99-3）/1+1 为97  
（97-3+2*1）/1+1 为97  
研究过网络的话看到stride为1的时候，当kernel为 3 padding为1或者kernel为5 padding为2 一看就是卷积前后尺寸不变。计算GoogLeNet全过程的尺寸也一样。

**影响聚类算法结果的主要因素有：分类准则； 特征选取； 模式相似性测度**

**马式距离较之于欧式距离的优点： 尺度不变性； 考虑了模式的分布：**

**TP、FP、TN、FN、各代表什么？**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70]

**什么是RNNs**

RNNs的目的使用来处理序列数据。在传统的神经网络模型中，是从输入层到隐含层再到输出层，层与层之间是全连接的，每层之间的节点是无连接的。但是这种普通的神经网络对于很多问题却无能无力。例如，你要预测句子的下一个单词是什么，一般需要用到前面的单词，因为一个句子中前后单词并不是独立的。RNNs之所以称为循环神经网路，即一个序列当前的输出与前面的输出也有关。具体的表现形式为网络会对前面的信息进行记忆并应用于当前输出的计算中，即隐藏层之间的节点不再无连接而是有连接的，并且隐藏层的输入不仅包括输入层的输出还包括上一时刻隐藏层的输出。理论上，RNNs能够对任何长度的序列数据进行处理  
**RNN、LSTM、GRU区别？**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 3]

**10.标准化与归一化的区别?**

简单来说，标准化是依照特征矩阵的列处理数据，其通过求z-score的方法，将样本的特征值转换到同一量纲下。归一化是依照特征矩阵的行处理数据，其目的在于样本向量在点乘运算或其他核函数计算相似性时，拥有统一的标准，也就是说都转化为“单位向量”。规则为L2的归一化公式如下：  
特征向量的缺失值处理：  
1.缺失值较多.直接将该特征舍弃掉，否则可能反倒会带入较大的noise，对结果造成不良影响。  
2.缺失值较少,其余的特征缺失值都在10%以内，我们可以采取很多的方式来处理:

1.  把NaN直接作为一个特征，假设用0表示；
2.  用均值填充；
3.  用随机森林等算法预测填充

**113.优化Kmeans**。

使用Kd树或者Ball Tree  
将所有的观测实例构建成一颗kd树，之前每个聚类中心都是需要和每个观测点做依次距离计算，现在这些聚类中心根据kd树只需要计算附近的一个局部区域即可。  
**114.KMeans初始类簇中心点的选取。**

K-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。  
1.从输入的数据点集合中随机选择一个点作为第一个聚类中心  
2.对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)  
3.选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大  
4.重复2和3直到k个聚类中心被选出来  
5.利用这k个初始的聚类中心来运行标准的k-means算法

**115.解释对偶的概念。**

一个优化问题可以从两个角度进行考察，一个是primal 问题，一个是dual 问题，就是对偶问题，一般情况下对偶问题给出主问题最优值的下界，在强对偶性成立的情况下由对偶问题可以得到主问题的最优下界，对偶问题是凸优化问题，可以进行较好的求解，SVM中就是将Primal问题转换为dual问题进行求解，从而进一步引入核函数的思想

**116.如何进行特征选择？**

特征选择是一个重要的数据预处理过程，主要有两个原因：一是减少特征数量、降维，使模型泛化能力更强，减少过拟合;二是增强对特征和特征值之间的理解。  
常见的特征选择方式：  
1.去除方差较小的特征。  
2.正则化。1正则化能够生成稀疏的模型。L2正则化的表现更加稳定，由于有用的特征往往对应系数非零。  
3.随机森林，对于分类问题，通常采用基尼不纯度或者信息增益，对于回归问题，通常采用的是方差或者最小二乘拟合。一般不需要feature engineering、调参等繁琐的步骤。它的两个主要问题，1是重要的特征有可能得分很低（关联特征问题），2是这种方法对特征变量类别多的特征越有利（偏向问题）。  
4.稳定性选择。是一种基于二次抽样和选择算法相结合较新的方法，选择算法可以是回归、SVM或其他类似的方法。它的主要思想是在不同的数据子集和特征子集上运行特征选择算法，不断的重复，最终汇总特征选择结果，比如可以统计某个特征被认为是重要特征的频率（被选为重要特征的次数除以它所在的子集被测试的次数）。理想情况下，重要特征的得分会接近100%。稍微弱一点的特征得分会是非0的数，而最无用的特征得分将会接近于0

**125.为什么LSTM模型中既存在Sigmoid又存在Tanh两种激活函数**

sigmoid 用在了各种gate上，产生0~1之间的值，这个一般只有sigmoid最直接了。tanh 用在了状态和输出上，是对数据的处理，这个用其他激活函数或许也可以。

**133.SVD和PCA。**

PCA的理念是使得数据投影后的方差最大，找到这样一个投影向量，满足方差最大的条件即可。而经过了去除均值的操作之后，就可以用SVD分解来求解这样一个投影向量，选择特征值最大的方向。

**设f(x)在\[a,b\]上连续，在（a,b)内具有一阶和二阶导数，那么，**  
（1）若在（a,b)内f”(x)>0,则f(x)在\[a,b\]上的图形是凹的；  
（2）若在（a,b)内f”(x)<0,则f(x)在\[a,b\]上的图形是凸的。  
凸优化问题的性质：  
凸优化问题的可行域为凸集  
凸优化问题的局部最优解即为全局最优解

**机器学习中常见的最优化算法**

梯度下降法（Gradient Descent）  
梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。  
牛顿法的缺点：  
（1）靠近极小值时收敛速度减慢，如下图所示；  
（2）直线搜索时可能会产生一些问题；  
（3）可能会“之字形”地下降。  
h(x)是要拟合的函数，J(theta)为损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的样本个数，n是特征的个数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 6]  
（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。  
　　随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。

两者的关系可以这样理解：**随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。**

**对批量梯度下降法和随机梯度下降法的总结：**  
　　  
　　批量梯度下降—最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。  
随机梯度下降—最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况

**牛顿法和拟牛顿法**

![在这里插入图片描述][20190220100500904.png]  
从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）  
牛顿法的优缺点总结：

优点：二阶收敛，收敛速度快；

缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。

**随机森林算法学习(RandomForest)**

**Bagging和Boosting的概念与区别**

Bagging和Boosting都是将已有的分类或回归算法通过一定方式组合起来，形成一个性能更加强大的分类器，更准确的说这是一种分类算法的组装方法。即将弱分类器组装成强分类器的方法。  
首先介绍Bootstraping，即自助法：**它是一种有放回的抽样方法（可能抽到重复的样本）。**

**1、Bagging (bootstrap aggregating)**

Bagging即套袋法，其算法过程如下：  
A）从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）  
B）每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）  
C）对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

**2、Boosting**

其主要思想是将弱分类器组装成一个强分类器。在PAC（概率近似正确）学习框架下，则一定可以将弱分类器组装成一个强分类器。

关于Boosting的两个核心问题：  
1）在每一轮如何改变训练数据的权值或概率分布？  
通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。  
2）通过什么方式来组合弱分类器？  
通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。  
而提升树通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。

**3、Bagging，Boosting二者之间的区别**

Bagging和Boosting的区别：  
1）样本选择上：  
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。  
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。  
2）样例权重：  
Bagging：使用均匀取样，每个样例的权重相等  
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。  
3）预测函数：  
Bagging：所有预测函数的权重相等。  
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。  
4）并行计算：  
Bagging：各个预测函数可以并行生成  
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

**4、总结**

这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果，但是也增大了计算量。

下面是将决策树与这些算法框架进行结合所得到的新的算法：

**1）Bagging + 决策树 = 随机森林  
2）AdaBoost + 决策树 = 提升树  
3）Gradient Boosting + 决策树 = GBDT**

\*\*随机森林属于集成学习（Ensemble Learning）中的bagging算法。在集成学习中，主要分为bagging算法和boosting算法。\*\*我们先看看这两种方法的特点和区别。  
Bagging（套袋法）

**bagging的算法过程如下：**

从原始样本集中使用Bootstraping方法随机抽取n个训练样本，共进行k轮抽取，得到k个训练集。（k个训练集之间相互独立，元素可以有重复）  
对于k个训练集，我们训练k个模型（这k个模型可以根据具体问题而定，比如决策树，knn等）  
对于分类问题：由投票表决产生分类结果；对于回归问题：由k个模型预测结果的均值作为最后预测结果。（所有模型的重要性相同）  
Boosting（提升法）

**boosting的算法过程如下：**

对于训练集中的每个样本建立权值wi，表示对每个样本的关注度。当某个样本被误分类的概率很高时，需要加大对该样本的权值。  
进行迭代的过程中，每一步迭代都是一个弱分类器。我们需要用某种策略将其组合，作为最终模型。（例如AdaBoost给每个弱分类器一个权值，将其线性组合最为最终分类器。误差越小的弱分类器，权值越大）  
Bagging，Boosting的主要区别

样本选择上：Bagging采用的是Bootstrap随机有放回抽样；而Boosting每一轮的训练集是不变的，改变的只是每一个样本的权重。  
样本权重：Bagging使用的是均匀取样，每个样本权重相等；Boosting根据错误率调整样本权重，错误率越大的样本权重越大。  
预测函数：Bagging所有的预测函数的权重相等；Boosting中误差越小的预测函数其权重越大。  
并行计算：Bagging各个预测函数可以并行生成；Boosting各个预测函数必须按顺序迭代生成。

**决策树**

常用的决策树算法有ID3，C4.5，CART三种。3种算法的模型构建思想都十分类似，只是采用了不同的指标。决策树模型的构建过程大致如下：  
ID3，C4.5决策树的生成  
输入：训练集D，特征集A，阈值eps 输出：决策树T

若D中所有样本属于同一类Ck，则T为单节点树，将类Ck作为该结点的类标记，返回T  
若A为空集，即没有特征作为划分依据，则T为单节点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T  
否则，计算A中各特征对D的信息增益(ID3)/信息增益比(C4.5)，选择信息增益最大的特征Ag  
若Ag的信息增益（比）小于阈值eps，则置T为单节点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T  
否则，依照特征Ag将D划分为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由结点及其子节点构成树T，返回T  
对第i个子节点，以Di为训练集，以A-\{Ag\}为特征集，递归地调用1~5，得到子树Ti，返回Ti  
CART决策树的生成

这里只简单介绍下CART与ID3和C4.5的区别。  
CART树是二叉树，而ID3和C4.5可以是多叉树  
CART在生成子树时，是选择一个特征一个取值作为切分点，生成两个子树  
选择特征和切分点的依据是基尼指数，选择基尼指数最小的特征及切分点生成子树  
决策树的剪枝

决策树的剪枝主要是为了预防过拟合，过程就不详细介绍了。  
主要思路是从叶节点向上回溯，尝试对某个节点进行剪枝，比较剪枝前后的决策树的损失函数值。最后我们通过动态规划（树形dp，acmer应该懂）就可以得到全局最优的剪枝方案。

**随机森林（Random Forests）**

随机森林是一种重要的基于Bagging的集成学习方法，可以用来做分类、回归等问题。  
随机森林有许多优点：  
具有极高的准确率  
随机性的引入，使得随机森林不容易过拟合  
随机性的引入，使得随机森林有很好的抗噪声能力  
能处理很高维度的数据，并且不用做特征选择  
既能处理离散型数据，也能处理连续型数据，数据集无需规范化  
训练速度快，可以得到变量重要性排序  
容易实现并行化

**随机森林的缺点：**

当随机森林中的决策树个数很多时，训练时需要的空间和时间会较大  
随机森林模型还有许多不好解释的地方，有点算个黑盒模型  
与上面介绍的Bagging过程相似，随机森林的构建过程大致如下：

从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本，共进行n\_tree次采样，生成n\_tree个训练集  
对于n\_tree个训练集，我们分别训练n\_tree个决策树模型  
对于单个决策树模型，假设训练样本特征的个数为n，那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂  
每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝  
将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果

**rf中模型方差随着子树的增加而减少  
rf主要通过增加子树之间的相关性来减少模型的方差**

[https_xijunlee.github.io_2017_06_03]: https://xijunlee.github.io/2017/06/03/%E9%9B%86%E6%88%90%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70]: /images/20220318/feab5f3417ee421a9cc9b5e8282186ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 1]: /images/20220318/03248216bfde49bb96a13c9b2275543e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 2]: /images/20220318/ef8e9faa948e4aa288dfcf4a363c28f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 3]: /images/20220318/ff4c9aa25cef4d238e8357a980dd20f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 4]: /images/20220318/1e92a715088248b38ef17aadb0692fbc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 5]: /images/20220318/f27678db0fc346ac8810dd0d38c0e956.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 6]: /images/20220318/7b1d106c40e64f3fa78da2db07e4401f.png
[20190220100500904.png]: /images/20220318/a09d80c0e3eb4e9c966b91a094dfe571.png