OpenRaiser/Intern-Atlas huggingface dataset:
Leech Constellations of Construction-A Lattices
Venue: arXiv cs.IT 2017
Year: 2017

The problem of communicating over the additive white Gaussian noise (AWGN) channel with lattice codes is addressed in this paper. Theoretically, Voronoi constellations have proved to yield very powerful lattice codes when the fine/coding lattice is AWGN-good and the coarse/shaping lattice has an optimal shaping gain. However, achieving Shannon capacity with these premises and practically implementable encoding algorithms is in general not an easy task. In this work, a new way to encode and demap Construction-A Voronoi lattice codes is presented. As a meaningful application of this scheme, the second part of the paper is focused on Leech constellations of low-density Construction-A (LDA) lattices: LDA Voronoi lattice codes are presented whose numerically measured waterfall region is situated at less than 0.8 dB from Shannon capacity. These LDA lattice codes are based on dual-diagonal nonbinary low-density parity-check codes. With this choice, encoding, iterative decoding, and demapping have all linear complexity in the blocklength.
Matrix Characterization for GFDM Systems: Low-Complexity MMSE Receivers and Optimal Prototype Filters
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, a new matrix-based characterization of generalized-frequency-division-multiplexing (GFDM) transmitter matrices is proposed, as opposed to traditional vector-based characterization with prototype filters. The characterization facilitates deriving properties of GFDM (transmitter) matrices, including conditions for GFDM matrices being nonsingular and unitary, respectively. Using the new characterization, the necessary and sufficient conditions for the existence of a form of low-complexity implementation for a minimum mean square error (MMSE) receiver are derived. Such an implementation exists under multipath channels if the GFDM transmitter matrix is selected to be unitary. For cases where this implementation does not exist, a low-complexity suboptimal MMSE receiver is proposed, with its performance approximating that of an MMSE receiver. The new characterization also enables derivations of optimal prototype filters in terms of minimizing receiver mean square error (MSE). They are found to correspond to the use of unitary GFDM matrices under many scenarios. The use of such optimal filters in GFDM systems does not cause the problem of noise enhancement, thereby demonstrating the same MSE performance as orthogonal frequency division multiplexing. Moreover, we find that GFDM matrices with a size of power of two are verified to exist in the class of unitary GFDM matrices. Finally, while the out-of-band (OOB) radiation performance of systems using a unitary GFDM matrix is not optimal in general, it is shown that the OOB radiation can be satisfactorily low if parameters in the new characterization are carefully chosen.
Optimally Leveraging Density and Locality to Support LIMIT Queries
Venue: arXiv cs.DB 2017
Year: 2017

Existing database systems are not optimized for queries with a LIMIT clause---operating instead in an all-or-nothing manner. In this paper, we propose a fast LIMIT query evaluation engine, called NeedleTail, aimed at letting analysts browse a small sample of the query results on large datasets as quickly as possible, independent of the overall size of the result set. NeedleTail introduces density maps, a lightweight in-memory indexing structure, and a set of efficient algorithms (with desirable theoretical guarantees) to quickly locate promising blocks, trading off locality and density. In settings where the samples are used to compute aggregates, we extend techniques from survey sampling to mitigate the bias in our samples. Our experimental results demonstrate that NeedleTail returns results 4x faster on HDDs and 9x faster on SSDs on average, while occupying up to 23x less memory than existing techniques.
The Opening Scholarly Communication in Social Sciences project OSCOSS
Venue: arXiv cs.DL 2017
Year: 2017

The OSCOSS project (Opening Scholarly Communication in Social Sciences), which will be outlined, aims at providing integrated support for all steps of the scholarly communication process. Incl. collaborative writing of a scientific paper, collecting data related to existing publications, interpreting and including data in a paper, submitting the paper for peer review, reviewing the paper, publishing an article, and, finally, facilitating its consumption by readers. The OSCOSS project will support this process considering in particular the perspective of three main actors detailed in the use case descriptions below: readers, authors and reviewers.
The Power of Side-information in Subgraph Detection
Venue: arXiv cs.LG 2017
Year: 2017

In this work, we tackle the problem of hidden community detection. We consider Belief Propagation (BP) applied to the problem of detecting a hidden Erdős-Rényi (ER) graph embedded in a larger and sparser ER graph, in the presence of side-information. We derive two related algorithms based on BP to perform subgraph detection in the presence of two kinds of side-information. The first variant of side-information consists of a set of nodes, called cues, known to be from the subgraph. The second variant of side-information consists of a set of nodes that are cues with a given probability. It was shown in past works that BP without side-information fails to detect the subgraph correctly when an effective signal-to-noise ratio (SNR) parameter falls below a threshold. In contrast, in the presence of non-trivial side-information, we show that the BP algorithm achieves asymptotically zero error for any value of the SNR parameter. We validate our results through simulations on synthetic datasets as well as on a few real world networks.
Inferring Network Structure from Cascades
Venue: arXiv cs.SI 2017
Year: 2017

