《机器学习》笔记(第一部分:绪论、模型评估与选择、线性模型)
1 绪论
1.2 基本术语
数据集 D={xi}i=1m 是一个包含 m 个示例 (instance) 或样本 (sample) 的数据集 (data set). 每个示例用 d 个属性 (attribute) 或特征 (feature) 描述, 属性张成的空间 X 称为属性空间 (attribute space) 或样本空间 (sample space) 或输入空间 (input space). 每个示例 xi=(xij)j=1d 是 d 维样本空间 X=∏iXi 中的一个向量, 称为特征向量注 (feature vector), 其中 xij 是 xi 在第 j 个属性上的取值, 称为属性值 (attribute value). d 称为样本 xi 的维数 (dimensionality).
注 此处的“特征向量”(feature vector) 需要与线性代数中的“特征向量”(eigenvector) 区分.
训 练 从数据中学得模型的过程称为学习 (learning) 或训练 (training). 训练使用的数据称为训练数据 (training data), 单条训练数据称为训练样本 (training sample), 所有训练样本构成训练集 (training set). 训练样本的期待输出称为标记或标签 (label), 拥有标记的示例称为样例 (example). 设 Y 是所有标记的集合, 称为标记空间 (label space) 或输出空间 (output space). 一般用 (xi,yi) 表示第 i 个样例, 其中 yi∈Y 是标记. 若标记空间 Y 是离散的 (亦即 ∣Y∣≤ℵ0) 则称此类学习任务是分类 (classification); 若是连续的 (亦即 ∣Y∣≥ℵ1), 则称是回归 (regression). 二者都是预测 (prediction) 问题, 是希望通过对训练集 {(xi,yi)}i=1m 学习, 建立一个预测映射 f:X→Y.
分类问题 ∣Y∣=2 时称为二分类 (binary classification) 问题, 两类分别为正类 (positive class) 和反类 (negative class). 涉及多个类别时称为多分类 (multi-class classification) 问题. 对二分类任务, 通常令 Y=B={+1,−1} 或 {0,1}.
测 试 学得模型后使用其进行预测的过程叫测试 (testing). 被预测的样本称为测试样本 (testing sample). 学得 f 后对测试例 x∗ 可以得到其预测标记 y∗=f(x∗).
无监督学习 分类和回归的训练数据都有标记信息, 属于监督学习 (supervised learning). 聚类 (clustering) 是将训练集中样本分为若干个簇 (cluster) 的算法, 属于无监督学习 (unsupervised learning).
1.3 假设空间
学得的模型对应了关于数据的某种存在规律, 所以模型亦称假设 (hypothesis), 这种潜在规律称为真实 (ground-truth). 我们的目的是寻找与训练集匹配 (fit) 的假设. 所有假设构成的空间 H 称为假设空间 (hypothesis space), 假设空间里那些与训练集一致的假设的集合称为版本空间 (version space). 一种算法 L 在一个训练集 X 下会产生一个假设 h.
1.4 归纳偏好
版本空间的所有假设在面对测试数据中会各有偏好, 称为归纳偏好 (inductive bias).
设样本空间 X 和假设空间 H 都是离散的. 令 Pr(h∣X,La) 是算法 La 在训练集 X 下产生假设 h 的概率. 给定训练集 X, 假想存在真实目标函数 f (即 x 与 y 的真实对应关系), 定义算法 L 对于某个样本 x∗ 的平均误差为
E(L,x∗∣X,f)=h∑(Pr(h∣X,La)⋅ℓ(h(x∗),f(x∗)))
其中 ℓ(⋅,⋅) 是距离函数.
给定训练集 X, 假想存在真实目标函数 f, 定义算法 L 的训练集外误差 (out-of-training-set error) EOTE 是所有样本 (训练集除外) 的误差之和
EOTE(L∣X,f)=x∈X∖X∑(Pr(x)⋅E(L,x∣X,f))
现在考虑所有可能的真实目标函数 f 的误差总和
E=f∑(Pr(f)⋅EOTE(L∣X,f))
没有免费的午餐定理 (NFL 定理, no free lunch theorem) 假设真实目标函数 f 是均匀分布的. 以二分类问题为例, f 可以取遍 X→B 这 2∣X∣ 个函数. 将误差总和全部展开重组得到
E=x∈X∖X∑(Pr(x)⋅h∑(Pr(h∣X,La)⋅f∑(Pr(f)⋅ℓ(h(x),f(x)))))
以 ℓ(y1,y2)=1y1=y2 为例, 此时 Pr(f)=1/2∣x∣, 且有恰好一半的 f 能使 f(x)=0 或 f(x)=1. 所以
E=x∈X∖X∑(Pr(x)⋅h∑(Pr(h∣X,La)⋅2∣X∣1⋅21⋅2∣X∣))=21x∈X∖X∑(Pr(x)⋅h∑(Pr(h∣X,La)))=21x∈X∖X∑(Pr(x)⋅1)=21−Pr(X)
以上计算的结论是: 如果真实的目标函数 f 是均匀分布的, 那么预测总误差的期望 E 与具体算法 L 无关, 聪明的学习算法在预测期望上与随机乱猜相同. 这是因为“f 均匀分布”这个假设不合理, 每一个现实问题中的 f 各有各的不均匀性. NFL 定理启发我们谈论算法的优劣必须要针对具体的学习问题, 学习算法的优劣与算法本身无关, 而与具体的学习问题强相关.
2 模型评估与选择
2.2 评估方法
首先需要将数据集 D={(xi,yi)}i=1m 分割为训练集 S 和测试集 T.
留出法 (hold-out) 即把 D=S∪T 分割为两个互斥的集合, S∩T=∅. 训练集一般占总量的 66% 至 80%. 经常使用分层采样 (stratified sampling), 即 S 和 T 中正反例的比例相等. 留出法一般需要使用不同的分割方法重复验证, 然后取平均误差.
交叉验证法 (cross validation) 将 D=⋃i=1kDi 划分为 k 个大小相似的互斥子集, ∀i,j,Di∩Dj=∅. 然后每次用 Di 作为测试集, 其余的子集作为训练集. 又称 k-倍交叉验证 (k-fold cross validation). 极端情况下令 k=m, 则 ∀i,∣Di∣=1, 此时成为留一法 (LOO, leave-one-out).
自助法 (bootstrapping) 即在数据集 D 中重复有放回采样 m 次构成测试集 S. 当 m 很大时, 某个样本始终不被采集到的概率是
m→∞lim(1−m1)m=e−1≈37%
然后取测试集 T=D∖S .这样就可以指定 ∣S∣=m 同时保证 ∣T∣ 大概占总量的 37%.
2.3 性能度量