[Machine Learning] 损失函数和优化过程

损失函数和凸优化 (Loss Functions and Convex Optimisation)

在统计学习的框架中，我们通常试图找到一个函数或概念，这个函数可以很好地解释或拟合给定的数据。这通常通过最小化某种风险或损失来实现。为了找到一个好的模型，我们尝试在预定义的假设空间 $H$ 中找到一个函数，该函数在训练数据上的经验风险 (Empirical Risk) 最小。但是，我们的真正目标是找到一个函数，其预期风险 (Expected Risk)（对于所有可能的数据分布）最小。

假设类 $H$是一个函数集，其中每个函数都尝试从输入特征映射到输出标签， H = { h 1 , h 2 , …   } H = \{ h_1, h_2, \dots \} H={h1​,h2​,…}。通常，$H$ 由一个特定的算法或模型结构定义，如线性回归、决策树等。

在实践中，我们不能在所有可能的函数空间中搜索，因此我们限制搜索在一个预定义的 hypothesis class（假设类）$H$中。给定训练样本 $S=\{(X_1,Y_1),\dots ,(X_n,Y_n)\}$，函数 $h$ 的经验风险 $R_S(h)$ 是指在这组训练数据上的平均损失，用来衡量 $h$ 的性能：

$$R_S(h)=\sum _{i=1}^n\ell (X_i,Y_i,h)$$

预期风险 $R(h)$ 是模型 $h$ 在所有可能的数据分布上的平均风险。在理想情况下，我们希望找到的模型在任何可能的数据上都表现良好，而不仅仅是我们的训练数据：

$$R(h)=\mathbb{E}[R_S(h)]=\mathbb{E}[\ell (X_i,Y_i,h)]$$

目标概念 $c$ 是整个函数空间中的最佳假设，即在所有可能的假设中具有最低预期风险的假设:

$$c=\underset{h}{\mathrm{argmin}}R(h)$$

$h^{\ast }$ 是在预定义的假设类 $H$ 中的最优假设，即在 $H$ 中具有最低预期风险的假设:

$$h^{\ast }=\underset{h\in H}{\mathrm{argmin}}R(h)$$

在实践中，我们通常无法直接计算预期风险 $R(h)$，因为我们不知道所有可能的数据分布。因此，我们使用经验风险 $R_S(h)$ 作为 $R(h)$ 的一个估计，并从假设类 $H$ 中选择最小化经验风险的假设 $h_S$:

$$h_S=\underset{h\in H}{\mathrm{argmin}}{R}_S(h)=\underset{h\in H}{\mathrm{argmin}}\frac{1}{n}\sum _{i=1}^n\ell (X_i,Y_i,h)$$

因此，选择一个合适的假设空间和损失函数 $\ell$ 是至关重要的。

首先，0-1损失函数是最直接的分类误差度量。对于给定的分类器 $h$，它只是简单地计算误分类的数据点的数量。数学上，这定义为：$\underset{h}{\mathrm{argmin}}\mathbb{E}[1_{Y\ne sign(h(X))}]$。但我们通常遇到的问题是：

1. 真实数据的分布 $P(X,Y)$ 是未知的，因此我们不能直接计算上述期望。
2. 0-1损失在计算上是困难的，因为它是不连续的、非凸的，这使得优化变得复杂。

大数定律描述了随机变量的样本均值与整体均值之间的关系。它确保了当样本大小趋于无穷大时，样本均值趋于整体均值。更形式化地说，考虑一个随机变量 $X$，其期望值为 $\mathbb{E}[X]$。对于 $X$ 的 $n$ 个独立同分布的样本 $X_1,X_2,\dots ,X_n$，它们的样本均值定义为$\overline{X_n}=\frac{1}{n}{\sum }_{i=1}^n{X}_i$。当 $n\to \infty$ 时, $\overline{X_n}\to \mathbb{E}[X]$。

通过大数定律，我们可以使用这些样本来估计某些与分布相关的数量，例如期望损失。假设我们的目标是估计由假设 $h$ 引起的期望损失 $\mathbb{E}[1_{Y\ne \text{sign}(h(X))}]$。我们可以使用来自真实分布的样本 $\mathcal{D}$ 来估计这个期望：

$$\frac{1}{n}\sum _{i=1}^n{1}_{Y_i\ne \text{sign}(h(X_i))}$$

随着样本数量 $n$ 的增加，上述估计将接近真实的期望损失。

为了在实践中使问题变得可解，我们使用所谓的 surrogate loss function（替代损失函数），它们在优化上更容易处理，但仍旨在近似0-1损失函数。

• Hinge loss（合页损失）：这是支持向量机中使用的损失函数。
  ℓ ( X , Y , h ) = max ⁡ { 0 , 1 − Y h ( X ) } \ell(X,Y,h) = \max \{0,1−Yh(X)\} ℓ(X,Y,h)=max{0,1−Yh(X)}

