Decision support systems based on prediction sets have proven to be effective
at helping human experts solve classification tasks. Rather than providing
single-label predictions, these systems provide sets of label predictions
constructed using conformal prediction, namely prediction sets, and ask human
experts to predict label values from these sets. In this paper, we first show
that the prediction sets constructed using conformal prediction are, in
general, suboptimal in terms of average accuracy. Then, we show that the
problem of finding the optimal prediction sets under which the human experts
achieve the highest average accuracy is NP-hard. More strongly, unless P = NP,
we show that the problem is hard to approximate to any factor less than the
size of the label set. However, we introduce a simple and efficient greedy
algorithm that, for a large class of expert models and non-conformity scores,
is guaranteed to find prediction sets that provably offer equal or greater
performance than those constructed using conformal prediction. Further, using a
simulation study with both synthetic and real expert predictions, we
demonstrate that, in practice, our greedy algorithm finds near-optimal
prediction sets offering greater performance than conformal prediction.

采用贪婪算法，该论文发现了一种可比或更好性能的预测集构造方法，该方法能帮助基于预测集的决策支持系统有效解决分类任务。