OpenRaiser/Intern-Atlas huggingface dataset:
High Dimensional Robust Sparse Regression
Venue: arXiv cs.LG 2019
Year: 2019

We provide a novel -- and to the best of our knowledge, the first -- algorithm for high dimensional sparse regression with constant fraction of corruptions in explanatory and/or response variables. Our algorithm recovers the true sparse parameters with sub-linear sample complexity, in the presence of a constant fraction of arbitrary corruptions. Our main contribution is a robust variant of Iterative Hard Thresholding. Using this, we provide accurate estimators: when the covariance matrix in sparse regression is identity, our error guarantee is near information-theoretically optimal. We then deal with robust sparse regression with unknown structured covariance matrix. We propose a filtering algorithm which consists of a novel randomized outlier removal technique for robust sparse mean estimation that may be of interest in its own right: the filtering algorithm is flexible enough to deal with unknown covariance. Also, it is orderwise more efficient computationally than the ellipsoid algorithm. Using sub-linear sample complexity, our algorithm achieves the best known (and first) error guarantee. We demonstrate the effectiveness on large-scale sparse regression problems with arbitrary corruptions.
Why Botnets Work: Distributed Brute-Force Attacks Need No Synchronization
Venue: arXiv cs.IT 2019
Year: 2019

In September 2017, McAffee Labs quarterly report estimated that brute force attacks represent 20\% of total network attacks, making them the most prevalent type of attack ex-aequo with browser based vulnerabilities. These attacks have sometimes catastrophic consequences, and understanding their fundamental limits may play an important role in the risk assessment of password-secured systems, and in the design of better security protocols. While some solutions exist to prevent online brute-force attacks that arise from one single IP address, attacks performed by botnets are more challenging. In this paper, we analyze these distributed attacks by using a simplified model. Our aim is to understand the impact of distribution and asynchronization on the overall computational effort necessary to breach a system. Our result is based on Guesswork, a measure of the number of queries (guesses) required of an adversary before a correct sequence, such as a password, is found in an optimal attack. Guesswork is a direct surrogate for time and computational effort of guessing a sequence from a set of sequences with associated likelihoods. We model the lack of synchronization by a worst-case optimization in which the queries made by multiple adversarial agents are received in the worst possible order for the adversary, resulting in a min-max formulation. We show that, even without synchronization, and for sequences of growing length, the asymptotic optimal performance is achievable by using randomized guesses drawn from an appropriate distribution. Therefore, randomization is key for distributed asynchronous attacks. In other words, asynchronous guessers can asymptotically perform brute-force attacks as efficiently as synchronized guessers.
Characterizing Energy Efficiency of Wireless Transmission for Green Internet of Things: A Data-Oriented Approach
Venue: arXiv cs.IT 2019
Year: 2019

The growing popularity of Internet of Things (IoT) applications brings new challenges to the wireless communication community. Numerous smart devices and sensors within IoT will generate a massive amount of short data packets. Future wireless transmission systems need to support the reliable transmission of such small data with extremely high energy efficiency. In this article, we introduce a novel data-oriented approach for characterizing the energy efficiency of wireless transmission strategies for IoT applications. Specifically, we present new energy efficiency performance limits targeting at individual data transmission sessions. Through preliminary analysis on two channel-adaptive transmission strategies, we develop several important design guidelines on green transmission of small data. We also present several promising future applications of the proposed data-oriented energy efficiency characterization.
Contextual Centrality: Going Beyond Network Structures
Venue: arXiv cs.SI 2019
Year: 2019

Centrality is a fundamental network property which ranks nodes by their structural importance. However, structural importance may not suffice to predict successful diffusions in a wide range of applications, such as word-of-mouth marketing and political campaigns. In particular, nodes with high structural importance may contribute negatively to the objective of the diffusion. To address this problem, we propose contextual centrality, which integrates structural positions, the diffusion process, and, most importantly, nodal contributions to the objective of the diffusion. We perform an empirical analysis of the adoption of microfinance in Indian villages and weather insurance in Chinese villages. Results show that contextual centrality of the first-informed individuals has higher predictive power towards the eventual adoption outcomes than other standard centrality measures. Interestingly, when the product of diffusion rate $p$ and the largest eigenvalue $λ_1$ is larger than one and diffusion period is long, contextual centrality linearly scales with eigenvector centrality. This approximation reveals that contextual centrality identifies scenarios where a higher diffusion rate of individuals may negatively influence the cascade payoff. Further simulations on the synthetic and real-world networks show that contextual centrality has the advantage of selecting an individual whose local neighborhood generates a high cascade payoff when $p λ_1 < 1$. Under this condition, stronger homophily leads to higher cascade payoff. Our results suggest that contextual centrality captures more complicated dynamics on networks and has significant implications for applications, such as information diffusion, viral marketing, and political campaigns.
Tiling and Stitching Segmentation Output for Remote Sensing: Basic Challenges and Recommendations
Venue: arXiv cs.CV 2019
Year: 2019

