We consider the problem of learning in the presence of irrelevant attributes in Valiant's PAC model (1984). In the PAC model, the goal of the learner is to produce an approximately correct hypothesis from random sample data. If the number of relevant attributes in the target function is small, it may be desirable to produce a hypothesis that also depends on only a small number of variables. Haussler (1988) previously considered the problem of learning monomials of a small number of variables. He showed that the greedy set cover approximation algorithm can be used as a polynomial-time Occam algorithm for learning monomials on r of n variables. A outputs a monomial on r(ln q+1) variables, where q is the number of negative examples in the sample. We extend this result by showing that there is a polynomial-time Occam algorithm for learning k-term DNF formulas depending on r of n variables that outputs a DNF formula depending on O(r/sup k/log/sup k/q) variables, where q is the number of negative examples in the sample. We also give a polynomial-time Occam algorithm for learning decision lists (sometimes called 1-decision lists) with k alternations.>

Article Free Access Share on Searching in the presence of linearly bounded errors Authors: Javed A. Aslam Massachusetts Institute of Technology, Cambridge Massachusetts Institute of Technology, CambridgeView Profile , Aditi Dhagat Massachusetts Institute of Technology, Cambridge Massachusetts Institute of Technology, CambridgeView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 486–493https://doi.org/10.1145/103418.103469Published:03 January 1991Publication History 71citation321DownloadsMetricsTotal Citations71Total Downloads321Last 12 Months17Last 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 SiteeReaderPDF