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.
