OpenRaiser/Intern-Atlas huggingface dataset:
ImageNet Training in Minutes
Venue: arXiv cs.CV 2018
Year: 2018

Finishing 90-epoch ImageNet-1k training with ResNet-50 on a NVIDIA M40 GPU takes 14 days. This training requires 10^18 single precision operations in total. On the other hand, the world's current fastest supercomputer can finish 2 * 10^17 single precision operations per second (Dongarra et al 2017, https://www.top500.org/lists/2017/06/). If we can make full use of the supercomputer for DNN training, we should be able to finish the 90-epoch ResNet-50 training in one minute. However, the current bottleneck for fast DNN training is in the algorithm level. Specifically, the current batch size (e.g. 512) is too small to make efficient use of many processors. For large-scale DNN training, we focus on using large-batch data-parallelism synchronous SGD without losing accuracy in the fixed epochs. The LARS algorithm (You, Gitman, Ginsburg, 2017, arXiv:1708.03888) enables us to scale the batch size to extremely large case (e.g. 32K). We finish the 100-epoch ImageNet training with AlexNet in 11 minutes on 1024 CPUs. About three times faster than Facebook's result (Goyal et al 2017, arXiv:1706.02677), we finish the 90-epoch ImageNet training with ResNet-50 in 20 minutes on 2048 KNLs without losing accuracy. State-of-the-art ImageNet training speed with ResNet-50 is 74.9% top-1 test accuracy in 15 minutes. We got 74.9% top-1 test accuracy in 64 epochs, which only needs 14 minutes. Furthermore, when we increase the batch size to above 16K, our accuracy is much higher than Facebook's on corresponding batch sizes. Our source code is available upon request.
Feature-Fused SSD: Fast Detection for Small Objects
Venue: arXiv cs.CV 2018
Year: 2018

Small objects detection is a challenging task in computer vision due to its limited resolution and information. In order to solve this problem, the majority of existing methods sacrifice speed for improvement in accuracy. In this paper, we aim to detect small objects at a fast speed, using the best object detector Single Shot Multibox Detector (SSD) with respect to accuracy-vs-speed trade-off as base architecture. We propose a multi-level feature fusion method for introducing contextual information in SSD, in order to improve the accuracy for small objects. In detailed fusion operation, we design two feature fusion modules, concatenation module and element-sum module, different in the way of adding contextual information. Experimental results show that these two fusion modules obtain higher mAP on PASCALVOC2007 than baseline SSD by 1.6 and 1.7 points respectively, especially with 2-3 points improvement on some smallobjects categories. The testing speed of them is 43 and 40 FPS respectively, superior to the state of the art Deconvolutional single shot detector (DSSD) by 29.4 and 26.4 FPS. Code is available at https://github.com/wnzhyee/Feature-Fused-SSD. Keywords: small object detection, feature fusion, real-time, single shot multi-box detector
Adaptive Laplace Mechanism: Differential Privacy Preservation in Deep Learning
Venue: arXiv cs.CR 2018
Year: 2018

In this paper, we focus on developing a novel mechanism to preserve differential privacy in deep neural networks, such that: (1) The privacy budget consumption is totally independent of the number of training steps; (2) It has the ability to adaptively inject noise into features based on the contribution of each to the output; and (3) It could be applied in a variety of different deep neural networks. To achieve this, we figure out a way to perturb affine transformations of neurons, and loss functions used in deep neural networks. In addition, our mechanism intentionally adds "more noise" into features which are "less relevant" to the model output, and vice-versa. Our theoretical analysis further derives the sensitivities and error bounds of our mechanism. Rigorous experiments conducted on MNIST and CIFAR-10 datasets show that our mechanism is highly effective and outperforms existing solutions.
Finite-Alphabet Precoding for Massive MU-MIMO with Low-resolution DACs
Venue: arXiv cs.IT 2018
Year: 2018

