# 6.2 Subset Selection

前一節的 Introduction 裡面我們有提到，feature selection 的一種做法叫做 subset selection。在 subset selection 中，我們的目標是從原本所有的 features 裡面，挑出一個最好的 subset。

什麼叫「最好的 subset」呢？

:::info
The best subset ++contains the least number of dimensions++ that ++most contribute to accuracy++.
:::

至於剩下的 features，我們就直接捨棄掉。

透過利用適合的 error function，subset selection 可以應用在 regression / classification 的問題上。

## 方法

假如一開始我們的 data 有 $d$ 個 variables，也就是說每一筆 data 都是一個 $d$ 維向量：

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

我們要從這些 $x_i, \ i=1,...,d$ 之中挑出一部分（或全部）的 features，所有可能的 subsets 有 $2^d$ 種。
> 因為對每個 $x_i$，我們都有取或不取兩種選擇，所以一共是 $2$ 的 $d$ 次方。

但是如果我們要把這 $2^d$ 個 subsets 都試過一輪，再挑出最好的那個，這樣太耗費時間了，除非是 $d$ 非常小的情形。
> 我們可以想像如果當我們有十個 features $d=10$，那麼所有可能的 model 就有一千個左右，如果 $d=20$，那所有可能的 model 就超過一百萬個。
>
> 即使是現代速度非常快的電腦，當 $d>40$ 時，我們也沒辦法用這種方式來一一檢查並找出 optimal subset。

因此，有兩種方法讓我們不用試過每個可能的 subsets：

1. <font color = "snake">forward selection</font>
2. <font color = "snake">backward selection</font>

### forward selection

如果我們用的是 forward selection，那麼首先我們從一個空的集合（不取任何 variable）開始，接著再將 variables 一個一個加入。

每一步我們都選擇可以讓 error 降低最多的那個 variable，就這樣不斷加入 variables，直到再加入任何 variable 都不會使 error 再降低，或者降低的幅度很小。

為了要進行後續的討論，我們先來定義一些 notation：


把剛剛所說的步驟，結合上方的 notation 表示如下：

> 最後要停止的 threshold 為 user-defined，這個 threshold 訂定的依據為 application 本身的限制，還有在 error 和 complexity 之間哪個比較重要的 tradeoff。
>
> $\rightarrow$ 如果加入一個 feature，會帶來 observe 這個 feature 的 cost，也會讓 classifier / regressor 更 complex。

### backward selection

如果我們選擇使用 backward selection，那麼我們就是反過來先取所有的 variables，再一個一個把 variables 移除。

每一步我們都移除<font color = "red">使 error 下降最多</font>（或是只會稍微增加 error）的 variable。

:::danger
為什麼是要移除使 error 下降最多的 variable 呢？直覺上不是移除會讓 error 增加最多的 variable，會使最終的 error 最小嗎？
:::

這麼做的原因在於，如果有一個 variable 是當我們移除它時，會使得 error 大幅提升，那意味著這個 variable 很具代表性，有了它，我們就能做出精確很多的預測。

相反的，如果當移除一個 variable 時 error 只會稍微增加，或是甚至使 error 下降，那代表說這個 variable 根本不重要，少掉這個 variable error 也不會大到哪裡去。

$\rightarrow$ 也就是說，我們選擇去捨棄使 error 下降最多的 variable，實際上是在挑出那些最不重要的 features。

最後，我們不斷重複移除的步驟，直到再移除任何 variable 都會使 error 大幅增加為止。
> 代表剩下來的 variables 都很重要，拿掉都會產生很大的 error。

把上面講的再整理一次：


按照上面的作法，當移除任何一個 feature 都不會讓 error 下降時，我們就停止；但是為了要去減少 complexity，我們也可以訂說如果移除某個 feature 只會讓 error 稍微增加，那我們就直接把它移除。

### 檢驗 error

不管是上面兩種方法的哪一種，我們要去檢驗 error 時，都是用一個不同於 training set 的 validation set，因為我們不是想看針對 training set 來說正確率高不高，而是想透過沒用來 train 的 validation set 來看看 generalized accuracy。
> 以前我們有提過，training error 一般來說會比 test error 小一些；並且即便 training error 很低，也不保證 test error 會是低的。

:::warning
如果我們有更多的 features，一般來說我們會有更低的 training error，但是不一定會有比較低的 validation error。
:::

## 例子

看個例子，假如我們原始的 data 有：

- 四個 inputs
> 代表每個 data point 為一個四維的向量。
- 三個 classes
$\rightarrow$ 每個 class 有 50 個 instances，我們把這 50 個 instances 分為：
- 包含 20 個 instances 的 training set
- 包含剩下 30 個 instances 的 validation set