• Logistic loss（逻辑损失）：这是逻辑回归中使用的。它对于异常值更为稳健，并且为概率提供了良好的估计。

• Least square loss（最小二乘损失）：主要在回归问题中使用。

• Exponential loss（指数损失）：是AdaBoost算法中使用的损失函数。

大多数流行的替代损失函数都是为了在大样本极限下模拟0-1损失函数的效果。这些被称为 classification-calibrated （分类校准的）替代损失函数。这意味着，如果训练数据无穷大，则使用这些损失函数训练的分类器在0-1损失上的表现将与真正的最佳分类器一致。

在二元分类问题中，模型通常会输出一个分数或概率值 $h(X)$，代表输入 $X$ 属于正类的可能性。公式 $\varphi (Yh(X))=\ell (X,Y,h)$ 实际上定义了一个映射，它将模型输出的分数 $h(X)$ 和真实标签 $Y$ 的组合 $Yh(X)$ 映射到代理损失函数的值上。这个映射允许我们通过优化 $\ell$ 来间接优化分类性能。

• $\varphi$ 是一个函数，它将 $Yh(X)$ 转换为一个实数值，这个值表示损失。
• $Yh(X)$ 的计算考虑了预测的得分 $h(X)$ 与实际标签 $Y$ 之间的关系。例如，在二元分类中，$Y$ 通常取值为 $-1$ 或 $1$，而 $h(X)$ 是模型对 $X$ 的预测得分。$Yh(X)$ 的正负反映了预测是否准确。
• $\ell (X,Y,h)$ 表示在给定输入 $X$、标签 $Y$ 和预测函数 $h$ 的情况下，模型所受的损失。

为了检查 $\ell$ 是否是分类校准的，我们通常检查以下条件:

1. $\varphi$ 是凹的 (convex)：这意味着函数 $\varphi$ 的图形是一个凸形状，这有利于优化过程，因为凸函数有全局最小值。
2. $\varphi$ 在0处可导，并且 ${\varphi }^{\prime }(0)<0$：这个条件保证了当预测得分 $h(X)$ 接近于正确分类的边界时（即 $Yh(X)$ 接近 0），函数 $\varphi$ 对预测错误的惩罚会增加。

满足上述条件意味着在大部分情况下，对于一个给定的数据点，分类器 $h$ 使代理损失最小化时，也会使0-1损失最小化。

例如，考虑Hinge损失 ℓ hinge ( X , Y , h ) = max ⁡ { 0 , 1 − Y h ( X ) } \ell_{\text{hinge}}(X,Y,h) = \max \{ 0, 1-Yh(X) \} ℓhinge​(X,Y,h)=max{0,1−Yh(X)}

对应的 $\varphi$ 函数为 ϕ ( z ) = max ⁡ { 0 , 1 − z } \phi(z) = \max \{ 0, 1-z \} ϕ(z)=max{0,1−z}

这个函数在 $z=1$ 处是不可导的，但是在 $z=0$ 处是可导的，且其导数小于0，因此Hinge损失是分类校准的。

现在可以考虑以下两个分类器的定义：

• $h_s$ 是基于有限训练数据和替代损失函数的最优分类器。
• $h_c$ 是基于整个数据分布和0-1损失函数的最优分类器。

使用替代损失函数和训练数据，我们可以找到 $h_s$：

$$h_s=\underset{h}{\mathrm{argmin}}\frac{1}{n}\sum _{i=1}^n\ell (X_i,Y_i,h)$$

与此同时，如果我们知道整个数据的分布，我们可以找到 $h_c$：

$$h_c=\underset{h}{\mathrm{argmin}}\mathbb{E}[1_{Y\ne \text{sign}(h(X))}]$$

当我们的训练数据量无限大时，使用替代损失函数得到的 $h_s$ 将与使用0-1损失函数得到的 $h_c$越来越接近。这可以通过以下公式表示：

$$\mathbb{E}[1_{Y\ne \text{sign}(h_S(X))}]\stackrel{n\to \infty }{⟶}\mathbb{E}[1_{Y\ne \text{sign}(h_c(X))}]$$

这意味着，当我们基于有限的样本数据集优化代理损失时，我们实际上是在优化该数据集上的经验损失。大数定律保证，随着样本数的增加，这个经验损失的期望会接近于真实的期望损失。同时，如果我们的代理损失是分类校准的，那么优化这个代理损失将隐式地优化0-1损失。当训练数据的大小趋向于无穷大时，通过最小化替代损失函数得到的分类器的期望0-1损失将趋近于最优的0-1损失。

当替代损失函数是凹的且光滑时，我们可以使用一系列的优化算法，如梯度下降、牛顿法等，来解决以下问题：

