主成分分析

1. 一維資料的統計學

假設我們有

$n$ 筆資料, 每筆資料都是一個數字 (例如

$n$ 個學生的成績). 這

$n$ 筆資料我們設為

$x_1,\cdots ,x_n$, 並且定義一個矩陣

$$\begin{array}{}\text{(1)}& A=\left[\begin{array}{ccc}{x}_1& \cdots & x_n\end{array}\right]\in M_{1\times n}.\end{array}$$

那這些資料的平均數為

$$\begin{array}{}\text{(2)}& \mu =\frac{1}{n}(x_1+\cdots +x_n)=\frac{1}{n}\left[\begin{array}{ccc}1& \cdots & 1\end{array}\right]\left[\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right]=\frac{1}{n}{\mathbb{1}}^T{A}^T,\end{array}$$

其中

${\mathbb{1}}^T=[1,\cdots ,1]$ 是個全為

$1$ 的向量.

資料的變異數 (variance) 則定義為

$$\begin{array}{}\text{(3)}& \text{Var}(A)={\sigma }^2=\frac{1}{n}\sum _{k=1}^n(x_i-\mu {)}^2,\end{array}$$

而

$\sigma$ 則是標準差 (standard deviation, std).

要將之寫成矩陣形式首先我們定義置中矩陣 (centering matrix)

$$\begin{array}{}\text{(4)}& H=I-\frac{1}{n}\mathbb{1}{\mathbb{1}}^T.\end{array}$$

計算一下可以發現

$$\begin{array}{}\text{(5)}& H{A}^T=(I-\frac{1}{n}\mathbb{1}{\mathbb{1}}^T)A^T=A^T-\mu \mathbb{1}=\left[\begin{array}{c}{x}_1-\mu \\ ⋮\\ x_n-\mu \end{array}\right]=Y^T,\end{array}$$

其中我們將這些置中後的資料存為

$Y$ 矩陣. 接著我們就可以知道

$$\begin{array}{}\text{(6)}& {\sigma }^2=\frac{1}{n}Y{Y}^T.\end{array}$$

2. 二維資料的統計學

假設我們有

$n$ 筆資料, 每筆資料都是

$2$ 個數字 (例如

$n$ 個學生在

$2$ 次考試的成績), 這兩個數字我們稱之為這筆資料的 features. 這

$n$ 筆資料我們設為

$(x_1,y_1),\cdots ,(x_n,y_n)$, 並且定義一個矩陣

$$\begin{array}{}\text{(7)}& A=\left[\begin{array}{ccc}{x}_1& \cdots & x_n\\ y_1& \cdots & y_n\end{array}\right]\in M_{2\times n}.\end{array}$$

我們把每種資料都平移, 使其平均為

$0$, 並令平移後的資料為

$Y$. 簡單計算可以發現我們一樣可以用置中矩陣來做,

$H{A}^T=Y^T$,

$$\begin{array}{}\text{(8)}& Y^T=\left[\begin{array}{cc}{x}_1-{\mu }_x& y_1-{\mu }_y\\ ⋮& ⋮\\ x_n-{\mu }_x& y_n-{\mu }_y\end{array}\right],{\mu }_x=\frac{1}{n}\sum _{k=1}^n{x}_k,{\mu }_y=\frac{1}{n}\sum _{k=1}^n{y}_k.\end{array}$$

接著我們可以定義兩個變數的共變異數 (covariance),

$$\begin{array}{}\text{(9)}& \text{cov}(x,y)=\frac{1}{n}\sum _{k=1}^n(x_k-{\mu }_x)(y_k-{\mu }_y).\end{array}$$

接著計算一下就可以發現

$$\begin{array}{}\text{(10)}& \frac{1}{n}Y{Y}^T=\left[\begin{array}{cc}\text{cov}(x,x)& \text{cov}(x,y)\\ \text{cov}(x,y)& \text{cov}(y,y)\end{array}\right],\end{array}$$

也就是所謂的共變異數矩陣. 這個矩陣的對角線元素代表每個 feature 自己的變異數, 而非對角線則是共變異數, 代表兩個 features 的相關程度.

Remark: 不過要真正算相關程度會更近一步的去計算相關係數 (correlation coefficients), 這邊就不再深入探討.

3. PCA: maximize variance

我們想要找到一個方向, 使得資料投影上去之後, 新資料的變異數會最大.

假設這個方向為

$v\in {\mathbb{R}}^2$, 並且

$\Vert v\Vert =1$, 那資料投影到

$v$ 所得的新資料就是

$v^{T}Y\in M_{1\times n}$. 接著我們就來算這筆新資料的變異數.

第一步一樣先置中. 也就是計算

$H{Y}^{T}v$. 不過由於

$Y$ 是置中過的資料, 因此

$H{Y}^T=Y^T$, 所以

$H{Y}^{T}v=Y^{T}v$, 也就是說, 新資料

