Lecture 4: Classification: Probabilistic Generative Model¶
分類問題常被用在各種領域,例如:
- 金融交易成功與否
- 醫學診斷分類
- 手寫辨識
- 人臉辨試
課堂上的例子:根據寶可夢各屬性(features)去預測其類別(class)。
Training data:寶可夢的各屬性(features)及其類別(class)。
How to do Classification?¶
Classification as Regression?¶
像上圖右側,即使分類正確了,還是會因為遠大於 $1$,造成 loss 過大,因此不適合使用 regression。
此外,當類別超過 $2$ 種時,也會產生許多問題,因為這樣表示,各類別之間是有大小遠近關係的,但在分類問題這樣是不合理的。
Ideal Alternatives¶
-
Function (Model):
$$ f(x) = \begin{cases} g(x) > 0 & \text{output: class 1}, \\ \text{else} & \text{output: class 2} \end{cases} $$
-
Loss function:
$$L(f) = \sum_n \delta(f(x^n) \ne \hat y^n)$$
-
Find the best function
Bayes' Theorem¶
假設有兩個類別,我們想要估算來自 training data 的機率。
Given an $x$, which class does it belong to:
$$ P \left( C _ { 1 } | x \right) = \frac { P ( x | C _ { 1 } ) P \left( C _ { 1 } \right) } { P ( x | C _ { 1 } ) P \left( C _ { 1 } \right) + P ( x | C _ { 2 } ) P \left( C _ { 2 } \right) } $$
Generative Model:
$$ P ( x ) = P ( x | C _ { 1 } ) P \left( C _ { 1 } \right) + P ( x | C _ { 2 } ) P \left( C _ { 2 } \right) $$
Prior¶
舉例來說:我們挑選出 79 隻水系($C_1$)和 61 隻一般系($C_2$)的寶可夢,那麼
\begin{align} P(C_1) & = 79 / (79 + 61) = 0.56 \\ P(C_2) & = 61 / (79 + 61) = 0.44 \end{align}
Probability from Class¶
現在我們想要知道的事,從水系($C_1$)挑出一隻「海龜」的機率是多少?
Probability from Class - Feature¶
因為寶可夢的 features 太多,為了方便,我們只考慮兩項,Defense 和 SP Defense,並假設這 79 隻水系寶可夢都是由 Gaussian distribution sample 出來的。
Maximum Likelihood¶
因為每個點 $x$ 是獨立的,所以我們可以透過以下連乘來得出 $L(\mu, \Sigma)$
Likelihood of Gaussian with mean $\mu$ and covariance matrix $\Sigma$ = the probability of the Gaussian samples $x^1, x^2, x^3, \dots, x^{79}$:
$$L(\mu, \Sigma) = f_{\mu, \Sigma}(x^1) f_{\mu, \Sigma}(x^2) f_{\mu, \Sigma}(x^3) \dots f_{\mu, \Sigma}(x^{79})$$
所以我們的目的是,找出一個 $(\mu^*, \Sigma^*)$ 能讓上式的 likelihood 最大:
$$\mu^*, \Sigma^* = \arg \max_{\mu, \Sigma} L(\mu, \Sigma)$$
透過微分可得以下結果:
$$ \begin{aligned} \mu^* & = \frac 1 {79} \sum_{n = 1}^{79} x^n \\ \Sigma^* & = \frac 1 {79} \sum_{n = 1}^{79} (x^n - \mu^*)(x^n - \mu^*)^T \end{aligned} $$
所以我們可計算出:
現在可以開始分類了,
$$P(C_1 \mid x) = \frac{P(x \mid C_1) P(C_1)}{P(x \mid C_1) P(C_1) + P(x \mid C_2) P(C_2)}$$
其中,
- $P(C_1) = 79 / (79 + 61) = 0.56$
- $P(C_2) = 61 / (79 + 61) = 0.44$
$$P(x \mid C_1) = f_{\mu^1, \Sigma^1}(x) = \frac 1 {(2\pi)^{D / 2}} \frac 1 {|\Sigma^1|^{1 / 2}} exp \Big(- \frac 1 2 (x - \mu^1)^T (\Sigma^1)^{-1} (x - \mu^1) \Big)$$
$$P(x \mid C_2) = f_{\mu^2, \Sigma^2}(x) = \frac 1 {(2\pi)^{D / 2}} \frac 1 {|\Sigma^2|^{1 / 2}} exp \Big(- \frac 1 2 (x - \mu^2)^T (\Sigma^2)^{-1} (x - \mu^2) \Big)$$
若 $P(C_1 \mid x) > 0.5$,$x$ 就屬於 class 1(水系)
但結果卻不怎麼樣,因為參數太多了,可能有 overfit 疑慮。
Modifying Model¶
原本對兩個分佈(水系、一般系)都有對應的 covariance matrix ($\Sigma_1, \Sigma_2$),但這樣參數量太大,可能會 overfit,所以我們降低參數量去避免 overfit,只考慮一個 convariance matrix($\Sigma$),修改 loss function 如下:
$$L(\mu^1, \mu^2, \Sigma) = f_{\mu^1, \Sigma}(x^1) f_{\mu^2, \Sigma}(x^2) \cdots f_{\mu^1, \Sigma}(x^{79}) \times f_{\mu^1, \Sigma}(x^{80}) f_{\mu^1, \Sigma}(x^{81}) \cdots f_{\mu^1, \Sigma}(x^{140})$$
$\mu^1$ 和 $\mu^2$ 維持不變,$\Sigma = \frac{79}{140}\Sigma^1 + \frac{61}{140}\Sigma^2$
Three Steps¶
-
Function Set (Model):
輸入一個 $x$:$P(C_1 \mid x) = \frac{P(x \mid C_1) P(C_1)}{P(x \mid C_1) P(C_1) + P(x \mid C_2) P(C_2)}$
$$ \begin{cases} P(C_1 \mid x) > 0.5 & \text{output: class 1}, \\ \text{else} & \text{output: class 2} \end{cases} $$
-
Goodness of a function
The mean $\mu$ and covariance $\Sigma$ that maximizing the likelihood (the probability of generating data)
-
Find the test function: easy
Posterior Probability¶
$$ \begin{aligned} P(C_1 \mid x) & = \frac{P(x \mid C_1) P(C_1)}{P(x \mid C_1) P(C_1) + P(x \mid C_2) P(C_2)} \\ & = \frac 1 {1 + \frac{P(x \mid C_2) P(C_2)}{P(x \mid C_1) P(C_1)}} \\ & = \frac 1 {1 + e^{-z}} = \sigma(z) \end{aligned} $$
其中,$z = \ln \frac{P(x \mid C_1) P(C_1)}{P(x \mid C_2) P(C_2)}$ (sigmoid)
經過很長一段推導(這裡就不再贅述,可直接看老師投影片),可得出:
$$ \begin{aligned} P(C_1 \mid x) & = \sigma(z) \\ & = \sigma(w \cdot x + b) \end{aligned} $$
其中,
- $w^T = (\mu^1 - \mu^2)^T \Sigma^{-1}$
- $b = -\frac 1 2 (\mu^1)^T \Sigma^{-1} \mu^1 + \frac 1 2 (\mu^2)^T \Sigma^{-1} \mu^2 + \ln \frac{N_1}{N_2}$