绪论

1.2 基本术语

1. 数据集(data set)
2. 示例(instance), 样例(sample)
3. 属性(attribute),特征(feature)
4. 属性值(attribute value)
5. 属性空间(attribute space), 样本空间(sample space)
6. 特征向量(feature vector)
7. 假设(hypothesis)
8. 真相(ground-truth)
9. 学习器(learner)
10. 标记(label)
11. 样例(example)
12. 标记空间(label space)
13. 分类(classification),回归(regression)
14. 聚类(clustering),簇(cluster)

15. 监督学习(supervised learning), 无监督学习(unsupervised learning)

16. 根据训练数据是否拥有标记信息，学习任务可大致划分为两大类。分类和回归是前者的代表，聚类是后者的代表。

1.3 假设空间

1. 归纳学习

2. 侠义上是概念学习，最基本的是布尔概念学习

3. 搜索过程中可以不断删除与正例不一致的假 设、和(或)与反例→致的假设.最终将会获得与训练集一致(即对所有训练样本 能够进行正确判断)的假设，这就是我们学得的结果。即存在着一个与 训练集一致的"假设集合"，我们称之为"版本空间" (version space).

1.4 归纳偏好

1. 奥卡姆剃刀：若有多个假设与观察一致，则选最简单的那个

2. 对于一个学习算法A，若它在某些问题上比学习算法B好，则必然存在另一些问题，在那里B比A好。有趣的是，这个结论对任何算法均成立

3. NFL定理，天下没有免费的午餐

4. $$\sum_{f}E_{ote}(\xi_a|X, f) = 2^{|X| - 1}\sum_{x\in \mathcal{X}-X}P(x)\times 1=\sum_{f}E_{ote}(\xi_b|X, f)$$

5. 无论算法A多聪明，算法B多笨拙，他们的期望性能是相同的。

6. NFL 定理有一个重要前提:所有"问题"出现的机会相 同、或所有问题同等重要.但实际情形并不是这样.很多时候，我们只关注自己正在试图解决的问题(例如某个具体应用任务)，希望为它找到一个解决方案， 至于这个解决方案在别的问题、甚至在相似的问题上是否为好方案，我们并不关心.

7. 学习算法自身的归纳偏好与问题是否相配，往往会起到决定性的作用.

1.5 发展历程

1. 推理期
2. 知识期

3. 学习期

4. 连接主义

5. 符号主义
6. 统计学习

7. 支持向量机(Support Vector Machine，简称 SVM) 以及更一般的"核方法" (kernel methods).

8. 21世纪

9. 深度学习

10. 数据挖掘

11. 数据挖掘与机器学习的联系.数据挖掘领域在二十世纪九十年 代形成，它受到很多学科领域的影响，其中数据库、机器学习、统计学无疑影 响最大. 数据挖掘是从海量数据中发掘知识，这就必然涉及对"海量数据"的管理和分析.大体来说，数据库领域的研究为数据挖掘提供数据管 理技术?而机器学习和统计学的研究为数据挖掘提供数据分析技术.由于统计学界的研究成果通常需要经由机器学习研究来形成有效的学习算法，之后再进入数据挖掘领域，因此从这个意义上说，统计学主要是通过机器学习对数据挖掘发挥影响，而机器学习领域和数据库领域则是数据挖掘的两大支撑.

1.6 课后题

1. 上文默认使用了"分类错 误率"作为性能度量来对分类器进行评估，若换用其他性能度量，试证明仍然成立。

$$\sum_{f}E_{ote}(\xi_a|X, f) =\sum_{f}\sum_{h}\sum_{x\in \mathcal{X}-X}P(x) l(h(x), f(x))P(h|X, \xi_a) \\ = \sum_{x\in \mathcal{X}-X}P(x)\sum_{f}\sum_{h}l(h(x), f(x))P(h|X, \xi_a)\\ =\sum_{x\in \mathcal{X}-X}P(x)\sum_{h}P(h|X, \xi_a)\sum_{f}l(h(x), f(x))\\ =2^{|X| - 1}\sum_{x\in \mathcal{X}-X}P(x)\sum_{h}(l(h(x),h(x)) + l(h(x),1 - h(x))))P(h|X, \xi_a)\\ =2^{|X| - 1}\sum_{x\in \mathcal{X}-X}P(x)\sum_{h}C\times P(h|X, \xi_a)\\ =2^{|X| - 1}C\sum_{x\in \mathcal{X}-X}P(x)\times 1\\ $$

所以也成立，注意这里暗含了条件$l(0,0)=l(1,1), l(0,1) = l(1, 0)$。

2 模型评估与选择

2.1 经验误差与过拟合

1. 经验误差和泛化误差

2. 我们把 学习器的实际预测输出与样本的真实输出之间的差异称为"误差" (error), 学习器在训练集上的误差称为"训练误差" (training error)或"经验误 差" (empirical error) ，在新样本上的误差称为"泛化误差" (generalization error).

