OpenRaiser/Intern-Atlas huggingface dataset:
Solving large number of non-stiff, low-dimensional ordinary differential equation systems on GPUs and CPUs: performance comparisons of MPGOS, ODEINT and DifferentialEquations.jl
Venue: arXiv cs.DC 2020
Year: 2020

In this paper, the performance characteristics of different solution techniques and program packages to solve a large number of independent ordinary differential equation systems is examined. The employed hardware are an Intel Core i7-4820K CPU with 30.4 GFLOPS peak double-precision performance per cores and an Nvidia GeForce Titan Black GPU that has a total of 1707 GFLOPS peak double-precision performance. The tested systems (Lorenz equation, Keller--Miksis equation and a pressure relief valve model) are non-stiff and have low dimension. Thus, the performance of the codes are not limited by memory bandwidth, and Runge--Kutta type solvers are efficient and suitable choices. The tested program packages are MPGOS written in C++ and specialised only for GPUs; ODEINT implemented in C++, which supports execution on both CPUs and GPUs; finally, DifferentialEquations.jl written in Julia that also supports execution on both CPUs and GPUs. Using GPUs, the program package MPGOS is superior. For CPU computations, the ODEINT program package has the best performance.
Deep Reinforcement Learning Based Dynamic Route Planning for Minimizing Travel Time
Venue: arXiv cs.LG 2020
Year: 2020

Route planning is important in transportation. Existing works focus on finding the shortest path solution or using metrics such as safety and energy consumption to determine the planning. It is noted that most of these studies rely on prior knowledge of road network, which may be not available in certain situations. In this paper, we design a route planning algorithm based on deep reinforcement learning (DRL) for pedestrians. We use travel time consumption as the metric, and plan the route by predicting pedestrian flow in the road network. We put an agent, which is an intelligent robot, on a virtual map. Different from previous studies, our approach assumes that the agent does not need any prior information about road network, but simply relies on the interaction with the environment. We propose a dynamically adjustable route planning (DARP) algorithm, where the agent learns strategies through a dueling deep Q network to avoid congested roads. Simulation results show that the DARP algorithm saves 52% of the time under congestion condition when compared with traditional shortest path planning algorithms.
On Singleton Congestion Games with Resilience Against Collusion
Venue: arXiv cs.GT 2020
Year: 2020

We study the subclass of singleton congestion games with identical and increasing cost functions, i.e., each agent tries to utilize from the least crowded resource in her accessible subset of resources. Our main contribution is a novel approach for proving the existence of equilibrium outcomes that are resilient to weakly improving deviations: $(i)$ by singletons (Nash equilibria), $(ii)$ by the grand coalition (Pareto efficiency), and $(iii)$ by coalitions with respect to an a priori given partition coalition structure (partition equilibria). To the best of our knowledge, this is the strongest existence guarantee in the literature of congestion games that is resilient to weakly improving deviations by coalitions.
Human-in-the-Loop Robot Planning with Non-Contextual Bandit Feedback
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we consider a robot navigation problem in environments populated by humans. The goal is to determine collision-free and dynamically feasible trajectories that also maximize human satisfaction. This is because they may drive the robot close to humans that need help with their work or because they may keep the robot away from humans when it can interfere with human sight or work. In practice, human satisfaction is subjective and hard to describe mathematically. As a result, the planning problem we consider in this paper may lack important contextual information. To address this challenge, we propose a semi-supervised Bayesian Optimization (BO) method to design globally optimal robot trajectories using non-contextual bandit human feedback in the form of complaints or satisfaction ratings that express how satisfactory a trajectory is, without revealing the reason. Since trajectory planning is typically a high-dimensional optimization problem in the space of waypoints that define a trajectory, BO may require prohibitively many queries for human feedback to return a good solution. To this end, we use an autoencoder to reduce the high-dimensional problem space into a low dimensional latent space, which we update using human feedback. Moreover, we improve the exploration efficiency of BO by biasing the search for new trajectories towards dynamically feasible and collision-free trajectories obtained using off-the-shelf motion planners. We demonstrate the efficiency of our proposed trajectory planning method in a scenario with humans that have diversified and unknown demands.
Specialization in Hierarchical Learning Systems
Venue: arXiv cs.LG 2020
Year: 2020

