经验风险最小化

一、形式化定义

1.1 知识回顾

我们首先回顾一下SVM模型：

$(w,b)=\underset{w,b}{argmin}~w^Tw+C\sum_{i=1}^n\max(1-y_i(w^Tx_i+b),0)$

其对应的损失函数为：

$l(w,b)=||w||_2^2+C\sum_{i=1}^n\max(1-y_i(w^Tx_i+b),0)$

我们将$~C\sum_{i=1}^n\max(1-y_i(w^Tx_i+b),0)~$称为铰链损失函数，$~||w||_2^2~$称为$~l2~$正则化项

损失函数是惩罚训练错误的连续函数，正则化器是惩罚分类器复杂性的连续函数。

经验风险最小化模型的一般形式为：由损失函数$~I(h(x),y)~$和正则化项$~r(w)~$构成：

$\min_{w}\frac1n\sum_{i=1}^n I(h(x_i),y_i)+\lambda r(w)$

经验风险最小化（Empirical Risk Minimization）策略认为经验风险最小的模型是最优的模型，当样本容量足够大时，经验风险最小化能保证有很好的学习效果。比如，极大似然估计就是经验风险最小化的一个例子，当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。

但当样本容量很小时，经验风险最小化容易导致“过拟合”。

1.2 核心思想

我们考虑一个监督学习常见的场景：

（1）我们有两个对象空间：$~\mathcal{X}~$和$~\mathcal{Y}~$，$X\in \mathcal{X},Y\in\mathcal{Y}$
我们要建模一个函数$~h\in\mathcal{H}~$，函数$~h~$是$~X\rightarrow Y~$的映射，对于任意$~x\in X~$，有$~h(x)=y\in Y~$

（2）而模型的训练建立在我们所拥有的数据集：$~D=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}~$
我们假设存在一个建立在$~X~$和$~Y~$上的联合分布$~P(x,y)~$，$~D~$是从$~P(x,y)~$对应的一个独立同分布中获得的数据

独立同分布：每次抽样之间独立而且数据属于同一分布

注意：联合概率分布的假设允许我们对预测中的不确定性进行建模，因为$~y~$不是$~x~$的确定函数，而是一个具有固定$~x~$的条件分布$~P(y|x)~$的随机变量。

（3）我们还假设我们得到了一个非负的损失函数$~L(h(x),y)~$，它能反映出我们对标签的估计值和实际值之间的差距
然后我们将与假设$~h(x)~$的相关风险定义为损失函数的期望值：

$R(h)=E\big[L(h(x),y)\big]=\int L(h(x),y)~\mathrm{d}P(x,y)$

（4）我们的最终目标为找到一个：

$h^*=\underset{h}{argmin}~R(h)$

（5）通常，风险$~R(h)~$无法计算，因为学习算法并不知道联合分布$~P(x,y)~$，这种情况称为不可知学习
然而，我们可以通过平均训练集上的损失函数来计算近似值，我们称之为经验风险：

$R_{emp}=\frac1n\sum_{i=1}^n~L(h(x_i),y_i)$

相应的，我们经验风险最小化所要建立的模型即为：

$h^*=\underset{h\in\mathcal{H}}{argmin}~R_{emp}(h)$

经验风险最小化（ERM）是统计学习理论中的一个原则，它定义了一系列学习算法，并用于给出其性能的理论界限

二、损失函数

2.1 分类问题损失函数

（1）Hinge-Loss：在$~p=1~$时，是软约束的支持向量机所引入的铰链损失函数

$l(h(x_i),y_i)=\max(1-y_i(w^Tx_i+b),0)^p$

（2）Log-Loss：用于逻辑回归的损失函数

$l(h(x_i),y_i)=\log(1+e^{-y_ih(x_i)})$

（3）Exponential-Loss：指数损失函数，一般用于自适应提升算法

$l(h(x_i),y_i)=e^{-y_ih(x_i)}$

（4）Zero-One-Loss：0-1损失函数，用于分类问题

$l(h(x_i),y_i)=I(h(x_i)\not= y_i)$

如上图所示，横坐标为$~y_ih(x_i)~$的值，纵坐标代表损失函数的值。

2.2 回归问题损失函数

（1）Squared-Loss：平方损失函数

$l(h(x_i),y_i)=(h(x_i)-y_i)^2$

（2）Absolute-Loss：绝对值损失函数

$l(h(x_i),y_i)=|h(x_i)-y_i|$

（3）Huber-Loss：对$~MSE~$和$~MAE~$的结合，超参数$~\delta~$决定了Huber-Loss对二者的侧重性

$l(h(x_i),y_i)=\left\{ \begin{aligned} &~~~~~\frac12(h(x_i)-y_i)^2~~~~~,|h(x_i)-y_i|<\delta\\ &\delta\cdot(|h(x_i)-y_i|-\frac{\delta}2),|h(x_i)-y_i|\ge\delta \end{aligned} \right.$

（4）Log-Cosh-Loss：$~\cosh(x)=\frac{e^x+e^{-x}}{2}~$

$l(h(x_i),y_i)=\log\cosh(h(x_i)-y_i)$

如上图所示，横坐标为$~h(x_i)-y_i~$的值，纵坐标为损失函数的值。

三、正则化

在数学、统计学和计算机科学中，特别是在机器学习问题中，正则化是指添加信息以解决不确定问题或防止过度拟合的过程。
正则化器有助于改变优化问题的公式，以获得更好的几何直觉。

（1）$~l1~$正则化项：

$r(w)=||w||_1=\sum_{i=1}^d w_i$

（2）$~l2~$正则化项：

$r(w)=||w||_2^2=\sum_{i=1}^d w_i^2$

（3）$~lp~$范数：

$r(w)=||w||_p=(\sum_{i=1}^d w_i^p)^{\frac1p}$

（4）弹性网络（Elastic-Net）：对$~l1~$和$~l2~$正则化项的结合，超参数$~\alpha~$决定了弹性网络对二者的侧重性，$~\alpha~\in[0,1)$

$r(w)=\alpha||w||_1+(1-\alpha)||w||_2^2$

一些著名特例为：

（1）最小二乘法：

$\hat{w}_{MLE}=\underset{w}{argmin}~\frac1n\sum_{i=1}^n(x_i^Tw-y_i)^2$

（2）岭回归：

$\hat{w}_{MAP}=\underset{w}{argmin}~\frac1n\sum_{i=1}^n(x_i^Tw-y_i)^2+\lambda||w||_2^2$

（3）Lasso回归：

$\hat{w}=\underset{w}{argmin}~\frac1n\sum_{i=1}^n(x_i^Tw-y_i)^2+\lambda||w||_1$

（4）弹性网：

$\hat{w}=\underset{w}{argmin}~\frac1n\sum_{i=1}^n(x_i^Tw-y_i)^2+\alpha||w||_1+(1-\alpha)||w||_2^2$

（5）逻辑回归：

$\hat{w}=\underset{w}{argmin}~\log(1+e^{-y_i(w^Tx_i+b)})$

（6）支持向量机：

$(w,b)=\underset{w,b}{argmin}~||w||_2^2+C\sum_{i=1}^n\max(1-y_i(w^Tx_i+b),0)$