Selecting expansion terms as a set via integer linear programming

ABSTRACT

Pseudo-relevance feedback via query expansion has been widely studied from various perspectives in the past decades. Its effectiveness in improving retrieval effectiveness has been shown in many tasks. A variety of criteria were proposed to select additional terms for the original queries. However, most of the existing methods weight and select terms individually and do not consider the impact of term-to-term relationship. In this paper, we first examine the influence of combinations of terms through data analysis, which demonstrate the significant effect of term-to-term relationship on retrieval effectiveness. Then, to address this problem, we formalize the query expansion task as an integer linear programming (ILP) problem. The model combines the weights learned from a supervised method for individual terms, and integrates constraints to capture relations between terms. Finally, three standard TREC collections are used to evaluate the proposed method. Experimental results demonstrate that the proposed method can significantly improve the effectiveness of retrieval.

References

1. D. Alevras and M. W. Padberg. Linear Optimization and Extensions: Problems and Solutions. Springer, 2001.
2. J. Bhogal, A. Macfarlane, and P. Smith. A review of ontology based query expansion. Information Processing & Management, 43(4):866--886, 2007.
3. C. Buckley. Automatic query expansion using smart : Trec 3. In Proceedings of The third Text REtrieval Conference (TREC-3), pages 69--80, 1994.
4. G. Cao, J.-Y. Nie, J. Gao, and S. Robertson. Selecting good expansion terms for pseudo-relevance feedback. In SIGIR '08, pages 243--250, 2008.
5. C. Carpineto, R. de Mori, G. Romano, and B. Bigi. An information-theoretic approach to automatic query expansion. ACM Transactions on Information Systems, 19(1):1--27, 2001.
6. K. Collins-Thompson. Estimating robust query models with convex optimization. In Advances in Neural Information Processing Systems 21 (NIPS), pages 329--336, 2008.
7. K. Collins-Thompson. Reducing the risk of query expansion via robust constrained optimization. In Proceedings of the Eighteenth International Conference on Information and Knowledge Management (CIKM 2009), pages 329--336, Hong Kong, China, 2009. ACM.
8. K. Collins-Thompson and J. Callan. Estimation and use of uncertainty in pseudo-relevance feedback. In SIGIR '07, pages 303--310, 2007.
9. B. Croft, D. Metzler, and T. Strohman. Search Engines: Information Retrieval in Practice. Addison-Wesley Publishing Company, USA, 1st edition, 2009.
10. H. Cui, J.-R. Wen, J.-Y. Nie, and W.-Y. Ma. Query expansion by mining user logs. IEEE Transactions on Knowledge and Data Engineering, 15(4):829--839, 2003.
11. X. Huang and W. B. Croft. A unified relevance model for opinion retrieval. In Proceedings of 16th Conference on Information and Knowledge Management(CIKM 2009), Hong Kong, China, 2009.
12. K. S. Lee, W. B. Croft, and J. Allan. A cluster-based resampling method for pseudo-relevance feedback. In SIGIR '08, pages 235--242, 2008.
13. D. I. Moldovan and R. Mihalcea. Using wordnet and lexical operators to improve internet searches. IEEE Internet Computing, 4(1):34--43, 2000.
14. S. E. Robertson. On term selection for query expansion. Journal of Documentation, 46(4):359--364, 1990.
15. J. Rocchio. Relevance Feedback in Information Retrieval, pages 313--323. 1971.
16. R. Sun, C.-H. Ong, and T.-S. Chua. Mining dependency relations for query expansion in passage retrieval. In Proceedings of SIGIR 2006, pages 382--389, 2006.
17. R. Udupa, A. Bhole, and P. Bhattacharyya. "a term is known by the company it keeps": On selecting a good expansion set in pseudo-relevance feedback. In ICTIR '09: Proceedings of the 2nd International Conference on Theory of Information Retrieval, pages 104--115, Berlin, Heidelberg, 2009. Springer-Verlag.
18. Y. Wu, Q. Zhang, Y. Zhou, and X. Huang. Pseudo-relevance feedback based on mrmr criteria. In P.-J. Cheng, M.-Y. Kan, W. Lam, and P. Nakov, editors, Information Retrieval Technology, volume 6458 of Lecture Notes in Computer Science, pages 211--220. Springer Berlin / Heidelberg, 2010.
19. Y. Xu, G. J. Jones, and B. Wang. Query dependent pseudo-relevance feedback based on wikipedia. In SIGIR '09, pages 59--66, 2009.
20. S. Yu, D. Cai, J.-R. Wen, and W.-Y. Ma. Improving pseudo-relevance feedback in web information retrieval using web page segmentation. In Proceedings of WWW 2003, pages 11--18, 2003.

Index Terms

• Information systems

  • Information retrieval

    • Evaluation of retrieval results

      • Relevance assessment