OpenRaiser/Intern-Atlas huggingface dataset:
Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of recovering a complete (i.e., square and invertible) matrix $\mathbf A_0$, from $\mathbf Y \in \mathbb{R}^{n \times p}$ with $\mathbf Y = \mathbf A_0 \mathbf X_0$, provided $\mathbf X_0$ is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers $\mathbf A_0$ when $\mathbf X_0$ has $O(n)$ nonzeros per column, under suitable probability model for $\mathbf X_0$. In contrast, prior results based on efficient algorithms either only guarantee recovery when $\mathbf X_0$ has $O(\sqrt{n})$ zeros per column, or require multiple rounds of SDP relaxation to work when $\mathbf X_0$ has $O(n^{1-δ})$ nonzeros per column (for any constant $δ\in (0, 1)$). } Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint. In this paper, we provide a geometric characterization of the objective landscape. In particular, we show that the problem is highly structured: with high probability, (1) there are no "spurious" local minimizers; and (2) around all saddle points the objective has a negative directional curvature. This distinctive structure makes the problem amenable to efficient optimization algorithms. In a companion paper (arXiv:1511.04777), we design a second-order trust-region algorithm over the sphere that provably converges to a local minimizer from arbitrary initializations, despite the presence of saddle points.
Document Context Language Models
Venue: arXiv cs.CL 2016
Year: 2016

Text documents are structured on multiple levels of detail: individual words are related by syntax, but larger units of text are related by discourse structure. Existing language models generally fail to account for discourse structure, but it is crucial if we are to have language models that reward coherence and generate coherent texts. We present and empirically evaluate a set of multi-level recurrent neural network language models, called Document-Context Language Models (DCLM), which incorporate contextual information both within and beyond the sentence. In comparison with word-level recurrent neural network language models, the DCLM models obtain slightly better predictive likelihoods, and considerably better assessments of document coherence.
Adaptive Affinity Matrix for Unsupervised Metric Learning
Venue: arXiv cs.CV 2016
Year: 2016

Spectral clustering is one of the most popular clustering approaches with the capability to handle some challenging clustering problems. Most spectral clustering methods provide a nonlinear map from the data manifold to a subspace. Only a little work focuses on the explicit linear map which can be viewed as the unsupervised distance metric learning. In practice, the selection of the affinity matrix exhibits a tremendous impact on the unsupervised learning. While much success of affinity learning has been achieved in recent years, some issues such as noise reduction remain to be addressed. In this paper, we propose a novel method, dubbed Adaptive Affinity Matrix (AdaAM), to learn an adaptive affinity matrix and derive a distance metric from the affinity. We assume the affinity matrix to be positive semidefinite with ability to quantify the pairwise dissimilarity. Our method is based on posing the optimization of objective function as a spectral decomposition problem. We yield the affinity from both the original data distribution and the widely-used heat kernel. The provided matrix can be regarded as the optimal representation of pairwise relationship on the manifold. Extensive experiments on a number of real-world data sets show the effectiveness and efficiency of AdaAM.
Kilombo: a Kilobot simulator to enable effective research in swarm robotics
Venue: arXiv cs.RO 2016
Year: 2016

The Kilobot is a widely used platform for investigation of swarm robotics. Physical Kilobots are slow moving and require frequent recalibration and charging, which significantly slows down the development cycle. Simulators can speed up the process of testing, exploring and hypothesis generation, but usually require time consuming and error-prone translation of code between simulator and robot. Moreover, code of different nature often obfuscates direct comparison, as well as determination of the cause of deviation, between simulator and actual robot swarm behaviour. To tackle these issues we have developed a C-based simulator that allows those working with Kilobots to use the same programme code in both the simulator and the physical robots. Use of our simulator, coined Kilombo, significantly simplifies and speeds up development, given that a simulation of 1000 robots can be run at a speed 100 times faster than real time on a desktop computer, making high-throughput pre-screening possible of potential algorithms that could lead to desired emergent behaviour. We argue that this strategy, here specifically developed for Kilobots, is of general importance for effective robot swarm research. The source code is freely available under the MIT license.
Similarity-based Text Recognition by Deeply Supervised Siamese Network
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a new text recognition model based on measuring the visual similarity of text and predicting the content of unlabeled texts. First a Siamese convolutional network is trained with deep supervision on a labeled training dataset. This network projects texts into a similarity manifold. The Deeply Supervised Siamese network learns visual similarity of texts. Then a K-nearest neighbor classifier is used to predict unlabeled text based on similarity distance to labeled texts. The performance of the model is evaluated on three datasets of machine-print and hand-written text combined. We demonstrate that the model reduces the cost of human estimation by $50\%-85\%$. The error of the system is less than $0.5\%$. The proposed model outperform conventional Siamese network by finding visually-similar barely-readable and readable text, e.g. machine-printed, handwritten, due to deep supervision. The results also demonstrate that the predicted labels are sometimes better than human labels e.g. spelling correction.
Dynamic Sum Product Networks for Tractable Inference on Sequence Data (Extended Version)
Venue: arXiv cs.LG 2016
Year: 2016

