《机器学习》 - 周志华

机器学习 读书笔记 DOING

---

1 绪论

1.1 引言

机器学习致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。

1.2 基本术语

数据集、样本、属性（特征）、属性值、属性空间（样本空间、输入空间）、特征向量
从数据中学得模型的过程称为“学习”或“训练”
训练数据、训练样本、训练集、假设、真相
预测任务是希望通过对训练集进行学习，建立一个从输入空间到输出空间的映射
测试集、测试样本
泛化、独立同分布

1.3 假设空间

归纳：从特殊到一般的泛化
演绎：从一般到特殊的特化

将学习过程看作一个在所有假设组成的空间中进行搜索的过程，搜索目标是找到与训练集“匹配”的假设；可以有许多策略对这个假设空间进行搜索，例如从顶而下、从一般到特殊或是自底而上、从特殊到一般，搜索过程中可以不断删除与正例不一致的假设、和（或）与反例一致的假设。

可能存在多个假设与训练集一致（训练集是有限的），即存在“假设集合”，称为“版本空间”（version space）

1.4 归纳偏好

通过学习得到的模型对应了假设空间中的一个假设
机器学习算法中对某种类型假设的偏好，称为“归纳偏好”（inductive bias），或简称为偏好
归纳偏好可看着学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或“价值观”

奥卡姆剃刀: 如果有多个假设与观察一致，则选最简单的那个

NFL定理（No Free Lunch Theorem）

$P(h|X,\mathcal A)$表示算法A基于X产生假设h的概率，则在训练集外误差为 $$E_{ote}(\mathcal A|X,f)=\sum_h\sum_{x\in \mathcal X-X}P(x)Ｉ(h(x)\ne f(x))P(h|X,\mathcal A)$$

todo

1.5 发展历程

推理 -> 知识工程 -> 机器学习

机器学习

• 机械学习：信息存储和检索
• 示例学习，类比学习：从指令中学习，通过观察和发现学习
• 归纳学习：从样例中学习，统计学习基本上都属于该类
  
  • 符号主要学习：决策树、基于逻辑的学习
  • 连接主义学习：
  • 统计学习：SVM、核方法

第2章 模型评估与选择

2.1 经验误差与过拟合

错误率：分类错误的样本数占样本总数的比例
精度： = 1 - 错误率
误差：实际预测输出与样本的真实输出之间的差异
训练误差/经验误差：学习器在训练集上的误差
泛化误差：学习器在新样本上的误差

过拟合
欠拟合

模型选择：理想解决方案就是对候选模型的泛化误差进行评估，然后选择泛化误差最小的那个模型

2.2 评估方法

假设测试样本也是从样本真实分布中独立同分布采样而得。测试集应该尽可能与训练集互斥。

留出法

• 一部分作为测试集，一部分作为训练集，采用若干次随机划分、重复进行实验评估后取平均值
• 一般选取2/3~4/5的样本用于训练，剩余用于测试

交叉验证法

k折交叉验证，通常取10
通常随机划分p次，取p次的平均值
留一法，不受随机样本划分方式的影响，比较准确；缺点：训练时间长，由于训练样本原因，其不一定比其他评估方法准确

自助法

针对数据集随机抽取并放回，取与样本空间数量相等的样本数作为训练集，未在训练集中出现的作为测试集
未采用概率为

$$\lim_{m\rightarrow\infty}(1-{1\over m})^m\rightarrow{1\over e}\approx0.368$$
优点：数据集较少不容易划分测试、训练集；对集成学习有好处；
缺点：改变初始数据集的分布，引入估计偏差；

调参与最终模型

两类参数

• 算法参数，超参数，数目在10以内，通常由人工设定多个参数候选值
• 模型的参数，可能非常多，通过学习来产生多个候选模型（如神经网络不同轮数停止）

往往对参数选择一个范围和变化步长，减少评估的值

2.3 性能度量

回归任务常见的性能度量是“均方误差”（mean squared error）

$$E(f;D)={1\over m}\sum_{i=1}^m(f(x_i)-y_i)^2$$ 更一般对于数据分布D和概率密度函数$p(\cdot)$，均方误差可描述为 $$E(f;D)=\int_{x\sim D}(f(x)-y)^2p(x)d(x)$$

• 错误率与精度
  适用于二分类和多分类，错误率是分类错误的样本数占样本总数的比例，精度则是分类正确的样本数占样本总数的比例。
  $$E(f;D)={1\over m}\sum_{i=1}^mI(f(x_i)\ne y_i)$$ $$acc(f;D)={1\over m}\sum_{i=1}^mI(f(x_i)=y_i)=1-E(f;D)$$
