本教程將概述最近機器學習對組合優化的影響,特別是在混合整數規劃(MIP)框架下。涵蓋的主題將包括用于預測可行解決方案的ML和強化學習,使用ML改進精確求解器,在精確MIP求解器中學習的軟件框架,以及新興的以決策為中心的學習范式。
//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:
Part 2 by Elias B. Khalil
Part 3 by Didier Chételat & Maxime Gasse: [slides]
Part 4 by Giulia Zarpellon & Laurent Charlin
Part 5 by Antoine Prouvost
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]
Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for each natural number $k$, we seek a vertex ordering such every vertex can (weakly respectively strongly) reach in $k$ steps only few vertices with lower index in the ordering. Both notions capture the sparsity of a graph or a graph class, and have interesting applications in the structural and algorithmic graph theory. Recently, the first author together with McCarty and Norin observed a natural volume-based upper bound for the strong coloring numbers of intersection graphs of well-behaved objects in $\mathbb{R}^d$, such as homothets of a centrally symmetric compact convex object, or comparable axis-aligned boxes. In this paper, we prove upper and lower bounds for the $k$-th weak coloring numbers of these classes of intersection graphs. As a consequence, we describe a natural graph class whose strong coloring numbers are polynomial in $k$, but the weak coloring numbers are exponential. We also observe a surprising difference in terms of the dependence of the weak coloring numbers on the dimension between touching graphs of balls (single-exponential) and hypercubes (double-exponential).
Histogram-based template fits are the main technique used for estimating parameters of high energy physics Monte Carlo generators. Parametrized neural network reweighting can be used to extend this fitting procedure to many dimensions and does not require binning. If the fit is to be performed using reconstructed data, then expensive detector simulations must be used for training the neural networks. We introduce a new two-level fitting approach that only requires one dataset with detector simulation and then a set of additional generation-level datasets without detector effects included. This Simulation-level fit based on Reweighting Generator-level events with Neural networks (SRGN) is demonstrated using simulated datasets for a variety of examples including a simple Gaussian random variable, parton shower tuning, and the top quark mass extraction.
Light fidelity (LiFi), which is based on visible light communications (VLC), is celebrated as a cutting-edge technological paradigm that is envisioned to be an indispensable part of 6G systems. Nonetheless, LiFi performance is subject to efficiently overcoming the line-of-sight blockage, whose adverse effect on wireless reception reliability becomes even more pronounced in highly dynamic environments, such as vehicular application scenarios. Meanwhile, intelligent reflecting surfaces (IRS) emerged recently as a revolutionary concept that transfers the physical propagation environment into a fully controllable and customisable space in a low-cost low-power fashion. We anticipate that the integration of IRS in LiFi-enabled networks will not only support blockage mitigation but will also provision complex interactions among network entities, and is hence manifested as a promising platform that enables a plethora of technological trends and new applications. In this article, for the first time in the open literature, we set the scene for a holistic overview of IRS-assisted LiFi systems. Specifically, we explore the underlying IRS architecture from the perspective of physics and present a forward-looking vision that outlines potential operational elements supported by IRS-enabled transceivers and IRS-enabled environments. Finally, we highlight major associated challenges and offer a look ahead toward promising future directions.
The number of connected Internet of Things (IoT) devices within cyber-physical infrastructure systems grows at an increasing rate. This poses significant device management and security challenges to current IoT networks. Among several approaches to cope with these challenges, data-based methods rooted in deep learning (DL) are receiving an increased interest. In this paper, motivated by the upcoming surge of 5G IoT connectivity in industrial environments, we propose to integrate a DL-based anomaly detection (AD) as a service into the 3GPP mobile cellular IoT architecture. The proposed architecture embeds autoencoder based anomaly detection modules both at the IoT devices (ADM-EDGE) and in the mobile core network (ADM-FOG), thereby balancing between the system responsiveness and accuracy. We design, integrate, demonstrate and evaluate a testbed that implements the above service in a real-world deployment integrated within the 3GPP Narrow-Band IoT (NB-IoT) mobile operator network.
Authorization or access control limits the actions a user may perform on a computer system, based on predetermined access control policies, thus preventing access by illegitimate actors. Access control for the Internet of Things (IoT) should be tailored to take inherent IoT network scale and device resource constraints into consideration. However, common authorization systems in IoT employ conventional schemes, which suffer from overheads and centralization. Recent research trends suggest that blockchain has the potential to tackle the issues of access control in IoT. However, proposed solutions overlook the importance of building dynamic and flexible access control mechanisms. In this paper, we design a decentralized attribute-based access control mechanism with an auxiliary Trust and Reputation System (TRS) for IoT authorization. Our system progressively quantifies the trust and reputation scores of each node in the network and incorporates the scores into the access control mechanism to achieve dynamic and flexible access control. We design our system to run on a public blockchain, but we separate the storage of sensitive information, such as user's attributes, to private sidechains for privacy preservation. We implement our solution in a public Rinkeby Ethereum test-network interconnected with a lab-scale testbed. Our evaluations consider various performance metrics to highlight the applicability of our solution for IoT contexts.
Path-based relational reasoning over knowledge graphs has become increasingly popular due to a variety of downstream applications such as question answering in dialogue systems, fact prediction, and recommender systems. In recent years, reinforcement learning (RL) has provided solutions that are more interpretable and explainable than other deep learning models. However, these solutions still face several challenges, including large action space for the RL agent and accurate representation of entity neighborhood structure. We address these problems by introducing a type-enhanced RL agent that uses the local neighborhood information for efficient path-based reasoning over knowledge graphs. Our solution uses graph neural network (GNN) for encoding the neighborhood information and utilizes entity types to prune the action space. Experiments on real-world dataset show that our method outperforms state-of-the-art RL methods and discovers more novel paths during the training procedure.
教程題目:Knowledge-based Sequential Decision-Making under Uncertainty
教程簡介:
在本教程中,重點討論用于推理和學習的聲明性表示和概率表示的交集。在概率順序決策(SDM)和知識表示與推理(KRR)的聲明性方法中都有重要的前期工作。并且強調這些方法的互補功能,結合這些功能的現有研究,并確定在不同應用領域設計和使用此類集成系統時存在的一些開放問題。然后重點討論面向目標的SDM和聲明性KRR之間的相互作用,并演示這種相互作用如何為解決各個研究領域的開放問題提供新的機會。利用自己在開發架構方面的專業知識,利用這些互補的功能,使機器人能夠相互交互并與人類協作。目標是鼓勵更多的研究人員在不同的應用領域探索概率SDM和聲明式KRR方法的集成。因此,本教程將使這些領域和應用領域(如機器人、計算機視覺和自然語言處理)的研究人員感興趣。
組織者:
張世琦,紐約州立大學賓厄姆頓分校計算機科學系助理教授。2014-2016年,他是德克薩斯大學奧斯汀分校的博士后研究員,2013年,他獲得了德克薩斯理工大學的計算機科學博士學位。
Mohan Sridharan是英國伯明翰大學計算機科學學院的高級講師。他在美國德克薩斯大學奧斯汀分校獲得博士學位。他的研究興趣包括知識表示和推理、機器學習、計算視覺和認知系統,并將其應用于人機協作。
In many real-world network datasets such as co-authorship, co-citation, email communication, etc., relationships are complex and go beyond pairwise. Hypergraphs provide a flexible and natural modeling tool to model such complex relationships. The obvious existence of such complex relationships in many real-world networks naturaly motivates the problem of learning with hypergraphs. A popular learning paradigm is hypergraph-based semi-supervised learning (SSL) where the goal is to assign labels to initially unlabeled vertices in a hypergraph. Motivated by the fact that a graph convolutional network (GCN) has been effective for graph-based SSL, we propose HyperGCN, a novel GCN for SSL on attributed hypergraphs. Additionally, we show how HyperGCN can be used as a learning-based approach for combinatorial optimisation on NP-hard hypergraph problems. We demonstrate HyperGCN's effectiveness through detailed experimentation on real-world hypergraphs.
Keypoint-based methods are a relatively new paradigm in object detection, eliminating the need for anchor boxes and offering a simplified detection framework. Keypoint-based CornerNet achieves state of the art accuracy among single-stage detectors. However, this accuracy comes at high processing cost. In this work, we tackle the problem of efficient keypoint-based object detection and introduce CornerNet-Lite. CornerNet-Lite is a combination of two efficient variants of CornerNet: CornerNet-Saccade, which uses an attention mechanism to eliminate the need for exhaustively processing all pixels of the image, and CornerNet-Squeeze, which introduces a new compact backbone architecture. Together these two variants address the two critical use cases in efficient object detection: improving efficiency without sacrificing accuracy, and improving accuracy at real-time efficiency. CornerNet-Saccade is suitable for offline processing, improving the efficiency of CornerNet by 6.0x and the AP by 1.0% on COCO. CornerNet-Squeeze is suitable for real-time detection, improving both the efficiency and accuracy of the popular real-time detector YOLOv3 (34.4% AP at 34ms for CornerNet-Squeeze compared to 33.0% AP at 39ms for YOLOv3 on COCO). Together these contributions for the first time reveal the potential of keypoint-based detection to be useful for applications requiring processing efficiency.
We present a new clustering method in the form of a single clustering equation that is able to directly discover groupings in the data. The main proposition is that the first neighbor of each sample is all one needs to discover large chains and finding the groups in the data. In contrast to most existing clustering algorithms our method does not require any hyper-parameters, distance thresholds and/or the need to specify the number of clusters. The proposed algorithm belongs to the family of hierarchical agglomerative methods. The technique has a very low computational overhead, is easily scalable and applicable to large practical problems. Evaluation on well known datasets from different domains ranging between 1077 and 8.1 million samples shows substantial performance gains when compared to the existing clustering techniques.