OpenRaiser/Intern-Atlas huggingface dataset:
A Survey on Traffic Signal Control Methods
Venue: arXiv cs.LG 2020
Year: 2020

Traffic signal control is an important and challenging real-world problem, which aims to minimize the travel time of vehicles by coordinating their movements at the road intersections. Current traffic signal control systems in use still rely heavily on oversimplified information and rule-based methods, although we now have richer data, more computing power and advanced methods to drive the development of intelligent transportation. With the growing interest in intelligent transportation using machine learning methods like reinforcement learning, this survey covers the widely acknowledged transportation approaches and a comprehensive list of recent literature on reinforcement for traffic signal control. We hope this survey can foster interdisciplinary research on this important topic.
Deep learning for image segmentation: veritable or overhyped?
Venue: arXiv cs.CV 2020
Year: 2020

Deep learning has achieved great success as a powerful classification tool and also made great progress in sematic segmentation. As a result, many researchers also believe that deep learning is the most powerful tool for pixel level image segmentation. Could deep learning achieve the same pixel level accuracy as traditional image segmentation techniques by mapping the features of the object into a non-linear function? This paper gives a short survey of the accuracies achieved by deep learning so far in image classification and image segmentation. Compared to the high accuracies achieved by deep learning in classifying limited categories in international vision challenges, the image segmentation accuracies achieved by deep learning in the same challenges are only about eighty percent. On the contrary, the image segmentation accuracies achieved in international biomedical challenges are close to ninty five percent. Why the difference is so big? Since the accuracies of the competitors methods are only evaluated based on their submitted results instead of reproducing the results by submitting the source codes or the software, are the achieved accuracies verifiable or overhyped? We are going to find it out by analyzing the working principle of deep learning. Finally, we compared the accuracies of state of the art deep learning methods with a threshold selection method quantitatively. Experimental results showed that the threshold selection method could achieve significantly higher accuracy than deep learning methods in image segmentation.
Design of Communication Systems using Deep Learning: A Variational Inference Perspective
Venue: arXiv cs.IT 2020
Year: 2020

Recent research in the design of end to end communication system using deep learning has produced models which can outperform traditional communication schemes. Most of these architectures leveraged autoencoders to design the encoder at the transmitter and decoder at the receiver and train them jointly by modeling transmit symbols as latent codes from the encoder. However, in communication systems, the receiver has to work with noise corrupted versions of transmit symbols. Traditional autoencoders are not designed to work with latent codes corrupted with noise. In this work, we provide a framework to design end to end communication systems which accounts for the existence of noise corrupted transmit symbols. The proposed method uses deep neural architecture. An objective function for optimizing these models is derived based on the concepts of variational inference. Further, domain knowledge such as channel type can be systematically integrated into the objective. Through numerical simulation, the proposed method is shown to consistently produce models with better packing density and achieving it faster in multiple popular channel models as compared to the previous works leveraging deep learning models.
Assigning tasks to agents under time conflicts: a parameterized complexity approach
Venue: arXiv cs.DM 2020
Year: 2020

We consider the problem of assigning tasks to agents under time conflicts, with applications also to frequency allocations in point-to-point wireless networks. In particular, we are given a set $V$ of $n$ agents, a set $E$ of $m$ tasks, and $k$ different time slots. Each task can be carried out in one of the $k$ predefined time slots, and can be represented by the subset $e\subseteq E$ of the involved agents. Since each agent cannot participate to more than one task simultaneously, we must find an allocation that assigns non-overlapping tasks to each time slot. Being the number of slots limited by $k$, in general it is not possible to executed all the possible tasks, and our aim is to determine a solution maximizing the overall social welfare, that is the number of executed tasks. We focus on the restriction of this problem in which the number of time slots is fixed to be $k=2$, and each task is performed by exactly two agents, that is $|e|=2$. In fact, even under this assumptions, the problem is still challenging, as it remains computationally difficult. We provide parameterized complexity results with respect to several reasonable parameters, showing for the different cases that the problem is fixed-parameter tractable or it is paraNP-hard.
Can Machine Learning Model with Static Features be Fooled: an Adversarial Machine Learning Approach
Venue: arXiv cs.CR 2020
Year: 2020

