文章基本信息

标题：On Learning Correlated Boolean Functions Using Statistical Query
本地全文：下载
作者：Ke Yang
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：blind computation , Linear Threshold Functions , statistical query