A constraint-satisfaction approach to dependency parsing and generation

Parsing and generation actions

• Create a candidate dependency from one word (head) to another (dependent); [generation] possibly add the dependent to the sentence
  • Head feature of candidate dependent must unify with some dependent feature of candidate head
  • Rigid word-order constraint must be satisfied
• Remove a candidate dependency
• [Generation] change the position of a word

Constraints

Lexical, grammatical entries

• NCS: [pos=N, num=sing,
        obl-dep = {[det=[pos=DT, dir=[side=left!, attr=1]]]},
        opt-dep = {[relmod=[pos=V*, dir=[side=right!, attr=1]]],
                   [adjmod=[pos=Adj, dir=[side=left!, attr=2]]]}]
  

  VT: [pos=VT, num=?n,
       obl-dep = {[subj=[pos=N, dir=[side=left!, attr=2],
                         num=?n]],
                  [dirobj=[pos=N, dir=[side=right, attr=1]]]},
       opt-dep = {[prepmod = [pos=Prep, dir=[side=right, attr=1]]]},
       head = [none] | [relmod=?self]
  

  V*R: [pos=V*, +rel,
        head=[relmod=?self]]
  

  that: [pos=N, lex=that,
         head=[pos=V, +rel, dir=[side=left!, attr=1]]]
  

  Adj: [pos=Adj,
        head = [adjmod=?self] | [predadj=?self]]
  

  be: [pos=V, lex=be,
       opt-dep = {[prednom=[pos=N, dir=[side=right, attr=2]]],
                  [predadj=[pos=Adj, dir=[side=right, attr=2]]]}]
  

  Prep: [pos=Prep,
         obl-dep = {[prepobj=[pos=N, dir=[side=right!, attr=2]]]}]
  

• boy: [pos=NCS]
  meal: [pos=NCS]
  cooked: [pos=VT, tns=past]
  for: [pos=Prep]
  is: [pos=V, lex=be, tns=pres, num=sing, pers=3]
  big: [pos=Adj]
  enough: [pos=Adj, head=[rel=predadj]]
  

Parsing

1. Parse words, returning all possible morphological parses, senses.
   
2. Assign each word sense an id and a position.
3. Create all possible dependencies between words (obeying strict constraints).
   
4. Calculate goodness (function of the extent to which constraints are satisfied).
5. Until goodness fails to improve, remove dependencies. (Or create a constraint satisfaction network joining the dependencies, updating their strengths until there are no changes.)
   
   

Generation

1. Lexicalize each dependency head and dependent.
2. Assign a position to each word.
3. Calculate goodness.
4. Until goodness fails to improve (or there are no changes of strengths of dependencies), either
   1. Add a new dependency between existing words.
   2. Add a new obligatory dependency from an existing head, creating a dependent place holder.
   3. Merge an existing word with a dependent place holder.
   4. Create a new word to fill a dependent place holder.
   5. Remove a dependency.
   6. Change the position of a word.
5. Generate words from morphological information.

© 2008. Indiana University and Michael Gasser. www.cs.indiana.edu/classes/B651/dep_proc.html 2008-03-17