OpenRaiser/Intern-Atlas huggingface dataset:
Économie des biens immatériels - Economics of Intangible Goods
Venue: arXiv cs.OH 2012
Year: 2012

We introduce a new economic system suited for Intangible Goods ({\sc ig}). We argue that such system can now be implemented in the real world using advance technics in distributed network computing and cryptography. The specification of the so called \net{} is presented. To Limit the number of financial transactions, the system is forced to define its own currency, with many benefits. The new "cup" currency, extended worldwide, is dedicated to {\sc ig}, available only for person-to-person trading, protected from speculation and adapted for tax recovery with no additional computation. Those nices features makes the \net{} a new democratic tool, fixing specific issues in {\sc ig} trading and reviving a whole domain activity. We emphasis on the fact that all proposed documentation, algorithm, program in any language related to this proposal shall be open-source without any possibility to post any patent of any sort on the system or subsystem. This new trading model should be considered as a pure intellectual construction, like parts of Mathematics and then belongs to nobody or everybody, like $1+1=2$. Next step will be to test, validate the security of various implementations details, and to ask for legal rules adaptations. The first draft paper is written in French language and posted to arXiv.org and hal.archive-ouverte.fr . We expect to provide an English translation before Christmas.
Joint Cache Partition and Job Assignment on Multi-Core Processors
Venue: arXiv cs.DS 2012
Year: 2012

Multicore shared cache processors pose a challenge for designers of embedded systems who try to achieve minimal and predictable execution time of workloads consisting of several jobs. To address this challenge the cache is statically partitioned among the cores and the jobs are assigned to the cores so as to minimize the makespan. Several heuristic algorithms have been proposed that jointly decide how to partition the cache among the cores and assign the jobs. We initiate a theoretical study of this problem which we call the joint cache partition and job assignment problem. By a careful analysis of the possible cache partitions we obtain a constant approximation algorithm for this problem. For some practical special cases we obtain a 2-approximation algorithm, and show how to improve the approximation factor even further by allowing the algorithm to use additional cache. We also study possible improvements that can be obtained by allowing dynamic cache partitions and dynamic job assignments. We define a natural special case of the well known scheduling problem on unrelated machines in which machines are ordered by "strength". Our joint cache partition and job assignment problem generalizes this scheduling problem which we think is of independent interest. We give a polynomial time algorithm for this scheduling problem for instances obtained by fixing the cache partition in a practical case of the joint cache partition and job assignment problem where job loads are step functions.
NP-Completeness of deciding the feasibility of Linear Equations over binary-variables with coefficients and constants that are 0, 1, or -1
Venue: arXiv cs.CC 2012
Year: 2012

We convert, within polynomial-time and sequential processing, NP-Complete Problems into a problem of deciding feasibility of a given system S of linear equations with constants and coefficients of binary-variables that are 0, 1, or -1. S is feasible, if and only if, the NP-Complete problem has a feasible solution. We show separate polynomial-time conversions to S, from the SUBSET-SUM and 3-SAT problems, both of which are NP-Complete. The number of equations and variables in S is bounded by a polynomial function of the size of the NP-Complete problem, showing that deciding the feasibility of S is strongly-NP-Complete. We also show how to apply the approach used for the SUBSET-SUM problem to decide the feasibility of Integer Linear Programs, as it involves reducing the coefficient-magnitudes of variables to the logarithm of their initial values, though the number of variables and equations are increased.
A Biologically Realistic Model of Saccadic Eye Control with Probabilistic Population Codes
Venue: arXiv cs.NE 2012
Year: 2012

