I am looking for an algorithm that will get an optimal projective undirected dependency parse.

That is, given the sentence 'Mary does love John', and an edge-weight function $f$ (that is, a function from pairs of words in the sentence to real numbers), like

$f$(Mary,does) = 1

$f$(Mary,love) = 5

$f$(Mary,John) = 2

$f$(does,love) = 2

$f$(does,John) = 3

$f$(love,John) = 5

I want an algorithm that will give the edges of the maximum projective spanning tree as: {(Mary,love), (does,love), (love,John)} with a total weight of 12. That is, it should give this:

Crucially, the algorithm shouldn't give {(Mary,love), (does,John), (love,John)}, even though it has a higher weight of 13, because in that case the dependencies are not projective (the arcs (Mary,love), (does,John) cross each other). That is, it should not give this:

Equivalently, I am asking: what algorithms exist for finding a Minimum/Maximum Spanning Tree on an ordered graph, such that the resulting structure is projective? A bit more formally: given a totally ordered set of nodes $(S,<)$, and a edge weight function $W: S × S → ℝ$, is there a good algorithm for finding the optimal-weight spanning tree over this set of nodes, such that the resulting structure has the property that every sub-tree is contiguous in the ordering (for any subtree $T$, for all $t,s$ in $T$ there is no $r$ not in $T$ such that $t<r<s$)?

  • Without the projectivity requirement, any classic MST algorithm will do (such as Prim's, or Kruskal's).
  • With the projectivity requirement, but for directed graphs/dependencies Eisner's algorithm (a faster version of Arc-factored Projective Parsing) is standard for getting the optimal directed projective dependency parse.

I am looking for a (probably CYK-like) algorithm like Eisner's, but which will work on undirected dependency parsing. That is, an algorithm for finding the maximum projective spanning tree for undirected ordered graphs. Or, perhaps, a proof that Eisner's algorithm will with some modification to work on undirected graphs will be guaranteed to give the optimal projective spanning tree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.