OpenRaiser/Intern-Atlas huggingface dataset:
Controlled conflict resolution for replicated document
Venue: arXiv cs.DB 2012
Year: 2012

Collaborative working is increasingly popular, but it presents challenges due to the need for high responsiveness and disconnected work support. To address these challenges the data is optimistically replicated at the edges of the network, i.e. personal computers or mobile devices. This replication requires a merge mechanism that preserves the consistency and structure of the shared data subject to concurrent modifications. In this paper, we propose a generic design to ensure eventual consistency (every replica will eventually view the same data) and to maintain the specific constraints of the replicated data. Our layered design provides to the application engineer the complete control over system scalability and behavior of the replicated data in face of concurrent modifications. We show that our design allows replication of complex data types with acceptable performances.
New Advances in Inference by Recursive Conditioning
Venue: arXiv cs.AI 2012
Year: 2012

Recursive Conditioning (RC) was introduced recently as the first any-space algorithm for inference in Bayesian networks which can trade time for space by varying the size of its cache at the increment needed to store a floating point number. Under full caching, RC has an asymptotic time and space complexity which is comparable to mainstream algorithms based on variable elimination and clustering (exponential in the network treewidth and linear in its size). We show two main results about RC in this paper. First, we show that its actual space requirements under full caching are much more modest than those needed by mainstream methods and study the implications of this finding. Second, we show that RC can effectively deal with determinism in Bayesian networks by employing standard logical techniques, such as unit resolution, allowing a significant reduction in its time requirements in certain cases. We illustrate our results using a number of benchmark networks, including the very challenging ones that arise in genetic linkage analysis.
Incremental Compilation of Bayesian networks
Venue: arXiv cs.AI 2012
Year: 2012

Most methods of exact probability propagation in Bayesian networks do not carry out the inference directly over the network, but over a secondary structure known as a junction tree or a join tree (JT). The process of obtaining a JT is usually termed {sl compilation}. As compilation is usually viewed as a whole process; each time the network is modified, a new compilation process has to be carried out. The possibility of reusing an already existing JT, in order to obtain the new one regarding only the modifications in the network has received only little attention in the literature. In this paper we present a method for incremental compilation of a Bayesian network, following the classical scheme in which triangulation plays the key role. In order to perform incremental compilation we propose to recompile only those parts of the JT which can have been affected by the networks modifications. To do so, we exploit the technique OF maximal prime subgraph decomposition in determining the minimal subgraph(s) that have to be recompiled, and thereby the minimal subtree(s) of the JT that should be replaced by new subtree(s).We focus on structural modifications : addition and deletion of links and variables.
Symbolic Generalization for On-line Planning
Venue: arXiv cs.AI 2012
Year: 2012

Symbolic representations have been used successfully in off-line planning algorithms for Markov decision processes. We show that they can also improve the performance of on-line planners. In addition to reducing computation time, symbolic generalization can reduce the amount of costly real-world interactions required for convergence. We introduce Symbolic Real-Time Dynamic Programming (or sRTDP), an extension of RTDP. After each step of on-line interaction with an environment, sRTDP uses symbolic model-checking techniques to generalizes its experience by updating a group of states rather than a single state. We examine two heuristic approaches to dynamic grouping of states and show that they accelerate the planning process significantly in terms of both CPU time and the number of steps of interaction with the environment.
On Information Regularization
Venue: arXiv cs.LG 2012
Year: 2012

We formulate a principle for classification with the knowledge of the marginal distribution over the data points (unlabeled data). The principle is cast in terms of Tikhonov style regularization where the regularization penalty articulates the way in which the marginal density should constrain otherwise unrestricted conditional distributions. Specifically, the regularization penalty penalizes any information introduced between the examples and labels beyond what is provided by the available labeled examples. The work extends Szummer and Jaakkola's information regularization (NIPS 2002) to multiple dimensions, providing a regularizer independent of the covering of the space used in the derivation. We show in addition how the information regularizer can be used as a measure of complexity of the classification task with unlabeled data and prove a relevant sample-complexity bound. We illustrate the regularization principle in practice by restricting the class of conditional distributions to be logistic regression models and constructing the regularization penalty from a finite set of unlabeled examples.
Locally Weighted Naive Bayes
Venue: arXiv cs.LG 2012
Year: 2012

