OpenRaiser/Intern-Atlas huggingface dataset:
Scalable Matrix-valued Kernel Learning for High-dimensional Nonlinear Multivariate Regression and Granger Causality
Venue: arXiv cs.LG 2014
Year: 2014

We propose a general matrix-valued multiple kernel learning framework for high-dimensional nonlinear multivariate regression problems. This framework allows a broad class of mixed norm regularizers, including those that induce sparsity, to be imposed on a dictionary of vector-valued Reproducing Kernel Hilbert Spaces. We develop a highly scalable and eigendecomposition-free algorithm that orchestrates two inexact solvers for simultaneously learning both the input and output components of separable matrix-valued kernels. As a key application enabled by our framework, we show how high-dimensional causal inference tasks can be naturally cast as sparse function estimation problems, leading to novel nonlinear extensions of a class of Graphical Granger Causality techniques. Our algorithmic developments and extensive empirical studies are complemented by theoretical analyses in terms of Rademacher generalization bounds.
A Critical Review of "Automatic Patch Generation Learned from Human-Written Patches": Essay on the Problem Statement and the Evaluation of Automatic Software Repair
Venue: arXiv cs.SE 2014
Year: 2014

At ICSE'2013, there was the first session ever dedicated to automatic program repair. In this session, Kim et al. presented PAR, a novel template-based approach for fixing Java bugs. We strongly disagree with key points of this paper. Our critical review has two goals. First, we aim at explaining why we disagree with Kim and colleagues and why the reasons behind this disagreement are important for research on automatic software repair in general. Second, we aim at contributing to the field with a clarification of the essential ideas behind automatic software repair. In particular we discuss the main evaluation criteria of automatic software repair: understandability, correctness and completeness. We show that depending on how one sets up the repair scenario, the evaluation goals may be contradictory. Eventually, we discuss the nature of fix acceptability and its relation to the notion of software correctness.
Generating k-independent variables in constant time
Venue: arXiv cs.DS 2014
Year: 2014

The generation of pseudorandom elements over finite fields is fundamental to the time, space and randomness complexity of randomized algorithms and data structures. We consider the problem of generating $k$-independent random values over a finite field $\mathbb{F}$ in a word RAM model equipped with constant time addition and multiplication in $\mathbb{F}$, and present the first nontrivial construction of a generator that outputs each value in constant time, not dependent on $k$. Our generator has period length $|\mathbb{F}|\,\mbox{poly} \log k$ and uses $k\,\mbox{poly}(\log k) \log |\mathbb{F}|$ bits of space, which is optimal up to a $\mbox{poly} \log k$ factor. We are able to bypass Siegel's lower bound on the time-space tradeoff for $k$-independent functions by a restriction to sequential evaluation.
R-UCB: a Contextual Bandit Algorithm for Risk-Aware Recommender Systems
Venue: arXiv cs.IR 2014
Year: 2014

Mobile Context-Aware Recommender Systems can be naturally modelled as an exploration/exploitation trade-off (exr/exp) problem, where the system has to choose between maximizing its expected rewards dealing with its current knowledge (exploitation) and learning more about the unknown user's preferences to improve its knowledge (exploration). This problem has been addressed by the reinforcement learning community but they do not consider the risk level of the current user's situation, where it may be dangerous to recommend items the user may not desire in her current situation if the risk level is high. We introduce in this paper an algorithm named R-UCB that considers the risk level of the user's situation to adaptively balance between exr and exp. The detailed analysis of the experimental results reveals several important discoveries in the exr/exp behaviour.
Genetic Programming for Smart Phone Personalisation
Venue: arXiv cs.NE 2014
Year: 2014

Personalisation in smart phones requires adaptability to dynamic context based on user mobility, application usage and sensor inputs. Current personalisation approaches, which rely on static logic that is developed a priori, do not provide sufficient adaptability to dynamic and unexpected context. This paper proposes genetic programming (GP), which can evolve program logic in realtime, as an online learning method to deal with the highly dynamic context in smart phone personalisation. We introduce the concept of collaborative smart phone personalisation through the GP Island Model, in order to exploit shared context among co-located phone users and reduce convergence time. We implement these concepts on real smartphones to demonstrate the capability of personalisation through GP and to explore the benefits of the Island Model. Our empirical evaluations on two example applications confirm that the Island Model can reduce convergence time by up to two-thirds over standalone GP personalisation.
Source-Channel Coding under Energy, Delay and Buffer Constraints
Venue: arXiv cs.IT 2014
Year: 2014

