Learning (k,l)-context-sensitive probabilistic grammars with nonparametric Bayesian approach
Learning (k,l)-context-sensitive probabilistic grammars with nonparametric Bayesian approach
复制标题
使用非参数贝叶斯方法学习 (k,l) 上下文相关概率语法
DOI：
10.1007/s10994-021-06034-2
复制
发表时间：
2021
期刊：
影响因子：
7.5
通讯作者：
Shibata Chihiro
中科院分区：
文献类型：
--
作者：
寺田侑司;塚本皓斗;甲斐充彦;Shibata Chihiro
利用非参数贝叶斯方法进行形式语法推断是实现无监督数据高准确率的最有效方法之一。本文在上下文无关语法（CFGs）上定义了轻度上下文敏感概率，称为（k,l）上下文敏感概率。从上下文中识别规则概率的推理cfg可以被视为一种分布式学习的双重方法，其中上下文表征子字符串。我们可以通过分层非参数贝叶斯模型（如Pitman-Yor过程（PYPs））的平滑效应来处理上下文敏感概率的数据稀疏性。我们自然地通过扩充无限的pcfg来定义pyp的层次结构。已知阻断吉布斯采样对推断pcfg是有效的。我们证明，通过修改内部概率，阻塞的Gibbs采样能够应用于(k,l)-上下文敏感的概率语法。同时，我们证明了CFG的(k,l)-上下文敏感概率的时间复杂度为每个句子w，其中v是一组非终结符。由于迭代足够的次数在计算上过于昂贵，特别是当|V|不小时，需要一些替代的采样算法。因此，我们提出了一种新的采样方法，称为复合采样，该方法将采样过程分为非终结子过程和推导树子过程。最后，我们证明了推断的（k, 0）上下文敏感的概率语法比其他概率语言模型（如pcfg、n-grams和hmm）可以实现更低的困惑。
Inferring formal grammars with nonparametric Bayesian approach is one of the most powerful approach for achieving high accuracy from unsupervised data. In this paper, mildly-context-sensitive probabilities, called (k,l)-context-sensitive probabilities, are defined on context-free grammars (CFGs). Inferring CFGs where the probabilities of rules are identified from contexts can be seen as a kind of dual approaches for distributional learning, in which the contexts characterize the substrings. We can handle the data sparsity for the context-sensitive probabilities by the smoothing effect of the hierarchical nonparametric Bayesian models such as Pitman–Yor processes (PYPs). We define the hierarchy of PYPs naturally by augmenting the infinite PCFGs. The blocked Gibbs sampling is known to be effective for inferring PCFGs. We show that, by modifying the inside probabilities, the blocked Gibbs sampling is able to be applied to the (k,l)-context-sensitive probabilistic grammars. At the same time, we show that the time complexity for (k,l)-context-sensitive probabilities of a CFG isfor each sentencew, whereVis a set of nonterminals. Since it is computationally too expensive to iterate sufficient times especially when |V| is not small, some alternative sampling algorithms are required. Therefore, we propose a new sampling method called composite sampling, with which the sampling procedure is separated into sub-procedures for nonterminals and for derivation trees. Finally, we demonstrate that the inferred (k, 0)-context-sensitive probabilistic grammars can achieve lower perplexities than other probabilistic language models such as PCFGs, n-grams, and HMMs.
登录
查看更多内容
PAC-学习明确的 NTS 语言
DOI：
10.1007/11872436_6
发表时间：
2006
期刊：
--
影响因子：
--
作者：
Alexander Clark
通讯作者：
Alexander Clark
跳过n元语法与改进Kneser Ney平滑相结合的广义语言模型
DOI：
10.3115/v1/p14-1108
发表时间：
2014
期刊：
Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval
影响因子：
--
作者：
Rene Pickhardt;Thomas Gottron;Martin Körner;P. Wagner;Till Speicher;Steffen Staab
通讯作者：
Steffen Staab
物种抽样混合模型的广义加权中餐馆流程
DOI：
--
发表时间：
2003
期刊：
影响因子：
--
作者：
H. Ishwaran;Lancelot F. James
通讯作者：
Lancelot F. James
手性环状α,α-二取代氨基酸及其叠氮基寡肽的设计与合成
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
佐藤由紀子;金子文也;奥田晴宏;長野正展;出水庸介;土井光暢;田中正一;末宗洋;栗原正明;M. Nagano;M. Tanaka;石川奈保子;高崎紘臣
通讯作者：
高崎紘臣
迈向基于历史的语法：使用更丰富的模型进行概率解析
DOI：
10.3115/981574.981579
发表时间：
1993
期刊：
--
影响因子：
--
作者：
Ezra Black;F. Jelinek;J. Lafferty;David M. Magerman;R. Mercer;S. Roukos
通讯作者：
S. Roukos