arXiv cs.CL· Yuxi Wang, Jungyeul Park·· 10 小时前AI 评分18
Bock 算法用于精确依存句法分析的重新表述与等价性证明
Reformulation and Equivalence of Bock's Algorithm for Exact Dependency Parsing
AI 导读
研究提出 Bock 算法的一种重新表述，通过组件标签、列调整与 star-and-bar 变换保留原始节点和弧的身份，并证明在匹配扫描与平局规则下与原 Bock 算法操作等价，且在指定组件调度下与修正版 Tarjan 对应。
正文 · AI 翻译
摘要：Bock 算法为精确依存句法分析提供了一种基于矩阵的替代方案，可替代 Chu--Liu/Edmonds（CL/E）算法。我们提出了一种重新表述，通过组件标签、列调整以及星-杠转移来保留原始节点和弧的身份。在精确算术下，我们证明了在匹配的扫描和并列规则下与原始 Bock 的操作等价性，并在规定的组件调度下建立了与修正后 Tarjan 的对应关系。另一项独立分析在给定的得分和单根约定下，建立了与 Dozat 衍生 CL/E 的最优值等价性。我们将重新表述的 Bock 集成到双仿射依存句法分析器中，并在 Penn Treebank 和 Chinese Treebank 上评估了解码和结构化训练。这些结果确立了 Bock 作为依存句法分析和结构化训练的一种替代精确 oracle，同时区分了最优值的相等性与返回树及训练轨迹的同一性。
| 主题： | 计算与语言（cs.CL） |
| 引用为： | arXiv:2611.00939 [cs.CL] |
| （或 arXiv:2611.00939v1 [cs.CL] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.00939 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Jungyeul Park [查看电子邮件]
[v1]
2026年10月31日星期六 13:40:25 UTC（33 KB）
来源：arXiv cs.CL · arxiv.org