OpenRaiser/Intern-Atlas huggingface dataset:
Autotagging music with conditional restricted Boltzmann machines
Venue: arXiv cs.LG 2011
Year: 2011

This paper describes two applications of conditional restricted Boltzmann machines (CRBMs) to the task of autotagging music. The first consists of training a CRBM to predict tags that a user would apply to a clip of a song based on tags already applied by other users. By learning the relationships between tags, this model is able to pre-process training data to significantly improve the performance of a support vector machine (SVM) autotagging. The second is the use of a discriminative RBM, a type of CRBM, to autotag music. By simultaneously exploiting the relationships among tags and between tags and audio-based features, this model is able to significantly outperform SVMs, logistic regression, and multi-layer perceptrons. In order to be applied to this problem, the discriminative RBM was generalized to the multi-label setting and four different learning algorithms for it were evaluated, the first such in-depth analysis of which we are aware.
Reweighted LP Decoding for LDPC Codes
Venue: arXiv cs.IT 2011
Year: 2011

We introduce a novel algorithm for decoding binary linear codes by linear programming. We build on the LP decoding algorithm of Feldman et al. and introduce a post-processing step that solves a second linear program that reweights the objective function based on the outcome of the original LP decoder output. Our analysis shows that for some LDPC ensembles we can improve the provable threshold guarantees compared to standard LP decoding. We also show significant empirical performance gains for the reweighted LP decoding algorithm with very small additional computational complexity.
Computing the Fréchet Distance Between Folded Polygons
Venue: arXiv cs.CG 2011
Year: 2011

Computing the Fréchet distance for surfaces is a surprisingly hard problem and the only known algorithm is limited to computing it between flat surfaces. We adapt this algorithm to create one for computing the Fréchet distance for a class of non-flat surfaces which we call folded polygons. Unfortunately, the original algorithm cannot be extended directly. We present three different methods to adapt it. The first of which is a fixed-parameter tractable algorithm. The second is a polynomial-time approximation algorithm. Finally, we present a restricted class of folded polygons for which we can compute the Fréchet distance in polynomial time.
On optimum strategies for minimizing the exponential moments of a given cost function
Venue: arXiv cs.IT 2011
Year: 2011

We consider a general problem of finding a strategy that minimizes the exponential moment of a given cost function, with an emphasis on its relation to the more common criterion of minimization the expectation of the first moment of the same cost function. In particular, our main result is a theorem that gives simple sufficient conditions for a strategy to be optimum in the exponential moment sense. This theorem may be useful in various situations, and application examples are given. We also examine the asymptotic regime and investigate universal asymptotically optimum strategies in light of the aforementioned sufficient conditions, as well as phenomena of irregularities, or phase transitions, in the behavior of the asymptotic performance, which can be viewed and understood from a statistical-mechanical perspective. Finally, we propose a new route for deriving lower bounds on exponential moments of certain cost functions (like the square error in estimation problems) on the basis of well known lower bounds on their expectations.
Data sets of very large linear feasibility problems solved by projection methods
Venue: arXiv cs.MS 2011
Year: 2011

We give a link to a page on the Web on which we deposited a set of eight huge Linear Programming (LP) problems for Intensity-Modulated Proton Therapy (IMPT) treatment planning. These huge LP problems were employed in our recent research and we were asked to make them public.
Xampling: Compressed Sensing of Analog Signals
Venue: arXiv cs.IT 2011
Year: 2011

Xampling generalizes compressed sensing (CS) to reduced-rate sampling of analog signals. A unified framework is introduced for low rate sampling and processing of signals lying in a union of subspaces. Xampling consists of two main blocks: Analog compression that narrows down the input bandwidth prior to sampling with commercial devices followed by a nonlinear algorithm that detects the input subspace prior to conventional signal processing. A variety of analog CS applications are reviewed within the unified Xampling framework including a general filter-bank scheme for sparse shift-invariant spaces, periodic nonuniform sampling and modulated wideband conversion for multiband communications with unknown carrier frequencies, acquisition techniques for finite rate of innovation signals with applications to medical and radar imaging, and random demodulation of sparse harmonic tones. A hardware-oriented viewpoint is advocated throughout, addressing practical constraints and exemplifying hardware realizations where relevant. It will appear as a chapter in a book on "Compressed Sensing: Theory and Applications" edited by Yonina Eldar and Gitta Kutyniok.
A study of the existing libraries to read from configuration files (from C++)
Venue: arXiv cs.SE 2011
Year: 2011

A study of the existing libraries to read from configuration files (from C++)
Connectivity Damage to a Graph by the Removal of an Edge or a Vertex
Venue: arXiv cs.DL 2011
Year: 2011

