In this work we consider the task of constructing prediction intervals in an inductive batch setting. We present a discriminative learning framework which optimizes the expected error rate under a budget constraint on the interval sizes. Most current methods for constructing prediction intervals offer guarantees for a single new test point. Applying these methods to multiple test points results in a high computational overhead and degraded statistical properties. By focusing on expected errors, our method allows for variability in the per-example conditional error rates. As we demonstrate both analytically and empirically, this flexibility can increase the overall accuracy, or alternatively, reduce the average interval size. While the problem we consider is of a regressive flavor, the loss we use is of a combinatorial nature. This allows us to provide PAC-style, finite-sample guarantees. Computationally, we show that our original objective is NP-hard, and suggest a tractable convex surrogate. We conclude with a series of experimental evaluations.

本文提出了一种区分学习框架，它在区间大小预算约束下，优化预期错误率，以构建归纳批处理中的预测区间。通过专注于预期误差，我们的方法允许条件错误率的变异性，这可以提高整体准确性或者减少平均区间大小。虽然我们考虑的问题是回归型的，但我们使用的损失是组合型的，这使我们能够提供PAC样式的有限样本保证。

预测区间的判别式学习