We consider three natural models of random logarithmic depth decision trees over Boolean variables. We give an efficient algorithm that for each of these models learns all but an inverse polynomial fraction of such trees using only uniformly distributed random examples from {0,1} n . The learning algorithm constructs a decision tree as its hypothesis.

We give an algorithm for learning a more expressive circuit class than the class AC/sup 0/ considered by Linial et al. (1993) and Kharitonov (1993). The new algorithm learns constant-depth AND/OR/NOT circuits augmented with (a limited number of) majority gates. Our main positive result for these circuits is stated informally.

We give an algorithm to learn constant-depth polynomial-size circuits augmented with majority gates under the uniform distribution using random examples only. For circuits which contain a polylogarithmic number of majority gates the algorithm runs in quasipolynomial time. This is the first algorithm for learning a more expressive circuit class than the class AC0 of constant-depth polynomial-size circuits, a class which was shown to be learnable in quasipolynomial time by Linial, Mansour and Nisan in 1989. Our approach combines an extension of some of the Fourier analysis from Linial et al. with hypothesis boosting. We also show that under a standard cryptographic assumption our algorithm is essentially optimal with respect to both running time and expressiveness (number of majority gates) of the circuits being learned.

We study the problem of PAC-learning Boolean functions with random attribute noise under the uniform distribution.First, we define a noisy distance measure for function classes and show that if this measure is small for a class C and an attribute noise distribution D then C is not learnable with respect to the uniform distribution in the presence of noise generated according to D .The noisy distance measure is then characterized in terms of Fourier properties of the function class.We use this characterization to show that the class of all parity functions is not learnable for any but very concentrated noise distributions D. On the other hand, we show that if C is learnable with respect to uniform using a standard Fourier-based Iearning technique, then C is learnable with time and sample complexity also determined by the noisy distance.In fact, we show that this style algorithm is the best possible for learning in the presence of attribute noise.

An efficient algorithm exists for learning disjunctive normal form (DNF) expressions in the uniformdistribution PAC learning model with membership queries [J97], but in practice the algorithm can only be applied to small problems. We present several modifications to the algorithm that substantially improve its asymptotic efficiency. First, we show how to significantly improve the time and sample complexity of a key subprogram, resulting in similar improvements in the bounds on the overall DNF algorithm. We also apply known methods to convert the resulting algorithm to an attribute efficient algorithm. Furthermore, we develop techniques for lower bounding the sample size required for PAC learning with membership queries under a fixed distribution and apply this technique to the uniform-distribution DNF learning problem. Finally, we present a learning algorithm for DNF that is attribute efficient in its use of random bits. 1 INTRODUCTION Jackson [J97] gave the first polynomial-time PAC ...

We generalize the notion of probably approximately correct (PAC) learning from an example oracle to a notion of efficient learning on a quantum computer using a quantum example oracle. This quantum example oracle is a natural extension of the traditional PAC example oracle, and it immediately follows that all PAC-learnable function classes are learnable in the quantum model. Furthermore, we obtain positive quantum learning results for classes that are not known to be PAC learnable. Specifically, we show that disjunctive normal form (DNF) is efficiently learnable with respect to the uniform distribution by a quantum algorithm using a quantum example oracle. While it was already known that DNF is uniform-learnable using a membership oracle, we prove that a quantum example oracle with respect to uniform is less powerful than a membership oracle.

In the k-Restricted-Focus-of-Attention (k-RFA) model, only k of the n attributes of each example are revealed to the learner, although the set of visible attributes in each example is determined by the learner.While the k-RFA model is a natural extension of the PAC model, there are also significant differences.For example, it was previously known that learnability in this model is not characterized by the VC dimension and that many PAC learning algorithms are not applicable in the k-RFA setting.In this paper we further explore the relationship between the PAC and k-RFA models, with several interesting results.First, we develop a characterization of k-RFA learnability upon which we build a general tool for proving hardness results.We then apply this and other new techniques for studying RFA learning to two particularly expressive function classes, k-decision-lists (k-DL) and k-TOP, the class of thresholds of parity functions in which each parity function takes at most k inputs.Among other results, we prove a hardness result for k-RFA learnability of k-DL, k ~n -2.In sharp contrast, an (n -1)-RFA algorithm for learning (n -l)decision-lists is presented.Similarly, we prove that 1-DL is learnable if and only if at least half of the inputs are visible in each instance.In addition, we show that there is a uniform-distribution lc-RFA learning algorithm for the class of k-decision-lists

We generalize the notion of PAC learning from an example oracle to a notion of efficient learning on

We present a membership-query algorithm for efficiently learning DNF with respect to the uniform distribution. In fact, the algorithm properly learns the more general class of functions that are computable as a majority of polynomially-many parity functions. We also describe extensions of this algorithm for learning DNF over certain nonuniform distributions and from noisy examples as well as for learning a class of geometric concepts that generalizes DNF. The algorithm utilizes one of Freund's boosting techniques and relies on the fact that boosting does not require a completely distribution-independent weak learner. The boosted weak learner is a nonuniform extension of a Fourier-based algorithm due to Kushilevitz and Mansour (1991).>

We present new results, both positive and negative, on the well-studied problem of learning disjunctive normal form (DNF) expressions.We first prove that an algorithm due to Kushilevitz and Mansour ysis of a finite class of boolean functions 011 the hypercube.1

Article On learning embedded symmetric concepts Share on Authors: Avrim Blum View Profile , Prasad Chalasani View Profile , Jeffrey Jackson View Profile Authors Info & Claims COLT '93: Proceedings of the sixth annual conference on Computational learning theoryAugust 1993 Pages 337–346https://doi.org/10.1145/168304.168367Online:01 August 1993Publication History 15citation146DownloadsMetricsTotal Citations15Total Downloads146Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Goldman and Kearns [GK91] recently introduced a notion of the teaching dimension of a concept class. The teaching dimension is intended to capture the combinatorial difficulty of teaching a concept class. We present a computational analog which allows us to make statements about bounded-complexity teachers and learners, and we extend the model by incorporating trusted information. Under this extended model, we modify algorithms for learning several expressive classes in the exact identification model of Angluin [Ang88]. We study the relationships between variants of these models, and also touch on a relationship with distribution-free learning.

We describe our experience with the object-oriented design methodology OMT [19] applied to a project in an undergraduate software engineering course at Carnegie Mellon University.The project involved 30 students previously unfamiliar with objectoriented modeling.They designed and implemented a system of 125 classes (27,000 lines of C++ and C code) in the relatively short time of 15 weeks.We describe the overall structure of the project and the system model, the usefulness of OMT and its impact on communication, and discuss some of the problems encountered during the development of the system.

A method for selecting graphical objects with a mouse by circling them is described. Circling motions are detected automatically; no button presses are required. Trials conducted on a Sun 3 workstation indicate that, for the object size and layout chosen, even users experienced with mouse selection via button presses and unfamiliar with circling are able to select pairs of objects in approximately the same amount of time with either method. The number of target misses between circling and clicking also compare well for both single and paired object cases. Furthermore, many users showed a measurable preference for the circling method when given a choice.