机器学习笔记：模型评估与选择

• 机器学习笔记：模型评估与选择
• • 1 绪论
  • 2 模型评估与选择
  • • 2.1 经验误差与过拟合
    • 2.2 评估方法
    • 2.3 性能度量

• 模型：全局性结果。
• 模式：局部性结果（例如一条规则）。
• 机器学习的方法：所谓的无监督学习和有监督学习实际上就是有没有标记信息（即y值）
  1. 分类及回归
  2. 聚类（和分类最不一样的地方在于它事先不知道y的值）
• 机器学习的目的：使学得的模型能更好的适用于“新样本”。
• 泛化能力：是指学得模型适用于新样本得能力。
• 假设：学得模型对应了关于数据的某种潜在的规律。
• 假设空间：所有假设组成的空间。
• 版本空间：可能有多个假设与训练集一致“假设集合”或“版本空间”
• 归纳偏好：实际上就是机器学习算法在从版本空间中选取一个模型的时候，用的是什么方法。
  • 奥卡姆剃刀：若多个假设与观察一致，则选最简单的那个

一、误差

• 训练误差、经验误差：学习器在训练集上的误差
• 泛化误差：学习器在新样本上的误差

二、机器学习的目的

实际上我们想要的学习器是在新样本上表现很好对的学习器。

三、什么是不好的学习器：

1. 过拟合：学习能力过强，是机器学习面临的关键障碍
2. 欠拟合：学习能力低下

⭐四、机器学习面临的问题

​ 机器学习面临的问题通常是NP难甚至更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则可通过经验误差最小化获得最优解，这就意味着我们构造性的证明了“P=NP”；因此只要相信“P ≠ neq =NP”，过拟合就不可避免。

• 算法复杂度：完成一件事情需要多少时间。
  1. O(1):常数时间，不随事件复杂度增长。
     1. 四级考试时间不会因为题目的难度变化。
  2. O(n):与复杂度线性相关。
     1. 吃一个鸡蛋要用三分钟那么吃三个鸡蛋要用九分钟
  3. O( n c n^{c} nc):多项式时间
  4. O( n n n^{n} nn):指数时间
  5. O(n!):比多项式复杂度还要高很难被接受。
• P和NP问题是什么？
  1. P(deterministic polynomial time):多项式时间内算法一定停止。
  2. NP(non-deterministic polynomial time):算法不一定会在多项式时间里停止
• 最著名的NP问题
  1. TSP(traveling salesman problem)旅行推销商问题
     1. 推销商有N个目的城市
     2. 他需要访问所有城市一次=>（不能多不能少）
     3. 每两座城市都是链接的=>（有权完全图，距离已知）
     4. Q：求出访问所有城市的最短路径
  2. 暴力解法：枚举所有可能性，复杂度O(n!)。
• 到底P=NP是否成立？
  1. 我们相信P=NP是成立的但没有办法证明，不能够使用这个说法。
• ⭐如何证明？
  1. P ⊂ subset ⊂NP根据计算机理论的一些定义，很简单。
  2. NP ⊂ subset ⊂P???