The widespread adoption of smartphones dramatically increases the risk of attacks and the spread of mobile malware, especially on the Android platform. Machine learning-based solutions have been already used as a tool to supersede signature-based anti-malware systems. However, malware authors leverage features from malicious and legitimate samples to estimate statistical difference in-order to create adversarial examples. Hence, to evaluate the vulnerability of machine learning algorithms in malware detection, we propose five different attack scenarios to perturb malicious applications (apps). By doing this, the classification algorithm inappropriately fits the discriminant function on the set of data points, eventually yielding a higher misclassification rate. Further, to distinguish the adversarial examples from benign samples, we propose two defense mechanisms to counter attacks. To validate our attacks and solutions, we test our model on three different benchmark datasets. We also test our methods using various classifier algorithms and compare them with the state-of-the-art data poisoning method using the Jacobian matrix. Promising results show that generated adversarial samples can evade detection with a very high probability. Additionally, evasive variants generated by our attack models when used to harden the developed anti-malware system improves the detection rate up to 50% when using the Generative Adversarial Network (GAN) method.
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation
Venue: arXiv cs.DS 2020
Year: 2020

In $masked\ low-rank\ approximation$, one is given $A \in \mathbb{R}^{n \times n}$ and binary mask matrix $W \in \{0,1\}^{n \times n}$. The goal is to find a rank-$k$ matrix $L$ for which: $$cost(L) = \sum_{i=1}^{n} \sum_{j = 1}^{n} W_{i,j} \cdot (A_{i,j} - L_{i,j} )^2 \leq OPT + ε\|A\|_F^2 ,$$ where $OPT = \min_{rank-k\ \hat{L}} cost(\hat L)$ and $ε$ is a given error parameter. Depending on the choice of $W$, this problem captures factor analysis, low-rank plus diagonal decomposition, robust PCA, low-rank matrix completion, low-rank plus block matrix approximation, and many problems. Many of these problems are NP-hard, and while some algorithms with provable guarantees are known, they either 1) run in time $n^{Ω(k^2/ε)}$ or 2) make strong assumptions, e.g., that $A$ is incoherent or that $W$ is random. In this work, we show that a common polynomial time heuristic, which simply sets $A$ to $0$ where $W$ is $0$, and then finds a standard low-rank approximation, yields bicriteria approximation guarantees for this problem. In particular, for rank $k' > k$ depending on the $public\ coin\ partition\ number$ of $W$, the heuristic outputs rank-$k'$ $L$ with cost$(L) \leq OPT + ε\|A\|_F^2$. This partition number is in turn bounded by the $randomized\ communication\ complexity$ of $W$, when interpreted as a two-player communication matrix. For many important examples of masked low-rank approximation, including all those listed above, this result yields bicriteria approximation guarantees with $k' = k \cdot poly(\log n/ε)$. Further, we show that different models of communication yield algorithms for natural variants of masked low-rank approximation. For example, multi-player number-in-hand communication complexity connects to masked tensor decomposition and non-deterministic communication complexity to masked Boolean low-rank factorization.
Non-Stationary Markov Decision Processes, a Worst-Case Approach using Model-Based Reinforcement Learning, Extended version
Venue: arXiv cs.LG 2020
Year: 2020

