Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Ottawa

$22,000.00

New set-theoretic tools for statistical learning

FY 2013-14

Summary
Statistical machine learning theory is a major research direction in computer science, providing a concentual framework for such applications as pattern recognition, classification, and data mining. The theory is using a wide variety of mathematical tools, primarily probability theory and statistics, as well as modern functional analysis, combinatorics, and geometry. In this proposal, we aim to address some open problems of statistical learning using tools of set theory, logic, and set-theoretic topology that have not been previously applied. Here are some of the problems we want to focus on. The question about the existence of finite sample compression schemes for every concept class of finite VC dimension remains open for a quarter of a century. It is a challenging combinatorial problem where, we believe, the methods of Ramsey theory of Fraïssé structures could be applied profitably. Another old open question is that of existence of a universally consistent learning algorithm that is at the same time ""smart"", that is, whose average performance improves with the sample size. Again, the problem seems to be essentially combinatorial in nature, and we believe the answer is in the negative due to a Ramsey-type argument. We will apply methods of logic and model theory in order to develop an ""automatic"" way of translating any known result involving an assumption of independent identically distributed random variables to a more general result involving a weaker assumption of exchangeable random variables in the sense of de Finetti. An open problem by Vidyasagar calls for determining the maximal discrepancy of a learning algorithm in a case where it is not zero (which is perhaps more realistic for applications); we will address the problem using the techniques of Talagrand (""witness of irregularity"") and descriptive set theory. Finally, much effort will go to the problem of dimensionality reduction of data to lower dimensions using a rather revolutionary idea of Borel isomorphisms between the domains, as opposed to traditionally used ""nicer"" functions (mostly, Lipschitz).
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
261450-2012
Name nom
Pestov, Vladimir
Department département
Mathematics and Statistics
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2012
Award amount
22000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2805
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Learning and inference theories
Research subject fr
Théories de l'apprentissage et l'inférence
Partie
2
Nb partie
5
Application title
New set-theoretic tools for statistical learning
Keyword
NSERC
Application summary
Statistical machine learning theory is a major research direction in computer science, providing a concentual framework for such applications as pattern recognition, classification, and data mining. The theory is using a wide variety of mathematical tools, primarily probability theory and statistics, as well as modern functional analysis, combinatorics, and geometry. In this proposal, we aim to address some open problems of statistical learning using tools of set theory, logic, and set-theoretic topology that have not been previously applied. Here are some of the problems we want to focus on. The question about the existence of finite sample compression schemes for every concept class of finite VC dimension remains open for a quarter of a century. It is a challenging combinatorial problem where, we believe, the methods of Ramsey theory of Fraïssé structures could be applied profitably. Another old open question is that of existence of a universally consistent learning algorithm that is at the same time ""smart"", that is, whose average performance improves with the sample size. Again, the problem seems to be essentially combinatorial in nature, and we believe the answer is in the negative due to a Ramsey-type argument. We will apply methods of logic and model theory in order to develop an ""automatic"" way of translating any known result involving an assumption of independent identically distributed random variables to a more general result involving a weaker assumption of exchangeable random variables in the sense of de Finetti. An open problem by Vidyasagar calls for determining the maximal discrepancy of a learning algorithm in a case where it is not zero (which is perhaps more realistic for applications); we will address the problem using the techniques of Talagrand (""witness of irregularity"") and descriptive set theory. Finally, much effort will go to the problem of dimensionality reduction of data to lower dimensions using a rather revolutionary idea of Borel isomorphisms between the domains, as opposed to traditionally used ""nicer"" functions (mostly, Lipschitz).