深度 | 结合Logistic回归构建最大熵马尔科夫模型

2017 年 11 月 25 日 机器之心

选自davidsbatista

作者:David S. Batista

机器之心编译

参与:乾树、刘晓坤


这是应用于 NLP 的连续监督学习系列博文的第二篇。它可以看作是上一篇文章的续作(参见:深度 | 从朴素贝叶斯到维特比算法:详解隐马尔科夫模型),在上一篇博客中,作者试着解释了隐马尔科夫模型(HMM)和朴素贝叶斯(Naive Bayes)之间的关系。在这篇博客中,作者将尝试解释如何构建一个基于 Logistic 回归分类器的序列分类器,即,使用一种有区别性的方法。


判定模型 vs 生成模型


上一篇博文中,我讨论了朴素贝叶斯模型,以及它与隐马尔可夫模型之间的联系。它们都属于生成模型,但本文要讲的 Logistic 回归模型是一个判定模型,全文以讨论这种差异开始。


通常,机器学习分类器通过从所有可能的 y_i 中选择有最大的 P(y | x) 的那个,来决定将哪个输出标签 y 分配给输入 x。


朴素贝叶斯分类器通过应用贝叶斯定理间接估计 p(y | x),然后计算类的条件分布/概率 P(x | y) 和先验概率 P(y)。



这种间接性使得朴素贝叶斯成为一种生成模型,一种通过训练从类 y 生成数据 x 的模型。p(x | y) 的意义是给定一个类 y,然后预测对应的输入 x 中包含哪些特征。相比之下,判定模型通过直接判定类别 y 的不同可能值来计算 p(y | x),而不是计算概率。Logistic 回归分类器正是这种分类器。



Logistic 回归


Logistic 回归是用于分类的一种监督学习算法,它的本质是线性回归。


当用于解决 NLP 任务时,它通过从输入文本中提取特征并线性组合它们来估计 p(y | x),即,将每个特征乘以一个权重,然后将它们相加,然后将指数函数应用于该线性组合:



其中 f_i 是一个特征,w_i 是与该特征相关的权重。对于权重和特征点积进行的 exp(即,指数函数)确保所有值都是正值,并且需要除以分母 Z 以得到(所有概率值的总和为 1)有效概率。


提取到的是二值特征,即只取值 0 和 1,通常称为指标函数。其中每一个特征都是通过输入 x 和类 y 的函数来计算的。每个指标函数表示为 f_i(y , x),对于类 y 的特征 i,给定观测值 x:



训练


我们想通过训练 logistic 回归来获得每一个特征的理想权重(使训练样本和属于的类拟合得最好的权重)。


Logistic 回归用条件极大似然估计进行训练。这意味着我们将选择参数 w,使对给定输入值 x 在训练数据中 y 标签的概率最大化:



需要最大化的目标函数是:



通过用前面展示的扩展形式替换,并应用对数除法规则,得到以下形式:



通常可以运用随机梯度下降法、L-BFGS 或共轭梯度法来求此函数的最大值,即找到最优权重。


分类


在分类任务中,logistic 回归通过计算给定观察的属于每个可能类别的概率,然后选择产生最大概率的类别。



最大熵马尔可夫模型


最大熵马尔可夫模型(Maximum Entropy Markov Model,MEMM)的思想是利用 HMM 框架预测给定输入序列的序列标签,同时结合多项 Logistic 回归(又名最大熵,其给出了可以从输入序列中提取特征的类型和数量上的自由度)。


HMM 基于两种概率:


  • P(tag | tag) 状态转换,从一个状态到另一个状态的概率。

  • P(word | tag) 输出概率,从一个状态输出一个字的概率。


在现实问题中,我们要预测一个给定词/输入的标签/状态。但是,由于贝叶斯定理(即生成方法),在 HMM 中不可能进行编码,而模型估计的是产生某个确定单词的状态的概率。


MEMM 因包含丰富的输入特征而备受推崇:


  • 除了传统的单词识别之外,还有描述输入的多种重叠特征的表示,例如大写字母、单词结尾、词类、格式、页面上的位置以及 WordNet 中的节点成员等。


