机器学习

监督学习的期望损失与最优性推导

监督学习的基本设定

输入空间：$ x \in \mathbb{R}^d $（高维，$ d \gg 1 $）；输出空间：$ y \in \mathbb{R}^k $；
样本：$ (X_i, Y_i) $（$ i=1,2,\dots,m $），来自**联合分布 $ p(x,y) $**；
目标：确定函数 $ f: \mathbb{R}^d \to \mathbb{R}^k $，使对输入 $ x $，输出 $ f(x) $ 尽可能接近真实标签 $ y $。

损失函数与期望损失

损失函数：衡量预测值与真实值的差异，记为 $ \ell: y \times y \to \mathbb{R} $（如分类任务中，$ \ell(\hat{y}, y) = 0 $ 当且仅当 $ \hat{y} = y $，否则为正）；
期望损失：函数 $ f $ 的整体性能，定义为
$L(f) = \mathbb{E}_{(X,Y) \sim p} \left[ \ell(f(X), Y) \right]$
（对所有样本的损失取期望，反映泛化性能）。

最优函数的存在性与最优性

定义**条件期望下的最优函数**：

$f^*(x) = \arg\min_{a \in \mathbb{R}^k} \mathbb{E}\left[ \ell(a, Y) \,\big|\, X = x \right]$

（对每个输入 $ x $，选择使"给定 $ X=x $ 时 $ Y $ 的条件损失期望最小"的 $ a $ 作为 $ f^*(x) $）。

最优性证明：对任意函数 $ f $，有

$L(f) \geq L(f^*)$

推导：利用期望的塔式性质（重期望公式），

$\begin{align*} L(f) &= \mathbb{E}_X \left[ \mathbb{E}_Y \left[ \ell(f(X), Y) \,\big|\, X \right] \right] \\ &\geq \mathbb{E}_X \left[ \min_{a} \mathbb{E}_Y \left[ \ell(a, Y) \,\big|\, X \right] \right] \\ &= \mathbb{E}_X \left[ \mathbb{E}_Y \left[ \ell(f^*(X), Y) \,\big|\, X \right] \right] = L(f^*) \end{align*}$

（对每个 $ X=x $，内层期望在 $ a=f^*(x) $ 时取到最小值，故整体期望满足不等式）。

监督学习与非参数估计的核心框架

监督学习的基础设定

分布建模：将输入 $ X $ 与输出 $ Y $ 的关系建模为 $ \mathcal{X} \times \mathcal{Y} $ 上的**联合分布 $ \mathbb{P} $**，即 $ (X,Y) \sim \mathbb{P} $。
模型假设：
参数模型：假设 $ \mathbb{P} \in {\mathbb{P}_\theta: \theta \in \Theta} $（$ \Theta \subset \mathbb{R}^d $ 为参数空间）；
非参数模型：不预设分布的参数形式，更具一般性。

风险最小化与目标函数

损失函数：选择 $ \ell: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R} $，衡量预测值与真实值的差异（如回归用平方损失 $ \ell(a,y) = \frac{1}{2}(a - y)^2 $，分类用指示损失 $ \ell(a,y) = \mathbb{1}_{a \neq y} $）。
总体风险：目标是最小化**期望损失**（泛化风险）：
$f^* = \arg\min_{\text{可测 } f} \mathcal{L}(f) = \mathbb{E}_{(X,Y) \sim \mathbb{P}} \left[ \ell(f(X), Y) \right]$
任务特例：
回归：$ \mathcal{Y} = \mathbb{R} $，$ f^*(x) = \mathbb{E}[Y \mid X = x] $（条件期望为最优预测）；
分类：$ \mathcal{Y} = [K] = {1,\dots,K} $，$ f^*(x) = \arg\max_{k \in [K]} \mathbb{P}(Y = k \mid X = x) $（后验概率最大类为最优类别）。

经验风险最小化（ERM）

给定训练数据 $ (X_1,Y_1),\dots,(X_n,Y_n) \stackrel{\text{iid}}{\sim} \mathbb{P} $，定义**经验风险**：

