统计学习问题

二分类用 0–1 损失评价错误概率；平方回归评价数值偏差。共同协议并未强迫预测器是有限维参数，它也可以是树、查找规则或随机决策核。

已知完整目标函数后求最小值是优化问题理路优化问题Optimization problem在可行解集合上最小化或最大化目标函数的计算问题。；目标由未知分布定义、只能用样本近似，并须接受样本外评价时才出现学习层。假设类规定比较对象，损失规定何谓表现好，学习协议则规定算法实际看到了什么。这三层不能由某个优化器的名字代替。

IID 是本页主线而非学习的唯一可能：时间序列、自适应采样和分布漂移需要另写数据协议，不能沿用 $D^m$ 的证明。样本复杂度理路样本复杂度、精度与置信度Sample complexity · Accuracy and confidence用 m(ε,δ) 描述达到风险精度与失败概率所需的数据量。随后把风险目标变成有限数据保证。

即使有无限数据，总体风险也不必趋零。下面 Bernoulli 例子中的不可消去项 $p(1-p)$ 来自标签自身随机性；恢复了 $p$ 也无法预知下一次标签，因此学习保证往往比较超额风险而非原始风险。

邮件分类与分布迁移 ​

一项完整的统计学习问题还必须固定信息边界。设邮件分类的 $X$ 包含正文和发件域，$Y$ 表示是否为垃圾邮件；训练样本若来自旧月份，而部署风险按新月份分布计算，就不再是同一个 $D$。即使训练误差为零，原 IID 保证也没有覆盖这种分布迁移。相反，若该月原始邮件本身是从同一个 $D$ 独立采样的，再按独立于内容的随机方式划分训练和测试部分，且测试集始终封存，那么条件于训练过程，测试点仍可作独立风险评价。仅仅“随机切分”不能把原本存在用户聚类、时间依赖或选择偏差的数据变成 IID。

估计作为学习的特例 ​

令 $Y\sim \mathrm{Bernoulli}(p)$，预测器是常数 $a\in [0,1]$，损失为 $(a-Y{)}^2$。总体风险可以逐项算出：

唯一最优动作是 $a=p$，经验风险最小化器则是样本均值 $\hat{p}=m^{-1}\sum _i{Y}_i$。若 $m=4$ 且标签为 $(1,0,1,0)$，经验准则是 $[2(a-1{)}^2+2a^2]/4=(a-1/2{)}^2+1/4$，所以输出 $\hat{p}=1/2$。若未知真实参数恰为 $p=0.8$，总体风险为 $0.25$，最优总体风险为 $p(1-p)=0.16$，超额风险是 $(0.5-0.8{)}^2=0.09$。算法能算出前一个经验二次式，却不能从这四条数据直接读出 $p$；风险分解是分析者对未知环境作的评价。

因此 Bernoulli 参数估计确实是常数预测器类上的平方损失学习，而不只是术语类比。

分布族边界 ​

最后还需规定允许的分布族。分布无关 PAC 允许全部满足可测性与损失条件的 $D$，minimax 估计常把 $D$ 限制在参数族 $\{P_{\theta }\}$，协变量漂移理路协变量漂移Covariate shift · 协变量偏移 · Covariate-shift adaptation输入人群的组成改变而给定输入的标签机制不变时，以输入密度比把源分布损失转换为目标风险。则区分源训练分布与目标部署分布，假定给定输入的整个条件标签分布不变，并在目标输入由源输入覆盖时用密度比识别目标风险。限制越强，可能获得越快的速率；这些速率不能回填到未受限制的协议。

经验风险最小化把未知总体风险换成样本上可计算的目标；一致收敛、复杂度界或稳定性再负责证明这个替换对数据依赖输出仍可靠。算法成功需要两件事同时成立：经验目标确实被近似优化，经验量与总体量之间的桥也足够牢固。

PAC 可学习性进一步为本页协议加入 $\epsilon$ 精度、$\delta$ 置信度和样本复杂度量词。可实现与不可知版本选择不同的总体基准，VC 理论、PAC-Bayes 和算法稳定性则提供不同的泛化证明路线；它们共享本页对象，却不能省略各自的附加条件。

若数据改为逐轮到达、算法必须在结果揭示前行动，问题转向在线学习协议理路在线学习协议Online learning protocol学习器按轮先行动、再接收结果与反馈的序贯决策协议。，评价也常改为相对比较器的遗憾；若未选动作的结果被隐藏，则进一步进入 bandit。批学习、在线学习和 bandit 采用不同的信息结构，不能把三者视为同一算法的运行模式标签。