OpenRaiser/Intern-Atlas huggingface dataset:
Fast Dimensional Analysis for Root Cause Investigation in a Large-Scale Service Environment
Venue: arXiv cs.DC 2020
Year: 2020

Root cause analysis in a large-scale production environment is challenging due to the complexity of services running across global data centers. Due to the distributed nature of a large-scale system, the various hardware, software, and tooling logs are often maintained separately, making it difficult to review the logs jointly for understanding production issues. Another challenge in reviewing the logs for identifying issues is the scale - there could easily be millions of entities, each described by hundreds of features. In this paper we present a fast dimensional analysis framework that automates the root cause analysis on structured logs with improved scalability. We first explore item-sets, i.e. combinations of feature values, that could identify groups of samples with sufficient support for the target failures using the Apriori algorithm and a subsequent improvement, FP-Growth. These algorithms were designed for frequent item-set mining and association rule learning over transactional databases. After applying them on structured logs, we select the item-sets that are most unique to the target failures based on lift. We propose pre-processing steps with the use of a large-scale real-time database and post-processing techniques and parallelism to further speed up the analysis and improve interpretability, and demonstrate that such optimization is necessary for handling large-scale production datasets. We have successfully rolled out this approach for root cause investigation purposes in a large-scale infrastructure. We also present the setup and results from multiple production use cases in this paper.
Nearly Optimal Static Las Vegas Succinct Dictionary
Venue: arXiv cs.DS 2020
Year: 2020

Given a set $S$ of $n$ (distinct) keys from key space $[U]$, each associated with a value from $Σ$, the \emph{static dictionary} problem asks to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given $x\in [U]$, $\mathtt{valRet}(x)$ must return the value associated with $x$ if $x\in S$, or return $\bot$ if $x\notin S$. The special case where $|Σ|=1$ is called the \emph{membership} problem. The "textbook" solution is to use a hash table, which occupies linear space and answers each query in constant time. On the other hand, the minimum possible space to encode all (key, value) pairs is only $\mathtt{OPT}:= \lceil\lg_2\binom{U}{n}+n\lg_2|Σ|\rceil$ bits, which could be much less. In this paper, we design a randomized dictionary data structure using $\mathtt{OPT}+\mathrm{poly}\lg n+O(\lg\lg\lg\lg\lg U)$ bits of space, and it has \emph{expected constant} query time, assuming the query algorithm can access an external lookup table of size $n^{0.001}$. The lookup table depends only on $U$, $n$ and $|Σ|$, and not the input. Previously, even for membership queries and $U\leq n^{O(1)}$, the best known data structure with constant query time requires $\mathtt{OPT}+n/\mathrm{poly}\lg n$ bits of space (Pagh [Pag01] and Pǎtraşcu [Pat08]); the best-known using $\mathtt{OPT}+n^{0.999}$ space has query time $O(\lg n)$; the only known non-trivial data structure with $\mathtt{OPT}+n^{0.001}$ space has $O(\lg n)$ query time and requires a lookup table of size $\geq n^{2.99}$ (!). Our new data structure answers open questions by Pǎtraşcu and Thorup [Pat08,Tho13]. We also present a scheme that compresses a sequence $X\inΣ^n$ to its zeroth order (empirical) entropy up to $|Σ|\cdot\mathrm{poly}\lg n$ extra bits, supporting decoding each $X_i$ in $O(\lg |Σ|)$ expected time.
Counting Small Permutation Patterns
Venue: arXiv cs.DS 2020
Year: 2020

A sample of n generic points in the xy-plane defines a permutation that relates their ranks along the two axes. Every subset of k points similarly defines a pattern, which occurs in that permutation. The number of occurrences of small patterns in a large permutation arises in many areas, including nonparametric statistics. It is therefore desirable to count them more efficiently than the straightforward ~O(n^k) time algorithm. This work proposes new algorithms for counting patterns. We show that all patterns of order 2 and 3, as well as eight patterns of order 4, can be counted in nearly linear time. To that end, we develop an algebraic framework that we call corner tree formulas. Our approach generalizes the existing methods and allows a systematic study of their scope. Using the machinery of corner trees, we find twenty-three independent linear combinations of order-4 patterns, that can be computed in time ~O(n). We also describe an algorithm that counts one of the remaining 4-patterns, and hence all 4-patterns, in time ~O(n^(3/2)). As a practical application, we provide a nearly linear time computation of a statistic by Yanagimoto (1970), Bergsma and Dassios (2010). This statistic yields a natural and strongly consistent variant of Hoeffding's test for independence of X and Y, given a random sample as above. This improves upon the so far most efficient ~O(n^2) algorithm.
New Potential-Based Bounds for Prediction with Expert Advice
Venue: arXiv cs.LG 2020
Year: 2020

