OpenRaiser/Intern-Atlas huggingface dataset:
The Rabin index of parity games
Venue: arXiv cs.GT 2013
Year: 2013

We study the descriptive complexity of parity games by taking into account the coloring of their game graphs whilst ignoring their ownership structure. Colored game graphs are identified if they determine the same winning regions and strategies, for all ownership structures of nodes. The Rabin index of a parity game is the minimum of the maximal color taken over all equivalent coloring functions. We show that deciding whether the Rabin index is at least k is in PTIME for k=1 but NP-hard for all fixed k > 1. We present an EXPTIME algorithm that computes the Rabin index by simplifying its input coloring function. When replacing simple cycle with cycle detection in that algorithm, its output over-approximates the Rabin index in polynomial time. Experimental results show that this approximation yields good values in practice.
Probabilistic data flow analysis: a linear equational approach
Venue: arXiv cs.PL 2013
Year: 2013

Speculative optimisation relies on the estimation of the probabilities that certain properties of the control flow are fulfilled. Concrete or estimated branch probabilities can be used for searching and constructing advantageous speculative and bookkeeping transformations. We present a probabilistic extension of the classical equational approach to data-flow analysis that can be used to this purpose. More precisely, we show how the probabilistic information introduced in a control flow graph by branch prediction can be used to extract a system of linear equations from a program and present a method for calculating correct (numerical) solutions.
Supervised Metric Learning with Generalization Guarantees
Venue: arXiv cs.LG 2013
Year: 2013

The crucial importance of metrics in machine learning algorithms has led to an increasing interest in optimizing distance and similarity functions, an area of research known as metric learning. When data consist of feature vectors, a large body of work has focused on learning a Mahalanobis distance. Less work has been devoted to metric learning from structured objects (such as strings or trees), most of it focusing on optimizing a notion of edit distance. We identify two important limitations of current metric learning approaches. First, they allow to improve the performance of local algorithms such as k-nearest neighbors, but metric learning for global algorithms (such as linear classifiers) has not been studied so far. Second, the question of the generalization ability of metric learning methods has been largely ignored. In this thesis, we propose theoretical and algorithmic contributions that address these limitations. Our first contribution is the derivation of a new kernel function built from learned edit probabilities. Our second contribution is a novel framework for learning string and tree edit similarities inspired by the recent theory of (e,g,t)-good similarity functions. Using uniform stability arguments, we establish theoretical guarantees for the learned similarity that give a bound on the generalization error of a linear classifier built from that similarity. In our third contribution, we extend these ideas to metric learning from feature vectors by proposing a bilinear similarity learning method that efficiently optimizes the (e,g,t)-goodness. Generalization guarantees are derived for our approach, highlighting that our method minimizes a tighter bound on the generalization error of the classifier. Our last contribution is a framework for establishing generalization bounds for a large class of existing metric learning algorithms based on a notion of algorithmic robustness.
Mammogram Edge Detection Using Hybrid Soft Computing Methods
Venue: arXiv cs.CV 2013
Year: 2013

Image segmentation is a crucial step in a wide range of method image processing systems. It is useful in visualization of the different objects present in the image. In spite of the several methods available in the literature, image segmentation still a challenging problem in most of image processing applications. The challenge comes from the fuzziness of image objects and the overlapping of the different regions. Detection of edges in an image is a very important step towards understanding image features. There are large numbers of edge detection operators available, each designed to be sensitive to certain types of edges. The Quality of edge detection can be measured from several criteria objectively. Some criteria are proposed in terms of mathematical measurement, some of them are based on application and implementation requirements. Since edges often occur at image locations representing object boundaries, edge detection is extensively used in image segmentation when images are divided into areas corresponding to different objects. This can be used specifically for enhancing the tumor area in mammographic images. Different methods are available for edge detection like Roberts, Sobel, Prewitt, Canny, Log edge operators. In this paper a novel algorithms for edge detection has been proposed for mammographic images. Breast boundary, pectoral region and tumor location can be seen clearly by using this method. For comparison purpose Roberts, Sobel, Prewitt, Canny, Log edge operators are used and their results are displayed. Experimental results demonstrate the effectiveness of the proposed approach.
Extending the ER Model to relational Model novel transformation Algorithm: transforming relationship Types among Subtypes
Venue: arXiv cs.DB 2013
Year: 2013

A novel approach for creating ER conceptual models and an algorithm for transforming them to the relational model has been developed by modifying and extending the existing methods. A part of the new algorithm has previously been presented. This paper presents the rest of the algorithm. One of the objectives of this paper is to use it as a supportive document for ongoing empirical evaluations of the new approach being conducted using the cognitive engagement method and with the participation of different segments of the field as respondents.
Crowd-assisted Search for Price Discrimination in E-Commerce: First results
Venue: arXiv cs.CY 2013
Year: 2013

