OpenRaiser/Intern-Atlas huggingface dataset:
Modelling the Evolution of Programming Languages
Venue: arXiv cs.PL 2015
Year: 2015

Programming languages are engineered languages that allow to instruct a machine and share algorithmic information; they have a great influence on the society since they underlie almost every information technology artefact, and they are at the core of the current explosion of software technology. The history of programming languages is marked by innovations, diversifications, lateral transfers and social influences; moreover, it represents an intermediate case study between the evolution of human languages and the evolution of technology. In this paper we study the application of the Darwinian explanation to the programming languages evolution by discussing to what extent the evolutionary mechanisms distinctive of biology can be applied to this area. We show that a number of evolutionary building blocks can be recognised in the realm of computer languages, but we also identify critical issues. Far from being crystal clear, this fine-grained study shows to be a useful tool to assess recent results about programming languages phylogenies. Finally, we show that rich evolutionary patterns, such as co-evolution, macro-evolutionary trends, niche construction and exaptation, can be effectively applied to programming languages and provide for interesting explanatory tools.
Sparsity-aware Possibilistic Clustering Algorithms
Venue: arXiv cs.CV 2015
Year: 2015

In this paper two novel possibilistic clustering algorithms are presented, which utilize the concept of sparsity. The first one, called sparse possibilistic c-means, exploits sparsity and can deal well with closely located clusters that may also be of significantly different densities. The second one, called sparse adaptive possibilistic c-means, is an extension of the first, where now the involved parameters are dynamically adapted. The latter can deal well with even more challenging cases, where, in addition to the above, clusters may be of significantly different variances. More specifically, it provides improved estimates of the cluster representatives, while, in addition, it has the ability to estimate the actual number of clusters, given an overestimate of it. Extensive experimental results on both synthetic and real data sets support the previous statements.
New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem
Venue: arXiv cs.NA 2015
Year: 2015

In this paper, two accelerated divide-and-conquer algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost $O(N^2r)$ {flops} in the worst case, where $N$ is the dimension of the matrix and $r$ is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices which are Cauchy-like matrices and are off-diagonally low-rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by {ADC1}) uses a structured low-rank approximation method and the other ({ADC2}) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off-diagonal rank. Numerous experiments have been done to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than 6x times faster for some large matrices with few deflations.
A lower bound for the dispersion on the torus
Venue: arXiv cs.CC 2015
Year: 2015

We consider the volume of the largest axis-parallel box in the $d$-dimensional torus that contains no point of a given point set $\mathcal{P}_n$ with $n$ elements. We prove that, for all natural numbers $d, n$ and every point set $\mathcal{P}_n$, this volume is bounded from below by $\min\{1,d/n\}$. This implies the same lower bound for the discrepancy on the torus.
Monte Carlo Dynamically Weighted Importance Sampling For Finite Element Model Updating
Venue: arXiv cs.NA 2015
Year: 2015

The Finite Element Method (FEM) is generally unable to accurately predict natural frequencies and mode shapes of structures (eigenvalues and eigenvectors). Engineers develop numerical methods and a variety of techniques to compensate for this misalignment of modal properties, between experimentally measured data and the computed result from the FEM of structures. In this paper we compare two indirect methods of updating namely, the Adaptive Metropolis Hastings and a newly applied algorithm called Monte Carlo Dynamically Weighted Importance Sampling (MCDWIS). The approximation of a posterior predictive distribution is based on Bayesian inference of continuous multivariate Gaussian probability density functions, defining the variability of physical properties affected by forced vibration. The motivation behind applying MCDWIS is in the complexity of computing normalizing constants in higher dimensional or multimodal systems. The MCDWIS accounts for this intractability by analytically computing importance sampling estimates at each time step of the algorithm. In addition, a dynamic weighting step with an Adaptive Pruned Enriched Population Control Scheme (APEPCS) allows for further control over weighted samples and population size. The performance of the MCDWIS simulation is graphically illustrated for all algorithm dependent parameters and show unbiased, stable sample estimates.
SRMR variants for improved blind room acoustics characterization
Venue: arXiv cs.SD 2015
Year: 2015

Reverberation, especially in large rooms, severely degrades speech recognition performance and speech intelligibility. Since direct measurement of room characteristics is usually not possible, blind estimation of reverberation-related metrics such as the reverberation time (RT) and the direct-to-reverberant energy ratio (DRR) can be valuable information to speech recognition and enhancement algorithms operating in enclosed environments. The objective of this work is to evaluate the performance of five variants of blind RT and DRR estimators based on a modulation spectrum representation of reverberant speech with single- and multi-channel speech data. These models are all based on variants of the so-called Speech-to-Reverberation Modulation Energy Ratio (SRMR). We show that these measures outperform a state-of-the-art baseline based on maximum-likelihood estimation of sound decay rates in terms of root-mean square error (RMSE), as well as Pearson correlation. Compared to the baseline, the best proposed measure, called NSRMR_k , achieves a 23% relative improvement in terms of RMSE and allows for relative correlation improvements ranging from 13% to 47% for RT prediction.
Efficient Replication of Queued Tasks for Latency Reduction in Cloud Systems
Venue: arXiv cs.DC 2015
Year: 2015

