Learning Boolean functions in AC(0) on attribute and classification noise-Estimating an upper bound on attribute and classification noise
We study a procedure for estimating an upper bound of an unknown noise factor in the frequency domain. A learning algorithm using a Fourier transformation method was originally given by Linial, Mansour and Nisan. While Linial, Mansour and Nisan assumed that the learning algorithm estimates Fourier coefficients from noiseless data, Bshouty, Jackson, and Tamon, and also Ohtsuki and Tomita extended the algorithm to ones that are robust for noisy data. The noise process that we consider is as follows: for an example  , where x is an element of {0, 1}(n), f(x) is an element of {-1, 1}, each bit of x and f (x) gets flipped independently with probability eta during a learning process. The previous learning algorithms for noisy data all assume that the noise factor eta or an upper bound of eta is known in advance. The learning algorithm proposed in this paper works without this assumption. We estimate an upper bound of the noise factor by evaluating a noisy power spectrum in the frequency domain and by using a sampling trick. Combining this procedure with Ohtsuki and Tomita's algorithm, we obtain a quasi-polynomial-time learning algorithm that can cope with noise without knowing any information about the noise in advance. (C) 2011 Elsevier B.V. All rights reserved.
learning boolean functions ac(0) classification noise attribute noise