监督学习Supervised learning

1.1 监督学习(supervised learning）

指从标注数据中学习预测模型的机器学习问题。标注数据表示输入输出的对应关系，预测模型对给定的输入产生相应的输出。监督学习的本质是学习输入到输出的映射的统计规律。

1.1.1 特征空间(feature space)

每个具体的输入是一个实例(instance)，通常由**特征向量(feature vector)**表示。所有特征向量存在的空间称为特征空间(feature space)。特征空间的每一维对应于一个特征。

• 有时假设输入空间与特征空间为相同的空间，对它们不予区分;

• 有时假设输入空间与特征空间为不同的空间，将实例从输入空间映射到特征空间。

模型实际上都是定义在特征空间上的。

1.1.2 符号说明

在监督学习中，将输入与输出看作是定义在输入（特征）空间与输出空间上的随机变量的取值。

• 输入输出变量用大写字母表示，习惯上输入变量写作X，输出变量写作Y。
• 输入输出变量的取值用小写字母表示，输入变量的取值写作α，输出变量的取值写作y。

变量可以是标量或向量，都用相同类型字母表示。

• 输入实例x的特征向量记作

  KaTeX parse error: {align} can be used only in display mode.

  $x^{(i)} $ 表示 x 的第 i 个特征。

• 注意 $x^{(i)} $ 与 $x_{i} $ 不同, 本书通常用 $x_i$ 表示多个输入变量中 的第 i 个变量, 即

  $x_i={\left(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}\right)}^{\mathrm{T}}$

训练集的表示

监督学习从训练数据(training data)集合中学习模型，对测试数据(test data)进行预测。训练数据由输入(或特征向量)与输出对组成，训练集通常表示为

KaTeX parse error: {align} can be used only in display mode.

