OpenRaiser/Intern-Atlas huggingface dataset:
On the Weisfeiler-Leman Dimension of Fractional Packing
Venue: arXiv cs.CC 2020
Year: 2020

The $k$-dimensional Weisfeiler-Leman procedure ($k$-WL), which colors $k$-tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are $k$-WL-equivalent if the $k$-dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. 1-WL-equivalence is known as fractional isomorphism of graphs, and the $k$-WL-equivalence relation becomes finer as $k$ increases. We investigate to what extent standard graph parameters are preserved by $k$-WL-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of $k$-WL-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.
Towards Distributed Privacy-Preserving Prediction
Venue: arXiv cs.CR 2020
Year: 2020

In privacy-preserving machine learning, individual parties are reluctant to share their sensitive training data due to privacy concerns. Even the trained model parameters or prediction can pose serious privacy leakage. To address these problems, we demonstrate a generally applicable Distributed Privacy-Preserving Prediction (DPPP) framework, in which instead of sharing more sensitive data or model parameters, an untrusted aggregator combines only multiple models' predictions under provable privacy guarantee. Our framework integrates two main techniques to guarantee individual privacy. First, we introduce the improved Binomial Mechanism and Discrete Gaussian Mechanism to achieve distributed differential privacy. Second, we utilize homomorphic encryption to ensure that the aggregator learns nothing but the noisy aggregated prediction. Experimental results demonstrate that our framework has comparable performance to the non-private frameworks and delivers better results than the local differentially private framework and standalone framework.
The SIGMORPHON 2019 Shared Task: Morphological Analysis in Context and Cross-Lingual Transfer for Inflection
Venue: arXiv cs.CL 2020
Year: 2020

The SIGMORPHON 2019 shared task on cross-lingual transfer and contextual analysis in morphology examined transfer learning of inflection between 100 language pairs, as well as contextual lemmatization and morphosyntactic description in 66 languages. The first task evolves past years' inflection tasks by examining transfer of morphological inflection knowledge from a high-resource language to a low-resource language. This year also presents a new second challenge on lemmatization and morphological feature analysis in context. All submissions featured a neural component and built on either this year's strong baselines or highly ranked systems from previous years' shared tasks. Every participating team improved in accuracy over the baselines for the inflection task (though not Levenshtein distance), and every team in the contextual analysis task improved on both state-of-the-art neural and non-neural baselines.
KRED: Knowledge-Aware Document Representation for News Recommendations
Venue: arXiv cs.IR 2020
Year: 2020

News articles usually contain knowledge entities such as celebrities or organizations. Important entities in articles carry key messages and help to understand the content in a more direct way. An industrial news recommender system contains various key applications, such as personalized recommendation, item-to-item recommendation, news category classification, news popularity prediction and local news detection. We find that incorporating knowledge entities for better document understanding benefits these applications consistently. However, existing document understanding models either represent news articles without considering knowledge entities (e.g., BERT) or rely on a specific type of text encoding model (e.g., DKN) so that the generalization ability and efficiency is compromised. In this paper, we propose KRED, which is a fast and effective model to enhance arbitrary document representation with a knowledge graph. KRED first enriches entities' embeddings by attentively aggregating information from their neighborhood in the knowledge graph. Then a context embedding layer is applied to annotate the dynamic context of different entities such as frequency, category and position. Finally, an information distillation layer aggregates the entity embeddings under the guidance of the original document representation and transforms the document vector into a new one. We advocate to optimize the model with a multi-task framework, so that different news recommendation applications can be united and useful information can be shared across different tasks. Experiments on a real-world Microsoft News dataset demonstrate that KRED greatly benefits a variety of news recommendation applications.
BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search
Venue: arXiv cs.LG 2020
Year: 2020

