Note 7 - 核主成分分析（Kernel Principal Component Analysis）

核主成分分析

• Note 7 - 核主成分分析（Kernel Principal Component Analysis）
• • 7.1 用內(nèi)積表示的線性PCA(Linear PCA expressed with inner products)
  • 7.2 向核PCA過渡 (Transition to Kernel PCA)
  • Definition 7.1 正定核 (Positive Definite Kernel)

標(biāo)準(zhǔn)PCA通過將觀察到的數(shù)據(jù)投射到一個線性子空間來降低其維度。選擇投影的方式是使以平方的標(biāo)準(zhǔn)歐氏準(zhǔn)則衡量的誤差最小，這也可以解釋為減少白高斯噪聲的一種方式。一個非常重要的應(yīng)用是將PCA作為分類的預(yù)處理，因為分類器在減少噪聲的特征空間中表現(xiàn)更好。

標(biāo)準(zhǔn)PCA的主要缺點是，它嚴(yán)重依賴數(shù)據(jù)的近似線性結(jié)構(gòu)。在許多應(yīng)用中，這是一個過于嚴(yán)格的假設(shè)。核PCA（K-PCA）是標(biāo)準(zhǔn)PCA的一個擴展，它沒有這些缺點。K-PCA的關(guān)鍵思想是，它隱含地假設(shè)存在一個非線性映射

$$?:{\mathbb{R}}^p\to \mathcal{H},\text{\hspace{1em}(7.1)}$$
其中$\mathcal{H}$是一個非常高維的向量空間（甚至可能是無限維的），其內(nèi)積為${}^1??,??$。我們無妨把$\mathcal{H}$看作是一些${\mathbb{R}}^P$，有非常大的$P$。作為一個初步的步驟，我們重新表述眾所周知的標(biāo)準(zhǔn)PCA，使其只涉及我們數(shù)據(jù)的內(nèi)積。

${}^1$ 形式上，希爾伯特空間$\mathcal{H}$是一個實數(shù)或復(fù)數(shù)內(nèi)積空間，就內(nèi)積所引導(dǎo)的距離函數(shù)而言，它也是一個完整的公制空間。

7.1 用內(nèi)積表示的線性PCA(Linear PCA expressed with inner products)

讓$\mathbf{X}\in {\mathbb{R}}^{p\times n}$為居中的數(shù)據(jù)矩陣（這將是下面推導(dǎo)的一個關(guān)鍵假設(shè)），讓$\mathbf{K}:={\mathbf{X}}^{?}\mathbf{X}$為$(n\times n)$矩陣，由數(shù)據(jù)的所有內(nèi)積組成。更確切地說，$(i,j)$項是$\mathbf{K}$第$i$和第$j$觀測值的內(nèi)積${\mathbf{x}}_i^{?}{\mathbf{x}}_j$。

回顧一下，如果$\mathbf{X}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^{?}$是數(shù)據(jù)矩陣的SVD。那么數(shù)據(jù)向量$\mathbf{y}\in {\mathbb{R}}^p$的前$k$主分量是由${\mathbf{U}}_k^{?}$給出的。在目前的情況下，只給出了內(nèi)積，因此不可能直接得到${\mathbf{U}}_k$。然而，$\mathbf{K}$的特征值分解允許對這個問題有一個優(yōu)雅的解決方案。記住，我們有 $\mathbf{K}:={\mathbf{X}}^{?}\mathbf{X}$ 并用它的SVD代替$\mathbf{X}$。我們得到

$$\mathbf{K}=\mathbf{V}{\mathbf{\Sigma }}^{?}\mathbf{\Sigma }{\mathbf{V}}^{?}\text{.?}\text{\hspace{1em}(7.2)}$$

記住，$\mathbf{V}$是正交的，${\mathbf{\Sigma }}^{?}\mathbf{\Sigma }$是對角的。因此，方程（7.2）是$\mathbf{K}$的特征值分解(EVD)，由于EVD的唯一性，通過計算$\mathbf{K}$的$k$最大特征值與它們各自的特征向量，我們得到${\sigma }_1^2,?,{\sigma }_k^2$和${\mathbf{V}}_k$。我們將假設(shè)${\sigma }_k>0$，否則我們可以減少目標(biāo)子空間的維度而不損失任何數(shù)據(jù)信息。為了簡單起見，我們定義對角矩陣${\Sigma }_k=\mathrm{diag}\left({\sigma }_1,\dots ,{\sigma }_k\right)$。

這使我們能夠?qū)τ谝粋€給定的觀測值 $\mathbf{y}$只需使用內(nèi)積就可以計算出 ${\mathbf{U}}_k^{?}\mathbf{y}$的主成分。對于一個新的測量值$\mathbf{y}$，我們有

