两组带标签的点若有不同的均值,沿两个均值之差的方向投影,似乎就是自然的区分方法。不过,均值相差一个单位,在每个方向并不具有同样意义。如果点在该方向本来就分散得很广,投影后的两组仍可能大量重叠。另一个均值差较小、组内散布却更小的方向,反而可能更有区分力。
Fisher 准则把这两种量放在一起比较:它选择一维线性投影,使均值差的平方相对于类内散布尽量大。本节会推导最优方向,而不只是记住一条含逆矩阵的公式。之后还要分清另一个步骤:如何把投影变成分类器。单是最大化一个比值,并没有指定阈值、后验概率或未来分类错误率的保证。
先固定数据与投影约定
我们有两个非空的带标签样本,类别记为 0 和 1。每个数据点 xi 是 Rd 中的列向量。令 Ik 是第 k 类的索引集合,nk=∣Ik∣。两个样本均值及它们的差定义为
μk=nk1i∈Ik∑xi,δ=μ1−μ0.
非零向量 w 给每个点一个标量分数 s(x)=wTx。两个投影均值之差是 wTδ。度量类内散布时,必须减去每个点所属类别的均值,而不是全体样本的共同均值。
定义 19.1.1
(类内散布与 Fisher 商)
类内散布矩阵定义为
SW=k=0∑1i∈Ik∑(xi−μk)(xi−μk)T.对满足 wTSWw>0 的方向,Fisher 商为
J(w)=wTSWw(wTδ)2.分母等于各投影点偏离其所属类别投影均值的残差平方和。它不是相对于同一个全体均值的平方距离和。
散布矩阵对称且半正定,因为对任意 v,其二次型都是 (vT(xi−μk))2 这些平方的总和。但它未必可逆。以下主定理会明确假设正定。
这里采用未归一化的残差和。当 n0+n1−2>0 时,把整个矩阵除以这个正数,就得到常用的合并协方差估计。乘上同一个正常数会改变 J 的值,却不改变最优方向。若对两个类别的散布分别使用不同权重,则会改变准则,也可能改变方向;这是模型选择的改变,不只是记号差别。
用内积推导方向
对任意非零标量 c,J(cw) 的分子与分母都乘上 c2,所以准则只能确定 w 所张成的直线。正负号也会在平方后消失。若希望类别 1 的投影均值较大,还须另外选择符号。
定理 19.1.2
(散布正定时的 Fisher 方向)
假设 SW 正定,而且 δ=0,则
w=0maxJ(w)=δTSW−1δ,w 使 J 最大 ⟺ w=cSW−1δ 对某个 c=0.选择 c>0 时,wTδ>0。实际计算一个方向时,应解线性系统 SWw=δ,不必显式形成逆矩阵。
由于 SW 对称正定,⟨a,b⟩W=aTSWb 是内积。令 v=SW−1δ,则 v=0,而且
wTδ=wTSWv=⟨w,v⟩W.在这个内积中使用 Cauchy–Schwarz 不等式,得到
(wTδ)2≤(wTSWw)(vTSWv).除以正的分母,再用 vTSWv=δTSW−1δ,就得到上界。Cauchy–Schwarz 取等号,当且仅当非零向量 w、v 互为标量倍数;这些方向确实达到上界。最后,若 w=cv 且 c>0,则 wTδ=cδTSW−1δ>0。
证明透视
正定性与柯西–施瓦茨(Cauchy–Schwarz)在哪里出现
不显然的一步,是把分子 wTδ 改写成 ⟨w,v⟩W,其中 v=SW−1δ,使分子与分母在同一个几何中度量;其后只需用一次柯西–施瓦茨(Cauchy–Schwarz)不等式。SW 的正定性用了两次:它使 ⟨⋅,⋅⟩W 成为真正的内积(取等号的刻画需要正定),也使 SW−1 存在,从而定义 v;而 δ=0 保证 v=0。条件 δ=0 使最大值为正,并使最优方向恰为一条直线;若 δ=0,每个方向的值都是 0。若 SW 只是半正定,不等式仍然成立,但 v 未必存在,而且某些方向的分母可能为零;奇异散布一节会以例子处理这种情况。
这条公式不是单纯偏好原始均值差较大的坐标,而是利用整个散布矩阵,包括坐标间的相关性,调整均值差。如果散布是对角矩阵,每个坐标的均值差会除以该坐标的类内散布;若坐标相关,逆矩阵也会考虑它们共同变动的方向。
概念视角几何
先白化散布,再取均值差
令 x′=SW−1/2x、δ′=SW−1/2δ、u=SW1/2w。那么 wTx=uTx′,wTδ=uTδ′,wTSWw=∥u∥2,所以 J=(uTδ′)2/∥u∥2。在白化后的坐标中,类内散布矩阵是单位矩阵,而 J 等于 ∥δ′∥2 乘以 u 与 δ′ 夹角余弦的平方。当且仅当 u 与 δ′ 平行时它最大,即 w∝SW−1/2δ′=SW−1δ。
若 δ=0,但 SW 仍然正定,每个非零方向的 J(w) 都是零,此时不能使用“除倍数外唯一”的结论。下一节最后一个例题显示这种情况如何出现。
完整计算一个二维例子
例题 19.1.3
(选择投影时,把垂直散布也计算在内)
考虑以下八个带标签的点:
两个均值是 μ0=(0,0)T、μ1=(2,1)T,所以 δ=(2,1)T。两个类别各自减去均值后,残差都是 (−1,0)T、(1,0)T、(0,−2)T、(0,2)T。每类的散布因此是 diag(2,8),故
SW=(40016),SW−1δ=(1/21/16).把这个方向乘以 16,可以使用 w=(8,1)T。两个投影均值是 0 和 17;均值差的平方是 172=289,投影后的类内散布是 4⋅82+16⋅12=272。因此 J(w)=289/272=17/16,与定理一致。
若直接使用原始均值差 w=δ=(2,1)T,分子为 52=25,分母为 4⋅22+16=32,得到 J(δ)=25/32。Fisher 方向的商较大,因为垂直方向的残差散布较大,在此准则下应减轻其权重。
对 w=(8,1)T,一个可选的分类规则是:若 8x1+x2>17/2,就预测类别 1。阈值是两个投影均值的中点;为使规则完整,等号情况归入类别 0。这个阈值能正确分类表中的全部八个训练点,但这只是一个有限样本观察,不是泛化保证。
新点 x=(3/4,2)T 的 Fisher 分数是 8,小于 17/2,所以此规则预测类别 0。若沿 δ 投影,并使用相应中点阈值 5/2,分数是 7/2,就预测类别 1。我们没有这个新点的真实标签;这个分歧展示的是不同的边界,不能证明哪个预测正确。
设类别 0 由 (−1,−1)T,(1,1)T 组成,类别 1 由 (1,0)T,(3,0)T 组成。均值为 μ0=(0,0)T、μ1=(2,0)T,所以 δ=(2,0)T。类别 0 的残差就是这两个点本身,贡献 2(1111);类别 1 的残差 (∓1,0)T 贡献 diag(2,0)。因此
SW=(4222),SW−1=41(2−2−24),SW−1δ=(1−1).取 w=(1,−1)T,则 wTδ=2,wTSWw=4−2−2+2=2,所以 J(w)=4/2=2=δTSW−1δ。原始方向 w=(1,0)T 的分子是 4、分母是 4,只得 J=1。原因是类别 0 只沿 (1,1)T 变动;方向 (1,−1)T 与这个变动正交,所以类别 0 的两个点都投影到 0,只有类别 1 贡献类内散布。
两个投影均值是 0 和 2,中点阈值为 1。类别 0 的分数是 0,0,类别 1 的分数是 1,3。规则“当 x1−x2>1 时预测类别 1”正确分类四个训练点中的三个;点 (1,0)T 恰好落在阈值上,等号归入类别 0,所以被误分。
取一维两类样本值 {−1,1} 与 {−2,2}。两个均值都是 0,所以 δ=0。散布为 SW=2+8=10>0,对每个 w=0 都有 J(w)=0/(10w2)=0:每个方向都是最优的(值为 0),准则无法偏好任何一个。然而两类的散布不同,规则“当 ∣x∣>3/2 时预测类别 1”可以完全分开它们。这个规则不是任何分数 wx 上的阈值,因为在数轴上,类别 1 的值分布在类别 0 的值两侧。只依靠均值差建立的准则,无法察觉这类差异。
投影方向不会自动选定概率模型或阈值
Fisher 商并没有阈值参数。即使确定了 w 的符号,仍要另选决策规则,例如“当 wTx>t 时预测类别 1”。可以用验证数据、应用中的错误代价,或概率模型决定 t;这些问题与最大化训练散布比值并不相同。
命题 19.1.6
(两类共用协方差高斯(Gauss)下的贝叶斯(Bayes)规则)
设给定类别 k 时,数据点服从 N(μk,Σ),两类共用同一个正定协方差 Σ;类别先验为 π0,π1>0,π0+π1=1,且两种误判的代价相同。令 a=Σ−1δ。则使错误概率最小的规则,恰在以下不等式成立时预测类别 1:
aTx>21aT(μ0+μ1)−logπ0π1.
写出两个高斯(Gaussian)密度的指数并展开,关于 x 的共同二次项相消。后验对数几率为
logPr(Y=0∣x)Pr(Y=1∣x)=δTΣ−1x−21δTΣ−1(μ0+μ1)+logπ0π1.这里用到 μ1TΣ−1μ1−μ0TΣ−1μ0=δTΣ−1(μ0+μ1)。等代价的贝叶斯(Bayes)规则在后验几率大于 1,即对数几率为正时预测类别 1;整理便得所述不等式。
证明透视
每个假设换来什么
共用协方差:它使二次项相消,边界才是线性的。若两类协方差 Σ0,Σ1 不同,对数几率会保留 −21xT(Σ1−1−Σ0−1)x 这一项,边界便是二次曲面。等代价:它把阈值放在几率为 1 处;代价不等会给阈值加上一个常数。先验:它贡献 log(π1/π0),先验相等时,阈值正是两个投影均值的中点。尺度:这里的 a 是确定的向量 Σ−1δ。Fisher 方向只定到一个标量倍数,阈值必须随之缩放,所以不能把任意缩放的 Fisher 向量代入此公式,却让先验项保持不变。当 Σ 与 SW 成比例时,a 与样本 Fisher 方向平行,这就是两者的联系。
这个推导是在说明两者的联系,不是在 Fisher 定理中暗藏额外假设。比值最优化本身并不要求高斯样本。反过来说,在共用协方差高斯模型以外,线性中点规则未必最小化分类错误率。训练比值较大,并不普遍代表测试准确率较高。
Fisher 商度量的是投影均值相对于散布的分离程度,并不最小化训练错误,也不选定阈值。在上面的相关散布例子中,商最大的方向仍有一个训练点恰好落在中点阈值上,按等号归类的约定被误分。把 w 变号而不把不等号反向,会使预测标签对调,商却完全不变。
奇异散布包含两种不同情况
如果独立的残差方向太少,SW 就会奇异。例如,每类残差的总和为零,所以合并散布的秩最多是 n0+n1−2。维度高于这个数时,它不可能正定。即使观测很多,特征共线也可能造成奇异。
反例模式
零散布的分离方向,不能靠盲目使用伪逆处理
令 SW=diag(1,0)、δ=(0,1)T。沿 w=(0,1)T 投影,两类均值不同,类内散布却是零。按本节定义,比值的分母为零,不能视为一个有限实数。
对 w=(ε,1)T,若 ε=0,分母是 ε2,分子是 1;因此当 ε→0,比值无界。在正分母定义域内,没有方向达到有限最大值。伪逆给出的 SW+δ=0 甚至不是允许的非零方向,也漏掉了这种零散布分离。
若使用相同散布,但改为 δ=(1,0)T,每个 w=(1,t)T 都有商 1。零空间方向既不改变投影均值差,也不改变类内散布。因此有很多互不平行的最优方向。这里伪逆会选出其中一个代表,但仍不能使用正定定理的唯一性结论。
这些矩阵可以由实际样本产生。类别 0 的点取 (−1/2,0)T,(1/2,0)T,类别 1 的点取 (−1/2,1)T,(1/2,1)T,就得到第一组散布与均值差。若把第二类的中心改放在 (1,0)T,则得到第二种情况。
一种有明确目的的处理方式是正则化:以 SW+λI 取代 SW,其中 λ>0。新矩阵正定,相同定理现在最大化的是使用以下修改后分母的比值:
wTSWw+λ∥w∥2.
当 δ=0 时,所得方向与 (SW+λI)−1δ 平行。这不表示原本的奇异商突然有了定义。在八点例子中,λ=4 给出 (1/4,1/20)T,与 (5,1)T 平行,而非原来的 (8,1)T:正则化确实改变了准则。
改变特征坐标时,同时变换散布
设新坐标为 x′=Ax+t,其中 A 可逆。平移在均值差中相消,所以 δ′=Aδ;每个残差变成 A(xi−μk),因此 SW′=ASWAT。
设 SW 正定、δ=0,且 x′=Ax+t,其中 A 可逆。则 δ′=Aδ,而 SW′=ASWAT 正定。若 w 是原数据的 Fisher 方向,则 w′=A−Tw 是新数据的 Fisher 方向。此外 w′Tx′=wTx+w′Tt,且 J′(w′)=J(w)。
对 v′=0,v′TSW′v′=(ATv′)TSW(ATv′)>0,因为 AT 可逆,所以 SW′ 正定。其次,
(ASWAT)−1Aδ=A−TSW−1A−1Aδ=A−TSW−1δ,故最优方向 cSW−1δ 对应到 cA−TSW−1δ,即 w′=A−Tw。至于分数,w′Tx′=wTA−1(Ax+t)=wTx+w′Tt:每个分数都增加同一个常数,阈值也须增加同一个常数。最后 w′Tδ′=wTδ 且 w′TSW′w′=wTSWw,所以商不变。因此一致地改变可逆坐标,不会改变未正则化的决策边界。
上述不变性只适用于未正则化的规则。ASWAT+λI 一般不等于 A(SW+λI)AT,所以任意改变尺度后再使用同一个数值 λ,相当于选了不同的惩罚。在八点例子中 SW=diag(4,16),λ=4 使第一个对角元素加倍。改变单位 A=diag(100,1) 后,第一个元素是 40000,同样的 λ=4 只改变它 0.01%。应先决定特征尺度,再选正则化强度。
练习与解答
快速检查
(在八点例子中,验证 w=(8,1)T 的 Fisher 商,说明换成 −w 后会怎样,并写出如何保留同一个中点分类器。)
解答 · 答案
投影均值差为 17,投影类内散布为 272,所以商是 289/272=17/16。以 −w 取代 w 不改变两个平方量,但类别 1 的投影均值变成 −17,类别 0 仍为 0。要保留原来的严格规则,应在 (−w)Tx<−17/2 时预测类别 1,等号仍归入类别 0。若继续使用“大于”,即使比值完全相同,也会把分类标签反转。
快速检查
(在共用协方差高斯模型下,设 μ0=(0,0)T、μ1=(2,1)T、Σ=diag(1,4),而 π1=3π0。以对数几率的系数求等代价阈值,并解释移动方向。)
此时 π1/π0=3。
解答 · 答案
此时 a=Σ−1δ=(2,1/4)T,而 aT(μ0+μ1)/2=17/8。所以在 2x1+x2/4>17/8−log3 时预测类别 1。相比先验相等,阈值较小,因为尚未观察特征时,类别 1 已较可能出现。此式使用题目指定的协方差尺度及自然对数,而非任意归一化的 Fisher 向量。
快速检查
(令 SW=diag(1,0)、δ=(1,0)T。证明正分母定义域中 J 的未正则化最大值是 1。加入 λI(λ>0)后,哪些方向最优?最大值是多少?)
设 w=(u,v)T;正分母定义域是 u=0。
解答 · 答案
设 w=(u,v)T。正分母条件是 u=0,而商是 u2/u2=1,与 v 无关。因此所有这些向量都最优,其中有很多互不平行的向量。
正则化后,商为 u2/((1+λ)u2+λv2)。最大值是 1/(1+λ),当且仅当 v=0、u=0 时达到;等价地,最优直线由 ((1+λ)−1,0)T 张成。在这个例子中,额外惩罚消除了原本零空间方向的不确定性。
快速检查
(在八点例子中,只改变第一个特征的单位,令 x′=diag(100,1)x,不作平移。求新的 δ′、SW′,以及对应于 w=(8,1)T 的方向。同一个实际数据点的中点决策会改变吗?)
利用 w′=A−Tw。
解答 · 答案
新均值差是 (200,1)T,散布是 diag(40000,16)。与原方向一致的尺度选择是 w′=A−Tw=(2/25,1)T。它在 x′ 的分数等于原来在 x 的分数,所以中点阈值仍是 17/2,决策不变。若解新线性系统,会得到 (1/200,1/16)T,正好是 w′/16;只要阈值也除以 16,就代表相同的方向及规则。