BIGDATA: F: Big Data Analysis via Non-Standard Property Testing

在现代，各个领域都在不断产生海量数据：包括正在进行的大规模科学实验，无处不在的智能手机和传感器，社交媒体上内容的持续生产和演变，以及许多其他领域。如何有效地处理和分析这些海量数据？计算机科学的一个分支“属性测试”寻求开发超快算法来分析海量数据集，以快速确定数据是否具有某些感兴趣的属性。然而，在性能测试中主要考虑的标准理论模型并不能很好地适用于许多真实世界的数据分析场景；这些标准模型优先考虑数学优雅，但它们所做的假设与实际数据分析算法的能力或许多实际数据集的性质不太一致。(作为一个例子，这些模型通常假设数据分析算法可以合成任意数据点并对其进行查询以接收关于应该如何标记这些数据点的准确信息，但是在许多真实世界的设置中，这种查询是不可能的，在这些环境中，数据点是按原样出现的，并且不能被合成以满足数据分析师的规范。作为另一个例子，这些模型通常只能处理被假设服从某些高度结构化的概率分布的数据，但现实世界的数据是杂乱无章的，很少具有如此高度的结构。)这个项目的高级目标是开发和分析非标准的性能测试模型，明确的目标是开发与现实世界数据分析问题的现实和约束相一致的算法。一个重要的相关目标是，通过开展外联活动和培训研究生，包括历来任职人数不足的群体的成员，促进人力资源开发，使其掌握对该项目至关重要的分析和算法技术。为了实现更广泛的影响，计划的活动还包括新课程、调查文章，以及继续针对中小学生的推广活动。更详细地说，该项目将专注于大数据属性测试算法的三个不同方面，所有这些都是出于对真实世界数据分析的考虑：(1)该项目的第一个重点将是开发灵活的算法，用于测试海量高维数据集是否已被标记为“军政府”-这是一种标记规则，它只依赖于巨大的可能特征集中非常小但未知的数据特征集。在之前工作的基础上，调查人员将致力于开发军政府测试算法，这种算法可以处理任意数据分布和噪声数据，即使只给出对正在分析的数据集的有限形式的访问，也可以成功。(2)该项目的第二个重点将是将思想和技术从理论机器学习算法转移到海量数据集的性能测试领域。研究人员之前的工作为如何修改(某些相对低效的)机器学习算法以产生用于数据分析的更有效的属性测试算法提供了概念验证，但这种转移仅在上文提到的相对受限的属性测试标准模型中进行，这些模型假设高度结构化的数据分布。在这个项目中，研究人员将致力于扩展这些早期的结果，以便机器学习技术将产生更灵活的、具有更大现实适用性的属性测试模型的算法。(3)最后，本项目的第三个重点是开发不需要对合成数据点进行查询而只使用随机样本的属性测试算法，该算法可以应用于高维连续数据集。这种类型的数据通常出现在传感器或不同类型的测量生成数据的环境中，但大多数属性测试算法是为离散二进制值数据而不是连续数据设计的。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

In the modern era truly enormous amounts of data are constantly being generated across a wide range of domains: these include ongoing large-scale scientific experiments, ubiquitous smartphones and sensors, the continuous production and evolution of content on social media, and many others. How can this flood of data be efficiently processed and analyzed? A branch of computer science called "property testing" seeks to develop ultra-fast algorithms for analyzing massive data sets to quickly determine whether or not the data has some property of interest. However, the standard theoretical models that have mostly been considered in property testing are not well suited to many real-world data analysis scenarios; these standard models prioritize mathematical elegance, but the resulting assumptions they make do not align well with the abilities of actual data analysis algorithms or with the nature of many actual data sets. (As one example, these models typically assume that a data analysis algorithm can synthesize arbitrary data points and query them to receive accurate information about how such data points should be labeled, but such queries are impossible in many real-world settings where data points "come as they are" and cannot be synthesized to meet the specifications of a data analyst. As another example, these models typically can only deal with data which is assumed to follow certain highly structured probability distributions, but real-world data is messy and rarely possesses such a high degree of structure.) The high-level goal of this project is to develop and analyze non-standard models of property testing, with the explicit goal of developing algorithms which align with the realities and constraints of real-world data analysis problems. An important related goal is to foster human resource development by performing outreach and training graduate students, including members of historically under-represented groups, in the analytic and algorithmic techniques that are central to this project. Planned activities to achieve broader impacts also include new courses, survey articles, and the continuation of outreach activities aimed at students at the elementary and middle school levels.In more detail, the project will focus on three different aspects of property testing algorithms for big data, all of which are motivated by considerations arising from real-world data analysis:(1) The first focus of the project will be on developing flexible algorithms for testing whether a massive high-dimensional data set has been labeled according to a "junta" --- this is a labeling rule which depends only on a very small but unknown set of data features out of a huge set of possible features. Building on their previous work, the investigators will work to develop junta testing algorithms which can handle arbitrary data distributions and noisy data, and can succeed even given only a limited form of access to the data set being analyzed. (2) The second focus of the project will be on transferring ideas and techniques from theoretical machine learning algorithms to the domain of property testing of massive data sets. Previous work of the investigators gave a proof-of-concept for how (certain relatively inefficient) machine learning algorithms can be modified to yield far more efficient property testing algorithms for data analysis, but this transfer went through only in the relatively constrained standard models of property testing, alluded to above, which assume highly structured data distributions. In this project the investigators will work to extend these earlier results so that the machine learning techniques will yield algorithms for more flexible property testing models that are of greater real-world applicability.(3) Finally, the third focus of the project is to develop property testing algorithms which do not need to make queries on synthetic data points but instead use only random samples, and which can be applied to high-dimensional continuous data sets. Data of this type arises commonly in settings where sensors or measurements of different sorts are generating the data, but most property testing algorithms are designed for discrete binary-valued data rather than continuous data.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.