3
$\begingroup$

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.

$\endgroup$

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.