$$h=\underset{h\in H}{\mathrm{argmin}}\frac{1}{n}\sum _{i=1}^n\ell (X_i,Y_i,h)$$

假设函数 $f(h)$ 在点 $h_k$ 是可微的，我们可以使用泰勒级数来近似函数在 $h_k$ 附近的值：

$f(x+\Delta x)\approx f(x)+\nabla f(x{)}^T\Delta x+\frac{1}{2}\Delta x^T{\nabla }^{2}f(x)\Delta x+\dots$

如果我们只考虑上述近似的第一项和第二项（线性近似），我们得到：
$f(h+\Delta h)\approx f(h)+\nabla f(h{)}^T\Delta h$

现在，考虑我们的梯度下降更新步骤：$h_{k+1}=h_k+\eta d_k$，其中 $d_k$ 是下降方向， $\Delta h=\eta d_k$。我们要找到一个 $\Delta h$ 使得 $f(h+\Delta h)$ 尽可能小。从上面的线性近似中，我们可以看到，要使 $f(h+\Delta h)$ 的增量 $\nabla f(h{)}^T\Delta h$ 尽可能小，$\Delta h$ 应该与梯度 $\nabla f(h)$ 的反方向对齐。因此，通常会选择梯度的负方向 $-\nabla f(h)$ 作为下降方向 。

基本的更新规则是 $h_{k+1}=h_k-\eta \nabla f(h_k)$，其中 $\eta$ 是学习率，$\nabla f(h_k)$ 是函数在 $h_k$ 处的梯度。

纯粹的梯度下降方法在某些情况下可能不够高效，尤其是当函数的等高线呈延伸椭圆形时。在这种情况下，梯度下降路径可能会在延伸方向上“之字形”前进，导致需要更多的迭代次数。

为了解决这个问题，可以引入预条件矩阵 $D^k$。这个矩阵作为一个缩放因子，调整每个维度上梯度的大小，使得优化过程更加高效。

$D^k$ 可以根据问题的具体情况设计，目的是使得在函数的不同方向上移动时步长更加合理。通常，$D^k$ 是对角矩阵，其对角线元素表示不同方向上的缩放因子。

例如，在牛顿法中，$D^k$ 是Hessian矩阵的逆矩阵，它利用了函数的二阶导数信息，从而在曲率较大的方向上减小步长，在曲率较小的方向上增大步长。

通过引入预条件矩阵，更新规则变为 $h_{k+1}=h_k-\eta D^k\nabla f(h_k)$。这种方法使得在函数的每个方向上的移动更加符合函数本身的形状，从而加快收敛速度。其中， $D^k$ 是一个正定对称矩阵。正定性保证了更新的方向是下降方向，即 $\nabla f(h_k{)}^T{D}^k\nabla f(h_k)>0$。

• Steepest Descent（最速下降法）

  $D^k=I$

  此时，矩阵$D^k$ 是单位矩阵，这意味着我们只沿着梯度的负方向移动。

• Newton’s Method（牛顿法）

  $D^k=[{\nabla }^{2}f(h_k){]}^{-1}$

  这里，矩阵$D^k$ 是Hessian矩阵的逆，Hessian矩阵是一个用于描述多元函数局部曲率的矩阵。

对于一个二次可微的多元函数 $f(x_1,x_2,\dots ,x_n)$，其Hessian矩阵 $H$ 定义为该函数的所有二阶偏导数构成的矩阵。即：

H ( f ) = [ ∂ 2 f ∂ x 1 2 ∂ 2 f ∂ x 1 ∂ x 2 ⋯ ∂ 2 f ∂ x 1 ∂ x n ∂ 2 f ∂ x 2 ∂ x 1 ∂ 2 f ∂ x 2 2 ⋯ ∂ 2 f ∂ x 2 ∂ x n ⋮ ⋮ ⋱ ⋮ ∂ 2 f ∂ x n ∂ x 1 ∂ 2 f ∂ x n ∂ x 2 ⋯ ∂ 2 f ∂ x n 2 ] H(f) = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix} H(f)= ​∂x12​∂2f​∂x2​∂x1​∂2f​⋮∂xn​∂x1​∂2f​​∂x1​∂x2​∂2f​∂x22​∂2f​⋮∂xn​∂x2​∂2f​​⋯⋯⋱⋯​∂x1​∂xn​∂2f​∂x2​∂xn​∂2f​⋮∂xn2​∂2f​​ ​

• Hessian矩阵用于判断多元函数的某个点是局部极大值、局部极小值还是鞍点。

  • 如果 $H$ 在该点的所有特征值都是正的，则该点是一个局部极小值。
  • 如果 $H$ 在该点的所有特征值都是负的，则该点是一个局部极大值。
  • 如果 $H$ 的特征值中既有正的也有负的，则该点是一个鞍点。
  • 如果 $H$ 的特征值包含零，则该方法无法确定该点的性质，可能需要进一步的分析。