After years of speculation, price discrimination in e-commerce driven by the personal information that users leave (involuntarily) online, has started attracting the attention of privacy researchers, regulators, and the press. In our previous work we demonstrated instances of products whose prices varied online depending on the location and the characteristics of perspective online buyers. In an effort to scale up our study we have turned to crowd-sourcing. Using a browser extension we have collected the prices obtained by an initial set of 340 test users as they surf the web for products of their interest. This initial dataset has permitted us to identify a set of online stores where price variation is more pronounced. We have focused on this subset, and performed a systematic crawl of their products and logged the prices obtained from different vantage points and browser configurations. By analyzing this dataset we see that there exist several retailers that return prices for the same product that vary by 10%-30% whereas there also exist isolated cases that may vary up to a multiplicative factor, e.g., x2. To the best of our efforts we could not attribute the observed price gaps to currency, shipping, or taxation differences.
Creative Telescoping for Holonomic Functions
Venue: arXiv cs.SC 2013
Year: 2013

The aim of this article is twofold: on the one hand it is intended to serve as a gentle introduction to the topic of creative telescoping, from a practical point of view; for this purpose its application to several problems is exemplified. On the other hand, this chapter has the flavour of a survey article: the developments in this area during the last two decades are sketched and a selection of references is compiled in order to highlight the impact of creative telescoping in numerous contexts.
Benchmarking mixed-mode PETSc performance on high-performance architectures
Venue: arXiv cs.DC 2013
Year: 2013

The trend towards highly parallel multi-processing is ubiquitous in all modern computer architectures, ranging from handheld devices to large-scale HPC systems; yet many applications are struggling to fully utilise the multiple levels of parallelism exposed in modern high-performance platforms. In order to realise the full potential of recent hardware advances, a mixed-mode between shared-memory programming techniques and inter-node message passing can be adopted which provides high-levels of parallelism with minimal overheads. For scientific applications this entails that not only the simulation code itself, but the whole software stack needs to evolve. In this paper, we evaluate the mixed-mode performance of PETSc, a widely used scientific library for the scalable solution of partial differential equations. We describe the addition of OpenMP threaded functionality to the library, focusing on sparse matrix-vector multiplication. We highlight key challenges in achieving good parallel performance, such as explicit communication overlap using task-based parallelism, and show how to further improve performance by explicitly load balancing threads within MPI processes. Using a set of matrices extracted from Fluidity, a CFD application code which uses the library as its linear solver engine, we then benchmark the parallel performance of mixed-mode PETSc across multiple nodes on several modern HPC architectures. We evaluate the parallel scalability on Uniform Memory Access (UMA) systems, such as the Fujitsu PRIMEHPC FX10 and IBM BlueGene/Q, as well as a Non-Uniform Memory Access (NUMA) Cray XE6 platform. A detailed comparison is performed which highlights the characteristics of each particular architecture, before demonstrating efficient strong scalability of sparse matrix-vector multiplication with significant speedups over the pure-MPI mode.
Integrating Datalog and Constraint Solving
Venue: arXiv cs.PL 2013
Year: 2013

LP is a common formalism for the field of databases and CSP, both at the theoretical level and the implementation level in the form of Datalog and CLP. In the past, close correspondences have been made between both fields at the theoretical level. Yet correspondence at the implementation level has been much less explored. In this article we work towards relating them at the implementation level. Concretely, we show how to derive the efficient Leapfrog Triejoin execution algorithm of Datalog from a generic CP execution scheme.
Outage Exponent: A Unified Performance Metric for Parallel Fading Channels
Venue: arXiv cs.IT 2013
Year: 2013

The parallel fading channel, which consists of finite number of subchannels, is very important, because it can be used to formulate many practical communication systems. The outage probability, on the other hand, is widely used to analyze the relationship among the communication efficiency, reliability, SNR, and channel fading. To the best of our knowledge, the previous works only studied the asymptotic outage performance of the parallel fading channel which are only valid for a large number of subchannels or high SNRs. In this paper, a unified performance metric, which we shall refer to as the outage exponent, will be proposed. Our approach is mainly based on the large deviations theory and the Meijer's G-function. It is shown that the proposed outage exponent is not only an accurate estimation of the outage probability for any number of subchannels, any SNR, and any target transmission rate, but also provides an easy way to compute the outage capacity, finite-SNR diversity-multiplexing tradeoff, and SNR gain. The asymptotic performance metrics, such as the delay-limited capacity, ergodic capacity, and diversity-multiplexing tradeoff can be directly obtained by letting the number of subchannels or SNR tends to infinity. Similar to Gallager's error exponent, a reliable function for parallel fading channels, which illustrates a fundamental relationship between the transmission reliability and efficiency, can also be defined from the outage exponent. Therefore, the proposed outage exponent provides a complete and comprehensive performance measure for parallel fading channels.
Small Depth Proof Systems
Venue: arXiv cs.CC 2013
Year: 2013

