如何从上下文无关语法中枚举树
比较了树相邻语法(TAG)和组合范畴语法(CCG)对于字符串和树的表达能力,发现它们在树上的表达能力基本上是一致的,特别地,只要有限制条件,如 CCG 没有空字符串的词库条目和一阶规则的度数不超过 2,则其表达能力可以达到最大。
May, 2022
本文介绍了一种将组合子术语表示为证明树的方法,并引入了基于参数化组合子术语定义的证明模式,实现了基于连接结构演算的特征的自动化一阶证明的实现和第一批实验结果。
Sep, 2022
本研究论文介绍了如何编写一种简约语法(MG),通过使用一种上下文无关文法(CFG)的变体作为输入格式,以算法的形式给出编写指南。该方法通过利用许可者和被许可者来处理异常情况,避免 CFG 中的递归导致过度生成,并通过适当分配许可者和被许可者来处理例外情况。同时,还通过引入所谓的适配器解决大多数许可者和被许可者不需要触发的问题。
Nov, 2023
本文提出一种新的 GNN 设计策略,利用无上下文语法生成矩阵语言 MATLANG,从而确保 WL 表达能力,子结构计数能力和谱属性。根据该策略,设计了语法图神经网络 G$^2$N$^2$,证明了其在边级上计算长度为 6 的环并能够达到带通滤波器,实验结果证实了理论结果。
Mar, 2023
本研究设计实验以探究生成式语言模型如何学习上下文无关文法,并发现了 Transformer 如何利用物理机制隐式地编码文法结构、形成类动态规划的 attention,并在处理语法错误时表现出的鲁棒性方面的相关拓展。
May, 2023
针对一类无上下文语法,研究了等价性的可决定性问题,证明了 Clark-congruential grammar 类中此问题是可决定的,同时考虑了如何检查 CFG 是否属于此类,并证明在给定 CFG 是 DCFG 的情况下此问题是可决的。
May, 2018
本文介绍了一种基于 Earley 解析法的扩展,可以给定随机上下文无关语法和输入字符串来计算被语法生成的前缀和子字符串的概率,以及字符串的最大可能 (Viterbi) 划分和每个语法生成的后验预期应用数量。
Nov, 1994
我们研究了一个语法归纳问题的正式化,其将句子建模为由复合概率上下文无关文法生成。与传统的学习单一随机文法的方式不同,我们的文法的规则概率由每个句子的连续潜变量调制,这在传统上下文无关假设以外引出了边际依赖性。这种文法的推理通过折叠变分推理实现,在这种方法中,连续变量上放置平化的变分后验,并通过动态规划边际化潜在树。针对英语和中文的实验表明,与最近的最先进方法相比,我们的方法在无监督语法分析评估时非常有效。
Jun, 2019
研究语法诱导,使用线性无上下文重写系统进行无监督不连续解析,将文法形式限制为二元 LFCRS 并使用张量分解与参数化规则概率得到大量非终端符号,从而能够诱导出具有连续和不连续结构的语言学意义的树。
Dec, 2022