CS229 笔记 05

Nov 17 2017

生成学习方法

判别学习方法的主要思想是假设属于不同 target 的样本，服从不同的分布。

例如 $P(x|y=0) \sim {\scr N}(\mu_1,\sigma_1^2)$ ， $P(x|y=1) \sim {\scr N}(\mu_2,\sigma_2^2)$ 。

  • Gaussian Discriminant Analysis（高斯判别分析）

    在这里还是讨论 $y\in{0,1}$ 的二元分类问题， $P(y)=\phi^y(1-\phi)^{1-y}$。

    由于 $x$ 是一个向量，所以需要用到多元高斯分布。

    假设 $P(x|y=0) \sim {\scr N}(\vec{\mu_0}, \Sigma)$ ， $P(x|y=0) \sim {\scr N}(\vec{\mu_1}, \Sigma)$ 。

    $$ \begin{eqnarray*} &&l(\phi\mu_0\mu_1\Sigma)\\[1em] &=&\log\prod_{i=1}^{m}P(x^{(i)},y^{(i)}) \\[1em] &=&\log\prod_{i=1}^{m}P(x^{(i)}|y^{(i)})P(y^{(i)}) \\[1em] &=&\log\prod_{i=1}^{m}P(y^{(i)})\left[I\{y^{(i)}=1\}P(x^{(i)}|y^{(i)}=1)\right.\\[1em] &&\left.+I\{y^{(i)}=0\}P(x^{(i)}|y^{(i)}=0)\right] \\[1em] &=&\log\prod_{i=1}^{m}\left\{\frac{y\phi}{\sqrt{2\pi|\Sigma|}}\left[(x^{(i)}-\mu_1)^{\rm T}\Sigma^{-1}(x^{(i)}-\mu_1)\right]\right.\\[1em] &&\left.+\frac{(1-y)(1-\phi)}{\sqrt{2\pi|\Sigma|}}\left[(x^{(i)}-\mu_0)^{\rm T}\Sigma^{-1}(x^{(i)}-\mu_0)\right]\right\} \\[1em] \end{eqnarray*}\\ {\text{...}}\\ {\text{To be continue}}\\ {\text{...}} $$

    通过改变 $\phi,\mu_0,\mu_1,\Sigma$ 的值，使得似然函数 $l(\phi\mu_0\mu_1\Sigma)$ 最大化，此时各参数为：

    $$ \begin{eqnarray*} \phi&=&\frac{\sum_i^my^{(i)}}{m}=\frac{\sum_i^mI\{y^{(i)}=1\}}{m} \\[1em] \mu_0&=&\frac{\sum_i^m\left(I\{y^{(i)}=0\}\cdot x^{(i)}\right)}{\sum_i^mI\{y^{(i)}=0\}} \\[1em] \mu_1&=&\frac{\sum_i^m\left(I\{y^{(i)}=1\}\cdot x^{(i)}\right)}{\sum_i^mI\{y^{(i)}=1\}} \\[1em] \end{eqnarray*} $$

    训练完成之后，对于一个新样本，只需要看该样本更符合哪一个模型即可：

    $$ \begin{eqnarray*} h(x)&=&\arg \max_y P(y|x) \\[1em] &=&\arg \max_y \frac{P(x|y)P(y)}{P(x)} \\[1em] &=&\arg \max_y P(x|y)P(y) \\[1em] \end{eqnarray*} $$

  • 高斯判别分析与逻辑回归的关系

    若样本的两部分分别来自两个参数不同的高斯分布，则后验分布函数 $P(y=1|x)$ 就是 Logistic 函数。

    $$ \begin{eqnarray*} P(y=1|x)&=&\frac{P(x|y=1)P(y=1)}{P(x)}\\[1em] &=&\frac{\frac{\phi}{\sqrt{2\pi|\Sigma|}}\left((x-\mu_1)^{\rm T}\Sigma^{-1}(x-\mu_1)\right)}{\frac{\phi}{\sqrt{2\pi|\Sigma|}}\left((x-\mu_1)^{\rm T}\Sigma^{-1}(x-\mu_1)\right)+\frac{1-\phi}{\sqrt{2\pi|\Sigma|}}\left((x-\mu_0)^{\rm T}\Sigma^{-1}(x-\mu_0)\right)}\\[1em] &=&\frac{\phi\left((x-\mu_1)^{\rm T}\Sigma^{-1}(x-\mu_1)\right)}{\phi\left((x-\mu_1)^{\rm T}\Sigma^{-1}(x-\mu_1)\right)+(1-\phi)\left((x-\mu_0)^{\rm T}\Sigma^{-1}(x-\mu_0)\right)}\\[1em] \end{eqnarray*}\\ {\text{...}}\\ {\text{To be continue}}\\ {\text{...}} $$

    不仅如此，若样本的两部分分别来自两个参数不同的同样的指数分布族分布，则后验分布函数 $P(y=1|x)$ 也是 Logistic 函数。

    因此「假设样本的两部分都来自高斯分布」 比「假设样本的后验分布函数是 Logistic 函数」有更强的约束性，利用了更多的已知信息，所以相对来说高斯判别分析需要较少的训练样本就能达到较好的效果。

    当决定采用逻辑回归，就意味着选择了一个约束较少的假设，这样就会有更强的泛化能力。与此同时也就意味着需要更多的样本来训练模型。

