CAREER: Making Exponential-Time Learning Algorithms Efficient

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

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.