In cloud computing systems, assigning a job to multiple servers and waiting for the earliest copy to finish is an effective method to combat the variability in response time of individual servers. Although adding redundant replicas always reduces service time, the total computing time spent per job may be higher, thus increasing waiting time in queue. The total time spent per job is also proportional to the cost of computing resources. We analyze how different redundancy strategies, for eg. number of replicas, and the time when they are issued and canceled, affect the latency and computing cost. We get the insight that the log-concavity of the service time distribution is a key factor in determining whether adding redundancy reduces latency and cost. If the service distribution is log-convex, then adding maximum redundancy reduces both latency and cost. And if it is log-concave, then having fewer replicas and canceling the redundant requests early is more effective.
A Survey: Time Travel in Deep Learning Space: An Introduction to Deep Learning Models and How Deep Learning Models Evolved from the Initial Ideas
Venue: arXiv cs.LG 2015
Year: 2015

This report will show the history of deep learning evolves. It will trace back as far as the initial belief of connectionism modelling of brain, and come back to look at its early stage realization: neural networks. With the background of neural network, we will gradually introduce how convolutional neural network, as a representative of deep discriminative models, is developed from neural networks, together with many practical techniques that can help in optimization of neural networks. On the other hand, we will also trace back to see the evolution history of deep generative models, to see how researchers balance the representation power and computation complexity to reach Restricted Boltzmann Machine and eventually reach Deep Belief Nets. Further, we will also look into the development history of modelling time series data with neural networks. We start with Time Delay Neural Networks and move further to currently famous model named Recurrent Neural Network and its extension Long Short Term Memory. We will also briefly look into how to construct deep recurrent neural networks. Finally, we will conclude this report with some interesting open-ended questions of deep neural networks.
MSoS: A Multi-Screen-Oriented Web Page Segmentation Approach
Venue: arXiv cs.HC 2015
Year: 2015

In this paper we describe a multiscreen-oriented approach for segmenting web pages. The segmentation is an automatic and hybrid visual and structural method. It aims at creating coherent blocks which have different functions determined by the multiscreen environment. It is also characterized by a dynamic adaptation to the page content. Experiments are conducted on a set of existing applications that contain multimedia elements, in particular YouTube and video player pages. Results are compared with one seg-mentation method from the literature and with a ground truth manually created. With a 75% precision, the MSoS is a promising method that is capable of producing good segmentation results.
Using Duality in Circuit Complexity
Venue: arXiv cs.CC 2015
Year: 2015

We investigate in a method for proving separation results for abstract classes of languages. A well established method to characterize varieties of regular languages are identities. We use a recently established generalization of these identities to non-regular languages by Gehrke, Grigorieff, and Pin: so called equations, which are capable of describing arbitrary Boolean algebras of languages. While the main concern of their result is the existence of these equations, we investigate in a general method that could allow to find equations for language classes in an inductive manner. Thereto we extend an important tool -- the block product or substitution principle -- known from logic and algebra, to non-regular language classes. Furthermore, we abstract this concept by defining it directly as an operation on (non-regular) language classes. We show that this principle can be used to obtain equations for certain circuit classes, given equations for the gate types. Concretely, we demonstrate the applicability of this method by obtaining a description via equations for all languages recognized by circuit families that contain a constant number of (inner) gates, given a description of the gate types via equations.
A Novel and Efficient Vector Quantization Based CPRI Compression Algorithm
Venue: arXiv cs.IT 2015
Year: 2015

The future wireless network, such as Centralized Radio Access Network (C-RAN), will need to deliver data rate about 100 to 1000 times the current 4G technology. For C-RAN based network architecture, there is a pressing need for tremendous enhancement of the effective data rate of the Common Public Radio Interface (CPRI). Compression of CPRI data is one of the potential enhancements. In this paper, we introduce a vector quantization based compression algorithm for CPRI links, utilizing Lloyd algorithm. Methods to vectorize the I/Q samples and enhanced initialization of Lloyd algorithm for codebook training are investigated for improved performance. Multi-stage vector quantization and unequally protected multi-group quantization are considered to reduce codebook search complexity and codebook size. Simulation results show that our solution can achieve compression of 4 times for uplink and 4.5 times for downlink, within 2% Error Vector Magnitude (EVM) distortion. Remarkably, vector quantization codebook proves to be quite robust against data modulation mismatch, fading, signal-to-noise ratio (SNR) and Doppler spread.
Latency Versus Survivability in Geo-Distributed Data Center Design
Venue: arXiv cs.NI 2015
Year: 2015

