OpenRaiser/Intern-Atlas huggingface dataset:
Optimization of Graph Based Codes for Belief Propagation Decoding
Venue: arXiv cs.IT 2016
Year: 2016

A low-density parity-check (LDPC) code is a linear block code described by a sparse parity-check matrix, which can be efficiently represented by a bipartite Tanner graph. The standard iterative decoding algorithm, known as belief propagation, passes messages along the edges of this Tanner graph. Density evolution is an efficient method to analyze the performance of the belief propagation decoding algorithm for a particular LDPC code ensemble, enabling the determination of a decoding threshold. The basic problem addressed in this work is how to optimize the Tanner graph so that the decoding threshold is as large as possible. We introduce a new code optimization technique which involves the search space range which can be thought of as minimizing randomness in differential evolution or limiting the search range in exhaustive search. This technique is applied to the design of good irregular LDPC codes and multiedge type LDPC codes.
New Density Evolution Approximation for LDPC and Multi-Edge Type LDPC Codes
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers density evolution for lowdensity parity-check (LDPC) and multi-edge type low-density parity-check (MET-LDPC) codes over the binary input additive white Gaussian noise channel. We first analyze three singleparameter Gaussian approximations for density evolution and discuss their accuracy under several conditions, namely at low rates, with punctured and degree-one variable nodes. We observe that the assumption of symmetric Gaussian distribution for the density-evolution messages is not accurate in the early decoding iterations, particularly at low rates and with punctured variable nodes. Thus single-parameter Gaussian approximation methods produce very poor results in these cases. Based on these observations, we then introduce a new density evolution approximation algorithm for LDPC and MET-LDPC codes. Our method is a combination of full density evolution and a single-parameter Gaussian approximation, where we assume a symmetric Gaussian distribution only after density-evolution messages closely follow a symmetric Gaussian distribution. Our method significantly improves the accuracy of the code threshold estimation. Additionally, the proposed method significantly reduces the computational time of evaluating the code threshold compared to full density evolution thereby making it more suitable for code design.
A Process Model for Crowdsourcing: Insights from the Literature on Implementation
Venue: arXiv cs.CY 2016
Year: 2016

The purpose of the current study is to systematically review the crowdsourcing literature, extract the activities which have been cited, and synthesise these activities into a general process model. For this to happen, we reviewed the related literature on crowdsourcing methods as well as relevant case studies and extracted the activities which they referred to as part of crowdsourcing projects. The systematic review of the related literature and an in-depth analysis of the steps in those papers were followed by a synthesis of the extracted activities resulting in an eleven-phase process model. This process model covers all of the activities suggested by the literature. This paper then briefly discusses activities in each phase and concludes with a number of implications for both academics and practitioners.
The Case for Dynamic Key Distribution for PKI-Based VANETs
Venue: arXiv cs.NI 2016
Year: 2016

Vehicular Ad hoc Networks (VANETs) are becoming a reality where secure communication is a prerequisite. Public key infrastructure (PKI) can be used to secure VANETs where an onboard tamper proof device (TPD) stores a number of encryption keys which are renewed upon visiting a certificate authority (CA). We previously proposed a dynamic key distribution protocol for PKI-based VANETs [1] to reduce the role of the TPD. A vehicle dynamically requests a key from its nearest road side unit. This request is propagated through network infrastructure to reach a CA cloud and a key is securely returned. A proposed key revocation mechanism reduced the number of messages needed for revocation through Certificate Revocation List (CRL) distribution. In this paper, performance evaluation and security of the proposed dynamic key distribution is investigated analytically and through network simulation. Furthermore, extensive analysis is performed to demonstrate how the proposed protocol can dynamically support efficient and cost-reduced key distribution. Analysis and performance evaluation results clearly make the case for dynamic key distribution for PKI-based VANETS.
Orthogonal Basis Spreading Sequence for Optimal CDMA
Venue: arXiv cs.IT 2016
Year: 2016

Recently, new spreading sequences have been proposed to increase the capacity of users. In particular, the Weyl spreading sequences have the larger capacity of users than the Gold codes. This paper shows that the Weyl spreading sequences appear in a bit recovering model and they are orthogonal basis vectors. This result shows the reason why they have the large capacity and that any spreading sequence is expressed as the sum of the Weyl spreading sequences.
Geometry Aware Mappings for High Dimensional Sparse Factors
Venue: arXiv cs.LG 2016
Year: 2016

