生成学习算法(Generative Learning algorithms)

一、引言

     前面我们谈论到的算法都是在给定\(x\)的情况下直接对\(p(y|x;\theta)\)进行建模。例如,逻辑回归利用\(h_\theta(x)=g(\theta^T x)\)对\(p(y|x;\theta)\)建模,这类算法称作判别学习算法。

     考虑这样一个分类问题,我们根据一些特征来区别动物是大象\((y=1)\)还是狗\((y=0)\)。给定了这样一个训练集,逻辑回归或感知算法要做的就是去找到一个决策边界,将大象和狗的样本分开来。可以换个思路,首先根据大象的特征来学习出一个大象的模型,然后根据狗的特征学习出狗的模型,对于一个新的样本,提取它的特征先放到大象的模型中求得是大象的概率,然后放到狗的模型中求得是狗的概率,最后我们比较两个概率哪个大,即确定这个动物是哪种类型。也即求\(p(y|x)=\frac{p(x|y)p(y)}{p(x)}\),\(y\)为输出结果,\(x\)为特征。

现在我们来定义这两种解决问题的方法:

判别学习算法(discriminative learning algorithm):直接学习\(p(y|x)\)或者是从输入直接映射到输出的方法

生成学习算法(generative learning algorithm):对\(p(x|y)\)(也包括\(p(y))\)进行建模。

\(y\)为输出变量,值为0或1,如果是大象取1,狗则取0

\(p(x|y = 0)\):对狗的特征进行建模

\(p(x|y = 1)\):对大象的特征建模

对\(p(x|y)\)和\(p(y)\)完成建模后,运用贝叶斯公式,就可以求得在给定\(x\)的情况下\(y\)的概率:

\[p(y|x)=\frac{p(x|y)p(y)}{p(x)}\]

\[p(x) = p(x|y = 1)p(y = 1) + p(x|y =0)p(y = 0)\]

由于我们关心的是\(y\)离散结果中哪一个的概率更大,而不是要求得具体的概率,所以上面的公式我们可以表达为:

\begin{align*} arg\,\underset{y}{max}p(y|x) &=arg\,\underset{y}{max}\frac{p(x|y)p(y)}{p(x)} \\ 
&=arg\,\underset{y}{max}p(x|y)p(y) \end{align*}

\(arg\,\underset{y}{max}p(y|x)\)的含义:满足条件的最大\(y\)值。对\(y\)求取最大值,与\(p(x)\)无关,所以可以不需要计算\(p(x)\)了

常见的生成模型有:隐马尔可夫模型HMM、朴素贝叶斯模型、高斯混合模型GMM、LDA等

二、高斯判别分析(Gaussian Discriminant Analysis)

下面介绍第一个生成学习算法GDA。在GDA中,假设\(x \in R^n\)且是连续的,且\(p(x|y)\)满足多项正态分布。

2.1 多项正态分布(The multivariate normal distribution)

假设随机变量\(X\)满足\(n\)维的多项正态分布,参数为均值向量\(\mu\in R^n\),协方差矩阵\(\Sigma \in R^{n\times n}\),记为\(N(\mu,\Sigma)\)其概率密度表示为:

\[p(x;\mu,\Sigma)=\frac{1}{(2\pi)^{n/2}(det\Sigma)^\frac{1}{2}}exp\bigg(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\bigg)\]

\(det\Sigma\)表示矩阵\(\Sigma\)的行列式(determinant)。

均值向量 :\(\mu\)

协方差矩阵:\(\Sigma=E[(X-E[X])(X-E[X])^T]=E[(x-\mu)(x-\mu)^T]\)

接下来我们用matlab来画一下二维正态分布的图像,我们可以调整均值和协方差矩阵来观察图像。

代码:

mu=[0 0];
sigma=[1.0 0;0 1.0];
[x y]=meshgrid(linspace(-3,3,40)',linspace(-3,3,40)');
X=[x(:) y(:)];
z=mvnpdf(X,mu,sigma);
surf(x,y,reshape(z,40,40));
hold on;
figure;
contour(x,y,reshape(z,40,40));

\(\mu\)决定中心位置,\(\Sigma\)决定投影椭圆的朝向和大小。

2.2高斯判别分析模型(The Gaussian Discriminant Analysis model)

现在有一个分类问题,训练集的特征值\(x\)是随机连续值,那么我们可以利用高斯判别分析模型,假设\(p(x|y)\)满足多值正态分布,即:

\[y \sim Bernoulli(\phi)\]

\[x|y=0 \sim N(\mu_0, \Sigma)\]

\[x|y=1 \sim N(\mu_1, \Sigma)\]

概率分布为:

