Improving Diversity in Ranking using Absorbing Random Walks

Proceedings of NAACL HLT 2007, pages 97–104, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Improving Diversity in Ranking using Absorbing Random Walks Xiaojin Zhu Andrew B. Goldberg Jurgen Van Gael David Andrzejewski Department of Computer Sciences University of Wisconsin, Madison Madison, WI 53705 {jerryzhu, goldberg, jvangael, andrzeje}@cs.wisc.edu Abstract We introduce a novel ranking algorithm called GRASSHOPPER, which ranks items with an emphasis on diversity. That is, the top items should be different from each other in order to have a broad coverage of the whole item set. Many natural lan- guage processing tasks can benefit from such diversity ranking. Our algorithm is based on random walks in an absorbing Markov chain. We turn ranked items into absorbing states, which effectively pre- vents redundant items from receiving a high rank. We demonstrate GRASSHOP- PER’s effectiveness on extractive text sum- marization: our algorithm ranks between the 1st and 2nd systems on DUC 2004 Task 2; and on a social network analy- sis task that identifies movie stars of the world. 1 Introduction Many natural language processing tasks involve ranking a set of items. Sometimes we want the top items to be not only good individually but also di- verse collectively. For example, extractive text sum- marization generates a summary by selecting a few good sentences from one or more articles on the same topic (Goldstein et al., 2000). This can be for- mulated as ranking all the sentences, and taking the top ones. A good sentence is one that is represen- tative, i.e., similar to many other sentences, so that it likely conveys the central meaning of the articles. On the other hand, we do not want multiple near- identical sentences. The top sentences should be di- verse. As another example, in information retrieval on news events, an article is often published by multi- ple newspapers with only minor changes. It is unde- sirable to rank all copies of the same article highly, even though it may be the most relevant. Instead, the top results should be different and complemen- tary. In other words, one wants ‘subtopic diversity’ in retrieval results (Zhai et al., 2003). The need for diversity in ranking is not unique to natural language processing. In social network anal- ysis, people are connected by their interactions, e.g., phone calls. Active groups of people have strong in- teractions among them, but many groups may exist with fewer interactions. If we want a list of people that represent various groups, it is important to con- sider both activity and diversity, and not to fill the list with people from the same active groups. Given the importance of diversity in ranking, there has been significant research in this area. Per- haps the most well-known method is maximum marginal relevance (MMR) (Carbonell and Gold- stein, 1998), as well as cross-sentence informational subsumption (Radev, 2000), mixture models (Zhang et al., 2002), subtopic diversity (Zhai et al., 2003), diversity penalty (Zhang et al., 2005), and others. The basic idea is to penalize redundancy …

Content truncated to 500 words