ML Anthology

Compressing to VC Dimension Many Points

Manfred K. Warmuth
COLT 2003 pp. 743-744
doi:10.1007/978-3-540-45167-9_60 /colt/2003/warmuth2003colt-compressing/

Abstract

Any set of labeled examples consistent with some hidden orthogonal rectangle can be “compressed” to at most four examples: An upmost, a leftmost, a rightmost and a bottommost positive example. These four examples represent an orthogonal rectangle (the smallest such rectangle that contains them) that is consistent with all examples.

PDF COLT Semantic Scholar

Cite

Text

Warmuth. "Compressing to VC Dimension Many Points." Annual Conference on Computational Learning Theory, 2003. doi:10.1007/978-3-540-45167-9_60

Markdown

[Warmuth. "Compressing to VC Dimension Many Points." Annual Conference on Computational Learning Theory, 2003.](https://mlanthology.org/colt/2003/warmuth2003colt-compressing/) doi:10.1007/978-3-540-45167-9_60

BibTeX

@inproceedings{warmuth2003colt-compressing,
  title     = {{Compressing to VC Dimension Many Points}},
  author    = {Warmuth, Manfred K.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2003},
  pages     = {743-744},
  doi       = {10.1007/978-3-540-45167-9_60},
  url       = {https://mlanthology.org/colt/2003/warmuth2003colt-compressing/}
}