朴素贝叶斯

首先定义符号：

训练样本为 $\left(x^{(1)},y^{(1)}\right),\left(x^{(2)},y^{(2)}\right),\cdots,\left(x^{(m)},y^{(m)}\right)$ ， $x^{(i)}\in{0,1}^n$ ， $y^{(i)}\in{0,1}$ 。

  • 假设

    朴素贝叶斯方法一个很重要的特点是，它有一个很强的假设：

    假设给定 $y$ 之后， $x_j$ 之间是彼此条件独立的，即：

    $$ P(x_1,x_2,\cdots,x_n|y)=P(x_i|y)P(x_2|y) \cdots P(x_n|y) $$

  • 参数及其训练推导

    朴素贝叶斯算法中有如下参数：

    $$ \begin{eqnarray*} \phi_{j|y=0}&=&P(x_j|y=0)\\[1em] \phi_{j|y=1}&=&P(x_j|y=1)\\[1em] \phi_{y=1}&=&P(y=1)\\[1em] \phi_{y=0}&=&1-P(y=1)\\[1em] \end{eqnarray*} $$

    似然函数：

    $$ \begin{eqnarray*} &&l(\phi_{y=0}\phi_{y=1}\phi_{j|y=0}\phi_{j|y=1}\cdots)\\[1em] &=&\log\prod_i^mP(x^{(i)},y^{(i)})\\[1em] &=&\log\prod_i^m\left[P(x^{(i)}|y^{(i)}=0)P(y^{(i)}=0)\right.\\[1em] &&\left.+P(x^{(i)}|y^{(i)}=1)P(y^{(i)}=1)\right]\\[1em] &=&\log\prod_i^m\left[\prod_j^nP(x^{(i)}_j|y^{(i)}=0)P(y^{(i)}=0)\right.\\[1em] &&\left.+\prod_j^nP(x^{(i)}_j|y^{(i)}=1)P(y^{(i)}=1)\right]\\[1em] &=&\log\prod_i^m\left[\prod_j^n\phi_{j|y=0}\phi_{y=0}+\prod_j^n\phi_{j|y=1}\phi_{y=1}\right]\\[1em] \end{eqnarray*}\\ {\text{...}}\\ {\text{To be continue}}\\ {\text{...}} $$

    最大化似然函数，求得：

    $$ \begin{eqnarray*} \phi_{j|y=0}&=&\frac{\sum_i^mI\{x^{(i)}_j=1,y^{(i)}=0\}}{\sum_i^mI\{y^{(i)}=0\}}\\[1em] \phi_{j|y=1}&=&\frac{\sum_i^mI\{x^{(i)}_j=1,y^{(i)}=1\}}{\sum_i^mI\{y^{(i)}=1\}}\\[1em] \phi_{y=0}&=&\frac{\sum_i^mI\{y^{(i)}=0\}}{m}\\[1em] \phi_{y=1}&=&\frac{\sum_i^mI\{y^{(i)}=1\}}{m}\\[1em] \end{eqnarray*} $$

  • 预测

    预测函数为：

    $$ \begin{eqnarray*} h(x)&=&\arg \max_y P(y|x)\\[1em] &=&\arg \max_y \frac{P(x|y)P(y)}{P(x)}\\[1em] &=&\arg \max_y P(x|y)P(y)\\[1em] &=&\arg \max_y \prod_j^nP(x_j|y)P(y)\\[1em] &=&\arg \max_y \prod_j^n\phi_{j|y}\phi_y\\[1em] \end{eqnarray*} $$ ​

  • Laplace Smoothing

    当遇到一些在训练集未出现过的样本时，以上的算法会失效，所以可以考虑在估计参数时增加一些噪声。

Machine Learning