监督学习 Supervised Learning(决策树+SVM/Perceptron+AdaBoost)

监督学习的形式化描述

问题描述

  • 样本空间\(X\)(如X为所有的网页集合)和目标空间\(Y\)(Y={个人主页,公司主页,科研机构主页,其他网页})
  • 预测函数\(f:X->Y\)
  • 假设空间\(H=\{h|h:X->Y\}\)

算法输入

  • 训练集合\(D={(x_i,y_i)}_{i=1}^N\),其中\((x_i,y_i)\in X*Y\)

算法输出

  • 根据D中的样本估计"最优"的函数\(h\in H\),使之能够对未出现在D中的样本的标签进行预测

二值分类(Y为类别集合) 回归(Y为实数集合) 结构预测/排序(Y为结构类型/排序)
线性函数\(f(x)=<w,x>\) Perceptron,SVM Ridge regression SVR Structured SVM,Ranking SVM
Decision tree Regression tree LambdaMART
神经网络 神经网络 神经网络 RankNet
叠加函数\(f(x)=\sum_th_t(x)\) AdaBoost Boosted Regression Tree RankBoost

分类模型的评价方法

n折交叉验证

评价准则

预测为正样本 预测为负样本
标注为正样本 TP(true positive) FN(false negative)
标注为负样本 FP(false positive) TN(true negative)
  • \(Accuracy = \frac{TP+TN}{TP+FN+FP+TN}\)
  • \(Precision = \frac{TP}{TP+FP}\)
  • \(Recall = \frac{TP}{TP+FN}\)
  • \(F = \frac{2PR}{P+R}\) 调和平均数

由于数据大多不平衡,Accuracy在所有的预测样本均预测到负样本的时候,会严重偏差。


决策树

分类函数\(f\)为一棵树,称为决策树 中间节点:决策步骤 叶子节点:决策结果、类别标签

给定的训练数据,可能存在多颗能够拟合数据的决策树,那么如何选择呢? 1. 选择最简单的树 2. 拟合精度高的树

选择决策特征

核心步骤:选择合适的特征进行决策,划分数据,生成子节点 合适:尽量大的减少划分后自数据集的混杂度

信息增益(Information gain)

从上图可以看出有以下性质 \[ \begin{aligned} &H(A,X) = H(X,A)\\ &IG(X|A) = IG(A|X)\\ &IG(X|X) = H(X)\\ &IG(X|A) = H(X) + H(A) - H(X,A) \end{aligned} \]

对于上述决策树算法有以下特征: * 贪心策略 * 从根节点开始,已建立的树不再改变 * 数据划分后不再改变 * 每次选择局部信息增益最大的特征划分数据 * 局部最优解 * 递归算法 - 每一个决策节点用相同的策略扩张 * 信息增益IG不是唯一的选择

改进

上述算法只能够处理类别型的特征,对于数值型特征需要划分区间,按照IG最大化的原则选择阈值。 对于过拟合的情况要降低模型复杂度,采用剪枝方法减少节点数目(post-pruning)。


SVM/Perceptron

分类边距Margin:对线性分类器而言,边距就是从分类面到最近的训练样本的距离。 SVM(support vector machine):最大化分类边距,VC理论证明最大边距分类器有较好的泛化能力。

\[ Margin = |x^+-x^-| = |\lambda w|=\frac{2}{<w,w>}\sqrt{<w,w>}=\frac{2}{\sqrt{w,w}} \]

优化目标: \(min_{w,b}|w|^2\),约束条件\(y_i(<w,x_i>+b)\geq 1, for \,i=1,...,N\)

当出现线性不可分的时候,解决方案是容忍错误的发生,采用软边距

优化目标:\(min_{w,b}|w|^2+C\cdot \sum_{i=1}^N\xi_i\),约束条件\(y_i(<w,x_i>+b)\geq 1-\xi_i,\xi_i \geq 0\) \(C\):权衡边距大小与错误容忍度,C变大牺牲边距减少训练集合上的错误


AdaBoost

  • 组会有差异性的弱分类器可以得到强分类器
  • 不同的弱分类器可以通过不同的算法、特征、数据训练得到
  • 弱分类器的预测精度强于随机预测

基本训练过程如下:

AdaBoost 算法如下: