OpenRaiser/Intern-Atlas huggingface dataset:
Robust supervised classification and feature selection using a primal-dual method
Venue: arXiv cs.LG 2019
Year: 2019

This paper deals with supervised classification and feature selection in high dimensional space. A classical approach is to project data on a low dimensional space and classify by minimizing an appropriate quadratic cost. A strict control on sparsity is moreover obtained by adding an $\ell_1$ constraint, here on the matrix of weights used for projecting the data. Tuning the sparsity bound results in selecting the relevant features for supervised classification. It is well known that using a quadratic cost is not robust to outliers. We cope with this problem by using an $\ell_1$ norm both for the constraint and for the loss function. In this case, the criterion is convex but not gradient Lipschitz anymore. Another second issue is that we optimize simultaneously the projection matrix and the centers used for classification. In this paper, we provide a novel tailored constrained primal-dual method to compute jointly selected features and classifiers. Extending our primal-dual method to other criteria is easy provided that efficient projection (on the dual ball for the loss data term) and prox (for the regularization term) algorithms are available. We illustrate such an extension in the case of a Frobenius norm for the loss term. We provide a convergence proof of our primal-dual method, and demonstrate its effectiveness on three datasets (one synthetic, two from biological data) on which we compare $\ell_1$ and $\ell_2$ costs.
Detecting Permanent and Intermittent Purchase Hotspots via Computational Stigmergy
Venue: arXiv cs.SI 2019
Year: 2019

The analysis of credit card transactions allows gaining new insights into the spending occurrences and mobility behavior of large numbers of individuals at an unprecedented scale. However, unfolding such spatiotemporal patterns at a community level implies a non-trivial system modeling and parametrization, as well as, a proper representation of the temporal dynamic. In this work we address both those issues by means of a novel computational technique, i.e. computational stigmergy. By using computational stigmergy each sample position is associated with a digital pheromone deposit, which aggregates with other deposits according to their spatiotemporal proximity. By processing transactions data with computational stigmergy, it is possible to identify high-density areas (hotspots) occurring in different time and days, as well as, analyze their consistency over time. Indeed, a hotspot can be permanent, i.e. present throughout the period of observation, or intermittent, i.e. present only in certain time and days due to community level occurrences (e.g. nightlife). Such difference is not only spatial (where the hotspot occurs) and temporal (when the hotspot occurs) but affects also which people visit the hotspot. The proposed approach is tested on a real-world dataset containing the credit card transaction of 60k users between 2014 and 2015.
Low-latency job scheduling with preemption for the development of deep learning
Venue: arXiv cs.DC 2019
Year: 2019

One significant challenge in the job scheduling of computing clusters for the development of deep learning algorithms is the efficient scheduling of trial-and-error (TE) job, the type of job in which the users seek to conduct small-scale experiments while monitoring their processes. Unfortunately, the existing job schedulers to date do not feature well-balanced scheduling for the mixture of TE jobs and best-effort (BE) jobs, or they can handle the mixture in limited situations at most. To fill in this niche, we propose an algorithm that can significantly reduce the latency of TE jobs in versatile situations without greatly elongating the slowdown of the BE jobs. Our algorithm efficiently schedules both TE and BE jobs by selectively preempting the BE jobs that can be, when the time comes, resumed without much delay. In our simulation study with synthetic and real workloads, we were able to reduce the 95th percentile of the slowdown rates for the TE jobs in the standard FIFO strategy by 96.6%, while compromising the median of the BE slowdown rates by only 18.0% and the 95th percentile by only 23.9%.
Echo State Networks: analysis, training and predictive control
Venue: arXiv cs.SY 2019
Year: 2019

The goal of this paper is to investigate the theoretical properties, the training algorithm, and the predictive control applications of Echo State Networks (ESNs), a particular kind of Recurrent Neural Networks. First, a condition guaranteeing incremetal global asymptotic stability is devised. Then, a modified training algorithm allowing for dimensionality reduction of ESNs is presented. Eventually, a model predictive controller is designed to solve the tracking problem, relying on ESNs as the model of the system. Numerical results concerning the predictive control of a nonlinear process for pH neutralization confirm the effectiveness of the proposed algorithms for the identification, dimensionality reduction, and the control design for ESNs.
Agent-Based Simulation Modelling for Reflecting on Consequences of Digital Mental Health
Venue: arXiv cs.MA 2019
Year: 2019

The premise of this working paper is based around agent-based simulation models and how to go about creating them from given incomplete information. Agent-based simulations are stochastic simulations that revolve around groups of agents that each have their own characteristics and can make decisions. Such simulations can be used to emulate real life situations and to create hypothetical situations without the need for real-world testing prior. Here we describe the development of an agent-based simulation model for studying future digital mental health scenarios. An incomplete conceptual model has been used as the basis for this development. To define differences in responses to stimuli we employed fuzzy decision making logic. The model has been implemented but not been used for structured experimentation yet. This is planned as our next step.
Rama: Controller Fault Tolerance in Software-Defined Networking Made Practical
Venue: arXiv cs.NI 2019
Year: 2019