Many physical, biological, and social phenomena can be described by cascades taking place on a network. Often, the activity can be empirically observed, but not the underlying network of interactions. In this paper we offer three topological methods to infer the structure of any directed network given a set of cascade arrival times. Our formulas hold for a very general class of models where the activation probability of a node is a generic function of its degree and the number of its active neighbors. We report high success rates for synthetic and real networks, for several different cascade models.
A Data Quality Metric (DQM): How to Estimate The Number of Undetected Errors in Data Sets
Venue: arXiv cs.DB 2017
Year: 2017

Data cleaning, whether manual or algorithmic, is rarely perfect leaving a dataset with an unknown number of false positives and false negatives after cleaning. In many scenarios, quantifying the number of remaining errors is challenging because our data integrity rules themselves may be incomplete, or the available gold-standard datasets may be too small to extrapolate. As the use of inherently fallible crowds becomes more prevalent in data cleaning problems, it is important to have estimators to quantify the extent of such errors. We propose novel species estimators to estimate the number of distinct remaining errors in a dataset after it has been cleaned by a set of crowd workers -- essentially, quantifying the utility of hiring additional workers to clean the dataset. This problem requires new estimators that are robust to false positives and false negatives, and we empirically show on three real-world datasets that existing species estimators are unstable for this problem, while our proposed techniques quickly converge.
Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights
Venue: arXiv cs.LG 2017
Year: 2017

In a semi-supervised learning scenario, (possibly noisy) partially observed labels are used as input to train a classifier, in order to assign labels to unclassified samples. In this paper, we study this classifier learning problem from a graph signal processing (GSP) perspective. Specifically, by viewing a binary classifier as a piecewise constant graph-signal in a high-dimensional feature space, we cast classifier learning as a signal restoration problem via a classical maximum a posteriori (MAP) formulation. Unlike previous graph-signal restoration works, we consider in addition edges with negative weights that signify anti-correlation between samples. One unfortunate consequence is that the graph Laplacian matrix $\mathbf{L}$ can be indefinite, and previously proposed graph-signal smoothness prior $\mathbf{x}^T \mathbf{L} \mathbf{x}$ for candidate signal $\mathbf{x}$ can lead to pathological solutions. In response, we derive an optimal perturbation matrix $\boldsymbolΔ$ - based on a fast lower-bound computation of the minimum eigenvalue of $\mathbf{L}$ via a novel application of the Haynsworth inertia additivity formula---so that $\mathbf{L} + \boldsymbolΔ$ is positive semi-definite, resulting in a stable signal prior. Further, instead of forcing a hard binary decision for each sample, we define the notion of generalized smoothness on graph that promotes ambiguity in the classifier signal. Finally, we propose an algorithm based on iterative reweighted least squares (IRLS) that solves the posed MAP problem efficiently. Extensive simulation results show that our proposed algorithm outperforms both SVM variants and graph-based classifiers using positive-edge graphs noticeably.
Neural Machine Translation with Pivot Languages
Venue: arXiv cs.CL 2017
Year: 2017

While recent neural machine translation approaches have delivered state-of-the-art performance for resource-rich language pairs, they suffer from the data scarcity problem for resource-scarce language pairs. Although this problem can be alleviated by exploiting a pivot language to bridge the source and target languages, the source-to-pivot and pivot-to-target translation models are usually independently trained. In this work, we introduce a joint training algorithm for pivot-based neural machine translation. We propose three methods to connect the two models and enable them to interact with each other during training. Experiments on Europarl and WMT corpora show that joint training of source-to-pivot and pivot-to-target models leads to significant improvements over independent training across various languages.
The Fluctuating Two-Ray Fading Model: Statistical Characterization and Performance Analysis
Venue: arXiv cs.IT 2017
Year: 2017

We introduce the Fluctuating Two-Ray (FTR) fading model, a new statistical channel model that consists of two fluctuating specular components with random phases plus a diffuse component. The FTR model arises as the natural generalization of the two-wave with diffuse power (TWDP) fading model; this generalization allows its two specular components to exhibit a random amplitude fluctuation. Unlike the TWDP model, all the chief probability functions of the FTR fading model (PDF, CDF and MGF) are expressed in closed-form, having a functional form similar to other state-of-the-art fading models. We also provide approximate closed-form expressions for the PDF and CDF in terms of a finite number of elementary functions, which allow for a simple evaluation of these statistics to an arbitrary level of precision. We show that the FTR fading model provides a much better fit than Rician fading for recent small-scale fading measurements in 28 GHz outdoor millimeter-wave channels. Finally, the performance of wireless communication systems over FTR fading is evaluated in terms of the bit error rate and the outage capacity, and the interplay between the FTR fading model parameters and the system performance is discussed. Monte Carlo simulations have been carried out in order to validate the obtained theoretical expressions.
Will People Like Your Image? Learning the Aesthetic Space
Venue: arXiv cs.CV 2017
Year: 2017