$$\begin{array}{rl}{\mathbf{V}}_k^{?}{\mathbf{X}}^{?}\mathbf{y}& ={\mathbf{V}}_k^{?}\mathbf{V}\mathbf{\Sigma }{\mathbf{U}}^{?}\mathbf{y}\\ & =\left[I_k\mid 0\right]\mathbf{\Sigma }{\mathbf{U}}^{?}\mathbf{y}\\ & =\left[{\mathbf{\Sigma }}_k\mid 0\right]{\mathbf{U}}^{?}\mathbf{y}\\ & ={\mathbf{\Sigma }}_k{\mathbf{U}}_k^{?}\mathbf{y}.\end{array}\text{\hspace{1em}(7.3)}$$

將此方程與${\Sigma }_k^{?1}$相乘，我們可以得到

$${\mathbf{U}}_k^{?}\mathbf{y}={\mathbf{\Sigma }}_k^{?1}{\mathbf{V}}_k^{?}{\mathbf{X}}^{?}\mathbf{y}={\mathbf{\Sigma }}_k^{?1}{\mathbf{V}}_k^{?}?\begin{array}{c}{\mathbf{x}}_1^{?}\mathbf{y}\\ ?\\ {\mathbf{x}}_n^{?}\mathbf{y}\end{array}?.\text{\hspace{1em}(7.4)}$$

注意，這個方程的右邊可以通過只涉及數(shù)據(jù)的內(nèi)積的數(shù)據(jù)來計算，即Gram-matrix $\mathbf{K}$和內(nèi)積${\mathbf{x}}_n^{?}\mathbf{y}$。

使數(shù)據(jù)居中
到目前為止，我們已經(jīng)假定數(shù)據(jù)是居中的，也就是說，Gram-matrix $\mathbf{K}$來自居中化的數(shù)據(jù)。這個假設(shè)很關(guān)鍵，因為否則方程（7.4）的推導(dǎo)將不成立。現(xiàn)在讓我們假設(shè)，我們沒有可用的居中數(shù)據(jù)，而Gram-matrix $\mathbf{K}$是由非居中數(shù)據(jù)建立的。好消息是，可以通過以下公式直接從$\mathbf{K}$推導(dǎo)出對應(yīng)于中心數(shù)據(jù)的格拉姆矩陣，例如$\tilde{\mathbf{K}}$，即

$$\tilde{\mathbf{K}}=\mathbf{H}\mathbf{K}\mathbf{H},\text{\hspace{1em}(7.5)}$$

其中$\mathbf{H}=\left({\mathbf{I}}_n?\frac{1}{n}{1}_n{1}_n^{?}\right)$.

---

證明：
從方程（1.3）中可以看出，如果$\mathbf{X}$表示非居中的數(shù)據(jù)矩陣，那么居中的矩陣由以下公式給出

$$\overline{\mathbf{X}}=\mathbf{X}?\hat{\mu }{1}_n^{?},\text{\hspace{1em}(7.6)}$$

有$\hat{\mu }=\frac{1}{n}\mathbf{X}{1}_n$。 由此，可以看出

$$\overline{\mathbf{X}}=\mathbf{X}?\frac{1}{n}\mathbf{X}{1}_n{1}_n^{?}=\mathbf{X}\left({\mathbf{I}}_n?\frac{1}{n}{1}_n{1}_n^{?}\right).\text{\hspace{1em}(7.7)}$$
用對稱矩陣的速記符號來表示 $\mathbf{H}:={\mathbf{I}}_n?\frac{1}{n}{1}_n{1}_n^{?}$。我們可以得到

$$\tilde{\mathbf{K}}={\overline{\mathbf{X}}}^{?}\overline{\mathbf{X}}={\mathbf{H}\mathbf{X}}^{?}\mathbf{X}\mathbf{H}=\mathbf{H}\mathbf{K}\mathbf{H}.\text{\hspace{1em}(7.8)}$$

---

因此，如果我們有來自非中心數(shù)據(jù)的Gram-matrix，我們可以很容易地計算出對應(yīng)于中心數(shù)據(jù)的Gram-matrix（無需明確地將$\mathbf{X}$居中）。由此，我們可以–如上所述–計算${\mathbf{V}}_k$和${\mathbf{\Sigma }}_k$。為了計算新數(shù)據(jù)樣本$\mathbf{y}$的主成分，我們首先要根據(jù)訓(xùn)練樣本把$\mathbf{y}$居中處理。具體來說，這意味著我們必須從$\mathbf{y}$減去訓(xùn)練數(shù)據(jù)的經(jīng)驗平均值$\hat{\mu }=\frac{1}{n}{\sum }_i{\mathbf{x}}_i=\frac{1}{n}\mathbf{X}{1}_n$。然后我們必須用$\overline{\mathbf{X}}=\mathbf{X}\mathbf{H}$替換公式（7.3）和（7.4）中的$\mathbf{X}$。這就得到了