This work tackles the problem of robust zero-shot planning in non-stationary stochastic environments. We study Markov Decision Processes (MDPs) evolving over time and consider Model-Based Reinforcement Learning algorithms in this setting. We make two hypotheses: 1) the environment evolves continuously with a bounded evolution rate; 2) a current model is known at each decision epoch but not its evolution. Our contribution can be presented in four points. 1) we define a specific class of MDPs that we call Non-Stationary MDPs (NSMDPs). We introduce the notion of regular evolution by making an hypothesis of Lipschitz-Continuity on the transition and reward functions w.r.t. time; 2) we consider a planning agent using the current model of the environment but unaware of its future evolution. This leads us to consider a worst-case method where the environment is seen as an adversarial agent; 3) following this approach, we propose the Risk-Averse Tree-Search (RATS) algorithm, a zero-shot Model-Based method similar to Minimax search; 4) we illustrate the benefits brought by RATS empirically and compare its performance with reference Model-Based algorithms.
Reinterpreting CTC training as iterative fitting
Venue: arXiv cs.CV 2020
Year: 2020

The connectionist temporal classification (CTC) enables end-to-end sequence learning by maximizing the probability of correctly recognizing sequences during training. The outputs of a CTC-trained model tend to form a series of spikes separated by strongly predicted blanks, know as the spiky problem. To figure out the reason for it, we reinterpret the CTC training process as an iterative fitting task that is based on frame-wise cross-entropy loss. It offers us an intuitive way to compare target probabilities with model outputs for each iteration, and explain how the model outputs gradually turns spiky. Inspired by it, we put forward two ways to modify the CTC training. The experiments demonstrate that our method can well solve the spiky problem and moreover, lead to faster convergence over various training settings. Beside this, the reinterpretation of CTC, as a brand new perspective, may be potentially useful in other situations. The code is publicly available at https://github.com/hzli-ucas/caffe/tree/ctc.
Distributed Optimal Power Flow Algorithms Over Time-Varying Communication Networks
Venue: arXiv cs.SY 2020
Year: 2020

In this paper, we consider the problem of optimally coordinating the response of a group of distributed energy resources (DERs) in distribution systems by solving the so-called optimal power flow (OPF) problem. The OPF problem is concerned with determining an optimal operating point, at which some cost function, e.g., generation cost or power losses, is minimized, and operational constraints are satisfied. To solve the OPF problem, we propose distributed algorithms that are able to operate over time-varying communication networks and have geometric convergence rate. We solve the second-order cone program (SOCP) relaxation of the OPF problem for radial distribution systems, which is formulated using the so-called DistFlow model. Theoretical results are further supported by the numerical simulations.
Optimal Policies for Recovery of Multiple Systems After Disruptions
Venue: arXiv cs.SY 2020
Year: 2020

We consider a scenario where a system experiences a disruption, and the states (representing health values) of its components continue to reduce over time, unless they are acted upon by a controller. Given this dynamical setting, we consider the problem of finding an optimal control (or switching) sequence to maximize the sum of the weights of the components whose states are brought back to the maximum value. We first provide several characteristics of the optimal policy for the general (fully heterogeneous) version of this problem. We then show that under certain conditions on the rates of repair and deterioration, we can explicitly characterize the optimal control policy as a function of the states. When the deterioration rate (when not being repaired) is larger than or equal to the repair rate, and the deterioration and repair rates as well as the weights are homogeneous across all the components, the optimal control policy is to target the component that has the largest state value at each time step. On the other hand, if the repair rates are sufficiently larger than the deterioration rates, the optimal control policy is to target the component whose state minus the deterioration rate is least in a particular subset of components at each time step.
DPVis: Visual Analytics with Hidden Markov Models for Disease Progression Pathways
Venue: arXiv cs.LG 2020
Year: 2020

