机器学习算法原理、实现与实践——机器学习的三要素

1 模型

在监督学习中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。例如，假设决策函数是输入变量的线性函数，那么模型的假设空间就是这些线性函数构成的函数的集合。

假设空间用$\mathcal{F}$表示。假设空间可以定义为决策函数的集合
$$\mathcal{F}=\{f|Y=f(X)\}$$

其中，$X$和$Y$是定义在输入空间$\mathcal{X}$和输出空间$\mathcal{Y}$上的变量。这时$\mathcal{F}$通常是由一个参数向量决定的函数族
$$\mathcal{F}=\{f|Y=f_{\theta}(X),\theta\in \mathbf{R}^n\}$$

参数向量$\theta$取值于$n$维欧氏空间$\mathbf{R}^n$，称为参数空间（parameter space）。

假设空间也可以定义为条件概率的集合
$$\mathcal{F}=\{P|P(Y|X)\}$$

其中，$X$和$Y$是定义在输入空间$\mathcal{X}$和输出空间$\mathcal{Y}$上的变量。这时$\mathcal{F}$通常是由一个参数向量决定的条件概率分布族

$$\mathcal{F}=\{P|P_{\theta}(Y|X),\theta\in \mathbf{R}^n\}$$

称由决策函数表示的模型为非概率模型，由条件概率表示的模型为概率模型。

2 策略

有了模型的假设空间，机器学习接着要考虑的是按照什么样的准则学习或选择最优的模型。
首先引入损失函数与风险函数的概念。损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。

2.1 损失函数与风险函数

对于给定的输入$X$和假设空间$\mathcal{F}$中选择的决策函数模型$f$，由$f(X)$给出相应的输入$Y$，这个输出的预没值$f(X)$与真实值$Y$可能一致，也可能不一致，用一个损失函数或代价函数来度量预测的错误程度。损失函数是$f(x)$和$Y$的非负实值函数，记作$L(Y,f(X))$

几种常用的损失函数：

1） 0-1损失函数(0-1 loss function)
$$L(Y,f(X)) = \begin{cases}1, &Y\neq f(X) \\ 0, & Y=f(X)\end{cases}$$

2） 平方损失函数（quadratic loss function）
$$L(Y,f(X)) = (Y – f(X))^2$$

3）绝对损失函数（absolute loss function）
$$L(Y,f(X)) = |Y-f(X)|$$

4） 对数损失函数（logarithmic loss function）或对数似然损失函数
$$L(Y,P(Y|X)) = –logP(Y|X)$$

损失函数值越小，模型就越好。由于模型的输入、输出$(X,Y)$是随机变量，遵循联合分布$P(X,Y)$，所以损失函数的期望是
$$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)$关于联合分布$P(X,Y)$的平均意义下的损失，称为风险函数(risk function)或期望损失(expected loss)。

学习的目标就是选择期望风险最小的模型。由于联合分布$P(X,Y)$是所有样本所遵循的统计规律，它是未知的，所以$R_{exp}(f)$不能直接计算。实际上如果知道了联合分布，那么可以直接计算出$P(Y|X) = \int_{\mathcal{X}}P(x,y)dx$，也就不需要学习了。
所以用上面那种方式定义风险函数是不行的，那样的话监督学习变成了一个病态问题。

对于给定的训练数据集
$$T={(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}$$

模型$f(X)$关于训练数据集的平均损失称为经验风险（empirical risk）或经验损失（empirical loss），记作$R_{emp}$：
$$R_{emp}(f) = \frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))$$

期望风险$R_{exp}(f)$是模型关于联合分布的期望损失，经验风险$R_{emp}(f)$是模型关于训练样本集的平均损失。根据大数定律，当样本容量$N$趋于无穷时，经验风险$R_{emp}(f)$趋向于期望风险$R_{exp}(f)$

所以，一个很自然的想法是用经验风险估计期望风险。但是，由于现实中训练样本数目很有限，所以用经验风险估计期望风险常常不理想，要对经验风险进行一定的矫正。这就关系到监督学习的两个基本策略：经验风险最小化和结构风险最小化。

2.2 经验风险最小化与结构风险最小化

在假设空间、损失函数以及训练数据集确定的情况下，经验风险函数式就可以确定。经验风险最小化的策略认为，经验风险最小的模型就是最优的模型。根据这一策略，按照经验风险最小化求最佳模型就是求解最优化问题：
$$\min_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))$$

其中$\mathcal{F}$是假设空间。

当样本容量足够大时，经验风险最小化能保证有很好的学习效果，在现实中广泛采用。比如极大似然估计就是经验风险最小化的一个例子。当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。
但是当样本容量很小时，经验风险最小化学习效果就未必很好，会产生“过拟合(over-fitting)”现象。

结构风险最小化（structural risk minimization SRM）是为了防止过拟合而提出来的策略。结构风险最小化等价于正则化。结构风险在经验风险上加上表示模型复杂度的正则化项或罚项。在假设空间，损失函数以及训练样本集确定的情况下，结构风险的定义是
$$R_{srm}(f) = \frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)$$

其中$J(f)$为模型的复杂度，是定义在假设空间$\mathcal{F}$上的泛函。模型$f$越复杂，复杂度$J(f)$就越大；反之，模型$f$越简单，复杂度$J(f)$就越小。也就是说复杂度表示了对复杂模型的惩罚。$\lambda\ge 0$是系数，用以权衡经验风险和模型的复杂度。结构风险小需要经验风险与模型复杂度同时小。结构风险小的模型往往对训练数据以及未知的测试数据都有较好的预测。
比如，贝叶斯估计中的最大后验概率估计（maximum posterior probability estimation,MAP）就是结构风险最小化的例子。当模型是条件概率分布、损失函数就是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计。

结构风险最小化的策略认为结构风险最小的模型是最优的模型。所以求最优化模型时，就是求解最优化问题：

$$\min_{f\in\mathcal{F}}\frac{1}{N}L(y_i,f(x_i))+\lambda J(f)$$

这样，监督学习问题就变成了经验风险或结构风险函数的最优化问题。这时经验或结构风险函数是最优化的目标函数。

3 算法

从上面可以看出，在确定寻找最优模型的策略后

机器学习的问题归结为最优化的问题。机器学习讨论的算法问题就成为了求解最优化模型解的算法。而且往往最优化模型没有的解析解，需要用数值计算的方法求解，我们要确保找到全局最优解，以及使求解的过程非常高效。

机器学习的三要素