The posterior parietal cortex is believed to direct eye movements, especially in regards to target tracking tasks, and a number of debates exist over the precise nature of the computations performed by the parietal cortex, with each side supported by different sets of biological evidence. In this paper I will present my model which navigates a course between some of these debates, towards the end of presenting a model which can explain some of the competing interpretations among the data sets. In particular, rather than assuming that proprioception or efference copies form the key source of information for computing eye position information, I use a biological plausible implementation of a Kalman filter to optimally combine the two signals, and a simple gain control mechanism in order to accommodate the latency of the proprioceptive signal. Fitting within the Bayesian brain hypothesis, the result is a Bayes optimal solution to the eye control problem, with a range of data supporting claims of biological plausibility.
An example illustrating the imprecision of the efficient approach for diagnosis of Petri nets via integer linear programming
Venue: arXiv cs.SY 2012
Year: 2012

This document demonstrates that the efficient approach for diagnosis of Petri nets via integer linear programming may be unable to detect a fault even if the system is diagnosable.
A Fast Iterative Algorithm for Recovery of Sparse Signals from One-Bit Quantized Measurements
Venue: arXiv cs.IT 2012
Year: 2012

This paper considers the problem of reconstructing sparse or compressible signals from one-bit quantized measurements. We study a new method that uses a log-sum penalty function, also referred to as the Gaussian entropy, for sparse signal recovery. Also, in the proposed method, sigmoid functions are introduced to quantify the consistency between the acquired one-bit quantized data and the reconstructed measurements. A fast iterative algorithm is developed by iteratively minimizing a convex surrogate function that bounds the original objective function, which leads to an iterative reweighted process that alternates between estimating the sparse signal and refining the weights of the surrogate function. Connections between the proposed algorithm and other existing methods are discussed. Numerical results are provided to illustrate the effectiveness of the proposed algorithm.
Distributed Formation of Balanced and Bistochastic Weighted Diagraphs in Multi-Agent Systems
Venue: arXiv cs.MA 2012
Year: 2012

Consensus strategies find a variety of applications in distributed coordination and decision making in multi-agent systems. In particular, average consensus plays a key role in a number of applications and is closely associated with two classes of digraphs, weight-balanced (for continuous-time systems) and bistochastic (for discrete-time systems). A weighted digraph is called balanced if, for each node, the sum of the weights of the edges outgoing from that node is equal to the sum of the weights of the edges incoming to that node. In addition, a weight-balanced digraph is bistochastic if all weights are nonnegative and, for each node, the sum of weights of edges incoming to that node and the sum of the weights of edges out-going from that node is unity; this implies that the corresponding weight matrix is column and row stochastic (i.e., doubly stochastic). We propose two distributed algorithms: one solves the weight-balance problem and the other solves the bistochastic matrix formation problem for a distributed system whose components (nodes) can exchange information via interconnection links (edges) that form an arbitrary, possibly directed, strongly connected communication topology (digraph). Both distributed algorithms achieve their goals asymptotically and operate iteratively by having each node adapt the (nonnegative) weights on its outgoing edges based on the weights of its incoming links (i.e., based on purely local information). We also provide examples to illustrate the operation, performance, and potential advantages of the proposed algorithms.
Semantic integration and analysis of clinical data
Venue: arXiv cs.DB 2012
Year: 2012

There is a growing need to semantically process and integrate clinical data from different sources for Clinical Data Management and Clinical Decision Support in the healthcare IT industry. In the clinical practice domain, the semantic gap between clinical information systems and domain ontologies is quite often difficult to bridge in one step. In this paper, we report our experience in using a two-step formalization approach to formalize clinical data, i.e. from database schemas to local formalisms and from local formalisms to domain (unifying) formalisms. We use N3 rules to explicitly and formally state the mapping from local ontologies to domain ontologies. The resulting data expressed in domain formalisms can be integrated and analyzed, though originating from very distinct sources. Practices of applying the two-step approach in the infectious disorders and cancer domains are introduced.
Random Sequences Based on the Divisor Pairs Function
Venue: arXiv cs.CR 2012
Year: 2012