\[p(y) = \phi^y(1-\phi)^{1-y}\]

\[p(x|y=0) = \frac{1}{(2\pi)^{n/2}(det\Sigma)^\frac{1}{2}}exp\bigg(-\frac{1}{2}(x-\mu_0)^T\Sigma^{-1}(x-\mu_0)\bigg)\]

\[p(x|y=1) = \frac{1}{(2\pi)^{n/2}(det\Sigma)^\frac{1}{2}}exp\bigg(-\frac{1}{2}(x-\mu_1)^T\Sigma^{-1}(x-\mu_1)\bigg)\]

模型参数为\(\phi, \Sigma, \mu_0, \mu_1\),对数似然函数为:

\[l(\phi,\mu_0,\mu_1,\Sigma)=log\prod_{i=1}^{m}p(x^{(i)},y^{(i)};\phi,\mu_0,\mu_1,\Sigma)=log\prod_{i=1}^{m}p(x^{(i)}|y^{(i)};\mu_0,\mu_1,\Sigma)p(y^{(i)};\phi)\]

注意这里的参数有两个\(\mu\),表示在不同的结果模型下,特征均值不同,但我们假设协方差相同。反映在图上就是不同模型中心位置不同,但形状相同。这样就可以用直线来进行分隔判别。

求得所有的参数:

\[\phi = \frac{1}{m}\sum\limits_{i=1}^{m}1\{y^{(i)}=1\}\]

\[\mu_0=\frac{\sum\limits_{i=1}^{m}1\{y^{(i)}=0\}x^{(i)}}{\sum\limits_{i=1}^{m}1\{y^{(i)}=0\}}\]

\[\mu_1=\frac{\sum\limits_{i=1}^{m}1\{y^{(i)}=1\}x^{(i)}}{\sum\limits_{i=1}^{m}1\{y^{(i)}=1\}}\]

\[\Sigma = \frac{1}{m}\sum\limits_{i=1}^{m}(x^{(i)}-\mu_{y{(i)}})(x^{(i)}-\mu_{y{(i)}})^T\]

\(\phi\)是训练样本中结果\(y=1\)占有的比例。

\(\mu_0\)是\(y=0\)的样本中特征均值。

\(\mu_1\)是\(y=1\)的样本中特征均值。

\(\Sigma\)是样本特征方差均值。

所以通过上面所述,画出图像如下图:

直线两边的\(y\)值不同,但协方差矩阵相同,因此形状相同,\(\mu\)不同,因此位置不同。

2.3讨论GDA和逻辑回归(Discussion: GDA and logistic regression)

现在我们把\(p(y = 1|x; \phi, \mu_0, \mu_1, \Sigma)\)看成是\(x\)的函数,则可以表达为:

\[p(y=1|x;\phi,\Sigma,\mu_0,\mu_1)=\frac{1}{1+exp(-\theta^Tx)}\]

\(\theta\) 是参数\(\phi,\Sigma,\mu_0,\mu_1\)的函数,这正是逻辑回归的形式。

逻辑回归和GDA在训练相同的数据集的时候我们得到两种不同的决策边界,那么怎么样来进行选择模型呢:

上面提到如果\(p(x|y)\)是一个多维的高斯分布,那么\(p(y|x)\)可以推出一个logistic函数;反之则不一定正确,\(p(y|x)\)是一个logistic函数并不能推出\(p(x|y)\)服从高斯分布.这说明GDA比logistic回归做了更强的模型假设.

如果\(p(x|y)\)真的服从或者趋近于服从高斯分布,则GDA比logistic回归效率高.

当训练样本很大时,严格意义上来说并没有比GDA更好的算法(不管预测的多么精确).

事实证明即使样本数量很小,GDA相对logisic都是一个更好的算法.

但是,logistic回归做了更弱的假设,相对于不正确的模型假设,具有更好的鲁棒性(robust).许多不同的假设能够推出logistic函数的形式. 比如说,如果\(x|y=0 \sim Poisson(\lambda_0)\),\(x|y=1 \sim Poisson(\lambda_1)\)那么\(p(y|x)\)是logistic。

logstic回归在这种类型的Poisson数据中性能很好. 但是如果我们使用GDA模型,把高斯分布应用于并不是高斯数据中,结果是不好预测的,GDA就不是很好了.

三:朴素贝叶斯(Naive Bayes)

在GDA中,特征向量\(x\)是连续的实数向量,那么现在谈论一下当\(x\)是离散时的情况。

我们沿用对垃圾邮件进行分类的例子,我们要区分邮件是不是垃圾邮件。分类邮件是文本分类的一种应用

