Oct, 2014

一种对半空间进行不可知学习的 PTAS 算法

TL;DR本文提出了一个以多项式回归和定位技术相结合的算法, 用于在 d - 球上均匀分布的情况下,实现对零时最佳半空间分类器的确定性多项式近似方案(PTAS),误差保证为 opt 的 (1+μ)+ε 倍, 并提供了比以前使用定位技术的算法更加优越的针对全局的误差近似解决方案。