OpenRaiser/Intern-Atlas huggingface dataset:
Sequential Labeling with online Deep Learning
Venue: arXiv cs.LG 2015
Year: 2015

Deep learning has attracted great attention recently and yielded the state of the art performance in dimension reduction and classification problems. However, it cannot effectively handle the structured output prediction, e.g. sequential labeling. In this paper, we propose a deep learning structure, which can learn discriminative features for sequential labeling problems. More specifically, we add the inter-relationship between labels in our deep learning structure, in order to incorporate the context information from the sequential data. Thus, our model is more powerful than linear Conditional Random Fields (CRFs) because the objective function learns latent non-linear features so that target labeling can be better predicted. We pretrain the deep structure with stacked restricted Boltzmann machines (RBMs) for feature learning and optimize our objective function with online learning algorithm, a mixture of perceptron training and stochastic gradient descent. We test our model on different challenge tasks, and show that our model outperforms significantly over the completive baselines.
A Novel Adaptive Possibilistic Clustering Algorithm
Venue: arXiv cs.CV 2015
Year: 2015

In this paper a novel possibilistic c-means clustering algorithm, called Adaptive Possibilistic c-means, is presented. Its main feature is that {\it all} its parameters, after their initialization, are properly adapted during its execution. Provided that the algorithm starts with a reasonable overestimate of the number of physical clusters formed by the data, it is capable, in principle, to unravel them (a long-standing issue in the clustering literature). This is due to the fully adaptive nature of the proposed algorithm that enables the removal of the clusters that gradually become obsolete. In addition, the adaptation of all its parameters increases the flexibility of the algorithm in following the variations in the formation of the clusters that occur from iteration to iteration. Theoretical results that are indicative of the convergence behavior of the algorithm are also provided. Finally, extensive simulation results on both synthetic and real data highlight the effectiveness of the proposed algorithm.
A Topic Modeling Approach to Ranking
Venue: arXiv cs.LG 2015
Year: 2015

We propose a topic modeling approach to the prediction of preferences in pairwise comparisons. We develop a new generative model for pairwise comparisons that accounts for multiple shared latent rankings that are prevalent in a population of users. This new model also captures inconsistent user behavior in a natural way. We show how the estimation of latent rankings in the new generative model can be formally reduced to the estimation of topics in a statistically equivalent topic modeling problem. We leverage recent advances in the topic modeling literature to develop an algorithm that can learn shared latent rankings with provable consistency as well as sample and computational complexity guarantees. We demonstrate that the new approach is empirically competitive with the current state-of-the-art approaches in predicting preferences on some semi-synthetic and real world datasets.
A Robust Transformation-Based Learning Approach Using Ripple Down Rules for Part-of-Speech Tagging
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, we propose a new approach to construct a system of transformation rules for the Part-of-Speech (POS) tagging task. Our approach is based on an incremental knowledge acquisition method where rules are stored in an exception structure and new rules are only added to correct the errors of existing rules; thus allowing systematic control of the interaction between the rules. Experimental results on 13 languages show that our approach is fast in terms of training time and tagging speed. Furthermore, our approach obtains very competitive accuracy in comparison to state-of-the-art POS and morphological taggers.
Sharing Non-Anonymous Costs of Multiple Resources Optimally
Venue: arXiv cs.GT 2015
Year: 2015

In cost sharing games, the existence and efficiency of pure Nash equilibria fundamentally depends on the method that is used to share the resources' costs. We consider a general class of resource allocation problems in which a set of resources is used by a heterogeneous set of selfish users. The cost of a resource is a (non-decreasing) function of the set of its users. Under the assumption that the costs of the resources are shared by uniform cost sharing protocols, i.e., protocols that use only local information of the resource's cost structure and its users to determine the cost shares, we exactly quantify the inefficiency of the resulting pure Nash equilibria. Specifically, we show tight bounds on prices of stability and anarchy for games with only submodular and only supermodular cost functions, respectively, and an asymptotically tight bound for games with arbitrary set-functions. While all our upper bounds are attained for the well-known Shapley cost sharing protocol, our lower bounds hold for arbitrary uniform cost sharing protocols and are even valid for games with anonymous costs, i.e., games in which the cost of each resource only depends on the cardinality of the set of its users.
Rehabilitation of Count-based Models for Word Vector Representations
Venue: arXiv cs.CL 2015
Year: 2015