Despite its simplicity, the naive Bayes classifier has surprised machine learning researchers by exhibiting good performance on a variety of learning problems. Encouraged by these results, researchers have looked to overcome naive Bayes primary weakness - attribute independence - and improve the performance of the algorithm. This paper presents a locally weighted version of naive Bayes that relaxes the independence assumption by learning local models at prediction time. Experimental results show that locally weighted naive Bayes rarely degrades accuracy compared to standard naive Bayes and, in many cases, improves accuracy dramatically. The main advantage of this method compared to other techniques for enhancing naive Bayes is its conceptual and computational simplicity.
On the Convergence of Bound Optimization Algorithms
Venue: arXiv cs.LG 2012
Year: 2012

Many practitioners who use the EM algorithm complain that it is sometimes slow. When does this happen, and what can be done about it? In this paper, we study the general class of bound optimization algorithms - including Expectation-Maximization, Iterative Scaling and CCCP - and their relationship to direct optimization algorithms such as gradient-based methods for parameter learning. We derive a general relationship between the updates performed by bound optimization methods and those of gradient and second-order methods and identify analytic conditions under which bound optimization algorithms exhibit quasi-Newton behavior, and conditions under which they possess poor, first-order convergence. Based on this analysis, we consider several specific algorithms, interpret and analyze their convergence properties and provide some recipes for preprocessing input to these algorithms to yield faster convergence behavior. We report empirical results supporting our analysis and showing that simple data preprocessing can result in dramatically improved performance of bound optimizers in practice.
Strong Faithfulness and Uniform Consistency in Causal Inference
Venue: arXiv cs.AI 2012
Year: 2012

A fundamental question in causal inference is whether it is possible to reliably infer manipulation effects from observational data. There are a variety of senses of asymptotic reliability in the statistical literature, among which the most commonly discussed frequentist notions are pointwise consistency and uniform consistency. Uniform consistency is in general preferred to pointwise consistency because the former allows us to control the worst case error bounds with a finite sample size. In the sense of pointwise consistency, several reliable causal inference algorithms have been established under the Markov and Faithfulness assumptions [Pearl 2000, Spirtes et al. 2001]. In the sense of uniform consistency, however, reliable causal inference is impossible under the two assumptions when time order is unknown and/or latent confounders are present [Robins et al. 2000]. In this paper we present two natural generalizations of the Faithfulness assumption in the context of structural equation models, under which we show that the typical algorithms in the literature (in some cases with modifications) are uniformly consistent even when the time order is unknown. We also discuss the situation where latent confounders may be present and the sense in which the Faithfulness assumption is a limiting case of the stronger assumptions.
Exploiting Locality in Searching the Web
Venue: arXiv cs.IR 2012
Year: 2012

Published experiments on spidering the Web suggest that, given training data in the form of a (relatively small) subgraph of the Web containing a subset of a selected class of target pages, it is possible to conduct a directed search and find additional target pages significantly faster (with fewer page retrievals) than by performing a blind or uninformed random or systematic search, e.g., breadth-first search. If true, this claim motivates a number of practical applications. Unfortunately, these experiments were carried out in specialized domains or under conditions that are difficult to replicate. We present and apply an experimental framework designed to reexamine and resolve the basic claims of the earlier work, so that the supporting experiments can be replicated and built upon. We provide high-performance tools for building experimental spiders, make use of the ground truth and static nature of the WT10g TREC Web corpus, and rely on simple well understand machine learning techniques to conduct our experiments. In this paper, we describe the basic framework, motivate the experimental design, and report on our findings supporting and qualifying the conclusions of the earlier research.
On The Delays In Spiking Neural P Systems
Venue: arXiv cs.NE 2012
Year: 2012

In this work we extend and improve the results done in a previous work on simulating Spiking Neural P systems (SNP systems in short) with delays using SNP systems without delays. We simulate the former with the latter over sequential, iteration, join, and split routing. Our results provide constructions so that both systems halt at exactly the same time, start with only one spike, and produce the same number of spikes to the environment after halting.
Self Authentication of color image through Wavelet Transformation Technique (SAWT)
Venue: arXiv cs.CR 2012
Year: 2012

In this paper a self organized legal document/content authentication, copyright protection in composite domain has been proposed without using any external information. Average values of transformed red and green components in frequency domain generated through wavelet transform are embedded into the blue component of the color image matrix in spatial domain. A reverse transformation is made in RG matrix to obtain embedded image in association with blue component in spatial domain. Reverse procedure is done during decoding where transformed average values are obtained from red and green components and compared with the same from blue component for authentication. Results are compared with existing technique which shows better performance interns of PSNR, MSE & IF.
Feasibility Tests for Recurrent Real-Time Tasks in the Sporadic DAG Model
Venue: arXiv cs.DS 2012
Year: 2012