In Software-Defined Networking (SDN), network applications use the logically centralized network view provided by the controller to remotely orchestrate the network switches. To avoid the controller being a single point of failure, traditional fault-tolerance techniques are employed to guarantee availability, a fundamental requirement in production environments. Unfortunately, these techniques fall short of ensuring correct network behaviour under controller failures. The problem of these techniques is that they deal with only part of the problem: guaranteeing that application and controller state remains consistent between replicas. However, in an SDN the switches maintain hard state that must also be handled consistently. Fault-tolerant SDN must therefore include switch state into the problem. A recently proposed fault-tolerant controller platform, Ravana, solves this problem by extending fault-tolerant SDN control with mechanisms that guarantee control messages to be processed transactionally and exactly once, at both the controllers and the switches. These guarantees are given even in the face of controller and switch crashes. The elegance of this solution comes at a cost. Ravana requires switches to be modified and OpenFlow to be extended with hitherto unforeseen additions to the protocol. In face of this challenge we propose Rama, a fault-tolerant SDN controller platform that offers the same strong guarantees as Ravana without requiring modifications to switches or to the OpenFlow protocol. Experiments with our prototype implementation show the additional overhead to be modest, making Rama the first fault-tolerant SDN solution that can be immediately deployable.
Hamiltonicity below Dirac's condition
Venue: arXiv cs.DS 2019
Year: 2019

Dirac's theorem (1952) is a classical result of graph theory, stating that an $n$-vertex graph ($n \geq 3$) is Hamiltonian if every vertex has degree at least $n/2$. Both the value $n/2$ and the requirement for every vertex to have high degree are necessary for the theorem to hold. In this work we give efficient algorithms for determining Hamiltonicity when either of the two conditions are relaxed. More precisely, we show that the Hamiltonian cycle problem can be solved in time $c^k \cdot n^{O(1)}$, for some fixed constant $c$, if at least $n-k$ vertices have degree at least $n/2$, or if all vertices have degree at least $n/2-k$. The running time is, in both cases, asymptotically optimal, under the exponential-time hypothesis (ETH). The results extend the range of tractability of the Hamiltonian cycle problem, showing that it is fixed-parameter tractable when parameterized below a natural bound. In addition, for the first parameterization we show that a kernel with $O(k)$ vertices can be found in polynomial time.
Dungeon Crawl Stone Soup as an Evaluation Domain for Artificial Intelligence
Venue: arXiv cs.AI 2019
Year: 2019

Dungeon Crawl Stone Soup is a popular, single-player, free and open-source rogue-like video game with a sufficiently complex decision space that makes it an ideal testbed for research in cognitive systems and, more generally, artificial intelligence. This paper describes the properties of Dungeon Crawl Stone Soup that are conducive to evaluating new approaches of AI systems. We also highlight an ongoing effort to build an API for AI researchers in the spirit of recent game APIs such as MALMO, ELF, and the Starcraft II API. Dungeon Crawl Stone Soup's complexity offers significant opportunities for evaluating AI and cognitive systems, including human user studies. In this paper we provide (1) a description of the state space of Dungeon Crawl Stone Soup, (2) a description of the components for our API, and (3) the potential benefits of evaluating AI agents in the Dungeon Crawl Stone Soup video game.
Guaranteed Safe Reachability-based Trajectory Design for a High-Fidelity Model of an Autonomous Passenger Vehicle
Venue: arXiv cs.SY 2019
Year: 2019

Trajectory planning is challenging for autonomous cars since they operate in unpredictable environments with limited sensor horizons. To incorporate new information as it is sensed, planning is done in a loop, with the next plan being computed as the previous plan is executed. The recent Reachability-based Trajectory Design (RTD) is a provably safe, real-time algorithm for trajectory planning. RTD consists of an offline component, where a Forward Reachable Set (FRS) is computed for the vehicle tracking parameterized trajectories; and an online part, where the FRS is used to map obstacles to constraints for trajectory optimization in a provably-safe way. In the literature, RTD has only been applied to small mobile robots. The contribution of this work is applying RTD to a passenger vehicle in CarSim, with a full powertrain model, chassis and tire dynamics. RTD produces safe trajectory plans with the vehicle traveling up to 15 m/s on a two-lane road, with randomly-placed obstacles only known to the vehicle when detected within its sensor horizon. RTD is compared with a Nonlinear Model-Predictive Control (NMPC) and a Rapidly-exploring Random Tree (RRT) approach. The experiment demonstrates RTD's ability to plan safe trajectories in real time, in contrast to the existing state-of-the-art approaches.
Error Rate Analysis of Amplitude-Coherent Detection over Rician Fading Channels with Receiver Diversity
Venue: arXiv cs.IT 2019
Year: 2019