In this work we consider the application of convolutional neural networks (CNNs) for pixel-wise labeling (a.k.a., semantic segmentation) of remote sensing imagery (e.g., aerial color or hyperspectral imagery). Remote sensing imagery is usually stored in the form of very large images, referred to as "tiles", which are too large to be segmented directly using most CNNs and their associated hardware. As a result, during label inference, smaller sub-images, called "patches", are processed individually and then "stitched" (concatenated) back together to create a tile-sized label map. This approach suffers from computational ineffiency and can result in discontinuities at output boundaries. We propose a simple alternative approach in which the input size of the CNN is dramatically increased only during label inference. This does not avoid stitching altogether, but substantially mitigates its limitations. We evaluate the performance of the proposed approach against a vonventional stitching approach using two popular segmentation CNN models and two large-scale remote sensing imagery datasets. The results suggest that the proposed approach substantially reduces label inference time, while also yielding modest overall label accuracy increases. This approach contributed to our wining entry (overall performance) in the INRIA building labeling competition.
Imaging with SPADs and DMDs: Seeing through Diffraction-Photons
Venue: arXiv cs.CV 2019
Year: 2019

This paper addresses the problem of imaging in the presence of diffraction-photons. Diffraction-photons arise from the low contrast ratio of DMDs ($\sim\,1000:1$), and very much degrade the quality of images captured by SPAD-based systems. Herein, a joint illumination-deconvolution scheme is designed to overcome diffraction-photons, enabling the acquisition of intensity and depth images. Additionally, a proof-of-concept experiment is conducted to demonstrate the viability of the designed scheme. It is shown that by co-designing the illumination and deconvolution phases of imaging, one can substantially overcome diffraction-photons.
Probabilistic Model of Visual Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Visual segmentation is a key perceptual function that partitions visual space and allows for detection, recognition and discrimination of objects in complex environments. The processes underlying human segmentation of natural images are still poorly understood. In part, this is because we lack segmentation models consistent with experimental and theoretical knowledge in visual neuroscience. Biological sensory systems have been shown to approximate probabilistic inference to interpret their inputs. This requires a generative model that captures both the statistics of the sensory inputs and expectations about the causes of those inputs. Following this hypothesis, we propose a probabilistic generative model of visual segmentation that combines knowledge about 1) the sensitivity of neurons in the visual cortex to statistical regularities in natural images; and 2) the preference of humans to form contiguous partitions of visual space. We develop an efficient algorithm for training and inference based on expectation-maximization and validate it on synthetic data. Importantly, with the appropriate choice of the prior, we derive an intuitive closed--form update rule for assigning pixels to segments: at each iteration, the pixel assignment probabilities to segments is the sum of the evidence (i.e. local pixel statistics) and prior (i.e. the assignments of neighboring pixels) weighted by their relative uncertainty. The model performs competitively on natural images from the Berkeley Segmentation Dataset (BSD), and we illustrate how the likelihood and prior components improve segmentation relative to traditional mixture models. Furthermore, our model explains some variability across human subjects as reflecting local uncertainty about the number of segments. Our model thus provides a viable approach to probe human visual segmentation.
On Efficient Domination for Some Classes of $H$-Free Bipartite Graphs
Venue: arXiv cs.DM 2019
Year: 2019

