ML Anthology

Learning the Unlearnable

Dan Nabutovsky, Eytan Domany
NeCo 1991 pp. 604-616
doi:10.1162/NECO.1991.3.4.604 /neco/1991/nabutovsky1991neco-learning/

Abstract

We present a local perceptron-learning rule that either converges to a solution, or establishes linear nonseparability. We prove that when no solution exists, the algorithm detects this in a finite time (number of learning steps). This time is polynomial in typical cases and exponential in the worst case, when the set of patterns is nonstrictly linearly separable. The algorithm is local and has no arbitrary parameters.

NeCo Semantic Scholar

Cite

Text

Nabutovsky and Domany. "Learning the Unlearnable." Neural Computation, 1991. doi:10.1162/NECO.1991.3.4.604

Markdown

[Nabutovsky and Domany. "Learning the Unlearnable." Neural Computation, 1991.](https://mlanthology.org/neco/1991/nabutovsky1991neco-learning/) doi:10.1162/NECO.1991.3.4.604

BibTeX

@article{nabutovsky1991neco-learning,
  title     = {{Learning the Unlearnable}},
  author    = {Nabutovsky, Dan and Domany, Eytan},
  journal   = {Neural Computation},
  year      = {1991},
  pages     = {604-616},
  doi       = {10.1162/NECO.1991.3.4.604},
  volume    = {3},
  url       = {https://mlanthology.org/neco/1991/nabutovsky1991neco-learning/}
}