OpenRaiser/Intern-Atlas huggingface dataset:
Clustered Bandits
Venue: arXiv cs.LG 2012
Year: 2012

We consider a multi-armed bandit setting that is inspired by real-world applications in e-commerce. In our setting, there are a few types of users, each with a specific response to the different arms. When a user enters the system, his type is unknown to the decision maker. The decision maker can either treat each user separately ignoring the previously observed users, or can attempt to take advantage of knowing that only few types exist and cluster the users according to their response to the arms. We devise algorithms that combine the usual exploration-exploitation tradeoff with clustering of users and demonstrate the value of clustering. In the process of developing algorithms for the clustered setting, we propose and analyze simple algorithms for the setup where a decision maker knows that a user belongs to one of few types, but does not know which one.
Designing Incoherent Dictionaries for Compressed Sensing: Algorithm Comparison
Venue: arXiv cs.IT 2012
Year: 2012

A new method presented for design of incoherent dictionaries.
On a Class of Discrete Memoryless Broadcast Interference Channels
Venue: arXiv cs.IT 2012
Year: 2012

We study a class of discrete memoryless broadcast interference channels (DM-BICs), where one of the broadcast receivers is subject to the interference from a point-to-point transmission. A general achievable rate region $\mathcal{R}$ based on rate splitting, superposition coding and binning at the broadcast transmitter and rate splitting at the interfering transmitter is derived. Under two partial order broadcast conditions {\em interference-oblivious less noisy} and {\em interference-cognizant less noisy}, a reduced form of $\mathcal{R}$ is shown to be equivalent to the region based on a simpler scheme that uses only superposition coding at the broadcast transmitter. Furthermore, the capacity regions of DM-BIC under the two partial order broadcast conditions are characterized respectively for the strong and very strong interference conditions.
Revisiting Timed Specification Theories: A Linear-Time Perspective
Venue: arXiv cs.SE 2012
Year: 2012

We consider the setting of component-based design for real-time systems with critical timing constraints. Based on our earlier work, we propose a compositional specification theory for timed automata with I/O distinction, which supports substitutive refinement. Our theory provides the operations of parallel composition for composing components at run-time, logical conjunction/disjunction for independent development, and quotient for incremental synthesis. The key novelty of our timed theory lies in a weakest congruence preserving safety as well as bounded liveness properties. We show that the congruence can be characterised by two linear-time semantics, timed-traces and timed-strategies, the latter of which is derived from a game-based interpretation of timed interaction.
Initiality for Typed Syntax and Semantics
Venue: arXiv cs.LO 2012
Year: 2012

We give an algebraic characterization of the syntax and semantics of a class of simply-typed languages, such as the language PCF: we characterize simply-typed binding syntax equipped with reduction rules via a universal property, namely as the initial object of some category. For this purpose, we employ techniques developed in two previous works: in [2], we model syntactic translations between languages over different sets of types as initial morphisms in a category of models. In [1], we characterize untyped syntax with reduction rules as initial object in a category of models. In the present work, we show that those techniques are modular enough to be combined: we thus characterize simply-typed syntax with reduction rules as initial object in a category. The universal property yields an operator which allows to specify translations - that are semantically faithful by construction - between languages over possibly different sets of types. We specify a language by a 2-signature, that is, a signature on two levels: the syntactic level specifies the types and terms of the language, and associates a type to each term. The semantic level specifies, through inequations, reduction rules on the terms of the language. To any given 2-signature we associate a category of models. We prove that this category has an initial object, which integrates the types and terms freely generated by the 2-signature, and the reduction relation on those terms generated by the given inequations. We call this object the (programming) language generated by the 2-signature. [1] Ahrens, B.: Modules over relative monads for syntax and semantics (2011), arXiv:1107.5252, to be published in Math. Struct. in Comp. Science [2] Ahrens, B.: Extended Initiality for Typed Abstract Syntax. Logical Methods in Computer Science 8(2), 1-35 (2012)
Optimal compression of hash-origin prefix trees
Venue: arXiv cs.IT 2012
Year: 2012

There is a common problem of operating on hash values of elements of some database. In this paper there will be analyzed informational content of such general task and how to practically approach such found lower boundaries. Minimal prefix tree which distinguish elements turns out to require asymptotically only about 2.77544 bits per element, while standard approaches use a few times more. While being certain of working inside the database, the cost of distinguishability can be reduced further to about 2.33275 bits per elements. Increasing minimal depth of nodes to reduce probability of false positives leads to simple relation with average depth of such random tree, which is asymptotically larger by about 1.33275 bits than lg(n) of the perfect binary tree. This asymptotic case can be also seen as a way to optimally encode n large unordered numbers - saving lg(n!) bits of information about their ordering, which can be the major part of contained information. This ability itself allows to reduce memory requirements even to about 0.693 of required in Bloom filter for the same false positive probability.
Initiality for Typed Syntax and Semantics
Venue: arXiv cs.LO 2012
Year: 2012