$${\mathbf{U}}_k^{?}\left(\mathbf{y}?\frac{1}{n}\mathbf{X}{1}_n\right)={\mathbf{\Sigma }}_k^{?1}{\mathbf{V}}_k^{?}(\mathbf{X}\mathbf{H}{)}^{?}\left(\mathbf{y}?\frac{1}{n}\mathbf{X}{1}_n\right)={\mathbf{\Sigma }}_k^{?1}{\mathbf{V}}_k^{?}{\mathbf{k}}_y\text{\hspace{1em}(7.9)}$$

其中

$${\mathbf{k}}_y=\mathbf{H}?\begin{array}{c}{\mathbf{x}}_1^{?}\mathbf{y}\\ ?\\ {\mathbf{x}}_n^{?}\mathbf{y}\end{array}??\frac{1}{n}\mathbf{H}\mathbf{K}{1}_n$$

7.2 向核PCA過渡 (Transition to Kernel PCA)

現(xiàn)在，通過簡單地將內(nèi)積 ${\mathbf{x}}^{?}\mathbf{y}$替換為$??(\mathbf{x}),?(\mathbf{y})?$來擴展經(jīng)典的PCA是很簡單的。K-PCA的實際成功是由于計算$??(\mathbf{x}),?(\mathbf{y})?$時，既不需要$?$也不需要$??,??$ 的內(nèi)積。相反，只需要有一個函數(shù)

$$\kappa :{\mathbb{R}}^p\times {\mathbb{R}}^p\to \mathbb{R},(\mathbf{x},\mathbf{y})?\kappa (\mathbf{x},\mathbf{y})\text{\hspace{1em}(7.10)}$$

這反映了$??(\mathbf{x}),?(\mathbf{y})?$的屬性，即對于所有$\mathbf{x}\in {\mathbb{R}}^p$來說是對稱的，并且滿足$\kappa (\mathbf{x},\mathbf{x})\ge 0$ 的正定屬性。用$\kappa (\mathbf{x},\mathbf{y})$代替$??(\mathbf{x}),?(\mathbf{y})?$，因此不需要知道特征映射$?$，稱為核技巧（Kernel trick）。

Definition 7.1 正定核 (Positive Definite Kernel)

1. 令S:={x1,…,xn}?RpS:=\left\{\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right\} \subset \mathbb{R}^{p}S:={x1?,…,xn?}?Rp 與$\kappa (?)$如上定義. 帶有$(i,j)$ 項$k_{ij}=\kappa \left({\mathbf{x}}_i,{\mathbf{x}}_j\right)$的 $(n\times n)$-矩陣$\mathbf{K}$ 被稱為$S$的Gram-或Kernel-矩陣，相對于$\kappa$。

2. 如果對于所有有限的、非空的集合 $S?{\mathbb{R}}^p$來說，相應(yīng)的Gram-matrix是正半定的（正定的），那么這個函數(shù)$\kappa (?)$被稱為核（正定的核）。

在上一小節(jié)中，我們討論了在潛在的希爾伯特空間中的數(shù)據(jù)居中問題。我們在這里也面臨同樣的問題。當(dāng)一個新的數(shù)據(jù)點出現(xiàn)時，直接計算新數(shù)據(jù)點的非中心化內(nèi)積向量與訓(xùn)練數(shù)據(jù)的關(guān)系是很簡單的。我們將把它稱為

$${\mathbf{k}}^{\text{new?}}=?\begin{array}{c}??\left({\mathbf{x}}_1\right),?(\mathbf{y})?\\ ?\\ ??\left({\mathbf{x}}_n\right),?(\mathbf{y})?\end{array}?.$$

那么，中心化數(shù)據(jù)的第$j$條是

$${\left({\mathbf{k}}_{cent}^{new}\right)}_j=??\left({\mathbf{x}}_j\right)?\frac{1}{n}\sum _i?\left({\mathbf{x}}_i\right),?(\mathbf{y})?\frac{1}{n}\sum _i?\left({\mathbf{x}}_i\right)?$$

為了找到一個更簡潔的表達方式，我們利用標(biāo)量乘積的線性來得到

$$\begin{array}{c}??\left({\mathbf{x}}_j\right)?\frac{1}{n}\sum _i?\left({\mathbf{x}}_i\right),?(\mathbf{y})?\frac{1}{n}\sum _i?\left({\mathbf{x}}_i\right)?\\ =??\left({\mathbf{x}}_j\right),?(\mathbf{y})??\frac{1}{n}?\sum _i?\left({\mathbf{x}}_i\right),?(\mathbf{y})?\\ ?\frac{1}{n}??\left({\mathbf{x}}_j\right),\sum _i?\left({\mathbf{x}}_i\right)?+\frac{1}{n^2}?\sum _i?\left({\mathbf{x}}_i\right),\sum _i?\left({\mathbf{x}}_i\right)?,\end{array}$$

