# DIMENSIONALITY REDUCTION 維度下降
1. Principal Components Analysis (PCA)
2. Factor Analysis (FA)
3. Independent Components Analysis (ICA)
4. Linear Discriminant Analysis (LDA)
---
## Motivation
為什需要進行維度下降
* 更快的分類速度（複雜度下降）
* 降低噪音點（noise or outlier）對模型的影響力
* 較好的資料視覺檢視
* 可能有利於分析

在高維度的空間中，有些屬性在經過線性轉換後會變得相當小（可忽略）
## Principal Components Analysis (PCA)
[ Data Points ] ${\large x_i \in R^p , i = 1,2,...,n}$
[ Load Vector ] ${\large w_k \in R^p, k = 1,2,...,m}$
</br>
**Find the first component** (dot means Inner product)
$${\large w_1 = arg \max_{||w|| = 1} \sum_i(x_i \cdot w)^2} $$
This **OPTIMIZATION PROBLEM** can be solved by **Lagrange multipliers** or **SVD**.

### PCA 概念
想找出一個 axis $w_1 \ni$ 投影到此axis上的 $x_i$ 能**獲得最大的平方和**

### PCA 計算
$$X^TX = W\Lambda W^T$$
${\large W = \begin{bmatrix}
w_1 & w_2 & ... & w_p\\ \end{bmatrix}_{p\times p}}$ consists of normalized eigenvectors **$\Large w_k$** which is associated with $\lambda_k$; btw, **$\Large w_j$** and **$\Large w_k$** are **orthonormal**.
$\Lambda = diag(\lambda_1, ...,\lambda_p)$ is a diagonal matrix consisting of eigenvalues of **$X^TX$**
#### 執行步驟
* 令 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_p$
* 進行維度下降，直到僅保留 k 個最具影響力的屬性
* 計算樣本 $\Large x_i$ 維度下降後的特徵矩陣
$$\begin{bmatrix} t_{i,1} & t_{i,2} & ... & t_{i,k}\\ \end{bmatrix} =\begin{bmatrix} x_{i,1} & x_{i,2} & ... & x_{i,p}\\ \end{bmatrix}
\begin{bmatrix} w_1 & w_2 & ... & w_k\\ \end{bmatrix}_{p\times k}$$
* 透過 Proportion of Variance 挑出k個屬性, PoV = $\Large \frac{\lambda_1+\cdots+\lambda_k}{\lambda_1+\cdots+\lambda_p} \geq 0.9$ (typically)

## Factor Analysis (FA)
FA是一種統計方法，透過潛在數量較少的未觀察變量因子（unobserved variable / factors）來描述觀察到的相關變量之間的變異性。其主要精神，即找出「潛在變項」( Latent Variable )。試想一份50題問卷，如果能找到 4 個因素包含 50 個題目中 95% 的資訊，那麼我們應該分析 50 題的所有差異或是直接觀察 4 個主要因素呢?

「基本公式」($x_i,z_j, and \varepsilon_i$ are scalar **random variables**)
$$ x_i - \mu_i = v_{i,1}z_1+v_{i,2}z_2+\cdots+v_{i,k}z_k+\varepsilon_i$$
* $\large x_i$, i = 1...p 可測量變數（e.g. Waiting time）
* $\large z_j$ , j = 1...k 潛在因素（e.g. Food quality）
* $E[z_j] = 0, \sum = I$ (i.e. covariance is Identity matrix)
* $\large \varepsilon_i$ 是噪音項，其中 $E[\varepsilon_i] = 0, \sum = \Psi$ (diagonal matrix)
* $z_j$ 及 $\varepsilon_i$ 的關係為 not correlated
* 令 $x = \begin{bmatrix} x_1 & x_2 & ... & x_p\\ \end{bmatrix}^T$ 則可將基本公式改寫成矩陣形式，同時不失一般性去除平均值 mean ( $\mu$ ) = 0

$$\large x-\mu = Vz + \varepsilon$$
$$\Rightarrow{\large x = Vz + \varepsilon}$$

$$\Rightarrow{\large \begin{bmatrix}x_1 \\x_2 \\ \cdots \\ x_p \end{bmatrix} =
\begin{bmatrix}
v_{1,1} & v_{1,2} & ... & v_{1,k} \\
v_{2,1} & v_{2,2} & \cdots & v_{2,k} \\
\cdot & \cdot & \cdot & \cdot \\
v_{p,1} & v_{p,2} & \cdots & v_{p,k}
\end{bmatrix}_{p \times k}
\begin{bmatrix}
z_1 \\ z_2 \\ \cdots \\ z_k
\end{bmatrix}_{k \times 1}
+
\begin{bmatrix}\varepsilon_1 \\ \varepsilon_2 \\ \cdots \\ \varepsilon_p \end{bmatrix}}$$