A hot topic in data center design is to envision geo-distributed architectures spanning a few sites across wide area networks, allowing more proximity to the end users and higher survivability, defined as the capacity of a system to operate after failures. As a shortcoming, this approach is subject to an increase of latency between servers, caused by their geographic distances. In this paper, we address the trade-off between latency and survivability in geo-distributed data centers, through the formulation of an optimization problem. Simulations considering realistic scenarios show that the latency increase is significant only in the case of very strong survivability requirements, whereas it is negligible for moderate survivability requirements. For instance, the worst-case latency is less than 4~ms when guaranteeing that 80% of the servers are available after a failure, in a network where the latency could be up to 33 ms.
A Community Contribution Framework for Sharing Materials Data with Materials Project
Venue: arXiv cs.SE 2015
Year: 2015

As scientific discovery becomes increasingly data-driven, software platforms are needed to efficiently organize and disseminate data from disparate sources. This is certainly the case in the field of materials science. For example, Materials Project has generated computational data on over 60,000 chemical compounds and has made that data available through a web portal and REST interface. However, such portals must seek to incorporate community submissions to expand the scope of scientific data sharing. In this paper, we describe MPContribs, a computing/software infrastructure to integrate and organize contributions of simulated or measured materials data from users. Our solution supports complex submissions and provides interfaces that allow contributors to share analyses and graphs. A RESTful API exposes mechanisms for book-keeping, retrieval and aggregation of submitted entries, as well as persistent URIs or DOIs that can be used to reference the data in publications. Our approach isolates contributed data from a host project's quality-controlled core data and yet enables analyses across the entire dataset, programmatically or through customized web apps. We expect the developed framework to enhance collaborative determination of material properties and to maximize the impact of each contributor's dataset. In the long-term, MPContribs seeks to make Materials Project an institutional, and thus community-wide, memory for computational and experimental materials science.
A class of optimal ternary cyclic codes and their duals
Venue: arXiv cs.IT 2015
Year: 2015

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. Let $m=2\ell+1$ for an integer $\ell\geq 1$ and $π$ be a generator of $\gf(3^m)^*$. In this paper, a class of cyclic codes $\C_{(u,v)}$ over $\gf(3)$ with two nonzeros $π^{u}$ and $π^{v}$ is studied, where $u=(3^m+1)/2$, and $v=2\cdot 3^{\ell}+1$ is the ternary Welch-type exponent. Based on a result on the non-existence of solutions to certain equation over $\gf(3^m)$, the cyclic code $\C_{(u,v)}$ is shown to have minimal distance four, which is the best minimal distance for any linear code over $\gf(3)$ with length $3^m-1$ and dimension $3^m-1-2m$ according to the Sphere Packing bound. The duals of this class of cyclic codes are also studied.
Comprehensive indicator comparisons intelligible to non-experts: The case of two SNIP versions
Venue: arXiv cs.DL 2015
Year: 2015

A framework is proposed for comparing different types of bibliometric indicators, introducing the notion of an Indicator Comparison Report. It provides a comprehensive overview of the main differences and similarities of indicators. The comparison shows both the strong points and the limitations of each of the indicators at stake, rather than over-promoting one indicator and ignoring the benefits of alternative constructs. It focuses on base notions, assumptions, and application contexts, which makes it more intelligible to non-experts. As an illustration, a comparison report is presented for the original and the modified SNIP (Source Normalized Impact per Paper) indicator of journal citation impact.
Satisfiability of Short Circuit Logic
Venue: arXiv cs.LO 2015
Year: 2015

