Fisher's Linear Discriminant (FDA, LDA, QDA)

一種監督式學習的機器學習模型，根據資料常態假設做的線性分類模型

2024/03/24

引言

給定資料 $(X, Y) \iid P_{X, Y}$ ，其中 $Y \in \{ \conti{K} \} = \mathcal Y$ 是類別型的，根據貝氏定理

\begin{align*} P (Y = k | X = x) & = \frac{P (X = x | Y = k) P (Y = k)}{\sum_{u \in \mathcal Y} P (X = x | Y = u) P (Y = u)} \end{align*}

左側的 $P (Y = k | X = x)$ 就是目標函數，用於描述 “給定 $x$ 的條件下， $Y$ 是第 $k$ 類的機率”。

若 $G (x)$ 是 $Y$ 的預測函數，在 0-1 loss function $L (Y, G (x)) = I (Y \ne G (x))$ 情況下，則「最小化 Bayes Risk 的 $G$ 」同時也是「最大化 $P (Y = y | X = x)$ 的解」

\begin{align*} G (x) & = \argmin_{G \in \mathcal F} E_{Y | x } L (Y, G (x)) \newline & = \argmax_{k \in \mathcal Y} P (Y = k | X = x) \newline & = \argmax_{k \in \mathcal Y} P (X = x | Y = k) P (Y = k) \end{align*}

Fisher’s Linear Discriminant 是藉由分配假設，將資料視為 $K$ 群 normal，藉此找到在給定 $x$ 的條件下，能使 $P (Y = k | X = x)$ 最大化的 $k$ 。

模型假設

在 $P (Y = k | X = x)$ 的等式中有兩部分需要運算，分別是 $P (Y = k)$ 與 $P (X = x | Y = k)$ 。此時會假設

$P (Y = k) = \pi_k$
$X | Y = k \sim N_p (\mu_k, \Sigma_k)$

對於 $\pi_k$ 通常直接採用第 $k$ 類所佔比例直接估計且 $\sum_{k \in \mathcal Y} \pi_k = 1$ 。對於常態假設，理解為「不同群的 $Y = k$ ，其 $X$ 分屬於不同群體的 normal 群體。」寫作

\begin{align*} f_k (x) & = P (X | Y = k) \newline & = \frac{1}{(2 \pi)^{p / 2} |\Sigma_k|^{1/2}} \exp \left[ - \frac{1}{2} (x - \mu_k)^T \Sigma_k^{-1} (x - \mu_k) \right] \end{align*}

模型在此分成兩種，若假設

$\Sigma_k$ 相同，則此分類問題稱為 linear discriminant analysis (LDA)
$\Sigma_k$ 不同，則此分類問題稱為 quadratic discriminant analysis (QDA)

Base Line Method

以第 $K$ 項作為 base line，比較在給定 $x$ 時， $Y$ 為何類的機率最高

\begin{align*} G (x) & = \argmax_{k \in \mathcal Y} P (X = x | Y = k) P (Y = k) \newline & = \argmax_{k \in \mathcal Y} \ln \left[ \frac{P (Y = k | X = x)}{P (Y = K | X = x)} \right] \newline & = \argmax_{k \in \mathcal Y} \ln \left( \frac{f_k (x)}{f_K (x)} \right) + \ln \left( \frac{\pi_k}{\pi_K} \right) \end{align*}

會選擇將兩項對除的理由是，能消除常數項；取 $\ln$ 的理由是，且此機率有關 normal 分布，能與 $\exp$ 對消。

Linear Discriminant Analysis (LDA)

假設 $\Sigma_k = \Sigma$ 全部相同

\begin{align*} & \ln \left( \frac{f_k (x)}{f_K (x)} \right) + \ln \left( \frac{\pi_k}{\pi_K} \right) \newline = & \ x^T \Sigma^{-1} (\mu_k - \mu_K) - \frac{1}{2} (\mu_k + \mu_K)^T \Sigma^{-1} (\mu_k - \mu_K) \end{align*}

其中的 $K$ 有關次項在 $G (x)$ 最大化的目標 $\argmax_{k \in \mathcal Y}$ 不起作用，因此等價於

\begin{align*} G (x) & = \argmax_{k \in \mathcal Y} \ln \left( \frac{f_k (x)}{f_K (x)} \right) + \ln \left( \frac{\pi_k}{\pi_K} \right) \newline & = \argmax_{k \in \mathcal Y} x^T \Sigma^{-1} \mu_k - \frac{1}{2} \mu_k^T \Sigma^{-1} \mu_k + \ln (\pi_k) \end{align*}

設其中的

\begin{align*} \delta_k (x) & = x^T \Sigma^{-1} \mu_k - \frac{1}{2} \mu_k^T \Sigma^{-1} \mu_k + \ln (\pi_k) \end{align*}

因此 $G (x) = \argmax_{k \in \mathcal Y} \delta_k (x)$ 。其中有數個參數需要估計

$\hat \mu_k = n_k / n$ ，其中 $n_K$ 是第 $k$ 類的數量， $n$ 是樣本總數
$\hat \mu_k = \sum_{y_i = k} x_i / n_k$
$\hat \Sigma = \sum_{k = 1}^{K} \sum_{y_i = k} (x_i - \hat \mu_k) (x_i - \hat \mu_k)^T / (n - K)$

Auadratic Discriminant Analysis (QDA)

假設 $\Sigma_k$ 是不同的，使得 base line 函式寫成

\begin{align*} \delta_k (x) & = -\frac{1}{2} (x - \mu_k)^T \Sigma_k^{-1} (x - \mu_k) - \frac{1}{2} \ln |\Sigma_k^{-1}| + \ln (\pi_k) \end{align*}

其中的

\hat \Sigma_k = \frac{1}{n_k} \sum_{y_i = k} (x_i - \hat \mu_k) (x_i - \hat \mu_k)^T

LDA vs QDA

這討論這兩個模型的好壞前，先了解到 LDA 與 QDA 並沒有 nested 的關係，例如線性回歸的 $f_1(x) = \beta_0 + \beta_1 x$ 與 $f_2(x) = \beta_0 + \beta_1 x + \beta_2 x^2$ ，可以透過 $H : \beta_2 = 0$ 的假設檢定，若 $\beta_2$ 顯著為 0 則 $f_2$ 會退化成 $f_1$ ，因此稱為 nested。由於 LDA 與 QDA 並不 nested，因此建議是兩種模型均嘗試。

若 $x \in \bb R^p$ ，則 LDA 需要估計 $\contia{\mu}{K}$ 與 $\Sigma$ ，大致上需要估計 $K p + p^2$ 個參數；相對於 QDA 需要估計更多 $\contia{\Sigma}{K}$ ，大致上需要估計 $K (p^2 + p)$ 個參數，眾多參數量使得 QDA 在小樣本，多分類情況下表現並不一定理想。

參數假設

QDA 假設每個群組都有不同的 $\Sigma_k$ ，雖然能更適用範圍更大，但複雜模型有太多參數需要估計，有時用更強的假設會得到更好的結果。

Normal

若 $X$ 的分布並非常態分布，可以考慮

降低維度
轉換 (ex: $x^{1/2}$ 、 $\ln (x)$ )

Variance-Covariance

假設 $\Sigma_k = \Sigma$ 都相同，即用 LDA 取代 QDA
Independent: 假設 $\Sigma = \text{diag} (\sigma_1^2, \sigma_2^2, \cdots, \sigma_p^2)$
Common variance: 假設 $\Sigma = \sigma^2 I_{p \times p}$

參考資料

The Element of Statistical Learning, Second Edition