结合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 发布的序列句子标记的实现,并有详细文档。


企业会员

免责声明:本网站内容主要来自原创、合作伙伴供稿和第三方自媒体作者投稿,凡在本网站出现的信息,均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性,但不保证有关资料的准确性及可靠性,读者在使用前请进一步核实,并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏,概不负任何法律责任。任何单位或个人认为本网站中的网页或链接内容可能涉嫌侵犯其知识产权或存在不实内容时,应及时向本网站提出书面权利通知或不实情况说明,并提供身份证明、权属证明及详细侵权或不实情况证明。本网站在收到上述法律文件后,将会依法尽快联系相关文章源头核实,沟通删除相关内容或断开相关链接。

2017-11-27
结合Logistic回归构建最大熵马尔科夫模型
判定模型 vs 生成模型 上一篇博文中,我讨论了朴素贝叶斯模型,以及它与隐马尔可夫模型之间的联系。它们都属于生成模型,但本文要讲的 Logistic 回归模型是

长按扫码 阅读全文

Baidu
map