论文标题
一种强烈的多项式算法，用于近似福斯特变换及其在半空间学习中的应用
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
论文作者
论文摘要
福斯特变换是一种通过将数据集放置在{\ em radial各向同性位置}同时维护其某些必需属性的方法来正规化数据集的方法。 Forster Transform在跨越计算机科学和功能分析的各种设置中发挥了关键作用。先前的工作给出了{\ em弱}的多项式时间算法，用于计算Forster变换时。我们的主要结果是第一个{\ em强烈多项式时间}算法计算给定数据集的近似福特转换或证明不存在这种转换。通过利用我们强烈的多项式福尔斯特算法，我们获得了第一个强烈多项式时间算法，用于{\ em分布}的pac pac学习。这个学习结果令人惊讶，因为{\ em prom}半空间的PAC学习是{\ em等效}与线性编程的{\ em quarterment}。我们的学习方法扩展到在存在随机分类噪声和更一般而言的Massart噪声的情况下，具有强烈多项式的半空间学习者。
The Forster transform is a method of regularizing a dataset by placing it in {\em radial isotropic position} while maintaining some of its essential properties. Forster transforms have played a key role in a diverse range of settings spanning computer science and functional analysis. Prior work had given {\em weakly} polynomial time algorithms for computing Forster transforms, when they exist. Our main result is the first {\em strongly polynomial time} algorithm to compute an approximate Forster transform of a given dataset or certify that no such transformation exists. By leveraging our strongly polynomial Forster algorithm, we obtain the first strongly polynomial time algorithm for {\em distribution-free} PAC learning of halfspaces. This learning result is surprising because {\em proper} PAC learning of halfspaces is {\em equivalent} to linear programming. Our learning approach extends to give a strongly polynomial halfspace learner in the presence of random classification noise and, more generally, Massart noise.
