動機
無監督學習沒有唯一通用的「好群組」定義。歐幾里得(Euclid)聚類獎勵接近同一中心,圖聚類重視組內強連接及組間弱連接,非負分解則尋找矩陣的相加構件。這些目標都有用途,但改變幾何或表示方式,同一批觀測也可能得到不同分組。
小樣本帶來第二層困難:較靈活的模型可更貼合已觀察數據,卻未必更能預測。選群組數、表示維數、正則化強度,本身就是學習決策。若反覆查看測試樣本來作選擇,測試樣本便成了訓練的一部分。因此,最優化與可信的模型評估必須一起理解。
本節推導 k-means、譜鬆弛、非負矩陣分解、嶺回歸及 lasso 的有限維基礎。
定義
定義 3.1.1
(k-means 目標)
給定 與整數 ,選指派 及中心 ,以最小化
通常交替把觀測指派給最近中心,再把每個非空群組的中心換成平均值。空群組需要明確處理規則;任意放置的新中心並不是「空集合的平均」。
歐幾里得距離依賴量度單位。同一座標從米改為毫米,平方差會增大一百萬倍。標準化座標會改變最優化目標,有時合理,但若要評估預測表現,位置與尺度估計也必須只用訓練數據擬合。
定義 3.1.2
(加權圖及其拉普拉斯矩陣)
設 為對稱、非負、對角為零的 矩陣。令 ,未正規化拉普拉斯(Laplacian)矩陣為 。若兩頂點之間有一條每條邊權重皆正的路徑,便稱它們連通。頂點子集 的割權重為 。
用甚麼圖來聚類,本身就是建模選擇。距離核、最近鄰圖及連接門檻可能表達不同鄰近關係。下述譜結論要求矩陣對稱,因此對稱化不可忽略。另外,這裏的未正規化形式不同於涉及 的正規化割形式;不可不檢查目標就交換兩者的特徵向量。
定義 3.1.3
(非負矩陣分解)
對非負數據 ,非負矩陣分解(NMF)例如選 、 最小化 。每個數據列於是是 的非負列向量的相加組合。秩參數 、損失與限制都是問題定義的一部分。固定一個因子後,目標對另一因子是凸二次式;但聯合最優化通常非凸,不能把分別的凸性誤當聯合凸性。
「相加」有具體含義:非負係數不能抵銷另一構件的正貢獻。當量度本身具有可加性時,這可令表示較容易檢視,卻不能證明因子是唯一的物理物件。相關構件可在不同因子之間重新分配,精確擬合也仍有尺度歧義。可解釋性是需要研究的問題,不是只加符號限制就得到的定理。
平方損失的無限制梯度為 與 。在受限制駐點,嚴格正的座標必須有零梯度;零座標則可有非負梯度,因為只可向增加方向移動。這已說明為何不能先解無限制正規方程,再把負值截成零:截斷改變了耦合最優點,必須重新檢查原來的受限制問題。
定義 3.1.4
(嶺回歸與 lasso 目標)
對設計矩陣 與反應 ,嶺回歸目標為 ,lasso 目標為 ,其中 、。水平為 的軟門檻映射把實數 送到 。
定理/命題
定理 3.1.5
(質心最優性與交替下降)
對非空固定群組 ,算術平均 唯一最小化 。因此,最近中心指派後接平均更新,不會增加 k-means 目標,前提是空群組也以不增加目標的方式處理。下降不代表已找到全域最優聚類。
定理 3.1.6
(拉普拉斯量度邊上的變化)
對每個 ,
其零空間恰由在每個連通分量內為常數的向量組成。特別地,若圖連通且至少有兩頂點,在 、 限制下, 的最小化點可以取為 的第二小特徵值所對應的特徵向量。
概念視角組合
同一能量也是割的計數
對頂點子集 ,令 為其指示向量,在 內取一,其餘取零。在 中,只有恰好一端屬於 的頂點對才有貢獻,這時 。每個無序頂點對在雙重和中出現兩次,所以 ,即割權重。以三頂點單位權重路徑圖為例, 時 ,恰是離開 的一條邊; 時為 ,即離開 的兩條邊。因此,對實向量定義的二次型,把「切斷了多少條邊」的組合計數推廣成沿邊變化的連續量度。
定理 3.1.7
(嶺回歸唯一性及正交設計下的 lasso 收縮)
對任何實 及 , 有唯一最小化點 。若 ,則 的最小化點各座標為
這裏每個係數都受懲罰;若截距不受懲罰,必須另列設定。
證明思路或證明
證明
(質心恆等式為何保證下降)
寫 ,展開平方並利用 ,得
第二項證明均值唯一最優。固定中心時,各觀測的最近中心指派逐項最小化誤差;固定指派時,上式則逐組最小化誤差。串起兩個不等式便證明下降。目標下界為零,因此其數值序列收斂;但單憑這點,不能證明所有平手處理方式都會終止,更不能證明找到最佳分割。
證明
(圖能量與譜鬆弛)
展開圖能量的平方。由對稱性,兩個平方項合成 ,交叉項為 ,故等於 。非負加權平方和為零,要求每條正權邊兩端數值相等,從而在整個連通分量上相等;反過來,分量內常數顯然給零能量。
對連通圖取正交特徵基底,第一向量為 ,特徵值為 。每個可行向量可寫成 ,其中 ,故 ,第二特徵空間內可達等號。離散指示向量有更多限制;放寬成實向量後,最終仍需取整或按門檻分組。
證明透視
從割變成特徵向量時放寬了甚麼
圖能量等於割權重,只對 – 指示向量 成立。實特徵向量未必是指示向量,對它套用門檻會改變向量及限制。譜定理精確解決的是鬆弛後的二次問題,不會自動保證任意門檻都產生全域最優的平衡圖分割。
證明
(二次穩定化與稀疏門檻)
嶺回歸梯度為 。對任意非零 ,有 ,所以即使 秩不足,駐點仍是唯一最小值。
若 ,lasso 目標與 只差常數。正座標的導數方程給 ,僅在 可行;負座標給 ,僅在 可行。零處的次梯度條件是 。合起來就是軟門檻公式。若列向量不正交,各座標互相耦合,這個一次逐座標公式一般不成立。
反例模式
列向量不正交時軟門檻失效
設想一個斷言:對任何設計,lasso 的最小化點都是 ,其中 。取只有一個觀測、兩個完全相同特徵的例子:、、。此時 ,公式給出 ,目標值為
但 的目標值是 ,較小,所以公式的輸出不是最小化點。這裏 。事實上,令 ,目標至少為 ,當且僅當兩個座標不異號時取等號;這個下界在 最小,值為 。因此最小化點是所有滿足 、 的 ,並不唯一。逐座標軟門檻只在 時精確成立;一般設計的各座標互相牽動,lasso 必須當作耦合的凸問題來解。
例題詳解
嶺回歸也可按奇異方向理解。若設計的非零奇異值為 ,右奇異向量上的係數等於反應的相應左奇異座標乘以 ;未正則化求逆則乘以 。極小奇異值會把噪音大幅放大,嶺回歸能抑制這種放大,但同時也收縮真實信號。選懲罰強度是在取捨偏差與方差,並非對所有真實係數都能免費改善。另外,特徵尺度若改變,其相對二次懲罰也會改變,除非已明確處理尺度。
例題 3.1.8
(一次下降的 k-means 迭代)
觀測為 ,起始中心為零與十。最近中心指派給群組 與 ,目標為 。均值更新給一與十,目標降至 。下次指派不變,故這是穩定的交替解。一般數據上若要證明全域最優,仍須另外論證。
例題 3.1.9
(三頂點路徑圖)
一與二、二與三之間各有一條單位權重邊,故
向量 、、 分別對應特徵值零、一、三。單位且均值為零的 能量為一,與兩條邊的平方差總和相同。正負號提供頂點排序,但中間的零仍需分組慣例。把特徵向量反號,不會改變原來的圖。
例題 3.1.10
(相加分解的尺度並不唯一)
矩陣 有精確非負秩一分解 、。對任何 , 與 給出相同乘積及零誤差。因此非負性本身不能識別尺度。把列標準化可以消除此歧義,但一般不能證明高秩分解唯一。另外,非負因子乘積不可能精確重構含負元素的矩陣。
例題 3.1.11
(嶺回歸收縮,lasso 可以移除座標)
取 、、。嶺回歸把每個係數除以二,得 ;lasso 以軟門檻得 。零來自絕對值在原點的尖角,並非數值捨入。平方損失或懲罰的係數若改變,門檻也會改變,因此公式必須對照實際寫下的目標。
模型選擇利用數據挑選 、因子秩或 等設定。驗證集在獨立訓練擬合後估計表現;交叉驗證讓不同摺輪流擔任驗證集。所有依賴數據的步驟,包括尺度標準化、特徵篩選及 PCA,都要在每個訓練摺內擬合,再應用到該摺驗證數據。選好設定後,可在全部開發數據上重新擬合;若要獨立評估,最後仍需要未曾用來選擇的測試樣本。
對有 個自由參數的似然模型,常見分數為 、,通常選較小者。兩者有不同漸近動機與正則條件,並非通用的有限樣本風險界。例如無限制混合有似然奇異與識別困難,僅僅數參數,並不能證明正則模型的 BIC 近似適用。小樣本時更要留意這些條件;驗證分數本身也有不確定性,少許數值優勢不代表持久的總體優勢。
常見錯誤
反例模式
穩定 k-means 仍可錯過較好分割
數據為 ,兩中心為二與七。指派是 與 ,每個中心已是群組均值,交替步驟不會改變,目標為 。但改用群組 與 ,均值零與六,目標為 。所以穩定與下降都不能當作全域最優證書。
常見錯誤
(小樣本不能支持無限次搜索模型)
嘗試大量超參數後,報告最佳測試結果,會挑中有利的測試噪音。即使沒有對測試集計算梯度,這樣重用它仍改變了其統計角色。交叉驗證前先用全部觀測估計尺度,也把資訊跨越了分割。完整選擇程序應留在開發數據內,並報告評估的不確定性,不要把每個小差異都當成實質進步。
總結
質心更新解固定指派的 k-means 問題,拉普拉斯特徵向量解鬆弛圖能量問題,NMF 要求非負相加結構。嶺回歸穩定所有係數方向,lasso 則可把座標設成精確零。每種方法都有指定目標,而選擇目標及複雜度也是學習的一部分,可靠評估必須把這些選擇算進去。
練習
快速檢查
(群組含零、二、七。求最佳中心及最小平方誤差;若用中心四,會增加多少誤差?)
使用質心恆等式,不必重複展開二次式。
解答 · 答案
均值為三,最小平方誤差為 。用中心四,額外增加 ,總誤差為二十九。乘數是群組大小,不是數據維數。
快速檢查
(圖有兩個分量:頂點一、二之間有單位權重邊,第三頂點孤立。描述拉普拉斯零空間及其維數。)
孤立頂點本身也是連通分量。
解答 · 答案
拉普拉斯為 ,零空間是 ,維數二,可用 、 作基底。若只允許一個全圖常數,便會漏掉不連通分量的自由度。
快速檢查
(X 只有一行 (1,1),反應為二,嶺參數為一。求嶺係數,並比較未正則化最小二乘的唯一性。)
沿用定理中平方損失前有二分之一的約定。
解答 · 答案
嶺方程為 ,故 。沒有懲罰時,所有滿足 的向量皆令平方誤差最小。嶺回歸選出唯一但帶偏的擬合,係數和為 ;即使原來可插值,加入懲罰後也不會自動保留精確插值。
快速檢查
(正交設計下 ,lasso 參數為 0.5。求係數,並解釋恰在門檻上的座標。)
使用零處的次梯度條件。
解答 · 答案
軟門檻結果為 。當 ,零滿足次梯度條件,且二次項嚴格凸,故仍是唯一純量最小化點。在等號處係數變成零,並不會產生一整段最小化點。