A model has been proposed in [Baruah et al., in Proceedings of the IEEE Real-Time Systems Symposium 2012] for representing recurrent precedence-constrained tasks to be executed on multiprocessor platforms, where each recurrent task is modeled by a directed acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and have to be completed within some specified relative deadline. The task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. The feasibility problem is to determine whether such a recurrent task can be scheduled to always meet all deadlines on a specified number of dedicated processors. The case of a single task has been considered in [Baruah et al., 2012]. The main contribution of this paper is to consider the case of multiple tasks. We show that EDF has a speedup bound of 2-1/m, where m is the number of processors. Moreover, we present polynomial and pseudopolynomial schedulability tests, of differing effectiveness, for determining whether a set of sporadic DAG tasks can be scheduled by EDF to meet all deadlines on a specified number of processors.
The PAPR Problem in OFDM Transmission: New Directions for a Long-Lasting Problem
Venue: arXiv cs.IT 2012
Year: 2012

Peak power control for multicarrier communications has been a long-lasting problem in signal processing and communications. However, industry and academia are confronted with new challenges regarding energy efficient system design. Particularly, the envisioned boost in network energy efficiency (e.g. at least by a factor of 1000 in the Green Touch consortium) will tighten the requirements on component level so that the efficiency gap with respect to single-carrier transmission must considerably diminish. This paper reflects these challenges together with a unified framework and new directions in this field. The combination of large deviation theory, de-randomization and selected elements of Banach space geometry will offer a novel approach and will provide ideas and concepts for researchers with a background in industry as well as those from academia.
Speed Optimization In Unplanned Traffic Using Bio-Inspired Computing And Population Knowledge Base
Venue: arXiv cs.CY 2012
Year: 2012

Bio-Inspired Algorithms on Road Traffic Congestion and safety is a very promising research problem. Searching for an efficient optimization method to increase the degree of speed optimization and thereby increasing the traffic Flow in an unplanned zone is a widely concerning issue. However, there has been a limited research effort on the optimization of the lane usage with speed optimization. The main objective of this article is to find avenues or techniques in a novel way to solve the problem optimally using the knowledge from analysis of speeds of vehicles, which, in turn will act as a guide for design of lanes optimally to provide better optimized traffic. The accident factors adjust the base model estimates for individual geometric design element dimensions and for traffic control features. The application of these algorithms in partially modified form in accordance of this novel Speed Optimization Technique in an Unplanned Traffic analysis technique is applied to the proposed design and speed optimization plan. The experimental results based on real life data are quite encouraging.
Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
Venue: arXiv cs.DS 2012
Year: 2012

Computing the LZ factorization (or LZ77 parsing) of a string is a computational bottleneck in many diverse applications, including data compression, text indexing, and pattern discovery. We describe new linear time LZ factorization algorithms, some of which require only 2n log n + O(log n) bits of working space to factorize a string of length n. These are the most space efficient linear time algorithms to date, using n log n bits less space than any previous linear time algorithm. The algorithms are also practical, simple to implement, and very fast in practice.
Accelerating Inference: towards a full Language, Compiler and Hardware stack
Venue: arXiv cs.SE 2012
Year: 2012

We introduce Dimple, a fully open-source API for probabilistic modeling. Dimple allows the user to specify probabilistic models in the form of graphical models, Bayesian networks, or factor graphs, and performs inference (by automatically deriving an inference engine from a variety of algorithms) on the model. Dimple also serves as a compiler for GP5, a hardware accelerator for inference.
Claw-free graphs, skeletal graphs, and a stronger conjecture on $ω$, $Δ$, and $χ$
Venue: arXiv cs.DM 2012
Year: 2012

The second author's $ω$, $Δ$, $χ$ conjecture proposes that every graph satisties $χ\leq \lceil \frac 12 (Δ+1+ω)\rceil$. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colourable complement. To prove our results we introduce a very useful $χ$-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called "skeletal" graphs.
Asymmetrical two-level scalar quantizer with extended Huffman coding for compression of Laplacian source
Venue: arXiv cs.IT 2012
Year: 2012

