流形正則化

機器學習中，流形正則化（Manifold regularization）是一種利用數據集形狀以約束應在數據集上被學習的函數的技術。在很多機器學習問題中，待學習數據不能涵蓋整個輸入空間。例如，人臉識別系統不需要分類所有圖像，只需分類包含人臉的圖像。流形學習技術假定相關數據子集來自流形，是一種具有有用屬性的數學結構；且待學習函數是光滑的，即不同標籤的數據不應靠在一起，即在有大量數據的區域，標籤函數不應快速變化。這樣，流形正則化算法便可利用無標數據，通過推廣的吉洪諾夫正則化推斷哪些區域允許待學習函數快速變化，哪些區域不允許。流形正則化算法可將監督學習算法推廣到半監督學習和轉導，因為當中有無標數據。流形正則化技術已被應用於醫學成像、大地成像與物體識別等領域。

標記數據（黑、白圓圈）稀疏時，流形正則化可利用無標數據（灰色圓圈）將數據分類。無大量標記點時，監督學習算法智能學習非常簡單的決策邊界（上圖）。基於鄰點很可能屬於同一類的假設，決策邊界應避開含大量未標記點的區域。這也就是一種半監督學習。

流形正則器

動機

流形正則化是正則化的一種。正則化是通過懲罰複雜解，以減少過擬合、確保問題良置的一系列技術。具體說，流形正則化擴展了應用於再生核希爾伯特空間（RKHSs）的吉洪諾夫正則化。在RKHS的標準吉洪諾夫正則化下，學習算法試圖從函數${\displaystyle {\mathcal {H}}}$的假設空間中學習函數f。假設空間是RKHS，就是說與核K相關聯，於是候選函數f都有範數${\displaystyle \left\|f\right\|_{K}}$，代表候選函數在假設空間中的複雜度。算法會考慮候選函數的範數，以懲罰複雜函數。

形式化：給定一組有標訓練數據${\displaystyle (x_{1},y_{1}),\ldots ,(x_{\ell },y_{\ell })}$，其中${\displaystyle x_{i}\in X,y_{i}\in Y}$，以及損失函數V。基于吉洪諾夫正則化的學習算法將試圖求解

${\displaystyle {\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }V(f(x_{i}),y_{i})+\gamma \left\|f\right\|_{K}^{2}}$

其中${\displaystyle \gamma }$是超參數，用於控制算法對簡單函數與更能擬合數據的函數的偏好。

嵌入3維空間的2維流形（左）。流形正則化試圖學習在展開流形上光滑的函數（右）。

流形正則化在標準吉洪諾夫正則化的環境正則項（ambient regularizer）上增加了第二個正則化項——內蘊正則項（intrinsic regularizer）。在流形假設下，數據不是來自整個輸入空間X，而是來自非線性流形${\displaystyle M\subset X}$。流形（即內蘊空間）的幾何用於確定正則化範數。^[1]

拉普拉斯範數

內蘊正則項${\displaystyle \left\|f\right\|_{I}}$有很多選擇。如流形上的梯度${\displaystyle \nabla _{M}}$，可以衡量目標函數的光滑程度。光滑函數應在輸入數據密集處變化較慢，即梯度${\displaystyle \nabla _{M}f(x)}$與邊際概率密度（marginal probability density）${\displaystyle {\mathcal {P}}_{X}(x)}$（隨機選定的數據點落在x處的概率密度）呈負相關。這就為內蘊正則項提供了合適的選擇：

${\displaystyle \left\|f\right\|_{I}^{2}=\int _{x\in M}\left\|\nabla _{M}f(x)\right\|^{2}\,d{\mathcal {P}}_{X}(x)}$

實踐中，由於邊際概率密度${\displaystyle {\mathcal {P}}_{X}}$未知，無法直接計算範數，但可根據數據進行估計。

基於圖的拉普拉斯範數

