cs229笔记4-生成学习算法

笔记4:生成学习算法 Genrative Learning algorithms,对应讲义Note2 Part4 ,对应Lecture5-6(25)

主要内容包括提及了生成学习法的意义,判别学习法和生成学习法的区别,并重点介绍了几种生成学习算法——高斯判别分析(Gaussian Discriminant Analysis,GDA)、朴素贝叶斯(Navie Bayes)、拉普拉斯平滑(Laplace Smoothing),以及针对文本分类问题的事件模型(Event models for text classification)。

课程地址:【Andrew Ng】机器学习 吴恩达 中文字幕 (2008版 CS229)_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

Genrative Learning algorithms 生成学习算法简介

Discriminative Learning algorithm判别学习法

之前的课程中讲到的方法都是直接对问题进行求解,如二类分类问题,不管是感知器算法还是逻辑斯蒂回归算法,都是在解空间中寻找一条直线从而把两种类别的样例分开,对于新的样例只要判断在直线的哪一侧即可;这种直接对问题求解的方法可以成为判别学习方法(discriminative learning algorithm)

Discriminative

  • learns $p(y|x)$
  • or learns $h_\theta(x)\in\{0,1\}$ directly

Generative Learning algorithm生成学习法

生成学习算法(Discriminative Learning algorithm)则是对两个类别分别进行建模,用新的样例去匹配两个模型,匹配度较高的作为新样例的类别,比如良性肿瘤与恶性肿瘤的分类,首先对两个类别分别建模,用新的肿瘤样本去匹配两个模型,匹配度较高的作为该肿瘤类别判断。

Generative

  • learns $p(x|y)$ and $p(y)$

    $x$ 是样本的特征,$y$ 是样本所属类

    一个生成模型对样本特征建立概率模型,在给定了样本所属类的条件下

    A generative model builds a probabilistic model for what the features looks like,conditioned on class label.

  • 根据贝叶斯公式可利用模型中的条件概率$p(x|y)$ 与先验概率$p(y)$ 计算出

    image-20181122152244387

Guassian discriminant analysis 高斯判别分析

接下来介绍一种特殊的生成学习算法。

假设 $x\in\mathbb R^n$ 是连续函数,假设 $p(x|y)$ 是高斯分布。

基于以上假设,有高斯判别分析

The multivariate normal distribution 多变量高斯分布

多变量高斯分布的概率密度函数为:

当变量之间存在一定的相关性:

image-20181122155926537

The Guassian Discriminant Analysis model 高斯判别分析模型

模型建立

这个模型的基本假设是目标值 $y$ 服从伯努利分布,条件概率 $p(x|y)$ 服从正态分布。于是,它们的概率密度为:

image-20181122154903043

则数据集的极大似然函数的对数为 (Joint likehood)

image-20181122155115610

注:对比之前判别学习法的极大似然函数(conditional likehood)

image-20181118112229613

对极大似然函数对数最大化,我们就的得到了 GDA 模型的各参数的极大似然估计,即得到了如何使用 GDA 算法的方法。各参数的极大似然估计如下:

image-20181122160455235

预测新样本

对于一个新样本$x$,由于预测无需考虑x出现的概率,故有$p(x)=1$,则预测如下:

且若$p(y)$是均匀分布的,即$p(y=0)=p(y=1)$:

GDA and logistic regression

对于GDA建立的模型,计算$p(y=1|x)$,你得到了一条函数如下,可以看出这条函数与sigmoid函数相同。区别是GDA得到的曲线,取脸是位置还是曲线最陡峭点的陡峭程度都与sigmoid不同。

image-20181122163346426

Discussion:GDA and logistic regression 生成学习法与逻辑回归的关系

GDA与logistic function是泛化与特化的关系,GDA 比逻辑斯蒂回归有更多的前置假设。

假设 $x|y \sim \text{Guassian}$,可以导出logistic后验分布$p(y=1|x)$.

然而反向并不成立,也就是说,服从logistic分布的 $p(y=1|x)$并不能推出$x|y \sim \text{Guassian}$