為了要去決定每個 data point 要被分到三個 classes 中的哪一個 ，我們需要利用 discriminant function $g_i(\vec{x})$。
> Recall：我們判斷一個 data point $\vec{x}$ 要分到哪個 class 的方式，就是將它代入每個 class 對應的 discriminant function，最後以值最大的 output 將 $\vec{x}$ 分到對應的 class。
>
> 在我們現在的例子中，因為有三個 classes，所以我們會有 $g_1(), g_2(), g_3()$，假設代入 $\vec{x}$ 後的結果為 $g_1(\vec{x}) > g_2(\vec{x}) > g_3(\vec{x})$，那麼我們就將 $\vec{x}$ 分類到 class $1$。

至於這些 discriminant functions 到底長什麼樣子，這裡我們選擇採用的是 nearest mean classifier，如下：

> 這樣的 discriminant 使得當我們的 data point $\vec{x}$，和已知屬於 class $i$ 的那些 instances 的平均（class $i$ 的 sample mean）距離最小時，平方取負號會負的最少，因此有最大的 $g_i(\vec{x})$ 值。
>
>> 關於 nearest mean classifier 的介紹可參考筆記「[5.5 Multivariate Classification](https://hackmd.io/@pipibear/ByBQVbqKR)」中：
>>
>> 「estimate discriminant function 裡的 parameters」$\Rightarrow$「shared, hyperspheric」$\Rightarrow$「nearest mean classifier」

在訂好所有的前提以後，我們先來看看畫出來的圖長什麼樣子。

首先我們從單一個 feature 開始，下圖 $6.1$ 為我們分別只考慮四個 features $F1, F2, F3, F4$ 的其中一個時，data points 在該 feature 的值是如何分佈，每個符號（正字、打叉、圓形）分別代表一個 class。


我們從圖中可以發現 $F4$ 的分界相對比較清楚，代表只考慮 $F4$ 的情況下，我們可以很容易地去分類 training set 中的 data points。

接著，我們就可以透過這些四種情況下的結果，分別計算三個 classes 的 mean，來得到該情況下的 discriminant functions。講起來有點不清楚，看 $F = \{F4\}$ 的情形如下：


接下來，我們將每個 class 一開始沒用來 train 的 instances，也就是共三個 validation sets 中的所有 data points，代入剛剛 train 完得到的 discriminant function，看看正確率有多高。

一樣只看 $F = \{F4\}$ 的情形如下：


如果我們對 $F = \{F1\}$、$F = \{F2\}$、$F = \{F3\}$、$F = \{F4\}$ 的四種情形都分別去計算出 accuracy，課本給的值依序是 $0.76, 0.57, 0.92, 0.94$，於是我們取正確率最高的 $F4$ 真正加入原本為空的 feature set。

接下來，因為我們要繼續去考慮如果再加入一個 feature 會不會讓正確率提升，我們就考慮 $F4$ 分別加上剩下三個 features 中的一個的三種情形，一樣再去計算正確率。

課本給的例子結論是加入 $F3$ 以後正確率會從只有 $F4$ 的 $0.94$ 提升到 $0.96$，因此我們加入 $F3$ 到 feature set，取 $F = \{F3,F4\}$。

最後，我們一樣再看看分別加入剩下的兩個 $F1,F2$ 這個正確率會不會再提高，課本假設 $F = \{F1,F3,F4\}$ 和 $F = \{F2,F3,F4\}$ 這兩種情形正確率都是 $0.94$，於是我們發現已經沒辦法再透過加入 feature 提升正確率了，因此最終取 $F = \{F3,F4\}$。

假如四個 features 都考慮，即 $F = \{F1,F2,F3,F4\}$ 的時候，正確率也是 $0.94$，那我們就會發現：

原本想像中越多 features 應該要有更多的資訊，所以把所有已知的東西都考慮進去正確率應該要最高，但是其實不是。透過去掉兩個 features，我們反而將正確率從 $0.94$ 提升到 $0.96$。

## Note

### feature set 取決於 classifier

我們要注意的是，最後我們的 feature set $F$ 到底取了哪些 features，是很大程度地取決於我們用什麼樣的 ++classifier++。

在上面的例子裡，我們用 nearest mean classifier，但如果我們用 naive Bayes classifier，或許選出來的 $F$ 就不一樣。
> 關於 naive Bayes classifier，有興趣可參考筆記「[5.5 Multivariate Classification](https://hackmd.io/@pipibear/ByBQVbqKR)」中：
>>
>> 「estimate discriminant function 裡的 parameters」$\Rightarrow$「shared, axis-aligned: Naive Bayes Model」$\Rightarrow$「discriminant function」

### dataset 小的情形

如果我們的 datasets 很小時，我們最後選出來的 $F$，也會很大程度地受++分割 training / validation data 的方式++影響。

因此在 datasets 很小的情況下，我們應該要做多次且隨機的 splits，計算每次的 validation performance 再取平均。

> [!Note] 第十九章我們會再介紹 resampling methods。

### time complexity

像上面的例子裡我們可以看到：

第一輪我們需要從全部 $d$ 個 features 中挑出最好的那個、第二輪時我們已經挑好一個了，因此要從剩下的 $d-1$ 個裡面挑出最好的那個⋯⋯，因此假如我們要從原本的 dimension $d$ 減少到 $k$，我們需要 train 和 test 共：

\begin{equation}
d + (d-1) + (d-2) + ... + (d-k) = O(d^2)
\end{equation}

所以這樣一個一個去挑 feature 的過程是 costly 的。

### 不保證找到 optimal subset

Forward selection 是一個 local search procedure，因此不保證能夠找到 optimal subset，也就是不保證能找到產生最小 error 的 subset。

舉例來說：

如果我們分別去看 $x_i,x_j$ 兩個 features，或許有可能它們都不是最適合的，但是當它們一起被加入 feature set，反而可能讓 error 下降許多。

這是因為 forward selection 是 <font color = "green">greedy</font> 的，並且我們每一輪只會加入一個新的 attribute，所以這樣的 algorithm 就沒辦法發現上述那樣的情形。

$\rightarrow$ 不過我們也不一定只能一次加入一個 feature，要一次加入多個也行，只是會需要更多的 computation。

$\rightarrow$ 為了避免像例子中那樣的情形，我們也可以 backtrack，然後去檢查在目前的 feature 加入以後，前面是否有 feature 可以被移除。這樣一來，我們的 search space 就會增加，但 complexity 當然也會跟著增加。
> - 這樣的方式其實是 forward 和 backward 的 hybrid version，目的是保留 forward 和 backward 在計算上的優勢的情況下，去模仿考慮所有可能的 subsets 的作法。
>
> 如果我們這樣反覆在每次加入 feature 後回頭去檢查，最極端的例子其實就回歸到一開始我們直接去檢查所有可能的 subset，也就是所有 $2^d$ 種情形。
>
> 在這樣的情況下，search space 是最大的，因此我們也會有更高的機率能夠去找到一個 model，來讓 training data 看起來有很好的結果。但是我們知道，training 的結果好並不保證這個 model 能對未來沒看過的 data 有好的 prediction。
>
> 因此，有這麼大的 search space 反而不見得是好事，甚至可能導致 overfitting，並且使得係數的 estimates 具有 high variance。

- 在 <font color = "snake">floating search</font> 中，在每一步驟我們都可以調整要增加的 feature 數量，也可以自由地去決定要不要移除 feature。

---

基本上上面提到的所有 forward search 的性質、會遇到的問題也都適用於 backward search。

backward search 的 time complexity 也和 forward 相同，只不過對 backward search 來說，去 train 一個有比較多 features 的 system 比起去 train 一個 features 比較少的 system 來的更 costly。

此外，如果我們預期會有很多沒有用的 features，那我們也會較偏好用 forward search。

---
## 結論

最後，我們做一點總結：

- 因為我們利用 outputs 來讓 regressor / classifier 計算 error，所以 subset selection 是 supervised。
- subset selection 可以被應用在任何 regression / classification method，像是在我們之間講過的 multivariate normal 這個特例中：

> Recall：如果原本的 $d$-dimensional class densities 是 multivariate normal，那我們任取它的 subset 也會是 multivariate normal 的。

我們仍然可以在不用原本的 $d\times d$ covariance matrix，改取 $k\times k$ 的情況下，去做 parametric classification。
> 關於這部分內容，如果不熟悉，可參考筆記「[5.5 Multivariate Classification](https://hackmd.io/@pipibear/ByBQVbqKR)」。

- 在一些 applications 中，如人臉辨識，feature selection 就不是一個適合拿來做 dimensionality reduction 的方式，因為每個單一的 pixel 並不會帶有太多的 discriminative information，是許多 pixels 組合起來的值才會帶有臉部身份的資訊。

$\rightarrow$ 因此，這就需要用到我們在後面的小節裡會講到的 feature extraction methods。

# 參考資料

- Introduction to Statistical Learning (Python), p.231-235
- [Variable Subset Selection](https://bookdown.org/ssjackson300/Machine-Learning-Lecture-Notes/variable-subset-selection.html)
> 我沒有引用在這篇筆記裡，但是覺得寫得很好的筆記！