OpenRaiser/Intern-Atlas huggingface dataset:
Policy Synthesis for Factored MDPs with Graph Temporal Logic Specifications
Venue: arXiv cs.MA 2020
Year: 2020

We study the synthesis of policies for multi-agent systems to implement spatial-temporal tasks. We formalize the problem as a factored Markov decision process subject to so-called graph temporal logic specifications. The transition function and the spatial-temporal task of each agent depend on the agent itself and its neighboring agents. The structure in the model and the specifications enable to develop a distributed algorithm that, given a factored Markov decision process and a graph temporal logic formula, decomposes the synthesis problem into a set of smaller synthesis problems, one for each agent. We prove that the algorithm runs in time linear in the total number of agents. The size of the synthesis problem for each agent is exponential only in the number of neighboring agents, which is typically much smaller than the number of agents. We demonstrate the algorithm in case studies on disease control and urban security. The numerical examples show that the algorithm can scale to hundreds of agents.
Why Temporal Persistence of Biometric Features is so Valuable for Classification Performance
Venue: arXiv cs.CR 2020
Year: 2020

It is generally accepted that relatively more permanent (i.e., more temporally persistent) traits are more valuable for biometric performance than less permanent traits. Although this finding is intuitive, there is no current work identifying exactly where in the biometric analysis temporal persistence makes a difference. In this paper, we answer this question. In a recent report, we introduced the intraclass correlation coefficient (ICC) as an index of temporal persistence for such features. In that report, we also showed that choosing only the most temporally persistent features yielded superior performance in 12 of 14 datasets. Motivated by those empirical results, we present a novel approach using synthetic features to study which aspects of a biometric identification study are influenced by the temporal persistence of features. What we show is that using more temporally persistent features produces effects on the similarity score distributions that explain why this quality is so key to biometric performance. The results identified with the synthetic data are largely reinforced by an analysis of two datasets, one based on eye-movements and one based on gait. There was one difference between the synthetic and real data: In real data, features are intercorrelated, with the level of intercorrelation increasing with increasing ICC. This increasedhttps://www.overleaf.com/project/5e2b14694c5dc600017292e6 intercorrelation in real data was associated with an increase in the spread of the impostor similarity score distributions. Removing these intercorrelations for real datasets with a decorrelation step produced results which were very similar to that obtained with synthetic features.
Touchless Typing Using Head Movement-based Gestures
Venue: arXiv cs.HC 2020
Year: 2020

In this paper, we propose a novel touchless typing interface that makes use of an on-screen QWERTY keyboard and a smartphone camera. The keyboard was divided into nine color-coded clusters. The user moved their head toward clusters, which contained the letters that they wanted to type. A front-facing smartphone camera recorded the head movements. A bidirectional GRU based model which used pre-trained embedding rich in head pose features was employed to translate the recordings into cluster sequences. The model achieved an accuracy of 96.78% and 86.81% under intra- and inter-user scenarios, respectively, over a dataset of 2234 video sequences collected from 22 users.
A Combinatorial View of the Service Rates of Codes Problem, its Equivalence to Fractional Matching and its Connection with Batch Codes
Venue: arXiv cs.IT 2020
Year: 2020

We propose a novel technique for constructing a graph representation of a code through which we establish a significant connection between the service rate problem and the well-known fractional matching problem. Using this connection, we show that the service capacity of a coded storage system equals the fractional matching number in the graph representation of the code, and thus is lower bounded and upper bounded by the matching number and the vertex cover number, respectively. This is of great interest because if the graph representation of a code is bipartite, then the derived upper and lower bounds are equal, and we obtain the capacity. Leveraging this result, we characterize the service capacity of the binary simplex code whose graph representation, as we show, is bipartite. Moreover, we show that the service rate problem can be viewed as a generalization of the multiset primitive batch codes problem.
Learning to Catch Security Patches
Venue: arXiv cs.SE 2020
Year: 2020

Timely patching is paramount to safeguard users and maintainers against dire consequences of malicious attacks. In practice, patching is prioritized following the nature of the code change that is committed in the code repository. When such a change is labeled as being security-relevant, i.e., as fixing a vulnerability, maintainers rapidly spread the change and users are notified about the need to update to a new version of the library or of the application. Unfortunately, oftentimes, some security-relevant changes go unnoticed as they represent silent fixes of vulnerabilities. In this paper, we propose a Co-Training-based approach to catch security patches as part of an automatic monitoring service of code repositories. Leveraging different classes of features, we empirically show that such automation is feasible and can yield a precision of over 90% in identifying security patches, with an unprecedented recall of over 80%. Beyond such a benchmarking with ground truth data which demonstrates an improvement over the state-of-the-art, we confirmed that our approach can help catch security patches that were not reported as such.
Weakly Supervised Lesion Co-segmentation on CT Scans
Venue: arXiv cs.CV 2020
Year: 2020

