# 6.3 Principal Component Analysis

我們在 $6.1$ 的 Introduction 中有提到，feature extraction 有兩種常用的 method：

1. Principal Component Analysis (PCA)
2. linear discriminant analysis

兩者都是利用 linear projection。在像這樣的 projection methods 中，我們想要做的是：

:::info
找到一個 mapping，在喪失的資訊最小化的情況下，將原本在 $d$-dimensional space 中的 original inputs，map 到另一個小於 $d$ 的 $k$-dimensional space。
:::

為什麼我們能這麼做，是因為 high-dimensional data 本身具備的特性——很多時候許多 dimensions 是多餘的，因此可以用其他 dimensions 的組合來解釋；並且 high-dimensional data 的 dimensions 之間通常也存在著 correlation，所以實際上 data 真正的結構維度是比較低的。

講起來或許有點抽象，我們可以先看個圖例：

> 假設我們的空間是三維的（圖中的六個長方體），三個軸為 $x,y,z$，每個圖中的藍色點為 data points。
>
> 在上半部分的三個圖中，我們可以大概看出它們各自之中的點都是 uniformly distributed。在這樣的情況下，既然 $x,y,z$ 之間並沒有 correlation，我們就沒辦法在保留這些點的資訊的同時，把維度再減少。
>
> 但是在下方的三個圖中，我們可以看到 data points 大致都呈現在某個平面上的分佈。在這樣的情況下，其實我們可以用兩個 variables 表示這些點就好，也就是說這些點的 intrinsic dimension 其實是一個二維平面而非三維空間。
>
> 不過，在保留兩個維度時，很多時候並不是直接取 $x,y$、刪掉 $z$ 這麼簡單的事情。比如說左下角的圖中，如果我們直接把每個點的座標從 $(x,y,z)$ 變成 $(x,y)$，就失去了那個右高左低的分佈資訊。
>
> 所以 PCA 大概的想法是，我們就在盡可能保留資訊的情況下，想辦法組合原本的座標軸，來形成少條一點的新的座標軸。

首先，我們考慮簡單一點的情況：假設我們要 project onto 一個 one-dimensional space（$k=1$），我們可以用一個具有和原本 input 相同 dimension 的 $d$-dimensional vector $\vec{w}$，來定義這個 space 的方向。
> 也就是說，我們要把原本在 $\mathbb{R}^d$ 中的 data points，投影到 $span\{\vec{w}\}$。
>> 因為 $\dim(span\{\vec{w}\})=1$，所以即使 $\vec{w} \in \mathbb{R}^d$，它所生成的空間仍是一維的。

為了要使 solution unique，並且因為我們只關心由 $\vec{w}$ 所定義出來的方向，而不是 $\vec{w}$ 本身的大小，我們限制 ++$\vec{w}$++ 為 unit vector，也就是：

\begin{equation}
||\vec{w}|| = \vec{w}^T\vec{w} = 1
\end{equation}

這樣一來，input $\vec{x}$ 在 $\vec{w}$ 方向上的投影為一個 scalar value $z$：

:::success
\begin{equation}
z = \vec{w}^T\vec{x}
\end{equation}
:::
> 原本我們平常說投影是指一個向量，但是我們現在只想取以 $\vec{w}$ 作為新的座標軸，data 投影下去的座標值。
>
> $\rightarrow$ 至於為什麼會這樣定義，如果真的很想知道，可以先跳著看後面的小節「意義」中的「scalar value」部分。

## 定義

回到我們這節的主題，<font color = "snake">Principal Component Analysis (PCA)</font> 是一種 ++unsupervised++ 的 method，因為在 PCA 裡我們並不會用到 output information，而是像上面說的，我們要對 inputs 做 projection。
> 用到 output information 的 supervised learning 就像前面幾個小節一樣，像是在 classification 裡面，我們想辦法構造出一個 classifier（某個 linear discriminant），用實際的 output 來檢查預測的 output 正確率有多少。

可是這樣的投影有很多種可能，因此，要如何決定投影到哪？怎樣投？
回歸到我們的目標去想，我們要選擇的方式就是要能夠：

:::warning
maximize（投影結果的）variance。
:::

但是為什麼要 maximize variance 呢？