Amplitude-coherent (AC) detection is an efficient detection technique that can simplify the receiver design while providing reliable symbol error rate (SER). Therefore, this work considers AC detector design and SER analysis using M-ary amplitude shift keying (MASK) modulation over Rician fading channels. More specifically, we derive the optimum, near-optimum and a suboptimum AC detectors and compare their SER to the coherent, noncoherent and the heuristic AC detectors. Moreover, the analytical SER of the heuristic detector is derived using two different approaches for single and multiple receiving antennas. One of the derived expressions is expressed in terms of a single integral that can be evaluated numerically, while the second approach gives a closed-form analytical expression for the SER, which is also used to derive a simple formula for the asymptotic SER at high signal-to-noise ratios (SNRs). The obtained analytical and simulation results show that the SER of the AC and coherent MASK detectors are comparable, particularly for high values of the Rician K-factor, and small number of receiving antennas. Moreover, the obtained results show that the SER of the optimal AC detector is equivalent to that of the coherent detector. However, the optimal AC detector complexity is prohibitively high, particularly at high SNRs. In most of the scenarios, the heuristic AC detector significantly outperforms the optimum noncoherent detector, except for the binary ASK case at low SNRs. Moreover, the obtained results show that the heuristic AC detector is immune to phase noise, and thus, it outperforms the coherent detector in scenarios where system is subject to considerable phase noise.
Hierarchical Matrix Operations on GPUs: Matrix-Vector Multiplication and Compression
Venue: arXiv cs.DS 2019
Year: 2019

Hierarchical matrices are space and time efficient representations of dense matrices that exploit the low rank structure of matrix blocks at different levels of granularity. The hierarchically low rank block partitioning produces representations that can be stored and operated on in near-linear complexity instead of the usual polynomial complexity of dense matrices. In this paper, we present high performance implementations of matrix vector multiplication and compression operations for the $\mathcal{H}^2$ variant of hierarchical matrices on GPUs. This variant exploits, in addition to the hierarchical block partitioning, hierarchical bases for the block representations and results in a scheme that requires only $O(n)$ storage and $O(n)$ complexity for the mat-vec and compression kernels. These two operations are at the core of algebraic operations for hierarchical matrices, the mat-vec being a ubiquitous operation in numerical algorithms while compression/recompression represents a key building block for other algebraic operations, which require periodic recompression during execution. The difficulties in developing efficient GPU algorithms come primarily from the irregular tree data structures that underlie the hierarchical representations, and the key to performance is to recast the computations on flattened trees in ways that allow batched linear algebra operations to be performed. This requires marshaling the irregularly laid out data in a way that allows them to be used by the batched routines. Marshaling operations only involve pointer arithmetic with no data movement and as a result have minimal overhead. Our numerical results on covariance matrices from 2D and 3D problems from spatial statistics show the high efficiency our routines achieve---over 550GB/s for the bandwidth-limited mat-vec and over 850GFLOPS/s in sustained performance for the compression on the P100 Pascal GPU.
Distribution-Dependent Analysis of Gibbs-ERM Principle
Venue: arXiv cs.LG 2019
Year: 2019

Gibbs-ERM learning is a natural idealized model of learning with stochastic optimization algorithms (such as Stochastic Gradient Langevin Dynamics and ---to some extent--- Stochastic Gradient Descent), while it also arises in other contexts, including PAC-Bayesian theory, and sampling mechanisms. In this work we study the excess risk suffered by a Gibbs-ERM learner that uses non-convex, regularized empirical risk with the goal to understand the interplay between the data-generating distribution and learning in large hypothesis spaces. Our main results are distribution-dependent upper bounds on several notions of excess risk. We show that, in all cases, the distribution-dependent excess risk is essentially controlled by the effective dimension $\mathrm{tr}\left(\boldsymbol{H}^{\star} (\boldsymbol{H}^{\star} + λ\boldsymbol{I})^{-1}\right)$ of the problem, where $\boldsymbol{H}^{\star}$ is the Hessian matrix of the risk at a local minimum. This is a well-established notion of effective dimension appearing in several previous works, including the analyses of SGD and ridge regression, but ours is the first work that brings this dimension to the analysis of learning using Gibbs densities. The distribution-dependent view we advocate here improves upon earlier results of Raginsky et al. (2017), and can yield much tighter bounds depending on the interplay between the data-generating distribution and the loss function. The first part of our analysis focuses on the localized excess risk in the vicinity of a fixed local minimizer. This result is then extended to bounds on the global excess risk, by characterizing probabilities of local minima (and their complement) under Gibbs densities, a results which might be of independent interest.
Reinforcement Learning for Optimal Load Distribution Sequencing in Resource-Sharing System
Venue: arXiv cs.DC 2019
Year: 2019

