The Vapnik-Chervonenkis dimension provides a notion of complexity for systems
of sets. If the VC dimension is small, then knowing this can drastically
simplify fundamental computational tasks such as classification, range
counting, and density estimation through the use of sampling bounds. We analyze
set systems where the ground set $X$ is a set of polygonal curves in
$R^d$ and the sets $R$ are metric balls defined by curve
similarity metrics, such as the Fréchet distance and the Hausdorff distance,
as well as their discrete counterparts. We derive upper and lower bounds on the
VC dimension that imply useful sampling bounds in the setting that the number
of curves is large, but the complexity of the individual curves is small. Our
upper bounds are either near-quadratic or near-linear in the complexity of the
curves that define the ranges and they are logarithmic in the complexity of the
curves that define the ground set.
Описание
[1903.03211] The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances
%0 Journal Article
%1 driemel2019dimension
%A Driemel, Anne
%A Phillips, Jeff M.
%A Psarros, Ioannis
%D 2019
%K complexity foundations generalization learning theory vc-dim
%T The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances
%U http://arxiv.org/abs/1903.03211
%X The Vapnik-Chervonenkis dimension provides a notion of complexity for systems
of sets. If the VC dimension is small, then knowing this can drastically
simplify fundamental computational tasks such as classification, range
counting, and density estimation through the use of sampling bounds. We analyze
set systems where the ground set $X$ is a set of polygonal curves in
$R^d$ and the sets $R$ are metric balls defined by curve
similarity metrics, such as the Fréchet distance and the Hausdorff distance,
as well as their discrete counterparts. We derive upper and lower bounds on the
VC dimension that imply useful sampling bounds in the setting that the number
of curves is large, but the complexity of the individual curves is small. Our
upper bounds are either near-quadratic or near-linear in the complexity of the
curves that define the ranges and they are logarithmic in the complexity of the
curves that define the ground set.
@article{driemel2019dimension,
abstract = {The Vapnik-Chervonenkis dimension provides a notion of complexity for systems
of sets. If the VC dimension is small, then knowing this can drastically
simplify fundamental computational tasks such as classification, range
counting, and density estimation through the use of sampling bounds. We analyze
set systems where the ground set $X$ is a set of polygonal curves in
$\mathbb{R}^d$ and the sets $\mathcal{R}$ are metric balls defined by curve
similarity metrics, such as the Fr\'echet distance and the Hausdorff distance,
as well as their discrete counterparts. We derive upper and lower bounds on the
VC dimension that imply useful sampling bounds in the setting that the number
of curves is large, but the complexity of the individual curves is small. Our
upper bounds are either near-quadratic or near-linear in the complexity of the
curves that define the ranges and they are logarithmic in the complexity of the
curves that define the ground set.},
added-at = {2019-07-19T20:57:39.000+0200},
author = {Driemel, Anne and Phillips, Jeff M. and Psarros, Ioannis},
biburl = {https://www.bibsonomy.org/bibtex/21ab750c7ab35597018c49c7a97ef0c80/kirk86},
description = {[1903.03211] The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances},
interhash = {f4886e153424c16780aa7e936e51c006},
intrahash = {1ab750c7ab35597018c49c7a97ef0c80},
keywords = {complexity foundations generalization learning theory vc-dim},
note = {cite arxiv:1903.03211Comment: 23 pages, 5 figures},
timestamp = {2019-07-19T20:57:39.000+0200},
title = {The VC Dimension of Metric Balls under Fr\'echet and Hausdorff Distances},
url = {http://arxiv.org/abs/1903.03211},
year = 2019
}