OpenRaiser/Intern-Atlas huggingface dataset:
A Comparative Study of Replication Techniques in Grid Computing Systems
Venue: arXiv cs.DC 2013
Year: 2013

Grid Computing is a type of parallel and distributed systems that is designed to provide reliable access to data and computational resources in wide area networks. These resources are distributed in different geographical locations, however are organized to provide an integrated service. Effective data management in today`s enterprise environment is an important issue. Also, Performance is one of the challenges of using these environments. For improving the performance of file access and easing the sharing amongst distributed systems, replication techniques are used. Data replication is a common method used in distributed environments, where essential data is stored in multiple locations, so that a user can access the data from a site in his area. In this paper, we present a survey on basic and new replication techniques that have been proposed by other researchers. After that, we have a full comparative study on these replication strategies. Also, at the end of the paper, we summarize the results and points of these replication techniques.
Minimizing Rosenthal Potential in Multicast Games
Venue: arXiv cs.GT 2013
Year: 2013

A multicast game is a network design game modelling how selfish non-cooperative agents build and maintain one-to-many network communication. There is a special source node and a collection of agents located at corresponding terminals. Each agent is interested in selecting a route from the special source to its terminal minimizing the cost. The mutual influence of the agents is determined by a cost sharing mechanism, which evenly splits the cost of an edge among all the agents using it for routing. In this paper we provide several algorithmic and complexity results on finding a Nash equilibrium minimizing the value of Rosenthal potential. Let n be the number of agents and G be the communication network. We show that - For a given strategy profile s and integer k>=1, there is a local search algorithm which in time n^{O(k)}|G|^{O(1)} finds a better strategy profile, if there is any, in a k-exchange neighbourhood of s. In other words, the algorithm decides if Rosenthal potential can be decreased by changing strategies of at most k agents; - The running time of our local search algorithm is essentially tight: unless FPT= W[1], for any function f(k), searching of the k-neighbourhood cannot be done in time f(k)|G|^{O(1)}. The key ingredient of our algorithmic result is a subroutine that finds an equilibrium with minimum potential in 3^n|G|^{O(1)} time. In other words, finding an equilibrium with minimum potential is fixed-parameter tractable when parameterized by the number of agents.
Generative Multiple-Instance Learning Models For Quantitative Electromyography
Venue: arXiv cs.LG 2013
Year: 2013

We present a comprehensive study of the use of generative modeling approaches for Multiple-Instance Learning (MIL) problems. In MIL a learner receives training instances grouped together into bags with labels for the bags only (which might not be correct for the comprised instances). Our work was motivated by the task of facilitating the diagnosis of neuromuscular disorders using sets of motor unit potential trains (MUPTs) detected within a muscle which can be cast as a MIL problem. Our approach leads to a state-of-the-art solution to the problem of muscle classification. By introducing and analyzing generative models for MIL in a general framework and examining a variety of model structures and components, our work also serves as a methodological guide to modelling MIL tasks. We evaluate our proposed methods both on MUPT datasets and on the MUSK1 dataset, one of the most widely used benchmarks for MIL.
Boosting in the presence of label noise
Venue: arXiv cs.LG 2013
Year: 2013

Boosting is known to be sensitive to label noise. We studied two approaches to improve AdaBoost's robustness against labelling errors. One is to employ a label-noise robust classifier as a base learner, while the other is to modify the AdaBoost algorithm to be more robust. Empirical evaluation shows that a committee of robust classifiers, although converges faster than non label-noise aware AdaBoost, is still susceptible to label noise. However, pairing it with the new robust Boosting algorithm we propose here results in a more resilient algorithm under mislabelling.
Sample Complexity of Multi-task Reinforcement Learning
Venue: arXiv cs.LG 2013
Year: 2013

Transferring knowledge across a sequence of reinforcement-learning tasks is challenging, and has a number of important applications. Though there is encouraging empirical evidence that transfer can improve performance in subsequent reinforcement-learning tasks, there has been very little theoretical analysis. In this paper, we introduce a new multi-task algorithm for a sequence of reinforcement-learning tasks when each task is sampled independently from (an unknown) distribution over a finite set of Markov decision processes whose parameters are initially unknown. For this setting, we prove under certain assumptions that the per-task sample complexity of exploration is reduced significantly due to transfer compared to standard single-task algorithms. Our multi-task algorithm also has the desired characteristic that it is guaranteed not to exhibit negative transfer: in the worst case its per-task sample complexity is comparable to the corresponding single-task algorithm.
Automorphism Groups of Graphical Models and Lifted Variational Inference
Venue: arXiv cs.AI 2013
Year: 2013

Using the theory of group action, we first introduce the concept of the automorphism group of an exponential family or a graphical model, thus formalizing the general notion of symmetry of a probabilistic model. This automorphism group provides a precise mathematical framework for lifted inference in the general exponential family. Its group action partitions the set of random variables and feature functions into equivalent classes (called orbits) having identical marginals and expectations. Then the inference problem is effectively reduced to that of computing marginals or expectations for each class, thus avoiding the need to deal with each individual variable or feature. We demonstrate the usefulness of this general framework in lifting two classes of variational approximation for maximum a posteriori (MAP) inference: local linear programming (LP) relaxation and local LP relaxation with cycle constraints; the latter yields the first lifted variational inference algorithm that operates on a bound tighter than the local constraints.
Monte-Carlo Planning: Theoretically Fast Convergence Meets Practical Efficiency
Venue: arXiv cs.AI 2013
Year: 2013

Popular Monte-Carlo tree search (MCTS) algorithms for online planning, such as epsilon-greedy tree search and UCT, aim at rapidly identifying a reasonably good action, but provide rather poor worst-case guarantees on performance improvement over time. In contrast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improvement over time, yet it is not geared towards identifying reasonably good choices right at the go. We take a stand on the individual strengths of these two classes of algorithms, and show how they can be effectively connected. We then rationalize a principle of "selective tree expansion", and suggest a concrete implementation of this principle within MCTS. The resulting algorithm,s favorably compete with other MCTS algorithms under short planning times, while preserving the attractive convergence properties of BRUE.
Batch-iFDD for Representation Expansion in Large MDPs
Venue: arXiv cs.LG 2013
Year: 2013

Matching pursuit (MP) methods are a promising class of feature construction algorithms for value function approximation. Yet existing MP methods require creating a pool of potential features, mandating expert knowledge or enumeration of a large feature pool, both of which hinder scalability. This paper introduces batch incremental feature dependency discovery (Batch-iFDD) as an MP method that inherits a provable convergence property. Additionally, Batch-iFDD does not require a large pool of features, leading to lower computational complexity. Empirical policy evaluation results across three domains with up to one million states highlight the scalability of Batch-iFDD over the previous state of the art MP algorithm.
Unsupervised Learning of Noisy-Or Bayesian Networks
Venue: arXiv cs.LG 2013
Year: 2013

This paper considers the problem of learning the parameters in Bayesian networks of discrete variables with known structure and hidden variables. Previous approaches in these settings typically use expectation maximization; when the network has high treewidth, the required expectations might be approximated using Monte Carlo or variational methods. We show how to avoid inference altogether during learning by giving a polynomial-time algorithm based on the method-of-moments, building upon recent work on learning discrete-valued mixture models. In particular, we show how to learn the parameters for a family of bipartite noisy-or Bayesian networks. In our experimental results, we demonstrate an application of our algorithm to learning QMR-DT, a large Bayesian network used for medical diagnosis. We show that it is possible to fully learn the parameters of QMR-DT even when only the findings are observed in the training data (ground truth diseases unknown).
Cyclic Causal Discovery from Continuous Equilibrium Data
Venue: arXiv cs.LG 2013
Year: 2013

We propose a method for learning cyclic causal models from a combination of observational and interventional equilibrium data. Novel aspects of the proposed method are its ability to work with continuous data (without assuming linearity) and to deal with feedback loops. Within the context of biochemical reactions, we also propose a novel way of modeling interventions that modify the activity of compounds instead of their abundance. For computational reasons, we approximate the nonlinear causal mechanisms by (coupled) local linearizations, one for each experimental condition. We apply the method to reconstruct a cellular signaling network from the flow cytometry data measured by Sachs et al. (2005). We show that our method finds evidence in the data for feedback loops and that it gives a more accurate quantitative description of the data at comparable model complexity.
Pay or Play
Venue: arXiv cs.GT 2013
Year: 2013

We introduce the class of pay or play games, which captures scenarios in which each decision maker is faced with a choice between two actions: one with a fixed payoff and an- other with a payoff dependent on others' selected actions. This is, arguably, the simplest setting that models selection among certain and uncertain outcomes in a multi-agent system. We study the properties of equilibria in such games from both a game-theoretic perspective and a computational perspective. Our main positive result establishes the existence of a semi-strong equilibrium in every such game. We show that although simple, pay of play games contain a large variety of well-studied environments, e.g., vaccination games. We discuss the interesting implications of our results for these environments.
Identifying Finite Mixtures of Nonparametric Product Distributions and Causal Inference of Confounders
Venue: arXiv cs.LG 2013
Year: 2013

We propose a kernel method to identify finite mixtures of nonparametric product distributions. It is based on a Hilbert space embedding of the joint distribution. The rank of the constructed tensor is equal to the number of mixture components. We present an algorithm to recover the components by partitioning the data points into clusters such that the variables are jointly conditionally independent given the cluster. This method can be used to identify finite confounders.
On MAP Inference by MWSS on Perfect Graphs
Venue: arXiv cs.AI 2013
Year: 2013

Finding the most likely (MAP) configuration of a Markov random field (MRF) is NP-hard in general. A promising, recent technique is to reduce the problem to finding a maximum weight stable set (MWSS) on a derived weighted graph, which if perfect, allows inference in polynomial time. We derive new results for this approach, including a general decomposition theorem for MRFs of any order and number of labels, extensions of results for binary pairwise models with submodular cost functions to higher order, and an exact characterization of which binary pairwise MRFs can be efficiently solved with this method. This defines the power of the approach on this class of models, improves our toolbox and expands the range of tractable models.
Active Learning with Expert Advice
Venue: arXiv cs.LG 2013
Year: 2013

Conventional learning with expert advice methods assumes a learner is always receiving the outcome (e.g., class labels) of every incoming training instance at the end of each trial. In real applications, acquiring the outcome from oracle can be costly or time consuming. In this paper, we address a new problem of active learning with expert advice, where the outcome of an instance is disclosed only when it is requested by the online learner. Our goal is to learn an accurate prediction model by asking the oracle the number of questions as small as possible. To address this challenge, we propose a framework of active forecasters for online active learning with expert advice, which attempts to extend two regular forecasters, i.e., Exponentially Weighted Average Forecaster and Greedy Forecaster, to tackle the task of active learning with expert advice. We prove that the proposed algorithms satisfy the Hannan consistency under some proper assumptions, and validate the efficacy of our technique by an extensive set of experiments.
Accurate Profiling of Microbial Communities from Massively Parallel Sequencing using Convex Optimization
Venue: arXiv cs.CE 2013
Year: 2013

We describe the Microbial Community Reconstruction ({\bf MCR}) Problem, which is fundamental for microbiome analysis. In this problem, the goal is to reconstruct the identity and frequency of species comprising a microbial community, using short sequence reads from Massively Parallel Sequencing (MPS) data obtained for specified genomic regions. We formulate the problem mathematically as a convex optimization problem and provide sufficient conditions for identifiability, namely the ability to reconstruct species identity and frequency correctly when the data size (number of reads) grows to infinity. We discuss different metrics for assessing the quality of the reconstructed solution, including a novel phylogenetically-aware metric based on the Mahalanobis distance, and give upper-bounds on the reconstruction error for a finite number of reads under different metrics. We propose a scalable divide-and-conquer algorithm for the problem using convex optimization, which enables us to handle large problems (with $\sim10^6$ species). We show using numerical simulations that for realistic scenarios, where the microbial communities are sparse, our algorithm gives solutions with high accuracy, both in terms of obtaining accurate frequency, and in terms of species phylogenetic resolution.
Kaczmarz Algorithm with Soft Constraints for User Interface Layout
Venue: arXiv cs.NA 2013
Year: 2013

The Kaczmarz method is an iterative method for solving large systems of equations that projects iterates orthogonally onto the solution space of each equation. In contrast to direct methods such as Gaussian elimination or QR-factorization, this algorithm is efficient for problems with sparse matrices, as they appear in constraint-based user interface (UI) layout specifications. However, the Kaczmarz method as described in the literature has its limitations: it considers only equality constraints and does not support soft constraints, which makes it inapplicable to the UI layout problem. In this paper we extend the Kaczmarz method for solving specifications containing soft constraints, using the prioritized IIS detection algorithm. Furthermore, the performance and convergence of the proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that these methods offer improvements in performance over standard methods like Matlab's LINPROG, a well-known efficient linear programming solver.
Social Business Transformation through Gamification
Venue: arXiv cs.CY 2013
Year: 2013

Being an emerging business practice, gamification is going to the mainstream to enable and transform social business initiatives across enterprises. With the consistent focus on customer behavior and experience, there is a paradigm shift in thinking about how Gamification and Social initiatives together help to increase the engagement level of knowledge worker, yielding better business results. Business scenarios for gamification are wide spread ranging from customer service and support to communities and collaboration. The Paper discusses the characteristics & mechanism to learn from games that are important for businesses to understand and apply. It also gives insights on gamification trends, real-world business challenges and also describes on how game thinking can revolutionize the business and create an engaging experience.
Establishing digital molecular communications in blood vessels
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we propose a solution for transmitting digital information within the cardiocirculatory system. In particular, we make use of a channel delivering burst of molecules, emitted by mobile transmitters, which diffuse in the blood towards fixed receivers, that are attached to the vessel walls. This communication scheme has been inspired by the real signaling between platelets and endothelial cells, the behavior of which has been investigated experimentally. We thus believe that our proposal can be successfully deployed in living bodies. On the basis of the results achieved through simulations on the communication system capabilities, we propose a simple but effective receiver scheme, and we outline the future research directions.
Propagating Regular Counting Constraints
Venue: arXiv cs.AI 2013
Year: 2013

Constraints over finite sequences of variables are ubiquitous in sequencing and timetabling. Moreover, the wide variety of such constraints in practical applications led to general modelling techniques and generic propagation algorithms, often based on deterministic finite automata (DFA) and their extensions. We consider counter-DFAs (cDFA), which provide concise models for regular counting constraints, that is constraints over the number of times a regular-language pattern occurs in a sequence. We show how to enforce domain consistency in polynomial time for atmost and atleast regular counting constraints based on the frequent case of a cDFA with only accepting states and a single counter that can be incremented by transitions. We also prove that the satisfaction of exact regular counting constraints is NP-hard and indicate that an incomplete algorithm for exact regular counting constraints is faster and provides more pruning than the existing propagator from [3]. Regular counting constraints are closely related to the CostRegular constraint but contribute both a natural abstraction and some computational advantages.
Evaluating Link-Based Techniques for Detecting Fake Pharmacy Websites
Venue: arXiv cs.CY 2013
Year: 2013

Fake online pharmacies have become increasingly pervasive, constituting over 90% of online pharmacy websites. There is a need for fake website detection techniques capable of identifying fake online pharmacy websites with a high degree of accuracy. In this study, we compared several well-known link-based detection techniques on a large-scale test bed with the hyperlink graph encompassing over 80 million links between 15.5 million web pages, including 1.2 million known legitimate and fake pharmacy pages. We found that the QoC and QoL class propagation algorithms achieved an accuracy of over 90% on our dataset. The results revealed that algorithms that incorporate dual class propagation as well as inlink and outlink information, on page-level or site-level graphs, are better suited for detecting fake pharmacy websites. In addition, site-level analysis yielded significantly better results than page-level analysis for most algorithms evaluated.
Small Polynomial Time Universal Petri Nets
Venue: arXiv cs.CC 2013
Year: 2013

The time complexity of the presented in 2013 by the author small universal Petri nets with the pairs of places/transitions numbers (14,42) and (14,29) was estimated as exponential. In the present paper, it is shown, that their slight modification and interpretation as timed Petri nets with multichannel transitions, introduced by the author in 1991, allows obtaining polynomial time complexity. The modification concerns using only inhibitor arcs to control transitions' firing in multiple instances and employing an inverse control flow represented by moving zero. Thus, small universal Petri nets are efficient that justifies their application as models of high performance computations.
An Application of Backpropagation Artificial Neural Network Method for Measuring The Severity of Osteoarthritis
Venue: arXiv cs.NE 2013
Year: 2013

The examination of Osteoarthritis disease through X-ray by rheumatology can be classified into four grade of severity. This paper discusses about the application of artificial neural network backpropagation method for measuring the severity of the disease, where the observed X-ray range from wrist to fingers. The main procedures of system in this paper is divided into three, which are image processing, feature extraction, and artificial neural network process. First, an X-ray image digital (200x150 pixels and greyscale) will be thresholded, then extracted features based on probabilistic values of the color intensity of seven bit quantization result, and statistical textures. That feature values then will be normalizing to interval [0.1, 0.9], and then the result would be processing on backpropagation artificial neural network system as input to determine the severity of disease from an X-ray had input before it. From testing with learning rate 0.3, momentum 0.4, hidden units five pieces and about 132 feature vectors, this system had had a level of accuracy of 100% for learning data, 80% for learning and non-learning data, and 66.6% for non-learning data
Parsing methods streamlined
Venue: arXiv cs.FL 2013
Year: 2013

This paper has the goals (1) of unifying top-down parsing with shift-reduce parsing to yield a single simple and consistent framework, and (2) of producing provably correct parsing methods, deterministic as well as tabular ones, for extended context-free grammars (EBNF) represented as state-transition networks. Departing from the traditional way of presenting as independent algorithms the deterministic bottom-up LR(1), the top-down LL(1) and the general tabular (Earley) parsers, we unify them in a coherent minimalist framework. We present a simple general construction method for EBNF ELR(1) parsers, where the new category of convergence conflicts is added to the classical shift-reduce and reduce-reduce conflicts; we prove its correctness and show two implementations by deterministic push-down machines and by vector-stack machines, the latter to be also used for Earley parsers. Then the Beatty's theoretical characterization of LL(1) grammars is adapted to derive the extended ELL(1 parsing method, first by minimizing the ELR(1) parser and then by simplifying its state information. Through using the same notations in the ELR(1) case, the extended Earley parser is obtained. Since all the parsers operate on compatible representations, it is feasible to combine them into mixed mode algorithms.