Deranomized Learning of Boolean Functions

Abstract

We define a new model of learning called the Always Approximately Correct or AAC model. In this model the learner does not have random bits at its disposal, and instead learns by making the usual membership queries from a deterministic “training set.” This model is an extension of Angluin's Query model of exact learning with membership queries alone. We discuss crucial issues and questions that arise when this model is used. One such question is whether a uniform training set is available for learning any concept in the concept class. This issue seems not to have been studied in the context of Angluin's Query model. Another question is whether the training set can be found quickly if partial information about the function is given to the learner (in addition to the answers to membership queries); for example information about a subclass in which the concept belongs. We formalize the latter scenario by introducing the notion of “subclass queries.” Using this new model of learning, we prove three learnability results for classes of Boolean functions that are approximable (with respect to various norms) by linear combinations of a set of few Parity functions. We compare and contrast these results with several existing results for similar classes in the PAC model of learning with and without membership queries — these classes have not been previously emphasized under Angluin's Query model for exact learning. Moreover, we point out the significance — in various contexts — of the classes of Boolean functions being learnt, for example in the context of probabilistic communication complexity.