# 5.6 Tuning Complexity

本節的內容不多，基本上都是前一節：

筆記「[5.5 Multivariate Classification](https://hackmd.io/@pipibear/ByBQVbqKR)」

的整理與延伸，因此如果有沒特別說明的地方，基本上回頭看這篇筆記，就可以在裡面找到答案 :)

---
## discriminant function 在 simplicity 和 generality 之間的 tradeoff

在前一小節最後整理的表格裡，也就是這張表：


我們看到在不同的條件下，covariance matrix 的 estimator $S$（或者如果讓每個 class 有自己的 covariance matrix $S_i$，共 $K$ 個）中，需要 estimate 的 parameter 數量可以藉由訂定不同的 assumptions 增減。

但是像我們在那篇筆記裡提到過的一樣，這又是一個 model 在 simplicity 和 generality 之間的 tradeoff。
> 可以去回顧該篇筆記中，我們設立越多的條件，來使 covariance matrix 的 estimator 越簡化的過程。
>
> 當我們條件到最嚴格的情況時，我們限制 $K$ 個 classes 都只能用同一個 covariance matrix，且在給定某個 class 的情況下，$d$ 個 features 之間彼此獨立，每個 feature 為 univariate normal conditioned on 這個 class，最後，甚至我們要求這 $d$ 個 features 的 variance 相同。
>
> $\rightarrow$ 在這種種的條件下，我們最後發現 $S$ 變成對角矩陣，且對角項都相同，因此我們只需要 estimate 一個 parameter $s^2$。（在 covariance matrix 的部分）

這樣的 tradeoff，其實也是 bias / variance dilemma 的一個例子：

:::warning
當我們為了簡化 covariance matrix 去做出一些 assumptions，進而去減少需要 estimate 的 parameter 數量時，我們就需要去承擔 bias 變大的風險。
:::

另一方面：

:::warning
如果我們完全不去做任何這樣的 assumption，也就是我們的 covariance matrix 是任意的，那麼 quadratic discriminant 可能就會在 small datasets 的情況下有很大的 variance。
:::

Recall：如果我們讓每個 class 有自己的 covariance matrix estimate $S_i$，不限制任何東西的情況下，discriminant function 就會是 quadratic，如下：

\begin{equation}
g_i(\vec{x}) = \vec{x}^TW_i\vec{x} + \vec{w}_i^T\vec{x} + w_{i0}
\end{equation}

其中：
- $W_i = -\frac{1}{2}S_i^{-1}$
- $\vec{w}_i = S_i^{-1}\vec{m}_i$
- $w_{i0} = -\frac{1}{2}\log|S_i|-\frac{1}{2}\vec{m}_i^TS_i^{-1}\vec{m}_i+\log\hat{P}(C_i)$

> 如果忘記這怎麼來的，可以回去看筆記「[5.5 Multivariate Classification](https://hackmd.io/@pipibear/ByBQVbqKR)」中：
>
> 「estimate discriminant function 裡的 parameters」$\Rightarrow$「different, hyperellipsoidal」$\Rightarrow$ 「discriminant function」小節。

## 決定複雜度：特殊情形

### dataset 很小時

因此，我們應該要根據手邊有的 data 所呈現的問題複雜度，以及我們有的 data 數量，來決定最理想的情況——我們的 discriminant function 到底要像 nearest mean classifier 那麼簡單，還是像 quadratic 那麼複雜，或者是介於這兩者之間呢？

關於這個問題，有一些情況下我們有一般來說比較適合的方式：

當我們的 dataset 很小時，即使每個 class 的 covariance matrix 實際上不同，我們最好還是直接 ++assume 一個 shared covariance matrix++，因為這樣一來，一方面需要預測的 parameters 少，另一方面是我們可以用更多的 data（因為所有 classes 的 instances 都能拿來用）來 estimate 這些 parameters。

$\rightarrow$ 用 shared covariance matrix 的做法，就會使得 discriminant function 為 linear discriminant，也就是：

\begin{equation}
g_i(\vec{x}) =\vec{w}_i^T\vec{x} + w_{i0}
\end{equation}

> 詳細說明可參考筆記「[5.5 Multivariate Classification](https://hackmd.io/@pipibear/ByBQVbqKR)」中：
> 「estimate discriminant function 裡的 parameters」$\Rightarrow$ 「shared, hyperellipsoidal」

>[!Note] 關於 linear discriminants，未來第十章會有更詳細的說明。

### data 不足以計算 dependency 時

Note：

:::warning
當我們用 Euclidean distance 時，我們就是在 assume 所有的 variables 有相同的 variance，且它們是 independent 的。
:::

在大多數的情況下，上述這樣的 assumptions 並不成立。

舉例來說：

「年紀」和「年收入」有著不同的單位，且在許多情境底下這兩個 features 都是 dependent 的。

$\rightarrow$ 這樣的情況下，我們可以在一個 preprocess 的階段，先把 inputs 分別 z-normalize，也就是讓 mean $=0$、 variance $=1$，接著才去用 Euclidean distance。

$\rightarrow$ 但是如果我們的 data 不足以讓我們準確地去計算 variables 之間的 dependency，那麼即使這些 variables 之間是 dependent 的，我們最好還是直接 assume 他們 independent，然後用 Naive Bayes Classifier。

## RDA: Regularized discriminant analysis

上面我們所說的這些情形，其實都是一些 discriminant function 在最極端的情況下的特例，因此 Friedman 就提出一種方法，叫做 <font color = "snake">Regularized discriminant analysis (RDA)</font> ，來把所有這些 special cases 結合在一起。

首先，recall 我們在筆記「[4.8 Model Selection Procedures](https://hackmd.io/@pipibear/BJ5s6ZIO0)」有介紹過的 regularization，也就是用一些方法，在增加 bias 的風險下，將比較高的 variance 限制到較低的 variance。
> 比如說在計算 error 時，多加一個 term 為 model 的 complexity 去乘上某個權重，使得越複雜的 model error 越高。

同樣的想法套用到具有 Gaussian densities 的 classification 上，我們的 covariance matrix 就可以寫成前面我們講過的三種情況：

:::info
1. quadratic classifier
> 沒有任何限制，最複雜的情形。
2. linear classifier
> shared covariance matrix
3. nearest mean classfier
> shared, diagonal，對角項都是 $\sigma^2$
:::

的 weighted average。

也就是：

:::success
\begin{equation}
S_i' = \alpha\sigma^2 I + \beta S + (1 - \alpha -\beta)S_i
\end{equation}
:::

藉由訂定這樣的 $S_i'$，我們可以透過改變 weight $\alpha, \beta$ 的值，來達到調節 variance / bias 的效果；並且當 $\alpha, \beta$ 為特定的值時，我們也能回過來得到三種 special cases：

1. ==$\alpha = \beta = 0$==
> $S_i' = S_i$ （quadratic classifier）

2. ==$\alpha = 0, \ \beta = 1$==
> $S_i' = S$ （shared covariance matrix $\Rightarrow$ linear classifier）

3. ==$\alpha = 1, \ \beta = 0$==
> $S_i' = \sigma^2 I$ （covariance matrix diagonal with $\sigma^2$ on the diagonals $\Rightarrow$ nearest mean classfier）

在這些極端值之間，我們可以得到各種不同的 classifiers，其中，透過 cross-validation，我們可以得到 $\alpha, \beta$ 的 optimized value。
> 關於 cross-validation，一樣可回顧筆記「[4.8 Model Selection Procedures](https://hackmd.io/@pipibear/BJ5s6ZIO0)」的說明。