Testing Halfspaces
Testing Halfspaces
复制标题
测试半空间
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Servedio
中科院分区：
文献类型：
--
作者：
Kevin Matulef;R. O'Donnell;R. Rubinfeld;R. Servedio
本文讨论布尔值函数f是否为半空间的判别问题，即f（x）= sgn（w · x - θ）型函数。我们考虑连续域Rn上的半空间（赋以标准多元高斯分布）以及布尔立方体{−1，1}n上的半空间（赋以均匀分布）。在这两种情况下，我们给出了一个算法，区分半空间的功能是e-远的任何半空间，只使用多（1/e）查询，独立的维数n。
关于半空间的两个简单的结构结果是我们对高斯分布的方法的核心：第一个给出了半空间f的期望值与f的1度Hermite系数的平方和之间的精确关系，第二个表明任何近似满足这种关系的函数都接近半空间。我们证明了平衡半空间的布尔立方体{−1，1}n（用傅立叶系数代替Hermite系数）的类似结果，其中所有的1次傅立叶系数都是小的。处理{-1，1}n上的一般半空间会造成相当大的额外复杂性，并需要其他成分。这些包括“交叉一致性”的版本，上述结果对半空间具有相同的权重，但不同的阈值;新的结构性结果相关的最大程度1傅立叶系数和最大的权重不平衡的半空间;和算法技术，从最近的工作测试juntas [FKR+02]。
This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x) = sgn(w · x - θ). We consider halfspaces over the continuous domain Rn (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {−1, 1}n (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are e-far from any halfspace using only poly(1/e) queries, independent of the dimension n.
Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: the first gives an exact relationship between the expected value of a halfspace f and the sum of the squares of f's degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube {−1, 1}n (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over {−1, 1}n poses significant additional complications and requires other ingredients. These include "cross-consistency" versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas [FKR+02].