OpenRaiser/Intern-Atlas huggingface dataset:
Mixed Linear Layouts of Planar Graphs
Venue: arXiv cs.CG 2018
Year: 2018

A $k$-stack (respectively, $k$-queue) layout of a graph consists of a total order of the vertices, and a partition of the edges into $k$ sets of non-crossing (non-nested) edges with respect to the vertex ordering. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed $1$-stack $1$-queue layout in which every edge is assigned to a stack or to a queue that use a common vertex ordering. We disprove this conjecture by providing a planar graph that does not have such a mixed layout. In addition, we study mixed layouts of graph subdivisions, and show that every planar graph has a mixed subdivision with one division vertex per edge.
2D Map Alignment With Region Decomposition
Venue: arXiv cs.RO 2018
Year: 2018

In many applications of autonomous mobile robots the following problem is encountered. Two maps of the same environment are available, one a prior map and the other a sensor map built by the robot. To benefit from all available information in both maps, the robot must find the correct alignment between the two maps. There exist many approaches to address this challenge, however, most of the previous methods rely on assumptions such as similar modalities of the maps, same scale, or existence of an initial guess for the alignment. In this work we propose a decomposition-based method for 2D spatial map alignment which does not rely on those assumptions. Our proposed method is validated and compared with other approaches, including generic data association approaches and map alignment algorithms. Real world examples of four different environments with thirty six sensor maps and four layout maps are used for this analysis. The maps, along with an implementation of the method, are made publicly available online.
Iteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems
Venue: arXiv cs.NA 2018
Year: 2018

In this paper, we consider solving a class of nonconvex and nonsmooth problems frequently appearing in signal processing and machine learning research. The traditional alternating direction method of multipliers encounters troubles in both mathematics and computations in solving the nonconvex and nonsmooth subproblem. In view of this, we propose a reweighted alternating direction method of multipliers. In this algorithm, all subproblems are convex and easy to solve. We also provide several guarantees for the convergence and prove that the algorithm globally converges to a critical point of an auxiliary function with the help of the Kurdyka-Łojasiewicz property. Several numerical results are presented to demonstrate the efficiency of the proposed algorithm.
A short note on the joint entropy of n/2-wise independence
Venue: arXiv cs.DM 2018
Year: 2018

In this note, we prove a tight lower bound on the joint entropy of $n$ unbiased Bernoulli random variables which are $n/2$-wise independent. For general $k$-wise independence, we give new lower bounds by adapting Navon and Samorodnitsky's Fourier proof of the `LP bound' on error correcting codes. This counts as partial progress on a problem asked by Gavinsky and Pudlák.
Upper Bound on Normalized Maximum Likelihood Codes for Gaussian Mixture Models
Venue: arXiv cs.IT 2018
Year: 2018

This paper shows that the normalized maximum likelihood~(NML) code-length calculated in [1] is an upper bound on the NML code-length strictly calculated for the Gaussian Mixture Model. When we use this upper bound on the NML code-length, we must change the scale of the data sequence to satisfy the restricted domain. However, we also show that the algorithm for model selection is essentially universal, regardless of the scale conversion of the data in Gaussian Mixture Models, and that, consequently, the experimental results in [1] can be used as they are. In addition to this, we correct the NML code-length in [1] for generalized logistic distributions.
WESPE: Weakly Supervised Photo Enhancer for Digital Cameras
Venue: arXiv cs.CV 2018
Year: 2018

Low-end and compact mobile cameras demonstrate limited photo quality mainly due to space, hardware and budget constraints. In this work, we propose a deep learning solution that translates photos taken by cameras with limited capabilities into DSLR-quality photos automatically. We tackle this problem by introducing a weakly supervised photo enhancer (WESPE) - a novel image-to-image Generative Adversarial Network-based architecture. The proposed model is trained by under weak supervision: unlike previous works, there is no need for strong supervision in the form of a large annotated dataset of aligned original/enhanced photo pairs. The sole requirement is two distinct datasets: one from the source camera, and one composed of arbitrary high-quality images that can be generally crawled from the Internet - the visual content they exhibit may be unrelated. Hence, our solution is repeatable for any camera: collecting the data and training can be achieved in a couple of hours. In this work, we emphasize on extensive evaluation of obtained results. Besides standard objective metrics and subjective user study, we train a virtual rater in the form of a separate CNN that mimics human raters on Flickr data and use this network to get reference scores for both original and enhanced photos. Our experiments on the DPED, KITTI and Cityscapes datasets as well as pictures from several generations of smartphones demonstrate that WESPE produces comparable or improved qualitative results with state-of-the-art strongly supervised methods.
FraudDroid: Automated Ad Fraud Detection for Android Apps
Venue: arXiv cs.CR 2018
Year: 2018

