On Learning Boolean Functions.

Abstract

This paper deals with the learnability of boolean functions. An intuitive appealing notion of dimensionality of boolean functions is developed and used to identify the most general class of boolean function families that are learnable from polynominally many positive examples with one-sided error. It is then argued that although bounded DNF expressions lie outside this class, they must have efficient learning algorithms as they are well suited for expressing many human concepts. A framework that enables efficient learning of bounded DNF functions is then identified. (Author)

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1986
Accession Number
ADA176516

Entities

People

  • B. K. Natarajan

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Complex Variables
  • Functions (Mathematics)
  • Learning
  • Mathematical Analysis
  • Mathematics
  • Mental Processes

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Neural Network Machine Learning.