上海大学 机器学习 · 研究生　第 2 讲　学习问题的形式化 https://kaizhao.net/teaching/shu-ml-grad
第 2 讲

学习问题的形式化

风险、假设空间与归纳偏好
期望风险与经验风险 · 假设空间 · 泛化间隙 · 归纳偏好

监督学习问题的组织

① 输入输出
→
② 数据分布
→
③ 训练样本
→
④ 假设空间
→
⑤ 损失函数
训练目标
风险、经验风险最小化与复杂度
建模选择的延伸
归纳偏好：为什么这样选模型与目标

监督学习的基本要素

要素记号说明
① 输入与输出空间$\mathcal{X}$，$\mathcal{Y}$ 样本与标签的取值范围
② 数据分布$\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$ 未知，需从有限数据推断
③ 训练样本$S=\{(x_i,y_i)\}_{i=1}^{n}\sim\mathcal{D}^{n}$ 通常假设独立同分布抽取
④ 假设空间$\mathcal{H}\subseteq\{h:\mathcal{X}\to\mathcal{Y}\}$ 候选函数的集合，由建模者选定
⑤ 损失函数$\ell(\hat y,y)\ge 0$ 一次预测的代价
建模时需选定假设空间与损失函数。 分布未知，样本已给定。

① 输入与输出空间

房价预测：多种房屋特征 → 房屋总价

输入 $x$：一套房屋的特征

面积120 m²离地铁距离1.5 km
卫生间数量2 个房龄10 年
楼层8 楼学区A 学区
$$x=(x_1,x_2,\ldots,x_d)^\top\in\mathcal X\subseteq\mathbb R^d$$

学区等类别特征先编码；$d$ 为编码后的特征数。

→
模型 $h$将特征映射到总价
↓
预测 $\hat y=h(x)$房屋总价 / 万元
$$y\in\mathcal Y=\mathbb R$$
$x$ 是一套房屋的特征向量；$\mathcal X$ 是所有允许输入的特征向量的集合。

② 数据分布

$\mathcal D$ 描述：哪些房屋更常出现，以及它们的价格如何变化。

输入的分布

小户型与大户型各有多少？
不同房龄、学区的房屋各有多少？

$$p(x)$$

给定输入后的价格

已记录的特征相同，
总价仍可能受议价等因素影响。

$$p(y\mid x)$$
$$(x,y)\sim\mathcal D,\qquad p(x,y)=p(x)\,p(y\mid x)$$
目标分布通常未知；有限样本提供关于它的观测。

③ 训练样本

$$S=\{(x_i,y_i)\}_{i=1}^{n},\qquad x_i=(x_{i1},x_{i2},\ldots,x_{id})^\top$$
样本 $i$面积 $x_{i1}$ / m²距离 $x_{i2}$ / km总价 $y_i$ / 万元
1600.4294
21200.4522
31802.4680
$\vdots$$\vdots$$\vdots$$\vdots$
一行是一套房屋；$x_i$ 是输入，$y_i$ 是真实观测。

表中仅展开面积与距离，数值为教学构造。$n$ 为样本数，$d$ 为特征数。

③ 训练样本：独立同分布假设

记 $S\sim\mathcal{D}^n$ 时已假定样本独立同分布 （independent and identically distributed, i.i.d.）。 经典分析还要求训练与测试来自同一分布。

失效方式场景后果
跨地区分布偏移
distribution shift		 上海房屋数据训练
→ 东京房屋数据测试		 房屋特征分布、定价规律都可能变化
标签偏移
label shift		 疾病流行率随季节变化先验错配，需重新校准
非独立 时间序列；同一病人的多次采样 随机拆分可能高估性能
分布漂移 推荐系统、金融、用户行为原有评估可能不再适用
常见错误：将同一病人的不同切片同时纳入训练集与测试集。 模型可能利用个体身份信息获得偏乐观的成绩。 数据划分应以独立单元为准。

④ 假设空间：所有候选模型

以两个输入为例：面积 $x_1$、离地铁距离 $x_2$ → 总价 $y$

