第一章 机器学习及监督学习概论

1.机器学习方法定义与分类

1.1 机器学习的概念

机器学习(Machine Learning) 是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。

• 以计算机和网络为平台

• 以数据为研究对象

• 以预测和分析数据为目的

• 以方法为中心

• 是多领域的交叉学科

1.2 机器学习方法的步骤

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

2. 确定学习模型的集合--------------------------模型

3. 确定模型选择的准则--------------------------策略

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

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

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

1.3 机器学习方法的分类

2.机器学习方法的基本分类

机器学习一般包括监督学习、无监督学习、强化学习。有时还包括半监督学习、主动学习。

2.1 监督学习(Supervised Learning)

2.1.1 定义

监督学习是指从从标注数据中学习预测模型的机器学习问题，其本质是学习输入到输出的映射统计规律。

2.1.2 相关概念

• 输入空间(Input Space)：输入的所有可能取值的集合

• 实例(Instance)：每一个具体的输入，通常由特征向量(Feature Vector)表示

• 特征空间(Feature Space)：所有特征向量存在的空间

• 输出空间(Output Space)：输出的所有可能取值的集合

根据变量类型的不同：

• 回归问题：输入变量与输出变量均为连续变量的预测问题

• 分类问题：输出变量为有限个离散变量的预测问题

• 标注问题：输入变量与输出变量均为变量序列的预测问题

符号表示：

• 输入变量: $X$；输入变量的取值:$x$

• 输出变量:$Y$；输出变量的取值表示：$y$

• 输入实例$x$的特征向量表示：$x=(x^{(1)},x^{(2)},...,x^{(i)},...,x^{(n)}{)}^T$

• 使用$x_i$表示多个输入变量中的第$i$个变量：$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(i)},...,x_i^{(n)}{)}^T$

• 样本容量为N的训练集：$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

• 监督学习的基本假设：$X$和$Y$具有联合概率分布$P(X,Y)$

• 监督学习的目的：学习一个输入到输出的映射，这一映射用模型表示

• 模型的形式：条件概率分布$P(Y|X)$或者决策函数$Y=f(X)$

• 假设空间(Hypothesis Space)：所有这些可能的模型的集合

2.1.3 监督学习的流程图

2.2 无监督学习(Unsupervised learning)

2.2.1 定义

无监督学习是从无标注数据中学习预测模型的机器学习问题，其本质是学习数据的统计规律或者潜在结构。

监督学习VS无监督学习：

监督学习：

• 标注数据：表示输入输出的对应关系

• 预测模型：对给定输入产生相应输出

• 本质：学习输入到输出的映射统计规律

无监督学习：

• 无标注数据：自然得到的数据

• 预测模型：表示数据的类别、转换或概率

• 本质：学习数据中的统计规律或者潜在结构

2.2.2 相关概念

• 输入空间：$\mathcal{X}$

• 输入变量：$x$;$x\in \mathcal{X}$

• 隐式结构空间：$\mathcal{Z}$

• 输出变量：$z$;$z\in \mathcal{Z}$

• 模型：函数$z=g(x)$,条件概率分布$P(z|x)$或者$P(x|z)$

• 假设空间：所有可能的模型集合

• 样本容量为N的训练集：U={x1,x2,...,xN}U=\{x_1,x_2,...,x_N\}U={x1​,x2​,...,xN​}

2.2.3 无监督学习流程图

2.3 强化学习（Reinforcement learning）

强化学习是指智能系统在与环境的连续互动中学习最优行为策略的机器学习问题。其本质是学习最优行为决策。

3.机器学习方法的三要素

机器学习方法都是由模型、策略和算法构成。可以简单表示为：方法=模型+策略+算法

3.1 监督学习三要素

3.1.1 模型

假设空间：所有可能的条件概率分布或者决策函数，用$\mathcal{F}$表示。

• 若定义为决策函数的集合：F={f∣Y=f(X)}\mathcal{F}=\{f|Y=f(X)\}F={f∣Y=f(X)}

• $\mathcal{F}$由一个参数向量决定的函数族构成：F={f∣Y=fθ(X),θ∈Rn}\mathcal{F}=\{f|Y=f_{\theta}(X),\theta\in{R^n}\}F={f∣Y=fθ​(X),θ∈Rn}

• 参数空间：Θ={θ∣θ∈Rn}\Theta=\{\theta|\theta\in{R^n}\}Θ={θ∣θ∈Rn}

例：线性回归

实例：$x=(x^{(1)},x^{(2)},...,x^{(n)}{)}^T$

