OpenRaiser/Intern-Atlas huggingface dataset:
Integer Programming Models and Parameterized Algorithms for Controlling Palletizers
Venue: arXiv cs.DS 2016
Year: 2016

We study the combinatorial FIFO Stack-Up problem, where bins have to be stacked-up from conveyor belts onto pallets. Given k sequences of labeled bins and a positive integer p, the goal is to stack-up the bins by iteratively removing the first bin of one of the k sequences and put it onto a pallet located at one of p stack-up places. The FIFO Stack-Up problem asks whether there is some processing of the sequences of bins such that at most p stack-up places are used. In this paper we strengthen the hardness of the FIFO Stack-Up by considering practical cases and the distribution of the pallets onto the sequences. We introduce a digraph model for this problem, the so called decision graph, which allows us to give a breadth first search solution. Further we apply methods to solve hard problems to the FIFO Stack-Up problem. In order to evaluate our algorithms, we introduce a method to generate random, but realistic instances for the FIFO Stack-Up problem. Our experimental study of running times shows that the breadth first search solution on the decision graph combined with a cutting technique can be used to solve practical instances on several thousands of bins of the FIFO Stack-Up problem. Further we analyze two integer programming approaches implemented in CPLEX and GLPK. As expected CPLEX can solve the instances much faster than GLPK and our pallet solution approach is much better than the bin solution approach.
Unbounded Lookahead in WMSO+U Games
Venue: arXiv cs.GT 2016
Year: 2016

Delay games are two-player games of infinite duration in which one player may delay her moves to obtain a lookahead on her opponent's moves. We consider delay games with winning conditions expressed in weak monadic second order logic with the unbounding quantifier (WMSO+U), which is able to express (un)boundedness properties. It is decidable whether the delaying player is able to win such a game with bounded lookahead, i.e., if she only skips a finite number of moves. However, bounded lookahead is not always sufficient: we present a game that can be won with unbounded lookahead, but not with bounded lookahead. Then, we consider WMSO+U delay games with unbounded lookahead and show that the exact evolution of the lookahead is irrelevant: the winner is always the same, as long as the initial lookahead is large enough and the lookahead tends to infinity.
Detecting Sparse Mixtures: Rate of Decay of Error Probability
Venue: arXiv cs.IT 2016
Year: 2016

We study the rate of decay of the probability of error for distinguishing between a sparse signal with noise, modeled as a sparse mixture, from pure noise. This problem has many applications in signal processing, evolutionary biology, bioinformatics, astrophysics and feature selection for machine learning. We let the mixture probability tend to zero as the number of observations tends to infinity and derive oracle rates at which the error probability can be driven to zero for a general class of signal and noise distributions via the likelihood ratio test. In contrast to the problem of detection of non-sparse signals, we see the log-probability of error decays sublinearly rather than linearly and is characterized through the $χ^2$-divergence rather than the Kullback-Leibler divergence for "weak" signals and can be independent of divergence for "strong" signals. Our contribution is the first characterization of the rate of decay of the error probability for this problem for both the false alarm and miss probabilities.
A dedicated greedy pursuit algorithm for sparse spectral representation of music sound
Venue: arXiv cs.SD 2016
Year: 2016

A dedicated algorithm for sparse spectral representation of music sound is presented. The goal is to enable the representation of a piece of music signal, as a linear superposition of as few spectral components as possible. A representation of this nature is said to be sparse. In the present context sparsity is accomplished by greedy selection of the spectral components, from an overcomplete set called a dictionary. The proposed algorithm is tailored to be applied with trigonometric dictionaries. Its distinctive feature being that it avoids the need for the actual construction of the whole dictionary, by implementing the required operations via the Fast Fourier Transform. The achieved sparsity is theoretically equivalent to that rendered by the Orthogonal Matching Pursuit method. The contribution of the proposed dedicated implementation is to extend the applicability of the standard Orthogonal Matching Pursuit algorithm, by reducing its storage and computational demands. The suitability of the approach for producing sparse spectral models is illustrated by comparison with the traditional method, in the line of the Short Time Fourier Transform, involving only the corresponding orthonormal trigonometric basis.
High-dimensional Time Series Prediction with Missing Values
Venue: arXiv cs.LG 2016
Year: 2016

High-dimensional time series prediction is needed in applications as diverse as demand forecasting and climatology. Often, such applications require methods that are both highly scalable, and deal with noisy data in terms of corruptions or missing values. Classical time series methods usually fall short of handling both these issues. In this paper, we propose to adapt matrix matrix completion approaches that have previously been successfully applied to large scale noisy data, but which fail to adequately model high-dimensional time series due to temporal dependencies. We present a novel temporal regularized matrix factorization (TRMF) framework which supports data-driven temporal dependency learning and enables forecasting ability to our new matrix factorization approach. TRMF is highly general, and subsumes many existing matrix factorization approaches for time series data. We make interesting connections to graph regularized matrix factorization methods in the context of learning the dependencies. Experiments on both real and synthetic data show that TRMF outperforms several existing approaches for common time series tasks.
Weaver: A High-Performance, Transactional Graph Database Based on Refinable Timestamps
Venue: arXiv cs.DC 2016
Year: 2016

