机器学习—2—理论基础

2026/10/09

机器学习—2—理论基础(更新中)

unknown pattern -> f:未知规律,在数学上记作函数 $f:X→Y$。机器学习的目标就是为了去逼近(近似)这个未知的 $f$(即希望学出来的结果 $g≈f$)。

training data:训练数据 / 经验样本 $D$,在数学上记为 $D={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$。

hypothesis sets:假设空间 / 候选模型集合 $H$。整个集合 $H$ 就是你的模型所能表达的所有可能性。在数学上记作 $H={h_1,h_2,…}$。

$H$ 限制了机器人的“思考范围”。如果未知的真实规律 $f$ 是一条复杂的波浪曲线,而你的 $H$ 仅仅是一堆直线,那算法再聪明也只能挑出一条直线,永远不可能完美还原 $f$。

把这三个术语串联起来,机器学习的整个过程就是:

$$ \text{未知规律 } f \xrightarrow{\text{产生}} \text{训练数据 } \mathcal{D} $$

$$ 演算法 (Algorithm A) 看着数据 D,从假设集合 H 中精挑细选出一个最好的 g \\ 最终希望:g≈f(挑出来的这个假设 g 能最大程度贴近未知的真实规律 f) $$

1.Percetron Linear Algorithm 线性感知器算法

核心思想:知错就改

1.创建model x_1,x_2…,x_d h = sign(w^T * x)

2.找错误 if: $sign(w_t^T * x_n) != y_n$ then: $w_{t+1} = w_t + y_n * x_n$ 变化量是$y_n * x_n$,可以想象向量钝角相加变锐角,锐角相减变钝角

3.finally 一个完整的循环,不再发生错误,模型已经成功。

总结:sign函数的空间几何意义–》向量内积,锐角结果大于0,钝角结果小于0。初始化时 w 向量为0向量,更新后分界线是 w_t^T 的法线。

线形可分证明PLA

当数据线形可分时,证明PLA的可行性:

$$\frac{w_f^T}{|||w_f|} \quad \frac{w_T}{||w_T||} \ge \sqrt{T} \cdot \text{constant}$$

备注:

  1. $w_f$表示完美的分界线参数向量,$w_T$表示经过T次找错误更新后的参数向量。
  2. 左边的几何意义:两个向量归一化后的点积,也就是完美向量 $w_f$ 与当前向量 $w_T$ 夹角的余弦值(cosθ):$\frac{w_f^T}{|||w_f|} \quad \frac{w_T}{||w_T||} = \cos\theta $

证明过程

1.感知器遇到某个样本 ($X_{n(t)}$,$y_{n(t)}$) 错误就会更新参数:$w_{t+1}=w_t+y_{n(t)}X_{n(t)}$

2.$w_0$ 累计 T 次更新后:$w_T = \sum_{t=1}^Ty_tX_t$

3.因为完美分界线 $w_f$,所以 $y_t(w_f^TX_t)>0$。定义样本中离分界线最近的距离为 $\rho = \min yn \frac{w_f^T}{||w_f||}x_n > 0$

4.由 1,2,3 式得:

$$\frac{w_f^T}{||w_f||} w_T = \sum_{t=1}^Ty_t (\frac{w_f^T}{||w_f||} X_t) \ge T \cdot \rho$$

5.令数据集中最大的样本模长为 $R = \max ||Xn||$

每次更新:$||w_t||^2 = ||w_{t-1} + y_nX_{t-1}||^2 = ||w_{t-1}||^2 + 2y_n(w_{t-1}^T X_{t-1}) + ||x_{t-1}||^2 \le ||w_{t-1}||^2 + R^2$

$w_0$ 累计 T 次更新后容易得出:$||w_t||^2 \le T \cdot R^2 \Longrightarrow ||w_T|| \le \sqrt{T} \cdot R$

6.因为 $||w||$ 大于0,由 5 式可得出:

$$\frac{1}{||w_T||} \ge \frac{1}{\sqrt{T} \cdot R}$$

7.因为 5,6 式子两边都大于 0,所以相乘不等式符号不变:

$$\frac{w_f^T}{|||w_f|} \quad \frac{w_T}{||w_T||} \ge \frac{T \cdot \rho}{\sqrt{T} \cdot R} = \sqrt{T} \cdot (\frac{\rho}{R}) = \sqrt{T} \cdot \text{constant}$$

常数 constant 就是 $\frac{\rho}{R}$

8(额外).因为两个向量的余弦值最大为1,i.e. $\cos (\theta) \le 0$ ,所以:

$$1 \ge \sqrt{T} \cdot (\frac{\rho}{R}) \Longrightarrow T \le \frac{R^2}{\rho ^2} = \frac{1}{\text{constant}^2} $$

总结:

  1. 余弦值的增长速度的下限是以 $\sqrt{T}$ 的速度增长的。(地板)
  2. 犯错修正次数 $T$ 必然有上限 $(T ≤ \frac {ρ^2}{R^2})$,证明了感知机算法一定会收敛并停止。(天花板) $$1_{天花板} \ge \cos{\theta} \ge {\sqrt{T} \cdot \text{constant}}_{地板} $$
  3. 随着 T 的增加,权重向量 $w_T$ 会越来越和完美向量 $w_f$ 在方向上重合,即回到了开始的结论, $\theta$ 越来越小。

思考

如果数据不是线性可分该怎么去做机器学习来找到目标函数呢? pocket算法

2.Multiclass Classification 多分类

机器学习分类(根据输出空间不同):

机器学习分类(不同的数据标注):

机器学习分类(不同的学习方法):

机器学习分类(不同的输入空间):

$\mu$

没关系,我们把公式先放一边,用一个具体例子来理解。

霍夫丁不等式联系机器学习

霍夫丁不等式数学公式:

$$P(|\hat{\mu}-\mu| > \epsilon) \le 2e^{-2N\epsilon^2}$$

hoffding-inquality

理解单个模型(单个h(x))

霍夫丁不等式(Hoeffding inequality)。它正好把图片中“罐子和抽弹珠”变成一个数学保证:抽出来的橙色比例,和罐子里真实的橙色比例,通常不会差得太远;样本越多,这种差距越小。

把弹珠变成数字:假设我们已经固定了一个模型 (h),然后随机抽 (N) 个样本来测试。对第 (i) 个样本记:

$$X_i = \begin{cases} 1, & \text{模型答错(橙色)} \ 0, & \text{模型答对(绿色)} \end{cases} $$

霍夫丁不等式告诉我们:

$$\Pr\left( |\hat{\mu} - \mu| > \epsilon \right) \leq 2e^{-2N\epsilon^2}$$

白话讲:样本数是 $(N)$ 时,抽样错误率和真实错误率相差至少 $(\epsilon)$ 的概率,最多有多大。它是对独立随机样本的样本平均值偏离真实平均值的概率进行上界估计;在学习问题里,每个样本的 $(0/1)$ 错误正好可以作为这样的变量。$> \epsilon$: 超过误差值,即超过可接受的范围,认为是不好的模型。$\le 2e^{-2N\epsilon^2}$:表示概率的上限,当N增大,或者误差接受范围增大,概率上限越低。单个模型的上限由接受误差范围以及抽样数量决定

有限数量分布集合:并集界(union bound)

通过并集界,推导到 M 个模型。

推论:有限个 (M) 个候选模型时,可以把单个模型的霍夫丁上界加 (M) 次,来控制“至少有一个模型遇到坏数据”的概率上限:

$$P(\text{至少一个模型是坏的}) \le \sum_{m=1}^MP(h_m是坏的) \le 2Me^{2N\epsilon^2}$$

推导过程: 当 hoeffding-inequality 扩展到 M 个 h 的不等式时,由并集界(union bound)可得出 M 个分布的存在坏分布的上界:

$$ Pr([(Eh_{in}^1-E_{out}^1)> \epsilon] \cup [(Eh_{in}^2-E_{out}^2)> \epsilon] … [(Eh_{in}^M-E_{out}^M)> \epsilon]) \ \le Pr([(Eh_{in}^{1}-E_{out}^{1})> \epsilon] + [(Eh_{in}^{2}-E_{out}^{2})> \epsilon] … [(Eh_{in}^{M}-E_{out}^{M})> \epsilon]) \ \le M \cdot 2e^{2N\epsilon^2} $$

因此,当 M 小时,坏模型(不好的模型)的概率上限更小,但是选择更少;相反地,当 M 大时,坏模型(不好的模型)的概率上限更大,但是模型选择更多。

思考:

  1. 同一类型的分布函数,$E_in$ 一样了,但是 $E_out$ 还是不一样。那么它对于 hoeffding-equaility 有什么意义呢?
  2. 如何推广到无限种的分类函数中去呢?

无限数量分布集合

增长函数 -> vc 维(shatter/break) -> 影子样本

dichotomy:Mini-hypothesis

growth function 成长函数:

brek point

bounding function

影子样本 S_一撇,当 $N \ge \frac{8}{\epsilon^2}$ 时:

$$P_{s_1}$$

总结:

  1. 霍夫丁不等式说明了,当N足够大时,h 的样本错误率接近真实错误率。
  2. 并集界(union bound)说明了 h 的数量越多,存在 h 不好的几率可能越大。

机器学习完整的推理过程:

  1. 单个假设:霍夫丁不等式证明,单个模型无法作弊(验证可行)。
  2. 有限假设:联合界证明,有限个模型无法作弊( $M$ 较小时可行)。
  3. 无穷危机:现实模型有连续参数, $M=∞$ 导致联合界报废。
  4. 影子样本与对称化:用第二组样本代替未知的真实分布,将整个问题局限在有限的 $2N$ 个点上。
  5. VC 维与多项式:在有限点上,有效行为从 $∞$ 降至多项式级别 $(2N)_{d_VC}$。
  6. 最终可行:多项式与霍夫丁的指数衰减碰撞,概率趋于 0。机器学习在数学上被证明完全可行。

参考

  1. 林轩田:机器学习基石
  2. https://tangshusen.me/2018/12/09/vc-dimension/