OpenRaiser/Intern-Atlas huggingface dataset:
Oblivious and Semi-Oblivious Boundedness for Existential Rules
Venue: arXiv cs.AI 2020
Year: 2020

We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure, that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem. This report contains the paper published at IJCAI 2019 and an appendix with full proofs.
Symbolic Logic meets Machine Learning: A Brief Survey in Infinite Domains
Venue: arXiv cs.AI 2020
Year: 2020

The tension between deduction and induction is perhaps the most fundamental issue in areas such as philosophy, cognition and artificial intelligence (AI). The deduction camp concerns itself with questions about the expressiveness of formal languages for capturing knowledge about the world, together with proof systems for reasoning from such knowledge bases. The learning camp attempts to generalize from examples about partial descriptions about the world. In AI, historically, these camps have loosely divided the development of the field, but advances in cross-over areas such as statistical relational learning, neuro-symbolic systems, and high-level control have illustrated that the dichotomy is not very constructive, and perhaps even ill-formed. In this article, we survey work that provides further evidence for the connections between logic and learning. Our narrative is structured in terms of three strands: logic versus learning, machine learning for logic, and logic for machine learning, but naturally, there is considerable overlap. We place an emphasis on the following "sore" point: there is a common misconception that logic is for discrete properties, whereas probability theory and machine learning, more generally, is for continuous properties. We report on results that challenge this view on the limitations of logic, and expose the role that logic can play for learning in infinite domains.
The Limit of the Batch Size
Venue: arXiv cs.LG 2020
Year: 2020

Large-batch training is an efficient approach for current distributed deep learning systems. It has enabled researchers to reduce the ImageNet/ResNet-50 training from 29 hours to around 1 minute. In this paper, we focus on studying the limit of the batch size. We think it may provide a guidance to AI supercomputer and algorithm designers. We provide detailed numerical optimization instructions for step-by-step comparison. Moreover, it is important to understand the generalization and optimization performance of huge batch training. Hoffer et al. introduced "ultra-slow diffusion" theory to large-batch training. However, our experiments show contradictory results with the conclusion of Hoffer et al. We provide comprehensive experimental results and detailed analysis to study the limitations of batch size scaling and "ultra-slow diffusion" theory. For the first time we scale the batch size on ImageNet to at least a magnitude larger than all previous work, and provide detailed studies on the performance of many state-of-the-art optimization schemes under this setting. We propose an optimization recipe that is able to improve the top-1 test accuracy by 18% compared to the baseline.
Learning to map source code to software vulnerability using code-as-a-graph
Venue: arXiv cs.SE 2020
Year: 2020