Graph databases have become an increasingly common infrastructure component. Yet existing systems either operate on offline snapshots, provide weak consistency guarantees, or use expensive concurrency control techniques that limit performance. In this paper, we introduce a new distributed graph database, called Weaver, which enables efficient, transactional graph analyses as well as strictly serializable ACID transactions on dynamic graphs. The key insight that allows Weaver to combine strict serializability with horizontal scalability and high performance is a novel request ordering mechanism called refinable timestamps. This technique couples coarse-grained vector timestamps with a fine-grained timeline oracle to pay the overhead of strong consistency only when needed. Experiments show that Weaver enables a Bitcoin blockchain explorer that is 8x faster than Blockchain.info, and achieves 12x higher throughput than the Titan graph database on social network workloads and 4x lower latency than GraphLab on offline graph traversal workloads.
RF Lens-Embedded Massive MIMO Systems: Fabrication Issues and Codebook Design
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we investigate a radio frequency (RF) lens-embedded massive multiple-input multiple-output (MIMO) system and evaluate the system performance of limited feedback by utilizing a technique for generating a suitable codebook for the system. We fabricate an RF lens that operates on a 77 GHz (mmWave) band. Experimental results show a proper value of amplitude gain and an appropriate focusing property. In addition, using a simple numerical technique--beam propagation method (BPM)--we estimate the power profile of the RF lens and verify its accordance with experimental results. We also design a codebook--multi-variance codebook quantization (MVCQ)--for limited feedback by considering the characteristics of the RF lens antenna for massive MIMO systems. Numerical results confirm that the proposed system shows significant performance enhancement over a conventional massive MIMO system without an RF lens.
Controlled Matching Game for Resource Allocation and User Association in WLANs
Venue: arXiv cs.GT 2016
Year: 2016

In multi-rate IEEE 802.11 WLANs, the traditional user association based on the strongest received signal and the well known anomaly of the MAC protocol can lead to overloaded Access Points (APs), and poor or heterogeneous performance. Our goal is to propose an alternative game-theoretic approach for association. We model the joint resource allocation and user association as a matching game with complementarities and peer effects consisting of selfish players solely interested in their individual throughputs. Using recent game-theoretic results we first show that various resource sharing protocols actually fall in the scope of the set of stability-inducing resource allocation schemes. The game makes an extensive use of the Nash bargaining and some of its related properties that allow to control the incentives of the players. We show that the proposed mechanism can greatly improve the efficiency of 802.11 with heterogeneous nodes and reduce the negative impact of peer effects such as its MAC anomaly. The mechanism can be implemented as a virtual connectivity management layer to achieve efficient APs-user associations without modification of the MAC layer.
An Experimental Study of Segregation Mechanisms
Venue: arXiv cs.SI 2016
Year: 2016

Segregation is widespread in all realms of human society. Several influential studies have argued that intolerance is not a prerequisite for a segregated society, and that segregation can arise even when people generally prefer diversity. We investigated this paradox experimentally, by letting groups of high-school students play four different real-time interactive games. Incentives for neighbor similarity produced segregation, but incentives for neighbor dissimilarity and neighborhood diversity prevented it. The participants continued to move while their game scores were below optimal, but their individual moves did not consistently take them to the best alternative position. These small differences between human and simulated agents produced different segregation patterns than previously predicted, thus challenging conclusions about segregation arising from these models.
Sparse approximation based on a random overcomplete basis
Venue: arXiv cs.IT 2016
Year: 2016

We discuss a strategy of sparse approximation that is based on the use of an overcomplete basis, and evaluate its performance when a random matrix is used as this basis. A small combination of basis vectors is chosen from a given overcomplete basis, according to a given compression rate, such that they compactly represent the target data with as small a distortion as possible. As a selection method, we study the $\ell_0$- and $\ell_1$-based methods, which employ the exhaustive search and $\ell_1$-norm regularization techniques, respectively. The performance is assessed in terms of the trade-off relation between the representation distortion and the compression rate. First, we evaluate the performance analytically in the case that the methods are carried out ideally, using methods of statistical mechanics. Our result clarifies the fact that the $\ell_0$-based method greatly outperforms the $\ell_1$-based one. Second, we examine the practical performances of two well-known algorithms, orthogonal matching pursuit and approximate message passing, when they are used to execute the $\ell_0$- and $\ell_1$-based methods, respectively. Our examination shows that orthogonal matching pursuit achieves a much better performance than the exact execution of the $\ell_1$-based method, as well as approximate message passing. However, regarding the $\ell_0$-based method, there is still room to design more effective greedy algorithms than orthogonal matching pursuit. Finally, we evaluate the performances of the algorithms when they are applied to image data compression.
Aperiodic Subshifts on Polycyclic Groups
Venue: arXiv cs.DM 2016
Year: 2016