• 特征值反映了函数在对应特征向量方向上的曲率。

  正特征值意味着函数在该方向上呈凸形，负特征值意味着函数在该方向上呈凹形。

在实践中，计算Hessian矩阵和其逆可能会遇到困难，尤其是当维度很高时。因此，提出了多种牛顿法的实用变种：

• 修改Hessian以确保其为正定:

  为了确保Hessian矩阵是可逆的和正定的，我们可以对其进行微小的修改，例如，通过向其添加一个正则化项。

• 每m次迭代计算一次Hessian:

  由于Hessian矩阵的计算可能是计算密集型的，所以一个策略是每m次迭代计算一次，而在其他迭代中使用最近计算的Hessian。

• 只使用Hessian的对角线:

  通过只考虑Hessian矩阵的对角线元素，可以大大减少计算的复杂性。这种方法称为对角Hessian牛顿法。

• 拟牛顿法:

  拟牛顿法是一种旨在近似Hessian矩阵而避免直接计算它的方法。其中，BFGS (Broyden–Fletcher–Goldfarb–Shanno algorithm) 和L-BFGS (Limited-memory BFGS) 是最著名的拟牛顿方法。L-BFGS 是BFGS的内存效率版本，只存储Hessian矩阵的最近的几个更新。

假设我们已经选择了下降方向$d_k$，精确线搜索 (Exact Line Search) 是这样定义的：

• 假设当前迭代点为 $h_k$，下降方向为 $d_k$（在梯度下降中为 $-\nabla f(h_k)$）。
• 精确线搜索试图找到一个步长 ${\eta }_k$，使得 $f(h_k+{\eta }_k{d}_k)$ 最小。
• 这涉及到在一维空间上最小化函数 $f$，即求解问题 $\eta =\underset{\eta }{\mathrm{argmin}}f(h_k-\eta \nabla f(h_k))$。

简单地说，它搜索一个步长$\eta$，使得从当前位置$x_k$开始，沿着梯度方向移动$\eta$步长后，函数$f$达到最小值。尽管这种方法可以找到最佳的步长，但在实际应用中，它可能会很昂贵，因为每次迭代都需要求解一个新的优化问题。

精确线搜索通常涉及到求解一个一维优化问题，这可能需要使用一些数学技术，如黄金分割搜索或二分搜索。在实践中，精确线搜索可能是计算密集型的，因为它要求在每次迭代中都要精确地最小化一维函数。

为了避免精确线搜索的高计算成本，我们可以使用一些近似的策略来选择步长 $\eta$。如果我们知道梯度的Lipschitz平滑常数 $L$，我们可以保证选择的步长不会太大，从而避免过度调整参数并保证算法的稳定性。这个常数 $L$ 告诉我们函数的梯度怎样被限制在一个平滑的变化范围内。具体来说，如果 $L$ 已知，我们可以使用如下的迭代更新规则：

$$h_{k+1}=h_k-\frac{1}{L}\nabla f(h_k)$$

以及保证函数值下降的条件：

$$f(h_{k+1})\le f(h_k)-\frac{1}{2L}\Vert \nabla f(h_k){\Vert }^2$$

这个更新规则简化了步长的选择过程，因为它不需要每次都计算最优步长，而是依靠 $L$ 的值来控制步长。这种方法虽然不如精确线搜索精细，但计算上更为可行，对于大规模问题更为实用。

Lipschitz平滑常数 $L$ 是用来描述函数梯度平滑度的一个数值，如果一个函数的梯度（或导数）变化不超过其自身与另一点差的常数倍，那么这个函数就被认为具有Lipschitz连续的梯度，而这个常数倍 $L$ 就是所谓的Lipschitz平滑常数。

更具体地说，考虑一个函数 $f:{\mathbb{R}}^n\to \mathbb{R}$，如果对于定义域内的任意两点 $x$ 和 $y$，该函数的梯度满足以下不等式：

$$\Vert \nabla f(x)-\nabla f(y)\Vert \le L\Vert x-y\Vert$$

这里，$\nabla f(x)$ 是函数在 $x$ 点的梯度，$\Vert \cdot \Vert$ 表示向量的欧几里得范数（即长度）。如果这样的 $L$ 存在，我们就可以说函数 $f$ 在其定义域内是Lipschitz平滑的，且 $L$ 是一个Lipschitz平滑常数。

所以，如果我们知道 $L$，我们就可以更好地控制梯度下降算法中的步长，以避免步长太大导致的震荡，或步长太小导致的收敛速度慢。简而言之，Lipschitz平滑常数 $L$ 提供了一个梯度变化的上界，帮助我们在优化问题中做出更好的步长选择。

不同算法的收敛速率是不同的：