In this thesis we give an algebraic characterization of the syntax and semantics of simply-typed languages. More precisely, we characterize simply-typed binding syntax equipped with reduction rules via a universal property, namely as the initial object of some category. We specify a language by a 2-signature (Σ, A), that is, a signature on two levels: the syntactic level Σ specifies the sorts and terms of the language, and associates a sort to each term. The semantic level A specifies, through inequations, reduction rules on the terms of the language. To any given 2-signature (Σ, A) we associate a category of "models" of (Σ, A). We prove that this category has an initial object, which integrates the terms freely generated by Σ and the reduction relation - on those terms - generated by A. We call this object the programming language generated by (Σ, A). Initiality provides an iteration principle which allows to specify translations on the syntax, possibly to a language over different sorts. Furthermore, translations specified via the iteration principle are by construction type-safe and faithful with respect to reduction. To illustrate our results, we consider two examples extensively: firstly, we specify a double negation translation from classical to intuitionistic propositional logic via the category-theoretic iteration principle. Secondly, we specify a translation from PCF to the untyped lambda calculus which is faithful with respect to reduction in the source and target languages. In a second part, we formalize some of our initiality theorems in the proof assistant Coq. The implementation yields a machinery which, when given a 2-signature, returns an implementation of its associated abstract syntax together with certified substitution operation, iteration operator and a reduction relation generated by the specified reduction rules.
Adaptive Regularization for Weight Matrices
Venue: arXiv cs.LG 2012
Year: 2012

Algorithms for learning distributions over weight-vectors, such as AROW were recently shown empirically to achieve state-of-the-art performance at various problems, with strong theoretical guaranties. Extending these algorithms to matrix models pose challenges since the number of free parameters in the covariance of the distribution scales as $n^4$ with the dimension $n$ of the matrix, and $n$ tends to be large in real applications. We describe, analyze and experiment with two new algorithms for learning distribution of matrix models. Our first algorithm maintains a diagonal covariance over the parameters and can handle large covariance matrices. The second algorithm factors the covariance to capture inter-features correlation while keeping the number of parameters linear in the size of the original matrix. We analyze both algorithms in the mistake bound model and show a superior precision performance of our approach over other algorithms in two tasks: retrieving similar images, and ranking similar documents. The factored algorithm is shown to attain faster convergence rate.
Bayesian Watermark Attacks
Venue: arXiv cs.CR 2012
Year: 2012

This paper presents an application of statistical machine learning to the field of watermarking. We propose a new attack model on additive spread-spectrum watermarking systems. The proposed attack is based on Bayesian statistics. We consider the scenario in which a watermark signal is repeatedly embedded in specific, possibly chosen based on a secret message bitstream, segments (signals) of the host data. The host signal can represent a patch of pixels from an image or a video frame. We propose a probabilistic model that infers the embedded message bitstream and watermark signal, directly from the watermarked data, without access to the decoder. We develop an efficient Markov chain Monte Carlo sampler for updating the model parameters from their conjugate full conditional posteriors. We also provide a variational Bayesian solution, which further increases the convergence speed of the algorithm. Experiments with synthetic and real image signals demonstrate that the attack model is able to correctly infer a large part of the message bitstream and obtain a very accurate estimate of the watermark signal.
On the Secrecy Rate Region of a Fading Multiple-Antenna Gaussian Broadcast Channel with Confidential Messages and Partial CSIT
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we consider the secure transmission over the fast fading multiple antenna Gaussian broadcast channels with confidential messages (FMGBC-CM), where a multiple-antenna transmitter sends independent confidential messages to two users with information theoretic secrecy and only the statistics of the receivers' channel state information are known at the transmitter. We first use the same marginal property of the FMGBC-CM to classify the non-trivial cases, i.e., those not degraded to the common wiretap channels. We then derive the achievable rate region for the FMGBC-CM by solving the channel input covariance matrices and the inflation factor. Due to the complicated rate region formulae, we resort to low SNR analysis to investigate the characteristics of the channel. Finally, the numerical examples show that under the information-theoretic secrecy requirement both users can achieve positive rates simultaneously.
Indexed realizability for bounded-time programming with references and type fixpoints
Venue: arXiv cs.LO 2012
Year: 2012

The field of implicit complexity has recently produced several bounded-complexity programming languages. This kind of language allows to implement exactly the functions belonging to a certain complexity class. We here present a realizability semantics for a higher-order functional language based on a fragment of linear logic called LAL which characterizes the complexity class PTIME. This language features recursive types and higher-order store. Our realizability is based on biorthogonality, step-indexing and is moreover quantitative. This last feature enables us not only to derive a semantical proof of termination, but also to give bounds on the number of computational steps needed by typed programs to terminate.
On the Localization of the Personalized PageRank of Complex Networks
Venue: arXiv cs.DM 2012
Year: 2012

