OpenRaiser/Intern-Atlas huggingface dataset:
Are Pretrained Language Models Symbolic Reasoners Over Knowledge?
Venue: arXiv cs.CL 2020
Year: 2020

How can pretrained language models (PLMs) learn factual knowledge from the training set? We investigate the two most important mechanisms: reasoning and memorization. Prior work has attempted to quantify the number of facts PLMs learn, but we present, using synthetic data, the first study that investigates the causal relation between facts present in training and facts learned by the PLM. For reasoning, we show that PLMs seem to learn to apply some symbolic reasoning rules correctly but struggle with others, including two-hop reasoning. Further analysis suggests that even the application of learned reasoning rules is flawed. For memorization, we identify schema conformity (facts systematically supported by other facts) and frequency as key factors for its success.
Artificial Musical Intelligence: A Survey
Venue: arXiv cs.SD 2020
Year: 2020

Computers have been used to analyze and create music since they were first introduced in the 1950s and 1960s. Beginning in the late 1990s, the rise of the Internet and large scale platforms for music recommendation and retrieval have made music an increasingly prevalent domain of machine learning and artificial intelligence research. While still nascent, several different approaches have been employed to tackle what may broadly be referred to as "musical intelligence." This article provides a definition of musical intelligence, introduces a taxonomy of its constituent components, and surveys the wide range of AI methods that can be, and have been, brought to bear in its pursuit, with a particular emphasis on machine learning methods.
On the complexity of detecting hazards
Venue: arXiv cs.CC 2020
Year: 2020

Detecting and eliminating logic hazards in Boolean circuits is a fundamental problem in logic circuit design. We show that there is no $O(3^{(1-ε)n} \text{poly}(s))$ time algorithm, for any $ε> 0$, that detects logic hazards in Boolean circuits of size $s$ on $n$ variables under the assumption that the strong exponential time hypothesis is true. This lower bound holds even when the input circuits are restricted to be formulas of depth four. We also present a polynomial time algorithm for detecting $1$-hazards in DNF (or, $0$-hazards in CNF) formulas. Since $0$-hazards in DNF (or, $1$-hazards in CNF) formulas are easy to eliminate, this algorithm can be used to detect whether a given DNF or CNF formula has a hazard in practice.
Robust Group Subspace Recovery: A New Approach for Multi-Modality Data Fusion
Venue: arXiv cs.LG 2020
Year: 2020

Robust Subspace Recovery (RoSuRe) algorithm was recently introduced as a principled and numerically efficient algorithm that unfolds underlying Unions of Subspaces (UoS) structure, present in the data. The union of Subspaces (UoS) is capable of identifying more complex trends in data sets than simple linear models. We build on and extend RoSuRe to prospect the structure of different data modalities individually. We propose a novel multi-modal data fusion approach based on group sparsity which we refer to as Robust Group Subspace Recovery (RoGSuRe). Relying on a bi-sparsity pursuit paradigm and non-smooth optimization techniques, the introduced framework learns a new joint representation of the time series from different data modalities, respecting an underlying UoS model. We subsequently integrate the obtained structures to form a unified subspace structure. The proposed approach exploits the structural dependencies between the different modalities data to cluster the associated target objects. The resulting fusion of the unlabeled sensors' data from experiments on audio and magnetic data has shown that our method is competitive with other state of the art subspace clustering methods. The resulting UoS structure is employed to classify newly observed data points, highlighting the abstraction capacity of the proposed method.
A unified framework for equivalences in social networks
Venue: arXiv cs.SI 2020
Year: 2020

A key concern in network analysis is the study of social positions and roles of actors in a network. The notion of "position" refers to an equivalence class of nodes that have similar ties to other nodes, whereas a "role" is an equivalence class of compound relations that connect the same pairs of nodes. An open question in network science is whether it is possible to simultaneously perform role and positional analysis. Motivated by the principle of functoriality in category theory we propose a new method that allows to tie role and positional analysis together. We illustrate our methods on two well-studied data sets in network science.
Bootstrapping Complete The Look at Pinterest
Venue: arXiv cs.CV 2020
Year: 2020

