Skip to content

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}$