1. 梯度下降（对于凹函数）：

   • 假设：
     • 目标函数是凹的 (convex) 。
     • 目标函数的梯度满足Lipschitz连续性。
   • 收敛速率：
     • 对于凹函数，梯度下降的收敛速率是 $O\left(\frac{1}{k}\right)$。
     • 这意味着经过 $k$ 次迭代后，算法与最优解的差距大约是初始差距的 $\frac{1}{k}$。

2. 梯度下降（对于强凸函数）：

   • 假设：
     • 目标函数是强凹的 (strongly-convex) ，意味着除了凹性外，还满足某种形式的下界条件。
     • 梯度满足Lipschitz连续性。
   • 收敛速率：
     • 对于强凹函数，梯度下降的收敛速率是 $O{\left(1-\frac{\mu }{L}\right)}^k$。
     • 这里 $\mu$ 是表示函数强凹性的常数。收敛速度依赖于 $\mu$ 和 $L$ 的比例。

3. 牛顿法：

   • 假设：
     • 目标函数具有Lipschitz连续的梯度。
     • 目标函数是强凹的。
   • 收敛速率：
     • 牛顿法的收敛速率是局部二次的，这意味着靠近最优解时，误差的减少速度是指数级的。
     • 牛顿法的精确收敛速率取决于多个因素，通常表示为 $\sum _{i=1}^k{\rho }_k$，其中 ${\rho }_k$ 是逐步减少的序列。

PAC学习框架 (Probably Approximately Correct Learning Framework)

在机器学习中，我们经常关心两种主要的误差来源：近似误差 (Approximation Error) 和估计误差 (Estimation Error)。近似误差是因预定义的假设空间 $H$ 的限制而导致的误差，它是最优假设 $h^{\ast }$ 和目标概念 $c$ 之间的差异。估计误差是由于有限的样本大小而导致的误差，它是从数据中学习的假设 $h_S$ 和最优假设 $h^{\ast }$ 之间的差异。

如果目标概念 $c$ 在预定义的假设空间 $H$ 中，那么近似误差将为零。然而，选择一个大而复杂的假设空间虽然可以减小近似误差，但它会增加估计误差，因为模型可能会过拟合数据。

在实际应用中，我们希望了解从有限的训练样本中学到的知识能够多大程度上应用到新的、未曾见过的数据上。PAC学习框架给出了为了从预定义的假设类中学到近似最优假设所需的训练样本数量的上界。该框架为学习算法的泛化性能提供了理论基础。它揭示了训练数据集的大小、假设类的复杂性和学到的模型的泛化误差之间的关系。

假设类 $H$ 是PAC可学习的，意味着存在一个算法，可以从假设类中选取一个假设，这个假设在新的数据上的误差与假设类中最佳假设的误差之差小于 $ϵ$，且这种情况发生的概率至少为 $1-\delta$。

如果存在学习算法 $\mathcal{A}$ 和多项式函数 $poly(\cdot ,\cdot )$，使得对于任意 $ϵ>0$ 和 $\delta >0$，对于所有定义在 $X\times Y$ 上的分布 $D$，只要样本的大小 $n$ 超过 $poly(\frac{1}{\delta },\frac{1}{ϵ})$，则由算法 $\mathcal{A}$ 学到的假设 $h_S$ 满足以下条件:

p { R ( h S ) − min ⁡ h ∈ H R ( h ) ≤ ϵ } ≥ 1 − δ p\{ R(h_S) - \min\limits_{h \in H} R(h) \leq \epsilon\} \geq 1 - \delta p{R(hS​)−h∈Hmin​R(h)≤ϵ}≥1−δ

这里 $R(h_S)$ 是学到的假设的经验风险，而 $\underset{h\in H}{\min }R(h)$ 是假设类 $H$ 中所有假设的最小可能风险。

如果训练样本大小足够大，例如 $n>\text{poly}(\frac{1}{\delta },\frac{1}{ϵ})$，那么有很高的概率，学到的假设 $h_S$ 可以近似地作为预定义假设类 $H$ 中任何任务的最佳假设。

这里，“学到的假设” $h_S$ 是学习算法基于样本数据产生的结果，“近似地”意味着 $h_S$ 的经验风险与 $H$ 中最佳假设的风险相差不超过 $ϵ$，而“大概地”指出这个结果是有 $1-\delta$ 的置信度保证的。

总的来说，PAC学习提供了统计上的保证，说明在足够大的样本量下，我们的学习算法有很大概率找到一个与最优假设相当接近的假设。这里的“大概”反映了学习结果的置信程度，“近似”则表示所学假设的准确度。

我们使用经验风险最小化（ERM）算法来验证一个假设类是否是PAC可学习的。

泛化误差 (Generalisation Error)