This paper investigates the randomness properties of a function of the divisor pairs of a natural number. This function, the antecedents of which go to very ancient times, has randomness properties that can find applications in cryptography, key distribution, and other problems of computer science. It is shown that the function is aperiodic and it has excellent autocorrelation properties.
A Primarily Survey on Energy Efficiency in Cloud and Distributed Computing Systems
Venue: arXiv cs.DC 2012
Year: 2012

A survey of available techniques in hardware to reduce energy consumption
Optimal Lempel-Ziv based lossy compression for memoryless data: how to make the right mistakes
Venue: arXiv cs.IT 2012
Year: 2012

Compression refers to encoding data using bits, so that the representation uses as few bits as possible. Compression could be lossless: i.e. encoded data can be recovered exactly from its representation) or lossy where the data is compressed more than the lossless case, but can still be recovered to within prespecified distortion metric. In this paper, we prove the optimality of Codelet Parsing, a quasi-linear time algorithm for lossy compression of sequences of bits that are independently and identically distributed (\iid) and Hamming distortion. Codelet Parsing extends the lossless Lempel Ziv algorithm to the lossy case---a task that has been a focus of the source coding literature for better part of two decades now. Given \iid sequences $\x$, the expected length of the shortest lossy representation such that $\x$ can be reconstructed to within distortion $\dist$ is given by the rate distortion function, $\rd$. We prove the optimality of the Codelet Parsing algorithm for lossy compression of memoryless bit sequences. It splits the input sequence naturally into phrases, representing each phrase by a codelet, a potentially distorted phrase of the same length. The codelets in the lossy representation of a length-$n$ string ${\x}$ have length roughly $(\log n)/\rd$, and like the lossless Lempel Ziv algorithm, Codelet Parsing constructs codebooks logarithmic in the sequence length.
An Efficient Message-Passing Algorithm for the M-Best MAP Problem
Venue: arXiv cs.AI 2012
Year: 2012

Much effort has been directed at algorithms for obtaining the highest probability configuration in a probabilistic random field model known as the maximum a posteriori (MAP) inference problem. In many situations, one could benefit from having not just a single solution, but the top M most probable solutions known as the M-Best MAP problem. In this paper, we propose an efficient message-passing based algorithm for solving the M-Best MAP problem. Specifically, our algorithm solves the recently proposed Linear Programming (LP) formulation of M-Best MAP [7], while being orders of magnitude faster than a generic LP-solver. Our approach relies on studying a particular partial Lagrangian relaxation of the M-Best MAP LP which exposes a natural combinatorial structure of the problem that we exploit.
Causal Inference by Surrogate Experiments: z-Identifiability
Venue: arXiv cs.AI 2012
Year: 2012

We address the problem of estimating the effect of intervening on a set of variables X from experiments on a different set, Z, that is more accessible to manipulation. This problem, which we call z-identifiability, reduces to ordinary identifiability when Z = empty and, like the latter, can be given syntactic characterization using the do-calculus [Pearl, 1995; 2000]. We provide a graphical necessary and sufficient condition for z-identifiability for arbitrary sets X,Z, and Y (the outcomes). We further develop a complete algorithm for computing the causal effect of X on Y using information provided by experiments on Z. Finally, we use our results to prove completeness of do-calculus relative to z-identifiability, a result that does not follow from completeness relative to ordinary identifiability.
Variational Dual-Tree Framework for Large-Scale Transition Matrix Approximation
Venue: arXiv cs.LG 2012
Year: 2012

In recent years, non-parametric methods utilizing random walks on graphs have been used to solve a wide range of machine learning problems, but in their simplest form they do not scale well due to the quadratic complexity. In this paper, a new dual-tree based variational approach for approximating the transition matrix and efficiently performing the random walk is proposed. The approach exploits a connection between kernel density estimation, mixture modeling, and random walk on graphs in an optimization of the transition matrix for the data graph that ties together edge transitions probabilities that are similar. Compared to the de facto standard approximation method based on k-nearestneighbors, we demonstrate order of magnitudes speedup without sacrificing accuracy for Label Propagation tasks on benchmark data sets in semi-supervised learning.
Learning to Rank With Bregman Divergences and Monotone Retargeting
Venue: arXiv cs.LG 2012
Year: 2012

