OpenRaiser/Intern-Atlas huggingface dataset:
Grammar-based Neural Text-to-SQL Generation
Venue: arXiv cs.CL 2019
Year: 2019

The sequence-to-sequence paradigm employed by neural text-to-SQL models typically performs token-level decoding and does not consider generating SQL hierarchically from a grammar. Grammar-based decoding has shown significant improvements for other semantic parsing tasks, but SQL and other general programming languages have complexities not present in logical formalisms that make writing hierarchical grammars difficult. We introduce techniques to handle these complexities, showing how to construct a schema-dependent grammar with minimal over-generation. We analyze these techniques on ATIS and Spider, two challenging text-to-SQL datasets, demonstrating that they yield 14--18\% relative reductions in error.
Identifying Cache-Based Side Channels through Secret-Augmented Abstract Interpretation
Venue: arXiv cs.CR 2019
Year: 2019

Cache-based side channels enable a dedicated attacker to reveal program secrets by measuring the cache access patterns. Practical attacks have been shown against real-world crypto algorithm implementations such as RSA, AES, and ElGamal. By far, identifying information leaks due to cache-based side channels, either in a static or dynamic manner, remains a challenge: the existing approaches fail to offer high precision, full coverage, and good scalability simultaneously, thus impeding their practical use in real-world scenarios. In this paper, we propose a novel static analysis method on binaries to detect cache-based side channels. We use abstract interpretation to reason on program states with respect to abstract values at each program point. To make such abstract interpretation scalable to real-world cryptosystems while offering high precision and full coverage, we propose a novel abstract domain called the Secret-Augmented Symbolic domain (SAS). SAS tracks program secrets and dependencies on them for precision, while it tracks only coarse-grained public information for scalability. We have implemented the proposed technique into a practical tool named CacheS and evaluated it on the implementations of widely-used cryptographic algorithms in real-world crypto libraries, including Libgcrypt, OpenSSL, and mbedTLS. CacheS successfully confirmed a total of 154 information leaks reported by previous research and 54 leaks that were previously unknown. We have reported our findings to the developers. And they confirmed that many of those unknown information leaks do lead to potential side channels.
Reducing Tail Latency via Safe and Simple Duplication
Venue: arXiv cs.NI 2019
Year: 2019

Duplication can be a powerful strategy for overcoming stragglers in cloud services, but is often used conservatively because of the risk of overloading the system. We present duplicate-aware scheduling or DAS, which makes duplication safe and easy to use, by leveraging the two well-known primitives of prioritization and purging. To support DAS across diverse layers of a cloud system (e.g., network, storage, etc), we propose the D-Stage abstraction, which decouples the duplication policy from the mechanism, and facilitates working with legacy layers of a system. Using this abstraction, we evaluate the benefits of DAS for two data parallel applications (HDFS, an in-memory workload generator) and a network function (snort-based IDS cluster). Our experiments on the public cloud and Emulab show that DAS is safe to use, and the tail latency improvement holds across a wide range of workloads
Efficient Multiway Hash Join on Reconfigurable Hardware
Venue: arXiv cs.DB 2019
Year: 2019

We propose the algorithms for performing multiway joins using a new type of coarse grain reconfigurable hardware accelerator~-- ``Plasticine''~-- that, compared with other accelerators, emphasizes high compute capability and high on-chip communication bandwidth. Joining three or more relations in a single step, i.e. multiway join, is efficient when the join of any two relations yields too large an intermediate relation. We show at least 200X speedup for a sequence of binary hash joins execution on Plasticine over CPU. We further show that in some realistic cases, a Plasticine-like accelerator can make 3-way joins more efficient than a cascade of binary hash joins on the same hardware, by a factor of up to 45X.
Learning Equilibria of Simulation-Based Games
Venue: arXiv cs.GT 2019
Year: 2019

