OpenRaiser/Intern-Atlas huggingface dataset:
Non-Gaussian Component Analysis using Entropy Methods
Venue: arXiv cs.LG 2018
Year: 2018

Non-Gaussian component analysis (NGCA) is a problem in multidimensional data analysis which, since its formulation in 2006, has attracted considerable attention in statistics and machine learning. In this problem, we have a random variable $X$ in $n$-dimensional Euclidean space. There is an unknown subspace $Γ$ of the $n$-dimensional Euclidean space such that the orthogonal projection of $X$ onto $Γ$ is standard multidimensional Gaussian and the orthogonal projection of $X$ onto $Γ^{\perp}$, the orthogonal complement of $Γ$, is non-Gaussian, in the sense that all its one-dimensional marginals are different from the Gaussian in a certain metric defined in terms of moments. The NGCA problem is to approximate the non-Gaussian subspace $Γ^{\perp}$ given samples of $X$. Vectors in $Γ^{\perp}$ correspond to `interesting' directions, whereas vectors in $Γ$ correspond to the directions where data is very noisy. The most interesting applications of the NGCA model is for the case when the magnitude of the noise is comparable to that of the true signal, a setting in which traditional noise reduction techniques such as PCA don't apply directly. NGCA is also related to dimension reduction and to other data analysis problems such as ICA. NGCA-like problems have been studied in statistics for a long time using techniques such as projection pursuit. We give an algorithm that takes polynomial time in the dimension $n$ and has an inverse polynomial dependence on the error parameter measuring the angle distance between the non-Gaussian subspace and the subspace output by the algorithm. Our algorithm is based on relative entropy as the contrast function and fits under the projection pursuit framework. The techniques we develop for analyzing our algorithm maybe of use for other related problems.
Are generative deep models for novelty detection truly better?
Venue: arXiv cs.LG 2018
Year: 2018

Many deep models have been recently proposed for anomaly detection. This paper presents comparison of selected generative deep models and classical anomaly detection methods on an extensive number of non--image benchmark datasets. We provide statistical comparison of the selected models, in many configurations, architectures and hyperparamaters. We arrive to conclusion that performance of the generative models is determined by the process of selection of their hyperparameters. Specifically, performance of the deep generative models deteriorates with decreasing amount of anomalous samples used in hyperparameter selection. In practical scenarios of anomaly detection, none of the deep generative models systematically outperforms the kNN.
What Your DRAM Power Models Are Not Telling You: Lessons from a Detailed Experimental Study
Venue: arXiv cs.AR 2018
Year: 2018

Main memory (DRAM) consumes as much as half of the total system power in a computer today, resulting in a growing need to develop new DRAM architectures and systems that consume less power. Researchers have long relied on DRAM power models that are based off of standardized current measurements provided by vendors, called IDD values. Unfortunately, we find that these models are highly inaccurate, and do not reflect the actual power consumed by real DRAM devices. We perform the first comprehensive experimental characterization of the power consumed by modern real-world DRAM modules. Our extensive characterization of 50 DDR3L DRAM modules from three major vendors yields four key new observations about DRAM power consumption: (1) across all IDD values that we measure, the current consumed by real DRAM modules varies significantly from the current specified by the vendors; (2) DRAM power consumption strongly depends on the data value that is read or written; (3) there is significant structural variation, where the same banks and rows across multiple DRAM modules from the same model consume more power than other banks or rows; and (4) over successive process technology generations, DRAM power consumption has not decreased by as much as vendor specifications have indicated. Based on our detailed analysis and characterization data, we develop the Variation-Aware model of Memory Power Informed by Real Experiments (VAMPIRE). We show that VAMPIRE has a mean absolute percentage error of only 6.8% compared to actual measured DRAM power. VAMPIRE enables a wide range of studies that were not possible using prior DRAM power models. As an example, we use VAMPIRE to evaluate a new power-aware data encoding mechanism, which can reduce DRAM energy consumption by an average of 12.2%. We plan to open-source both VAMPIRE and our extensive raw data collected during our experimental characterization.
Tune: A Research Platform for Distributed Model Selection and Training
Venue: arXiv cs.LG 2018
Year: 2018

Modern machine learning algorithms are increasingly computationally demanding, requiring specialized hardware and distributed computation to achieve high performance in a reasonable time frame. Many hyperparameter search algorithms have been proposed for improving the efficiency of model selection, however their adaptation to the distributed compute environment is often ad-hoc. We propose Tune, a unified framework for model selection and training that provides a narrow-waist interface between training scripts and search algorithms. We show that this interface meets the requirements for a broad range of hyperparameter search algorithms, allows straightforward scaling of search to large clusters, and simplifies algorithm implementation. We demonstrate the implementation of several state-of-the-art hyperparameter search algorithms in Tune. Tune is available at http://ray.readthedocs.io/en/latest/tune.html.
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
Venue: arXiv cs.CC 2018
Year: 2018

Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well-known problems can be cast as promise CSPs including approximate graph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, the tractability of promise CSPs can be tied to the structure of operations on the solution space called polymorphisms, though in the promise world these operations are much less constrained. Under the thesis that non-trivial polymorphisms govern tractability, promise CSPs therefore provide a fertile ground for the discovery of novel algorithms. In previous work, we classified Boolean promise CSPs when the constraint predicates are symmetric. In this work, we vastly generalize these algorithmic results. Specifically, we show that promise CSPs that admit a family of "regional-periodic" polymorphisms are in P, assuming that determining which region a point is in can be computed in polynomial time. Such polymorphisms are quite general and are obtained by gluing together several functions that are periodic in the Hamming weights in different blocks of the input. Our algorithm is based on a novel combination of linear programming and solving linear systems over rings. We also abstract a framework based on reducing a promise CSP to a CSP over an infinite domain, solving it there, and then rounding the solution to an assignment for the promise CSP instance. The rounding step is intimately tied to the family of polymorphisms and clarifies the connection between polymorphisms and algorithms in this context. As a key ingredient, we introduce the technique of finding a solution to a linear program with integer coefficients that lies in a different ring (such as $\mathbb Z[\sqrt{2}]$) to bypass ad-hoc adjustments for lying on a rounding boundary.
Learning Deployable Navigation Policies at Kilometer Scale from a Single Traversal
Venue: arXiv cs.RO 2018
Year: 2018

Model-free reinforcement learning has recently been shown to be effective at learning navigation policies from complex image input. However, these algorithms tend to require large amounts of interaction with the environment, which can be prohibitively costly to obtain on robots in the real world. We present an approach for efficiently learning goal-directed navigation policies on a mobile robot, from only a single coverage traversal of recorded data. The navigation agent learns an effective policy over a diverse action space in a large heterogeneous environment consisting of more than 2km of travel, through buildings and outdoor regions that collectively exhibit large variations in visual appearance, self-similarity, and connectivity. We compare pretrained visual encoders that enable precomputation of visual embeddings to achieve a throughput of tens of thousands of transitions per second at training time on a commodity desktop computer, allowing agents to learn from millions of trajectories of experience in a matter of hours. We propose multiple forms of computationally efficient stochastic augmentation to enable the learned policy to generalise beyond these precomputed embeddings, and demonstrate successful deployment of the learned policy on the real robot without fine tuning, despite environmental appearance differences at test time. The dataset and code required to reproduce these results and apply the technique to other datasets and robots is made publicly available at rl-navigation.github.io/deployable.
Survey on Deep Learning Techniques for Person Re-Identification Task
Venue: arXiv cs.CV 2018
Year: 2018

Intelligent video-surveillance is currently an active research field in computer vision and machine learning techniques. It provides useful tools for surveillance operators and forensic video investigators. Person re-identification (PReID) is one among these tools. It consists of recognizing whether an individual has already been observed over a camera in a network or not. This tool can also be employed in various possible applications such as off-line retrieval of all the video-sequences showing an individual of interest whose image is given a query, and online pedestrian tracking over multiple camera views. To this aim, many techniques have been proposed to increase the performance of PReID. Among the systems, many researchers utilized deep neural networks (DNNs) because of their better performance and fast execution at test time. Our objective is to provide for future researchers the work being done on PReID to date. Therefore, we summarized state-of-the-art DNN models being used for this task. A brief description of each model along with their evaluation on a set of benchmark datasets is given. Finally, a detailed comparison is provided among these models followed by some limitations that can work as guidelines for future research.
A matching-based heuristic algorithm for school bus routing problems
Venue: arXiv cs.DS 2018
Year: 2018

School bus planning problem (SBPP) has drawn much research attention due to the huge costs of school transportation. In the literature, the SBPP is usually decomposed into the routing and scheduling subproblems due to its complexity. Because of the nature of the decomposition, even if all the subproblems are solved to optimality, the final solution may not be as good as the solution from the integrated model. In this paper, we present a new approach that incorporates the scheduling information (namely the trip compatibility) into the routing stage such that the interrelationship between the subproblems is still considered even in the decomposed problems. A novel two-step heuristic adopting the trip compatibility idea is presented to solve the school bus routing problem. The first step finds an initial solution using an iterative minimum cost matching-based insertion heuristic. Then, the initial trips are improved using a Simulated Annealing and Tabu Search hybrid method. Experiments were conducted on randomly generated problems and benchmark problems in the literature. The result shows that our two-step heuristic improves existing solutions up to 25% on the benchmark problems.
Fully Distributed Event-Triggered Protocols for Linear Multi-Agent Networks
Venue: arXiv cs.SY 2018
Year: 2018

This paper considers the distributed event-triggered consensus problem for general linear multi-agent networks. Both the leaderless and leader-follower consensus problems are considered. Based on the local sampled state or local output information, distributed adaptive event-triggered protocols are designed, which can ensure that consensus of the agents is achieved and the Zeno behavior is excluded by showing that the interval between any two triggering events is lower bounded by a strictly positive value. Compared to the previous related works, our main contribution is that the proposed adaptive event-based protocols are fully distributed and scalable, which do not rely on any global information of the network graph and are independent of the network's scale. In these event-based protocols, continuous communications are not required for either control laws updating or triggering functions monitoring.
Non-local RoIs for Instance Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

We introduce the concept of Non-Local RoI (NL-RoI) Block as a generic and flexible module that can be seamlessly adapted into different Mask R-CNN heads for various tasks. Mask R-CNN treats RoIs (Regions of Interest) independently and performs the prediction based on individual object bounding boxes. However, the correlation between objects may provide useful information for detection and segmentation. The proposed NL-RoI Block enables each RoI to refer to all other RoIs' information, and results in a simple, low-cost but effective module. Our experimental results show that generalizations with NL-RoI Blocks can improve the performance of Mask R-CNN for instance segmentation on the Robust Vision Challenge benchmarks.
Backscatter-assisted Relaying in Wireless Powered Communications Network
Venue: arXiv cs.NI 2018
Year: 2018

This paper studies a novel cooperation method in a two-user wireless powered communication network (WPCN), in which one hybrid access point (HAP) broadcasts wireless energy to two distributed wireless devices (WDs), while the WDs use the harvested energy to transmit their independent information to the HAP. To tackle the user unfairness problem caused by the near-far effect in WPCN, we allow the WD with the stronger WD-to-HAP channel to use part of its harvested energy to help relay the other weaker user's information to the HAP. In particular, we exploit the use of backscatter communication during the wireless energy transfer phase such that the helping relay user can harvest energy and receive the information from the weaker user simultaneously. We derive the maximum common throughput performance by jointly optimizing the time duration and power allocations on wireless energy and information transmissions. Our simulation results demonstrate that the backscatter-assisted cooperation scheme can effectively improve the throughput fairness performance in WPCNs.
Hierarchical Reinforcement Learning Framework towards Multi-agent Navigation
Venue: arXiv cs.RO 2018
Year: 2018

In this paper, we propose a navigation algorithm oriented to multi-agent environment. This algorithm is expressed as a hierarchical framework that contains a Hidden Markov Model (HMM) and a Deep Reinforcement Learning (DRL) structure. For simplification, we term our method Hierarchical Navigation Reinforcement Network (HNRN). In high- level architecture, we train an HMM to evaluate the agent's perception to obtain a score. According to this score, adaptive control action will be chosen. While in low-level architecture, two sub-systems are introduced, one is a differential target- driven system, which aims at heading to the target; the other is a collision avoidance DRL system, which is used for avoiding dynamic obstacles. The advantage of this hierarchical structure is decoupling the target-driven and collision avoidance tasks, leading to a faster and more stable model to be trained. The experiments indicate that our algorithm has higher learning efficiency and rate of success than traditional Velocity Obstacle (VO) algorithms or hybrid DRL method.
Semi-supervised Feature Learning For Improving Writer Identification
Venue: arXiv cs.LG 2018
Year: 2018

Data augmentation is usually used by supervised learning approaches for offline writer identification, but such approaches require extra training data and potentially lead to overfitting errors. In this study, a semi-supervised feature learning pipeline was proposed to improve the performance of writer identification by training with extra unlabeled data and the original labeled data simultaneously. Specifically, we proposed a weighted label smoothing regularization (WLSR) method for data augmentation, which assigned the weighted uniform label distribution to the extra unlabeled data. The WLSR method could regularize the convolutional neural network (CNN) baseline to allow more discriminative features to be learned to represent the properties of different writing styles. The experimental results on well-known benchmark datasets (ICDAR2013 and CVL) showed that our proposed semi-supervised feature learning approach could significantly improve the baseline measurement and perform competitively with existing writer identification approaches. Our findings provide new insights into offline write identification.
A Tight Upper Bound on Bit Error Rate of Joint OFDM and Multi-Carrier Index Keying
Venue: arXiv cs.IT 2018
Year: 2018

This letter investigates performance enhancement by the concept of multi-carrier index keying in orthogonal frequency division multiplexing (OFDM) systems. For the performance evaluation, a tight closed-form approximation of the bit error rate (BER) is derived introducing the expression for the number of bit errors occurring in both the index domain and the complex domain, in the presence of both imperfect and perfect detection of active multi-carrier indices. The accuracy of the derived BER results for various cases are validated using simulations, which can provide accuracy within 1 dB at favorable channels.
Deep Learning for Semantic Segmentation on Minimal Hardware
Venue: arXiv cs.LG 2018
Year: 2018

Deep learning has revolutionised many fields, but it is still challenging to transfer its success to small mobile robots with minimal hardware. Specifically, some work has been done to this effect in the RoboCup humanoid football domain, but results that are performant and efficient and still generally applicable outside of this domain are lacking. We propose an approach conceptually different from those taken previously. It is based on semantic segmentation and does achieve these desired properties. In detail, it is being able to process full VGA images in real-time on a low-power mobile processor. It can further handle multiple image dimensions without retraining, it does not require specific domain knowledge for achieving a high frame rate and it is applicable on a minimal mobile hardware.
Caching at the Edge with Fountain Codes
Venue: arXiv cs.IT 2018
Year: 2018

We address the use of linear randon fountain codes caching schemes in a heterogeneous satellite network. We consider a system composed of multiple hubs and a geostationary Earth orbit satellite. Coded content is memorized in hubs' caches in order to serve immediately the user requests and reduce the usage of the satellite backhaul link. We derive the analytical expression of the average backhaul rate, as well as a tight upper bound to it with a simple expression. Furthermore, we derive the optimal caching strategy which minimizes the average backhaul rate and compare the performance of the linear random fountain code scheme to that of a scheme using maximum distance separable codes. Our simulation results indicate that the performance obtained using fountain codes is similar to that of maximum distance separable codes.
Cross Pixel Optical Flow Similarity for Self-Supervised Learning
Venue: arXiv cs.CV 2018
Year: 2018

We propose a novel method for learning convolutional neural image representations without manual supervision. We use motion cues in the form of optical flow, to supervise representations of static images. The obvious approach of training a network to predict flow from a single image can be needlessly difficult due to intrinsic ambiguities in this prediction task. We instead propose a much simpler learning goal: embed pixels such that the similarity between their embeddings matches that between their optical flow vectors. At test time, the learned deep network can be used without access to video or flow information and transferred to tasks such as image classification, detection, and segmentation. Our method, which significantly simplifies previous attempts at using motion for self-supervision, achieves state-of-the-art results in self-supervision using motion cues, competitive results for self-supervision in general, and is overall state of the art in self-supervised pretraining for semantic image segmentation, as demonstrated on standard benchmarks.
LATE Ain'T Earley: A Faster Parallel Earley Parser
Venue: arXiv cs.CL 2018
Year: 2018

We present the LATE algorithm, an asynchronous variant of the Earley algorithm for parsing context-free grammars. The Earley algorithm is naturally task-based, but is difficult to parallelize because of dependencies between the tasks. We present the LATE algorithm, which uses additional data structures to maintain information about the state of the parse so that work items may be processed in any order. This property allows the LATE algorithm to be sped up using task parallelism. We show that the LATE algorithm can achieve a 120x speedup over the Earley algorithm on a natural language task.
Time Series Deinterleaving of DNS Traffic
Venue: arXiv cs.LG 2018
Year: 2018

Stream deinterleaving is an important problem with various applications in the cybersecurity domain. In this paper, we consider the specific problem of deinterleaving DNS data streams using machine-learning techniques, with the objective of automating the extraction of malware domain sequences. We first develop a generative model for user request generation and DNS stream interleaving. Based on these we evaluate various inference strategies for deinterleaving including augmented HMMs and LSTMs on synthetic datasets. Our results demonstrate that state-of-the-art LSTMs outperform more traditional augmented HMMs in this application domain.
Disease Classification within Dermascopic Images Using features extracted by ResNet50 and classification through Deep Forest
Venue: arXiv cs.CV 2018
Year: 2018

In this report we propose a classification technique for skin lesion images as a part of our submission for ISIC 2018 Challenge in Skin Lesion Analysis Towards Melanoma Detection. Our data was extracted from the ISIC 2018: Skin Lesion Analysis Towards Melanoma Detection grand challenge datasets. The features are extracted through a Convolutional Neural Network, in our case ResNet50 and then using these features we train a DeepForest, having cascading layers, to classify our skin lesion images. We know that Convolutional Neural Networks are a state-of-the-art technique in representation learning for images, with the convolutional filters learning to detect features from images through backpropagation. These features are then usually fed to a classifier like a softmax layer or other such classifiers for classification tasks. In our case we do not use the traditional backpropagation method and train a softmax layer for classification. Instead, we use Deep Forest, a novel decision tree ensemble approach with performance highly competitive to deep neural networks in a broad range of tasks. Thus we use a ResNet50 to extract the features from skin lesion images and then use the Deep Forest to classify these images. This method has been used because Deep Forest has been found to be hugely efficient in areas where there are only small-scale training data available. Also as the Deep Forest network decides its complexity by itself, it also caters to the problem of dataset imbalance we faced in this problem.