Lesion segmentation in medical imaging serves as an effective tool for assessing tumor sizes and monitoring changes in growth. However, not only is manual lesion segmentation time-consuming, but it is also expensive and requires expert radiologist knowledge. Therefore many hospitals rely on a loose substitute called response evaluation criteria in solid tumors (RECIST). Although these annotations are far from precise, they are widely used throughout hospitals and are found in their picture archiving and communication systems (PACS). Therefore, these annotations have the potential to serve as a robust yet challenging means of weak supervision for training full lesion segmentation models. In this work, we propose a weakly-supervised co-segmentation model that first generates pseudo-masks from the RECIST slices and uses these as training labels for an attention-based convolutional neural network capable of segmenting common lesions from a pair of CT scans. To validate and test the model, we utilize the DeepLesion dataset, an extensive CT-scan lesion dataset that contains 32,735 PACS bookmarked images. Extensive experimental results demonstrate the efficacy of our co-segmentation approach for lesion segmentation with a mean Dice coefficient of 90.3%.
A tutorial on the range variant of asymmetric numeral systems
Venue: arXiv cs.IT 2020
Year: 2020

This paper is intended to be a brief and accessible introduction to the range variant of asymmetric numeral systems (ANS), a system for lossless compression of sequences which can be used as a drop in replacement for arithmetic coding (AC). Because of the relative simplicity of ANS, we are able to provide enough mathematical detail to rigorously prove that ANS attains a compression rate close to the Shannon limit. Pseudo-code, intuitive interpretation and diagrams are given alongside the mathematical derivations. A working Python demo which accompanies this tutorial is available at https://raw.githubusercontent.com/j-towns/ans-notes/master/rans.py.
Modular network for high accuracy object detection
Venue: arXiv cs.CV 2020
Year: 2020

We present a novel modular object detection convolutional neural network that significantly improves the accuracy of object detection. The network consists of two stages in a hierarchical structure. The first stage is a network that detects general classes. The second stage consists of separate networks to refine the classification and localization of each of the general classes objects. Compared to a state of the art object detection networks the classification error in the modular network is improved by approximately 3-5 times, from 12% to 2.5 %-4.5%. This network is easy to implement and has a 0.94 mAP. The network architecture can be a platform to improve the accuracy of widespread state of the art object detection networks and other kinds of deep learning networks. We show that a deep learning network initialized by transfer learning becomes more accurate as the number of classes it later trained to detect becomes smaller.
Explainable Active Learning (XAL): An Empirical Study of How Local Explanations Impact Annotator Experience
Venue: arXiv cs.HC 2020
Year: 2020

The wide adoption of Machine Learning technologies has created a rapidly growing demand for people who can train ML models. Some advocated the term "machine teacher" to refer to the role of people who inject domain knowledge into ML models. One promising learning paradigm is Active Learning (AL), by which the model intelligently selects instances to query the machine teacher for labels. However, in current AL settings, the human-AI interface remains minimal and opaque. We begin considering AI explanations as a core element of the human-AI interface for teaching machines. When a human student learns, it is a common pattern to present one's own reasoning and solicit feedback from the teacher. When a ML model learns and still makes mistakes, the human teacher should be able to understand the reasoning underlying the mistakes. When the model matures, the machine teacher should be able to recognize its progress in order to trust and feel confident about their teaching outcome. Toward this vision, we propose a novel paradigm of explainable active learning (XAL), by introducing techniques from the recently surging field of explainable AI (XAI) into an AL setting. We conducted an empirical study comparing the model learning outcomes, feedback content and experience with XAL, to that of traditional AL and coactive learning (providing the model's prediction without the explanation). Our study shows benefits of AI explanation as interfaces for machine teaching--supporting trust calibration and enabling rich forms of teaching feedback, and potential drawbacks--anchoring effect with the model judgment and cognitive workload. Our study also reveals important individual factors that mediate a machine teacher's reception to AI explanations, including task knowledge, AI experience and need for cognition. By reflecting on the results, we suggest future directions and design implications for XAL.
Fast Cubic Spline Interpolation
Venue: arXiv cs.MS 2020
Year: 2020

