# 5.5 Multivariate Classification

我們以前學過：

在 classification 的問題裡，我們希望透過 sample 的 data 來對每個 class 找出一個適合的 function（叫做 discriminant function），來使得當我們有新的 input 時，我們可以代入這些 functions 裡，並藉由找出最大的 output 來決定要把這個新的 input 分類到哪個 class。

最初我們的討論都建立在 input 只是某個值（一維）的情況下，而在這個小節裡，我們要做的是延續前幾節對 multivariate 的介紹，來看看一個 $d$ 維的 random vector 要怎麼去做 classification。

也就是說，當 feature 很多時，要怎麼去分類我們的 input？

---
# normal class conditional densitiy

## 定義

假設 $\vec{x} \in \mathbb{R}^d$，也就是說每個 input 都是一個含 $d$ 個 features 的向量。

如果 ++class-conditional densities 為 normally distributed++，也就是：

:::success

\begin{equation}
p(\vec{x}|C_i) \sim N_d(\vec{\mu}_i, \Sigma_i)
\end{equation}
:::
> 舉例來說，假設我們 dataset 中的點可以分成兩個 classes，$C_1$ 包含了一部分的點、$C_2$ 包含了另一部分。
>
> 如果我們說 "class conditional densities are taken as normal density" 代表這些 data points 的分佈滿足：
>
> $p(\vec{x}|C_1) \sim N_d(\vec{\mu}_1, \Sigma_1)$
> $p(\vec{x}|C_2) \sim N_d(\vec{\mu}_2, \Sigma_2)$
>
> 第一條式子的意思是：
>
> 如果我們只看屬於 class $1$ 的那些點，我們會發現這些點的分佈是 normal 的，也就是畫出來的 pdf 呈 bell-shaped，並且以 $\vec{\mu}_1$ 為中心、分散的程度由 $\Sigma_1$ 定義。
>
> 另一種說法是：
>
> 如果我們去看屬於 class $1$ 的那些點，我們會發現最有可能 observe 的 input $\vec{x}$ 會是 $\vec{\mu}_1$；而和 $\vec{\mu}_1$ 距離越遠的點，越不會是我們從 $C_1$ 中任挑某個點時會看到的點，也就是說和 $\vec{\mu}_1$ 差越多的點，發生的機率越小，並且這個隨著遠離 $\vec{\mu}_1$，機率變小的程度由 $\Sigma_1$ 決定。

因為我們假定 class conditional densities 是 normally distributed，所以它的 pdf 會滿足 multivariate normal 的 pdf：

\begin{equation}
p(\vec{x}|C_i) = \frac{1}{(2\pi)^{\frac{d}{2}}|\Sigma_i|^{\frac{1}{2}}}e^{-\frac{1}{2}(\vec{x} - \vec{\mu}_i)^T\Sigma_i^{-1}(\vec{x} - \vec{\mu}_i)}
\end{equation}

以前我們說過，normal density 是一種很多自然現象都符合的 model，並且大部分 classes 中的 examples，都可以被視為對單一一個 prototype $\vec{\mu}_i$ 做出些微調整的不同版本，而 covariance matrix $\Sigma_i$ 代表了每個 variable $X_i$ 之中的 noise 量，以及這些 noise 來源之間的 correlations。

所以儘管實際的 data 通常不會是 exactly multivariate normal，但是作為一個 approximation 還是很適合的。

不過，有一個條件是我們的 class sample 必須形成單一個 group，如果有多個 groups，那我們就應該要用 mixture model。

課本沒有對這部分特別說明，但我們可以看看這張圖：

> 在這張圖裡面，我們的 data points 大致可以分成三個 groups，這三個 groups 分別都是 normally distributed，所以我們可以用 Gaussian mixture model (GMM) 來描述這整個 dataset。
>
> 因為這個例子是 univariate 的，所以每個 normally distributed 的 group 具有 mean $\mu_i$ 和 variance $\sigma_i^2$，我們根據這些 groups 各自的 prior probability 去施加一個 weight $\phi_i$，因為必須滿足 pdf 的定義，所以 $\phi_i$ 的總和會是 $1$。
>
> 這樣加總起來，我們就得到能夠描述多個 normal distributed groups 的 model。
>> 這部分如果之後有讀到會再做更詳細的筆記，此處課本只是帶過，就不多說明。

