---
abstract: 'The connection between the maximum spanning tree in a directed graph and the best dependency tree of a sentence has been exploited by the NLP community. However, for many dependency parsing schemes, an important detail of this approach is that the spanning tree must have exactly one edge emanating from the root. While work has been done to efficiently solve this problem for finding the one-best dependency tree, no research has attempted to extend this solution to finding the $\nK$-best dependency trees. This is arguably a more important extension as a larger proportion of decoded trees will not be subject to the root constraint of dependency trees. Indeed, we show that the rate of root constraint violations increases by an average of $13$ times when decoding with $\nK\!=\!50$ as opposed to $\nK\!=\!1$. In this paper, we provide a simplification of the $\nK$-best spanning tree algorithm of @CameriniFM80. Our simplification allows us to obtain a constant time speed-up over the original algorithm. Furthermore, we present a novel extension of the algorithm for decoding the $\nK$-best dependency trees of a graph which are subject to a root constraint.[^1]'
author:
- |
    <span>Ran Zmigrod1.0ex1.0ex</span>  Tim Vieira1.0ex  Ryan Cotterell1.0ex\
    1.0exUniversity of Cambridge  1.0exJohns Hopkins University  1.0exETH Zürich\
    `annegriffin@example.com`  `annegriffin@example.com`\
    `annegriffin@example.com`
bibliography:
- 'acl2021.bib'
title: 'On Finding the $\nK$-best Non-projective Dependency Trees'
---

=1

Introduction
============

Non-projective, graph-based dependency parsers are widespread in the NLP literature. [@mcdonald-etal-2005-non; @dozat; @stanza]. However, despite the prevalence of $\nK$-best dependency parsing for other parsing formalisms—often in the context of re-ranking [@collins-koo-2005-discriminative; @sangati-etal-2009-generative; @zhu-etal-2015-ranking; @do-rehbein-2020-neural] and other areas of NLP [@shen-etal-2004-discriminative; @huang-chiang-2005-better; @pauls-klein-2009-k; @zhang-etal-2009-k], we have only found three works that consider $\nK$-best non-projective dependency parsing [@hall-2007-k; @hall-etal-2007-log; @agic-2012-k]. All three papers utilize the $\nK$-best spanning tree algorithm of @CameriniFM80. Despite the general utility of $\nK$-best methods in NLP, we suspect that the relative lack of interest in $\nK$-best non-projective dependency parsing is due to the implementation complexity and nuances of @CameriniFM80's algorithm.[^2]

![Violation rate of the root constraint when using regular $K$-best decoding [@CameriniFM80] on pre-trained models of @stanza for languages with varying training set sizes.<span data-label="fig:experiment"></span>](figures/kbest-figure.pdf){width="47.00000%"}

We make a few changes to @CameriniFM80's algorithm, which result in both a simpler algorithm and simpler proof of correctness.[^3] Firstly, both algorithms follow the key property that we can find the second-best tree of a graph by removing a single edge from the graph (\[thm:second\]); this property is used iteratively to enumerate the $\nK$-best trees in order. Our approach to finding the second-best tree (see \[sec:next-best\]) is faster because of it performs half as many of the expensive cycle-contraction operations (see \[sec:best\]). Overall, this change is responsible for our $1.39$x speed-up (see \[sec:kbest\]). Secondly, their proof of correctness is based on reasoning about a complicated ordering on the edges in the $\nK\th$ tree [@CameriniFM80 Section 4]; our proof side-steps the complicated ordering by directly reasoning over the ancestry relations of the $\nK\th$ tree. Consequently, our proofs of correctness are considerably simpler and shorter. Throughout the paper, we provide the statements of all lemmas and theorems in the main text, but defer all proofs to the appendix.

In addition to simplifying @CameriniFM80's algorithm, we offer a novel extension. For many dependency parsing schemes such as the Universal Dependency (UD) scheme [@ud], there is a restriction on dependency trees to only have one edge emanate from the root.[^4] Finding the maximally weighted spanning tree that obeys this constraint was considered by @GabowT84 who extended the $\bigo{\nN^2}$ maximum spanning tree algorithm of @Tarjan77 [@camerini1979note]. However, no algorithm exists for $\nK$-best decoding of dependency trees subject to a root constraint. As such, we provide the first $\nK$-best algorithm that returns dependency trees that obey the root constraint.

