CAREER: Combinatorial Online Learning and its Applications

机器学习中的几个重要问题，如图模型中的最大后验（MAP）推理，本质上是组合的。虽然广泛的研究已经致力于设计近似算法，这样的问题，现有的算法不能很好地扩展到大的问题。这个项目的重点是利用在线学习的想法与专家的意见，开发一个新的家庭的在线学习算法的组合优化问题。组合在线学习的算法是有效的和简单的分析，以建立保证。与现有的文献中的组合问题的近似算法依赖于适当的真实的松弛的原始问题，组合在线学习算法从来没有使用松弛，他们直接与二进制/整数的解决方案，并具有全局近似保证。 该项目研究了该框架的泛化，以解决在线和批处理二进制二次规划问题，产生各种组合问题的近似算法，包括NP完全问题，以及有向和无向图形模型中的MAP推理。该项目考虑了三个重要的真实的生活应用：有效投资于股票市场的投资组合选择，通过加快组织图像中的疾病检测来自动化手术病理学，以及从时空气候数据中发现突然气候变化的气候变化检测。该项目预计将具有变革性，特别是在外科病理学和气候变化检测方面，将产生重大的长期社会效益。研究成果将通过研究论文、教程、开源软件和利用模拟股票市场游戏开展的外联活动向社区传播。

Several important problems in machine learning, such as maximumaposteriori (MAP) inference in graphical models, are inherently combinatorial. While extensive research has been devoted to designing approximation algorithms for such problems, existing algorithms do not scale well to large problems. This project focuses on leveraging ideas from online learning with expert advice to develop a novel family of online learning algorithms for combinatorial optimization problems. Algorithms for combinatorial online learning are efficient and simple to analyze in order to establish guarantees. Unlike existing literature on approximation algorithms for combinatorial problems which rely on suitable real relaxations of the original problem, combinatorial online learning algorithms never use relaxations; they work directly with binary/integer solutions and have global approximation guarantees. The project investigates generalizations of the framework to solve online and batch binary quadratic programming problems, yielding approximation algorithms for a variety of combinatorial problems, including NP-complete problems, and MAP inference in directed and undirected graphical models. The project considers three important real life applications: portfolio selection for effectively investing in the stock market, automating surgical pathology by expediting disease detection in tissue images, and climate change detection for discovering abrupt climate changes from spatiotemporal climate data. The project is expected to be transformative, especially in the context of surgical pathology and climate change detection, yielding significant long term societal benefits. The research results will be disseminated to the community through research papers, tutorials, open source software, and outreach activities using games based on mock stock markets.