A proof system for a language L is a function f such that Range(f) is exactly L. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by bounded fanin circuits of constant depth (NC^0), or of O(log log n) depth but with O(1) alternations (polylog AC^0). Each output bit depends on very few input bits; thus such proof systems correspond to a kind of local error-correction on a theorem-proof pair. We identify exactly how much power we need for proof systems to capture all regular languages. We show that all regular language have polylog AC^0 proof systems, and from a previous result (Beyersdorff et al, MFCS 2011, where NC^0 proof systems were first introduced), this is tight. Our technique also shows that MAJ has polylog AC^0 proof system. We explore the question of whether TAUT has NC^0 proof systems. Addressing this question about 2TAUT, and since 2TAUT is closely related to reachability in graphs, we ask the same question about Reachability. We show that both Undirected Reachability and Directed UnReachability have NC^0 proof systems, but Directed Reachability is still open. In the context of how much power is needed for proof systems for languages in NP, we observe that proof systems for a good fraction of languages in NP do not need the full power of AC^0; they have SAC^0 or coSAC^0 proof systems.
The Yao Graph $Y_5$ is a Spanner
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we prove that $Y_5$, the Yao graph with five cones, is a spanner with stretch factor $ρ= 2+\sqrt{3} \approx 3.74$. Since $Y_5$ is the only Yao graph whose status of being a spanner or not was open, this completes the picture of the Yao graphs that are spanners: a Yao graph $Y_k$ is a spanner if and only if $k \geq 4$. We complement the above result with a lower bound of 2.87 on the stretch factor of $Y_5$. We also show that $YY_5$, the Yao-Yao graph with five cones, is not a spanner.
Low-rank Approximations for Computing Observation Impact in 4D-Var Data Assimilation
Venue: arXiv cs.CE 2013
Year: 2013

We present an efficient computational framework to quantify the impact of individual observations in four dimensional variational data assimilation. The proposed methodology uses first and second order adjoint sensitivity analysis, together with matrix-free algorithms to obtain low-rank approximations of ob- servation impact matrix. We illustrate the application of this methodology to important applications such as data pruning and the identification of faulty sensors for a two dimensional shallow water test system.
Large-scale Multi-label Learning with Missing Labels
Venue: arXiv cs.LG 2013
Year: 2013

The multi-label classification problem has generated significant interest in recent years. However, existing approaches do not adequately address two key challenges: (a) the ability to tackle problems with a large number (say millions) of labels, and (b) the ability to handle data with missing labels. In this paper, we directly address both these problems by studying the multi-label problem in a generic empirical risk minimization (ERM) framework. Our framework, despite being simple, is surprisingly able to encompass several recent label-compression based methods which can be derived as special cases of our method. To optimize the ERM problem, we develop techniques that exploit the structure of specific loss functions - such as the squared loss function - to offer efficient algorithms. We further show that our learning framework admits formal excess risk bounds even in the presence of missing labels. Our risk bounds are tight and demonstrate better generalization performance for low-rank promoting trace-norm regularization when compared to (rank insensitive) Frobenius norm regularization. Finally, we present extensive empirical results on a variety of benchmark datasets and show that our methods perform significantly better than existing label compression based methods and can scale up to very large datasets such as the Wikipedia dataset.
Automated Small-Cell Deployment for Heterogeneous Cellular Networks
Venue: arXiv cs.NI 2013
Year: 2013

Optimizing the cellular network's cell locations is one of the most fundamental problems of network design. The general objective is to provide the desired Quality-of-Service (QoS) with the minimum system cost. In order to meet a growing appetite for mobile data services, heterogeneous networks have been proposed as a cost- and energy-efficient method of improving local spectral efficiency. Whilst unarticulated cell deployments can lead to localized improvements, there is a significant risk posed to network-wide performance due to the additional interference. The first part of the paper focuses on state-of-the-art modelling and radio-planning methods based on stochastic geometry and Monte-Carlo simulations, and the emerging automatic deployment prediction technique for low-power nodes (LPNs) in heterogeneous networks. The technique advises a LPN where it should be deployed, given certain knowledge of the network. The second part of the paper focuses on algorithms that utilize interference and physical environment knowledge to assist LPN deployment. The proposed techniques can not only improve network performance, but also reduce radio-planning complexity, capital expenditure, and energy consumption of the cellular network. The theoretical work is supported by numerical results from system-level simulations that employ real cellular network data and physical environments.
Unified Performance Analysis of Orthogonal Transmit Beamforming Methods with User Selection
Venue: arXiv cs.IT 2013
Year: 2013