To motivate the practical necessity of our extension, consider \[fig:experiment\]. \[fig:experiment\] shows the percentage of trees that violate the root constraint when doing one-best and $50$-best decoding for 63 languages from the UD treebank [@ud] using the pre-trained model of @stanza.[^5]$^,$[^6] We find that decoding without the root constraint has a much more extreme effect when decoding the $50$-best than the one-best. Specifically, we observe that on average, the number of violations of the root constraint increased by $13$ times, with the worst increase being 44 times. The results thus suggest that finding $\nK$-best trees that obey the root constraint from a non-projective dependency parser requires a specialist algorithm. We provide a more detailed results table in \[app:table\], including root constraint violation rates for $\nK\!=\!5$, $\nK\!=\!10$, and $\nK\!=\!20$. Furthermore, we note that the $\nK$-best algorithm may also be used for marginalization of latent variables [@correiaNAM20] and for constructing parsers with global scoring functions [@leeLZ16].

Results Table for \[fig:experiment\] {#app:table .unnumbered}
------------------------------------

Finding the Best Tree {#sec:best}
=====================

We consider the study of , which we will abbreviate to simply .[^7] A graph is given by $\graph=(\root,\nodes, \edges)$ where $\nodes$ is a set of $\nN+1$ nodes with a designated root node $\root\in \nodes$ and $\edges$ is a set of directed weighted edges. Each edge $e=\edgeij\in \edges$ has a weight $\weight{e}\in\mathbb{R}_{+}$. We assume that self-loops are not allowed in the graph (i.e., $\edge{i}{i}\not\in \edges$). Additionally, we assume our graph is not a multi-graph, therefore, there can exist at most one edge from node $i$ to node $j$.[^8] When it is clear from context, we abuse notation and use $j\in\graph$ and $e\in\graph$ for $j\in \nodes$ and $e\in \edges$ respectively. When discussing runtimes, we will assume a fully connected graph ($\abs{\edges}=\nN^2$).[^9] An (henceforth called a ) of $\graph$ is a subgraph $\tree=(\root,\nodes,\edges')$ such that $\edges'\subseteq \edges$ and the following is true:

1.  For all $j\in \nodes \setminus \{\root\}$, $\abs{\{\edge{\_}{j}\in \edges'\}}=1$.

2.  $\tree$ does not contain any cycles.

Other definitions of trees can also include that there is at least one edge emanating from the root. However, this condition is immediately satisfied by the above two conditions. A $\tree=(\root,\nodes,\edges')$ is a tree with the extra constraint

1.  $\abs{\{ \edge{\root}{\_}\in \nodes' \}}= 1$

The set of all trees and dependency trees in a graph are given by $\arbs{\graph}$ and $\arbsrc{\graph}$ respectively. The weight of a tree is given by the sum of its edge weights[^10] $$\weight{\tree} = \sum_{e\in\tree} \weight{e}$$

This paper concerns finding the $\nK$ highest-weighted (henceforce called ) tree or dependency tree, these are denoted by $\kbest{K}{\graph}$ and $\kbestrc{K}{\graph}$ respectively. @Tarjan77 [@camerini1979note] provided the details for an $\bigo{\nN^2}$ algorithm for decoding the one-best tree. This algorithm was extended by @GabowT84 to find the best dependency tree in $\bigo{\nN^2}$ time. We borrow the algorithm (and notation) of @zmigrod-etal-2020-please, who provide an exposition and proofs of these algorithms in the context of non-projective dependency parsing. The pseudocode for finding $\first{\graph}$ and $\kbestrc{1}{\graph}$ is given in \[alg:ma\]. We briefly describe the key components of the algorithm.[^11]

The of $\graph$ is denoted by $\greedy{\graph}=(\root,\nodes,\edges')$ where $\edges'$ contains the highest weighted incoming edge to each non-root node. Therefore, if $\greedy{\graph}$ has no cycles, then $\greedy{\graph}=\first{\graph}$. A cycle $\cg$ in $\greedy{\graph}$ is called a . If we encounter a critical cycle in the algorithm, we contract the graph by the critical cycle. A graph , $\contract{\graph}{\cg}$, by a cycle $\cg$ replaces the nodes in $\cg$ by a mega-node $\cc$ such that the nodes of $\contract{\graph}{\cg}$ are $\nodes\setminus \cg \cup \{\cc\}$. Furthermore, for each edge $e=\edgeij\in\graph$:

1.  If $i\not\in\cg$ and $j\in\cg$, then $e'=\edge{i}{c}\in\contract{\graph}{\cg}$ such that $\weight{e'}=\weight{e} + \weight{\greedy{\cg_j}}$ where $\cg_j$ is the subgraph of $\cg$ rooted at $j$.

2.  If $i\in\cg$ and $j\not\in\cg$, then $e'=\edge{c}{j}\in\contract{\graph}{\cg}$ such that $\weight{e'}=\weight{e}$.

3.  If $i\not\in\cg$ and $j\not\in\cg$, then $e\in\contract{\graph}{\cg}$.

4.  If $i\in\cg$ and $j\in\cg$, then there is no edge related to $\edgeij$ in $\contract{\graph}{\cg}$.

There also exists a bookkeeping function $\prov$ such that for all $e'\in\contract{\graph}{\cg}$, $\prov(e')\in\graph$. This bookkeeping function returns the edge in the original graph that led to the creation of the edge in the contracted graph using one of the constructions above.

Finding $\first{\graph}$ is then the task of finding a contracted graph $\graph'$ such that $\greedy{\graph'}=\first{\graph'}$. Once this is done, we can stitch back the cycles we contracted. If $\graph'=\contract{\graph}{\cg}$, for any $\tree\in\arbs{\contract{\graph}{\cg}}$, $\stitch{\tree}{\cg}\in\arbs{\graph}$ is the tree made with edges $\prov(\tree)$ ($\prov$ applied to each edge $\tree$) and $\greedy{\cg_j}$ where $\cg_j$ is the subgraph of the nodes in $\cg$ rooted at node $j$ and $\prov(e)=\edge{i}{j}$ for $e=\edge{i}{\cc}\in\tree$. The contraction weighting scheme means that $\weight{\tree}=\weight{\stitch{\tree}{\cg}}$ [@georgiadis]. Therefore, $\first{\graph}=\first{(\stitch{\first{\graph'}}{\cg})}$.

The strategy for finding $\kbestrc{1}{\graph}$ is to find the contracted graph for $\first{\graph}$ and attempt to remove edges emanating from the root. This was first proposed by @GabowT84. When we consider removing an edge emanating from the root, we are doing this in a possibly contracted graph, and so an edge $\edge{\root}{j}$ may exist multiple times in the graph. We denote $\medgedelete{\graph}{e}$ to be the graph $\graph$ with all edges with the same end-points as $e$ removed. \[fig:example\] gives an example of a graph $\graph$, its best tree $\first{\graph}$, and its best dependency tree $\kbestrc{1}{\graph}$.

\[t!\]

The runtime complexity of finding $\first{\graph}$ or $\kbestrc{1}{\graph}$ is $\bigo{\nN^2}$ for dense graphs by using efficient priority queues and sorting algorithms [@Tarjan77; @GabowT84]. We assume this runtime for the remainder of the paper.

Finding the Second Best Tree {#sec:next-best}
============================

In the following two sections, we provide a simplified reformulation of @CameriniFM80 to find the $\nK$-best trees. The simplifications additionally provide a constant time speed-up over @CameriniFM80's algorithm. We discuss the differences throughout our exposition.

The underlying concept behind finding the $\nK$-best tree, is that $\kbest{K}{\graph}$ is the second best tree $\second{\graph'}$ of some subgraph $\graph'\subseteq\graph$. In order to explore the space of subgraphs, we introduce the concept of edge inclusion and exclusion graphs.

\[Edge inclusion and exclusion\] For any graph $\graph$ and edge $e\in\graph$, the $\edgeinclude{\graph}{e}\subset\graph$ is the graph such that for any $\tree\in\arbs{\edgeinclude{\graph}{e}}$, $e\in\tree$. Similarly, the $\edgedelete{\graph}{e}\subset\graph$ is the graph such that for any $\tree\in\arbs{\edgedelete{\graph}{e}}$, $e\not\in\tree$.

When we discuss finding the $\nK$-best dependency trees in \[sec:kbest-rc\], we implicitly change the above definition to use $\arbsrc{\edgeinclude{\graph}{e}}$ and $\arbsrc{\edgedelete{\graph}{e}}$ instead of $\arbs{\edgeinclude{\graph}{e}}$ and $\arbs{\edgedelete{\graph}{e}}$ respectively.

In this section, we will specifically focus on finding $\second{\graph}$, we extend this to finding the $\kbest{k}{\graph}$ in \[sec:kbest\]. Finding $\second{\graph}$ relies on the following fundamental theorem.

\[\]<span>thm</span><span>thmSecond</span> \[thm:second\]For any graph $\graph$ and $e\in\first{\graph}$ $$\second{\graph}=\first{(\edgedelete{\graph}{e})}$$ where $$\label{eq:del-e}
    e=\argmax_{e'\in\first{\graph}}\weight{\first{(\edgedelete{\graph}{e'})}}$$

There must be at least one edge $e\in\first{\graph}$ such that $e\not\in\second{\graph}$. Therefore, there exists an $e\in\first{\graph}$ such that $\second{\graph}=\first{(\edgedelete{\graph}{e})}$. Now suppose by way of contradiction that $e$ is not as given in \[eq:del-e\]. If we choose an $e'$ that satisfies \[eq:del-e\], then by definition $\weight{\first{(\edgedelete{\graph}{e'})}} > \weight{\first{(\edgedelete{\graph}{e})}}$. As $\first{(\edgedelete{\graph}{e'})}\neq\first{\graph}$, we arrive at a contradiction.

\[thm:second\] states that we can find $\second{\graph}$ by identifying an edge $e\in\first{\graph}$ such that $\second{\graph}=\first{(\edgedelete{\graph}{e})}$. We next show an efficient method for identifying this edge, as well as the weight of $\second{\graph}$ without actually having to find $\second{\graph}$.

\[<span> Blue</span> and <span> red</span> edges\] For any graph $\graph$, tree $\tree\in\arbs{\graph}$, and edge $e=\edgeij\in\tree$, the set of $\blueedges{\graph}{e}{\tree}$ and $\rededges{\graph}{e}{\tree}$ are defined by[^12] $$\begin{aligned}
    \blueedges{\graph}{e}{\tree} \defeq \{e'=&\edge{i'}{j} \mid  \weight{e'} \le \weight{e}, \nonumber\\ 
    &\tree \setminus \{e\} \cup \{e'\} \in \arbs{\graph} \}  \\
    \rededges{\graph}{e}{\tree} \defeq \{e'=&\edge{i'}{j}  \mid e'\not\in\blueedges{\graph}{e}{\tree} \}\end{aligned}$$ An example of <span> blue</span> and <span> red</span> edges are given in \[fig:blue\].

\[\]<span>lemma</span><span>lemmaOneDiff</span> \[lemma:one-diff\]For any graph $\graph$, if $\first{\graph}=\greedy{\graph}$, then for some $e\in\first{\graph}$ and $e'\in\blueedges{\graph}{e}{\first{\graph}}$ $$\second{\graph} = \first{\graph} \setminus \{e\} \cup \{e'\}$$

By \[thm:second\], we have $\second{\graph}=\first{(\edgedelete{\graph}{e})}$ where $e=\edge{i}{j}$ is chosen according to \[eq:del-e\]. Consider the graph $\edgedelete{\graph}{e}$; we have that $\greedy{\edgedelete{\graph}{e}}=\first{\graph}\setminus\{e\}\cup\{e'\}$ where $e'$ is the second best incoming edge to $j$ in $\graph$ by the definition of the greedy graph.

1.  Then $\greedy{\edgedelete{\graph}{e}}$ is a tree and $\first{(\edgedelete{\graph}{e})}=\greedy{\edgedelete{\graph}{e}}$.

2.  Then, $\greedy{\edgedelete{\graph}{e}}$ has a cycle $\cg$ by construction. Since this is a greedy graph, cycle $\cg$ is critical. In the expansion phase of the $1$-best algorithm, we will break the cycle $\cg$.

    1.  Then, $e'\not\in\first{(\edgedelete{\graph}{e})}$ and we must choose an edge $e''=\edge{i'}{j}$ to be in $\first{(\edgedelete{\graph}{e})}$. We require that $e''\in\blueedges{\graph}{e}{\first{\graph}}$ as we would otherwise re-introduce a cycle in the expansion phase, which is not possible. Therefore, $\second{\graph}=\first{\graph}\setminus\{e\}\cup\{e''\}$.

    2.  Then, there exists an edge $f=\edge{i''}{j'}\in\cg$ (and in $\first{\graph}$) which is not in $\second{\graph}$. Instead, we choose $f'=\edge{i'}{j'}$ to be in $\second{\graph}$. Therefore, $\second{\graph}=\first{\graph}\setminus\{e, f\}\cup\{e', f'\}$. However, it is not possible for $f'$ and $e$ to form a cycle and so $\tree=\first{\graph}\setminus\{f\}\cup\{f'\}\in\arbs{\graph}$ and $\weight{\tree}>\weight{\second{\graph}}$. This is a contradiction as only $\weight{\first{\graph}}>\weight{\second{\graph}}$.

\[lemma:one-diff\] can be understood more clearly by following the worked example in \[fig:blue\]. The moral of \[lemma:one-diff\] is that in the base case where there are no critical cycles, we only need to examine the <span>blue</span> edges of the greedy graph to find the second best tree. Furthermore, our second best tree will only differ from our best tree by exactly one <span>blue</span> edge. @CameriniFM80 make use of the concepts of the <span>blue</span> and <span>red</span> edge sets, but rather than consider a base case as \[lemma:one-diff\], they propose an ordering in which to visit the edges of the graph. This results in several properties about the possible orderings, requiring much more complicated proofs.

\[Swap cost\] For any graph $\graph$, tree $\tree\in\arbs{\graph}$, and edge $e\in\tree$, the denotes the minimum change to a tree weight to replace $e$ by a single edge in $\tree$. It is given by $$\swapcost{\graph,\tree}{e}=\min_{e'\in\blueedges{\graph}{e}{\tree}}\left(\weight{e} - \weight{e'}\right)$$ We will shorthand $\swapcost{\graph}{e}$ to mean $\swapcost{\graph,\first{\graph}}{e}$.

\[cor:greedy-second\] For any graph $\graph$, if $\first{\graph}=\greedy{\graph}$, then $\second{\graph}=\first{(\edgedelete{\graph}{e})}$ where $e$ is given by $$\label{eq:min-cost}
    e=\argmin_{e'\in\first{\graph}}\swapcost{\graph}{e'}$$ Furthermore, $\weight{\second{\graph}}=\weight{\first{\graph}} - \swapcost{\graph}{e}$.

\[cor:greedy-second\] provides us a procedure for finding the best edge to remove to find $\second{\graph}$ as well as its weight in the base case of $\graph$ having no critical cycles. We next illustrate what must be done in the recursive case when a critical cycle exists.

\[htb!\]

\[\]<span>lemma</span><span>lemmaExpansion</span> \[lemma:expansion\]For any $\graph$ with a critical cycle $\cg$, either $\second{\graph}\!=\!\stitch{\second{(\contract{\graph}{\cg})}}{\cg}$ (with $\weight{\second{\graph}}\!=\!\weight{\second{(\contract{\graph}{\cg})}}$) or $\second{\graph}\!=\!\first{(\edgedelete{\graph}{e})}$ (with $\weight{\second{\graph}}\!=\!\weight{\first{\graph}}-\swapcost{\graph}{e}$) for some $e\in\cg\cap\first{\graph}$.

It must be that $\second{\graph}=\stitch{\second{(\contract{\graph}{\cg})}}{\cg}$ or $\second{\graph}\neq\stitch{\second{(\contract{\graph}{\cg})}}{\cg}$.

1.  Since the weight of a tree is preserved during expansion, we are done.

2.  Then, for all $e'\!\in\!\first{(\contract{\graph}{\cg})}$, $\prov(e')\!\in\!\second{\graph}$. Therefore, if $j$ is the entrance site of $\cg$ in $\first{(\contract{\graph}{\cg})}$, $\second{\graph}\!=\!\prov(\first{(\contract{\graph}{\cg})})\cup \second{\cg_j}$. As $\first{\cg_j}\!=\!\greedy{\cg_j}$, by \[cor:greedy-second\], $\second{\cg_j}\!=\!\first{(\edgedelete{\cg_j}{e})}$ for $e\!\in\!\first{\cg_j}$ and $\weight{\second{\cg_j}}\!=\!\weight{\first{\cg_j}}-\swapcost{\cg_j}{e}$. Thus, $\second{\graph}\!=\!\first{(\edgedelete{\graph}{e})}$ where $e\!\in\!\cg\!\cap\!\tree$ and $\weight{\second{\graph}}\!=\!\weight{\first{\graph}}-\swapcost{\graph}{e}$.

Combining \[cor:greedy-second\] and \[lemma:expansion\], we can directly modify $\opt$ to find the weight of $\second{\graph}$ and the edge we must remove to obtain it. We detail this algorithm as $\optnext$ in \[alg:next-best\].

\[\]<span>thm</span><span>thmOptnext</span> \[thm:optnext\]For any graph $\graph$, executing $\optnextCall{\graph}$ returns $\first{\graph}$ and $\langle w, e \rangle$ such that $\second{\graph}=\first{(\edgedelete{\graph}{e})}$ and $\weight{\second{\graph}}=w$.

$\optnextCall{\graph}$ returns $\first{\graph}$ by the correctness of $\opt$. We prove that $w, e$ satisfy the above conditions.

1.  Then, by \[cor:greedy-second\] we can find the best edge to remove and the weight of $\second{\graph}$.

2.  Then, $\graph$ has a critical cycle $\cg$. By \[lemma:expansion\], we can either recursively call $\optnextCall{\contract{\graph}{\cg}}$ or examine the edges in $\cg\cap\first{\graph}$ to find the best edge to remove and the weight of $\second{\graph}$.

#### Runtime analysis.

We know that without lines \[line:argmin1,line:w1,line:argmin2,line:w2\], $\optnext$ is identical to $\opt$ and so will run in $\bigo{\nN^2}$. We call $\bar{w}$ at most $\nN+2$ times during a full call of $\optnext$: $\nN$ times from lines \[line:argmin1,line:argmin2\] combined, once from \[line:w1\], and once from \[line:w2\]. To find $\bar{w}$, we first need to find the set of <span>blue</span> edges, which can be done in $\bigo{\nN}$ by computing the reachability graph. Then, we need another $\bigo{\nN}$ to find the minimising value. Therefore, $\optnext$ does $\bigo{\nN^2}$ extra work than $\opt$ and so retains the runtime of $\bigo{\nN^2}$. @CameriniFM80 require $\first{\graph}$ to be known ahead of time. This results in having to run the original algorithm in $\bigo{\nN^2}$ time and then having to do the same amount of work as $\optnext$ because they must still contract the graph. Therefore, $\optnext$ has a constant-time speed-up over its counterpart in @camerini1979note.=-1

Finding the $\nK\th$ Best Tree {#sec:kbest}
==============================

In the previous section, we found an efficient method for finding $\second{\graph}$. We now utilize this method to efficiently find the $\nK$-best trees.

\[\]<span>lemma</span><span>lemmaKbest</span> \[lemma:k-best\]For any graph $\graph$ and $\nK>1$, there exists a subgraph $\graph'\subseteq\graph$ and $1 \le l < \nK$ such that $\kbest{l}{\graph}=\first{\graph'}$ and $\kbest{\nK}{\graph}=\second{\graph'}$.

There must exist some subgraph $\graph'\subseteq\graph$ such that $\kbest{\nK}{\graph}=\second{\graph'}$. Suppose by way of contradiction that there does not exist an $l < \nK$ such that $\kbest{l}{\graph}=\first{\graph'}$. However, since $\weight{\first{\graph'}} > \weight{\kbest{\nK+1}{\graph}}$, $\first{\graph'}$ must be in the $\nK$-highest weighted trees. Therefore, there must exist an $l$ such that $\kbest{l}{\graph}=\first{\graph'}$

\[lemma:k-best\] suggests that we can find the $\nK$-best trees by only examining the second best trees of subgraphs of $\graph$. This idea is formalized as algorithm $\kbestalg$ in \[alg:kbest\]. A walk-through of the exploration space using $\kbestalg$ for our example graph in \[fig:example\] is shown in \[fig:kbest\].

\[\]<span>thm</span><span>thmKbest</span> For any graph $\graph$ and $\nK \!>\! 0$, at any iteration $1\le k \le K$, $\kbestalgCall{\graph}{\nK}$ returns $\kbest{k}{\graph}$.

We prove this by induction on $k$.

Then, $k=1$ and $\first{\graph}$ is returned by \[thm:optnext\].

Assume that for all $l\le k$, at iteration $l$, $\kbest{l}{\graph}$ is returned. Now consider iteration $k+1$, by \[lemma:k-best\], we know that $\kbest{k+1}{\graph}=\second{\graph'}$ where $\first{\graph'}=\kbest{l}{\graph}$ for some $l \le k$. By the induction hypothesis, $\kbest{l}{\graph}$ is returned at the $l\th$ iteration, and by \[thm:optnext\], we have pushed $\second{\graph'}$ onto the queue. Therefore, we will return $\kbest{k+1}{\graph}$.

\[htb!\]

                          $\nK=10$                   $\nK=20$                   $\nK=50$          
  --------------- ------------------------- -------------------------- -------------------------- --
  @CameriniFM80    $6.95\hphantom{\times}$   $14.04\hphantom{\times}$   $35.11\hphantom{\times}$  
  $\kbestalg$      $4.89\hphantom{\times}$   $10.10\hphantom{\times}$   $25.63\hphantom{\times}$  
  Speed-up              $1.42\times$         $\hphantom{1}1.39\times$   $\hphantom{1}1.37\times$  

  : Runtime experiment for parsing the $K$-best spanning trees in the English UD test set [@ud]. Times are given in $10^{-2}$ seconds for the average parse of the $K$-best spanning trees. <span data-label="tab:runtime"></span>

#### Runtime analysis.

We call $\optnext$ once at the start of the algorithm, then every subsequent iteration we make two calls to $\optnext$. As we have $K-1$ iterations , the runtime of $\kbestalg$ is $\bigo{\nK \nN^2}$. The first call to $\optnext$ in each iteration finds the $K\th$ best tree as well as an edge to remove. @CameriniFM80 make one call to of $\opt$ and two calls to $\optnext$ which only finds the weight-edge pair of our algorithm. Therefore, $\kbestalg$ has a constant time speed-up on the original algorithm.[^13]

#### A short experiment.

We empirically measure the constant time speed-up between $\kbestalg$ and the original algorithm of @CameriniFM80. We take the English UD test set (as used for \[fig:experiment\]) and find the $10$, $20$, and $50$ best spanning trees using both algorithms.[^14] We give the results of the experiment in \[tab:runtime\].[^15] We note that on average $\kbestalg$ leads to a $1.39$ times speed-up. This is lower than we anticipated as we have to make half as many calls to $\optnext$ than the original algorithm. However, in the original $\optnext$ of @CameriniFM80, we do not require to stitch together the tree, which may explain the slightly smaller speed-up.

Finding the $\nK\th$ Best *Dependency* Tree {#sec:kbest-rc}
===========================================

In this section, we present a novel extension to the algorithm presented thus far, that allows us to efficiently find the $\nK$-best dependency trees. Recall that we consider dependency trees to be spanning trees *with a root constraint* such that only one edge may emanate from $\root$. , we can use $\kbestalg$ where we initialize the queue with $\first{(\edgeinclude{\graph}{e_{\root}})}$ for each $e_{\root}=\edge{\root}{j}\in\graph$. However, this adds a $\bigo{\nN^3}$ component to our runtime as we have to call $\opt$ $\nN$ times. Instead, our algorithm maintains the $\bigo{\nK \nN^2}$ runtime as the regular $\nK$-best algorithm. We begin by noting that we can find second best dependency tree, by finding either the best dependency tree with a different root edge or the second best tree with the same root edge.

\[\]<span>lemma</span><span>lemmaSecondRc</span> \[lemma:second-rc\]For any graph $\graph$ and edge $e_{\root}=\edge{\root}{j}\in\kbestrc{1}{\graph}$, $\kbestrc{2}{\graph}=\kbestrc{1}{(\edgedelete{\graph}{e_{\root}})}$ or $\kbestrc{2}{\graph}=\kbestrc{2}{(\edgeinclude{\graph}{e_{\root}})}$.

If $e_{\root}\!\not\in\!\kbestrc{2}{\graph}$, then clearly $\kbestrc{2}{\graph}\!=\!\kbestrc{1}{(\edgedelete{\graph}{e_{\root}})}$. Otherwise, $e_{\root}\in\kbestrc{2}{\graph}$. As $e_{\root}\in\kbestrc{1}{\graph}$, $\kbestrc{2}{\graph}=\kbestrc{2}{(\edgeinclude{\graph}{e_{\root}})}$.

\[\]<span>lemma</span><span>lemmaKbestRc</span> \[lemma:k-best-rc\]For any graph $\graph$ and $\nK>1$, if $e=\edge{\root}{j}\in\kbestrc{\nK}{\graph}$, then either $e$ is not in any of the $\nK\!-\!1$-best trees or there exists a subgraph $\graph'\subseteq\graph$ and $1 \le l < \nK$ such that $\kbestrc{l}{\graph}=\kbestrc{1}{\graph'}$, $e\in\kbestrc{1}{\graph'}$ and $\kbestrc{\nK}{\graph}=\kbestrc{2}{\graph'}$.

It must be that either there exists an $1\le l < \nK$ such that $e\in\kbestrc{l}{\graph}$ (Case 1) or no such $l$ exists (Case 2).

1.  Consider the graph $\edgeinclude{\graph}{e}$. Under our definition of edge-inclusion graphs for dependency trees, $\arbs{\edgeinclude{\graph}{e}}=\arbsrc{\edgeinclude{\graph}{e}}$. Then, by \[lemma:k-best\], there exists a $l'$ and $\graph'$ such that $\kbestrc{l'}{(\graph}=\kbestrc{1}{\graph'}$ and $\kbestrc{\nK}{\graph}=\kbestrc{2}{\graph'}$.

2.  Then, $e$ is not in any of the $(\nK\!-\!1)$-best trees.

\[lemma:k-best-rc\] suggests that we can find the $\nK$-best dependency trees, by examining the second best dependency trees of subgraphs of $\graph$ or finding the best dependency tree with a unique root edge. This idea is formalized as algorithm $\kbestrcalg$ in \[alg:kbest-rc\]. A walk-through of the exploration space using $\kbestrcalg$ for our example graph in \[fig:example\] is shown in \[fig:kbest-rc\].

\[\]<span>thm</span><span>thmKbestRc</span> For any graph $\graph$ and $\nK \ge 1$, at iteration $1\le k \le K$, $\kbestrcalgCall{\graph}{\nK}$ returns $\kbestrc{k}{\graph}$.

We prove this by induction on $k$.

Then, $k=1$ and $\first{\graph}$ is returned by the correctness of $\opt$.

Assume that for all $l\le k$, at iteration $l$, $\kbestrc{l}{\graph}$ was returned. Now consider iteration $k+1$, by \[lemma:k-best-rc\], we know that either $\kbestrc{k+1}{\graph}$ has a unique root edge to the $k$-best trees (Case 1) or $e=\edge{\root}{j}$ and there exists a $\graph'$ and $l \le k$ such that $\first{\graph'}=\kbest{l}{\graph}$, $e\in\kbest{l}{\graph}$, and $\kbestrc{k+1}{\graph}=\kbestrc{2}{\graph'}$ (Case 2).

1.  There always exists a tree in the queue that has a unique root edge to all trees that came before it. Furthermore, it is the highest such tree by the correctness of $\opt$.

2.  By our induction hypothesis, $\kbestrc{l}{\graph}$ is returned at the $l\th$ iteration, and by \[thm:optnext\], we have pushed $\kbestrc{2}{\edgeinclude{\graph'}{e}}$ onto the queue. Therefore, we will return $\kbestrc{k+1}{\graph}$.

#### Runtime analysis.

At the start of the algorithm, we call $\opt$ twice and $\optnext$ once. Then, at each iteration we either make two calls two $\optnext$, or two calls to $\opt$ and one call to $\optnext$. As both algorithms have a runtime of $\bigo{\nN^2}$, each iteration has a runtime of $\bigo{\nN^2}$. Therefore, running $\nK$ iterations gives a runtime of $\bigo{\nK \nN^2}$.

Conclusion
==========

In this paper, we provided a simplification to @CameriniFM80's $\bigo{\nK \nN^2}$ $\nK$-best spanning trees algorithm. Furthermore, we provided a novel extension to the algorithm that decodes the $\nK$-best dependency trees in $\bigo{\nK \nN^2}$. We motivated the need for this new algorithm as using regular $\nK$-best decoding yields up to $36\%$ trees which violation the root constraint. This is a substantial (up to $44$ times) increase in the violation rate from decoding the one-best tree, and thus such an algorithm is even more important than in the one-best case. We hope that this paper encourages future research in $\nK$-best dependency parsing.

Acknowledgments {#acknowledgments .unnumbered}
===============

We would like to thank the reviewers for their valuable feedback and suggestions to improve this work. The first author is supported by the University of Cambridge School of Technology Vice-Chancellor's Scholarship as well as by the University of Cambridge Department of Computer Science and Technology's EPSRC.

Ethical Concerns {#ethical-concerns .unnumbered}
================

We do not foresee how the more efficient algorithms presented this work exacerbate any existing ethical concerns with NLP systems.

[^1]: \[footnote:code\]Our implementation is available at <https://github.com/rycolab/spanningtrees>.

[^2]: In fact, an anonymous reviewer called it "one of the most 'feared' algorithms in dependency parsing."=-1

[^3]: While our algorithm is by no means *simple*, an anonymous reviewer called it "a big step in that direction."

[^4]: There are certain exceptions to this such as the Prague Treebank [@prague_dep].

[^5]: @zmigrod-etal-2020-please conduct a similar experiment for only the one-best tree.

[^6]: We note that @stanza do apply the root constraint for one-best decoding, albeit with a sub-optimal algorithm.

[^7]: As we use the algorithm in @zmigrod-etal-2020-please as our base algorithm, we borrow their notation wherever convenient.

[^8]: We make this assumption for simplicity, the algorithms presented here will also work with multi-graphs. This might be desirable for decoding labeled dependency trees. However, we note that in most graph-based parsers such as @stanza and @ma, dependency labels are extracted after the unlabeled tree has been decoded.

[^9]: We make this assumption as in the context of dependency parsing, we generate scores for each possible edge. Furthermore, @Tarjan77 prove that the runtime of finding the best tree for dense graphs is $\bigo{\nN^2}$. This is $\bigo{\abs{\edges}\log \nN}$ in the non-dense case.

[^10]: For inference, the weight of a trees often decomposes multiplicatively rather than additively over the edges. One can take the exponent (or logarithm) of the original edge weights to make the weights distribute additively (or multiplicative).

[^11]: For a more complete and detailed description as well as a proof of correctness, please refer to the original manuscripts.

[^12]: We can also define $\blueedges{\graph}{e}{\tree}$ as $\edge{i'}{j}\in\blueedges{\graph}{e}{\tree} \iff i'$ is an ancestor of $j$ in $\tree$ and $\rededges{\graph}{e}{\tree}$ as $\edge{i'}{j}\in\rededges{\graph}{e}{\tree} \iff i'$ is a descendant of $j$ in $\tree$. This equivalence exists as we can only swap an incoming edge to $j$ in $\tree$ without introducing a cycle if the new edge emanates from an ancestor of $j$. The exposition using ancestors and descendants is more similar to the exposition originally presented by @CameriniFM80.

[^13]: In practice, we maintain a set of edges to include and exclude to save space.

[^14]: Implementations for both versions can be found in our code release (see \[footnote:code\])

[^15]: The experiment was conducted using an Intel(R) Core(TM) i7-7500U processor with 16GB RAM.

{'source': 'arXiv_out/2106'}