ML Anthology

Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts

Wolfgang Maass, György Turán
MLJ 1994 pp. 251-269
doi:10.1023/A:1022653511837 /mlj/1994/maass1994mlj-algorithms/

Abstract

The complexity of on-line learning is investigated for the basic classes of geometrical objects over a discrete (“digitized”) domain. In particular, upper and lower bounds are derived for the complexity of learning algorithms for axis-parallel rectangles, rectangles in general position, balls, half-spaces, intersections of half-spaces, and semi-algebraic sets. The learning model considered is the standard model for on-line learning from counterexamples.

PDF MLJ Semantic Scholar

Cite

Text

Maass and Turán. "Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts." Machine Learning, 1994. doi:10.1023/A:1022653511837

Markdown

[Maass and Turán. "Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts." Machine Learning, 1994.](https://mlanthology.org/mlj/1994/maass1994mlj-algorithms/) doi:10.1023/A:1022653511837

BibTeX

@article{maass1994mlj-algorithms,
  title     = {{Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts}},
  author    = {Maass, Wolfgang and Turán, György},
  journal   = {Machine Learning},
  year      = {1994},
  pages     = {251-269},
  doi       = {10.1023/A:1022653511837},
  volume    = {14},
  url       = {https://mlanthology.org/mlj/1994/maass1994mlj-algorithms/}
}