决策函数：$f(x)=w^{(1)}{x}^{(1)}+w^{(2)}{x}^{(2)}+...+w^{(n)}{x}^{(n)}+b$

向量形式：$f(x)=wx+b$,其中，$w=(w^{(1)},w^{(2)},...,w^{(n)})$

• 若定义为条件概率的集合：F={P∣P(Y∣X)}\mathcal{F}=\{P|P(Y|X)\}F={P∣P(Y∣X)}

• $\mathcal{F}$由一个参数向量决定的条件概率分布族构成：F={P∣Pθ(Y∣X),θ∈Rn}\mathcal{F}=\{P|P_{\theta}(Y|X),\theta\in{R^n}\}F={P∣Pθ​(Y∣X),θ∈Rn}

例：逻辑回归

实例：$x=(x^{(1)},x^{(2)},...,x^{(n)}{)}^T$

条件概率分布：$P(y\mid x;\theta )=\{\begin{array}{ll}\frac{1}{1+e^{-{\theta }^{\mathrm{T}}x}}& y=1\\ \frac{e^{-{\theta }^{\mathrm{T}}x}}{1+e^{-{\theta }^{\mathrm{T}}x}}& y=0\end{array}$

3.1.2 策略

3.1.2.1 相关概念

• 损失函数：度量模型一次预测的好坏，记作$L(Y,f(X))$;$Y$为真实值，$f(X)$为预测值。

• 风险函数：度量平均意义下模型预测的好坏
  $R_{exp}(f)=E_p[L(Y,f(x)]={\int }_{\mathcal{X}\times \mathcal{Y}}L(y,f(x))P(x,y)dxdy$
  平均就是求数学期望，风险函数就是对损失函数求数学期望

• 经验风险：模型$f(X)$关于训练集的平均损失
  $R_{emp}(f)=\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))$
  其中，训练集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

3.1.2.2 四种常见损失函数

• 0-1 损失函数(0-1 Loss Function)
  $L(Y,f(X))=\{\begin{array}{l}1,Y\ne f(X)\\ 0,Y=f(X)\end{array}$

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

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

• 对数损失函数(Logarithmic Loss Function)
  $L(Y,P(Y|X)=-logP(Y|X)$

3.1.2.3 经验风险的基本策略

$R_{emp}(f)=\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))\to R_{exp}(f)=E_p[L(Y,f(x)],N\to \infty$

根据大数定律，当样本容量N趋于无穷大时，经验损失趋于风险损失。所以在一定程度上可以选取经验风险作为风险函数的估计值。

经验风险最小化：$\underset{f\in \mathcal{F}}{\min }\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))$

当样本容量不足时，仅使经验风险最小化容易过拟合，这里可以引入结构风险。

结构风险：$R_{srm}=\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))+\lambda J(f)$ ；其中，$\lambda J(f)$为惩罚项,$J(f)$为模型复杂度，$\lambda$为惩罚系数

结构风险最小化：${\min }_{f\in \mathcal{F}}\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))+\lambda J(f)$

机器学习就是选取一个目标函数，可以是经验风险函数或结构风险函数，通过优化使其达到最小化，这样我们就得到了最佳模型。

3.1.3 算法

• 算法：如何求解最优模型的问题

• 若优化问题存在显示解析解，算法简易

• 通常是不存在解析解的，需要数值计算方法，比如梯度下降

3.2 无监督学习三要素

• 模型： 函数$z=g_{\theta }(x)$,条件概率分布$P_{\theta }(z|x)或P_{\theta }(x|z)$

• 策略：优化目标函数

• 算法：通常是迭代算法

4.模型的评估与选择

4.1 训练误差与测试误差

训练误差：

• 学习到的模型：$Y=\hat{f}(X)$

• 训练集(Training Set)：$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

• 训练误差(Training Error)：$R_{emp}(\hat{f})=\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,\hat{f}(x_i))$

测试误差:

• 学习到的模型：$Y=\hat{f}(X)$

• 测试集(Test Set)：$T^{\prime }=\{(x_1,y_1),(x_2,y_2),...,(x_{N^{\prime }}，y_{N^{\prime }})\}$

• 测试误差(Test error)：$e_{test}=\frac{1}{N^{\prime }}{\sum }_{i=1}^{N^{\prime }}L(y_i,\hat{f}(x_i))$

误差率与准确率：

• 误差率(Error Rate)：预测错误样本占总样本比例
  $err=\frac{1}{N}{\sum }_{i=1}^{N}I(y_i\ne \hat{f}(x_i))$,其中I是指示函数，即$y_i\ne \hat{f}(x_i)$时为1,否则为0