This work addresses the classic machine learning problem of online prediction with expert advice. We consider the finite-horizon version of this zero-sum, two-person game. Using verification arguments from optimal control theory, we view the task of finding better lower and upper bounds on the value of the game (regret) as the problem of finding better sub- and supersolutions of certain partial differential equations (PDEs). These sub- and supersolutions serve as the potentials for player and adversary strategies, which lead to the corresponding bounds. To get explicit bounds, we use closed-form solutions of specific PDEs. Our bounds hold for any given number of experts and horizon; in certain regimes (which we identify) they improve upon the previous state of the art. For two and three experts, our bounds provide the optimal leading order term.
Data Poisoning Attacks to Local Differential Privacy Protocols
Venue: arXiv cs.CR 2020
Year: 2020

Local Differential Privacy (LDP) protocols enable an untrusted data collector to perform privacy-preserving data analytics. In particular, each user locally perturbs its data to preserve privacy before sending it to the data collector, who aggregates the perturbed data to obtain statistics of interest. In the past several years, researchers from multiple communities -- such as security, database, and theoretical computer science -- have proposed many LDP protocols. These studies mainly focused on improving the utility of the LDP protocols. However, the security of LDP protocols is largely unexplored. In this work, we aim to bridge this gap. We focus on LDP protocols for frequency estimation and heavy hitter identification, which are two basic data analytics tasks. Specifically, we show that an attacker can inject fake users into an LDP protocol and the fake users send carefully crafted data to the data collector such that the LDP protocol estimates high frequencies for arbitrary attacker-chosen items or identifies them as heavy hitters. We call our attacks data poisoning attacks. We theoretically and/or empirically show the effectiveness of our attacks. We also explore three countermeasures against our attacks. Our experimental results show that they can effectively defend against our attacks in some scenarios but have limited effectiveness in others, highlighting the needs for new defenses against our attacks.
Optimal group testing
Venue: arXiv cs.DM 2020
Year: 2020

In the group testing problem the aim is to identify a small set of $k\sim n^θ$ infected individuals out of a population size $n$, $0<θ<1$. We avail ourselves of a test procedure capable of testing groups of individuals, with the test returning a positive result iff at least one individual in the group is infected. The aim is to devise a test design with as few tests as possible so that the set of infected individuals can be identified correctly with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition $\minf$ for non-adaptive group testing, where all tests are conducted in parallel. Thus, with more than $\minf$ tests the infected individuals can be identified in polynomial time \whp, while learning the set of infected individuals is information-theoretically impossible with fewer tests. In addition, we develop an optimal adaptive scheme where the tests are conducted in two stages.
Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods
Venue: arXiv cs.LG 2020
Year: 2020

As machine learning black boxes are increasingly being deployed in domains such as healthcare and criminal justice, there is growing emphasis on building tools and techniques for explaining these black boxes in an interpretable manner. Such explanations are being leveraged by domain experts to diagnose systematic errors and underlying biases of black boxes. In this paper, we demonstrate that post hoc explanations techniques that rely on input perturbations, such as LIME and SHAP, are not reliable. Specifically, we propose a novel scaffolding technique that effectively hides the biases of any given classifier by allowing an adversarial entity to craft an arbitrary desired explanation. Our approach can be used to scaffold any biased classifier in such a way that its predictions on the input data distribution still remain biased, but the post hoc explanations of the scaffolded classifier look innocuous. Using extensive evaluation with multiple real-world datasets (including COMPAS), we demonstrate how extremely biased (racist) classifiers crafted by our framework can easily fool popular explanation techniques such as LIME and SHAP into generating innocuous explanations which do not reflect the underlying biases.
Impact Factor volatility to a single paper: A comprehensive analysis
Venue: arXiv cs.DL 2020
Year: 2020

We study how a single paper affects the Impact Factor (IF) by analyzing data from 3,088,511 papers published in 11639 journals in the 2017 Journal Citation Reports of Clarivate Analytics. We find that IFs are highly volatile. For example, the top-cited paper of 381 journals caused their IF to increase by more than 0.5 points, while for 818 journals the relative increase exceeded 25%. And one in 10 journals had their IF boosted by more than 50% by their top three cited papers. Because the single-paper effect on the IF is inversely proportional to journal size, small journals are rewarded much more strongly than large journals for a highly-cited paper, while they are penalized more for a low-cited paper, especially if their IF is high. This skewed reward mechanism incentivizes high-IF journals to stay small, to remain competitive in rankings. We discuss the implications for breakthrough papers appearing in prestigious journals. We question the reliability of IF rankings given the high IF sensitivity to a few papers for thousands of journals.
Polymorphic Encryption and Pseudonymisation of IP Network Flows
Venue: arXiv cs.CR 2020
Year: 2020