While matrix factorisation models are ubiquitous in large scale recommendation and search, real time application of such models requires inner product computations over an intractably large set of item factors. In this manuscript we present a novel framework that uses the inverted index representation to exploit structural properties of sparse vectors to significantly reduce the run time computational cost of factorisation models. We develop techniques that use geometry aware permutation maps on a tessellated unit sphere to obtain high dimensional sparse embeddings for latent factors with sparsity patterns related to angular closeness of the original latent factors. We also design several efficient and deterministic realisations within this framework and demonstrate with experiments that our techniques lead to faster run time operation with minimal loss of accuracy.
An Alternative Matting Laplacian
Venue: arXiv cs.CV 2016
Year: 2016

Cutting out and object and estimate its transparency mask is a key task in many applications. We take on the work on closed-form matting by Levin et al., that is used at the core of many matting techniques, and propose an alternative formulation that offers more flexible controls over the matting priors. We also show that this new approach is efficient at upscaling transparency maps from coarse estimates.
Log-linear Combinations of Monolingual and Bilingual Neural Machine Translation Models for Automatic Post-Editing
Venue: arXiv cs.CL 2016
Year: 2016

This paper describes the submission of the AMU (Adam Mickiewicz University) team to the Automatic Post-Editing (APE) task of WMT 2016. We explore the application of neural translation models to the APE problem and achieve good results by treating different models as components in a log-linear model, allowing for multiple inputs (the MT-output and the source) that are decoded to the same target language (post-edited translations). A simple string-matching penalty integrated within the log-linear model is used to control for higher faithfulness with regard to the raw machine translation output. To overcome the problem of too little training data, we generate large amounts of artificial data. Our submission improves over the uncorrected baseline on the unseen test set by -3.2\% TER and +5.5\% BLEU and outperforms any other system submitted to the shared-task by a large margin.
Achievable information rates of ambient backscatter communications
Venue: arXiv cs.IT 2016
Year: 2016

Ambient backscatter is an intriguing wireless communication paradigm that allows small devices to compute and communicate by using only the power they harvest from radio-frequency (RF) signals in the air. Ambient backscattering devices reflect existing RF signals emitted by legacy communications systems, such as digital TV broadcasting, cellular or Wi-Fi ones, which would be otherwise treated as harmful sources of interference. This paper deals with the ultimate performance limits of ambient backscatter systems in broadband fading environments, by considering different amounts of network state information at the receivers. After introducing a detailed signal model of the relevant communication links, we study the influence of physical parameters on the capacity of both legacy and backscatter systems. We find that, under reasonable operative conditions, a legacy system employing multicarrier modulation can turn the RF interference arising from the backscatter process into a form of multipath diversity that can be suitably exploited to noticeably increase its performance. Moreover, we show that, even when employing simple single-carrier modulation techniques, the backscatter system can achieve significant data rates over relatively short distances, especially when the intended recipient of the backscatter signal is co-located with the legacy transmitter, i.e., they are on the same machine.
Reducing the Model Order of Deep Neural Networks Using Information Theory
Venue: arXiv cs.LG 2016
Year: 2016

Deep neural networks are typically represented by a much larger number of parameters than shallow models, making them prohibitive for small footprint devices. Recent research shows that there is considerable redundancy in the parameter space of deep neural networks. In this paper, we propose a method to compress deep neural networks by using the Fisher Information metric, which we estimate through a stochastic optimization method that keeps track of second-order information in the network. We first remove unimportant parameters and then use non-uniform fixed point quantization to assign more bits to parameters with higher Fisher Information estimates. We evaluate our method on a classification task with a convolutional neural network trained on the MNIST data set. Experimental results show that our method outperforms existing methods for both network pruning and quantization.
Well-Posed Models of Memristive Devices
Venue: arXiv cs.ET 2016
Year: 2016

Existing compact models for memristive devices (including RRAM and CBRAM) all suffer from issues related to mathematical ill-posedness and/or improper implementation. This limits their value for simulation and design and in some cases, results in qualitatively unphysical predictions. We identify the causes of ill-posedness in these models. We then show how memristive devices in general can be modelled using only continuous/smooth primitives in such a way that they always respect physical bounds for filament length and also feature well-defined and correct DC behaviour. We show how to express these models properly in languages like Verilog-A and ModSpec (MATLAB). We apply these methods to correct previously published RRAM and memristor models and make them well posed. The result is a collection of memristor models that may be dubbed "simulation-ready", i.e., that feature the right physical characteristics and are suitable for robust and consistent simulation in DC, AC, transient, etc., analyses. We provide implementations of these models in both ModSpec/MATLAB and Verilog-A.
Cloud-Based Topological Interference Management: A Case with No Cooperative Transmission Gain
Venue: arXiv cs.IT 2016
Year: 2016

