OpenRaiser/Intern-Atlas huggingface dataset:
Single neuron-based neural networks are as efficient as dense deep neural networks in binary and multi-class recognition problems
Venue: arXiv cs.LG 2019
Year: 2019

Recent advances in neuroscience have revealed many principles about neural processing. In particular, many biological systems were found to reconfigure/recruit single neurons to generate multiple kinds of decisions. Such findings have the potential to advance our understanding of the design and optimization process of artificial neural networks. Previous work demonstrated that dense neural networks are needed to shape complex decision surfaces required for AI-level recognition tasks. We investigate the ability to model high dimensional recognition problems using single or several neurons networks that are relatively easier to train. By employing three datasets, we test the use of a population of single neuron networks in performing multi-class recognition tasks. Surprisingly, we find that sparse networks can be as efficient as dense networks in both binary and multi-class tasks. Moreover, single neuron networks demonstrate superior performance in binary classification scheme and competing results when combined for multi-class recognition.
A Simple Saliency Method That Passes the Sanity Checks
Venue: arXiv cs.LG 2019
Year: 2019

There is great interest in "saliency methods" (also called "attribution methods"), which give "explanations" for a deep net's decision, by assigning a "score" to each feature/pixel in the input. Their design usually involves credit-assignment via the gradient of the output with respect to input. Recently Adebayo et al. [arXiv:1810.03292] questioned the validity of many of these methods since they do not pass simple *sanity checks* which test whether the scores shift/vanish when layers of the trained net are randomized, or when the net is retrained using random labels for inputs. We propose a simple fix to existing saliency methods that helps them pass sanity checks, which we call "competition for pixels". This involves computing saliency maps for all possible labels in the classification task, and using a simple competition among them to identify and remove less relevant pixels from the map. The simplest variant of this is "Competitive Gradient $\odot$ Input (CGI)": it is efficient, requires no additional training, and uses only the input and gradient. Some theoretical justification is provided for it (especially for ReLU networks) and its performance is empirically demonstrated.
Closed-Loop Adaptation for Weakly-Supervised Semantic Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Weakly-supervised semantic segmentation aims to assign each pixel a semantic category under weak supervisions, such as image-level tags. Most of existing weakly-supervised semantic segmentation methods do not use any feedback from segmentation output and can be considered as open-loop systems. They are prone to accumulated errors because of the static seeds and the sensitive structure information. In this paper, we propose a generic self-adaptation mechanism for existing weakly-supervised semantic segmentation methods by introducing two feedback chains, thus constituting a closed-loop system. Specifically, the first chain iteratively produces dynamic seeds by incorporating cross-image structure information, whereas the second chain further expands seed regions by a customized random walk process to reconcile inner-image structure information characterized by superpixels. Experiments on PASCAL VOC 2012 suggest that our network outperforms state-of-the-art methods with significantly less computational and memory burden.
Accelerating Monte Carlo Bayesian Inference via Approximating Predictive Uncertainty over Simplex
Venue: arXiv cs.LG 2019
Year: 2019

Estimating the predictive uncertainty of a Bayesian learning model is critical in various decision-making problems, e.g., reinforcement learning, detecting adversarial attack, self-driving car. As the model posterior is almost always intractable, most efforts were made on finding an accurate approximation the true posterior. Even though a decent estimation of the model posterior is obtained, another approximation is required to compute the predictive distribution over the desired output. A common accurate solution is to use Monte Carlo (MC) integration. However, it needs to maintain a large number of samples, evaluate the model repeatedly and average multiple model outputs. In many real-world cases, this is computationally prohibitive. In this work, assuming that the exact posterior or a decent approximation is obtained, we propose a generic framework to approximate the output probability distribution induced by model posterior with a parameterized model and in an amortized fashion. The aim is to approximate the true uncertainty of a specific Bayesian model, meanwhile alleviating the heavy workload of MC integration at testing time. The proposed method is universally applicable to Bayesian classification models that allow for posterior sampling. Theoretically, we show that the idea of amortization incurs no additional costs on approximation performance. Empirical results validate the strong practical performance of our approach.
RESDN: A Novel Metric and Method for Energy Efficient Routing in Software Defined Networks
Venue: arXiv cs.NI 2019
Year: 2019

