Given an input sentence ¢ , we would like to be able to compute the best parse; that is, a projective tree, 6 5 1 2 ¤ 3 ¢ 4 , that obtains the highest "score".
we follow (Eisner, 1996;Eisner and Satta, 1999;McDonald et al., 2005) and assume that the score of a complete spanning tree for a given sentence, whether probabilistically motivated or not, can be decomposed as a sum of local scores for each link (a word pair).