Clinical researchers use disease progression models to understand patient status and characterize progression patterns from longitudinal health records. One approach for disease progression modeling is to describe patient status using a small number of states that represent distinctive distributions over a set of observed measures. Hidden Markov models (HMMs) and its variants are a class of models that both discover these states and make inferences of health states for patients. Despite the advantages of using the algorithms for discovering interesting patterns, it still remains challenging for medical experts to interpret model outputs, understand complex modeling parameters, and clinically make sense of the patterns. To tackle these problems, we conducted a design study with clinical scientists, statisticians, and visualization experts, with the goal to investigate disease progression pathways of chronic diseases, namely type 1 diabetes (T1D), Huntington's disease, Parkinson's disease, and chronic obstructive pulmonary disease (COPD). As a result, we introduce DPVis which seamlessly integrates model parameters and outcomes of HMMs into interpretable and interactive visualizations. In this study, we demonstrate that DPVis is successful in evaluating disease progression models, visually summarizing disease states, interactively exploring disease progression patterns, and building, analyzing, and comparing clinically relevant patient subgroups.
Stability Optimization of Positive Semi-Markov Jump Linear Systems via Convex Optimization
Venue: arXiv cs.SY 2020
Year: 2020

In this paper, we study the problem of optimizing the stability of positive semi-Markov jump linear systems. We specifically consider the problem of tuning the coefficients of the system matrices for maximizing the exponential decay rate of the system under a budget-constraint. By using a result from the matrix theory on the log-log convexity of the spectral radius of nonnegative matrices, we show that the stability optimization problem reduces to a convex optimization problem under certain regularity conditions on the system matrices and the cost function. We illustrate the validity and effectiveness of the proposed results by using an example from the population biology.
A Large Scale Urban Surveillance Video Dataset for Multiple-Object Tracking and Behavior Analysis
Venue: arXiv cs.CV 2020
Year: 2020

Multiple-object tracking and behavior analysis have been the essential parts of surveillance video analysis for public security and urban management. With billions of surveillance video captured all over the world, multiple-object tracking and behavior analysis by manual labor are cumbersome and cost expensive. Due to the rapid development of deep learning algorithms in recent years, automatic object tracking and behavior analysis put forward an urgent demand on a large scale well-annotated surveillance video dataset that can reflect the diverse, congested, and complicated scenarios in real applications. This paper introduces an urban surveillance video dataset (USVD) which is by far the largest and most comprehensive. The dataset consists of 16 scenes captured in 7 typical outdoor scenarios: street, crossroads, hospital entrance, school gate, park, pedestrian mall, and public square. Over 200k video frames are annotated carefully, resulting in more than 3:7 million object bounding boxes and about 7:1 thousand trajectories. We further use this dataset to evaluate the performance of typical algorithms for multiple-object tracking and anomaly behavior analysis and explore the robustness of these methods in urban congested scenarios.
Copy mechanism and tailored training for character-based data-to-text generation
Venue: arXiv cs.LG 2020
Year: 2020

In the last few years, many different methods have been focusing on using deep recurrent neural networks for natural language generation. The most widely used sequence-to-sequence neural methods are word-based: as such, they need a pre-processing step called delexicalization (conversely, relexicalization) to deal with uncommon or unknown words. These forms of processing, however, give rise to models that depend on the vocabulary used and are not completely neural. In this work, we present an end-to-end sequence-to-sequence model with attention mechanism which reads and generates at a character level, no longer requiring delexicalization, tokenization, nor even lowercasing. Moreover, since characters constitute the common "building blocks" of every text, it also allows a more general approach to text generation, enabling the possibility to exploit transfer learning for training. These skills are obtained thanks to two major features: (i) the possibility to alternate between the standard generation mechanism and a copy one, which allows to directly copy input facts to produce outputs, and (ii) the use of an original training pipeline that further improves the quality of the generated texts. We also introduce a new dataset called E2E+, designed to highlight the copying capabilities of character-based models, that is a modified version of the well-known E2E dataset used in the E2E Challenge. We tested our model according to five broadly accepted metrics (including the widely used BLEU), showing that it yields competitive performance with respect to both character-based and word-based approaches.
Deep pNML: Predictive Normalized Maximum Likelihood for Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