將輸入點間距解釋為圖，圖的拉普拉斯矩陣就可幫助估計邊際分布。假設輸入數據包括${\displaystyle \ell }$個有標例子（輸入x與標籤y的點對）、u個無標例子（無對應標籤的輸入）。定義W為圖的邊權重矩陣，${\displaystyle W_{ij}}$是數據點${\displaystyle x_{i},\ x_{j}}$間的距離。定義D為對角矩陣，其中${\displaystyle D_{ii}=\sum _{j=1}^{\ell +u}W_{ij}}$。L是拉普拉斯矩陣${\displaystyle D-W}$。則，隨着數據點數${\displaystyle \ell +u}$增加，L將收斂於拉普拉斯-貝爾特拉米算子${\displaystyle \Delta _{M}}$，其是梯度${\displaystyle \nabla _{M}}$的散度。^[2][3]則若${\displaystyle \mathbf {f} }$是f在數據處的值向量，${\displaystyle \mathbf {f} =[f(x_{1}),\ldots ,f(x_{l+u})]^{\mathrm {T} }}$，則就可估計內蘊範數：

${\displaystyle \left\|f\right\|_{I}^{2}={\frac {1}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

隨着數據點數${\displaystyle \ell +u}$增加，${\displaystyle \left\|f\right\|_{I}^{2}}$的經驗定義會收斂到已知${\displaystyle {\mathcal {P}}_{X}}$時的定義。^[1]

基於圖的方法解正則化問題

用權重${\displaystyle \gamma _{A},\ \gamma _{I}}$作為環境正則項和內蘊正則項，最終的待解表達式變為

${\displaystyle {\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }V(f(x_{i}),y_{i})+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

與其他核方法類似，${\displaystyle {\mathcal {H}}}$可能是無限維空間。因此，若正則化表達式無法明確求解，就不可能在整個空間中搜索解；相反，表示定理表明，在選擇範數${\displaystyle \left\|f\right\|_{I}}$的特定條件下，最優解${\displaystyle f^{*}}$必須是以每個輸入點為中心的核的線性組合：對某些權重${\displaystyle \alpha _{i}}$

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}K(x_{i},x)}$

利用這結果，可在${\displaystyle \alpha _{i}}$的可能選擇定義的有限維空間中搜索最優解${\displaystyle f^{*}}$。^[1]

拉普拉斯範數的泛函方法

圖拉普拉斯之外的想法是利用鄰域估計拉普拉斯量。這種方法類似於局部平均法，但眾所周知處理高維問題時擴展性很差。事實上，圖拉普拉斯函數會受到維數災難影響。^[2] 幸運的是，通過更先進的泛函分析，可利用函數的預期光滑性進行估算：由核導數估計拉普拉斯算子的值${\displaystyle \partial _{1,j}K(x_{i},x)}$，其中${\displaystyle \partial _{1,j}}$表示對第一個變量第j個坐標的偏導數。^[4] 這第二種方法與無網格法有關，同PDE中的有限差分法形成對比。

應用

選擇適當的損失函數V、假設空間${\displaystyle {\mathcal {H}}}$，流形正則化可推廣到各種可用吉洪諾夫正則化表達的算法。兩個常用例子是支持向量機和正則化最小二乘法。（正則化最小二乘包括嶺回歸；相關的LASSO、彈性網正則化等算法可被表為支持向量機。^[5][6]）這些算法的推廣分別稱作拉普拉斯正則化最小二乘（LapRLS）和拉普拉斯支持向量機（LapSVM）。^[1]

拉普拉斯正則化最小二乘（LapRLS）

正則化最小二乘（RLS）是一類回歸分析算法：預測輸入x的值${\displaystyle y=f(x)}$，目標是使預測值接近數據的真實標籤。RLS的設計目標是在正則化的前提下，最大限度減小預測值與真實標籤之間的均方誤差。嶺回歸是RLS的一種形式，一般來說RLS與結合了核方法的嶺回歸是一樣的。^{[來源請求]}在吉洪諾夫正則化中，損失函數V的均方誤差是RLS問題陳述的結果：

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma \left\|f\right\|_{K}^{2}}$

根據表示定理，解可寫作在數據點求值的核的加權和：

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell }\alpha _{i}^{*}K(x_{i},x)}$

解${\displaystyle \alpha ^{*}}$可得

${\displaystyle \alpha ^{*}=(K+\gamma \ell I)^{-1}Y}$

其中K定義為核矩陣，${\displaystyle K_{ij}=K(x_{i},x_{j})}$，Y是標籤向量。

