# 6.1 Introduction

不管是在 regression 或 classification 裡：

:::warning
任何 regressor / classifier 的 complexity，都 depends on input (feature / attribute) 的數量。
:::

在前面第五章裡，我們在討論 multivariate data 時，都是令每個 data point 為：

\begin{equation}
\vec{x} = [\,x_1,...,x_d]\,
\end{equation}

也就是說，每個點 $\vec{x}$ 都是一個 $d$ 維的向量，其中的每一個 entry 都是一個 input，或者也可以稱作 feature 或 attribute。

因為 $d$ 的大小決定了 time / space complexity，還有要 train 這樣的一個 classifier / regressor 所需要的 training examples 數量，在這個章節裡面，我們就要來討論：

- <font color = "snake">feature selection</font>：從所有的 features 中，挑出重要的 features，並刪掉剩下的。
- <font color = "snake">feature extraction</font>：從原本的 input 裡面形成新的、更少的 features。

## 減少 dimension 的目的

在不管是 classification 或是 regression 的 application 中，我們都相信觀察到的 observed data 應該要包含一些資訊，因此我們將 observed data 作為 inputs，丟到我們的系統裡面來做出 decisions。

理想上，我們應該不需要另外去做 feature selection / extraction，因為我們的 classifier / regressor 應該要能自己去挑出需要的 features、拋棄不必要的 features。
> 例如在 regression 中：
>
> 假設原始 data 為 $K$ 維向量，其中有一個 feature 對 output 影響不大，另一個 feature 的值不管是多少，對 output 不造成影響；那麼理想上我們應該要可以直接用這些 $K$-dimensional data，然後讓我們的 regressor 把這兩個 features 對應的 weight 分別設成很小的值或零即可，不需要自己先去對 data 的 feature 刪減或修改。

那之所以要加上額外的 preprocessing step 來減少 dimension 的大小有幾個理由：

- 在大部分的 learning algorithms 中，complexity 由 input dimensions $d$ 和 sample size $N$ 決定，因此為了去降低 memory 和 computation，我們就會希望問題的 dimensionality 可以被減少。並且，減少 dimension $d$ 也會讓 testing 時用的 inference algorithm 的 complexity 也跟著降低。
- 如果有 input 被認定是不必要的，那我們就能節省 extract 這個 input 的成本。
- 對比較小的 datasets 來說，簡單一點的 models 會比較 robust。simpler models 的 variance 比較小，也就是說，比較不會受一個 sample 中特定的值（像是 noise, outliers⋯⋯）影響而變化。
> 關於這點，可參考筆記「[4.7 Tuning Model Complexity: Bias / Variance Dilemma](https://hackmd.io/@pipibear/Sy7Fs2VOA)」中的例子。
- 如果我們可以用比較少的 features 來解釋我們的 data，那麼我們也能對 data 背後運作的方式有比較清晰的概念。這部分比較少的 features 可以被解釋為能夠組合產生 observed features 的 <font color = "snake">hidden / latent factors</font>。
- 當 data 可以在不損失資訊的情況下用比較少的 dimension 表示，那就能被標在圖上，讓我們能用看的去分析整個 structure 和找出 outliers。
> 但要用看的找出 outliers 頂多只能在 dimension $d \le 2$ 時，關於 outliers 可參考筆記「[補充：multivariate outliers](https://hackmd.io/@pipibear/rkalaWUtR)」。

回到一開始說的，為了要減少 dimension，我們主要有兩種方法叫做 feature selection 和 feature extraction，下面分別簡單這兩種方法要做什麼，以及主要（之後的筆記會談到的）有哪些 methods。

## feature selection

在 <font color = 'snake'>feature selection</font> 中，我們主要的目標是要從原本的 $d$ 個 dimensions 中：

- 挑出 $k$ 個帶給我們大部分資訊的 dimensions
- 拋棄剩下 $d-k$ 個不重要的 dimensions

之後我們會來講 feature selection 的其中一個 method，叫做 <font color = "snake">subset selection</font>。

## feature extraction

在 <font color = 'snake'>feature extraction</font> 中，我們想要利用原本的 $d$ 個 dimensions，組合產生一個新的 $k$ 個 dimensions 的 set。

根據是否會利用到 output information，feature extraction 的 methods 可以被分成 supervised / unsupervised。最常見也最常用的 feature extraction methods 為：

- <font color = "snake">principal component analysis (PCA)</font>
- <font color = "snake">linear discriminant analysis</font>

兩者皆為利用 linear projection 的 methods。

我們可以先簡單看個之前也有稍為提到過的 PCA 的圖：

> 原本我們的 dimension $d=3$
>> 每個 data point $\vec{x} = [\,x_1, x_2, x_3]\,^T$，共有三個 variables $X_1,X_2,X_3$
>>
> 透過 PCA，我們（主要是利用一些線性代數的投影技巧）將維度下降成二維的平面，得到的結果兩個軸並不是從原本的 variables 中挑出兩個，而是由原本 variables 的資訊組合而成的 principal component。

雖然後面會再詳細一點的講，但可以先大概看看這個圖，就能對 PCA 大概有個概念：


最後，PCA 和另外兩個 unsupervised linear methods 很相似，之後我們也會再討論這兩個 methods：

1. <font color = "snake">factor analysis</font>
2. <font color = "snake">multidimensional scaling</font>

如果我們不是只有一個，而是有兩個 sets 的 observed variables，我們可利用 <font color = "snake">canonical correlation analysis</font> 來找出解釋這兩個 sets 之間的 dependency 的 joint features。

上述我們所說的 methods 都是 linear 的，至於 nonlinear 的 dimensionality reduction，我們之後會講到的有：

1. <font color = "snake">isometric feature mapping
2. locally linear embedding
3. Laplacian eigenmaps</font>