本教程将概述最近机器学习对组合优化的影响,特别是在混合整数规划(MIP)框架下。涵盖的主题将包括用于预测可行解决方案的ML和强化学习,使用ML改进精确求解器,在精确MIP求解器中学习的软件框架,以及新兴的以决策为中心的学习范式。

https://sites.google.com/view/ml-co-aaai-21/

组合优化(CO)是计算机科学、人工智能(AI)和运筹学的基石。它在从机组人员规划到运动日程安排和的工业应用中取得了广泛的成功。虽然CO过去是大多数人工智能研究的基础,通过可满足性问题(SAT),现代人工智能研究已经转向更多的概率方法,并且这两个领域之间的联系已经减弱。然而,在过去的五到十年里,人们对使用机器学习方法改进组合优化的兴趣又强烈起来。

本教程旨在向观众介绍这一令人兴奋的不断发展的领域。我们相信,听众将从提出的教程中获益良多,因为它将布局这个研究空间的视角,不同的ML技术在CO设置中的优点,以及各种受益于ML使用的CO任务。我们还将引入一个新的开源库,Ecole,旨在方便该领域的新人访问。虽然本教程将主要关注作为CO的具体数学框架的混合整数规划,我们也将接触到MIP和其他约束推理框架之间的关系,如可满足性(SAT)和约束满足性(CSP),因为将提出的大多数思想都将适用于这些框架。

内容目录:

Part I by Elias B. Khalil:

  • 组合优化导论 Introduction to combinatorial optimization & Tutorial overview.
    • Modeling decision-making problems with Mixed Integer Programming (MIP);
    • Complexity and solution approaches (exact and heuristic);
    • Real-world applications;
    • Data-driven algorithm design.

Part 2 by Elias B. Khalil

  • 机器学习方法 The pure ML approach: predicting feasible solutions.
    • Reinforcement learning for combinatorial optimization;
    • Neural network architectures for representing graph problems;
    • Limitations: lack of guarantees, scalability challenges.

Part 3 by Didier Chételat & Maxime Gasse: [slides]

  • 混合方法 The hybrid approach: improving exact solvers with ML.
    • The branch-and-bound framework for mixed-integer linear programs (MIP);
    • Standard approaches to solver engineering;
    • Learning solver search policies: a Markov decision process (MDP) perspective;
    • Overview of tasks of interest;
    • Open challenges for ML/RL.

Part 4 by Giulia Zarpellon & Laurent Charlin

  • 机器学习MIP解决 Machine learning for MIP solving: challenges & literature.
    • Hands-on ML-for-MIP with a focus on the Branching problem;
    • Representations & Features;
    • Generalization notions;
    • Data & Metrics.

Part 5 by Antoine Prouvost

  • Ecole: A python framework for learning in exact MIP solvers.
    • A streamlined interface for doing ML in the open-source MIP solver SCIP, based on OpenAI Gym;
    • Example: "learning to branch'' using Ecole;
    • Easily extending predefined environments for your own research; Performance evaluation and analysis.

Part 6 by Bistra Dilkina 决策 Decision-focused Learning. Integrating LP/MIP combinatorial downstream tasks end-to-end in learning; Integrating graph optimization tasks end-to-end in learning.

Part 7 by Andrea Lodi: [slides]

  • Concluding remarks and new frontiers.
    • Business applications;
    • Recap of various contributions in this area;
    • Evaluation and Challenges going forward.
成为VIP会员查看完整内容
0
32

相关内容

The integration of deep learning to reinforcement learning (RL) has enabled RL to perform efficiently in high-dimensional environments. Deep RL methods have been applied to solve many complex real-world problems in recent years. However, development of a deep RL-based system is challenging because of various issues such as the selection of a suitable deep RL algorithm, its network configuration, training time, training methods, and so on. This paper proposes a comprehensive software framework that not only plays a vital role in designing a connect-the-dots deep RL architecture but also provides a guideline to develop a realistic RL application in a short time span. We have designed and developed a deep RL-based software framework that strictly ensures flexibility, robustness, and scalability. By inheriting the proposed architecture, software managers can foresee any challenges when designing a deep RL-based system. As a result, they can expedite the design process and actively control every stage of software development, which is especially critical in agile development environments. To enforce generalization, the proposed architecture does not depend on a specific RL algorithm, a network configuration, the number of agents, or the type of agents. Using our framework, software developers can develop and integrate new RL algorithms or new types of agents, and can flexibly change network configuration or the number of agents.

0
0
下载
预览

