经典算法

1 支持向量机

知识点：SVM模型推导、核函数、SMO算法

问题：在空间上线性可分的两类点，分别向SVM分类的超平面做投影，这些点在超平面上的投影仍然是线性可分的吗？

（1）SVM直观推导：

对于任意线性可分的两组点，它们在SVM分类的超平面上的投影都是线性不可分的。

由于SVM的分类超平面仅由支持向量决定，可以考虑只含支持向量SVM模型场景。使用反证法举例。

证明还不严谨，即假设了只有支持向量的情况，会不会在超平面的变换过程中支持向量发生改变，原先的非支持向量和支持向量发生了转化。

要会证明SVM的分类结果仅依赖于支持向量。这是SVM拥有极高运行效率的关键之一。

（2）凸优化理论

此问题也可以通过凸优化理论中的超平面分离定理（SHT）更加轻巧地解决。

该定理描述的是，不相交的两个凸集，存在一个超平面，将两个凸集分离。对于二维的情况，两个凸集间距离最短两点连线的中垂线就是一个将它们分离的超平面。

根据的凸包的性质，可知凸包上的点要么是样本点，要么处于两个样本点的连线上。

问题：是否存在一组参数使SVM训练误差为0？

一个使用高斯核训练的SVM中，试证明若给定训练集中不存在两个点在同一个位置，则存在一组参数使得该SVM训练误差为0

问题：训练误差为0的SVM分类器一定存在吗？

本文旨在找到一组参数满足训练误差为0，且是SVM模型的一个解

问题：加入松弛变量的SVM的训练误差可以为0吗？

使用SMO算法训练的线性分类器并不一定能得到训练误差为0的模型。这是由于我们的优化目标变了，并不再是使训练误差最小。

一个带有训练误差，但是参数较小的点将成为更优的结果。

一个简单的特例是，当C取0时，w也取0即可达到优化目标，但是显然此时我们的训练误差不一定能达到0。

3 逻辑回归

知识点：逻辑回归，线性回归，多标签分类，softmax

问题：逻辑回归相比于线性回归，有何异同？

逻辑回归处理的是分类问题，线性回归处理的是回归问题。

逻辑回归中，因变量取值是一个二元分布，给定自变量和超参数后，得到因变量的期望，并基于此期望来处理预测分类结果。

线性回归中，使用近似项来处理回归问题。

逻辑回归中的因变量为离散的，而线性回归中的因变量是连续的。

当然也有相同之处。二者都使用了极大似然估计来对训练样本进行建模；
二者在求解超参数的过程中，都可以使用梯度下降的方法，这也是监督学习中一个常见的相似之处。

问题：当使用逻辑回归处理多标签的分类问题时，有哪些常见做法，分别应用于哪些场景，它们之间又有怎样的关系？

首先，如果一个样本只对应一个标签，可以假设每个样本属于不同标签的概率服从于几何分布，使用多项式逻辑回归来进行分类。一般来说，多现实逻辑回归具有参数冗余的特点。多项式逻辑回归实际是二分类逻辑回归在多分类标签分类下的一种拓展。

当存在样本可能属于多个标签的情况时，我们可以训练k个二分类的逻辑回归分类器。在第i个分类器用以区分每个样本是否可以归为第i类，训练该分类器时，需要把标签重新整理为“第i类标签”与“非第i类标签”两类。通过这样的办法，可以解决每个样本可能拥有多个标签的情况。

3 决策树

知识点：信息论，树形数据结构，优化理论

问题：决策树有哪些常用的启发函数？

常用的决策树算法有ID3，C4.5，CART，它们构建所使用的的启发式函数各是什么？除了构建准则之外，它们之间的区别于联系是什么？

这几种决策树构造时使用的准则：

• ID3——最大信息增益

• C4.5——最大信息增益比

• CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。但与ID3,C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切成两份，分别进入左右子树。

对比三种决策树的构造准则，总结三者之间的差异：

• ID3采用信息增益作为评价指标，会倾向于取值较多的特征。因此，信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性越高，也就是条件熵越小。实际应用中是一个缺陷。

• C4.5实际是对ID3进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力。

• 从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续性变量。

• ID3和C4.5只能用于分类任务，而CART（分类回归树）不仅可以用于分类，也可以用于回归任务（回归树使用最小平方误差准则）

• 从实现细节、优化过程等角度：
  ID3对于样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理；
  ID3和C4.5可以在每个结点产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，因此最后会形成一颗二叉树，且每个特征可以被重复使用；
  ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。

问题：如何对决策树进行剪枝？

预剪枝，即在生成决策树的过程中提前停止树的增长；
后剪枝，是在已生成的过拟合决策树上进行剪枝，得到简化版的剪枝决策树。

• 预剪枝
  核心思想是在书中结点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树。此时可能存在不同类别的样本同时存于结点中，按照多数投票的原则判断该节点所属类别。预剪枝对于何时停止决策树的生长有以下几种方法：
  （1）当树到达一定深度的时候，停止树的生长；
  （2）当到达当前结点的样本数量小于某个阈值的时候，停止树的生长；
  （3）计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继续扩展。

预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模问题。但如何准确地估计何时停止树的生长，针对不同问题会有很大差别，需要一定经验判断。且预剪枝存在一定局限性，有欠拟合的风险，虽然当前的划分会到导致测试集准确率降低，但在之后的划分中，准确率可能会有显著上升。

后剪枝的核心思想是让算法生成一颗完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断。同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝后准确率有所提升，则进行剪枝。相比于预剪枝，后剪枝通常可以得到泛化能力更强的决策树，但时间开销会更大。

常见的后剪枝方法包括错误率降低剪枝（REP）,悲观剪枝（PEP），代价复杂度剪枝（CCP），最小误差剪枝（MEP），CVP，OPP等。

代价复杂剪枝主要包含步骤：