Using the cross-entropy method to re-rank search results

We present a novel unsupervised approach to re-ranking an initially retrieved list. The approach is based on the Cross Entropy method applied to permutations of the list, and relies on performance prediction. Using pseudo predictors we establish a lower bound on the prediction quality that is required so as to have our approach significantly outperform the original retrieval. Our experiments serve as a proof of concept demonstrating the considerable potential of the proposed approach. A case in point, only a tiny fraction of the huge space of permutations needs to be explored to attain significant improvements over the original retrieval.