贝叶斯分类器

这是3月25日我在TM组机器学习讨论会上的分享。

Content


  1. 贝叶斯决策论
  2. 朴素贝叶斯分类器
  3. 半朴素贝叶斯分类器
  4. 贝叶斯网络

1. 贝叶斯决策论


贝叶斯决策论是一种基于概率的决策理论。当所有相关的概率都已知的理想情况下,贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。

Example

哈工大与哈师大的同学举办大型联♂谊♀会,两个学校分别有500人参与。在联谊会上随机找到一个同学,请猜测他是那个学校的学生?

如果我们一点额外信息都不知道的话,只能随机猜测给出答案。如果我们能够提前知道一点点信息的话,就能够更大程度地猜中正确答案。比如,性别信息:

 

如此的话,假若这个同学是男生,我们肯定会猜测他是哈工大的学生。而从贝叶斯决策论的角度来看,我们需要比较以下两个概率大小:

  • P(工大学生=是 | 性别 = X)
  • P(师大学生=是 | 性别 = X)

上述两个概率被称作后验概率。后验概率往往难以直接获得,我们需要采用一定的手段进行计算。一些算法采用直接对后验概率进行建模的方法,例如SVM、决策树等,这些模型称为判别式模型。而先对联合概率进行建模、进而计算后验概率的模型,称为生成式模型

\(P(c|\boldsymbol{x})=\frac{P(\boldsymbol{x}, c)}{P(\boldsymbol{x})}=\frac{P(c)P(\boldsymbol{x}|c)}{P(\boldsymbol{x})}\)

由此可以计算得到,P(工大学生=是 | 性别 = 男)为4/5,P(师大学生=是 | 性别 = 男)为1/5.

在上面的例子中,我们直接使用了后验概率对类别进行估计。实际问题中,如果将某一类估计错误的代价比较大的话,可以选择在后验概率前乘以一个系数,变为期望损失。分类也从最小化分类错误率变为最小化期望损失。

在上面的式子中,\(P(c)\)代表的是类先验概率。在样本足够大的情况下,直接使用频率即可作为这一概率;\(P(\boldsymbol{x}|c)\)叫做类条件概率,它跟属性x的联合概率有关。上面的例子中,x只有一维,而在实际问题中,往往会选择很多个Feature。此时他们的联合概率就变得难以计算,因此我们需要一些手段对它们进行估计。

Continue reading “贝叶斯分类器”

深度学习简介及单词的向量化表示

Content

  • 深度学习简介
  • NLP与深度学习
  • 单词的向量化表示

1. 深度学习简介

首先应当明确的是,深度学习是机器学习中的一个领域。然而与传统机器学习所不同的是,传统的机器学习的重点在于特征的设计。在设计过特征之后,就变成了研究如何调整权重、优化参数来得到一个最优的结果。

图片1

然而特征设计所涉及的知识、经验的储备往往只有博士级别的研究人员才能够得心应手,而且特征设计的优劣往往直接影响最终的分类结果。与之相反,深度学习应用的是多层特征学习,其中特征学习指的是计算机能够自动地学习到特征的表示,这就解决了手工选择特征局限性较大的问题。深度学习提供了一个近乎统一的框架。它够表达各种信息,能够自动学习,并且非常灵活。这个框架也同样支持监督学习与非监督学习两种学习方式。

除此之外,深度学习还具备以下特点:

  1. 数据量增大时,深度学习的获益更多;
  2. 能够利用多核CPU、GPU加速
  3. 不断涌出的新模型、新算法
  4. 最终性能的提升

2. NLP与深度学习

事实上,在NLP领域,深度学习已经开始展现它的威力了。在应用方面,机器翻译、情感分析、问答系统等都依靠深度学习取得了重大的进步;而在NLP的各个层次上,例如语音识别、形态分析、句法分析、语义解释等,深度学习也发挥了重要的作用。接下来

选区_006

语音

在语音层面,传统的表示形式采用了表格的形式来表示每一个音素。而在深度学习中,将每一个音素表示为向量。

字形

对于一个单词来说,传统的表示形式将词根、前缀和后缀分开表示,例如un-interest-ed。而在深度学习中,往往将一个词素表示为一个向量。

图片3

句法

传统的表示方法会显示地标注出每一个短语的具体类别,例如VP、NP等。而在深度学习中,会将一个词或短语均表示为向量。

语义

lambda演算是一种在语义层面的传统表示方式。例如,将likes视作接受两个参数的函数,每一次合并都相当于柯里化的过程:

图片4

而在深度学习中,仍然将语义表示为向量的合并。

可以看出,向量形式是NLP中所有层次的表达形式。


3. 文本的向量化表示

意义

