Kernel PCA

PCA是一個有效了解資料分佈的方式。然而由於他是線性的，因此在許多狀況無法被直接套用。Kernel PCA解除了線性分析的限制。

注意

本篇內容需要對PCA有一定程度的了解。建議先看過PCA篇的內容。

簡介

關於kernel PCA的用途在PCA篇已經介紹過了，這裡簡介這個方法和PCA的差異之處。

在PCA中，我們定義一個covariance matrix $S_X = \cfrac{1}{n-1}XX^T$，並利用這個matrix來定義資料的好壞，進而利用Singular Value Decomposition (SVD)來最大化資料的好壞。我們也提到了Kernel PCA即是把資料先投影到高維空間再來做PCA。因此，假設資料本來的設定為 $${x_1, x_2, \dots, x_k \quad \text{with } x_l \in \Bbb{R}^N, \sum_l x_l = 0}$$ 則我們定義一個function投影到feature space $F \in \Bbb{R}^M$ $$\phi : \Bbb{R}^N \to \Bbb{R}^M \quad ,\phi(x) \in \Bbb{R}^M$$ 所以我們現在便是在計算 $S_{\phi(x)}$，其中對於每一個元素$S_{\phi(x), ij}$ $$S_{\phi(x), ij} = \cfrac 1 k \; \phi(X_{i}) \cdot \phi(X_{j})^T$$ 但是因為這樣對於每一筆資料我們都要計算一次，我們其實並不這麼做。

數學理論

Kernel Trick

Kernel trick讓我們不用將每一筆資料的$\phi(x_l)$算出來（又或者，我們不在乎這個關係），我們轉而要量化的是兩筆資料經過轉換後的關係。關鍵點就在，定義一個kernel function $\kappa(x, y)$。這個function接受兩筆資料，然後傳回一個數字代表這個關係。 $$\kappa(x, y) = \phi(x)^T \cdot \phi(y)$$ 所以我們要從定義出發，把所有遇到$\phi(x)$的變數都轉化為kernel function的方式表示。如此一來我們就不用詳細定義 $\phi : \Bbb{R}^N \to \Bbb{R}^M$ 。

待補充：kernel function重要之處

首先，$S_{\phi(x), ij}$是一個$\left( M \times M \right)$的矩陣，可以被改寫成 $$S_{\phi(x)} = \cfrac 1 k \; \sum_{l=1}^k \phi(x_l) \cdot \phi(x_l)^T$$ 然後，先把計算eigenvector和eigenvalue的方程式寫出來（注意$\mathbf{v}_t$是一個$M$維的向量） $$S_{\phi(x)} \mathbf{v}_t = \lambda_t \mathbf{v}_t \quad,t=1, 2, \dots,M$$ 結合前兩式，再兩邊同除以 $\lambda_t$ $$\mathbf{v}_t = \sum_{l=1}^k a_{tl} \cdot \phi(x_l)$$ 再代回去計算eigenvector和eigenvalue的方程式，兩邊乘以 $\phi(x_s)^T$（把eigenvector換掉，想辦法把kernel function $\kappa(x, y)$ 湊出來） $$\left[\cfrac 1 k \; \sum_{l=1}^k \phi(x_l) \cdot \phi(x_l)^T \right]\left[ \sum_{l=1}^k a_{tl} \cdot \phi(x_l) \right] = \lambda_t \left[ \sum_{l=1}^k a_{tl} \cdot \phi(x_l) \right] \\[2ex] \left[\cfrac 1 k \; \sum_{l=1}^k \phi(x_l) \cdot \phi(x_l)^T \right]\left[ \sum_{l=1}^k a_{tl} \cdot \phi(x_l) \cdot \phi(x_s)^T \right] = \lambda_t \left[ \sum_{l=1}^k a_{tl} \cdot \phi(x_l)\cdot \phi(x_s)^T \right]$$ 最後generalize $\phi(x_s)^T$（讓 $s$ 等於 $1, 2, \dots, k$），就得到 $$K^2 \cdot a_t = (\lambda_t k) \; K \cdot a_t \quad, \begin{cases} K_{ij} = \kappa(x_i, x_j) \\[2ex] a_t = \left[ \; a_{t1} \; a_{t2} \; a_{t3} \dots a_{tk} \;\right]^T \end{cases}$$ 同除以 $K$，這就是一個算 $a_t$ 的方程式（很有趣的是，我們是在這裡才把 $\lambda_t$ 算出來），解出 $a_t$ 就可以解出 $\mathbf{v}_t$ ，如果我們有定義 $\phi(x)$ 的話。

就算沒有解出 $\mathbf{v}_t$ ，我們還是可以用 $a_t$ 解出kernel principal component $y_t(x)$ $$y_t(x) = \phi(x)^T \mathbf{v}_t = \sum_{l=1}^k a_{tl} \kappa(x, x_l)$$

Kernel PCA

所以要如何使用kernel PCA？以下整理步驟

1. 設計一個kernel function，把 $K$ （一個 $(l \times l)$ 的kernel matrix）算出來。

2. 前面未提及的步驟：通常 ${\phi(x)}$ 的mean都不是 $0$ ，這時候要計算代替的 $\tilde{K}$ $$\tilde{K} = K - 1_l K = K 1_l + 1_l K 1_l \qquad, 1_{l, ij} = \cfrac 1 l \quad \forall \; i, j$$

3. 計算 $a_t$

4. 計算 $y_t(x)$

Kernel Function

有幾個常用的kernel function

1. Gaussian radial basis function (RBF) kernel $$\kappa_\gamma(x_i, x_j) = e^{- \gamma \lVert x-y \rVert^2_2} \quad, \gamma > 0$$

2. Sigmoid kernel $$\kappa_{\gamma, \theta}(x_i, x_j) = tanh(\gamma \; x_i^T \cdot x_j + \theta)$$

3. Linear kernel （這就是PCA） $$\kappa(x_i, x_j) = x^T_i \cdot x_j$$

4. Polynomial kernel $$\kappa_{d, \gamma, \theta} = \left( \gamma \; x^T_i \cdot x_j + \theta \right)^d \quad, \gamma > 0$$

選擇一個適合的kernel需要一些對model的認識。如果對model完全不了解，可以使用Gaussian RBF作為初步嘗試。可以參考一下這篇CrossValidated的post。

結論

特點

1. kernel function能夠設定參數

   PCA是個沒有參數的資料分析方法，因此帶有諸多限制。Kernel PCA中的 $\kappa(x, y)$ 可以讓我們在設定kernel function的時候調整參數，來達到更好的效果。

待補充

其他討論

在很大的資料上使用kernel PCA

待補充

參考資料