Although mobile ad frauds have been widespread, state-of-the-art approaches in the literature have mainly focused on detecting the so-called static placement frauds, where only a single UI state is involved and can be identified based on static information such as the size or location of ad views. Other types of fraud exist that involve multiple UI states and are performed dynamically while users interact with the app. Such dynamic interaction frauds, although now widely spread in apps, have not yet been explored nor addressed in the literature. In this work, we investigate a wide range of mobile ad frauds to provide a comprehensive taxonomy to the research community. We then propose, FraudDroid, a novel hybrid approach to detect ad frauds in mobile Android apps. FraudDroid analyses apps dynamically to build UI state transition graphs and collects their associated runtime network traffics, which are then leveraged to check against a set of heuristic-based rules for identifying ad fraudulent behaviours. We show empirically that FraudDroid detects ad frauds with a high precision (93%) and recall (92%). Experimental results further show that FraudDroid is capable of detecting ad frauds across the spectrum of fraud types. By analysing 12,000 ad-supported Android apps, FraudDroid identified 335 cases of fraud associated with 20 ad networks that are further confirmed to be true positive results and are shared with our fellow researchers to promote advanced ad fraud detection
Towards social pattern characterization in egocentric photo-streams
Venue: arXiv cs.CV 2018
Year: 2018

Following the increasingly popular trend of social interaction analysis in egocentric vision, this manuscript presents a comprehensive study for automatic social pattern characterization of a wearable photo-camera user, by relying on the visual analysis of egocentric photo-streams. The proposed framework consists of three major steps. The first step is to detect social interactions of the user where the impact of several social signals on the task is explored. The detected social events are inspected in the second step for categorization into different social meetings. These two steps act at event-level where each potential social event is modeled as a multi-dimensional time-series, whose dimensions correspond to a set of relevant features for each task, and LSTM is employed to classify the time-series. The last step of the framework is to characterize social patterns, which is essentially to infer the diversity and frequency of the social relations of the user through discovery of recurrences of the same people across the whole set of social events of the user. Experimental evaluation over a dataset acquired by 9 users demonstrates promising results on the task of social pattern characterization from egocentric photo-streams.
A deep generative model for gene expression profiles from single-cell RNA sequencing
Venue: arXiv cs.LG 2018
Year: 2018

We propose a probabilistic model for interpreting gene expression levels that are observed through single-cell RNA sequencing. In the model, each cell has a low-dimensional latent representation. Additional latent variables account for technical effects that may erroneously set some observations of gene expression levels to zero. Conditional distributions are specified by neural networks, giving the proposed model enough flexibility to fit the data well. We use variational inference and stochastic optimization to approximate the posterior distribution. The inference procedure scales to over one million cells, whereas competing algorithms do not. Even for smaller datasets, for several tasks, the proposed procedure outperforms state-of-the-art methods like ZIFA and ZINB-WaVE. We also extend our framework to account for batch effects and other confounding factors, and propose a Bayesian hypothesis test for differential expression that outperforms DESeq2.
Local Neighborhood Intensity Pattern: A new texture feature descriptor for image retrieval
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, a new texture descriptor based on the local neighborhood intensity difference is proposed for content based image retrieval (CBIR). For computation of texture features like Local Binary Pattern (LBP), the center pixel in a 3*3 window of an image is compared with all the remaining neighbors, one pixel at a time to generate a binary bit pattern. It ignores the effect of the adjacent neighbors of a particular pixel for its binary encoding and also for texture description. The proposed method is based on the concept that neighbors of a particular pixel hold a significant amount of texture information that can be considered for efficient texture representation for CBIR. Taking this into account, we develop a new texture descriptor, named as Local Neighborhood Intensity Pattern (LNIP) which considers the relative intensity difference between a particular pixel and the center pixel by considering its adjacent neighbors and generate a sign and a magnitude pattern. Since sign and magnitude patterns hold complementary information to each other, these two patterns are concatenated into a single feature descriptor to generate a more concrete and useful feature descriptor. The proposed descriptor has been tested for image retrieval on four databases, including three texture image databases - Brodatz texture image database, MIT VisTex database and Salzburg texture database and one face database AT&T face database. The precision and recall values observed on these databases are compared with some state-of-art local patterns. The proposed method showed a significant improvement over many other existing methods.
DeepFense: Online Accelerated Defense Against Adversarial Deep Learning
Venue: arXiv cs.CR 2018
Year: 2018