$\hat{\mathcal{L}}(f) = \frac{1}{n} \sum_{i=1}^n \ell(f(X_i), Y_i)$

ERM 是找函数 $ \hat{f} \in \mathcal{F} $（假设空间）最小化经验风险：

$\hat{f} = \arg\min_{f \in \mathcal{F}} \hat{\mathcal{L}}(f)$

（例：平方损失+线性假设空间时，ERM 等价于最小二乘法）。

非参数估计的误差分解

问题设定：从数据 $ Z_1,\dots,Z_n \stackrel{\text{iid}}{\sim} \mu_Z $ 估计 $ f^* $，通过 ERM 选 $ \hat{f} \in \mathcal{F} $，再用求解器 $ \mathcal{A}(\tau) $ 输出近似解 $ f_{\mathcal{A}(\tau)} $（满足 $ \hat{\mathcal{L}}(f_{\mathcal{A}(\tau)}) \leq \hat{\mathcal{L}}(\hat{f}) + \tau $）。
Excess Risk 分解：目标是约束 $ \mathcal{E}(f_{\mathcal{A}(\tau)}) = \mathcal{L}(f_{\mathcal{A}(\tau)}) - \mathcal{L}(f^*) $，分解为三部分：
$ \varepsilon_{\text{sta}} $：统计误差（经验风险与总体风险的偏差）；
$ \varepsilon_{\text{app}} $：逼近误差（假设空间 $ \mathcal{F} $ 对 $ f^* $ 的近似能力）；
$ \varepsilon_{\text{opt}} $：优化误差（求解器与 ERM 最优解的偏差）。

具体分解式：

$\mathcal{L}(f_{\mathcal{A}(\tau)}) - \mathcal{L}(f^*) = \underbrace{[\mathcal{L}(f_{\mathcal{A}(\tau)}) - \hat{\mathcal{L}}(f_{\mathcal{A}(\tau)})]}_{\text{统计误差}} + \underbrace{[\hat{\mathcal{L}}(f_{\mathcal{A}(\tau)}) - \hat{\mathcal{L}}(\hat{f})]}_{\text{优化误差}} + \underbrace{[\hat{\mathcal{L}}(\hat{f}) - \mathcal{L}(\hat{f})]}_{\text{统计误差}} + \underbrace{[\mathcal{L}(\hat{f}) - \mathcal{L}(f^*)]}_{\text{逼近误差}}$

压缩感知与微分方程数值解

压缩感知的优化模型

考虑**压缩感知**问题：在观测 $ y = \Psi x + \varepsilon $（$ \Psi $ 为感知矩阵，$ \varepsilon $ 为噪声）下，最小化稀疏性度量 $ |x|_1 $，即

$\min \|x\|_1 \quad \text{约束} \quad y = \Psi x + \varepsilon$

引入**正则化项**（平衡稀疏性与拟合度），转化为无约束优化：

$\min \|x\|_1 + \lambda \|y - \Psi x\|_2^2$

（$ \lambda > 0 $ 为正则化参数）。

求解思路：构造拉格朗日函数

$\mathcal{L}(x, \lambda) = \|x\|_1 + \lambda^T (y - \Psi x)$

并通过**对偶问题**或梯度类方法（如ISTA/FISTA）求解。

次高斯分布（Sub-Gaussian Distribution）

1. 次高斯分布的定义与尾部估计

次高斯分布（sub-Gaussian）的核心是**矩生成函数（MGF）的指数上界**：若随机变量 X 满足存在 σ² > 0，使得对所有 s ∈ ℝ，