Putting together an ideal outfit is a process that involves creativity and style intuition. This makes it a particularly difficult task to automate. Existing styling products generally involve human specialists and a highly curated set of fashion items. In this paper, we will describe how we bootstrapped the Complete The Look (CTL) system at Pinterest. This is a technology that aims to learn the subjective task of "style compatibility" in order to recommend complementary items that complete an outfit. In particular, we want to show recommendations from other categories that are compatible with an item of interest. For example, what are some heels that go well with this cocktail dress? We will introduce our outfit dataset of over 1 million outfits and 4 million objects, a subset of which we will make available to the research community, and describe the pipeline used to obtain and refresh this dataset. Furthermore, we will describe how we evaluate this subjective task and compare model performance across multiple training methods. Lastly, we will share our lessons going from experimentation to working prototype, and how to mitigate failure modes in the production environment. Our work represents one of the first examples of an industrial-scale solution for compatibility-based fashion recommendation.
Supervision Accelerates Pre-training in Contrastive Semi-Supervised Learning of Visual Representations
Venue: arXiv cs.LG 2020
Year: 2020

We investigate a strategy for improving the efficiency of contrastive learning of visual representations by leveraging a small amount of supervised information during pre-training. We propose a semi-supervised loss, SuNCEt, based on noise-contrastive estimation and neighbourhood component analysis, that aims to distinguish examples of different classes in addition to the self-supervised instance-wise pretext tasks. On ImageNet, we find that SuNCEt can be used to match the semi-supervised learning accuracy of previous contrastive approaches while using less than half the amount of pre-training and compute. Our main insight is that leveraging even a small amount of labeled data during pre-training, and not only during fine-tuning, provides an important signal that can significantly accelerate contrastive learning of visual representations. Our code is available online at github.com/facebookresearch/suncet.
Stability of Internal States in Recurrent Neural Networks Trained on Regular Languages
Venue: arXiv cs.LG 2020
Year: 2020

We provide an empirical study of the stability of recurrent neural networks trained to recognize regular languages. When a small amount of noise is introduced into the activation function, the neurons in the recurrent layer tend to saturate in order to compensate the variability. In this saturated regime, analysis of the network activation shows a set of clusters that resemble discrete states in a finite state machine. We show that transitions between these states in response to input symbols are deterministic and stable. The networks display a stable behavior for arbitrarily long strings, and when random perturbations are applied to any of the states, they are able to recover and their evolution converges to the original clusters. This observation reinforces the interpretation of the networks as finite automata, with neurons or groups of neurons coding specific and meaningful input patterns.
Image classification in frequency domain with 2SReLU: a second harmonics superposition activation function
Venue: arXiv cs.CV 2020
Year: 2020

Deep Convolutional Neural Networks are able to identify complex patterns and perform tasks with super-human capabilities. However, besides the exceptional results, they are not completely understood and it is still impractical to hand-engineer similar solutions. In this work, an image classification Convolutional Neural Network and its building blocks are described from a frequency domain perspective. Some network layers have established counterparts in the frequency domain like the convolutional and pooling layers. We propose the 2SReLU layer, a novel non-linear activation function that preserves high frequency components in deep networks. It is demonstrated that in the frequency domain it is possible to achieve competitive results without using the computationally costly convolution operation. A source code implementation in PyTorch is provided at: https://gitlab.com/thomio/2srelu
Prioritizing documentation effort: Can we do better?
Venue: arXiv cs.SE 2020
Year: 2020