其中 $V = [v_{i,j}]$ 是一個 $p\times k$ 階常數矩陣，稱為因素負荷 (factor loading)，描述因素 $\mathbf{z}$ 是多變數 $\mathbf{x}$ 的變換。你不妨想像 $z_1,\ldots,z_k$ 代表未知的信號源，將 k 個信號同時送入 p 個通道，每個通道各自有增強或衰減信號的方式 (線性組合)，通道末端再引入雜音 (殘差) 就是我們接收到的變數 $x_1,\ldots,x_p$

因素分析的模型參數包括 $p\times k$ 階因素負荷 F 與殘差的變異數 $\Psi=\hbox{diag}(\psi_1,\ldots,\psi_p)$，合計 p(k+1) 個參數值。根據上述假設，你可以計算隨機向量 $\mathbf{x}$ 的期望值與共變異數矩陣。期望值 $\hbox{E}[\cdot]$ 是線性算子，因此
$$\displaystyle \hbox{E}[\mathbf{x}]=\hbox{E}[V\mathbf{z}+\boldsymbol{\epsilon}]=V\hbox{E}[\mathbf{z}]+\hbox{E}[\boldsymbol{\epsilon}]=\mathbf{0}$$
$$ Cov[x]= \Sigma = VV^T + \Psi$$

#### 參數估計

假設你有一筆樣本大小為 n 的數據$\{\mathbf{x}_1,\ldots,\mathbf{x}_n\}$，每個數據點視為一個向量 $\mathbf{x}_l=(x_{l1},\ldots,x_{lp})^T\in\mathbb{R}^p$。定義 $n\times p$ 階數據矩陣
$$\displaystyle X=\begin{bmatrix} \mathbf{x}_1^T\\ \vdots\\ \mathbf{x}_n^T \end{bmatrix}=\begin{bmatrix} x_{11}&\cdots&x_{1p}\\ \vdots&\ddots&\vdots\\ x_{n1}&\cdots&x_{np} \end{bmatrix}$$
其中 $x_{li}$ 表示第 i 個隨機變數 $x_i$ 的第 $l$ 個量測值，$i=1,\ldots,p，l=1,\ldots,n$。我們假設樣本已經去除平均數，$\sum_{l=1}^n\mathbf{x}_l=\mathbf{0}$。共變異數矩陣 $\Sigma$ 通常以樣本共變異數矩陣估計：

$$\displaystyle S=\frac{1}{n-1}\sum_{i=1}^n\mathbf{x}_i\mathbf{x}_i^T=\frac{1}{n-1}X^TX。$$

接下來的問題是從給定的樣本共變異數矩陣 $S=[s_{ij}]$
**求出因素分析的參數估計** : $\hat{V} 與 \hat{\Psi} 使得 S\approx \hat{V}\hat{V}^T+\hat{\Psi}$。
兩種常見的估計法
主因素分析 (principal factor analysis) 與最大似然估計 (maximum likelihood estimation) (數學過程略過)

如果特殊變異矩陣不存在，$\Psi=0$ 表示 $Cov[\mathbf{x}] = \Sigma = VV^T$
已知
$$\large S=W\Lambda W^T = (W \Lambda^\frac{1}{2})(\Lambda^\frac{1}{2} W^T)=(W \Lambda^\frac{1}{2})(W \Lambda^\frac{1}{2})^T$$

如果 V 的大小與 $(W\Lambda^\frac{1}{2})$ 相同，則可直接使用估計值 $$\hat{V}=(W\Lambda^\frac{1}{2}) , \mathbf{\hat{z}} = \hat{V}^{-1}(\mathbf{x}-\mathbf{\varepsilon})$$
否則，如果大小不同但 p > k (註： $\small \mathbf{x} = \begin{bmatrix} x_1 & x_2 & ... & x_p\\ \end{bmatrix}^T$, $\small \mathbf{z} = \begin{bmatrix} z_1 & z_2 & ... & z_k\\ \end{bmatrix}^T$ ) 則
$$ \mathbf{\hat{V}}=
\begin{bmatrix} \uparrow & & \uparrow \\ \sqrt{\lambda_1}\mathbf{w_l} & ... & \sqrt{\lambda_k}\mathbf{w_k}\\
\downarrow & & \downarrow
\end{bmatrix}_{p \times k}$$