机器学习
绪论
机器学习研究的主要内容，是关于在计算机上从数据中产生模型（model）的算法，即学习算法（learning algorithm）。
《机器学习》一书中，模型泛指从数据中学得的结果，有时将模型称为学习器learner，可以看作学习算法在给定数据和参数空间上的实例化。有些文献，模型指全局性结果，如一棵决策树，模式指局部性结果，如一条规则。
基本术语
数据集 data set：记录的集合
- 示例/样本 instance/sample：关于一个事件或对象的描述。
属性/特征 attribute/feature：反映事件或对象在某方面的表现或性质的事项。
样本空间 sample space：属性张成的空间。
e.g. 把色泽、根蒂、敲声作为三个坐标轴，则张成一个用于描述西瓜的三维空间，每个西瓜都可以找到自己的坐标位置。
一个样本也可以称为样本空间中的一个特征向量 feature vector。
$D={x_1,x_2,…,x_m}$表示包含$m$个示例的数据集，每个示例包含$d$个属性描述。每个示例$x_i=(x_{i1};x_{i2};…;x_{id})$是d维样本空间中的一个向量。
学习/训练 learning/training：从数据中学得模型的过程，这个过程通过执行某个学习算法来完成，学习过程就是为了找出或逼近真相。
训练数据 training data：训练过程中使用的数据
训练样本 training sample
训练集 training set：训练样本组成的集合
标记 label：训练样本的结果信息
拥有了标记label 的示例sample，称为样例example，一般用$(x_u,y_i)$表示第i个样例，$y_i$是示例$x_i$的标记。
$Y$是所有标记label的集合，称为标记空间label space/输出空间
假设 hypothesis
学得的模型对应了关于数据的某种潜在的规律。
真实 ground-truth：客观规律自身
预测模型 prediction model
分类 classification
预测离散值的学习任务。例如好瓜、坏瓜。
- binary classification 二分类
- positive class 正类
- negative class 反类
- multi-class classification 多分类
一般地，预测prediction任务希望通过对训练集training set进行学习，建立一个从输入空间X到输出空间Y的映射。
- binary classification 二分类
回归 regression
预测连续值的学习任务。例如西瓜成熟度0.95、0.37。
测试 testing
testing sample 被预测的样本
聚类 clustering
将训练集中的西瓜分成若干组，每组称为一个簇cluster。
这些自动形成的簇可能对应一些潜在的概念划分，例如“浅色瓜”、“深色瓜”。
监督学习 supervised learning
训练数据拥有标记信息
- 分类、回归
无监督学习 unsupervised learning
训练数据没有标记信息
- 聚类
泛化 generalization
学得模型适用于新样本的能力，称为泛化能力。
通常假设样本空间中全体样本服从一个未知分布(distribution)D，我们获得的每个样本都是独立地从这个分布上采样获得的，即“独立同分布”(independent and identically distributed)
假设空间
归纳 induction
从特殊到一般的泛化(generalization)过程，即从具体的事实归结出一般性规律。
从样例中学习显然是一个归纳的过程，因此亦称归纳学习(induction learning)
演绎 deduction
从一般到特殊的特化(specialization)过程，即从基础原理推演出具体状况。
可以把学习过程看作一个在所有假设(hypothesis)组成的空间中进行搜索的过程，搜索目标是找到与训练集**匹配(fit)**的假设。假设的表示一旦确定，假设空间及其规模大小就确定了。
现实问题中我们常面临很大的假设空间，但学习的过程是基于有限样本训练集进行的，因此可能有多个假设与训练集一致。与训练集一致的假设集合，称之为**版本空间(version space)**。
归纳偏好
对于一个具体的学习算法而言，它必须要产生一个模型。学习算法本身的偏好会起到关键作用。
机器学习算法在学习过程中对某类假设的偏好，称为**归纳偏好(inductive bias)**。
是否存在一般性的原则来引导算法确立“正确”的偏好？
**“奥卡姆剃刀”(Occam’s razor)**原则
奥卡姆剃刀原则是一种常用的、自然科学研究中最基本的原则：若有多个假设与观察一致，则选最简单的那个。
然而，奥卡姆剃刀并非唯一可行的原则，且其本身存在不同的诠释。例如：
- 好瓜↔(色泽 = *) ^ (根蒂 = 蜷缩) ^ (敲声 = 浊响)
- 好瓜↔(色泽 = *) ^ (根蒂 = 蜷缩) ^ (敲声 = *)
这两个假设何者更简单的问题并不简单，需要借助其他机制才能解决。
数据挖掘与机器学习的联系
数据库领域的研究为数据挖掘提供数据管理技术；
机器学习和统计学的研究为数据挖掘提供数据分析技术；(统计学主要通过机器学习对数据挖掘发挥影响)
模型评估与选择
经验误差与过拟合
m个样本，a个样本分类错误
- 错误率(error rate) E = a / m：分类错误的样本数占样本总数的比例
- **精度(accuracy)**：1 - a / m
把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，会导致泛化性能下降。这种现象在机器学习中称为**“过拟合”(overfitting)。“欠拟合”(underfitting)**指对训练样本的一般性质尚未学好。
评估方法
包含$m$个样例的数据集$D={(x_1,y_1), (x_2,y_2),…,(x_m,y_m)}$，如果既要训练，又要测试，需要把数据集$D$进行适当的处理，从中产生出**训练集$S$和测试集$T$**。对数据集$D$的处理方法，有以下常见的几种。
留出法 (hold-out)
留出法直接将数据集$D$划分为两个互斥的集合。在$S$上训练出模型后，用$T$来评估其测试误差，作为对泛化误差的估计。
训练/测试集的划分要尽可能保持数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响，例如在分类任务中至少要保持样本的类别比例相似。如果从采样的角度来看待数据集的划分过程，则保留类别比例的采样方式通常称为**分层采样（stratified sampling)**。若$S$、$T$中样本类别比例差别很大，则误差估计将由于训练/测试数据分布的差异而产生偏差。
即使给定训练/测试集的样本比例后，仍然存在多种划分方式对初始数据集$D$进行分割。因此，单次使用留出法得到的估计结果往往不够稳定可靠。使用留出法，一般要采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果。
常见的做法是将大约${\frac{2}{3}}$~${\frac{4}{5}}$的样本用于训练，剩余样本用于测试。
交叉验证法 (cross validation)
交叉验证法先将数据集$D$划分为$k$个大小相似的互斥子集，每个子集$D_i$都尽可能保持数据的一致性，即从$D$中通过分层采样得到。然后，每次用$k-1$个子集的并集作为训练集，剩下的那个子集作为测试集，这样就可以获得$k$组训练/测试集，最终返回$k$个测试结果的平均值。
交叉验证法评估结果的稳定性和保证性很大程度上取决于k的取值，因此交叉验证法通常又称为**$k$折交叉验证($k$-fold cross validation)。$k$最常用的取值是10，此时称为10折交叉验证**，其他常用的k值有5、20等。
与留出法相似，将数据集$D$划分为$k$个子集同样存在多种划分方式。为减小因样本划分不同而引入的差别，$k$折交叉验证通常要随机使用不同的划分重复$p$次，最终结果是这$p$次$k$折交叉验证结果的均值，常见的有10次10折交叉验证。
自助法 (bootstrapping)
自助法将给定包含$m$个样本的数据集$D$进行采样，产生数据集$D^{‘}$：每次随机从D中挑选一个样本，将其拷贝放入$D^{‘}$，这个过程重复执行$m$次，就得到了数据集$D^{‘}$。
$D$中有一部分样本会多次出现，另一部分样本则不出现。样本在$m$次采样中始终不被采到的概率是$(1-\frac{1}{m})^m$，取极限：$\displaystyle\lim_{x\to\infty}(1-\frac{1}{m})^m={\frac{1}{e}}\approx 0.368$。即通过自助采样，初始数据$D$中约有36.8%的样本不会出现在采样数据集$D^{‘}$中。于是，可将$D^{‘}$用作训练集，剩余样本用作测试集。这样，实际评估的模型与期望评估的模型都使用$m$个训练样本，而仍有数据总量约1/3的、没在训练集中出现的样本用于测试。这样的测试结果，亦称**“包外估计”（out-of-bag estimate)**。
自助法在数据集较小、难以有效划分训练/测试集时很有用；自助集能从初始数据集中产生多个不同的训练集，这对集成学习等方法有很大好处。
然而，自助法产生的数据改变了初始数据集的分布，会引入估计偏差。因此，在初始数据量足够时，留出法和交叉验证法更常用。
调参（parameter tuning）与最终模型
大多数学习算法都有些参数需要设定，参数配置不同，学得模型的性能往往有显著差别。因此，在进行模型评估与选择时，还需要算法参数进行设定，这就是常说的调参。
学习算法的很多参数在实数范围内取值，因此对每种参数配置都训练出模型是不可行的。常用的做法是，对每个参数选定一个范围和变化步长。例如，在$[0, 0.2]$范围内以0.05为步长，则实际要评估的候选参数数值有5个，最终从这5个候选值中产生选定值。显然，这样选定的参数值往往不是最佳值，但这是计算开销和性能估计之间进行折中的结果，通过这种折中，学习过程才变得可行。
在研究对比不同算法的泛化性能时，我们用测试集上的判别效果来估计模型在实际使用时的泛化能力。而把训练数据另外划分为训练集和验证集（validation set），基于验证集上的性能来进行模型选择和调参。
性能度量 (performance measure)
对学习器的泛性能进行评估，不仅需要有效可行的实验估计方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量。
回归任务最常用的性能度量是均方误差（mean squared error）：
$$E(f; D)=\frac{1}{m}\sum_{i=1}^{m}(f(x_i)-y_i)^2$$
更一般地，对于数据分布D和概率密度函数p(·)，均方误差可描述为：
$$E(f; D)=\int_{x\sim D}(f(x)-y)^2p(x)dx$$
错误率与精度
在经验误差与过拟合中，提到了错误率和精度。这是分类任务中最常用的两种性能度量，既适用于二分类任务，也适用于多分类任务。
错误率
$$E(f;D)=\frac{1}{m}\sum_{i=1}^mⅡ(f(x_i)\ne y_i)$$
精度
$$acc(f;D)=\frac{1}{m}\sum_{i=1}^mⅡ(f(x_i)=y_i)=1-E(f;D)$$
更一般地，对于数据分布D和概率密度函数p(·)，错误率和精度可分别描述为
- $$E(f;D)=\int_{x\sim D}Ⅱ(f(x)\ne y)p(x)dx$$
- $$acc(f;D)=\int_{x\sim D}Ⅱ(f(x)=y)p(x)dx=1-E(f;D)$$
查准率(Precision)、查全率(Recall)与F1
对于二分类问题，可将样例根据其真实类别与学习器预测类别的组合划分为**真正例(True Positive)、假正例(False Positive)、真反例(True Negative)、假反例(False Negative)**。
样例总数=$TP+FP+TN+FN$
查准率P
$$P=\frac{TP}{TP+FP}$$
查全率R
$$R=\frac{TP}{TP+FN}$$
基于P和R的**调和平均(harmonic mean)**定义的F1
$$\frac{1}{F1}=\frac{1}{2}(\frac{1}{P}+\frac{1}{R})$$
在一些应用中，对查准率和查全率的重视程度不同。例如，在商品推荐系统中，为了尽可能少打扰用户，更希望推荐内容确实是用户感兴趣的，此时查准率更重要；而在逃犯信息检索系统中， 更希望尽可能少漏掉逃犯，查全率更重要。F1度量的一般形式$F_\beta$，能表达出不同的偏好：
$$\frac{1}{F_\beta}=\frac{1}{1+\beta^2}(\frac{1}{P}+\frac{\beta^2}{R})$$
ROC与AUC
分类过程相当于以某个**截断点(cut point)**将样本分为两部分，前一部分判作正例，后一部分判作反例。
ROC(Receiver Operating Characteristic)
受试者工作特征曲线，根据学习器的预测结果对样例进行排序，按此顺序逐个把样本作为正例进行预测，每次计算出两个重要量的值，分别作为横纵坐标作图，就得到了ROC曲线。