ML Anthology

Epsilon-Approximations of K-Label Spaces

Susumu Hasegawa, Hiroshi Imai, Masaki Ishiguro
ALT 1993 pp. 288-299
doi:10.1007/3-540-57370-4_55 /alt/1993/hasegawa1993alt-epsilonapproximations/

Abstract

In learning a geometric concept from examples, examples are mostly classified into two, positive examples and negative examples which are contained and not contained, respectively, in the concept. However, there exist cases where examples are classified into k classes. For example, clustering a concept space by the Voronoi diagram generated by k points is a very common tool used in image processing and many other areas. We call such a space a k -label space. The case of positive and negative examples corresponds to the 2-label space. In this paper, we first extend the ε -approximation for the 2-label space originally considered by Vapnik and Chervonenkis [10] (see also [1, 5]) to that for the k -label space. The generalized ε -approximation is then applied to the randomized algorithm for the assignment problem by Tokuyama and Nakano

PDF ALT Semantic Scholar

Cite

Text

Hasegawa et al. "Epsilon-Approximations of K-Label Spaces." International Conference on Algorithmic Learning Theory, 1993. doi:10.1007/3-540-57370-4_55

Markdown

[Hasegawa et al. "Epsilon-Approximations of K-Label Spaces." International Conference on Algorithmic Learning Theory, 1993.](https://mlanthology.org/alt/1993/hasegawa1993alt-epsilonapproximations/) doi:10.1007/3-540-57370-4_55

BibTeX

@inproceedings{hasegawa1993alt-epsilonapproximations,
  title     = {{Epsilon-Approximations of K-Label Spaces}},
  author    = {Hasegawa, Susumu and Imai, Hiroshi and Ishiguro, Masaki},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {1993},
  pages     = {288-299},
  doi       = {10.1007/3-540-57370-4_55},
  url       = {https://mlanthology.org/alt/1993/hasegawa1993alt-epsilonapproximations/}
}