Estimating Learnability in the Sublinear Data Regime
Estimating Learnability in the Sublinear Data Regime
复制标题
DOI：
--
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Weihao Kong;G. Valiant
中科院分区：
文献类型：
--
作者：
Weihao Kong;G. Valiant
我们考虑了估计模型类能够拟合标记数据分布的问题的问题。我们表明，即使给出了一定数量的数据，通常可以准确估计这种“可学习性”，而这些数据太小而无法可靠地学习任何准确的模型。我们的第一个结果适用于从$ d $维分布中绘制数据的设置（或各向同性协方差）（或已知协方差），并且每个数据点的标签是数据点的任意嘈杂函数。在这种情况下，我们表明，使用$ O（\ sqrt {d}）$样本，可以准确估计标签方差的分数，可以通过数据的最佳线性函数来解释。与此均方根样本量相反，找到最佳拟合线性功能的近似值需要按$ d $样本的顺序进行。我们的额定性样本结果和方法还扩展到非各向异性设置，其中数据分布具有（未知的）任意协方差矩阵：我们表明，如果标签$ y $ y $ y $ y $ y $ y $ x $是具有独立噪声的线性函数，$ y = \ langle x，\ beta \ rangle + noise $ with $ \ | \ beta \ | $有限，噪声的差异可以估计为错误$ \ epsilon $ with $ o（d^{1-1） /\ log {1/\ epsilon}}）$如果协方差矩阵的条件号有限，或$ o（d^{1- \ sqrt {\ epsilon}}}）$，如果条件编号没有界限。我们还确定这些样本复杂性是最佳的，对于恒定因素。最后，我们将这些技术扩展到二进制分类的设置，在该设置中，我们在二进制标记数据的自然模型中获得了估计最佳线性分类器的预测误差的问题。我们证明了我们在几个真实和合成数据集上的方法的实际生存能力。
We consider the problem of estimating how well a model class is capable of fitting a distribution of labeled data. We show that it is often possible to accurately estimate this "learnability" even when given an amount of data that is too small to reliably learn any accurate model. Our first result applies to the setting where the data is drawn from a $d$-dimensional distribution with isotropic covariance (or known covariance), and the label of each datapoint is an arbitrary noisy function of the datapoint. In this setting, we show that with $O(\sqrt{d})$ samples, one can accurately estimate the fraction of the variance of the label that can be explained via the best linear function of the data. In contrast to this sublinear sample size, finding an approximation of the best-fit linear function requires on the order of $d$ samples. Our sublinear sample results and approach also extend to the non-isotropic setting, where the data distribution has an (unknown) arbitrary covariance matrix: we show that, if the label $y$ of point $x$ is a linear function with independent noise, $y = \langle x , \beta \rangle + noise$ with $\|\beta \|$ bounded, the variance of the noise can be estimated to error $\epsilon$ with $O(d^{1-1/\log{1/\epsilon}})$ if the covariance matrix has bounded condition number, or $O(d^{1-\sqrt{\epsilon}})$ if there are no bounds on the condition number. We also establish that these sample complexities are optimal, to constant factors. Finally, we extend these techniques to the setting of binary classification, where we obtain analogous sample complexities for the problem of estimating the prediction error of the best linear classifier, in a natural model of binary labeled data. We demonstrate the practical viability of our approaches on several real and synthetic datasets.