Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

概率上下文无关文法

PCFG扩展上下文无关语法(Context-free grammar),类似于隐马尔可夫模型常规语法的扩展。

来源:Wikipedia
简介

在自然语言,如英语中,词与词连接起来构成词组,词组和词组连接起来构成新的词组。例如,在句子「Sam thinks Sandy likes the book」中,单词「the」和「book」结合起来构成了名词词组(NP)「the book」,「the book」又和动词「like」连接起来构成了动词词组(VP)「likes the book」,它与「Sandy」连接起来构成了嵌入句或语句(S)「Sandy likes the book」。PCFG的目的就是解析从单词串中发现某种结构。PCFG是短语结构树(phrasestructure trees)的简单模型。 我们首先解释什么是正式语言和语法,然后提出上下文无关语法和PCFG(它们的概率对应)。

正式语言(formal language)是一种语言的数学抽象。它是根据终端词汇表来定义的,终端词汇表是终端符号(terminal symbol,或简称终端)的有限集合V,它是构成语言表达式的基本元素。例如,V可能是一组英文单词,或者可能是字符'a' - 'z'。给定终端的集合V,W = V*是V的成员的字符串(V⋆也包含空字符串ǫ)。语言是W的子集,而语法是语言的有限规范。 (一种语言可以包含无限数量的字符串,或者即使它是有限的,也可以包含如此多的字符串以至于将它们全部列出是不实际的)。概率语言是W上的概率分布,而概率语法是概率语言的有限规范。语法也可以提供关于语言中字符串的其他信息。

上下文无关语法也许是短语结构树最简单的模型。 上下文无关语法(Context-Free Grammar, 简称 CFG),G 可以定义为四元组 G={N,Σ, P, S}。其中,N 是非终极符号的集合,Σ是终极符号的集合,S 是初始符号,P 是重写规则, 规则的形式为 A → β,规则左部的 A 是单独的非终极符号,规则的右部β是符号串,它可以由终极符号组成,也可以由非终极符号组成,还可以由终极符号和非终极符号混合组成。我们可以以句子「Sam thinks Sandy likes the book」为例,给出一组示范:

概率上下文无关文法(PCFG)通过将概率$\rho_{A→β}$与语法中的每个规则A→β∈R相关联来扩展上下文无关语法。$\rho_{A→β}$可以看作是非终结符A扩展到β的条件概率。 更正式地说,一个PCFG是一个五元组G = (V, N, S, R, \rho), 其中(V, N, S, R)是一个CFG, \rho是属于[0,1]的实数向量,满足:

其中$R_A = {A→β∈R}$是R中父项为A的所有规则的集合。如果我们将$\rho_{A→β}$解释为A扩展为β的条件概率,则这个条件是自然的,它表示相同左部的产生式概率分布满足归一化条件。 继续使用上文中的例子,我们可以求得ρ为:

PCFG定义树T∈T_G上的概率分布P_G(T)如下:

其中n_{A→β}(t)是父代标记为A的子树和标签为β的子代出现在t中的次数, 这相当于说树的概率是所有局部树的概率的乘积。如果T_G(w)是由G生成的树,并且产量为w,那么我们定义P_G (w)为T_G(w)中树的概率之和,即,

[图片及描述来源:Charniak, E. and Johnson, M. (2016). Introduction to Computational Linguistics. ]


发展历史

在计算机科学中,PCFG具有较长的传统,并且主要用于自然语言处理领域。1979年J. K. Baker受到有限状态隐马尔可夫过程算法的成功的启发,将语音建模的算法推广到某些可隐藏状态的隐马尔可夫过程。该算法允许自动训练任意上下文无关语法的随机模拟,并允许语法具有任意程度的模糊性。Sean R. Eddy, Richard Durbin于1994年将SCFG引入生物信息学中用于建模RNA二级结构,他们也是将SCFG应用在生物信息学领域的早期学者之一。由于这两条工作线都相当独立地发展起来,在论文中提及术语并不总是相同的,从下文开始我们将其统一为PCFG。

2003年Dan Klein和Christopher D. Manning证明了非灵活化的PCFG可以比以前显示的更准确地解析,且与非复杂的词法模型相比,非灵活化的PCFG更紧凑,更容易复制,更易于解释,分析算法更简单。它具有较低的渐近复杂性,并且更易于优化。2006年Walter L. Ruzzo 等学者提出了CMfinder,用于在RNA中找到稳定的结构基序,能够预测未对齐序列中的RNA基序,这也是PCFG在生物信息学中的实际应用。

主要事件

年份事件相关论文/Reference
1979J. K. Baker受到有限状态隐马尔可夫过程算法的成功的启发,将语音建模的算法推广到某些可隐藏状态的隐马尔可夫过程。Baker, J. K. (1979). Trainable grammars for speech recognition. The Journal of the Acoustical Society of America. 65.
1994Sean R. Eddy, Richard Durbin于1994年将SCFG引入生物信息学中用于建模RNA二级结构Eddy, S. R.; Durbin, R. (1994). RNA sequence analysis using covariance models, Nucleic Acids Research. 22(11): 2079–2088,
2003Dan Klein和Christopher D. Manning证明了非灵活化的PCFG可以比以前显示的更准确地解析Klein, D.; Manning, C. D. (2003). Accurate Unlexicalized Parsing. NLP.
2006Walter L. Ruzzo等学者提出了CMfinderYao, Z.; Weinberg, Z.; Ruzzo, W. L. (2006). CMfinder—a covariance model based RNA motif finding algorithm. Bioinformatics. 22(4): 445–452.

发展分析

瓶颈

PCFG假设非终结符的展开之间是互相独立的,但这是一个很强的假设,在实际使用中往往需要通过 state-splitting 来放宽假设;但如果分割过度,又会导致稀疏性问题。另外,PCFG对词汇不敏感,无法在使用相同规则的句法树中择优。

目前已经提出了不少基于规则的歧义消解方法来排除歧义,例如,基于选择限制的方法、基于词典的词义排歧方法等。但是这些基于规则的方法消解歧义的效果都不很理想。于是,学者们试图改进上下文无关语法,采用基于统计的方法,计算上下文无关语法重写规则的使用概率,试图根据概率来改进上下文无关语法。

在自然语言处理中关于规则方法和统计方法的争论反映了语言学中的理性主义思潮与 经验主义思潮的对立。

[来源:自然语言处理中的概率语法, http://www.lingviko.net/feng/0501.pdf]

未来发展方向

PCFG仍然是自然语言处理领域的重要模型,它的优势主要在于进行了歧义消解,并且比较稳健,并且可以从前文看到,PCFG在RNA建模中很受欢迎。

Contributor: Yuanyuan Li

简介