Sum-Product Networks (SPN) have recently emerged as a new class of tractable probabilistic graphical models. Unlike Bayesian networks and Markov networks where inference may be exponential in the size of the network, inference in SPNs is in time linear in the size of the network. Since SPNs represent distributions over a fixed set of variables only, we propose dynamic sum product networks (DSPNs) as a generalization of SPNs for sequence data of varying length. A DSPN consists of a template network that is repeated as many times as needed to model data sequences of any length. We present a local search technique to learn the structure of the template network. In contrast to dynamic Bayesian networks for which inference is generally exponential in the number of variables per time slice, DSPNs inherit the linear inference complexity of SPNs. We demonstrate the advantages of DSPNs over DBNs and other models on several datasets of sequence data.
Transductive Zero-Shot Action Recognition by Word-Vector Embedding
Venue: arXiv cs.CV 2016
Year: 2016

The number of categories for action recognition is growing rapidly and it has become increasingly hard to label sufficient training data for learning conventional models for all categories. Instead of collecting ever more data and labelling them exhaustively for all categories, an attractive alternative approach is zero-shot learning" (ZSL). To that end, in this study we construct a mapping between visual features and a semantic descriptor of each action category, allowing new categories to be recognised in the absence of any visual training data. Existing ZSL studies focus primarily on still images, and attribute-based semantic representations. In this work, we explore word-vectors as the shared semantic space to embed videos and category labels for ZSL action recognition. This is a more challenging problem than existing ZSL of still images and/or attributes, because the mapping between video spacetime features of actions and the semantic space is more complex and harder to learn for the purpose of generalising over any cross-category domain shift. To solve this generalisation problem in ZSL action recognition, we investigate a series of synergistic strategies to improve upon the standard ZSL pipeline. Most of these strategies are transductive in nature which means access to testing data in the training phase.
Jointly Learning Non-negative Projection and Dictionary with Discriminative Graph Constraints for Classification
Venue: arXiv cs.CV 2016
Year: 2016

Sparse coding with dictionary learning (DL) has shown excellent classification performance. Despite the considerable number of existing works, how to obtain features on top of which dictionaries can be better learned remains an open and interesting question. Many current prevailing DL methods directly adopt well-performing crafted features. While such strategy may empirically work well, it ignores certain intrinsic relationship between dictionaries and features. We propose a framework where features and dictionaries are jointly learned and optimized. The framework, named joint non-negative projection and dictionary learning (JNPDL), enables interaction between the input features and the dictionaries. The non-negative projection leads to discriminative parts-based object features while DL seeks a more suitable representation. Discriminative graph constraints are further imposed to simultaneously maximize intra-class compactness and inter-class separability. Experiments on both image and image set classification show the excellent performance of JNPDL by outperforming several state-of-the-art approaches.
Coding in the Finite-Blocklength Regime: Bounds based on Laplace Integrals and their Asymptotic Approximations
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we provide new compact integral expressions and associated simple asymptotic approximations for converse and achievability bounds in the finite blocklength regime. The chosen converse and random coding union bounds were taken from the recent work of Polyanskyi-Poor-Verdu, and are investigated under parallel AWGN channels, the AWGN channels, the BI-AWGN channel, and the BSC. The technique we use, which is a generalization of some recent results available from the literature, is to map the probabilities of interest into a Laplace integral, and then solve (or approximate) the integral by use of a steepest descent technique. The proposed results are particularly useful for short packet lengths, where the normal approximation may provide unreliable results.
Robust Elastic Net Regression
Venue: arXiv cs.LG 2016
Year: 2016