The approach of quantifying the damage inflicted on a graph in Albert, Jeong and Barabsi's (AJB) report "Error and Attack Tolerance of Complex Networks" using the size of the largest connected component and the average size of the remaining components does not capture our intuitive idea of the damage to a graph caused by disconnections. We evaluate an alternative metric based on average inverse path lengths (AIPLs) that better fits our intuition that a graph can still be reasonably functional even when it is disconnected. We compare our metric with AJB's using a test set of graphs and report the differences. AJB's report should not be confused with a report by Crucitti et al. with the same name. Based on our analysis of graphs of different sizes and types, and using various numerical and statistical tools; the ratio of the average inverse path lengths of a connected graph of the same size as the sum of the size of the fragments of the disconnected graph can be used as a metric about the damage of a graph by the removal of an edge or a node. This damage is reported in the range (0,1) where 0 means that the removal had no effect on the graph's capability to perform its functions. A 1 means that the graph is totally dysfunctional. We exercise our metric on a collection of sample graphs that have been subjected to various attack profiles that focus on edge, node or degree betweenness values. We believe that this metric can be used to quantify the damage done to the graph by an attacker, and that it can be used in evaluating the positive effect of adding additional edges to an existing graph.
Optimal Power Cost Management Using Stored Energy in Data Centers
Venue: arXiv cs.PF 2011
Year: 2011

Since the electricity bill of a data center constitutes a significant portion of its overall operational costs, reducing this has become important. We investigate cost reduction opportunities that arise by the use of uninterrupted power supply (UPS) units as energy storage devices. This represents a deviation from the usual use of these devices as mere transitional fail-over mechanisms between utility and captive sources such as diesel generators. We consider the problem of opportunistically using these devices to reduce the time average electric utility bill in a data center. Using the technique of Lyapunov optimization, we develop an online control algorithm that can optimally exploit these devices to minimize the time average cost. This algorithm operates without any knowledge of the statistics of the workload or electricity cost processes, making it attractive in the presence of workload and pricing uncertainties. An interesting feature of our algorithm is that its deviation from optimality reduces as the storage capacity is increased. Our work opens up a new area in data center power management.
Incrementally Maintaining Classification using an RDBMS
Venue: arXiv cs.DB 2011
Year: 2011

The proliferation of imprecise data has motivated both researchers and the database industry to push statistical techniques into relational database management systems (RDBMSs). We study algorithms to maintain model-based views for a popular statistical technique, classification, inside an RDBMS in the presence of updates to the training examples. We make three technical contributions: (1) An algorithm that incrementally maintains classification inside an RDBMS. (2) An analysis of the above algorithm that shows that our algorithm is optimal among all deterministic algorithms (and asymptotically within a factor of 2 of a nondeterministic optimal). (3) An index structure based on the technical ideas that underlie the above algorithm which allows us to store only a fraction of the entities in memory. We apply our techniques to text processing, and we demonstrate that our algorithms provide several orders of magnitude improvement over non-incremental approaches to classification on a variety of data sets: such as the Cora, UCI Machine Learning Repository data sets, Citeseer, and DBLife.
A Broadcast Approach To Secret Key Generation Over Slow Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

A secret-key generation scheme based on a layered broadcasting strategy is introduced for slow-fading channels. In the model considered, Alice wants to share a key with Bob while keeping the key secret from Eve, who is a passive eavesdropper. Both Alice-Bob and Alice-Eve channels are assumed to undergo slow fading, and perfect channel state information (CSI) is assumed to be known only at the receivers during the transmission. In each fading slot, Alice broadcasts a continuum of coded layers and, hence, allows Bob to decode at the rate corresponding to the fading state (unknown to Alice). The index of a reliably decoded layer is sent back from Bob to Alice via a public and error-free channel and used to generate a common secret key. In this paper, the achievable secrecy key rate is first derived for a given power distribution over coded layers. The optimal power distribution is then characterized. It is shown that layered broadcast coding can increase the secrecy key rate significantly compared to single-level coding.
Fast $q$-gram Mining on SLP Compressed Strings
Venue: arXiv cs.DS 2011
Year: 2011

We present simple and efficient algorithms for calculating $q$-gram frequencies on strings represented in compressed form, namely, as a straight line program (SLP). Given an SLP of size $n$ that represents string $T$, we present an $O(qn)$ time and space algorithm that computes the occurrence frequencies of $q$-grams in $T$. Computational experiments show that our algorithm and its variation are practical for small $q$, actually running faster on various real string data, compared to algorithms that work on the uncompressed text. We also discuss applications in data mining and classification of string data, for which our algorithms can be useful.
Path coalitional games
Venue: arXiv cs.GT 2011
Year: 2011

