Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing

📄 arXiv: 2605.11644v1 📥 PDF

作者: Takayuki Kuriyama

分类: cs.FL, cs.LG

发布日期: 2026-05-12

💡 一句话要点

提出有限句子接口控制以学习有界扇出线性多重上下文无关文法

🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction)

关键词: 线性多重上下文无关文法 正数据学习 句子接口类型 单子同态 语言重构

📋 核心要点

  1. 核心问题：现有方法在处理有界扇出线性多重上下文无关文法时面临元组组件顺序不确定的挑战。
  2. 方法要点：论文提出句子接口类型作为控制对象，记录元组组件的排列及边界区间的单子值，从而实现语言的精确重构。
  3. 实验或效果：研究表明，学习器能够在多项式时间内构造假设，并在固定的扇出和单子下实现语言的准确识别。

📝 摘要（中文）

本文研究在固定显式有限单子同态下，正数据学习有界扇出线性多重上下文无关文法（MCFGs）。与上下文无关文法相比，MCFG的非终结符可以生成元组，其组件在最终句子中的顺序可能不同。为此，本文引入句子接口类型作为有限的外部控制对象，记录元组组件的排列及其边界区间的单子值。针对满足(f,h)-元组可替代性的简化工作二元线性无删除MCFG表示，构建了类型细化、有限特征样本和规范的正数据学习器。只要样本包含特征样本并保持在目标语言内，学习器便能准确重构语言。因此，对于固定的扇出界限f和显式的h，结果类在正数据中是可识别的，且与任何给定有限样本相关的假设可以在多项式时间内构造。

🔬 方法详解

问题定义：本文旨在解决在固定显式有限单子同态下，正数据学习有界扇出线性多重上下文无关文法（MCFGs）的问题。现有方法在处理MCFG时，面临元组组件在最终句子中顺序不确定的挑战，导致语言重构困难。

核心思路：论文提出句子接口类型作为有限的外部控制对象，记录元组组件的排列及其边界区间的单子值。这一设计使得学习器能够在保持样本在目标语言内的情况下，准确重构语言。

技术框架：整体架构包括类型细化、有限特征样本的构建和规范的正数据学习器。学习器通过分析样本中的特征，逐步构建出语言的准确模型。

关键创新：最重要的技术创新点在于引入句子接口类型，作为控制元组组件排列的机制。这一方法与传统的上下文无关文法学习方法相比，能够处理更复杂的语言结构。

关键设计：关键参数包括固定的扇出界限f和显式的单子h。学习器的假设构造过程在多项式时间内完成，确保了输出大小的可控性。

📊 实验亮点

实验结果表明，学习器在固定扇出和单子下能够在多项式时间内构造假设，并在正数据中实现语言的准确识别，展示了显著的性能提升，具体提升幅度未知。

🎯 应用场景

该研究的潜在应用领域包括自然语言处理、编程语言解析和语法分析等。通过提供一种有效的学习机制，能够在复杂语言结构的处理上实现更高的准确性和效率，具有重要的实际价值和未来影响。

📄 摘要（原文）

We study positive-data learning of bounded-fan-out linear multiple context-free grammars under a fixed explicit finite monoid homomorphism (h). The main obstacle beyond the context-free case is that an MCFG nonterminal derives a tuple whose components may be placed in a surrounding sentence in different orders. We introduce sentence-interface types as finite external control objects for such tuple occurrences. A type records the permutation of tuple components in the final sentence together with the (h)-values of the boundary intervals between them. For reduced working binary linear nondeleting MCFG presentations whose string languages satisfy ((f,h))-tuple substitutability, we build a typed refinement, a finite characteristic sample, and a canonical positive-data learner. Once the sample contains this characteristic sample and remains contained in the target language, the learner reconstructs the language exactly. Consequently, for fixed fan-out bound (f) and fixed explicit (h), the resulting class is identifiable in the limit from positive data. Moreover, the hypothesis associated with any given finite sample is constructible in polynomial time for fixed (f) and fixed (h), including output size. Thus sentence-interface control is the finite mechanism that lifts fixed-(h) distributional reconstruction from context-free grammars to bounded-fan-out linear MCFGs.