Machine Learning, On-line Algorithms, and Optimization

机器学习、在线算法和优化

• 批准号: 0105488
• 负责人: Avrim Blum
• 金额: $ 28万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0105488&HistoricalAwards=false
• 关键词: Machine; Learning; line; Algorithms; Optimization

This research involves developing new connections between the areas ofmachine learning, on-line algorithms, and optimization, and usingthese connections to address fundamental problems in allthree areas.In machine learning, one focus of this research is how to best combinea small sample of labeled data with a large amount of unlabeled datain order to produce high quality predictions. This type of problemhas become especially important given the explosion of data nowavailable over the web. This research is exploring how techniquessuch as network flow and graph cuts from the optimization literaturecan be used to provide a new means of attack, and how to best make anumber of design choices that arise in this approach. Another basicquestion this work investigates is what kinds of concepts can beautomatically learned in the presence of highly noisy data, and towhat extent substantially new types of algorithms may be possible.The PI recently gave the first algorithm to learn a class of conceptsin the presence of noise that is provably not learnable by a wideclass of techniques known as Statistical Query methods. The currentresearch aims to expand on this work and explore the extent to whichit can be pushed much further. The types of learning problems beingstudied have close connections to problems of decoding random linearcodes and finding approximate shortest lattice vectors that arise incryptography. Improvements to the learning algorithms should impactour understanding of those problems as well.Another major thrust of this research is the use of techniques frommachine learning to address problems in online algorithms. Inparticular, the highly-developed "weighted experts" technology inmachine learning suggests new approaches for combining multiple onlinealgorithms that may simplify a number of longstanding open problems.This work is studying the extent to which this connection can provideinsight into several basic questions, such as dynamic optimality insearch trees and the weighted caching problem. Finally, this researchis also studying a number of basic approximability questions, as wellas exploring new frameworks for the analysis of local searchtechniques.

这项研究涉及在机器学习、在线算法和优化领域之间建立新的联系，并利用这些联系来解决这三个领域的基本问题。在机器学习中，这项研究的一个重点是如何最好地将小样本的标记数据与大量的未标记数据结合起来，以产生高质量的预测。 鉴于现在网络上可用的数据爆炸式增长，此类问题变得尤为重要。 这项研究正在探索如何使用优化文献中的网络流和图切割等技术来提供新的攻击手段，以及如何最好地做出这种方法中出现的许多设计选择。 这项工作研究的另一个基本问题是，在存在高噪声数据的情况下可以自动学习什么类型的概念，以及在多大程度上可能出现新型算法。PI 最近给出了第一个在存在噪声的情况下学习一类概念的算法，而事实证明，这些概念是无法通过称为统计查询方法的广泛技术来学习的。 当前的研究旨在扩展这项工作，并探索其可以进一步推进的程度。 正在研究的学习问题类型与解码随机线性码和寻找密码学中出现的近似最短格向量的问题密切相关。 学习算法的改进也应该影响我们对这些问题的理解。这项研究的另一个主要目标是使用机器学习技术来解决在线算法中的问题。 特别是，机器学习中高度发达的“加权专家”技术提出了组合多种在线算法的新方法，可以简化许多长期悬而未决的问题。这项工作正在研究这种连接可以在多大程度上深入了解几个基本问​​题，例如搜索树的动态最优性和加权缓存问题。 最后，本研究还研究了一些基本的近似性问题，并探索了分析本地搜索技术的新框架。