动机
凸分类损失方便我们求解,但能够求解,并不等于所得的最小点一定善于分类。铰链损失要求带符号的间隔;逻辑斯损失则要求概率估计。最后报告的分类错误率,与这两个目标都不同。我们需要一个明确的定理把它们连起来。
正确的比较基准,是数据分布本身允许的最佳预测。在某个输入上,若正标签的出现概率为 ,即使最佳的确定性分类器也有 的错误概率。我们应该衡量学习方法超出这个不可避免部分的错误。这种超额风险把标签的不确定性,与决策不佳带来的代价分开。
以下先在每个输入上分别解决预测问题,再把所得不等式积分,完整推导铰链及逻辑斯风险的比较。最后才接回经验风险最小化。这一步不可省略:某个损失在不受限制时有正确的最优解,不代表一个太小或选择不当的模型类能接近那个解。
定义
设 服从固定的概率分布,且 。假设条件概率 有一个可测版本。所有关于 的叙述,都允许忽略一个输入概率为零的集合。例如有限输入空间及通常以实向量为输入的模型都满足这个假设。分类器 是取值于 的可测函数,其风险为 。
定义 15.1.1
(分数、平手规则与条件风险)
分数函数 是取有限实数值的可测函数。当 时,其分类器 ;否则 。所以零分数预测为正。对非负的间隔损失 ,定义
这里 是固定输入下的条件风险,而 同时对输入及标签取平均。以下比较的分数假设满足 。记 ,下确界遍及所有取有限实数值的可测分数,并设 。
我们研究 与 。所有对数均为自然对数。风险的下确界未必能由有限分数取得;我们会证明所需的下确界恒等式,而不会直接把下确界与期望交换。
每个分类器的比较基准,都是选择较可能标签的决策规则。
定义 15.1.2
(Bayes 规则与分类超额风险)
Bayes 规则为:当 时 ,否则 。在 时,两种决定同样最优;选正标签只是固定一个代表。定义 及 。
定理与命题
定理 15.1.3
(Bayes 风险与作出错误决策的代价)
Bayes 规则取得最小分类风险,且
所以在 接近 时,偏离 Bayes 决策的代价很小;当其中一个标签明显较可能出现时,代价便较大。
定理 15.1.4
(铰链与逻辑斯损失的校准)
对每个相应替代风险有限的分数,
不受模型类限制的替代风险下确界为
其中 ,并约定 。因此,替代风险收敛到不受限制的下确界,便保证分类风险收敛到 Bayes 风险。这些比较针对超额风险;原始逻辑斯风险并不是分类错误的概率。
这里的校准,指替代超额风险小,便能推出分类超额风险小。上述不等式把这个推论量化。它们没有宣称任意损失都享有相同常数,甚至没有宣称任意损失都享有这个推论。
反例模式
一个不校准的凸损失
断言:每个凸间隔损失都是校准的。取凸且非负的损失 ,以及一个 的输入。此时 ,故 ,零分数的替代超额风险为零。按平手规则它预测为正,分类风险为 ,而 Bayes 风险为 :分类超额风险为 。事实上,对每个 , 都使 最小,所以这个损失完全不理会标签概率。修正是一个标准结果(这里不证明):凸间隔损失是校准的,当且仅当它在 处可微且 ;铰链、逻辑斯与平方损失都满足这一条件。
证明与推导
以下给出完整的条件论证。
证明
(逐点比较两个决策)
固定一个正标签条件概率为 的输入,预测为正的错误概率为 ,预测为负则为 。较小者是 ;改选另一个决策,错误率便增加 。当 时,不论选哪个平手代表,增加量都是零。取期望即得第一个定理。
证明
(由分段条件风险得到铰链校准)
铰链损失的整个条件风险图像都是分段仿射的:
最小值为 。当 ,分数 是一个最小点;当 ,则可取 。因此可测分数 在每个输入上都取得条件最小值,也就取得该最小值的期望,证明了铰链风险的下确界公式。
假设分数作出了与 Bayes 不同的决策。如果 ,这表示 ;由分段公式可见 。如果 ,错误决策表示 ,也有相同下界。所以条件替代超额风险至少为 。若决策正确,条件分类超额为零,而替代超额非负;在 时也是如此。积分便得 ,并完整包含零分数的既定规则。
证明
(以相对熵得到逻辑斯校准)
对逻辑斯损失,设 ,故 。把两个对数改写,得到
其中 是二元相对熵。固定 ,把它视为 的函数。在 时,其值及一阶导数都是零,并且
在 与 之间把这个二阶导数不等式积分两次,得到 。再利用关于 的连续性,便推广到 及 。特别地,相对熵非负。若 ,在 时取得最小值零,对应分数为 。
当 ,条件损失随 下降至零;当 ,则随 下降至零。这两种情形都没有有限的最小点。为了证明整体下确界,把对数几率截断到 ,并在 及 处分别取 及 。这些分数都是有限且可测的。当 ,其条件风险逐点下降至 ,而且介于 与 之间:截断分数是从零向条件最小点移动。由上界 及控制收敛定理,其风险趋于 。另一方面,相对熵非负保证任意分数的风险都不低于此值。因此逻辑斯风险下确界公式成立,并有 。
若分数作出错误决策, 与 位于 的两侧;边界上的等号按既定平手规则处理。故 ,而条件分类超额满足
若决策正确,左边为零,所以第一个不等式仍成立。取期望,并对 与常数随机变量一使用 Cauchy–Schwarz 不等式,即得逻辑斯比较。
证明透视
逻辑斯论证如何收尾
逻辑斯证明建立在一个恒等式和两个不等式之上。恒等式 把条件风险分成不可避免的部分与一个散度;只要下确界恒等式成立,超额便是散度的期望。下确界恒等式正是微妙之处:在 时没有有限分数是最优的,所以证明不能在最小点上计算风险。截断的对数几率给出有限分数,其条件风险随 增大而下降,因为凸函数 在 由 向最小点移动时递减;这些风险又以 为上界。于是控制收敛定理允许取极限。
不明显的一步是曲率界 ,它把相对熵转化为两个概率之间的平方距离 。平手规则只在错误决策一步出现:当 时,零分数给出 并预测为正,此时 取等号。论证最后以 Cauchy–Schwarz 不等式收尾,等价于对凹的平方根用 Jensen 不等式。所以逻辑斯界带有平方根;铰链界则直接读自分段仿射的条件风险,没有曲率一步,因而是线性的。
完整例题
例题 15.1.5
(Bayes 错误率可以非零,平手也需要规则)
设 取值 的概率为 ,并有 、。Bayes 决策在 选正、在 选负,风险为 。改取分数 、。两个决策都与 Bayes 相反,包括零分数所作出的正预测。风险为 ,故超额为 。Bayes 恒等式也给出相同答案:。
两个条件铰链风险为 及 。因此 ,而 。替代超额为 ,确实大于分类超额 。若只把分类超额与原始铰链风险比较,就无法清楚区分不可避免的不确定性与所选分数造成的额外代价。
例题 15.1.6
(概率估计与决策提供不同的信息)
只有一个输入,且 。取满足 的分数,它为负,分类超额为 。逻辑斯超额为
定理给出 ,这是有效上界,但不是等号。若改取正分数,分类超额便为零,可是逻辑斯超额通常仍然为正:决策的正负可以已经正确,概率估计却仍不准确。
例题 15.1.7
(确定标签:铰链取得下确界,逻辑斯则不然)
只有一个输入,且 。铰链条件风险为 ,对每个 都是零,所以下确界由有限分数取得。逻辑斯条件风险 对每个有限 都大于零,只在 时才趋于 ;在 时它等于 。每个正分数的分类超额都是零,而 的逻辑斯界只给出 。
对负分数 ,分类超额为 。铰链超额为 ,逻辑斯超额为 ,而 。在 的这个边界值上两个比较都成立;证明中的截断步骤正是为这种情形而设。
反例模式
校准比较的是不受模型限制的最优值
只有一个输入,,分数类限制为两个常数 及 。分数 的分类风险为 ,铰链风险为 ;分数 的分类风险为 ,铰链风险为 。因此,类内的铰链最小点反而有较差的分类风险。这并不矛盾:不受限制的铰链最优值为 ,在分数 取得,而该分数并不在这个类内。对所选的 ,分类超额为 ,相对于不受限制最优值的铰链超额为 ,符合校准不等式。相对于两元素类的最小值,其铰链超额则为零;不能把这个零代入定理。
常见误解
有限样本的经验错误率不会直接告诉我们 ;训练替代风险小,也不会单独给出总体替代超额的上界。要把校准用于学习结果,设 为非空分数类,定义其近似误差为
假设比较中的总体风险均有限。在满足 的事件上,假设所得分数 的经验风险不超过 ,其中 。对类内任意比较函数 ,
对比较函数取下确界不需要最小值能够取得。减去 ,便得 。铰链分类超额由这个和控制;逻辑斯分类超额则由此和的两倍的平方根控制。三项分别代表三种障碍:模型类缺少合适分数、有限样本估计,以及尚未完成的优化。若三项都趋于零,且估计事件的概率趋于一,所得分类风险便依概率收敛到 Bayes 风险。单是增加参数个数,或单是解好一个固定的优化问题,都没有同时证明这三项条件。
常见错误
(把有界损失的集中界用于不受限制的分数)
在不受限制的分数上,逻辑斯及铰链损失都无界。若样本独立同分布、分数类固定且不依赖数据,类的大小为 ,并且每个类内函数几乎处处满足 ,损失才落在 :铰链可取 ,逻辑斯可取 。此时 Hoeffding 不等式配合联合界,以至少 的概率给出 。把有界损失界用在任意分数上,就漏掉了必要假设。如果类是从同一训练样本选出的,还需要另外控制;直接以这个选择为条件,不会自动恢复固定类的论证。
常见错误
(把原始逻辑斯风险当作错误概率)
在 的输入上,每个分数的逻辑斯条件风险都是 ;可是那里每个分类器的错误概率都恰为 ,而且都是 Bayes 最优的。原始风险超过任何可能的错误率。只有超额 才与 比较。
快速检查
快速检查
(在 的输入上,负分数是否与选定的 Bayes 规则不同?这种不同是否贡献分类超额?)
解答 · 答案
是不同的:选定的 Bayes 规则在 时预测为正。但它不贡献分类超额,因为其权重 为零。逻辑斯风险却仍可惩罚一个很有信心的负分数,因为它给出的 偏离真实概率 。
练习
快速检查
(只有一个输入,。分别计算分数 的分类风险及铰链超额风险。对零分数,另算逻辑斯超额风险,并验证逻辑斯比较。保留零分数预测为正的规则。)
解答 · 答案
Bayes 决策为负,风险为 。分数 的分类风险依次为 ,故超额为 。铰链风险依次为 ,而不受限制的铰链最优值为 。所以铰链超额为 ,各自都不小于相应的分类超额。零分数给出 ,逻辑斯超额为 ,故 。零分数在铰链比较中取得等号,也说明平手规则必须明确固定。
练习 15.1.8
(对平方间隔损失 ,设 。证明 及 ,并证明不存在通用的有限常数 ,使所有分布及分数都满足 。)
核心证明
解答(4)
- 1
对 配方
展开 ,得到 。有限可测分数 同时取得条件及总体下确界,所以 。
- 2
在错误决策上控制分类超额
关键一步
若决策错误且 ,则 ,右边恰是该事件上的条件分类超额 。决策正确或 时超额为零。因此处处有 。
依据: 错误决策使 与 位于零的两侧,平手也包括在内。
- 3
积分并用 Cauchy–Schwarz 不等式
。
- 4
排除线性比较
∎考虑单一输入,、,分数为零。分类超额为 ,平方损失超额却为 ,比值 在 趋于零时无界。
快速检查
(一个固定的有限分数类有 个函数,每个分数都满足 ,训练样本有 个独立同分布观测。此类的总体铰链近似误差至多为 ,所得分数的经验优化误差至多为 。给出以至少 的概率成立的分类超额界,并指出哪个已知量无法只靠数类中元素的个数得知。)
解答 · 答案
铰链损失上界为 。取 得 。因此以所要求的概率,分类超额至多为 。近似误差 描述总体分布与可用分数函数之间是否匹配;单靠数目 不能证明这个误差。优化误差也需要由所得解的性质另行保证,不能从类的大小推出。
练习 15.1.9
(输入空间恰有 个点,分布任意。设 包含所有只取 的 个分数函数。证明此类上的铰链经验最小化就是分类经验最小化,并推导精确经验最小点的 Bayes 超额分类保证,保留这个分数选择带来的常数改进。)
综合证明
解答(4)
- 1
计算取值于 的分数的铰链损失
对这类分数,预测正确时铰链损失为零,错误时为二。因此经验及总体铰链风险都恰等于分类风险的两倍,两个经验最小化选出相同的分数。
- 2
确定近似误差
此类包含在全部输入点上作 Bayes 决策的分数,其铰链风险为 。所以铰链近似误差为零,且每个类内分数都满足 。
- 3
应用有限类界
关键一步
取 。以至少 的概率,精确经验最小化给出 ,其中 。
依据: 此类固定,有 个元素,铰链损失落在 。
- 4
转回分类超额
∎由 得 。若只用一般校准不等式 ,就会多出一个二倍因子。由于分类超额不会超过一,也可把此界与一取较小者。