Code documentations are essential for software quality assurance, but due to time or economic pressures, code developers are often unable to write documents for all modules in a project. Recently, a supervised artificial neural network (ANN) approach is proposed to prioritize important modules for documentation effort. However, as a supervised approach, there is a need to use labeled training data to train the prediction model, which may not be easy to obtain in practice. Furthermore, it is unclear whether the ANN approach is generalizable, as it is only evaluated on several small data sets. In this paper, we propose an unsupervised approach based on PageRank to prioritize documentation effort. This approach identifies "important" modules only based on the dependence relationships between modules in a project. As a result, the PageRank approach does not need any training data to build the prediction model. In order to evaluate the effectiveness of the PageRank approach, we use six additional large data sets to conduct the experiments in addition to the same data sets collected from open-source projects as used in prior studies. The experimental results show that the PageRank approach is superior to the state-of-the-art ANN approach in prioritizing important modules for documentation effort. In particular, due to the simplicity and effectiveness, we advocate that the PageRank approach should be used as an easy-to-implement baseline in future research on documentation effort prioritization, and any new approach should be compared with it to demonstrate its effectiveness.
Recommendations for Emerging Air Taxi Network Operations based on Online Review Analysis of Helicopter Services
Venue: arXiv cs.CY 2020
Year: 2020

The effects of traffic congestion are adverse, primarily including air pollution, commuter stress, and an increase in vehicle operating costs and accidents on the road. In efforts to alleviate these problems in metropolitan cities, logistics companies plan to introduce a new method of everyday commute called air taxis, an Urban Air Mobility (UAM) service. These are electric-powered vehicles that are expected to operate in the forthcoming years by international transportation companies like Airbus, Uber, and Kitty Hawk. Since these flying taxis are emerging mode of transportation, it is necessary to provide recommendations for the initial design, implementation, and operation. This study proposes managerial insights for these upcoming services by analyzing online customer reviews and conducting an internal assessment of helicopter operations. Helicopters are similar to air taxis in regards to their operations, and therefore, customer reviews pertaining to the former can enable us to obtain insights into the strengths and weaknesses of the short-distance aviation service, in general. A four-stage sequential approach is used in this research, wherein the online reviews are mined in Stage 1, analyzed using the bigram and trigram models in Stage 2, 7S internal assessment is conducted for helicopter services in Stage 3, and managerial recommendations for air taxis are proposed in Stage 4. The insights obtained in this paper could assist any air taxi companies in providing better customer service when they venture into the market. Keywords: Air taxi; Emerging technology; Urban Air Mobility (UAM); Helicopter services; Online customer reviews; Text analytics;
Sparse GPU Kernels for Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

Scientific workloads have traditionally exploited high levels of sparsity to accelerate computation and reduce memory requirements. While deep neural networks can be made sparse, achieving practical speedups on GPUs is difficult because these applications have relatively moderate levels of sparsity that are not sufficient for existing sparse kernels to outperform their dense counterparts. In this work, we study sparse matrices from deep learning applications and identify favorable properties that can be exploited to accelerate computation. Based on these insights, we develop high-performance GPU kernels for two sparse matrix operations widely applicable in neural networks: sparse matrix-dense matrix multiplication and sampled dense-dense matrix multiplication. Our kernels reach 27% of single-precision peak on Nvidia V100 GPUs. Using our kernels, we demonstrate sparse Transformer and MobileNet models that achieve 1.2-2.1x speedups and up to 12.8x memory savings without sacrificing accuracy.
FedFMC: Sequential Efficient Federated Learning on Non-iid Data
Venue: arXiv cs.LG 2020
Year: 2020

As a mechanism for devices to update a global model without sharing data, federated learning bridges the tension between the need for data and respect for privacy. However, classic FL methods like Federated Averaging struggle with non-iid data, a prevalent situation in the real world. Previous solutions are sub-optimal as they either employ a small shared global subset of data or greater number of models with increased communication costs. We propose FedFMC (Fork-Merge-Consolidate), a method that dynamically forks devices into updating different global models then merges and consolidates separate models into one. We first show the soundness of FedFMC on simple datasets, then run several experiments comparing against baseline approaches. These experiments show that FedFMC substantially improves upon earlier approaches to non-iid data in the federated learning context without using a globally shared subset of data nor increase communication costs.
V-Dream: Immersive Exploration of Generative Design Solution Space
Venue: arXiv cs.HC 2020
Year: 2020

