监督学习的形式化描述
问题描述
- 样本空间\(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 算法如下：