Massive multiuser multiple-input multiple-output (MU-MIMO) systems are expected to be the core technology in fifth-generation wireless systems because they significantly improve spectral efficiency. However, the requirement for a large number of radio frequency (RF) chains results in high hardware costs and power consumption, which obstruct the commercial deployment of massive MIMO systems. A potential solution is to use low-resolution digital-to-analog converters (DAC)/analog-to-digital converters for each antenna and RF chain. However, using low-resolution DACs at the transmit side directly limits the degree of freedom of output signals and thus poses a challenge to the precoding design. In this study, we develop efficient and universal algorithms for a downlink massive MU-MIMO system with finite-alphabet precodings. Our algorithms are developed based on the alternating direction method of multipliers (ADMM) framework. The original ADMM does not converge in a nonlinear discrete optimization problem. The primary cause of this problem is that the alternating (update) directions in ADMM on one side are biased, and those on the other side are unbiased. By making the two updates consistent in an unbiased manner, we develop two algorithms called iterative discrete estimation (IDE) and IDE2: IDE demonstrates excellent performance and IDE2 possesses a significantly low computational complexity. Compared with state-of-the-art techniques, the proposed precoding algorithms present significant advantages in performance and computational complexity.
Microscopy Cell Segmentation via Adversarial Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

We present a novel method for cell segmentation in microscopy images which is inspired by the Generative Adversarial Neural Network (GAN) approach. Our framework is built on a pair of two competitive artificial neural networks, with a unique architecture, termed Rib Cage, which are trained simultaneously and together define a min-max game resulting in an accurate segmentation of a given image. Our approach has two main strengths, similar to the GAN, the method does not require a formulation of a loss function for the optimization process. This allows training on a limited amount of annotated data in a weakly supervised manner. Promising segmentation results on real fluorescent microscopy data are presented. The code is freely available at: https://github.com/arbellea/DeepCellSeg.git
Enumeration on Trees under Relabelings
Venue: arXiv cs.DB 2018
Year: 2018

We study how to evaluate MSO queries with free variables on trees, within the framework of enumeration algorithms. Previous work has shown how to enumerate answers with linear-time preprocessing and delay linear in the size of each output, i.e., constant-delay for free first-order variables. We extend this result to support relabelings, a restricted kind of update operations on trees which allows us to change the node labels. Our main result shows that we can enumerate the answers of MSO queries on trees with linear-time preprocessing and delay linear in each answer, while supporting node relabelings in logarithmic time. To prove this, we reuse the circuit-based enumeration structure from our earlier work, and develop techniques to maintain its index under node relabelings. We also show how enumeration under relabelings can be applied to evaluate practical query languages, such as aggregate, group-by, and parameterized queries.
Ultimate SLAM? Combining Events, Images, and IMU for Robust Visual SLAM in HDR and High Speed Scenarios
Venue: arXiv cs.CV 2018
Year: 2018

Event cameras are bio-inspired vision sensors that output pixel-level brightness changes instead of standard intensity frames. These cameras do not suffer from motion blur and have a very high dynamic range, which enables them to provide reliable visual information during high speed motions or in scenes characterized by high dynamic range. However, event cameras output only little information when the amount of motion is limited, such as in the case of almost still motion. Conversely, standard cameras provide instant and rich information about the environment most of the time (in low-speed and good lighting scenarios), but they fail severely in case of fast motions, or difficult lighting such as high dynamic range or low light scenes. In this paper, we present the first state estimation pipeline that leverages the complementary advantages of these two sensors by fusing in a tightly-coupled manner events, standard frames, and inertial measurements. We show on the publicly available Event Camera Dataset that our hybrid pipeline leads to an accuracy improvement of 130% over event-only pipelines, and 85% over standard-frames-only visual-inertial systems, while still being computationally tractable. Furthermore, we use our pipeline to demonstrate - to the best of our knowledge - the first autonomous quadrotor flight using an event camera for state estimation, unlocking flight scenarios that were not reachable with traditional visual-inertial odometry, such as low-light environments and high-dynamic range scenes.
Uncoded Placement Optimization for Coded Delivery
Venue: arXiv cs.IT 2018
Year: 2018