Software-defined networking (SDN) paradigm, with the flexible and logically centralized control, enables dynamically minimizing the network energy consumption by redirecting paths of packets. However, the links and switches are designed to accommodate maximum traffic volume and their power consumption is not traffic proportional. Moreover, there exists a trade-off between energy efficiency and network performance that need to be considered together. Addressing these issues, we propose an energy efficiency metric named Ratio for Energy Saving in SDN (RESDN) that quantifies energy efficiency based on link utility intervals. We provide integer programming formulation and method for maximizing the RESDN of the network. To the best of our knowledge, RESDN approach is novel as it measures how links are profitably utilized in terms of the amount of energy they consume with respect to their utility. We analyze our approach considering various metrics of interest, and different types of SDN enabled switches. Experiments show that maximizing the RESDN value improves energy efficiency while maintaining acceptable network performance. In comparison to state-of-the-art utility-based heuristics, RESDN method achieves up to 30% better ratio for energy saving, 14.7 watts per switch power saving, 38% link saving, 2 hops decrease in average path length, 5% improved traffic proportionality.
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set
Venue: arXiv cs.DS 2019
Year: 2019

Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning heuristic. In this paper, we prove that this empirically fast algorithm runs in $O(3.460^k n)$ time, where $k$ is the solution size. This improves the previous best $O(3.619^k n)$-time deterministic algorithm obtained by Kociumaka and Pilipczuk.
From User-independent to Personal Human Activity Recognition Models Exploiting the Sensors of a Smartphone
Venue: arXiv cs.LG 2019
Year: 2019

In this study, a novel method to obtain user-dependent human activity recognition models unobtrusively by exploiting the sensors of a smartphone is presented. The recognition consists of two models: sensor fusion-based user-independent model for data labeling and single sensor-based user-dependent model for final recognition. The functioning of the presented method is tested with human activity data set, including data from accelerometer and magnetometer, and with two classifiers. Comparison of the detection accuracies of the proposed method to traditional user-independent model shows that the presented method has potential, in nine cases out of ten it is better than the traditional method, but more experiments using different sensor combinations should be made to show the full potential of the method.
Complex-valued neural networks for machine learning on non-stationary physical data
Venue: arXiv cs.LG 2019
Year: 2019

Deep learning has become an area of interest in most scientific areas, including physical sciences. Modern networks apply real-valued transformations on the data. Particularly, convolutions in convolutional neural networks discard phase information entirely. Many deterministic signals, such as seismic data or electrical signals, contain significant information in the phase of the signal. We explore complex-valued deep convolutional networks to leverage non-linear feature maps. Seismic data commonly has a lowcut filter applied, to attenuate noise from ocean waves and similar long wavelength contributions. Discarding the phase information leads to low-frequency aliasing analogous to the Nyquist-Shannon theorem for high frequencies. In non-stationary data, the phase content can stabilize training and improve the generalizability of neural networks. While it has been shown that phase content can be restored in deep neural networks, we show how including phase information in feature maps improves both training and inference from deterministic physical data. Furthermore, we show that the reduction of parameters in a complex network outperforms larger real-valued networks.
A Boxology of Design Patterns for Hybrid Learning and Reasoning Systems
Venue: arXiv cs.AI 2019
Year: 2019

We propose a set of compositional design patterns to describe a large variety of systems that combine statistical techniques from machine learning with symbolic techniques from knowledge representation. As in other areas of computer science (knowledge engineering, software engineering, ontology engineering, process mining and others), such design patterns help to systematize the literature, clarify which combinations of techniques serve which purposes, and encourage re-use of software components. We have validated our set of compositional design patterns against a large body of recent literature.
Probabilistic Decoupling of Labels in Classification
Venue: arXiv cs.LG 2019
Year: 2019

We investigate probabilistic decoupling of labels supplied for training, from the underlying classes for prediction. Decoupling enables an inference scheme general enough to implement many classification problems, including supervised, semi-supervised, positive-unlabelled, noisy-label and suggests a general solution to the multi-positive-unlabelled learning problem. We test the method on the Fashion MNIST and 20 News Groups datasets for performance benchmarks, where we simulate noise, partial labelling etc.
Relationship Estimation Metrics for Binary SoC Data
Venue: arXiv cs.DC 2019
Year: 2019

System-on-Chip (SoC) designs are used in every aspect of computing and their optimization is a difficult but essential task in today's competitive market. Data taken from SoCs to achieve this is often characterised by very long concurrent bit vectors which have unknown relationships to each other. This paper explains and empirically compares the accuracy of several methods used to detect the existence of these relationships in a wide range of systems. A probabilistic model is used to construct and test a large number of SoC-like systems with known relationships which are compared with the estimated relationships to give accuracy scores. The metrics Ċov and Dep based on covariance and independence are demonstrated to be the most useful, whereas metrics based on the Hamming distance and geometric approaches are shown to be less useful for detecting the presence of relationships between SoC data.
GlyphGAN: Style-Consistent Font Generation Based on Generative Adversarial Networks
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we propose GlyphGAN: style-consistent font generation based on generative adversarial networks (GANs). GANs are a framework for learning a generative model using a system of two neural networks competing with each other. One network generates synthetic images from random input vectors, and the other discriminates between synthetic and real images. The motivation of this study is to create new fonts using the GAN framework while maintaining style consistency over all characters. In GlyphGAN, the input vector for the generator network consists of two vectors: character class vector and style vector. The former is a one-hot vector and is associated with the character class of each sample image during training. The latter is a uniform random vector without supervised information. In this way, GlyphGAN can generate an infinite variety of fonts with the character and style independently controlled. Experimental results showed that fonts generated by GlyphGAN have style consistency and diversity different from the training images without losing their legibility.
ATTACK2VEC: Leveraging Temporal Word Embeddings to Understand the Evolution of Cyberattacks
Venue: arXiv cs.CR 2019
Year: 2019