• 准确率(Accuracy): 预测正确样本占总样本比例
  $acc=\frac{1}{N}{\sum }_{i=1}^{N}I(y_i=\hat{f}(x_i))$

注：$err+acc=1$

4.2 过拟合与模型选择

例：真实函数为$y=sin(2\pi x)$,样本为$y_i=sin(2\pi x_i)+{\epsilon }_i$，训练集为

$T=\{(x_1,y_1),(x_2,y_2),...,(x_{10},y_{10})\}$

通过M次多项式进行拟合：$f_M(x,w)=w_0+w_{1}x+w_2{x}^2+...+w_M{x}^M={\sum }_{j=0}^M{w}_j{x}^j$

经验风险：$L(w)=\frac{1}{2}{\sum }_{i=1}^N(f_M(x_i,w)-y_i{)}^2$,这里除2是为了方便求导，不影响结果

代入多项式：$L(w)=\frac{1}{2}{\sum }_{i=1}^N({\sum }_{j=0}^M{w}_j{x}_i^j-y_i{)}^2$

选取M={0,1,3,9}的情况，通过最小二乘法求解参数，函数图像如下：

可以看出M=9的时候，函数穿过所有训练样本点，此时训练误差为0，但确实一个过拟合现象。而M=3的时候就能比较好的拟合实际情况。

过拟合(Over-Fitting): 学习所得模型包含参数过多，出现对已知数据预测很好，但对未知数据预测很差的情况。

下面是之前例子模型复杂度和对训练误差和测试误差的图像

训练误差和测试误差与模型复杂度的关系：

可以看出，随着模型复杂度增加，训练误差一直降低，而测误差先减小后增大。因此选择模型，要选择适当的模型复杂度，使得训练误差和测试误差都比较小。

5. 正则化与交叉验证

5.1 正则化

**正则化：**实现结构风险最小化策略

• 一般形式：${\min }_{f\in \mathcal{F}}\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))+\lambda J(f)$

• 经验风险：$\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))$

• 正则化项：$\lambda J(f)$

其中，$\lambda$权衡经验风险和模型复杂度，模型参数越多复杂度越高。$\lambda$越大，正则化后的模型参数越少。

正则化项形式：

• $L_1$范数：$L(w)=\frac{1}{N}{\sum }_{i=1}^N(f(x_i;w)-y_i{)}^2+\lambda ||w|{|}_1$ ；其中，$||w|{|}_1={\sum }_j|w_j|$,是模型参数的绝对值之和

• $L_2$范数：$L(w)=\frac{1}{N}{\sum }_{i=1}^N(f(x_i;w)-y_i{)}^2+\frac{\lambda }{2}||w|{|}_2^2$；其中，$$||w|{|}_2=\sqrt{\sum _j{w}_j^2}$$，$||w|{|}_2^2={\sum }_j{w}_j^2$

$L_1$范数对异常值不敏感，会产生稀疏性（很多参数都等于0），常用于特征选择。

$L_2$范数通常被用来做优化目标函数的正则化项，防止出现过拟合的情况，从而提高模型的泛化能力。它倾向于保持所有权重较小，但不会让它们完全为0。

**奥卡姆剃刀原理：**在模型选择时，选择所有可能模型中，能够很好解释已知数据并十分简单的模型。

5.2 交叉验证

数据充足情况下：数据集可以划分为训练集、验证集、测试集。

• 训练集(Training Set):用以训练模型

• 验证集(Validation Set): 用以选择模型

• 测试集(Test Set):用以最终对学习方法的评估

数据不足情况下：

• 简单交叉验证: 随机将数据分为两部分，即训练集和测试集

• S折交叉验证: 随机将数据分为S个互不相交、大小相同的子集，其中以S-1个子集作为训练集，余下的子集作为测试集。将这一过程对可能的S种选择重复进行；最后选出S次评测中平均测试误差最小的模型。

• 留一交叉验证: S折交叉验证的特殊情况，S=N(N是给定数据集的容量)

6.泛化能力

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

6.1 泛化误差

泛化误差(Genneralization Error)
若所学习到的模型是$\hat{f}$，那么这个模型对未知数据的预测误差即为泛化误差：