We consider the classical coded caching problem as defined by Maddah-Ali and Niesen, where a server with a library of $N$ files of equal size is connected to $K$ users via a shared error-free link. Each user is equipped with a cache with capacity of $M$ files. The goal is to design a static content placement and delivery scheme such that the average load over the shared link is minimized. We first present a class of centralized coded caching schemes consisting of a general content placement strategy specified by a file partition parameter, enabling efficient and flexible content placement, and a specific content delivery strategy, enabling load reduction by exploiting common requests of different users. For the proposed class of schemes, we consider two cases for the optimization of the file partition parameter, depending on whether a large subpacketization level is allowed or not. In the case of an unrestricted subpacketization level, we formulate the coded caching optimization in order to minimize the average load under an arbitrary file popularity. A direct formulation of the problem involves $N2^K$ variables. By imposing some additional conditions, the problem is reduced to a linear program with $N(K+1)$ variables under an arbitrary file popularity and with $K+1$ variables under the uniform file popularity. We can recover Yu {\em et al.}'s optimal scheme for the uniform file popularity as an optimal solution of our problem. When a low subpacketization level is desired, we introduce a subpacketization level constraint involving the $\ell_0$ norm for each file. Again, by imposing the same additional conditions, we can simplify the problem to a difference of two convex functions (DC) problem with $N(K+1)$ variables that can be efficiently solved.
SalNet360: Saliency Maps for omni-directional images with CNN
Venue: arXiv cs.CV 2018
Year: 2018

The prediction of Visual Attention data from any kind of media is of valuable use to content creators and used to efficiently drive encoding algorithms. With the current trend in the Virtual Reality (VR) field, adapting known techniques to this new kind of media is starting to gain momentum. In this paper, we present an architectural extension to any Convolutional Neural Network (CNN) to fine-tune traditional 2D saliency prediction to Omnidirectional Images (ODIs) in an end-to-end manner. We show that each step in the proposed pipeline works towards making the generated saliency map more accurate with respect to ground truth data.
ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs
Venue: arXiv cs.DB 2018
Year: 2018

Single-source and top-$k$ SimRank queries are two important types of similarity search in graphs with numerous applications in web mining, social network analysis, spam detection, etc. A plethora of techniques have been proposed for these two types of queries, but very few can efficiently support similarity search over large dynamic graphs, due to either significant preprocessing time or large space overheads. This paper presents ProbeSim, an index-free algorithm for single-source and top-$k$ SimRank queries that provides a non-trivial theoretical guarantee in the absolute error of query results. ProbeSim estimates SimRank similarities without precomputing any indexing structures, and thus can naturally support real-time SimRank queries on dynamic graphs. Besides the theoretical guarantee, ProbeSim also offers satisfying practical efficiency and effectiveness due to several non-trivial optimizations. We conduct extensive experiments on a number of benchmark datasets, which demonstrate that our solutions significantly outperform the existing methods in terms of efficiency and effectiveness. Notably, our experiments include the first empirical study that evaluates the effectiveness of SimRank algorithms on graphs with billion edges, using the idea of pooling.
Accelerating PageRank using Partition-Centric Processing
Venue: arXiv cs.DC 2018
Year: 2018

