OpenRaiser/Intern-Atlas huggingface dataset:
Probability Distributions on Partially Ordered Sets and Network Interdiction Games
Venue: arXiv cs.GT 2020
Year: 2020

This article poses the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset's elements and maximal chains is satisfied? We present a combinatorial algorithm to positively resolve this question. The algorithm can be implemented in polynomial time in the special case where maximal chain probabilities are affine functions of their elements. This existence problem is relevant for the equilibrium characterization of a generic strategic interdiction game on a capacitated flow network. The game involves a routing entity that sends its flow through the network while facing path transportation costs, and an interdictor who simultaneously interdicts one or more edges while facing edge interdiction costs. Using our existence result on posets and strict complementary slackness in linear programming, we show that the Nash equilibria of this game can be fully described using primal and dual solutions of a minimum-cost circulation problem. Our analysis provides a new characterization of the critical components in the interdiction game. It also leads to a polynomial-time approach for equilibrium computation.
Mobility-Aware Electric Vehicle Fast Charging Load Models with Geographical Price Variations
Venue: arXiv cs.SY 2020
Year: 2020

We study the traffic patterns as well as the charging patterns of a population of cost-minimizing EV owners traveling and charging within a transportation network equipped with fast charging stations (FCSs). Specifically, we study how the charging network operator (CNO) can influence where EV users charge in order to optimize the utilization of fast charging stations. These charging decisions of private EV owners affect aggregate congestion at stations (i.e., waiting time) as well as the aggregate EV charging load across the network. In this work, we capture the resulting equilibrium wait times and electricity load through a so-called \textit{traffic and charge assignment problem} (TCAP) in a fast charging station network. Our formulation allows us to: 1) Study the expected station wait times as well as the probability distribution of aggregate charging load of EVs in a FCS network in a mobility-aware fashion (an aspect unique to our work), while accounting for heterogeneities in users' travel patterns, energy demands, and geographically variant electricity prices. 2) Analytically characterize the special threshold-based structure that determines how EV owners choose where to charge their vehicle at equilibrium, in response to the FCS's charging price structure, users' energy demands, and users' mobility patterns. 3) Provide a convex optimization problem formulation to identify the network's unique equilibrium. Furthermore, we illustrate how to induce a socially optimal charging behavior by deriving the socially optimal plug-in fees and electricity prices at the charging stations.
Bandits with Temporal Stochastic Constraints
Venue: arXiv cs.LG 2020
Year: 2020

We study the effect of impairment on stochastic multi-armed bandits and develop new ways to mitigate it. Impairment effect is the phenomena where an agent only accrues reward for an action if they have played it at least a few times in the recent past. It is practically motivated by repetition and recency effects in domains such as advertising (here consumer behavior may require repeat actions by advertisers) and vocational training (here actions are complex skills that can only be mastered with repetition to get a payoff). Impairment can be naturally modelled as a temporal constraint on the strategy space, and we provide two novel algorithms that achieve sublinear regret, each working with different assumptions on the impairment effect. We introduce a new notion called bucketing in our algorithm design, and show how it can effectively address impairment as well as a broader class of temporal constraints. Our regret bounds explicitly capture the cost of impairment and show that it scales (sub-)linearly with the degree of impairment. Our work complements recent work on modeling delays and corruptions, and we provide experimental evidence supporting our claims.
Tight Approximation for Unconstrained XOS Maximization
Venue: arXiv cs.DS 2020
Year: 2020

A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width $1$ because they are just additive, but it is already nontrivial even when the width is restricted to $2$. We show two types of tight bounds on the polynomial-time approximability for this problem. First, in general, the approximation bound is between $O(n)$ and $Ω(n / \log n)$, and exactly $Θ(n / \log n)$ if randomization is allowed, where $n$ is the ground set size. Second, when the width of the input XOS functions is bounded by a constant $k \geq 2$, the approximation bound is between $k - 1$ and $k - 1 - ε$ for any $ε> 0$. In particular, we give a linear-time algorithm to find an exact maximizer of a given XOS function of width $2$, while we show that any exact algorithm requires an exponential number of value oracle calls even when the width is restricted to $3$.
Multiple Partitioning of Multiplex Signed Networks: Application to European Parliament Votes
Venue: arXiv cs.SI 2020
Year: 2020