Rating how aesthetically pleasing an image appears is a highly complex matter and depends on a large number of different visual factors. Previous work has tackled the aesthetic rating problem by ranking on a 1-dimensional rating scale, e.g., incorporating handcrafted attributes. In this paper, we propose a rather general approach to automatically map aesthetic pleasingness with all its complexity into an "aesthetic space" to allow for a highly fine-grained resolution. In detail, making use of deep learning, our method directly learns an encoding of a given image into this high-dimensional feature space resembling visual aesthetics. Additionally to the mentioned visual factors, differences in personal judgments have a large impact on the likeableness of a photograph. Nowadays, online platforms allow users to "like" or favor certain content with a single click. To incorporate a huge diversity of people, we make use of such multi-user agreements and assemble a large data set of 380K images (AROD) with associated meta information and derive a score to rate how visually pleasing a given photo is. We validate our derived model of aesthetics in a user study. Further, without any extra data labeling or handcrafted features, we achieve state-of-the art accuracy on the AVA benchmark data set. Finally, as our approach is able to predict the aesthetic quality of any arbitrary image or video, we demonstrate our results on applications for resorting photo collections, capturing the best shot on mobile devices and aesthetic key-frame extraction from videos.
Joint Energy-Bandwidth Allocation for Multi-User Channels with Cooperating Hybrid Energy Nodes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider the energy-bandwidth allocation for a network of multiple users, where the transmitters each powered by both an energy harvester and conventional grid, access the network orthogonally on the assigned frequency band. We assume that the energy harvesting state and channel gain of each transmitter can be predicted for $K$ time slots a priori. The different transmitters can cooperate by donating energy to each other. The tradeoff among the weighted sum throughput, the use of grid energy, and the amount of energy cooperation is studied through an optimization objective which is a linear combination of these quantities. This leads to an optimization problem with O($N^2K$) constraints, where $N$ is the total number of transmitter-receiver pairs, and the optimization is over seven sets of variables that denote energy and bandwidth allocation, grid energy utilization, and energy cooperation. To solve the problem efficiently, an iterative algorithm is proposed using the Proximal Jacobian ADMM. The optimization sub-problems corresponding to Proximal Jacobian ADMM steps are solved in closed form. We show that this algorithm converges to the optimal solution with an overall complexity of O($N^2K^2$). Numerical results show that the proposed algorithms can make efficient use of the harvested energy, grid energy, energy cooperation, and the available bandwidth.
A Semi-supervised Framework for Image Captioning
Venue: arXiv cs.CV 2017
Year: 2017

State-of-the-art approaches for image captioning require supervised training data consisting of captions with paired image data. These methods are typically unable to use unsupervised data such as textual data with no corresponding images, which is a much more abundant commodity. We here propose a novel way of using such textual data by artificially generating missing visual information. We evaluate this learning approach on a newly designed model that detects visual concepts present in an image and feed them to a reviewer-decoder architecture with an attention mechanism. Unlike previous approaches that encode visual concepts using word embeddings, we instead suggest using regional image features which capture more intrinsic information. The main benefit of this architecture is that it synthesizes meaningful thought vectors that capture salient image properties and then applies a soft attentive decoder to decode the thought vectors and generate image captions. We evaluate our model on both Microsoft COCO and Flickr30K datasets and demonstrate that this model combined with our semi-supervised learning method can largely improve performance and help the model to generate more accurate and diverse captions.
DelugeNets: Deep Networks with Efficient and Flexible Cross-layer Information Inflows
Venue: arXiv cs.CV 2017
Year: 2017

Deluge Networks (DelugeNets) are deep neural networks which efficiently facilitate massive cross-layer information inflows from preceding layers to succeeding layers. The connections between layers in DelugeNets are established through cross-layer depthwise convolutional layers with learnable filters, acting as a flexible yet efficient selection mechanism. DelugeNets can propagate information across many layers with greater flexibility and utilize network parameters more effectively compared to ResNets, whilst being more efficient than DenseNets. Remarkably, a DelugeNet model with just model complexity of 4.31 GigaFLOPs and 20.2M network parameters, achieve classification errors of 3.76% and 19.02% on CIFAR-10 and CIFAR-100 dataset respectively. Moreover, DelugeNet-122 performs competitively to ResNet-200 on ImageNet dataset, despite costing merely half of the computations needed by the latter.
The Algebraic Intersection Type Unification Problem
Venue: arXiv cs.LO 2017
Year: 2017

