OpenRaiser/Intern-Atlas huggingface dataset:
Prototype Filter Design for FBMC in Massive MIMO Channels
Venue: arXiv cs.IT 2017
Year: 2017

We perform an asymptotic study on the performance of filter bank multicarrier (FBMC) in the context of massive multi-input multi-output (MIMO). We show that the signal-to-interference-plus-noise ratio (SINR) cannot grow unboundedly by increasing the number of base station (BS) antennas, and is upper bounded by a certain deterministic value. This is a result of the correlation between the multi-antenna combining tap values and the channel impulse responses between the terminals and the BS antennas. To solve this problem, we introduce a simple FBMC prototype filter design method that removes this correlation, enabling us to achieve arbitrarily large SINR values by increasing the number of BS antennas.
Modeling Scalability of Distributed Machine Learning
Venue: arXiv cs.LG 2017
Year: 2017

Present day machine learning is computationally intensive and processes large amounts of data. It is implemented in a distributed fashion in order to address these scalability issues. The work is parallelized across a number of computing nodes. It is usually hard to estimate in advance how many nodes to use for a particular workload. We propose a simple framework for estimating the scalability of distributed machine learning algorithms. We measure the scalability by means of the speedup an algorithm achieves with more nodes. We propose time complexity models for gradient descent and graphical model inference. We validate our models with experiments on deep learning training and belief propagation. This framework was used to study the scalability of machine learning algorithms in Apache Spark.
Resilience by Structural Entrenchment: Dynamics of Single-Layer and Multiplex Networks Following Sudden Changes to Tie Costs
Venue: arXiv cs.SI 2017
Year: 2017

We examine a model of network formation in single-layer and multiplex networks in which individuals have positive incentives for social ties, closed triangles, and spillover edges. In particular, we investigate the influence of shocks to the network in which the cost of social ties changes after an initial equilibrium. We highlight the emergence of structural entrenchment: the retention of structural features, such as closed triangles and spillover edges, which are formed under historically different conditions from those currently driving network evolution. This work has broad implications for understanding path dependence in the structure and dynamics of single-layer and multiplex networks.
STDP allows close-to-optimal spatiotemporal spike pattern detection by single coincidence detector neurons
Venue: arXiv cs.NE 2017
Year: 2017

By recording multiple cells simultaneously, electrophysiologists have found evidence for repeating spatiotemporal spike patterns, which can carry information. How this information is extracted by downstream neurons is unclear. In this theoretical paper, we investigate to what extent a single cell could detect a given spike pattern and what the optimal parameters to do so are, in particular the membrane time constant $τ$. Using a leaky integrate-and-fire (LIF) neuron with instantaneous synapses and homogeneous Poisson input, we were able to compute this optimum analytically. Our results indicate that a relatively small $τ$ (at most a few tens of ms) is usually optimal, even when the pattern is much longer. This is somewhat counter intuitive as the resulting detector ignores most of the pattern, due to its fast memory decay. Next, we wondered if spike-timing-dependent plasticity (STDP) could enable a neuron to reach the theoretical optimum. We simulated a LIF neuron equipped with additive spike-timing-dependent potentiation and homeostatic rate-based depression, and repeatedly exposed it to a given input spike pattern. As in previous studies, the LIF progressively became selective to the repeating pattern with no supervision, even when the pattern was embedded in Poisson activity. Here we show that, using certain STDP parameters, the resulting pattern detector can be optimal. Taken together, these results may explain how humans can learn repeating visual or auditory sequences. Long sequences could be recognized thanks to coincidence detectors working at a much shorter timescale. This is consistent with the fact that recognition is still possible if a sound sequence is compressed, played backward, or scrambled using 10ms bins. Coincidence detection is a simple yet powerful mechanism, which could be the main function of neurons in the brain.
End-to-end Learning of Deep Visual Representations for Image Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

While deep learning has become a key ingredient in the top performing methods for many computer vision tasks, it has failed so far to bring similar improvements to instance-level image retrieval. In this article, we argue that reasons for the underwhelming results of deep methods on image retrieval are threefold: i) noisy training data, ii) inappropriate deep architecture, and iii) suboptimal training procedure. We address all three issues. First, we leverage a large-scale but noisy landmark dataset and develop an automatic cleaning method that produces a suitable training set for deep retrieval. Second, we build on the recent R-MAC descriptor, show that it can be interpreted as a deep and differentiable architecture, and present improvements to enhance it. Last, we train this network with a siamese architecture that combines three streams with a triplet loss. At the end of the training process, the proposed architecture produces a global image representation in a single forward pass that is well suited for image retrieval. Extensive experiments show that our approach significantly outperforms previous retrieval approaches, including state-of-the-art methods based on costly local descriptor indexing and spatial verification. On Oxford 5k, Paris 6k and Holidays, we respectively report 94.7, 96.6, and 94.8 mean average precision. Our representations can also be heavily compressed using product quantization with little loss in accuracy. For additional material, please see www.xrce.xerox.com/Deep-Image-Retrieval.
Transfer entropy in continuous time, with applications to jump and neural spiking processes
Venue: arXiv cs.IT 2017
Year: 2017

