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.