经典算法
SVM
参考 https://zhuanlan.zhihu.com/p/35755150
SVM的基本型：
\[min_{w,b} = \frac{1}{2} ||w||^{2}\] \[s.t. \quad y_i(w^T x_i + b) \leq 1, i=1,2,3...m \]
空间上线性可分的两点，分别向svm的超平面做投影，投影的点在超平面上依然线性可分吗？ > 一定线性不可分
硬间隔和软间隔是指什么？ > SVM的基本形态是一个硬间隔分类器，它要求所有样本都满足硬间隔约束(即函数间隔要大于1)，所以当数据集有噪声点时，SVM为了把噪声点也划分正确，超平面就会向另外一个类的样本靠拢，这就使得划分超平面的几何间距变小，降低模型的泛化性能。除此之外，当噪声点混入另外一个类时，对于硬间隔分类器而言，这就变成了一个线性不可分的问题，于是就使用核技巧，通过将样本映射到高维特征空间使得样本线性可分，这样得到一个复杂模型，并由此导致过拟合（原样本空间得到的划分超平面会是弯弯曲曲的，它确实可以把所有样本都划分正确，但得到的模型只对训练集有效）。 > 为了解决上述问题，SVM通过引入松弛变量构造了软间隔分类器，它允许分类器对一些样本犯错，允许一些样本不满足硬间隔约束条件，这样做可以避免SVM分类器过拟合，于是也就避免了模型过于复杂，降低了模型对噪声点的敏感性，提升了模型的泛化性能。 因为松弛变量是非负的，因此样本的函数间隔可以比1小。函数间隔比1小的样本被叫做离群点，我们放弃了对离群点的精确分类，这对我们的分类器来说是种损失。但是放弃这些点也带来了好处，那就是超平面不必向这些点的方向移动，因而可以得到更大的几何间隔（在低维空间看来，分类边界也更平滑）。显然我们必须权衡这种损失和好处。
松弛变量和惩罚因子是什么？ > 松弛变量：松弛变量表示样本离群的程度，松弛变量越大，离群越远，松弛变量为零，则样本没有离群。 > 惩罚因子：惩罚因子表示我们有多重视离群点带来的损失，当C取无穷大时，会迫使超平面将所有的样本都划分正确，这就退化成了硬间隔分类器。
拉格朗日乘子法是什么？ > 拉格朗日乘数法是一种优化算法，主要运用于解决优化问题，它的基本思想就是用拉格朗日乘子构造一个新的优化函数将原本的约束优化问题转换成等价的无约束优化问题。
什么是对偶问题? > 常一个优化问题可以从两个角度来考虑，即主问题(primal problem)和对偶问题(dual problem)。在约束最优化问题中，常常利用拉格朗日对偶性将原始问题（主问题）转换成对偶问题，通过解对偶问题来得到原始问题的解。这样做是因为对偶问题的复杂度往往低于主问题。
什么是 kernel trick? > \(x_i\) 和 \(x_j\) 在特征空间的內积等于它们在原始的样本空间通过 \(k(x_i,x_j)\) 计算的结果。有了这样的函数，我们不必去计算高维甚至无穷维特征空间中的內积。 d > SVM 基本式的对偶问题为: \[max_{\alpha} \sum_{i=1}^{m}\alpha_{i} - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_i y_j \Phi{x_i}^{T}\Phi_{x_j}\] \[s.t. \sum_{i=1}^{m}\alpha_i y_i = 0\] \[\alpha_i \geq 0, i = 1,2,...,m.\]
逻辑回归
什么是逻辑回归？ > 对数几率回归。对逻辑回归的公式进行整理，得到: \[log\frac{p}{1-p} = \theta^{T}x\] \[p = P(y=1 | x)\] > 逻辑回归通过极大似然来得到最佳参数 \[L(\theta) = \prod_{i:y_{i}=1}p(x_{i})\prod_{i^{\prime}:y_{i^{\prime}}=0}(1-p(x_{i^{\prime}}))\]
使用逻辑回归处理多标签的分类问题时，有哪些常用做法？ > 1. 如果一个样本只对应一个标签，那么可以使用 sofmax regression > 2. 当存在样本属于多个标签的情况，可以训练\(i\)个分类器，第\(i\)个分类器用以区分每个样本是否可以归为第i类。可以训练 softmax regression. 设定一个 threshold，判断每个类别的概率是否高于 threshold.
决策树
决策树有哪些启发函数？ > ID3（最大信息增益） 计算每个特征的信息增益，然后选择信息增益最大的特征来划分样本，完成决策树的增长。 > C4.5（最大信息增益比）。 > CART(最大基尼指数)
信息熵、信息增益、信息增益比、最大基尼系数是什么？ > 1. 信息熵 是度量样本集合不确定度（纯度）的最常用的指标。 > 当前样本集合 D 中第 k 类样本所占的比例为 pk ，则 D 的信息熵定义为 \[ Ent(D) = - \sum_{K=1}^{|y|}p_k log_2^{p_k}\] > 2. 信息增益 表示得知属性 a 的信息而使得样本集合不确定度减少的程度 > 假设离散属性 a 有 V 个可能的取值 {a1,a2,…,aV}；样本集合中，属性 a 上取值为 av 的样本集合，记为 Dv。 \[Gain(D,a) = Ent(D) - \sum_{v=1}^{V}\frac{D^v}{D}Ent(D^v)\] > 信息增益率 = 信息增益/IV(a),说明信息增益率是信息增益除了一个属性a的固有值得来的。 \[IV(a) = -sum_{v=1}^{v}\frac{D^v}{D}log_2\frac{D^v}{D}\] > Gini描述的是数据的纯度 \[Gini(D) = 1 - sum_{k=1}^{n}(\frac{|C_k|}{|D|})^2\] 特征 A 的 Gini指数定义为: \[Gini(D|A) = \sum_{i=1}^{n}\frac{|D_i|}{|D|}Gini(D_i)\]
ID3,C4.5,CART 各自的优缺点是什么？ > ID3倾向于取值较多的特征,因为信息增益放映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性越高，也就是条件熵越小、信息增益越大。 > C4.5实际上是对 ID3 进行优化，通过引入信息增益比，一定程度上对取值较多的特征进行惩罚、避免 ID3 出现过拟合。 > CART 与 ID3,C4.5不同，它是一颗二叉树，采用二元分割法，每一步将数据按照特征 A 的取值切成两份，分别进入左右子树。
Cart 在做 regression 和 classification 的区别是？ > 在分类问题中，CART 使用基尼指数（Gini index）作为选择特征（feature）和划分（split）的依据；在回归问题中，CART 使用 mse（mean square error）或者 mae（mean absolute error）作为选择 feature 和 split 的 criteria。 在分类问题中，CART的每一片叶子都代表的是一个class；在回归问题中，CART 的每一片叶子表示的是一个预测值，取值是连续的。预测值一般是该片叶子所含训练集元素输出的均值。
决策树如何进行剪枝？ > 预剪枝：1. 当树到达一定深度时，停止树的生长；2.当到达当前节点的样本数量小于某个阈值时，停止树的生长；3. 计算每次分裂时测试集的准确度提升，当小于某个阈值时不再继续扩展。 后剪枝：后剪枝的方法有很多，比如代价复杂度剪枝、悲观剪枝、最小误差剪枝等。
Naive Bayes
简述朴素贝叶斯的原理。 > 朴素贝叶斯采用
属性条件独立性的假设，对于给定的待分类观测数据X, 计算在X出现的条件下，各个目标类出现的概率（即后验概率）， 将该后验概率最大的类作为X所属的类。方法是根据已有样本进行贝叶斯估计学习出先验概率\(P(Y)\)和条件概率\(P(X|Y)\)，进而求出联合分布概率P(XY),最后利用贝叶斯定理求解后验概率P(Y|X).朴素贝叶斯“朴素”在哪里？ > 利用贝叶斯定理求解联合概率P(XY)时，需要计算条件概率P(X|Y)。在计算P(X|Y)时，朴素贝叶斯做了一个很强的条件独立假设（当Y确定时，X的各个分量取值之间相互独立），即 \[P(X_1=x_1,X_2=x_2,\cdots,X_j=x_j|Y=y_k) = P(X_1=x_1|Y=y_k) * P(X_2=x_2|Y=y_k),\cdots,P(X_j=x_j|Y=y_k)\]
什么是拉普拉斯平滑法? > 拉普拉斯平滑法是朴素贝叶斯中处理零概率问题的一种修正方式。在进行分类的时候，可能会出现某个属性在训练集中没有与某个类同时出现过的情况，如果直接基于朴素贝叶斯分类器的表达式进行计算的话就会出现零概率现象。为了避免其他属性所携带的信息被训练集中未出现过的属性值“抹去”，所以才使用拉普拉斯估计器进行修正。具体的方法是：在分子上加1,对于先验概率，在分母上加上训练集中可能的类别数；对于条件概率，则在分母上加上第i个属性可能的取值数
朴素贝叶斯中有哪些不同的模型？ > 朴素贝叶斯含有3种模型，分别是高斯模型，对连续型数据进行处理；多项式模型，对离散型数据进行处理，计算数据的条件概率(使用拉普拉斯估计器进行平滑的一个模型)；伯努利模型，伯努利模型的取值特征是布尔型，即出现为ture,不出现为false,在进行文档分类时，就是一个单词有没有在一个文档中出现过。