Transfer entropy has been used to quantify the directed flow of information between source and target variables in many complex systems. While transfer entropy was originally formulated in discrete time, in this paper we provide a framework for considering transfer entropy in continuous time systems, based on Radon-Nikodym derivatives between measures of complete path realizations. To describe the information dynamics of individual path realizations, we introduce the pathwise transfer entropy, the expectation of which is the transfer entropy accumulated over a finite time interval. We demonstrate that this formalism permits an instantaneous transfer entropy rate. These properties are analogous to the behavior of physical quantities defined along paths such as work and heat. We use this approach to produce an explicit form for the transfer entropy for pure jump processes, and highlight the simplified form in the specific case of point processes (frequently used in neuroscience to model neural spike trains). Finally, we present two synthetic spiking neuron model examples to exhibit the pertinent features of our formalism, namely, that the information flow for point processes consists of discontinuous jump contributions (at spikes in the target) interrupting a continuously varying contribution (relating to waiting times between target spikes). Numerical schemes based on our formalism promise significant benefits over existing strategies based on discrete time formalisms.
Compressive K-means
Venue: arXiv cs.LG 2017
Year: 2017

The Lloyd-Max algorithm is a classical approach to perform K-means clustering. Unfortunately, its cost becomes prohibitive as the training dataset grows large. We propose a compressive version of K-means (CKM), that estimates cluster centers from a sketch, i.e. from a drastically compressed representation of the training dataset. We demonstrate empirically that CKM performs similarly to Lloyd-Max, for a sketch size proportional to the number of cen-troids times the ambient dimension, and independent of the size of the original dataset. Given the sketch, the computational complexity of CKM is also independent of the size of the dataset. Unlike Lloyd-Max which requires several replicates, we further demonstrate that CKM is almost insensitive to initialization. For a large dataset of 10^7 data points, we show that CKM can run two orders of magnitude faster than five replicates of Lloyd-Max, with similar clustering performance on artificial data. Finally, CKM achieves lower classification errors on handwritten digits classification.
Aligning coding sequences with frameshift extension penalties
Venue: arXiv cs.DS 2017
Year: 2017

Frameshift translation is an important phenomenon that contributes to the appearance of novel Coding DNA Sequences (CDS) and functions in gene evolution, by allowing alternative amino acid translations of genes coding regions. Frameshift translations can be identified by aligning two CDS, from a same gene or from homologous genes, while accounting for their codon structure. Two main classes of algorithms have been proposed to solve the problem of aligning CDS, either by amino acid sequence alignment back-translation, or by simultaneously accounting for the nucleotide and amino acid levels. The former does not allow to account for frameshift translations and up to now, the latter exclusively accounts for frameshift translation initiation, not accounting for the length of the translation disruption caused by a frameshift. Here, we introduce a new scoring scheme with an algorithm for the pairwise alignment of CDS accounting for frameshift translation initiation and length, while simultaneously accounting for nucleotide and amino acid sequences. We compare the method to other CDS alignment methods based on an application to the comparison of pairs of CDS from homologous \emph{human}, \emph{mouse} and \emph{cow} genes of ten mammalian gene families from the Ensembl-Compara database. The results show that our method is particularly robust to parameter changes as compared to existing methods. It also appears to be a good compromise, performing well both in the presence and absence of frameshift translations between the CDS. An implementation of the method is available at https://github.com/UdeS-CoBIUS/FsePSA.
BehavioCog: An Observation Resistant Authentication Scheme
Venue: arXiv cs.CR 2017
Year: 2017

We propose that by integrating behavioural biometric gestures---such as drawing figures on a touch screen---with challenge-response based cognitive authentication schemes, we can benefit from the properties of both. On the one hand, we can improve the usability of existing cognitive schemes by significantly reducing the number of challenge-response rounds by (partially) relying on the hardness of mimicking carefully designed behavioural biometric gestures. On the other hand, the observation resistant property of cognitive schemes provides an extra layer of protection for behavioural biometrics; an attacker is unsure if a failed impersonation is due to a biometric failure or a wrong response to the challenge. We design and develop an instantiation of such a "hybrid" scheme, and call it BehavioCog. To provide security close to a 4-digit PIN---one in 10,000 chance to impersonate---we only need two challenge-response rounds, which can be completed in less than 38 seconds on average (as estimated in our user study), with the advantage that unlike PINs or passwords, the scheme is secure under observation.
Generalized Common Informations: Measuring Commonness by the Conditional Maximal Correlation
Venue: arXiv cs.IT 2017
Year: 2017