Recent advances in adversarial Deep Learning (DL) have opened up a largely unexplored surface for malicious attacks jeopardizing the integrity of autonomous DL systems. With the wide-spread usage of DL in critical and time-sensitive applications, including unmanned vehicles, drones, and video surveillance systems, online detection of malicious inputs is of utmost importance. We propose DeepFense, the first end-to-end automated framework that simultaneously enables efficient and safe execution of DL models. DeepFense formalizes the goal of thwarting adversarial attacks as an optimization problem that minimizes the rarely observed regions in the latent feature space spanned by a DL network. To solve the aforementioned minimization problem, a set of complementary but disjoint modular redundancies are trained to validate the legitimacy of the input samples in parallel with the victim DL model. DeepFense leverages hardware/software/algorithm co-design and customized acceleration to achieve just-in-time performance in resource-constrained settings. The proposed countermeasure is unsupervised, meaning that no adversarial sample is leveraged to train modular redundancies. We further provide an accompanying API to reduce the non-recurring engineering cost and ensure automated adaptation to various platforms. Extensive evaluations on FPGAs and GPUs demonstrate up to two orders of magnitude performance improvement while enabling online adversarial sample detection.
Gaussian Quadrature for Kernel Features
Venue: arXiv cs.LG 2018
Year: 2018

Kernel methods have recently attracted resurgent interest, showing performance competitive with deep neural networks in tasks such as speech recognition. The random Fourier features map is a technique commonly used to scale up kernel machines, but employing the randomized feature map means that $O(ε^{-2})$ samples are required to achieve an approximation error of at most $ε$. We investigate some alternative schemes for constructing feature maps that are deterministic, rather than random, by approximating the kernel in the frequency domain using Gaussian quadrature. We show that deterministic feature maps can be constructed, for any $γ> 0$, to achieve error $ε$ with $O(e^{e^γ} + ε^{-1/γ})$ samples as $ε$ goes to 0. Our method works particularly well with sparse ANOVA kernels, which are inspired by the convolutional layer of CNNs. We validate our methods on datasets in different domains, such as MNIST and TIMIT, showing that deterministic features are faster to generate and achieve accuracy comparable to the state-of-the-art kernel methods based on random Fourier features.
Less Is More: A Comprehensive Framework for the Number of Components of Ensemble Classifiers
Venue: arXiv cs.LG 2018
Year: 2018

The number of component classifiers chosen for an ensemble greatly impacts the prediction ability. In this paper, we use a geometric framework for a priori determining the ensemble size, which is applicable to most of existing batch and online ensemble classifiers. There are only a limited number of studies on the ensemble size examining Majority Voting (MV) and Weighted Majority Voting (WMV). Almost all of them are designed for batch-mode, hardly addressing online environments. Big data dimensions and resource limitations, in terms of time and memory, make determination of ensemble size crucial, especially for online environments. For the MV aggregation rule, our framework proves that the more strong components we add to the ensemble, the more accurate predictions we can achieve. For the WMV aggregation rule, our framework proves the existence of an ideal number of components, which is equal to the number of class labels, with the premise that components are completely independent of each other and strong enough. While giving the exact definition for a strong and independent classifier in the context of an ensemble is a challenging task, our proposed geometric framework provides a theoretical explanation of diversity and its impact on the accuracy of predictions. We conduct a series of experimental evaluations to show the practical value of our theorems and existing challenges.
An Efficient Approximation Algorithm for the Steiner Tree Problem
Venue: arXiv cs.DS 2018
Year: 2018

The Steiner tree problem is one of the classic and most fundamental $\mathcal{NP}$-hard problems: given an arbitrary weighted graph, seek a minimum-cost tree spanning a given subset of the vertices (terminals). Byrka \emph{et al}. proposed a $1.3863+ε$-approximation algorithm in which the linear program is solved at every iteration after contracting a component. Goemans \emph{et al}. shown that it is possible to achieve the same approximation guarantee while only solving hypergraphic LP relaxation once. However, optimizing hypergraphic LP relaxation exactly is strongly NP-hard. This article presents an efficient two-phase heuristic in greedy strategy that achieves an approximation ratio of $1.4295$.
Time Integrating Articulated Body Dynamics Using Position-Based Collocation Method
Venue: arXiv cs.RO 2018
Year: 2018

We present a new time integrator for articulated body dynamics. We formulate the governing equations of the dynamics using only the position variables and recast the position-based articulated dynamics as an optimization problem. Our reformulation allows us to integrate the dynamics in a fully implicit manner without computing high-order derivatives. Therefore, under arbitrarily large timestep sizes, the stability of our time integration scheme is guaranteed using an off-the-shelf numerical optimizer. In addition to stability, we show that, similar to the Runge-Kutta method, the accuracy of our time integrator can also be increased arbitrarily by using a high-order collocation method. We provide efficient algorithms to perform time integration using our position-based formulation. We show that each iteration of optimization has a complexity of O(N) using Quasi-Newton method or O(N^2) using Newton's method, where N is the number of links. Finally, our method is highly parallelizable and can be accelerated using a Graphics Processing Unit (GPU). We highlight the efficiency and stability of our method on different benchmarks and compare the performance with prior articulated body dynamics simulation methods based on the Newton-Euler's equation. Our method is stable under a timestep size as large as 0.1s. Using a larger timestep size and less timesteps, our method achieves up to 4 times speedup on a single-core CPU. With GPU acceleration, we observe an additional 3-6 times speedup over a 4-core CPU.
Rational Solutions of High-Order Algebraic Ordinary Differential Equations
Venue: arXiv cs.SC 2018
Year: 2018