We tackle a fundamental problem in empirical game-theoretic analysis (EGTA), that of learning equilibria of simulation-based games. Such games cannot be described in analytical form; instead, a black-box simulator can be queried to obtain noisy samples of utilities. Our approach to EGTA is in the spirit of probably approximately correct learning. We design algorithms that learn so-called empirical games, which uniformly approximate the utilities of simulation-based games with finite-sample guarantees. These algorithms can be instantiated with various concentration inequalities. Building on earlier work, we first apply Hoeffding's bound, but as the size of the game grows, this bound eventually becomes statistically intractable; hence, we also use the Rademacher complexity. Our main results state: with high probability, all equilibria of the simulation-based game are approximate equilibria in the empirical game (perfect recall); and conversely, all approximate equilibria in the empirical game are approximate equilibria in the simulation-based game (approximately perfect precision). We evaluate our algorithms on several synthetic games, showing that they make frugal use of data, produce accurate estimates more often than the theory predicts, and are robust to different forms of noise.
Using Latent Variable Models to Observe Academic Pathways
Venue: arXiv cs.LG 2019
Year: 2019

Understanding large-scale patterns in student course enrollment is a problem of great interest to university administrators and educational researchers. Yet important decisions are often made without a good quantitative framework of the process underlying student choices. We propose a probabilistic approach to modelling course enrollment decisions, drawing inspiration from multilabel classification and mixture models. We use ten years of anonymized student transcripts from a large university to construct a Gaussian latent variable model that learns the joint distribution over course enrollments. The models allow for a diverse set of inference queries and robustness to data sparsity. We demonstrate the efficacy of this approach in comparison to others, including deep learning architectures, and demonstrate its ability to infer the underlying student interests that guide enrollment decisions.
Comparative Analysis of State-of-the-Art EDoS Mitigation Techniques in Cloud Computing Environment
Venue: arXiv cs.CR 2019
Year: 2019

A new variant of the DDoS attack, called Economic Denial of Sustainability attack has emerged. Since the cloud service is based on the pay-per-use model, the EDoS attack endeavors to scale up the resource usage over time to the point the purveyor of the server is financially incapable of sustaining the service due to the incurred unaffordable usage charges. The implication of the EDoS attack is a major security implication as more elastic cloud services are being deployed. Existing techniques to detect and mitigate such attacks are either have low accuracy or ineffective and, in some cases, aggravate the attack even further. Therefore, an Enhanced Mitigation Mechanism is proposed to address these shortcomings using OpenFlow and statistical techniques, i.e. Hellinger Distance and Entropy. The experiments clearly depicted that EMM is able to detect and mitigate EDoS attacks with high accuracy and it is effective in terms of resource utilization compared to existing mitigation techniques. Thus, can be deployed in the cloud environment without the need for additional resource requirements.
Ordinal Bucketing for Game Trees using Dynamic Quantile Approximation
Venue: arXiv cs.AI 2019
Year: 2019

In this paper, we present a simple and cheap ordinal bucketing algorithm that approximately generates $q$-quantiles from an incremental data stream. The bucketing is done dynamically in the sense that the amount of buckets $q$ increases with the number of seen samples. We show how this can be used in Ordinal Monte Carlo Tree Search (OMCTS) to yield better bounds on time and space complexity, especially in the presence of noisy rewards. Besides complexity analysis and quality tests of quantiles, we evaluate our method using OMCTS in the General Video Game Framework (GVGAI). Our results demonstrate its dominance over vanilla Monte Carlo Tree Search in the presence of noise, where OMCTS without bucketing has a very bad time and space complexity.
Autonomous Human Activity Classification from Ego-vision Camera and Accelerometer Data
Venue: arXiv cs.CV 2019
Year: 2019

