Probabilistic methods in computer science and machine learning

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

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.