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）将迭代划分为多个epoch并在每个epoch执行一个投影效率高的SGD来减少投影的数量。研究LSUD-DML的数据依赖抽样策略（即，选择性抽样、重要性抽样以及两者的组合）将进一步扩展所提出的方法。本研究将提供关于所提出算法的可扩展性的实验证据，同时揭示对所提出的技术和各种分析权衡的见解。欲了解更多信息，请参阅该项目的网站：http://homepage.cs.uiowa.edu/~tyng/dml.html。