OpenRaiser/Intern-Atlas huggingface dataset:
Second-Generation Curvelets on the Sphere
Venue: arXiv cs.IT 2016
Year: 2016

Curvelets are efficient to represent highly anisotropic signal content, such as a local linear and curvilinear structure. First-generation curvelets on the sphere, however, suffered from blocking artefacts. We present a new second-generation curvelet transform, where scale-discretised curvelets are constructed directly on the sphere. Scale-discretised curvelets exhibit a parabolic scaling relation, are well-localised in both spatial and harmonic domains, support the exact analysis and synthesis of both scalar and spin signals, and are free of blocking artefacts. We present fast algorithms to compute the exact curvelet transform, reducing computational complexity from $\mathcal{O}(L^5)$ to $\mathcal{O}(L^3\log_{2}{L})$ for signals band-limited at $L$. The implementation of these algorithms is made publicly available. Finally, we present an illustrative application demonstrating the effectiveness of curvelets for representing directional curve-like features in natural spherical images.
Fast Computation on Semirings Isomorphic to $(\times, \max)$ on $\mathbb{R}_+$
Venue: arXiv cs.DS 2016
Year: 2016

Important problems across multiple disciplines involve computations on the semiring $(\times, \max)$ (or its equivalents, the negated version $(\times, \min)$), the log-transformed version $(+, \max)$, or the negated log-transformed version $(+, \min)$): max-convolution, all-pairs shortest paths in a weighted graph, and finding the largest $k$ values in $x_i+y_j$ for two lists $x$ and $y$. However, fast algorithms such as those enabling FFT convolution, sub-cubic matrix multiplication, \emph{etc.}, require inverse operations, and thus cannot be computed on semirings. This manuscript generalizes recent advances on max-convolution: in this approach a small family of $p$-norm rings are used to efficiently approximate results on a nonnegative semiring. The general approach can be used to easily compute sub-cubic estimates of the all-pairs shortest paths in a graph with nonnegative edge weights and sub-quadratic estimates of the top $k$ values in $x_i+y_j$ when $x$ and $y$ are nonnegative. These methods are fast in practice and can benefit from coarse-grained parallelization.
Prioritized Experience Replay
Venue: arXiv cs.LG 2016
Year: 2016

Experience replay lets online reinforcement learning agents remember and reuse experiences from the past. In prior work, experience transitions were uniformly sampled from a replay memory. However, this approach simply replays transitions at the same frequency that they were originally experienced, regardless of their significance. In this paper we develop a framework for prioritizing experience, so as to replay important transitions more frequently, and therefore learn more efficiently. We use prioritized experience replay in Deep Q-Networks (DQN), a reinforcement learning algorithm that achieved human-level performance across many Atari games. DQN with prioritized experience replay achieves a new state-of-the-art, outperforming DQN with uniform replay on 41 out of 49 games.
ABC-CNN: An Attention Based Convolutional Neural Network for Visual Question Answering
Venue: arXiv cs.CV 2016
Year: 2016

We propose a novel attention based deep learning architecture for visual question answering task (VQA). Given an image and an image related natural language question, VQA generates the natural language answer for the question. Generating the correct answers requires the model's attention to focus on the regions corresponding to the question, because different questions inquire about the attributes of different image regions. We introduce an attention based configurable convolutional neural network (ABC-CNN) to learn such question-guided attention. ABC-CNN determines an attention map for an image-question pair by convolving the image feature map with configurable convolutional kernels derived from the question's semantics. We evaluate the ABC-CNN architecture on three benchmark VQA datasets: Toronto COCO-QA, DAQUAR, and VQA dataset. ABC-CNN model achieves significant improvements over state-of-the-art methods on these datasets. The question-guided attention generated by ABC-CNN is also shown to reflect the regions that are highly relevant to the questions.
Compact Bilinear Pooling
Venue: arXiv cs.CV 2016
Year: 2016