Generative Design workflows have introduced alternative paradigms in the domain of computational design, allowing designers to generate large pools of valid solutions by defining a set of goals and constraints. However, analyzing and narrowing down the generated solution space, which usually consists of various high-dimensional properties, has been a major challenge in current generative workflows. By taking advantage of the interactive unbounded spatial exploration, and the visual immersion offered in virtual reality platforms, we propose V-Dream, a virtual reality generative analysis framework for exploring large-scale solution spaces. V-Dream proposes a hybrid search workflow in which a spatial stochastic search approach is combined with a recommender system allowing users to pick desired candidates and eliminate the undesired ones iteratively. In each cycle, V-Dream reorganizes the remaining options in clusters based on the defined features. Moreover, our framework allows users to inspect design solutions and evaluate their performance metrics in various hierarchical levels, assisting them in narrowing down the solution space through iterative cycles of search/select/re-clustering of the solutions in an immersive fashion. Finally, we present a prototype of our proposed framework, illustrating how users can navigate and narrow down desired solutions from a pool of over 16000 monitor stands generated by Autodesk's Dreamcatcher software.
Differentiable Language Model Adversarial Attacks on Categorical Sequence Classifiers
Venue: arXiv cs.LG 2020
Year: 2020

An adversarial attack paradigm explores various scenarios for the vulnerability of deep learning models: minor changes of the input can force a model failure. Most of the state of the art frameworks focus on adversarial attacks for images and other structured model inputs, but not for categorical sequences models. Successful attacks on classifiers of categorical sequences are challenging because the model input is tokens from finite sets, so a classifier score is non-differentiable with respect to inputs, and gradient-based attacks are not applicable. Common approaches deal with this problem working at a token level, while the discrete optimization problem at hand requires a lot of resources to solve. We instead use a fine-tuning of a language model for adversarial attacks as a generator of adversarial examples. To optimize the model, we define a differentiable loss function that depends on a surrogate classifier score and on a deep learning model that evaluates approximate edit distance. So, we control both the adversability of a generated sequence and its similarity to the initial sequence. As a result, we obtain semantically better samples. Moreover, they are resistant to adversarial training and adversarial detectors. Our model works for diverse datasets on bank transactions, electronic health records, and NLP datasets.
Analyzing the Real-World Applicability of DGA Classifiers
Venue: arXiv cs.CR 2020
Year: 2020

Separating benign domains from domains generated by DGAs with the help of a binary classifier is a well-studied problem for which promising performance results have been published. The corresponding multiclass task of determining the exact DGA that generated a domain enabling targeted remediation measures is less well studied. Selecting the most promising classifier for these tasks in practice raises a number of questions that have not been addressed in prior work so far. These include the questions on which traffic to train in which network and when, just as well as how to assess robustness against adversarial attacks. Moreover, it is unclear which features lead a classifier to a decision and whether the classifiers are real-time capable. In this paper, we address these issues and thus contribute to bringing DGA detection classifiers closer to practical use. In this context, we propose one novel classifier based on residual neural networks for each of the two tasks and extensively evaluate them as well as previously proposed classifiers in a unified setting. We not only evaluate their classification performance but also compare them with respect to explainability, robustness, and training and classification speed. Finally, we show that our newly proposed binary classifier generalizes well to other networks, is time-robust, and able to identify previously unknown DGAs.
From Discrete to Continuous Convolution Layers
Venue: arXiv cs.LG 2020
Year: 2020

