OpenRaiser/Intern-Atlas huggingface dataset:
A Generic Checkpoint-Restart Mechanism for Virtual Machines
Venue: arXiv cs.OS 2012
Year: 2012

It is common today to deploy complex software inside a virtual machine (VM). Snapshots provide rapid deployment, migration between hosts, dependability (fault tolerance), and security (insulating a guest VM from the host). Yet, for each virtual machine, the code for snapshots is laboriously developed on a per-VM basis. This work demonstrates a generic checkpoint-restart mechanism for virtual machines. The mechanism is based on a plugin on top of an unmodified user-space checkpoint-restart package, DMTCP. Checkpoint-restart is demonstrated for three virtual machines: Lguest, user-space QEMU, and KVM/QEMU. The plugins for Lguest and KVM/QEMU require just 200 lines of code. The Lguest kernel driver API is augmented by 40 lines of code. DMTCP checkpoints user-space QEMU without any new code. KVM/QEMU, user-space QEMU, and DMTCP need no modification. The design benefits from other DMTCP features and plugins. Experiments demonstrate checkpoint and restart in 0.2 seconds using forked checkpointing, mmap-based fast-restart, and incremental Btrfs-based snapshots.
IK-PSO, PSO Inverse Kinematics Solver with Application to Biped Gait Generation
Venue: arXiv cs.RO 2012
Year: 2012

This paper describes a new approach allowing the generation of a simplified Biped gait. This approach combines a classical dynamic modeling with an inverse kinematics' solver based on particle swarm optimization, PSO. First, an inverted pendulum, IP, is used to obtain a simplified dynamic model of the robot and to compute the target position of a key point in biped locomotion, the Centre Of Mass, COM. The proposed algorithm, called IK-PSO, Inverse Kinematics PSO, returns and inverse kinematics solution corresponding to that COM respecting the joints constraints. In This paper the inertia weight PSO variant is used to generate a possible solution according to the stability based fitness function and a set of joints motions constraints. The method is applied with success to a leg motion generation. Since based on a pre-calculated COM, that satisfied the biped stability, the proposal allowed also to plan a walk with application on a small size biped robot.
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
Venue: arXiv cs.DS 2012
Year: 2012

Kolla and Tulsiani [KT07,Kolla11} and Arora, Barak and Steurer [ABS10] introduced the technique of subspace enumeration, which gives approximation algorithms for graph problems such as unique games and small set expansion; the running time of such algorithms is exponential in the threshold-rank of the graph. Guruswami and Sinop [GS11,GS12], and Barak, Raghavendra, and Steurer [BRS11] developed an alternative approach to the design of approximation algorithms for graphs of bounded threshold-rank, based on semidefinite programming relaxations in the Lassere hierarchy and on novel rounding techniques. These algorithms are faster than the ones based on subspace enumeration and work on a broad class of problems. In this paper we develop a third approach to the design of such algorithms. We show, constructively, that graphs of bounded threshold-rank satisfy a weak Szemeredi regularity lemma analogous to the one proved by Frieze and Kannan [FK99] for dense graphs. The existence of efficient approximation algorithms is then a consequence of the regularity lemma, as shown by Frieze and Kannan. Applying our method to the Max Cut problem, we devise an algorithm that is faster than all previous algorithms, and is easier to describe and analyze.
Soft Constraint Logic Programming for Electric Vehicle Travel Optimization
Venue: arXiv cs.AI 2012
Year: 2012

Soft Constraint Logic Programming is a natural and flexible declarative programming formalism, which allows to model and solve real-life problems involving constraints of different types. In this paper, after providing a slightly more general and elegant presentation of the framework, we show how we can apply it to the e-mobility problem of coordinating electric vehicles in order to overcome both energetic and temporal constraints and so to reduce their running cost. In particular, we focus on the journey optimization sub-problem, considering sequences of trips from a user's appointment to another one. Solutions provide the best alternatives in terms of time and energy consumption, including route sequences and possible charging events.
A Data Warehouse Design for a Typical University Information System
Venue: arXiv cs.DB 2012
Year: 2012

Presently, large enterprises rely on database systems to manage their data and information. These databases are useful for conducting daily business transactions. However, the tight competition in the marketplace has led to the concept of data mining in which data are analyzed to derive effective business strategies and discover better ways in carrying out business. In order to perform data mining, regular databases must be converted into what so called informational databases also known as data warehouse. This paper presents a design model for building data warehouse for a typical university information system. It is based on transforming an operational database into an informational warehouse useful for decision makers to conduct data analysis, predication, and forecasting. The proposed model is based on four stages of data migration: Data extraction, data cleansing, data transforming, and data indexing and loading. The complete system is implemented under MS Access 2010 and is meant to serve as a repository of data for data mining operations.
Collaborative Competitive filtering II: Optimal Recommendation and Collaborative Games
Venue: arXiv cs.IR 2012
Year: 2012