Despite the fact that cyberattacks are constantly growing in complexity, the research community still lacks effective tools to easily monitor and understand them. In particular, there is a need for techniques that are able to not only track how prominently certain malicious actions, such as the exploitation of specific vulnerabilities, are exploited in the wild, but also (and more importantly) how these malicious actions factor in as attack steps in more complex cyberattacks. In this paper we present ATTACK2VEC, a system that uses temporal word embeddings to model how attack steps are exploited in the wild, and track how they evolve. We test ATTACK2VEC on a dataset of billions of security events collected from the customers of a commercial Intrusion Prevention System over a period of two years, and show that our approach is effective in monitoring the emergence of new attack strategies in the wild and in flagging which attack steps are often used together by attackers (e.g., vulnerabilities that are frequently exploited together). ATTACK2VEC provides a useful tool for researchers and practitioners to better understand cyberattacks and their evolution, and use this knowledge to improve situational awareness and develop proactive defenses.
Privacy-Preserving Causal Inference via Inverse Probability Weighting
Venue: arXiv cs.LG 2019
Year: 2019

The use of inverse probability weighting (IPW) methods to estimate the causal effect of treatments from observational studies is widespread in econometrics, medicine and social sciences. Although these studies often involve sensitive information, thus far there has been no work on privacy-preserving IPW methods. We address this by providing a novel framework for privacy-preserving IPW (PP-IPW) methods. We include a theoretical analysis of the effects of our proposed privatisation procedure on the estimated average treatment effect, and evaluate our PP-IPW framework on synthetic, semi-synthetic and real datasets. The empirical results are consistent with our theoretical findings.
Top-k Combinatorial Bandits with Full-Bandit Feedback
Venue: arXiv cs.LG 2019
Year: 2019

Top-k Combinatorial Bandits generalize multi-armed bandits, where at each round any subset of $k$ out of $n$ arms may be chosen and the sum of the rewards is gained. We address the full-bandit feedback, in which the agent observes only the sum of rewards, in contrast to the semi-bandit feedback, in which the agent observes also the individual arms' rewards. We present the Combinatorial Successive Accepts and Rejects (CSAR) algorithm, which generalizes SAR (Bubeck et al, 2013) for top-k combinatorial bandits. Our main contribution is an efficient sampling scheme that uses Hadamard matrices in order to estimate accurately the individual arms' expected rewards. We discuss two variants of the algorithm, the first minimizes the sample complexity and the second minimizes the regret. We also prove a lower bound on sample complexity, which is tight for $k=O(1)$. Finally, we run experiments and show that our algorithm outperforms other methods.
Fallout: Reading Kernel Writes From User Space
Venue: arXiv cs.CR 2019
Year: 2019

Recently, out-of-order execution, an important performance optimization in modern high-end processors, has been revealed to pose a significant security threat, allowing information leaks across security domains. In particular, the Meltdown attack leaks information from the operating system kernel to user space, completely eroding the security of the system. To address this and similar attacks, without incurring the performance costs of software countermeasures, Intel includes hardware-based defenses in its recent Coffee Lake R processors. In this work, we show that the recent hardware defenses are not sufficient. Specifically, we present Fallout, a new transient execution attack that leaks information from a previously unexplored microarchitectural component called the store buffer. We show how unprivileged user processes can exploit Fallout to reconstruct privileged information recently written by the kernel. We further show how Fallout can be used to bypass kernel address space randomization. Finally, we identify and explore microcode assists as a hitherto ignored cause of transient execution. Fallout affects all processor generations we have tested. However, we notice a worrying regression, where the newer Coffee Lake R processors are more vulnerable to Fallout than older generations.
Geolocating Political Events in Text
Venue: arXiv cs.CL 2019
Year: 2019