A basic operation in Convolutional Neural Networks (CNNs) is spatial resizing of feature maps. This is done either by strided convolution (donwscaling) or transposed convolution (upscaling). Such operations are limited to a fixed filter moving at predetermined integer steps (strides). Spatial sizes of consecutive layers are related by integer scale factors, predetermined at architectural design, and remain fixed throughout training and inference time. We propose a generalization of the common Conv-layer, from a discrete layer to a Continuous Convolution (CC) Layer. CC Layers naturally extend Conv-layers by representing the filter as a learned continuous function over sub-pixel coordinates. This allows learnable and principled resizing of feature maps, to any size, dynamically and consistently across scales. Once trained, the CC layer can be used to output any scale/size chosen at inference time. The scale can be non-integer and differ between the axes. CC gives rise to new freedoms for architectural design, such as dynamic layer shapes at inference time, or gradual architectures where the size changes by a small factor at each layer. This gives rise to many desired CNN properties, new architectural design capabilities, and useful applications. We further show that current Conv-layers suffer from inherent misalignments, which are ameliorated by CC layers.
Systematic Attack Surface Reduction For Deployed Sentiment Analysis Models
Venue: arXiv cs.CR 2020
Year: 2020

This work proposes a structured approach to baselining a model, identifying attack vectors, and securing the machine learning models after deployment. This method for securing each model post deployment is called the BAD (Build, Attack, and Defend) Architecture. Two implementations of the BAD architecture are evaluated to quantify the adversarial life cycle for a black box Sentiment Analysis system. As a challenging diagnostic, the Jigsaw Toxic Bias dataset is selected as the baseline in our performance tool. Each implementation of the architecture will build a baseline performance report, attack a common weakness, and defend the incoming attack. As an important note: each attack surface demonstrated in this work is detectable and preventable. The goal is to demonstrate a viable methodology for securing a machine learning model in a production setting.
Graphs with Multiple Sources per Vertex
Venue: arXiv cs.LO 2020
Year: 2020

Several attempts have been made at constructing Abstract Meaning Representations (AMRs) compositionally, and recently the idea of using s-graphs with the HR-algebra (Koller, 2015) has been simplified to reduce the number of options when parsing (Groschwitz et al., 2017). This apply-modify algebra (AM-algebra) is a linguistically plausible graph algebra with two classes of operations, both of rank two: the apply operation is used to combine a predicate with its argument; the modify operation is used to modify a predicate. While the AM-algebra correctly handles relative clauses and complex cases of coordination, it cannot parse reflexive sentences like: "The raven washes herself." To facilitate processing of such reflexive sentences, this paper proposes to change the definition of s-graphs underlying the AM-algebra to allow vertices with multiple sources, and additionally proposes an adaption to the type system of the algebra to correctly handle such vertices.
$λ$-Regularized A-Optimal Design and its Approximation by $λ$-Regularized Proportional Volume Sampling
Venue: arXiv cs.DS 2020
Year: 2020

In this work, we study the $λ$-regularized $A$-optimal design problem and introduce the $λ$-regularized proportional volume sampling algorithm, generalized from [Nikolov, Singh, and Tantipongpipat, 2019], for this problem with the approximation guarantee that extends upon the previous work. In this problem, we are given vectors $v_1,\ldots,v_n\in\mathbb{R}^d$ in $d$ dimensions, a budget $k\leq n$, and the regularizer parameter $λ\geq0$, and the goal is to find a subset $S\subseteq [n]$ of size $k$ that minimizes the trace of $\left(\sum_{i\in S}v_iv_i^\top + λI_d\right)^{-1}$ where $I_d$ is the $d\times d$ identity matrix. The problem is motivated from optimal design in ridge regression, where one tries to minimize the expected squared error of the ridge regression predictor from the true coefficient in the underlying linear model. We introduce $λ$-regularized proportional volume sampling and give its polynomial-time implementation to solve this problem. We show its $(1+\fracε{\sqrt{1+λ'}})$-approximation for $k=Ω\left(\frac dε+\frac{\log 1/ε}{ε^2}\right)$ where $λ'$ is proportional to $λ$, extending the previous bound in [Nikolov, Singh, and Tantipongpipat, 2019] to the case $λ>0$ and obtaining asymptotic optimality as $λ\rightarrow \infty$.