$\mathbb{E}(e^{sX}) \leq \exp\left(\frac{\sigma^2 s^2}{2}\right) 则称 X 服从参数为 σ² 的次高斯分布，记为 X ~ sub-G(σ²)。 **尾部估计**：由 Markov 不等式（P(X > t) ≤ P(e^{sX} > e^{st}) ≤ e^{-st} E(e^{sX})），结合 MGF 的上界，取最优 s 可得： ```math P(X > t) \leq \exp\left(-\frac{t^2}{2\sigma^2}\right)$

同理对双侧尾部 P(|X| > t)，可得 P(|X| > t) ≤ 2exp(-t²/(2σ²))，体现 "次高斯分布尾部指数衰减" 的性质。

2. 次高斯分布的线性不变性

若 X ~ sub-G(σ²)，则对任意向量 u，线性组合 u^T X 仍服从次高斯分布：

$u^T X \sim \text{sub-G}(\sigma^2 \|u\|_2^2) （体现次高斯性在 "线性变换下保持" 的特点，是高维概率中处理随机向量的关键性质）。 ### 3. Hoeffding 引理：有界随机变量的次高斯性对**有界随机变量** X ∈ [a, b]，定义矩生成函数的对数 ψ(s) = log E(e^{sX})，则： - 一阶导数：ψ'(s) = E(e^{sX}) / E(Xe^{sX}) = E_α(X)（其中 dα = e^{sX} dP / E(e^{sX}) 是 "倾斜测度"）； - 二阶导数：ψ''(s) = Var_α(X)（倾斜测度下的方差），且由 X 有界 [a, b]，得方差上界： ```math \text{Var}_\alpha(X) \leq \frac{(b-a)^2}{4}$

因此，ψ(s) 作为凸函数，满足**上界估计**：

$\psi(s) \leq \frac{(b-a)^2 s^2}{4} 即 E(e^{sX}) ≤ exp((b-a)²s²/4)，故有界随机变量是次高斯分布（参数 σ² = (b-a)²/4）。 --- *添加时间: 2026-04-07* --- ## 次高斯随机变量的最大值与覆盖定理 ### 1. 最大值的期望与大偏差（次高斯情形）设 Z = max_{1≤i≤N} X_i，其中 X_i 是次高斯随机变量（满足 E[e^{sX_i}] ≤ exp(σ_i² s²/2)），则： #### 期望估计（MGF 技巧）由 Jensen 不等式和 MGF（矩生成函数）， ```math \mathbb{E}[Z] = \frac{1}{s} \mathbb{E}[\log e^{sZ}] \leq \frac{1}{s} \log \mathbb{E}[e^{sZ}]$

再由 "最大值的 MGF ≤ 各变量 MGF 之和"（E[e^{sZ}] = E[max_i e^{sX_i}] ≤ ∑_i E[e^{sX_i}]），结合次高斯 MGF 的上界，得：

$\mathbb{E}[Z] \leq \frac{1}{s} \log N + \frac{1}{2s} \sum \sigma_i^2 s 取最优 s = √(2 log N) / σ（假设 σ_i = σ），化简得**期望上界**： ```math \mathbb{E}[Z] \leq \sigma\sqrt{2\log N}$

大偏差界

由 Union 界（联合界），

$P(Z > t) = P(\max_i X_i > t) \leq \sum_i P(X_i > t) 再由次高斯变量的尾部界 P(X_i > t) ≤ exp(-t²/(2σ²))，得： ```math P(Z > t) \leq N \exp\left(-\frac{t^2}{2\sigma^2}\right)$

2. 有限覆盖定理：将 "无限" 转化为 "有限"

考虑高维空间中 "无限个方向 θ" 的最大值 max_{θ∈B_2} θ^T X（B_2 是欧氏单位球），需通过**有限覆盖**将其转化为 "有限个方向 z∈N" 的最大值：

覆盖数（packing 数）

存在有限点集 N ⊂ B_2，使得对任意 θ ∈ B_2，存在 z ∈ N 满足 ‖θ - z‖_2 ≤ ε。覆盖数满足上界：

$N(B_2, \|\cdot\|_2, \varepsilon) \leq \left(\frac{3}{\varepsilon}\right)^d （d 是空间维度，体现 "高维空间中用有限点覆盖单位球" 的可能性）。 #### 最大值的期望估计（覆盖后）由覆盖的近似性，max_{θ∈B_2} θ^T X ≤ max_{z∈N} z^T X + ε‖X‖_2。结合次高斯性（若 X 是次高斯向量，‖X‖_2 的期望可控），最终可得： ```math \mathbb{E}\left[\max_{\theta \in B_2} \theta^T X\right] \leq \sigma\sqrt{2\log N}$

