在线学习交错训练与预测
传统学习常先训练再预测;
在线学习把两阶段交错进行,当前预测后才能得到新反馈并更新。
分析在线算法时,不能假设已知未来样本的标签或顺序。
主题对照
从最小二乘与线性/逻辑回归出发,梯度下降、随机梯度、牛顿法、AdaGrad/RMSProp 各自在改什么;L1/L2 惩罚为什么是不同目标;在线学习与专家算法(Hedge、乘性权重、遗憾界)如何在只有过去反馈时更新。
传统学习常先训练再预测;
在线学习把两阶段交错进行,当前预测后才能得到新反馈并更新。
分析在线算法时,不能假设已知未来样本的标签或顺序。
在线预测可同时参考多个“专家”。
乘性权重法给每位专家正权重,表现差时按比例降低其权重;目标是在未知未来样本的条件下,让累计预测表现接近最佳专家。
梯度下降沿目标函数的下降方向反复调整参数,寻找局部极小值。
在有标签的学习任务中,下降一步意味着修改假设参数,以改善对训练样本的拟合;局部极小不保证全局最优。
训练目标可加入正则项,对过于复杂的假设施加惩罚,以缓解只对训练数据拟合很好的过拟合。
书中仅说明这个设计入口,没有给出具体正则形式或保证。
第t轮先收集专家对二元事件的预测,学习者据此及过去反馈给出自己的预测;真实结果在预测后才揭示。
算法不能看未来事件,也不能额外使用当前事件的隐藏结果。
设学习者总错误数为m,各专家错误数为mᵢ,事后最佳单一专家错误数m*=minᵢmᵢ。
遗憾值定义为m−m*;目标是让它小,即使起初不知道哪位专家最终最好。
若n位专家中至少一位始终正确,只保留从未出错者并按其多数票预测。学习者每次预测错误,至少淘汰当前一半专家;完美专家始终留下,因此最多错⌈lg n⌉次。
每轮把预测1和预测0的专家权重分别求和,选择权重和较大的一侧作为预测;相等时按约定选1。
多数票依据当前信任权重,而非简单数人数。
观察真实结果后,对预测错误的专家把权重乘以1−γ,正确者权重不变,其中0<γ≤1/2。
初始权重都为1;重复出错者影响力逐轮下降,但权重仍为正。
令W为所有专家权重之和。
算法若预测错误,错误一侧至少占当前总权重一半,更新后W至多乘1−γ/2;预测正确时W也不会增加。
每位专家权重仍给W一个下界,由此可比较算法与任意专家的错误数。
共有n位专家,算法连续预测T轮。对任意专家i和任意前T′轮(T′≤T),令m(T′)为加权多数算法犯错次数,mᵢ(T′)为专家i犯错次数。若错误专家的权重每次乘以1−γ,且0<γ≤1/2,则
m(T′) ≤ 2(1+γ)mᵢ(T′) + 2ln(n)/γ。
它不是只在最后一轮成立:任取前缀和任取比较专家都成立。右侧第一项随该专家错误数增长,第二项是从n个专家中竞争付出的代价;γ越大,第二项越小,但第一项系数越大。
乘性权重不局限二元预测:结果和预测可为实数,更新因子可随损失变化,也可把权重归一化成专家抽样分布。
具体保证须按新损失与更新规则重新分析,不能直接套二元错误数界。
从初始点x⁽⁰⁾开始,每轮在当前点计算∇f,再沿负梯度方向移动得到下一点。
要成为可执行算法,还必须确定步长、停止条件及可接受的解质量;方向正确不等于任意步长都下降。
线性回归用权重和偏置把特征向量映射为预测值,再从训练样本学习这些参数。
模型形式f(x)=w₀+Σwⱼxⱼ;用于新样本前,应区分训练拟合与未见样本上的预测质量。
对样本i,残差是预测值f(x⁽ⁱ⁾)与标签y⁽ⁱ⁾之差;最小二乘把所有残差平方求和,并以权重为变量最小化。
在线性模型下损失是凸函数,但训练损失低不自动保证泛化。
以∥w∥≤B约束线性模型权重,可限制权重整体规模。
投影到该球时,
书中直接缩放公式须加上这个条件。
Hedge把专家权重归一化为概率,按此分布抽取专家并采用其预测;错误专家再按损失更新权重。
它和加权多数的确定性投票不同;题目给出的期望错误界是待证明结论,不能当作已推导的保证。
随机梯度下降逐次读取随机样本,用该样本损失对参数的梯度估计总体梯度,再沿负方向小步更新。
单步成本较低,但轨迹含随机波动;本书该处要求读者自行推导期望误差,未直接给出证明。
最小二乘法为模型选参数,使预测值与观测值的残差平方和最小。在线性拟合中,给定点 (Xᵢ,Yᵢ),选择斜率 a 和截距 b,最小化 Σ(aXᵢ+b−Yᵢ)²。平方使正负残差不会抵消,并对大残差更敏感;“最佳”只针对所选模型形式和这一损失函数,不意味着数据严格落在直线上,也不保证预测关系有因果含义。
多元线性模型 y=β₀+β₁x₁+…+βₙxₙ 用 m 个样本拟合时,把样本排成设计矩阵 A(每行一个样本,第一列全为 1 对应截距,其余列是各特征),参数排成向量 β,观测值排成向量 Y。最小二乘要最小化 ‖Aβ−Y‖²(各样本残差平方和),对 β 求导置零得正规方程 AᵀAβ=AᵀY。
只有 A 的列满秩(任何一列都不能由其他列线性组合出来)时,AᵀA 才可逆,解 β=(AᵀA)⁻¹AᵀY 才唯一。样本数少于参数个数,或某特征与其他特征线性相关,都会导致不满秩。
示例(补充):若每个样本都有 x₂=x₁,那么 β₁=1、β₂=0 与 β₁=0、β₂=1 给出完全相同的预测,残差平方和一样小。这说明不满秩时最小值仍能达到,只是解有无穷多个,而不是“无解”。增加样本也须带来新的独立信息(例中须出现 x₂≠x₁ 的样本)才能修复秩缺陷。
在线性回归的平方残差 ‖Aβ−Y‖² 后加惩罚项 λ·R(β)(λ>0 是正则参数,越大越压低系数),可限制系数大小并处理共线性。共线性指特征之间线性相关,此时 AᵀA 不可逆或接近不可逆(病态:数据稍有变化,解就大幅波动)。
L2 有解析解 β=(AᵀA+λD)⁻¹AᵀY,D 是对角矩阵,截距对应位置为 0(截距不受惩罚)、其余为 1;λ>0 时括号内矩阵一定可逆。原书式(17-11)把逆号和括号排错了位置,应按上式理解,不能直接照抄实现。L1 的绝对值在 0 处不可导,没有这样的逆矩阵公式,需要迭代求解。
最小二乘是“让残差平方和最小”的目标,正规方程与梯度下降是求这个目标的不同方法。在线性、满列秩等条件下可用解析式求唯一解;迭代法不要求形成逆矩阵,能处理更多模型,但收敛性取决于目标函数和步长等条件。非线性模型也能采用最小二乘目标,原书把最小二乘限于线性模型,是混淆了平方损失与特定线性解析解。选择方法还应考虑矩阵规模、病态性与计算成本。
最小二乘支持向量机(LSSVM)改写了 SVM 的约束和误差惩罚。下表中 yₖ=±1 是类别,φ 把输入映射到特征空间,w、b 确定分类超平面:
| 标准软间隔 SVM | LSSVM | |
|---|---|---|
| 约束 | yₖ[wᵀφ(xₖ)+b] ≥ 1−ξₖ,ξₖ≥0 | yₖ[wᵀφ(xₖ)+b] = 1−eₖ |
| 误差惩罚 | c·Σξₖ(松弛量线性计) | ½γ·Σeₖ²(误差平方计) |
等式约束下,对拉格朗日函数的各变量求偏导置零,得到 αₖ=γeₖ 等四组条件,合并后正好是一个关于 b 和 α 的线性方程组,系数中含核矩阵(元素由核函数 K(xₖ,xₗ) 算出);解出后代入得分类或回归函数。由 αₖ=γeₖ 可见,误差不为零的样本 α 都不为零,所以所有训练点都成为支持向量。
“解线性方程组”不自动保证训练更快或预测更准:N 个样本要解 N+1 阶方程,效率还受核矩阵规模和数值条件影响;书中也说标准 LSSVM 精度比 SVM 稍差。
损失函数把预测与目标之间的差异变成可优化的数。Y 为真实值,f(x) 为预测:
| 损失 | 公式 | 演示 |
|---|---|---|
| 0–1 | 预测错为 1,对为 0 | 只问对错 |
| 平方 | [Y−f(x)]² | Y=3、预测 1:4 |
| 绝对 | |Y−f(x)| | Y=3、预测 1:2 |
| 对数 | −log P(Y|X) | 真实类概率 0.9:约 0.11;0.1:约 2.30 |
平方损失放大大残差;绝对损失按偏差幅度线性计;对数损失按模型给真实类别的概率计,越不自信惩罚越重。选损失前应明确任务输出和代价含义,再看它是否便于优化。训练损失低只说明拟合训练数据,不能单独证明未知样本上的效果。
梯度下降沿目标函数的负梯度更新参数:θ ← θ − α·∂J/∂θ,其中梯度指向函数上升最快的方向,学习率 α(步长)决定单次改变量。三种做法的区别在于每次用多少样本估计梯度。
演示(补充):训练集 10000 个样本,
| 做法 | 每次更新用样本 | 遍历一轮更新次数 |
|---|---|---|
| 全批量 | 10000 | 1 |
| 小批量(100) | 100 | 100 |
| 随机梯度 | 1 | 10000 |
全批量单次成本高而方向稳定;随机梯度单次便宜但方向波动大;小批量在计算和噪声间折中。特征尺度与学习率会影响训练过程,过大步长可越过低损失区。达到零梯度只表示驻点,还需区分极小、极大和鞍点。
SGD 用随机小批量估计梯度,第 k 步的学习率 εₖ 决定沿负梯度走多远。过小会训练缓慢,过大会振荡或发散。
原书给出的收敛条件是两条:
实践常用线性衰减:εₖ=(1−α)ε₀+αε_τ,α=k/τ,从初值 ε₀ 在 τ 步内线性降到 ε_τ,之后保持常数。
这两条是特定随机逼近假设下的经典条件,不能脱离目标光滑性、噪声和采样条件当作深度网络收敛的充分保证;衰减到常数后也已不满足平方和有限。
Hessian 矩阵 H 是目标 J 对参数 θ 的二阶导数矩阵,描述各方向上的曲率(坡度变化有多快)。牛顿法在当前点 θ₀ 用二阶泰勒展开近似 J,再直接跳到这个二次近似的临界点:θ* = θ₀ − H⁻¹∇J(θ₀)。曲率大的方向步子小,曲率小的方向步子大,不必手调学习率。
精确 Hessian 的存储与求逆代价高,原书据此认为牛顿法只适合参数较少的网络。
AdaGrad 给每个参数各配一个累积量 r,每步累加梯度平方 r←r+g⊙g(⊙为逐元素相乘),更新量与 ε·g/(δ+√r) 成正比:ε 是全局学习率,δ 是防止除零的小常数。于是累积量大的坐标有效学习率 ε/√r 较小。
演示(假设 ε 相同、忽略 δ):
| 情形 | 累积 r | 有效学习率 | 本步更新幅度 |
|---|---|---|---|
| 参数 A 连续 4 步梯度为 1 | 4 | ε/2 | 0.5ε |
| 参数 B 连续 4 步梯度为 0.1 | 0.04 | 5ε | 0.5ε |
| 参数 A 连续 100 步梯度为 1 | 100 | ε/10 | 0.1ε |
前两行说明梯度尺度不同的坐标被拉到相近步幅;第三行说明即使梯度不变,r 只增不减,步长也会持续缩小,这正是原书说的学习率过早、过量减小。因此自适应不等于无需调参,也不保证所有目标都比 SGD 好。
RMSProp 把 AdaGrad 的“梯度平方全历史求和”改成指数移动平均,常见写法为 r←ρr+(1−ρ)g⊙g,再同样按 g/(δ+√r) 缩放更新。衰减率 ρ(0 到 1 之间)越大,旧梯度保留越久;每过一步,旧信息的权重就乘一次 ρ。
对比(示例:某参数梯度一直为 1,ρ=0.9):AdaGrad 的 r 在第 100 步为 100,更新幅度缩到 0.1ε;RMSProp 的 r 逐渐趋近 1 而不再增长,更新幅度保持在约 ε。这就是它缓解 AdaGrad 步长持续缩小的原因。
仍须设置基础学习率 ε、ρ 和稳定项 δ。它不保证非凸目标最终进入凸区域,也不保证快速收敛。
用 PSO 训练网络时,每个粒子的位置 x 就是一整套权重和偏置,以平方损失 L=½‖y−h_{w,b}(x)‖² 评价它(y 为类别标签,h 为网络输出)。每轮按下式更新第 i 个粒子的第 d 维:
v ← ωv + c₁·Rand·(p_i−x) + c₂·Rand·(p_g−x),x ← x+v
ω 是惯性权重,保留旧速度;p_i 是该粒子自己找到过的最好位置,p_g 是全群最好位置;c₁、c₂ 是加速系数,Rand 为随机数。更新后重算损失,若更好就替换 p_i、p_g,直到损失低于阈值 T_min。损失阈值只是停止条件,不能证明动态稳定或全局最优;实践还需最大迭代预算、参数边界和独立验证,避免昂贵搜索与过拟合。
点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。
来源书籍
算法与数据结构类
书籍类型:经典原理
清单覆盖 7/7
1142 张卡片
来源书籍
书籍类型:未标注
424 张卡片
来源书籍
实时流计算系统类
书籍类型:未标注
清单覆盖 8/8
172 张卡片
来源书籍
算法与数据结构类。按全文与现有卡核对七项;“已覆盖”表示保留了本书实际展开的部分,不表示穷尽该领域。
书籍类型:经典原理
清单覆盖 6/7
367 张卡片
主题索引
比较传统机器学习、深度学习与强化学习的学习方式、特征假设、模型取舍与数据反馈闭环。
与 3 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类