$$\begin{array}{rl}{R}_{exp}(\hat{f})& =E_p[L(Y,\hat{f}(X)]\\ & ={\int }_{\mathcal{X}\times \mathcal{Y}}L(y,\hat{f}(x))P(x,y)dxdy\end{array}$$

泛化误差反映了学习方法的泛化能力，如果一种方法学习的模型比另一种方法学习的模型具有更小的泛化误差，那么这种方法就更有效。

6.2 泛化误差上界

泛化误差上界(Genneralization Error Bound)
指泛化误差的概率上界。两种学习方法的优劣，通常比较他们的泛化误差上界。

性质：

• 样本容量的函数：当样本容量增加时，泛化上界趋于0。

• 假设空间容量的函数：假设空间就是所有可能的模型，假设空间容量越大，模型就越难学，泛化误差上界就越大。

考虑如下二分类问题：

• 训练数据集：$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$
  其中，$T
  $是从联合概率分布$P(X,Y)$独立同分布产生的，$X\in{R^n},Y\in{{-1,1}}$。

• 假设空间：F={f1,f2,...,fd}\mathcal{F}=\{f_1,f_2,...,f_d\}F={f1​,f2​,...,fd​},其中，d是函数的个数。

假设$f\in \mathcal{F}$，损失函数为0-1损失

• 期望风险：$R(f)=E[L(Y,f(X))]$

• 经验风险：$\hat{R}(f)=\frac{1}{N}{\sum }_{i=1}^{N}L(y_i,f(x_i))$

• 经验风险最小化：$f_N={\mathrm{argmin}}_{f\in \mathcal{F}}\hat{R}(f)$

• $f_N$的泛化能力：$R(f_N)=E[L(Y,f_N(X))]$

定理(泛化误差上界):

对于二分类问题，当假设空间是有限个函数的集合F={f1,f2,...,fd}\mathcal{F}=\{f_1,f_2,...,f_d\}F={f1​,f2​,...,fd​}时，对$\forall f\in \mathcal{F}$,至少以概率$1-\delta ,0<\delta <1$,以下不等式成立：

$R(f)\le \hat{R}(f)+\epsilon (d,N,\delta )$ ，其中 $\epsilon (d,N,\delta )=\sqrt{\frac{1}{2N}(logd+log\frac{1}{\delta })}$

生成模型与判别模型

7.1 生成模型和判别模型

生成模型(Gennerative Model)
由数据学习联合分布概率$P(X,Y)$,然后求出$P(Y|X)$作为预测模型:

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

**典型的生成模型：**朴素贝叶斯法、隐马尔科夫模型

注： 输入和输出变量要求为随机变量

判别模型（Discriminative Model）

由数据直接学习决策函数$f(X)$或者条件概率分布$P(Y|X)$作为预测模型

**典型的判别模型： **K近邻法、感知机、决策树等

注： 不需要输出和输出变量为随机变量

7.2 生成模型VS判别模型

生成模型：

• 所需数据量比较大

• 可还原出联合概率分布$P(X,Y)$

• 收敛速度更快

• 能反映同类数据本身的相似度

• 隐变量存在时，仍可用生成模型

判别模型：

• 所需样本的数量少于生成模型

• 可直接面对预测，准确率更高

• 可简化学习问题

• 不可以反映数据本身的特性

8.监督学习应用

8.1 分类问题

分类准确率

对于给定测试数据集，分类器正确分类的样本数与总样本数之比称为分类准确率：

$r_{test}=\frac{1}{N^{\prime }}{\sum }_{i=1}^{N^{\prime }}I(y_i=\hat{f}(x_i))$

二分类问题：

对于二类分类问题，常用的评价指标是准确率(precision)与召回率(recall)。通常以关注的类为正类，其他类为负类

• 准确率： $P=\frac{TP}{TP+FP}$

• 召回率：$R=\frac{TP}{TP+FN}$

• 调和值：$\frac{2}{F_1}=\frac{1}{P}+\frac{1}{R}$

准确率和召回率都高时，F1值也会高。

方法：

• 感知机

• k近邻法

• 朴素贝叶斯

• 决策树

• 逻辑回归

应用：

• 银行业务

• 网络安全

• 图像处理

• 手写识别

• 互联网搜索

8.2 标注问题

标注(也是一个监督学习问题。可以认为标注问题是分类问题的一个推广，标注问题又是更复杂的结构预测问题的简单形式。标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。

方法：

• 隐马尔科夫模型

• 条件随机场

应用：

• 信息抽取

• 自然语言处理

8.3 回归问题

回归(regression)是监督学习的另一个重要问题。回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生的变化。

• 类型：
  - 按输入变量个数：一元回归、多元回归
  - 按输入和输出变量之间关系：线性回归、非线性回归

• 损失函数：平方损失

• 应用：商务领域