Recommender systems have emerged as a new weapon to help online firms to realize many of their strategic goals (e.g., to improve sales, revenue, customer experience etc.). However, many existing techniques commonly approach these goals by seeking to recover preference (e.g., estimating ratings) in a matrix completion framework. This paper aims to bridge this significant gap between the clearly-defined strategic objectives and the not-so-well-justified proxy. We show it is advantageous to think of a recommender system as an analogy to a monopoly economic market with the system as the sole seller, users as the buyers and items as the goods. This new perspective motivates a game-theoretic formulation for recommendation that enables us to identify the optimal recommendation policy by explicit optimizing certain strategic goals. In this paper, we revisit and extend our prior work, the Collaborative-Competitive Filtering preference model, towards a game-theoretic framework. The proposed framework consists of two components. First, a conditional preference model that characterizes how a user would respond to a recommendation action; Second, knowing in advance how the user would respond, how a recommender system should act (i.e., recommend) strategically to maximize its goals. We show how objectives such as click-through rate, sales revenue and consumption diversity can be optimized explicitly in this framework. Experiments are conducted on a commercial recommender system and demonstrate promising results.
Fast and Robust Linear Motion Deblurring
Venue: arXiv cs.CV 2012
Year: 2012

We investigate efficient algorithmic realisations for robust deconvolution of grey-value images with known space-invariant point-spread function, with emphasis on 1D motion blur scenarios. The goal is to make deconvolution suitable as preprocessing step in automated image processing environments with tight time constraints. Candidate deconvolution methods are selected for their restoration quality, robustness and efficiency. Evaluation of restoration quality and robustness on synthetic and real-world test images leads us to focus on a combination of Wiener filtering with few iterations of robust and regularised Richardson-Lucy deconvolution. We discuss algorithmic optimisations for specific scenarios. In the case of uniform linear motion blur in coordinate direction, it is possible to achieve real-time performance (less than 50 ms) in single-threaded CPU computation on images of $256\times256$ pixels. For more general space-invariant blur settings, still favourable computation times are obtained. Exemplary parallel implementations demonstrate that the proposed method also achieves real-time performance for general 1D motion blurs in a multi-threaded CPU setting, and for general 2D blurs on a GPU.
Data traffic load balancing and QoS in IEEE 802.11 network: Experimental study of the signal strength effect
Venue: arXiv cs.NI 2012
Year: 2012

The performances of multimedia applications built on wireless systems depend on bandwidth availability that might heavily affect the quality of service. The IEEE 802.11 standards do not provide performed mechanism for bandwidth management through data load distribution among different APs of the network. Then, an AP can be heavily overloaded causing throughput degradation. Load Balancing Algorithms (LBAs) was been considered as one of the attractive solution to share the traffic through the available access points bandwidths. However, applying the load balancing algorithm and shifting a mobile connection from an access point to another without considering the received signal strength indicator of the concerned APs might causes worst communication performances. This paper is a contribution to check the performance's limits of the LBA algorithm through experimental evaluation of communication metrics for MPEG-4 video transmission over IEEE 802.11 network. Then, the paper focuses on the proposition of a new LBA algorithm structure with the consideration of the RSS level.
Distributed MIMO coding scheme with low decoding complexity for future mobile TV broadcasting
Venue: arXiv cs.NI 2012
Year: 2012

A novel distributed space-time block code (STBC) for the next generation mobile TV broadcasting is proposed. The new code provides efficient performance within a wide range of power imbalance showing strong adaptivity to the single frequency network (SFN) broadcasting deployments. The new code outperforms existing STBCs with equivalent decoding complexity and approaches those with much higher complexities.
Active Collaborative Filtering
Venue: arXiv cs.IR 2012
Year: 2012

Collaborative filtering (CF) allows the preferences of multiple users to be pooled to make recommendations regarding unseen products. We consider in this paper the problem of online and interactive CF: given the current ratings associated with a user, what queries (new ratings) would most improve the quality of the recommendations made? We cast this terms of expected value of information (EVOI); but the online computational cost of computing optimal queries is prohibitive. We show how offline prototyping and computation of bounds on EVOI can be used to dramatically reduce the required online computation. The framework we develop is general, but we focus on derivations and empirical study in the specific case of the multiple-cause vector quantization model.
RSAED: Robust and Secure Aggregation of Encrypted Data in Wireless Sensor Networks
Venue: arXiv cs.CR 2012
Year: 2012