Source-channel coding for an energy limited wireless sensor node is investigated. The sensor node observes independent Gaussian source samples with variances changing over time slots and transmits to a destination over a flat fading channel. The fading is constant during each time slot. The compressed samples are stored in a finite size data buffer and need to be delivered in at most $d$ time slots. The objective is to design optimal transmission policies, namely, optimal power and distortion allocation, over the time slots such that the average distortion at destination is minimized. In particular, optimal transmission policies with various energy constraints are studied. First, a battery operated system in which sensor node has a finite amount of energy at the beginning of transmission is investigated. Then, the impact of energy harvesting, energy cost of processing and sampling are considered. For each energy constraint, a convex optimization problem is formulated, and the properties of optimal transmission policies are identified. For the strict delay case, $d=1$, $2D$ waterfilling interpretation is provided. Numerical results are presented to illustrate the structure of the optimal transmission policy, to analyze the effect of delay constraints, data buffer size, energy harvesting, processing and sampling costs.
A Statistical Modelling and Analysis of Residential Electric Vehicles' Charging Demand in Smart Grids
Venue: arXiv cs.CE 2014
Year: 2014

Electric vehicles (EVs) add significant load on the power grid as they become widespread. The characteristics of this extra load follow the patterns of people's driving behaviours. In particular, random parameters such as arrival time and charging time of the vehicles determine their expected charging demand profile from the power grid. In this paper, we first present a model for uncoordinated charging power demand of EVs based on a stochastic process and accordingly we characterize an EV's expected daily power demand profile. Next, we illustrate it for different charging time distributions through simulations. This gives us useful insights into the long-term planning for upgrading power systems' infrastructure to accommodate EVs. Then, we incorporate departure time as another random variable into this modelling and introduce an autonomous demand response (DR) technique to manage the EVs' charging demand. Our results show that, it is possible to accommodate a large number of EVs and achieve the same peak-to-average ratio (PAR) in daily aggregated power consumption of the grid as when there is no EV in the system. This peak value can be decreased further significantly when we add vehicle-to-grid (V2G) capability in the system.
Flow-based Influence Graph Visual Summarization
Venue: arXiv cs.SI 2014
Year: 2014

Visually mining a large influence graph is appealing yet challenging. People are amazed by pictures of newscasting graph on Twitter, engaged by hidden citation networks in academics, nevertheless often troubled by the unpleasant readability of the underlying visualization. Existing summarization methods enhance the graph visualization with blocked views, but have adverse effect on the latent influence structure. How can we visually summarize a large graph to maximize influence flows? In particular, how can we illustrate the impact of an individual node through the summarization? Can we maintain the appealing graph metaphor while preserving both the overall influence pattern and fine readability? To answer these questions, we first formally define the influence graph summarization problem. Second, we propose an end-to-end framework to solve the new problem. Our method can not only highlight the flow-based influence patterns in the visual summarization, but also inherently support rich graph attributes. Last, we present a theoretic analysis and report our experiment results. Both evidences demonstrate that our framework can effectively approximate the proposed influence graph summarization objective while outperforming previous methods in a typical scenario of visually mining academic citation networks.
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
Venue: arXiv cs.DM 2014
Year: 2014

The celebrated Cheeger's Inequality \cite{am85,a86} establishes a bound on the expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on studying the eigenvalues and eigenvectors of the adjacency matrix (and other related matrices) of graphs. It has remained open to define a suitable spectral model for hypergraphs whose spectra can be used to estimate various combinatorial properties of the hypergraph. In this paper we introduce a new hypergraph Laplacian operator (generalizing the Laplacian matrix of graphs)and study its spectra. We prove a Cheeger-type inequality for hypergraphs, relating the second smallest eigenvalue of this operator to the expansion of the hypergraph. We bound other hypergraph expansion parameters via higher eigenvalues of this operator. We give bounds on the diameter of the hypergraph as a function of the second smallest eigenvalue of the Laplacian operator. The Markov process underlying the Laplacian operator can be viewed as a dispersion process on the vertices of the hypergraph that might be of independent interest. We bound the {\em Mixing-time} of this process as a function of the second smallest eigenvalue of the Laplacian operator. All these results are generalizations of the corresponding results for graphs. We show that there can be no linear operator for hypergraphs whose spectra captures hypergraph expansion in a Cheeger-like manner. For any $k$, we give a polynomial time algorithm to compute an approximation to the $k^{th}$ smallest eigenvalue of the operator. We show that this approximation factor is optimal under the SSE hypothesis (introduced by \cite{rs10}) for constant values of $k$. Finally, using the factor preserving reduction from vertex expansion in graphs to hypergraph expansion, we show that all our results for hypergraphs extend to vertex expansion in graphs.
Optimal Control for LQG Systems on Graphs---Part I: Structural Results
Venue: arXiv cs.SY 2014
Year: 2014