## 例子

從剛剛到現在講了那麼多，不如實際看個例子：


Recall 我們之前在講 classification 時，我們希望對每個 class $i$，都有一個對應的 function 叫做 discriminant function $g_i(x)$，來使得當我們把 input $x$（當初是 univariate，現在是 multivariate $\vec{x}$）代入每個 $g_i(x)$ 以後，我們能夠找出值最大的某個 $g_j(x)$，來決定 $\vec{x}$ 應該要分類到 class $j$。
> 關於 discriminant function，可參考筆記「[3.4 Discriminant Functions](https://hackmd.io/@pipibear/B1pu4naNR)」。

那麼現在我們把 discriminant function 訂為：


如果按照我們上面提到的假設，我們把現有條件再寫一次：


## discriminant function

我們可以把 $p(\vec{x}|C_i)$ 的這串式子代入 discriminant function：

> 前面我們將 discriminant function 訂為多取一個 $\log$，就是因為在這裡我們可以把乘法和指數轉為加減法來簡化計算。

# estimate discriminant function 裡的 parameters

有了綠色螢光筆這串醜醜的式子以後，因為不知道裡面那些值（例如 $\mu_i, \Sigma_i$⋯⋯）到底是什麼，所以我們仍然沒辦法代 $\vec{x}$ 進去、比 $g_i(\vec{x})$ 的大小，來知道 $\vec{x}$ 到底要歸類到哪個 class。因此我們又要像第四章在做的事一樣，去估計式子裡面那些 parameters 的值。

為了要知道 parameters 的值，因為我們無法取得 underlying population 的所有 data，所以我們要來取 sample，在假定 sample 取得好、能夠代表整個 population 的情況下，再來 estimate 這些未知的 parameters。

儘管是 multivariate case，但 sample 的概念還是一樣的，不過我們再把每個東西的意思寫清楚一點：


## different, hyperellipsoidal

標題的名稱可以先不用管，那代表的是在 estimate 未知的 paramters 時，我們的條件和結果。
> $\rightarrow$ 後面我們會看到在不同的條件下，取出不同 estimates 的情形。

前面我們推導出在 class $i$ 為 multivariate normal 的情況下，它的 discriminant function 為：

\begin{equation}
g_i(\vec{x}) = -\frac{d}{2}\log (2\pi) -\frac{1}{2}\log |\Sigma_i| - \frac{1}{2}(\vec{x} - \vec{\mu}_i)^T\Sigma_i^{-1}(\vec{x} - \vec{\mu}_i) + \log P(C_i)
\end{equation}

在這個式子裡面，我們需要估計的未知 paramters 有三個：

1. $P(C_i)$
2. $\vec{\mu}_i$
3. $\Sigma_i$

### estimates

透過 sample，我們對這三個 paramters 的 estimate 的 notation 如下方表示：

1. $P(C_i) \Rightarrow \hat{P}(C_i)$
2. $\vec{\mu}_i \Rightarrow \bar{m}_i$
3. $\Sigma_i \Rightarrow S_i$

分別來算這三個 estimate：



### discriminant function

算好這些 estimates 以後，我們就可以代回 discriminant function，並且透過一些變數名稱的轉換，我們最後會得到 $g_i(\vec{x})$ 的式子如下：


得到 discriminant function 的形式以後，我們發現要估計的 parameters 值好像還蠻多的，實際上到底有幾個呢？有這麼多 parameters 需要被 estimate 又會發生什麼事？

### parameter 數量

我們先來看需要去 estimate 的 parameter 數量：


++當 $d$ 很大++（也就是 feature 的數目很多），且 samples 的大小很小時，covariance matrix $S_i$ 可能會是 singular，也就是不存在 $S_i^{-1}$；或者 $|S_i| = \det(S_i)$ 可能不為零（$S_i$ 可逆），但是這個值可能很小，使得它 ++unstable++，$S_i$ 一點小小的改變就會使 $S_i^{-1}$ 產生很大的變動。

為了讓我們的 estimates 在即使 samples 很小的情況下也是 reliable 的，我們就會想去++降低 dimensionality $d$++。這件事如何去達到，可能是透過從現有的 features 中去取一個 subset，或是用某種方式去結合現有的 features，關於這些方法我們會在第六章中說明。

## shared, hyperellipsoidal

這裡我們用一種方法，就是把我們的 data 結合在一起，去 estimate 一個所有 classes 都可以共用的共同 covariance matrix $S$：


前面我們讓每個 $g_i(\vec{x})$ 在代入 sample estimates 都用各自的 $S_i$，現在我們改成用這個共同的 $S$ 代入：

> 需要估計的 paramters 數目變成 $K$ 個 $g_i(\vec{x})$ 都用同個 covariance matrix $S$，所以全部只要 $\frac{d(d+1)}{2}$ 個 entries 的 estimate；至於 $\bar{m}_i$ 不變，還是每個 $g_i(\vec{x})$ 各 $d$ 個。

### prior 相同／不同的情形

#### 相同：MD

有了這個代入 estimates（且用共同的 $S$）的 $g_i(\vec{x})$ 以後，我們分別考慮兩種情形，一種是當 priors 相同、一種是 priors 不同：


#### 不同：linear classifier

不同的情況下可以省略一項 $\vec{x}^TW_i\vec{x}$，使 $g_i(\vec{x})$ 變成 linear discriminant：

> - 為什麼 prior 的值不同會將 decision boundaries 平移是因為在 $g_i(\vec{x})$ 的式子裡我們可以看到 prior probabilities $P(C_i)$ 只有出現在 $w_{i0}$ 中，不會受 $\vec{x}$ 的改變而影響。
>> 想像 $y = 2x + 3$ 和 $y = 2x + 5$ 就知道為什麼是 prior probabilities 造成的是 prarallel shift 啦！
> - 如果我們沒有 assume 這個共同的 covariance matrix，而是像前面一開始的做法，讓每個 class conditional density $p(\vec{x}| C_i)$ 有自己的 covariance matrix $\Sigma_i$，那這項 $\vec{x}^TW_i\vec{x}$ 就不能省略，於是我們就會得到 $\vec{x}$ 的 quadratic function，也就是說不是 linear discriminant 而是 quadratic discriminant。

這樣的 linear classifier 會使 decision region 是 convex 的，我們先來定義 <font color = "snake">convex</font>：

:::info
Decision regions of such linear classifier are convex; namely, ++when two points are chosen arbitrarily in one decision region and are connected by a straight line, all the points on the line will lie in the region.++
:::


## shared, axis-aligned: Naive Bayes Model

如果我們再進一步假設：

:::info
conditioned on class $K$ 的情況下，$X_i$ 之間為 independent variables。
:::
> 也就是說在 class $K$ 裡的那些點 $\vec{X} = [\,X_1...X_d]\,^T$，它們的 input variables $X_1,...,X_d$ 的 distribution independent。
>
> $\rightarrow$ 為什麼要這樣做，是因為我們希望用 conditional independence 的假設來++簡化我們的 model++。
> - 假設 ++conditional independence++ 是一種 classification 的方法，稱作 <font color = "snake">naive Bayes model</font>。
>> 但是我們可以這樣想像現實的情境，就會發現這樣的假設其實不符合現實情況。比如說如果我們在做關於健康狀況的研究，那麼 features 可能會有「運動量」、「卡路里攝取」等等，Naive Bayes 假設在給定某個 class（好比說「BMI 為肥胖」的群體）的情況下，這些 features 的分佈不會互相影響，但是其實很有可能是「運動量」和「卡路里攝取」之間息息相關，至少不會是完全獨立的。
>>
>> 因此 Naive Bayes 雖然讓計算簡化了，但也代表這樣的 model 比較沒辦法去 capture features 之間複雜的 dependencies。

總之，透過這樣的假設，就會使得 covariance matrix 對角線以外的 entries 為零，也就是說 $S$ 為對角矩陣（因此 $S^{-1}$ 也會是對角矩陣），達到簡化的目的：
> Recall：Covariance matrix 的非對角項為各個 features 之間的 covariance。


可以看個圖回顧一下我們之前講說：

假設一個 random vector $\vec{X} = [\,X_1,...,X_d]\,^T$ 是 multivariate Gaussian，那麼它之中的每個 $X_i \quad i=1,...,d$ 都是 univariate Gaussian。現在套用到限制在 $C_i$ 也一樣。


其實 Naive Bayes 並沒有假設要用一個共同的 covariance matrix，只有 assume conditioned on 某個 class 的情況下，各個 feature 之間的 distribution independent。

### discriminant function

但是在此我們假設既用 Naive Bayes，也用共同的 covariance matrix。

在這樣的條件下，我們發現給定某個 class $i$ 的情況下， $C_i$ 裡的點的每個 feature $j$ 的分佈滿足：

\begin{equation}
p(x_j|C_i) \sim N(m_{ij},s_j^2)
\end{equation}
> 其中 $s_j^2$ 是共同的 covariance matrix $S$ 的對角項。

Recall：我們假設 naive bayes 意味的是在限制條件為 $C_i$ 的情況下各個 features 間 independent；而 variables independent 代表 joint distribution 的 pdf 可拆成各別的每個 pdf 相乘。

所以代入每個 feature 的 pdf（即 $N(m_{ij},s_j^2)$ 的 pdf）再相乘以後，我們會得到 log likelihood，加上 estimated 的 log prior，再捨棄常數項，就能得到 discriminant function。

詳細過程如下：

> 其中 $\frac{x_j - m_{ij}}{s_j}$ 有 normalization 的效果，並且會用 standard deviation $s_j$ 為單位來衡量距離。

### parameter 數量

在上述這樣的條件下，我們發現總共需要 estimate 的 parameters 確實變少了！從最後 $g_i(\vec{x})$ 的式子裡我們可以看到：

$\rightarrow$ 因為 $S$ 為一個 $d \times d$ 的對角矩陣，所以我們只有 $d$ 個 variances $s_j^2$ 需要估計；以及 $K$ 個 classes，每個 class 有自己的各個 feature 的 mean $m_{ij}$（代表 class $i$ feature $j$ 的 mean），每個 class 共 $d$ 個 features，因此總共 $K \times d$ 個 parameters。

整理清楚一點對比一下差距：


### 圖像說明

我們可以用幾何的角度來看我們從剛剛到現在在做的事情：

> 如果我們總共有兩個 classes，假設只看 class $1$ 的點的情況下，這些點的 distribution 是 multivariate Gaussian，也就是圖中左側的那個 bell-curve；只看 class $2$ 也同理，畫出 probability distribution 就是右側的那個 bell-curve。
>
> 根據機率高低，我們用不同的顏色表示（由紅橙黃綠⋯⋯的順序來表示機率由高到低），投影在平面上就形成 contour plot。
>
> 按照圖上的說明，prior probability 相同，$p(w_1) = p(w_2)$，所以我們可以看到 decision boundary 在兩個 hyperellipsoid 的正中間，並沒有偏向哪一方；且這個 decision boundary 形成兩個 decision region $R_1,R_2$。
>
> 除了 prior 會決定 decision boundary 會比較靠哪個 class，我們剛剛在 estimate 的 $S$，也決定了 contour plot 的那些橢圓的角度和形狀。

至於我們剛剛用到的 naive bayes，因為 covariance 皆為零（conditional independent），所以 contour plot 大概會長這樣：

> 關於 covariance matrix 在不同的 variance, covariance 的情況下會有什麼樣的形狀，可參考筆記「[5.4 Multivariate Normal Distribution](https://hackmd.io/@pipibear/SkgL8C3OA)」。

這樣一來，我們就能去判斷一個 input $\vec{x}$ 應該要被分到哪個 class，如下圖：


## shared, hyperspheric

到這邊，雖然我們的 model 已經簡化了許多，但是如同前第二張圖，我們說雖然每個 class 共用同一個 covariance matrix $S$，但是裡面對角項的 entries $s_j^2$ 卻不一定相同；假如我們想再更簡化，如果我們讓這些 variances 都相同，也就是 $s_1^2 = s_2^2 =...=s_d^2$，那會怎麼樣呢？

答案其實我們在筆記「[5.4 Multivariate Normal Distribution](https://hackmd.io/@pipibear/SkgL8C3OA)」和「[補充：multivariate outliers](https://hackmd.io/@pipibear/rkalaWUtR)」都講到過：

:::warning
如果 variances 都相同，Mahalanobis distance (MD) 會退化成 Euclidean distance。
:::

如下圖：

> 圖中每個圈代表落在這個圈上的點具有相同的 probability，像以前地理課中等高線的概念。為什麼我們說 variances 都相同時，MD 會退化成 Euclidean distance，也就是一般我們計算距離的方式，是因為：
>
> 當我們在考量一個點和比如說中心的距離時，如果是前面的 hyperellipsoid，圍繞中心的橢圓儘管有長軸和短軸，但是在同個橢圓上的距離都是相同的，這是因為考量不同 variances 的緣故；可是當 variances 都相同時，一個圓上的任何一個點本來就都和中心的距離相同，所以以這樣的方式去考量距離就失去了 MD 的意義，退化為一般的方式。
>> 這些內容都在上面提到的筆記有更詳細的說明。

這樣的情況下會有什麼樣的影響，如下圖：


### discriminant function

至於 discriminant function，則是會變成：


### nearest mean classifier

在這樣的基礎上，如果又～要再簡化，我們又假設 prior 相同，最後會得到很精簡的式子：


$\rightarrow$ 這樣的 discriminant function 稱作 <font color = "snake">nearest mean classifier</font>。
> 其實就是字面上的意思。recall 我們在決定一個 input $\vec{x}$ 要分類到哪個 class 時，是去選擇 $K$ 個 discriminant functions 中，代入 $\vec{x}$ 後的值最大的那個。
>
> 因此如果今天 $\vec{x}$ 和某個 class $i$ 的 mean $\vec{m}_i$ 很接近，那 $||\vec{x} - \vec{m}_i||^2$ 就會小，$-||\vec{x} - \vec{m}_i||^2$ 就會大，我們就越有可能把 $\vec{x}$ classify 到 $C_i$。

這樣的想法代表將一個 class 的 mean 視為這個 class 的 ideal prototype 或 template，所以我們去找各個 class 裡的 mean 裡，最接近 $\vec{x}$ 的那一個，就是一個 <font color = "snake">template matching</font> 的過程。

對這個 nearest mean classifier，如果我們回過來又把它展開，就會發現它又變回了 linear classifier 的形式：


這個時候，如果每個 class mean 的長度都差不多，也就是 $||\vec{m}_i||^2$ 的值差不多，那我們再把這項省略掉，就會是：

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

這代表的意思是，當我們可以去比較 $\vec{m}_i$ 的 norm 時，我們就可以用 dot product $\vec{w}_i^T\vec{x} = \vec{m}_i^T\vec{x}$ 來取代前面（負的）Euclidean distance $-||\vec{x} - \vec{m}_i||^2$。

# 總結

## distance function

但是這又能怎麼樣？代表了什麼？其實最終可以下一個結論：

:::warning
我們可以把「去找出最好的 discriminant function」這件事，想成「去找出最好的 distance function」。
:::

也就是說，在 classification 裡，與其去 learn discriminant functions $g_i(\vec{x})$，我們其實是想去 learn 一種最適合的 distance function ==$D(\vec{x}_1,\vec{x}_2)$==：

:::success
We want to learn the suitable distance function $D(\vec{x}_1,\vec{x}_2) \ni$
\begin{equation}
\text{for any } \vec{x}_1,\vec{x}_2,\vec{x}_3 \quad \text{where } \vec{x}_1,\vec{x}_2 \in C_i \quad \vec{x}_3 \in C_j \quad i \ne j
\end{equation}

\begin{equation}
D(\vec{x}_1,\vec{x}_2) < D(\vec{x}_1,\vec{x}_3)
\end{equation}
:::
> 意思很簡單，就是我們想要找到一個適合的計算距離的 function，使得在同個 class 裡的點之間的距離，一定比在不同 classes 裡的點的距離小。

## 各類型整理

最後，下表為不同的假設下我們的 covariance matrix 需要 estimate 的 parameters 數量：

> 表中的字代表的意義：
> - shared $\Rightarrow$ 不管哪個 class，都用共同的 covariance matrix $S$
> - different $\Rightarrow$ 最開始我們假設每個 class 有自己的 covariance matrix
> - hyperspsheric $\Rightarrow$ contour plot 的樣子是多個同心圓，因為我們假設 naive Bayes 且共同的 covariance matrix 中對角項都相同。
> - axis-alligned $\Rightarrow$ covariance 都是零，代表 contour plot 的樣子長軸和短軸分別和兩軸平行。
> - hyperellipsoidal $\Rightarrow$ 如果沒假設 variances 都相同的情況下，contour plot 的樣子是很多個同心的橢圓。

# 參考資料
- Christopher Bishop, Pattern Recognition and Machine Learning, p.199, 380-381