The Predictive Normalized Maximum Likelihood (pNML) scheme has been recently suggested for universal learning in the individual setting, where both the training and test samples are individual data. The goal of universal learning is to compete with a ``genie'' or reference learner that knows the data values, but is restricted to use a learner from a given model class. The pNML minimizes the associated regret for any possible value of the unknown label. Furthermore, its min-max regret can serve as a pointwise measure of learnability for the specific training and data sample. In this work we examine the pNML and its associated learnability measure for the Deep Neural Network (DNN) model class. As shown, the pNML outperforms the commonly used Empirical Risk Minimization (ERM) approach and provides robustness against adversarial attacks. Together with its learnability measure it can detect out of distribution test examples, be tolerant to noisy labels and serve as a confidence measure for the ERM. Finally, we extend the pNML to a ``twice universal'' solution, that provides universality for model class selection and generates a learner competing with the best one from all model classes.
Improved Dynamic Graph Coloring
Venue: arXiv cs.DS 2020
Year: 2020

This paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within $n^{1-ε}$ for any $ε> 0$, is NP-hard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting. It is therefore only natural to consider the combinatorial aspects of dynamic coloring, or alternatively, study restricted families of graphs. Towards understanding the combinatorial aspects of this problem, one may assume a black-box access to a static algorithm for $C$-coloring any subgraph of the dynamic graph, and investigate the trade-off between the number of colors and the number of recolorings per update step. In WADS'17, Barba et al. devised two complementary algorithms: For any $β> 0$ the first (respectively, second) maintains an $O(C βn^{1/β})$ (resp., $O(C β)$)-coloring while recoloring $O(β)$ (resp., $O(βn^{1/β})$) vertices per update. Our contribution is two-fold: - We devise a new algorithm for general graphs that improves significantly upon the first trade-off in a wide range of parameters: For any $β> 0$, we get a $\tilde{O}(\frac{C}β\log^2 n)$-coloring with $O(β)$ recolorings per update, where the $\tilde{O}$ notation supresses polyloglog$(n)$ factors. In particular, for $β=O(1)$ we get constant recolorings with polylog$(n)$ colors; this is an exponential improvement over the previous bound. - For uniformly sparse graphs, we use low out-degree orientations to strengthen the above result by bounding the update time of the algorithm rather than the number of recolorings. Then, we further improve this result by introducing a new data structure that refines bounded out-degree edge orientations and is of independent interest.
Distributed Classification of Urban Congestion Using VANET
Venue: arXiv cs.LG 2020
Year: 2020

Vehicular Ad-hoc NETworks (VANET) can efficiently detect traffic congestion, but detection is not enough because congestion can be further classified as recurrent and non-recurrent congestion (NRC). In particular, NRC in an urban network is mainly caused by incidents, workzones, special events and adverse weather. We propose a framework for the real-time distributed classification of congestion into its components on a heterogeneous urban road network using VANET. We present models built on an understanding of the spatial and temporal causality measures and trained on synthetic data extended from a real case study of Cologne. Our performance evaluation shows a predictive accuracy of 87.63\% for the deterministic Classification Tree (CT), 88.83\% for the Naive Bayesian classifier (NB), 89.51\% for Random Forest (RF) and 89.17\% for the boosting technique. This framework can assist transportation agencies in reducing urban congestion by developing effective congestion mitigation strategies knowing the root causes of congestion.
New optimization algorithms for neural network training using operator splitting techniques
Venue: arXiv cs.LG 2020
Year: 2020

In the following paper we present a new type of optimization algorithms adapted for neural network training. These algorithms are based upon sequential operator splitting technique for some associated dynamical systems. Furthermore, we investigate through numerical simulations the empirical rate of convergence of these iterative schemes toward a local minimum of the loss function, with some suitable choices of the underlying hyper-parameters. We validate the convergence of these optimizers using the results of the accuracy and of the loss function on the MNIST, MNIST-Fashion and CIFAR 10 classification datasets.