Second Order Calibration: A Simple Way to Get Approximate Posteriors

Many large-scale machine learning problems involve estimating an unknown parameter θ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 θi. A posterior distribution for each θi is usually more useful but harder to get. We present a simple post-processing technique that takes point estimates or scores ti (from any method) and estimates an approximate posterior for each θi. We build on the idea of calibration, a common post-processing technique that estimates Eleft(θi!!bigm|!! tiright). Our method, second order calibration, uses empirical Bayes methods to estimate the distribution of θi!!bigm|!! ti and uses the estimated distribution as an approximation to the posterior distribution of θ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.