CAREER: Making Exponential-Time Learning Algorithms Efficient

职业：使指数时间学习算法变得高效

• 批准号: 0092761
• 负责人: Stephen Scott
• 金额: $ 30万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-01 至 2006-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0092761&HistoricalAwards=false
• 关键词: CAREER; Making; Exponential; Time; Learning

In the past fifteen years, researchers have developed new algorithmsfor machine learning (computer programs that learn from experience)that have excellent theoretical guarantees on their error. Theseso-called multiplicative weight update algorithms receive inputs (likean image taken by a robot), and make a prediction as to whether or notthat image came from a particular location. The theoretical errorbounds imply that the number of mistakes made by these algorithms isguaranteed to be very small. However, many applications of thesealgorithms require an enormous amount of time to learn and predict.Thus special techniques must be employed to make them efficient. Theinvestigators study new, general, theoretical techniques to make thesealgorithms faster. This research also involves empirically evaluatingsuch algorithms in new areas, including computational biology, which isstudied extensively at the investigators' university. Applyingtheoretical techniques to real problems creates a better understandingof the real-world problems and helps direct future theoretical work,guiding the transfer of results from theory to practice.Specifically, the investigators study multiplicative weight-updatealgorithms such as Weighted Majority (WM) and Winnow, which haveon-line mistake bounds with a logarithmic dependence on N, the totalnumber of features. This attribute efficiency allows them to beapplied to problems where N is exponential in the input size, yieldinggreat flexibility in their application areas. Such areas includepruning decision trees, pruning ensembles of classifiers, learningfinite geometric concepts, learning DNF formulas, and usingpseudo-Bayesian predictors over finite hypothesis spaces. However, alarge N requires techniques to efficiently compute the weighted sums ofthese algorithms. This research explores methods to overcome thisdifficulty, including exploiting commonalities among the features, andthe more general approach of using Markov chain Monte Carlo (MCMC)methods to estimate the total weight contribution without the need forspecial structure in the problem. The investigators also are applyingtheir algorithms to various problems in computational biology,including drug activity prediction, analyzing microbial populationdynamics, and identifying special types of human genes.

在过去的15年里，研究人员已经开发出了新的机器学习算法（从经验中学习的计算机程序），这些算法对它们的错误有很好的理论保证。 这些所谓的乘法权重更新算法接收输入（比如机器人拍摄的图像），并预测该图像是否来自特定位置。 理论上的误差界意味着这些算法所犯的错误数量保证是非常小的。 然而，这些算法的许多应用需要大量的时间来学习和预测，因此必须采用特殊的技术来提高它们的效率。 研究人员研究新的、通用的、理论上的技术来使这些算法更快。 这项研究还涉及在新的领域，包括计算生物学，这是在调查人员的大学广泛研究经验评估这样的算法。 将理论技术应用于真实的问题，可以更好地理解现实世界的问题，并有助于指导未来的理论工作，指导结果从理论到实践的转移。具体来说，研究人员研究了乘法权重更新算法，如加权多数（WM）和Winnow，它们具有对N（特征总数）对数依赖的在线错误界。 这种属性效率允许他们被应用于问题，N是指数的输入大小，yieldinggreat灵活性，在其应用领域。 这些领域包括修剪决策树、修剪分类器集合、学习有限几何概念、学习DNF公式以及在有限假设空间上使用伪贝叶斯预测器。 然而，大的N需要技术来有效地计算这些算法的加权和。 本研究探讨了克服这一困难的方法，包括利用特征之间的共性，以及使用马尔可夫链蒙特卡罗（MCMC）方法来估计总权重贡献而不需要特殊结构的问题。 研究人员还将他们的算法应用于计算生物学中的各种问题，包括药物活性预测，分析微生物种群动态，以及识别特殊类型的人类基因。