Learning Algorithm for Enclosing Points in Bregmanian Spheres
Abstract
We discuss the problem of finding a generalized sphere that encloses points originating from a single source. The points contained in such a sphere are within a maximal divergence from a center point. The divergences we study are known as the Bregman divergences which include as a special case both the Euclidean distance and the relative entropy. We cast the learning task as an optimization problem and show that it results in a simple dual form which has interesting algebraic properties. We then discuss a general algorithmic framework to solve the optimization problem. Our training algorithm employs an auxiliary function that bounds the dual’s objective function and can be used with a broad class of Bregman functions. As a specific application of the algorithm we give a detailed derivation for the relative entropy. We analyze the generalization ability of the algorithm by adopting margin-style proof techniques. We also describe and analyze two schemes of online algorithms for the case when the radius of the sphere is set in advance.
Cite
Text
Crammer and Singer. "Learning Algorithm for Enclosing Points in Bregmanian Spheres." Annual Conference on Computational Learning Theory, 2003. doi:10.1007/978-3-540-45167-9_29Markdown
[Crammer and Singer. "Learning Algorithm for Enclosing Points in Bregmanian Spheres." Annual Conference on Computational Learning Theory, 2003.](https://mlanthology.org/colt/2003/crammer2003colt-learning/) doi:10.1007/978-3-540-45167-9_29BibTeX
@inproceedings{crammer2003colt-learning,
title = {{Learning Algorithm for Enclosing Points in Bregmanian Spheres}},
author = {Crammer, Koby and Singer, Yoram},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2003},
pages = {388-402},
doi = {10.1007/978-3-540-45167-9_29},
url = {https://mlanthology.org/colt/2003/crammer2003colt-learning/}
}