Recent works on word representations mostly rely on predictive models. Distributed word representations (aka word embeddings) are trained to optimally predict the contexts in which the corresponding words tend to appear. Such models have succeeded in capturing word similarties as well as semantic and syntactic regularities. Instead, we aim at reviving interest in a model based on counts. We present a systematic study of the use of the Hellinger distance to extract semantic representations from the word co-occurence statistics of large text corpora. We show that this distance gives good performance on word similarity and analogy tasks, with a proper type and size of context, and a dimensionality reduction based on a stochastic low-rank approximation. Besides being both simple and intuitive, this method also provides an encoding function which can be used to infer unseen words or phrases. This becomes a clear advantage compared to predictive models which must train these new words.
Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation
Venue: arXiv cs.SC 2015
Year: 2015

Blackbox algorithms for linear algebra problems start with projection of the sequence of powers of a matrix to a sequence of vectors (Lanczos), a sequence of scalars (Wiedemann) or a sequence of smaller matrices (block methods). Such algorithms usually depend on the minimal polynomial of the resulting sequence being that of the given matrix. Here exact formulas are given for the probability that this occurs. They are based on the generalized Jordan normal form (direct sum of companion matrices of the elementary divisors) of the matrix. Sharp bounds follow from this for matrices of unknown elementary divisors. The bounds are valid for all finite field sizes and show that a small blocking factor can give high probability of success for all cardinalities and matrix dimensions.
A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness
Venue: arXiv cs.CC 2015
Year: 2015

We present simple, self-contained proofs of correctness for algorithms for linearity testing and program checking of linear functions on finite subsets of integers represented as n-bit numbers. In addition we explore a generalization of self-testing to homomorphisms on a multidimensional vector space. We show that our self-testing algorithm for the univariate case can be directly generalized to vector space domains. The number of queries made by our algorithms is independent of domain size.
Capacity-Approaching PhaseCode for Low-Complexity Compressive Phase Retrieval
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we tackle the general compressive phase retrieval problem. The problem is to recover a K-sparse complex vector of length n, $x\in \mathbb{C}^n$, from the magnitudes of m linear measurements, $y=|Ax|$, where $A \in \mathbb{C}^{m \times n}$ can be designed, and the magnitudes are taken component-wise for vector $Ax\in \mathbb{C}^m$. We propose a variant of the PhaseCode algorithm, and show that, using an irregular left-degree sparse-graph code construction, the algorithm can recover almost all the K non-zero signal components using only slightly more than 4K measurements under some mild assumptions, with optimal time and memory complexity of ${\cal O}(K)$. It is known that the fundamental limit for the number of measurements in compressive phase retrieval problem is $4K - o(K)$. To the best of our knowledge, this is the first constructive capacity-approaching compressive phase retrieval algorithm. As a second contribution, we propose another variant of the PhaseCode algorithm that is based on a Compressive Sensing framework involving sparse-graph codes. Our proposed algorithm is an instance of a more powerful "separation" architecture that can be used to address the compressive phase-retrieval problem in general. This modular design features a compressive sensing outer layer, and a trigonometric-based phase-retrieval inner layer. The compressive-sensing layer operates as a linear phase-aware compressive measurement subsystem, while the trig-based phase-retrieval layer provides the desired abstraction between the actually targeted nonlinear phase-retrieval problem and the induced linear compressive-sensing problem. Invoking this architecture based on the use of sparse-graph codes for the compressive sensing layer, we show that we can exactly recover a signal from only the magnitudes of its linear measurements using only slightly more than 6K measurements.
Dynamic Structure Embedded Online Multiple-Output Regression for Stream Data
Venue: arXiv cs.LG 2015
Year: 2015

Online multiple-output regression is an important machine learning technique for modeling, predicting, and compressing multi-dimensional correlated data streams. In this paper, we propose a novel online multiple-output regression method, called MORES, for stream data. MORES can \emph{dynamically} learn the structure of the coefficients change in each update step to facilitate the model's continuous refinement. We observe that limited expressive ability of the regression model, especially in the preliminary stage of online update, often leads to the variables in the residual errors being dependent. In light of this point, MORES intends to \emph{dynamically} learn and leverage the structure of the residual errors to improve the prediction accuracy. Moreover, we define three statistical variables to \emph{exactly} represent all the seen samples for \emph{incrementally} calculating prediction loss in each online update round, which can avoid loading all the training data into memory for updating model, and also effectively prevent drastic fluctuation of the model in the presence of noise. Furthermore, we introduce a forgetting factor to set different weights on samples so as to track the data streams' evolving characteristics quickly from the latest samples. Experiments on one synthetic dataset and three real-world datasets validate the effectiveness of the proposed method. In addition, the update speed of MORES is at least 2000 samples processed per second on the three real-world datasets, more than 15 times faster than the state-of-the-art online learning algorithm.
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Venue: arXiv cs.GT 2015
Year: 2015

Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and optimality. We focus on AMD's paradigmatic problem: combinatorial auctions. We present a new generalization of the VC dimension to multivalued collections of functions, which encompasses the classical VC dimension, Natarajan dimension, and Steele dimension. We present a corresponding generalization of the Sauer-Shelah Lemma and harness this VC machinery to establish inapproximability results for deterministic truthful mechanisms. Our results essentially unify all inapproximability results for deterministic truthful mechanisms for combinatorial auctions to date and establish new separation gaps between truthful and non-truthful algorithms.
Algorithmic Robustness for Learning via $(ε, γ, τ)$-Good Similarity Functions
Venue: arXiv cs.LG 2015
Year: 2015