输入与输出对又称为样本(sample）或样本点。

根据输入输出变量的不同类型，对预测任务给予不同的名称:

1. 输入变量与输出变量均为连续变量的预测问题称为回归问题;
2. 输出变量为有限个离散变量的预测问题称为分类问题;
3. 输入变量与输出变量均为变量序列的预测问题称为标注问题。

训练数据与预测数据被看作是依联合概率分布P(X, Y)独立同分布产生的。统计学习假设数据存在一定的统计规律，X和Y具有联合概率分布就是监督学习关于数据的基本假设。

1.1.3 假设空间

监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间(hypothesis space)。

具体描述可以是条件分布形式也可是决策函数形式

1. 决策函数 $\quad Y=f(X) $
   预测形式 $\quad y=f(x) $
2. 条件概率分布 $P(Y \mid X) $
   预测形式 $ \quad \arg \max _{y} P(y \mid x) $

1.1.4 监督学习的实现步骤

1.得到一个有限的训练数据集合

2.确定模型的假设空间，也就是所有的备选模型

3.确定模型选择的准则，即学习的策略

4.实现求解最优模型的算法

5.通过学习方法选择最优模型

6.利用学习的最优模型对新数据进行预测或分析

1.2 统计学习三要素

1. 模型（假设空间）

   决策函数

   F = { f ∣ Y = f θ ( X ) , θ ∈ R n } F = \left\{f \mid Y = f_{\theta}(X), \theta \in R^{n}\right\} F={f∣Y=fθ​(X),θ∈Rn}

   参数向量$\theta$取值于 n 维欧氏空间$ \mathbf{R}^{n}$ ,称为参数空间（parameter space）。用来确定模型。

   条件概率分布

   F = { P ∣ P θ ( Y ∣ X ) , θ ∈ R n } F = \left\{P \mid P_{\theta}(Y \mid X), \theta \in R^{n}\right\} F={P∣Pθ​(Y∣X),θ∈Rn}

2. 策略

   引入损失函数与风险函数的概念。损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。

   • 0-1损失函数
     $L(Y, f(X))=\left{1,Y≠f(X) 0,Y=f(X)

     \right. $

   • 平方损失函数
     $ L(Y, f(X))=(Y-f(X))^{2} $

   • 绝对损失函数
     $ L(Y, f(X))=|Y-f(X)| $

   • 对数损失函数
     $ L(Y, P(Y \mid X))=-\log P(Y \mid X) $

     目的

   • 经验风险最小化：

     ${\min }_{f\in F}\frac{1}{N}{\sum }_{i=1}^{N}L\left(y_i,f\left(x_i\right)\right)$

     结构风险最小化:

     ${\min }_{f\in F}\frac{1}{N}{\sum }_{i=1}^{N}L\left(y_i,f\left(x_i\right)\right)+\lambda J(f)$

     加入正则项，防止过拟合

3. 算法:
   挑选一个合适的算法,使得可以求解最优模型

   训练误差:

   $\frac{1}{N}{\sum }_{i=1}^{N}L\left(y_i,\hat{f}\left(x_i\right)\right)$

   测试误差

   $\frac{1}{N^{\prime }}{\sum }_{i=1}^{N^{\prime }}L\left(y_i,\hat{f}\left(x_i\right)\right)$

1.3 模型评估与选择（Model evaluation and model selection）

如果一味追求提高对训练数据的预测能力，所选模型的复杂度则往往会比真模型更高。这种现象称为过拟合(over-fitting)。过拟合是指**学习时选择的模型所包含的参数过多，以至出现这一模型对已知数据预测得很好，但对未知数据预测得很差的现象。**可以说模型选择旨在避免过拟合并提高模型的预测能力。

1.4 正则化与交叉验证（Regularization and cross validation)

1.4.1 最小化结构风险

$\frac{1}{N}{\sum }_{i=1}^{N}L\left(y_i,f\left(x_i\right)\right)+\lambda J(f)$

1.4.2 交叉验证

数据集随机划分为3部分: 训练集\测试集\验证集

1.5 泛化能力(generalization ability)

1.5.1 介绍

学习方法的泛化能力(generalization ability)是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。

• 现实中常通过测试误差来评价学习方法的泛化能力。但这种评价是依赖于测试数据集的。因为测试数据集是有限的，很有可能由此得到的评价结果是不可靠的。
• 因此统计学习理论试图从理论上对学习方法的泛化能力进行分析。

首先给出泛化误差的定义。如果学到的模型是 $\hat{f}$ , 那么用

个模型对末知数据预测的误差即为泛化误插(generalization error)：

R exp ⁡ ( f ^ ) = E P [ L ( Y , f ^ ( X ) ) ] = ∫ X × Y L ( y , f ^ ( x ) ) P ( x , y ) d x   d y Rexp(ˆf)=EP[L(Y,ˆf(X))]=∫X×YL(y,ˆf(x))P(x,y)dx dy

Rexp​(f^​)​=EP​[L(Y,f^​(X))]=∫X×Y​L(y,f^​(x))P(x,y)dx dy​

事实上，泛化误差就是所学习到的模型的期望风险。

1.5.2 泛化误差上界

学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的，简称为**泛化误差上界(generalization error bound)。**具体来说，就是通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。泛化误差上界通常具有以下性质:它是样本容量的函数，当样本容量增加时，泛化上界趋于0;它是假设空间容量(capacity)的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。

定理 1.1 (泛化误差上界) 对二类分桊问题, 当假设空间是有限个函数的集合 $\mathcal{F}=\left{f_{1}, f_{2}, \cdots, f_{d}\right} $ 时, 对任意一个函数 $f\in \mathcal{F}$ , 至少以概率 $ 1-\delta, 0<\delta<1 $, 以下 不等式成立:

$R(f)⩽\hat{R}(f)+\epsilon (d,N,\delta )$

其中,

$\epsilon (d,N,\delta )=\sqrt{\frac{1}{2N}\left(\log d+\log \frac{1}{\delta }\right)}$

其中

R ( f ) = E [ L ( Y , f ( x ) ) ] R ^ ( f ) = 1 N ∑ i = 1 N L ( y i , f ( x i ) ) R(f)=E[L(Y,f(x))]ˆR(f)=1N∑Ni=1L(yi,f(xi))

R(f)=E[L(Y,f(x))]R^(f)=N1​∑i=1N​L(yi​,f(xi​))​

前者代表泛化误差（期望风险），即在其他的数据集上的误差，后者代表经验风险，即在训练集上的误差。

该不等式的含义：期望风险一定是有一个上界的，看这个上界能不能接受，作为选择模型的一个参考。

1.5.3 推导

证明中采用Hoeffding不等式

下面简单介绍一下：

设 $X_{1}, X_{2}, \cdots, X_{N} $ 是独立随机变量, 且 $X_i\in \left[a_i,b_i\right],i=1,2,\cdots ,N$ ; $\bar{X} $是 $ X_{1}, X_{2}, \cdots, X_{N} $的经验均值,即$ \bar{X}=\frac{1}{N} \sum_{i=1}^{N} X_{i} $, 则对任意 t>0 , 以下不等式成立:

$P[E(\bar{X})-\bar{X}⩾t]⩽\exp \left(-\frac{2N^2{t}^2}{{\sum }_{i=1}^N{\left(b_i-a_i\right)}^2}\right)$

可以带入得到

$P\left(t\frac{S_n}{n}-\frac{S_n}{n}⩾t^{\prime }\right)⩽\exp \left(-\frac{2(n{t}^{\prime }{)}^2}{{\sum }_{i=1}^n{\left(b_i-a_i\right)}^2}\right)$

此处$t^{\prime }=\frac{t}{n}=\mathcal{E}$

由于是针对二分类，$X_i\in [0,1]$,因此$b_i-a_i=1$，${\sum }_{i=1}^n{\left(b_i-a_i\right)}^2=n$,可以化简为：$\exp \left(-\frac{2(n t^{\prime}){2}}{\sum_{i = 1}^{{n}\left(b_{i}-a_{i}\right)}{2}}\right) $=$\exp \left(-{2n (t^{\prime}){2}}\right)$

由此可得，

$P(R(f)-\hat{R}(f)⩾\mathcal{E})⩽exp\left(-2N{\mathcal{E}}^2\right)$

希望经验风险尽可能小，由于 F = { f 1 , f 2 , ⋯   , f d } \mathcal{F}=\left\{f_{1}, f_{2}, \cdots, f_{d}\right\} F={f1​,f2​,⋯,fd​}是一个有限集合, 一共有d项，故

KaTeX parse error: {align} can be used only in display mode.

解释部分U≤Σ：一个基本不等式，就像1U2=2≤1+2=3一样。

等价地，KaTeX parse error: {align} can be used only in display mode.

令

$\delta =d\exp \left(-2N{\epsilon }^2\right)$

则

$P(R(f)<\hat{R}(f)+\epsilon )⩾1-\delta$

即至少以概率$ 1-\delta $有 $R(f)<\hat{R}(f)+\epsilon$ , 其中 $\epsilon$ 可以由$\delta =d\exp \left(-2N{\epsilon }^2\right)$得到。

总结：这部分不太常用，因为实际中假设空间一般为无限个函数。

1.6 生成模型与判别模型（Generative model and discriminant model）

生成方法:

$P(Y\mid X)=\frac{P(X,Y)}{P(X)}$

一般只要出现联合概率分布就是生成模型，相当于是从源头上求解。

判别方法:

$ f(X) 或 P(Y \mid X) $

1.7 分类问题（Classification）

• TP—将正类预测为正类数;
• FN―将正类预测为负类数;
• FP—将负类预测为正类数;
• TN―将负类预测为负类数。

评价指标

1.7.2 精确率

预测为正类的样本（predict）中有多少被分对了（true）

$P=\frac{TP}{TP+FP}$

1.7.3 召回率

在实际正类中（true），有多少正类被模型发现了（predict）

$R=\frac{TP}{TP+FN}$

1.7.4 F1值

是精确率和召回率的调和均值，精确率和召回率都高时，F值也会高。

2 F 1 = 1 P + 1 R F 1 = 2 T P 2 T P + F P + F N 2F1=1P+1RF1=2TP2TP+FP+FN

F1​2​F1​​=P1​+R1​=2TP+FP+FN2TP​​

1.8 标注问题（Tagging）

输入:

$x={\left(x^{(1)},x^{(2)},\cdots ,x^{(n)}\right)}^T$

输出:

$y={\left(y^{(1)},y^{(2)},\cdots ,y^{(n)}\right)}^T$

1.9 总结（Summarization）

1. 统计学习路线:设计模型->训练->预测
2. 监督学习与非监督学习的联系与区别 有无label
3. 统计学习三要素:模型、策略、算法
4. 模型的评估:训练误差、验证误差select、测试误差score
5. 正则化与交叉验证 模型复杂度相关
6. 泛化能力:泛化误差上界 假设空间有限个
7. 生成模型与判别模型的联系与区别 P(X,Y)
8. 分类问题:准确率、精确率召回率、F1值
9. 标注问题:序列标注
10. 回归问题:输出为连续值