The complexity of learning formulas and decision trees that have restricted reads
Thomas R. Hancock · 1992
Many learning problems can be phrased in terms of finding a close approximation to some unknown target formula f, based on observing f's value on a sample of points either drawn at random according to some underlying distribution, or perhaps selected by a learner for algorithmic reasons. In this research our goal is to prove theorems about what classes of formulas permit such learning in polynomial time (using the definitions of either Valiant's PAC model or Angluin's exact identification model). In particular we take powerful classes of formulas whose learnability is unknown or provably intractable, and then consider restricted cases where the number of different times a single variable may appear in the formula is limited to a small constant. We prove positive learnability results in several such cases, given either added assumptions on the underlying distribution of random points or the ability of the learner to select some of the sample points. We provide polynomial time learning algorithms for decision trees and monotone disjunctive normal form (DNF) formulas when variables appear at most some arbitrary constant number of times, given that the sample points are chosen uniformly. Over arbitrary distributions, we show algorithms that chose their own sample points, besides using random examples, to closely approximate the same class of decision trees and the class of DNF formulas where variables appear at most twice. For arbitrary formulas, we give a number of algorithms for the read-once case (where variables appear only once) over different bases (the functions computed at formula's nodes). Besides identification algorithms for large classes of boolean read-once formulas, these results include new interpolation algorithms for classes of rational functions, and a membership query algorithm for a new class of neural networks.