In this paper new results on personalized PageRank are shown. We consider directed graphs that may contain dangling nodes. The main result presented gives an analytical characterization of all the possible values of the personalized PageRank for any node.We use this result to give a theoretical justification of a recent model that uses the personalized PageRank to classify users of Social Networks Sites. We introduce new concepts concerning competitivity and leadership in complex networks. We also present some theoretical techniques to locate leaders and competitors which are valid for any personalization vector and by using only information related to the adjacency matrix of the graph and the distribution of its dangling nodes.
Planarizing an Unknown Surface
Venue: arXiv cs.DS 2012
Year: 2012

It has been recently shown that any graph of genus g>0 can be stochastically embedded into a distribution over planar graphs, with distortion Olog (g+1)) [Sidiropoulos, FOCS 2010]. This embedding can be computed in polynomial time, provided that a drawing of the input graph into a genus-g surface is given. We show how to compute the above embedding without having such a drawing. This implies a general reduction for solving problems on graphs of small genus, even when the drawing into a small genus surface is unknown. To the best of our knowledge, this is the first result of this type.
An Adaptative Multi-GPU based Branch-and-Bound. A Case Study: the Flow-Shop Scheduling Problem
Venue: arXiv cs.DC 2012
Year: 2012

Solving exactly Combinatorial Optimization Problems (COPs) using a Branch-and-Bound (B&B) algorithm requires a huge amount of computational resources. Therefore, we recently investigated designing B&B algorithms on top of graphics processing units (GPUs) using a parallel bounding model. The proposed model assumes parallelizing the evaluation of the lower bounds on pools of sub-problems. The results demonstrated that the size of the evaluated pool has a significant impact on the performance of B&B and that it depends strongly on the problem instance being solved. In this paper, we design an adaptative parallel B&B algorithm for solving permutation-based combinatorial optimization problems such as FSP (Flow-shop Scheduling Problem) on GPU accelerators. To do so, we propose a dynamic heuristic for parameter auto-tuning at runtime. Another challenge of this work is to exploit larger degrees of parallelism by using the combined computational power of multiple GPU devices. The approach has been applied to the permutation flow-shop problem. Extensive experiments have been carried out on well-known FSP benchmarks using an Nvidia Tesla S1070 Computing System equipped with two Tesla T10 GPUs. Compared to a CPU-based execution, accelerations up to 105 are achieved for large problem instances.
A New Bound on the Minimum Distance of Cyclic Codes Using Small-Minimum-Distance Cyclic Codes
Venue: arXiv cs.IT 2012
Year: 2012

A new bound on the minimum distance of q-ary cyclic codes is proposed. It is based on the description by another cyclic code with small minimum distance. The connection to the BCH bound and the Hartmann--Tzeng (HT) bound is formulated explicitly. We show that for many cases our approach improves the HT bound. Furthermore, we refine our bound for several families of cyclic codes. We define syndromes and formulate a Key Equation that allows an efficient decoding up to our bound with the Extended Euclidean Algorithm. It turns out that lowest-code-rate cyclic codes with small minimum distances are useful for our approach. Therefore, we give a sufficient condition for binary cyclic codes of arbitrary length to have minimum distance two or three and lowest code-rate
A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs
Venue: arXiv cs.SI 2012
Year: 2012

Recently there has been much interest in graph-based learning, with applications in collaborative filtering for recommender networks, link prediction for social networks and fraud detection. These networks can consist of millions of entities, and so it is very important to develop highly efficient techniques. We are especially interested in accelerating random walk approaches to compute some very interesting proximity measures of these kinds of graphs. These measures have been shown to do well empirically (Liben-Nowell & Kleinberg, 2003; Brand, 2005). We introduce a truncated variation on a well-known measure, namely commute times arising from random walks on graphs. We present a very novel algorithm to compute all interesting pairs of approximate nearest neighbors in truncated commute times, without computing it between all pairs. We show results on both simulated and real graphs of size up to 100; 000 entities, which indicate near-linear scaling in computation time.
Reading Dependencies from Polytree-Like Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

We present a graphical criterion for reading dependencies from the minimal directed independence map G of a graphoid p when G is a polytree and p satisfies composition and weak transitivity. We prove that the criterion is sound and complete. We argue that assuming composition and weak transitivity is not too restrictive.
On Discarding, Caching, and Recalling Samples in Active Learning
Venue: arXiv cs.LG 2012
Year: 2012

