CRII: III: Scaling up Distance Metric Learning for Large-scale Ultrahigh-dimensional Data

CRII：III：扩大大规模超高维数据的距离度量学习

• 批准号: 1463988
• 负责人: Tianbao Yang
• 金额: $ 17.46万
• 依托单位: University of Iowa
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-03-01 至 2018-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1463988&HistoricalAwards=false
• 关键词: CRII; III; Scaling; up; Distance

This project is to research and develop highly scalable stochastic optimization algorithms for distance metric learning (DML) for large-scale ultrahigh-dimensional (LSUD) data. DML is a fundamental problem in machine learning aiming to learn a distance metric such that intra-class variation is small and inter-class variation is large. When the scale and dimensionality of data is very large, the computational cost of DML is prohibitive. Domains utilizing machine learning techniques such as computer vision, natural language processing and bioinformatics will be directly impacted by this research. For example, one application is fine-grained image classification, e.g., categorizing different types of flowers or models of vehicles from pictures (this application will be used as one criteria to evaluate success of the research.) The research will enable data scientists to extract more knowledge from massive high-dimensional data complementing the White House BIG DATA Initiative to analyze large and complex data sets. Beyond its research impact, this project will facilitate the development of a new machine learning course at the University of Iowa (UI), and contribute to training future professionals in big data analytics. Broader impact will be further affected by dissemination of results through publications, open-sourced software, etc.This project addresses the computational challenges of LSUD-DML by scaling up the state of the art stochastic gradient descent (SGD) methods. A key computational bottleneck in applying SGD to DML is to project the updated solution into a complicated feasible domain at each iteration. The innovative proposed ideas lie at reducing the total cost of projections by (i) constructing and exploring a low-rank structured stochastic gradient to reduce the cost of projection, and (ii) dividing iterations into epochs and performing a projection-efficient SGD at each epoch to reduce the number of projections. Investigating data-dependent sampling strategies (i.e., selective sampling, importance sampling, and a combination of both) for LSUD-DML will further scale up the proposed methods. This research will provide experimental evidence regarding the scalability of the proposed algorithms while revealing insights into the proposed techniques and various analytical tradeoffs.For further information see the project web site at: http://homepage.cs.uiowa.edu/~tyng/dml.html.

本项目旨在研究和开发用于大规模超高维（LSUD）数据的距离度量学习（DML）的高度可扩展的随机优化算法。DML是机器学习中的一个基本问题，旨在学习一个距离度量，使得类内变化很小，类间变化很大。 当数据的规模和维数非常大时，DML的计算成本是令人望而却步的。利用机器学习技术的领域，如计算机视觉、自然语言处理和生物信息学，将直接受到这项研究的影响。例如，一个应用是细粒度图像分类，例如，从图片中分类不同类型的花或车辆模型（此应用程序将用作评估研究成功的标准之一）。该研究将使数据科学家能够从大量高维数据中提取更多知识，补充白宫大数据计划，以分析大型复杂的数据集。除了研究影响外，该项目还将促进爱荷华州大学（UI）新机器学习课程的开发，并有助于培训未来的大数据分析专业人员。通过出版物、开源软件等传播结果将进一步影响更广泛的影响。该项目通过扩大最先进的随机梯度下降（SGD）方法来解决LSUD-DML的计算挑战。SGD应用于DML的一个关键计算瓶颈是在每次迭代时将更新的解投影到一个复杂的可行域中。提出的创新思想在于通过以下方式降低投影的总成本：（i）构建和探索低秩结构化随机梯度以降低投影成本，以及（ii）将迭代划分为历元并在每个历元执行投影有效的SGD以减少投影的数量。调查依赖数据的抽样策略（即，选择性采样、重要性采样以及两者的组合）将进一步扩展所提出的方法。这项研究将提供有关所提出的算法的可扩展性的实验证据，同时揭示对所提出的技术和各种分析权衡的见解。http://homepage.cs.uiowa.edu/~tyng/dml.html