$v^{T}Y$ 的平均一定是

$0$.

接著, 新資料的變異數就會是

$$\begin{array}{}\text{(11)}& {\sigma }^2=\frac{1}{n}(v^{T}Y)(v^{T}Y{)}^T=\frac{1}{n}{v}^{T}Y{Y}^{T}v.\end{array}$$

所以統整一下, 若我們將資料投影到

$v$ 上, 那新資料的變異數就是 (11). 而PCA 所要找的方向就是使變異數最大的方向, 也就是

$$\begin{array}{}\text{(12)}& \hat{v}=\arg \underset{v\in {\mathbb{R}}^2,\Vert v\Vert =1}{max}\left(v^{T}Y{Y}^{T}v\right).\end{array}$$

最後, 我們知道這個解可以由

$Y^T$ 這個矩陣的 SVD 得出.

假設

$Y^T=U\mathrm{\Sigma }{V}^T$, 那

$\hat{v}=v_1$, 也就是第一個 singular vector.

4. PCA: minimize square distance

我們想要找到一個方向, 使得資料投影上去之後, 新舊資料的距離平方和最小.

假設這個方向為

$v\in {\mathbb{R}}^2$, 並且

$\Vert v\Vert =1$, 那資料投影到

$v$ 的投影點就是

$v{v}^{T}Y\in M_{2\times n}$. 接著我們就來算新舊資料的距離平方和:

$$\begin{array}{}\text{(13)}& \begin{array}{rl}\sum _{k=1}^n{d}_k^2& =\sum _{k=1}^n\Vert Y_k-v{v}^T{Y}_k{\Vert }^2\\ & =\sum _{k=1}^n<Y_k-v{v}^T{Y}_k,Y_k-v{v}^T{Y}_k>\\ & =\sum _{k=1}^n{Y}_k^T{Y}_k-Y_k^{T}v{v}^T{Y}_k\\ & =\sum _{k=1}^n{Y}_k^T{Y}_k-v^T{Y}_k{Y}_k^{T}v\\ & =\sum _{k=1}^n(Y_k^T{Y}_k)-v^{T}Y{Y}^{T}v,\end{array}\end{array}$$

其中我們用到了

$v^T{Y}_k$ 是個數字以及

$\sum Y_k{Y}_k^T=Y{Y}^T$ 這兩件事.

我們希望找到一個方向使得距離平方和最小, 也就是

$$\begin{array}{}\text{(14)}& \hat{v}=\arg \underset{v\in {\mathbb{R}}^2,\Vert v\Vert =1}{min}(\sum _{k=1}^n(Y_k^T{Y}_k)-v^{T}Y{Y}^{T}v)=\arg \underset{v\in {\mathbb{R}}^2,\Vert v\Vert =1}{max}\left(v^{T}Y{Y}^{T}v\right).\end{array}$$

觀察 (12) 與 (14) 發現他們一模一樣. 也就是這兩個問題的解會是一樣的, 最佳的方向都是第一個 singular vector.

5. Conclusion

1. PCA 想做的事就是找到一個仿射子空間 (affine subspace), 使得
   a) 投影下去之後的資料有最大的變異數
   b) 投影前後的資料距離平方合最小.
   而這兩件事情是等價的.

2. PCA 也是一種資料降維的工具, 而將資料投影到一維所出來的新資料就是

   $v^{T}Y$.

3. 以上雖然是以二維資料為例, 不過若有

   $m$ 維資料整個推導是一樣的.

4. 以上是以投影到一維為例, 若投影到更高維度就是依序找第二, 三, 等等的 singular vectors. 不過推導會利用到矩陣 trace 的一些性質, 一些細節這裡就先跳過.

5. PCA 要找的是個仿射子空間,

   $V=\mu +\text{span}\{v\}$, 這裏我們都直接說
   $\mu$ 就是資料的平均. 不過其實這是可以算出來的. 假設我們想要找一個點
   $\mu$ 使得所有資料到這個點的距離和為最小, 也就是
   
   $$\begin{array}{}\text{(15)}& \mu =\arg min\sum _{k=1}^n(x_k-\mu {)}^2.\end{array}$$

   我們先定義

   $f(\mu )=\sum _{k=1}^n(x_k-\mu {)}^2$. 這是個單變數函數, 而且其實就是個
   $\mu$ 的二次多項式, 首項係數等於
   $1$, 有一個最小值. 接著微分求極值得到
   
   $$\begin{array}{}\text{(16)}& \frac{d}{d\mu }f=\sum _{k=1}^n(-2)(x_k-\mu )=(-2)[\sum _{k=1}^n{x}_k-n\mu ]\end{array}$$

   因此極值發生在

   $\frac{d}{d\mu }f=0$, 也就是

$$\begin{array}{}\text{(17)}& \mu =\frac{1}{n}\sum _{k=1}^n{x}_k.\end{array}$$