In this paper, we study the problem of using statistical query (SQ) to learn highly correlated boolean functions, namely, a class of functions where any pair agree on significantly more than a fraction 1/2 of the inputs. We give a limit on how well one can approximate all the functions without making any query, and then we show that beyond this limit, the number of statistical queries the algorithm has to make increases with the ``extra'' advantage the algorithm gains in learning the functions. Here the advantage is defined to be the probability the algorithm agrees with the target function minus the probability the algorithm doesn't agree. An interesting consequence of our results is that the class of booleanized linear functions over a finite field ( f ( a ( x ) = 1 iff ( a x ) = 1 , where : G F p ? 1 1 is an arbitrary boolean function the maps any elements in G F p to 1 ). This result is useful since the hardness of learning booleanized linear functions over a finite field is related to the security of certain cryptosystems (cite{B01}). In particular, we prove that the class of linear threshold functions over a finite field ( f ( a b ( x ) = 1 iff a x b ) cannot be learned efficiently using statistical query. This contrasts with Blum et al.'s result cite{BFK+96} that linear threshold functions over reals (perceptrons) are learnable using SQ model. Finally, we describe a PAC-learning algorithm that learns a class of linear threshold functions in time that is provably impossible for statistical query algorithms to learn the class. With properly chosen parameters, this class of linear threshold functions can become an example of PAC-learnable, but not SQ-learnable functions that are not parity functions.
展开▼