In this two-part paper, we identify a broad class of decentralized output-feedback LQG systems for which the optimal control strategies have a simple intuitive estimation structure and can be computed efficiently. Roughly, we consider the class of systems for which the coupling of dynamics among subsystems and the inter-controller communication is characterized by the same directed graph. Furthermore, this graph is assumed to be a multitree, that is, its transitive reduction can have at most one directed path connecting each pair of nodes. In this first part, we derive sufficient statistics that may be used to aggregate each controller's growing available information. Each controller must estimate the states of the subsystems that it affects (its descendants) as well as the subsystems that it observes (its ancestors). The optimal control action for a controller is a linear function of the estimate it computes as well as the estimates computed by all of its ancestors. Moreover, these state estimates may be updated recursively, much like a Kalman filter.
LT Code Design for Inactivation Decoding
Venue: arXiv cs.IT 2014
Year: 2014

We present a simple model of inactivation decoding for LT codes which can be used to estimate the decoding complexity as a function of the LT code degree distribution. The model is shown to be accurate in variety of settings of practical importance. The proposed method allows to perform a numerical optimization on the degree distribution of a LT code aiming at minimizing the number of inactivations required for decoding.
Integration Testing of Heterotic Systems
Venue: arXiv cs.ET 2014
Year: 2014

Computational theory and practice generally focus on single-paradigm systems, but relatively little is known about how best to combine components based on radically different approaches (e.g., silicon chips and wetware) into a single coherent system. In particular, while testing strategies for single-technology components are generally well developed, it is unclear at present how to perform integration testing on heterotic systems: can we develop a test-set generation strategy for checking whether specified behaviours emerge (and unwanted behaviours do not) when components based on radically different technologies are combined within a single system? In this paper, we describe an approach to modelling multi-technology heterotic systems using a general-purpose formal specification strategy based on Eilenberg's X-machine model of computation. We show how this approach can be used to represent disparate technologies within a single framework, and propose a strategy for using these formal models for automatic heterotic test-set generation. We illustrate our approach by showing how to derive a test set for a heterotic system combining an X-machine-based device with a cell-based P system (membrane system).
A Noble Methodology for Users Work Process Driven Software Requirements for Smart Handheld Devices
Venue: arXiv cs.SE 2014
Year: 2014

Requirement engineering is a key ingredient for software development to be effective. Apart from the traditional software requirement which is not much appropriate for new emerging software such as smart handheld device based software. In many perspectives of requirement engineering, traditional and new emerging software are not similar. Whereas requirement engineering of traditional software needs more research, it is obvious that new emerging software needs methodically and in-depth research for improved productivity, quality, risk management and validity. In particular, the result of this paper shows that how effective requirement engineering can improve in project negotiation, project planning, managing feature creep, testing, defect, rework and product quality. This paper also shows a new methodology which is focused on users work process applicable for eliciting the requirement of traditional software and any new type software of smart handheld device such as iPad. As an example, the paper shows how the methodology will be applied as a software requirement of iPad-based software for play-group students.
Spectral Unmixing of Hyperspectral Imagery using Multilayer NMF
Venue: arXiv cs.CV 2014
Year: 2014

Hyperspectral images contain mixed pixels due to low spatial resolution of hyperspectral sensors. Spectral unmixing problem refers to decomposing mixed pixels into a set of endmembers and abundance fractions. Due to nonnegativity constraint on abundance fractions, nonnegative matrix factorization (NMF) methods have been widely used for solving spectral unmixing problem. In this letter we proposed using multilayer NMF (MLNMF) for the purpose of hyperspectral unmixing. In this approach, spectral signature matrix can be modeled as a product of sparse matrices. In fact MLNMF decomposes the observation matrix iteratively in a number of layers. In each layer, we applied sparseness constraint on spectral signature matrix as well as on abundance fractions matrix. In this way signatures matrix can be sparsely decomposed despite the fact that it is not generally a sparse matrix. The proposed algorithm is applied on synthetic and real datasets. Synthetic data is generated based on endmembers from USGS spectral library. AVIRIS Cuprite dataset has been used as a real dataset for evaluation of proposed method. Results of experiments are quantified based on SAD and AAD measures. Results in comparison with previously proposed methods show that the multilayer approach can unmix data more effectively.
Star-free languages and local divisors
Venue: arXiv cs.FL 2014
Year: 2014

A celebrated result of Schützenberger says that a language is star-free if and only if it is is recognized by a finite aperiodic monoid. We give a new proof for this theorem using local divisors.
Affinity Prediction in Online Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