For more than a decade, graphs have been used to model the voting behavior taking place in parliaments. However, the methods described in the literature suffer from several limitations. The two main ones are that 1) they rely on some temporal integration of the raw data, which causes some information loss, and/or 2) they identify groups of antagonistic voters, but not the context associated to their occurrence. In this article, we propose a novel method taking advantage of multiplex signed graphs to solve both these issues. It consists in first partitioning separately each layer, before grouping these partitions by similarity. We show the interest of our approach by applying it to a European Parliament dataset.
Signal strength based scheme for following mobile IoT devices in dynamic environments
Venue: arXiv cs.NI 2020
Year: 2020

The increased maturity level of technological achievements towards the realization of the Internet of Things (IoT) vision allowed sophisticated solutions to emerge, offering reliable monitoring in highly dynamic environments that lack well-defined and well-designed infrastructures. In this paper, we use a bio-inspired IoT architecture, which allows flexible creation and discovery of sensor-based services offering self-organization and self-optimization properties to the dynamic network, in order to make the required monitoring information available. The main contribution of the paper is the introduction of a new algorithm for following mobile monitored targets/individuals in the context of an IoT system, especially a dynamic one as the aforementioned. The devised technique, called Hot-Cold, is able to ensure proximity maintenance by the tracking robotic device solely based on the strength of the RF signal broadcasted by the target to communicate its sensors' data. Complete geometrical, numerical, simulation, and convergence analyses of the proposed technique are thoroughly presented, along with a detailed simulation-based evaluation that reveals the higher following accuracy of Hot-Cold compared to the popular concept of trilateration-based tracking. Finally, a prototype of the full architecture was implemented not only to demonstrate the applicability of the presented approach for monitoring in dynamic environments, but also the operability of the introduced tracking technique.
Similarity-preserving Image-image Domain Adaptation for Person Re-identification
Venue: arXiv cs.CV 2020
Year: 2020

This article studies the domain adaptation problem in person re-identification (re-ID) under a "learning via translation" framework, consisting of two components, 1) translating the labeled images from the source to the target domain in an unsupervised manner, 2) learning a re-ID model using the translated images. The objective is to preserve the underlying human identity information after image translation, so that translated images with labels are effective for feature learning on the target domain. To this end, we propose a similarity preserving generative adversarial network (SPGAN) and its end-to-end trainable version, eSPGAN. Both aiming at similarity preserving, SPGAN enforces this property by heuristic constraints, while eSPGAN does so by optimally facilitating the re-ID model learning. More specifically, SPGAN separately undertakes the two components in the "learning via translation" framework. It first preserves two types of unsupervised similarity, namely, self-similarity of an image before and after translation, and domain-dissimilarity of a translated source image and a target image. It then learns a re-ID model using existing networks. In comparison, eSPGAN seamlessly integrates image translation and re-ID model learning. During the end-to-end training of eSPGAN, re-ID learning guides image translation to preserve the underlying identity information of an image. Meanwhile, image translation improves re-ID learning by providing identity-preserving training samples of the target domain style. In the experiment, we show that identities of the fake images generated by SPGAN and eSPGAN are well preserved. Based on this, we report the new state-of-the-art domain adaptation results on two large-scale person re-ID datasets.
A Multidisciplinary Survey and Framework for Design and Evaluation of Explainable AI Systems
Venue: arXiv cs.HC 2020
Year: 2020

The need for interpretable and accountable intelligent systems grows along with the prevalence of artificial intelligence applications used in everyday life. Explainable intelligent systems are designed to self-explain the reasoning behind system decisions and predictions, and researchers from different disciplines work together to define, design, and evaluate interpretable systems. However, scholars from different disciplines focus on different objectives and fairly independent topics of interpretable machine learning research, which poses challenges for identifying appropriate design and evaluation methodology and consolidating knowledge across efforts. To this end, this paper presents a survey and framework intended to share knowledge and experiences of XAI design and evaluation methods across multiple disciplines. Aiming to support diverse design goals and evaluation methods in XAI research, after a thorough review of XAI related papers in the fields of machine learning, visualization, and human-computer interaction, we present a categorization of interpretable machine learning design goals and evaluation methods to show a mapping between design goals for different XAI user groups and their evaluation methods. From our findings, we develop a framework with step-by-step design guidelines paired with evaluation methods to close the iterative design and evaluation cycles in multidisciplinary XAI teams. Further, we provide summarized ready-to-use tables of evaluation methods and recommendations for different goals in XAI research.
LoAdaBoost: loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data
Venue: arXiv cs.LG 2020
Year: 2020