Joining multiple decision-makers together is a powerful way to obtain more sophisticated decision-making systems, but requires to address the questions of division of labor and specialization. We investigate in how far information constraints in hierarchies of experts not only provide a principled method for regularization but also to enforce specialization. In particular, we devise an information-theoretically motivated on-line learning rule that allows partitioning of the problem space into multiple sub-problems that can be solved by the individual experts. We demonstrate two different ways to apply our method: (i) partitioning problems based on individual data samples and (ii) based on sets of data samples representing tasks. Approach (i) equips the system with the ability to solve complex decision-making problems by finding an optimal combination of local expert decision-makers. Approach (ii) leads to decision-makers specialized in solving families of tasks, which equips the system with the ability to solve meta-learning problems. We show the broad applicability of our approach on a range of problems including classification, regression, density estimation, and reinforcement learning problems, both in the standard machine learning setup and in a meta-learning setting.
Decoupling entrainment from consistency using deep neural networks
Venue: arXiv cs.CL 2020
Year: 2020

Human interlocutors tend to engage in adaptive behavior known as entrainment to become more similar to each other. Isolating the effect of consistency, i.e., speakers adhering to their individual styles, is a critical part of the analysis of entrainment. We propose to treat speakers' initial vocal features as confounds for the prediction of subsequent outputs. Using two existing neural approaches to deconfounding, we define new measures of entrainment that control for consistency. These successfully discriminate real interactions from fake ones. Interestingly, our stricter methods correlate with social variables in opposite direction from previous measures that do not account for consistency. These results demonstrate the advantages of using neural networks to model entrainment, and raise questions regarding how to interpret prior associations of conversation quality with entrainment measures that do not account for consistency.
Periodic Scheduling and Packing Problems
Venue: arXiv cs.DS 2020
Year: 2020

This paper is motivated by periodic data transmission in autonomous cars. We considered periodic tasks (with different periods) on one or several machines. After reviewing the literature on the subject, we managed to generalize a result of Lukasiewicz et al. (i.e., the equivalence of periodic scheduling with the power of two periods and special 2D bin packing) to harmonic periods. Furthermore, we use quite old results by Coffman, Garey, and Johnson to get an approximation algorithm.
Warped Language Models for Noise Robust Language Understanding
Venue: arXiv cs.CL 2020
Year: 2020

Masked Language Models (MLM) are self-supervised neural networks trained to fill in the blanks in a given sentence with masked tokens. Despite the tremendous success of MLMs for various text based tasks, they are not robust for spoken language understanding, especially for spontaneous conversational speech recognition noise. In this work we introduce Warped Language Models (WLM) in which input sentences at training time go through the same modifications as in MLM, plus two additional modifications, namely inserting and dropping random tokens. These two modifications extend and contract the sentence in addition to the modifications in MLMs, hence the word "warped" in the name. The insertion and drop modification of the input text during training of WLM resemble the types of noise due to Automatic Speech Recognition (ASR) errors, and as a result WLMs are likely to be more robust to ASR noise. Through computational results we show that natural language understanding systems built on top of WLMs perform better compared to those built based on MLMs, especially in the presence of ASR errors.
The dynamics of U.S. college network formation on Facebook
Venue: arXiv cs.SI 2020
Year: 2020

In the U.S., a significant portion of many people's life-long social networks is formed in college. Yet our understanding of many aspects of this formation process, such as the role of time variation, heterogeneity between educational contexts, and the persistence of ties formed during college, is incomplete. In order to help fill some of these gaps, we use a population-level dataset of the social networks of 1,181 U.S. institutions of higher education, ranging from 2008 to 2019, to provide a detailed view of how the structure of college networks changes over time. The most prominent feature in the evolution of these networks is the burst in friending activity when students first enter college. Ties formed during this period play a strong role in shaping the structure of the networks overall and the students' position within them. Subsequent starts and breaks from instruction further affect the volume of new tie formation. Homophily in tie formation likewise shows variation in time. Same-gender ties are more likely to form when students settle into housing, while sharing a major spurs friendships as students progress through their degree. Properties of the college, such as whether many students live on campus, also modulate these effects. Ties that form in different contexts and at different points in students' college lives vary in their likelihood of remaining close years after graduation. Together, these findings suggest that educational context mediates network formation in multiple different ways.
Bayesian Variational Optimization for Combinatorial Spaces
Venue: arXiv cs.LG 2020
Year: 2020

