Theoretical analysis of emerging machine learning paradigms

统计和计算机器学习领域取得了令人印象深刻的成功，为学习预测数据标签提供了严格的工具，基于训练样本。支持向量机（Support-Vector-Machines）、决策树（Decision-Trees）和助推（Boosting）等算法范例从理论模型发展成为流行且广泛适用的软件包。因此，机器学习为理论分析对实际应用发展的影响提供了一个响亮的证明。然而，机器学习的许多常见应用解决的场景比目前可用的数学理论建模的场景更复杂。举个例子，医学研究的目的是确定预测痴呆未来发展的生理标记。假设这项研究在丹麦进行。我们能轻易地将其结论应用到加拿大患者身上吗？当训练数据和测试数据来自同一总体时，常用的分类学习方法表现良好。然而，正如上面的示例所示，在许多应用程序中并非如此。在哪些条件下，以及如何，我们可以将在某个源域上训练的分类器应用于不同的目标域？为了应对这样的情况，学习实践者已经开发了启发式，虽然显然工作得相当好，但没有得到现有数学分析的支持。机器学习理论分析的成功可以推广到这样的场景吗？提出的研究旨在为这些新兴的机器学习和数据挖掘启发式范式提供数学支持，这些范式虽然被广泛应用，但缺乏严格的理论基础。在最近的一系列论文中，我和我的几个学生在这个方向上迈出了开创性的一步。此类工作的一些例子包括：关于聚类的流行模型选择启发式的论文（其中一篇获得了COLT最佳学生论文）；NIPS'06关于领域适应的论文；一篇关于半监督学习的COLT08论文，以及一篇关于聚类基础的NIPS’08论文。这些论文，以及我组织的相关研讨会，是一个雄心勃勃的项目的开始，我将用这笔资金继续研究。

The field of statistical and computational machine learning has had impressive successes, offering rigorous tools for learning to predict labels of data, based on training samples. Algorithmic paradigms like Support-Vector-Machines, Decision-Trees and Boosting grew from theoretical models into popular and vastly applicable software packages. Machine learning thus provides a resounding demonstration of the impact of theoretical analysis on the development of practical applications. However, many common applications of machine learning address scenarios that are more complex than what is modeled by the currently available mathematical theory. Consider, for example, medical research aimed to identify physiological markers that predict future development of dementia. Say the research took place in Denmark. Can one readily apply its conclusions to Canadian patients? Common learning methods for classification perform well when training and test data are drawn from the same population. However, as the above example demonstrates, in many application this is not the case. Under which conditions, and how, can we adapt a classifier trained on some source domain to apply to a different target domain? To cope with such scenarios, learning practitioners have developed heuristics that, while apparently working reasonably well, are not supported by existing mathematical analysis. Can the success of theoretical analysis of machine learning be extended to such scenarios? The proposed research aims to provide mathematical support for such emerging machine learning and data mining heuristic paradigms that, while being widely applied, lack rigorous theoretical underpinnings. In a series of recent papers, with several students of mine, we have made pioneering steps in that direction. Some examples of such work include: papers on popular model-selection heuristics for clustering (one of which awarded COLT Best Student Paper); a NIPS'06 paper on domain adaptation; a COLT08 paper on semi-supervised learning, and a NIPS'08 paper on the foundations of clustering. These papers, as well as related workshops that I have organized, are the start of an ambitious project that I will pursue with this grant.