We describe a system, PEP3, for storage and retrieval of IP flow information in which the IP addresses are replaced by pseudonyms. Every eligible party gets its own set of pseudonyms. A single entity, the transcryptor, that is composed of five independent peers, is responsible for the generation of, depseudonymisation of, and translation between different sets of pseudonyms. These operations can be performed by any three of the five peers, preventing a single point of trust or failure. Using homomorphic aspects of ElGamal encryption the peers perform their operations on encrypted and --potentially-- pseudonymised IP addresses only, thereby never learning the (pseudonymised) IP addresses handled by the parties. Moreover, using Schnorr type proofs, the behaviour of the peers can be verified, without revealing the (pseudonymised) IP addresses either. Hence the peers are central, but need not be fully trusted. The design of our system, while easily modified to other settings, is tuned to the sheer volume of data presented by IP flow information.
Incremental Text-to-Speech Synthesis with Prefix-to-Prefix Framework
Venue: arXiv cs.CL 2020
Year: 2020

Text-to-speech synthesis (TTS) has witnessed rapid progress in recent years, where neural methods became capable of producing audios with high naturalness. However, these efforts still suffer from two types of latencies: (a) the {\em computational latency} (synthesizing time), which grows linearly with the sentence length even with parallel approaches, and (b) the {\em input latency} in scenarios where the input text is incrementally generated (such as in simultaneous translation, dialog generation, and assistive technologies). To reduce these latencies, we devise the first neural incremental TTS approach based on the recently proposed prefix-to-prefix framework. We synthesize speech in an online fashion, playing a segment of audio while generating the next, resulting in an $O(1)$ rather than $O(n)$ latency.
Improving Grammatical Error Correction with Machine Translation Pairs
Venue: arXiv cs.CL 2020
Year: 2020

We propose a novel data synthesis method to generate diverse error-corrected sentence pairs for improving grammatical error correction, which is based on a pair of machine translation models of different qualities (i.e., poor and good). The poor translation model resembles the ESL (English as a second language) learner and tends to generate translations of low quality in terms of fluency and grammatical correctness, while the good translation model generally generates fluent and grammatically correct translations. We build the poor and good translation model with phrase-based statistical machine translation model with decreased language model weight and neural machine translation model respectively. By taking the pair of their translations of the same sentences in a bridge language as error-corrected sentence pairs, we can construct unlimited pseudo parallel data. Our approach is capable of generating diverse fluency-improving patterns without being limited by the pre-defined rule set and the seed error-corrected data. Experimental results demonstrate the effectiveness of our approach and show that it can be combined with other synthetic data sources to yield further improvements.
Perspectives on urban theories
Venue: arXiv cs.DL 2020
Year: 2020

At the end of the five years of work in our GeoDiverCity program, we brought together a diversity of authors from different disciplines. Each person was invited to present an important question about the theories and models of urbanization. They are representative of a variety of currents in urban research. Rather than repeat here the contents of all chapters, we propose two ways to synthesize the scientific contributions of this book. In a first part we replace them in relation to a few principles that were experimented in our program, and in a second part we situate them with respect to a broader view of international literature on these topics.
Improving Joint Training of Inference Networks and Structured Prediction Energy Networks
Venue: arXiv cs.CL 2020
Year: 2020

Deep energy-based models are powerful, but pose challenges for learning and inference (Belanger and McCallum, 2016). Tu and Gimpel (2018) developed an efficient framework for energy-based models by training "inference networks" to approximate structured inference instead of using gradient descent. However, their alternating optimization approach suffers from instabilities during training, requiring additional loss terms and careful hyperparameter tuning. In this paper, we contribute several strategies to stabilize and improve this joint training of energy functions and inference networks for structured prediction. We design a compound objective to jointly train both cost-augmented and test-time inference networks along with the energy function. We propose joint parameterizations for the inference networks that encourage them to capture complementary functionality during learning. We empirically validate our strategies on two sequence labeling tasks, showing easier paths to strong performance than prior work, as well as further improvements with global energy terms.
Blockwise Self-Attention for Long Document Understanding
Venue: arXiv cs.CL 2020
Year: 2020

We present BlockBERT, a lightweight and efficient BERT model for better modeling long-distance dependencies. Our model extends BERT by introducing sparse block structures into the attention matrix to reduce both memory consumption and training/inference time, which also enables attention heads to capture either short- or long-range contextual information. We conduct experiments on language model pre-training and several benchmark question answering datasets with various paragraph lengths. BlockBERT uses 18.7-36.1% less memory and 12.0-25.1% less time to learn the model. During testing, BlockBERT saves 27.8% inference time, while having comparable and sometimes better prediction accuracy, compared to an advanced BERT-based model, RoBERTa.
Resurrecting Submodularity for Neural Text Generation
Venue: arXiv cs.CL 2020
Year: 2020

