A Necessary Condition for Learning from Positive Examples

Schweitzer, Haim

doi:10.1007/BF00115896

A Necessary Condition for Learning from Positive Examples

Haim Schweitzer

MLJ 1990 pp. 101-113

doi:10.1007/BF00115896 /mlj/1990/schweitzer1990mlj-necessary/

Abstract

We present a simple combinatorial criterion for determining concept classes that cannot be learned in the sense of Valiant from a polynomial number of positive-only examples. The criterion is applied to several types of Boolean formulae in conjunctive and disjunctive normal form, to the majority function, to graphs with large connected components, and to a neural network with a single threshold unit. All are shown to be nonlearnable from positive-only examples.

PDF MLJ Semantic Scholar

Cite

Text

Schweitzer. "A Necessary Condition for Learning from Positive Examples." Machine Learning, 1990. doi:10.1007/BF00115896

Markdown

[Schweitzer. "A Necessary Condition for Learning from Positive Examples." Machine Learning, 1990.](https://mlanthology.org/mlj/1990/schweitzer1990mlj-necessary/) doi:10.1007/BF00115896

BibTeX

@article{schweitzer1990mlj-necessary,
  title     = {{A Necessary Condition for Learning from Positive Examples}},
  author    = {Schweitzer, Haim},
  journal   = {Machine Learning},
  year      = {1990},
  pages     = {101-113},
  doi       = {10.1007/BF00115896},
  volume    = {5},
  url       = {https://mlanthology.org/mlj/1990/schweitzer1990mlj-necessary/}
}