当前位置：首页 > news >正文

【高级机器学习】 4. 假设复杂度与泛化理论详解

news 2025/8/31 5:23:37

机器学习中的假设复杂度与泛化理论详解

引言

在机器学习中，我们经常面临一个核心问题：为什么我们的模型能够在训练数据上表现良好，同时也能在未见过的新数据上表现出色？ 这就是著名的泛化问题。本文将深入探讨假设复杂度与泛化性能之间的关系。

1. 基础概念回顾

1.1 最优分类器的定义

理论上的最佳分类器可以数学化定义为：

$arg⁡min⁡hE[1{Y≠sign(h(X))}]\arg \min_h E[1_{\{Y \neq \text{sign}(h(X))\}}]$

其中：

$h (X)$ 是我们的假设函数
$Y$ 是真实标签
$1{⋅}1_{\{\cdot\}}$ 是指示函数（条件成立时为1，否则为0）
$E[⋅]E[\cdot]$ 表示期望

问题：这个目标函数既不是凸函数也不光滑，很难直接优化。

1.2 替代损失函数

为了解决优化困难，我们通常使用替代损失函数：

常见的凸替代损失函数：

合页损失（Hinge Loss）： $ℓ(X,Y,h)=max⁡{0,1−Yh(X)}\ell(X,Y,h) = \max\{0, 1-Yh(X)\}$
逻辑损失（Logistic Loss）： $ℓ(X,Y,h)=log⁡2(1+exp⁡(−Yh(X)))\ell(X,Y,h) = \log_2(1 + \exp(-Yh(X)))$
平方损失（Least Squares）： $ℓ(X,Y,h)=(Y−h(X))2=(1−Yh(X))2\ell(X,Y,h) = (Y - h(X))^2 = (1 - Yh(X))^2$
指数损失（Exponential Loss）： $ℓ(X,Y,h)=exp⁡(−Yh(X))\ell(X,Y,h) = \exp(-Yh(X))$

非凸替代损失函数：

柯西损失： $ℓ(X,Y,h)=log⁡2(1+(1−Yh(X)σ)2)\ell(X,Y,h) = \log_2\left(1 + \left(\frac{1-Yh(X)}{\sigma}\right)^2\right)$
相关熵损失： $ℓ(X,Y,h)=1−exp⁡(−(1−Yh(X)σ)2)\ell(X,Y,h) = 1 - \exp\left(-\left(\frac{1-Yh(X)}{\sigma}\right)^2\right)$

2. 梯度下降优化方法

2.1 基本思想

我们要解决的无约束凸优化问题：
$arg⁡min⁡h∈Hf(h)=arg⁡min⁡h∈H1n∑i=1nℓ(Xi,Yi,h)\arg \min_{h \in H} f(h) = \arg \min_{h \in H} \frac{1}{n}\sum_{i=1}^n \ell(X_i, Y_i, h)$

2.2 泰勒定理应用

根据泰勒定理，对于在点 $a$ 处 $k$ 次可微的函数 $f$ ：

$\cdots + \frac{f^{(k)}(a)}{k!}(x-a)^k + h_k(x)(x-a)^k$

其中 $lim⁡x→ahk(x)=0\lim_{x \to a} h_k(x) = 0$ 。

