论文标题
关于原型规则的错误和压缩率
On Error and Compression Rates for Prototype Rules
论文作者
论文摘要
我们根据原型学习规则研究了非参数多类分类设置中错误与压缩之间的密切相互作用。我们特别关注最近提出的基于压缩的学习规则，称为OptInet（Kontorovich，Sabato和Urner 2016； Kontorovich，Sabato和Weiss 2017； Hanneke等，2021）。除了其计算优点外，最近已证明该规则在任何承认普遍一致的规则的指标实例空间中都是普遍一致的 - 首先已知享受此属性的学习算法。但是，其误差和压缩率已经打开。在这里，我们得出了这样的速率，如果实例在欧几里得空间中存在于数据分布上的平滑度和尾部条件下。我们首先表明OptInet达到了非平凡的压缩率，同时享受最小的错误率。然后，我们继续研究一种新型的通用压缩方案，以进一步压缩原型规则，该规则在不牺牲准确性的情况下局部适应噪声水平。将其应用于OptInet，我们表明在几何边缘条件下，可以实现压缩率的进一步增益。提出了比较各种方法的性能的实验结果。
We study the close interplay between error and compression in the non-parametric multiclass classification setting in terms of prototype learning rules. We focus in particular on a recently proposed compression-based learning rule termed OptiNet (Kontorovich, Sabato, and Urner 2016; Kontorovich, Sabato, and Weiss 2017; Hanneke et al. 2021). Beyond its computational merits, this rule has been recently shown to be universally consistent in any metric instance space that admits a universally consistent rule--the first learning algorithm known to enjoy this property. However, its error and compression rates have been left open. Here we derive such rates in the case where instances reside in Euclidean space under commonly posed smoothness and tail conditions on the data distribution. We first show that OptiNet achieves non-trivial compression rates while enjoying near minimax-optimal error rates. We then proceed to study a novel general compression scheme for further compressing prototype rules that locally adapts to the noise level without sacrificing accuracy. Applying it to OptiNet, we show that under a geometric margin condition, further gain in the compression rate is achieved. Experimental results comparing the performance of the various methods are presented.
