3. 经典算法

3.1 支持向量机 ****

1. 空间上线性可分的两类点，在超平面上的投影，仍然是线性可分的吗？***

• 一定是 线性不可分 的，因为 SVM 的分类结果仅依赖支持向量

• 超平面分离定理（SHT）： 对于不相交的两个凸集，存在超平面分离

  • 凸包上的点：样本点 / 两个样本点的连线，三种情况都线性不可分

2. 是否存在一组参数使 SVM 训练误差为 0？***

• 使用高斯核，若不存在两个点在同一位置，存在一组参数，使得 SVM 训练误差为 0

  • 高斯核 $K(x,z)=e^{-||x-z||^2/\gamma^2}$

  • 预测公式 $f(x)=\sum_{i=1}^{m}\alpha_i y^{(i)}K(x^{(i)},x)+b$

  • 固定 $\alpha_=1, b=0$，可证 $||f(x^{(j)})-y^{(j)}||<1$

3. 训练误差为 0 的 SVM 分类器一定存在吗？****

• 问题2 的参数，训练误差为 0，但不一定是满足 SVM 条件的解

  • 不加入松弛变量，能否保持得到的 SVM 训练误差为 0？

  • 能，仍然固定 $b=0$，每个 $\alpha_j$ 都选择很大的值，同时取非常小的 $\gamma$

4. 加入松弛变量的 SVM 训练误差可以为 0 吗？***

• 不一定，因为优化目标改变了，不再是使训练误差最小

• $C\sum_{i=1}^m \xi_i+\frac{1}{2}||w||^2$，当 C 选取较小的值，正则项占据较大权重

3.2 逻辑回归 ***

• 相比于线性回归，有何异同

  • 区别：LR 分类，是对数几率 $\log\frac{p}{1-p}$ 的回归，是广义线性模型

  • 相同：极大似然估计，梯度下降

• 多标签分类

  • 样本只对应一个标签（几何分布）$softmax(x)=\frac{e^{x}}{\sum_{j=1}^k e^x}$

  • 样本可能属于多个标签：k 个二分类 LR

3.3 决策树 ***

• 启发函数（从若干决策树中选取最优，是 NP-Complete 问题）

  • ID3 - information gain - 倾向于取值较多的特征（离散 分类）

    • 经验熵 $H(D)=-\sum_{k=1}^K p_k \log p_k$

    • 信息增益 $g(D,A)=H(D)-H(D|A)$

  • C4.5 - information gain ratio - 惩罚取值过多（离散/连续 分类）

    • 信息增益比 $g_R(D,A)=\frac{g(D,A)}{H_A(D)}$

  • CART - gini - 二值划分（离散/连续 分类/回归）

    • $Gini(D)=1-\sum_{k=1}^n p_k^2$

• 如何剪枝

  • 预剪枝（pre-pruning）max_depth, min_data_in_leaf, min_gain_to_split

  • 后剪枝（post-pruning）泛化能力更强，时间开销更大

    • 错误率降低 REP、悲观 PEP、代价复杂度 CCP、最小误差 MEP、CVP、OPP