當我們面對的是一個包含許多 correlated variables 的 dataset，我們希望能夠透過一些具代表性的 variables，共同去解釋原本這個 dataset 之中的變化；也就是說，我們想用比較少的 variables，把原本 data 會怎樣變動的情形給保留下來。

而作法就是去找出那些 linear correlated variables，用它們的 ++linear combination++ 形成新的 variable，稱作 <font color = "snake">principal component</font> 來取代。
> 比較詳細的簡單解釋可以參考筆記「[5.4 Multivariate Normal Distribution](https://hackmd.io/@pipibear/ByBQVbqKR)」中的「Projection」小節。

也就是說，假如我們今天取來讓 inputs $\vec{x}$ 投影在上面的第一個軸（我們總共要找 $k$ 個，來形成 $k$ 維的 reduced space），用向量 ==$\vec{w_1}$== 來定義，那麼：

:::info
$\vec{w_1}$ 為 principal component，這個 $\vec{w_1}$ 要是能夠使得當我們將 sample points 投影在它之上以後，投影出來的點是最分散的，進而讓 sample points 間的距離變得最明顯。
:::
> 我用中文講的還是不夠清楚，原文如下：
>> "The principal component is $\vec{w_1}$ such that the sample, after projection on to $\vec{w_1}$, is most spread out so that the difference between the sample points becomes most apparent."

上面是我主要用的課本（Ethem Alpaydin 的 *Introduction to Machine Learning*）裡給出的定義，不過我覺得並沒有很清楚，所以下方我再列出 Bishop 的課本中給出的兩種定義（這兩種定義是等價的），原文如下：

PCA can be defined as

:::info
the orthogonal projection of the data onto a lower dimensional space, known as the <font color = "blue">principal subspace</font>, such that the variance of the projected data is maximized.
:::

Equivalently, it can be defined as

:::info
the linear projection that minimizes the average projection cost, defined as the mean squared distance between the data points and their projections.
:::

第二種定義是什麼意思，我們可以看下方這張圖：

> 假設我們的 data points 為圖中的四個紅點 $x_n$，我們想找出的 unit vector（圖中以 $u_1$ 表示）為能夠使得四個 $x_n$ 和它們各自的投影 $\tilde{x}_n$ 之間的距離（即藍色的線段），平方後加總再除四取平均為最小，簡化一點的說就是 average squared distance，而這個值也叫做 projection cost。

不過這裡有一個問題是，從剛剛到現在的討論，我們都很自然而然的取正交投影，像是第一個定義裡我們開頭就說了 orthogonal projection，我們的 $z = \vec{w}^T\vec{x}$ 也是從正交投影公式來的，可是為什麼是正交投影？為什麼我們不取斜投影？

第一種定義強調我們要找的 principal components 要能使 variance 最大化，著重在要怎麼選擇 $\vec{w}$ 來定義方向；但是第二種定義是希望我們能最大程度地還原原本的點，因此最好投影點跟原本的點離越近越好，那很直觀地，當然我們就知道取垂直距離會是最近的了！

看個簡單的圖例：

> 當我們要投影 data point $\vec{x}$ 到 $span\{\vec{b}\}$ 上時，每一條紅色的線連到 $\vec{b}$ 上其實都是一種可能的投影。如果要從這些紅色的線當中挑出最短的一條，就會是我畫的紫色的和 $\vec{b}$ 垂直的那條。

## 作法：求 principal component

### first principal component

講到這裡，我們已經知道目標是要去找出一個 unit vector $\vec{w_1}$，使得 $Var(\vec{w_1}^T\vec{x})$ maximized。那麼現在的問題首先會是：

要如何計算 $Var(\vec{w_1}^T\vec{x})$？

其實在筆記「[5.4 Multivariate Normal Distribution](https://hackmd.io/@pipibear/ByBQVbqKR)」中的「Projection」小節，我們就證明過這個 variance 怎麼算，說明如下圖：


因此，我們發現我們的目標轉換成要找到長度為一的 $\vec{w_1}$，使得 $\vec{w_1}^T\Sigma\vec{w_1}$ 越大越好。

這要怎麼解呢？

$\rightarrow$ 利用微積分中的 Lagrange multiplier，詳細過程如下圖：


最後當我們在求 stationary point 時，我們發現結果居然長得像 eigenvalue (eigenvector) 的定義一樣！並且，當我們把這個結果代回去原本要求的 $\max \vec{w_1}^T\Sigma\vec{w_1}$ 之後，我們發現要求的最大值變成了 $\lambda_1$ ！

這樣的結果意思是：

:::warning
我們要找的 principal component $\vec{w_1}$，其實就是 covariance matrix $\Sigma$ 最大的 eigenvalue 對應的 eigenvector。
:::

### 其餘 principal component

到目前為止，我們只找到了第一條新的軸，但是我們的目的是將原本的 $d$ 維降到 $k$ 維，因此我們要用類似的方式去找剩下的 $k-1$ 條座標軸。

剩下的每一個 principal component，一樣在挑選上目標都是去 maximize projected variance；除此之外，每次在形成新的 principal component 時，都要 ++orthogonal++ to 已經挑好的。

最終：

:::warning
讓投影後的 data variance 最大化的 optimal linear projection 就會由 $k$ 個 eigenvectors：

\begin{equation}
\vec{w}_1, \vec{w}_2, ..., \vec{w}_k
\end{equation}

所定義，而這些 $\vec{w}_1, ..., \vec{w}_k$ 為 covariance matrix $\Sigma$ 最大的 $k$ 個 eigenvalues 所對應的 eigenvectors。
:::

---

我們實際來求第二個 principal component 看看。不過首先我們現在的條件限制變成了兩個了：

1. 長度為一
2. 和 $\vec{w}_1$ 垂直

我們先來複習一下如果有兩個條件限制的時候，Lagrange multiplier 要怎麼用：


用幾何的方式來解釋：


有了這些工具，我們就可以實際來求 second principal component 了，和前面差不多的作法：


解完後我們發現要找的 $\vec{w}_2$ 為 $\Sigma$ 的 eigenvalue $\alpha$ 對應的 eigenvector，所以 second principal component $\vec{w}_2$ 即為第二大的 eigenvalue 對應的 eigenvector。

因為 $\Sigma$ symmetric（$\because$ covariance matrix 的第 $ij$ 項等於 $ji$ 項，為 $x_i,x_j$ 的 covariance），所以根據定理，相異的 eigenvalues 對應的 eigenvectors orthogonal，定理證明如下：


但是對稱矩陣的性質不止如此，Spectral theorem 告訴我們，對一個 $n\times n$ 的矩陣，不管它是否有 $n$ 個相異的 eigenvalues，也沒有任何其他的條件，只要對稱，我們都可以找到一組 orthonormal basis。

意思也就是，我們可以用和上方同樣的作法，一路做下去，直到找到 $k$ 個 principal component。

> Spectral theorem 的意思是，只要我們的矩陣是對稱矩陣（這裡我們的 $\Sigma$ 確實是），那我們就一定能找到一組 basis，這個 basis 裡的向量為 $\Sigma$ 的 eigenvalues 對應的 eigenvectors，且它們 orthonormal（彼此互相垂直，長度皆為 $1$）

## 意義

### scalar value

由上面的內容，我們知道作為對稱矩陣的 covariance matrix 也可以寫成下圖中的形式：


以我們原本的符號表示，意義也就是：

:::warning
covariance matrix $\Sigma$ 可以寫成 $d$ 個 one-dimensional projections 的組合。

$\rightarrow$ 每個 $\vec{w}_i\vec{w}_i^T$ 都是一個 $rank=1$ 的投影矩陣。
:::
> 這件事情對++所有的++對稱矩陣都成立，因此即使 $\Sigma$ 有重複的 eigenvalues，我們還是可以找到 $d$ 個 orthonormal eigenvectors。

但是：

:::danger
為什麼 $\vec{w}_i\vec{w}_i^T$ 會是投影到 $\vec{w}_i$ 的投影矩陣呢？
:::

我們可以先回過來想，一開始我們說如果要把一個 data point $\vec{x}$ 投影到 $i$th principal component $\vec{w}_i$ 上，那我們會取 scalar value $\vec{w}_i^T\vec{x}$，可是這是什麼意思、怎麼來的？

我們可以看下圖的說明：

> 沿用圖中的符號，假設這裡的 $\vec{a}$ 是我們找到的其中一個 principal component，那麼，因為每個 data point 投影到 $\vec{a}$ 上都是 $\vec{a}$ 乘上某個倍數 $\hat{x}$，那我們就用這個倍數，也就是++投影到由 $\vec{a}$ 所生成的一維空間的座標++，來表示原來的 data point 在這個 principal component 的值。

### 投影矩陣

知道 scalar value $\vec{w}^T\vec{x}$ 怎麼來的以後，我們就會想問：

既然我們能夠求出 $\vec{b}$ 在 $\vec{a}$ 上的正交投影 $\vec{p}$，那應該要有個正交投影矩陣吧！那這個正交投影矩陣會是什麼呢？
> $\rightarrow$ 也就是說，我們要對原本的 input vector $\vec{b}$ 乘上什麼樣的矩陣（以 $P$ 表示），才會得到 $\vec{b}$ 在 $\vec{a}$ 上的正交投影？

我們可以從 $\vec{p}$ 是怎麼來的的式子找到 $P$：



### PCA 的概念

在上面這些都理解以後，我們就可以回過來看整個 PCA 的概念：

我們知道，根據 covaraince matrix 的定義，$\Sigma$ 一定是正半定矩陣，也就是說：

\begin{equation}
\vec{x}^T\Sigma\vec{x} \ge 0 \qquad \forall \vec{x} \in \mathbb{R}^d
\end{equation}

根據正半定矩陣的定義，$\Sigma$ 所有的 eigenvalue 都 $\ge0$；可是我們不能保證 $\Sigma$ 一定是正定矩陣，也就是說，有可能 $\Sigma$ 具 eigenvalue 為零。

我們來看看有 eigenvalue 為零的情況會是怎麼回事（假設我們有將 eigenvalues 由大排到小，即 $\lambda_1 \ge \lambda_2\ge ...$）：


有兩個定理可以告訴我們，在上圖中的情況下 $\Sigma$ 不可逆：

:::success
1. 對稱矩陣的 $rank$ 為它的非零 eigenvalue 個數。
2. 對稱矩陣的 $\det$ 為它的 eigenvalue 乘積。
:::
> $\Sigma$ 的 $rank$ 為某個 $k$ 且 $k<d$，且 eigenvalue 中有零，所以 $\det$ 為零。

回想一個矩陣什麼時候不可逆，就是當 linearly dependent 時，也就是說有某些行（列）可以寫成其他行（列）的線性組合；在 covariance matrix 的情形中，就代表 input 的某個或某些 features 可以寫成其他 features 的線性組合。

因此回到最初的目的，我們想要去除這些多餘的 features，因此作法是：

首先我們透過 spectral decomposition 將原本的空間 $\mathbb{R}^d$ 的 basis，比如說可能是一般歐式空間的 standard basis：

\begin{equation}
\{ \vec{x}_1 = [\,1\ 0\cdots0]\,^T, \ \vec{x}_2 = [\,0\ 1 \ 0\cdots0]\,^T\,...... , \ \vec{x}_d = [\,0\cdots0 \ 1]^T \}
\end{equation}

轉換成一組由 eigenvector 組成的 orthonormal basis：

\begin{equation}
\{\vec{w}_1,...,\vec{w}_d\}
\end{equation}

接著，既然 $\lambda_{k+1},...,\lambda_d = 0$，代表新的軸裡面，這些 eigenvalue 對應的那些軸對解釋 data 的分佈並沒有意義，於是我們取前面的 $k$ 個對應到非零 eigenvalues 的 eigenvectors 為 reduced space 的 dimensions。
> 當然也不一定是所有非零 eigenvalues 對應的 eigenvectors 都一定要作為 principal component，我們可以視需要看要取前幾大的 eigenvalues 對應的 eigenvectors 都行。
>
> Recall：$\lambda_i$ 為 data points 投影在 $\vec{w}_i$ 上的 variance，所以我們可以透過要保留多大的 variance 來決定要留多少個 principal component。當然也可以一開始就基於各種原因決定要把 dimension 降到多少。

$\rightarrow$ 第一個 eigenvector（對應最大 eigenvalue 的那個，也就是 first principal component）$\vec{w}_1$，作為新的軸，說明的意義是 variance 最大的那部分，同理 second principal component 說明 variance 第二大的部分⋯⋯。

## 用矩陣表示 principal components

上面我們已經說明我們可以，並且如何可以找到 $k$-dimensional reduced space 的 orthonormal basis，我們也說明了 $\vec{x}$ 在每個 principal component 投影的 scalar value 為 $\vec{w}_i^T\vec{x}$。

那麼接著我們就來將這 $k$ 個 principal component 寫成一個矩陣 $W$，來同時對 $\vec{x}$ 作用，就能同時計算 $z_1,...,z_k$：



真正展開後的結果告訴我們 $\vec{z}$ 的各個 element 確實是 $\vec{x}$ 投影在對應的 principal component 的結果。

看一個二維的圖例：

> 這裡如果 $\vec{z}_2$ 方向上的 variance 太小，那我們也可以捨棄它，取一個 principal component，即把 data points 都投影到 $\vec{z}_1$ 就好。

### 求對角矩陣

有了這個矩陣 $W$ 以後，我們也可以反過來看要如何求出 spectral decomposition 裡的那個由 eigenvalues 組成的對角矩陣：


## 例子

假設我們要對一個班級的學生用成績去排名，考試的科目總共有五科。

由於名次是一個值，那麼意思也就是說我們要將 input vector，也就是原本每個學生的五科成績：

\begin{equation}
\vec{x}^t = [\,x^t_1 \ x^t_2\ x^t_3\ x^t_4\ x^t_5]^T\,
\end{equation}
> $t$ 為第 $t$ 位學生，$x^t_i \quad i=1,...,5$ 為他的第 $i$ 科成績。

++投影到一個一維空間++，使得這些學生成績的 data variance 最大。

我們一樣可以用前面 PCA 這樣的做法，比起直接取這五科成績的平均，可能會有更好的效果，因為我們把各科的 correlations 和各科 variance 的差距都考慮進去了。

## 決定 reduced space 的 dimension k
### proportion of variance

在實務中：

:::warning
即使所有的 eigenvalues 都 $>0$，仍然可能的是有些 eigenvalues 對 variance 的影響很小，所以可以被捨棄。
:::
> Recall： covariance matrix $\Sigma$ 的 $\det$ 為 eigenvalue 相乘，也就是 $\det(\Sigma) = \prod_{i=1}^d \lambda_i$，所以如果有某個 $\lambda_j$ 很小，即使它大於零，仍然會使得 $\det(\Sigma)$ 的值很小。
>> covariance matrix 的 determinant 代表的意義是 ++variables 之間的變化量++，因此如果這個值很小，代表我們留下來的 principal components 仍有一些 dimensions 是 data 投影在那個方向變化量不大的。

因此，假設我們的 $d$ 個 eigenvalues 按大到小的順序排列，前 $k$ 個對應到我們的 principal components，那麼這 $k$ 個 principal components 可以代表的 variance 為：

:::info
\begin{equation}
\sum_{i=1}^k \lambda_i \qquad \text{where } \ \lambda_i: k \ \text{個 } \Sigma \ \text{最大的 eigenvalues}
\end{equation}
:::

我們說這 $k$ 個 principal components 能夠說明的 <font color = "snake">proportion of variance</font> 為：

:::info
\begin{equation}
\frac{\lambda_1 + \lambda_2 + ... + \lambda_k}{\lambda_1 + \lambda_2 + ... + \lambda_k + ... +\lambda_d}
\end{equation}
:::

並且我們能得到結論：

:::warning
如果 dimensions 為 highly correlated，那就只會有很少的 eigenvectors 具有很大的 eigenvalues，且 $k<<d$，也就是說我們可以得到一個很大的 reduction in dimensionality。
:::

這種例子同常發生在 <font color = "green">image / speech processing</font>，因為在（空間或時間上）附近的 inputs 為 highly correlated。
> 可以簡單想像在一張照片裡，在附近的 pixels 通常會有差不多的 RGB values。

$\rightarrow$ 但是如果 dimensions 之間沒什麼關聯，那就像我們最一開始的圖例一樣，我們很難再去降低維度，減少後的 dimension $k$ 和原本的 dimension $d$ 差不多大，我們就不太能透過 PCA 來得到什麼幫助。

### scree graph

知道不見得 eigenvalue $>0$ 我們就要取它對應的 eigenvector 作為 principal component 以後，我們又想再問：

:::danger
有沒有什麼方法可以幫助我們判斷要把 dimension 下降到多少呢？（即要取 $k$ 等於多少？）
:::

其中一種方法是我們透過一種叫做 <font color = "snake">scree graph</font> 的圖，畫一個用「留下的 eigenvectors 數」作為 input、「variance」作為 output 的 function。

例子如下圖：

> 在這個例子裡，原本我們的 input 的 dimension $=64$
> - 上圖是 scree graph，我們假設 eigenvector 以對應的 eigenvalue 由大排到小，例如最左上角的那個十字代表最大的 eigenvalue（接近 $180$ 左右）和它對應的 eigenvector 排序（第一個），我們可以看到大約到第三四十個 eigenvector，對應的 eigenvalue 已經快降到零了，這樣的 eigenvectors 就是即使它大於零，我們也可能選擇捨棄的那些。
> - 下圖的橫軸一樣是 eigenvector 的個數，每個十字也是照對應 eigenvalue 大小排序的 eigenvector；縱軸是 proportional of variance，例如綠色標記處表示當我們留下前 $20$ 大的 eigenvalues 對應的 eigenvectors 作為 principal components，這些 eigenvectors 就足以表示原本的 data 九成的 variance。

### 取大於平均 input variance 的

另一種決定 reduced dimension 的方式為：

:::info
捨棄那些對應的 eigenvalue $<$ ++平均 input variance++ 的 eigenvectors。
:::

說明見下圖：

> 在上文的內容中，我都直接用 $\Sigma$ 作為 covariance matrix，但是就像我們前幾節中在討論的，這個 $\Sigma$ 指的是整個 underlying distribution 的 covariance matrix，因此它的 entries 到底是哪些值我們無法知道（因為我們只能取 sample，也就是從這個背後的 distribution 中取出某些樣本）
>
> 透過取出的 sample，我們假定我們取樣取的夠好，足以代表背後的 distribution，因此我們用 sample 裡的 data points 的值，來估計 $\Sigma$ 的 entries。
>
> 剩下的步驟就都和原本我們前面對 $\Sigma$ 做的相同。

根據線性代數學過的性質，我們就能得到 「sample variance 的平均」會等同於「eigenvalue 的平均」，這樣的結果：


## 問題與解決方法
### 標準化 mean, variance

假如原本的各個 dimension $x_i$ 的 variance 很大，那麼 principal components 的方向就會更受 variance 影響，而不是 correlations，然而我們不希望這樣的事發生。

:::danger
Q：為什麼我們不希望 principal components 的方向太受 high variance variables 影響？
:::
我們可以想像一個情況，在 $d$ 個 variables 裡面，有一個 $x_j$ 的 variance 特別大，代表我們的 inputs 在 feature $j$ 的值有很大的變動。

$\rightarrow$ 可是這並不保證 feature $j$ 是很重要的 feature 呀！

舉例來說：

> 有可能某個情況是我們要透過患者的各項身體資訊，來判斷得到某個疾病的可能性，因此我們的每個 input vector 是一位患者的 $d$ 項身體資訊，如身高、體重⋯⋯。
>
> 假設身高是具有最大 variance 的 feature，那麼當我們對這些 data 做 PCA 時，畫出來的 principal components，可能前幾個維度的方向都很受身高的影響，但實際上是否得到這樣的疾病或許跟身高沒有太大的關聯。
>
> 在這樣的情況下，浮動比較小（variance 較小）的 features，例如血糖、血壓⋯⋯，這些可能真正能夠決定生病可能性的 features，就沒辦法在做完 PCA 後的結果中呈現出來。

因此常用的做法是，我們在做 PCA 之前，先 preprocess data，使得++每個 dimension 的 mean 為零，且具 unit variance++。
> $\rightarrow$ 這樣的作法也可以視為我們賦予每個 variable 相同的 weight。

### robust estimation

正因為 PCA 能夠解釋 variance，所以它也特別容易受 outliers 影響。也就是說，如果有幾個點離中心比較遠，那麼這些點就會對 variance 造成巨大的變化，進而去影響 eigenvectors。

為了處理這個問題，我們會用 <font color = "snake">robust estimation methods</font>，這樣的 methods 讓我們在即使有 outliers 的情況下也可以好好去計算 parameters。

其中一種簡單的 robust estimation method 就是我們用 Mahalanobis distance (MD) 來計算 data points 間的距離，然後把獨立於大部分 data points 很遠的那些點捨棄。
> 關於 Mahalanobis distance (MD) 的內容，可參考筆記「[補充：multivariate outliers](https://hackmd.io/@pipibear/rkalaWUtR)」。

## 應用
### visual analysis


像上圖的例子，如果我們的 data 只需要靠兩個 principal components 就能解釋大部分的 variance，那我們就可以做 <font color = "snake">visual analysis</font>。

意思很簡單，就只是把 data 投影到這樣的二維空間。

這樣一來，我們就可以直接看出這些 data 的 structure, groups, outliers, normality⋯⋯。比起從原本的 variables 中挑兩個，這樣的 plot 能更好的去描述我們的 sample。藉由去觀察 principal components 所構成的 dimensions，我們甚至可以試著去尋找真正能夠好好描述 data 的 underlying variables。

舉個例子，在做人臉辨識時，我們可以利用一種東西叫做 <font color = "snake">eigenfaces</font>，先看圖我再稍微解釋：


簡單的說，原本我們的 face dataset 裡的每張臉都可以用一個 high-dimensional vector 表示，這些臉部照片構成了一個維度很高的向量空間。
> 比如說一張照片有 $r$ 列 $c$ 行的 pixels，那麼總共就有 $r\times c$ 個 pixels；如果我們將每個 pixel 的值用一個維度表示，那這些 face dataset 就構成了一個 $r\times c$ 維的向量空間。
>
> 下圖我們可以大概看一下實際上這樣的向量空間到底有多大，例如一張 $3 \times 5$ 吋的照片就有 $900 \times 1500$ pixels：
>
> 

不過對於這些維度很大的向量，我們一樣可以用一般 multivariate data 的方式去計算它們的 distribution，當然也能計算 covariance matrix。

得到 covariance matrix 以後，我們一樣做 eigen-decomposition，取一些 orthonormal eigenvectors 作為一個維度比較低的子空間的 basis，而這些 eigenvectors 就被稱作 eigenfaces、它們所生成的空間則叫做 <font color = "snake">face space</font>。

我們可以回想前面在取 eigenvector 作為 principal component 時，我們的這些新的軸，每個 principal component $\vec{w}_i$ 和原本的 data 維度是相同的。同樣的道理，這些 eigenfaces 也是作為 principal components，每個也都和我們原本的臉部照片有同樣的維度，並且每個 dimension 具有某個特定的值，所以也是臉的樣子（如上方的圖中每個 eigenface 是一張糊糊的人臉。）

整個概念大概是：

透過上面的作法，我們可以將每一張人臉照片大略用這些 eigenfaces 的組合表示。也可以說，我們假定所有的人臉樣貌，其實都是由少數的「標準臉部基底」組合而成，一張人臉可以是 $20\%$ 的 eigenface $1$，加上 $10\%$ 的 eigenface $2$⋯⋯。

### 在低維空間做 parametric discrimination

在前幾個小節裡，尤其「[5.5 Multivariate Classification](https://hackmd.io/@pipibear/ByBQVbqKR)」我們花很多時間在討論要怎麼在 input 不只是一個值，而是一個 $d$ 維向量時去對這些 input vectors 做分類。

當時我們假設 input vectors $\vec{x} \in \mathbb{R}^d$ 在屬於各個 class $i$ 的情況下，class conditional densities $p(\vec{x}|C_i)$ 皆為 normally distributed。圖例如下，如果還是忘記了，可以去回顧上面 $5.5$ 的筆記連結：


在這樣的假設下，我們去討論要怎麼估計各個 class 的 parameters，如 $\vec{\mu}_i, \ \Sigma_i$ 等等，來形成我們的 discriminant functions。

當然這些問題在 $d$ 一大時就變得很麻煩，複雜度也會變得很高，所以對於這樣的情形，我們其實也可以先用 PCA 來降低 data 的維度。


根據筆記「[5.4 Multivariate Normal Distribution](https://hackmd.io/@pipibear/SkgL8C3OA)」的定理，我們知道投影後維度雖然下降，但投影完的 data 分佈仍然會是 normal 的：


這樣一來，我們就可以在比較小的向量空間下去進行計算；不只如此，因為投影後的 $z_j$ 彼此不相關，所以 covariance matrix 會是對角、 unit variance 的情況下，我們也不用去計算 MD，因為這等同於一般的 Euclidean distance，這些都會使我們的 classifier 大大簡化。詳細說明如下圖：


> 有興趣的話，可以回過頭去對照筆記「[5.5 Multivariate Classification](https://hackmd.io/@pipibear/ByBQVbqKR)」，就能知道經過 PCA，有多少東西能夠被簡化。

## Reconstruction

假如我們想要把投影後（以 principal components 為 basis 的）的新座標 $\vec{z}^t$，還原回原本的 $\vec{x}^t$，是否做得到呢？

我們先來回顧一下一開始 $\vec{z}^t$ 怎麼來的：


根據前面的作法，我們是用 orthonormal 的 unit vectors 來當作 $W$ 的行，因此 $W$ 為 orthogonal，所以必定存在反矩陣，代表一定存在一個 $W^{-1}$ 可以把 $\vec{z}^t$ 「反投影」回去，但是問題是：這樣投影回去的結果還會是原本那個 $\vec{x}^t$ 嗎？


問題就變成：

:::danger
$\hat{x}^t = \vec{x}^t$ ？
:::

我們將這個問題分成兩種情況來看：



從 $Case \ 2$ 中我們發現，如果為了把 dimension 降低得多一點，我們捨棄一部分具有非零 eigenvalues 的 eigenvectors，這樣一來就會產生 <font color = "snake">reconstruction error</font>：

:::info
\begin{equation}
\sum_{t=1}^N ||\vec{x}^t - \hat{x}^t||^2
\end{equation}
:::
> reconstruction error 即 data set 中的所有 instances，和它投影後又還原回來的版本，兩者之間的 squared distance 總和。

- reconstruction error 的大小會 depend on 我們捨棄掉的 eigenvectors 對應的 eigenvalues 大小。

那知道這個東西可以拿來幹嘛呢？

舉例來說，像是前面我們在講人臉辨識的例子裡，我們去呈現還原回來的 $\hat{x}^t$，就能用看的去檢查經過 PCA 以後產生了多少 information loss。

---

這節的內容就大概到這裡，儘管課本在最後有很一點點的補充，在講一些 PCA 的不同版本和擴充，但因為每一種都只有一兩句話，就在此先省略。

如果對從另一個角度去看 PCA，也就是將我們的目標放在去 minimize 平均的 reconstruction error 有興趣，可以參考 A. Aldo Faisal 那本課本的 $10.3$ Projection Perspective，這本課本真的寫得很棒！簡單清楚、不太省略每件事為什麼是這樣子的解釋，非常推薦～

# 參考資料

- A. Aldo Faisal, Cheng Soon Ong, Marc Peter Deisenroth, Mathematics for Machine Learning, p.317-325
- Christopher Bishop, Pattern Recognition and Machine Learning, p.561-563
- Gilbert Strang, Linear Algebra and Its Applications, 4th edition, p.171-175, 317-318
- [Principal component analysis with Lagrange multiplier](https://ekamperi.github.io/mathematics/2020/11/01/principal-component-analysis-lagrange-multiplier.html)
- [3.2 Spectral/eigen decomposition](https://rich-d-wilkinson.github.io/MATH3030/3.2-spectraleigen-decomposition.html)
- [Face Recognition Using Eigenfaces](https://www.mit.edu/~9.54/fall14/Classes/class10/Turk%20Pentland%20Eigenfaces.pdf)
- wiki: [Eigenface](https://en.wikipedia.org/wiki/Eigenface#:~:text=Informally%2C%20eigenfaces%20can%20be%20considered,combination%20of%20these%20standard%20faces.)