Second Order Calibration: A Simple Way to Get Approximate Posteriors

Abstract

Many large-scale machine learning problems involve estimating an unknown parameter ${\theta }_i$ for each of many items. For example, a key problem in sponsored search is to estimate the click through rate (CTR) of each of billions of query-ad pairs. Most common methods, though, only give a point estimate of each ${\theta }_i$. A posterior distribution for each ${\theta }_i$ is usually more useful but harder to get. We present a simple post-processing technique that takes point estimates or scores $t_i$ (from any method) and estimates an approximate posterior for each ${\theta }_i$. We build on the idea of calibration, a common post-processing technique that estimates $\mathrm{E}\left({\theta }_i|t_i\right)$. Our method, second order calibration, uses empirical Bayes methods to estimate the distribution of ${\theta }_i|t_i$ and uses the estimated distribution as an approximation to the posterior distribution of ${\theta }_i$. We show that this can yield improved point estimates and useful accuracy estimates. The method scales to large problems - our motivating example is a CTR estimation problem involving tens of billions of query-ad pairs.

References in corpus (2)

• Needles and straw in haystacks: Empirical Bayes estimates of possibly sparse sequences
• Detecting mutations in mixed sample sequencing data using empirical Bayes