RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Ufimsk. Mat. Zh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Ufimsk. Mat. Zh., 2018, Volume 10, Issue 1, Pages 50–65 (Mi ufa417)  

Combinatorial bounds of overfitting for threshold classifiers

Sh. Kh. Ishkina

Federal Research Center УComputer Science and ControlФ of RAS, Vavilova str. 44/2, 119333, Moscow, Russia

Abstract: Estimating the generalization ability is a fundamental objective of statistical learning theory. However, accurate and computationally efficient bounds are still unknown even for many very simple cases. In this paper, we study one-dimensional threshold decision rules. We use the combinatorial theory of overfitting based on a single probabilistic assumption that all partitions of a set of objects into an observed training sample and a hidden test sample are of equal probability. We propose a polynomial algorithm for computing both probability of overfitting and of complete cross-validation. The algorithm exploits the recurrent calculation of the number of admissible paths while walking over a three-dimensional lattice between two prescribed points with restrictions of special form. We compare the obtain sharp estimate of the generalized ability and demonstrate that the known upper bound are too overstated and they can not be applied for practical problems.

Keywords: computational learning theory, empirical risk minimization, combinatorial theory of overfitting, probability of overfitting, complete cross-validation, generalization ability, threshold classifier, computational complexity.

Funding Agency Grant Number
Russian Foundation for Basic Research 15-37-50350_мол_нр
14-07-00847_а
The work is supported by RFBR under projects no. 15-37-50350 mol nr and no. 14-07-00847.


Full text: PDF file (552 kB)
References: PDF file   HTML file

English version:
Ufa Mathematical Journal, 2018, 10:1, 49–63 (PDF, 471 kB); https://doi.org/10.13108/2018-10-1-49

Bibliographic databases:

Document Type: Article
UDC: 519.25
MSC: 68Q32, 60C05
Received: 21.12.2016

Citation: Sh. Kh. Ishkina, “Combinatorial bounds of overfitting for threshold classifiers”, Ufimsk. Mat. Zh., 10:1 (2018), 50–65; Ufa Math. J., 10:1 (2018), 49–63

Citation in format AMSBIB
\Bibitem{Ish18}
\by Sh.~Kh.~Ishkina
\paper Combinatorial bounds of overfitting for threshold classifiers
\jour Ufimsk. Mat. Zh.
\yr 2018
\vol 10
\issue 1
\pages 50--65
\mathnet{http://mi.mathnet.ru/ufa417}
\elib{http://elibrary.ru/item.asp?id=32705552}
\transl
\jour Ufa Math. J.
\yr 2018
\vol 10
\issue 1
\pages 49--63
\crossref{https://doi.org/10.13108/2018-10-1-49}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000432413800004}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85044277776}


Linking options:
  • http://mi.mathnet.ru/eng/ufa417
  • http://mi.mathnet.ru/eng/ufa/v10/i1/p50

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • ”фимский математический журнал
    Number of views:
    This page:62
    Full text:23
    References:7

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019