Learning with Maximum-Entropy Distributions

We are interested in distributions which are derived as a maximumentropy distribution given a set of constraints. More specifically, we are interested in the case where the constraints are the expectation of individual and pairs of attributes. For such a given maximum entropy distribution we develop an efficient learning algorithm for read-once DNF. We also show how to extend our results to monotone read-k DNF, following the techniques of [HM91] 1 Introduction The PAC learning model [Val84] is the most basic model in computational learning theory. Its introduction brought forward a simple set of assumptions and raised many challenging problems. Initially, the main goal was a computational one, to develop new algorithms within this framework and show the learnability of different concept classes. The PAC model has been very successful in the study of the tradeoff between sample size versus accuracy and confidence, but less successful in the algorithmic study. Only few algorithmic techn..