也可以用一个判定方法来解决预测问题:


  • 传统的方法通过设置 HMM 参数以最大化输入序列的概率; 然而,在大多数文本应用中,其任务是根据输入序列来预测状态序列。换句话说,传统方法不恰当地使用生成联合模型来解决给定输入的条件问题。


(左)传统 HMM 的依赖关系图。(右)最大熵马尔可夫模型的依赖关系图(选自 A. McCallum et al. 2000)。


在最大熵马尔可夫模型中,转换函数和输入函数(即上一篇博客的 HMM 矩阵 A 和 B)被单个函数代替:



给定前一个状态 s_t-1 和当前的输入值 o_t,得到当前状态的概率 s_t。下图展示了计算状态/标签/标记转换的不同之处。


HMM 和 MEMM 之间状态转换估计的对比。(选自「Speech and Language Processing」,Daniel Jurafsky & James H. Martin)


与当前输入仅依赖于当前状态的 HMM 相比,MEMM 中的当前输入也可以取决于之前的状态。HMM 模型对于每个转换和输入都有确定的概率估计,而 MEMM 给出每个隐藏状态的一个概率估计,这是给定前一个标记和输入值情况下的下一个标记的概率。


在 MEMM 而不是转换和观测矩阵中,只有一个转换概率矩阵。该矩阵将训练数据中先前状态 S_t-1 和当前输入 O_t 对的所有组合封装到当前状态 S_t。


令 N 为独特状态的个数,M 为独特单词的个数,矩阵的形状为:(N⋅M)⋅N


特征函数


MEMM 可以对输入值的任何有用特征进行条件化。在 HMM 中这是不可能的,因为 HMM 是基于概率的,因此需要计算每个输入特征的概率。使用状态-输入转换函数,而不是像 HMM 那样的独立的转换和输入函数,使我们能够对输入的多个非独立特征进行建模。


