Extracting lexically divergent paraphrases from Twitter

We present MULTIP (Multi-instance Learn-ing Paraphrase Model), a new model suited to identify paraphrases within the short mes-sages on Twitter. We jointly model para-phrase relations between word and sentence pairs and assume only sentence-level annota-tions during learning. Using this principled la-tent variable model alone, we achieve the per-formance competitive with a state-of-the-art method which combines a latent space model with a feature-based supervised classifier. Our model also captures lexically divergent para-phrases that differ from yet complement previ-ous methods; combining our model with pre-vious work significantly outperforms the state-of-the-art. In addition, we present a novel an-notation methodology that has allowed us to crowdsource a paraphrase corpus from Twit-ter. We make this new dataset available to the research community.