We present a general framework to model strategic aspects and stable and fair resource allocations in networks via variants and generalizations of path coalitional games. In these games, a coalition of edges or vertices is successful if it can enable an s-t path. We present polynomial-time algorithms to compute and verify least core payoffs of cost-based generalizations of path coalitional games and their duals, thereby settling a number of open problems. The least core payoffs of path coalitional games are completely characterized and a polynomial-time algorithm for computing the nucleolus of edge path coalitional games on undirected series-parallel graphs is presented.
Confidentiality & Authentication Mechanism for Biometric Information Transmitted over Low Bandwidth & Unreliable channel
Venue: arXiv cs.CR 2011
Year: 2011

The security of bio-metric information - finger print, retina mapping, DNA mapping and some other chemical and biological modified genes related information - transfer through low bandwidth and unreliable or covert channel is challenging task. Therefore, Security of biometric information is essential requirement in this fast developing communication world. Thus, in this paper, we propose efficient and effective mechanism for confidentiality and authentication for biometric information transmitted by using arithmetic encoding representation over low bandwidth and unreliable channel. It enhances the speed of encryption, decryption and authentication process. It uses arithmetic encoding scheme and public key cryptography e.g. modified version of RSA algorithm called RSA-2 algorithm.
Ex ante prediction of cascade sizes on networks of agents facing binary outcomes
Venue: arXiv cs.SI 2011
Year: 2011

We consider in this paper the potential for ex ante prediction of the cascade size in a model of binary choice with externalities (Schelling 1973, Watts 2002). Agents are connected on a network and can be in one of two states of the world, 0 or 1. Initially, all are in state 0 and a small number of seeds are selected at random to switch to state1. A simple threshold rule specifies whether other agents switch subsequently. The cascade size (the percolation) is the proportion of all agents which eventually switches to state 1. We select information on the connectivity of the initial seeds, the connectivity of the agents to which they are connected, the thresholds of these latter agents, and the thresholds of the agents to which these are connected. We obtain results for random, small world and scale -free networks with different network parameters and numbers of initial seeds. The results are robust with respect to these factors. We perform least squares regression of the logit transformation of the cascade size (Hosmer and Lemeshow 1989) on these potential explanatory variables. We find considerable explanatory power for the ex ante prediction of cascade sizes. For the random networks, on average 32 per cent of the variance of the cascade sizes is explained, 40 per cent for the small world and 46 per cent for the scale-free. The connectivity variables are hardly ever significant in the regressions, whether relating to the seeds themselves or to the agents connected to the seeds. In contrast, the information on the thresholds of agents contains much more explanatory power. This supports the conjecture of Watts and Dodds (2007.) that large cascades are driven by a small mass of easily influenced agents.
Globalisation of science in kilometres
Venue: arXiv cs.DL 2011
Year: 2011

The ongoing globalisation of science has undisputedly a major impact on how and where scientific research is being conducted nowadays. Yet, the big picture remains blurred. It is largely unknown where this process is heading, and at which rate. Which countries are leading or lagging? Many of its key features are difficult if not impossible to capture in measurements and comparative statistics. Our empirical study measures the extent and growth of scientific globalisation in terms of physical distances between co-authoring researchers. Our analysis, drawing on 21 million research publications across all countries and fields of science, reveals that contemporary science has globalised at a fairly steady rate during recent decades. The average collaboration distance per publication has increased from 334 kilometres in 1980 to 1553 in 2009. Despite significant differences in globalisation rates across countries and fields of science, we observe a pervasive process in motion, moving towards a truly interconnected global science system.
The AllDifferent Constraint with Precedences
Venue: arXiv cs.AI 2011
Year: 2011

We propose AllDiffPrecedence, a new global constraint that combines together an AllDifferent constraint with precedence constraints that strictly order given pairs of variables. We identify a number of applications for this global constraint including instruction scheduling and symmetry breaking. We give an efficient propagation algorithm that enforces bounds consistency on this global constraint. We show how to implement this propagator using a decomposition that extends the bounds consistency enforcing decomposition proposed for the AllDifferent constraint. Finally, we prove that enforcing domain consistency on this global constraint is NP-hard in general.
Validation Measures in CMMI
Venue: arXiv cs.SE 2011
Year: 2011

Validation is one of the software engineering disciplines that help build quality into software. The major objective of software validation process is to determine that the software performs its intended functions correctly and provide information about its quality and reliability. This paper identifies general measures for the specific goals and its specific practices of Validation Process Area (PA) in Capability Maturity Model Integration (CMMI). CMMI is developed by Software Engineering Institute (SEI). CMMI is a framework for improvement and assessment of a software development process. CMMI needs a measurement program that is practical. The method we used to define the measures is to apply the Goal Question Metrics (GQM) paradigm to the specific goals and its specific practices of Validation Process Area in CMMI.
A New Proposed Dynamic Quantum with Re-Adjusted Round Robin Scheduling Algorithm and Its Performance Analysis
Venue: arXiv cs.OS 2011
Year: 2011

