nips nips2012 nips2012-141 nips2012-141-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jingrui He, Hanghang Tong, Qiaozhu Mei, Boleslaw Szymanski
Abstract: Diversified ranking is a fundamental task in machine learning. It is broadly applicable in many real world problems, e.g., information retrieval, team assembling, product search, etc. In this paper, we consider a generic setting where we aim to diversify the top-k ranking list based on an arbitrary relevance function and an arbitrary similarity function among all the examples. We formulate it as an optimization problem and show that in general it is NP-hard. Then, we show that for a large volume of the parameter space, the proposed objective function enjoys the diminishing returns property, which enables us to design a scalable, greedy algorithm to find the (1 − 1/e) near-optimal solution. Experimental results on real data sets demonstrate the effectiveness of the proposed algorithm.
[1] A. Agarwal and S. Chakrabarti. Learning random walks to rank nodes in graphs. In ICML, pages 9–16, 2007. 8
[2] R. Agrawal, S. Gollapudi, A. Halverson, and S. Ieong. Diversifying search results. In WSDM, pages 5–14, 2009.
[3] C. J. C. Burges, K. M. Svore, P. N. Bennett, A. Pastusiak, and Q. Wu. Learning to rank using an ensemble of lambda-gradient models. Journal of Machine Learning Research - Proceedings Track, 14:25–35, 2011.
[4] G. Capannini, F. M. Nardini, R. Perego, and F. Silvestri. Efficient diversification of search results using query logs. In WWW (Companion Volume), pages 17–18, 2011.
[5] J. G. Carbonell and J. Goldstein. The use of mmr, diversity-based reranking for reordering documents and producing summaries. In SIGIR, pages 335–336, 1998.
[6] A. Dubey, S. Chakrabarti, and C. Bhattacharyya. Diversity in ranking via resistive graph centers. In KDD, pages 78–86, 2011.
[7] U. Feige, G. Kortsarz, and D. Peleg. The dense k-subgraph problem. Algorithmica, 29, 1999.
[8] T. H. Haveliwala. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. IEEE Trans. Knowl. Data Eng., 15(4):784–796, 2003.
[9] P. Jain, B. Kulis, and I. S. Dhillon. Inductive regularized learning of kernel functions. In NIPS, pages 946–954, 2010.
[10] T.-Y. Liu. Learning to rank for information retrieval. In SIGIR, page 904, 2010.
[11] Q. Mei, J. Guo, and D. R. Radev. Divrank: the interplay of prestige and diversity in information networks. In KDD, pages 1009–1018, 2010.
[12] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functionsłi. MATHEMATICAL PROGRAMMING, (1):265–294, 1973.
[13] L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998. Paper SIDL-WP-1999-0120 (version of 11/11/1999).
[14] F. Radlinski, P. N. Bennett, B. Carterette, and T. Joachims. Redundancy, diversity and interdependent document relevance. SIGIR Forum, 43(2):46–52, 2009.
[15] M. Srivastava, T. Abdelzaher, and B. Szymanski. Human-centric sensing. Phil. Trans. R. Soc. 370 ser. A(1958), pages 176–197, 2012.
[16] H. Tong, J. He, Z. Wen, R. Konuru, and C.-Y. Lin. Diversified ranking on large graphs: an optimization viewpoint. In KDD, pages 1028–1036, 2011.
[17] M. Y. S. Uddin, M. T. A. Amin, H. Le, T. Abdelzaher, B. Szymanski, and T. Nguyen. On diversifying source selection in social sensing. In INSS, 2012.
[18] J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural diversity in social contagion. PNAS, 109(16):596–5966, 2012.
[19] J. Wang, H. Do, A. Woznica, and A. Kalousis. Metric learning with multiple kernels. In NIPS, pages 1170–1178, 2011.
[20] M. J. Welch, J. Cho, and C. Olston. Search result diversity for informational queries. In WWW, pages 237–246, 2011.
[21] L. Wu. Social network effects on performance and layoffs: Evidence from the adoption of a social networking tool. Job Market Paper, 2011.
[22] E. P. Xing, A. Y. Ng, M. I. Jordan, and S. J. Russell. Distance metric learning with application to clustering with side-information. In NIPS, pages 505–512, 2002.
[23] C. Zhai, W. W. Cohen, and J. D. Lafferty. Beyond independent relevance: methods and evaluation metrics for subtopic retrieval. In SIGIR, pages 10–17, 2003.
[24] X. Zhu, A. B. Goldberg, J. V. Gael, and D. Andrzejewski. Improving diversity in ranking using absorbing random walks. In HLT-NAACL, pages 97–104, 2007.
[25] X. Zhu, J. Guo, X. Cheng, P. Du, and H. Shen. A unified framework for recommending diverse and relevant queries. In WWW, pages 37–46, 2011. 9