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