The notion of metric plays a key role in machine learning problems such as classification, clustering or ranking. However, it is worth noting that there is a severe lack of theoretical guarantees that can be expected on the generalization capacity of the classifier associated to a given metric. The theoretical framework of $(ε, γ, τ)$-good similarity functions (Balcan et al., 2008) has been one of the first attempts to draw a link between the properties of a similarity function and those of a linear classifier making use of it. In this paper, we extend and complete this theory by providing a new generalization bound for the associated classifier based on the algorithmic robustness framework.
Fast Label Embeddings via Randomized Linear Algebra
Venue: arXiv cs.LG 2015
Year: 2015

Many modern multiclass and multilabel problems are characterized by increasingly large output spaces. For these problems, label embeddings have been shown to be a useful primitive that can improve computational and statistical efficiency. In this work we utilize a correspondence between rank constrained estimation and low dimensional label embeddings that uncovers a fast label embedding algorithm which works in both the multiclass and multilabel settings. The result is a randomized algorithm whose running time is exponentially faster than naive algorithms. We demonstrate our techniques on two large-scale public datasets, from the Large Scale Hierarchical Text Challenge and the Open Directory Project, where we obtain state of the art results.
Why does Deep Learning work? - A perspective from Group Theory
Venue: arXiv cs.LG 2015
Year: 2015

Why does Deep Learning work? What representations does it capture? How do higher-order representations emerge? We study these questions from the perspective of group theory, thereby opening a new approach towards a theory of Deep learning. One factor behind the recent resurgence of the subject is a key algorithmic step called pre-training: first search for a good generative model for the input samples, and repeat the process one layer at a time. We show deeper implications of this simple principle, by establishing a connection with the interplay of orbits and stabilizers of group actions. Although the neural networks themselves may not form groups, we show the existence of {\em shadow} groups whose elements serve as close approximations. Over the shadow groups, the pre-training step, originally introduced as a mechanism to better initialize a network, becomes equivalent to a search for features with minimal orbits. Intuitively, these features are in a way the {\em simplest}. Which explains why a deep learning network learns simple features first. Next, we show how the same principle, when repeated in the deeper layers, can capture higher order representations, and why representation complexity increases as the layers get deeper.
Semantic Modelling with Long-Short-Term Memory for Information Retrieval
Venue: arXiv cs.IR 2015
Year: 2015

In this paper we address the following problem in web document and information retrieval (IR): How can we use long-term context information to gain better IR performance? Unlike common IR methods that use bag of words representation for queries and documents, we treat them as a sequence of words and use long short term memory (LSTM) to capture contextual dependencies. To the best of our knowledge, this is the first time that LSTM is applied to information retrieval tasks. Unlike training traditional LSTMs, the training strategy is different due to the special nature of information retrieval problem. Experimental evaluation on an IR task derived from the Bing web search demonstrates the ability of the proposed method in addressing both lexical mismatch and long-term context modelling issues, thereby, significantly outperforming existing state of the art methods for web document retrieval task.
Neural Network Regularization via Robust Weight Factorization
Venue: arXiv cs.LG 2015
Year: 2015

Regularization is essential when training large neural networks. As deep neural networks can be mathematically interpreted as universal function approximators, they are effective at memorizing sampling noise in the training data. This results in poor generalization to unseen data. Therefore, it is no surprise that a new regularization technique, Dropout, was partially responsible for the now-ubiquitous winning entry to ImageNet 2012 by the University of Toronto. Currently, Dropout (and related methods such as DropConnect) are the most effective means of regularizing large neural networks. These amount to efficiently visiting a large number of related models at training time, while aggregating them to a single predictor at test time. The proposed FaMe model aims to apply a similar strategy, yet learns a factorization of each weight matrix such that the factors are robust to noise.
Incidence coloring of graphs with high maximum average degree
Venue: arXiv cs.DM 2015
Year: 2015