Intensive care data are valuable for improvement of health care, policy making and many other purposes. Vast amount of such data are stored in different locations, on many different devices and in different data silos. Sharing data among different sources is a big challenge due to regulatory, operational and security reasons. One potential solution is federated machine learning, which is a method that sends machine learning algorithms simultaneously to all data sources, trains models in each source and aggregates the learned models. This strategy allows utilization of valuable data without moving them. One challenge in applying federated machine learning is the possibly different distributions of data from diverse sources. To tackle this problem, we proposed an adaptive boosting method named LoAdaBoost that increases the efficiency of federated machine learning. Using intensive care unit data from hospitals, we investigated the performance of learning in IID and non-IID data distribution scenarios, and showed that the proposed LoAdaBoost method achieved higher predictive accuracy with lower computational complexity than the baseline method.
Model Evaluation, Model Selection, and Algorithm Selection in Machine Learning
Venue: arXiv cs.LG 2020
Year: 2020

The correct use of model evaluation, model selection, and algorithm selection techniques is vital in academic machine learning research as well as in many industrial settings. This article reviews different techniques that can be used for each of these three subtasks and discusses the main advantages and disadvantages of each technique with references to theoretical and empirical studies. Further, recommendations are given to encourage best yet feasible practices in research and applications of machine learning. Common methods such as the holdout method for model evaluation and selection are covered, which are not recommended when working with small datasets. Different flavors of the bootstrap technique are introduced for estimating the uncertainty of performance estimates, as an alternative to confidence intervals via normal approximation if bootstrapping is computationally feasible. Common cross-validation techniques such as leave-one-out cross-validation and k-fold cross-validation are reviewed, the bias-variance trade-off for choosing k is discussed, and practical tips for the optimal choice of k are given based on empirical evidence. Different statistical tests for algorithm comparisons are presented, and strategies for dealing with multiple comparisons such as omnibus tests and multiple-comparison corrections are discussed. Finally, alternative methods for algorithm selection, such as the combined F-test 5x2 cross-validation and nested cross-validation, are recommended for comparing machine learning algorithms when datasets are small.
Anchor Box Optimization for Object Detection
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we propose a general approach to optimize anchor boxes for object detection. Nowadays, anchor boxes are widely adopted in state-of-the-art detection frameworks. However, these frameworks usually pre-define anchor box shapes in heuristic ways and fix the sizes during training. To improve the accuracy and reduce the effort of designing anchor boxes, we propose to dynamically learn the anchor shapes, which allows the anchors to automatically adapt to the data distribution and the network learning capability. The learning approach can be easily implemented with stochastic gradient descent and can be plugged into any anchor box-based detection framework. The extra training cost is almost negligible and it has no impact on the inference time or memory cost. Exhaustive experiments demonstrate that the proposed anchor optimization method consistently achieves significant improvement ($\ge 1\%$ mAP absolute gain) over the baseline methods on several benchmark datasets including Pascal VOC 07+12, MS COCO and Brainwash. Meanwhile, the robustness is also verified towards different anchor initialization methods and the number of anchor shapes, which greatly simplifies the problem of anchor box design.
Mitigating Planner Overfitting in Model-Based Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

An agent with an inaccurate model of its environment faces a difficult choice: it can ignore the errors in its model and act in the real world in whatever way it determines is optimal with respect to its model. Alternatively, it can take a more conservative stance and eschew its model in favor of optimizing its behavior solely via real-world interaction. This latter approach can be exceedingly slow to learn from experience, while the former can lead to "planner overfitting" - aspects of the agent's behavior are optimized to exploit errors in its model. This paper explores an intermediate position in which the planner seeks to avoid overfitting through a kind of regularization of the plans it considers. We present three different approaches that demonstrably mitigate planner overfitting in reinforcement-learning environments.
Practical relevance of software engineering research: Synthesizing the community's voice
Venue: arXiv cs.SE 2020
Year: 2020

