Algorithms for Data Analysis

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