将一封邮件作为输入特征向量,与现有的字典进行比较,如果在字典中第i个词在邮件中出现,则\(x_i=1\),否则\(x_i=0\),所以现在我们假设输入特征向量如下:

选定特征向量后,现在要对\(p(x|y)\)进行建模:

假设字典中有50000个词,\(x \in \{0, 1\}^{50000}\)   如果采用多项式建模, 将会有\(2^{50000}\)种结果,\(2^{50000}-1\)维的参数向量,这样明显参数过多。所以为了对\(p(x|y)\)建模,需要做一个强假设,假设\(x\)的特征是条件独立的,这个假设称为朴素贝叶斯假设(Naive Bayes (NB) assumption),这个算法就称为朴素贝叶斯分类(Naive Bayes classifier).

解释:

如果有一封垃圾邮件\((y=1)\),在邮件中出现buy这个词在2087这个位置,它对39831这个位置是否出现price这个词没有影响,也就是,我们可以这样表达\(p(x_{2087}|y)=p(x_{2087}|y,x_{39831})\),这个和\(x_{2087}\)和\(x_{39831}\)相互独立不同,如果相互独立,则可以写为\(p(x_{2087})=p(x_{2087}|x_{39831})\),我们这里假设的是在给定y的情下,\(x_{2087}\)和\(x_{39831}\)独立。

现在我们回到问题中,在做出假设后,可以得到:

解释

第一个等号用到的是概率的性质 链式法则

第二个等式用到的是朴素贝叶斯假设

朴素贝叶斯假设是约束性很强的假设,一般情况下 buy和price是有关系的,这里我们假设的是条件独立 ,独立和条件独立不相同

模型参数:

\[\phi_{i|y=1}=p(x_i=1|y=1)\]

\[\phi_{i|y=0}=p(x_i=1|y=0)\]

\[\phi_y=p(y=1)\]

对于训练集{(x(i) , y(i)); i =1, . . . , m},根据生成学习模型规则,联合似然函数(joint likelihood)为:

得到最大似然估计值:

最后一个式子是表示\(y=1\)的样本数占全部样本数的比例,前两个表示在\(y=1\)或\(y=0\)的样本中,特征\(x_j=1\)的比例。

拟合好所有的参数后,如果我们现在要对一个新的样本进行预测,特征为x,则有:

实际上只要比较分子就行了,分母对于y = 0和y = 1是一样的,这时只要比较p(y = 0|x)与p(y = 1|x)哪个大就可以确定邮件是否是垃圾邮件。

3.1拉普拉斯平滑(Laplace smoothing)

朴素贝叶斯模型可以在大部分情况下工作良好。但是该模型有一个缺点:对数据稀疏问题敏感。

  比如在邮件分类中,对于低年级的研究生,NIPS显得太过于高大上,邮件中可能没有出现过,现在新来了一个邮件"NIPS call for papers",假设NIPS这个词在词典中的位置为35000,然而NIPS这个词从来没有在训练数据中出现过,这是第一次出现NIPS,于是算概率时:

由于NIPS从未在垃圾邮件和正常邮件中出现过,所以结果只能是0了。于是最后的后验概率:

对于这样的情况,我们可以采用拉普拉斯平滑,对于未出现的特征,我们赋予一个小的值而不是0。具体平滑方法为:

假设离散随机变量取值为{1,2,···,k},原来的估计公式为:

使用拉普拉斯平滑后,新的估计公式为:

即每个k值出现次数加1,分母总的加k,类似于NLP中的平滑,具体参考宗成庆老师的《统计自然语言处理》一书。

  对于上述的朴素贝叶斯模型,参数计算公式改为:

时间: 2024-10-21 00:03:18

生成学习算法(Generative Learning algorithms)的相关文章

Andrew Ng机器学习公开课笔记 -- Generative Learning algorithms

网易公开课,第5课  notes,http://cs229.stanford.edu/notes/cs229-notes2.pdf 学习算法有两种,一种是前面一直看到的,直接对p(y|x; θ)进行建模,比如前面说的线性回归或逻辑回归,这种称为判别学习算法(discriminative learning algorithms) 另外一种思路,就是这里要谈的,称为生成学习算法(generative learning algorithms),区别在于不会直接对p(y|x; θ)进行建模,而是对p(x

【学习排序】 Learning to Rank 中Listwise关于ListNet算法讲解及实现

    前一篇文章"Learning to Rank中Pointwise关于PRank算法源码实现"讲述了基于点的学习排序PRank算法的实现.该篇文章主要讲述Listwise Approach和基于神经网络的ListNet算法及Java实现.包括:     1.基于列的学习排序(Listwise)介绍     2.ListNet算法介绍     3.ListNet算法Java实现    LTR中单文档方法是将训练集里每一个文档当做一个训练实例,文档对方法是将同一个查询的搜索结果里任意