当 $k = 1$ 时：
$f (x) = f (a) + f^{'} (a) (x - a) + o (x - a)$

2.3 更新规则

设更新规则为： $hk+1=hk+ηdkh^{k+1} = h^k + \eta d^k$

令 $x = h^{k+1}$ , $a = h^k$ ，我们得到：
$f(hk+1)=f(hk)+η∇f(hk)Tdk+o(η)f(h^{k+1}) = f(h^k) + \eta \nabla f(h^k)^T d^k + o(\eta)$

关键设计问题：

如何设计方向 $d^k$ ？
如何选择步长 $η\eta$ ？

通常设置 $dk=−Dk∇f(hk)d^k = -D^k \nabla f(h^k)$ ，其中 $D^k$ 是某个正定矩阵。

2.4 收敛速度

算法	假设条件	收敛速度
梯度下降	Lipschitz梯度，凸函数	$O (1/ k)$
梯度下降	Lipschitz梯度，强凸函数	$O((1−μ/L)k)O((1-\mu/L)^k)$
牛顿法	Lipschitz梯度，强凸函数	二次收敛

其中强凸情况下的线性收敛率为：
$f(hk+1)−f(h∗)≤(1−μL)k(f(h1)−f(h∗))f(h^{k+1}) - f(h^*) \leq \left(1 - \frac{\mu}{L}\right)^k (f(h^1) - f(h^*))$

3. 假设类与泛化理论

3.1 关键概念定义

机器学习算法本质上是一个映射：
$\in (X \times Y)^n \rightarrow h_S \in H$

其中：

$S$ 是训练样本
$H$ 是预定义的假设类
$h_S$ 是从数据中学到的假设

3.2 三个重要的假设

目标概念（Target Concept）： $c = \arg \min_h R(h)$
假设类中的最优假设： $h∗=arg⁡min⁡h∈HR(h)h^* = \arg \min_{h \in H} R(h)$
从数据学到的假设： $hS=arg⁡min⁡h∈HRS(h)h_S = \arg \min_{h \in H} R_S(h)$

3.3 两类误差分解

总误差 = 近似误差 + 估计误差

近似误差： $R(h^*) - R(c)$ ，由假设类 $H$ 的表达能力限制造成
估计误差： $R(h_S) - R(h^*)$ ，由有限训练数据造成

![误差分解示意图]

通用函数空间↓目标c ← 近似误差 → h* (假设类H中的最优)↓ 估计误差h_S (从数据学到的)

如果目标c在预定义的假设类H中，那么近似approximation误差会等于0
但是同时，我们不可以把假设空间设得很大。1.大的假设会使得更难学习2.estimate估计误差会变大

3.4 风险定义

经验风险： $RS(h)=1n∑i=1nℓ(Xi,Yi,h)R_S(h) = \frac{1}{n}\sum_{i=1}^n \ell(X_i, Y_i, h)$
期望风险： $E[R_S(h)] = E[\ell(X,Y,h)]$

4. PAC学习框架

4.1 PAC学习定义

定义：假设类 $H$ 被称为PAC（概率近似正确）可学习的，如果存在学习算法 $A$ 和多项式函数 $poly(⋅,⋅)\text{poly}(\cdot, \cdot)$ ，使得对于任意 $ϵ>0\epsilon > 0$ , $δ>0\delta > 0$ ，以及 $\times Y$ 上的任意分布 $D$ ，当样本大小 $\text{poly}(1/\delta, 1/\epsilon)$ 时，算法 $A$ 学到的假设 $h_S$ 满足：

$P{R(hS)−min⁡h∈HR(h)≤ϵ}≥1−δP\left\{R(h_S) - \min_{h \in H} R(h) \leq \epsilon\right\} \geq 1 - \delta$

直观理解：

概率（Probably）：以高概率 $1−δ1-\delta$
近似（Approximately）：误差不超过 $ϵ\epsilon$
正确（Correct）：找到接近最优的假设

如果训练样本量足够大，具有很高的概率，则学习到的假设可以是任何task的预定义假设类中最佳假设的近似值

4.2 PAC可学习性检验

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

关键不等式推导：

$R(hS)−min⁡h∈HR(h)=R(hS)−R(h∗)R(h_S) - \min_{h \in H} R(h) = R(h_S) - R(h^*)$

展开得到：
$R(h_S) - R_S(h_S) + R_S(h_S) - R_S(h^*) + R_S(h^*) - R(h^*)$

由于 $RS(hS)≤RS(h∗)R_S(h_S) \leq R_S(h^*)$ （ERM的定义），所以：
$R(hS)−R(h∗)≤∣R(hS)−RS(hS)∣+∣R(h∗)−RS(h∗)∣R(h_S) - R(h^*) \leq |R(h_S) - R_S(h_S)| + |R(h^*) - R_S(h^*)|$

$≤2sup⁡h∈H∣R(h)−RS(h)∣\leq 2\sup_{h \in H}|R(h) - R_S(h)|$

核心问题：如何控制 $sup⁡h∈H∣R(h)−RS(h)∣\sup_{h \in H}|R(h) - R_S(h)|$ ？

5. 集中不等式与泛化界

5.1 Hoeffding不等式

定理：设 $X1,…,XnX_1, \ldots, X_n$ 为独立随机变量，且 $Xi∈[ai,bi]X_i \in [a_i, b_i]$ 。令 $Sn=1n∑i=1nXiS_n = \frac{1}{n}\sum_{i=1}^n X_i$ ，则对任意 $ϵ>0\epsilon > 0$ ：

$P{∣Sn−E[Sn]∣≥ϵ}≤2exp⁡(−2n2ϵ2∑i=1n(bi−ai)2)P\{|S_n - E[S_n]| \geq \epsilon\} \leq 2\exp\left(-\frac{2n^2\epsilon^2}{\sum_{i=1}^n(b_i-a_i)^2}\right)$

5.2 应用到学习理论

假设损失函数有界： $ℓ(X,Y,h)∈[0,M]\ell(X,Y,h) \in [0,M]$ ，则对单个假设 $h$ ：

$P{∣R(h)−RS(h)∣≥ϵ}≤2exp⁡(−2nϵ2M2)P\{|R(h) - R_S(h)| \geq \epsilon\} \leq 2\exp\left(-\frac{2n\epsilon^2}{M^2}\right)$

5.3 联合界（Union Bound）

对于有限假设类 $H$ ，使用联合界：

$P{sup⁡h∈H∣R(h)−RS(h)∣≥ϵ}≤∑h∈HP{∣R(h)−RS(h)∣≥ϵ}P\left\{\sup_{h \in H}|R(h) - R_S(h)| \geq \epsilon\right\} \leq \sum_{h \in H} P\{|R(h) - R_S(h)| \geq \epsilon\}$

$≤2∣H∣exp⁡(−2nϵ2M2)\leq 2|H|\exp\left(-\frac{2n\epsilon^2}{M^2}\right)$

5.4 泛化界

设 $δ=2∣H∣exp⁡(−2nϵ2M2)\delta = 2|H|\exp\left(-\frac{2n\epsilon^2}{M^2}\right)$ ，解得：

$ϵ=Mlog⁡∣H∣+log⁡(2/δ)2n\epsilon = M\sqrt{\frac{\log|H| + \log(2/\delta)}{2n}}$

因此，以至少 $1−δ1-\delta$ 的概率：
$sup⁡h∈H∣R(h)−RS(h)∣≤Mlog⁡∣H∣+log⁡(2/δ)2n\sup_{h \in H}|R(h) - R_S(h)| \leq M\sqrt{\frac{\log|H| + \log(2/\delta)}{2n}}$

关键洞察：假设类越大（ $∣ H ∣$ 越大），泛化界越松！

6. VC维理论

6.1 动机

当假设类 $H$ 包含无穷多个假设时，如何分析泛化性能？

核心思想：虽然 $H$ 可能无穷大，但对于固定的训练集，我们可以将假设按照它们在训练集上的预测结果进行分组。

6.2 增长函数

定义：假设类 $H$ 的增长函数定义为：
$ΠH(n)=max⁡X1,…,Xn∣{(h(X1),…,h(Xn)):h∈H}∣\Pi_H(n) = \max_{X_1,\ldots,X_n} |\{(h(X_1),\ldots,h(X_n)) : h \in H\}|$

直观含义：对于 $n$ 个样本点，假设类 $H$ 最多能产生多少种不同的分类结果。

6.3 打散（Shattering）

定义：数据点集合 ${X1,…,Xn}\{X_1,\ldots,X_n\}$ 被假设类 $H$ 打散，当且仅当 $H$ 能实现所有可能的二元预测，即：
$ΠH(n)=2n\Pi_H(n) = 2^n$

6.4 VC维

定义：假设类 $H$ 的VC维是能被 $H$ 完全打散的最大集合的大小：
$VC-dim(H)=max⁡{n:ΠH(n)=2n}\text{VC-dim}(H) = \max\{n : \Pi_H(n) = 2^n\}$

6.5 VC维示例

示例1：区间函数类

$\{x \mapsto 1_{\{x \in (a,b)\}} : a < b \in \mathbb{R}\}$

$ΠH(1)=2\Pi_H(1) = 2$
$ΠH(2)=4\Pi_H(2) = 4$
$ΠH(3)=7<23\Pi_H(3) = 7 < 2^3$

VC维 = 2

示例2： $R2\mathbb{R}^2$ 中的线性分类器

$\{(x_1,x_2) \mapsto 1_{\{w_1x_1 + w_2x_2 + b \geq 0\}} : w_1,w_2,b \in \mathbb{R}\}$

通过几何分析可以证明：

可以打散3个点
不能打散任意4个点

VC维 = 3

6.6 Sauer引理

定理：设假设类 $H$ 的VC维为 $d$ ，则对所有 $\geq d$ ：
$ΠH(n)≤(end)d\Pi_H(n) \leq \left(\frac{en}{d}\right)^d$

6.7 基于VC维的泛化界

通过复杂的分析（涉及Rademacher复杂度等高级技术），可以证明：

以至少 $1−δ1-\delta$ 的概率：
$sup⁡h∈H∣R(h)−RS(h)∣≤M32(dlog⁡(en/d)+log⁡(8/δ))n\sup_{h \in H}|R(h) - R_S(h)| \leq M\sqrt{\frac{32(d\log(en/d) + \log(8/\delta))}{n}}$