Stanford: Probabilistic Edit Distance Metrics for STS

First Joint Conference on Lexical and Computational Semantics (*SEM), pages 648–654, Montr´eal, Canada, June 7-8, 2012. c⃝2012 Association for Computational Linguistics Stanford: Probabilistic Edit Distance Metrics for STS Mengqiu Wang and Daniel Cer∗ Computer Science Department Stanford University Stanford, CA 94305 USA {mengqiu,danielcer}@cs.stanford.edu Abstract This paper describes Stanford University’s submission to SemEval 2012 Semantic Tex- tual Similarity (STS) shared evaluation task. Our proposed metric computes probabilistic edit distance as predictions of semantic sim- ilarity. We learn weighted edit distance in a probabilistic finite state machine (pFSM) model, where state transitions correspond to edit operations. While standard edit dis- tance models cannot capture long-distance word swapping or cross alignments, we rectify these shortcomings using a novel pushdown automaton extension of the pFSM model. Our models are trained in a regression framework, and can easily incorporate a rich set of lin- guistic features. The performance of our edit distance based models is contrasted with an adaptation of the Stanford textual entailment system to the STS task. Our results show that the most advanced edit distance model, pPDA, outperforms our entailment system on all but one of the genres included in the STS task. 1 Introduction We describe a probabilistic edit distance based met- ric, which was originally designed for evaluating machine translation quality, for computing seman- tic textual similarity (STS). This metric models weighted edit distance in a probabilistic finite state machine (pFSM), where state transitions correspond to edit operations. The weights of the edit op- erations are automatically learned in a regression framework. One of the major contributions of this ∗ Daniel Cer is one of the organizers for the STS task. The STS test set data was not used in any way for the development or training of the systems described in this paper. paper is a novel extension of the pFSM model into a probabilistic Pushdown Automaton (pPDA), which enhances traditional edit-distance models with the ability to model phrase shift and word swapping. Furthermore, we give a new log-linear parameteri- zation to the pFSM model, which allows it to easily incorporate rich linguistic features. We contrast the performance of our probabilistic edit distance metric with an adaptation of the Stanford textual entailment system to the STS task. 2 pFSMs for Semantic Textual Similarity We start off by framing the problem of semantic tex- tual similarity in terms of weighted edit distance cal- culated using probabilistic finite state machines (pF- SMs). A FSM defines a language by accepting a string of input tokens in the language, and reject- ing those that are not. A probabilistic FSM defines the probability that a string is in a language, extend- ing on the concept of a FSM. Commonly used mod- els such as HMMs, n-gram models, Markov Chains and probabilistic finite state transducers all fall in the broad family of pFSMs (Knight and Al-Onaizan, 1998; Eisner, 2002; Kumar and Byrne, 2003; Vi- dal et al., 2005). Unlike all the other applications of FSMs where tokens in the language are words, in our language …

Content truncated to 500 words