Deriving and Analyzing Learning Algorithms

推导和分析学习算法

• 批准号: 9821087
• 负责人: Manfred Warmuth
• 金额: $ 30.02万
• 依托单位: University of California-Santa Cruz
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9821087&HistoricalAwards=false
• 关键词: Deriving; Analyzing; Learning; Algorithms

It can be difficult to tell which learning algorithm is best for a particular situation. The bias of many on-line learning algorithms can be encoded with a "distance function" on the hypothesis space, and (for simple problems) an amortized analysis can be used to provide relative performance guarantees (analogous to the competitive ratios for k-server problems). These guarantees can be used to indicate when one bias is more appropriate than another, allowing an intelligent choice of learning algorithm.This project explores the connection between the distance functions over hypotheses and the Bregman divergences used in convex optimization. By adapting the tools developed for Bregman divergences, the investigators will improve and generalize the performance guarantees. This will result in more accurate predictions of how well the various learning algorithms will perform on a wider variety of problems. Furthermore, the improved understanding will enable the derivation of new learning algorithms tailored to specific situations.

很难说出哪种学习算法最适合特定情况。 许多在线学习算法的偏差可以在假设空间上使用“距离函数”编码，并且（对于简单的问题）可以使用摊销分析来提供相对性能保证（类似于K-Server的竞争比率问题）。 这些保证可以用来指出一个偏差何时比另一个偏差更合适，从而允许学习算法的智能选择。该项目探讨了假设的距离函数与凸优化中使用的Bregman差异之间的连接。 通过调整为Bregman Diverence开发的工具，研究人员将改善和推广性能保证。 这将导致更准确地预测各种学习算法在更广泛的问题上的表现。 此外，改进的理解将使针对特定情况量身定制的新学习算法的推导。