The Numerical Recipes series of books are a useful resource, but all the algorithms they contain cannot be used within open-source projects. In this paper we develop drop-in alternatives to the two algorithms they present for cubic spline interpolation, showing as much of our work as possible to allow for replication or criticsm. The output of the new algorithms is compared to the old, and found to be no different within the limits imposed by floating-point precision. Benchmarks of all these algorithms, plus variations which may run faster in certain instances, are performed. In general, all these algorithms have approximately the same execution time when interpolating curves with few control points on feature-rich Intel processors; as the number of control points increases or processor features are removed, the new algorithms become consistently faster than the old. Exceptions to that generalization are explored to create implementation guidelines, such as when to expect division to be faster than multiplication.
Improper Learning for Non-Stochastic Control
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of controlling a possibly unknown linear dynamical system with adversarial perturbations, adversarially chosen convex loss functions, and partially observed states, known as non-stochastic control. We introduce a controller parametrization based on the denoised observations, and prove that applying online gradient descent to this parametrization yields a new controller which attains sublinear regret vs. a large class of closed-loop policies. In the fully-adversarial setting, our controller attains an optimal regret bound of $\sqrt{T}$-when the system is known, and, when combined with an initial stage of least-squares estimation, $T^{2/3}$ when the system is unknown; both yield the first sublinear regret for the partially observed setting. Our bounds are the first in the non-stochastic control setting that compete with \emph{all} stabilizing linear dynamical controllers, not just state feedback. Moreover, in the presence of semi-adversarial noise containing both stochastic and adversarial components, our controller attains the optimal regret bounds of $\mathrm{poly}(\log T)$ when the system is known, and $\sqrt{T}$ when unknown. To our knowledge, this gives the first end-to-end $\sqrt{T}$ regret for online Linear Quadratic Gaussian controller, and applies in a more general setting with adversarial losses and semi-adversarial noise.
An Immunology-Inspired Network Security Architecture
Venue: arXiv cs.CR 2020
Year: 2020

The coming 5G networks have been enabling the creation of a wide variety of new services and applications which demand a new network security architecture. Immunology is the study of the immune system in vertebrates (including humans) which protects us from infection through various lines of defence. By studying the resemblance between the immune system and network security system, we acquire some inspirations from immunology and distill some guidelines for the design of network security architecture. We present a philosophical design principle, that is maintaining the balance between security and availability. Then, we derive two methodological principles: 1) achieving situation-awareness and fast response through community cooperation among heterogeneous nodes, and 2) Enhancing defense capability through consistently contesting with invaders in a real environment and actively mutating/evolving attack strategies. We also present a reference architecture designed based on the principles.
Learning Non-Markovian Reward Models in MDPs
Venue: arXiv cs.AI 2020
Year: 2020

There are situations in which an agent should receive rewards only after having accomplished a series of previous tasks. In other words, the reward that the agent receives is non-Markovian. One natural and quite general way to represent history-dependent rewards is via a Mealy machine; a finite state automaton that produces output sequences (rewards in our case) from input sequences (state/action observations in our case). In our formal setting, we consider a Markov decision process (MDP) that models the dynamic of the environment in which the agent evolves and a Mealy machine synchronised with this MDP to formalise the non-Markovian reward function. While the MDP is known by the agent, the reward function is unknown from the agent and must be learnt. Learning non-Markov reward functions is a challenge. Our approach to overcome this challenging problem is a careful combination of the Angluin's L* active learning algorithm to learn finite automata, testing techniques for establishing conformance of finite model hypothesis and optimisation techniques for computing optimal strategies in Markovian (immediate) reward MDPs. We also show how our framework can be combined with classical heuristics such as Monte Carlo Tree Search. We illustrate our algorithms and a preliminary implementation on two typical examples for AI.
Vehicle Scheduling Problem
Venue: arXiv cs.RO 2020
Year: 2020

We define a new problem called the Vehicle Scheduling Problem (VSP). The goal is to minimize an objective function, such as the number of tardy vehicles over a transportation network subject to maintaining safety distances, meeting hard deadlines, and maintaining speeds on each link between the allowed minimums and maximums. We prove VSP is an NP-hard problem for multiple objective functions that are commonly used in the context of job shop scheduling. With the number of tardy vehicles as the objective function, we formulate VSP in terms of a Mixed Integer Linear Programming (MIP) and design a heuristic algorithm. We analyze the complexity of our algorithm and compare the quality of the solutions to the optimal solution for the MIP formulation in the small cases. Our main motivation for defining VSP is the upcoming integration of Unmanned Aerial Vehicles (UAVs) into the airspace for which this novel scheduling framework is of paramount importance.
Bayesian optimization for backpropagation in Monte-Carlo tree search
Venue: arXiv cs.LG 2020
Year: 2020

In large domains, Monte-Carlo tree search (MCTS) is required to estimate the values of the states as efficiently and accurately as possible. However, the standard update rule in backpropagation assumes a stationary distribution for the returns, and particularly in min-max trees, convergence to the true value can be slow because of averaging. We present two methods, Softmax MCTS and Monotone MCTS, which generalize previous attempts to improve upon the backpropagation strategy. We demonstrate that both methods reduce to finding optimal monotone functions, which we do so by performing Bayesian optimization with a Gaussian process (GP) prior. We conduct experiments on computer Go, where the returns are given by a deep value neural network, and show that our proposed framework outperforms previous methods.
An Analysis of Word2Vec for the Italian Language
Venue: arXiv cs.CL 2020
Year: 2020