This paper proposes a novel model of the two-level scalar quantizer with extended Huffman coding. It is designed for the average bit rate to approach the source entropy as close as possible provided that the signal to quantization noise ratio (SQNR) value does not decrease more than 1 dB from the optimal SQNR value. Assuming the asymmetry of representation levels for the symmetric Laplacian probability density function, the unequal probabilities of representation levels are obtained, i.e. the proper basis for further implementation of lossless compression techniques is provided. In this paper, we are concerned with extended Huffman coding technique that provides the shortest length of codewords for blocks of two or more symbols. For the proposed quantizer with extended Huffman coding the convergence of the average bit rate to the source entropy is examined in the case of two to five symbol blocks. It is shown that the higher SQNR is achieved by the proposed asymmetrical quantizer with extended Huffman coding when compared with the symmetrical quantizers with extended Huffman coding having equal average bit rates.
Measures of Fault Tolerance in Distributed Simulated Annealing
Venue: arXiv cs.DC 2012
Year: 2012

In this paper, we examine the different measures of Fault Tolerance in a Distributed Simulated Annealing process. Optimization by Simulated Annealing on a distributed system is prone to various sources of failure. We analyse simulated annealing algorithm, its architecture in distributed platform and potential sources of failures. We examine the behaviour of tolerant distributed system for optimization task. We present possible methods to overcome the failures and achieve fault tolerance for the distributed simulated annealing process. We also examine the implementation of Simulated Annealing in MapReduce system and possible ways to prevent failures in reaching the global optima. This paper will be beneficial to those who are interested in implementing a large scale distributed simulated annealing optimization problem of industrial or academic interest. We recommend hybrid tolerance technique to optimize the trade-off between efficiency and availability.
Optimal Pricing Effect on Equilibrium Behaviors of Delay-Sensitive Users in Cognitive Radio Networks
Venue: arXiv cs.NI 2012
Year: 2012

This paper studies price-based spectrum access control in cognitive radio networks, which characterizes network operators' service provisions to delay-sensitive secondary users (SUs) via pricing strategies. Based on the two paradigms of shared-use and exclusive-use dynamic spectrum access (DSA), we examine three network scenarios corresponding to three types of secondary markets. In the first monopoly market with one operator using opportunistic shared-use DSA, we study the operator's pricing effect on the equilibrium behaviors of self-optimizing SUs in a queueing system. %This queue represents the congestion of the multiple SUs sharing the operator's single \ON-\OFF channel that models the primary users (PUs) traffic. We provide a queueing delay analysis with the general distributions of the SU service time and PU traffic using the renewal theory. In terms of SUs, we show that there exists a unique Nash equilibrium in a non-cooperative game where SUs are players employing individual optimal strategies. We also provide a sufficient condition and iterative algorithms for equilibrium convergence. In terms of operators, two pricing mechanisms are proposed with different goals: revenue maximization and social welfare maximization. In the second monopoly market, an operator exploiting exclusive-use DSA has many channels that will be allocated separately to each entering SU. We also analyze the pricing effect on the equilibrium behaviors of the SUs and the revenue-optimal and socially-optimal pricing strategies of the operator in this market. In the third duopoly market, we study a price competition between two operators employing shared-use and exclusive-use DSA, respectively, as a two-stage Stackelberg game. Using a backward induction method, we show that there exists a unique equilibrium for this game and investigate the equilibrium convergence.
Inapproximability of Dominating Set in Power Law Graphs
Venue: arXiv cs.CC 2012
Year: 2012

We give logarithmic lower bounds for the approximability of the Minimum Dominating Set problem in connected (alpha,beta)-Power Law Graphs. We give also a best up to now upper approximation bound on the problem for the case of the parameters beta>2. We develop also a new functional method for proving lower approximation bounds and display a sharp phase transition between approximability and inapproximability of the underlying problem. This method could also be of independent interest.
Social Network Based Search for Experts
Venue: arXiv cs.SI 2012
Year: 2012

Our system illustrates how information retrieved from social networks can be used for suggesting experts for specific tasks. The system is designed to facilitate the task of finding the appropriate person(s) for a job, as a conference committee member, an advisor, etc. This short description will demonstrate how the system works in the context of the HCIR2012 published tasks.
Tracking of a Mobile Target Using Generalized Polarization Tensors
Venue: arXiv cs.NA 2012
Year: 2012

In this paper we apply an extended Kalman filter to track both the location and the orientation of a mobile target from multistatic response measurements. We also analyze the effect of the limited-view aspect on the stability and the efficiency of our tracking approach. Our algorithm is based on the use of the generalized polarization tensors, which can be reconstructed from the multistatic response measurements by solving a linear system. The system has the remarkable property that low order generalized polarization tensors are not affected by the error caused by the instability of higher orders in the presence of measurement noise.