This paper introduces a novel approach for learning to rank (LETOR) based on the notion of monotone retargeting. It involves minimizing a divergence between all monotonic increasing transformations of the training scores and a parameterized prediction function. The minimization is both over the transformations as well as over the parameters. It is applied to Bregman divergences, a large class of "distance like" functions that were recently shown to be the unique class that is statistically consistent with the normalized discounted gain (NDCG) criterion [19]. The algorithm uses alternating projection style updates, in which one set of simultaneous projections can be computed independent of the Bregman divergence and the other reduces to parameter estimation of a generalized linear model. This results in easily implemented, efficiently parallelizable algorithm for the LETOR task that enjoys global optimum guarantees under mild conditions. We present empirical results on benchmark datasets showing that this approach can outperform the state of the art NDCG consistent techniques.
Weighted Sets of Probabilities and MinimaxWeighted Expected Regret: New Approaches for Representing Uncertainty and Making Decisions
Venue: arXiv cs.GT 2012
Year: 2012

We consider a setting where an agent's uncertainty is represented by a set of probability measures, rather than a single measure. Measure-bymeasure updating of such a set of measures upon acquiring new information is well-known to suffer from problems; agents are not always able to learn appropriately. To deal with these problems, we propose using weighted sets of probabilities: a representation where each measure is associated with a weight, which denotes its significance. We describe a natural approach to updating in such a situation and a natural approach to determining the weights. We then show how this representation can be used in decision-making, by modifying a standard approach to decision making-minimizing expected regret-to obtain minimax weighted expected regret (MWER).We provide an axiomatization that characterizes preferences induced by MWER both in the static and dynamic case.
Semantic Understanding of Professional Soccer Commentaries
Venue: arXiv cs.CL 2012
Year: 2012

This paper presents a novel approach to the problem of semantic parsing via learning the correspondences between complex sentences and rich sets of events. Our main intuition is that correct correspondences tend to occur more frequently. Our model benefits from a discriminative notion of similarity to learn the correspondence between sentence and an event and a ranking machinery that scores the popularity of each correspondence. Our method can discover a group of events (called macro-events) that best describes a sentence. We evaluate our method on our novel dataset of professional soccer commentaries. The empirical results show that our method significantly outperforms the state-of-theart.
Exploiting compositionality to explore a large space of model structures
Venue: arXiv cs.LG 2012
Year: 2012

The recent proliferation of richly structured probabilistic models raises the question of how to automatically determine an appropriate model for a dataset. We investigate this question for a space of matrix decomposition models which can express a variety of widely used models from unsupervised learning. To enable model selection, we organize these models into a context-free grammar which generates a wide variety of structures through the compositional application of a few simple rules. We use our grammar to generically and efficiently infer latent components and estimate predictive likelihood for nearly 2500 structures using a small toolbox of reusable algorithms. Using a greedy search over our grammar, we automatically choose the decomposition structure from raw data by evaluating only a small fraction of all models. The proposed method typically finds the correct structure for synthetic data and backs off gracefully to simpler models under heavy noise. It learns sensible structures for datasets as diverse as image patches, motion capture, 20 Questions, and U.S. Senate votes, all using exactly the same code.
Mechanism Design for Cost Optimal PAC Learning in the Presence of Strategic Noisy Annotators
Venue: arXiv cs.LG 2012
Year: 2012

We consider the problem of Probably Approximate Correct (PAC) learning of a binary classifier from noisy labeled examples acquired from multiple annotators (each characterized by a respective classification noise rate). First, we consider the complete information scenario, where the learner knows the noise rates of all the annotators. For this scenario, we derive sample complexity bound for the Minimum Disagreement Algorithm (MDA) on the number of labeled examples to be obtained from each annotator. Next, we consider the incomplete information scenario, where each annotator is strategic and holds the respective noise rate as a private information. For this scenario, we design a cost optimal procurement auction mechanism along the lines of Myerson's optimal auction design framework in a non-trivial manner. This mechanism satisfies incentive compatibility property, thereby facilitating the learner to elicit true noise rates of all the annotators.
Uniform Solution Sampling Using a Constraint Solver As an Oracle
Venue: arXiv cs.AI 2012
Year: 2012

