机器学习—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,…}$。
- 如果你决定用感知机(PLA),你的假设空间 $H$ 就是“空间中所有可能切分数据的超平面(所有可能角度和位置的直线/平面)”;
- 如果你用二次曲线,$H$ 就是“所有的抛物线/双曲线模型”;
- 如果你用深度神经网络,$H$ 就是“该网络架构下所有参数组合所能形成的复杂函数”。
$H$ 限制了机器人的“思考范围”。如果未知的真实规律 $f$ 是一条复杂的波浪曲线,而你的 $H$ 仅仅是一堆直线,那算法再聪明也只能挑出一条直线,永远不可能完美还原 $f$。
把这三个术语串联起来,机器学习的整个过程就是:
- f:是我们要抓的幕后真凶(客观存在但未知);
- D 是案发现场的证据照片(历史数据);
- H 是刑警脑海里的嫌疑人候选名单(备选函数库);
- 学习算法就是刑警根据证据 $D$,从名单 $H$ 中锁定嫌疑最大的那个人 $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的可行性:
备注:
- $w_f$表示完美的分界线参数向量,$w_T$表示经过T次找错误更新后的参数向量。
- 左边的几何意义:两个向量归一化后的点积,也就是完美向量 $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 式得:
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 式可得出:
7.因为 5,6 式子两边都大于 0,所以相乘不等式符号不变:
常数 constant 就是 $\frac{\rho}{R}$
8(额外).因为两个向量的余弦值最大为1,i.e. $\cos (\theta) \le 0$ ,所以:
总结:
- 余弦值的增长速度的下限是以 $\sqrt{T}$ 的速度增长的。(地板)
- 犯错修正次数 $T$ 必然有上限 $(T ≤ \frac {ρ^2}{R^2})$,证明了感知机算法一定会收敛并停止。(天花板) $$1_{天花板} \ge \cos{\theta} \ge {\sqrt{T} \cdot \text{constant}}_{地板} $$
- 随着 T 的增加,权重向量 $w_T$ 会越来越和完美向量 $w_f$ 在方向上重合,即回到了开始的结论, $\theta$ 越来越小。
思考
如果数据不是线性可分该怎么去做机器学习来找到目标函数呢? pocket算法
2.Multiclass Classification 多分类
机器学习分类(根据输出空间不同):
- *binary classification:二分类,输出2个离散值
- multiclass classification:多分类,输出多个离散值
- *regression classification:输出实数
- structured learning:输出是结构化的数据
机器学习分类(不同的数据标注):
- *supervised learning:all $y_n$
- unsupervised learning: (clustering 分群):no $y_n$
- semi-supervised learning:some $y_n$
- reinforcement learning:implicit $y_n$ by goodness($y_n^~$)
机器学习分类(不同的学习方法):
- batch learning
- online learning
- active learning
机器学习分类(不同的输入空间):
- contrete
- raw
- abstract
$\mu$
没关系,我们把公式先放一边,用一个具体例子来理解。
霍夫丁不等式联系机器学习
霍夫丁不等式数学公式:

理解单个模型(单个h(x))
霍夫丁不等式(Hoeffding inequality)。它正好把图片中“罐子和抽弹珠”变成一个数学保证:抽出来的橙色比例,和罐子里真实的橙色比例,通常不会差得太远;样本越多,这种差距越小。
把弹珠变成数字:假设我们已经固定了一个模型 (h),然后随机抽 (N) 个样本来测试。对第 (i) 个样本记:
- 罐子里橙色弹珠的真实比例,也就是模型真实错误率,记作 $(\mu)$。
- 抽样中看到的橙色比例,记作 $(\hat\mu)$。它就是测试错误率,例如 (100) 个样本错了 (4) 个,那么 ($\hat\mu=4%$)。
霍夫丁不等式告诉我们:
白话讲:样本数是 $(N)$ 时,抽样错误率和真实错误率相差至少 $(\epsilon)$ 的概率,最多有多大。它是对独立随机样本的样本平均值偏离真实平均值的概率进行上界估计;在学习问题里,每个样本的 $(0/1)$ 错误正好可以作为这样的变量。$> \epsilon$: 超过误差值,即超过可接受的范围,认为是不好的模型。$\le 2e^{-2N\epsilon^2}$:表示概率的上限,当N增大,或者误差接受范围增大,概率上限越低。单个模型的上限由接受误差范围以及抽样数量决定
有限数量分布集合:并集界(union bound)
通过并集界,推导到 M 个模型。
推论:有限个 (M) 个候选模型时,可以把单个模型的霍夫丁上界加 (M) 次,来控制“至少有一个模型遇到坏数据”的概率上限:
推导过程: 当 hoeffding-inequality 扩展到 M 个 h 的不等式时,由并集界(union bound)可得出 M 个分布的存在坏分布的上界:
因此,当 M 小时,坏模型(不好的模型)的概率上限更小,但是选择更少;相反地,当 M 大时,坏模型(不好的模型)的概率上限更大,但是模型选择更多。
思考:
- 同一类型的分布函数,$E_in$ 一样了,但是 $E_out$ 还是不一样。那么它对于 hoeffding-equaility 有什么意义呢?
- 如何推广到无限种的分类函数中去呢?
无限数量分布集合
增长函数 -> vc 维(shatter/break) -> 影子样本
dichotomy:Mini-hypothesis
growth function 成长函数:
- positive rays: $m_h(N)=N+1$
- positive intervals: $m_h(N)=\frac{1}{2}N^2+\frac{1}{2}N+1$
- convex sets: $m_h(N)=2^N$
- 2D perceptrons: $m_h(N)<2^N$
brek point
bounding function
影子样本 S_一撇,当 $N \ge \frac{8}{\epsilon^2}$ 时:
总结:
- 霍夫丁不等式说明了,当N足够大时,h 的样本错误率接近真实错误率。
- 并集界(union bound)说明了 h 的数量越多,存在 h 不好的几率可能越大。
机器学习完整的推理过程:
- 单个假设:霍夫丁不等式证明,单个模型无法作弊(验证可行)。
- 有限假设:联合界证明,有限个模型无法作弊( $M$ 较小时可行)。
- 无穷危机:现实模型有连续参数, $M=∞$ 导致联合界报废。
- 影子样本与对称化:用第二组样本代替未知的真实分布,将整个问题局限在有限的 $2N$ 个点上。
- VC 维与多项式:在有限点上,有效行为从 $∞$ 降至多项式级别 $(2N)_{d_VC}$。
- 最终可行:多项式与霍夫丁的指数衰减碰撞,概率趋于 0。机器学习在数学上被证明完全可行。