OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic Normalizations as Bayesian Learning
Venue: arXiv cs.LG 2018
Year: 2018

In this work we investigate the reasons why Batch Normalization (BN) improves the generalization performance of deep networks. We argue that one major reason, distinguishing it from data-independent normalization methods, is randomness of batch statistics. This randomness appears in the parameters rather than in activations and admits an interpretation as a practical Bayesian learning. We apply this idea to other (deterministic) normalization techniques that are oblivious to the batch size. We show that their generalization performance can be improved significantly by Bayesian learning of the same form. We obtain test performance comparable to BN and, at the same time, better validation losses suitable for subsequent output uncertainty estimation through approximate Bayesian posterior.
Online Embedding Compression for Text Classification using Low Rank Matrix Factorization
Venue: arXiv cs.LG 2018
Year: 2018

Deep learning models have become state of the art for natural language processing (NLP) tasks, however deploying these models in production system poses significant memory constraints. Existing compression methods are either lossy or introduce significant latency. We propose a compression method that leverages low rank matrix factorization during training,to compress the word embedding layer which represents the size bottleneck for most NLP models. Our models are trained, compressed and then further re-trained on the downstream task to recover accuracy while maintaining the reduced size. Empirically, we show that the proposed method can achieve 90% compression with minimal impact in accuracy for sentence classification tasks, and outperforms alternative methods like fixed-point quantization or offline word embedding compression. We also analyze the inference time and storage space for our method through FLOP calculations, showing that we can compress DNN models by a configurable ratio and regain accuracy loss without introducing additional latency compared to fixed point quantization. Finally, we introduce a novel learning rate schedule, the Cyclically Annealed Learning Rate (CALR), which we empirically demonstrate to outperform other popular adaptive learning rate algorithms on a sentence classification benchmark.
Adaptive MTD Security using Markov Game Modeling
Venue: arXiv cs.CR 2018
Year: 2018

Large scale cloud networks consist of distributed networking and computing elements that process critical information and thus security is a key requirement for any environment. Unfortunately, assessing the security state of such networks is a challenging task and the tools used in the past by security experts such as packet filtering, firewall, Intrusion Detection Systems (IDS) etc., provide a reactive security mechanism. In this paper, we introduce a Moving Target Defense (MTD) based proactive security framework for monitoring attacks which lets us identify and reason about multi-stage attacks that target software vulnerabilities present in a cloud network. We formulate the multi-stage attack scenario as a two-player zero-sum Markov Game (between the attacker and the network administrator) on attack graphs. The rewards and transition probabilities are obtained by leveraging the expert knowledge present in the Common Vulnerability Scoring System (CVSS). Our framework identifies an attacker's optimal policy and places countermeasures to ensure that this attack policy is always detected, thus forcing the attacker to use a sub-optimal policy with higher cost.
Implicit Regularization of Stochastic Gradient Descent in Natural Language Processing: Observations and Implications
Venue: arXiv cs.CL 2018
Year: 2018

Deep neural networks with remarkably strong generalization performances are usually over-parameterized. Despite explicit regularization strategies are used for practitioners to avoid over-fitting, the impacts are often small. Some theoretical studies have analyzed the implicit regularization effect of stochastic gradient descent (SGD) on simple machine learning models with certain assumptions. However, how it behaves practically in state-of-the-art models and real-world datasets is still unknown. To bridge this gap, we study the role of SGD implicit regularization in deep learning systems. We show pure SGD tends to converge to minimas that have better generalization performances in multiple natural language processing (NLP) tasks. This phenomenon coexists with dropout, an explicit regularizer. In addition, neural network's finite learning capability does not impact the intrinsic nature of SGD's implicit regularization effect. Specifically, under limited training samples or with certain corrupted labels, the implicit regularization effect remains strong. We further analyze the stability by varying the weight initialization range. We corroborate these experimental findings with a decision boundary visualization using a 3-layer neural network for interpretation. Altogether, our work enables a deepened understanding on how implicit regularization affects the deep learning model and sheds light on the future study of the over-parameterized model's generalization ability.
A Multi-Robotic System for Environmental Cleaning
Venue: arXiv cs.RO 2018
Year: 2018

There is a lot of waste in an industrial environment that could cause harmful effects to both the products and the workers resulting in product defects, itchy eyes or chronic obstructive pulmonary disease, etc. While automative cleaning robots could be used, the environment is often too big for one robot to clean alone in addition to the fact that it does not have adequate stored dirt capacity. We present a multi-robotic dirt cleaning system algorithm for multiple automatic iRobot Creates teaming to efficiently clean an environment. Moreover, since some spaces in the environment are clean while others are dirty, our multi-robotic system possesses a path planning algorithm to allow the robot team to clean efficiently by spending more time on the area with higher dirt level. Overall, our multi-robotic system outperforms the single robot system in time efficiency while having almost the same total battery usage and cleaning efficiency result.
Design Verifiably Correct Model Patterns to Facilitate Modeling Medical Best Practice Guidelines with Statecharts (Technical Report)
Venue: arXiv cs.SE 2018
Year: 2018