Word representation is fundamental in NLP tasks, because it is precisely from the coding of semantic closeness between words that it is possible to think of teaching a machine to understand text. Despite the spread of word embedding concepts, still few are the achievements in linguistic contexts other than English. In this work, analysing the semantic capacity of the Word2Vec algorithm, an embedding for the Italian language is produced. Parameter setting such as the number of epochs, the size of the context window and the number of negatively backpropagated samples is explored.
Learning Constraints from Locally-Optimal Demonstrations under Cost Function Uncertainty
Venue: arXiv cs.RO 2020
Year: 2020

We present an algorithm for learning parametric constraints from locally-optimal demonstrations, where the cost function being optimized is uncertain to the learner. Our method uses the Karush-Kuhn-Tucker (KKT) optimality conditions of the demonstrations within a mixed integer linear program (MILP) to learn constraints which are consistent with the local optimality of the demonstrations, by either using a known constraint parameterization or by incrementally growing a parameterization that is consistent with the demonstrations. We provide theoretical guarantees on the conservativeness of the recovered safe/unsafe sets and analyze the limits of constraint learnability when using locally-optimal demonstrations. We evaluate our method on high-dimensional constraints and systems by learning constraints for 7-DOF arm and quadrotor examples, show that it outperforms competing constraint-learning approaches, and can be effectively used to plan new constraint-satisfying trajectories in the environment.
CorGAN: Correlation-Capturing Convolutional Generative Adversarial Networks for Generating Synthetic Healthcare Records
Venue: arXiv cs.LG 2020
Year: 2020

Deep learning models have demonstrated high-quality performance in areas such as image classification and speech processing. However, creating a deep learning model using electronic health record (EHR) data, requires addressing particular privacy challenges that are unique to researchers in this domain. This matter focuses attention on generating realistic synthetic data while ensuring privacy. In this paper, we propose a novel framework called correlation-capturing Generative Adversarial Network (CorGAN), to generate synthetic healthcare records. In CorGAN we utilize Convolutional Neural Networks to capture the correlations between adjacent medical features in the data representation space by combining Convolutional Generative Adversarial Networks and Convolutional Autoencoders. To demonstrate the model fidelity, we show that CorGAN generates synthetic data with performance similar to that of real data in various Machine Learning settings such as classification and prediction. We also give a privacy assessment and report on statistical analysis regarding realistic characteristics of the synthetic data. The software of this work is open-source and is available at: https://github.com/astorfi/cor-gan.
Following Instructions by Imagining and Reaching Visual Goals
Venue: arXiv cs.LG 2020
Year: 2020

While traditional methods for instruction-following typically assume prior linguistic and perceptual knowledge, many recent works in reinforcement learning (RL) have proposed learning policies end-to-end, typically by training neural networks to map joint representations of observations and instructions directly to actions. In this work, we present a novel framework for learning to perform temporally extended tasks using spatial reasoning in the RL framework, by sequentially imagining visual goals and choosing appropriate actions to fulfill imagined goals. Our framework operates on raw pixel images, assumes no prior linguistic or perceptual knowledge, and learns via intrinsic motivation and a single extrinsic reward signal measuring task completion. We validate our method in two environments with a robot arm in a simulated interactive 3D environment. Our method outperforms two flat architectures with raw-pixel and ground-truth states, and a hierarchical architecture with ground-truth states on object arrangement tasks.
Towards Cooperative Data Rate Prediction for Future Mobile and Vehicular 6G Networks
Venue: arXiv cs.NI 2020
Year: 2020

Machine learning-based data rate prediction is one of the key drivers for anticipatory mobile networking with applications such as dynamic Radio Access Technology (RAT) selection, opportunistic data transfer, and predictive caching. User Equipment (UE)-based prediction approaches that rely on passive measurements of network quality indicators have successfully been applied to forecast the throughput of vehicular data transmissions. However, the achievable prediction accuracy is limited as the UE is unaware of the current network load. To overcome this issue, we propose a cooperative data rate prediction approach which brings together knowledge from the client and network domains. In a real world proof-of-concept evaluation, we utilize the Software Defined Radio (SDR)-based control channel sniffer FALCON in order to mimic the behavior of a possible network-assisted information provisioning within future 6G networks. The results show that the proposed cooperative prediction approach is able to reduce the average prediction error by up to 30%. With respect to the ongoing standardization efforts regarding the implementation of intelligence for network management, we argue that future 6G networks should go beyond network-focused approaches and actively provide load information to the UEs in order to fuel pervasive machine learning and catalyze UE-based network optimization techniques.