Learning to recognize features of valid textual inferences Bill MacCartney Stanford University

Learning to recognize features of valid textual inferences

• Bill MacCartney Stanford University

• with Trond Grenager, Marie-Catherine de Marneffe, Daniel Cer, and Christopher D. Manning

Textual inference as graph alignment

• Many efforts have converged on this approach [Haghighi et al. 05, de Salvo Braz et al. 05]

• Represent P & H as typed dependency graphs

• Graph nodes = words of sentence
• Graph edges = grammatical relations (subject, possessive, etc.)

• Find least-cost alignment of H to (part of) P

• Can H be (approximately) embedded within P?

• Use locally-decomposable cost model

• Lexical costs penalize aligning semantically unrelated words
• Structural costs penalize aligning dissimilar subgraphs

• Assume good alignment  valid inference

Example: graph alignment

Problems with alignment models

• Alignments are important, but…

• Good alignment valid inference:

• Assumption of upward monotonicity
• Assumption of locality
• Confounding of alignment and entailment

Problem 1: non-monotonicity

• In normal “upward monotone” contexts, broadening a concept preserves truth:

• P: Some Korean historians believe the murals are of Korean origin.

• H: Some historians believe the murals are of Korean origin.

• But not in “downward monotone” contexts:

• P: Few Korean historians doubt that Koguryo belonged to Korea.

• H: Few historians doubt that Koguryo belonged to Korea.

• Lots of constructs invert monotonicity!

Problem 2: non-locality

• To be tractable, alignment scoring must be local

• But valid inference can hinge on non-local factors:

Problem 3: confounding alignment & inference

• If alignment  entailment, lexical cost model must penalize e.g. antonyms, inverses:

• P: Stocks fell on worries that oil prices would rise this winter.
• H: Stock prices climbed.

• But aligner will seek the best alignment:

• P: Stocks fell on worries that oil prices would rise this winter.
• H: Stock prices climbed.

• Actually, we want the first alignment, and then a separate assessment of entailment! [cf. Marsi & Krahmer 05]

Solution: three-stage architecture

1. Linguistic analysis

• Typed dependencies from statistical parser [de Marneffe et al. 06]

• Collocations from WordNet (Bill hung_up the phone)

• Statistical named entity recognizers [Finkel et al. 05]

• Canonicalization of quantity, date, and money expressions

• P: Kessler’s team conducted 60,643 [60,643] face-to-face interviews...
• H: Kessler’s team interviewed more than 60,000 [>60,000] adults...

• Semantic role identification: PropBank roles [Toutanova et al. 05]

• Coreference resolution:

• P: Since its formation in 1948, Israel… H: Israel was established in 1948.

• Hand-built: acronyms, country and nationality, factive verbs

• TF-IDF scores

2. Aligning dependency graphs

• Beam search for least-cost alignment

• Locally decomposable cost model

• Can’t do Viterbi-style DP or heuristic search without this
• Assessment of global features postponed to next stage

• Lexical matching costs

• Use lexical semantic relatedness scores derived from WordNet, LSA, string sim, distributional similarity [Lin 98]
• Do not penalize antonyms, inverses, alternatives…

• Structural matching costs

• Each edge in graph of H determines path in graph of P
• Preserved edges get low cost; longer paths cost more

3. Features of valid inferences

• After alignment, extract features of inference

• Look for global characteristics of valid and invalid inferences
• Features embody crude semantic theories
• Feature categories: adjuncts, modals, quantifiers, implicatives, antonymy, tenses, pred-arg structure, explicit numbers & dates
• Alignment score is also an important feature

• Extracted features  statistical model  score

• Can learn feature weights using logistic regression
• Or, can use hand-tuned weights

• (Score ≥ threshold) ?  prediction: yes/no

• Threshold can be tuned

Features: restrictive adjuncts

• Does hypothesis add/drop a restrictive adjunct?

• Adjunct is dropped: usually truth-preserving
• Adjunct is added: suggests no entailment
• But in a downward monotone context, this is reversed
• P: In all, Zerich bought $422 million worth of oil from Iraq, according to the Volcker committee.
• H: Zerich bought oil from Iraq during the embargo.
• P: Zerich didn’t buy any oil from Iraq, according to the Volcker committee.
• H: Zerich didn’t buy oil from Iraq during the embargo.

• Generate features for add/drop, monotonicity

Features: modality

Features: factives & implicatives

• P: Libya has tried, with limited success, to develop its own indigenous missile, and to extend the range of its aging SCUD force for many years under the Al Fatah and other missile programs.

• H: Libya has developed its own domestic missile program.

• Evaluate governing verbs for implicativity class

• Unknown: say, tell, suspect, try, …
• Fact: know, acknowledge, ignore, …
• True: manage to, …
• False: fail to, forget to, …

• Need to check for -monotone context here too

• not try to win not win, but not manage to win not win

Evaluation: PASCAL RTE

• RTE = recognizing textual “entailment” [Dagan et al. 05]

• Does premise P “entail” hypothesis H?

• P: Wal-Mart defended itself in court today against claims that its female employees were kept out of jobs in management because they are women.
• H: Wal-Mart was sued for sexual discrimination.

• Three annual competitions (so far)

• RTE1 (2005): 567 dev pairs, 800 test pairs
• RTE2 (2006) and RTE3 (2007): 800 dev pairs, 800 test pairs

• Considerable variance from year to year

• High inter-annotator agreement (~95%)

Results & useful features

Results for all RTE data [updated]

What we have trouble with

• Non-entailment is easier than entailment

• Good at finding knock-out features
• But, hard to be certain that we’ve considered everything

• Lots of adjuncts, but which are restrictive?

• H: Maurice was subsequently killed in Angola.

• Multiword “lexical” semantics/world knowledge

• We’re pretty good at synonyms, hyponyms, antonyms
• But we aren’t good at recognizing multi-word equivalences
• P: David McCool took the money and decided to start Muzzy Lane in 2002.
• H: David McCool is the founder of Muzzy Lane. [RTE2-379]
• Other teams (e.g. LCC) have done well with paraphrase models

Conclusion

• Alignment models promising, but flawed:

• Assumption of monotonicity
• Assumption of locality
• Confounding of alignment and inference

• Solution: align, then judge validity of inference

• We extract global-level semantic features

• Working from richly-annotated, aligned dependency graphs … not just word sequences
• Features are designed to embody crude semantic theories

• Still lots of room to improve…