Fisher's Linear Discriminant (FDA, LDA, QDA)
引言
給定資料 $(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}$