Bilinear models has been shown to achieve impressive performance on a wide range of visual tasks, such as semantic segmentation, fine grained recognition and face recognition. However, bilinear features are high dimensional, typically on the order of hundreds of thousands to a few million, which makes them impractical for subsequent analysis. We propose two compact bilinear representations with the same discriminative power as the full bilinear representation but with only a few thousand dimensions. Our compact representations allow back-propagation of classification errors enabling an end-to-end optimization of the visual recognition system. The compact bilinear representations are derived through a novel kernelized analysis of bilinear pooling which provide insights into the discriminative power of bilinear pooling, and a platform for further research in compact pooling methods. Experimentation illustrate the utility of the proposed representations for image classification and few-shot learning across several datasets.
Unsupervised Learning of Visual Structure using Predictive Generative Networks
Venue: arXiv cs.LG 2016
Year: 2016

The ability to predict future states of the environment is a central pillar of intelligence. At its core, effective prediction requires an internal model of the world and an understanding of the rules by which the world changes. Here, we explore the internal models developed by deep neural networks trained using a loss based on predicting future frames in synthetic video sequences, using a CNN-LSTM-deCNN framework. We first show that this architecture can achieve excellent performance in visual sequence prediction tasks, including state-of-the-art performance in a standard 'bouncing balls' dataset (Sutskever et al., 2009). Using a weighted mean-squared error and adversarial loss (Goodfellow et al., 2014), the same architecture successfully extrapolates out-of-the-plane rotations of computer-generated faces. Furthermore, despite being trained end-to-end to predict only pixel-level information, our Predictive Generative Networks learn a representation of the latent structure of the underlying three-dimensional objects themselves. Importantly, we find that this representation is naturally tolerant to object transformations, and generalizes well to new tasks, such as classification of static images. Similar models trained solely with a reconstruction loss fail to generalize as effectively. We argue that prediction can serve as a powerful unsupervised loss for learning rich internal representations of high-level object features.
Compressing Word Embeddings
Venue: arXiv cs.CL 2016
Year: 2016

