Hierarchical Bracketing Encodings for Dependency Parsing as Tagging¶

会议: ACL 2025
arXiv: 2505.11693
代码: 无
领域: NLP理解
关键词: 依存句法分析, 序列标注, 括号编码, 投射树, 非投射性

一句话总结¶

提出层次化括号编码家族用于依存句法分析的序列标注范式，证明现有4-bit编码是该家族的非最优特例，推导出仅需12个标签的最优编码，并将其推广到处理任意非投射性。

领域现状: 序列标注范式的依存分析利用预训练编码器将依存树转化为标签序列，计算效率高且性能有竞争力。
现有痛点: 早期括号编码标签空间无界(Θ(n²))，虽然4-bit编码将投射树限制到16个标签，但仍非最优。现有非投射性扩展（如多平面方法）与编码框架不完全匹配。
核心矛盾: 标签空间越小，序列标注模型学习越容易；但如何在保持解码正确性的同时最小化标签数量？
本文要解决什么: 推导最紧凑的括号编码，同时支持投射和非投射依存树。
切入角度: 基于Yli-Jyrä的rope cover概念，建立层次化括号编码框架，区分结构弧（超括号）和辅助弧（半括号），通过最优rope cover最小化标签使用。
核心idea一句话: 利用proper rope cover（最小结构弧集合）将投射树的标签空间从16个压缩到12个，并通过带索引的括号扩展到非投射树。

定义两级括号系统：超括号(superbrackets)编码结构弧（需要左右各一个括号），半括号(semibrackets)编码辅助弧（只需一个括号）。核心优化是最小化结构弧数量。

层次化括号框架: 将依存弧分为结构弧（用超括号对编码）和辅助弧（用半括号编码）。辅助弧"依附"于结构弧，共享一个端点，只需一个括号标记另一端点。
Proper Rope Cover: Yli-Jyrä的算法：从最左端点的未标记弧中选最长的作为结构弧，标记依附弧为辅助弧，重复直到所有弧标记完毕。证明这是最小基数的rope cover。
最优编码推导: 证明投射树的标签形式为 ()? (> | > | < | <) (/)? 但proper rope cover排除了 </ 和 > 组合（因为它们意味着结构弧互相依附），将16个标签减少到12个。
非投射性扩展: 通过为半括号和超括号添加索引i（跳过i个匹配括号），支持交叉弧。索引上界由rope thickness决定，实验中UD树库最多需要索引2。

线性时间栈式解码：读到开括号压栈，读到闭半括号匹配栈顶但不弹出，读到闭超括号弹出直到匹配的开超括号。非投射扩展中索引括号跳过指定数量的匹配。

编码	标签数	英语PTB LAS	多语言平均
4-bit (B4)	16	竞争性	竞争性
最优 (OP)	12	竞争性	竞争性
Hexatagging	8	竞争性	竞争性

紧凑层次化括号标签形式：$(\backslash)? (> | \mathbf{>} | < | \mathbf{<}) (/)? $，排除 $\mathbf{<}/$ 和 $\backslash\mathbf{>}$ 后从16→12个标签
Proper rope cover计算：贪心选最左最长未标记弧为结构弧 → 标记依附弧为辅助弧 → 重复
解码复杂度：O(n)，每个弧恰好一次push和一次pop/peek
非投射扩展中索引分布：UD树库中大多数语言索引≤2即可全覆盖，仅古希腊语需更高索引
4-bit编码的rope cover策略：取每个节点最长左向弧和最长右向弧为结构弧，是proper rope cover的一个非最优特例
Theorem 2是首次正式证明proper rope cover具有最小基数（此前Yli-Jyrä未证明）