This paper focuses on Bayesian Optimization in combinatorial spaces. In many applications in the natural science. Broad applications include the study of molecules, proteins, DNA, device structures and quantum circuit designs, a on optimization over combinatorial categorical spaces is needed to find optimal or pareto-optimal solutions. However, only a limited amount of methods have been proposed to tackle this problem. Many of them depend on employing Gaussian Process for combinatorial Bayesian Optimizations. Gaussian Processes suffer from scalability issues for large data sizes as their scaling is cubic with respect to the number of data points. This is often impractical for optimizing large search spaces. Here, we introduce a variational Bayesian optimization method that combines variational optimization and continuous relaxations to the optimization of the acquisition function for Bayesian optimization. Critically, this method allows for gradient-based optimization and has the capability of optimizing problems with large data size and data dimensions. We have shown the performance of our method is comparable to state-of-the-art methods while maintaining its scalability advantages. We also applied our method in molecular optimization.
The Min-Cost Matching with Concave Delays Problem
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of online min-cost perfect matching with concave delays. We begin with the single location variant. Specifically, requests arrive in an online fashion at a single location. The algorithm must then choose between matching a pair of requests or delaying them to be matched later on. The cost is defined by a concave function on the delay. Given linear or even convex delay functions, matching any two available requests is trivially optimal. However, this does not extend to concave delays. We solve this by providing an $O(1)$-competitive algorithm that is defined through a series of delay counters. Thereafter we consider the problem given an underlying $n$-points metric. The cost of a matching is then defined as the connection cost (as defined by the metric) plus the delay cost. Given linear delays, this problem was introduced by Emek et al. and dubbed the Min-cost perfect matching with linear delays (MPMD) problem. Liu et al. considered convex delays and subsequently asked whether there exists a solution with small competitive ratio given concave delays. We show this to be true by extending our single location algorithm and proving $O(\log n)$ competitiveness. Finally, we turn our focus to the bichromatic case, wherein requests have polarities and only opposite polarities may be matched. We show how to alter our former algorithms to again achieve $O(1)$ and $O(\log n)$ competitiveness for the single location and for the metric case.
Multi-hop Routing with Proactive Route Refinement for 60 GHz Millimeter-Wave Networks
Venue: arXiv cs.NI 2020
Year: 2020

Fundamental requirements of mmWave systems are peak data rates of multiple Gbps and latencies of the order of at most a few milliseconds. However, highly directional mmWave links are susceptible to frequent link failures under stress conditions such as mobility and human blockage. Under these conditions, multi-hop routing can achieve reliable and robust performance. In this paper, we consider multi-hop millimeter wave (mmWave) wireless systems and propose proactive route refinement schemes that are particularly important under dynamic scenarios. First, we consider the AODV-type protocols and propose a cross-layer approach that integrates sectorized communication at the MAC layer with on-demand multi-hop routing at the network layer. Next, we consider Backpressure routing protocol, and enhance this protocol with periodic HELLO status messages. System-level simulation results based on the IEEE 802.11ad standard are provided that confirm the benefits of proactive route refinement for the ADOV-type and Backpressure routing protocols.
An On-Line POMDP Solver for Continuous Observation Spaces
Venue: arXiv cs.AI 2020
Year: 2020

Planning under partial obervability is essential for autonomous robots. A principled way to address such planning problems is the Partially Observable Markov Decision Process (POMDP). Although solving POMDPs is computationally intractable, substantial advancements have been achieved in developing approximate POMDP solvers in the past two decades. However, computing robust solutions for problems with continuous observation spaces remains challenging. Most on-line solvers rely on discretising the observation space or artificially limiting the number of observations that are considered during planning to compute tractable policies. In this paper we propose a new on-line POMDP solver, called Lazy Belief Extraction for Continuous POMDPs (LABECOP), that combines methods from Monte-Carlo-Tree-Search and particle filtering to construct a policy reprentation which doesn't require discretised observation spaces and avoids limiting the number of observations considered during planning. Experiments on three different problems involving continuous observation spaces indicate that LABECOP performs similar or better than state-of-the-art POMDP solvers.
Analysing Long Short Term Memory Models for Cricket Match Outcome Prediction
Venue: arXiv cs.LG 2020
Year: 2020

As the technology advances, an ample amount of data is collected in sports with the help of advanced sensors. Sports Analytics is the study of this data to provide a constructive advantage to the team and its players. The game of international cricket is popular all across the globe. Recently, various machine learning techniques have been used to analyse the cricket match data and predict the match outcome as win or lose. Generally these models make use of the overall match level statistics such as teams, venue, average run rate, win margin, etc to predict the match results before the beginning of the match. However, very few works provide insights based on the ball-by-ball level statistics. Here we propose a novel Recurrent Neural Network model which can predict the win probability of a match at regular intervals given the ball-by-ball statistics. The Long Short Term Memory (LSTM) Model takes as input the ball wise features as well as the match level details available from the training dataset. It gives a prediction of winning the match at any time stamp during the match. This level of insight will help the team to predict the probability of them winning the match after every ball and help them determine the critical in-game changes they should make in their game strategies.
Planning to Chronicle
Venue: arXiv cs.RO 2020
Year: 2020

