Active Property Testing
Active Property Testing
复制标题
活性性能测试
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Liu Yang
中科院分区：
文献类型：
--
作者：
Maria;Eric Blais;Avrim Blum;Liu Yang
布尔函数属性测试的一个动机是测试可以在学习之前提供快速的预处理步骤。然而，在大多数机器学习应用中，不可能请求由算法构造的任意示例的标签。相反，应用机器学习中的主要查询范例，称为主动学习，是一种算法可以查询标签的范例，但仅在从一些底层分布D中提取的给定（多项式大小）未标记样本中的点上。在这项工作中，我们把这个经过充分研究的模型带到测试领域。我们开发的一般结果，这种积极的测试模型，以及有效的测试算法的几个重要属性的学习，证明测试仍然可以产生实质性的好处，在这种限制设置。例如，我们证明了在我们的设置中，测试d个区间的并集可以用O（1）标签请求来完成，而众所周知，学习需要Ω（d）标记的示例（被动测试需要Ω（d）），其中算法必须为从D中提取的每个示例付费）。事实上，我们的结果测试工会的时间间隔也产生了改进以前的工作，在经典的查询模型（在域中的任何点都可以查询）和被动测试模型。对于在高斯分布上测试Rn中的线性分离器的问题，我们证明了主动和被动测试都可以用O（n）次查询来完成，大大低于学习所需的Ω（n），并且具有接近匹配的下限。我们还在这个模型中提出了一个通用的组合结果，用于从其他模型中构建可测试的属性，然后我们使用它来为半监督学习中使用的一些假设提供测试人员。除了上述结果，我们还开发了一个一般的概念，一个给定的属性相对于一个给定的分布的测试维度，我们表现出表征（常数因子）的内在数量的标签要求需要测试该属性。我们开发这样的概念，主动和被动的测试模型。然后，我们使用这些维度来证明一些下界，包括线性分离器和独裁者函数类。
One motivation for property testing of boolean functions is the idea that testing can provide a fast preprocessing step before learning. However, in most machine learning applications, it is not possible to request for labels of arbitrary examples constructed by an algorithm. Instead, the dominant query paradigm in applied machine learning, called active learning, is one where the algorithm may query for labels, but only on points in a given (polynomial-sized) unlabeled sample, drawn from some underlying distribution D. In this work, we bring this well-studied model to the domain of testing. We develop both general results for this active testing model as well as efficient testing algorithms for several important properties for learning, demonstrating that testing can still yield substantial benefits in this restricted setting. For example, we show that testing unions of d intervals can be done with O(1) label requests in our setting, whereas it is known to √ require Ω(d) labeled examples for learning (and Ω(√d) for passive testing [22] where the algorithm must pay for every example drawn from D). In fact, our results for testing unions of intervals also yield improvements on prior work in both the classic query model (where any point in the domain can be queried) and the passive testing model as well. For the problem of testing linear separators in Rn over the Gaussian distribution, we show that both active and passive testing can be done with O(√n) queries, substantially less than the Ω(n) needed for learning, with near-matching lower bounds. We also present a general combination result in this model for building testable properties out of others, which we then use to provide testers for a number of assumptions used in semi-supervised learning. In addition to the above results, we also develop a general notion of the testing dimension of a given property with respect to a given distribution, that we show characterizes (up to constant factors) the intrinsic number of label requests needed to test that property. We develop such notions for both the active and passive testing models. We then use these dimensions to prove a number of lower bounds, including for linear separators and the class of dictator functions.