Recently, secure in-network aggregation in wireless sensor networks becomes a challenge issue, there is an extensive research on this area due to the large number of applications where the sensors are deployed and the security needs. In the last few years, aggregation of encrypted data has been proposed in order to maintain secrecy between the sensors and the sink, so the end-to-end data confidentiality is provided. However, the data integrity was not addressed. In this paper, we propose RSAED that allows integrity verification at intermediate nodes, ensures the base station to receive ciphertexts which come only from legitimate nodes and also improves the efficiency. Through implementation results, we evaluate our scheme using computation and communication overhead.
Structure-Based Causes and Explanations in the Independent Choice Logic
Venue: arXiv cs.AI 2012
Year: 2012

This paper is directed towards combining Pearl's structural-model approach to causal reasoning with high-level formalisms for reasoning about actions. More precisely, we present a combination of Pearl's structural-model approach with Poole's independent choice logic. We show how probabilistic theories in the independent choice logic can be mapped to probabilistic causal models. This mapping provides the independent choice logic with appealing concepts of causality and explanation from the structural-model approach. We illustrate this along Halpern and Pearl's sophisticated notions of actual cause, explanation, and partial explanation. This mapping also adds first-order modeling capabilities and explicit actions to the structural-model approach.
Probabilistic Reasoning about Actions in Nonmonotonic Causal Theories
Venue: arXiv cs.AI 2012
Year: 2012

We present the language {m P}{cal C}+ for probabilistic reasoning about actions, which is a generalization of the action language {cal C}+ that allows to deal with probabilistic as well as nondeterministic effects of actions. We define a formal semantics of {m P}{cal C}+ in terms of probabilistic transitions between sets of states. Using a concept of a history and its belief state, we then show how several important problems in reasoning about actions can be concisely formulated in our formalism.
Preference-based Graphic Models for Collaborative Filtering
Venue: arXiv cs.IR 2012
Year: 2012

Collaborative filtering is a very useful general technique for exploiting the preference patterns of a group of users to predict the utility of items to a particular user. Previous research has studied several probabilistic graphic models for collaborative filtering with promising results. However, while these models have succeeded in capturing the similarity among users and items in one way or the other, none of them has considered the fact that users with similar interests in items can have very different rating patterns; some users tend to assign a higher rating to all items than other users. In this paper, we propose and study of two new graphic models that address the distinction between user preferences and ratings. In one model, called the decoupled model, we introduce two different variables to decouple a users preferences FROM his ratings. IN the other, called the preference model, we model the orderings OF items preferred BY a USER, rather than the USERs numerical ratings of items. Empirical study over two datasets of movie ratings shows that appropriate modeling of the distinction between user preferences and ratings improves the performance substantially and consistently. Specifically, the proposed decoupled model outperforms all five existing approaches that we compare with significantly, but the preference model is not very successful. These results suggest that explicit modeling of the underlying user preferences is very important for collaborative filtering, but we can not afford ignoring the rating information completely.
Sufficient Dimensionality Reduction with Irrelevant Statistics
Venue: arXiv cs.LG 2012
Year: 2012

The problem of finding a reduced dimensionality representation of categorical variables while preserving their most relevant characteristics is fundamental for the analysis of complex data. Specifically, given a co-occurrence matrix of two variables, one often seeks a compact representation of one variable which preserves information about the other variable. We have recently introduced ``Sufficient Dimensionality Reduction' [GT-2003], a method that extracts continuous reduced dimensional features whose measurements (i.e., expectation values) capture maximal mutual information among the variables. However, such measurements often capture information that is irrelevant for a given task. Widely known examples are illumination conditions, which are irrelevant as features for face recognition, writing style which is irrelevant as a feature for content classification, and intonation which is irrelevant as a feature for speech recognition. Such irrelevance cannot be deduced apriori, since it depends on the details of the task, and is thus inherently ill defined in the purely unsupervised case. Separating relevant from irrelevant features can be achieved using additional side data that contains such irrelevant structures. This approach was taken in [CT-2002], extending the information bottleneck method, which uses clustering to compress the data. Here we use this side-information framework to identify features whose measurements are maximally informative for the original data set, but carry as little information as possible on a side data set. In statistical terms this can be understood as extracting statistics which are maximally sufficient for the original dataset, while simultaneously maximally ancillary for the side dataset. We formulate this tradeoff as a constrained optimization problem and characterize its solutions. We then derive a gradient descent algorithm for this problem, which is based on the Generalized Iterative Scaling method for finding maximum entropy distributions. The method is demonstrated on synthetic data, as well as on real face recognition datasets, and is shown to outperform standard methods such as oriented PCA.
Automated Analytic Asymptotic Evaluation of the Marginal Likelihood for Latent Models
Venue: arXiv cs.LG 2012
Year: 2012