Over the past half-decade, many methods have been considered for neural architecture search (NAS). Bayesian optimization (BO), which has long had success in hyperparameter optimization, has recently emerged as a very promising strategy for NAS when it is coupled with a neural predictor. Recent work has proposed different instantiations of this framework, for example, using Bayesian neural networks or graph convolutional networks as the predictive model within BO. However, the analyses in these papers often focus on the full-fledged NAS algorithm, so it is difficult to tell which individual components of the framework lead to the best performance. In this work, we give a thorough analysis of the "BO + neural predictor" framework by identifying five main components: the architecture encoding, neural predictor, uncertainty calibration method, acquisition function, and acquisition optimization strategy. We test several different methods for each component and also develop a novel path-based encoding scheme for neural architectures, which we show theoretically and empirically scales better than other encodings. Using all of our analyses, we develop a final algorithm called BANANAS, which achieves state-of-the-art performance on NAS search spaces. We adhere to the NAS research checklist (Lindauer and Hutter 2019) to facilitate best practices, and our code is available at https://github.com/naszilla/naszilla.
Cross-Channel Intragroup Sparsity Neural Network
Venue: arXiv cs.LG 2020
Year: 2020

Modern deep neural networks rely on overparameterization to achieve state-of-the-art generalization. But overparameterized models are computationally expensive. Network pruning is often employed to obtain less demanding models for deployment. Fine-grained pruning removes individual weights in parameter tensors and can achieve a high model compression ratio with little accuracy degradation. However, it introduces irregularity into the computing dataflow and often does not yield improved model inference efficiency in practice. Coarse-grained model pruning, while realizing satisfactory inference speedup through removal of network weights in groups, e.g. an entire filter, often lead to significant accuracy degradation. This work introduces the cross-channel intragroup (CCI) sparsity structure, which can prevent the inference inefficiency of fine-grained pruning while maintaining outstanding model performance. We then present a novel training algorithm designed to perform well under the constraint imposed by the CCI-Sparsity. Through a series of comparative experiments we show that our proposed CCI-Sparsity structure and the corresponding pruning algorithm outperform prior art in inference efficiency by a substantial margin given suited hardware acceleration in the future.
Selection on $X_1+X_2+\cdots + X_m$ with layer-ordered heaps
Venue: arXiv cs.DS 2020
Year: 2020

Selection on $X_1+X_2+\cdots + X_m$ is an important problem with many applications in areas such as max-convolution, max-product Bayesian inference, calculating most probable isotopes, and computing non-parametric test statistics, among others. Faster-than-naïve approaches exist for $m=2$: Frederickson (1993) published the optimal algorithm with runtime $O(k)$ and Kaplan \emph{et al.} (2018) has since published a much simpler algorithm which makes use of Chazelle's soft heaps (2003). No fast methods exist for $m>2$. Johnson \& Mizoguchi (1978) introduced a method to compute the single $k^{th}$ value when $m>2$, but that method runs in $O(m\cdot n^{\lceil\frac{m}{2}\rceil} \log(n))$ time and is inefficient when $m \gg 1$ and $k \ll n^{\lceil\frac{m}{2}\rceil}$. In this paper, we introduce the first efficient methods, both in theory and practice, for problems with $m>2$. We introduce the ``layer-ordered heap,'' a simple special class of heap with which we produce a new, fast selection algorithm on the Cartesian product. Using this new algorithm to perform $k$-selection on the Cartesian product of $m$ arrays of length $n$ has runtime $\in o(k\cdot m)$. We also provide implementations of the algorithms proposed and evaluate their performance in practice.
Decentralized Cooperative Communication-less Multi-Agent Task Assignment with Monte-Carlo Tree Search
Venue: arXiv cs.MA 2020
Year: 2020

