OpenRaiser/Intern-Atlas huggingface dataset:
Do We Need Neural Models to Explain Human Judgments of Acceptability?
Venue: arXiv cs.CL 2019
Year: 2019

Native speakers can judge whether a sentence is an acceptable instance of their language. Acceptability provides a means of evaluating whether computational language models are processing language in a human-like manner. We test the ability of computational language models, simple language features, and word embeddings to predict native English speakers judgments of acceptability on English-language essays written by non-native speakers. We find that much of the sentence acceptability variance can be captured by a combination of features including misspellings, word order, and word similarity (Pearson's r = 0.494). While predictive neural models fit acceptability judgments well (r = 0.527), we find that a 4-gram model with statistical smoothing is just as good (r = 0.528). Thanks to incorporating a count of misspellings, our 4-gram model surpasses both the previous unsupervised state-of-the art (Lau et al., 2015; r = 0.472), and the average non-expert native speaker (r = 0.46). Our results demonstrate that acceptability is well captured by n-gram statistics and simple language features.
Variable Population Memetic Search: A Case Study on the Critical Node Problem
Venue: arXiv cs.NE 2019
Year: 2019

Population-based memetic algorithms have been successfully applied to solve many difficult combinatorial problems. Often, a population of fixed size was used in such algorithms to record some best solutions sampled during the search. However, given the particular features of the problem instance under consideration, a population of variable size would be more suitable to ensure the best search performance possible. In this work, we propose variable population memetic search (VPMS), where a strategic population sizing mechanism is used to dynamically adjust the population size during the memetic search process. Our VPMS approach starts its search from a small population of only two solutions to focus on exploitation, and then adapts the population size according to the search status to continuously influence the balancing between exploitation and exploration. We illustrate an application of the VPMS approach to solve the challenging critical node problem (CNP). We show that the VPMS algorithm integrating a variable population, an effective local optimization procedure (called diversified late acceptance search) and a backbone-based crossover operator performs very well compared to state-of-the-art CNP algorithms. The algorithm is able to discover new upper bounds for 13 instances out of the 42 popular benchmark instances, while matching 23 previous best-known upper bounds.
Barracuda: The Power of $\ell$-polling in Proof-of-Stake Blockchains
Venue: arXiv cs.CR 2019
Year: 2019

A blockchain is a database of sequential events that is maintained by a distributed group of nodes. A key consensus problem in blockchains is that of determining the next block (data element) in the sequence. Many blockchains address this by electing a new node to propose each new block. The new block is (typically) appended to the tip of the proposer's local blockchain, and subsequently broadcast to the rest of the network. Without network delay (or adversarial behavior), this procedure would give a perfect chain, since each proposer would have the same view of the blockchain. A major challenge in practice is forking. Due to network delays, a proposer may not yet have the most recent block, and may, therefore, create a side chain that branches from the middle of the main chain. Forking reduces throughput, since only one a single main chain can survive, and all other blocks are discarded. We propose a new P2P protocol for blockchains called Barracuda, in which each proposer, prior to proposing a block, polls $\ell$ other nodes for their local blocktree information. Under a stochastic network model, we prove that this lightweight primitive improves throughput as if the entire network were a factor of $\ell$ faster. We provide guidelines on how to implement Barracuda in practice, guaranteeing robustness against several real-world factors.
Supporting On-Stack Replacement in Unstructured Languages by Loop Reconstruction and Extraction
Venue: arXiv cs.PL 2019
Year: 2019

On-stack replacement (OSR) is a common technique employed by dynamic compilers to reduce program warm-up time. OSR allows switching from interpreted to compiled code during the execution of this code. The main targets are long running loops, which need to be represented explicitly, with dedicated information about condition and body, to be optimized at run time. Bytecode interpreters, however, represent control flow implicitly via unstructured jumps and thus do not exhibit the required high-level loop representation. To enable OSR also for jump-based - often called unstructured - languages, we propose the partial reconstruction of loops in order to explicitly represent them in a bytecode interpreter. Besides an outline of the general idea, we implemented our approach in Sulong, a bytecode interpreter for LLVM bitcode, which allows the execution of C/C++. We conducted an evaluation with a set of C benchmarks, which showed speed-ups in warm-up of up to 9x for certain benchmarks. This facilitates execution of programs with long-running loops in rarely called functions, which would yield significant slowdown without OSR. While shown with a prototype implementation, the overall idea of our approach is generalizable for all bytecode interpreters.
Slices of Attention in Asynchronous Video Job Interviews
Venue: arXiv cs.CV 2019
Year: 2019

The impact of non verbal behaviour in a hiring decision remains an open question. Investigating this question is important, as it could provide a better understanding on how to train candidates for job interviews and make recruiters be aware of influential non verbal behaviour. This research has recently been accelerated due to the development of tools for the automatic analysis of social signals, and the emergence of machine learning methods. However, these studies are still mainly based on hand engineered features, which imposes a limit to the discovery of influential social signals. On the other side, deep learning methods are a promising tool to discover complex patterns without the necessity of feature engineering. In this paper, we focus on studying influential non verbal social signals in asynchronous job video interviews that are discovered by deep learning methods. We use a previously published deep learning system that aims at inferring the hirability of a candidate with regard to a sequence of interview questions. One particularity of this system is the use of attention mechanisms, which aim at identifying the relevant parts of an answer. Thus, information at a fine-grained temporal level could be extracted using global (at the interview level) annotations on hirability. While most of the deep learning systems use attention mechanisms to offer a quick visualization of slices when a rise of attention occurs, we perform an in-depth analysis to understand what happens during these moments. First, we propose a methodology to automatically extract slices where there is a rise of attention (attention slices). Second, we study the content of attention slices by comparing them with randomly sampled slices. Finally, we show that they bear significantly more information for hirability than randomly sampled slices.
Optimal Policies of Advanced Sleep Modes for Energy-Efficient 5G networks
Venue: arXiv cs.IT 2019
Year: 2019

We study in this paper optimal control strategy for Advanced Sleep Modes (ASM) in 5G networks. ASM correspond to different levels of sleep modes ranging from deactivation of some components of the base station for several micro-seconds to switching off of almost all of them for one second or more. ASMs are made possible in 5G networks thanks to the definition of so-called lean carrier radio access which allows for configurable signaling periodicities. We model such a system using Markov Decision Processes (MDP) and find optimal sleep policy in terms of a trade-off between saved power consumption versus additional incurred delay for user traffic which has to wait for the network components to be woken-up and serve it. Eventually, for the system not to oscillate between sleep levels, we add a switching component in the cost function and show its impact on the energy reduction versus delay trade-off.
A Corpus for Automatic Readability Assessment and Text Simplification of German
Venue: arXiv cs.CL 2019
Year: 2019

In this paper, we present a corpus for use in automatic readability assessment and automatic text simplification of German. The corpus is compiled from web sources and consists of approximately 211,000 sentences. As a novel contribution, it contains information on text structure, typography, and images, which can be exploited as part of machine learning approaches to readability assessment and text simplification. The focus of this publication is on representing such information as an extension to an existing corpus standard.
Using Quantifier Elimination to Enhance the Safety Assurance of Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Advances in the field of Machine Learning and Deep Neural Networks (DNNs) has enabled rapid development of sophisticated and autonomous systems. However, the inherent complexity to rigorously assure the safe operation of such systems hinders their real-world adoption in safety-critical domains such as aerospace and medical devices. Hence, there is a surge in interest to explore the use of advanced mathematical techniques such as formal methods to address this challenge. In fact, the initial results of such efforts are promising. Along these lines, we propose the use of quantifier elimination (QE) - a formal method technique, as a complimentary technique to the state-of-the-art static analysis and verification procedures. Using an airborne collision avoidance DNN as a case example, we illustrate the use of QE to formulate the precise range forward propagation through a network as well as analyze its robustness. We discuss the initial results of this ongoing work and explore the future possibilities of extending this approach and/or integrating it with other approaches to perform advanced safety assurance of DNNs.
Polar Codes and Their Quantum-Domain Counterparts
Venue: arXiv cs.IT 2019
Year: 2019

Arikan's polar codes are capable of achieving the Shannon's capacity at a low encoding and decoding complexity, while inherently supporting rate adaptation. By virtue of these attractive features, polar codes have provided fierce competition to both the turbo as well as the Low Density Parity Check (LDPC) codes, making its way into the 5G New Radio (NR). Realizing the significance of polar codes, in this paper we provide a comprehensive survey of polar codes, highlighting the major milestones achieved in the last decade. Furthermore, we also provide tutorial insights into the polar encoder, decoders as well as the code construction methods. We also extend our discussions to quantum polar codes with an emphasis on the underlying quantum-to-classical isomorphism and the syndrome-based quantum polar codes.
Gaze Estimation for Assisted Living Environments
Venue: arXiv cs.CV 2019
Year: 2019

Effective assisted living environments must be able to perform inferences on how their occupants interact with one another as well as with surrounding objects. To accomplish this goal using a vision-based automated approach, multiple tasks such as pose estimation, object segmentation and gaze estimation must be addressed. Gaze direction in particular provides some of the strongest indications of how a person interacts with the environment. In this paper, we propose a simple neural network regressor that estimates the gaze direction of individuals in a multi-camera assisted living scenario, relying only on the relative positions of facial keypoints collected from a single pose estimation model. To handle cases of keypoint occlusion, our model exploits a novel confidence gated unit in its input layer. In addition to the gaze direction, our model also outputs an estimation of its own prediction uncertainty. Experimental results on a public benchmark demonstrate that our approach performs on pair with a complex, dataset-specific baseline, while its uncertainty predictions are highly correlated to the actual angular error of corresponding estimations. Finally, experiments on images from a real assisted living environment demonstrate the higher suitability of our model for its final application.
An Introduction to Quaternion-Valued Recurrent Projection Neural Networks
Venue: arXiv cs.NE 2019
Year: 2019

Hypercomplex-valued neural networks, including quaternion-valued neural networks, can treat multi-dimensional data as a single entity. In this paper, we introduce the quaternion-valued recurrent projection neural networks (QRPNNs). Briefly, QRPNNs are obtained by combining the non-local projection learning with the quaternion-valued recurrent correlation neural network (QRCNNs). We show that QRPNNs overcome the cross-talk problem of QRCNNs. Thus, they are appropriate to implement associative memories. Furthermore, computational experiments reveal that QRPNNs exhibit greater storage capacity and noise tolerance than their corresponding QRCNNs.
On the Impact of Ground Sound
Venue: arXiv cs.SD 2019
Year: 2019

Rigid-body impact sound synthesis methods often omit the ground sound. In this paper we analyze an idealized ground-sound model based on an elastodynamic halfspace, and use it to identify scenarios wherein ground sound is perceptually relevant versus when it is masked by the impacting object's modal sound or transient acceleration noise. Our analytical model gives a smooth, closed-form expression for ground surface acceleration, which we can then use in the Rayleigh integral or in an "acoustic shader" for a finite-difference time-domain wave simulation. We find that when modal sound is inaudible, ground sound is audible in scenarios where a dense object impacts a soft ground and scenarios where the impact point has a low elevation angle to the listening point.
Cross-lingual Dependency Parsing with Unlabeled Auxiliary Languages
Venue: arXiv cs.CL 2019
Year: 2019

Cross-lingual transfer learning has become an important weapon to battle the unavailability of annotated resources for low-resource languages. One of the fundamental techniques to transfer across languages is learning \emph{language-agnostic} representations, in the form of word embeddings or contextual encodings. In this work, we propose to leverage unannotated sentences from auxiliary languages to help learning language-agnostic representations. Specifically, we explore adversarial training for learning contextual encoders that produce invariant representations across languages to facilitate cross-lingual transfer. We conduct experiments on cross-lingual dependency parsing where we train a dependency parser on a source language and transfer it to a wide range of target languages. Experiments on 28 target languages demonstrate that adversarial training significantly improves the overall transfer performances under several different settings. We conduct a careful analysis to evaluate the language-agnostic representations resulted from adversarial training.
Forecasting Future Action Sequences with Neural Memory Networks
Venue: arXiv cs.CV 2019
Year: 2019

We propose a novel neural memory network based framework for future action sequence forecasting. This is a challenging task where we have to consider short-term, within sequence relationships as well as relationships in between sequences, to understand how sequences of actions evolve over time. To capture these relationships effectively, we introduce neural memory networks to our modelling scheme. We show the significance of using two input streams, the observed frames and the corresponding action labels, which provide different information cues for our prediction task. Furthermore, through the proposed method we effectively map the long-term relationships among individual input sequences through separate memory modules, which enables better fusion of the salient features. Our method outperforms the state-of-the-art approaches by a large margin on two publicly available datasets: Breakfast and 50 Salads.
Intelligent Policing Strategy for Traffic Violation Prevention
Venue: arXiv cs.AI 2019
Year: 2019

Police officer presence at an intersection discourages a potential traffic violator from violating the law. It also alerts the motorists' consciousness to take precaution and follow the rules. However, due to the abundant intersections and shortage of human resources, it is not possible to assign a police officer to every intersection. In this paper, we propose an intelligent and optimal policing strategy for traffic violation prevention. Our model consists of a specific number of targeted intersections and two police officers with no prior knowledge on the number of the traffic violations in the designated intersections. At each time interval, the proposed strategy, assigns the two police officers to different intersections such that at the end of the time horizon, maximum traffic violation prevention is achieved. Our proposed methodology adapts the PROLA (Play and Random Observe Learning Algorithm) algorithm [1] to achieve an optimal traffic violation prevention strategy. Finally, we conduct a case study to evaluate and demonstrate the performance of the proposed method.
CNN-based RGB-D Salient Object Detection: Learn, Select and Fuse
Venue: arXiv cs.CV 2019
Year: 2019

The goal of this work is to present a systematic solution for RGB-D salient object detection, which addresses the following three aspects with a unified framework: modal-specific representation learning, complementary cue selection and cross-modal complement fusion. To learn discriminative modal-specific features, we propose a hierarchical cross-modal distillation scheme, in which the well-learned source modality provides supervisory signals to facilitate the learning process for the new modality. To better extract the complementary cues, we formulate a residual function to incorporate complements from the paired modality adaptively. Furthermore, a top-down fusion structure is constructed for sufficient cross-modal interactions and cross-level transmissions. The experimental results demonstrate the effectiveness of the proposed cross-modal distillation scheme in zero-shot saliency detection and pre-training on a new modality, as well as the advantages in selecting and fusing cross-modal/cross-level complements.
Automated Verification of Integer Overflow
Venue: arXiv cs.PL 2019
Year: 2019

Integer overflow accounts for one of the major source of bugs in software. Verification systems typically assume a well defined underlying semantics for various integer operations and do not explicitly check for integer overflow in programs. In this paper we present a specification mechanism for expressing integer overflow. We develop an automated procedure for integer overflow checking during program verification. We have implemented a prototype integer overflow checker and tested it on a benchmark consisting of already verified programs (over 14k LOC). We have found 43 bugs in these programs due to integer overflow.
Simple proof of Parikh's theorem a la Takahashi
Venue: arXiv cs.FL 2019
Year: 2019

In this report we describe a simple proof of Parikh's theorem a la Takahashi, based on a decomposition of derivation trees. The idea of decomposition is appeared in her master's thesis written in 1970.
Simulating Crowds in Real Time with Agent-Based Modelling and a Particle Filter
Venue: arXiv cs.MA 2019
Year: 2019

Agent-based modelling is a valuable approach for systems whose behaviour is driven by the interactions between distinct entities. They have shown particular promise as a means of modelling crowds of people in streets, public transport terminals, stadiums, etc. However, the methodology faces a fundamental difficulty: there are no established mechanisms for dynamically incorporating real-time data into models. This limits simulations that are inherently dynamic, such as pedestrian movements, to scenario testing of, for example, the potential impacts of new architectural configurations on movements. This paper begins to address this fundamental gap by demonstrating how a particle filter could be used to incorporate real data into an agent-based model of pedestrian movements at run time. The experiments show that it is indeed possible to use a particle filter to perform online (real time) model optimisation. However, as the number of agents increases, the number of individual particles (and hence the computational complexity) required increases exponentially. By laying the groundwork for the real-time simulation of crowd movements, this paper has implications for the management of complex environments (both nationally and internationally) such as transportation hubs, hospitals, shopping centres, etc.
Retro-Actions: Learning 'Close' by Time-Reversing 'Open' Videos
Venue: arXiv cs.CV 2019
Year: 2019

We investigate video transforms that result in class-homogeneous label-transforms. These are video transforms that consistently maintain or modify the labels of all videos in each class. We propose a general approach to discover invariant classes, whose transformed examples maintain their label; pairs of equivariant classes, whose transformed examples exchange their labels; and novel-generating classes, whose transformed examples belong to a new class outside the dataset. Label transforms offer additional supervision previously unexplored in video recognition benefiting data augmentation and enabling zero-shot learning opportunities by learning a class from transformed videos of its counterpart. Amongst such video transforms, we study horizontal-flipping, time-reversal, and their composition. We highlight errors in naively using horizontal-flipping as a form of data augmentation in video. Next, we validate the realism of time-reversed videos through a human perception study where people exhibit equal preference for forward and time-reversed videos. Finally, we test our approach on two datasets, Jester and Something-Something, evaluating the three video transforms for zero-shot learning and data augmentation. Our results show that gestures such as zooming in can be learnt from zooming out in a zero-shot setting, as well as more complex actions with state transitions such as digging something out of something from burying something in something.