Our approach proceeds in two steps. First, treating the base expansion method as a 'black box', we gather information about how the algorithm's output — a set of expansion terms — changes with perturbations of the initial query and top-ranked documents. This step also results in a set of plausible expansion model candidates. We then introduce a novel risk framework based on convex optimization that prunes and combines these candidates to produce a much more reliable version of the original baseline expansion algorithm. Highlights of our results include: • A new algorithmic framework for estimating more precise query and document models, based on treating queries and document sets as random variables instead of single observations. • The first significant application and analysis of convex optimization methods to query expansion problems in information retrieval. • A new family of statistical similarity measures we call perturbation kernels that are efficient to compute and give context-sensitive word clustering. • The introduction of risk-reward analysis to information retrieval, including tradeoff curves, analysis, and risk measures. • A new general form of query difficulty measure that reflects clustering in the collection as well as the relation between a query and the collection.