PageRank is a fundamental link analysis algorithm that also functions as a key representative of the performance of Sparse Matrix-Vector (SpMV) multiplication. The traditional PageRank implementation generates fine granularity random memory accesses resulting in large amount of wasteful DRAM traffic and poor bandwidth utilization. In this paper, we present a novel Partition-Centric Processing Methodology (PCPM) to compute PageRank, that drastically reduces the amount of DRAM communication while achieving high sustained memory bandwidth. PCPM uses a Partition-centric abstraction coupled with the Gather-Apply-Scatter (GAS) programming model. By carefully examining how a PCPM based implementation impacts communication characteristics of the algorithm, we propose several system optimizations that improve the execution time substantially. More specifically, we develop (1) a new data layout that significantly reduces communication and random DRAM accesses, and (2) branch avoidance mechanisms to get rid of unpredictable data-dependent branches. We perform detailed analytical and experimental evaluation of our approach using 6 large graphs and demonstrate an average 2.7x speedup in execution time and 1.7x reduction in communication volume, compared to the state-of-the-art. We also show that unlike other GAS based implementations, PCPM is able to further reduce main memory traffic by taking advantage of intelligent node labeling that enhances locality. Although we use PageRank as the target application in this paper, our approach can be applied to generic SpMV computation.
Extended-Alphabet Finite-Context Models
Venue: arXiv cs.IT 2018
Year: 2018

The Normalized Relative Compression (NRC) is a recent dissimilarity measure, related to the Kolmogorov Complexity. It has been successfully used in different applications, like DNA sequences, images or even ECG (electrocardiographic) signal. It uses a compressor that compresses a target string using exclusively the information contained in a reference string. One possible approach is to use finite-context models (FCMs) to represent the strings. A finite-context model calculates the probability distribution of the next symbol, given the previous $k$ symbols. In this paper, we introduce a generalization of the FCMs, called extended-alphabet finite-context models (xaFCM), that calculates the probability of occurrence of the next $d$ symbols, given the previous $k$ symbols. We perform experiments on two different sample applications using the xaFCMs and the NRC measure: ECG biometric identification, using a publicly available database; estimation of the similarity between DNA sequences of two different, but related, species -- chromosome by chromosome. In both applications, we compare the results against those obtained by the FCMs. The results show that the xaFCMs use less memory and computational time to achieve the same or, in some cases, even more accurate results.
Urban Land Cover Classification with Missing Data Modalities Using Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Automatic urban land cover classification is a fundamental problem in remote sensing, e.g. for environmental monitoring. The problem is highly challenging, as classes generally have high inter-class and low intra-class variance. Techniques to improve urban land cover classification performance in remote sensing include fusion of data from different sensors with different data modalities. However, such techniques require all modalities to be available to the classifier in the decision-making process, i.e. at test time, as well as in training. If a data modality is missing at test time, current state-of-the-art approaches have in general no procedure available for exploiting information from these modalities. This represents a waste of potentially useful information. We propose as a remedy a convolutional neural network (CNN) architecture for urban land cover classification which is able to embed all available training modalities in a so-called hallucination network. The network will in effect replace missing data modalities in the test phase, enabling fusion capabilities even when data modalities are missing in testing. We demonstrate the method using two datasets consisting of optical and digital surface model (DSM) images. We simulate missing modalities by assuming that DSM images are missing during testing. Our method outperforms both standard CNNs trained only on optical images as well as an ensemble of two standard CNNs. We further evaluate the potential of our method to handle situations where only some DSM images are missing during testing. Overall, we show that we can clearly exploit training time information of the missing modality during testing.
NC Algorithms for Weighted Planar Perfect Matching and Related Problems
Venue: arXiv cs.DS 2018
Year: 2018

Consider a planar graph $G=(V,E)$ with polynomially bounded edge weight function $w:E\to [0, poly(n)]$. The main results of this paper are NC algorithms for the following problems: - minimum weight perfect matching in $G$, - maximum cardinality and maximum weight matching in $G$ when $G$ is bipartite, - maximum multiple-source multiple-sink flow in $G$ where $c:E\to [1, poly(n)]$ is a polynomially bounded edge capacity function, - minimum weight $f$-factor in $G$ where $f:V\to [1, poly(n)]$, - min-cost flow in $G$ where $c:E\to [1, poly(n)]$ is a polynomially bounded edge capacity function and $b:V\to [1, poly(n)]$ is a polynomially bounded vertex demand function. There have been no known NC algorithms for any of these problems previously (Before this and independent paper by Anari and Vazirani). In order to solve these problems we develop a new relatively simple but versatile framework that is combinatorial in spirit. It handles the combinatorial structure of matchings directly and needs to only know weights of appropriately defined matchings from algebraic subroutines.
Fast, Robust, and Versatile Event Detection through HMM Belief State Gradient Measures
Venue: arXiv cs.RO 2018
Year: 2018

