Learning Context Free Grammars with the Syntactic Concept Lattice
Learning Context Free Grammars with the Syntactic Concept Lattice
复制标题
使用句法概念格学习上下文无关语法
DOI：
10.1007/978-3-642-15488-1_5
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Alexander Clark
中科院分区：
文献类型：
--
作者：
Alexander Clark
句法概念格是基于语言分布结构的剩余格；基于此的自然表示是上下文敏感的形式主义。在这里，我们研究基于该格结构的上下文无关语法（cfg）的可能性；特别是通过选择非终结符来对应于该格中的概念。我们提出了一种使用正数据和隶属查询的上下文无关语法学习算法，并在极限范式的识别下证明了其正确性。由于格本身可能是无限的，因此我们仅考虑概念集的多项式有界子集，以获得有效的算法。我们一方面将其与上下文无关语法的学习算法进行比较，其中非终结符对应于同余类，另一方面与上下文敏感技术（例如二元特征语法和分布格语法）的使用进行比较。可以通过这种方式学习的 cfgs 类包括本质上不明确且因此不确定的语言；因此，这种方法突破了推理中的一个重要障碍。
The Syntactic Concept Lattice is a residuated lattice based on the distributional structure of a language; the natural representation based on this is a context sensitive formalism. Here we examine the possibility of basing a context free grammar (cfg) on the structure of this lattice; in particular by choosing non-terminals to correspond to concepts in this lattice. We present a learning algorithm for context free grammars which uses positive data and membership queries, and prove its correctness under the identification in the limit paradigm. Since the lattice itself may be infinite, we consider only a polynomially bounded subset of the set of concepts, in order to get an efficient algorithm. We compare this on the one hand to learning algorithms for context free grammars, where the non-terminals correspond to congruence classes, and on the other hand to the use of context sensitive techniques such as Binary Feature Grammars and Distributional Lattice Grammars. The class ofcfgs that can be learned in this way includes inherently ambiguous and thus non-deterministic languages; this approach therefore breaks through an important barrier incfginference.