Software engineering (SE) research should be relevant to industrial practice. There have been regular discussions in the SE community on this issue since the 1980's, led by pioneers such as Robert Glass. As we recently passed the milestone of "50 years of software engineering", some recent positive efforts have been made in this direction, e.g., establishing "industrial" tracks in several SE conferences. However, many researchers and practitioners believe that we, as a community, are still struggling with research relevance and utility. The goal of this paper is to synthesize the evidence and experience-based opinions shared on this topic so far in the SE community, and to encourage the community to further reflect and act on the research relevance. For this purpose, we have conducted a Multi-vocal Literature Review (MLR) of 54 systematically-selected sources (papers and non peer-reviewed articles). Instead of relying on and considering the individual opinions on research relevance, mentioned in each of the sources, the MLR aims to synthesize and provide the "holistic" view on the topic. The highlights of our MLR findings are as follows. The top three root causes of low relevance, discussed in the community, are: (1) Researchers having simplistic views (or wrong assumptions) about SE in practice; (2) Lack of connection with industry; and (3) Wrong identification of research problems. The top three suggestions for improving research relevance are: (1) Using appropriate research approaches such as action-research; (2) Choosing relevant research problems; and (3) Collaborating with industry. By synthesizing all the discussions on this important topic so far, this paper aims to encourage further discussions and actions in the community to increase our collective efforts to improve the research relevance.
Searching for an analogue of ATR in the Weihrauch lattice
Venue: arXiv cs.LO 2020
Year: 2020

There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far ATR_0 has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.
InferLine: ML Prediction Pipeline Provisioning and Management for Tight Latency Objectives
Venue: arXiv cs.DC 2020
Year: 2020

Serving ML prediction pipelines spanning multiple models and hardware accelerators is a key challenge in production machine learning. Optimally configuring these pipelines to meet tight end-to-end latency goals is complicated by the interaction between model batch size, the choice of hardware accelerator, and variation in the query arrival process. In this paper we introduce InferLine, a system which provisions and manages the individual stages of prediction pipelines to meet end-to-end tail latency constraints while minimizing cost. InferLine consists of a low-frequency combinatorial planner and a high-frequency auto-scaling tuner. The low-frequency planner leverages stage-wise profiling, discrete event simulation, and constrained combinatorial search to automatically select hardware type, replication, and batching parameters for each stage in the pipeline. The high-frequency tuner uses network calculus to auto-scale each stage to meet tail latency goals in response to changes in the query arrival process. We demonstrate that InferLine outperforms existing approaches by up to 7.6x in cost while achieving up to 34.5x lower latency SLO miss rate on realistic workloads and generalizes across state-of-the-art model serving frameworks.
Teacher-Student Compression with Generative Adversarial Networks
Venue: arXiv cs.LG 2020
Year: 2020

More accurate machine learning models often demand more computation and memory at test time, making them difficult to deploy on CPU- or memory-constrained devices. Teacher-student compression (TSC), also known as distillation, alleviates this burden by training a less expensive student model to mimic the expensive teacher model while maintaining most of the original accuracy. However, when fresh data is unavailable for the compression task, the teacher's training data is typically reused, leading to suboptimal compression. In this work, we propose to augment the compression dataset with synthetic data from a generative adversarial network (GAN) designed to approximate the training data distribution. Our GAN-assisted TSC (GAN-TSC) significantly improves student accuracy for expensive models such as large random forests and deep neural networks on both tabular and image datasets. Building on these results, we propose a comprehensive metric---the TSC Score---to evaluate the quality of synthetic datasets based on their induced TSC performance. The TSC Score captures both data diversity and class affinity, and we illustrate its benefits over the popular Inception Score in the context of image classification.
Pseudo-Rehearsal: Achieving Deep Reinforcement Learning without Catastrophic Forgetting
Venue: arXiv cs.LG 2020
Year: 2020

Neural networks can achieve excellent results in a wide variety of applications. However, when they attempt to sequentially learn, they tend to learn the new task while catastrophically forgetting previous ones. We propose a model that overcomes catastrophic forgetting in sequential reinforcement learning by combining ideas from continual learning in both the image classification domain and the reinforcement learning domain. This model features a dual memory system which separates continual learning from reinforcement learning and a pseudo-rehearsal system that "recalls" items representative of previous tasks via a deep generative network. Our model sequentially learns Atari 2600 games without demonstrating catastrophic forgetting and continues to perform above human level on all three games. This result is achieved without: demanding additional storage requirements as the number of tasks increases, storing raw data or revisiting past tasks. In comparison, previous state-of-the-art solutions are substantially more vulnerable to forgetting on these complex deep reinforcement learning tasks.