Cooperative task assignment is an important subject in multi-agent systems with a wide range of applications. These systems are usually designed with massive communication among the agents to minimize the error in pursuit of the general goal of the entire system. In this work, we propose a novel approach for Decentralized Cooperative Communication-less Multi-Agent Task Assignment (DCCMATA) employing Monte-Carlo Tree Search (MCTS). Here, each agent can assign the optimal task by itself for itself. We design the system to automatically maximize the success rate, achieving the collective goal effectively. To put it another way, the agents optimally compute each following step, only by knowing the current location of other agents, with no additional communication overhead. In contrast with the previously proposed methods which rely on the task assignment procedure for similar problems, we describe a method in which the agents move towards the collective goal. This may lead to scenarios where some agents not necessarily move towards the closest goal. However, the total efficiency (makespan) and effectiveness (success ratio) in these cases are significantly improved. To evaluate our approach, we have tested the algorithm with a wide range of parameters(agents, size, goal). Our implementation completely solves (Success Rate = %100) a 20*20 grid with 20 goals by 20 agents in 7.9 s runtime for each agent. Also, the proposed algorithm runs with the complexity of O(N^2I^2 + IN^4), where the I and N are the MCTS iterative index and grid size, respectively.
Adversarial Defense via Local Flatness Regularization
Venue: arXiv cs.CV 2020
Year: 2020

Adversarial defense is a popular and important research area. Due to its intrinsic mechanism, one of the most straightforward and effective ways of defending attacks is to analyze the property of loss surface in the input space. In this paper, we define the local flatness of the loss surface as the maximum value of the chosen norm of the gradient regarding to the input within a neighborhood centered on the benign sample, and discuss the relationship between the local flatness and adversarial vulnerability. Based on the analysis, we propose a novel defense approach via regularizing the local flatness, dubbed local flatness regularization (LFR). We also demonstrate the effectiveness of the proposed method from other perspectives, such as human visual mechanism, and analyze the relationship between LFR and other related methods theoretically. Experiments are conducted to verify our theory and demonstrate the superiority of the proposed method.
Formalising perfectoid spaces
Venue: arXiv cs.LO 2020
Year: 2020

Perfectoid spaces are sophisticated objects in arithmetic geometry introduced by Peter Scholze in 2012. We formalised enough definitions and theorems in topology, algebra and geometry to define perfectoid spaces in the Lean theorem prover. This experiment confirms that a proof assistant can handle complexity in that direction, which is rather different from formalising a long proof about simple objects. It also confirms that mathematicians with no computer science training can become proficient users of a proof assistant in a relatively short period of time. Finally, we observe that formalising a piece of mathematics that is a trending topic boosts the visibility of proof assistants amongst pure mathematicians.
Sound Event Recognition in a Smart City Surveillance Context
Venue: arXiv cs.SD 2020
Year: 2020

Due to the growing demand for improving surveillance capabilities in smart cities, systems need to be developed to provide better monitoring capabilities to competent authorities, agencies responsible for strategic resource management, and emergency call centers. This work assumes that, as a complementary monitoring solution, the use of a system capable of detecting the occurrence of sound events, performing the Sound Events Recognition (SER) task, is highly convenient. In order to contribute to the classification of such events, this paper explored several classifiers over the SESA dataset, composed of audios of three hazard classes (gunshots, explosions, and sirens) and a class of casual sounds that could be misinterpreted as some of the other sounds. The best result was obtained by SGD, with an accuracy of 72.13% with 6.81 ms classification time, reinforcing the viability of such an approach.
Simplifying Neural Networks using Formal Verification
Venue: arXiv cs.LO 2020
Year: 2020

Deep neural network (DNN) verification is an emerging field, with diverse verification engines quickly becoming available. Demonstrating the effectiveness of these engines on real-world DNNs is an important step towards their wider adoption. We present a tool that can leverage existing verification engines in performing a novel application: neural network simplification, through the reduction of the size of a DNN without harming its accuracy. We report on the work-flow of the simplification process, and demonstrate its potential significance and applicability on a family of real-world DNNs for aircraft collision avoidance, whose sizes we were able to reduce by as much as 10%.
Unsupervised pre-training for sequence to sequence speech recognition
Venue: arXiv cs.SD 2020
Year: 2020