We propose a robust elastic net (REN) model for high-dimensional sparse regression and give its performance guarantees (both the statistical error bound and the optimization bound). A simple idea of trimming the inner product is applied to the elastic net model. Specifically, we robustify the covariance matrix by trimming the inner product based on the intuition that the trimmed inner product can not be significant affected by a bounded number of arbitrarily corrupted points (outliers). The REN model can also derive two interesting special cases: robust Lasso and robust soft thresholding. Comprehensive experimental results show that the robustness of the proposed model consistently outperforms the original elastic net and matches the performance guarantees nicely.
A Simple DFT-aided Spatial Basis Expansion Model and Channel Estimation Strategy for TDD/FDD Massive MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes a new transmission strategy for the multiuser massive multiple-input multiple-output (MIMO) systems, including uplink/downlink channel estimation and user scheduling for data transmission. A discrete Fourier transform (DFT) aided spatial basis expansion model (SBEM) is first introduced to represent the uplink/downlink channels with much few parameter dimensions by exploiting angle reciprocity and the physical characteristics of the uniform linear array (ULA). With SBEM, both uplink and downlink channel estimation of multiuser can be carried out with very few amount of training resources, which significantly reduces the training overhead and feedback cost. Meanwhile, the pilot contamination problem in the uplink raining is immediately relieved by exploiting the spatial information of users. To enhance the spectral efficiency and to fully utilize the spatial resources, we also design a greedy user scheduling scheme during the data transmission period. Compared to existing low-rank models, the newly proposed SBEM offers an alternative for channel acquisition without need of channel statistics for both TDD and FDD systems based on the angle reciprocity. Moreover, the proposed method can be efficiently deployed by the fast Fourier transform (FFT). Various numerical results are provided to corroborate the proposed studies.
A Neural Transducer
Venue: arXiv cs.LG 2016
Year: 2016

Sequence-to-sequence models have achieved impressive results on various tasks. However, they are unsuitable for tasks that require incremental predictions to be made as more data arrives or tasks that have long input sequences and output sequences. This is because they generate an output sequence conditioned on an entire input sequence. In this paper, we present a Neural Transducer that can make incremental predictions as more input arrives, without redoing the entire computation. Unlike sequence-to-sequence models, the Neural Transducer computes the next-step distribution conditioned on the partially observed input sequence and the partially generated sequence. At each time step, the transducer can decide to emit zero to many output symbols. The data can be processed using an encoder and presented as input to the transducer. The discrete decision to emit a symbol at every time step makes it difficult to learn with conventional backpropagation. It is however possible to train the transducer by using a dynamic programming algorithm to generate target discrete decisions. Our experiments show that the Neural Transducer works well in settings where it is required to produce output predictions as data come in. We also find that the Neural Transducer performs well for long sequences even when attention mechanisms are not used.
Context Sensitive Article Ranking with Citation Context Analysis
Venue: arXiv cs.DL 2016
Year: 2016

It is hard to detect important articles in a specific context. Information retrieval techniques based on full text search can be inaccurate to identify main topics and they are not able to provide an indication about the importance of the article. Generating a citation network is a good way to find most popular articles but this approach is not context aware. The text around a citation mark is generally a good summary of the referred article. So citation context analysis presents an opportunity to use the wisdom of crowd for detecting important articles in a context sensitive way. In this work, we analyze citation contexts to rank articles properly for a given topic. The model proposed uses citation contexts in order to create a directed and weighted citation network based on the target topic. We create a directed and weighted edge between two articles if citation context contains terms related with the target topic. Then we apply common ranking algorithms in order to find important articles in this newly created network. We showed that this method successfully detects a good subset of most prominent articles in a given topic. The biggest contribution of this approach is that we are able to identify important articles for a given search term even though these articles do not contain this search term. This technique can be used in other linked documents including web pages, legal documents, and patents.
Reduced-Precision Strategies for Bounded Memory in Deep Neural Nets
Venue: arXiv cs.LG 2016
Year: 2016

This work investigates how using reduced precision data in Convolutional Neural Networks (CNNs) affects network accuracy during classification. More specifically, this study considers networks where each layer may use different precision data. Our key result is the observation that the tolerance of CNNs to reduced precision data not only varies across networks, a well established observation, but also within networks. Tuning precision per layer is appealing as it could enable energy and performance improvements. In this paper we study how error tolerance across layers varies and propose a method for finding a low precision configuration for a network while maintaining high accuracy. A diverse set of CNNs is analyzed showing that compared to a conventional implementation using a 32-bit floating-point representation for all layers, and with less than 1% loss in relative accuracy, the data footprint required by these networks can be reduced by an average of 74% and up to 92%.
The Use of Machine Learning Algorithms in Recommender Systems: A Systematic Review
Venue: arXiv cs.SE 2016
Year: 2016