语言文字或一些符号具备一定的意义。例如,苹果和apple所指代的意义相同。而对于一个外星人来讲,■△▲〓※↓↑〓↓说不定就代表“苹果”。因此,如果想要让计算机理解这一层意义,那么它也需要一种表示;反之,如果我们认为某种表示是计算机所理解的“苹果”,那么即便我们无法阅读(例如■△▲〓※↓↑〓↓),这也是在合理范围之中的。

意义在计算机中的表示

一种表达意义的方式是利用同义词和上位词。例如,熊猫属于动物一类,我们可以用“动物”来表达熊猫的某些方面的意义。再比如,good和well有时意义相近,那么我们可以用well来代表good的某些方面的意义。

然而,这样的表示的问题在于:

  • 缺乏语义差别的信息
  • 难以适应新词
  • 主观
  • 需要人工标注
  • 相似度难以计算

究其根本原因,在于这种方式将单词视为了一种原子符号。或者说,如果在向量空间中对其进行表示的话,我们把它叫做one-hot:

选区_007

one-hot的问题在于,无法表示单词之间的意义相近的关系。例如,hotel和motel两个词,如果利用one-hot形式来表示的话:

hotel  = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

motel = [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

我们无法使用向量运算来获得它们之间意义上的相似度。

You shall know a word by the company it keeps.

–J.R.Firth

J.R.Firth是50年代著名的语言学家,他的这句话被誉为当代NLP领域中最成功的思想之一。对于一个单词的意义,较好的方式是考虑它的上下文。

图片5

而这个“上下文”,则有不同的范围可以选择:其一是将整个文档作为上下文,另一种是选择一个较小的固定的窗口作为上下文。对于“全文档共现”来说,单词向量的维数是文档的个数,如果这一单词在某一篇文档中出现,则该维置1。全文档共现的方式能够挖掘单词的隐含语义。例如,对于“足球”和“教练”来说,它们很有可能在多篇文档中共同出现,则它们的向量也有多维同为1;如果取and的话,就可以获得它们之间的相似程度。

而对于基于窗口的共现来说,其能够同时获得语法与语义的信息。下面我们通过一个例子来看一下基于窗口共现方式的词向量学习过程。

我们选取三句话:

  • I like deep learning.
  • I like NLP.
  • I enjoy flying.

窗口大小取为1,即向前看1一个词、向后看1个词,窗口中一共3个词。通过对共现次数的计数,可以得到以下的矩阵:

图片6

我们可以发现,这个矩阵有这样的几个问题。一是维度过高,它与整个vocabulary相关,因此维度也会随着词汇量的增加而增加;而是矩阵十分稀疏,这将导致难以训练出有效的模型。我们可以通过两种方法来降低词向量的维度:一是用数学方法对这个矩阵进行降维(如SVD奇异值分解);或是不通过这个矩阵,而是直接估计出词向量。

SVD奇异值分解

通过SVD分解,可以将一个mxn的矩阵分解为3个维度分别为rxn、rxr、mxr的矩阵。我们所需要的词向量信息都存储在第一个rxn的矩阵当中。第二个rxr的矩阵是一个对角矩阵,通过调整对角线上的数值可以对第一个rxn矩阵的列进行排序,从而让比较重要的维排在前面。

图片7

使用numpy可以很容易地进行SVD分解计算:

U, s, Vh = numpy.linalg.svd(X, full_matrices=False)

下图是取前两维生成的plot:

图片1

可以看出,相对相近的单词距离更近。

使用SVD方法时,可以进行一些hack,例如通过阈值或过滤的方法对停用词进行处理、添加权重、使用Pearson相关系数代替count等。

图片2

然而,SVD奇异值分解有一些弊端。例如,计算复杂度与m×n相关、难以加入新的单词等。最后,它与深度学习的审美不同:深度学习通常追求从某一个例子中学习一些东西然后再移动到下一个,而SVD方法却需要对所有语料进行整体地处理。

直接学习低维向量

除了利用SVD方法把高维矩阵降维处理外,还可以直接学习低维向量。例如word2vec,他直接预测每个单词相邻单词的概率。除了word2vec,2014年出现了Glove: Global Vectors for Word Representation. Pennington et al. (2014)。它们可以向语料库中不断添加新词。

word2vec的核心思想是:当窗口长度为c时,预测与中心词共现的单词。其目标函数为:

图片3

其中p为

图片4

然而当单词量增大后,其计算将会变得缓慢。因此,我们可以通过采取采样、简化概率函数等方式进行近似。

  基于频数的方法 直接预测方法
优势 训练速度快充分利用了统计信息

性能更好可以获得到比单词相似性更复杂的信息

劣势 主要用来获得单词之间的相似度当频数较少时,获得的比重不合适

与语料库的大小有关没有利用统计信息

 

Reference

http://cs224d.stanford.edu/

感知器算法

这是我之前在实验室的机器学习讨论会上的分享。


Table of Contents

  • 人脑的启示
  • 感知器算法
  • 双层感知器
  • 反向传播算法
  • 应用

人脑的启示


人的神经是由一个个神经元组成的,包括树突、轴突、胞体等。

Picture1

人脑具有以下特征:

  • 超过100亿个神经元
  • 神经元响应时间:约1毫秒
  • 人脸识别:约0.1secs
  • 平均每个神经元与1000个神经元相连
  • 计算高度并行

人脑擅长于模式识别、联想,并可以容忍噪声;电脑则擅长于计算,罗辑清晰。人脑的操作速度很慢,并且运算的结果不可靠,但其可以大规模地并行计算;而电脑的运算速度相当快,并且结果非常可靠。

模拟神经元的结构和工作方式,是感知器算法的主要机制。例如,刺激程度决定了这个神经元的兴奋程度,并且与其他神经元连接紧密时,信号强度大;连接疏松时,信号强度弱。

感知器算法


感知器算法的原理非常简单:

感知器算法

首先对输入信号的求和,当超过阈值时即使感知器兴奋。算法描述如下(from A Course in Machine Learning):

感知器算法

从算法描述可以看出,学习的意义在于向正确的结果靠拢。两组同样的数据,第一次分错了,第二次将会更加接近正确结果。

MaxIter是需要人工指定的参数,如果MaxItger 过大,容易发生过拟合;过小则容易学不到什么东西 。

同时,整个学习的过程就是在一个平面上寻找判别边界。为了简化问题,假设有一个线性可分问题,b=0,则感知器算法即在寻找分界面B:

snapshot7

B就是虚线,而由wd组成的向量w垂直于B:

snapshot8

由此也可以得出,w的绝对大小并不重要。

感知器算法的特点有:

  1. 在线学习,不需要一次性考虑整个数据集

  2. 错误驱动,当分类正确时,不进行学习操作

  3. 对训练集的输入顺序敏感。例如,有10000条训练数据,前9000条数据在默认的参数上就分类正确,则此次迭代只有最后1000条数据得到了训练。因此,不断地调整训练数据的顺序将有助于加快训练速度:

Picture4

朴素的感知器算法仍然存在一定的缺陷,例如后训练的数据会更加重要。参考上面举得例子,如果有10000条训练数据,前100条数据已经训练出足够好的分类器,一直到最后一条之前全部分类正确。最后一条数据就会掉了一个在99.9%的数据上工作得都非常好的分类器。

从以上的分析也可以看出,单层的感知器算法只能用于解决线性可分的问题。

算法改进

投票感知器算法

投票感知器算法会在训练时记录每一个分类器的存活时间,在最终预测时根据权重进行投票。

Picture5

但是由于需要保存每一个超平面,并且预测时需要使用每一个分类器进行预测,时空开销将非常大。

平均感知器算法

平均感知器算法仅记录加权平均后的分类器:

Picture6

除此之外,还有像信任权感知器、被动主动感知器、权表决感知器等。信任权感知器通过对输入添加信任权重的概率分布,使得信任度大的输入会得到更大幅度的修正;被动主动感知器可以主动修正学习速率;权表决感知器会为每一维输入产生一个分类器,最终由虽有分类器结果汇总投票产生,并对错误的分类器予以惩罚。

双层感知器


 snapshot9

在双层感知器中,将有两层感知器需要训练。除此之外,在单层感知器中,我们使用的是线性函数来计算感知器是否被激活;这种用于判断感知器是否激活的函数叫做激活函数(link function)。双层感知器中,隐含层通常采用非线性的sigmoid(tanh)函数来作激活函数。

对于双层感知器来说,它可以模拟任意连续函数;隐含层节点越多,函数越复杂。如果隐含层层数再增加,则可以模拟任意函数。

反向传播算法


对于感知器计算输出的过程来说,相当于正向传播;而通过计算结果反馈给隐含层和输出层来调整参数,则属于反向传播。例如:

Picture1

我们可以通过输出结果与标准值的误差,来修正向量v和矩阵w。常用的方法是梯度下降法,目标函数为结果误差的几何均值。通过对目标函数f求w和v的偏导,就可以求出v和w的梯度。

目标函数:

Picture5

计算结果:

Picture3

Picture4

总结


优势

  • 数学基础 如果有线性解则可以找到(单层)
  • 可以容忍噪声
  • 可以处理任意连续/非连续函数(多层)
  • 可以学到复杂的输入输出映射关系

劣势

  • 知识表示不易解释
  • 依赖于hidden层激励函数
  • 输入输出的设计对结果具有影响
  • 参数较多(神经元数目、层数、学习速率等)
  • 可能需要使用者的经验
  • 训练时间长
  • 过拟合