$$\mathcal H_1=\left\{h(x_1,x_2)=w_{00}+w_{10}x_1+w_{01}x_2 \;\middle|\; w_{00},w_{10},w_{01}\in\mathbb R\right\}$$
候选模型（示意）函数
$h_A\in\mathcal H_1$$h_A(x_1,x_2)=60+4x_1-20x_2$
$h_B\in\mathcal H_1$$h_B(x_1,x_2)=80+3x_1-10x_2$
定次数：确定模型范围；学系数：选出具体模型。
函数空间

实数系数可连续变化，候选模型有无穷多个。 参考阅读：CS229 讲义（PDF）

⑤ 常用损失函数

损失形式用于
0-1$\mathbb{1}[\hat y\ne y]$分类的真目标
平方$(\hat y-y)^2$回归
绝对值$|\hat y-y|$抗离群点
Huber分段两者折中
Hinge
合页		 $\max(0,1-y\hat y)$支持向量机，第 8 讲
对数$\log(1+e^{-y\hat y})$逻辑回归，第 5 讲
0-1 损失不连续，不便于梯度优化。 hinge 与对数损失提供凸替代目标。

期望风险与经验风险

期望风险 expected risk

面向总体分布 $\mathcal D$
$$R(h)=\mathbb E_{(x,y)\sim\mathcal D}\big[\ell(h(x),y)\big]$$

从 $\mathcal D$ 抽取新样本时的平均损失

分布未知 → 通常无法直接计算
希望降低的泛化目标

经验风险 empirical risk

面向已有训练样本 $S$
$$\widehat R_S(h)=\frac1n\sum_{i=1}^{n}\ell\big(h(x_i),y_i\big)$$

在 $n$ 个训练样本上算出的平均损失

样本已知 → 可以直接计算
训练时的优化依据
经验风险看“做过的题”；期望风险看“新题平均做得怎样”。

经验风险最小化

① 给定训练集
$D_{\rm train}=S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$
② 逐个算损失
模型预测 $h(x_i)$，与真实值 $y_i$ 比较：$\ell(h(x_i),y_i)$
③ 求平均损失
$$\widehat R_S(h)=\frac1n\sum_{i=1}^{n}\ell\big(h(x_i),y_i\big)$$
④ 寻找最优模型
$$\hat h\in\arg\min_{h\in\mathcal H}\widehat R_S(h)$$
在候选范围 $\mathcal H$ 内，找到使训练集平均损失最小的最优（optimal）模型 $\hat h$。
设定候选范围模型类型、复杂度
→
最小化经验风险学习模型参数
→
验证集比较选择类型与复杂度

经验风险最小化：Empirical Risk Minimization，ERM。

模型复杂度与两条误差曲线

●训练样本 ▲测试样本 拟合模型 真实函数
训练误差 测试误差
模型　$h_w(x)=w_0+w_1x+\cdots+w_dx^d$
平方损失　$\ell(h_w(x_i),y_i)=(h_w(x_i)-y_i)^2$
$$\hat w_d\in\arg\min_{w\in\mathbb R^{d+1}}\frac1n\sum_{i=1}^{n}\left(w_0+w_1x_i+\cdots+w_dx_i^d-y_i\right)^2,\qquad \hat h_d=h_{\hat w_d}$$

合成数据：$y=\sin(2\pi x)+\varepsilon$。固定训练集；每个次数 $d$ 分别求最优系数，测试集不参与拟合。

泛化间隙与误差分解

  • ERM 在候选空间内最小化训练误差
  • 泛化间隙（generalization gap）：$R(\hat h)-\widehat R_S(\hat h)$

把与最优解的差距拆开：

$$\underbrace{R(\hat h)-R(h^{*})}_{\text{估计误差}}\;+\; \underbrace{R(h^{*})-R(h^{\text{Bayes}})}_{\text{近似误差}}$$
$\mathcal{H}$ 变大近似误差估计误差
能表示的函数更多 不增 可能增大

$h^{*}$ 为假设空间内期望风险最小的模型，$h^{\text{Bayes}}$ 为全体候选函数中的最优者；假定二者存在。

同一个模板，不同的算法

