兩組帶標籤的點若有不同的平均值,沿兩個平均值之差的方向投影,似乎就是自然的區分方法。不過,平均值相差一個單位,在每個方向並不具有同樣意義。如果點在該方向本來就分散得很廣,投影後的兩組仍可能大量重疊。另一個平均差較小、組內散佈卻更小的方向,反而可能更有區分力。
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,所以被誤分。
例題 19.1.5
(平均值相同:比值完全看不見差異)
取一維兩類樣本值 {−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,就代表相同的方向及規則。