We present a framework for active inference, the selective acquisition of labels for cases at prediction time in lieu of using the estimated labels of a predictive model. The framework generalizes prior work on prediction time label acquisition. We develop techniques within this active inference framework for classifying streams, for example, for classifying web pages where online advertisements are being served. Such stream applications present novel complications; specifically, (i) we don't know at the time of any label acquisition decision what instances we will see, and (ii) instances repeat based on some unknown (and possibly skewed) distribution. To propose a solution, we combine ideas from decision theory, cost-sensitive learning, on-line density estimation, and on-line utility estimation. The resulting model tells which instances to label so that by the end of the budget period, the budget is best spent (in expectation). We test the method on streams from a real application and on partially synthetic streams. The main results show that: (1) active inference on streams can indeed reduce error cost substantially over not doing the on-line estimations, and (2) more sophisticated on-line estimation provides more reduction in error. We also discuss relationships with active learning: What if you also need to learn the model while doing the active inference?
