Greedy and Randomized Feature Selection for Web Search Ranking
Authors:
- Feng PanFPFeng Pan
- Tim ConverseTCTim Converse
- David AhnDADavid Ahn
- Franco SalvettiFSFranco Salvetti
- Gianluca DonatoGDGianluca Donato
- 1 August 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3, 436-442
Abstract
Modern search engines have to be fast to satisfy users, so there are hard back-end latency requirements. The set of features useful for search ranking functions, though, continues to grow, making feature computation a latency bottleneck. As a result, not all available features can be used for ranking, and in fact, much of the time only a small percentage of these features can be used. Thus, it is crucial to have a feature selection mechanism that can find a subset of features that both meets latency requirements and achieves high relevance. To this end, we explore different feature selection methods using boosted regression trees, including both greedy approaches (i.e., selecting the features with the highest relative influence as computed by boosted trees, discounting importance by feature similarity) and randomized approaches (i.e., best-only genetic algorithm, a proposed more efficient randomized method with feature-importance-based backward elimination). We evaluate and compare these approaches using two data sets, one from a commercial Wikipedia search engine and the other from a commercial Web search engine. The experimental results show that the greedy approach that selects top features with the highest relative influence performs close to the full-feature model, and the randomized feature selection with feature-importance-based backward elimination outperforms all other randomized and greedy approaches, especially on the Wikipedia data.Keywords
This publication has 11 references indexed in Scilit:
- Learning to efficiently rank2010
- Reducing long queries using query quality predictors2009
- FPGA-based Accelerator Design for RankBoost in Web Search Engines2007
- Feature selection for ranking2007
- AdaRank2007
- Learning to rank using gradient descent2005
- Cumulated gain-based evaluation of IR techniquesACM Transactions on Information Systems, 2002
- Greedy function approximation: A gradient boosting machine.The Annals of Statistics, 2001
- Genetic-based search for error-correcting graph isomorphismIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1997
- Overview of the Okapi projectsJournal of Documentation, 1997