$$\min_{h\in\mathcal{H}}\ \ \widehat{R}_S(h)\ +\ \lambda\,\Omega(h)$$
损失正则项得到的方法第几讲
平方无最小二乘线性回归4
平方$\|w\|_2^2$岭回归4
对数$\|w\|_2^2$正则化逻辑回归5
Hinge$\|w\|_2^2$支持向量机8
损失衡量拟合程度，正则项表达对模型的偏好。

演绎与归纳

Deduction · 演绎

一般 → 个别 general → specific
所有天鹅都是白色的。
这是一只天鹅。
∴ 它是白色的。
前提真、推理有效 ⇒ 结论必真

Induction · 归纳

个别 → 一般 specific → general
见过的天鹅都是白色的。
∴ 所有天鹅都是白色的。
结论可能被新观察推翻

澳大利亚的黑天鹅就是反例。

监督学习中的归纳

有限观测$(x_1,y_1),\ldots,(x_n,y_n)$
→
学习函数$\hat y=f(x)$
→
未见输入$x\in\mathcal X$
有限套房屋的成交记录 → 未成交房屋的价格预测
从“样本上成立”到“未见输入上也适用”，就是归纳的跨越。

连续输入空间中，有限样本之外还有无穷多个输入。

归纳偏好 inductive bias

建模选择的延伸：选模型范围、损失或正则项时带入的额外假定与选择倾向。

$$\begin{aligned} f_1(x)&=2x\\[.25em] f_2(x)&=2x+(x-1)(x-2)(x-3)(x-4) \end{aligned}$$
输入 $x$12345
$f_1(x)$246810
$f_2(x)$246834

第 5 项为未见输入。

偏好更简单的规律
→ 选择 $f_1$ → 预测 10。

已知四点上相同，未见输入上不同。

●已知点 $f_1(x)$ $f_2(x)$

房价预测中的归纳偏好 关联：④ 假设空间的选择

● 六套训练房屋◆ 当前房屋预测高度与颜色：总价
$h_A(x_1,x_2)=80+3.8x_1-35x_2$
$h_B(x_1,x_2)=h_A(x_1,x_2)$
$\displaystyle\quad+\frac{(x_1-60)(x_1-120)(x_1-180)}{1000}$
偏好平面关系
→ 限定一次模型 → 选择 $h_A$

合成房屋数据。两种曲面都通过训练点，却对新房屋给出不同预测；两张曲面使用相同坐标与色阶。

本讲小结

  1. 训练时最小化经验风险，期望降低的是期望风险
  2. 训练表现可能偏乐观，须用独立数据评估
  3. 数据本身不足以确定唯一假设，须引入归纳偏好
  4. 许多监督学习方法可写为 $\min_h\widehat{R}_S(h)+\lambda\Omega(h)$ 的实例
模型评估与选择：用哪些数据、哪些指标，判断模型在新样本上的表现。

记号约定

记号含义
$x\in\mathbb{R}^{d}$单个样本的特征向量
$X\in\mathbb{R}^{n\times d}$设计矩阵，一行一个样本
$y\in\mathbb{R}^{n}$标签向量
$w,\theta$模型参数
$\mathcal{H}$假设空间
$\ell(\cdot,\cdot)$损失函数
记号含义
$R(h)$期望风险
$\widehat{R}_S(h)$样本 $S$ 上的经验风险
$\lambda$正则化系数
$\Omega(h)$正则项
$\mathbb{1}[\cdot]$示性函数
$\|\cdot\|_p$$\ell_p$ 范数

延伸阅读

教材对应章节

  • 周志华《机器学习》
    第 1 章 1.3–1.4：假设空间与归纳偏好
  • 李航《统计学习方法》
    第 1 章 1.3–1.7：三要素、模型评估、正则化与交叉验证

进阶方向

问题参考内容
如何估计新样本表现第 3 讲：评估指标与数据划分
如何选择模型复杂度第 3 讲：验证集与交叉验证
泛化间隙的定量分析CS229：学习理论
具体模型如何表达偏好第 4–8 讲：回归、分类与核方法

第 2 讲结束

课程首页
全部讲次

← → 翻页 · o 总览 · s 演讲者视图 · f 全屏 · 网址后加 ?print-pdf 可导出 PDF