There has been significant amount of research work on human activity classification relying either on Inertial Measurement Unit (IMU) data or data from static cameras providing a third-person view. Using only IMU data limits the variety and complexity of the activities that can be detected. For instance, the sitting activity can be detected by IMU data, but it cannot be determined whether the subject has sat on a chair or a sofa, or where the subject is. To perform fine-grained activity classification from egocentric videos, and to distinguish between activities that cannot be differentiated by only IMU data, we present an autonomous and robust method using data from both ego-vision cameras and IMUs. In contrast to convolutional neural network-based approaches, we propose to employ capsule networks to obtain features from egocentric video data. Moreover, Convolutional Long Short Term Memory framework is employed both on egocentric videos and IMU data to capture temporal aspect of actions. We also propose a genetic algorithm-based approach to autonomously and systematically set various network parameters, rather than using manual settings. Experiments have been performed to perform 9- and 26-label activity classification, and the proposed method, using autonomously set network parameters, has provided very promising results, achieving overall accuracies of 86.6\% and 77.2\%, respectively. The proposed approach combining both modalities also provides increased accuracy compared to using only egovision data and only IMU data.
Gaining Extra Supervision via Multi-task learning for Multi-Modal Video Question Answering
Venue: arXiv cs.CV 2019
Year: 2019

This paper proposes a method to gain extra supervision via multi-task learning for multi-modal video question answering. Multi-modal video question answering is an important task that aims at the joint understanding of vision and language. However, establishing large scale dataset for multi-modal video question answering is expensive and the existing benchmarks are relatively small to provide sufficient supervision. To overcome this challenge, this paper proposes a multi-task learning method which is composed of three main components: (1) multi-modal video question answering network that answers the question based on the both video and subtitle feature, (2) temporal retrieval network that predicts the time in the video clip where the question was generated from and (3) modality alignment network that solves metric learning problem to find correct association of video and subtitle modalities. By simultaneously solving related auxiliary tasks with hierarchically shared intermediate layers, the extra synergistic supervisions are provided. Motivated by curriculum learning, multi task ratio scheduling is proposed to learn easier task earlier to set inductive bias at the beginning of the training. The experiments on publicly available dataset TVQA shows state-of-the-art results, and ablation studies are conducted to prove the statistical validity.
Quantization Loss Re-Learning Method
Venue: arXiv cs.LG 2019
Year: 2019

In order to quantize the gate parameters of the LSTM (Long Short-Term Memory) neural network model with almost no recognition performance degraded, a new quantization method named Quantization Loss Re-Learn Method is proposed in this paper. The method does lossy quantization on gate parameters during training iterations, and the weight parameters learn to offset the loss of gate parameters quantization by adjusting the gradient in back propagation during weight parameters optimization. We proved the effectiveness of this method through theoretical derivation and experiments. The gate parameters had been quantized to 0, 0.5, 1 three values, and on the Named Entity Recognition dataset, the F1 score of the model with the new quantization method on gate parameters decreased by only 0.7% compared to the baseline model.
Using Natural Language Processing to Develop an Automated Orthodontic Diagnostic System
Venue: arXiv cs.CL 2019
Year: 2019

We work on the task of automatically designing a treatment plan from the findings included in the medical certificate written by the dentist. To develop an artificial intelligence system that deals with free-form certificates written by dentists, we annotate the findings and utilized the natural language processing approach. As a result of the experiment using 990 certificates, 0.585 F1-score was achieved for the task of extracting orthodontic problems from findings, and 0.584 correlation coefficient with the human ranking was achieved for the treatment prioritization task.
A Riemanian Approach to Blob Detection in Manifold-Valued Images
Venue: arXiv cs.CV 2019
Year: 2019

This paper is devoted to the problem of blob detection in manifold-valued images. Our solution is based on new definitions of blob response functions. We define the blob response functions by means of curvatures of an image graph, considered as a submanifold. We call the proposed framework Riemannian blob detection. We prove that our approach can be viewed as a generalization of the grayscale blob detection technique. An expression of the Riemannian blob response functions through the image Hessian is derived. We provide experiments for the case of vector-valued images on 2D surfaces: the proposed framework is tested on the task of chemical compounds classification.
Independent Component Analysis based on multiple data-weighting
Venue: arXiv cs.LG 2019
Year: 2019

