流形正則化

機器學習中，流形正則化（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$是超參數，用於控制演算法對簡單函數與更能擬合數據的函數的偏好。

<image>

流形正則化在標準吉洪諾夫正則化的環境正則項（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 - J K \alpha)^{\mathrm{T}} (Y - J K \alpha) + \gamma_A \alpha^{\mathrm{T}} K \alpha + \frac{\gamma_I}{(\ell + u)^2} \alpha^{\mathrm{T}} K L K \alpha$$

解是

$\alpha^* = \left( JK + \gamma_A \ell I + \frac{\gamma_I \ell}{(\ell + u)^2} L K \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_if(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_if(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} L K \right)^{-1} J^{\mathrm{T}} Y \beta^*$$

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

$$\begin{align} & & \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 \le \beta_i \le \frac{1}{\ell}\; i = 1, \ldots, \ell \end{align}$$

Q的定義是

$Q = YJK \left( 2 \gamma_A I + 2 \frac{\gamma_I}{(\ell + u)^2} L K \right)^{-1} J^{\mathrm{T}} Y$

LapSVM已被應用於大地成像。

醫學成像。

人臉識別。

機器維護。

腦機接口等問題。

## 局限

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

## 外部連結

### 軟體

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