In literature, different common informations were defined by Gács and Körner, by Wyner, and by Kumar, Li, and Gamal, respectively. In this paper, we define two generalized versions of common informations, named approximate and exact information-correlation functions, by exploiting the conditional maximal correlation as a commonness or privacy measure. These two generalized common informations encompass the notions of Gács-Körner's, Wyner's, and Kumar-Li-Gamal's common informations as special cases. Furthermore, to give operational characterizations of these two generalized common informations, we also study the problems of private sources synthesis and common information extraction, and show that the information-correlation functions are equal to the minimum rates of commonness needed to ensure that some conditional maximal correlation constraints are satisfied for the centralized setting versions of these problems. As a byproduct, the conditional maximal correlation has been studied as well.
Resource Management in Non-orthogonal Multiple Access Networks for 5G and Beyond
Venue: arXiv cs.IT 2017
Year: 2017

Non-orthogonal multiple access (NOMA) schemes have been proposed for the next generation of mobile communication systems to improve the access efficiency by allowing multiple users to share the same spectrum in a non-orthogonal way. Due to the strong co-channel interference among mobile users introduced by NOMA, it poses significant challenges for system design and resource management. This article reviews resource management issues in NOMA systems. The main taxonomy of NOMA is presented by focusing on the following two categories: power-domain NOMA and code-domain NOMA. Then a novel radio resource management framework is presented based on game-theoretic models for uplink and downlink transmissions. Finally, potential applications and open research directions in the area of resource management for NOMA are provided.
Gap theorems for robust satisfiability: Boolean CSPs and beyond
Venue: arXiv cs.CC 2017
Year: 2017

A computational problem exhibits a "gap property" when there is no tractable boundary between two disjoint sets of instances. We establish a Gap Trichotomy Theorem for a family of constraint problem variants, completely classifying the complexity of possible ${\bf NP}$-hard gaps in the case of Boolean domains. As a consequence, we obtain a number of dichotomies for the complexity of specific variants of the constraint satisfaction problem: all are either polynomial-time tractable or $\mathbf{NP}$-complete. Schaefer's original dichotomy for $\textsf{SAT}$ variants is a notable particular case. Universal algebraic methods have been central to recent efforts in classifying the complexity of constraint satisfaction problems. A second contribution of the article is to develop aspects of the algebraic approach in the context of a number of variants of the constraint satisfaction problem. In particular, this allows us to lift our results on Boolean domains to many templates on non-Boolean domains.
The Geometry of Parallelism. Classical, Probabilistic, and Quantum Effects
Venue: arXiv cs.LO 2017
Year: 2017

We introduce a Geometry of Interaction model for higher-order quantum computation, and prove its adequacy for a full quantum programming language in which entanglement, duplication, and recursion are all available. Our model comes with a multi-token machine, a proof net system, and a PCF-style language. The approach we develop is not specific to quantum computation, and our model is an instance of a new framework whose main feature is the ability to model commutative effects in a parallel setting. Being based on a multi-token machine equipped with a memory, it has a concrete nature which makes it well suited for building low-level operational descriptions of higher-order languages.
Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments
Venue: arXiv cs.GT 2017
Year: 2017

We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneer's revenue in a variety of single-parameter auction environments including matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers. The analysis uses basic tools, is performed in its entirety in value-space, and simplifies the analysis of previously known results for special cases. Furthermore, the analysis extends to certain single-parameter auction environments where precise revenue maximization is known to be intractable, such as knapsack environments.
The Paths to Choreography Extraction
Venue: arXiv cs.PL 2017
Year: 2017

Choreographies are global descriptions of interactions among concurrent components, most notably used in the settings of verification (e.g., Multiparty Session Types) and synthesis of correct-by-construction software (Choreographic Programming). They require a top-down approach: programmers first write choreographies, and then use them to verify or synthesize their programs. However, most existing software does not come with choreographies yet, which prevents their application. To attack this problem, we propose a novel methodology (called choreography extraction) that, given a set of programs or protocol specifications, automatically constructs a choreography that describes their behavior. The key to our extraction is identifying a set of paths in a graph that represents the symbolic execution of the programs of interest. Our method improves on previous work in several directions: we can now deal with programs that are equipped with a state and internal computation capabilities; time complexity is dramatically better; we capture programs that are correct but not necessarily synchronizable, i.e., they work because they exploit asynchronous communication.
Neural Machine Translation in Linear Time
Venue: arXiv cs.CL 2017
Year: 2017

