### 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 language | English (US) |
---|---|

Title of host publication | Proc 6 Annu ACM Conf Comput Learn Theory |

Editors | Anon |

Publisher | Publ by ACM |

Pages | 317-326 |

Number of pages | 10 |

ISBN (Print) | 0897916115 |

State | Published - 1993 |

Externally published | Yes |

Event | Proceedings of the 6th Annual ACM Conference on Computational Learning Theory - Santa Cruz, CA, USA Duration: Jul 26 1993 → Jul 28 1993 |

### Other

Other | Proceedings of the 6th Annual ACM Conference on Computational Learning Theory |
---|---|

City | Santa Cruz, CA, USA |

Period | 7/26/93 → 7/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.