（将 "无限方向的最大值" 转化为 "有限覆盖点的最大值"，实现高维问题的有限化处理）。

添加时间: 2026-04-07

稀疏参数估计

1. 稀疏性假设与基本估计式

假设真实参数 θ* 是**稀疏的**，即非零元个数 ‖θ*‖_0 = s ≪ n（n 为样本量）。对估计量 θ̂_k，核心推导涉及：

二次型上界：利用柯西不等式或凸性，有

$\|X(\hat{\theta}_{t+s} - \theta^*)\|_2^2 \leq 2\varepsilon^T X(\hat{\theta}_{t+s} - \theta^*) （将范数平方转化为线性型，便于结合期望或概率分析）； - **残差平方和**：观测值与拟合值的残差平方和为 ‖Y - Xθ‖_2²，是衡量拟合优度的核心指标。 ### 2. 估计量的概率界（1-δ 置信）在概率 1-δ 下，估计量 θ̂_k 与真实参数 θ* 的偏差满足上界： ```math \|\hat{\theta}_k - \theta^*\| \leq \frac{\sigma^2 k}{n} \log\left(\frac{2ke}{d}\right) + \frac{\sigma^2 k}{n} \log\left(\frac{1}{\delta}\right) + \frac{\sigma^2}{n} \log\left(\frac{16}{\delta}\right)$

（其中 σ² 是噪声方差，d 是参数维度，k 是迭代或模型复杂度相关指标。该界体现 "偏差随样本量 n 增大而减小，随稀疏度 s、维度 d 增大而增大" 的规律）。

3. 风险（均方误差）的定义

定义估计量 θ̂ 的**风险**（均方误差）为：

$\mathcal{E}(\hat{\theta}) = \mathbb{E}_{X,Y}\left[\|\hat{\theta} - \theta^*\|_{\tilde{E}[Z]}^2\right] = \mathbb{E}_Y\left[\|\hat{\theta} - \theta^*\|_{\tilde{E}}^2\right] （对数据 X, Y 取期望，衡量 "估计量与真实参数的平均偏差"，是统计学习中评估模型性能的核心指标。当样本量足够大时，风险的阶为 O(sσ²/n)，体现 "稀疏性加速收敛" 的特点）。 --- *添加时间: 2026-04-07* --- ## 高维统计学习与稀疏估计 ### 1. 约束最小二乘估计的误差分析考虑线性模型 Y=Xθ*+ε（ε 是噪声，假设次高斯分布），θ̂_k 是参数 θ* 的估计量。核心估计式： - 残差范数控制：∥Xθ̂_k−Y∥_2² ≤ ∥Xθ*−Y∥_2² = 4∥ε∥_2²（体现估计的 "残差不增性"）； - 噪声的变换：定义 ε̃_i = X_i^T ε（将原始噪声 ε 变换为与特征 X_i 相关的新噪声项）。 ### 2. 集中不等式的应用（次高斯噪声）对次高斯分布的随机变量，利用**集中不等式**控制 "线性变换后的噪声上界"： ```math P\left(-\frac{s}{a}\tilde{\varepsilon}^T u > nt\right) \leq 2d\exp\left(-\frac{2nt^2}{\sigma^2}\right)$

（d 为特征维度，σ 是次高斯参数，通过指数尾部衰减控制概率）。

令该概率上界为 δ，解指数不等式得**阈值 t**：

$t = \sigma\sqrt{\frac{1}{2n}\log\frac{2d}{\delta}} ### 3. 参数估计的误差界结合残差与集中不等式，推导**估计误差的 ℓ2 范数界**： ```math \|\hat{\theta}_k - \theta^*\|_2^2 \leq \frac{\sigma^2}{n}\log d$

在**概率 1−δ** 下，进一步得到 "归一化误差" 的上界，最终误差界可简化为与 (log(d/δ))/n 同阶（体现 "高维下误差随对数维度和样本量的衰减"）。

