Stable and Semi-stable Sampling Approaches for Continuously Used Samples
This addresses a practical problem for search engine developers needing efficient and reliable continuous evaluation, though it appears incremental as it builds on existing sampling methods.
The paper tackles the trade-off between query sample representativeness, labeling cost, and overfitting in continuously measured information retrieval systems, proposing Stable and Semi-stable sampling variants that outperform existing approaches for settings like monitoring search engines or comparing rankers.
Information retrieval systems are usually measured by labeling the relevance of results corresponding to a sample of user queries. In practical search engines, such measurement needs to be performed continuously, such as daily or weekly. This creates a trade-off between (a) representativeness of query sample to current query traffic of the product; (b) labeling cost: if we keep the same query sample, results would be similar allowing us to reuse their labels; and (c) overfitting caused by continuous usage of same query sample. In this paper we explicitly formulate this tradeoff, propose two new variants -- Stable and Semi-stable -- to simple and weighted random sampling and show that they outperform existing approaches for the continuous usage settings, including monitoring/debugging search engine or comparing ranker candidates.