• 查准率、查全率与F1
  查准率（准确率）：$P={TP\over TP+FP}$
  查全率（召回率）：$R={TP\over TP+FN}$
  查全率和查准率往往是矛盾的
  P-R图，如果一个被另外一个包住，则后者较好，交叉则难以断言。
  BEP（Break-Even Point）：查全率与查准率相等时的取值
  F1：$F1={2*P*R\over P+R}$
  $F_\beta$：$F_\beta={(1+\beta^2)*P*R\over \beta^2*P + R}$，来源于${1\over F_\beta}={1\over 1+\beta^2}\cdot({1\over P}+{\beta^2\over R})$，$\beta$度量了查全率对于查准率的相对重要性，与算术平均和集合平均比较调和平均更重视较小值
  macro-P\macro-R\macro-F1:基于多次P\R，分别计算平均值$macro-P={1\over n}\sum_{i=1}^nP_i$
  micro-P\micro-R\micro-F1:先基于混淆矩阵计算出平均的TP\FP\TN\FN，然后再进行计算
• ROC与AUC
  
  • ROC受试者工作特征（Receiver Operating Characteristic）:y轴为真正例率TPR，ｘ轴为假正例率FPR $$TPR={TP\over TP+FN};FPR={FP\over TN+FP}$$ 可以理解为正例中找到的比例，以及负例中被判为正例的比例
  • AUC(Area Under ROC Curve) $$AUC={1\over 2}\sum_{i=1}^{m-1}(x_{i+1}-x_i)\cdot (y_i+y_{i+1})$$
    给定$m^+$个正例，$m^-$个负例，令$D^+和D^-$分别表示正反例集合，则排序损失$Loss$定义为 $$l_{rank}={1\over m^+m^-}\sum_{x^+\in D^+}\sum_{x^-\in D^-}(I(f(x^+)<f(x^-))+{1\over 2}I(f(x^+)=f(x^-)))$$ 则有 $$AUC=1-l_{rank}$$
• 代价敏感错误率与代价曲线
  不同类型的错误所造成的后果不同，此时可以为错误赋予“非均等代价”。
  代价曲线图的横轴是取值为$[0,1]$的正例概率代价 $$P(+)cost={p*cost_{01}\over p*cost_{01}+(1-p)*cost_{10}}$$ 纵轴为取值为[0,1]的归一化代价 $$cost_{norm}={FNR*p*cost_{01}+FNR*(1-p)*cost_{10}\over p*cost_{01}+(1-p)*cost_{10}}$$ FNR=1-TPR,是假反例率
  根据每一点(TPR,FPR)，在代价平面上绘制(0,FPR)到(1,FNR)的线段，线段下面的面积即表示该条件下的期望总体代价。所有线段的下界构成的面积即在所有条件下学习器的期望总体代价。

2.4 比较检验

涉及多个方面

• 希望比较为泛化性能，而实验评估的是测试集上的性能，两者未必相同
• 测试集上的性能与测试集的选择有很多关系
• 很多机器算法有一定的随机性，即使相同参数训练也可以会结果不同

假设检验

todo

第3章 线性模型

3.1 基本形式

线性模型可表示为

$$f(x)=w^Tx+b$$
许多功能更为强大的非线性模型可在线性模型的基础上通过引入层级结构或高维映射而得。线性模型可以用元素重要性来解释，因此其具有可解释性。

3.2 线性回归

对于离散属性，若属性值间存在“序”关系，则可通过连续化将其转化为连续值，例如(高,中,矮)转化为(1,0.5,0)，若属性间不存在序关系，则可将其转为k维向量。

线性回归视图学得

$$f(x_i)=wx_i+b,使得f(x_i)\simeq y_i$$ 使用均方误差作为性能度量 $$(w^*,b^*)=arg\min_{w,b}\sum_{i=1}^m(f(x_i)-y_i)^2$$ 均方误差有非常好几何意义，对应于欧几里得距离。基于均方误差最小化来进行模型求解的方法称为“最小二乘法”。求解w和b使用该值最小化的过程称为线性回归模型的最小二乘“参数估计”。

第7章 贝叶斯分类器

7.1 贝叶斯决策论

条件风险，$\lambda_{ij}将真实j类标为i类的所产生的损失$：

$$R(c_i|x) = \sum_{j=1}^N\lambda_{ij}P(c_j|x)$$
任务是寻找准则h使得 $$R(h)=\bolt E_x[R(h(x)|x)]$$
则在每个样本上选择使条件风险最小的类别标记 $$h^*(x)=arg\min_{c\in y}R(c|x)$$
$h^*$贝叶斯最优分类器，$R(h^*)$为贝叶斯风险，$1-R(h^*)$为理论最好性能
使用0-1错误率则有 $$R(c|x)=1-P(c|x)$$
因此最小化分类错误率的贝叶斯最优分类器为 $$h^*(x)=arg\max_{c\in y} P(c|x),即选择后验概率最大的类别标志$$

• 判别式模型，直接建模P(c|x)来预测c，决策树、BP神经网络、SVM
• 生成式模型，先对联合分布P(x,c)建模，然后由此获得P(c|x)

$$P(c|x) = {P(c)P(x|c)\over p(x)}$$
P(c):先验
P(x|c):似然
P(x):证据