4. 误差分解与支撑集约束

设 Δ=θ̂−θ*，A* 为 θ* 的**真实支撑集**（非零元的索引集）。通过正则化的稀疏诱导性，可得**支撑集补集的误差约束**：

$\|\Delta_{A^c}\|_2 \leq 3\|\Delta_A\|_2 （即 "非支撑集上的误差被支撑集上的误差控制"，体现稀疏估计的 "集中性"）。 ### 5. 正则化参数的选择为保证高维下的概率集中性，正则化参数 λ 需满足： ```math \lambda = 2\sigma\sqrt{\frac{2\ln(2d/\delta)}{n}}$

6. Lasso 误差界

结合支撑集约束与 Lasso 目标函数的最优性，最终推导**估计误差的上界**：

$\|\hat{\theta} - \theta^*\|_2 \lesssim \frac{\sigma\sqrt{|A^*| \cdot 2\ln(2d/\delta)}}{\gamma\sqrt{n}} （γ>0 为与特征矩阵 X 相关的 "强制性常数"，|A*| 是真实支撑集的大小，体现 "误差随样本量 n 增大而衰减，随稀疏度 |A*|、对数维度 ln(2d/δ) 增大而增大"） --- *添加时间: 2026-04-08* --- ## VC 维与打散数的概念 ### 1. VC 维与打散数的定义 - **打散数 $\Pi_{\mathcal{H}}(m)$**：假设类 $\mathcal{H}$ 对 $m$ 个样本能实现的"不同标签划分的数量"。 ```math \Pi_{\mathcal{H}}(m) = |\{(h(x_1), h(x_2), \cdots, h(x_m)) \mid x_i \in \mathcal{X}, h \in \mathcal{H}\}|$

VC 维 $\text{VC}(\mathcal{H})$：最大的 $m$ 使得 $\Pi_{\mathcal{H}}(m) = 2^m$（即能"完全打散" $m$ 个样本的所有 $2^m$ 种标签组合）。

2. 区间分类器的打散分析

考虑**区间分类器**（判断 $x$ 是否在区间 $[\alpha,\beta]$ 内），分析其对不同样本数 $m$ 的打散能力：

当 $m=2$：可验证 $\Pi_{\mathcal{H}}(2) = 4 = 2^2$（能完全打散 2 个样本的所有 4 种标签组合），故 $\text{VC}(\mathcal{H}) \geq 2$。
当 $m=3$：计算得 $\Pi_{\mathcal{H}}(3) = 7 < 2^3 = 8$（无法完全打散 3 个样本的所有 8 种标签组合），因此 $\text{VC}(\mathcal{H}) = 2$。

3. 单峰函数与假设空间的拓展

进一步假设"单峰函数"形式 $h(x; \alpha, b) = \text{sign}(\cdots)$（$x \in [a,b]$），通过分析这类函数对样本的划分能力，可推广到更一般的假设空间，验证其 VC 维是否与区间结构相关（核心逻辑："区间的线性划分能力限制了打散数的增长"）。

添加时间: 2026-04-11

凸优化与 L1 正则化

L1 问题的优化

考虑优化问题：

$x^* = \arg\min_{x \in \mathbb{R}^n} \left( \frac{1}{2n} \| A x - b \|^2 + \lambda \| x \|_1 \right)$

Proximal 算子

L1 正则化的 Proximal 算子（软阈值算子）：

$S_\lambda(t) = \begin{cases} 0, & |t| \leq \lambda \ t - \lambda, & t \geq \lambda \ t + \lambda, & t \leq -\lambda \end{cases}$

不动点算法：

$x^* = S_\lambda \left( x^* + \frac{1}{n} A^\top (b - A x^*) \right)$

迭代形式：

$x^{(k+1)} = S_\lambda \left( x^{(k)} + A^\top (b - A x^{(k)}) \right)$

次微分理论

凸函数的次微分（不要求连续）：

$f(y) \geq f(x) + z^\top (y - x), \forall y$

其中 $z$ 称为次微分。