Recent methods for learning vector space representations of words have succeeded in capturing fine-grained semantic and syntactic regularities using vector arithmetic. However, these vector space representations (created through large-scale text analysis) are typically stored verbatim, since their internal structure is opaque. Using word-analogy tests to monitor the level of detail stored in compressed re-representations of the same vector space, the trade-offs between the reduction in memory usage and expressiveness are investigated. A simple scheme is outlined that can reduce the memory footprint of a state-of-the-art embedding by a factor of 10, with only minimal impact on performance. Then, using the same `bit budget', a binary (approximate) factorisation of the same space is also explored, with the aim of creating an equivalent representation with better interpretability.
Denoising Criterion for Variational Auto-Encoding Framework
Venue: arXiv cs.LG 2016
Year: 2016

Denoising autoencoders (DAE) are trained to reconstruct their clean inputs with noise injected at the input level, while variational autoencoders (VAE) are trained with noise injected in their stochastic hidden layer, with a regularizer that encourages this noise injection. In this paper, we show that injecting noise both in input and in the stochastic hidden layer can be advantageous and we propose a modified variational lower bound as an improved objective function in this setup. When input is corrupted, then the standard VAE lower bound involves marginalizing the encoder conditional distribution over the input noise, which makes the training criterion intractable. Instead, we propose a modified training criterion which corresponds to a tractable bound when input is corrupted. Experimentally, we find that the proposed denoising variational autoencoder (DVAE) yields better average log-likelihood than the VAE and the importance weighted autoencoder on the MNIST and Frey Face datasets.
Fast Metric Learning For Deep Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

Similarity metrics are a core component of many information retrieval and machine learning systems. In this work we propose a method capable of learning a similarity metric from data equipped with a binary relation. By considering only the similarity constraints, and initially ignoring the features, we are able to learn target vectors for each instance using one of several appropriately designed loss functions. A regression model can then be constructed that maps novel feature vectors to the same target vector space, resulting in a feature extractor that computes vectors for which a predefined metric is a meaningful measure of similarity. We present results on both multiclass and multi-label classification datasets that demonstrate considerably faster convergence, as well as higher accuracy on the majority of the intrinsic evaluation tasks and all extrinsic evaluation tasks.
Resiliency of Deep Neural Networks under Quantization
Venue: arXiv cs.LG 2016
Year: 2016

The complexity of deep neural network algorithms for hardware implementation can be much lowered by optimizing the word-length of weights and signals. Direct quantization of floating-point weights, however, does not show good performance when the number of bits assigned is small. Retraining of quantized networks has been developed to relieve this problem. In this work, the effects of retraining are analyzed for a feedforward deep neural network (FFDNN) and a convolutional neural network (CNN). The network complexity is controlled to know their effects on the resiliency of quantized networks by retraining. The complexity of the FFDNN is controlled by varying the unit size in each hidden layer and the number of layers, while that of the CNN is done by modifying the feature map configuration. We find that the performance gap between the floating-point and the retrain-based ternary (+1, 0, -1) weight neural networks exists with a fair amount in 'complexity limited' networks, but the discrepancy almost vanishes in fully complex networks whose capability is limited by the training data, rather than by the number of connections. This research shows that highly complex DNNs have the capability of absorbing the effects of severe weight quantization through retraining, but connection limited networks are less resilient. This paper also presents the effective compression ratio to guide the trade-off between the network size and the precision when the hardware resource is limited.
Local Multipath Model Parameters for Generating 5G Millimeter-Wave 3GPP-like Channel Impulse Response
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents 28 GHz and 73 GHz empirically-derived large-scale and small-scale channel model parameters that characterize average temporal and angular properties of multipaths. Omnidirectional azimuth scans at both the transmitter and receiver used high gain directional antennas, from which global 3GPP modeling parameters for the mean global azimuth and zenith spreads of arrival were found to be 22 degrees and 6.2 degrees at 28 GHz, and 37.1 degrees and 3.8 degrees at 73 GHz, respectively, in non-line of sight (NLOS). Small-scale spatial measurements at 28 GHz reveal a mean cross-polar ratio for individual multipath components of 29.7 dB and 16.7 dB in line of sight and NLOS, respectively. Small-scale parameters extracted using the KPowerMeans algorithm yielded on average 5.3 and 4.6 clusters at 28 GHz and 73 GHz, respectively, in NLOS. The time cluster - spatial lobe (TCSL) modeling approach uses an alternative physically-based binning procedure and recreates 3GPP model parameters to generate channel impulse responses, as well as new parameters like the RMS lobe angular spreads useful in quantifying millimeter-wave directionality. The TCSL algorithm faithfully reproduces first- and second-order statistics of measured millimeter-wave channels.
ReSeg: A Recurrent Neural Network-based Model for Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

We propose a structured prediction architecture, which exploits the local generic features extracted by Convolutional Neural Networks and the capacity of Recurrent Neural Networks (RNN) to retrieve distant dependencies. The proposed architecture, called ReSeg, is based on the recently introduced ReNet model for image classification. We modify and extend it to perform the more challenging task of semantic segmentation. Each ReNet layer is composed of four RNN that sweep the image horizontally and vertically in both directions, encoding patches or activations, and providing relevant global information. Moreover, ReNet layers are stacked on top of pre-trained convolutional layers, benefiting from generic local features. Upsampling layers follow ReNet layers to recover the original image resolution in the final predictions. The proposed ReSeg architecture is efficient, flexible and suitable for a variety of semantic segmentation tasks. We evaluate ReSeg on several widely-used semantic segmentation datasets: Weizmann Horse, Oxford Flower, and CamVid; achieving state-of-the-art performance. Results show that ReSeg can act as a suitable architecture for semantic segmentation tasks, and may have further applications in other structured prediction problems. The source code and model hyperparameters are available on https://github.com/fvisin/reseg.
Which Regular Expression Patterns are Hard to Match?
Venue: arXiv cs.CC 2016
Year: 2016

Regular expressions constitute a fundamental notion in formal language theory and are frequently used in computer science to define search patterns. A classic algorithm for these problems constructs and simulates a non-deterministic finite automaton corresponding to the expression, resulting in an $O(mn)$ running time (where $m$ is the length of the pattern and $n$ is the length of the text). This running time can be improved slightly (by a polylogarithmic factor), but no significantly faster solutions are known. At the same time, much faster algorithms exist for various special cases of regular expressions, including dictionary matching, wildcard matching, subset matching, word break problem etc. In this paper, we show that the complexity of regular expression matching can be characterized based on its {\em depth} (when interpreted as a formula). Our results hold for expressions involving concatenation, OR, Kleene star and Kleene plus. For regular expressions of depth two (involving any combination of the above operators), we show the following dichotomy: matching and membership testing can be solved in near-linear time, except for "concatenations of stars", which cannot be solved in strongly sub-quadratic time assuming the Strong Exponential Time Hypothesis (SETH). For regular expressions of depth three the picture is more complex. Nevertheless, we show that all problems can either be solved in strongly sub-quadratic time, or cannot be solved in strongly sub-quadratic time assuming SETH. An intriguing special case of membership testing involves regular expressions of the form "a star of an OR of concatenations", e.g., $[a|ab|bc]^*$. This corresponds to the so-called {\em word break} problem, for which a dynamic programming algorithm with a runtime of (roughly) $O(n\sqrt{m})$ is known. We show that the latter bound is not tight and improve the runtime to $O(nm^{0.44\ldots})$.
DeePM: A Deep Part-Based Model for Object Detection and Semantic Part Localization
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a deep part-based model (DeePM) for symbiotic object detection and semantic part localization. For this purpose, we annotate semantic parts for all 20 object categories on the PASCAL VOC 2012 dataset, which provides information on object pose, occlusion, viewpoint and functionality. DeePM is a latent graphical model based on the state-of-the-art R-CNN framework, which learns an explicit representation of the object-part configuration with flexible type sharing (e.g., a sideview horse head can be shared by a fully-visible sideview horse and a highly truncated sideview horse with head and neck only). For comparison, we also present an end-to-end Object-Part (OP) R-CNN which learns an implicit feature representation for jointly mapping an image ROI to the object and part bounding boxes. We evaluate the proposed methods for both the object and part detection performance on PASCAL VOC 2012, and show that DeePM consistently outperforms OP R-CNN in detecting objects and parts. In addition, it obtains superior performance to Fast and Faster R-CNNs in object detection.
Block Matrix Formulations for Evolving Networks
Venue: arXiv cs.SI 2016
Year: 2016

Many types of pairwise interaction take the form of a fixed set of nodes with edges that appear and disappear over time. In the case of discrete-time evolution, the resulting evolving network may be represented by a time-ordered sequence of adjacency matrices. We consider here the issue of representing the system as a single, higher dimensional block matrix, built from the individual time-slices. We focus on the task of computing network centrality measures. From a modeling perspective, we show that there is a suitable block formulation that allows us to recover dynamic centrality measures respecting time's arrow. From a computational perspective, we show that the new block formulation leads to the design of more effective numerical algorithms.
Pushing the Boundaries of Boundary Detection using Deep Learning
Venue: arXiv cs.CV 2016
Year: 2016

In this work we show that adapting Deep Convolutional Neural Network training to the task of boundary detection can result in substantial improvements over the current state-of-the-art in boundary detection. Our contributions consist firstly in combining a careful design of the loss for boundary detection training, a multi-resolution architecture and training with external data to improve the detection accuracy of the current state of the art. When measured on the standard Berkeley Segmentation Dataset, we improve theoptimal dataset scale F-measure from 0.780 to 0.808 - while human performance is at 0.803. We further improve performance to 0.813 by combining deep learning with grouping, integrating the Normalized Cuts technique within a deep network. We also examine the potential of our boundary detector in conjunction with the task of semantic segmentation and demonstrate clear improvements over state-of-the-art systems. Our detector is fully integrated in the popular Caffe framework and processes a 320x420 image in less than a second.
Flexible Design for $α$-Duplex Communications in Multi-Tier Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

Backward compatibility is an essential ingredient for the success of new technologies. In the context of in-band full-duplex (FD) communication, FD base stations (BSs) should support half-duplex (HD) users' equipment (UEs) without sacrificing the foreseen FD gains. This paper presents flexible and tractable modeling framework for multi-tier cellular networks with FD BSs and FD/HD UEs. The presented model is based on stochastic geometry and accounts for the intrinsic vulnerability of uplink transmissions. The results show that FD UEs are not necessarily required to harvest rate gains from FD BSs. In particular, the results show that adding FD UEs to FD BSs offers a maximum of $5\%$ rate gain over FD BSs and HD UEs case if multi-user diversity is exploited, which is a marginal gain compared to the burden required to implement FD transceivers at the UEs' side. To this end, we shed light on practical scenarios where HD UEs operation with FD BSs outperforms the operation when both the BSs and UEs are FD and we find a closed form expression for the critical value of the self-interference attenuation power required for the FD UEs to outperform HD UEs.
Relative Citation Ratio (RCR): An empirical attempt to study a new field-normalized bibliometric indicator
Venue: arXiv cs.DL 2016
Year: 2016

Hutchins, Yuan, M., and Santangelo (2015) proposed the Relative Citation Ratio (RCR) as a new field-normalized impact indicator. This study investigates the RCR by correlating it on the level of single publications with established field-normalized indicators and assessments of the publications by peers. We find that the RCR correlates highly with established field-normalized indicators, but the correlation between RCR and peer assessments is only low to medium.
Compressed Sensing for Wireless Communications : Useful Tips and Tricks
Venue: arXiv cs.IT 2016
Year: 2016

As a paradigm to recover the sparse signal from a small set of linear measurements, compressed sensing (CS) has stimulated a great deal of interest in recent years. In order to apply the CS techniques to wireless communication systems, there are a number of things to know and also several issues to be considered. However, it is not easy to come up with simple and easy answers to the issues raised while carrying out research on CS. The main purpose of this paper is to provide essential knowledge and useful tips that wireless communication researchers need to know when designing CS-based wireless systems. First, we present an overview of the CS technique, including basic setup, sparse recovery algorithm, and performance guarantee. Then, we describe three distinct subproblems of CS, viz., sparse estimation, support identification, and sparse detection, with various wireless communication applications. We also address main issues encountered in the design of CS-based wireless communication systems. These include potentials and limitations of CS techniques, useful tips that one should be aware of, subtle points that one should pay attention to, and some prior knowledge to achieve better performance. Our hope is that this article will be a useful guide for wireless communication researchers and even non-experts to grasp the gist of CS techniques.
Deciding First-Order Satisfiability when Universal and Existential Variables are Separated
Venue: arXiv cs.LO 2016
Year: 2016

We introduce a new decidable fragment of first-order logic with equality, which strictly generalizes two already well-known ones -- the Bernays-Schönfinkel-Ramsey (BSR) Fragment and the Monadic Fragment. The defining principle is the syntactic separation of universally quantified variables from existentially quantified ones at the level of atoms. Thus, our classification neither rests on restrictions on quantifier prefixes (as in the BSR case) nor on restrictions on the arity of predicate symbols (as in the monadic case). We demonstrate that the new fragment exhibits the finite model property and derive a non-elementary upper bound on the computing time required for deciding satisfiability in the new fragment. For the subfragment of prenex sentences with the quantifier prefix $\exists^* \forall^* \exists^*$ the satisfiability problem is shown to be complete for NEXPTIME. Finally, we discuss how automated reasoning procedures can take advantage of our results.