Improving patient care safety is an ultimate objective for medical cyber-physical systems. A recent study shows that the patients' death rate can be significantly reduced by computerizing medical best practice guidelines. To facilitate the development of computerized medical best practice guidelines, statecharts are often used as a modeling tool because of their high resemblances to disease and treatment models and their capabilities to provide rapid prototyping and simulation for clinical validations. However, some implementations of statecharts, such as Yakindu statecharts, are priority-based and have synchronous execution semantics which makes it difficult to model certain functionalities that are essential in modeling medical guidelines, such as two-way communications and configurable execution orders. Rather than introducing new statechart elements or changing the statechart implementation's underline semantics, we use existing basic statechart elements to design model patterns for the commonly occurring issues. In particular, we show the design of model patterns for two-way communications and configurable execution orders and formally prove the correctness of these model patterns. We further use a simplified airway laser surgery scenario as a case study to demonstrate how the developed model patterns address the two-way communication and configurable execution order issues and their impact on validation and verification of medical safety properties.
On subexponential running times for approximating directed Steiner tree and related problems
Venue: arXiv cs.DS 2018
Year: 2018

This paper concerns proving almost tight (super-polynomial) running times, for achieving desired approximation ratios for various problems. To illustrate, the question we study, let us consider the Set-Cover problem with n elements and m sets. Now we specify our goal to approximate Set-Cover to a factor of (1-d)ln n, for a given parameter 0<d<1. What is the best possible running time for achieving such approximation? This question was answered implicitly in the work of Moshkovitz [Theory of Computing, 2015]: Assuming both the Projection Games Conjecture (PGC) and the Exponential-Time Hypothesis (ETH), any ((1-d) ln n)-approximation algorithm for Set-Cover must run in time >= 2^{n^{c d}}, for some constant 0<d<1. We study the questions along this line. First, we show that under ETH and PGC any ((1-d) \ln n)-approximation for Set-Cover requires 2^{n^{d}}-time. This (almost) matches the running time of 2^{O(n^d)} for approximating Set-Cover to a factor (1-d) ln n by Cygan et al. [IPL, 2009]. Our result is tight up to the constant multiplying the n^{d} terms in the exponent. This lower bound applies to all of its generalizations, e.g., Group Steiner Tree (GST), Directed Steiner (DST), Covering Steiner Tree (CST), Connected Polymatroid (CP). We also show that in almost exponential time, these problems reduce to Set-Cover: We show (1-d)ln n approximation algorithms for all these problems that run in time 2^{n^{d \log n } poly(m). We also study log^{2-d}n approximation for GST. Chekuri-Pal [FOCS, 2005] showed that GST admits (log^{2-d}n)-approximation in time exp(2^{log^{d+o(1)}n}), for any 0 < d < 1. We show the lower bound of GST: any (log^{2-d}n)-approximation for GST must run in time >= exp((1+o(1)){log^{d-c}n}), for any c>0, unless the ETH is false. Our result follows by analyzing the work of Halperin and Krauthgamer [STOC, 2003]. The same lower and upper bounds hold for CST.
Efficient Metropolitan Traffic Prediction Based on Graph Recurrent Neural Network
Venue: arXiv cs.AI 2018
Year: 2018

Traffic prediction is a fundamental and vital task in Intelligence Transportation System (ITS), but it is very challenging to get high accuracy while containing low computational complexity due to the spatiotemporal characteristics of traffic flow, especially under the metropolitan circumstances. In this work, a new topological framework, called Linkage Network, is proposed to model the road networks and present the propagation patterns of traffic flow. Based on the Linkage Network model, a novel online predictor, named Graph Recurrent Neural Network (GRNN), is designed to learn the propagation patterns in the graph. It could simultaneously predict traffic flow for all road segments based on the information gathered from the whole graph, which thus reduces the computational complexity significantly from O(nm) to O(n+m), while keeping the high accuracy. Moreover, it can also predict the variations of traffic trends. Experiments based on real-world data demonstrate that the proposed method outperforms the existing prediction methods.
Rationality-proof consensus: extended abstract
Venue: arXiv cs.DC 2018
Year: 2018

Blockchain systems benefit from lessons in prior art such as fault tolerance, distributed systems, peer-to-peer systems, and game theory. In this paper we argue that blockchain algorithms should tolerate both rational (self-interested) users and Byzantine (malicious) ones, rather than assuming all non-Byzantine users are altruistic and follow the protocols blindly. Such algorithms are called BAR-tolerant [1]. To design a BAR-tolerant system, one can follow these three steps: clearly define the utility function for the rational users, prove the algorithm is such that there is no benefit from unilaterally deviating (that is, it's a Byzantine Nash Equilibrium), then prove the algorithm correct assuming the rational actors follow the protocol. We present an example attack by rational users: the gatekeeping attack, where members of a system selfishly decide to prevent newcomers from joining. This attack may affect any stake-based system where the existing members prevent newcomers from making a stake, and essentially form a cartel. We then sketch a BAR-tolerant consensus protocol for blockchain that can defend against this attack. It relies on a strict order to decide who gets to propose a new block (so there's no need to race to solve a crypto puzzle) and it relies on hardware ID tokens to make sure every computer is only represented at most once as a block proposer to mitigate Sybil attacks. It also defends against the gatekeeper attack. The BAR-tolerant approach is naturally also applicable to other blockchain algorithms.
Confiding in and Listening to Virtual Agents: The Effect of Personality
Venue: arXiv cs.AI 2018
Year: 2018

We present an intelligent virtual interviewer that engages with a user in a text-based conversation and automatically infers the user's psychological traits, such as personality. We investigate how the personality of a virtual interviewer influences a user's behavior from two perspectives: the user's willingness to confide in, and listen to, a virtual interviewer. We have developed two virtual interviewers with distinct personalities and deployed them in a real-world recruiting event. We present findings from completed interviews with 316 actual job applicants. Notably, users are more willing to confide in and listen to a virtual interviewer with a serious, assertive personality. Moreover, users' personality traits, inferred from their chat text, influence their perception of a virtual interviewer, and their willingness to confide in and listen to a virtual interviewer. Finally, we discuss the implications of our work on building hyper-personalized, intelligent agents based on user traits.
Information Geometry of Sensor Configuration
Venue: arXiv cs.IT 2018
Year: 2018

In problems of parameter estimation from sensor data, the Fisher Information provides a measure of the performance of the sensor; effectively, in an infinitesimal sense, how much information about the parameters can be obtained from the measurements. From the geometric viewpoint, it is a Riemannian metric on the manifold of parameters of the observed system. In this paper we consider the case of parameterized sensors and answer the question, "How best to reconfigure a sensor (vary the parameters of the sensor) to optimize the information collected?" A change in the sensor parameters results in a corresponding change to the metric. We show that the change in information due to reconfiguration exactly corresponds to the natural metric on the infinite dimensional space of Riemannian metrics on the parameter manifold, restricted to finite-dimensional sub-manifold determined by the sensor parameters. The distance measure on this configuration manifold is shown to provide optimal, dynamic sensor reconfiguration based on an information criterion. Geodesics on the configuration manifold are shown to optimize the information gain but only if the change is made at a certain rate. An example of configuring two bearings-only sensors to optimally locate a target is developed in detail to illustrate the mathematical machinery, with Fast-Marching methods employed to efficiently calculate the geodesics and illustrate the practicality of using this approach.
Deep Optimisation: Solving Combinatorial Optimisation Problems using Deep Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Deep Optimisation (DO) combines evolutionary search with Deep Neural Networks (DNNs) in a novel way - not for optimising a learning algorithm, but for finding a solution to an optimisation problem. Deep learning has been successfully applied to classification, regression, decision and generative tasks and in this paper we extend its application to solving optimisation problems. Model Building Optimisation Algorithms (MBOAs), a branch of evolutionary algorithms, have been successful in combining machine learning methods and evolutionary search but, until now, they have not utilised DNNs. DO is the first algorithm to use a DNN to learn and exploit the problem structure to adapt the variation operator (changing the neighbourhood structure of the search process). We demonstrate the performance of DO using two theoretical optimisation problems within the MAXSAT class. The Hierarchical Transformation Optimisation Problem (HTOP) has controllable deep structure that provides a clear evaluation of how DO works and why using a layerwise technique is essential for learning and exploiting problem structure. The Parity Modular Constraint Problem (MCparity) is a simplistic example of a problem containing higher-order dependencies (greater than pairwise) which DO can solve and state of the art MBOAs cannot. Further, we show that DO can exploit deep structure in TSP instances. Together these results show that there exists problems that DO can find and exploit deep problem structure that other algorithms cannot. Making this connection between DNNs and optimisation allows for the utilisation of advanced tools applicable to DNNs that current MBOAs are unable to use.
Adversarial Training of End-to-end Speech Recognition Using a Criticizing Language Model
Venue: arXiv cs.CL 2018
Year: 2018

In this paper we proposed a novel Adversarial Training (AT) approach for end-to-end speech recognition using a Criticizing Language Model (CLM). In this way the CLM and the automatic speech recognition (ASR) model can challenge and learn from each other iteratively to improve the performance. Since the CLM only takes the text as input, huge quantities of unpaired text data can be utilized in this approach within end-to-end training. Moreover, AT can be applied to any end-to-end ASR model using any deep-learning-based language modeling frameworks, and compatible with any existing end-to-end decoding method. Initial results with an example experimental setup demonstrated the proposed approach is able to gain consistent improvements efficiently from auxiliary text data under different scenarios.
Listen to Dance: Music-driven choreography generation using Autoregressive Encoder-Decoder Network
Venue: arXiv cs.MM 2018
Year: 2018

Automatic choreography generation is a challenging task because it often requires an understanding of two abstract concepts - music and dance - which are realized in the two different modalities, namely audio and video, respectively. In this paper, we propose a music-driven choreography generation system using an auto-regressive encoder-decoder network. To this end, we first collect a set of multimedia clips that include both music and corresponding dance motion. We then extract the joint coordinates of the dancer from video and the mel-spectrogram of music from audio, and train our network using music-choreography pairs as input. Finally, a novel dance motion is generated at the inference time when only music is given as an input. We performed a user study for a qualitative evaluation of the proposed method, and the results show that the proposed model is able to generate musically meaningful and natural dance movements given an unheard song.
Classification of Findings with Localized Lesions in Fundoscopic Images using a Regionally Guided CNN
Venue: arXiv cs.CV 2018
Year: 2018

Fundoscopic images are often investigated by ophthalmologists to spot abnormal lesions to make diagnoses. Recent successes of convolutional neural networks are confined to diagnoses of few diseases without proper localization of lesion. In this paper, we propose an efficient annotation method for localizing lesions and a CNN architecture that can classify an individual finding and localize the lesions at the same time. Also, we introduce a new loss function to guide the network to learn meaningful patterns with the guidance of the regional annotations. In experiments, we demonstrate that our network performed better than the widely used network and the guidance loss helps achieve higher AUROC up to 4.1% and superior localization capability.
Quantum Structures in Human Decision-making: Towards Quantum Expected Utility
Venue: arXiv cs.AI 2018
Year: 2018

{\it Ellsberg thought experiments} and empirical confirmation of Ellsberg preferences pose serious challenges to {\it subjective expected utility theory} (SEUT). We have recently elaborated a quantum-theoretic framework for human decisions under uncertainty which satisfactorily copes with the Ellsberg paradox and other puzzles of SEUT. We apply here the quantum-theoretic framework to the {\it Ellsberg two-urn example}, showing that the paradox can be explained by assuming a state change of the conceptual entity that is the object of the decision ({\it decision-making}, or {\it DM}, {\it entity}) and representing subjective probabilities by quantum probabilities. We also model the empirical data we collected in a DM test on human participants within the theoretic framework above. The obtained results are relevant, as they provide a line to model real life, e.g., financial and medical, decisions that show the same empirical patterns as the two-urn experiment.
Competitively Chasing Convex Bodies
Venue: arXiv cs.DS 2018
Year: 2018

Let $\mathcal{F}$ be a family of sets in some metric space. In the $\mathcal{F}$-chasing problem, an online algorithm observes a request sequence of sets in $\mathcal{F}$ and responds (online) by giving a sequence of points in these sets. The movement cost is the distance between consecutive such points. The competitive ratio is the worst case ratio (over request sequences) between the total movement of the online algorithm and the smallest movement one could have achieved by knowing in advance the request sequence. The family $\mathcal{F}$ is said to be chaseable if there exists an online algorithm with finite competitive ratio. In 1991, Linial and Friedman conjectured that the family of convex sets in Euclidean space is chaseable. We prove this conjecture.
Probabilistic Programming with Densities in SlicStan: Efficient, Flexible and Deterministic
Venue: arXiv cs.PL 2018
Year: 2018

Stan is a probabilistic programming language that has been increasingly used for real-world scalable projects. However, to make practical inference possible, the language sacrifices some of its usability by adopting a block syntax, which lacks compositionality and flexible user-defined functions. Moreover, the semantics of the language has been mainly given in terms of intuition about implementation, and has not been formalised. This paper provides a formal treatment of the Stan language, and introduces the probabilistic programming language SlicStan --- a compositional, self-optimising version of Stan. Our main contributions are: (1) the formalisation of a core subset of Stan through an operational density-based semantics; (2) the design and semantics of the Stan-like language SlicStan, which facilities better code reuse and abstraction through its compositional syntax, more flexible functions, and information-flow type system; and (3) a formal, semantic-preserving procedure for translating SlicStan to Stan.