The chow parameters problem
The chow parameters problem
复制标题
周参数问题
DOI：
10.1145/1374376.1374450
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
R. Servedio
中科院分区：
文献类型：
--
作者：
R. O'Donnell;R. Servedio
在第二年的焦点（1961年）中，C。K。Chow证明，每个布尔阈值函数都由其学位-0和1级傅立叶系数确定。 - 即，鉴于其Chow参数，有效地构建了阈值函数的表示 - 此后一直保持着很大的打开。在电路复杂性，游戏理论和投票系统的设计和学习理论中的研究。 f在n位和任何常数ε> 0上，该算法在时间O（N2 log2 n）中运行，并且概率很高，输出阈值函数f'的表示形式为ε-close我们证明了对布尔阈值函数的独立兴趣的几个新结果。在Ben-David等人的“限制焦点”（RFA）模型中，学习半空间的均匀分布算法[3]。 O（N2） - 统一分布下半空间的不可知论算法与Guruswami和Raghavendra的最新结果进行了对比后来的结果，我们获得了最快的已知算法，用于学习半空间在均匀分布pAC学习模型中的恒定精度。 〜O（n2），它在以前的界限上实质上有所改善，并且几乎与任何成功学习算法都必须使用的训练数据相匹配。
In the 2nd Annual FOCS (1961), C. K. Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow Parameters. Providing an algorithmic version of Chow's theorem --- i.e., efficiently constructing a representation of a threshold function given its Chow Parameters --- has remained open ever since. This problem has received significant study in the fields of circuit complexity, game theory and the design of voting systems, and learning theory. In this paper we effectively solve the problem, giving a randomized PTAS with the following behavior: Theorem: Given the Chow Parameters of a Boolean threshold function f over n bits and any constant ε > 0, the algorithm runs in time O(n2 log2 n) and with high probability outputs a representation of a threshold function f' which is ε-close to f. Along the way we prove several new results of independent interest about Boolean threshold functions. In addition to various structural results, these include the following new algorithmic results in learning theory (where threshold functions are usually called "halfspaces"): An ~O(n2)-time uniform distribution algorithm for learning halfspaces to constant accuracy in the "Restricted Focus of Attention" (RFA) model of Ben-David et al. [3]. This answers the main open question of [6]. An O(n2)-time agnostic-type learning algorithm for halfspaces under the uniform distribution. This contrasts with recent results of Guruswami and Raghavendra [21] who show that the learning problem we solve is NP-hard under general distributions. As a special case of the latter result we obtain the fastest known algorithm for learning halfspaces to constant accuracy in the uniform distribution PAC learning model. For constant ε our algorithm runs in time ~O(n2), which substantially improves on previous bounds and nearly matches the Ω(n2) bits of training data that any successful learning algorithm must use.