We study the problem of managing interference in linear networks, with backhaul constraints that admit centralized allocation of messages to transmitters through the cloud. Our setting is that of a generic channel, where no channel state information is available at the transmitters. Knowing only the network topology, we characterize the optimal decisions for assigning messages to transmitters, given that each receiver is interested in one message that can be available at N transmitters. We show that using linear cooperation schemes, the per user degrees of freedom does not increase as we increase N beyond unity. Hence, we conclude for the considered problem that linear cooperative transmission does not increase the degrees of freedom.
On the Outage Performance of Non-Orthogonal Multiple Access with One-Bit Feedback
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, the outage performance of downlink non-orthogonal multiple access (NOMA) is investigated for the case where each user feeds back only one bit of its channel state information (CSI) to the base station. Conventionally, opportunistic one-bit feedback has been used in fading broadcast channels to select only one user for transmission. In contrast, the considered NOMA scheme adopts superposition coding to serve all users simultaneously in order to improve user fairness. A closed-form expression for the common outage probability (COP) is derived, along with the optimal diversity gains under two types of power constraints. Particularly, it is demonstrated that the diversity gain under a long-term power constraint is twice as large as that under a short-term power constraint. Furthermore, we study dynamic power allocation optimization for minimizing the COP, based on one-bit CSI feedback. This problem is challenging since the objective function is non-convex; however, under the short-term power constraint, we demonstrate that the original problem can be transformed into a set of convex problems. Under the long-term power constraint, an asymptotically optimal solution is obtained for high signal-to-noise ratio.
Semantics of Higher-Order Quantum Computation via Geometry of Interaction
Venue: arXiv cs.LO 2016
Year: 2016

While much of the current study on quantum computation employs low-level formalisms such as quantum circuits, several high-level languages/calculi have been recently proposed aiming at structured quantum programming. The current work contributes to the semantical study of such languages by providing interaction-based semantics of a functional quantum programming language; the latter is, much like Selinger and Valiron's, based on linear lambda calculus and equipped with features like the ! modality and recursion. The proposed denotational model is the first one that supports the full features of a quantum functional programming language; we prove adequacy of our semantics. The construction of our model is by a series of existing techniques taken from the semantics of classical computation as well as from process theory. The most notable among them is Girard's Geometry of Interaction (GoI), categorically formulated by Abramsky, Haghverdi and Scott. The mathematical genericity of these techniques---largely due to their categorical formulation---is exploited for our move from classical to quantum.
Lossless Compression in HEVC with Integer-to-Integer Transforms
Venue: arXiv cs.MM 2016
Year: 2016

Many approaches have been proposed to support lossless coding within video coding standards that are primarily designed for lossy coding. The simplest approach is to just skip transform and quantization and directly entropy code the prediction residual, which is used in HEVC version 1. However, this simple approach is inefficient for compression. More efficient approaches include processing the residual with DPCM prior to entropy coding. This paper explores an alternative approach based on processing the residual with integer-to-integer (i2i) transforms. I2i transforms map integers to integers, however, unlike the integer transforms used in HEVC for lossy coding, they do not increase the dynamic range at the output and can be used in lossless coding. Experiments with the HEVC reference software show competitive results.
Automatic Classification of Irregularly Sampled Time Series with Unequal Lengths: A Case Study on Estimated Glomerular Filtration Rate
Venue: arXiv cs.LG 2016
Year: 2016

A patient's estimated glomerular filtration rate (eGFR) can provide important information about disease progression and kidney function. Traditionally, an eGFR time series is interpreted by a human expert labelling it as stable or unstable. While this approach works for individual patients, the time consuming nature of it precludes the quick evaluation of risk in large numbers of patients. However, automating this process poses significant challenges as eGFR measurements are usually recorded at irregular intervals and the series of measurements differs in length between patients. Here we present a two-tier system to automatically classify an eGFR trend. First, we model the time series using Gaussian process regression (GPR) to fill in `gaps' by resampling a fixed size vector of fifty time-dependent observations. Second, we classify the resampled eGFR time series using a K-NN/SVM classifier, and evaluate its performance via 5-fold cross validation. Using this approach we achieved an F-score of 0.90, compared to 0.96 for 5 human experts when scored amongst themselves.
Automatic Detection and Categorization of Election-Related Tweets
Venue: arXiv cs.CL 2016
Year: 2016

With the rise in popularity of public social media and micro-blogging services, most notably Twitter, the people have found a venue to hear and be heard by their peers without an intermediary. As a consequence, and aided by the public nature of Twitter, political scientists now potentially have the means to analyse and understand the narratives that organically form, spread and decline among the public in a political campaign. However, the volume and diversity of the conversation on Twitter, combined with its noisy and idiosyncratic nature, make this a hard task. Thus, advanced data mining and language processing techniques are required to process and analyse the data. In this paper, we present and evaluate a technical framework, based on recent advances in deep neural networks, for identifying and analysing election-related conversation on Twitter on a continuous, longitudinal basis. Our models can detect election-related tweets with an F-score of 0.92 and can categorize these tweets into 22 topics with an F-score of 0.90.
Early Stopping for Interleaver Recovering of Turbo Codes
Venue: arXiv cs.IT 2016
Year: 2016

