MMJul, 2022

树的平面线性化中边长度期望和的线性时间计算

PDF
TL;DR本篇文章研究依赖图的句法结构，针对平面的排列方法和投射的排列方法，分别提出了预期边长总和的计算方法，并用一个包含词语的句子来给出了平面排列的数量或生成平面随机排列的有效算法。
dependency graphssyntactic structureprojective arrangementsplanar permutations
发现论文，激发创造
  • 树的随机投影线性化中边长期望和的线性时间计算

    本文提供一种新的算法来计算句子的依存距离期望值，在统计上足够准确，时间复杂度为 $n$。此外，文章还发现了星形树（star tree）在该算法中具有最大化作用，提出了一种可以找到最小化依存距离期望值的树的算法。

    Jul, 2021

  • 随机线性排列的边长度之和

    该研究探讨了在随机线性排列的节点中边长之和的分布情况，可用于各个领域；得到了任意图形和树的 1 阶、2 阶、方差的紧凑公式；并分析了该方差在 Erdos-Renyi 图中的演化和在均匀随机树中的缩放。

    May, 2019

  • 树的最大线性排列问题（基于 projectivity 和 planarity）

    本文研究了最大线性排列问题（MaxLA）的两个变体，即基于免费树和基于根树的平面和投影变体。针对树的平面和投影 MaxLA 问题，提出了相应的线性时间和空间的算法，并证明了最大投影和平面排列的几个性质，同时表明毛毛虫树是平面 MaxLA 问题中所有尺寸固定的树中最优的，从而推广了前人在树上的极值结果。

    Jun, 2022

  • 句法依存距离的分布

    本文提出了一种新的双指数模型，探讨了句子的句法结构和依赖距离分布及其与短期记忆限制之间的关系，并通过最近引入的优化分数，解释了最佳估计模型与句法依赖的紧密程度之间的关系。

    Nov, 2022

  • 使用无向最小生成树推断进行边缘线性一阶依存句法分析

    该研究提出了一种基于最小生成树的推断算法，可以将大规模的图形依赖分析模型边缘数量的运行时间复杂度降至 O (m)，并通过局部贪心更新进一步优化了有向解析树模型，验证实验表明，该算法在 18 种语言的测试中表现类似于原始解析器。

    Oct, 2015

  • 句法依赖距离的优化性

    通过空间网络将句子中单词的语法依赖关系表示为优化问题，引入新的评分方法来量化减少单词距离的认知压力，研究 93 种语言的句子，发现这种方法能准确评估大约一半的语言的优化水平，并对各个领域的语言研究提供了启示，特别是对网络科学有重要意义。

    Jul, 2020

  • 依存树中的 Hubiness、长度、交叉及其关系

    本文研究了三种不同角度的树形依赖结构：它们的度变化、平均依赖长度和依赖交叉数，并导出了揭示这三个指标之间成对依赖关系的边界。我们的发现表明，句子的在线内存成本不仅取决于单词顺序，还取决于基础结构的度变化。度的第二时刻具有重要作用，类似于其在大型复杂网络中的作用。

    Apr, 2013

  • 使用依赖树的多项式表示量化语法相似性

    引入了一个可以区分树结构的图多项式来表达依存语法，并基于多项式表示引入了一种量化句子语法相似度的方法。通过将这个基于多项式的方法运用到分析并比较不同语言中的句子与其翻译之间的句法以及在已有语料库中进行语法学的类型学研究，最后探讨并展示了这种方法在衡量语料库的句法多样性方面的潜力。

    Nov, 2022

  • 跨越依赖是否确实稀有？

    对句子进行的语法结构建模可以看作树形结构，基线或空假设缺乏的情况下，量化了真实句子中的交叉量并将其与一系列基线预测相比较，得出交叉相当稀少。

    Mar, 2017

  • 学习字符串部分序列

    本文提出一种基于部分排序的线性时间和空间复杂度算法来解决结构化预测问题，其中通过计算输入字符串中每个令牌的实数并相应地进行排序，得到了尽可能少的 2 个令牌总订单，这些总订单的交集形成了令牌的部分排序，并被解码成代表所需结构的有向图。在英语依存句法分析基准测试上，我们的方法通过使用 2 个总订单和 4 个总订单分别获得 95.4 LAS 和 96.9 UAS 以及 95.7 LAS 和 97.1 UAS 的结果；此外，该方法还是第一个实现了线性复杂度共指消解模型 —— 在英语 OntoNotes 基准测试上获得了 79.2 F1 分数，与现有技术相当。

    May, 2023