We present a novel neural network for processing sequences. The ByteNet is a one-dimensional convolutional neural network that is composed of two parts, one to encode the source sequence and the other to decode the target sequence. The two network parts are connected by stacking the decoder on top of the encoder and preserving the temporal resolution of the sequences. To address the differing lengths of the source and the target, we introduce an efficient mechanism by which the decoder is dynamically unfolded over the representation of the encoder. The ByteNet uses dilation in the convolutional layers to increase its receptive field. The resulting network has two core properties: it runs in time that is linear in the length of the sequences and it sidesteps the need for excessive memorization. The ByteNet decoder attains state-of-the-art performance on character-level language modelling and outperforms the previous best results obtained with recurrent networks. The ByteNet also achieves state-of-the-art performance on character-to-character machine translation on the English-to-German WMT translation task, surpassing comparable neural translation models that are based on recurrent networks with attentional pooling and run in quadratic time. We find that the latent alignment structure contained in the representations reflects the expected alignment between the tokens.
Bayesian Adaptive Data Analysis Guarantees from Subgaussianity
Venue: arXiv cs.LG 2017
Year: 2017

The new field of adaptive data analysis seeks to provide algorithms and provable guarantees for models of machine learning that allow researchers to reuse their data, which normally falls outside of the usual statistical paradigm of static data analysis. In 2014, Dwork, Feldman, Hardt, Pitassi, Reingold and Roth introduced one potential model and proposed several solutions based on differential privacy. In previous work in 2016, we described a problem with this model and instead proposed a Bayesian variant, but also found that the analogous Bayesian methods cannot achieve the same statistical guarantees as in the static case. In this paper, we prove the first positive results for the Bayesian model, showing that with a Dirichlet prior, the posterior mean algorithm indeed matches the statistical guarantees of the static case. The main ingredient is a new theorem showing that the $\mathrm{Beta}(α,β)$ distribution is subgaussian with variance proxy $O(1/(α+β+1))$, a concentration result also of independent interest. We provide two proofs of this result: a probabilistic proof utilizing a simple condition for the raw moments of a positive random variable and a learning-theoretic proof based on considering the beta distribution as a posterior, both of which have implications to other related problems.
A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group
Venue: arXiv cs.RO 2017
Year: 2017

Many geometric estimation problems take the form of synchronization over the special Euclidean group: estimate the values of a set of poses given noisy measurements of a subset of their pairwise relative transforms. This problem is typically formulated as a maximum-likelihood estimation that requires solving a nonconvex nonlinear program, which is computationally intractable in general. Nevertheless, in this paper we present an algorithm that is able to efficiently recover certifiably globally optimal solutions of this estimation problem in a non-adversarial noise regime. The crux of our approach is the development of a semidefinite relaxation of the maximum-likelihood estimation whose minimizer provides the exact MLE so long as the magnitude of the noise corrupting the available measurements falls below a certain critical threshold; furthermore, whenever exactness obtains, it is possible to verify this fact a posteriori, thereby certifying the optimality of the recovered estimate. We develop a specialized optimization scheme for solving large-scale instances of this semidefinite relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem on a low-dimensional Riemannian manifold, and then design a Riemannian truncated-Newton trust-region method to solve this reduction efficiently. We combine this fast optimization approach with a simple rounding procedure to produce our algorithm, SE-Sync. Experimental evaluation on a variety of simulated and real-world pose-graph SLAM datasets shows that SE-Sync is capable of recovering globally optimal solutions when the available measurements are corrupted by noise up to an order of magnitude greater than that typically encountered in robotics applications, and does so at a computational cost that scales comparably with that of direct Newton-type local search techniques.
Improving a Credit Scoring Model by Incorporating Bank Statement Derived Features
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we investigate the extent to which features derived from bank statements provided by loan applicants, and which are not declared on an application form, can enhance a credit scoring model for a New Zealand lending company. Exploring the potential of such information to improve credit scoring models in this manner has not been studied previously. We construct a baseline model based solely on the existing scoring features obtained from the loan application form, and a second baseline model based solely on the new bank statement-derived features. A combined feature model is then created by augmenting the application form features with the new bank statement derived features. Our experimental results using ROC analysis show that a combined feature model performs better than both of the two baseline models, and show that a number of the bank statement-derived features have value in improving the credit scoring model. The target data set used for modelling was highly imbalanced, and Naive Bayes was found to be the best performing model, and outperformed a number of other classifiers commonly used in credit scoring, suggesting its potential for future use on highly imbalanced data sets.