泛化误差是指模型在训练数据上的表现与在整个数据分布上的表现之间的差异。在实际应用中，我们不能直接计算这个错误率，因此我们使用训练数据上的经验误差 $R_S(h)$ 来估计它。

PAC学习想要确保，对于足够大的样本量，学到的模型 $h_S$ 的期望风险接近于最佳模型 $h^{\ast }$ 的风险。数学上表示为：对于任何 $ϵ>0$ 和 $\delta >0$，当样本量 $n$ 足够大时，我们可以以至少 $1-\delta$ 的概率保证 $R(h_S)-\underset{h\in H}{\min }R(h)<ϵ$。

考虑学习得到的假设 $h_S$ 和假设类 $H$ 中的最优假设 $h^{\ast }$ 的期望风险差 $R(h_S)-R(h^{\ast })$：

$$\begin{array}{rl}R(h_S)-\underset{h\in H}{\min }R(h)& =R(h_S)-R(h^{\ast })\\ & =R(h_S)-R_S(h_S)+R_S(h_S)-R_S(h^{\ast })+R_S(h^{\ast })-R(h^{\ast })\end{array}$$
最佳模型 $h^{\ast }$ 的风险应该小于或等于从训练数据学习到的模型 $h_S$ 的风险，所以：

$$\begin{array}{rl}R(h_S)-\underset{h\in H}{\min }R(h)& \le R(h_S)-R_S(h_S)+R_S(h^{\ast })-R(h^{\ast })\\ & \le |R(h_S)-R_S(h_S)|+|R(h^{\ast })-R_S(h^{\ast })|\\ & \le \underset{h\in H}{\sup }|R(h)-R_S(h)|+\underset{h\in H}{\sup }|R(h)-R_S(h)|\\ & =2\underset{h\in H}{\sup }|R(h)-R_S(h)|\end{array}$$

这个不等式说明，在最坏情况下，最优模型 $h_S$ 的期望风险与在假设空间 $H$ 中可能的最优模型的期望风险之间的差距最多是所有模型在期望风险和经验风险之间差的两倍。

我们还有一个不等式：

$$|R(h_S)-R_S(h_S)|\le \underset{h\in H}{\sup }|R(h)-R_S(h)|$$

这个不等式说明，所选模型 $h_S$ 的真实误差与其在训练集上的经验误差之间的差距，最多等于假设空间 $H$ 中所有模型的最大真实误差与经验误差之间的差的上界。

实际上，泛化误差以高概率被一个小数上界限定。我们首先需要理解霍夫丁不等式的基本形式，然后将其应用于泛化误差的上界。

假设有一个学习算法，它从训练数据集 $D$ 中学习并产生一个假设 $h$。

我们想要估计 $h$ 在整个数据分布上的真实误差 $R(h)$ 与在训练集 $D$ 上的经验误差 $\hat{R}(h)$ 之间的差异。

霍夫丁不等式用于估计一组独立随机变量的平均值与其期望值偏离的概率。对于一组界限明确的独立随机变量 $X_1,X_2,...,X_n$，且 $a_i\le X_i\le b_i$，平均值为 $\bar{X}=\frac{1}{n}{\sum }_{i=1}^n{X}_i$，则对任意 $ϵ>0$，有：