We prove that every polycyclic group of nonlinear growth admits a strongly aperiodic SFT and has an undecidable domino problem. This answers a question of [4] and generalizes the result of [2].
Mapping Unseen Words to Task-Trained Embedding Spaces
Venue: arXiv cs.CL 2016
Year: 2016

We consider the supervised training setting in which we learn task-specific word embeddings. We assume that we start with initial embeddings learned from unlabelled data and update them to learn task-specific embeddings for words in the supervised training data. However, for new words in the test set, we must use either their initial embeddings or a single unknown embedding, which often leads to errors. We address this by learning a neural network to map from initial embeddings to the task-specific embedding space, via a multi-loss objective function. The technique is general, but here we demonstrate its use for improved dependency parsing (especially for sentences with out-of-vocabulary words), as well as for downstream improvements on sentiment analysis.
Optimality of Rate Balancing in Wireless Sensor Networks
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of distributed binary hypothesis testing in a parallel network topology where sensors independently observe some phenomenon and send a finite rate summary of their observations to a fusion center for the final decision. We explicitly consider a scenario under which (integer) rate messages are sent over an error free multiple access channel, modeled by a sum rate constraint at the fusion center. This problem was previously studied by Chamberland and Veeravalli, who provided sufficient conditions for the optimality of one bit sensor messages. Their result is however crucially dependent on the feasibility of having as many one bit sensors as the (integer) sum rate constraint of the multiple access channel, an assumption that can often not be satisfied in practice. This prompts us to consider the case of an a-priori limited number of sensors and we provide sufficient condition under which having no two sensors with rate difference more than one bit, so called rate balancing, is an optimal strategy with respect to the Bhattacharyya distance between the hypotheses at the input to the fusion center. We further discuss explicit observation models under which these sufficient conditions are satisfied.
New Optimisation Methods for Machine Learning
Venue: arXiv cs.LG 2016
Year: 2016

A thesis submitted for the degree of Doctor of Philosophy of The Australian National University. In this work we introduce several new optimisation methods for problems in machine learning. Our algorithms broadly fall into two categories: optimisation of finite sums and of graph structured objectives. The finite sum problem is simply the minimisation of objective functions that are naturally expressed as a summation over a large number of terms, where each term has a similar or identical weight. Such objectives most often appear in machine learning in the empirical risk minimisation framework in the non-online learning setting. The second category, that of graph structured objectives, consists of objectives that result from applying maximum likelihood to Markov random field models. Unlike the finite sum case, all the non-linearity is contained within a partition function term, which does not readily decompose into a summation. For the finite sum problem, we introduce the Finito and SAGA algorithms, as well as variants of each. For graph-structured problems, we take three complementary approaches. We look at learning the parameters for a fixed structure, learning the structure independently, and learning both simultaneously. Specifically, for the combined approach, we introduce a new method for encouraging graph structures with the "scale-free" property. For the structure learning problem, we establish SHORTCUT, a O(n^{2.5}) expected time approximate structure learning method for Gaussian graphical models. For problems where the structure is known but the parameters unknown, we introduce an approximate maximum likelihood learning algorithm that is capable of learning a useful subclass of Gaussian graphical models.
Comparative computational results for some vertex and facet enumeration codes
Venue: arXiv cs.MS 2016
Year: 2016

We report some computational results comparing parallel and sequential codes for vertex/facet enumeration problems for convex polyhedra. The problems chosen span the range from simple to highly degenerate polytopes. We tested one code (lrs) based on pivoting and four codes (cddr+, ppl, normaliz, PORTA) based on the double description method. normaliz employs parallelization as do the codes plrs and mplrs which are based on lrs. We tested these codes using various hardware configurations with up to 1200 cores. Major speedups were obtained by parallelization, particularly by the code mplrs which uses MPI and can operate on clusters of machines.
SIBRA: Scalable Internet Bandwidth Reservation Architecture
Venue: arXiv cs.NI 2016
Year: 2016

This paper proposes a Scalable Internet Bandwidth Reservation Architecture (SIBRA) as a new approach against DDoS attacks, which, until now, continue to be a menace on today's Internet. SIBRA provides scalable inter-domain resource allocations and botnet-size independence, an important property to realize why previous defense approaches are insufficient. Botnet-size independence enables two end hosts to set up communication regardless of the size of distributed botnets in any Autonomous System in the Internet. SIBRA thus ends the arms race between DDoS attackers and defenders. Furthermore, SIBRA is based on purely stateless operations for reservation renewal, flow monitoring, and policing, resulting in highly efficient router operation, which is demonstrated with a full implementation. Finally, SIBRA supports Dynamic Interdomain Leased Lines (DILLs), offering new business opportunities for ISPs.
Where Is My Puppy? Retrieving Lost Dogs by Facial Features
Venue: arXiv cs.CV 2016
Year: 2016

