Probabilistic methods in computer science and machine learning

计算机科学和机器学习中的概率方法

• 批准号: RGPIN-2017-03777
• 负责人: Devroye, Luc
• 金额: $ 5.17万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=649173
• 关键词: Probabilistic; methods; computer; science; machine

We seek to further the understanding of probabilistic phenomena that occur in the design and behavior of algorithms, data structures, networks, graphs and pattern recognition (machine learning) methods. The long-term plan has four axes of research:******(1) The in-depth analysis of random trees and random structures that are practically relevant. We will in particular focus on families of randomized trees that act on arbitrary non-random high-dimensional data, on random tries (in the context of the bit model of complexity), and on hyperplane search trees.******(2) Networks with geometric, connectivity, directional, or other restrictions appear in many contexts. We propose to study broad classes of them and pay particular attention to connectivity thresholds, emergence of giant components, diameter, and structural properties in general. Included are Kademlia and peer-to-peer networks, random Erdos-Renyi graphs with external high-dimensional parameters, and various brands of random geometric graphs.******(3) The continued effort to design universally consistent but also computationally efficient classifiers, with particular attention given to tree classifiers. Random forest classifiers are of special interest in view of their simplicity. As part of this effort, we will try to understand, theoretically, why deep learning networks are often successful, and investigate the relationship between the accuracy of these learning networks and their complexity beyond classical measures such as the Vapnik- Chervonenkis dimension.******(4) The development of new paradigms for random variate generation and the exact simulation of objects or processes that hitherto could either not be generated in an exact manner, or could at best be generated inefficiently. In addition, we will develop Shannon style information-theoretic lower bounds, and hopefully matching upper bounds, for the expected number of random fair bits needed to generate random variables with a desired accuracy.

我们寻求进一步理解发生在算法、数据结构、网络、图形和模式识别（机器学习）方法的设计和行为中的概率现象。长期计划有四个研究轴：******(1)对实际相关的随机树和随机结构进行深入分析。我们将特别关注作用于任意非随机高维数据的随机树族、随机尝试（在复杂度的位模型的上下文中）和超平面搜索树。******(2)具有几何、连通性、方向性或其他限制的网络出现在许多环境中。我们建议对它们进行广泛的研究，并特别关注连接性阈值、巨型部件的出现、直径和结构特性。包括Kademlia和点对点网络，具有外部高维参数的随机Erdos-Renyi图，以及各种品牌的随机几何图。******(3)继续努力设计普遍一致但计算效率高的分类器，特别关注树分类器。随机森林分类器由于其简单性而受到特别关注。作为这项工作的一部分，我们将尝试从理论上理解为什么深度学习网络通常是成功的，并研究这些学习网络的准确性和它们的复杂性之间的关系，超越经典的度量，如Vapnik- Chervonenkis维度。******(4)为随机变量生成和对象或过程的精确模拟开发新的范例，这些对象或过程到目前为止要么不能以精确的方式生成，要么最多只能低效地生成。此外，我们将开发Shannon风格的信息理论下界，并希望匹配上界，用于生成具有所需精度的随机变量所需的随机公平比特的预期数量。