An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent if one of the following holds: (i) $v = w$, (ii) $e = f$ or (iii) $vw = e$ or $f$. An incidence coloring of $G$ assigns a color to each incidence of $G$ in such a way that adjacent incidences get distinct colors. In 2005, Hosseini Dolama \emph{et al.}~\citep{ds05} proved that every graph with maximum average degree strictly less than $3$ can be incidence colored with $Δ+3$ colors. Recently, Bonamy \emph{et al.}~\citep{Bonamy} proved that every graph with maximum degree at least $4$ and with maximum average degree strictly less than $\frac{7}{3}$ admits an incidence $(Δ+1)$-coloring. In this paper we give bounds for the number of colors needed to color graphs having maximum average degrees bounded by different values between $4$ and $6$. In particular we prove that every graph with maximum degree at least $7$ and with maximum average degree less than $4$ admits an incidence $(Δ+3)$-coloring. This result implies that every triangle-free planar graph with maximum degree at least $7$ is incidence $(Δ+3)$-colorable. We also prove that every graph with maximum average degree less than 6 admits an incidence $(Δ+ 7)$-coloring. More generally, we prove that $Δ+k-1$ colors are enough when the maximum average degree is less than $k$ and the maximum degree is sufficiently large.
Extraction of Salient Sentences from Labelled Documents
Venue: arXiv cs.CL 2015
Year: 2015

We present a hierarchical convolutional document model with an architecture designed to support introspection of the document structure. Using this model, we show how to use visualisation techniques from the computer vision literature to identify and extract topic-relevant sentences. We also introduce a new scalable evaluation technique for automatic sentence extraction systems that avoids the need for time consuming human annotation of validation data.
Multi-modal Sensor Registration for Vehicle Perception via Deep Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

The ability to simultaneously leverage multiple modes of sensor information is critical for perception of an automated vehicle's physical surroundings. Spatio-temporal alignment of registration of the incoming information is often a prerequisite to analyzing the fused data. The persistence and reliability of multi-modal registration is therefore the key to the stability of decision support systems ingesting the fused information. LiDAR-video systems like on those many driverless cars are a common example of where keeping the LiDAR and video channels registered to common physical features is important. We develop a deep learning method that takes multiple channels of heterogeneous data, to detect the misalignment of the LiDAR-video inputs. A number of variations were tested on the Ford LiDAR-video driving test data set and will be discussed. To the best of our knowledge the use of multi-modal deep convolutional neural networks for dynamic real-time LiDAR-video registration has not been presented.
Cloud Enabled Emergency Navigation Using Faster-than-real-time Simulation
Venue: arXiv cs.OH 2015
Year: 2015

State-of-the-art emergency navigation approaches are designed to evacuate civilians during a disaster based on real-time decisions using a pre-defined algorithm and live sensory data. Hence, casualties caused by the poor decisions and guidance are only apparent at the end of the evacuation process and cannot then be remedied. Previous research shows that the performance of routing algorithms for evacuation purposes are sensitive to the initial distribution of evacuees, the occupancy levels, the type of disaster and its as well its locations. Thus an algorithm that performs well in one scenario may achieve bad results in another scenario. This problem is especially serious in heuristic-based routing algorithms for evacuees where results are affected by the choice of certain parameters. Therefore, this paper proposes a simulation-based evacuee routing algorithm that optimises evacuation by making use of the high computational power of cloud servers. Rather than guiding evacuees with a predetermined routing algorithm, a robust Cognitive Packet Network based algorithm is first evaluated via a cloud-based simulator in a faster-than-real-time manner, and any "simulated casualties" are then re-routed using a variant of Dijkstra's algorithm to obtain new safe paths for them to exits. This approach can be iterated as long as corrective action is still possible.
Higher-order Spatial Accuracy in Diffeomorphic Image Registration
Venue: arXiv cs.CV 2015
Year: 2015

We discretize a cost functional for image registration problems by deriving Taylor expansions for the matching term. Minima of the discretized cost functionals can be computed with no spatial discretization error, and the optimal solutions are equivalent to minimal energy curves in the space of $k$-jets. We show that the solutions convergence to optimal solutions of the original cost functional as the number of particles increases with a convergence rate of $O(h^{d+k})$ where $h$ is a resolution parameter. The effect of this approach over traditional particle methods is illustrated on synthetic examples and real images.
Correctness and completeness of logic programs
Venue: arXiv cs.LO 2015
Year: 2015

We discuss proving correctness and completeness of definite clause logic programs. We propose a method for proving completeness, while for proving correctness we employ a method which should be well known but is often neglected. Also, we show how to prove completeness and correctness in the presence of SLD-tree pruning, and point out that approximate specifications simplify specifications and proofs. We compare the proof methods to declarative diagnosis (algorithmic debugging), showing that approximate specifications eliminate a major drawback of the latter. We argue that our proof methods reflect natural declarative thinking about programs, and that they can be used, formally or informally, in every-day programming.