We address challenges of active learning under scarce informational resources in non-stationary environments. In real-world settings, data labeled and integrated into a predictive model may become invalid over time. However, the data can become informative again with switches in context and such changes may indicate unmodeled cyclic or other temporal dynamics. We explore principles for discarding, caching, and recalling labeled data points in active learning based on computations of value of information. We review key concepts and study the value of the methods via investigations of predictive performance and costs of acquiring data for simulated and real-world data sets.
More-or-Less CP-Networks
Venue: arXiv cs.AI 2012
Year: 2012

Preferences play an important role in our everyday lives. CP-networks, or CP-nets in short, are graphical models for representing conditional qualitative preferences under ceteris paribus ("all else being equal") assumptions. Despite their intuitive nature and rich representation, dominance testing with CP-nets is computationally complex, even when the CP-nets are restricted to binary-valued preferences. Tractable algorithms exist for binary CP-nets, but these algorithms are incomplete for multi-valued CPnets. In this paper, we identify a class of multivalued CP-nets, which we call more-or-less CPnets, that have the same computational complexity as binary CP-nets. More-or-less CP-nets exploit the monotonicity of the attribute values and use intervals to aggregate values that induce similar preferences. We then present a search control rule for dominance testing that effectively prunes the search space while preserving completeness.
MAP Estimation, Linear Programming and Belief Propagation with Convex Free Energies
Venue: arXiv cs.AI 2012
Year: 2012

Finding the most probable assignment (MAP) in a general graphical model is known to be NP hard but good approximations have been attained with max-product belief propagation (BP) and its variants. In particular, it is known that using BP on a single-cycle graph or tree reweighted BP on an arbitrary graph will give the MAP solution if the beliefs have no ties. In this paper we extend the setting under which BP can be used to provably extract the MAP. We define Convex BP as BP algorithms based on a convex free energy approximation and show that this class includes ordinary BP with single-cycle, tree reweighted BP and many other BP variants. We show that when there are no ties, fixed-points of convex max-product BP will provably give the MAP solution. We also show that convex sum-product BP at sufficiently small temperatures can be used to solve linear programs that arise from relaxing the MAP problem. Finally, we derive a novel condition that allows us to derive the MAP solution even if some of the convex BP beliefs have ties. In experiments, we show that our theorems allow us to find the MAP in many real-world instances of graphical models where exact inference using junction-tree is impossible.
Constrained Automated Mechanism Design for Infinite Games of Incomplete Information
Venue: arXiv cs.GT 2012
Year: 2012

We present a functional framework for automated mechanism design based on a two-stage game model of strategic interaction between the designer and the mechanism participants, and apply it to several classes of two-player infinite games of incomplete information. At the core of our framework is a black-box optimization algorithm which guides the selection process of candidate mechanisms. Our approach yields optimal or nearly optimal mechanisms in several application domains using various objective functions. By comparing our results with known optimal mechanisms, and in some cases improving on the best known mechanisms, we provide evidence that ours is a promising approach to parametric design of indirect mechanisms.
On Sensitivity of the MAP Bayesian Network Structure to the Equivalent Sample Size Parameter
Venue: arXiv cs.LG 2012
Year: 2012

BDeu marginal likelihood score is a popular model selection criterion for selecting a Bayesian network structure based on sample data. This non-informative scoring criterion assigns same score for network structures that encode same independence statements. However, before applying the BDeu score, one must determine a single parameter, the equivalent sample size alpha. Unfortunately no generally accepted rule for determining the alpha parameter has been suggested. This is disturbing, since in this paper we show through a series of concrete experiments that the solution of the network structure optimization problem is highly sensitive to the chosen alpha parameter value. Based on these results, we are able to give explanations for how and why this phenomenon happens, and discuss ideas for solving this problem.
Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs
Venue: arXiv cs.AI 2012
Year: 2012

Memory-Bounded Dynamic Programming (MBDP) has proved extremely effective in solving decentralized POMDPs with large horizons. We generalize the algorithm and improve its scalability by reducing the complexity with respect to the number of observations from exponential to polynomial. We derive error bounds on solution quality with respect to this new approximation and analyze the convergence behavior. To evaluate the effectiveness of the improvements, we introduce a new, larger benchmark problem. Experimental results show that despite the high complexity of decentralized POMDPs, scalable solution techniques such as MBDP perform surprisingly well.
Nonuniform Vote Aggregation Algorithms
Venue: arXiv cs.DS 2012
Year: 2012

We consider the problem of non-uniform vote aggregation, and in particular, the algorithmic aspects associated with the aggregation process. For a novel class of weighted distance measures on votes, we present two different aggregation methods. The first algorithm is based on approximating the weighted distance measure by Spearman's footrule distance, with provable constant approximation guarantees. The second algorithm is based on a non-uniform Markov chain method inspired by PageRank, for which currently only heuristic guarantees are known. We illustrate the performance of the proposed algorithms on a number of distance measures for which the optimal solution may be easily computed.