Generating diverse populations of high quality solutions has gained interest as a promising extension to the traditional optimization tasks. We contribute to this line of research by studying evolutionary diversity optimization for two of the most prominent permutation problems, namely the Traveling Salesperson Problem (TSP) and Quadratic Assignment Problem (QAP). We explore the worst-case performance of a simple mutation-only evolutionary algorithm with different mutation operators, using an established diversity measure. Theoretical results show most mutation operators for both problems ensure production of maximally diverse populations of sufficiently small size within cubic expected run-time. We perform experiments on QAPLIB instances in unconstrained and constrained settings, and reveal much more optimistic practical performances. Our results should serve as a baseline for future studies.

0
0
下载
预览

Prediction rule ensembles (PREs) are a relatively new statistical learning method, which aim to strike a balance between predictive accuracy and interpretability. Starting from a decision tree ensemble, like a boosted tree ensemble or a random forest, PREs retain a small subset of tree nodes in the final predictive model. These nodes can be written as simple rules of the form if [condition] then [prediction]. As a result, PREs are often much less complex than full decision tree ensembles, while they have been found to provide similar predictive accuracy in many situations. The current paper introduces the methodology and shows how PREs can be fitted using the R package pre through several real-data examples from psychological research. The examples also illustrate a number of features of package \textbf{pre} that may be particularly useful for applications in psychology: support for categorical, multivariate and count responses, application of (non-)negativity constraints, inclusion of confirmatory rules and standardized variable importance measures.

0
0
下载
预览

https://deepmind.com/learning-resources/-introduction-reinforcement-learning-david-silver

这个经典的10部分课程,由强化学习(RL)的驱David Silver教授,虽然录制于2015年,但仍然是任何想要学习RL基础的同学所必需的资源。

强化学习已经成为现代机器学习中一项强大的技术,它允许系统通过反复试验进行学习。它已成功应用于许多领域,包括AlphaZero等系统,学会了掌握国际象棋、围棋和Shogi游戏。

这门课程由DeepMind首席科学家、伦敦大学学院教授、AlphaZero的共同创始人David Silver教授共同向学生们介绍RL中使用的主要方法和技术。学生们还会发现萨顿和巴托的经典著作《强化学习:入门》(Reinforcement Learning: an Introduction)是一个很有帮助的书籍。

经典书《强化学习导论》

强化学习教父 Richard Sutton 的经典教材《Reinforcement Learning:An Introduction》第二版公布啦。本书分为三大部分,共十七章,机器之心对其简介和框架做了扼要介绍,并附上了全书目录、课程代码与资料。下载《强化学习》PDF 请点击文末「阅读原文」。

原书籍地址:hhttp://incompleteideas.net/book/the-book.html

当我们思考学习的本质时,首先映入脑海的想法很可能是通过与环境的交互进行学习。当一个婴儿玩耍时,挥舞手臂,左顾右盼,旁边没有老师指导他,他与环境却有着一种直接的感知连接。通过这种连接,他懂得了因果关系,行动带来的结果,以及为了达成目标所需做的一切。人的一生中,这样的交互成了我们关于环境和自身知识的主要来源。不管学习驾驶汽车,还是进行一场交谈,实际上我们自始至终观察着环境如何回应我们的所为,并通过自身行为影响当下情景。交互式学习几乎是所有学习与智能理论的基石。

本书中我们提出了一种通过计算实现交互式学习的方法。我们没有直接理论化人类或动物的学习方式,而是探索理想的学习环境,评估不同学习方法的有效性。即,我们站在人工智能研究者或工程师的角度来解决问题。我们探讨了在解决科学或经济问题方面表现突出的机器的设计,通过数学分析或计算实验评估其设计。我们提出的这一方法称之为强化学习。相较于其他机器学习方法,它更专注于交互之中的目标导向性学习。

成为VIP会员查看完整内容
0
30

题目: Moving Objects Detection with a Moving Camera: A Comprehensive Review

摘要:

在大约30年的时间里,许多研究团队致力于在各种挑战性环境中检测移动对象的大挑战。最初的应用涉及静态相机,但随着移动传感器的兴起,对移动相机的研究也逐渐出现。在这项调查中,我们建议识别和分类在文献中发现的不同的现有的方法。为此,我们建议根据场景表示的选择:一个平面或多个部分来对这些方法进行分类。在这两类方法中,根据8种不同的方法进行分组:全景背景减法、双摄像头、运动补偿、子空间分割、运动分割、平面+视差、多平面、分块图像分割。本文介绍了静态相机的方法以及静态相机和移动相机的挑战。本文还对公开数据集和评价指标进行了研究。

作者简介:

Marie-Neige Chapel,2017年9月在里昂第一大学获得计算机科学博士学位,博士论文题目是“运动物体检测与运动相机”。研究重点是在摄像机运动引起的视频流中,运动物体的真实运动与视运动的区别。并且提出了一种新的方法,使用几何线索来分类特征点为静态或移动。通过对物体的静态估计,通过对三维欧几里得距离随时间的比较,可以区分运动的物体和运动相机视频流中的静态物体。个人主页:https://mnchapel.github.io/