3. 过拟合

4. 当学习器把训练样本学得"太 好"了的时候，很可能巳经把训练样本自身的一些特点当作了所有潜在样本都 会具有的一般性质，这样就会导致泛化性能下降。与"过拟合"相对的是"欠拟合(underfitting)，这 是指对训练样本的一般性质尚未学好

5. 证明：

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

7. 错误率和精度

8. $$错误率 = \frac{\alpha}{N} \\ 精度 = 1 - \frac{\alpha}{N}$$

2.2 评估方法

2.2.1 留出法

1. 使用留出法时，一般要采用若干次随机划分、重复进行实验评估后取平均值作 为留出法的评估结果.

2.2.2 交叉验证法

1. 
2. 留一法

2.2.3 自助法

1. 给定包含 m 个样 本的数据集D ， 我们对它进行采样产生数据集 D': 每次随机从D 中挑选一个 样本将其拷贝放入D'然后再将该样本放回初始数据集 D 中，使得该样本在下次采样时仍有可能被采到;这个过程重复执行 m 次后我们就得到了包含m个样本的数据集 D'，这就是自助采样的结果。
2. 由于$\lim_{m\rightarrow \infty}(1 - \frac{1}{m})^m = \frac{1}{e}$, 所以有1/3的样本没有出现在训练集。实际评估的模型与期望评估的模型都使用 m 个训练样本，而我们仍有数据总量约 1/3 的、没在训 练集中出现的样本用于测试。
3. 自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差。在数据集较小、难以有效划分训练/测试集时很有用;

2.3 性能度量

1. 衡量模型泛化能力的评价标准，这就是性能度量(performance measure).

2. 均方误差：

3. $$E(f;D)=\frac{1}{m}\sum_{i=1}^{m}(f(x_i) - y _i)^2\\ E(f;\mathcal{D}) = \int_{x\sim \mathcal{D}}(f(x) - y)^{2}p(x)dx$$

2.3.1 错误率与精度

• 样例集D

$$E(f;D)=\frac{1}{m}\sum_{i=1}^{m}I(f(x_i) \neq y _i) \\ acc(f;D) = \frac{1}{m}\sum_{i=1}^{m}I(f(x_i) = y _i) = 1 - E(f;D)$$

• 数据分布$\mathcal{D}$

$$E(f;\mathcal{D})=\int_{x\sim \mathcal{D}}I(f(x_i) \neq y _i)p(x)dx \\ acc(f;\mathcal{D}) = \int_{x\sim \mathcal{D}}I(f(x_i) = y _i)p(x)dx = 1 - E(f;\mathcal{D})$$

2.3.2 查准率、查全率、F1

1. 查准率、查全率

2. 查准率：检索出的信息中有多少比例是用户感兴趣的

3. 查全率：用户感兴趣的信息中有多少被检索出来了

4. 真正例(true positive)、假正例(false positive)、真反倒(true negative)、 假反例(false negative)

5. 混淆矩阵

   

6. $TP + TN + FP + FN = N$

7. $查准率P = \frac{TP}{TP + FP}$

8. $查全率R=\frac{TP}{TP + FN}$

9. 查准率高时，查全率往往低；查全率高时候，查准率往往低。

10. P-R线

    • 
    • 若一个学习器的 P-R 曲线被另一个学习器的曲线完全"包住" ， 则可断言 后者的性能优于前者

11. F1度量

12. $$\frac{1}{F1}=\frac{1}{2}(\frac{1}{P} + \frac{1}{R}) \\ F1 = \frac{2\times P \times R}{P+R}$$

13. $$\frac{1}{F_{\beta}}=\frac{1}{1+\beta^2}(\frac{1}{P} + \frac{\beta^2}{R}) \\ F_{\beta} = \frac{(1+\beta^2)\times P \times R}{(\beta^2 \times P) + R}$$

14. 调和平均更重视较小值，$\beta < 1$时查准率更大影响，$\beta > 1$时，查全率有更大的影响。

15. marco和micro

16. 宏 $$macro{-P} = \frac{1}{n}\sum_{i = 1}^n P_i\\ macro{-R} = \frac{1}{n}\sum_{i = 1}^n R_i\\ macro{-F1} = \frac{2\times macro{-P}\times macro{-R}}{macro{-P} + macro{-R}}$$

17. 微 $$micro{-P} = \frac{\overline{TP}}{\overline{TP}+\overline{FP}}\\ micro{-R} = \frac{\overline{TP}}{\overline{TP}+\overline{FN}}\\ micro{-F1} = \frac{2\times micro{-P}\times micro{-R}}{micro{-P} + micro{-R}}$$

2.3.3 ROC与AUC

1. 真正例率、假正例率

$$TPR = \frac{TP}{TP + FN}\\ FPR = \frac{FP}{TN + FP}$$

1. ROC曲线

• 若一个学习器的 ROC 曲线被另一 个学习器的曲线完全"包住"， 则可断言后者的性能优于前者

