LDA（线性判别分析，Linear Discriminant Analysis）

读完周志华教授的《机器学习》中的线性判别分析章节，他从LDA实现的效果角度对其进行了推导：类间间距要尽可能大，类内间距尽可能小的基本思想通过拉格朗日乘子法可以简单解出想要的结果。但是在章节的最后，教授提到：LDA可以从贝叶斯决策理论的角度来阐释，并可证明，当两类数据同先验、满足高斯分布且协方差相等时，LDA可达到最优分类。

今天，我们从贝叶斯理论的角度来阐释一回神奇的LDA.

---

贝叶斯定理

我们先从条件概率入手：
$\begin{aligned} P(A|B)&=\frac{P(A\cap B)}{P(B)}\\ P(B|A)&=\frac{P(B\cap A)}{P(A)}\\ \end{aligned}$P(A∣B)P(B∣A)​=P(B)P(A∩B)​=P(A)P(B∩A)​​
显然有$P(A\cap B)=P(B\cap A)$P(A∩B)=P(B∩A)，则可推导出贝叶斯定理：
$P(A|B)=\frac{P(B|A)\cdot P(A)}{P(B)}$P(A∣B)=P(B)P(B∣A)⋅P(A)​
贝叶斯公式可以解释为：事件B的发生是由事件A导致的概率。

---

LDA模型

将上述公式应用到我们的分类问题上来，我们可以改写这个公式。
$P(Y=k|X=x)=\frac{P(X=x|Y=k)\cdot P(Y=k)}{P(X=x)} \qquad(1)$P(Y=k∣X=x)=P(X=x)P(X=x∣Y=k)⋅P(Y=k)​(1)
在LDA中我们使用高斯分布，这样，我们来改写(1)式中的三项因子。
首先是$x$x在$k$k这个类别的类条件概率，建设我们的数据在每个类别上都是一个n维高斯分布。则：
$P(X=x|Y=k)=P_k(x)=\frac{1}{(2\pi)^{n/2}|\Sigma_k|^{1/2}}exp[-\frac{1}{2}(x-\mu_k)^T\Sigma_k^{-1}(x-\mu_k)] \qquad(2)$P(X=x∣Y=k)=Pk​(x)=(2π)n/2∣Σk​∣1/21​exp[−21​(x−μk​)TΣk−1​(x−μk​)](2)
其次是$k$k类的先验概率：
$P(Y=k)=\pi_k \qquad(3)$P(Y=k)=πk​(3)
最后是$P(X=x)$P(X=x)：
$P(X=x)=\sum_{i=1}^kP_i(x)\pi_i\qquad(4)$P(X=x)=i=1∑k​Pi​(x)πi​(4)
注意，在LDA模型中，我们假设所有类别的协方差矩阵是相等的，即：
$\Sigma_k=\Sigma \quad \forall k \qquad(5)$Σk​=Σ∀k(5)
将式子(2),(3),(4),(5)代入式子(1)我们可以得到：
$P(Y=k|X=x)=\frac{P_k(x)\cdot \pi_k}{P(X=x)} =\frac{\{\frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}exp[-\frac{1}{2}(x-\mu_k)^T\Sigma^{-1}(x-\mu_k)] \}\cdot \pi_k}{\sum_{i=1}^kP_i(x)\pi_i}\qquad (6)$P(Y=k∣X=x)=P(X=x)Pk​(x)⋅πk​​=∑i=1k​Pi​(x)πi​{(2π)n/2∣Σ∣1/21​exp[−21​(x−μk​)TΣ−1(x−μk​)]}⋅πk​​(6)
对式子(6)取对数。并去除仅与$x$x有关的项（如分母)，常数项（分子中exp之前的项，展开后仅与$x$x和$\Sigma$Σ有关的项），我们可以清晰地定义出判别函数（Discriminant functions）$\delta_k(x)$δk​(x)：
$\begin{aligned} \delta_k(x)&=(\Sigma^{-1}\mu_k)^Tx-\frac{1}{2}\mu_k^T\Sigma^{-1}\mu_k+log\pi_k \qquad(7)\\ C(x)&=\underset{k}{\mathrm{arg\ min}} \delta_k(x) \qquad(8) \end{aligned}$δk​(x)C(x)​=(Σ−1μk​)Tx−21​μkT​Σ−1μk​+logπk​(7)=karg min​δk​(x)(8)​

---

参数估计

从上面的模型我们可以看出，对于LDA，我们有三个大方面的参数需要估计，$\pi_k,\mu_k,\Sigma$πk​,μk​,Σ.
我们需要从联合概率的最大似然函数出发去进行参数估计。也正是因为LDA需要计算来联合概率$P(x_i,y_i)$P(xi​,yi​)，LDA被称之为生成模型（Generative model）。与之对应的是判别模型（Discriminative model），比如我们熟悉的逻辑回归。
$\begin{aligned} L(\theta)=\prod_{i=1}^mP(x_i,y_i)&=\prod_{i=1}^mP(x_i\mid y_i)\cdot P(y_i)\\ &=\prod_{i=1}^m\prod_{k=1}^KP_k(x_i)^{y_{ik}}\cdot \pi_k^{y_{ik}}\\ &=\prod_{i=1}^m\prod_{k=1}^K\phi(x_i,\mu_k,\Sigma)^{y_{ik}}\cdot \pi_k^{y_{ik}}\\ y_{ik}&=\mathbb{I}(y_i=k)\\ \end{aligned}$L(θ)=i=1∏m​P(xi​,yi​)yik​​=i=1∏m​P(xi​∣yi​)⋅P(yi​)=i=1∏m​k=1∏K​Pk​(xi​)yik​⋅πkyik​​=i=1∏m​k=1∏K​ϕ(xi​,μk​,Σ)yik​⋅πkyik​​=I(yi​=k)​
这样，我们可以得到参数的估计如下：
$\begin{aligned} \hat \pi_k&=\frac{m_k}{m}\quad m_k为k类的样本数，m为总样本数\\ \hat \mu_k&=\frac{1}{m_k}\sum_{i=1}^{m}y_{ik}\cdot x_i\\ \hat \Sigma &=\frac{1}{m}\sum_{k=1}^Km_k\hat \Sigma_k\\ \hat \Sigma_k&=\frac{1}{m_k}\sum_{i=1}^my_{ik}(x_i-\hat \mu_k)(x_i-\hat \mu_k)^T \end{aligned}$π^k​μ^​k​Σ^Σ^k​​=mmk​​mk​为k类的样本数，m为总样本数=mk​1​i=1∑m​yik​⋅xi​=m1​k=1∑K​mk​Σ^k​=mk​1​i=1∑m​yik​(xi​−μ^​k​)(xi​−μ^​k​)T​
这样得到的$\hat \Sigma$Σ^是有偏估计。真正的无偏估计如下：
$S=\frac{m}{m-K}\hat \Sigma$S=m−Km​Σ^

至此，我们完成了从贝叶斯角度对LDA的推导过程。

---

Python代码实现

https://github.com/Haifei-ZHANG/machine-learning-algorithms/tree/master/LDA