成为VIP会员查看完整内容
0
15

主题: Exploration-Exploitation in Reinforcement Learning

摘要: 强化学习(RL)研究的是当环境(即动力和反馈)最初未知,但可以通过直接交互学习时的顺序决策问题。学习问题的一个关键步骤是恰当地平衡对环境的探索,以便收集有用的信息,并利用所学的政策来收集尽可能多的回报。最近的理论结果证明,基于乐观主义或后验抽样的方法(如UCRL、PSRL等)成功地解决了勘探开发难题,并且可能需要比简单(但非常流行)的技术(如epsilon贪心)小指数的样本来收敛到接近最优的策略。乐观主义和后验抽样原则直接受到多臂bandit文献的启发,RL提出了具体的挑战(例如,“局部”不确定性如何通过Markov动力学传播),这需要更复杂的理论分析。本教程的重点是提供勘探开发困境的正式定义,讨论其挑战,并回顾不同优化标准(特别是有限时间和平均回报问题)的主要算法原则及其理论保证。在整个教程中,我们将讨论开放的问题和未来可能的研究方向。

邀请嘉宾: Ronan Fruit,Inria SequeL团队的博士生。他目前是蒙特利尔Facebook人工智能研究(FAIR)的研究实习生。他的研究集中在理论上理解强化学习中的探索性开发困境,以及设计具有可证明的良好后悔保证的算法。

Alessandro Lazaric,自2017年以来一直是Facebook AI Research(FAIR)实验室的研究科学家,他之前是SequeL团队Inria的研究员。他的主要研究主题是强化学习,在RL的理论和算法方面都做出了巨大贡献。在过去的十年中,他研究了多臂土匪和强化学习框架中的勘探与开发困境,特别是在遗憾最小化,最佳武器识别,纯粹探索和分层RL等问题上。

Matteo Pirotta,巴黎Facebook人工智能研究(FAIR)实验室的研究科学家。之前,他是SequeL团队的Inria博士后。2016年,他在米兰理工大学(意大利)获得计算机科学博士学位。他在强化学习方面的博士论文获得了Dimitris N.Chorafas基金会奖和EurAI杰出论文奖。他的主要研究兴趣是强化学习。近几年来,他主要关注的是RL的勘探开发困境。

成为VIP会员查看完整内容
0
16

Cloud Robotics is one of the emerging area of robotics. It has created a lot of attention due to its direct practical implications on Robotics. In Cloud Robotics, the concept of cloud computing is used to offload computational extensive jobs of the robots to the cloud. Apart from this, additional functionalities can also be offered on run to the robots on demand. Simultaneous Localization and Mapping (SLAM) is one of the computational intensive algorithm in robotics used by robots for navigation and map building in an unknown environment. Several Cloud based frameworks are proposed specifically to address the problem of SLAM, DAvinCi, Rapyuta and C2TAM are some of those framework. In this paper, we presented a detailed review of all these framework implementation for SLAM problem.

0
3
下载
预览
小贴士
相关VIP内容
专知会员服务
33+阅读 · 2020年11月17日
专知会员服务
97+阅读 · 2020年3月10日
专知会员服务
52+阅读 · 2019年8月30日
相关论文
Maura Pintor,Fabio Roli,Wieland Brendel,Battista Biggio
0+阅读 · 2月25日
Jinrong Yang,Shengkai Wu,Lijun Gou,Hangcheng Yu,Chenxi Lin,Jiazhuo Wang,Minxuan Li,Xiaoping Li
0+阅读 · 2月25日
RENT -- Repeated Elastic Net Technique for Feature Selection
Anna Jenul,Stefan Schrunner,Kristian Hovde Liland,Ulf Geir Indahl,Cecilia Marie Futsaether,Oliver Tomic
0+阅读 · 2月24日
Hai Zhu,Francisco Martinez Claramunt,Bruno Brito,Javier Alonso-Mora
0+阅读 · 2月23日
Ngoc Duy Nguyen,Thanh Thi Nguyen,Doug Creighton,Saeid Nahavandi
0+阅读 · 2月23日
Ngoc Duy Nguyen,Thanh Thi Nguyen,Hai Nguyen,Doug Creighton,Saeid Nahavandi
0+阅读 · 2月23日
Anh Viet Do,Mingyu Guo,Aneta Neumann,Frank Neumann
0+阅读 · 2月23日
Rajesh Doriya,Paresh Sao,Vinit Payal,Vibhav Anand,Pavan Chakraborty
3+阅读 · 2017年1月29日
Top