New set-theoretic tools for statistical learning

点击翻译按钮获取中文摘要

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).