An important class of applications entails a robot monitoring, scrutinizing, or recording the evolution of an uncertain time-extended process. This sort of situation leads an interesting family of planning problems in which the robot is limited in what it sees and must, thus, choose what to pay attention to. The distinguishing characteristic of this setting is that the robot has influence over what it captures via its sensors, but exercises no causal authority over the evolving process. As such, the robot's objective is to observe the underlying process and to produce a `chronicle' of occurrent events, subject to a goal specification of the sorts of event sequences that may be of interest. This paper examines variants of such problems when the robot aims to collect sets of observations to meet a rich specification of their sequential structure. We study this class of problems by modeling a stochastic process via a variant of a hidden Markov model, and specify the event sequences of interest as a regular language, developing a vocabulary of `mutators' that enable sophisticated requirements to be expressed. Under different suppositions about the information gleaned about the Markov model, we formulate and solve different planning problems. The core underlying idea is the construction of a product between the event model and a specification automaton. The paper reports and compares performance metrics by drawing on some small case studies analyzed in depth in simulation.
Leveraging Temporal Joint Depths for Improving 3D Human Pose Estimation in Video
Venue: arXiv cs.CV 2020
Year: 2020

The effectiveness of the approaches to predict 3D poses from 2D poses estimated in each frame of a video has been demonstrated for 3D human pose estimation. However, 2D poses without appearance information of persons have much ambiguity with respect to the joint depths. In this paper, we propose to estimate a 3D pose in each frame of a video and refine it considering temporal information. The proposed approach reduces the ambiguity of the joint depths and improves the 3D pose estimation accuracy.
Between proper and strong edge-colorings of subcubic graphs
Venue: arXiv cs.DM 2020
Year: 2020

In a proper edge-coloring the edges of every color form a matching. A matching is induced if the end-vertices of its edges induce a matching. A strong edge-coloring is an edge-coloring in which the edges of every color form an induced matching. We consider intermediate types of edge-colorings, where edges of some colors are allowed to form matchings, and the remaining form induced matchings. Our research is motivated by the conjecture proposed in a recent paper of Gastineau and Togni on S-packing edge-colorings (On S-packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019), 63-75) asserting that by allowing three additional induced matchings, one is able to save one matching color. We prove that every graph with maximum degree 3 can be decomposed into one matching and at most 8 induced matchings, and two matchings and at most 5 induced matchings. We also show that if a graph is in class I, the number of induced matchings can be decreased by one, hence confirming the above-mentioned conjecture for class I graphs.
Hyperspectral classification of blood-like substances using machine learning methods combined with genetic algorithms in transductive and inductive scenarios
Venue: arXiv cs.CV 2020
Year: 2020

This study is focused on applying genetic algorithms (GA) to model and band selection in hyperspectral image classification. We use a forensic-inspired data set of seven hyperspectral images with blood and five visually similar substances to test GA-optimised classifiers in two scenarios: when the training and test data come from the same image and when they come from different images, which is a more challenging task due to significant spectra differences. In our experiments we compare GA with a classic model optimisation through grid search. Our results show that GA-based model optimisation can reduce the number of bands and create an accurate classifier that outperforms the GS-based reference models, provided that during model optimisation it has access to examples similar to test data. We illustrate this with experiment highlighting the importance of a validation set.
A Self-stabilizing Control Plane for the Edge and Fog Ecosystems
Venue: arXiv cs.DC 2020
Year: 2020

Fog Computing is now emerging as the dominating paradigm bridging the compute and connectivity gap between sensing devices (a.k.a. "things") and latency-sensitive services. However, as fog deployments scale by accumulating numerous devices interconnected over highly dynamic and volatile network fabrics, the need for self-configuration and self-healing in the presence of failures is more evident now than ever. Using the prevailing methodology of self-stabilization, we propose a fault-tolerant framework for distributed control planes that enables fog services to cope and recover from a very broad fault model. Specifically, our model considers network uncertainties, packet drops, node fail-stop failures, and violations of the assumptions according to which the system was designed to operate, such as an arbitrary corruption of the system state. Our self-stabilizing algorithms guarantee automatic recovery within a constant number of communication rounds without the need for external (human) intervention. To showcase the framework's effectiveness, the correctness proof of the proposed self-stabilizing algorithmic process is accompanied by a comprehensive evaluation featuring an open and reproducible testbed utilizing real-world data from the intelligent transportation domain. Results show that our framework ensures a fog ecosystem recovery from faults in constant time, analytics are computed correctly, while the overhead to the system's control plane scales linearly towards the IoT load.