We consider algebraic ordinary differential equations (AODEs) and study their polynomial and rational solutions. A sufficient condition for an AODE to have a degree bound for its polynomial solutions is presented. An AODE satisfying this condition is called \emph{noncritical}. We prove that usual low order classes of AODEs are noncritical. For rational solutions, we determine a class of AODEs, which are called \emph{maximally comparable}, such that the poles of their rational solutions are recognizable from their coefficients. This generalizes a fact from linear AODEs, that the poles of their rational solutions are the zeros of the corresponding highest coefficient. An algorithm for determining all rational solutions, if there is any, of certain maximally comparable AODEs, which covers $78.54\%$ AODEs from a standard differential equations collection by Kamke, is presented.
A Tutorial on Deep Learning for Music Information Retrieval
Venue: arXiv cs.CV 2018
Year: 2018

Following their success in Computer Vision and other areas, deep learning techniques have recently become widely adopted in Music Information Retrieval (MIR) research. However, the majority of works aim to adopt and assess methods that have been shown to be effective in other domains, while there is still a great need for more original research focusing on music primarily and utilising musical knowledge and insight. The goal of this paper is to boost the interest of beginners by providing a comprehensive tutorial and reducing the barriers to entry into deep learning for MIR. We lay out the basic principles and review prominent works in this hard to navigate the field. We then outline the network structures that have been successful in MIR problems and facilitate the selection of building blocks for the problems at hand. Finally, guidelines for new tasks and some advanced topics in deep learning are discussed to stimulate new research in this fascinating field.
A Learning and Masking Approach to Secure Learning
Venue: arXiv cs.CR 2018
Year: 2018

Deep Neural Networks (DNNs) have been shown to be vulnerable against adversarial examples, which are data points cleverly constructed to fool the classifier. Such attacks can be devastating in practice, especially as DNNs are being applied to ever increasing critical tasks like image recognition in autonomous driving. In this paper, we introduce a new perspective on the problem. We do so by first defining robustness of a classifier to adversarial exploitation. Next, we show that the problem of adversarial example generation can be posed as learning problem. We also categorize attacks in literature into high and low perturbation attacks; well-known attacks like fast-gradient sign method (FGSM) and our attack produce higher perturbation adversarial examples while the more potent but computationally inefficient Carlini-Wagner (CW) attack is low perturbation. Next, we show that the dual approach of the attack learning problem can be used as a defensive technique that is effective against high perturbation attacks. Finally, we show that a classifier masking method achieved by adding noise to the a neural network's logit output protects against low distortion attacks such as the CW attack. We also show that both our learning and masking defense can work simultaneously to protect against multiple attacks. We demonstrate the efficacy of our techniques by experimenting with the MNIST and CIFAR-10 datasets.
Normalized Direction-preserving Adam
Venue: arXiv cs.LG 2018
Year: 2018

Adaptive optimization algorithms, such as Adam and RMSprop, have shown better optimization performance than stochastic gradient descent (SGD) in some scenarios. However, recent studies show that they often lead to worse generalization performance than SGD, especially for training deep neural networks (DNNs). In this work, we identify the reasons that Adam generalizes worse than SGD, and develop a variant of Adam to eliminate the generalization gap. The proposed method, normalized direction-preserving Adam (ND-Adam), enables more precise control of the direction and step size for updating weight vectors, leading to significantly improved generalization performance. Following a similar rationale, we further improve the generalization performance in classification tasks by regularizing the softmax logits. By bridging the gap between SGD and Adam, we also hope to shed light on why certain optimization algorithms generalize better than others.
Levelable Sets and the Algebraic Structure of Parameterizations
Venue: arXiv cs.LO 2018
Year: 2018

Asking which sets are fixed-parameter tractable for a given parameterization constitutes much of the current research in parameterized complexity theory. This approach faces some of the core difficulties in complexity theory. By focussing instead on the parameterizations that make a given set fixed-parameter tractable, we circumvent these difficulties. We isolate parameterizations as independent measures of complexity and study their underlying algebraic structure. Thus we are able to compare parameterizations, which establishes a hierarchy of complexity that is much stronger than that present in typical parameterized algorithms races. Among other results, we find that no practically fixed-parameter tractable sets have optimal parameterizations.