為流形正則化添加拉普拉斯項，得到拉普拉斯RLS的表達：

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

再根據流形正則化的表示定理，可知

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)}$

這就得到了向量${\displaystyle \alpha ^{*}}$的表達式。令K是上述核矩陣，Y是數據標籤向量，J是${\displaystyle (\ell +u)\times (\ell +u)}$分塊矩陣${\displaystyle {\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}}$：

${\displaystyle \alpha ^{*}={\underset {\alpha \in \mathbf {R} ^{\ell +u}}{\arg \!\min }}{\frac {1}{\ell }}(Y-JK\alpha )^{\mathrm {T} }(Y-JK\alpha )+\gamma _{A}\alpha ^{\mathrm {T} }K\alpha +{\frac {\gamma _{I}}{(\ell +u)^{2}}}\alpha ^{\mathrm {T} }KLK\alpha }$

解是

${\displaystyle \alpha ^{*}=\left(JK+\gamma _{A}\ell I+{\frac {\gamma _{I}\ell }{(\ell +u)^{2}}}LK\right)^{-1}Y}$^[1]

LapRLS已被用於傳感器網絡、^[7] 醫學成像、^[8][9] 物體檢測、^[10] 光譜學、^[11] 文檔分類、^[12] 藥物-蛋白質相互作用、^[13] 壓縮圖像與視頻等問題。^[14]

拉普拉斯支持向量機（LapSVM）

支持向量機（SVMs）是一系列算法，常用於數據分類。直觀說，SVM在類間畫出邊界，使最接近邊界的數據儘量遠離邊界。這可直接表為線性規劃問題，但也等同於帶鉸鏈損失的吉洪諾夫正則化，即${\displaystyle V(f(x),y)=\max(0,1-yf(x))}$：

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma \left\|f\right\|_{K}^{2}}$^[15][16]

將內蘊正則化項加進去，就得到了LapSVM問題的陳述：

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

同樣，表示定理允許用在數據點得值的核表示解：

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)}$

將問題重寫為線性規劃問題、求解對偶問題就可得到${\displaystyle \alpha }$。令K是核矩陣、J是分塊矩陣${\displaystyle {\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}}$，則解可寫作

${\displaystyle \alpha =\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y\beta ^{*}}$

其中${\displaystyle \beta ^{*}}$是對偶問題的解

${\displaystyle {\begin{aligned}&&\beta ^{*}=\max _{\beta \in \mathbf {R} ^{\ell }}&\sum _{i=1}^{\ell }\beta _{i}-{\frac {1}{2}}\beta ^{\mathrm {T} }Q\beta \\&{\text{subject to}}&&\sum _{i=1}^{\ell }\beta _{i}y_{i}=0\\&&&0\leq \beta _{i}\leq {\frac {1}{\ell }}\;i=1,\ldots ,\ell \end{aligned}}}$

Q的定義是

${\displaystyle Q=YJK\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y}$^[1]

LapSVM已被應用於大地成像、^[17][18][19] 醫學成像、^[20][21][22] 人臉識別、^[23] 機器維護、^[24] 腦機接口等問題。^[25]

局限

• 流形正則化假定不同標籤的數據不在一起，這樣就能從無標數據中提取信息。但這隻適用於一部分問題。根據數據結構不同，可能要用不同的半監督或轉導學習算法。^[26]
• 某些數據集中，函數的內蘊範數${\displaystyle \left\|f\right\|_{I}}$可能非常接近環境範數${\displaystyle \left\|f\right\|_{K}}$：例如，若數據由位於垂直線上的兩類組成，則內蘊範數將等於環境範數。這時，即便數據符合光滑分離器假設，無標數據也無法對流形正則化學習到的解產生影響。與聯合訓練相關的方法已用於解決這一限制。^[27]
• 若有大量無標數據，則核矩陣K將變得極大，計算時間可能非常久。這時在線算法與流形的稀疏近似可能有所幫助。^[28]

另見

• 流形學習
• 流形假設
• 半監督學習
• 轉導 (機器學習)
• 譜圖論
• 再生核希爾伯特空間
• 吉洪諾夫正則化
• 微分幾何