详细内容或原文请订阅后点击阅览
关于计算效率高的多类校准
考虑一个多类标记问题，其中标签可以取 [k] 中的值，而预测器可以预测标签上的分布。在这项工作中，我们研究了以下基本问题：是否存在多类校准的概念，可以强有力地保证有意义的预测，并且可以在时间和样本复杂度为 k 的多项式内实现？先前的校准概念在计算效率和表达能力之间表现出权衡：它们要么受制于样本复杂度为 k 的指数，要么需要解决计算上难以解决的问题，要么给出……
来源:Apple机器学习研究考虑一个多类标记问题，其中标签可以取 [k] 中的值，并且预测器预测标签上的分布。在这项工作中，我们研究了以下基本问题：是否存在多类校准的概念，可以对有意义的预测提供强有力的保证，并且可以在时间和样本复杂度为 k 的多项式内实现？先前的校准概念在计算效率和表达能力之间表现出权衡：它们要么受制于样本复杂度为 k 的指数，要么需要解决计算上难以解决的问题，要么提供相当弱的保证。
我们的主要贡献是一种校准概念，它可以实现所有这些要求：我们为多类预测制定了一个稳健的投影平滑校准概念，并给出了新的重新校准算法，用于在此定义下以 k 的复杂度多项式有效地校准预测器。投影平滑校准为所有想要使用预测器进行二元分类问题的下游决策者提供了强有力的保证，其形式为：标签是否属于子集 Tâ[k]：例如，这是动物的图像吗？它确保通过将分配给 T 中标签的概率相加而预测的概率接近该任务的某个完美校准的二元预测器。我们还表明，我们定义的自然加强在计算上很难实现：它们会遇到信息理论障碍或计算难处理性。我们的上限和下限都存在紧密的联系，我们证明了多类校准与（标准）二元预测设置中经过充分研究的不可知学习问题之间存在这种联系。