Divisible Load Theory (DLT) is a powerful tool for modeling divisible load problems in data-intensive systems. This paper studied an optimal divisible load distribution sequencing problem using a machine learning framework. The problem is to decide the optimal sequence to distribute divisible load to processors in order to achieve minimum finishing time. The scheduling is performed in a resource-sharing system where each physical processor is virtualized to multiple virtual processors. A reinforcement learning method called Multi-armed bandit (MAB) is used for our problem. We first provide a naive solution using the MAB algorithm and then several optimizations are performed. Various numerical tests are conducted. Our algorithm shows an increasing performance during the training progress and the global optimum will be acheived when the sample size is large enough.
Adaptive Stress Testing for Autonomous Vehicles
Venue: arXiv cs.RO 2019
Year: 2019

This paper presents a method for testing the decision making systems of autonomous vehicles. Our approach involves perturbing stochastic elements in the vehicle's environment until the vehicle is involved in a collision. Instead of applying direct Monte Carlo sampling to find collision scenarios, we formulate the problem as a Markov decision process and use reinforcement learning algorithms to find the most likely failure scenarios. This paper presents Monte Carlo Tree Search (MCTS) and Deep Reinforcement Learning (DRL) solutions that can scale to large environments. We show that DRL can find more likely failure scenarios than MCTS with fewer calls to the simulator. A simulation scenario involving a vehicle approaching a crosswalk is used to validate the framework. Our proposed approach is very general and can be easily applied to other scenarios given the appropriate models of the vehicle and the environment.
A User-Centric Cooperative Scheme for UAV Assisted Wireless Networks in Malfunction Areas
Venue: arXiv cs.NI 2019
Year: 2019

A promising application of unmanned aerial vehicles (UAVs) to the future communication networks is to address emergency communications. This paper considers such a scenario where a UAV is employed to a malfunction area (modeled as a circular disc) in which all ground base stations (BSs) break down. The ground BSs outside the malfunction area are modelled as a homogeneous Poisson point process (HPPP). Particularly, a user-centric cooperative scheme is proposed to serve the UEs in the malfunction area. According to the user equipment's (UE's) connections to the UAV and the nearest ground BS, the malfunction area is divided into three regions, namely the UAV region, the cooperation region and the nearest ground BS region, in which the UEs are served by the UAV only, both the UAV and the nearest ground BS, and the nearest ground BS, respectively. The region size of each type can be adjusted by a cooperation parameter $δ$. Through rigorous derivations, an expression for the coverage probability achieved by the UE in the malfunction area is obtained. In order to provide a fair comparison, the normalized spectral efficiency (NSE) which is defined by taking both system throughput and the number of serving BSs into consideration, is used as a criterion for the performance evaluation. Numerical results are presented to verify the accuracy of the analytical results and also to demonstrate the superior performance of the proposed scheme.
Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries
Venue: arXiv cs.MS 2019
Year: 2019

On common processors, integer multiplication is many times faster than integer division. Dividing a numerator n by a divisor d is mathematically equivalent to multiplication by the inverse of the divisor (n / d = n x 1/d). If the divisor is known in advance---or if repeated integer divisions will be performed with the same divisor---it can be beneficial to substitute a less costly multiplication for an expensive division. Currently, the remainder of the division by a constant is computed from the quotient by a multiplication and a subtraction. But if just the remainder is desired and the quotient is unneeded, this may be suboptimal. We present a generally applicable algorithm to compute the remainder more directly. Specifically, we use the fractional portion of the product of the numerator and the inverse of the divisor. On this basis, we also present a new, simpler divisibility algorithm to detect nonzero remainders. We also derive new tight bounds on the precision required when representing the inverse of the divisor. Furthermore, we present simple C implementations that beat the optimized code produced by state-of-art C compilers on recent x64 processors (e.g., Intel Skylake and AMD Ryzen), sometimes by more than 25%. On all tested platforms including 64-bit ARM and POWER8, our divisibility-test functions are faster than state-of-the-art Granlund-Montgomery divisibility-test functions, sometimes by more than 50%.
Exchangeable Generative Models with Flow Scans
Venue: arXiv cs.LG 2019
Year: 2019

In this work, we develop a new approach to generative density estimation for exchangeable, non-i.i.d. data. The proposed framework, FlowScan, combines invertible flow transformations with a sorted scan to flexibly model the data while preserving exchangeability. Unlike most existing methods, FlowScan exploits the intradependencies within sets to learn both global and local structure. FlowScan represents the first approach that is able to apply sequential methods to exchangeable density estimation without resorting to averaging over all possible permutations. We achieve new state-of-the-art performance on point cloud and image set modeling.