A vertex set $D$ in a finite undirected graph $G$ is an {\em efficient dominating set} (\emph{e.d.s.}\ for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$. The \emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d.s.\ in $G$, is known to be \NP-complete even for very restricted $H$-free graph classes such as for $2P_3$-free chordal graphs while it is solvable in polynomial time for $P_6$-free graphs. Here we focus on $H$-free bipartite graphs: We show that (weighted) ED can be solved in polynomial time for $H$-free bipartite graphs when $H$ is $P_7$ or $\ell P_4$ for fixed $\ell$, and similarly for $P_9$-free bipartite graphs with vertex degree at most 3, and when $H$ is $S_{2,2,4}$. Moreover, we show that ED is \NP-complete for bipartite graphs with diameter at most 6.
A Review of Challenges and Opportunities in Machine Learning for Health
Venue: arXiv cs.LG 2019
Year: 2019

Modern electronic health records (EHRs) provide data to answer clinically meaningful questions. The growing data in EHRs makes healthcare ripe for the use of machine learning. However, learning in a clinical setting presents unique challenges that complicate the use of common machine learning methodologies. For example, diseases in EHRs are poorly labeled, conditions can encompass multiple underlying endotypes, and healthy individuals are underrepresented. This article serves as a primer to illuminate these challenges and highlights opportunities for members of the machine learning community to contribute to healthcare.
Implicit Bias of Gradient Descent on Linear Convolutional Networks
Venue: arXiv cs.LG 2019
Year: 2019

We show that gradient descent on full-width linear convolutional networks of depth $L$ converges to a linear predictor related to the $\ell_{2/L}$ bridge penalty in the frequency domain. This is in contrast to linearly fully connected networks, where gradient descent converges to the hard margin linear support vector machine solution, regardless of depth.
Quantifying the dynamics of topical fluctuations in language
Venue: arXiv cs.CL 2019
Year: 2019

The availability of large diachronic corpora has provided the impetus for a growing body of quantitative research on language evolution and meaning change. The central quantities in this research are token frequencies of linguistic elements in texts, with changes in frequency taken to reflect the popularity or selective fitness of an element. However, corpus frequencies may change for a wide variety of reasons, including purely random sampling effects, or because corpora are composed of contemporary media and fiction texts within which the underlying topics ebb and flow with cultural and socio-political trends. In this work, we introduce a simple model for controlling for topical fluctuations in corpora - the topical-cultural advection model - and demonstrate how it provides a robust baseline of variability in word frequency changes over time. We validate the model on a diachronic corpus spanning two centuries, and a carefully-controlled artificial language change scenario, and then use it to correct for topical fluctuations in historical time series. Finally, we use the model to show that the emergence of new words typically corresponds with the rise of a trending topic. This suggests that some lexical innovations occur due to growing communicative need in a subspace of the lexicon, and that the topical-cultural advection model can be used to quantify this.
Principled Network Reliability Approximation: A Counting-Based Approach
Venue: arXiv cs.DS 2019
Year: 2019

As engineered systems expand, become more interdependent, and operate in real-time, reliability assessment is indispensable to support investment and decision making. However, network reliability problems are known to be #P-complete, a computational complexity class largely believed to be intractable. The computational intractability of network reliability motivates our quest for reliable approximations. Based on their theoretical foundations, available methods can be grouped as follows: (i) exact or bounds, (ii) guarantee-less sampling, and (iii) probably approximately correct (PAC). Group (i) is well regarded due to its useful byproducts, but it does not scale in practice. Group (ii) scales well and verifies desirable properties, such as the bounded relative error, but it lacks error guarantees. Group (iii) is of great interest when precision and scalability are required, as it harbors computationally feasible approximation schemes with PAC-guarantees. We give a comprehensive review of classical methods before introducing modern techniques and our developments. We introduce K-RelNet, an extended counting-based estimation method that delivers PAC-guarantees for the K-terminal reliability problem. Then, we test methods' performance using various benchmark systems. We highlight the range of application of algorithms and provide the foundation for future resilience engineering as it increasingly necessitates methods for uncertainty quantification in complex systems.
DRCD: a Chinese Machine Reading Comprehension Dataset
Venue: arXiv cs.CL 2019
Year: 2019

In this paper, we introduce DRCD (Delta Reading Comprehension Dataset), an open domain traditional Chinese machine reading comprehension (MRC) dataset. This dataset aimed to be a standard Chinese machine reading comprehension dataset, which can be a source dataset in transfer learning. The dataset contains 10,014 paragraphs from 2,108 Wikipedia articles and 30,000+ questions generated by annotators. We build a baseline model that achieves an F1 score of 89.59%. F1 score of Human performance is 93.30%.
Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
Venue: arXiv cs.IT 2019
Year: 2019

We consider a scenario involving computations over a massive dataset stored distributedly across multiple workers, which is at the core of distributed learning algorithms. We propose Lagrange Coded Computing (LCC), a new framework to simultaneously provide (1) resiliency against stragglers that may prolong computations; (2) security against Byzantine (or malicious) workers that deliberately modify the computation for their benefit; and (3) (information-theoretic) privacy of the dataset amidst possible collusion of workers. LCC, which leverages the well-known Lagrange polynomial to create computation redundancy in a novel coded form across workers, can be applied to any computation scenario in which the function of interest is an arbitrary multivariate polynomial of the input dataset, hence covering many computations of interest in machine learning. LCC significantly generalizes prior works to go beyond linear computations. It also enables secure and private computing in distributed settings, improving the computation and communication efficiency of the state-of-the-art. Furthermore, we prove the optimality of LCC by showing that it achieves the optimal tradeoff between resiliency, security, and privacy, i.e., in terms of tolerating the maximum number of stragglers and adversaries, and providing data privacy against the maximum number of colluding workers. Finally, we show via experiments on Amazon EC2 that LCC speeds up the conventional uncoded implementation of distributed least-squares linear regression by up to $13.43\times$, and also achieves a $2.36\times$-$12.65\times$ speedup over the state-of-the-art straggler mitigation strategies.
Deep Mixture of Experts via Shallow Embedding
Venue: arXiv cs.CV 2019
Year: 2019

Larger networks generally have greater representational power at the cost of increased computational complexity. Sparsifying such networks has been an active area of research but has been generally limited to static regularization or dynamic approaches using reinforcement learning. We explore a mixture of experts (MoE) approach to deep dynamic routing, which activates certain experts in the network on a per-example basis. Our novel DeepMoE architecture increases the representational power of standard convolutional networks by adaptively sparsifying and recalibrating channel-wise features in each convolutional layer. We employ a multi-headed sparse gating network to determine the selection and scaling of channels for each input, leveraging exponential combinations of experts within a single convolutional network. Our proposed architecture is evaluated on four benchmark datasets and tasks, and we show that Deep-MoEs are able to achieve higher accuracy with lower computation than standard convolutional networks.
Set-based Obfuscation for Strong PUFs against Machine Learning Attacks
Venue: arXiv cs.CR 2019
Year: 2019

Strong physical unclonable function (PUF) is a promising solution for device authentication in resourceconstrained applications but vulnerable to machine learning attacks. In order to resist such attack, many defenses have been proposed in recent years. However, these defenses incur high hardware overhead, degenerate reliability and are inefficient against advanced machine learning attacks such as approximation attacks. In order to address these issues, we propose a Random Set-based Obfuscation (RSO) for Strong PUFs to resist machine learning attacks. The basic idea is that several stable responses are derived from the PUF itself and pre-stored as the set for obfuscation in the testing phase, and then a true random number generator is used to select any two keys to obfuscate challenges and responses with XOR operations. When the number of challenge-response pairs (CRPs) collected by the attacker exceeds the given threshold, the set will be updated immediately. In this way, machine learning attacks can be prevented with extremely low hardware overhead. Experimental results show that for a 64x64 Arbiter PUF, when the size of set is 32 and even if 1 million CRPs are collected by attackers, the prediction accuracies of Logistic regression, support vector machines, artificial neural network, convolutional neural network and covariance matrix adaptive evolutionary strategy are about 50% which is equivalent to the random guessing.
Deep supervision with additional labels for retinal vessel segmentation task
Venue: arXiv cs.CV 2019
Year: 2019

Automatic analysis of retinal blood images is of vital importance in diagnosis tasks of retinopathy. Segmenting vessels accurately is a fundamental step in analysing retinal images. However, it is usually difficult due to various imaging conditions, low image contrast and the appearance of pathologies such as micro-aneurysms. In this paper, we propose a novel method with deep neural networks to solve this problem. We utilize U-net with residual connection to detect vessels. To achieve better accuracy, we introduce an edge-aware mechanism, in which we convert the original task into a multi-class task by adding additional labels on boundary areas. In this way, the network will pay more attention to the boundary areas of vessels and achieve a better performance, especially in tiny vessels detecting. Besides, side output layers are applied in order to give deep supervision and therefore help convergence. We train and evaluate our model on three databases: DRIVE, STARE, and CHASEDB1. Experimental results show that our method has a comparable performance with AUC of 97.99% on DRIVE and an efficient running time compared to the state-of-the-art methods.
Conditional Linear Regression
Venue: arXiv cs.LG 2019
Year: 2019

Work in machine learning and statistics commonly focuses on building models that capture the vast majority of data, possibly ignoring a segment of the population as outliers. However, there does not often exist a good model on the whole dataset, so we seek to find a small subset where there exists a useful model. We are interested in finding a linear rule capable of achieving more accurate predictions for just a segment of the population. We give an efficient algorithm with theoretical analysis for the conditional linear regression task, which is the joint task of identifying a significant segment of the population, described by a k-DNF, along with its linear regression fit.
Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation
Venue: arXiv cs.LG 2019
Year: 2019

Generating novel graph structures that optimize given objectives while obeying some given underlying rules is fundamental for chemistry, biology and social science research. This is especially important in the task of molecular graph generation, whose goal is to discover novel molecules with desired properties such as drug-likeness and synthetic accessibility, while obeying physical laws such as chemical valency. However, designing models to find molecules that optimize desired properties while incorporating highly complex and non-differentiable rules remains to be a challenging task. Here we propose Graph Convolutional Policy Network (GCPN), a general graph convolutional network based model for goal-directed graph generation through reinforcement learning. The model is trained to optimize domain-specific rewards and adversarial loss through policy gradient, and acts in an environment that incorporates domain-specific rules. Experimental results show that GCPN can achieve 61% improvement on chemical property optimization over state-of-the-art baselines while resembling known molecules, and achieve 184% improvement on the constrained property optimization task.