The algebraic intersection type unification problem is an important component in proof search related to several natural decision problems in intersection type systems. It is unknown and remains open whether the algebraic intersection type unification problem is decidable. We give the first nontrivial lower bound for the problem by showing (our main result) that it is exponential time hard. Furthermore, we show that this holds even under rank 1 solutions (substitutions whose codomains are restricted to contain rank 1 types). In addition, we provide a fixed-parameter intractability result for intersection type matching (one-sided unification), which is known to be NP-complete. We place the algebraic intersection type unification problem in the context of unification theory. The equational theory of intersection types can be presented as an algebraic theory with an ACI (associative, commutative, and idempotent) operator (intersection type) combined with distributivity properties with respect to a second operator (function type). Although the problem is algebraically natural and interesting, it appears to occupy a hitherto unstudied place in the theory of unification, and our investigation of the problem suggests that new methods are required to understand the problem. Thus, for the lower bound proof, we were not able to reduce from known results in ACI-unification theory and use game-theoretic methods for two-player tiling games.
Towards a Mathematical Understanding of the Difficulty in Learning with Feedforward Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Training deep neural networks for solving machine learning problems is one great challenge in the field, mainly due to its associated optimisation problem being highly non-convex. Recent developments have suggested that many training algorithms do not suffer from undesired local minima under certain scenario, and consequently led to great efforts in pursuing mathematical explanations for such observations. This work provides an alternative mathematical understanding of the challenge from a smooth optimisation perspective. By assuming exact learning of finite samples, sufficient conditions are identified via a critical point analysis to ensure any local minimum to be globally minimal as well. Furthermore, a state of the art algorithm, known as the Generalised Gauss-Newton (GGN) algorithm, is rigorously revisited as an approximate Newton's algorithm, which shares the property of being locally quadratically convergent to a global minimum under the condition of exact learning.
Finding Mirror Symmetry via Registration
Venue: arXiv cs.CV 2017
Year: 2017

Symmetry is prevalent in nature and a common theme in man-made designs. Both the human visual system and computer vision algorithms can use symmetry to facilitate object recognition and other tasks. Detecting mirror symmetry in images and data is, therefore, useful for a number of applications. Here, we demonstrate that the problem of fitting a plane of mirror symmetry to data in any Euclidian space can be reduced to the problem of registering two datasets. The exactness of the resulting solution depends entirely on the registration accuracy. This new Mirror Symmetry via Registration (MSR) framework involves (1) data reflection with respect to an arbitrary plane, (2) registration of original and reflected datasets, and (3) calculation of the eigenvector of eigenvalue -1 for the transformation matrix representing the reflection and registration mappings. To support MSR, we also introduce a novel 2D registration method based on random sample consensus of an ensemble of normalized cross-correlation matches. With this as its registration back-end, MSR achieves state-of-the-art performance for symmetry line detection in two independent 2D testing databases. We further demonstrate the generality of MSR by testing it on a database of 3D shapes with an iterative closest point registration back-end. Finally, we explore its applicability to examining symmetry in natural systems by assessing the degree of symmetry present in myelinated axon reconstructions from a larval zebrafish.
Precondition Inference for Peephole Optimizations in LLVM
Venue: arXiv cs.PL 2017
Year: 2017

Peephole optimizations are a common source of compiler bugs. Compiler developers typically transform an incorrect peephole optimization into a valid one by strengthening the precondition. This process is challenging and tedious. This paper proposes ALIVE-INFER, a data-driven approach that infers preconditions for peephole optimizations expressed in Alive. ALIVE-INFER generates positive and negative examples for an optimization, enumerates predicates on-demand, and learns a set of predicates that separate the positive and negative examples. ALIVE-INFER repeats this process until it finds a precondition that ensures the validity of the optimization. ALIVE-INFER reports both a weakest precondition and a set of succinct partial preconditions to the developer. Our prototype generates preconditions that are weaker than LLVM's preconditions for 73 optimizations in the Alive suite. We also demonstrate the applicability of this technique to generalize 54 optimization patterns generated by Souper, an LLVM~IR--based superoptimizer.
Approximate Near Neighbors for General Symmetric Norms
Venue: arXiv cs.DS 2017
Year: 2017

We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every $n$, $d = n^{o(1)}$, and every $d$-dimensional symmetric norm $\|\cdot\|$, there exists a data structure for $\mathrm{poly}(\log \log n)$-approximate nearest neighbor search over $\|\cdot\|$ for $n$-point datasets achieving $n^{o(1)}$ query time and $n^{1+o(1)}$ space. The main technical ingredient of the algorithm is a low-distortion embedding of a symmetric norm into a low-dimensional iterated product of top-$k$ norms. We also show that our techniques cannot be extended to general norms.