SafePredict：使用拒绝机制保证正确率的机器学习元算法

选自arXiv

机器之心编译

参与：路雪、刘晓坤

SafePredict 是一种新型元算法，可以使用拒绝机制保证正确率，其错误界限不依赖于任何关于数据分布或基础预测器的假设。该算法与顶尖的基于置信度的拒绝机制相比更有优势，可以更鲁棒地保证正确率，并减少拒绝的数量。

论文：SafePredict: A Meta-Algorithm for Machine Learning That Uses Refusals to Guarantee Correctness

论文链接：https://arxiv.org/abs/1708.06425

摘要：SafePredict 是一种新型元算法，它可以和任意基础预测算法一起处理在线数据，通过拒绝来保证任意选择的正确率 1−ϵ。允许拒绝表示元算法有时可拒绝基础算法生成的预测，以使非拒绝预测的错误率不超过 ϵ。SafePredict 的错误界限不依赖于任何关于数据分布或基础预测器的假设。如果基础预测器未超过目标错误率ϵ，则 SafePredict 只能拒绝有限次。如果基础预测器的错误率随着时间发生改变，则 SafePredict 利用重心转移的启发式算法在无需了解变化时间的情况下适应这些变化，同时保证准确率。实证研究表明：（1）SafePredict 与顶尖的基于置信度的拒绝机制相比更有优势，后者无法提供鲁棒的错误率保证；（2）SafePredict 和此类拒绝机制的组合可以在多种情况下进一步减少拒绝的数量。我们的软件（目前是 Python 程序）在补充材料中。

表 1：符号表示

图 1：M 代表元算法，其预测等同于基础预测器 P 的推荐，或者元算法为了保证目标正确率（target rate）ε 拒绝对数据点 t 进行预测。

图 2：基于合成数据的效率实验：SafePredict 的效率 (T∗/T) 随着α增加的变化趋势（上方图）。如果基础预测器的错误率是恒定的，且高于目标错误率，则 SafePredict 几乎一直在拒绝。这种情况下预测的数量随着α的增加而增加（下方图）。另一方面，当基础预测器的错误率在目标错误率上下波动时，SafePredict 的效率随着α的增加而上升，达到几乎与 oracle（当且仅当ε_t ≤ ε时，才会进行预测）等同的效率。在任何情况下，都确保渐近有效性（asymptotic validity）。

图 3：合成数据，效率进化：注意α = 0 对应初始 SafePredict，不具备适应性。对于α > 0 的情况，SafePredict 可以跟踪变异点，提升效率。α越大表示跟踪效果越好。随着变异点数量的增加，SafePredict 对基础预测器的性能跟踪效果越差，造成效率下降。图中所有预测器都是有效的。

图4. MNIST数据集：基础预测器的效率是1.0，但多种拒绝元算法的效率低于1.0。有效性作为目标错误率的一部分进行评估。因此，基础预测器的错误率很糟糕（超过ε）。尽管错误率在变异点位于t = 5000时增加，所有的SafePredict变体快速达到正常的错误率1。基于置信度的竞争无法确保渐近有效性。两种形式的适应性帮助减少拒绝的数量：重心转移（特别是α值很大的时候）和遗忘适应性（amnesic adaptivity）。把二者结合起来使得在保留有效性的同时实现最高的效率。

本文为机器之心编译，转载请联系本公众号获得授权。

✄------------------------------------------------