This paper proposes a novel approach to pre-train encoder-decoder sequence-to-sequence (seq2seq) model with unpaired speech and transcripts respectively. Our pre-training method is divided into two stages, named acoustic pre-trianing and linguistic pre-training. In the acoustic pre-training stage, we use a large amount of speech to pre-train the encoder by predicting masked speech feature chunks with its context. In the linguistic pre-training stage, we generate synthesized speech from a large number of transcripts using a single-speaker text to speech (TTS) system, and use the synthesized paired data to pre-train decoder. This two-stage pre-training method integrates rich acoustic and linguistic knowledge into seq2seq model, which will benefit downstream automatic speech recognition (ASR) tasks. The unsupervised pre-training is finished on AISHELL-2 dataset and we apply the pre-trained model to multiple paired data ratios of AISHELL-1 and HKUST. We obtain relative character error rate reduction (CERR) from 38.24% to 7.88% on AISHELL-1 and from 12.00% to 1.20% on HKUST. Besides, we apply our pretrained model to a cross-lingual case with CALLHOME dataset. For all six languages in CALLHOME dataset, our pre-training method makes model outperform baseline consistently.
The Hulls of Matrix-Product Codes over Commutative Rings and Applications
Venue: arXiv cs.IT 2020
Year: 2020

Given a commutative ring $R$ with identity, a matrix $A\in M_{s\times l}(R)$, and $R$-linear codes $\mathcal{C}_1, \dots, \mathcal{C}_s$ of the same length, this article considers the hull of the matrix-product codes $[\mathcal{C}_1 \dots \mathcal{C}_s]\,A$. Consequently, it introduces various sufficient conditions under which $[\mathcal{C}_1 \dots \mathcal{C}_s]\,A$ is a linear complementary dual (LCD) code. As an application, LCD matrix-product codes arising from torsion codes over finite chain rings are considered. Highlighting examples are also given.
PerceptNet: A Human Visual System Inspired Neural Network for Estimating Perceptual Distance
Venue: arXiv cs.LG 2020
Year: 2020

Traditionally, the vision community has devised algorithms to estimate the distance between an original image and images that have been subject to perturbations. Inspiration was usually taken from the human visual perceptual system and how the system processes different perturbations in order to replicate to what extent it determines our ability to judge image quality. While recent works have presented deep neural networks trained to predict human perceptual quality, very few borrow any intuitions from the human visual system. To address this, we present PerceptNet, a convolutional neural network where the architecture has been chosen to reflect the structure and various stages in the human visual system. We evaluate PerceptNet on various traditional perception datasets and note strong performance on a number of them as compared with traditional image quality metrics. We also show that including a nonlinearity inspired by the human visual system in classical deep neural networks architectures can increase their ability to judge perceptual similarity. Compared to similar deep learning methods, the performance is similar, although our network has a number of parameters that is several orders of magnitude less.
Ready, set, Go! Data-race detection and the Go language
Venue: arXiv cs.SE 2020
Year: 2020

Data races are often discussed in the context of lock acquisition and release, with race-detection algorithms routinely relying on vector clocks as a means of capturing the relative ordering of events from different threads. In this paper, we present a data-race detector for a language with channel communication as its sole synchronization primitive, and provide a semantics directly tied to the happens-before relation, thus forging the notion of vector clocks.
Certified Adversarial Robustness for Deep Reinforcement Learning
Venue: arXiv cs.RO 2020
Year: 2020

