New set-theoretic tools for statistical learning

用于统计学习的新集合论工具

• 批准号: 261450-2012
• 负责人: Pestov, Vladimir
• 金额: $ 1.6万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=571045
• 关键词: New; set; theoretic; tools; statistical

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

统计机器学习理论是计算机科学的一个重要研究方向，为模式识别、分类和数据挖掘等应用提供了一个概念框架。该理论使用了各种各样的数学工具，主要是概率论和统计学，以及现代泛函分析，组合学和几何学。在这个建议中，我们的目标是解决一些开放的问题，统计学习使用的工具集理论，逻辑和集理论拓扑结构，以前没有应用。以下是我们要关注的一些问题。 对于有限VC维的每一个概念类，有限样本压缩方案的存在性问题在世纪以来一直是一个悬而未决的问题。这是一个具有挑战性的组合问题，我们相信，Fraïssé结构的拉姆齐理论的方法可以被有益地应用。另一个老的开放的问题是，存在一个普遍一致的学习算法，在同一时间是“智能”，也就是说，其平均性能提高与样本大小。同样，这个问题似乎本质上是组合的，我们相信答案是否定的，因为拉姆齐型的论点。我们将应用逻辑和模型论的方法，以便开发一种“自动”的方式，将任何已知的涉及独立同分布随机变量假设的结果转化为更一般的结果，涉及de Finetti意义上的可交换随机变量的较弱假设。Vidyasagar的一个开放问题要求确定学习算法在不为零的情况下的最大差异（这对于应用程序来说可能更现实）;我们将使用Talagrand（“不规则性的见证”）和描述性集合论的技术来解决这个问题。最后，大量的努力将去降维的问题，数据到较低的维度使用一个相当革命性的想法，博雷尔同构域之间，而不是传统上使用的“更好”的功能（主要是，Lipschitz）。