A Joint Information Model for N-Best Ranking

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 681–688 Manchester, August 2008 A Joint Information Model for n-best Ranking Patrick Pantel Yahoo! Inc. Santa Clara, CA 95054 me@patrickpantel.com Vishnu Vyas USC Information Sciences Institute Marina del Rey, CA vishnu@isi.edu Abstract In this paper, we present a method for modeling joint information when gene- rating n-best lists. We apply the method to a novel task of characterizing the simi- larity of a group of terms where only a small set of many possible semantic properties may be displayed to a user. We demonstrate that considering the re- sults jointly, by accounting for the infor- mation overlap between results, generates better n-best lists than considering them independently. We propose an informa- tion theoretic objective function for mod- eling the joint information in an n-best list and show empirical evidence that humans prefer the result sets produced by our joint model. Our results show with 95% confidence that the n-best lists gen- erated by our joint ranking model are significantly different from a baseline in- dependent model 50.0% ± 3.1% of the time, out of which they are preferred 76.6% ± 5.2% of the time. 1 Introduction Ranking result sets is a pervasive problem in the NLP and IR communities, exemplified by key- word search engines such as Google (Brin and Page 1998), machine translation systems (Zhang et al. 2006), and recommender systems (Sharda- nand and Maes 1995; Resnick and Varian 1997). Consider the lexical semantics task of explain- ing why a set of terms are similar: given a set of terms and a large set of possible explanations for © 2008. Licensed under the Creative Commons Attri- bution-Noncommercial-Share Alike 3.0 Unported license (http://creativecommons.org/licenses/by-nc- sa/3.0/). Some rights reserved. their similarity, one must choose only the best n explanations to display to a user. There are many ways to explain why terms are similar2; one way is to list the semantic properties that are shared by the terms. For example, consider the follow- ing set of terms corresponding to fruit names: {apple, ume, pawpaw, quince} Example semantic properties that could be used to explain their similarity include: they are products, they can be eaten, they are solid (but not they are companies, for example). The list of such semantic properties can be very large and some are much more informative than others. For example, the property can-be-eaten is much more informative of the similarity of {apple, ume, pawpaw, quince} than the property is-solid. Us- ing a simple measure of association between properties and queries, explained in detail later in this paper, one can rank each property and obtain the following three highest scoring properties for explaining the similarity of these terms: {they are products, they can be imported, they can be exported} Even though can be imported and can be ex- ported are highly ranked explanations, taken jointly, once we know one the other does not of- fer much more information since most things that can be imported can also …

Content truncated to 500 words