Algorithms for Data Analysis

所建议活动的智力价值。本研究的主要焦点是以下普遍存在的算法挑战：给定一个大数据集，提供数据的“简单”但“准确”的描述。这个问题可以从几个层面来处理。在第一种方法中，它被视为一个数据聚类问题。聚类算法（针对测量点的不相似性的特定“失真”而设计）将数据划分到聚类中，以便聚类内点之间的失真最小化（即相似性最大化），而聚类之间的失真最大化。在科学、工程、商业、政府和医疗应用中普遍存在的庞大数据库中，“多项式时间算法”不够好，因为以二次或三次时间运行的典型算法太慢，无法在千兆字节或太字节的数据上执行。因此，这一建议将重点放在近线性时间算法上。本文描述了该提议者最近开发的一种特殊的新颖方法。在第二部分中，讨论了更高级的数据分析问题。在这些问题中，可以使用更丰富、更灵活的数据模型，如多个低次曲面的混合模型。这些模型中的数据分析超出了当前近似算法的范围。数据分析需要对数据进行划分，因此继承了聚类的np完备性；但除此之外，应用统计学也带来了新的困难，例如现实世界数据中缺失或不完整记录的问题。这种结合需要解决新的基本算法和几何问题。该建议的第三部分不是关注特定的聚类问题，而是为这种非参数推理问题建立正确的理论。基本原则是这样的：我们应该只对那些允许高质量聚类的数据集进行聚类。通常，对于聚类算法来说，使特定输入变得困难的原因是，它的最佳聚类并不比平均聚类好多少：输入没有被整齐地分成分离良好的部分。一个好的数据分析应该检测到这一事实，而不是停留在寻找最佳但接近平均的聚类上。因此，为聚类开发一个健全的理论框架需要抛弃迄今为止占主导地位的“最坏情况分析”框架。第四部分对EM聚类算法及其变体进行了理论分析。EM是一种迭代启发式算法，其性能几乎没有保证。然而，它是快速的，并在实践中广泛使用。正因为如此，一个重要的目标是确定在什么条件下EM表现良好，以及在什么条件下需要其他方法。该提案的第五部分专门讨论一个不同的主题：由于有限的处理能力或有限的通信能力而对反馈控制机制施加的限制。由于控制任务的实时性，传统的“输入-输出”电路复杂性并不是一个合适的理论框架。主要有两种类型的问题。首先是表征一类稳定任务，可以由高度并行，超高速数字控制电路执行。二是在通信信道存在噪声的情况下，保证控制系统各组成部分之间的可靠实时通信。拟议活动的更广泛影响。数据分析在许多科学、工程、商业、政府和医疗应用中都是必需的。从庞大的数据库中筛选出有用信息的重要性是如此之大，以至于数据分析算法以及支撑这些算法设计的数学框架的进步对社会具有重大的潜在益处。在我们的技术基础设施中，越来越多的自动化创造了控制、计算和通信技术的融合。与执行这种趋同有关的一些困难将通过在提案最后一节所述问题上取得进展而得到解决。提案中的所有主题都非常适合研究生，在某些情况下，本科生，研究。在算法、复杂性、控制和信息论方面的跨学科学生培训正在进行中（由PI和几位同事进行）。计划在拟议的调查期间增加这一活动。

Intellectual merit of the proposed activity. The primary focus of this investigation is the following ubiquitous algorithmic challenge: Given a large data set, provide a "simple" yet "accurate" description of the data.The question is treated at several levels. In the first it is considered as a data-clustering problem. A clustering algorithm (designed with regard to a particular "distortion" that measures dissimilarity of points) partitions the data into clusters so that the distortion between points within a cluster is minimized (i.e., similarity is maximized), while the distortion across clusters is maximized. In the huge databases prevalent in scientific, engineering, business, government and medical applications, "polynomial time algorithms" are not good enough since a typical algorithm running in quadratic or cubic time is too slow to be executed on gigabytes or terabytes of data. This proposal therefore places an emphasis on near-linear time algorithms. A particular novel approach, recently developed by the proposer, is described.In the second treatment, more advanced data analysis problems are addressed. In these problems richer and more flexible models for the data are allowed, such as mixture models of several low-degree surfaces. Data analysis in these models is beyond the reach of current approximation algorithms. The data analysis requires partitioning of the data, and so the NP-completeness of clustering is inherited; but in addition, new difficulties are inherited from applied statistics, such as the issue of missing or incomplete records in real world data. The combination requires solution of fundamental new algorithmic and geometric questions.The third part of the proposal is concerned not with a particular clustering problem but with setting up the right kind of theory for such nonparametric inference problems. The fundamental principle is this: We should seek to cluster only data sets that admit a high-quality clustering. Often, what makes a particular input hard for a clustering algorithm is that its best clustering is little better than average: the input does not separate cleanly into well-separated pieces. A good data analysis should detect this fact, rather than stall on a search for a best yet near-average clustering. Developing a sound theoretical framework for clustering therefore requires departing from the "worst-case analysis" framework that has been dominant so far.The fourth part of the proposal is devoted to theoretical analysis of the EM clustering algorithm and its variants. EM is an iterative heuristic for which there are few performance guarantees. However, it is fast, and widely used in practice. Because of this, an important goal is to determine under what conditions EM performs well, and what conditions require other approaches.The fifth part of the proposal is devoted to a different topic: the limitations imposed on feedbackControl mechanisms because of limited processing power or limited communication capacity. Because of the real-time nature of control tasks, conventional "input-output" circuit complexity is not an appropriate theoretical framework. Two general types of questions are pursued. The first is characterization of the class of stabilization tasks that can be performed by highly parallelized, ultra-fast digital control circuits. The second is the ensuring of reliable and real-time communications among components of a control system in spite of noise on the communication channels. Broader impact of the proposed activity. Data analysis is required in many scientific, engineering, business, government and medical applications. The importance of sifting out useful information from huge databases is such, that advances in data analysis algorithms as well as in the mathematical framework underpinning the design of these algorithms, has significant potential benefit to society.Increasing automation in our technological infrastructure has created a convergence of control, computation and communication technologies. Some of the difficulties associated with carrying out this convergence will be resolved through progress on the questions described in the last section of the proposal.All topics in the proposal are highly suited to graduate, and in some cases undergraduate, research. Interdisciplinary student training in algorithms, complexity, control and information theory is ongoing (by the PI and several colleagues). Increase in this activity is intended during the period of the proposed investigation.