Optimization in Coreference Resolution is not Needed: A Nearly-Optimal Algorithm with Intensional Constraints

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 442–450, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Optimization in Coreference Resolution Is Not Needed: A Nearly-Optimal Algorithm with Intensional Constraints Manfred Klenner & ´Etienne Ailloud Computational Linguistics Zurich University, Switzerland {klenner, ailloud}@cl.uzh.ch Abstract We show how global constraints such as transitiv- ity can be treated intensionally in a Zero-One Inte- ger Linear Programming (ILP) framework which is geared to find the optimal and coherent partition of coreference sets given a number of candidate pairs and their weights delivered by a pairwise classifier (used as reliable clustering seed pairs). In order to find out whether ILP optimization, which is NP- complete, actually is the best we can do, we com- pared the first consistent solution generated by our adaptation of an efficient Zero-One algorithm with the optimal solution. The first consistent solution, which often can be found very fast, is already as good as the optimal solution; optimization is thus not needed. 1 Introduction One of the main advantages of Integer Linear Pro- gramming (ILP) applied to NLP problems is that prescriptive linguistic knowledge can be used to pose global restrictions on the set of desirable so- lutions. ILP tries to find an optimal solution while adhering to the global constraints. One of the central global constraints in the field of corefer- ence resolution evolves from the interplay of intra- sentential binding constraints and the transitivity of the anaphoric relation. Consider the following sentence taken from the Internet: ’He told him that he deeply admired him’. ’He’ and ’him’ are ex- clusive (i.e. they could never be coreferent) within their clauses (the main and the subordinate clause, respectively). A pairwise classifier could learn this given appropriate features or, alternatively, bind- ing constraints could act as a hard filter preventing such pairs from being generated at all. But in ei- ther case, since pairwise classification is trapped in its local perspective, nothing can prevent the classifier to resolve the ’he’ and ’him’ from the subordinate clause in two independently carried out steps to the same antecedent from the main clause. It is transitivity that prohibits such an as- signment: if two elements are both coreferent to a common third element, then the two are (transi- tively given) coreferent as well. If they are known to be exclusive, such an assignment is disallowed. But transitivity is beyond the scope of pairwise classification—it is a global phenomena. The so- lution is to take ILP as a clustering device, where the probabilities of the pairwise classifier are in- terpreted as weights and transitivity and other re- strictions are acting as global constraints. Unfortunately, in an ILP program every con- straint has to be extensionalized (i.e. all instantia- tions of the constraint are to be generated). Cap- turing transitivity for e.g. 150 noun phrases (about 30 sentences) already produces 1,500,000 equa- tions (cf. Section 4). Solving such ILP programs is far too slow for real applications …

Content truncated to 500 words