This work introduces a general method for automatically finding the locations where political events in text occurred. Using a novel set of 8,000 labeled sentences, I create a method to link automatically extracted events and locations in text. The model achieves human level performance on the annotation task and outperforms previous event geolocation systems. It can be applied to most event extraction systems across geographic contexts. I formalize the event--location linking task, describe the neural network model, describe the potential uses of such a system in political science, and demonstrate a workflow to answer an open question on the role of conventional military offensives in causing civilian casualties in the Syrian civil war.
Sub-Turing Islands in the Wild
Venue: arXiv cs.PL 2019
Year: 2019

Recently, there has been growing debate as to whether or not static analysis can be truly sound. In spite of this concern, research on techniques seeking to at least partially answer undecidable questions has a long history. However, little attention has been given to the more empirical question of how often an exact solution might be given to a question despite the question being, at least in theory, undecidable. This paper investigates this issue by exploring sub-Turing islands -- regions of code for which a question of interest is decidable. We define such islands and then consider how to identify them. We implemented Cook, a prototype for finding sub-Turing islands and applied it to a corpus of 1100 Android applications, containing over 2 million methods. Results reveal that 55\% of the all methods are sub-Turing. Our results also provide empirical, scientific evidence for the scalability of sub-Turing island identification. Sub-Turing identification has many downstream applications, because islands are so amenable to static analysis. We illustrate two downstream uses of the analysis. In the first, we found that over 37\% of the verification conditions associated with runtime exceptions fell within sub-Turing islands and thus are statically decidable. A second use of our analysis is during code review where it provides guidance to developers. The sub-Turing islands from our study turns out to contain significantly fewer bugs than `theswamp' (non sub-Turing methods). The greater bug density in the swamp is unsurprising; the fact that bugs remain prevalent in islands is, however, surprising: these are bugs whose repair can be fully automated.
Learning to Crawl
Venue: arXiv cs.LG 2019
Year: 2019

Web crawling is the problem of keeping a cache of webpages fresh, i.e., having the most recent copy available when a page is requested. This problem is usually coupled with the natural restriction that the bandwidth available to the web crawler is limited. The corresponding optimization problem was solved optimally by Azar et al. [2018] under the assumption that, for each webpage, both the elapsed time between two changes and the elapsed time between two requests follow a Poisson distribution with known parameters. In this paper, we study the same control problem but under the assumption that the change rates are unknown a priori, and thus we need to estimate them in an online fashion using only partial observations (i.e., single-bit signals indicating whether the page has changed since the last refresh). As a point of departure, we characterise the conditions under which one can solve the problem with such partial observability. Next, we propose a practical estimator and compute confidence intervals for it in terms of the elapsed time between the observations. Finally, we show that the explore-and-commit algorithm achieves an $\mathcal{O}(\sqrt{T})$ regret with a carefully chosen exploration horizon. Our simulation study shows that our online policy scales well and achieves close to optimal performance for a wide range of the parameters.
Large Scale Question Paraphrase Retrieval with Smoothed Deep Metric Learning
Venue: arXiv cs.CL 2019
Year: 2019

The goal of a Question Paraphrase Retrieval (QPR) system is to retrieve equivalent questions that result in the same answer as the original question. Such a system can be used to understand and answer rare and noisy reformulations of common questions by mapping them to a set of canonical forms. This has large-scale applications for community Question Answering (cQA) and open-domain spoken language question answering systems. In this paper we describe a new QPR system implemented as a Neural Information Retrieval (NIR) system consisting of a neural network sentence encoder and an approximate k-Nearest Neighbour index for efficient vector retrieval. We also describe our mechanism to generate an annotated dataset for question paraphrase retrieval experiments automatically from question-answer logs via distant supervision. We show that the standard loss function in NIR, triplet loss, does not perform well with noisy labels. We propose smoothed deep metric loss (SDML) and with our experiments on two QPR datasets we show that it significantly outperforms triplet loss in the noisy label setting.
Bandlimiting Neural Networks Against Adversarial Attacks
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we study the adversarial attack and defence problem in deep learning from the perspective of Fourier analysis. We first explicitly compute the Fourier transform of deep ReLU neural networks and show that there exist decaying but non-zero high frequency components in the Fourier spectrum of neural networks. We demonstrate that the vulnerability of neural networks towards adversarial samples can be attributed to these insignificant but non-zero high frequency components. Based on this analysis, we propose to use a simple post-averaging technique to smooth out these high frequency components to improve the robustness of neural networks against adversarial attacks. Experimental results on the ImageNet dataset have shown that our proposed method is universally effective to defend many existing adversarial attacking methods proposed in the literature, including FGSM, PGD, DeepFool and C&W attacks. Our post-averaging method is simple since it does not require any re-training, and meanwhile it can successfully defend over 95% of the adversarial samples generated by these methods without introducing any significant performance degradation (less than 1%) on the original clean images.