On learning visual concepts and DNF formulae

Eyal Kushilevitz, Dan Roth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of learning visual concepts in the mistake-bound and the PAC models. We develop an approach that is shown to be useful also for the problem of learning DNF formulae in these models. As a result, we extend the class of learnable DNF (and CNF) formulae. The classes shown to be learnable are not limited in the number of terms or in the number of variables per term, and they contain the classes of k-DNF and k-term-DNF (and the corresponding classes of CNF) as special cases. We discuss some of the limitations of this approach and a number of applications.

Original languageEnglish (US)
Title of host publicationProc 6 Annu ACM Conf Comput Learn Theory
Editors Anon
PublisherPubl by ACM
Pages317-326
Number of pages10
ISBN (Print)0897916115
StatePublished - 1993
Externally publishedYes
EventProceedings of the 6th Annual ACM Conference on Computational Learning Theory - Santa Cruz, CA, USA
Duration: Jul 26 1993Jul 28 1993

Other

OtherProceedings of the 6th Annual ACM Conference on Computational Learning Theory
CitySanta Cruz, CA, USA
Period7/26/937/28/93

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Kushilevitz, E., & Roth, D. (1993). On learning visual concepts and DNF formulae. In Anon (Ed.), Proc 6 Annu ACM Conf Comput Learn Theory (pp. 317-326). Publ by ACM.