Principle component analysis - 0

1. 一維資料的統計學

假設我們有 $n$ 筆資料, 每筆資料都是一個數字 (例如 $n$ 個學生的成績). 這 $n$ 筆資料我們設為 $x_1, \cdots, x_n$, 並且定義一個矩陣

$$ \tag{1} A = \begin{bmatrix} x_1 & \cdots & x_n \end{bmatrix}\in M_{1\times n}. $$

那這些資料的平均數為

$$ \tag{2} \mu = \frac{1}{n}(x_1+\cdots+x_n) = \frac{1}{n}\begin{bmatrix} 1 & \cdots & 1 \end{bmatrix}\begin{bmatrix} x_1\\ \vdots\\
x_n \end{bmatrix} = \frac{1}{n}\mathbb{1}^TA^T, $$

其中 $\mathbb{1}^T = [1, \cdots, 1]$ 是個全為 $1$ 的向量.

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

$$ \tag{3} \text{Var}(A) = \sigma^2 = \frac{1}{n}\sum^n_{k=1} (x_i - \mu)^2, $$

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

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

$$ \tag{4} H = I - \frac{1}{n}\mathbb{1}\mathbb{1}^T. $$

計算一下可以發現

$$ \tag{5} HA^T = (I - \frac{1}{n}\mathbb{1}\mathbb{1}^T)A^T = A^T - \mu\mathbb{1} = \begin{bmatrix} x_1 -\mu\\
\vdots\\
x_n -\mu \end{bmatrix} = Y^T, $$

其中我們將這些置中後的資料存為 $Y$ 矩陣. 接著我們就可以知道

$$ \tag{6} \sigma^2 = \frac{1}{n}YY^T. $$

2. 二維資料的統計學

假設我們有 $n$ 筆資料, 每筆資料都是 $2$ 個數字 (例如 $n$ 個學生在 $2$ 次考試的成績), 這兩個數字我們稱之為這筆資料的 features. 這 $n$ 筆資料我們設為 $(x_1, y_1), \cdots, (x_n, y_n)$, 並且定義一個矩陣

$$ \tag{7} A = \begin{bmatrix} x_1 & \cdots & x_n\\
y_1 & \cdots & y_n \end{bmatrix}\in M_{2\times n}. $$

我們把每種資料都平移, 使其平均為 $0$, 並令平移後的資料為 $Y$. 簡單計算可以發現我們一樣可以用置中矩陣來做, $HA^T = Y^T$,

$$ \tag{8} Y^T = \begin{bmatrix} x_1 -\mu_x & y_1 -\mu_y\\ \vdots & \vdots\\
x_n -\mu_x & y_n -\mu_y \end{bmatrix}, \quad \mu_x = \frac{1}{n}\sum^n_{k=1} x_k, \quad \mu_y = \frac{1}{n}\sum^n_{k=1} y_k. $$

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

$$ \tag{9} \text{cov}(x, y) = \frac{1}{n}\sum^n_{k=1}(x_k - \mu_x)(y_k-\mu_y). $$

接著計算一下就可以發現

$$ \tag{10} \frac{1}{n}YY^T = \begin{bmatrix} \text{cov}(x,x) & \text{cov}(x,y)\\ \text{cov}(x,y) & \text{cov}(y,y) \end{bmatrix}, $$

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

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

3. PCA: maximize variance

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

假設這個方向為 $v\in\mathbb{R}^2$, 並且 $\|v\|=1$, 那資料投影到 $v$ 所得的新資料就是 $v^TY \in M_{1\times n}$. 接著我們就來算這筆新資料的變異數.

第一步一樣先置中. 也就是計算 $HY^Tv$. 不過由於 $Y$ 是置中過的資料, 因此 $HY^T = Y^T$, 所以 $HY^Tv = Y^Tv$, 也就是說, 新資料 $v^TY$ 的平均一定是 $0$.

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

$$ \tag{11} \sigma^2 =\frac{1}{n}(v^TY)(v^TY)^T =\frac{1}{n}v^TYY^Tv. $$

所以統整一下, 若我們將資料投影到 $v$ 上, 那新資料的變異數就是 (11). 而PCA 所要找的方向就是使變異數最大的方向, 也就是

$$ \tag{12} \hat{v} = \arg\max_{v\in\mathbb{R}^2, \|v\|=1} \left(v^TYY^Tv\right). $$

最後, 我們知道這個解可以由 $Y^T$ 這個矩陣的 SVD 得出.

假設 $Y^T = U\Sigma V^T$, 那 $\hat{v} = v_1$, 也就是第一個 singular vector.

4. PCA: minimize square distance

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

假設這個方向為 $v\in\mathbb{R}^2$, 並且 $\|v\|=1$, 那資料投影到 $v$ 的投影點就是 $vv^TY \in M_{2\times n}$. 接著我們就來算新舊資料的距離平方和:

$$ \tag{13} \begin{align} \sum^n_{k=1} d_k^2 &= \sum^n_{k=1}\|Y_k - vv^TY_k\|^2 \\
&= \sum^n_{k=1}<Y_k-vv^TY_k, Y_k-vv^TY_k> \\
&= \sum^n_{k=1}Y_k^TY_k -Y_k^Tvv^TY_k \\
&= \sum^n_{k=1}Y_k^TY_k -v^TY_kY_k^Tv \\
&= \sum^n_{k=1}(Y_k^TY_k) -v^TYY^Tv, \end{align} $$

其中我們用到了 $v^TY_k$ 是個數字以及 $\sum Y_kY_k^T = YY^T$ 這兩件事.

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

$$ \tag{14} \hat{v}=\arg\min_{v\in\mathbb{R}^2, \|v\|=1} \left(\sum^n_{k=1}(Y_k^TY_k) -v^TYY^Tv\right) = \arg\max_{v\in\mathbb{R}^2, \|v\|=1} \left(v^TYY^Tv\right). $$

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

5. Conclusion

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

     而這兩件事情是等價的.

2. PCA 也是一種資料降維的工具, 而將資料投影到一維所出來的新資料就是 $v^TY$.
3. 以上雖然是以二維資料為例, 不過若有 $m$ 維資料整個推導是一樣的.
4. 以上是以投影到一維為例, 若投影到更高維度就是依序找第二, 三, 等等的 singular vectors. 不過推導會利用到矩陣 trace 的一些性質, 一些細節這裡就先跳過.
5. PCA 要找的是個仿射子空間, $V = \mu + \text{span}\{v\}$, 這裏我們都直接說 $\mu$ 就是資料的平均. 不過其實這是可以算出來的. 假設我們想要找一個點 $\mu$ 使得所有資料到這個點的距離和為最小, 也就是 $$ \tag{15} \mu = \arg\min \sum^n_{k=1}(x_k - \mu)^2. $$ 我們先定義 $f(\mu) = \sum^n_{k=1}(x_k - \mu)^2$. 這是個單變數函數, 而且其實就是個 $\mu$ 的二次多項式, 首項係數等於 $1$, 有一個最小值. 接著微分求極值得到 $$ \tag{16} \frac{d}{d\mu} f = \sum^n_{k=1}(-2)(x_k - \mu) = (-2)\left[\sum^n_{k=1}x_k - n\mu\right] $$ 因此極值發生在 $\frac{d}{d\mu} f=0$, 也就是 $$ \tag{17} \mu = \frac{1}{n}\sum^n_{k=1}x_k. $$ 所以到所有資料點距離和最小的就是平均數.