Learning symmetric k-juntas in time n^o(k)

2005/04/12 by Mihail N. Kolountzakis, Evangelos Markakis, Kolountzakis, Mihail N. +3
Computer Science · Mathematics · #Algorithms and Data Compression #Imbalanced Data Classification Techniques #Machine Learning and Algorithms #math.CO

paper · pdf · doi:10.48550/arxiv.math/0504246

arxiv created 2005/04/12 · arxiv updated 2009/12/01

Abstract

We give an algorithm for learning symmetric k-juntas (boolean functions of n boolean variables which depend only on an unknown set of k of these variables) in the PAC model under the uniform distribution, which runs in time n^{O(k/log k)}. Our bound is obtained by proving the following result: Every symmetric boolean function on k variables, except for the parity and the constant functions, has a non-zero Fourier coefficient of order at least 1 and at most O(k/log k). This improves the previously best known bound of (3/31)k, and provides the first n^o(k) time algorithm for learning symmetric juntas.

Citations

• Selection of relevant features and examples in machine learning

Related

• Multiple Random Oracles Are Better Than One
• New Statistical and Computational Results for Learning Junta Distributions
• Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression
• Learning and Testing Junta Distributions with Subcube Conditioning
• Learning Functions of Halfspaces