4.3 Article

Learning half-spaces on general infinite spaces equipped with a distance function

Journal

INFORMATION AND COMPUTATION
Volume 291, Issue -, Pages -

Publisher

ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.ic.2023.105008

Keywords

VC-dimension; Pseudo-dimension; Independence number; Dual VC-dimension; Regular n-simplex; Non-metric space; Distance space; Learning with large margin (width)

Ask authors/readers for more resources

This paper investigates the VC-dimension of the class of half-spaces in an infinite distance space chi, where no assumptions about the distance function are made and the metric axioms need not be satisfied. It is not clear what the VC-dimension of Hof half-spaces in chi may be and if there are generalization error bounds for learning H. The authors define a combinatorial dimension of chi as the independence number of the class of balls in chi and compute it for different types of distance spaces. They then use this dimension to provide a generalization error bound for learning H in any infinite distance space chi.
For a general infinite distance space chi, with no assumptions about the distance function, which need not satisfy the metric axioms, it is not clear what the VC-dimension of the class Hof half-spaces in chi may be and if there are generalization error bounds for learning H. We define a combinatorial dimension of chi to be the independence number of the class of balls in chi. We compute it for Euclidean space and for several non-metric distance spaces. Using this dimension, we are able to provide a generalization error bound for learning Hover any infinite distance space chi. (c) 2023 Elsevier Inc. All rights reserved.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.3
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available