CAREER: Transforming data analysis via new algorithms for feature extraction

数据的分析和探索，包括分类、推理和检索，是科学和应用领域中普遍存在的任务。对于任何这样的任务，一个基本的范例是提取相关的特征。在数据分析和探索算法的设计中，特征提取技术作为基本的构建块或基元，可以组合起来模拟复杂的行为。一些基本的特征提取工具包括主成分分析（PCA）、独立成分分析（ICA）和基于半空间的学习和分类。数据很少满足这些模型和特征提取工具的精确假设，并且这些工具的组合放大了误差。这激发了设计新算法的挑战性任务，这些算法对噪声具有鲁棒性，并且可以组合为构建块，同时保持误差传播处于控制之下。建议的工作将：(1)将ICA从一个非常成功的实用工具提升到一个算法原语，具有强大的理论保证和适用于独立之外的丰富问题族。(2)找到合理的假设和算法，可以有效地学习半空间的交叉点。(3)系统地研究以下被称为子集选择问题的PCA的良好动机细化。这种改进的目的是在输入数据的给定特征中选择相关的特征，这与PCA不同，PCA会创建新的、可能是人为的特征。新的特征提取算法增强了数据密集型领域（如生物学、信号处理和计算机视觉）研究人员可用的工具箱。它们还使安全、市场营销、商业和政府流程中的从业人员以及本质上涉及分析功能丰富的数据的任何领域的从业人员能够改进数据分析。提出的工作包括实现更实用的算法。该项目的教育和推广方面包括对年轻研究人员的指导，为研究生和本科生设计一门新课程，其中包括一些PI的研究，以及让大学预科学生和当地社区参与科学和研究。

Analysis and exploration of data, including classification, inference, and retrieval, are ubiquitous tasks in science and applied fields. Given any such task, a fundamental paradigm is the extraction of features that are relevant. In the design of algorithms for the analysis and exploration of data, feature extraction techniques act as basic building blocks or primitives that can be combined to model complex behavior. Some of the fundamental feature extraction tools include Principal Component Analysis (PCA), Independent Component Analysis (ICA), and half-space-based learning and classification. Data rarely satisfy the precise assumptions of these models and feature extraction tools, and combining these tools amplifies errors. This motivates the challenging task of designing new algorithms that are robust against noise and that can be combined as building blocks while keeping the error propagation under control.The proposed work will:(1) Raise ICA from a very successful practical tool to an algorithmic primitive with strong theoretical guarantees and applicability to a rich family of problems beyond independence.(2) Find reasonable assumptions and algorithms that allow efficient learning of intersections of half-spaces.(3) Systematically study the following well-motivated refinement of PCA known as the subset selection problem. This refinement aims to select relevant features among the given features of the input data, unlike PCA, which creates new and possibly artificial features.New feature extraction algorithms enhance the toolbox available to researchers in data-intensive fields such as biology, signal processing and computer vision. They also enable improved data analysis by practitioners in security, marketing, business and government processes, and essentially any field that involves the analysis of feature-rich data. The proposed work includes the implementation of the more practical algorithms.Education and outreach aspects of this project include the mentoring of young researchers, the design of a new course for graduate and undergraduate students incorporating some of the PI's research, and the involvement of pre-college students and local communities into science and research.