Recommender systems use algorithms to provide users with product or service recommendations. Recently, these systems have been using machine learning algorithms from the field of artificial intelligence. However, choosing a suitable machine learning algorithm for a recommender system is difficult because of the number of algorithms described in the literature. Researchers and practitioners developing recommender systems are left with little information about the current approaches in algorithm usage. Moreover, the development of a recommender system using a machine learning algorithm often has problems and open questions that must be evaluated, so software engineers know where to focus research efforts. This paper presents a systematic review of the literature that analyzes the use of machine learning algorithms in recommender systems and identifies research opportunities for software engineering research. The study concludes that Bayesian and decision tree algorithms are widely used in recommender systems because of their relative simplicity, and that requirement and design phases of recommender system development appear to offer opportunities for further research.
Learning Neural Network Architectures using Backpropagation
Venue: arXiv cs.LG 2016
Year: 2016

Deep neural networks with millions of parameters are at the heart of many state of the art machine learning models today. However, recent works have shown that models with much smaller number of parameters can also perform just as well. In this work, we introduce the problem of architecture-learning, i.e; learning the architecture of a neural network along with weights. We introduce a new trainable parameter called tri-state ReLU, which helps in eliminating unnecessary neurons. We also propose a smooth regularizer which encourages the total number of neurons after elimination to be small. The resulting objective is differentiable and simple to optimize. We experimentally validate our method on both small and large networks, and show that it can learn models with a considerably small number of parameters without affecting prediction accuracy.
Could We Distinguish Child Users from Adults Using Keystroke Dynamics?
Venue: arXiv cs.HC 2016
Year: 2016

Significant portion of contemporary computer users are children, who are vulnerable to threats coming from the Internet. To protect children from such threats, in this study, we investigate how successfully typing data can be used to distinguish children from adults. For this purpose, we collect a dataset comprising keystroke data of 100 users and show that distinguishing child Internet users from adults is possible using Keystroke Dynamics with equal error rates less than 10 percent. However the error rates increase significantly when there are impostors in the system.
Metric learning approach for graph-based label propagation
Venue: arXiv cs.LG 2016
Year: 2016

The efficiency of graph-based semi-supervised algorithms depends on the graph of instances on which they are applied. The instances are often in a vectorial form before a graph linking them is built. The construction of the graph relies on a metric over the vectorial space that help define the weight of the connection between entities. The classic choice for this metric is usually a distance measure or a similarity measure based on the euclidean norm. We claim that in some cases the euclidean norm on the initial vectorial space might not be the more appropriate to solve the task efficiently. We propose an algorithm that aims at learning the most appropriate vectorial representation for building a graph on which the task at hand is solved efficiently.
Massive MIMO Relaying with Hybrid Processing
Venue: arXiv cs.IT 2016
Year: 2016

Massive multiple-input multiple-output (MIMO) relaying is a promising technological paradigm which can offer high spectral efficiency and substantially improved coverage. Yet, these configurations face some formidable challenges in terms of digital signal processing (DSP) power consumption and circuitry complexity, since the number of radio frequency (RF) chains may scale with the number of antennas at the relay station. In this paper, we advocate that performing a portion of the power-intensive DSP in the analog domain, using simple phase shifters and with a reduced number of RF paths, can address these challenges. In particular, we consider a multipair amplify-and-forward (AF) relay system with maximum ratio combining/transmission (MRC/MRT) and we determine the asymptotic spectral efficiency for this hybrid analog/digital architecture. After that, we extend our analytical results to account for heavily quantized analog phase shifters and show that the performance loss with 2 quantization bits is only 10%.
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
Venue: arXiv cs.DS 2016
Year: 2016

We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the Subtree Prune-and-Regraft (SPR) distance between two phylogenetic trees. Our result improves on the very recent 2.5-approximation algorithm due to Shi, Feng, You and Wang (2015). Our algorithm is the first approximation algorithm for this problem that uses LP duality in its analysis.
Predicting online user behaviour using deep learning algorithms
Venue: arXiv cs.LG 2016
Year: 2016

We propose a robust classifier to predict buying intentions based on user behaviour within a large e-commerce website. In this work we compare traditional machine learning techniques with the most advanced deep learning approaches. We show that both Deep Belief Networks and Stacked Denoising auto-Encoders achieved a substantial improvement by extracting features from high dimensional data during the pre-train phase. They prove also to be more convenient to deal with severe class imbalance.