This article is cited in 3 papers

Intellectual Control Systems, Data Analysis

Sharpness estimation of combinatorial generalization ability bounds for threshold decision rules

Sh. Kh. Ishkina^a, K. V. Vorontsov<sup>b

a</sup> Dorodnicyn Computing Centre, Russian Academy of Sciences, Moscow, 119333 Russia
^b Moscow Institute of Physics and Technology, Dolgoprudnyi, Moscow oblast, 141700 Russia

Abstract: This article is devoted to the problem of calculating an exact upper bound for the functionals of the generalization ability of a family of one-dimensional threshold decision rules. An algorithm is investigated that solves the stated problem and is polynomial in the total number of samples used for training and validation and in the number of training samples. A theorem is proved for calculating an estimate for the functional of expected overfitting and an estimate for the error rate of the method for minimizing empirical risk on a validation set. The exact bounds calculated using the theorem are compared with the previously known quick-to-compute upper bounds so as to estimate the orders of overestimation of the bounds and to identify the bounds that could be used in real problems.

Keywords: threshold classifier, generalization ability, combinatorial theory, probability of overfitting, complete cross-validation, Rademacher complexity.

Presented by the member of Editorial Board: A. I. Mikhal'skii

Received: 29.06.2020
Revised: 09.12.2020
Accepted: 15.01.2021

DOI: 10.31857/S000523102105010X

 English version: Automation and Remote Control, 2021, 82:5, 863–876

Bibliographic databases:

• 
• 
•