Submodularity is desirable for a variety of objectives in content selection where the current neural encoder-decoder framework is inadequate. However, it has so far not been explored in the neural encoder-decoder system for text generation. In this work, we define diminishing attentions with submodular functions and in turn, prove the submodularity of the effective neural coverage. The greedy algorithm approximating the solution to the submodular maximization problem is not suited to attention score optimization in auto-regressive generation. Therefore instead of following how submodular function has been widely used, we propose a simplified yet principled solution. The resulting attention module offers an architecturally simple and empirically effective method to improve the coverage of neural text generation. We run experiments on three directed text generation tasks with different levels of recovering rate, across two modalities, three different neural model architectures and two training strategy variations. The results and analyses demonstrate that our method generalizes well across these settings, produces texts of good quality and outperforms state-of-the-art baselines.
L-FGADMM: Layer-Wise Federated Group ADMM for Communication Efficient Decentralized Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

This article proposes a communication-efficient decentralized deep learning algorithm, coined layer-wise federated group ADMM (L-FGADMM). To minimize an empirical risk, every worker in L-FGADMM periodically communicates with two neighbors, in which the periods are separately adjusted for different layers of its deep neural network. A constrained optimization problem for this setting is formulated and solved using the stochastic version of GADMM proposed in our prior work. Numerical evaluations show that by less frequently exchanging the largest layer, L-FGADMM can significantly reduce the communication cost, without compromising the convergence speed. Surprisingly, despite less exchanged information and decentralized operations, intermittently skipping the largest layer consensus in L-FGADMM creates a regularizing effect, thereby achieving the test accuracy as high as federated learning (FL), a baseline method with the entire layer consensus by the aid of a central entity.
Contextualized End-to-End Neural Entity Linking
Venue: arXiv cs.CL 2020
Year: 2020

We propose yet another entity linking model (YELM) which links words to entities instead of spans. This overcomes any difficulties associated with the selection of good candidate mention spans and makes the joint training of mention detection (MD) and entity disambiguation (ED) easily possible. Our model is based on BERT and produces contextualized word embeddings which are trained against a joint MD and ED objective. We achieve state-of-the-art results on several standard entity linking (EL) datasets.
Minimalistic Attacks: How Little it Takes to Fool a Deep Reinforcement Learning Policy
Venue: arXiv cs.LG 2020
Year: 2020

Recent studies have revealed that neural network-based policies can be easily fooled by adversarial examples. However, while most prior works analyze the effects of perturbing every pixel of every frame assuming white-box policy access, in this paper we take a more restrictive view towards adversary generation - with the goal of unveiling the limits of a model's vulnerability. In particular, we explore minimalistic attacks by defining three key settings: (1) black-box policy access: where the attacker only has access to the input (state) and output (action probability) of an RL policy; (2) fractional-state adversary: where only several pixels are perturbed, with the extreme case being a single-pixel adversary; and (3) tactically-chanced attack: where only significant frames are tactically chosen to be attacked. We formulate the adversarial attack by accommodating the three key settings and explore their potency on six Atari games by examining four fully trained state-of-the-art policies. In Breakout, for example, we surprisingly find that: (i) all policies showcase significant performance degradation by merely modifying 0.01% of the input state, and (ii) the policy trained by DQN is totally deceived by perturbation to only 1% frames.
A class of two or three weights linear codes and their complete weight enumerators
Venue: arXiv cs.IT 2020
Year: 2020

In the past few years, linear codes with few weights and their weight analysis have been widely studied. In this paper, we further investigate a class of two-weight or three-weight linear codes from defining sets and determine their weight and complete weight enumerators by application of the theory of quadratic forms and some special Weil sums over finite fields. Some punctured codes of the discussed linear codes are optimal or almost optimal with respect to the Griesmer bound. This paper generalizes some results in \cite{ZhuXu2017,Jian2019}.
A Simple Differentiable Programming Language
Venue: arXiv cs.PL 2020
Year: 2020

Automatic differentiation plays a prominent role in scientific computing and in modern machine learning, often in the context of powerful programming systems. The relation of the various embodiments of automatic differentiation to the mathematical notion of derivative is not always entirely clear---discrepancies can arise, sometimes inadvertently. In order to study automatic differentiation in such programming contexts, we define a small but expressive programming language that includes a construct for reverse-mode differentiation. We give operational and denotational semantics for this language. The operational semantics employs popular implementation techniques, while the denotational semantics employs notions of differentiation familiar from real analysis. We establish that these semantics coincide.