Event detection is a critical feature in data-driven systems as it assists with the identification of nominal and anomalous behavior. Event detection is increasingly relevant in robotics as robots operate with greater autonomy in increasingly unstructured environments. In this work, we present an accurate, robust, fast, and versatile measure for skill and anomaly identification. A theoretical proof establishes the link between the derivative of the log-likelihood of the HMM filtered belief state and the latest emission probabilities. The key insight is the inverse relationship in which gradient analysis is used for skill and anomaly identification. Our measure showed better performance across all metrics than related state-of-the art works. The result is broadly applicable to domains that use HMMs for event detection.
Prioritized Norms in Formal Argumentation
Venue: arXiv cs.AI 2018
Year: 2018

To resolve conflicts among norms, various nonmonotonic formalisms can be used to perform prioritized normative reasoning. Meanwhile, formal argumentation provides a way to represent nonmonotonic logics. In this paper, we propose a representation of prioritized normative reasoning by argumentation. Using hierarchical abstract normative systems, we define three kinds of prioritized normative reasoning approaches, called Greedy, Reduction, and Optimization. Then, after formulating an argumentation theory for a hierarchical abstract normative system, we show that for a totally ordered hierarchical abstract normative system, Greedy and Reduction can be represented in argumentation by applying the weakest link and the last link principles respectively, and Optimization can be represented by introducing additional defeats capturing the idea that for each argument that contains a norm not belonging to the maximal obeyable set then this argument should be rejected.
A Simple Algorithm for Computing a Cycle Separator
Venue: arXiv cs.CG 2018
Year: 2018

We present a linear time algorithm for computing a cycle separator in a planar graph that is (arguably) simpler than previously known algorithms. Our algorithm builds on, and is somewhat similar to, previous algorithms for computing separators. The main new ingredient is a specific layered decomposition of the planar graph constructed differently from previous BFS-based layerings.
The Value of Distributed Energy Resources for Heterogeneous Residential Consumers
Venue: arXiv cs.SY 2018
Year: 2018

The presence of behind-the-meter rooftop photovoltaics and storage in the residential sector is poised to increase significantly. Here we quantify in detail the value of these technologies to consumers and service providers. We characterize the heterogeneity in household electricity cost savings under time-varying prices due to consumption behavior differences. Different pricing policies significantly alter how households fare with respect to one another. Furthermore, household savings in absolute terms are not strongly correlated with savings normalized by PV and storage system size. We characterize the financial value of improved forecasting capabilities for a household, finding that it is a relatively small fraction of a household's cost savings. Coordination services that combine the resources available at all households can reduce costs by an additional 10% to 15% of the original total cost. Surprisingly, coordination service providers will not encourage adoption beyond 35-55% within a group. We present a simple model that explains the value of coordination and its relationship to the pricing of distribution services.
Dataset for the First Evaluation on Chinese Machine Reading Comprehension
Venue: arXiv cs.CL 2018
Year: 2018

Machine Reading Comprehension (MRC) has become enormously popular recently and has attracted a lot of attention. However, existing reading comprehension datasets are mostly in English. To add diversity in reading comprehension datasets, in this paper we propose a new Chinese reading comprehension dataset for accelerating related research in the community. The proposed dataset contains two different types: cloze-style reading comprehension and user query reading comprehension, associated with large-scale training data as well as human-annotated validation and hidden test set. Along with this dataset, we also hosted the first Evaluation on Chinese Machine Reading Comprehension (CMRC-2017) and successfully attracted tens of participants, which suggest the potential impact of this dataset.