We explore the applicability of Graph Neural Networks in learning the nuances of source code from a security perspective. Specifically, whether signatures of vulnerabilities in source code can be learned from its graph representation, in terms of relationships between nodes and edges. We create a pipeline we call AI4VA, which first encodes a sample source code into a Code Property Graph. The extracted graph is then vectorized in a manner which preserves its semantic information. A Gated Graph Neural Network is then trained using several such graphs to automatically extract templates differentiating the graph of a vulnerable sample from a healthy one. Our model outperforms static analyzers, classic machine learning, as well as CNN and RNN-based deep learning models on two of the three datasets we experiment with. We thus show that a code-as-graph encoding is more meaningful for vulnerability detection than existing code-as-photo and linear sequence encoding approaches. (Submitted Oct 2019, Paper #28, ICST)
To Pretrain or Not to Pretrain: Examining the Benefits of Pretraining on Resource Rich Tasks
Venue: arXiv cs.CL 2020
Year: 2020

Pretraining NLP models with variants of Masked Language Model (MLM) objectives has recently led to a significant improvements on many tasks. This paper examines the benefits of pretrained models as a function of the number of training samples used in the downstream task. On several text classification tasks, we show that as the number of training examples grow into the millions, the accuracy gap between finetuning BERT-based model and training vanilla LSTM from scratch narrows to within 1%. Our findings indicate that MLM-based models might reach a diminishing return point as the supervised data size increases significantly.
HyperFlow: Representing 3D Objects as Surfaces
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we present HyperFlow - a novel generative model that leverages hypernetworks to create continuous 3D object representations in a form of lightweight surfaces (meshes), directly out of point clouds. Efficient object representations are essential for many computer vision applications, including robotic manipulation and autonomous driving. However, creating those representations is often cumbersome, because it requires processing unordered sets of point clouds. Therefore, it is either computationally expensive, due to additional optimization constraints such as permutation invariance, or leads to quantization losses introduced by binning point clouds into discrete voxels. Inspired by mesh-based representations of objects used in computer graphics, we postulate a fundamentally different approach and represent 3D objects as a family of surfaces. To that end, we devise a generative model that uses a hypernetwork to return the weights of a Continuous Normalizing Flows (CNF) target network. The goal of this target network is to map points from a probability distribution into a 3D mesh. To avoid numerical instability of the CNF on compact support distributions, we propose a new Spherical Log-Normal function which models density of 3D points around object surfaces mimicking noise introduced by 3D capturing devices. As a result, we obtain continuous mesh-based object representations that yield better qualitative results than competing approaches, while reducing training time by over an order of magnitude.
Using Amazon Alexa APIs as a Source of Digital Evidence
Venue: arXiv cs.CR 2020
Year: 2020

With the release of Amazon Alexa and the first Amazon Echo device, the company revolutionised the smart home. It allowed their users to communicate with, and control, their smart home ecosystem purely using voice commands. However, this also means that Amazon processes and stores a large amount of personal data about their users, as these devices are always present and always listening in peoples' private homes. That makes this data a valuable source of evidence for investigators performing digital forensics. The Alexa Voice Service uses a series of APIs for communication between clients and the Amazon cloud. These APIs return a wide range of data related to the functionality of the device used. The first goal of this research was to clarify exactly what kind of information about the user is stored and accessible through these APIs. To do this, a combination of literature review and exploratory analysis was used to establish a list of all relevant APIs. Then, possible artefacts and conclusions to be drawn from their responses were identified and presented. Lastly, the perspective of the users was taken, and options for improving their privacy were reviewed. Specifically, the history of interaction between the user and Alexa is available through multiple APIs, and there are several options to delete it. It was determined that these options have different behaviours and that most of them do not remove all data related to user interaction.
On Effective Parallelization of Monte Carlo Tree Search
Venue: arXiv cs.LG 2020
Year: 2020

Despite its groundbreaking success in Go and computer games, Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree, which calls for effective parallelization. However, how to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. In this paper, we seek to lay its first theoretical foundation, by examining the potential performance loss caused by parallelization when achieving a desired speedup. In particular, we discover the necessary conditions of achieving a desirable parallelization performance, and highlight two of their practical benefits. First, by examining whether existing parallel MCTS algorithms satisfy these conditions, we identify key design principles that should be inherited by future algorithms, for example tracking the unobserved samples (used in WU-UCT (Liu et al., 2020)). We theoretically establish this essential design facilitates $\mathcal{O} ( \ln n + M / \sqrt{\ln n} )$ cumulative regret when the maximum tree depth is 2, where $n$ is the number of rollouts and $M$ is the number of workers. A regret of this form is highly desirable, as compared to $\mathcal{O} ( \ln n )$ regret incurred by a sequential counterpart, its excess part approaches zero as $n$ increases. Second, and more importantly, we demonstrate how the proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms. To illustrate this, we propose a new parallel MCTS algorithm, called BU-UCT, by following our theoretical guidelines. The newly proposed algorithm, albeit preliminary, out-performs four competitive baselines on 11 out of 15 Atari games. We hope our theoretical results could inspire future work of more effective parallel MCTS.
FANOK: Knockoffs in Linear Time
Venue: arXiv cs.LG 2020
Year: 2020

We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems. Identifying the knockoff distribution requires solving a large scale semidefinite program for which we derive several efficient methods. One handles generic covariance matrices, has a complexity scaling as $O(p^3)$ where $p$ is the ambient dimension, while another assumes a rank $k$ factor model on the covariance matrix to reduce this complexity bound to $O(pk^2)$. We also derive efficient procedures to both estimate factor models and sample knockoff covariates with complexity linear in the dimension. We test our methods on problems with $p$ as large as $500,000$.
On the use of human reference data for evaluating automatic image descriptions
Venue: arXiv cs.CL 2020
Year: 2020

Automatic image description systems are commonly trained and evaluated using crowdsourced, human-generated image descriptions. The best-performing system is then determined using some measure of similarity to the reference data (BLEU, Meteor, CIDER, etc). Thus, both the quality of the systems as well as the quality of the evaluation depends on the quality of the descriptions. As Section 2 will show, the quality of current image description datasets is insufficient. I argue that there is a need for more detailed guidelines that take into account the needs of visually impaired users, but also the feasibility of generating suitable descriptions. With high-quality data, evaluation of image description systems could use reference descriptions, but we should also look for alternatives.
A Model-Based Approach to Anomaly Detection Trading Detection Time and False Alarm Rate
Venue: arXiv cs.CR 2020
Year: 2020

The complexity and ubiquity of modern computing systems is a fertile ground for anomalies, including security and privacy breaches. In this paper, we propose a new methodology that addresses the practical challenges to implement anomaly detection approaches. Specifically, it is challenging to define normal behavior comprehensively and to acquire data on anomalies in diverse cloud environments. To tackle those challenges, we focus on anomaly detection approaches based on system performance signatures. In particular, performance signatures have the potential of detecting zero-day attacks, as those approaches are based on detecting performance deviations and do not require detailed knowledge of attack history. The proposed methodology leverages an analytical performance model and experimentation and allows to control the rate of false positives in a principled manner. The methodology is evaluated using the TPCx-V workload, which was profiled during a set of executions using resource exhaustion anomalies that emulate the effects of anomalies affecting system performance. The proposed approach was able to successfully detect the anomalies, with a low number of false positives (precision 90%-98%).
End-to-End Code Switching Language Models for Automatic Speech Recognition
Venue: arXiv cs.CL 2020
Year: 2020

In this paper, we particularly work on the code-switched text, one of the most common occurrences in the bilingual communities across the world. Due to the discrepancies in the extraction of code-switched text from an Automated Speech Recognition(ASR) module, and thereby extracting the monolingual text from the code-switched text, we propose an approach for extracting monolingual text using Deep Bi-directional Language Models(LM) such as BERT and other Machine Translation models, and also explore different ways of extracting code-switched text from the ASR model. We also explain the robustness of the model by comparing the results of Perplexity and other different metrics like WER, to the standard bi-lingual text output without any external information.
CNN Acceleration by Low-rank Approximation with Quantized Factors
Venue: arXiv cs.CV 2020
Year: 2020

The modern convolutional neural networks although achieve great results in solving complex computer vision tasks still cannot be effectively used in mobile and embedded devices due to the strict requirements for computational complexity, memory and power consumption. The CNNs have to be compressed and accelerated before deployment. In order to solve this problem the novel approach combining two known methods, low-rank tensor approximation in Tucker format and quantization of weights and feature maps (activations), is proposed. The greedy one-step and multi-step algorithms for the task of multilinear rank selection are proposed. The approach for quality restoration after applying Tucker decomposition and quantization is developed. The efficiency of our method is demonstrated for ResNet18 and ResNet34 on CIFAR-10, CIFAR-100 and Imagenet classification tasks. As a result of comparative analysis performed for other methods for compression and acceleration our approach showed its promising features.
High-performance cloud computing for exhaustive protein-protein docking
Venue: arXiv cs.DC 2020
Year: 2020

Public cloud computing environments, such as Amazon AWS, Microsoft Azure, and the Google Cloud Platform, have achieved remarkable improvements in computational performance in recent years, and are also expected to be able to perform massively parallel computing. As the cloud enables users to use thousands of CPU cores and GPU accelerators casually, and various software types can be used very easily by cloud images, the cloud is beginning to be used in the field of bioinformatics. In this study, we ported the original protein-protein interaction prediction (protein-protein docking) software, MEGADOCK, into Microsoft Azure as an example of an HPC cloud environment. A cloud parallel computing environment with up to 1,600 CPU cores and 960 GPUs was constructed using four CPU instance types and two GPU instance types, and the parallel computing performance was evaluated. Our MEGADOCK on Azure system showed a strong scaling value of 0.93 for the CPU instance when H16 instance with 100 instances were used compared to 50, and a strong scaling value of 0.89 for the GPU instance when NC24 instance with 20 were used compared to 5. Moreover, the results of the usage fee and total computation time supported that using a GPU instance reduced the computation time of MEGADOCK and the cloud usage fee required for the computation. The developed environment deployed on the cloud is highly portable, making it suitable for applications in which an on-demand and large-scale HPC environment is desirable.
Multilinear Algebra for Distributed Storage
Venue: arXiv cs.IT 2020
Year: 2020

An $(n, k, d, α, β, M)$-ERRC (exact-repair regenerating code) is a collection of $n$ nodes used to store a file. For a file of total size $M$, each node stores $α$ symbols, any $k$ nodes recover the file, and any $d$ nodes repair any other node via sending out $β$ symbols. We establish a multilinear algebra foundation to assemble $(n, k, d, α, β, M)$-ERRCs for all meaningful $(n, k, d)$ tuples. Our ERRCs tie the $α/M$-versus-$β/M$ trade-off with cascade codes, the best known construction for this trade-off. We give directions on how these ERRCs repair multiple failures.
Plug-and-Play Anomaly Detection with Expectation Maximization Filtering
Venue: arXiv cs.CV 2020
Year: 2020

Anomaly detection in crowds enables early rescue response. A plug-and-play smart camera for crowd surveillance has numerous constraints different from typical anomaly detection: the training data cannot be used iteratively; there are no training labels; and training and classification needs to be performed simultaneously. We tackle all these constraints with our approach in this paper. We propose a Core Anomaly-Detection (CAD) neural network which learns the motion behavior of objects in the scene with an unsupervised method. On average over standard datasets, CAD with a single epoch of training shows a percentage increase in Area Under the Curve (AUC) of 4.66% and 4.9% compared to the best results with convolutional autoencoders and convolutional LSTM-based methods, respectively. With a single epoch of training, our method improves the AUC by 8.03% compared to the convolutional LSTM-based approach. We also propose an Expectation Maximization filter which chooses samples for training the core anomaly-detection network. The overall framework improves the AUC compared to future frame prediction-based approach by 24.87% when crowd anomaly detection is performed on a video stream. We believe our work is the first step towards using deep learning methods with autonomous plug-and-play smart cameras for crowd anomaly detection.
Relational Fusion Networks: Graph Convolutional Networks for Road Networks
Venue: arXiv cs.LG 2020
Year: 2020

The application of machine learning techniques in the setting of road networks holds the potential to facilitate many important intelligent transportation applications. Graph Convolutional Networks (GCNs) are neural networks that are capable of leveraging the structure of a network. However, many implicit assumptions of GCNs do not apply to road networks. We introduce the Relational Fusion Network (RFN), a novel type of GCN designed specifically for road networks. In particular, we propose methods that outperform state-of-the-art GCNs by 21%-40% on two machine learning tasks in road networks. Furthermore, we show that state-of-the-art GCNs may fail to effectively leverage road network structure and may not generalize well to other road networks.
Quantitative Group Testing and the rank of random matrices
Venue: arXiv cs.IT 2020
Year: 2020

Given a random Bernoulli matrix $ A\in \{0,1\}^{m\times n} $, an integer $ 0< k < n $ and the vector $ y:=Ax $, where $ x \in \{0,1\}^n $ is of Hamming weight $ k $, the objective in the {\em Quantitative Group Testing} (QGT) problem is to recover $ x $. This problem is more difficult the smaller $m$ is. For parameter ranges of interest to us, known polynomial time algorithms require values of $m$ that are much larger than $k$. In this work, we define a seemingly easier problem that we refer to as {\em Subset Select}. Given the same input as in QGT, the objective in Subset Select is to return a subset $ S \subseteq [n] $ of cardinality $ m $, such that for all $ i\in [n] $, if $ x_i = 1 $ then $ i\in S $. We show that if the square submatrix of $A$ defined by the columns indexed by $S$ has nearly full rank, then from the solution of the Subset Select problem we can recover in polynomial-time the solution $x$ to the QGT problem. We conjecture that for every polynomial time Subset Select algorithm, the resulting output matrix will satisfy the desired rank condition. We prove the conjecture for some classes of algorithms. Using this reduction, we provide some examples of how to improve known QGT algorithms. Using theoretical analysis and simulations, we demonstrate that the modified algorithms solve the QGT problem for values of $ m $ that are smaller than those required for the original algorithms.
PERL: Pivot-based Domain Adaptation for Pre-trained Deep Contextualized Embedding Models
Venue: arXiv cs.CL 2020
Year: 2020

Pivot-based neural representation models have lead to significant progress in domain adaptation for NLP. However, previous works that follow this approach utilize only labeled data from the source domain and unlabeled data from the source and target domains, but neglect to incorporate massive unlabeled corpora that are not necessarily drawn from these domains. To alleviate this, we propose PERL: A representation learning model that extends contextualized word embedding models such as BERT with pivot-based fine-tuning. PERL outperforms strong baselines across 22 sentiment classification domain adaptation setups, improves in-domain model performance, yields effective reduced-size models and increases model stability.
An STPA-based Approach for Systematic Security Analysis of In-vehicle Diagnostic and Software Update Systems
Venue: arXiv cs.CR 2020
Year: 2020

The in-vehicle diagnostic and software update system, which supports remote diagnostic and Over-The-Air (OTA) software updates, is a critical attack goal in automobiles. Adversaries can inject malicious software into vehicles or steal sensitive information through communication channels. Therefore, security analysis, which identifies potential security issues, needs to be conducted in system design. However, existing security analyses of in-vehicle systems are threat-oriented, which start with threat identification and assess risks by brainstorming. In this paper, a system-oriented approach is proposed on the basis of the System-Theoretic Process Analysis (STPA). The proposed approach extends the original STPA from the perspective of data flows and is applicable for information-flow-based systems. Besides, we propose a general model for in-vehicle diagnostic and software update systems and use it to establish a security analysis guideline. In comparison with threat-oriented approaches, the proposed approach shifts from focusing on threats to system vulnerabilities and seems to be efficient to prevent the system from known or even unknown threats. Furthermore, as an extension of the STPA, which has been proven to be applicable to high level designs, the proposed approach can be well integrated into high-level analyses and perform co-design in different disciplines within a unified STPA framework.