$$P(|\bar{X}-E[\bar{X}]|\ge ϵ)\le 2\exp \left(-\frac{2n^2{ϵ}^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right)$$

对于每个样本 $i$，定义随机变量 $X_i$ 表示分类器 $h$ 是否在该样本上犯错。$X_i=1$ 表示错误分类，$X_i=0$ 表示正确分类。
这些 $X_i$ 是独立同分布的，且 $\mathbb{E}[X_i]=R(h)$，其中 $R(h)$ 是期望风险。

经验风险 $R_S(h)$ 是在训练集上的分类错误的平均值，即 $R_S(h)=\frac{1}{n}\sum _{i=1}^n{X}_i$。

使用霍夫丁不等式，我们可以估计 $R_S(h)$ 与 $R(h)$ 之间偏离超过 $ϵ$ 的概率。由于 $X_i$ 的界限为 0 和 1，我们得到：

P ( ∣ 1 n ∑ i = 1 n X i − R ( h ) ∣ ≥ ϵ ) ≤ 2 exp ⁡ ( − 2 n ϵ 2 ) P\left(\left|\frac{1}{n}\sum_{i=1}^{n}X_i - R(h)\right| \geq \epsilon\right) \leq 2\exp(-2n\epsilon^2) P( ​n1​i=1∑n​Xi​−R(h) ​≥ϵ)≤2exp(−2nϵ2)

这意味着，对于任意给定的误差界限 $ϵ$，经验风险与期望风险之间的差异大于 $ϵ$ 的概率小于或等于 $2\exp (-2n{ϵ}^2)$。

因此，可以确定一个样本数量 $n$，使得以至少 $1-\delta$ 的概率，泛化误差 $|R_S(h)-R(h)|$ 被 $ϵ$ 上界限定，其中 $\delta =2\exp (-2n{ϵ}^2)$。

换句话说，通过增加样本量 $n$，我们可以增加泛化误差小于某个小数 $ϵ$ 的概率。

VC Dimension: Binary Case

在机器学习中，我们通常有一个假设集合 $H$，里面包含了很多不同的模型（或者说“假设”）。我们的目标是从这个集合中找到一个最好的模型来预测我们感兴趣的事物。如果这个假设集合非常大，甚至是无限的，找到最好的模型就会很困难。

为了解决这个问题，我们可以采用一种技巧，即不是直接在无限的假设集合中找最好的模型，而是将这些模型分成几个有限的组。每组里的模型在我们给定的一些数据点上预测的结果是一样的。这样，我们就可以将每个组中的模型看作是等价的，并且每个组只需要选择一个模型作为代表。

这样做之后，我们就不需要考虑原始无限假设集合中的每一个模型了，而只需要考虑有限个代表模型，这大大简化了问题。

最后，我们想要测量的是我们模型在实际应用中的表现（即期望风险 $R(h)$）和在我们手头数据上的表现（即经验风险 $R_S(h)$）之间的差异。理论上，我们希望这两者尽可能接近。通过上述的分组技巧，我们可以在数学上找到一个上限（或者说界限），确保无论我们选择哪一个代表模型，它在实际应用中的表现不会比在手头数据上的表现差太多。

如果这个假设类 $H$有无限多个模型，我们很难一一考虑它们。为了解决这个问题，我们需要找到一个方法，能让我们只考虑其中的一部分模型，并且这一部分能代表整个无限集合的特性。我们把这一部分称为 $H\prime$ 。

成长函数 (Growth Function) 是一种帮助我们理解假设类 $H$ 复杂性的工具。它告诉我们，对于任何数量的数据点 $n$，假设类 $H$ 能产生多少种不同的预测结果。如果对于每一组可能的预测结果，我们都能在 $H$ 中找到至少一个模型来生成这个结果，那么我们说 $H$ 能“破坏”这 $n$ 个数据点。

破坏性 (Shattering) 的概念帮助我们理解一个假设类能产生多少种不同的预测结果。如果一个假设类可以为任何可能的数据点组合生成所有可能的标签组合（例如，对于三个数据点，能生成 +++，±-，-±，等所有八种组合），那么我们说它破坏了这些点。

我们通常更关心的是，对于实际的数据点数 $n$，假设类 $H$ 实际能产生多少种不同的预测。这个数字是 ${\Pi }_H(n)$。如果 ${\Pi }_H(n)$ 等于 $2^n$ ，这意味着假设类 $H$ 可以为这 $n$ 个数据点生成所有可能的标签组合。

如果给定一个在 ${\mathbb{R}}^2$ 中的线性分类器： H = { ( x 1 , x 2 ) ↦ { 1 w 1 x 1 + w 2 x 2 + b ≥ 0 } : w 1 , w 2 , b ∈ R } \mathcal{H} = \{ (x_1, x_2) \mapsto \{1_{w_1x_1+w_2x_2+b \geq 0}\} : w_1, w_2, b \in \mathbb{R} \} H={(x1​,x2​)↦{1w1​x1​+w2​x2​+b≥0​}:w1​,w2​,b∈R}。

1. 给定 $m$ 个点，相应的生长函数用 ${\Pi }_{\mathcal{H}}(m)$ 表示。当 $m$ 分别等于 1, 2, 3, 4 时，这四个生长函数 ${\Pi }_{\mathcal{H}}(m)$ 的值是多少？

   • 当 $m=1$ 时，无论如何放置一个点，线性分类器都可以完美分类（要么全部归为正类，要么全部归为负类）。所以，生长函数 ${\Pi }_{\mathcal{H}}(1)=2$。

   • 当 $m=2$ 时，两个点可以以两种方式被线性分类器分开（每个点各属于一类，或者两个点属于同一类）。因此，${\Pi }_{\mathcal{H}}(2)=2^2=4$。

   • 当 $m=3$ 时，三个点可以构成一个三角形。线性分类器可以通过三种不同方式将其中一个点与其他两点分开，加上一种方式是将三个点全部分类为同一类，还有另外一种方式是将三个点分成两类但不是单独一个点对立两个点。因此，${\Pi }_{\mathcal{H}}(3)=2^3=8$。

• 当 $m=4$ 时，情况就更复杂了。四个点可以构成很多不同的配置，但一个线性分类器无法实现所有 $2^4=16$ 种可能的分割。在最坏的情况下，四个点形成一个凸形，线性分类器可以实现 14 种分割（不能实现的是四个点每个点各自成一类，以及三个点一类另一个点一类）。所以，${\Pi }_{\mathcal{H}}(4)\le 14$。

2. 计算 $\mathcal{H}$ 的VC维数：

   • VC维数是指一个假设类能够“破坏”的最大点集的大小。如果一个假设类可以通过某种方式将这个点集中的点分配到任意的类别中，那么它就破坏了这个点集。

   • 对于线性分类器 $\mathcal{H}$，我们可以用线性边界在平面上将任意两个点分开，所以 $\mathcal{H}$ 可以破坏任意两点的集合。当我们有三个点时，只要这三个点不共线，我们仍然可以用一条直线将它们分开成任意的分类。因此，$\mathcal{H}$ 的VC维数至少是3。

   • 但当我们有四个点时，如上面解释的，存在一些四点的配置，这些配置不能被任意分割成两类，特别是如果这四个点形成一个凸多边形。所以，$\mathcal{H}$ 不能破坏任意四点的集合。

因此，该线性分类器 $\mathcal{H}$ 在 ${\mathbb{R}}^2$ 中的VC维数是3。这是因为它可以破坏任意三点的集合，但不能破坏四个点的集合。

假设集合 $H$ 是由三个二元分类器构成的，它们分别是：

1. $h_1(x)=\text{sign}(e^x)$
2. $h_2(x)=\text{sign}(2|x|+1)$
3. $h_3(x)=\text{sign}((x-1{)}^2+2x)$

其中 $x$ 是实数 ($x\in \mathbb{R}$)，而 $\text{sign}$ 函数根据 $x$ 的值返回 $+1$ 或 $-1$。

生长函数 ${\Pi }_H(n)$ 表示集合 $H$ 在最坏情况下（即它能实现的最多种类的标签组合）能在任意 $n$ 个数据点上产生的不同标签的数量。

由于我们的假设集合 $H$ 只有三个假设，那么无论 $n$ 的值是多少，$H$ 最多只能在这 $n$ 个点上产生 $2^3=8$ 种不同的标签组合。这是因为每个假设 $h_i$ 对于任意一个点 $x$ 只能产生 $+1$ 或 $-1$ 两种标签。

然而，这个数字实际上可能更小，因为假设之间可能产生相同的标签。例如，对于 $h_1(x)$，由于 $e^x$ 总是正的，所以 $h_1(x)$ 总是返回 $+1$，不管 $x$ 的值是多少。这意味着 $h_1$ 不能在任意点上产生不同的标签，它对生长函数没有贡献。

对于 $h_2(x)$ 和 $h_3(x)$，我们需要分析它们是否能在某些 $x$ 的值上产生不同的标签。$h_2$ 由于 $2|x|+1$ 总是正的，所以也总是返回 $+1$。最后，$h_3(x)$ 是一个二次函数，它的符号会根据 $x$ 的值变化，但是由于我们考虑的是 $\text{sign}$ 函数，所以 $h_3$ 也总是返回 $+1$，因为 $(x-1{)}^2+2x$ 总是正的。

所以，实际上，这三个假设在任何点 $x$ 上都产生相同的标签 $+1$，那么它们的生长函数 ${\Pi }_H(n)=1$ 对于所有的 $n$。

VC维是指一个假设集合可以“破坏”的最大点集的大小。一个假设集合“破坏”一组点意味着它能对这些点产生所有可能的标签组合。

由于 $H$ 中的每个假设都不能产生除 $+1$ 以外的标签，$H$ 不能破坏任何大小的点集，因此 $H$ 的VC维是0。

一个高VC维度的假设类比低VC维度的假设类更复杂。这意味着高VC维度的假设类可能有更高的过拟合风险。

VC不等式它提供了期望风险（即在整个分布上的风险）和经验风险（即训练数据上的风险）之间的关系。给定一个假设类的VC维度和一个训练数据集的大小，VC不等式告诉我们期望风险和经验风险之间的差异不超过某个值的概率。

$$\mathrm{Pr}\left(\left|R(h)-R_S(h)\right|>ϵ\right)\le 4m_H(2n)\exp \left(-\frac{n{ϵ}^2}{8}\right)$$

其中，$m_H(n)$ 是假设空间 $H$ 能够打散的大小为 $n$ 的点集的数量，$R(h)$ 是真实风险，$R_S(h)$ 是经验风险。

通过上述不等式，我们可以估计为了达到特定的泛化误差，需要多少训练样本。这对于判断一个给定的假设类是否是PAC可学习的非常有用。

在PAC学习中，为了保证学习到的假设有良好的泛化性能，我们需要足够多的样本来控制期望风险和经验风险之间的差异。VC维度为我们提供了评估所需样本量的方法，从而使我们能够验证假设类是否是PAC可学习的。文章来源地址https://www.toymoban.com/news/detail-664633.html

到了这里，关于[Machine Learning] 损失函数和优化过程的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！