而且很容易看出，

$$\begin{array}{c}{\mathbf{k}}_{\text{cent?}}^{\text{new?}}={\mathbf{k}}^{\text{new?}}?\frac{1}{n}{1}_n{1}_n^{?}{\mathbf{k}}^{\text{new?}}?\frac{1}{n}\mathbf{K}{1}_n+\frac{1}{n^2}{1}_n{1}_n^{?}\mathbf{K}{1}_n\\ ={\mathbf{H}\mathbf{k}}^{\text{new?}}?\frac{1}{n}\mathbf{H}\mathbf{K}{1}_n.\end{array}$$

總之，對于一個訓(xùn)練集$\mathbf{X}=\left[{\mathbf{x}}_1,\dots {\mathbf{x}}_n\right],{\mathbf{x}}_i\in {\mathbb{R}}^p$ 的K-PCA包括以下步驟。

1. 找到一個合適的內(nèi)核函數(shù) $\kappa (?)$ 并計算Gram-matrix

$$\mathbf{K}=?\begin{array}{cccc}\kappa \left({\mathbf{x}}_1,{\mathbf{x}}_1\right)& \kappa \left({\mathbf{x}}_1,{\mathbf{x}}_2\right)& \dots & \kappa \left({\mathbf{x}}_1,{\mathbf{x}}_n\right)\\ \kappa \left({\mathbf{x}}_2,{\mathbf{x}}_1\right)& \kappa \left({\mathbf{x}}_2,{\mathbf{x}}_2\right)& & \kappa \left({\mathbf{x}}_2,{\mathbf{x}}_n\right)\\ ?& ?& ?& ?\\ \kappa \left({\mathbf{x}}_n,{\mathbf{x}}_1\right)& \kappa \left({\mathbf{x}}_n,{\mathbf{x}}_2\right)& \dots & \kappa \left({\mathbf{x}}_n,{\mathbf{x}}_n\right)\end{array}?$$

2. 計算Gram-matrix $\tilde{\mathbf{K}}=\mathbf{H}\mathbf{K}\mathbf{H}$，其中$\mathbf{H}={\mathbf{I}}_n?\frac{1}{n}{1}_n{1}_n^{?}$是居中化的數(shù)據(jù)。

3. 計算特征值分解$\tilde{\mathbf{K}}=\mathbf{V}\mathbf{\Lambda }{\mathbf{V}}^{?}$。由于核函數(shù)的定義，矩陣$\mathbf{K}$是半正定的，因此$\mathbf{\Lambda }$的對角線項是非負的。因此，我們可以寫成 $\mathbf{\Lambda }={\mathbf{\Sigma }}^2=\mathrm{diag}\left({\sigma }_1^2,\dots ,{\sigma }_n^2\right)$.

4. 定義縮減矩陣 ${\mathbf{\Sigma }}_k=\mathrm{diag}\left({\sigma }_1,\dots ,{\sigma }_k\right)\in {\mathbb{R}}^{k\times k}$ 與${\mathbf{V}}_k\in {\mathbb{R}}^{n\times k}$.

5. 縮減后的訓(xùn)練數(shù)據(jù)由以下公式得出

$$\mathbf{S}={\mathbf{\Sigma }}_k{\mathbf{V}}_k^{?}\text{\hspace{1em}(7.11)}$$

6. 對于一個新的數(shù)據(jù)點$\mathbf{y}\in {\mathbb{R}}^p$ ，$k$核主成分的計算方法是

$${\mathbf{s}}_{\text{new?}}:={\mathbf{\Sigma }}_k^{?1}{\mathbf{V}}_k^{?}{\mathbf{k}}_{\text{cent?}}^{\text{new?}}\text{\hspace{1em}(7.12)}$$

其中

$$\begin{array}{rl}{\mathbf{k}}_{\text{cent?}}^{\text{new?}}& =\mathbf{H}\left({\mathbf{k}}^{\text{new?}}?\frac{1}{n}\mathbf{K}{1}_n\right)\\ \text{?where?}{\mathbf{k}}^{\text{new?}}& ={\left[\kappa \left({\mathbf{x}}_1,\mathbf{y}\right),\dots ,\kappa \left({\mathbf{x}}_n,\mathbf{y}\right)\right]}^{?}.\end{array}$$

總結(jié)

以上是生活随笔為你收集整理的机器学习与高维信息检索 - Note 7 - 核主成分分析（Kernel Principal Component Analysis，K-PCA）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。