4.6 基于正则化的算法

• 算法家族:

  • 受到SRM方法的启发
  • 基于正则化的算法家族

• 假设集:

  • 选择复杂的家族 $\mathcal{H}$:
  • 嵌套假设集 ${\mathcal{H}}_{\gamma }$
    • $\mathcal{H}={\bigcup }_{\gamma >0}{\mathcal{H}}_{\gamma }$
    • 不可数并集

• 选择标准:

  • $\mathcal{H}$ 通常选为:
  • 在 $x$ 上的连续函数空间中稠密
  • 示例:
    • 所有线性函数的集合（高维空间）
    • 函数子集 ${\mathcal{H}}_{\gamma }$:
      • 范数被 $\gamma$ 限制
      • ${\mathcal{H}}_{\gamma }=\{x\mapsto \mathbf{w}\cdot \mathbf{\Phi }(x):\Vert \mathbf{w}\Vert \le \gamma \}$
  • 密度证明:
    • 对于某些 $\mathbf{\Phi }$ 的选择和高维空间:
    • 可以证明 $\mathcal{H}$ 在 $X$ 上的连续函数空间中稠密

• 扩展SRM方法:

  • 给定标记样本 $S$
  • 选择 $h$ 的优化问题:

  \mathop{\operatorname{argmin}}{\gamma > 0, h \in {H}{\gamma}} \widehat{R}{S}(h) + \Re{m}(\mathcal{H}_{\gamma}) + \sqrt{\frac{\log \gamma}{m}}

• 惩罚项:

  • 其他惩罚项 $\mathrm{pen}(\gamma ,m)$ 可替代特定选择:
  • $\mathrm{pen}(\gamma ,m)={\mathfrak{R}}_m({\mathcal{H}}_{\gamma })+\sqrt{\frac{\log \gamma }{m}}$

• 约束优化问题:

  • 存在函数 $\mathcal{R}:\mathcal{H}\to \mathbb{R}$:
  • 对于任何 $\gamma >0$，约束优化问题可以等价为无约束优化问题:
  • $${\mathrm{argmin}}_{h\in \mathcal{H}}{\hat{R}}_S(h)+\lambda \mathcal{R}(h)$$

• 正则项和超参数:

  • 对于某些 $\lambda >0$:
  • $\mathcal{R}(h)$ 被称为正则项
  • $\lambda$ 被视为超参数（最优值通常未知）

• 正则项选择:

  • 通常选为 $\parallel h\parallel$ 的增函数
  • 对于某些范数 $\parallel \cdot \parallel$ 的选择
  • 当 $\mathcal{H}$ 是希尔伯特空间的子集时

• 正则化参数:

  • 变量 $\lambda$ 被称为正则化参数
  • 较大的 $\lambda$ 值会惩罚更复杂的假设
  • 接近或等于零的 $\lambda$ 时，正则项没有效果
  • 算法与ERM相一致

• 实践中的选择:

  • $\lambda$ 通常通过交叉验证或 $n$-折交叉验证选择

• 正则项选择:

  • 选择 $\parallel h{\parallel }_p$:
    • 对于某些范数和 $p\ge 1$ 的选择
    • 是 $h$ 的凸函数
    • 原因: 任何范数都是凸的

• 零一损失:

  • 目标函数的第一项为非凸
  • 使得优化问题在计算上变得困难

• 实践中的解决方案:

  • 大多数基于正则化的算法:
    • 使用零一损失的凸上界
    • 用该凸替代的实证值替换实证零一项

• 得到的优化问题:

  • 是凸的
  • 比SRM更有效的解决方案

• 未来研究:

  • 下一节将研究这类凸替代损失的属性