United States

We propose a novel distributed user-car matching method based on a contract between users to mitigate the imbalance problem between vehicle distribution and demand in free-floating car sharing. Previous regulation methods involved an incentive system based on the predictions of origin-destination (OD) demand obtained from past usage history. However, the difficulty these methods have in obtaining accurate data limits their applicability. To overcome this drawback, we introduce contract-based coordination among drop-off and pick-up users in which an auction is conducted for drop-off users&#39; intended drop-off locations. We theoretically analyze the proposed method regarding the upper bound of its efficiency. We also compare it with a baseline method and non-regulation scenario on a free-floating car-sharing simulator. The experimental results show that the proposed method achieves a higher social surplus than the existing method.

AAAI 2021

Contract-Based Inter-User Usage Coordination in Free-Floating Car Sharing

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

AAAI 2022

We propose a novel distributed user-car matching method based on a contract between users to mitigate the imbalance problem between vehicle distribution and demand in free-floating car sharing. Previous regulation methods involved an incentive system based on the predictions of origin-destination (OD) demand obtained from past usage history. However, the difficulty these methods have in obtaining accurate data limits their applicability. To overcome this drawback, we introduce contract-based coordination among drop-off and pick-up users in which an auction is conducted for drop-off users' intended drop-off locations. We theoretically analyze the proposed method regarding the upper bound of its efficiency. We also compare it with a baseline method and non-regulation scenario on a free-floating car-sharing simulator. The experimental results show that the proposed method achieves a higher social surplus than the existing method.

technical paper

Post-hoc explanation methods are gaining popularity for interpreting, understanding, and debugging neural networks. Most analyses using such methods explain decisions in response to inputs drawn from the test set. However, the test set may have few 
examples that trigger some model behaviors, such as high-confidence failures or ambiguous classifications. To address these challenges, we introduce a flexible model inspection framework: Bayes-TrEx. Given a data distribution, Bayes-TrEx finds in-distribution examples which trigger a specified prediction confidence. We demonstrate several use cases of Bayes-TrEx, including revealing highly confident (mis)classifications, visualizing class boundaries via ambiguous examples, understanding novel-class extrapolation behavior, and exposing neural network overconfidence. We use Bayes-TrEx to study classifiers trained on CLEVR, MNIST, and Fashion-MNIST, and we show that this framework enables more flexible holistic model analysis than just inspecting the test set. Code and supplemental material are available at https://github.com/serenabooth/Bayes-TrEx.

Bayes-TrEx: a Bayesian Sampling Approach to Model Transparency by Example

Many widely-used causal discovery methods such as Greedy Equivalent Search (GES), although with asymptotic correctness guarantees, have been reported to produce sub-optimal solutions on finite data, or when the causal faithfulness condition is violated. The constraint-based procedure with Boolean satisfiability (SAT) solver, and the recently proposed Sparsest Permutation (SP) algorithm have shown superb performance, but currently they do not scale well. In this work, we demonstrate that optimal score-based exhaustive search is remarkably useful for causal discovery: it requires weaker conditions to guarantee asymptotic correctness, and outperforms well-known methods including PC, GES, GSP, and NOTEARS. In order to achieve scalability, we also develop an approximation algorithm for larger systems based on the  A* method, which scales up to 60+ variables and obtains better results than existing greedy algorithms such as GES, MMHC, and GSP. Our results illustrate the risk of assuming the faithfulness assumption, the advantages of exhaustive search methods, and the limitations of greedy search methods, and shed light on the computational challenges and techniques in scaling up to larger networks and handling unfaithful data.

Improving Causal Discovery by Optimal Bayesian Network Learning

Recent works within machine learning have been tackling inputs of ever increasing size, with cyber security presenting sequence classification problems of particularly extreme lengths. In the case of Windows executable malware detection, an input executable could be >=100 MB, which would translate to a time series with T=100,000,000 steps. To date, the closest approach to handling such task is MalConv --- a convolutional neural network capable of processing T=2,000,000 steps. Because the memory used by CNNs is O(T), this has prevented many from processing all executables or further extending the MalConv approach. In this work, we develop a new approach to temporal max pooling that makes the required memory invariant to the sequence length T. This makes MalConv 116x more memory efficient, and up to 25.8x faster to train, while removing the input length restrictions to MalConv. We re-invest these gains into improving the MalConv architecture by developing a new Global Channel Gating design, giving us an attention mechanism capable of learning feature interactions across 100 million time steps in an efficient manner, a capability lacked by the original MalConv approach.

Classifying Sequences of Extreme Length with Constant Memory Applied to Malware Detection

Community detection is a research hotspot in machine learning and data mining. However, most of the existing community detection methods only rely on the lower-order connectivity patterns, while ignoring the higher-order connectivity patterns, and unable to capture the building blocks of the complex network. In recent years, some community detection methods based on higher-order structures have been developed, but they mainly focus on the motif network composed of higher-order structures, which violate the original lower-order topological structure and are affected by the fragmentation issue, resulting in the deviation of community detection results. Therefore, there is still a lack of community detection methods that can effectively utilize higher-order connectivity patterns and lower-order connectivity patterns. To overcome the above limitations, this paper proposes the Hybrid-order Stochastic Block Model (HSBM) from the perspective of the generative model. Based on the classical stochastic block model, the generation of lower-order structure and higher-order structure of the network is modeled uniformly, and the original topological properties of the network are maintained while using higher-order connectivity patterns. At the same time, a heuristic algorithm for community detection is proposed to optimize the objective function. Extensive experiments on six real-world datasets show that the proposed method outperforms the existing approaches.

Hybrid-Order Stochastic Block Model

