lecture 5 : Gaussian Discriminant Analysis and Naive Bayes
前面我们学习的都是 discriminant learning algorthm, 直接对 \(p(y|x)\) 进行建模，或直接学习 \(X \to Y\) 的映射。GDA 和 naive bayes 是 generative learning algorithm, 对 \(p(x |y)\) 建模，再通过贝叶斯公式计算 \(p(y|x) = \frac{p(x|y)p(y)}{p(x)}\)
Gaussian Discriminant Analysis
对于输入，这里我们不再延续 \(x_0 = 1\) 的传统，\(x \in \mathbb{R}^n\)
assumption: \(x|y\) ~ \(N(\mu,\Sigma)\)
multivariate gaussian recap
如果随机变量 Z 服从高斯分布，即 \(Z\) ~ \(N(\mu, \Sigma)\), \(Z\in \mathbb{R}^n, \mu \in \mathbb{R}^n, \Sigma \in \mathbb{R}^{n\times n}\)
\[EZ = \mu\\ Cov(Z) = E((Z-\mu)(Z-\mu)^T)\\ p(x;\mu, \Sigma) = \frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)) \]对于二分类问题：
GDA model:
\(x|y = 0\) ~ \(N(\mu_0, \Sigma)\)
\(x|y=1\) ~ \(N(\mu_1, \Sigma)\)
\(y\) ~ \(Ber(\phi)\)
共有 \(\mu_0, \mu_1, \Sigma, \phi\) 这几个参数。
对于数据集 \(\{(x^{(i)},y^{(i)})\}_{i=1}^m\)
可以计算联合概率
\[L(\phi, \mu_0, \mu_1, \Sigma) = \prod_{i=1}^m p(x^{(i)},y^{(i)};\phi, \mu_0, \mu_1, \Sigma) \\ = \prod_{i=1}^m p(x^{(i)}|y^{(i)})p(y^{(i)})\\ l(\phi, \mu_0, \mu_1, \Sigma) = log(L(\phi, \mu_0, \mu_1, \Sigma)) \]最优化目标即为 \(l(\phi, \mu_0, \mu_1, \Sigma)\), 使用极大似然估计求得参数的估计值。
\[\phi = \frac{\sum_{i=1}^m 1\{y^{(i)} = 1\}}{m}\\ \mu_0 = \frac{\sum_{i=1}^m 1\{y^{(i)} = 0\} x^{(i)}}{\sum_{i=1}^m 1\{y^{(i)} = 0\}}\\ \mu_1 = \frac{\sum_{i=1}^m 1\{y^{(i)} = 1\} x^{(i)}}{\sum_{i=1}^m 1\{y^{(i)} = 1\}}\\ \Sigma = \frac{1}{m}\sum_{i=1}^m (x^{(i)} - \mu_{y^{(i)}})(x^{(i)} - \mu_{y^{(i)}})^T \]在最后做预测时，预测的标签为：
\(\underset{y} argmax \quad p(y|x) = \underset{y} argmax\quad \frac{p(x|y)p(y)}{p(x)} = \underset{y} argmax \quad p(x|y)p(y)\)
即找出后验概率最大的类别。
与逻辑回归的联系和比较
可以证明，
\[p(y = 1|x;\phi, \mu_0, \mu_1, \Sigma) = \frac{1}{1+exp(-\theta^T x)}, \theta = f(\phi, \mu_0, \mu_1,\Sigma) \]这就是 sigmoid 函数，可见 GDA 和 逻辑回归有某种联系。
下面分别看一下这两种模型：
- GDA
assumption :
\(x|y = i\) ~ \(N(\mu_i, \Sigma)\)
\(y\) ~ \(Ber(\phi)\)
- Logistic Regression
\(p(y=1|x) = \frac{1}{1+exp(-\theta^T x)}\)
可以证明 GDA's assumption implies LR's assumption, but LR's assumption does not implies GDA's assumption. 可见 GDA 做了一个更强的假设。
这使得我们在应用时应该合理地选择模型，如果我们能确定数据来源符合 GDA 的假设或者近似符合，那么 GDA 的效果往往会比逻辑回归好，即使数据集不大，这是因为更强的假设意味着我们告诉了模型更多的信息。（模型的信息来源：数据，假设）但是如果数据不符合 GDA 的假设，我们却采用 GDA 模型，那么效果的好坏就难以确定了，可能刚好还不错，也有可能很差，相比而言逻辑回归更加 robust。
Naive Bayes
用一个例子来讲解朴素贝叶斯模型 ： spam Email filter
首先考虑如何标识 input feature vector:
建立一个词典，将特征词放入词典，假设词典大小为 n，那么输入就是一个 n 维向量，如果第 i 个词出现，那么第 i 个分量为 1，否则为 0.
即 \(x \in \{0,1\}^n, x_i = 1\{\text{word i appears in email}\}\)
want to model: \(p(x|y), p(y)\)
如果 n = 10,000, 那么 x 有 \(2^{10,000}\) 种可能取值，那么 parameter vector 就有 \(2^{10,000} - 1\) 维，这是无法忍受的。
在朴素贝叶斯模型中，假设：
\(x_i\) s is conditionally independent given y.
在这个例子中，就是说，知道这个邮件是 spam email 这件事之后，知道 \(x_i\) 是否为 1 对知道 \(x_j\) 是否为 1 没有影响。
\[p(x_1, ...,x_n|y) = p(x_1|y)p(x2|x1, y) ....p(x_n|x1, ...,y)\\ = p(x_1|y) ... p(x_n|y) \]其中第一步不依赖于任何假设，第二步使用了朴素贝叶斯假设。
朴素贝叶斯模型有这些参数
\[\phi_{j|y=1} = p(x_j = 1|y=1)\\ \phi_{j|y=0} = p(x_j = 1| y = 0)\\ \phi = p(y = 1) \]和 GDA 类似，要求得这些参数，只要使联合概率最大化：
\[L(\phi_y, \phi_{j|y}) = \prod_{i=1}^mp(x^{(i)},y^{(i)};\phi_y, \phi_{j|y}) \]通过求偏导数求得：
\[\phi_y = \frac{\sum_{i=1}^m 1\{y^{(i)} = 1\}}{m}\\ \phi_{j|y} = \frac{\sum_{i=1}^m 1\{x_{j}^{(i)} = 1,y^{(i)} = 1\}}{\sum_{i=1}^m 1\{y^{(i)} = 1\}} \]在预测的时候，
\[p(y=1|x) = p(x|y=1)p(y=1)/p(x) \\= \prod_{i=1}^n p(x_i|y=1) p(y=1)/(\prod_{i=1}^n p(x_i|y=1)p(y=1) + \prod_{i=1}^n p(x_i|y=0)p(y=0)) \]后验概率最大的那一组即为预测的标签。