Simultaneous multiuser beamforming in multiantenna downlink channels can entail dirty paper (DP) precoding (optimal and high complexity) or linear precoding (suboptimal and low complexity) approaches. The system performance is typically characterized by the sum capacity with homogenous users with perfect channel state information at the transmitter. The sum capacity performance analysis requires the exact probability distributions of the user signal-to-noise ratios (SNRs) or signal-to-interference plus noise ratios (SINRs). The standard techniques from order statistics can be sufficient to obtain the probability distributions of SNRs for DP precoding due to the removal of known interference at the transmitter. Derivation of such probability distributions for linear precoding techniques on the other hand is much more challenging. For example, orthogonal beamforming techniques do not completely cancel the interference at the user locations, thereby requiring the analysis with SINRs. In this paper, we derive the joint probability distributions of the user SINRs for two orthogonal beamforming methods combined with user scheduling: adaptive orthogonal beamforming and orthogonal linear beamforming. We obtain compact and unified solutions for the joint probability distributions of the scheduled users' SINRs. Our analytical results can be applied for similar algorithms and are verified by computer simulations.
Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography
Venue: arXiv cs.CV 2013
Year: 2013

The development of energy selective, photon counting X-ray detectors allows for a wide range of new possibilities in the area of computed tomographic image formation. Under the assumption of perfect energy resolution, here we propose a tensor-based iterative algorithm that simultaneously reconstructs the X-ray attenuation distribution for each energy. We use a multi-linear image model rather than a more standard "stacked vector" representation in order to develop novel tensor-based regularizers. Specifically, we model the multi-spectral unknown as a 3-way tensor where the first two dimensions are space and the third dimension is energy. This approach allows for the design of tensor nuclear norm regularizers, which like its two dimensional counterpart, is a convex function of the multi-spectral unknown. The solution to the resulting convex optimization problem is obtained using an alternating direction method of multipliers (ADMM) approach. Simulation results shows that the generalized tensor nuclear norm can be used as a stand alone regularization technique for the energy selective (spectral) computed tomography (CT) problem and when combined with total variation regularization it enhances the regularization capabilities especially at low energy images where the effects of noise are most prominent.
Homology and Bisimulation of Asynchronous Transition Systems and Petri Nets
Venue: arXiv cs.LO 2013
Year: 2013

Homology groups of labelled asynchronous transition systems and Petri nets are introduced. Examples of computing the homology groups are given. It is proved that if labelled asynchronous transition systems are bisimulation equivalent, then they have isomorphic homology groups. A method of constructing a Petri net with given homology groups is found.
Convex Clustering via Optimal Mass Transport
Venue: arXiv cs.SY 2013
Year: 2013

We consider approximating distributions within the framework of optimal mass transport and specialize to the problem of clustering data sets. Distances between distributions are measured in the Wasserstein metric. The main problem we consider is that of approximating sample distributions by ones with sparse support. This provides a new viewpoint to clustering. We propose different relaxations of a cardinality function which penalizes the size of the support set. We establish that a certain relaxation provides the tightest convex lower approximation to the cardinality penalty. We compare the performance of alternative relaxations on a numerical study on clustering.
A scalable stage-wise approach to large-margin multi-class loss based boosting
Venue: arXiv cs.LG 2013
Year: 2013

We present a scalable and effective classification model to train multi-class boosting for multi-class classification problems. Shen and Hao introduced a direct formulation of multi- class boosting in the sense that it directly maximizes the multi- class margin [C. Shen and Z. Hao, "A direct formulation for totally-corrective multi- class boosting", in Proc. IEEE Conf. Comp. Vis. Patt. Recogn., 2011]. The major problem of their approach is its high computational complexity for training, which hampers its application on real-world problems. In this work, we propose a scalable and simple stage-wise multi-class boosting method, which also directly maximizes the multi-class margin. Our approach of- fers a few advantages: 1) it is simple and computationally efficient to train. The approach can speed up the training time by more than two orders of magnitude without sacrificing the classification accuracy. 2) Like traditional AdaBoost, it is less sensitive to the choice of parameters and empirically demonstrates excellent generalization performance. Experimental results on challenging multi-class machine learning and vision tasks demonstrate that the proposed approach substantially improves the convergence rate and accuracy of the final visual detector at no additional computational cost compared to existing multi-class boosting.
Random Rates for 0-Extension and Low-Diameter Decompositions
Venue: arXiv cs.DS 2013
Year: 2013

Consider the problem of partitioning an arbitrary metric space into pieces of diameter at most Δ, such every pair of points is separated with relatively low probability. We propose a rate-based algorithm inspired by multiplicatively-weighted Voronoi diagrams, and prove it has optimal trade-offs. This also gives us another logarithmic approximation algorithm for the 0-extension problem.