• 延伸阅读
  1. 算法导论（第一章~第三章）简单算法分析基础
  2. 计算理论导引（第三章）丘奇-图灵命题
  3. (http://zh.wikipedia.org/wiki/P/NP)问题简介
• 近似算法
  1. Approximation algorithms,Springer,2001
  2. The design of approximation algorithms

​ 为了对模型进行评估，生成训练集和测试集，生成训练集和测试集的方法有以下几种

• 留出法(hald-out):将数据集D划分成两个互斥的集合，其中一个集合作为训练集一个集合作为测试集（抽样的时候分层抽样）。
• 交叉验证(cross validation):将数据集D划分成k个大小相似的互斥子集。入过D中包含m个样本，且k=m则改交叉验证方法又称为留一法。
• 自助法(bootstrapping):对数据集D进行有放回的抽样形成新的数据集 D ′ D^{'} D′，把数据集 D ′ D^{'} D′看作训练集，D/ D ′ D^{'} D′看作测试集。
• 调参与最终模型

评估学习器 f f f的性能，就是要把学习器预测结果 f ( x ) f(x) f(x)与真是标记 y y y进行比较。

回归任务常用的性能：

• 均方误差(MSE)： 1 m ∑ i = 1 m ( f ( x i ) − y i ) 2 frac{1}{m}sum_{i=1}^{m}(f(x_{i})-y_{i})^{2} m1​∑i=1m​(f(xi​)−yi​)2

  分类任务中常用的性能度量：

• 错误率与精度

  离散：

  错误率： E ( f ; D ) = 1 m ∑ i = 1 m I ( f ( x i ) ≠ y i ) E(f;D)=frac{1}{m}sum_{i=1}^{m}I(f(x_{i})neq y_{i}) E(f;D)=m1​∑i=1m​I(f(xi​)=yi​)

  精确率： a c c ( f ; D ) = 1 m ∑ i = 1 m I ( f ( x i ) = y i ) = 1 − E ( f ; D ) acc(f;D)=frac{1}{m}sum_{i=1}^{m}I(f(x_{i})=y_{i})=1-E(f;D) acc(f;D)=m1​∑i=1m​I(f(xi​)=yi​)=1−E(f;D)

  连续：

  错误率： E ( f ; D ) E(f;cal{D}) E(f;D) = ∫ x ∼ D =int_{xsimcal{D}} =∫x∼D​ I ( f ( x ) ≠ y ) p ( x ) d x I(f(x)neq y)p(x)dx I(f(x)=y)p(x)dx

  精确率： a c c ( f ; D ) acc(f;cal{D}) acc(f;D) = ∫ x ∼ D =int_{xsimcal{D}} =∫x∼D​ I ( f ( x ) = y ) p ( x ) d x I(f(x)= y)p(x)dx I(f(x)=y)p(x)dx = 1 − E ( f ; D ) =1-E(f;cal{D}) =1−E(f;D)

• 查准率、查全率与F1
  查准率 P = T P T P + F P P=frac{TP}{TP+FP} P=TP+FPTP​
  查全率 R = T P T P + F N R=frac{TP}{TP+FN} R=TP+FNTP​

  真实情况	预测结果
  	正例	反例
  正例	T P TP TP	F N FN FN
  反例	F P FP FP	T N TN TN

  P − R P-R P−R图：横轴查全率纵轴查准率，本质上实际上用曲线下面积评价较好但是该面积不方便求解，因此使用“平衡点”。

  平衡点(Break-Even Point) B E P BEP BEP:是查准率 = = == ==查全率的数值。

  F 1 = 2 × P × R P + R = 2 × T P 样例总数 + T P − T N F1=frac{2times Ptimes R}{P+R}=frac{2times TP}{样例总数+TP-TN} F1=P+R2×P×R​=样例总数+TP−TN2×TP​

  对 F 1 F1 F1加权后形成 F β = ( 1 + β 2 ) × P × R ( β 2 × P ) + R F_{beta}=frac{(1+beta^{2})times Ptimes R}{(beta^{2}times P)+R} Fβ​=(β2×P)+R(1+β2)×P×R​； β > 1 beta>1 β>1时查全率更重要，否则相反

• ROC和AUC
  ROC全称是受试者工作特征曲线：其横轴为“假正例率” F P R FPR FPR，纵轴为“真正例率” T P R TPR TPR
  F P R = F P T P + F P FPR=frac{FP}{TP+FP} FPR=TP+FPFP​
  T P R = T P T P + F P TPR=frac{TP}{TP+FP} TPR=TP+FPTP​

  AUC的值即ROC曲线下的面积值

• 代价敏感错误率与代价曲线 color{red}{代价敏感错误率与代价曲线} 代价敏感错误率与代价曲线
  这里是根据任务的领域知识设定一个“代价矩阵”见书p35

• 比较检验具体见书（p37）

  1. 假设检验
  2. 交叉验证t检验
  3. McNemar检验
  4. Friedman检验和Nemenyi后续检验里写自定义目录标题)