PROBABILISTIC ESTIMATION OF VAPNIK-CHERVONENKIS DIMENSION

Przemyslaw Klesk

2012

Abstract

We present an idea of probabilistic estimation of Vapnik-Chervonenkis dimension given a set of indicator functions. The idea is embedded in two algorithms we propose --- named A and A. Both algorithms are based on an approach that can be described as 'expand or divide and conquer'. Also, algorithms are parametrized by probabilistic constraints expressed in a form of (epsilon, delta)-precision. The precision implies how often and by how much the estimate can deviate from the true VC-dimension. Analysis of convergence and computational complexity for proposed algorithms is also presented.

Paper Citation

in Harvard Style

Klesk P. (2012). PROBABILISTIC ESTIMATION OF VAPNIK-CHERVONENKIS DIMENSION . In Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8425-95-9, pages 262-270. DOI: 10.5220/0003721702620270

in Bibtex Style

@conference{icaart12,
author={Przemyslaw Klesk},
title={PROBABILISTIC ESTIMATION OF VAPNIK-CHERVONENKIS DIMENSION},
booktitle={Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2012},
pages={262-270},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003721702620270},
isbn={978-989-8425-95-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - PROBABILISTIC ESTIMATION OF VAPNIK-CHERVONENKIS DIMENSION
SN - 978-989-8425-95-9
AU - Klesk P.
PY - 2012
SP - 262
EP - 270
DO - 10.5220/0003721702620270