Link prediction is the problem of inferring whether potential edges between pairs of vertices in a graph will be present or absent in the near future. To perform this task it is usual to use information provided by a number of available and observed vertices/edges. Then, a number of edge scoring methods based on this information can be created. Usually, these methods assess local structures of the observed graph, assuming that closer vertices in the original period of observation will be more likely to form a link in the future. In this paper we explore the combination of local and global features to conduct link prediction in online social networks. The contributions of the paper are twofold: a) We evaluate a number of strategies that combines global and local features tackling the locality assumption of link prediction scoring methods, and b) We only use network topology-based features, avoiding the inclusion of informational or transactional based features that involve heavy computational costs in the methods. We evaluate our proposal using real-world data provided by Skout Inc., an affinity online social network with millions of users around the world. Our results show that our proposal is feasible.
Hashing for Similarity Search: A Survey
Venue: arXiv cs.DS 2014
Year: 2014

Similarity search (nearest neighbor search) is a problem of pursuing the data items whose distances to a query item are the smallest from a large database. Various methods have been developed to address this problem, and recently a lot of efforts have been devoted to approximate search. In this paper, we present a survey on one of the main solutions, hashing, which has been widely studied since the pioneering work locality sensitive hashing. We divide the hashing algorithms two main categories: locality sensitive hashing, which designs hash functions without exploring the data distribution and learning to hash, which learns hash functions according the data distribution, and review them from various aspects, including hash function design and distance measure and search scheme in the hash coding space.
An Improved Approach for Contrast Enhancement of Spinal Cord Images based on Multiscale Retinex Algorithm
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents a new approach for contrast enhancement of spinal cord medical images based on multirate scheme incorporated into multiscale retinex algorithm. The proposed work here uses HSV color space, since HSV color space separates color details from intensity. The enhancement of medical image is achieved by down sampling the original image into five versions, namely, tiny, small, medium, fine, and normal scale. This is due to the fact that the each versions of the image when independently enhanced and reconstructed results in enormous improvement in the visual quality. Further, the contrast stretching and MultiScale Retinex (MSR) techniques are exploited in order to enhance each of the scaled version of the image. Finally, the enhanced image is obtained by combining each of these scales in an efficient way to obtain the composite enhanced image. The efficiency of the proposed algorithm is validated by using a wavelet energy metric in the wavelet domain. Reconstructed image using proposed method highlights the details (edges and tissues), reduces image noise (Gaussian and Speckle) and improves the overall contrast. The proposed algorithm also enhances sharp edges of the tissue surrounding the spinal cord regions which is useful for diagnosis of spinal cord lesions. Elaborated experiments are conducted on several medical images and results presented show that the enhanced medical pictures are of good quality and is found to be better compared with other researcher methods.
Entropy Conserving Binarization Scheme for Video and Image Compression
Venue: arXiv cs.IT 2014
Year: 2014

The paper presents a binarization scheme that converts non-binary data into a set of binary strings. At present, there are many binarization algorithms, but they are optimal for only specific probability distributions of the data source. Overcoming the problem, it is shown in this paper that the presented binarization scheme conserves the entropy of the original data having any probability distribution of $m$-ary source. The major advantages of this scheme are that it conserves entropy without the knowledge of the source and the probability distribution of the source symbols. The scheme has linear complexity in terms of the length of the input data. The binarization scheme can be implemented in Context-based Adaptive Binary Arithmetic Coding (CABAC) for video and image compression. It can also be utilized by various universal data compression algorithms that have high complexity in compressing non-binary data, and by binary data compression algorithms to optimally compress non-binary data.
MEECDA: Multihop Energy Efficient Clustering and Data Aggregation Protocol for HWSN
Venue: arXiv cs.NI 2014
Year: 2014

Wireless sensor network consists of large number of inexpensive tiny sensors which are connected with low power wireless communications. Most of the routing and data dissemination protocols of WSN assume a homogeneous network architecture, in which all sensors have the same capabilities in terms of battery power, communication, sensing, storage, and processing. However the continued advances in miniaturization of processors and low-power communications have enabled the development of a wide variety of nodes. When more than one type of node is integrated into a WSN, it is called heterogeneous. Multihop short distance communication is an important scheme to reduce the energy consumption in a sensor network because nodes are densely deployed in a WSN. In this paper M-EECDA (Multihop Energy Efficient Clustering & Data Aggregation Protocol for Heterogeneous WSN) is proposed and analyzed. The protocol combines the idea of multihop communications and clustering for achieving the best performance in terms of network life and energy consumption. M-EECDA introduces a sleep state and three tier architecture for some cluster heads to save energy of the network. M-EECDA consists of three types of sensor nodes: normal, advance and super. To become cluster head in a round normal nodes use residual energy based scheme. Advance and super nodes further act as relay node to reduce the transmission load of a normal node cluster head when they are not cluster heads in a round.