The logical connectives typically found in programming languages are similar to their mathematical counterparts, yet different due to their short-circuit behaviour -- when evaluating them, the second argument is only evaluated if the first argument is not sufficient to determine the result. Combined with the possibility of side-effects, this creates a different type of logic called Short Circuit Logic. A greater theoretical understanding of this logic can lead to more efficient programming and faster program execution. In this thesis, formula satisfiability in the context of Short Circuit Logic is discussed. A formal definition of evaluation based on valuation algebras is presented, alongside an alternative definition based on valuation paths. The accompanying satisfiability and `path-satisfiability' are then proven to be equivalent, and an implementation of path-satisfiability is given. Although five types of valuation algebras can be discerned, there are only three corresponding types of valuation paths. From this, conclusions are drawn about satisfiability and side-effects; the manner in which side-effects alter truth values is relevant when analysing satisfiability, but the side-effects themselves are not.
Neural Reranking Improves Subjective Quality of Machine Translation: NAIST at WAT2015
Venue: arXiv cs.CL 2015
Year: 2015

This year, the Nara Institute of Science and Technology (NAIST)'s submission to the 2015 Workshop on Asian Translation was based on syntax-based statistical machine translation, with the addition of a reranking component using neural attentional machine translation models. Experiments re-confirmed results from previous work stating that neural MT reranking provides a large gain in objective evaluation measures such as BLEU, and also confirmed for the first time that these results also carry over to manual evaluation. We further perform a detailed analysis of reasons for this increase, finding that the main contributions of the neural models lie in improvement of the grammatical correctness of the output, as opposed to improvements in lexical choice of content words.
Clustering Noisy Signals with Structured Sparsity Using Time-Frequency Representation
Venue: arXiv cs.LG 2015
Year: 2015

We propose a simple and efficient time-series clustering framework particularly suited for low Signal-to-Noise Ratio (SNR), by simultaneous smoothing and dimensionality reduction aimed at preserving clustering information. We extend the sparse K-means algorithm by incorporating structured sparsity, and use it to exploit the multi-scale property of wavelets and group structure in multivariate signals. Finally, we extract features invariant to translation and scaling with the scattering transform, which corresponds to a convolutional network with filters given by a wavelet operator, and use the network's structure in sparse clustering. By promoting sparsity, this transform can yield a low-dimensional representation of signals that gives improved clustering results on several real datasets.
Large Enforced Sparse Non-Negative Matrix Factorization
Venue: arXiv cs.LG 2015
Year: 2015

Non-negative matrix factorization (NMF) is a common method for generating topic models from text data. NMF is widely accepted for producing good results despite its relative simplicity of implementation and ease of computation. One challenge with applying NMF to large datasets is that intermediate matrix products often become dense, stressing the memory and compute elements of a system. In this article, we investigate a simple but powerful modification of a common NMF algorithm that enforces the generation of sparse intermediate and output matrices. This method enables the application of NMF to large datasets through improved memory and compute performance. Further, we demonstrate empirically that this method of enforcing sparsity in the NMF either preserves or improves both the accuracy of the resulting topic model and the convergence rate of the underlying algorithm.
Latent Space Model for Multi-Modal Social Data
Venue: arXiv cs.SI 2015
Year: 2015

With the emergence of social networking services, researchers enjoy the increasing availability of large-scale heterogenous datasets capturing online user interactions and behaviors. Traditional analysis of techno-social systems data has focused mainly on describing either the dynamics of social interactions, or the attributes and behaviors of the users. However, overwhelming empirical evidence suggests that the two dimensions affect one another, and therefore they should be jointly modeled and analyzed in a multi-modal framework. The benefits of such an approach include the ability to build better predictive models, leveraging social network information as well as user behavioral signals. To this purpose, here we propose the Constrained Latent Space Model (CLSM), a generalized framework that combines Mixed Membership Stochastic Blockmodels (MMSB) and Latent Dirichlet Allocation (LDA) incorporating a constraint that forces the latent space to concurrently describe the multiple data modalities. We derive an efficient inference algorithm based on Variational Expectation Maximization that has a computational cost linear in the size of the network, thus making it feasible to analyze massive social datasets. We validate the proposed framework on two problems: prediction of social interactions from user attributes and behaviors, and behavior prediction exploiting network information. We perform experiments with a variety of multi-modal social systems, spanning location-based social networks (Gowalla), social media services (Instagram, Orkut), e-commerce and review sites (Amazon, Ciao), and finally citation networks (Cora). The results indicate significant improvement in prediction accuracy over state of the art methods, and demonstrate the flexibility of the proposed approach for addressing a variety of different learning problems commonly occurring with multi-modal social data.
Optimal Scalar Linear Index Codes for Some Symmetric Multiple Unicast Problems
Venue: arXiv cs.IT 2015
Year: 2015

The capacity of symmetric instance of the multiple unicast index coding problem with neighboring antidotes (side-information) with number of messages equal to the number of receivers was given by Maleki, Cadambe and Jafar. In this paper we consider ten symmetric multiple unicast problems with lesser antidotes than considered by them and explicitly construct scalar linear codes for these problems. These codes are shown to achieve the capacity or equivalently these codes shown to be of optimal length. Also, the constructed codes enable the receivers use small number of transmissions to decode their wanted messages which is important to have the probability of message error reduced in a noisy broadcast channel. Some of the cases considered are shown to be critical index coding problems and these codes help to identify some of the subclasses considered by others to be not critical index coding problems.