CAREER: Transforming data analysis via new algorithms for feature extraction

数据的分析和探索，包括分类，推理和检索，是科学和应用领域中普遍存在的任务。对于任何这样的任务，一个基本的范例是提取相关的特征。在设计用于分析和探索数据的算法时，特征提取技术充当基本构建块或基元，其可以组合以模拟复杂行为。一些基本的特征提取工具包括主成分分析（PCA）、独立成分分析（伊卡）和基于半空间的学习和分类。数据很少能满足这些模型和特征提取工具的精确假设，而将这些工具结合起来会放大错误。本文的工作将：（1）将伊卡从一个非常成功的实用工具提升为一个具有强大理论保证的算法原型，并使其适用于除独立性之外的大量问题。(2)找到合理的假设和算法，允许有效地学习半空间的交集。(3)系统地学习下面的动机良好的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.