A pet that goes missing is among many people's worst fears: a moment of distraction is enough for a dog or a cat wandering off from home. Some measures help matching lost animals to their owners; but automated visual recognition is one that - although convenient, highly available, and low-cost - is surprisingly overlooked. In this paper, we inaugurate that promising avenue by pursuing face recognition for dogs. We contrast four ready-to-use human facial recognizers (EigenFaces, FisherFaces, LBPH, and a Sparse method) to two original solutions based upon convolutional neural networks: BARK (inspired in architecture-optimized networks employed for human facial recognition) and WOOF (based upon off-the-shelf OverFeat features). Human facial recognizers perform poorly for dogs (up to 60.5% accuracy), showing that dog facial recognition is not a trivial extension of human facial recognition. The convolutional network solutions work much better, with BARK attaining up to 81.1% accuracy, and WOOF, 89.4%. The tests were conducted in two datasets: Flickr-dog, with 42 dogs of two breeds (pugs and huskies); and Snoopybook, with 18 mongrel dogs.
Channel Metrization
Venue: arXiv cs.IT 2016
Year: 2016

We present an algorithm that, given a channel, determines if there is a distance for it such that the maximum likelihood decoder coincides with the minimum distance decoder. We also show that any metric, up to a decoding equivalence, can be isometrically embedded into the hypercube with the Hamming metric, and thus, in terms of decoding, the Hamming metric is universal.
Deep convolutional neural networks for pedestrian detection
Venue: arXiv cs.CV 2016
Year: 2016

Pedestrian detection is a popular research topic due to its paramount importance for a number of applications, especially in the fields of automotive, surveillance and robotics. Despite the significant improvements, pedestrian detection is still an open challenge that calls for more and more accurate algorithms. In the last few years, deep learning and in particular convolutional neural networks emerged as the state of the art in terms of accuracy for a number of computer vision tasks such as image classification, object detection and segmentation, often outperforming the previous gold standards by a large margin. In this paper, we propose a pedestrian detection system based on deep learning, adapting a general-purpose convolutional network to the task at hand. By thoroughly analyzing and optimizing each step of the detection pipeline we propose an architecture that outperforms traditional methods, achieving a task accuracy close to that of state-of-the-art approaches, while requiring a low computational time. Finally, we tested the system on an NVIDIA Jetson TK1, a 192-core platform that is envisioned to be a forerunner computational brain of future self-driving cars.
Spatial Prediction Under Location Uncertainty In Cellular Networks
Venue: arXiv cs.OH 2016
Year: 2016

Coverage optimization is an important process for the operator as it is a crucial prerequisite towards offering a satisfactory quality of service to the end-users. The first step of this process is coverage prediction, which can be performed by interpolating geo-located measurements reported to the network by mobile users' equipments. In previous works, we proposed a low complexity coverage prediction algorithm based on the adaptation of the Geo-statistics Fixed Rank Kriging (FRK) algorithm. We supposed that the geo-location information reported with the radio measurements was perfect, which is not the case in reality. In this paper, we study the impact of location uncertainty on the coverage prediction accuracy and we extend the previously proposed algorithm to include geo-location error in the prediction model. We validate the proposed algorithm using both simulated and real field measurements. The FRK extended to take into account the location uncertainty proves to enhance the prediction accuracy while keeping a reasonable computational complexity.
Marking Shortest Paths On Pushdown Graphs Does Not Preserve MSO Decidability
Venue: arXiv cs.FL 2016
Year: 2016

In this paper we consider pushdown graphs, i.e. infinite graphs that can be described as transition graphs of deterministic real-time pushdown automata. We consider the case where some vertices are designated as being final and we built, in a breadth-first manner, a marking of edges that lead to such vertices (i.e., for every vertex that can reach a final one, we mark all out-going edges laying on some shortest path to a final vertex). Our main result is that the edge-marked version of a pushdown graph may itself no longer be a pushdown graph, as we prove that this enrich graph may have an undecidable MSO theory. In this paper we consider pushdown graphs, i.e. infinite graphs that can be described as transition graphs of deterministic real-time pushdown automata. We consider the case where some vertices are designated as being final and we build, in a breadth-first manner, a marking of edges that lead to such vertices (i.e., for every vertex that can reach a final one, we mark all out-going edges laying on some shortest path to a final vertex). Our main result is that the edge-marked version of a pushdown graph may itself no longer be a pushdown graph, as we prove that the MSO theory of this enriched graph may be undecidable.