机器学习-白板推导4.2 线性分类——高斯判别模型

机器学习-白板推导4.2 线性分类——高斯判别模型

1. 高斯判别模型描述

Gaussian Discriminate Analysis——GDA 模型描述。

假定数据集：

$$\mathcal{D}=\{(x_1, y_1),(x_2, y_2),\cdots,(x_N, y_N)\}, \ 其中x_i\in\mathbb{R}^{p}，y_i\in\mathbb{R}，i=1, \ 2,\cdots,\ N。$$

数据矩阵为：

$$\begin{equation} X=(x_1, x_2, \cdots, x_N)^T= \begin{pmatrix} x_1^T \\ x_2^T \\ \vdots\\ x_N^T \\ \end{pmatrix} = \begin{pmatrix} x_{11} & x_{12} & \dots & x_{1p}\\ x_{21} & x_{32} & \dots & x_{2p}\\ \vdots & \vdots & \ddots & \vdots\\ x_{N1} & x_{N2} & \dots & x_{Np}\\ \end{pmatrix}_{N\times P} \end{equation}$$ $$\begin{equation} Y= \begin{pmatrix} y_1 \\ y_2 \\ \vdots\\ y_N \\ \end{pmatrix}_{N\times 1} \end{equation}$$

这里讨论高斯判别分析解决二分类问题，那么对于数据集$\{ (x_i, y_i)\}$, 有。数据集分成+1, -1两部分并增加以下约定：

$$\begin{array}{ll} C_1 = \left\{ x_i|y_i=1, i=1,2,\cdots,N_1 \right\} & \\ C_2 = \left\{ x_i|y_i=0, i=1,2,\cdots,N_2 \right\} & \\ \end{array}$$

其中，$|C_1|=N_1，|C_2|=N_2，且N_1+N_2=N$。

现在用bayes公式来生成模型：

$$p(y|x)=\frac{p(x|y)p(y)}{p(x)}=\frac{p(x,y)}{p(x)}\propto p(x,y)$$

其中，$p(y)$是先验Prior， $p(y|x)$是后验Posterior。

$$\hat y = \text{argmax }_{y \in {0, 1}} p(x|y)p(y)$$

2. 高斯判别模型建立

因为是二分类问题，可以假定先验概率符合伯努利分布，$p(y)\sim \text{Bernoulli Distribution}$.

$$\begin{array}{c|cc} \mathrm{y} & 1 & 0 \\ \hline \mathrm{p} & \varphi & 1-\varphi \end{array}$$

所以，其表达式为：