Independent Component Analysis (ICA) - one of the basic tools in data analysis - aims to find a coordinate system in which the components of the data are independent. In this paper we present Multiple-weighted Independent Component Analysis (MWeICA) algorithm, a new ICA method which is based on approximate diagonalization of weighted covariance matrices. Our idea is based on theoretical result, which says that linear independence of weighted data (for gaussian weights) guarantees independence. Experiments show that MWeICA achieves better results to most state-of-the-art ICA methods, with similar computational time.
Thinking Slow about Latency Evaluation for Simultaneous Machine Translation
Venue: arXiv cs.CL 2019
Year: 2019

Simultaneous machine translation attempts to translate a source sentence before it is finished being spoken, with applications to translation of spoken language for live streaming and conversation. Since simultaneous systems trade quality to reduce latency, having an effective and interpretable latency metric is crucial. We introduce a variant of the recently proposed Average Lagging (AL) metric, which we call Differentiable Average Lagging (DAL). It distinguishes itself by being differentiable and internally consistent to its underlying mathematical model.
The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game
Venue: arXiv cs.GT 2019
Year: 2019

The Price of Anarchy (PoA) is a well-established game-theoretic concept to shed light on coordination issues arising in open distributed systems. Leaving agents to selfishly optimize comes with the risk of ending up in sub-optimal states (in terms of performance and/or costs), compared to a centralized system design. However, the PoA relies on strong assumptions about agents' rationality (e.g., resources and information) and interactions, whereas in many distributed systems agents interact locally with bounded resources. They do so repeatedly over time (in contrast to "one-shot games"), and their strategies may evolve. Using a more realistic evolutionary game model, this paper introduces a realized evolutionary Price of Anarchy (ePoA). The ePoA allows an exploration of equilibrium selection in dynamic distributed systems with multiple equilibria, based on local interactions of simple memoryless agents. Considering a fundamental game related to virus propagation on networks, we present analytical bounds on the ePoA in basic network topologies and for different strategy update dynamics. In particular, deriving stationary distributions of the stochastic evolutionary process, we find that the Nash equilibria are not always the most abundant states, and that different processes can feature significant off-equilibrium behavior, leading to a significantly higher ePoA compared to the PoA studied traditionally in the literature.
Model Agnostic Contrastive Explanations for Structured Data
Venue: arXiv cs.LG 2019
Year: 2019

Recently, a method [7] was proposed to generate contrastive explanations for differentiable models such as deep neural networks, where one has complete access to the model. In this work, we propose a method, Model Agnostic Contrastive Explanations Method (MACEM), to generate contrastive explanations for \emph{any} classification model where one is able to \emph{only} query the class probabilities for a desired input. This allows us to generate contrastive explanations for not only neural networks, but models such as random forests, boosted trees and even arbitrary ensembles that are still amongst the state-of-the-art when learning on structured data [13]. Moreover, to obtain meaningful explanations we propose a principled approach to handle real and categorical features leading to novel formulations for computing pertinent positives and negatives that form the essence of a contrastive explanation. A detailed treatment of the different data types of this nature was not performed in the previous work, which assumed all features to be positive real valued with zero being indicative of the least interesting value. We part with this strong implicit assumption and generalize these methods so as to be applicable across a much wider range of problem settings. We quantitatively and qualitatively validate our approach over 5 public datasets covering diverse domains.
On problems related to crossing families
Venue: arXiv cs.CG 2019
Year: 2019

