OpenRaiser/Intern-Atlas huggingface dataset:
Metrology for AI: From Benchmarks to Instruments
Venue: arXiv cs.AI 2019
Year: 2019

In this paper we present the first steps towards hardening the science of measuring AI systems, by adopting metrology, the science of measurement and its application, and applying it to human (crowd) powered evaluations. We begin with the intuitive observation that evaluating the performance of an AI system is a form of measurement. In all other science and engineering disciplines, the devices used to measure are called instruments, and all measurements are recorded with respect to the characteristics of the instruments used. One does not report mass, speed, or length, for example, of a studied object without disclosing the precision (measurement variance) and resolution (smallest detectable change) of the instrument used. It is extremely common in the AI literature to compare the performance of two systems by using a crowd-sourced dataset as an instrument, but failing to report if the performance difference lies within the capability of that instrument to measure. To illustrate the adoption of metrology to benchmark datasets we use the word similarity benchmark WS353 and several previously published experiments that use it for evaluation.
Analyzing connectivity of heterogeneous secure sensor networks
Venue: arXiv cs.DM 2019
Year: 2019

We analyze connectivity of a heterogeneous secure sensor network that uses key predistribution to protect communications between sensors. For this network on a set $\mathcal{V}_n$ of $n$ sensors, suppose there is a pool $\mathcal{P}_n$ consisting of $P_n$ distinct keys. The $n$ sensors in $\mathcal{V}_n$ are divided into $m$ groups $\mathcal{A}_1, \mathcal{A}_2, \ldots, \mathcal{A}_m$. Each sensor $v$ is independently assigned to exactly a group according to the probability distribution with $\mathbb{P}[v \in \mathcal{A}_i]= a_i$ for $i=1,2,\ldots,m$, where $\sum_{i=1}^{m}a_i = 1$. Afterwards, each sensor in group $\mathcal{A}_i$ independently chooses $K_{i,n}$ keys uniformly at random from the key pool $\mathcal{P}_n$, where $K_{1,n} \leq K_{2,n}\leq \ldots \leq K_{m,n}$. Finally, any two sensors in $\mathcal{V}_n$ establish a secure link in between if and only if they have at least one key in common. We present critical conditions for connectivity of this heterogeneous secure sensor network. The result provides useful guidelines for the design of secure sensor networks. This paper improves the seminal work [1] (IEEE Transactions on Information Theory 2016) of Ya{ğ}an on connectivity in several aspects (omitted due to arxiv abstract's character limitation; see the paper for details).
Scalable Variational Gaussian Processes for Crowdsourcing: Glitch Detection in LIGO
Venue: arXiv cs.LG 2019
Year: 2019

In the last years, crowdsourcing is transforming the way classification training sets are obtained. Instead of relying on a single expert annotator, crowdsourcing shares the labelling effort among a large number of collaborators. For instance, this is being applied to the data acquired by the laureate Laser Interferometer Gravitational Waves Observatory (LIGO), in order to detect glitches which might hinder the identification of true gravitational-waves. The crowdsourcing scenario poses new challenging difficulties, as it deals with different opinions from a heterogeneous group of annotators with unknown degrees of expertise. Probabilistic methods, such as Gaussian Processes (GP), have proven successful in modeling this setting. However, GPs do not scale well to large data sets, which hampers their broad adoption in real practice (in particular at LIGO). This has led to the recent introduction of deep learning based crowdsourcing methods, which have become the state-of-the-art. However, the accurate uncertainty quantification of GPs has been partially sacrificed. This is an important aspect for astrophysicists in LIGO, since a glitch detection system should provide very accurate probability distributions of its predictions. In this work, we leverage the most popular sparse GP approximation to develop a novel GP based crowdsourcing method that factorizes into mini-batches. This makes it able to cope with previously-prohibitive data sets. The approach, which we refer to as Scalable Variational Gaussian Processes for Crowdsourcing (SVGPCR), brings back GP-based methods to the state-of-the-art, and excels at uncertainty quantification. SVGPCR is shown to outperform deep learning based methods and previous probabilistic approaches when applied to the LIGO data. Moreover, its behavior and main properties are carefully analyzed in a controlled experiment based on the MNIST data set.
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
Venue: arXiv cs.DS 2019
Year: 2019

We present a $(1+\varepsilon)$-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving $\mathrm{poly}(\log n)$ depth and $m\mathrm{poly}(\log n)$ work for $n$-nodes $m$-edges graphs. Although sequential algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. For $(1+\varepsilon)$-approximation, all prior algorithms with $\mathrm{poly}(\log n)$ depth perform at least $Ω(mn^{c})$ work for some constant $c>0$. Improving this long-standing upper bound obtained by Cohen (STOC'94) has been open for $25$ years. We develop several new tools of independent interest. One of them is a new notion beyond hopsets --- low hop emulator --- a $\mathrm{poly}(\log n)$-approximate emulator graph in which every shortest path has at most $O(\log\log n)$ hops (edges). Direct applications of the low hop emulators are parallel algorithms for $\mathrm{poly}(\log n)$-approximate single source shortest path (SSSP), Bourgain's embedding, metric tree embedding, and low diameter decomposition, all with $\mathrm{poly}(\log n)$ depth and $m\mathrm{poly}(\log n)$ work. To boost the approximation ratio to $(1+\varepsilon)$, we introduce compressible preconditioners and apply it inside Sherman's framework (SODA'17) to solve the more general problem of uncapacitated minimum cost flow (a.k.a., transshipment problem). Our algorithm computes a $(1+\varepsilon)$-approximate uncapacitated minimum cost flow in $\mathrm{poly}(\log n)$ depth using $m\mathrm{poly}(\log n)$ work. As a consequence, it also improves the state-of-the-art sequential running time from $m\cdot 2^{O(\sqrt{\log n})}$ to $m\mathrm{poly}(\log n)$.
Language coverage and generalization in RNN-based continuous sentence embeddings for interacting agents
Venue: arXiv cs.CL 2019
Year: 2019

Continuous sentence embeddings using recurrent neural networks (RNNs), where variable-length sentences are encoded into fixed-dimensional vectors, are often the main building blocks of architectures applied to language tasks such as dialogue generation. While it is known that those embeddings are able to learn some structures of language (e.g. grammar) in a purely data-driven manner, there is very little work on the objective evaluation of their ability to cover the whole language space and to generalize to sentences outside the language bias of the training data. Using a manually designed context-free grammar (CFG) to generate a large-scale dataset of sentences related to the content of realistic 3D indoor scenes, we evaluate the language coverage and generalization abilities of the most common continuous sentence embeddings based on RNNs. We also propose a new embedding method based on arithmetic coding, AriEL, that is not data-driven and that efficiently encodes in continuous space any sentence from the CFG. We find that RNN-based embeddings underfit the training data and cover only a small subset of the language defined by the CFG. They also fail to learn the underlying CFG and generalize to unbiased sentences from that same CFG. We found that AriEL provides an insightful baseline.
Exploring the Suitability of BLE Beacons to Track Poacher Vehicles in Harsh Jungle Terrains
Venue: arXiv cs.NI 2019
Year: 2019

Our overall aim is focused on exploring whether we could use Bluetooth Low Energy (BLE) technology to track poacher vehicles in remote and rural areas such as Sabah, in Malaysia, especially deep inside the jungle terrain with little or no communication technologies exists. Tracking technologies are currently limited to relying on satellites or cellular towers, for environments that do not permit access to these signals, very few viable alternatives exist. This paper explores the use of BLE as a method to track vehicles. It works by mounting Bluetooth beacons beside a road and placing a receiver concealed somewhere inside the vehicle. As the vehicle drives past the beacon, the receiver and beacon are momentarily in range, the receiver then stores a unique ID from the beacon and when the vehicle is then in an area with GSM signal, an SMS is sent containing the unique IDs of the beacons that have been detected. This project is prototyped and tested in collaboration with the Danau Girang Field Centre in Sabah, Malaysia. The results offer insights for how effective BLE beacons are in a tracking situation for where the beacon and receiver are in range for a short period of time as well as how different obstructions will affect the range and strength of the signal. It is important to note that our objective is not to catch the poacher, instead to understand how they move around within jungle terrain, as we can use such information to develop a comprehensive plan against poaching activities.
uqSim: Scalable and Validated Simulation of Cloud Microservices
Venue: arXiv cs.DC 2019
Year: 2019

Current cloud services are moving away from monolithic designs and towards graphs of many loosely-coupled, single-concerned microservices. Microservices have several advantages, including speeding up development and deployment, allowing specialization of the software infrastructure, and helping with debugging and error isolation. At the same time they introduce several hardware and software challenges. Given that most of the performance and efficiency implications of microservices happen at scales larger than what is available outside production deployments, studying such effects requires designing the right simulation infrastructures. We present uqSim, a scalable and validated queueing network simulator designed specifically for interactive microservices. uqSim provides detailed intra- and inter-microservice models that allow it to faithfully reproduce the behavior of complex, many-tier applications. uqSim is also modular, allowing reuse of individual models across microservices and end-to-end applications. We have validated uqSim both against simple and more complex microservices graphs, and have shown that it accurately captures performance in terms of throughput and tail latency. Finally, we use uqSim to model the tail at scale effects of request fanout, and the performance impact of power management in latency-sensitive microservices.
Architectural Tricks for Deep Learning in Remote Photoplethysmography
Venue: arXiv cs.CV 2019
Year: 2019

Architectural improvements are studied for convolutional network performing estimation of heart rate (HR) values on color signal patches. Color signals are time series of color components averaged over facial regions recorded by webcams in two scenarios: Stationary (without motion of a person) and Mixed Motion (different motion patterns of a person). HR estimation problem is addressed as a classification task, where classes correspond to different heart rate values within the admissible range of [40; 125] bpm. Both adding convolutional filtering layers after fully connected layers and involving combined loss function where first component is a cross entropy and second is a squared error between the network output and smoothed one-hot vector, lead to better performance of HR estimation model in Stationary and Mixed Motion scenarios.
Information Update: TDMA or FDMA?
Venue: arXiv cs.IT 2019
Year: 2019

This paper studies information freshness in information update systems operated with TDMA and FDMA. Information freshness is characterized by a recently introduced metric, age of information (AoI), defined as the time elapsed since the generation of the last successfully received update. In an update system with multiple users sharing the same wireless channel to send updates to a common receiver, how to divide the channel among users affects information freshness. We investigate the AoI performances of two fundamental multiple access schemes, TDMA and FDMA. We first derive the time-averaged AoI by estimating the packet error rate of short update packets based on Gallager's random coding bound. For time-critical systems, we further define a new AoI metric, termed bounded AoI, which corresponds to an AoI threshold for the instantaneous AoI. Specifically, the instantaneous AoI is below the bounded AoI a large percentage of the time. We give a theoretical upper bound for bounded AoI. Our simulation results are consistent with our theoretical analysis. Although TDMA outperforms FDMA in terms of average AoI, FDMA is more robust against varying channel conditions since it gives a more stable bounded AoI across different received powers. Overall, our findings give insight to the design of practical multiple access systems with AoI requirements.
Hierarchical Contextualized Representation for Named Entity Recognition
Venue: arXiv cs.CL 2019
Year: 2019

Named entity recognition (NER) models are typically based on the architecture of Bi-directional LSTM (BiLSTM). The constraints of sequential nature and the modeling of single input prevent the full utilization of global information from larger scope, not only in the entire sentence, but also in the entire document (dataset). In this paper, we address these two deficiencies and propose a model augmented with hierarchical contextualized representation: sentence-level representation and document-level representation. In sentence-level, we take different contributions of words in a single sentence into consideration to enhance the sentence representation learned from an independent BiLSTM via label embedding attention mechanism. In document-level, the key-value memory network is adopted to record the document-aware information for each unique word which is sensitive to similarity of context information. Our two-level hierarchical contextualized representations are fused with each input token embedding and corresponding hidden state of BiLSTM, respectively. The experimental results on three benchmark NER datasets (CoNLL-2003 and Ontonotes 5.0 English datasets, CoNLL-2002 Spanish dataset) show that we establish new state-of-the-art results.
KLARAPTOR: A Tool for Dynamically Finding Optimal Kernel Launch Parameters Targeting CUDA Programs
Venue: arXiv cs.DC 2019
Year: 2019

In this paper we present KLARAPTOR (Kernel LAunch parameters RAtional Program estimaTOR), a new tool built on top of the LLVM Pass Framework and NVIDIA CUPTI API to dynamically determine the optimal values of kernel launch parameters of a CUDA program P. To be precise, we describe a novel technique to statically build (at the compile time of P) a so-called rational program R. Using a performance prediction model, and knowing particular data and hardware parameters of P at runtime, the program R can automatically and dynamically determine the values of launch parameters of P that will yield optimal performance. Our technique can be applied to parallel programs in general, as well as to generic performance prediction models which account for program and hardware parameters. We are particularly interested in programs targeting manycore accelerators. We have implemented and successfully tested our technique in the context of GPU kernels written in CUDA using the MWP-CWP performance prediction model.
Unfairness towards subjective opinions in Machine Learning
Venue: arXiv cs.LG 2019
Year: 2019

Despite the high interest for Machine Learning (ML) in academia and industry, many issues related to the application of ML to real-life problems are yet to be addressed. Here we put forward one limitation which arises from a lack of adaptation of ML models and datasets to specific applications. We formalise a new notion of unfairness as exclusion of opinions. We propose ways to quantify this unfairness, and aid understanding its causes through visualisation. These insights into the functioning of ML-based systems hint at methods to mitigate unfairness.
A Spoken Dialogue System for Spatial Question Answering in a Physical Blocks World
Venue: arXiv cs.AI 2019
Year: 2019

The blocks world is a classic toy domain that has long been used to build and test spatial reasoning systems. Despite its relative simplicity, tackling this domain in its full complexity requires the agent to exhibit a rich set of functional capabilities, ranging from vision to natural language understanding. There is currently a resurgence of interest in solving problems in such limited domains using modern techniques. In this work we tackle spatial question answering in a holistic way, using a vision system, speech input and output mediated by an animated avatar, a dialogue system that robustly interprets spatial queries, and a constraint solver that derives answers based on 3-D spatial modeling. The contributions of this work include a semantic parser that maps spatial questions into logical forms consistent with a general approach to meaning representation, a dialog manager based on a schema representation, and a constraint solver for spatial questions that provides answers in agreement with human perception. These and other components are integrated into a multi-modal human-computer interaction pipeline.
Rapid Uncertainty Propagation and Chance-Constrained Path Planning for Small Unmanned Aerial Vehicles
Venue: arXiv cs.RO 2019
Year: 2019

With the number of small Unmanned Aircraft Systems (sUAS) in the national airspace projected to increase in the next few years, there is growing interest in a traffic management system capable of handling the demands of this aviation sector. It is expected that such a system will involve trajectory prediction, uncertainty propagation, and path planning algorithms. In this work, we use linear covariance propagation in combination with a quadratic programming-based collision detection algorithm to rapidly validate declared flight plans. Additionally, these algorithms are combined with a Dynamic, Informed RRT* algorithm, resulting in a computationally efficient algorithm for chance-constrained path planning. Detailed numerical examples for both fixed-wing and quadrotor sUAS models are presented.
A Numerical Study of the Time of Extinction in a Class of Systems of Spiking Neurons
Venue: arXiv cs.NE 2019
Year: 2019

In this paper we present a numerical study of a mathematical model of spiking neurons introduced by Ferrari et al. in an article entitled Phase transition forinfinite systems of spiking neurons. In this model we have a countable number of neurons linked together in a network, each of them having a membrane potential taking value in the integers, and each of them spiking over time at a rate which depends on the membrane potential through some rate function $ϕ$. Beside being affected by a spike each neuron can also be affected by leaking. At each of these leak times, which occurs for a given neuron at a fixed rate $γ$, the membrane potential of the neuron concerned is spontaneously reset to $0$. A wide variety of versions of this model can be considered by choosing different graph structures for the network and different activation functions. It was rigorously shown that when the graph structure of the network is the one-dimensional lattice with a hard threshold for the activation function, this model presents a phase transition with respect to $γ$, and that it also presents a metastable behavior. By the latter we mean that in the sub-critical regime the re-normalized time of extinction converges to an exponential random variable of mean 1. It has also been proven that in the super-critical regime the renormalized time of extinction converges in probability to 1. Here, we investigate numerically a richer class of graph structures and activation functions. Namely we investigate the case of the two dimensional and the three dimensional lattices, as well as the case of a linear function and a sigmoid function for the activation function. We present numerical evidence that the result of metastability in the sub-critical regime holds for these graphs and activation functions as well as the convergence in probability to $1$ in the super-critical regime.
Word Embedding Algorithms as Generalized Low Rank Models and their Canonical Form
Venue: arXiv cs.CL 2019
Year: 2019

Word embedding algorithms produce very reliable feature representations of words that are used by neural network models across a constantly growing multitude of NLP tasks. As such, it is imperative for NLP practitioners to understand how their word representations are produced, and why they are so impactful. The present work presents the Simple Embedder framework, generalizing the state-of-the-art existing word embedding algorithms (including Word2vec (SGNS) and GloVe) under the umbrella of generalized low rank models. We derive that both of these algorithms attempt to produce embedding inner products that approximate pointwise mutual information (PMI) statistics in the corpus. Once cast as Simple Embedders, comparison of these models reveals that these successful embedders all resemble a straightforward maximum likelihood estimate (MLE) of the PMI parametrized by the inner product (between embeddings). This MLE induces our proposed novel word embedding model, Hilbert-MLE, as the canonical representative of the Simple Embedder framework. We empirically compare these algorithms with evaluations on 17 different datasets. Hilbert-MLE consistently observes second-best performance on every extrinsic evaluation (news classification, sentiment analysis, POS-tagging, and supersense tagging), while the first-best model depends varying on the task. Moreover, Hilbert-MLE consistently observes the least variance in results with respect to the random initialization of the weights in bidirectional LSTMs. Our empirical results demonstrate that Hilbert-MLE is a very consistent word embedding algorithm that can be reliably integrated into existing NLP systems to obtain high-quality results.
Towards Domain Adaptation from Limited Data for Question Answering Using Deep Neural Networks
Venue: arXiv cs.CL 2019
Year: 2019

This paper explores domain adaptation for enabling question answering (QA) systems to answer questions posed against documents in new specialized domains. Current QA systems using deep neural network (DNN) technology have proven effective for answering general purpose factoid-style questions. However, current general purpose DNN models tend to be ineffective for use in new specialized domains. This paper explores the effectiveness of transfer learning techniques for this problem. In experiments on question answering in the automobile manual domain we demonstrate that standard DNN transfer learning techniques work surprisingly well in adapting DNN models to a new domain using limited amounts of annotated training data in the new domain.
Detecting Driveable Area for Autonomous Vehicles
Venue: arXiv cs.CV 2019
Year: 2019

Autonomous driving is a challenging problem where there is currently an intense focus on research and development. Human drivers are forced to make thousands of complex decisions in a short amount of time,quickly processing their surroundings and moving factors. One of these aspects, recognizing regions on the road that are driveable is vital to the success of any autonomous system. This problem can be addressed with deep learning framed as a region proposal problem. Utilizing a Mask R-CNN trained on the Berkeley Deep Drive (BDD100k) dataset, we aim to see if recognizing driveable areas, while also differentiating between the car's direct (current) lane and alternative lanes is feasible.