$$\begin{equation} p(y)= \left\{ \begin{array}{ll} \varphi^y & y=1 \\ (1-\varphi)^{1-y} & y=0 \end{array} \right. \Longrightarrow \varphi^y(1-\varphi)^{1-y} \end{equation}$$

我们假设两类别数据$p(x|y)$都符合高斯分布，其均值不同，但不同变量间的协方差矩阵一样，(其实协方差不一样结论也一样，只是计算复杂)因此有：

$$\begin{equation} p(x|y)= \left\{ \begin{array}{ll} p(x|y=1)\sim \mathcal{N}(\mu_1, \Sigma) & \\ p(x|y=0)\sim \mathcal{N}(\mu_2, \Sigma) & \\ \end{array} \right. \Longrightarrow \mathcal{N}(\mu_1, \Sigma)^y\mathcal{N}(\mu_2, \Sigma)^{1-y} \end{equation}$$

后验估计函数为：

$$\begin{equation} \begin{split} \mathcal{L}(\theta) = & \log\prod_{i=1}^Np(x_i,y_i) \\ = & \sum_{i=1}^N\log p(x_i,y_i) \\ = & \sum_{i=1}^N\log p(x_i|y_i)p(y_i) \\ = & \sum_{i=1}^N\left[ \log p(x_i|y_i)+ \log p(y_i) \right]\\ = & \sum_{i=1}^N\left[ \log \mathcal{N}(\mu_1, \Sigma)^{y_i}\mathcal{N}(\mu_2, \Sigma)^{1-y_i}+ \log \varphi^y_i(1-\varphi)^{1-y_i} \right]\\ = & \sum_{i=1}^N \log \mathcal{N}(\mu_1, \Sigma)^y_i + \sum_{i=1}^N \log \mathcal{N}(\mu_2, \Sigma)^{1-y_i}+ \sum_{i=1}^N \log \varphi^{y_i} + \sum_{i=1}^N \log (1-\varphi)^{1-y_i} \\ \end{split} \end{equation} \tag{1}$$

为了推导方便，记：

$$\begin{align} \mathcal{L}_1& = \sum_{i=1}^N \log \mathcal{N}(\mu_1, \Sigma)^{y_i} \\ \mathcal{L}_2& =\sum_{i=1}^N \log \mathcal{N}(\mu_2, \Sigma)^{1-y_i} \\ \mathcal{L}_3& =\sum_{i=1}^N \log \varphi^{y_i} + \sum_{i=1}^N \log (1-\varphi)^{1-y_i} \end{align} \tag{2}$$

那么上述函数可以表示为：

$$\theta = (\mu_1,\mu_2,\Sigma,\varphi) \qquad \hat{\theta} = \text{argmax }_{\theta} \mathcal{L}(\theta) \tag{3}$$

3. 参数求解

1. 求解$\varphi$

只有$\mathcal{L}_3$跟参数$\varphi$有关，对其求导得：

$$\begin{align} \frac{\partial \mathcal{L}_3}{\partial \varphi} &= \sum_{i=1}^Ny_i\frac{1}{\varphi} + \sum_{i=1}^N (1-y_i)\frac{1}{1-\varphi} = 0 \\ \Longrightarrow& \sum_{i=1}^N y_i(1-\varphi) - (1-y_i)\varphi = 0 \\ \Longrightarrow& \sum_{i=1}^N (y_i-\varphi) = 0\\ \Longrightarrow& \hat{\varphi} = \frac{1}{N} \sum_{i=1}^N y_i \end{align} \tag{4}$$

因为只有类别为$C_1$中$y_i = 1$, 式4可以简化成：

$$\hat{\varphi} = \frac{1}{N} \sum_{i=1}^{N_1} y_i = \frac{N_1}{N} \tag{5}$$

2. 求解$\mu$

因为$\mu_1$只跟$\mathcal{L}_1$部分有关, 展开后得：

$$\begin{align} &\sum_{i=1}^N\log \mathcal{N}(\mu_1,\Sigma)^{y_i} \\\\ = &\sum_{i=1}^Ny_i\log \frac{1}{(2\pi)^{\frac{p}{2}}|\Sigma|^{\frac{1}{2}}} \text{exp }\left\{ -\frac{1}{2}(x_i-\mu_1)^T\Sigma^{-1}(x_i-\mu_1) \right\}\\ = &\sum_{i=1}^Ny_i\log \frac{1}{(2\pi)^{\frac{p}{2}}|\Sigma|^{\frac{1}{2}}} - \sum_{i=1}^Ny_i (\frac{1}{2}(x_i-\mu_1)^T\Sigma^{-1}(x_i-\mu_1))\\\\ \end{align} \tag{6}$$

式6只有后半部分跟$\mu_1$有关，剔除前面部分并化简：

$$\begin{align} \mathcal{L}_{\mu_1} &= \sum_{i=1}^Ny_i (\frac{1}{2}(x_i-\mu_1)^T\Sigma^{-1}(x_i-\mu_1))\\ &= \frac{1}{2}\sum_{i=1}^Ny_i (x_i^T\Sigma^{-1} - \mu_1^T\Sigma^{-1})(x_i-\mu_1)\\ &= \frac{1}{2}\sum_{i=1}^N y_i( x_i^T\Sigma^{-1}x_i - x_i^T\Sigma^{-1}\mu_1 - \mu_1^T\Sigma^{-1}x_i +\mu_1^T\Sigma^{-1}\mu_1 )\\ \end{align} \tag{7}$$

因为$x_i$是$p \times 1$的，那么$\Sigma^{-1}$是$p \times p$， 所以$x_i^T\Sigma^{-1}\mu_1 = \mu_1^T\Sigma^{-1}x_i$ （都是实数）。并且$x_i^T\Sigma^{-1}x_i$跟$\mu_1$无关

进一步简化得：

$$\Delta = \frac{1}{2}\sum_{i=1}^Ny_i (- 2\mu_1^T\Sigma^{-1}x_i + \mu_1^T\Sigma^{-1}\mu_1) \tag{8}$$

对$\mu_1$求导得：

$$\frac{\partial \Delta}{\partial \mu_1} = \sum_{i=1}^N(-y_i\Sigma^{-1}x_i + y_i\Sigma^{-1}\mu_1)\tag{9}$$

令式9为0得：

$$\sum_{i=1}^N y_i\mu_1 = \sum_{i=1}^Ny_ix_i \Longrightarrow \hat{\mu_1}= \frac{\sum_{i=1}^Ny_ix_i}{\sum_{i=1}^Ny_i} =\frac{\sum_{i=1}^{N_1}x_i}{N_1}\tag{10}$$

式10最后简化原因：$y_i \in \{0, 1\}$，只有当$y_i=1$时，累加才有用，所以

$$\sum_{i=1}^Ny_ix_i =\sum_{i=1}^{N_1}x_i$$

因为对称性，同理可得$\hat{\mu_2} = \frac{\sum_{i=1}^{N_2}x_i}{N_2}$

3. 求解 $\Sigma$

跟$\Sigma$有关的只有$\mathcal{L}_1, \mathcal{L}_2$, 即：

$$\Omega = \sum_{i=1}^N \log \mathcal{N}(\mu_1, \Sigma)^{y_i} +\sum_{i=1}^N \log \mathcal{N}(\mu_2, \Sigma)^{1-y_i}\\ = \sum_{i=1}^N ({y_i}\log \mathcal{N}(\mu_1, \Sigma) + (1-y_i)\log \mathcal{N}(\mu_2, \Sigma)) \tag{11}$$

同样因为$y_i$要么0， 要么1，式11可以简化为：

$$\Omega = \sum_{i=1}^{N_1} \log \mathcal{N}(\mu_1, \Sigma) + \sum_{i=1}^{N_2} \log \mathcal{N}(\mu_2, \Sigma) \tag{12}$$

为了简化计算，我们先计算下：

$$\begin{align} \hat\Omega &= \sum_{i=1}^{N} \log \mathcal{N}(\mu, \Sigma) \\&= \sum_{i=1}^{N} \log \frac{1}{(2\pi)^{\frac{p}{2}} |\Sigma|^{\frac{1}{2}}} \exp (-\frac{1}{2}(x_i -\mu)^T \Sigma^{-1}(x_i-\mu)) \\ &= \sum_{i=1}^{N} \left [ \log \frac{1}{(2\pi)^{\frac{p}{2}} } -\frac{1}{2} \log |\Sigma| -\frac{1}{2}(x_i-\mu)^T\Sigma^{-1}(x_i-\mu) \right] \\&= \sum_{i=1}^{N}\log \frac{1}{(2\pi)^{\frac{p}{2}}} + \sum_{i=1}^{N}(-\frac{1}{2} \log |\Sigma| -\frac{1}{2}(x_i-\mu)^T\Sigma^{-1}(x_i-\mu)) \\&= C + \sum_{i=1}^{N}(-\frac{1}{2} \log |\Sigma| -\frac{1}{2}(x_i-\mu)^T\Sigma^{-1}(x_i-\mu) \\ &= C -\frac{1}{2} N \log |\Sigma| -\frac{1}{2}\sum_{i=1}^{N}(x_i-\mu)^T\Sigma^{-1}(x_i-\mu)\\ \end{align} \tag{13}$$

其中$\sum_{i=1}^{N}\log \frac{1}{(2\pi)^{\frac{p}{2}}} = C$, 简化计算。

首先，有下列公式：

$$\begin{gather} \text{tr}(AB) = tr(BA) \tag{14}\\ \text{tr} (ABC) = \text{tr}(CAB) = \text{tr}(BCA)\tag{15}\\ \frac{\partial tr(AB)}{\partial A} = B^T \tag{16}\\ \frac{\partial|A|}{\partial A} = |A|A^{-1} \tag{17}\\ \end{gather}$$

式16证明：Gradient of tr(AB)

式13对$\Sigma$求导得：

$$\begin{align} \frac{\partial \hat \Omega}{\partial \Sigma} &= -\frac{1}{2} N\frac{1}{|\Sigma|}|\Sigma| \Sigma^{-1} - \frac{1}{2} \frac{\sum_{i=1}^{N}\text{ tr} [ (x_i-\mu)^T\Sigma^{-1}(x_i-\mu) ] }{\partial \Sigma} \\ &= -\frac{1}{2} N \Sigma^{-1}-\frac{1}{2} \frac{\sum_{i=1}^{N}\text{ tr} [ (x_i-\mu)^T(x_i-\mu) \Sigma^{-1}] }{\partial \Sigma} \\ &=-\frac{1}{2} N \Sigma^{-1}-\frac{1}{2} \frac{\text{ tr} \sum_{i=1}^{N}[ (x_i-\mu)^T(x_i-\mu) \Sigma^{-1}] }{\partial \Sigma} \\ &= -\frac{1}{2} N \Sigma^{-1}-\frac{1}{2} \frac{\text{ tr} (NS \Sigma^{-1})}{\partial \Sigma} \end{align} \tag{18}$$

其中$S = \frac{1}{N}\sum_{i=1}^{N}(x_i-\mu)^T(x_i-\mu)$是协方差矩阵。

由式18写出式12：

$$\begin{align} \frac{\partial \Omega}{\partial \Sigma} &= -\frac{1}{2} N_1 \Sigma^{-1} - \frac{1}{2} \frac{\text{ tr} (N_1S \Sigma^{-1})}{\partial \Sigma} -\frac{1}{2} N_2 \Sigma^{-1} - \frac{1}{2} \frac{\text{ tr} (N_2S \Sigma^{-1})}{\partial \Sigma} \\ &= -\frac{1}{2}N \Sigma^{-1}-\frac{1}{2}(N_1S_1^T(-1)\Sigma^{-2} + N_2S_2^T(-1)\Sigma^{-2})\\ &=\frac{1}{2}(N_1S_1^T\Sigma^{-2} +N_2S_2^T\Sigma^{-2} -N \Sigma^{-1} ) \end{align} \tag{19}$$

令其为0得两边同乘以$\Sigma^{-2}$得：

$$N_1S_1 + N_2S_2 = N\Sigma \Longrightarrow \Sigma = \frac{N_1S_1 + N_2S_2 }{N}$$

可以理解为协方差矩阵等于各自协方差矩阵的加权和。

高斯判别分析总结：

1. 首先假设先验$p(y)$ 服从伯努利分布和似然 $p(x|y)$服从高斯分布，利用贝叶斯公式得到条件概率$p(y|x)$函数。
2. 利用极大似然估计求解最大值参数。

$$\begin{align} \hat{\varphi} &=\frac{N_1}{N} \\ \hat{\mu_1} &= \frac{\sum_{i=1}^{N_1}x_i}{N_1}\\ \hat{\mu_2} &= \frac{\sum_{i=1}^{N_2}x_i}{N_2}\\ \Sigma &= \frac{N_1S_1 + N_2S_2 }{N} \end{align}$$