III: Small: Probabilistic Hashing for Efficient Search Learning

许多应用程序涉及大量高维数据集。例如，搜索行业通常处理数十亿个网页，其中每个页面通常表示为2^64维的二进制向量。在计算机视觉中，图像通常被表示为数百万维的非二进制向量。能够有效地压缩、检索和挖掘这些数据集的算法具有很高的实用价值。数学上严谨和计算效率高的哈希方法将被开发出来，以显着减少超高维数据集。这些算法将与各种学习技术相结合，包括分类、聚类、近邻搜索、矩阵分解等。该项目建立并扩展了最小散列和b位最小散列，这是搜索应用程序中的标准散列技术。该项目旨在(i)严格分析b位最小哈希，并开发、分析和应用更有效（更准确）的搜索和学习问题；（ii）开发一个统一的概率哈希框架，其本质上由一个排列后跟（最多）一个随机投影组成；（iii）在各种工程约束（存储空间、计算速度、索引能力、对流的适应等）下发展统一的汇总统计理论。在此框架下开发的哈希算法预计将比现有的流行算法（如随机投影和最小哈希）更加高效和准确。这个通用框架允许设计算法适应许多不同的数据类型（稀疏或密集数据，二进制或实值数据，静态或流数据），许多不同的工程需求（计算内积或lp距离，核学习或线性学习），以及不同的存储需求。预期的研究结果包括：用于处理超高维数据集的严格且计算效率高的哈希算法；将所得到的哈希算法与分类、聚类、近邻搜索、奇异值分解、矩阵分解等各种学习技术相结合；并对结果方法进行严格的实验评估，以处理高达2^64维的大数据（例如，tb或潜在的PetaByte）。更广泛的影响：从极高维度的数据中构建预测模型的有效方法可以影响许多依赖机器学习作为从数据中获取知识的主要方法的科学领域。PI的教育和外联工作旨在扩大妇女和代表性不足群体的参与。该项目产生的出版物、软件和数据集将免费传播给更大的科学界。

Numerous applications involve massive, high-dimensional datasets. For example, the search industry routinely deals with billions of web pages, where each page is often represented as a binary vector in 2^64 dimensions. In computer vision, images are often represented as non-binary vectors in millions of dimensions. Algorithms which are capable of efficiently compressing, retrieving, and mining these datasets are of high practical importance. Mathematically rigorous and computationally efficient hashing methods will be developed to dramatically reduce ultra-high-dimensional datasets. These algorithms will be integrated with a variety of learning techniques including classification, clustering, near-neighbor search, matrix factorizations, etc. The project builds on and extends minwise hashing, and b-bit minwise hashing which are standard hashing techniques in search applications. The project aims to (i) rigorously analyze b-bit minwise hashing and develop, analyze, and apply significantly more efficient (and more accurate) to problems in search and learning; (ii) develop a unified framework of probabilistic hashing which essentially consists of one permutation followed by (at most) one random projection; (iii) develop a unified theory of summary statistics under a variety of engineering constraints (storage space, computational speed, indexing capability, adaptation to streaming, etc.). Hashing algorithms developed under this framework are expected to be substantially much more efficient and more accurate than existing popular algorithms such as random projections and minwise hashing. This general framework allows the design algorithms to accommodate many different data types (sparse or dense data, binary or real-valued data, static or streaming data), many different engineering needs (computing inner products or lp distances, kernel learning or linear learning), and different storage requirements. Anticipated results of the proposed research include rigorous and computationally efficient hashing algorithms for dealing with ultra-high-dimensional datasets, the integration of the resulting hashing algorithms into with a variety of learning techniques for classification, clustering, near-neighbor search, singular value decompositions, matrix factorization, etc; and rigorous experimental evaluation of the resulting methods on big (e.g., TeraByte or potentially PetaByte) data of the order of up to 2^64 dimensions. Broader Impacts: Effective approaches to building predictive models from extremely high dimensional data can impact many areas of science that rely on machine learning as the primary methodology for knowledge acquisition from data. The PI's education and outreach efforts aim to broaden the participation of women and underrepresented groups. The publications, software, and datasets resulting from the project will be freely disseminated to the larger scientific community.