【重磅】AlphaZero炼成最强通用棋类AI,DeepMind强化学习算法8小时完爆人类棋类游戏

世界最强围棋AI AlphaGo Zero带给世人的震撼并没有想象中那么久--不是因为大家都去看谁(没)跟谁吃饭了,而是DeepMind再次迅速超越了他们自己,超越了我们剩下所有人的想象. 12月5日,距离发布AlphaGo Zero论文后不到两个月,他们在arXiv上传最新论文<用通用强化学习算法自我对弈,掌握国际象棋和将棋>(Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algori

TensorFlow Agents日前开源,轻松在TF中构建并行强化学习算法

用于在TensorFlow中构建并行强化学习算法的高效基础架构范例TensorFlow Agents日前开源,这个项目是由谷歌的两位研究员James Davidson.Vincent Vanhoucke,以及Danijar Hafner共同研发的.关于这个项目的开源信息他们在GitHub上进行了介绍,雷锋网 AI 科技评论将内容进行编译整理. TensorFlow Agents TensorFlow Agents为强化学习提供了优化的基础架构,它将OpenAI gym接口扩展到多个并行环境,并能

如何通过TensorFlow实现深度学习算法并运用到企业实践中

本文根据才云科技首席大数据科学家郑泽宇在QCon2016全球软件开发大会(上海站)上的演讲整理而成,希望大家可以了解如何通过TensorFlow实现深度学习算法,并将深度学习运用到企业实践中. 讲师介绍 郑泽宇,谷歌高级工程师.从 2013 年加入谷歌至今,郑泽宇作为主要技术人员参与并领导了多个大数据项目,拥有丰富机器学习.数据挖掘工业界及科研项目经验.2014 年,他提出产品聚类项目用于衔接谷歌购物和谷歌知识图谱(Knowledge Graph)数据,使得知识卡片形式的广告逐步取代传统的产品列

BAIR论文:通过“元学习”和“一次性学习”算法,让机器人快速掌握新技能

我们都知道,深度学习是在大数据的背景下火起来的,传统的基于梯度的深度神经网络需要大量的数据学习,而绝大多数的深度学习内容否基于大数据量下的广泛迭代训练,当遇到新信息时往往会出现模型失效的情况从而需要重新进行学习.在机器人领域,深度神经网络可以是机器人展示出复杂的技能,但在实际应用中,一旦环境发生变化,从头学习技能并不可行.因此,如何让机器"一次性学习",即在"看"了一次演示后无需事先了解新的环境场景,能在不同环境中重复工作尤为重要. 研究发现,具有增强记忆能力的架构

《中国人工智能学会通讯》——2.18 深度学习算法的计算与访存特征

2.18 深度学习算法的计算与访存特征 图 1 是一个用于手写识别的深度卷积神经元网络 LeNet5 [6] ,以此为例讨论深度学习算法的计算特征.在 LeNet5 中,包括了卷积层 C1.C3.C5 和Subsampling 层 S2.S4,以及全连接层 F6.其中卷积层是最为费时的操作. 对 于 有 R 个 输 入 feature map 和 Q 个 输 出feature map 的卷积层,假设 feature map 的大小为 M×N,卷积核的大小为 K×L,则该卷积层的代码大致可以表示为

《深度学习导论及案例分析》一3.2受限玻耳兹曼机的学习算法

本节书摘来自华章出版社<深度学习导论及案例分析>一书中的第3章,第3.2节,作者李玉鑑 张婷,更多章节内容可以访问"华章计算机"公众号查看. 3.2受限玻耳兹曼机的学习算法 受限玻耳兹曼机的学习就是对模型参数集θ进行计算,常用的方法是最大似然估计,其基本思想在于采用梯度上升算法最大化总体对数似然函数.在给定可视向量训练集S={v(l),1≤l≤N}时,受限玻耳兹曼机的对数似然函数定义为 lRBM(θ)=log∏Nl=1p(v(l)θ)=∑Nl=1logp(v(l)θ)(3.

Medium网友开发了一款应用程序 让学习算法和数据结构变得更有趣

CS-Playground-React接口 CS-Playground-React地址:http://cs-playground-react.surge.sh/ Medium网友Peter Weinberg的自述:我是一名自学成才的程序员.我觉得自己做得不够好,并且在掌握复杂的计算机科学概念方面处于劣势. 我对数学不是十分擅长.我总是把强大的数学技巧和天生擅长编程的能力联系在了一起.我觉得我必须比其他人(他们有天生的数学能力)更努力地学习相同的概念.这个想法深深扎根在我的大脑中,我很确定我永远无