We present and implement two algorithms for analytic asymptotic evaluation of the marginal likelihood of data given a Bayesian network with hidden nodes. As shown by previous work, this evaluation is particularly hard for latent Bayesian network models, namely networks that include hidden variables, where asymptotic approximation deviates from the standard BIC score. Our algorithms solve two central difficulties in asymptotic evaluation of marginal likelihood integrals, namely, evaluation of regular dimensionality drop for latent Bayesian network models and computation of non-standard approximation formulas for singular statistics for these models. The presented algorithms are implemented in Matlab and Maple and their usage is demonstrated for marginal likelihood approximations for Bayesian networks with hidden variables.
Decentralized Sensor Fusion With Distributed Particle Filters
Venue: arXiv cs.AI 2012
Year: 2012

This paper presents a scalable Bayesian technique for decentralized state estimation from multiple platforms in dynamic environments. As has long been recognized, centralized architectures impose severe scaling limitations for distributed systems due to the enormous communication overheads. We propose a strictly decentralized approach in which only nearby platforms exchange information. They do so through an interactive communication protocol aimed at maximizing information flow. Our approach is evaluated in the context of a distributed surveillance scenario that arises in a robotic system for playing the game of laser tag. Our results, both from simulation and using physical robots, illustrate an unprecedented scaling capability to large teams of vehicles.
Learning Generative Models of Similarity Matrices
Venue: arXiv cs.LG 2012
Year: 2012

We describe a probabilistic (generative) view of affinity matrices along with inference algorithms for a subclass of problems associated with data clustering. This probabilistic view is helpful in understanding different models and algorithms that are based on affinity functions OF the data. IN particular, we show how(greedy) inference FOR a specific probabilistic model IS equivalent TO the spectral clustering algorithm.It also provides a framework FOR developing new algorithms AND extended models. AS one CASE, we present new generative data clustering models that allow us TO infer the underlying distance measure suitable for the clustering problem at hand. These models seem to perform well in a larger class of problems for which other clustering algorithms (including spectral clustering) usually fail. Experimental evaluation was performed in a variety point data sets, showing excellent performance.
Learning Continuous Time Bayesian Networks
Venue: arXiv cs.LG 2012
Year: 2012

Continuous time Bayesian networks (CTBNs) describe structured stochastic processes with finitely many states that evolve over continuous time. A CTBN is a directed (possibly cyclic) dependency graph over a set of variables, each of which represents a finite state continuous time Markov process whose transition model is a function of its parents. We address the problem of learning parameters and structure of a CTBN from fully observed data. We define a conjugate prior for CTBNs, and show how it can be used both for Bayesian parameter estimation and as the basis of a Bayesian score for structure learning. Because acyclicity is not a constraint in CTBNs, we can show that the structure learning problem is significantly easier, both in theory and in practice, than structure learning for dynamic Bayesian networks (DBNs). Furthermore, as CTBNs can tailor the parameters and dependency structure to the different time granularities of the evolution of different variables, they can provide a better fit to continuous-time processes than DBNs with a fixed time granularity.
Practically Perfect
Venue: arXiv cs.AI 2012
Year: 2012

The property of perfectness plays an important role in the theory of Bayesian networks. First, the existence of perfect distributions for arbitrary sets of variables and directed acyclic graphs implies that various methods for reading independence from the structure of the graph (e.g., Pearl, 1988; Lauritzen, Dawid, Larsen & Leimer, 1990) are complete. Second, the asymptotic reliability of various search methods is guaranteed under the assumption that the generating distribution is perfect (e.g., Spirtes, Glymour & Scheines, 2000; Chickering & Meek, 2002). We provide a lower-bound on the probability of sampling a non-perfect distribution when using a fixed number of bits to represent the parameters of the Bayesian network. This bound approaches zero exponentially fast as one increases the number of bits used to represent the parameters. This result implies that perfect distributions with fixed-length representations exist. We also provide a lower-bound on the number of bits needed to guarantee that a distribution sampled from a uniform Dirichlet distribution is perfect with probability greater than 1/2. This result is useful for constructing randomized reductions for hardness proofs.
Efficiently Inducing Features of Conditional Random Fields
Venue: arXiv cs.LG 2012
Year: 2012

Conditional Random Fields (CRFs) are undirected graphical models, a special case of which correspond to conditionally-trained finite state machines. A key advantage of these models is their great flexibility to include a wide array of overlapping, multi-granularity, non-independent features of the input. In face of this freedom, an important question that remains is, what features should be used? This paper presents a feature induction method for CRFs. Founded on the principle of constructing only those feature conjunctions that significantly increase log-likelihood, the approach is based on that of Della Pietra et al [1997], but altered to work with conditional rather than joint probabilities, and with additional modifications for providing tractability specifically for a sequence model. In comparison with traditional approaches, automated feature induction offers both improved accuracy and more than an order of magnitude reduction in feature count; it enables the use of richer, higher-order Markov models, and offers more freedom to liberally guess about which atomic features may be relevant to a task. The induction method applies to linear-chain CRFs, as well as to more arbitrary CRF structures, also known as Relational Markov Networks [Taskar & Koller, 2002]. We present experimental results on a named entity extraction task.