| << Prev | - Up - | Next >> |
In this section, we develop a constraint model for the formal framework of Section 5.2. In essence, the constraint model is an axiomatization of admissible dependency trees, but also has a reading as a constraint program. It is carefully formulated to take effective advantage of modern technological support for constraint programming.
The approach is, as usual, a reduction to a CSP. We introduce variables to represent the quantities and mappings mentioned in the formal model, and formulate constraints on them that precisely capture the conditions that the formal model stipulates.
Our approach takes essential advantage of the intrinsic finiteness of the problem: (1) a dependency tree has precisely one node for each word, (2) there are finitely many edges labeled with roles that can be drawn between n nodes, (3) for each word, there are finitely many possible lexical entries. Thus the problem is to pick a set of edges and, for each node, a lexical entry, such that (a) the result is a tree, (b) none of the grammatical conditions are violated. Viewed in this light, dependency parsing is a configuration problem, and therefore it is no surprise that constraint programming should be able to address it very effectively.
| << Prev | - Up - | Next >> |