事实上,假设$x|y$服从柏松分布时,也可以推出后验概率$p(y=1|x)$服从logistic分布

更泛化的是,若你假设条件概率属于指数分布族,也可推出后验概率是logistic函数

GDA与逻辑回归的优缺点

当数据服从或大致服从正态分布时,使用 GDA 会达到更好的效果,因为 GDA利用了更多的信息构建模型。而且相比逻辑回归这种判别学习模型,GDA可以使用更少的数据构建出强壮的模型。

但是当数据不服从正态分布时,那么逻辑斯蒂回归更有效,因为它做出更少的假设,构建的模型更加具有鲁棒性。但是相比生成学习,为了拟合出模型,它需要更多的样本。

Naive Bayes 朴素贝叶斯算法

GDA 针对的是特征向量$x$为连续值时的问题。而朴素贝叶斯(Navie Bayes,NB)则针对的是特征向量$x$为离散值时的问题。

例如:垃圾邮件识别问题,其中特征向量$x$的分量是单词,在样本邮件中存在的单词,则该分量为1,否则为0。

image-20181122183807481

模型建立

朴素贝叶斯假设即是在给定分类 $y$ 后,假设特征向量$x$中 的各个分量是相互独立的。如下式所示:

image-20181122180428232

注:朴素贝叶斯假设在文本分类问题上的解释是:文本中出现某词语时不会影响其他词语在文本中的概率。事实上,虽然这个假设在例问题中显然是错误的,但是Naive Bayes算法任然是一个非常有效的算法,对文档分类等问题。

根据假设,我们得到贝叶斯方法:

Parameters:

image-20181122184938211

Joint likelihood:

image-20181122185136600

为了最大化极大似然估计函数,得到函数参数的极大似然估计:

image-20181122190041433

预测新样本

image-20181123211414383

以上就是最基本的Naive Bayes方法。注意到特征向量的每个分量都只能取值$\{0,1\}$,我们可以将其扩展为$\{0,1,2,…,k\}$,而概率分布由伯努利分布变为多项式分布。对于一些连续的变量,我们可以将其离散化使其可以用Naive Bayes方法解决,离散化的方法为将连续变量按值分段。

Laplace smoothing 改进NB:拉普拉斯平滑

拉普拉斯平滑(Laplace Smoothing)又被称为加1平滑,是比较常用的平滑方法。平滑方法的存在时为了解决零概率问题。

例如:针对文本分类问题就是当一个词语在训练集中没有出现过,那么该词语的概率为 0,使用连乘法计算文本出现的概率时,整个文本出现的概率也为 0。这显然是不合理的,因为不能因为一个事件没有没观测到就判断该事件的概率为 0。

引入拉普拉斯平滑

更广义地有

总之,

image-20181123212317695

Event models for text classification 多项式事件模型

最基本的Navie Bayes模型被成为 multi-variate Bernoulli event model 多变量伯努利事件模型

现在将要介绍一种与多元伯努利事件模型有较大区别的 NB 模型,即多项式事件模型(Multinomial Event Model,以下简称 NB-MEM)

这个模型对于文本分类问题更加的有效,继续以邮件分类为例。

多变量伯努利事件模型中,特征向量的每个分量代表词典中该 index 上的词语是否在文本中出现过,其取值范围为{0,1},特征向量的长度为词典的大小。

NB-MEM 改变了这样的特征向量的表示方法。在 NB-MEM 中,特征向量中的每个分量的值是文本中处于该分量的位置的词语在词典中的索引,其取值范围是{1,2,…,|V|},|V|是词典的大小,特征向量的长度为相应样本邮件的单词的个数,每个不同的邮件的特征向量长度不同,记第$i$个样本邮件的特征向量$x$长度为$n_i$。

image-20181123214020535

注: 在NB-MEM中,$x$ 的特征分量的值是邮件中这个位置的词在词典 $V$ 中的的位置。

模型建立

image-20181123214128739

极大似然估计函数:

image-20181123214221735

则可解得参数的极大似然估计:

image-20181123214312655

加入拉普拉斯平滑:

image-20181123214634330