机器学习面试干货精讲
原文章地址链接：https://zhuanlan.zhihu.com/p/32877396
机器学习理论和实践专栏：https://zhuanlan.zhihu.com/c_152307828
整体内容划分：
- 推荐书单、公开课
- 面试核心内容提纲
本内容涉及模型核心数学公式，把本人面试中常被问到问题以及模型知识点的总结，起到提纲挈领作用，在准备的过程中抓住每个模型的重点。
面试核心内容目录：
- 决策树
- 随机森林
- Adaboost
- GBDT
- logistic 回归
- SVM支持向量机
- 朴素贝叶斯
- xgboost
- lightgbm
推荐书单、公开课
网络公开课：
- 麻省理工公开课 线性代数——学习矩阵理论及线性代数的基本知识，推荐笔记MIT线性代数课程精细笔记by忆瑧。
- 台大机器学习公开课——授课人林轩田，课程分为机器学习基石和机器学习技法两部分。
- 华盛顿大学机器学习公开课——华盛顿大学在Coursera开的机器学习专项课，共有四个部分，这个课直接从应用案例开始讲起，对于回归，分类，协同过滤和情感分析等都会具体去讲怎么实现应用，并且会告诉你如何在Python中利用网上一些现有的库来实现特定的功能，也就是说基本上在课程的第一部分你就可以全面的知道机器学习能够在现实生活中的应用，以及简单方式去实现一些功能。
- 斯坦福大学公开课 机器学习——Andrew Ng（吴恩达）在斯坦福开设的CS229，难度远高于Coursera上面的课程。
书单：
- 《机器学习》by 周志华，这是一本中国无数Machine Learning热爱者的启蒙教材，它非常合适没有任何背景的初学者看，每一个概念的来龙去脉讲的都很细致，是一本大而全的教材。
- 《统计学习方法》by 李航，这本书主要偏优化和推倒，推倒相应算法的时候可以参考这本书。虽然只是薄薄的一本，但全是精华内容。
- 《机器学习实战》by Peter Harrington，可以对应《统计学习方法》进行实现代码。
- 《Pattern Recognition And Machine Learning》 by Christopher Bishop，属于机器学习进阶书籍，内容全，建议首先完成以上三本书籍，再看这本。
- 《利用Python进行数据分析》——Python常用的库学习（numpy，pandas）
- 《剑指offer》——常见面试题，面试必备。
最后推荐一个网站，收集了进阶的机器学习各种资源Github机器学习Machine-Learning
面试核心内容提纲
一、决策树
1.1 原理
决策树是一种基本的分类与回归方法，其模型就是用一棵树来表示我们的整个决策过程。这棵树可以是二叉树（比如CART 只能是二叉树），也可以是多叉树（比如 ID3、C4.5 可以是多叉树或二叉树）。根节点包含整个样本集，每个叶节都对应一个决策结果（注意，不同的叶节点可能对应同一个决策结果），每一个内部节点都对应一次决策过程或者说是一次属性测试。从根节点到每个叶节点的路径对应一个判定测试序列。
举个例子：
就像上面这个例子，训练集由三个特征：outlook(天气)，humidity（度），windy（是否有风）。那么我们该如何选择特征对训练集进行划分？连续型特征（比如湿度）划分的阈值又是如何确定的？
决策树的生成就是不断的选择最优的特征对训练集进行划分，是一个递归的过程。递归返回的条件有三种：
- 当前节点包含的样本属于同一类别，无需划分；
- 当前属性集为空，或所有样本在属性集上取值相同，无法划分；
- 当前节点包含样本集合为空，无法划分。
1.2 ID3、C4.5、CART
这三个是非常著名的决策树算法。简单粗暴来说:
- ID3 使用信息增益作为选择特征的准则；
- C4.5 使用信息增益比作为选择特征的准则；
- CART 使用 Gini 指数作为选择特征的准则。
熵(entropy)
在信息论与概率论中，熵用于表示随机变量不确定性的度量。
设X是一个有限状态的离散型随机变量，其概率分布为:
则随机变量的熵定义为
熵越大，则随机变量的不确定性越大。
条件熵(conditional entropy)
随机变量给定的条件下，随机变量
的条件熵
定义为：
其中，。
信息增益(information gain)
信息增益表示的是：得知特征X的信息而使得类Y的信息的不确定性减少的程度。
具体定义如下。
特征A对训练数据集D的信息增益定义为集合D的经验熵
与特征A给定条件下D的经验条件熵
之差，即
一般地，熵与条件熵
之差称为互信息(mutual information).
ID3
熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。
信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性a来进行划分所获得的 “纯度提升” 越大 。也就是说，用属性a来划分训练集，得到的结果中纯度比较高。
ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。
C4.5
C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。公式：
其中 ，
是特征
取值的个数
C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。
CART
CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。
CART 的全称是分类与回归树（classification and regression tree）。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。
- 回归树
使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。
要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。
具体为，假设已将输入空间划分为 个单元
，即
个特征，并且在每个单元
上有一个固定的输出值
，于是回归树可以表示为
当输入空间的划分确定时，可以用平方误差来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优值。
选择最优切分特征 和切分点
,具体做法为:
首先遍历特征 ,对固定的切分特征
扫描切分点
,选择使上式达到最小值的对
- 分类树
使用 Gini 指数最小化准则来选择特征并进行划分；Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。
假设有 个类别，样本点属于第
类的概率为
,则概率分布的基尼指数定义为：
1.3 信息增益 vs 信息增益比
之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。
1.4 Gini 指数 vs 熵
既然这两个都可以表示数据的不确定性，不纯度。那么这两个有什么区别那？
- Gini 指数的计算不需要对数运算，更加高效；
- Gini 指数更偏向于连续属性，熵更偏向于离散属性。
1.5 剪枝
决策树算法很容易过拟合（overfitting），剪枝算法就是用来防止决策树过拟合，提高泛华性能的方法，剪枝分为预剪枝与后剪枝。
预剪枝是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。
后剪枝是指先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。
那么怎么来判断是否带来泛化性能的提升呢？最简单的就是留出法，即预留一部分数据作为验证集来进行性能评估。交叉验证
预剪枝和后剪枝的比较
1.6 总结
决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。
- 特征选择。特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则：信息增益、信息增益比、Gini 指数；
- 决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始，递归的生成决策树。相当于是不断选取局部最优特征，或将训练集分割为基本能够正确分类的子集；
- 决策树的剪枝。决策树的剪枝是为了防止树的过拟合，增强其泛化能力。包括预剪枝和后剪枝。
二、随机森林（Random Forest）
要说随机森林就要先说 Bagging，要说 Bagging 就要先说集成学习。
2.1 集成学习方法
集成学习（ensemble learning）通过构建并组合多个学习器来完成学习任务。集成学习将多个学习器进行结合，常获得比单一学习器显著优越的泛化性能。
个体学习器通常由一个现有的学习算法从训练数据产生（比如 C4.5,BP 等），此时集成中只包含同种类型的个体学习器，例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络，这样的集成是“同质”的，同质集成中的个体学习器称“基学习器”。当然也存在不同质的学习器存在于统一集成中，常称为“组件学习器”或直接称为个体学习器。《机器学习》周志华
原则：要获得比单一学习器更好的性能，个体学习器应该好而不同。即个体学习器应该具有一定的准确性，不能差于弱学习器，并且具有多样性，即学习器之间有差异。
根据个体学习器的生成方式，目前集成学习分为两大类：
- 个体学习器之间存在强依赖关系、必须串行生成的序列化方法。代表是 Boosting；
- 个体学习器之间不存在强依赖关系、可同时生成的并行化方法。代表是 Bagging 和随机森林（Random Forest）。
2.2 Bagging
前面提到，想要集成算法获得性能的提升，个体学习器应该具有独立性。虽然 “独立” 在现实生活中往往无法做到，但是可以设法让基学习器尽可能的有较大的差异。
Bagging 给出的做法就是对训练集进行采样，产生出若干个不同的子集，再从每个训练子集中训练一个基学习器。由于训练数据不同，我们的基学习器可望具有较大的差异。
Bagging 是并行式集成学习方法的代表，采样方法是自助采样法（bootstrap），用的是有放回的采样。初始训练集中大约有 63.2% 的数据出现在采样集中。
Bagging 在预测输出进行结合时，对于分类问题，采用简单投票法；对于回归问题，采用简***均法。
Bagging 优点：
- 高效。Bagging 集成与直接训练基学习器的复杂度同阶；
- Bagging 能不经修改的适用于多分类、回归任务；
- 包外估计。使用剩下的样本作为验证集进行包外估计（out-of-bag estimate）。
Bagging 主要关注降低方差。（low variance）
偏差（bias）：描述的是预测值（估计值）的期望与真实值之间的差距。偏差越大，越偏离真实数据，如上图第二行所示。
方差（variance）：描述的是预测值的变化范围，离散程度，也就是离其期望值的距离。方差越大，数据的分布越分散，如上图右列所示。
2.3 随机森林（Random Forest）
2.3.1 原理
随机森林（Random Forest）是 Bagging 的一个变体。Ramdon Forest 在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入随机属性选择。
原来决策树从所有特征中，选择最优特征。Ramdom Forest 的每一颗决策树中的每一个节点，先从该节点的特征集中通过bootstrap的方法随机选择 K 个特征的子集，然后从这个特征子集中通过决策树算法选择最优特征进行划分。（注意：除了随机获取特征以外，还能随机获取样本集，使用这些随机抽取的样本得到不同的决策树）
控制了随机性的引入程度，是一个重要的超参数。
预测 ：
- 分类：简单投票法；
- 回归：简***均法。
2.3.2 具体构造过程
- 从原始训练集中使用bootstrap方法随机有放回采样选出m个样本，共进行n_tree次采样，生成n_tree个训练集
- 对于n_tree个训练集，我们分别训练n_tree个决策树模型
- 对于单个决策树模型，假设训练样本特征的个数为n，那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂
- 每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝
- 将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果
2.3.3 优缺点
优点：
- 由于每次不再考虑全部的属性，而是一个属性子集，所以相比于 Bagging 计算开销更小，训练效率更高；
- 由于增加了属性的扰动，随机森林中基学习器的性能降低，使得在随机森林在起始时候性能较差，但是随着基学习器的增多，随机森林通常会收敛于更低的泛化误差，相比于 Bagging；
- 两个随机性的引入，使得随机森林不容易陷入过拟合，具有很好的抗噪声能力；
- 对数据的适应能力强，可以处理离散和连续的，无需要规范化；
- 可以得到变量的重要性， 基于oob错误率（袋外错误率out-of-bag error）和基于 Gini 系数的变化。
- 不同决策树可以由不同主机并行训练生成，效率很高
缺点：
- 在噪声较大的时候容易过拟合。
三、AdaBoost
AdaBoost 是 Boosting 的代表，前面我们提到 Boosting 是集成学习中非常重要的一类串行化学习方法。
3.1 Boosting
Boosting 是指个体学习器之间存在强依赖关系，必须串行序列化生成的集成学习方法。他的思想来源是三个臭皮匠顶个诸葛亮。Boosting 意为提升，意思是希望将每个弱学习器提升为强学习器。
工作机制如下：
- 先从初始训练集中学习一个基学习器；
- 根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续收到更多关注；
- 基于调整后的样本分布来训练下一个基学习器；
- 如此反复，直到基学习器数目达到 T，最终将这 T 个基学习器进行加权结合。
对训练样本分布调整，主要是通过增加误分类样本的权重，降低正确分类样本的权重。
Boosting 关注的主要是降低偏差。（low bias）
3.2 AdaBoost 原理
面临两个问题：
- 在每一轮，如何改变训练数据的概率分布或者权值分布。（也可以重采样，但是 AdaBoost 没这么做）；
- 如何将弱分类器组合成强分类器。
AdaBoost 的做法：
- 提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类的样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮弱分类器的关注；
- 采用加权多数表决。具体的，加大分类错误率低的分类器的权值，使其在表决中起较大作用，减少分类误差率大的弱分类器的权值，使其在表决中起较小作用。
弱分类器被线性组合成为一个强分类器。
训练目标：
- 最小化指数损失函数。
三部分组成：
- 分类器权重更新公式；
- 样本分布（也就是样本权重）更新公式；
- 加性模型。 最小化指数损失函数。
3.3 AdaBoost 优缺点
优点：
- 不改变所给的训练数据，而不断改变训练数据的权值分布，使得训练数据在基本分类器的学习中起不同的作用。这是 AdaBoost 的一个特点；
- 利用基本分类器的加权线性组合构建最终分类器，是 AdaBoost 的另一个特点；
- AdaBoost 被实践证明是一种很好的防止过拟合的方法，但为什么会如此，至今没从理论上证明。
缺点：
- AdaBoost 只适用于二分类问题。
四、GBDT
GBDT（Gradient Boosting Decision Tree）又叫 MART（Multiple Additive Regression Tree），是一种迭代的决策树算法。本小节从以下几个方面进行阐述：
- Regression Decision Tree(DT)；
- Gradient Boosting(GB)；
- Shrinkage(算法的一个重要演进分支，目前大部分源码都是基于该版本实现)；
- GBDT 适用范围；
- 与随机森林的对比。
4.1 DT：回归树 Regression Decision Tree
GBDT 中的树全部都是回归树，核心就是累加所有树的结果作为最终结果。只有回归树的结果累加起来才是有意义的，分类的结果累加是没有意义的。
GBDT 调整之后可以用于分类问题，但是内部还是回归树。
这部分和决策树中的是一样的，无非就是特征选择。回归树用的是最小化均方误差，分类树是用的是最小化基尼指数（CART）
4.2 GB：梯度迭代 Gradient Boosting
首先 Boosting 是一种集成方法。通过对弱分类器的组合得到强分类器，他是串行的，几个弱分类器之间是依次训练的。GBDT 的核心就在于，每一颗树学习的是之前所有树结论和的残差。
Gradient 体现在：无论前面一颗树的 cost function 是什么，是均方差还是均差，只要它以误差作为衡量标准，那么残差向量都是它的全局最优方向，这就是 Gradient。
4.3 Shrinkage
Shrinkage（缩减）是 GBDT 算法的一个重要演进分支，目前大部分的源码都是基于这个版本的。
核心思想在于：Shrinkage 认为每次走一小步来逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易防止过拟合。
也就是说，它不信任每次学习到的残差，它认为每棵树只学习到了真理的一小部分，累加的时候只累加一小部分，通过多学习几棵树来弥补不足。
具体的做法就是：仍然以残差作为学习目标，但是对于残差学习出来的结果，只累加一小部分（step* 残差）逐步逼近目标，step 一般都比较小 0.01-0.001, 导致各个树的残差是渐变而不是陡变的。
本质上，Shrinkage 为每一颗树设置了一个 weight，累加时要乘以这个 weight，但和 Gradient 没有关系。
这个 weight 就是 step。跟 AdaBoost 一样，Shrinkage 能减少过拟合也是经验证明的，目前还没有理论证明。
4.4 GBDT 适用范围
- GBDT 可以适用于回归问题（线性和非线性）；
- GBDT 也可用于二分类问题（设定阈值，大于为正，否则为负）和多分类问题。
4.5 GBDT 和随机森林区别（重点）
- GBDT 和随机森林的相同点：
- 都是由多棵树组成；
- 最终的结果都由多棵树共同决定。
- GBDT 和随机森林的不同点：
- 组成随机森林的可以是分类树、回归树；组成 GBDT 只能是回归树；
- 组成随机森林的树可以并行生成（Bagging）；GBDT 只能串行生成（Boosting）；这两种模型都用到了Bootstrap的思想。
- 对于最终的输出结果而言，随机森林使用多数投票或者简***均；而 GBDT 则是将所有结果累加起来，或者加权累加起来；
- 随机森林对异常值不敏感，GBDT 对异常值非常敏感；
- 随机森林对训练集一视同仁权值一样，GBDT 是基于权值的弱分类器的集成；
- 随机森林通过减小模型的方差提高性能，GBDT 通过减少模型偏差提高性能。
TIP
1. GBDT 相比于决策树有什么优点
泛化性能更好！GBDT 的最大好处在于，每一步的残差计算其实变相的增大了分错样本的权重，而已经分对的样本则都趋向于 0。这样后面就更加专注于那些分错的样本。
2. Gradient 体现在哪里？
可以理解为残差是全局最优的绝对方向，类似于求梯度。
3. re-sample
GBDT 也可以在使用残差的同时引入 Bootstrap re-sampling，GBDT 多数实现版本中引入了这个选项，但是是否一定使用有不同的看法。
原因在于 re-sample 导致的随机性，使得模型不可复现，对于评估提出一定的挑战，比如很难确定性能的提升是由于 feature 的原因还是 sample 的随机因素。
五、Logistic 回归（熟悉推导过程）
- LR 原理；
- 参数估计；
- LR 的正则化；
- 为什么 LR 能比线性回归好？
- LR 与 MaxEnt 的关系。
5.1 LR 模型原理
首先必须给出Logistic分布：
是位置参数，
是形状参数。对称点是
，
越小，函数在
附近越陡峭。
然后，二分类 LR 模型，是参数化的 logistic 分布，使用条件概率来表示：
然后，一个事件的几率（odds）：指该事件发生与不发生的概率比值：
对数几率：
那么对于逻辑回归而言， 的对数几率就是：
最终，输出 的对数几率是输入
的线性函数表示的模型，这就是逻辑回归模型。
5.2 参数估计
在统计学中，常常使用极大似然估计法来估计参数。即找到一组参数，使得在这组参数下，我们数据的似然度（概率）最大。(极大似然估计：就是利用已知的样本结果信息，反推最具有可能（最大概率）导致这些样本结果出现的模型参数值，即‘模型已定，参数未知’)
似然函数：
对数似然函数：
如何得到逻辑回归的损失函数?
我们希望上式越大越好，换句话说，对于给定样本数量 ，我们希望
越小越好，这个也就是LogLoss。
对应的损失函数：
为什么LR的输入特征一般是离散的而不是连续的？
在工业界，很少直接将连续值作为逻辑回归模型的特征输入，而是将连续特征离散化为一系列0、1特征交给逻辑回归模型，这样做的优势有以下几点：
- 离散特征的增加和减少都很容易，易于模型的快速迭代；
- 稀疏向量内积乘法运算速度快，计算结果方便存储，容易扩展；
- 离散化后的特征对异常数据有很强的鲁棒性：比如一个特征是年龄>30是1，否则0。如果特征没有离散化，一个异常数据“年龄300岁”会给模型造成很大的干扰；
- 逻辑回归属于广义线性模型，表达能力受限；单变量离散化为N个后，每个变量有单独的权重，相当于为模型引入了非线性，能够提升模型表达能力，加大拟合；
- 离散化后可以进行特征交叉，由M+N个变量变为M*N个变量，进一步引入非线性，提升表达能力；
- 特征离散化后，模型会更稳定，比如如果对用户年龄离散化，20-30作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反，所以怎么划分区间是门学问；
- 特征离散化以后，起到了简化了逻辑回归模型的作用，降低了模型过拟合的风险。
李沐少帅指出，模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。就看是喜欢折腾特征还是折腾模型了。通常来说，前者容易，而且可以n个人一起并行做，有成功经验；后者目前看很赞，能走多远还须拭目以待。
5.3 最优化方法
逻辑回归模型的参数估计中，最后就是对求最小值。这种不带约束条件的最优化问题，常用梯度下降，牛顿法和拟牛顿法，共轭梯度法来解决。
使用梯度下降法求解逻辑回归参数估计
求 梯度：
:
更新 ：
5.4 正则化
正则化为了解决过拟合问题。分为 L1 和 L2 正则化。主要通过修正损失函数，加入模型复杂性评估；
正则化是符合奥卡姆剃刀原理：在所有可能的模型中，能够很好的解释已知数据并且十分简单的才是最好的模型。
表示范数，
和
分别应用 L1 和 L2 正则。
- L1 正则化。向量中各元素绝对值之和。又叫做稀疏规则算子（Lasso regularization）。关键在于能够实现特征的自动选择，参数稀疏可以避免非必要的特征引入的噪声；
- L2 正则化。使得每个元素都尽可能的小，但是都不为零。在回归里面，有人把他的回归叫做岭回归（Ridge Regression），也有人叫他 “权值衰减”（weight decay）。
一句话总结就是：L1 会趋向于产生少量的特征，而其他的特征都是 0，而 L2 会选择更多的特征，这些特征都会接近于 0.
5.5 逻辑回归 vs 线性回归
首先，逻辑回归比线性回归要好。
两者都属于广义线性模型。
线性回归优化目标函数用的最小二乘法，而逻辑回归用的是最大似然估计。逻辑回归只是在线性回归的基础上，将加权和通过 函数，映射到
范围内空间。
线性回归在整个实数范围内进行预测，敏感度一致，而分类范围，需要在 。而逻辑回归就是一种减小预测范围，将预测值限定为 [0,1] 间的一种回归模型。
逻辑曲线在 时，十分敏感，在
或
处，都不敏感，将预测值限定为
。逻辑回归的鲁棒性比线性回归要好。
5.6 逻辑回归模型 vs 最大熵模型 MaxEnt
简单粗暴的说：逻辑回归跟最大熵模型没有本质区别。逻辑回归是最大熵对应为二类时的特殊情况，也就是说，当逻辑回归扩展为多类别的时候，就是最大熵模型。
最大熵原理：学习概率模型的时候，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。
5.7 最大熵模型
六、SVM 支持向量机
虽然咱们的目标是尽可能的不涉及到公式，但是提到 SVM 就没有办法不涉及到公式推导，因为面试中只要问到 SVM，最基本也是最难的问题就是：SVM 的对偶问题数学公式推导。
所以想学好机器学习，还是要塌下心来，不仅仅要把原理的核心思想掌握了，公式推导也要好好学习才行。
6.1 SVM 原理
简单粗暴的说：SVM 的思路就是找到一个超平面将数据集进行正确的分类。对于在现有维度不可分的数据，利用核函数映射到高纬空间使其线性可分。
支持向量机 SVM 是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。SVM 的学习策略是间隔最大化，可形式化为求解凸二次规划问题。
SVM 分为：
- 线性可分支持向量机。当训练数据线性可分时，通过硬间隔最大化，学习到的一个线性分类器；
- 线性支持向量机。当训练数据近似线性可分时，通过软间隔最大化，学习到的一个线性分类器；
- 非线性支持向量机。当训练数据线性不可分，通过使用核技巧及软间隔最大化，学习非线性支持向量机。
上图中，X 表示负例，O 表示正例。此时的训练数据可分，线性可分支持向量机对应着将两类数据正确划分并且间隔最大的直线。
6.1.1 支持向量与间隔
支持向量：在线性可分的情况下，训练数据样本集中的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）。
函数间隔定义如下：
表示目标值，取值为
、
. 函数间隔虽然可以表示分类预测的准确性以及确信度。但是有个不好的性质：只要成倍的改变
和
，虽然此时的超平面并没有改变，但是函数间隔会变大。
所以我们想到了对超平面的法向量 施加一些约束，比如规范化，使得间隔确定，这就引出了几何间隔：
支持向量学习的基本思想就是求解能够正确划分训练数据集并且几何间隔最大的分类超平面。
6.1.2 对偶问题
为了求解线性可分支持向量机的最优化问题：
将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，这就是线性可分支持向量机的对偶算法。
本来的算法也可以求解 SVM，但是之所以要用对偶问题来求解，优点是：
- 一是对偶问题往往更容易求解；
- 二是自然引入核函数，进而推广到非线性分类问题。
6.1.3 核函数
对于在原始空间中不可分的问题，在高维空间中是线性可分的。
对于线性不可分的问题，使用核函数可以从原始空间映射到高纬空间，使得问题变得线性可分。核函数还可以使得在高维空间计算的内积在低维空间中通过一个函数来完成。
常用的核函数有：高斯核、线性核、多项式核。
6.1.4 软间隔
线性可分问题的支持向量机学习方法，对现行不可分训练数据是不适用的。所以讲间隔函数修改为软间隔，对于函数间隔，在其上加上一个松弛变量，使其满足大于等于 1。约束条件变为：
6.2 优缺点
缺点：
- 时空开销比较大，训练时间长；
- 核函数的选取比较难，主要靠经验。
优点：
- 在小训练集上往往得到比较好的结果；
- 使用核函数避开了高纬空间的复杂性；
- 泛化能力强。
6.3 LR和SVM的区别
- Linear SVM和LR都是线性分类器
- Linear SVM和LR都是判别模型
- Linear SVM不直接依赖数据分布，分类平面不受一类点影响；LR则受所有数据点的影响，如果数据不同类别处于极其不平衡的状态, 一般需要先对数据做平衡处理。
- Linear SVM依赖数据表达的距离测度，所以需要对数据先做标准化；LR不受其影响
- Linear SVM依赖惩罚项的系数，实验中需要做交叉验证
- Linear SVM和LR的执行都会受到异常值的影响，其敏感程度而言，谁更好很难下明确结论。
- Linear SVM和LR损失函数不同, LR为logloss, SVM为hinge loss. 而SVM中的
称为hinge loss。
七、朴素贝叶斯
八、XGBoost
参考资料
学习建议：多考虑各模型之间的优缺点，区别和适用范围。不要只知道用了哪些模型，而且知道为什么用这个模型。
最后祝各位面试成功！并以下面一句话来勉励你我。
路漫漫其修远兮，吾将上下而求索。
#机器学习##面经##秋招##算法工程师##数据挖掘#
投递小米集团等公司10个岗位 >
微软公司福利 59人发布
