Computing the Shattering Coefficient of Supervised Learning Algorithms
It provides foundational theoretical insights for the entire field of supervised machine learning, addressing uniform convergence and learning guarantees.
This paper proves the shattering coefficient for Hilbert spaces containing the input space, establishing theoretical guarantees for supervised learning algorithms based on the Empirical Risk Minimization Principle.
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.