Given a set of points in the plane, a \emph{crossing family} is a collection of segments, each joining two of the points, such that every two segments intersect internally. Aronov et al. [Combinatorica,~14(2):127-134,~1994] proved that any set of $n$ points contains a crossing family of size $Ω(\sqrt{n})$. They also mentioned that there exist point sets whose maximum crossing family uses at most $\frac{n}{2}$ of the points. We improve the upper bound on the size of crossing families to $5\lceil \frac{n}{24} \rceil$. We also introduce a few generalizations of crossing families, and give several lower and upper bounds on our generalized notions.
Variational Langevin Hamiltonian Monte Carlo for Distant Multi-modal Sampling
Venue: arXiv cs.LG 2019
Year: 2019

The Hamiltonian Monte Carlo (HMC) sampling algorithm exploits Hamiltonian dynamics to construct efficient Markov Chain Monte Carlo (MCMC), which has become increasingly popular in machine learning and statistics. Since HMC uses the gradient information of the target distribution, it can explore the state space much more efficiently than the random-walk proposals. However, probabilistic inference involving multi-modal distributions is very difficult for standard HMC method, especially when the modes are far away from each other. Sampling algorithms are then often incapable of traveling across the places of low probability. In this paper, we propose a novel MCMC algorithm which aims to sample from multi-modal distributions effectively. The method improves Hamiltonian dynamics to reduce the autocorrelation of the samples and uses a variational distribution to explore the phase space and find new modes. A formal proof is provided which shows that the proposed method can converge to target distributions. Both synthetic and real datasets are used to evaluate its properties and performance. The experimental results verify the theory and show superior performance in multi-modal sampling.
"President Vows to Cut <Taxes> Hair": Dataset and Analysis of Creative Text Editing for Humorous Headlines
Venue: arXiv cs.CL 2019
Year: 2019

We introduce, release, and analyze a new dataset, called Humicroedit, for research in computational humor. Our publicly available data consists of regular English news headlines paired with versions of the same headlines that contain simple replacement edits designed to make them funny. We carefully curated crowdsourced editors to create funny headlines and judges to score a to a total of 15,095 edited headlines, with five judges per headline. The simple edits, usually just a single word replacement, mean we can apply straightforward analysis techniques to determine what makes our edited headlines humorous. We show how the data support classic theories of humor, such as incongruity, superiority, and setup/punchline. Finally, we develop baseline classifiers that can predict whether or not an edited headline is funny, which is a first step toward automatically generating humorous headlines as an approach to creating topical humor.
Biomedical Named Entity Recognition via Reference-Set Augmented Bootstrapping
Venue: arXiv cs.LG 2019
Year: 2019

We present a weakly-supervised data augmentation approach to improve Named Entity Recognition (NER) in a challenging domain: extracting biomedical entities (e.g., proteins) from the scientific literature. First, we train a neural NER (NNER) model over a small seed of fully-labeled examples. Second, we use a reference set of entity names (e.g., proteins in UniProt) to identify entity mentions with high precision, but low recall, on an unlabeled corpus. Third, we use the NNER model to assign weak labels to the corpus. Finally, we retrain our NNER model iteratively over the augmented training set, including the seed, the reference-set examples, and the weakly-labeled examples, which improves model performance. We show empirically that this augmented bootstrapping process significantly improves NER performance, and discuss the factors impacting the efficacy of the approach.
Cooperative neural networks (CoNN): Exploiting prior independence structure for improved classification
Venue: arXiv cs.LG 2019
Year: 2019

We propose a new approach, called cooperative neural networks (CoNN), which uses a set of cooperatively trained neural networks to capture latent representations that exploit prior given independence structure. The model is more flexible than traditional graphical models based on exponential family distributions, but incorporates more domain specific prior structure than traditional deep networks or variational autoencoders. The framework is very general and can be used to exploit the independence structure of any graphical model. We illustrate the technique by showing that we can transfer the independence structure of the popular Latent Dirichlet Allocation (LDA) model to a cooperative neural network, CoNN-sLDA. Empirical evaluation of CoNN-sLDA on supervised text classification tasks demonstrates that the theoretical advantages of prior independence structure can be realized in practice -we demonstrate a 23\% reduction in error on the challenging MultiSent data set compared to state-of-the-art.