流形正則化

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

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

流形正則器

動機

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

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

${\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}$

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

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

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

拉普拉斯範數

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

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

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

基於圖的拉普拉斯範數

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

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

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

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

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

${\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}$

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

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

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

拉普拉斯範數的泛函方法

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

應用

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

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

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

$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}$

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

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

解$\alpha ^{*}$可得

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

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

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

$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}$

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

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

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

$\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$

解是

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

LapRLS已被用於傳感器網絡、 醫學成像、 物體檢測、 光譜學、 文檔分類、 藥物-蛋白質相互作用、 壓縮圖像與視頻等問題。

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

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

$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}$

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

$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}$

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

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

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

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

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

${\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的定義是

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

LapSVM已被應用於大地成像、 醫學成像、 人臉識別、 機器維護、 腦機接口等問題。

局限

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

另見

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

外部連結

軟件

• ManifoldLearn庫與Primal LapSVM庫在MATLAB中實現了LapRLS和LapSVM。
• C++的Dlib庫包含線性流形正則化函數。