Electrical Muscle Stimulation (EMS) has become a popular interaction technology in Human-Computer Interaction; allowing the computer to take direct control of the user's body. To date, however, the explorations have been limited to coarse, toy examples, due to the low resolution of achievable control. To increase this resolution, the EMS needs to increase significantly in complexity - using large numbers of electrodes in complex patterns. The calibration of such a system remains an unsolved challenge. We present a new SAT-based black-box calibration method, which requires no spatial information about muscular or electrode positioning. The method encodes domain knowledge and observations in a constraint model, and uses these to prune the space of feasible control signals.
In a simulated environment we find this method can scale reliably to large arrays while requiring only a modest number of trials, and preliminary tests on real hardware show we can effectively calibrate an electrode array in a few minutes.

Optimising Automatic Calibration of Electric Muscle Stimulation

We present a mean-variance policy iteration (MVPI) framework for risk-averse control in a discounted infinite horizon MDP optimizing the variance of a per-step reward random variable.
MVPI enjoys great flexibility in that
any policy evaluation method and risk-neutral control method can be dropped in for risk-averse control off the shelf,
in both on- and off-policy settings.
This flexibility reduces the gap between risk-neutral control and risk-averse control and is achieved by working on a novel augmented MDP directly.
We propose risk-averse TD3 as an example instantiating MVPI,
which outperforms vanilla TD3 and many previous risk-averse control methods in challenging Mujoco robot simulation tasks under a risk-aware performance metric.
This risk-averse TD3 is the first to introduce deterministic policies and off-policy learning into risk-averse reinforcement learning,
both of which are key to the performance boost we show in Mujoco domains.

Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learning

As an extension to the matroid span problem, we propose the submodular span problem that involves finding a large set of elements with small gain relative to a given query set. We then propose a two-stage Submodular Span Summarization (S3) framework to achieve a form of conditional or query-focused data summarization. The first stage encourages the summary to be relevant to a given query set, and the second stage encourages the final summary to be diverse, thus achieving two important necessities for a good query-focused summary. Unlike previous methods, our framework uses only a single submodular function defined over both data and query. We analyze theoretical properties in the context of both matroids and polymatroids that elucidate when our methods should work well. We find that a scalable approximation algorithm to the polymatroid submodular span problem has good theoretical and empirical properties. We provide empirical and qualitative results on three real-world tasks: conditional multi-document summarization on the DUC 2005-2007 datasets, conditional video summarization on the UT-Egocentric dataset, and conditional image corpus summarization on the ImageNet dataset. We use deep neural networks, specifically a BERT model for text, AlexNet for video frames, and Bi-directional Generative Adversarial Networks (BiGAN) for ImageNet images to help instantiate the submodular functions. The result is a minimally supervised form of conditional summarization that matches or improves over the previous state-of-the-art.

Submodular Span, with Applications to Conditional Data Summarization

Algorithms for noiseless collaborative PAC learning have been analyzed and optimized in recent years with respect to sample complexity. In this paper, we study collaborative PAC learning with the goal of reducing communication cost at essentially no penalty to the sample complexity. We develop communication efficient collaborative PAC learning algorithms using distributed boosting. We then consider the communication cost of collaborative learning in the presence of classification noise. As an intermediate step, we show how collaborative PAC learning algorithms can be adapted to handle classification noise. With this insight, we develop communication efficient algorithms for collaborative PAC learning robust to classification noise.

Communication-Aware Collaborative Learning

Current work in explainable reinforcement learning generally produces policies in the form of a decision tree over the state space. Such policies can be used for formal safety verification, agent behavior prediction, and manual inspection of important features. However, existing approaches fit a decision tree after training or use a custom learning procedure which is not compatible with new learning techniques, such as those which use neural networks. To address this limitation, we propose a novel Markov Decision Process (MDP) type for learning decision tree policies: Iterative Bounding MDPs (IBMDPs). An IBMDP is constructed around a base MDP so each IBMDP policy is guaranteed to correspond to a decision tree policy for the base MDP when using a method-agnostic masking procedure. Because of this decision tree equivalence, any function approximator can be used during training, including a neural network, while yielding a decision tree policy for the base MDP. We present the required masking procedure as well as a modified value update step which allows IBMDPs to be solved using existing algorithms. We apply this procedure to produce IBMDP variants of recent reinforcement learning methods. We empirically show the benefits of our approach by solving IBMDPs to produce decision tree policies for the base MDPs.

Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methods

This paper studies the adversarial graphical contextual bandits, a variant of adversarial multi-armed bandits that leverage two categories of the most common side information: contexts and side observations. In this setting, a learning agent repeatedly chooses from a set of K actions after being presented with a d-dimensional context vector. The agent not only incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures, which are encoded as a series of feedback graphs. This setting models a variety of applications in social networks, where both contexts and graph-structured side observations are available. Two efficient algorithms are developed based on EXP3. Under mild conditions, our analysis shows that for undirected feedback graphs the first algorithm, EXP3-LGC-U, achieves a sub-linear regret with respect to the time horizon and the average independence number of the feedback graphs. A slightly weaker result is presented for the directed graph setting as well. The second algorithm, EXP3-LGC-IX, is developed for a special class of problems, for which the regret is the same for both directed as well as undirected feedback graphs. Numerical tests corroborate the efficiency of proposed algorithms.

Downloads

Next from AAAI 2021

Bayes-TrEx: a Bayesian Sampling Approach to Model Transparency by Example

Similar lecture

Domain Reconstruction for UWB Car Key Localization Using Generative Adversarial Networks

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAAI 2021

Bayes-TrEx: a Bayesian Sampling Approach to Model Transparency by Example

Similar lecture

Domain Reconstruction for UWB Car Key Localization Using Generative Adversarial Networks

Downloads