Distributional Learning of Some Nonlinear Tree Grammars
Distributional Learning of Some Nonlinear Tree Grammars
复制标题
一些非线性树文法的分布式学习
DOI：
10.3233/fi-2016-1391
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ryo Yoshinaka
中科院分区：
文献类型：
--
作者：
Alexander Clark;Makoto Kanazawa;G. Kobele;Ryo Yoshinaka
Clark和Yoshinaka的分布式学习算法的一个关键组成部分是提取输入数据中包含的子结构和上下文。这个问题往往变得棘手的非线性文法形式主义，由于事实上，超过多项式许多子结构和/或上下文可能包含在每个对象。以前的非线性语法分布式学习的作品避免了这种困难，限制子结构或上下文，提供给学习者。在本文中，我们确定了两类非线性树文法的子结构和上下文的提取可以在多项式时间内进行，因此，承认成功的分布式学习在其未修改的，原始的形式。
A key component of Clark and Yoshinaka’s distributional learning algorithms is the extraction of substructures and contexts contained in the input data. This problem often becomes intractable with nonlinear grammar formalisms due to the fact that more than polynomially many substructures and/or contexts may be contained in each object. Previous works on distributional learning of nonlinear grammars avoided this difficulty by restricting the substructures or contexts that are made available to the learner. In this paper, we identify two classes of nonlinear tree grammars for which the extraction of substructures and contexts can be performed in polynomial time, and which, consequently, admit successful distributional learning in its unmodified, original form.