We consider the problem of sampling from solutions defined by a set of hard constraints on a combinatorial space. We propose a new sampling technique that, while enforcing a uniform exploration of the search space, leverages the reasoning power of a systematic constraint solver in a black-box scheme. We present a series of challenging domains, such as energy barriers and highly asymmetric spaces, that reveal the difficulties introduced by hard constraints. We demonstrate that standard approaches such as Simulated Annealing and Gibbs Sampling are greatly affected, while our new technique can overcome many of these difficulties. Finally, we show that our sampling scheme naturally defines a new approximate model counting technique, which we empirically show to be very accurate on a range of benchmark problems.
Incentive Decision Processes
Venue: arXiv cs.GT 2012
Year: 2012

We consider Incentive Decision Processes, where a principal seeks to reduce its costs due to another agent's behavior, by offering incentives to the agent for alternate behavior. We focus on the case where a principal interacts with a greedy agent whose preferences are hidden and static. Though IDPs can be directly modeled as partially observable Markov decision processes (POMDP), we show that it is possible to directly reduce or approximate the IDP as a polynomially-sized MDP: when this representation is approximate, we prove the resulting policy is boundedly-optimal for the original IDP. Our empirical simulations demonstrate the performance benefit of our algorithms over simpler approaches, and also demonstrate that our approximate representation results in a significantly faster algorithm whose performance is extremely close to the optimal policy for the original IDP.
A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models
Venue: arXiv cs.AI 2012
Year: 2012

We study the problem of complexity estimation in the context of parallelizing an advanced Branch and Bound-type algorithm over graphical models. The algorithm's pruning power makes load balancing, one crucial element of every distributed system, very challenging. We propose using a statistical regression model to identify and tackle disproportionally complex parallel subproblems, the cause of load imbalance, ahead of time. The proposed model is evaluated and analyzed on various levels and shown to yield robust predictions. We then demonstrate its effectiveness for load balancing in practice.
Hilbert Space Embeddings of POMDPs
Venue: arXiv cs.LG 2012
Year: 2012

A nonparametric approach for policy learning for POMDPs is proposed. The approach represents distributions over the states, observations, and actions as embeddings in feature spaces, which are reproducing kernel Hilbert spaces. Distributions over states given the observations are obtained by applying the kernel Bayes' rule to these distribution embeddings. Policies and value functions are defined on the feature space over states, which leads to a feature space expression for the Bellman equation. Value iteration may then be used to estimate the optimal value function and associated policy. Experimental results confirm that the correct policy is learned using the feature space representation.
Value Function Approximation in Noisy Environments Using Locally Smoothed Regularized Approximate Linear Programs
Venue: arXiv cs.LG 2012
Year: 2012

Recently, Petrik et al. demonstrated that L1Regularized Approximate Linear Programming (RALP) could produce value functions and policies which compared favorably to established linear value function approximation techniques like LSPI. RALP's success primarily stems from the ability to solve the feature selection and value function approximation steps simultaneously. RALP's performance guarantees become looser if sampled next states are used. For very noisy domains, RALP requires an accurate model rather than samples, which can be unrealistic in some practical scenarios. In this paper, we demonstrate this weakness, and then introduce Locally Smoothed L1-Regularized Approximate Linear Programming (LS-RALP). We demonstrate that LS-RALP mitigates inaccuracies stemming from noise even without an accurate model. We show that, given some smoothness assumptions, as the number of samples increases, error from noise approaches zero, and provide experimental examples of LS-RALP's success on common reinforcement learning benchmark problems.