• 若两个学习器 的 ROC 曲线发生交叉，则难以-般性地断言两者孰优孰劣. 此时如果一定要进行比较， 则较为合理的判据是比较 ROC 曲线下的面积，即 AUC

• $$AUC = \frac{1}{2}\sum_{i = 1}^{m - 1}(x_{i+1}-x_i)(y_i + y_{i + 1})$$

• $$\mathcal{l}_{rank} = \frac{1}{m^+m^-}\sum_{x^+\in D^+}\sum_{x^- \in D^-}(I(f(x^+) < f(x^-) + \frac{1}{2}I(f(x^+ )=f(x^-)))$$

  这对应着ROC曲线上面部分的面积。

• $$AUC = 1-\mathcal{l}_{rank}$$

2.3.4 代价敏感错误与代价曲线

1. 代价矩阵

2. 

3. $$E(f;D;cost)=\frac{1}{m}(\sum_{x_i \in D^+} I(f(x_i) \neq y_i)cost_{01} + \sum_{x_i \in D^-} I(f(x_i) \neq y_i)cost_{10})$$

4. 代价曲线

5. $$P_{(+)cost}=\frac{p \times cost_{01}}{p \times cost_{01} + (1 - p)\times cost_{10}}\\ cost_{norm}=\frac{FNR\times p \times cost_{01}+FPR\times(1-p)\times cost_{10}}{p\times cost_{01}+(1-p)\times cost_{10}}$$

6. $$cost_{norm}=FNR\times P_{(+)cost}+FPR\times (1-P_{(+)cost}) \\=(FNR-FPR)P_{(+)cost}+FPR$$

7. 

8. AUC表示了期望总体代价

9. $$AUL = \int cost_{norm}dP_{(+)cost}$$

   AUL代表了阈值固定时的期望总体代价，$AUC=min(AUL)$, 表示了所有可能性里面最小的代价期望。

2.4 比较检验

统计假设检验：统计假设检验(hypothesis test)为我们进行学习器t性能比较提供了重要依 据.基于假设检验结果我们可推断出，若在测试集上观察到学习器 A 比 B 好， 则 A 的泛化性能是否在统计意义上优于 B，以及这个结论的把握有多大。

2.4.1 假设检验

1. $$P(\hat\epsilon;\epsilon)=C(m, \hat\epsilon\times m) \epsilon^{\hat\epsilon\times m}(1-\epsilon)^{m-\hat\epsilon\times m}$$

2. 检验方法

3. 单次：二项检验，采用p值的方法

4. 多次：使用t检验 $$\mu = \frac{1}{k}\sum_{i=1}^k\hat\epsilon_i\\ \sigma^2=\frac{1}{k - 1}\sum_{i = 1}^k(\hat\epsilon_i-\mu)^2\\ t=\frac{\sqrt{k}(\mu-\epsilon_0)}{\sigma}$$ 其中t符合自由度为k-1的t分布，之后进行双侧检验

2.4.2 交叉验证t检验

1. 用于比较不同学习器的性能

2. 检验方法

3. $$\Delta_i=\epsilon_i^A-\epsilon_i^B\\ \mu=\frac{1}{k}\sum_{i=1}^k\Delta_i\\ \gamma_t = |\frac{\sqrt{k}\mu}{\sigma}|$$

4. 5*2折交叉验证

2.4.3 McNemar检验

1. $$\gamma_{x^2}=\frac{(|e_{01}-e_{10}| - 1)^2}{e_{01}+e_{10}}$$

2. -1为连续性修正

2.4.4 Friedman检验和Nemenyi后续检验

1. 在一组数据集上对多个算法进行比较

2. Friedman 检验

3. Nemenyi检验

4. 

2.5 偏差与方差

1. 偏差(2.40)度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力。
2. 方差(2.38)度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响;
3. 方差(2.38)度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的 影响;

4. 泛化误差可分解为偏差、方差与噪声之和.

5. $$E(f;D)=E_D((f(x;D)-y_D)^2) \\=E_D((f(x;D) - \bar f(x) + \bar f(x) -y_D)^2) \\=E_D((f(x;D)-\bar f(x))^2)+E_D((\bar f(x) - y_D)^2)+2E_D((f(x;D) - f(x))(f(x) - y_D)) \\=E_D((f(x;D)-\bar f(x))^2)+E_D((\bar f(x) - y + y - y_D)^2) \\=E_D((f(x;D)-\bar f(x))^2)+E_D((\bar f(x) - y)^2)+E_D((y-y_D)^2)+2E_D((\bar f(x) - y)(y - y_D)) \\=E_D((f(x;D)-\bar f(x))^2)+E_D((\bar f(x) - y)^2)+E_D((y-y_D)^2) \\=var(x)+bias^2(x)+\epsilon^2$$

6. 注意这里有个假设就是$E_D(y - y_D) = 0$,即噪声的期望为0，如果不为0这个定律不成立。

7. 偏差一方差窘境