Scheduling is the central concept used frequently in Operating System. It helps in choosing the processes for execution. Round Robin (RR) is one of the most widely used CPU scheduling algorithm. But, its performance degrades with respect to context switching, which is an overhead and it occurs during each scheduling. Overall performance of the system depends on choice of an optimal time quantum, so that context switching can be reduced. In this paper, we have proposed a new variant of RR scheduling algorithm, known as Dynamic Quantum with Readjusted Round Robin (DQRRR) algorithm. We have experimentally shown that performance of DQRRR is better than RR by reducing number of context switching, average waiting time and average turn around time.
Transmission Selection Schemes using Sum Rate Analysis in Distributed Antenna Systems
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study single cell multi-user downlink distributed antenna systems (DAS) where the antenna ports are geographically separated in a cell. First, we derive an expression of the ergodic sum rate for DAS in the presence of pathloss. Then, we propose a transmission selection scheme based on the derived expressions to maximize the overall ergodic sum rate. Utilizing the knowledge of distance information from a user to each distributed antenna (DA) port, we consider the pairings of each DA port and its supporting user to optimize the system performance. Then, we compute the ergodic sum rate for various transmission mode candidates and adopt a transmission selection scheme which chooses the best mode maximizing the ergodic sum rate among the mode candidates. In our proposed scheme, the number of mode candidates are greatly reduced compared to that of the ideal mode selection. Through Monte Carlo simulations, we will show the accuracy of our derivation for the ergodic sum rate expression. Moreover, simulation results with the pathloss modeling confirm that the proposed transmission selection scheme produces the average sum rate identical to the ideal mode selection with significantly reduced selection candidates.
Informed Heuristics for Guiding Stem-and-Cycle Ejection Chains
Venue: arXiv cs.AI 2011
Year: 2011

The state of the art in local search for the Traveling Salesman Problem is dominated by ejection chain methods utilising the Stem-and-Cycle reference structure. Though effective such algorithms employ very little information in their successor selection strategy, typically seeking only to minimise the cost of a move. We propose an alternative approach inspired from the AI literature and show how an admissible heuristic can be used to guide successor selection. We undertake an empirical analysis and demonstrate that this technique often produces better results than less informed strategies albeit at the cost of running in higher polynomial time.
Sampling-rate-aware noise generation
Venue: arXiv cs.SD 2011
Year: 2011

In this paper we consider the generation of discrete white noise. Despite this seems to be a simple problem, common noise generator implementations do not deliver comparable results at different sampling rates. First we define what we mean with "comparable results". From this we conclude, that the variance of the random variables shall grow proportionally to the sampling rate. Eventually we consider how noise behaves under common signal transformations, such as frequency filters, quantisation and impulse generation and we explore how these signal transformations must be designed in order generate sampling-rate-aware results when applied to white noise.
Parallel Online Learning
Venue: arXiv cs.LG 2011
Year: 2011

In this work we study parallelization of online learning, a core primitive in machine learning. In a parallel environment all known approaches for parallel online learning lead to delayed updates, where the model is updated using out-of-date information. In the worst case, or when examples are temporally correlated, delay can have a very adverse effect on the learning algorithm. Here, we analyze and present preliminary empirical results on a set of learning architectures based on a feature sharding approach that present various tradeoffs between delay, degree of parallelism, representation power and empirical performance.
A Stochastic-Geometry Approach to Coverage in Cellular Networks with Multi-Cell Cooperation
Venue: arXiv cs.IT 2011
Year: 2011

Multi-cell cooperation is a promising approach for mitigating inter-cell interference in dense cellular networks. Quantifying the performance of multi-cell cooperation is challenging as it integrates physical-layer techniques and network topologies. For tractability, existing work typically relies on the over-simplified Wyner-type models. In this paper, we propose a new stochastic-geometry model for a cellular network with multi-cell cooperation, which accounts for practical factors including the irregular locations of base stations (BSs) and the resultant path-losses. In particular, the proposed network-topology model has three key features: i) the cells are modeled using a Poisson random tessellation generated by Poisson distributed BSs, ii) multi-antenna BSs are clustered using a hexagonal lattice and BSs in the same cluster mitigate mutual interference by spatial interference avoidance, iii) BSs near cluster edges access a different sub-channel from that by other BSs, shielding cluster-edge mobiles from strong interference. Using this model and assuming sparse scattering, we analyze the shapes of the outage probabilities of mobiles served by cluster-interior BSs as the average number $K$ of BSs per cluster increases. The outage probability of a mobile near a cluster center is shown to be proportional to $e^{-c(2-\sqrtν)^2K}$ where $ν$ is the fraction of BSs lying in the interior of clusters and $c$ is a constant. Moreover, the outage probability of a typical mobile is proved to scale proportionally with $e^{-c' (1-\sqrtν)^2K}$ where $c'$ is a constant.