Deep Neural Network-based systems are now the state-of-the-art in many robotics tasks, but their application in safety-critical domains remains dangerous without formal guarantees on network robustness. Small perturbations to sensor inputs (from noise or adversarial examples) are often enough to change network-based decisions, which was already shown to cause an autonomous vehicle to swerve into oncoming traffic. In light of these dangers, numerous algorithms have been developed as defensive mechanisms from these adversarial inputs, some of which provide formal robustness guarantees or certificates. This work leverages research on certified adversarial robustness to develop an online certified defense for deep reinforcement learning algorithms. The proposed defense computes guaranteed lower bounds on state-action values during execution to identify and choose the optimal action under a worst-case deviation in input space due to possible adversaries or noise. The approach is demonstrated on a Deep Q-Network policy and is shown to increase robustness to noise and adversaries in pedestrian collision avoidance scenarios and a classic control task.
Measuring Similarity of Interactive Driving Behaviors Using Matrix Profile
Venue: arXiv cs.LG 2020
Year: 2020

Understanding multi-vehicle interactive behaviors with temporal sequential observations is crucial for autonomous vehicles to make appropriate decisions in an uncertain traffic environment. On-demand similarity measures are significant for autonomous vehicles to deal with massive interactive driving behaviors by clustering and classifying diverse scenarios. This paper proposes a general approach for measuring spatiotemporal similarity of interactive behaviors using a multivariate matrix profile technique. The key attractive features of the approach are its superior space and time complexity, real-time online computing for streaming traffic data, and possible capability of leveraging hardware for parallel computation. The proposed approach is validated through automatically discovering similar interactive driving behaviors at intersections from sequential data.
Shoestring: Graph-Based Semi-Supervised Learning with Severely Limited Labeled Data
Venue: arXiv cs.CV 2020
Year: 2020

Graph-based semi-supervised learning has been shown to be one of the most effective approaches for classification tasks from a wide range of domains, such as image classification and text classification, as they can exploit the connectivity patterns between labeled and unlabeled samples to improve learning performance. In this work, we advance this effective learning paradigm towards a scenario where labeled data are severely limited. More specifically, we address the problem of graph-based semi-supervised learning in the presence of severely limited labeled samples, and propose a new framework, called {\em Shoestring}, that improves the learning performance through semantic transfer from these very few labeled samples to large numbers of unlabeled samples. In particular, our framework learns a metric space in which classification can be performed by computing the similarity to centroid embedding of each class. {\em Shoestring} is trained in an end-to-end fashion to learn to leverage the semantic knowledge of limited labeled samples as well as their connectivity patterns with large numbers of unlabeled samples simultaneously. By combining {\em Shoestring} with graph convolutional networks, label propagation and their recent label-efficient variations (IGCN and GLP), we are able to achieve state-of-the-art node classification performance in the presence of very few labeled samples. In addition, we demonstrate the effectiveness of our framework on image classification tasks in the few-shot learning regime, with significant gains on miniImageNet ($2.57\%\sim3.59\%$) and tieredImageNet ($1.05\%\sim2.70\%$).
Flexible Graph Connectivity: Approximating Network Design Problems Between 1- and 2-connectivity
Venue: arXiv cs.DS 2020
Year: 2020

Graph connectivity and network design problems are among the most fundamental problems in combinatorial optimization. The minimum spanning tree problem, the two edge-connected spanning subgraph problem (2-ECSS) and the tree augmentation problem (TAP) are all examples of fundamental well-studied network design tasks that postulate different initial states of the network and different assumptions on the reliability of network components. In this paper we motivate and study \emph{Flexible Graph Connectivity} (FGC), a problem that mixes together both the modeling power and the complexities of all aforementioned problems and more. In a nutshell, FGC asks to design a connected network, while allowing to specify different reliability levels for individual edges. While this non-uniform nature of the problem makes it appealing from the modeling perspective, it also renders most existing algorithmic tools for dealing with network design problems unfit for approximating FGC. In this paper we develop a general algorithmic approach for approximating FGC that yields approximation algorithms with ratios that are very close to the best known bounds for many special cases, such as 2-ECSS and TAP. Our algorithm and analysis combine various techniques including a weight-scaling algorithm, a charging argument that uses a variant of exchange bijections between spanning trees and a factor revealing min-max-min optimization problem.