绝对值函数的次微分： - $x > 0$ 时：$\partial |x| = \{1\}$ - $x < 0$ 时：$\partial |x| = \{-1\}$ - $x = 0$ 时：$\partial |x| = [-1, 1]$

凸优化的一阶条件

优化条件：

$\arg\min_{x \in \mathbb{R}^n} f(x) \iff 0 \in \partial f(x^*)$

例子：$f(x) = \frac{1}{2}(x - t)^2 + \lambda |x|$ - $x > 0$ 时：$\partial f(x) = (x - t) + \lambda$ - $x < 0$ 时：$\partial f(x) = (x - t) - \lambda$ - $x = 0$ 时：$\partial f(0) = [-t - \lambda, -t + \lambda]$

解： - 若 $|t| \leq \lambda$，则 $x^* = 0$ - 若 $t > \lambda$，则 $x^* = t - \lambda$ - 若 $t < -\lambda$，则 $x^* = t + \lambda$

即 $x^* = S_\lambda(t)$

L1 正则化的次微分

$\| x \|_1 \text{ 的次微分性质：} \| y \|_1 \geq \| x \|_1 + \langle z, y - x \rangle$

其中 $z$ 是 $\| \cdot \|_1$ 在 $x$ 处的次微分。

逐项分析：

$\sum_i (|y_i| - |x_i|) \geq \sum_i z_i (y_i - x_i)$

即 $|y_i| - |x_i| - z_i (y_i - x_i) \geq 0$，其中 $z_i \in \partial |x_i|$

光滑项的梯度

$\frac{\partial}{\partial x} \left( \frac{1}{2n} \| A x - b \|^2 \right) = \frac{1}{n} A^\top (A x - b)$

优化的一阶条件

次梯度为 0：

$\frac{1}{n} A^\top (A x^* - b) + \lambda \partial \| x^* \|_1 = 0$

凸集上的优化

凸集上的凸函数优化：

$g(x) = f(x) + \mathbb{1}_C(x)$

其中 $\mathbb{1}_C$ 是凸集 $C$ 的示性函数。

若 $x \notin C$，则 $\partial g = \emptyset$。

法锥与对偶范数

法锥定义

法锥：

$N_C(x) = \{ z \mid \langle z, y - x \rangle \leq 0, \forall y \in C \}$

最优性条件

凸集约束优化：

$-\nabla f(x^*) \in N_C(x^*)$

（若 $0 \in C$，$C$ 为凸锥）

对偶范数

对偶范数定义：

$\| x \|_* = \sup_{\|y\| \leq 1} \langle x, y \rangle$

对于矩阵 $A = U \Sigma V^\top$（奇异值分解），其谱范数的对偶范数为核范数。

L2 正则化的优化

优化问题：

$\frac{1}{2n} \| A x - b \|_2^2 + \lambda \| x \|_2$

一阶条件：

$\frac{1}{n} A^\top (A x^* - b) + \lambda \partial \| x^* \|_2 = 0$

辅助函数方法

辅助函数：

$H(x) = \frac{1}{2} \| x - d^* \|^2 + \lambda \| x \|_2$

最优性条件：

$0 \in \partial H(x) \iff \exists (x - d^*) + \lambda \partial \| x \|_2 = 0$

优化器总结

梯度下降类方法

SGD：$\theta_{t+1} = \theta_t - \eta_t \nabla L(\theta_t)$
动量法：$m_t = \beta m_{t-1} + (1-\beta)\nabla L(\theta_t)$
AdaGrad：自适应学习率，适合稀疏数据
Adam：结合动量和自适应学习率

二阶优化方法

Newton 法：使用二阶信息，收敛快但计算量大
共轭梯度：避免显式计算 Hessian 矩阵

Proximal 梯度法

针对非光滑正则项（如 L1）：

$x^{(k+1)} = \text{prox}_{\lambda r} \left( x^{(k)} - \eta \nabla f(x^{(k)}) \right)$

其中 $\text{prox}_{\lambda r}(x) = \arg\min_y \left( r(y) + \frac{1}{2\lambda} \|y - x\|^2 \right)$

添加时间: 2026-04-15