这是通过多项 logistic 回归来实现的,给定先前标记(即,s'),输入词(即,o)和任意其它特征(即,fi(x,y’))来估计每个局部标记的概率:



其中 w_i 是与每个特征 f_i(x,y) 相关联的需要学习的权重,Z 是使矩阵在每行上总和为 1 的归一化因子。


考虑整个观测序列的特征函数。(选自「Speech and Language Processing」,Daniel Jurafsky & James H. Martin)


训练与解码


最初发表于 2000 年的 MEMM 论文使用广义迭代缩放(GIS)算法来拟合多项 logistic 回归,即根据训练数据找到完美的权重。该算法在很大程度上被基于梯度的方法(如 L-BFGS)所超越。


使用与 HMM 中相同的 Viterbi 算法进行解码,尽管不是那么适合估计状态转换的新方法。


MEMM 的重要结论


  • 相对于 HMM 的主要优势是使用特征向量,使得转换概率对输入序列中的任何词都敏感。

  • 每个(状态,单词)对都有一个指数模型来计算下一个状态的条件概率。

  • 指数模型允许 MEMM 支持整个观测序列与前一状态(而不是两个不同的概率分布)的长距离交互。

  • MEMM 还可以扩展为包含涉及额外过去状态(而不仅仅是前一个状态)的特征。

  • 它也使用 Viterbi 算法(稍作改动)来执行解码。

  • 它受到标签偏差问题的影响,我将在下一篇关于条件随机场的文章中详细介绍。


软件包


  • https://github.com/willxie/hmm-vs-memm:一个由 William Xie 负责的课程项目,在词性标注方面的任务上实现且比较了 HMM 与 MEMM。

  • https://github.com/yh1008/MEMM:由 Emily Hua 发布的名词短语拆分任务的实现。

  • https://github.com/recski/HunTag:由 GáborRecski 发布的序列句子标记的实现,并有详细文档。


参考文献


  • Chapter 7:「Logistic Regression」in Speech and Language Processing. Daniel Jurafsky & James H. Martin. Draft of August 7, 2017.(https://web.stanford.edu/~jurafsky/slp3/7.pdf)

  • Maximum Entropy Markov Models for Information Extraction and Segmentation(http://www.ai.mit.edu/courses/6.891-nlp/READINGS/maxent.pdf)

  • Chapter 6:「Hidden Markov and Maximum Entropy Models」in Speech and Language Processing. Daniel Jurafsky & James H. Martin. Draft of September 18, 2007(https://www.cs.jhu.edu/~jason/papers/jurafsky+martin.bookdraft07.ch6.pdf)

  • Hidden Markov Models vs. Maximum Entropy Markov Models for Part-of-speech tagging(https://github.com/willxie/hmm-vs-memm) 


原文链接:http://www.davidsbatista.net/blog/2017/11/12/Maximum_Entropy_Markov_Model/



本文为机器之心编译,转载请联系本公众号获得授权

✄------------------------------------------------

加入机器之心(全职记者/实习生):hr@jiqizhixin.com

投稿或寻求报道:content@jiqizhixin.com

广告&商务合作:bd@jiqizhixin.com

登录查看更多
4

相关内容

对数几率回归(Logistic Regression),简称为对率回归,也称逻辑斯蒂回归,或者逻辑回归。虽然它被很多人称为逻辑回归,但是中文的“逻辑”一词与“logistic”和“logit”意思相去甚远。它是广义的线性模型,只是将线性回归方程中的y换成了ln[p/(1-p),p是p(y=1|x),p/(1-p)是“几率”。对数几率回归是用来做分类任务的,所以,需要找一个单调可微函数,将分类任务的真实标记和线性回归模型的预测值联系起来。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等
【UCLA】基于深度神经网络的工业大模型预测控制,36页ppt
自回归模型:PixelCNN
专知会员服务
26+阅读 · 2020年3月21日
【MIT深度学习课程】深度序列建模,Deep Sequence Modeling
专知会员服务
77+阅读 · 2020年2月3日
一网打尽!100+深度学习模型TensorFlow与Pytorch代码实现集合
一文读懂线性回归、岭回归和Lasso回归
CSDN
34+阅读 · 2019年10月13日
【深度】从朴素贝叶斯到维特比算法:详解隐马尔科夫模型
算法与数学之美
7+阅读 · 2017年11月25日
逻辑回归(Logistic Regression) 模型简介
全球人工智能
5+阅读 · 2017年11月1日
10分钟搞懂Tensorflow 逻辑回归实现手写识别
全球人工智能
5+阅读 · 2017年10月19日
从浅层模型到深度模型:概览机器学习优化算法
机器之心
26+阅读 · 2017年7月9日
Logistic回归第一弹——二项Logistic Regression
机器学习深度学习实战原创交流
3+阅读 · 2015年10月22日
Deep Learning for Energy Markets
Arxiv
10+阅读 · 2019年4月10日
Parsimonious Bayesian deep networks
Arxiv
5+阅读 · 2018年10月17日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
Arxiv
4+阅读 · 2018年4月10日
Arxiv
9+阅读 · 2018年3月23日
Arxiv
3+阅读 · 2018年2月22日
Arxiv
3+阅读 · 2017年7月6日
Arxiv
4+阅读 · 2016年12月29日
VIP会员
相关资讯
一文读懂线性回归、岭回归和Lasso回归
CSDN
34+阅读 · 2019年10月13日
【深度】从朴素贝叶斯到维特比算法:详解隐马尔科夫模型
算法与数学之美
7+阅读 · 2017年11月25日
逻辑回归(Logistic Regression) 模型简介
全球人工智能
5+阅读 · 2017年11月1日
10分钟搞懂Tensorflow 逻辑回归实现手写识别
全球人工智能
5+阅读 · 2017年10月19日
从浅层模型到深度模型:概览机器学习优化算法
机器之心
26+阅读 · 2017年7月9日
Logistic回归第一弹——二项Logistic Regression
机器学习深度学习实战原创交流
3+阅读 · 2015年10月22日
相关论文
Deep Learning for Energy Markets
Arxiv
10+阅读 · 2019年4月10日
Parsimonious Bayesian deep networks
Arxiv
5+阅读 · 2018年10月17日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
Arxiv
4+阅读 · 2018年4月10日
Arxiv
9+阅读 · 2018年3月23日
Arxiv
3+阅读 · 2018年2月22日
Arxiv
3+阅读 · 2017年7月6日
Arxiv
4+阅读 · 2016年12月29日
Top
微信扫码咨询专知VIP会员