Parameter recovering of channel codes is important in applications such as cognitive radio. The main task for that of a turbo code is to recover the interleaver. The existing optimal algorithm recovers interleaver parameters incrementally one by one. This algorithm continues till the end even if it has failed in the halfway. And there would be lots of wasted computation, as well as incorrectly recovered parameters that will badly deteriorate turbo decoding performance. To address such drawbacks, this paper proposes an early stopping method for the algorithm. Thresholds needed for the method are set through theoretical analysis. Simulations show that the proposed method is able to stop the algorithm in time after it has failed, while no significant degradation in the correct recovering probability is observed.
Parallel Evaluation of Multi-Semi-Joins
Venue: arXiv cs.DB 2016
Year: 2016

While services such as Amazon AWS make computing power abundantly available, adding more computing nodes can incur high costs in, for instance, pay-as-you-go plans while not always significantly improving the net running time (aka wall-clock time) of queries. In this work, we provide algorithms for parallel evaluation of SGF queries in MapReduce that optimize total time, while retaining low net time. Not only can SGF queries specify all semi-join reducers, but also more expressive queries involving disjunction and negation. Since SGF queries can be seen as Boolean combinations of (potentially nested) semi-joins, we introduce a novel multi-semi-join (MSJ) MapReduce operator that enables the evaluation of a set of semi-joins in one job. We use this operator to obtain parallel query plans for SGF queries that outvalue sequential plans w.r.t. net time and provide additional optimizations aimed at minimizing total time without severely affecting net time. Even though the latter optimizations are NP-hard, we present effective greedy algorithms. Our experiments, conducted using our own implementation Gumbo on top of Hadoop, confirm the usefulness of parallel query plans, and the effectiveness and scalability of our optimizations, all with a significant improvement over Pig and Hive.
On the boosting ability of top-down decision tree learning algorithm for multiclass classification
Venue: arXiv cs.LG 2016
Year: 2016

We analyze the performance of the top-down multiclass classification algorithm for decision tree learning called LOMtree, recently proposed in the literature Choromanska and Langford (2014) for solving efficiently classification problems with very large number of classes. The algorithm online optimizes the objective function which simultaneously controls the depth of the tree and its statistical accuracy. We prove important properties of this objective and explore its connection to three well-known entropy-based decision tree objectives, i.e. Shannon entropy, Gini-entropy and its modified version, for which instead online optimization schemes were not yet developed. We show, via boosting-type guarantees, that maximizing the considered objective leads also to the reduction of all of these entropy-based objectives. The bounds we obtain critically depend on the strong-concavity properties of the entropy-based criteria, where the mildest dependence on the number of classes (only logarithmic) corresponds to the Shannon entropy.
An Energy-Aware Programming Approach for Mobile Application Development Guided by a Fine-Grained Energy Model
Venue: arXiv cs.SE 2016
Year: 2016

Energy efficiency has a significant influence on user experience of battery-driven devices such as smartphones and tablets. It is shown that software optimization plays an important role in reducing energy consumption of system. However, in mobile devices, the conventional nature of compiler considers not only energy-efficiency but also limited memory usage and real-time response to user inputs, which largely limits the compiler's positive impact on energy-saving. As a result, the code optimization relies more on developers. In this paper, we propose an energy-aware programming approach, which is guided by an operation-based source-code-level energy model. And this approach is placed at the end of software engineering life cycle to avoid distracting developers from guaranteeing the correctness of system. The experimental result shows that our approach is able to save from 6.4% to 50.2% of the overall energy consumption depending on different scenarios.
Yelp Dataset Challenge: Review Rating Prediction
Venue: arXiv cs.CL 2016
Year: 2016

Review websites, such as TripAdvisor and Yelp, allow users to post online reviews for various businesses, products and services, and have been recently shown to have a significant influence on consumer shopping behaviour. An online review typically consists of free-form text and a star rating out of 5. The problem of predicting a user's star rating for a product, given the user's text review for that product, is called Review Rating Prediction and has lately become a popular, albeit hard, problem in machine learning. In this paper, we treat Review Rating Prediction as a multi-class classification problem, and build sixteen different prediction models by combining four feature extraction methods, (i) unigrams, (ii) bigrams, (iii) trigrams and (iv) Latent Semantic Indexing, with four machine learning algorithms, (i) logistic regression, (ii) Naive Bayes classification, (iii) perceptrons, and (iv) linear Support Vector Classification. We analyse the performance of each of these sixteen models to come up with the best model for predicting the ratings from reviews. We use the dataset provided by Yelp for training and testing the models.