Computing the Shattering Coefficient of Supervised Learning Algorithms
The Statistical Learning Theory (SLT) provides the theoretical guarantees for supervised machine learning based on the Empirical Risk Minimization Principle (ERMP). Such principle defines an upper bound to ensure the uniform convergence of the empirical risk Remp(f), i.e., the error measured on a given data sample, to the expected value of risk R(f) (a.k.a. actual risk), which depends on the Joint Probability Distribution P(X x Y) mapping input examples x in X to class labels y in Y. The uniform convergence is only ensured when the Shattering coefficient N(F,2n) has a polynomial growing behavior. This paper proves the Shattering coefficient for any Hilbert space H containing the input space X and discusses its effects in terms of learning guarantees for supervised machine algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheorySimilar Papers 제목 키워드 기반
On the Complexity of Labeled Datasets
The Statistical Learning Theory (SLT) provides the foundation to ensure that a supervised algorithm generalizes the mapping $f: \mathcal{X} \to \mathcal{Y}$ given $f$ is selected from its search space bias $\mathcal{F}$.…
Learning TheoryProviding theoretical learning guarantees to Deep Learning Networks
Deep Learning (DL) is one of the most common subjects when Machine Learning and Data Science approaches are considered. There are clearly two movements related to DL: the first aggregates researchers in quest to outperfo…
Deep LearningLearning TheoryFat-Shattering Dimension of $k$-fold Aggregations
We provide estimates on the fat-shattering dimension of aggregation rules of real-valued function classes. The latter consists of all ways of choosing $k$ functions, one from each of the $k$ classes, and computing a poin…
Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
In 1984, Valiant [ 7 ] introduced the Probably Approximately Correct (PAC) learning framework for boolean function classes. Blumer et al. [ 2] extended this model in 1989 by introducing the VC dimension as a tool to char…
PAC learningImproved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation
Learning sketching matrices for fast and accurate low-rank approximation (LRA) has gained increasing attention. Recently, Bartlett, Indyk, and Wagner (COLT 2022) presented a generalization bound for the learning-based LR…