title: Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence (2011)

abstract: This is the Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, which was held in Barcelona, Spain, July 14 - 17 2011.


title: Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence (2010)

abstract: This is the Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, which was held on Catalina Island, CA, July 8 - 11 2010.


title: HST and Optical Data Reveal White Dwarf Cooling, Spin and Periodicities in GW Librae 3-4 Years after Outburst

abstract: Since the large amplitude 2007 outburst which heated its accreting, pulsating white dwarf, the dwarf nova system GW Librae has been cooling to its quiescent temperature. Our Hubble Space Telescope ultraviolet spectra combined with ground-based optical coverage during the 3rd and 4th year after outburst show that the fluxes and temperatures are still higher than quiescence (T=19,700K and 17,300K vs 16,000K pre-outburst for a log g=8.7 and d=100 pc). The K{wd} of 7.6+/-0.8 km/s determined from the CI1463 absorption line, as well as the gravitational redshift implies a white dwarf mass of 0.79+/-0.08 Msun. The widths of the UV lines imply a white dwarf rotation velocity vsin i of 40 km/s and a spin period of 209 s (for an inclination of 11 deg and a white dwarf radius of 7x10^{8} cm). Light curves produced from the UV spectra in both years show a prominent multiplet near 290 s, with higher amplitude in the UV compared to the optical, and increased amplitude in 2011 vs 2010. As the presence of this set of periods is intermittent in the optical on weekly timescales, it is unclear how this relates to the non-radial pulsations evident during quiescence.


title: On the Identifiability of the Post-Nonlinear Causal Model

abstract: By taking into account the nonlinear effect of the cause, the inner noise effect, and the measurement distortion effect in the observed variables, the post-nonlinear (PNL) causal model has demonstrated its excellent performance in distinguishing the cause from effect. However, its identifiability has not been properly addressed, and how to apply it in the case of more than two variables is also a problem. In this paper, we conduct a systematic investigation on its identifiability in the two-variable case. We show that this model is identifiable in most cases; by enumerating all possible situations in which the model is not identifiable, we provide sufficient conditions for its identifiability. Simulations are given to support the theoretical results. Moreover, in the case of more than two variables, we show that the whole causal structure can be found by applying the PNL causal model to each structure in the Markov equivalent class and testing if the disturbance is independent of the direct causes for each variable. In this way the exhaustive search over all possible causal structures is avoided.


title: A Uniqueness Theorem for Clustering

abstract: Despite the widespread use of Clustering, there is distressingly little general theory of clustering available. Questions like "What distinguishes a clustering of data from other data partitioning?", "Are there any principles governing all clustering paradigms?", "How should a user choose an appropriate clustering algorithm for a particular task?", etc. are almost completely unanswered by the existing body of clustering literature. We consider an axiomatic approach to the theory of Clustering. We adopt the framework of Kleinberg, [Kle03]. By relaxing one of Kleinberg's clustering axioms, we sidestep his impossibility result and arrive at a consistent set of axioms. We suggest to extend these axioms, aiming to provide an axiomatic taxonomy of clustering paradigms. Such a taxonomy should provide users some guidance concerning the choice of the appropriate clustering paradigm for a given task. The main result of this paper is a set of abstract properties that characterize the Single-Linkage clustering function. This characterization result provides new insight into the properties of desired data groupings that make Single-Linkage the appropriate choice. We conclude by considering a taxonomy of clustering functions based on abstract properties that each satisfies.


title: Most Relevant Explanation: Properties, Algorithms, and Evaluations

abstract: Most Relevant Explanation (MRE) is a method for finding multivariate explanations for given evidence in Bayesian networks [12]. This paper studies the theoretical properties of MRE and develops an algorithm for finding multiple top MRE solutions. Our study shows that MRE relies on an implicit soft relevance measure in automatically identifying the most relevant target variables and pruning less relevant variables from an explanation. The soft measure also enables MRE to capture the intuitive phenomenon of explaining away encoded in Bayesian networks. Furthermore, our study shows that the solution space of MRE has a special lattice structure which yields interesting dominance relations among the solutions. A K-MRE algorithm based on these dominance relations is developed for generating a set of top solutions that are more representative. Our empirical results show that MRE methods are promising approaches for explanation in Bayesian networks.


title: The Entire Quantile Path of a Risk-Agnostic SVM Classifier

abstract: A quantile binary classifier uses the rule: Classify x as +1 if P(Y = 1|X = x) >= t, and as -1 otherwise, for a fixed quantile parameter t {[0, 1]. It has been shown that Support Vector Machines (SVMs) in the limit are quantile classifiers with t = 1/2 . In this paper, we show that by using asymmetric cost of misclassification SVMs can be appropriately extended to recover, in the limit, the quantile binary classifier for any t. We then present a principled algorithm to solve the extended SVM classifier for all values of t simultaneously. This has two implications: First, one can recover the entire conditional distribution P(Y = 1|X = x) = t for t {[0, 1]. Second, we can build a risk-agnostic SVM classifier where the cost of misclassification need not be known apriori. Preliminary numerical experiments show the effectiveness of the proposed algorithm.


title: A Bayesian Framework for Community Detection Integrating Content and Link

abstract: This paper addresses the problem of community detection in networked data that combines link and content analysis. Most existing work combines link and content information by a generative model. There are two major shortcomings with the existing approaches. First, they assume that the probability of creating a link between two nodes is determined only by the community memberships of the nodes; however other factors (e.g. popularity) could also affect the link pattern. Second, they use generative models to model the content of individual nodes, whereas these generative models are vulnerable to the content attributes that are irrelevant to communities. We propose a Bayesian framework for combining link and content information for community detection that explicitly addresses these shortcomings. A new link model is presented that introduces a random variable to capture the node popularity when deciding the link between two nodes; a discriminative model is used to determine the community membership of a node by its content. An approximate inference algorithm is presented for efficient Bayesian inference. Our empirical study shows that the proposed framework outperforms several state-of-theart approaches in combining link and content information for community detection.


title: The Infinite Latent Events Model

abstract: We present the Infinite Latent Events Model, a nonparametric hierarchical Bayesian distribution over infinite dimensional Dynamic Bayesian Networks with binary state representations and noisy-OR-like transitions. The distribution can be used to learn structure in discrete timeseries data by simultaneously inferring a set of latent events, which events fired at each timestep, and how those events are causally linked. We illustrate the model on a sound factorization task, a network topology identification task, and a video game task.


title: Herding Dynamic Weights for Partially Observed Random Field Models

abstract: Learning the parameters of a (potentially partially observable) random field model is intractable in general. Instead of focussing on a single optimal parameter value we propose to treat parameters as dynamical quantities. We introduce an algorithm to generate complex dynamics for parameters and (both visible and hidden) state vectors. We show that under certain conditions averages computed over trajectories of the proposed dynamical system converge to averages computed over the data. Our "herding dynamics" does not require expensive operations such as exponentiation and is fully deterministic.


title: Exploring compact reinforcement-learning representations with linear regression

abstract: This paper presents a new algorithm for online linear regression whose efficiency guarantees satisfy the requirements of the KWIK (Knows What It Knows) framework. The algorithm improves on the complexity bounds of the current state-of-the-art procedure in this setting. We explore several applications of this algorithm for learning compact reinforcement-learning representations. We show that KWIK linear regression can be used to learn the reward function of a factored MDP and the probabilities of action outcomes in Stochastic STRIPS and Object Oriented MDPs, none of which have been proven to be efficiently learnable in the RL setting before. We also combine KWIK linear regression with other KWIK learners to learn larger portions of these models, including experiments on learning factored MDP transition and reward functions together.


title: Simulation-Based Game Theoretic Analysis of Keyword Auctions with Low-Dimensional Bidding Strategies

abstract: We perform a simulation-based analysis of keyword auctions modeled as one-shot games of incomplete information to study a series of mechanism design questions. Our first question addresses the degree to which incentive compatibility fails in generalized second-price (GSP) auctions. Our results suggest that sincere bidding in GSP auctions is a strikingly poor strategy and a poor predictor of equilibrium outcomes. We next show that the rank-by-revenue mechanism is welfare optimal, corroborating past results. Finally, we analyze profit as a function of auction mechanism under a series of alternative settings. Our conclusions coincide with those of Lahaie and Pennock [2007] when values and quality scores are strongly positively correlated: in such a case, rank-by-bid rules are clearly superior. We diverge, however, in showing that auctions that put little weight on quality scores almost universally dominate the pure rank-by-revenue scheme.


title: Temporal-Difference Networks for Dynamical Systems with Continuous Observations and Actions

abstract: Temporal-difference (TD) networks are a class of predictive state representations that use well-established TD methods to learn models of partially observable dynamical systems. Previous research with TD networks has dealt only with dynamical systems with finite sets of observations and actions. We present an algorithm for learning TD network representations of dynamical systems with continuous observations and actions. Our results show that the algorithm is capable of learning accurate and robust models of several noisy continuous dynamical systems. The algorithm presented here is the first fully incremental method for learning a predictive representation of a continuous dynamical system.


title: Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?

abstract: Recent theory work has found that a special type of spatial partition tree - called a random projection tree - is adaptive to the intrinsic dimension of the data from which it is built. Here we examine this same question, with a combination of theory and experiments, for a broader class of trees that includes k-d trees, dyadic trees, and PCA trees. Our motivation is to get a feel for (i) the kind of intrinsic low dimensional structure that can be empirically verified, (ii) the extent to which a spatial partition can exploit such structure, and (iii) the implications for standard statistical tasks such as regression, vector quantization, and nearest neighbor search.


title: Probabilistic Structured Predictors

abstract: We consider MAP estimators for structured prediction with exponential family models. In particular, we concentrate on the case that efficient algorithms for uniform sampling from the output space exist. We show that under this assumption (i) exact computation of the partition function remains a hard problem, and (ii) the partition function and the gradient of the log partition function can be approximated efficiently. Our main result is an approximation scheme for the partition function based on Markov Chain Monte Carlo theory. We also show that the efficient uniform sampling assumption holds in several application settings that are of importance in machine learning.


title: Ordinal Boltzmann Machines for Collaborative Filtering

abstract: Collaborative filtering is an effective recommendation technique wherein the preference of an individual can potentially be predicted based on preferences of other members. Early algorithms often relied on the strong locality in the preference data, that is, it is enough to predict preference of a user on a particular item based on a small subset of other users with similar tastes or of other items with similar properties. More recently, dimensionality reduction techniques have proved to be equally competitive, and these are based on the co-occurrence patterns rather than locality. This paper explores and extends a probabilistic model known as Boltzmann Machine for collaborative filtering tasks. It seamlessly integrates both the similarity and co-occurrence in a principled manner. In particular, we study parameterisation options to deal with the ordinal nature of the preferences, and propose a joint modelling of both the user-based and item-based processes. Experiments on moderate and large-scale movie recommendation show that our framework rivals existing well-known methods.


title: Computing Posterior Probabilities of Structural Features in Bayesian Networks

abstract: We study the problem of learning Bayesian network structures from data. Koivisto and Sood (2004) and Koivisto (2006) presented algorithms that can compute the exact marginal posterior probability of a subnetwork, e.g., a single edge, in O(n2n) time and the posterior probabilities for all n(n-1) potential edges in O(n2n) total time, assuming that the number of parents per node or the indegree is bounded by a constant. One main drawback of their algorithms is the requirement of a special structure prior that is non uniform and does not respect Markov equivalence. In this paper, we develop an algorithm that can compute the exact posterior probability of a subnetwork in O(3n) time and the posterior probabilities for all n(n-1) potential edges in O(n3n) total time. Our algorithm also assumes a bounded indegree but allows general structure priors. We demonstrate the applicability of the algorithm on several data sets with up to 20 variables.


title: Measuring Inconsistency in Probabilistic Knowledge Bases

abstract: This paper develops an inconsistency measure on conditional probabilistic knowledge bases. The measure is based on fundamental principles for inconsistency measures and thus provides a solid theoretical framework for the treatment of inconsistencies in probabilistic expert systems. We illustrate its usefulness and immediate application on several examples and present some formal results. Building on this measure we use the Shapley value-a well-known solution for coalition games-to define a sophisticated indicator that is not only able to measure inconsistencies but to reveal the causes of inconsistencies in the knowledge base. Altogether these tools guide the knowledge engineer in his aim to restore consistency and therefore enable him to build a consistent and usable knowledge base that can be employed in probabilistic expert systems.


title: Products of Hidden Markov Models: It Takes N>1 to Tango

abstract: Products of Hidden Markov Models(PoHMMs) are an interesting class of generative models which have received little attention since their introduction. This maybe in part due to their more computationally expensive gradient-based learning algorithm,and the intractability of computing the log likelihood of sequences under the model. In this paper, we demonstrate how the partition function can be estimated reliably via Annealed Importance Sampling. We perform experiments using contrastive divergence learning on rainfall data and data captured from pairs of people dancing. Our results suggest that advances in learning and evaluation for undirected graphical models and recent increases in available computing power make PoHMMs worth considering for complex time-series modeling tasks.


title: Effects of Treatment on the Treated: Identification and Generalization

abstract: Many applications of causal analysis call for assessing, retrospectively, the effect of withholding an action that has in fact been implemented. This counterfactual quantity, sometimes called "effect of treatment on the treated," (ETT) have been used to to evaluate educational programs, critic public policies, and justify individual decision making. In this paper we explore the conditions under which ETT can be estimated from (i.e., identified in) experimental and/or observational studies. We show that, when the action invokes a singleton variable, the conditions for ETT identification have simple characterizations in terms of causal diagrams. We further give a graphical characterization of the conditions under which the effects of multiple treatments on the treated can be identified, as well as ways in which the ETT estimand can be constructed from both interventional and observational distributions.


title: Bisimulation-based Approximate Lifted Inference

abstract: There has been a great deal of recent interest in methods for performing lifted inference; however, most of this work assumes that the first-order model is given as input to the system. Here, we describe lifted inference algorithms that determine symmetries and automatically lift the probabilistic model to speedup inference. In particular, we describe approximate lifted inference techniques that allow the user to trade off inference accuracy for computational efficiency by using a handful of tunable parameters, while keeping the error bounded. Our algorithms are closely related to the graph-theoretic concept of bisimulation. We report experiments on both synthetic and real data to show that in the presence of symmetries, run-times for inference can be improved significantly, with approximate lifted inference providing orders of magnitude speedup over ground inference.


title: Modeling Discrete Interventional Data using Directed Cyclic Graphical Models

abstract: We outline a representation for discrete multivariate distributions in terms of interventional potential functions that are globally normalized. This representation can be used to model the effects of interventions, and the independence properties encoded in this model can be represented as a directed graph that allows cycles. In addition to discussing inference and sampling with this representation, we give an exponential family parametrization that allows parameter estimation to be stated as a convex optimization problem; we also give a convex relaxation of the task of simultaneous parameter and structure learning using group l1-regularization. The model is evaluated on simulated data and intracellular flow cytometry data.


title: BPR: Bayesian Personalized Ranking from Implicit Feedback

abstract: Item recommendation is the task of predicting a personalized ranking on a set of items (e.g. websites, movies, products). In this paper, we investigate the most common scenario with implicit feedback (e.g. clicks, purchases). There are many methods for item recommendation from implicit feedback like matrix factorization (MF) or adaptive knearest-neighbor (kNN). Even though these methods are designed for the item prediction task of personalized ranking, none of them is directly optimized for ranking. In this paper we present a generic optimization criterion BPR-Opt for personalized ranking that is the maximum posterior estimator derived from a Bayesian analysis of the problem. We also provide a generic learning algorithm for optimizing models with respect to BPR-Opt. The learning method is based on stochastic gradient descent with bootstrap sampling. We show how to apply our method to two state-of-the-art recommender models: matrix factorization and adaptive kNN. Our experiments indicate that for the task of personalized ranking our optimization method outperforms the standard learning techniques for MF and kNN. The results show the importance of optimizing models for the right criterion.


title: Regret-based Reward Elicitation for Markov Decision Processes

abstract: The specification of aMarkov decision process (MDP) can be difficult. Reward function specification is especially problematic; in practice, it is often cognitively complex and time-consuming for users to precisely specify rewards. This work casts the problem of specifying rewards as one of preference elicitation and aims to minimize the degree of precision with which a reward function must be specified while still allowing optimal or near-optimal policies to be produced. We first discuss how robust policies can be computed for MDPs given only partial reward information using the minimax regret criterion. We then demonstrate how regret can be reduced by efficiently eliciting reward information using bound queries, using regret-reduction as a means for choosing suitable queries. Empirical results demonstrate that regret-based reward elicitation offers an effective way to produce near-optimal policies without resorting to the precise specification of the entire reward function.


title: Exact Structure Discovery in Bayesian Networks with Less Space

abstract: The fastest known exact algorithms for scorebased structure discovery in Bayesian networks on n nodes run in time and space 2nnO(1). The usage of these algorithms is limited to networks on at most around 25 nodes mainly due to the space requirement. Here, we study space-time tradeoffs for finding an optimal network structure. When little space is available, we apply the Gurevich-Shelah recurrence-originally proposed for the Hamiltonian path problem-and obtain time 22n-snO(1) in space 2snO(1) for any s = n/2, n/4, n/8, . . .; we assume the indegree of each node is bounded by a constant. For the more practical setting with moderate amounts of space, we present a novel scheme. It yields running time 2n(3/2)pnO(1) in space 2n(3/4)pnO(1) for any p = 0, 1, . . ., n/2; these bounds hold as long as the indegrees are at most 0.238n. Furthermore, the latter scheme allows easy and efficient parallelization beyond previous algorithms. We also explore empirically the potential of the presented techniques.


title: Logical Inference Algorithms and Matrix Representations for Probabilistic Conditional Independence

abstract: Logical inference algorithms for conditional independence (CI) statements have important applications from testing consistency during knowledge elicitation to constraintbased structure learning of graphical models. We prove that the implication problem for CI statements is decidable, given that the size of the domains of the random variables is known and fixed. We will present an approximate logical inference algorithm which combines a falsification and a novel validation algorithm. The validation algorithm represents each set of CI statements as a sparse 0-1 matrix A and validates instances of the implication problem by solving specific linear programs with constraint matrix A. We will show experimentally that the algorithm is both effective and efficient in validating and falsifying instances of the probabilistic CI implication problem.


title: Using the Gene Ontology Hierarchy when Predicting Gene Function

abstract: The problem of multilabel classification when the labels are related through a hierarchical categorization scheme occurs in many application domains such as computational biology. For example, this problem arises naturally when trying to automatically assign gene function using a controlled vocabularies like Gene Ontology. However, most existing approaches for predicting gene functions solve independent classification problems to predict genes that are involved in a given function category, independently of the rest. Here, we propose two simple methods for incorporating information about the hierarchical nature of the categorization scheme. In the first method, we use information about a gene's previous annotation to set an initial prior on its label. In a second approach, we extend a graph-based semi-supervised learning algorithm for predicting gene function in a hierarchy. We show that we can efficiently solve this problem by solving a linear system of equations. We compare these approaches with a previous label reconciliation-based approach. Results show that using the hierarchy information directly, compared to using reconciliation methods, improves gene function prediction.


title: Virtual Vector Machine for Bayesian Online Classification

abstract: In a typical online learning scenario, a learner is required to process a large data stream using a small memory buffer. Such a requirement is usually in conflict with a learner's primary pursuit of prediction accuracy. To address this dilemma, we introduce a novel Bayesian online classi cation algorithm, called the Virtual Vector Machine. The virtual vector machine allows you to smoothly trade-off prediction accuracy with memory size. The virtual vector machine summarizes the information contained in the preceding data stream by a Gaussian distribution over the classi cation weights plus a constant number of virtual data points. The virtual data points are designed to add extra non-Gaussian information about the classi cation weights. To maintain the constant number of virtual points, the virtual vector machine adds the current real data point into the virtual point set, merges two most similar virtual points into a new virtual point or deletes a virtual point that is far from the decision boundary. The information lost in this process is absorbed into the Gaussian distribution. The extra information provided by the virtual points leads to improved predictive accuracy over previous online classification algorithms.


title: Convexifying the Bethe Free Energy

abstract: The introduction of loopy belief propagation (LBP) revitalized the application of graphical models in many domains. Many recent works present improvements on the basic LBP algorithm in an attempt to overcome convergence and local optima problems. Notable among these are convexified free energy approximations that lead to inference procedures with provable convergence and quality properties. However, empirically LBP still outperforms most of its convex variants in a variety of settings, as we also demonstrate here. Motivated by this fact we seek convexified free energies that directly approximate the Bethe free energy. We show that the proposed approximations compare favorably with state-of-the art convex free energy approximations.


title: Convergent message passing algorithms - a unifying view

abstract: Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright's non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right update order for the case where trees are monotonic chains.


title: Group Sparse Priors for Covariance Estimation

abstract: Recently it has become popular to learn sparse Gaussian graphical models (GGMs) by imposing l1 or group l1,2 penalties on the elements of the precision matrix. Thispenalized likelihood approach results in a tractable convex optimization problem. In this paper, we reinterpret these results as performing MAP estimation under a novel prior which we call the group l1 and l1,2 positivedefinite matrix distributions. This enables us to build a hierarchical model in which the l1 regularization terms vary depending on which group the entries are assigned to, which in turn allows us to learn block structured sparse GGMs with unknown group assignments. Exact inference in this hierarchical model is intractable, due to the need to compute the normalization constant of these matrix distributions. However, we derive upper bounds on the partition functions, which lets us use fast variational inference (optimizing a lower bound on the joint posterior). We show that on two real world data sets (motion capture and financial data), our method which infers the block structure outperforms a method that uses a fixed block structure, which in turn outperforms baseline methods that ignore block structure.


title: Domain Knowledge Uncertainty and Probabilistic Parameter Constraints

abstract: Incorporating domain knowledge into the modeling process is an effective way to improve learning accuracy. However, as it is provided by humans, domain knowledge can only be specified with some degree of uncertainty. We propose to explicitly model such uncertainty through probabilistic constraints over the parameter space. In contrast to hard parameter constraints, our approach is effective also when the domain knowledge is inaccurate and generally results in superior modeling accuracy. We focus on generative and conditional modeling where the parameters are assigned a Dirichlet or Gaussian prior and demonstrate the framework with experiments on both synthetic and real-world data.


title: Multiple Source Adaptation and the Renyi Divergence

abstract: This paper presents a novel theoretical study of the general problem of multiple source adaptation using the notion of Renyi divergence. Our results build on our previous work [12], but significantly broaden the scope of that work in several directions. We extend previous multiple source loss guarantees based on distribution weighted combinations to arbitrary target distributions P, not necessarily mixtures of the source distributions, analyze both known and unknown target distribution cases, and prove a lower bound. We further extend our bounds to deal with the case where the learner receives an approximate distribution for each source instead of the exact one, and show that similar loss guarantees can be achieved depending on the divergence between the approximate and true distributions. We also analyze the case where the labeling functions of the source domains are somewhat different. Finally, we report the results of experiments with both an artificial data set and a sentiment analysis task, showing the performance benefits of the distribution weighted combinations and the quality of our bounds based on the Renyi divergence.


title: Interpretation and Generalization of Score Matching

abstract: Score matching is a recently developed parameter learning method that is particularly effective to complicated high dimensional density models with intractable partition functions. In this paper, we study two issues that have not been completely resolved for score matching. First, we provide a formal link between maximum likelihood and score matching. Our analysis shows that score matching finds model parameters that are more robust with noisy training data. Second, we develop a generalization of score matching. Based on this generalization, we further demonstrate an extension of score matching to models of discrete data.


title: Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions

abstract: Strategyproof mechanisms provide robust equilibrium with minimal assumptions about knowledge and rationality but can be unachievable in combination with other desirable properties such as budget-balance, stability against deviations by coalitions, and computational tractability. In the search for maximally-strategyproof mechanisms that simultaneously satisfy other desirable properties, we introduce a new metric to quantify the strategyproofness of a mechanism, based on comparing the payoff distribution, given truthful reports, against that of a strategyproof "reference" mechanism that solves a problem relaxation. Focusing on combinatorial exchanges, we demonstrate that the metric is informative about the eventual equilibrium, where simple regretbased metrics are not, and can be used for online selection of an effective mechanism.


title: Multi-Task Feature Learning Via Efficient l2,1-Norm Minimization

abstract: The problem of joint feature selection across a group of related tasks has applications in many areas including biomedical informatics and computer vision. We consider the l2,1-norm regularized regression model for joint feature selection from multiple tasks, which can be derived in the probabilistic framework by assuming a suitable prior from the exponential family. One appealing feature of the l2,1-norm regularization is that it encourages multiple predictors to share similar sparsity patterns. However, the resulting optimization problem is challenging to solve due to the non-smoothness of the l2,1-norm regularization. In this paper, we propose to accelerate the computation by reformulating it as two equivalent smooth convex optimization problems which are then solved via the Nesterov's method-an optimal first-order black-box method for smooth convex optimization. A key building block in solving the reformulations is the Euclidean projection. We show that the Euclidean projection for the first reformulation can be analytically computed, while the Euclidean projection for the second one can be computed in linear time. Empirical evaluations on several data sets verify the efficiency of the proposed algorithms.


title: Improving Compressed Counting

abstract: Compressed Counting (CC) [22] was recently proposed for estimating the ath frequency moments of data streams, where 0 < a <= 2. CC can be used for estimating Shannon entropy, which can be approximated by certain functions of the ath frequency moments as a -> 1. Monitoring Shannon entropy for anomaly detection (e.g., DDoS attacks) in large networks is an important task. This paper presents a new algorithm for improving CC. The improvement is most substantial when a -> 1--. For example, when a = 0:99, the new algorithm reduces the estimation variance roughly by 100-fold. This new algorithm would make CC considerably more practical for estimating Shannon entropy. Furthermore, the new algorithm is statistically optimal when a = 0.5.


title: MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts

abstract: We consider the task of obtaining the maximum a posteriori estimate of discrete pairwise random fields with arbitrary unary potentials and semimetric pairwise potentials. For this problem, we propose an accurate hierarchical move making strategy where each move is computed efficiently by solving an st-MINCUT problem. Unlike previous move making approaches, e.g. the widely used a-expansion algorithm, our method obtains the guarantees of the standard linear programming (LP) relaxation for the important special case of metric labeling. Unlike the existing LP relaxation solvers, e.g. interior-point algorithms or tree-reweighted message passing, our method is significantly faster as it uses only the efficient st-MINCUT algorithm in its design. Using both synthetic and real data experiments, we show that our technique outperforms several commonly used algorithms.


title: The Temporal Logic of Causal Structures

abstract: Computational analysis of time-course data with an underlying causal structure is needed in a variety of domains, including neural spike trains, stock price movements, and gene expression levels. However, it can be challenging to determine from just the numerical time course data alone what is coordinating the visible processes, to separate the underlying prima facie causes into genuine and spurious causes and to do so with a feasible computational complexity. For this purpose, we have been developing a novel algorithm based on a framework that combines notions of causality in philosophy with algorithmic approaches built on model checking and statistical techniques for multiple hypotheses testing. The causal relationships are described in terms of temporal logic formulae, reframing the inference problem in terms of model checking. The logic used, PCTL, allows description of both the time between cause and effect and the probability of this relationship being observed. We show that equipped with these causal formulae with their associated probabilities we may compute the average impact a cause makes to its effect and then discover statistically significant causes through the concepts of multiple hypothesis testing (treating each causal relationship as a hypothesis), and false discovery control. By exploring a well-chosen family of potentially all significant hypotheses with reasonably minimal description length, it is possible to tame the algorithm's computational complexity while exploring the nearly complete search-space of all prima facie causes. We have tested these ideas in a number of domains and illustrate them here with two examples.


title: Constraint Processing in Lifted Probabilistic Inference

abstract: First-order probabilistic models combine representational power of first-order logic with graphical models. There is an ongoing effort to design lifted inference algorithms for first-order probabilistic models. We analyze lifted inference from the perspective of constraint processing and, through this viewpoint, we analyze and compare existing approaches and expose their advantages and limitations. Our theoretical results show that the wrong choice of constraint processing method can lead to exponential increase in computational complexity. Our empirical tests confirm the importance of constraint processing in lifted inference. This is the first theoretical and empirical study of constraint processing in lifted inference.


title: Monolingual Probabilistic Programming Using Generalized Coroutines

abstract: Probabilistic programming languages and modeling toolkits are two modular ways to build and reuse stochastic models and inference procedures. Combining strengths of both, we express models and inference as generalized coroutines in the same general-purpose language. We use existing facilities of the language, such as rich libraries, optimizing compilers, and types, to develop concise, declarative, and realistic models with competitive performance on exact and approximate inference. In particular, a wide range of models can be expressed using memoization. Because deterministic parts of models run at full speed, custom inference procedures are trivial to incorporate, and inference procedures can reason about themselves without interpretive overhead. Within this framework, we introduce a new, general algorithm for importance sampling with look-ahead.


title: Counting Belief Propagation

abstract: A major benefit of graphical models is that most knowledge is captured in the model structure. Many models, however, produce inference problems with a lot of symmetries not reflected in the graphical structure and hence not exploitable by efficient inference techniques such as belief propagation (BP). In this paper, we present a new and simple BP algorithm, called counting BP, that exploits such additional symmetries. Starting from a given factor graph, counting BP first constructs a compressed factor graph of clusternodes and clusterfactors, corresponding to sets of nodes and factors that are indistinguishable given the evidence. Then it runs a modified BP algorithm on the compressed graph that is equivalent to running BP on the original factor graph. Our experiments show that counting BP is applicable to a variety of important AI tasks such as (dynamic) relational models and boolean model counting, and that significant efficiency gains are obtainable, often by orders of magnitude.


title: Temporal Action-Graph Games: A New Representation for Dynamic Games

abstract: In this paper we introduce temporal action graph games (TAGGs), a novel graphical representation of imperfect-information extensive form games. We show that when a game involves anonymity or context-specific utility independencies, its encoding as a TAGG can be much more compact than its direct encoding as a multiagent influence diagram (MAID).We also show that TAGGs can be understood as indirect MAID encodings in which many deterministic chance nodes are introduced. We provide an algorithm for computing with TAGGs, and show both theoretically and empirically that our approach improves significantly on the previous state of the art.


title: MAP Estimation, Message Passing, and Perfect Graphs

abstract: Efficiently finding the maximum a posteriori (MAP) configuration of a graphical model is an important problem which is often implemented using message passing algorithms. The optimality of such algorithms is only well established for singly-connected graphs and other limited settings. This article extends the set of graphs where MAP estimation is in P and where message passing recovers the exact solution to so-called perfect graphs. This result leverages recent progress in defining perfect graphs (the strong perfect graph theorem), linear programming relaxations of MAP estimation and recent convergent message passing schemes. The article converts graphical models into nand Markov random fields which are straightforward to relax into linear programs. Therein, integrality can be established in general by testing for graph perfection. This perfection test is performed efficiently using a polynomial time algorithm. Alternatively, known decomposition tools from perfect graph theory may be used to prove perfection for certain families of graphs. Thus, a general graph framework is provided for determining when MAP estimation in any graphical model is in P, has an integral linear programming relaxation and is exactly recoverable by message passing.


title: Identifying confounders using additive noise models

abstract: We propose a method for inferring the existence of a latent common cause ('confounder') of two observed random variables. The method assumes that the two effects of the confounder are (possibly nonlinear) functions of the confounder plus independent, additive noise. We discuss under which conditions the model is identifiable (up to an arbitrary reparameterization of the confounder) from the joint distribution of the effects. We state and prove a theoretical result that provides evidence for the conjecture that the model is generically identifiable under suitable technical conditions. In addition, we propose a practical method to estimate the confounder from a finite i.i.d. sample of the effects and illustrate that the method works well on both simulated and real-world data.


title: Bayesian Discovery of Linear Acyclic Causal Models

abstract: Methods for automated discovery of causal relationships from non-interventional data have received much attention recently. A widely used and well understood model family is given by linear acyclic causal models (recursive structural equation models). For Gaussian data both constraint-based methods (Spirtes et al., 1993; Pearl, 2000) (which output a single equivalence class) and Bayesian score-based methods (Geiger and Heckerman, 1994) (which assign relative scores to the equivalence classes) are available. On the contrary, all current methods able to utilize non-Gaussianity in the data (Shimizu et al., 2006; Hoyer et al., 2008) always return only a single graph or a single equivalence class, and so are fundamentally unable to express the degree of certainty attached to that output. In this paper we develop a Bayesian score-based approach able to take advantage of non-Gaussianity when estimating linear acyclic causal models, and we empirically demonstrate that, at least on very modest size networks, its accuracy is as good as or better than existing methods. We provide a complete code package (in R) which implements all algorithms and performs all of the analysis provided in the paper, and hope that this will further the application of these methods to solving causal inference problems.


title: Improved Mean and Variance Approximations for Belief Net Responses via Network Doubling

abstract: A Bayesian belief network models a joint distribution with an directed acyclic graph representing dependencies among variables and network parameters characterizing conditional distributions. The parameters are viewed as random variables to quantify uncertainty about their values. Belief nets are used to compute responses to queries; i.e., conditional probabilities of interest. A query is a function of the parameters, hence a random variable. Van Allen et al. (2001, 2008) showed how to quantify uncertainty about a query via a delta method approximation of its variance. We develop more accurate approximations for both query mean and variance. The key idea is to extend the query mean approximation to a "doubled network" involving two independent replicates. Our method assumes complete data and can be applied to discrete, continuous, and hybrid networks (provided discrete variables have only discrete parents). We analyze several improvements, and provide empirical studies to demonstrate their effectiveness.


title: New inference strategies for solving Markov Decision Processes using reversible jump MCMC

abstract: In this paper we build on previous work which uses inferences techniques, in particular Markov Chain Monte Carlo (MCMC) methods, to solve parameterized control problems. We propose a number of modifications in order to make this approach more practical in general, higher-dimensional spaces. We first introduce a new target distribution which is able to incorporate more reward information from sampled trajectories. We also show how to break strong correlations between the policy parameters and sampled trajectories in order to sample more freely. Finally, we show how to incorporate these techniques in a principled manner to obtain estimates of the optimal policy.


title: First-Order Mixed Integer Linear Programming

abstract: Mixed integer linear programming (MILP) is a powerful representation often used to formulate decision-making problems under uncertainty. However, it lacks a natural mechanism to reason about objects, classes of objects, and relations. First-order logic (FOL), on the other hand, excels at reasoning about classes of objects, but lacks a rich representation of uncertainty. While representing propositional logic in MILP has been extensively explored, no theory exists yet for fully combining FOL with MILP. We propose a new representation, called first-order programming or FOP, which subsumes both FOL and MILP. We establish formal methods for reasoning about first order programs, including a sound and complete lifted inference procedure for integer first order programs. Since FOP can offer exponential savings in representation and proof size compared to FOL, and since representations and proofs are never significantly longer in FOP than in FOL, we anticipate that inference in FOP will be more tractable than inference in FOL for corresponding problems.


title: Distributed Parallel Inference on Large Factor Graphs

abstract: As computer clusters become more common and the size of the problems encountered in the field of AI grows, there is an increasing demand for efficient parallel inference algorithms. We consider the problem of parallel inference on large factor graphs in the distributed memory setting of computer clusters. We develop a new efficient parallel inference algorithm, DBRSplash, which incorporates over-segmented graph partitioning, belief residual scheduling, and uniform work Splash operations. We empirically evaluate the DBRSplash algorithm on a 120 processor cluster and demonstrate linear to super-linear performance gains on large factor graph models.


title: Censored Exploration and the Dark Pool Problem

abstract: We introduce and analyze a natural algorithm for multi-venue exploration from censored data, which is motivated by the Dark Pool Problem of modern quantitative finance. We prove that our algorithm converges in polynomial time to a near-optimal allocation policy; prior results for similar problems in stochastic inventory control guaranteed only asymptotic convergence and examined variants in which each venue could be treated independently. Our analysis bears a strong resemblance to that of efficient exploration/ exploitation schemes in the reinforcement learning literature. We describe an extensive experimental evaluation of our algorithm on the Dark Pool Problem using real trading data.


title: Generating Optimal Plans in Highly-Dynamic Domains

abstract: Generating optimal plans in highly dynamic environments is challenging. Plans are predicated on an assumed initial state, but this state can change unexpectedly during plan generation, potentially invalidating the planning effort. In this paper we make three contributions: (1) We propose a novel algorithm for generating optimal plans in settings where frequent, unexpected events interfere with planning. It is able to quickly distinguish relevant from irrelevant state changes, and to update the existing planning search tree if necessary. (2) We argue for a new criterion for evaluating plan adaptation techniques: the relative running time compared to the "size" of changes. This is significant since during recovery more changes may occur that need to be recovered from subsequently, and in order for this process of repeated recovery to terminate, recovery time has to converge. (3) We show empirically that our approach can converge and find optimal plans in environments that would ordinarily defy planning due to their high dynamics.


title: Learning Continuous-Time Social Network Dynamics

abstract: We demonstrate that a number of sociology models for social network dynamics can be viewed as continuous time Bayesian networks (CTBNs). A sampling-based approximate inference method for CTBNs can be used as the basis of an expectation-maximization procedure that achieves better accuracy in estimating the parameters of the model than the standard method of moments algorithmfromthe sociology literature. We extend the existing social network models to allow for indirect and asynchronous observations of the links. A Markov chain Monte Carlo sampling algorithm for this new model permits estimation and inference. We provide results on both a synthetic network (for verification) and real social network data.


title: A Sampling-Based Approach to Computing Equilibria in Succinct Extensive-Form Games

abstract: A central task of artificial intelligence is the design of artificial agents that act towards specified goals in partially observed environments. Since such environments frequently include interaction over time with other agents with their own goals, reasoning about such interaction relies on sequential game-theoretic models such as extensive-form games or some of their succinct representations such as multi-agent influence diagrams. The current algorithms for calculating equilibria either work with inefficient representations, possibly doubly exponential inthe number of time steps, or place strong assumptions on the game structure. In this paper,we propose a sampling-based approach, which calculates extensive-form correlated equilibria with small representations without placing such strong assumptions. Thus, it is practical in situations where the previous approaches would fail. In addition, our algorithm allows control over characteristics of the target equilibrium, e.g., we can ask for an equilibrium with high social welfare. Our approach is based on a multiplicativeweight update algorithm analogous to AdaBoost, and Markov chain Monte Carlo sampling. We prove convergence guarantees and explore the utility of our approach on several moderately sized multi-player games.


title: Correlated Non-Parametric Latent Feature Models

abstract: We are often interested in explaining data through a set of hidden factors or features. When the number of hidden features is unknown, the Indian Buffet Process (IBP) is a nonparametric latent feature model that does not bound the number of active features in dataset. However, the IBP assumes that all latent features are uncorrelated, making it inadequate for many realworld problems. We introduce a framework for correlated nonparametric feature models, generalising the IBP. We use this framework to generate several specific models and demonstrate applications on realworld datasets.


title: Seeing the Forest Despite the Trees: Large Scale Spatial-Temporal Decision Making

abstract: We introduce a challenging real-world planning problem where actions must be taken at each location in a spatial area at each point in time. We use forestry planning as the motivating application. In Large Scale Spatial-Temporal (LSST) planning problems, the state and action spaces are defined as the cross-products of many local state and action spaces spread over a large spatial area such as a city or forest. These problems possess state uncertainty, have complex utility functions involving spatial constraints and we generally must rely on simulations rather than an explicit transition model. We define LSST problems as reinforcement learning problems and present a solution using policy gradients. We compare two different policy formulations: an explicit policy that identifies each location in space and the action to take there; and an abstract policy that defines the proportion of actions to take across all locations in space. We show that the abstract policy is more robust and achieves higher rewards with far fewer parameters than the elementary policy. This abstract policy is also a better fit to the properties that practitioners in LSST problem domains require for such methods to be widely useful.


title: Complexity Analysis and Variational Inference for Interpretation-based Probabilistic Description Logic

abstract: This paper presents complexity analysis and variational methods for inference in probabilistic description logics featuring Boolean operators, quantification, qualified number restrictions, nominals, inverse roles and role hierarchies. Inference is shown to be PEXP-complete, and variational methods are designed so as to exploit logical inference whenever possible.


title: L2 Regularization for Learning Kernels

abstract: The choice of the kernel is critical to the success of many learning algorithms but it is typically left to the user. Instead, the training data can be used to learn the kernel by selecting it out of a given family, such as that of non-negative linear combinations of p base kernels, constrained by a trace or L1 regularization. This paper studies the problem of learning kernels with the same family of kernels but with an L2 regularization instead, and for regression problems. We analyze the problem of learning kernels with ridge regression. We derive the form of the solution of the optimization problem and give an efficient iterative algorithm for computing that solution. We present a novel theoretical analysis of the problem based on stability and give learning bounds for orthogonal kernels that contain only an additive term O(pp/m) when compared to the standard kernel ridge regression stability bound. We also report the results of experiments indicating that L1 regularization can lead to modest improvements for a small number of kernels, but to performance degradations in larger-scale cases. In contrast, L2 regularization never degrades performance and in fact achieves significant improvements with a large number of kernels.


title: Prediction Markets, Mechanism Design, and Cooperative Game Theory

abstract: Prediction markets are designed to elicit information from multiple agents in order to predict (obtain probabilities for) future events. A good prediction market incentivizes agents to reveal their information truthfully; such incentive compatibility considerations are commonly studied in mechanism design. While this relation between prediction markets and mechanism design is well understood at a high level, the models used in prediction markets tend to be somewhat different from those used in mechanism design. This paper considers a model for prediction markets that fits more straightforwardly into the mechanism design framework. We consider a number of mechanisms within this model, all based on proper scoring rules. We discuss basic properties of these mechanisms, such as incentive compatibility. We also draw connections between some of these mechanisms and cooperative game theory. Finally, we speculate how one might build a practical prediction market based on some of these ideas.


title: Mean Field Variational Approximation for Continuous-Time Bayesian Networks

abstract: Continuous-time Bayesian networks is a natural structured representation language for multicomponent stochastic processes that evolve continuously over time. Despite the compact representation, inference in such models is intractable even in relatively simple structured networks. Here we introduce a mean field variational approximation in which we use a product of inhomogeneous Markov processes to approximate a distribution over trajectories. This variational approach leads to a globally consistent distribution, which can be efficiently queried. Additionally, it provides a lower bound on the probability of observations, thus making it attractive for learning tasks. We provide the theoretical foundations for the approximation, an efficient implementation that exploits the wide range of highly optimized ordinary differential equations (ODE) solvers, experimentally explore characterizations of processes for which this approximation is suitable, and show applications to a large-scale realworld inference problem.


title: Convex Coding

abstract: Inspired by recent work on convex formulations of clustering (Lashkari & Golland, 2008; Nowozin & Bakir, 2008) we investigate a new formulation of the Sparse Coding Problem (Olshausen & Field, 1997). In sparse coding we attempt to simultaneously represent a sequence of data-vectors sparsely (i.e. sparse approximation (Tropp et al., 2006)) in terms of a 'code' defined by a set of basis elements, while also finding a code that enables such an approximation. As existing alternating optimization procedures for sparse coding are theoretically prone to severe local minima problems, we propose a convex relaxation of the sparse coding problem and derive a boosting-style algorithm, that (Nowozin & Bakir, 2008) serves as a convex 'master problem' which calls a (potentially non-convex) sub-problem to identify the next code element to add. Finally, we demonstrate the properties of our boosted coding algorithm on an image denoising task.


title: Multilingual Topic Models for Unaligned Text

abstract: We develop the multilingual topic model for unaligned text (MuTo), a probabilistic model of text that is designed to analyze corpora composed of documents in two languages. From these documents, MuTo uses stochastic EM to simultaneously discover both a matching between the languages and multilingual latent topics. We demonstrate that MuTo is able to find shared topics on real-world multilingual corpora, successfully pairing related documents across languages. MuTo provides a new framework for creating multilingual topic models without needing carefully curated parallel corpora and allows applications built using the topic model formalism to be applied to a much wider class of corpora.


title: Optimization of Structured Mean Field Objectives

abstract: In intractable, undirected graphical models, an intuitive way of creating structured mean field approximations is to select an acyclic tractable subgraph. We show that the hardness of computing the objective function and gradient of the mean field objective qualitatively depends on a simple graph property. If the tractable subgraph has this property- we call such subgraphs v-acyclic-a very fast block coordinate ascent algorithm is possible. If not, optimization is harder, but we show a new algorithm based on the construction of an auxiliary exponential family that can be used to make inference possible in this case as well. We discuss the advantages and disadvantages of each regime and compare the algorithms empirically.


title: Deterministic POMDPs Revisited

abstract: We study a subclass of POMDPs, called Deterministic POMDPs, that is characterized by deterministic actions and observations. These models do not provide the same generality of POMDPs yet they capture a number of interesting and challenging problems, and permit more efficient algorithms. Indeed, some of the recent work in planning is built around such assumptions mainly by the quest of amenable models more expressive than the classical deterministic models. We provide results about the fundamental properties of Deterministic POMDPs, their relation with AND/OR search problems and algorithms, and their computational complexity.


title: Alternating Projections for Learning with Expectation Constraints

abstract: We present an objective function for learning with unlabeled data that utilizes auxiliary expectation constraints. We optimize this objective function using a procedure that alternates between information and moment projections. Our method provides an alternate interpretation of the posterior regularization framework (Graca et al., 2008), maintains uncertainty during optimization unlike constraint-driven learning (Chang et al., 2007), and is more efficient than generalized expectation criteria (Mann & McCallum, 2008). Applications of this framework include minimally supervised learning, semisupervised learning, and learning with constraints that are more expressive than the underlying model. In experiments, we demonstrate comparable accuracy to generalized expectation criteria for minimally supervised learning, and use expressive structural constraints to guide semi-supervised learning, providing a 3%-6% improvement over stateof-the-art constraint-driven learning.


title: REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs

abstract: We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP). The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector. For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of ~O(HSpAT). We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds.


title: On Smoothing and Inference for Topic Models

abstract: Latent Dirichlet analysis, or topic modeling, is a flexible latent variable framework for modeling high-dimensional sparse count data. Various learning algorithms have been developed in recent years, including collapsed Gibbs sampling, variational inference, and maximum a posteriori estimation, and this variety motivates the need for careful empirical comparisons. In this paper, we highlight the close connections between these approaches. We find that the main differences are attributable to the amount of smoothing applied to the counts. When the hyperparameters are optimized, the differences in performance among the algorithms diminish significantly. The ability of these algorithms to achieve solutions of comparable accuracy gives us the freedom to select computationally efficient approaches. Using the insights gained from this comparative study, we show how accurate topic models can be learned in several seconds on text corpora with thousands of documents.


title: Are visual dictionaries generalizable?

abstract: Mid-level features based on visual dictionaries are today a cornerstone of systems for classification and retrieval of images. Those state-of-the-art representations depend crucially on the choice of a codebook (visual dictionary), which is usually derived from the dataset. In general-purpose, dynamic image collections (e.g., the Web), one cannot have the entire collection in order to extract a representative dictionary. However, based on the hypothesis that the dictionary reflects only the diversity of low-level appearances and does not capture semantics, we argue that a dictionary based on a small subset of the data, or even on an entirely different dataset, is able to produce a good representation, provided that the chosen images span a diverse enough portion of the low-level feature space. Our experiments confirm that hypothesis, opening the opportunity to greatly alleviate the burden in generating the codebook, and confirming the feasibility of employing visual dictionaries in large-scale dynamic environments.


title: A Bayesian Sampling Approach to Exploration in Reinforcement Learning

abstract: We present a modular approach to reinforcement learning that uses a Bayesian representation of the uncertainty over models. The approach, BOSS (Best of Sampled Set), drives exploration by sampling multiple models from the posterior and selecting actions optimistically. It extends previous work by providing a rule for deciding when to resample and how to combine the models. We show that our algorithm achieves nearoptimal reward with high probability with a sample complexity that is low relative to the speed at which the posterior distribution converges during learning. We demonstrate that BOSS performs quite favorably compared to state-of-the-art reinforcement-learning approaches and illustrate its flexibility by pairing it with a non-parametric model that generalizes across states.


title: Lower Bound Bayesian Networks - An Efficient Inference of Lower Bounds on Probability Distributions in Bayesian Networks

abstract: We present a new method to propagate lower bounds on conditional probability distributions in conventional Bayesian networks. Our method guarantees to provide outer approximations of the exact lower bounds. A key advantage is that we can use any available algorithms and tools for Bayesian networks in order to represent and infer lower bounds. This new method yields results that are provable exact for trees with binary variables, and results which are competitive to existing approximations in credal networks for all other network structures. Our method is not limited to a specific kind of network structure. Basically, it is also not restricted to a specific kind of inference, but we restrict our analysis to prognostic inference in this article. The computational complexity is superior to that of other existing approaches.


title: Non-modal analysis of the diocotron instability. Plane geometry

abstract: The comprehensive investigation of the temporal evolution of the diocotron instability of the plane electron strip on the linear stage of its development is performed. By using the Kelvin's method of the shearing modes we elucidate the role of the initial perturbations of the electron density, which is connected with problem of the continuous spectrum. The linear non-modal evolution process, detected by the solution of the initial value problem, leads towards convergence to the phase-locking configuration of the mutually growing normal modes.


title: Multipartite Entanglement Evolution Under Separable Operations

abstract: We study how multi-partite entanglement evolves under the paradigm of separable operations, which include the local operations and classical communication (LOCC) as a special case. We prove that the average "decay" of entanglement induced by a separable operation is measure independent (among SL-invariant ones) and state independent: the ratio between the average output entanglement and the initial entanglement is solely a function of the separable operation, regardless of the input state and of the SL-invariant entanglement measure being used. We discuss the "disentangling power" of a quantum channel and show that it exhibits a similar state invariance as the average entanglement decay ratio. Our Rapid Communication significantly extends the bipartite results of Ref. [1-3] as well as the multi-partite one of Ref. [4], all of the previous work being restricted to one-sided or particular noise models.


title: Hyperbolic Components

abstract: Consider polynomial maps $f:\C\to\C$ of degree $d\ge 2$, or more generally polynomial maps from a finite union of copies of $\C$ to itself. In the space of suitably normalized maps of this type, the hyperbolic maps form an open set called the hyperbolic locus. The various connected components of this hyperbolic locus are called hyperbolic components, and those hyperbolic components with compact closure (or equivalently those contained in the "connectedness locus") are called bounded hyperbolic components. It is shown that each bounded hyperbolic component is a topological cell containing a unique post-critically finite map called its center point. For each degree $d$, the bounded hyperbolic components can be separated into finitely many distinct types, each of which is characterized by a suitable reduced mapping scheme $\bar S_f$. Any two components with the same reduced mapping scheme are canonically biholomorphic to each other. There are similar statementsfor real polynomial maps, for polynomial maps with marked critical points, and for rational maps. Appendix A, by Alfredo Poirier, proves that every reduced mapping scheme can be represented by some classical hyperbolic component, made up of polynomial maps of $\C$. This paper is a revised version of [M2], which was circulated but not published in 1992.


title: Pseudogap behavior of RuP probed by photoemission spectroscopy

abstract: We have studied the electronic structure of RuP and related Ru pnictides using photoemission spectroscopy. Ru 3d core-level and valence-band spectra of RuP show that the Ru valence is +3 with t_{2g}^5 configuration. The photoemisson spectral weight near the Fermi level is moderately suppressed in the pseudogap phase of RuP, consistent with the pseudogap opening of 2\Delta/k_BT_c ~ 3 (gap size \Delta ~ 50 meV and transition temperature T_c ~ 330 K). The Ru 3d peak remains sharp in the pseudogap phase and the insulating phase of RuP, suggesting that the electronic orderings responsible for the phase transitions are different from the conventional charge density wave.


title: Intelligent learning environments within blended learning for ensuring effective C programming course

abstract: This paper describes a blended learning implementation and experience supported with intelligent learning environments included in a learning management system (LMS) called @KU-UZEM. The blended learning model is realized as a combination of face to face education and e-learning. The intelligent learning environments consist of two applications named CTutor, ITest. In addition to standard e-learning tools, students can use CTutor to resolve C programming exercises. CTutor is a problem-solving environment, which diagnoses students' knowledge level but also gives feedbacks and tips to help them to understand the course subject, overcome their misconceptions and reinforce learnt concepts. ITest provides an assessment environment in which students can take quizzes that were prepared according to their learning levels. The realized model was used for two terms in the "C Programming" course given at Afyon Kocatepe University. A survey was conducted at the end of the course to find out to what extent the students were accepting the blended learning model supported with @KU-UZEM and to discover students' attitude towards intelligent learning environments. Additionally, an experiment formed with an experimental group who took an active part in the realized model and a control group who only took the face to face education was performed during the first term of the course. According to the results, students were satisfied with intelligent learning environments and the realized learning model. Furthermore, the use of intelligent learning environments improved the students' knowledge about C programming.


abstract: The Proceedings of the 2011 workshop on Fundamental Physics at the Intensity Frontier. Science opportunities at the intensity frontier are identified and described in the areas of heavy quarks, charged leptons, neutrinos, proton decay, new light weakly-coupled particles, and nucleons, nuclei, and atoms.


title: Electronic structure of CrN: A comparison between different exchange correlation potentials

abstract: We report a series of electronic structure calculations for CrN using different exchange correlation potentials: PBE, LDA+$U$, the Tran-Blaha modified Becke-Johnson, and hybrid functionals. In every case, our calculations show that the onset of magnetism in CrN should be accompanied by a gap opening. The experimentally found antiferromagnetic order always leads to an insulating behavior. Our results give further evidence that the Tran-Blaha functional is very useful for treating the electronic structure of correlated semiconductors allowing a parameter free description of the system. Hybrid functionals are also well capable of describing the electronic structure of CrN. The analysis of the system is complemented with our calculations of the thermopower that are in agreement with the experimental data.


title: Anisotropic Energy Gaps of Iron-based Superconductivity from Intra-band Quasiparticle Interference in LiFeAs

abstract: If strong electron-electron interactions between neighboring Fe atoms mediate the Cooper pairing in iron-pnictide superconductors, then specific and distinct anisotropic superconducting energy gaps \Delta_i(k) should appear on the different electronic bands i. Here we introduce intra-band Bogoliubov quasiparticle scattering interference (QPI) techniques for determination of \Delta_i(k) in such materials, focusing on LiFeAs. We identify the three hole-like bands assigned previously as \gamma, \alpha_2 and \alpha_1, and we determine the anisotropy, magnitude and relative orientations of their \Delta_i(k). These measurements will advance quantitative theoretical analysis of the mechanism of Cooper pairing in iron-based superconductivity.


title: Improved numerical methods for infinite spin chains with long-range interactions

abstract: We present several improvements of the infinite matrix product state (iMPS) algorithm for finding ground states of one-dimensional quantum systems with long-range interactions. As a main new ingredient we introduce the superposed multi-optimization (SMO) method, which allows an efficient optimization of exponentially many MPS of different length at different sites all in one step. Hereby the algorithm becomes protected against position dependent effects as caused by spontaneously broken translational invariance. So far, these have been a major obstacle to convergence for the iMPS algorithm if no prior knowledge of the systems translational symmetry was accessible. Further, we investigate some more general methods to speed up calculations and improve convergence, which might be partially interesting in a much broader context, too. As a more special problem, we also look into translational invariant states close to an invariance braking phase transition and show how to avoid convergence into wrong local minima for such systems. Finally, we apply the new methods to polar bosons with long-range interactions. We calculate several detailed Devil's Staircases with the corresponding phase diagrams and investigate some supersolid properties.


title: Quantum Mechanics, Gravity, and the Multiverse

abstract: The discovery of accelerating expansion of the universe has led us to take the dramatic view that our universe may be one of the many universes in which low energy physical laws take different forms: the multiverse. I explain why/how this view is supported both observationally and theoretically, especially by string theory and eternal inflation. I then describe how quantum mechanics plays a crucial role in understanding the multiverse, even at the largest distance scales. The resulting picture leads to a revolutionary change of our view of spacetime and gravity, and completely unifies the paradigm of the eternally inflating multiverse with the many worlds interpretation of quantum mechanics. The picture also provides a solution to a long-standing problem in eternal inflation, called the measure problem, which I briefly describe.

categories: hep-th astro-ph.CO gr-qc hep-ph quant-ph


title: On the logarithmic connections over curves

abstract: We study two different actions on the moduli spaces of logarithmic connections over smooth complex projective curves. Firstly, we establish a dictionary between logarithmic orbifold connections and parabolic logarithmic connections over the quotient curve. Secondly, we prove that fixed points on the moduli space of connections under the action of finite order line bundles are exactly the push-forward of logarithmic connections on a certain unramified Galois cover of the base curve. In the coprime case, this action of finite order line bundles on the moduli space is cohomologically trivial.


title: Purity Relative to Classes of Finitely Presented Modules

abstract: We investigate purities determined by classes of finitely presented modules including the correspondence between purities for left and right modules. We show some cases where purities determined by matrices of given sizes are different. Then we consider purities over finite-dimensional algebras, giving a general description of the relative pure injectives which we make completely explicit in the case of tame hereditary algebras.


title: Evaluation of Proactive, Reactive and Hybrid Ad hoc Routing Protocol for various Battery models in VANET using Qualnet

abstract: In VANET high speed is the real characteristics which leads frequent breakdown, interference etc. In this paper we studied various Ad hoc routing protocols, Reactive, Proactive & Hybrid, taking into consideration various VANET parameters like speed, altitude etc in real traffic scenario and evaluated them for various battery models for energy conservation.. The AODV and DYMO (Reactive), OLSR (Proactive) and ZRP (hybrid) protocols are compared for battery models Duracell AA(MX- 1500),Duracell AAA(MN-2400),Duracell AAA(MX-2400), Duracell C-MN(MN-1400),Panasonic AA standard using Qualnet as a Simulation tool. Since Energy conservation is main focus area nowadays. Hence performance of the protocols with various battery models counts and helps to make a right selection. Varying parameters of VANET shows that in the real traffic scenarios proactive protocol performs more efficiently for energy conservation.


title: Testing means from sampling populations with undefined labels

abstract: We consider the problem of testing means from samples of two populations for which the labels are not defined with certainty. We show that this problem is connected to another one that is testing expected values of components of mixture-models from two data samples. The underlying mixture-model is associated with known varying mixing-weights. We provide a testing procedure that performs well. Then we point out the loss of performance of our method due to the mixing-effect by comparing its numerical performances to the Welch's t-test on means which would have been done if true labels were available.


title: Operationalization of Relativistic Motion

abstract: We demonstrate the definition of basic observables from physical operations, the key to overcome hidden stumbling blocks and apparent paradoxes from unscrutinized (classical) formalisms. We develop Helmholtz program of basic measurements for relativistic motion. We define the basic observables by direct comparison: "longer than" if one object or process covers the other. To express the spatiotemporal order also numerically (how many times longer) we cover them by a locally regular grid of light clocks. These are the basic physical operations. From their interrelation we derive mathematical relations, e.g. for different observers the formal Lorentz transformation; for accelerating observers we reveal a measurement-methodical view on the apparent Twin paradox.


title: Detectability of Symbol Manipulation by an Amplify-and-Forward Relay

abstract: This paper studies the problem of detecting a potential malicious relay node by a source node that relies on the relay to forward information to other nodes. The channel model of two source nodes simultaneously sending symbols to a relay is considered. The relay is contracted to forward the symbols that it receives back to the sources in the amplify-and-forward manner. However there is a chance that the relay may send altered symbols back to the sources. Each source attempts to individually detect such malicious acts of the relay by comparing the empirical distribution of the symbols that it receives from the relay conditioned on its own transmitted symbols with known stochastic characteristics of the channel. It is shown that maliciousness of the relay can be asymptotically detected with sufficient channel observations if and only if the channel satisfies a non-manipulable condition, which can be easily checked. As a result, the non-manipulable condition provides us a clear-cut criterion to determine the detectability of the aforementioned class of symbol manipulation attacks potentially conducted by the relay.


title: Convergence in total variation on Wiener chaos

abstract: Let ${F_n}$ be a sequence of random variables belonging to a finite sum of Wiener chaoses. Assume further that it converges in distribution towards $F_\infty$ satisfying ${\rm Var}(F_\infty)>0$. Our first result is a sequential version of a theorem by Shigekawa (1980). More precisely, we prove, without additional assumptions, that the sequence ${F_n}$ actually converges in total variation and that the law of $F_\infty$ is absolutely continuous. We give an application to discrete non-Gaussian chaoses. In a second part, we assume that each $F_n$ has more specifically the form of a multiple Wiener-It\^o integral (of a fixed order) and that it converges in $L^2(\Omega)$ towards $F_\infty$. We then give an upper bound for the distance in total variation between the laws of $F_n$ and $F_\infty$. As such, we recover an inequality due to Davydov and Martynova (1987); our rate is weaker compared to Davydov and Martynova (1987) (by a power of 1/2), but the advantage is that our proof is not only sketched as in Davydov and Martynova (1987). Finally, in a third part we show that the convergence in the celebrated Peccati-Tudor theorem actually holds in the total variation topology.


title: The Avalanche Mechanism for Atom Loss near an Atom-Dimer Efimov Resonance

abstract: An Efimov trimer near the atom-dimer threshold can increase the atom loss rate in ultracold trapped atoms through the {\it avalanche mechanism} proposed by Zaccanti et al. A 3-body recombination event creates an energetic atom and dimer, whose subsequent elastic collisions produce additional atoms with sufficient energy to escape from the trapping potential. We use Monte Carlo methods to calculate the average number of atoms lost and the average heat generated by recombination events in both a Bose-Einstein condensate and a thermal gas. We take into account the energy-dependence of the cross sections and the spatial structure of the atom cloud. We confirm that the number of atoms lost can be much larger than the naive value 3 if there is an Efimov trimer near the atom-dimer threshold. This does not produce a narrow loss feature, but it can significantly affect the determination of Efimov parameters.


title: Convergence in law in the second Wiener/Wigner chaos

abstract: Let L be the class of limiting laws associated with sequences in the second Wiener chaos. We exhibit a large subset L_0 of L satisfying that, for any F_infinity in L_0, the convergence of only a finite number of cumulants suffices to imply the convergence in law of any sequence in the second Wiener chaos to F_infinity. This result is in the spirit of the seminal paper by Nualart and Peccati, in which the authors discovered the surprising fact that convergence in law for sequences of multiple Wiener-It\^o integrals to the Gaussian is equivalent to convergence of just the fourth cumulant. Also, we offer analogues of this result in the case of free Brownian motion and double Wigner integrals, in the context of free probability.


title: Thin-shell wormholes with a generalized Chaplygin gas in Einstein-Born-Infeld theory

abstract: We construct spherically symmetric thin-shell wormholes supported by a generalized Chaplygin gas in Born-Infeld electrodynamics coupled to Einstein gravity, and we analyze their stability under radial perturbations. For different values of the Born-Infeld parameter and the charge, we compare the results with those obtained in a previous work for Maxwell electrodynamics. The stability region in the parameter space reduces and then disappears as the value of the Born-Infeld parameter is modified in the sense of a larger departure from Maxwell theory.


title: Reduced Criteria for Degree Sequences

abstract: For many types of graphs, criteria have been discovered that give necessary and sufficient conditions for an integer sequence to be the degree sequence of such a graph. These criteria tend to take the form of a set of inequalities, and in the case of the Erd\H{o}s-Gallai criterion (for simple undirected graphs) and the Gale-Ryser criterion (for bipartite graphs), it has been shown that the number of inequalities that must be checked can be reduced significantly. We show that similar reductions hold for the corresponding criteria for many other types of graphs, including bipartite r-multigraphs, bipartite graphs with structural edges, directed graphs, r-multigraphs, and tournaments. We also prove a reduction for imbalance sequences.


title: If players are sparse social dilemmas are too: Importance of percolation for evolution of cooperation

abstract: Spatial reciprocity is a well known tour de force of cooperation promotion. A thorough understanding of the effects of different population densities is therefore crucial. Here we study the evolution of cooperation in social dilemmas on different interaction graphs with a certain fraction of vacant nodes. We find that sparsity may favor the resolution of social dilemmas, especially if the population density is close to the percolation threshold of the underlying graph. Regardless of the type of the governing social dilemma as well as particularities of the interaction graph, we show that under pairwise imitation the percolation threshold is a universal indicator of how dense the occupancy ought to be for cooperation to be optimally promoted. We also demonstrate that myopic updating, due to the lack of efficient spread of information via imitation, renders the reported mechanism dysfunctional, which in turn further strengthens its foundations.


title: 130 GeV dark matter and the Fermi gamma-ray line

abstract: Based on tentative evidence for a peak in the Fermi gamma-ray spectrum originating from near the center of the galaxy, it has been suggested that dark matter of mass ~130 GeV is annihilating directly into photons with a cross section ~24 times smaller than that needed for the thermal relic density. We propose a simple particle physics model in which the DM is a scalar X, with a coupling lambda_X X^2|S|^2 to a scalar multiplet S carrying electric charge, which allows for XX -> gamma gamma at one loop due to the virtual S. We predict a second monochromatic photon peak at 114 GeV due to XX-> gamma Z. The S is colored under a hidden sector SU(N) or QCD to help boost the XX -> gamma gamma cross section. The analogous coupling lambda_h h^2 |S|^2 to the Higgs boson can naturally increase the partial width for h -> gamma gamma by an amount comparable to its standard model value, as suggested by recent measurements from CMS. Due to the hidden sector SU(N) (or QCD), S binds to its antiparticle to form S-mesons, which will be pair-produced in colliders and then decay predominantly to XX, hh, or to glueballs of the SU(N) which subsequently decay to photons. The cross section for X on nucleons is close to the Xenon100 upper limit, suggesting that it should be discovered soon by direct detection.


title: Principles for a unified picture of fermions

abstract: It is shown that a chiral SU(2) model can break Lorentz symmetry spontaneously at the Lagrangian level when gauge bosons become massive. This model seems to propose the principles and conceptual foundations leading to a unified picture of fermions, and may reduce the standard theory to a far simpler form. The model suggests describing leptons and quarks as quasi-excitations, while electromagnetic and strong interactions as secondary interactions mediated by Nambu-Goldstone bosons originating from spontaneous violations of global SU(2) and rotational symmetries. Both the possibility of observing Lorentz-violating phenomena and their magnitudes are discussed. The model also provides an alternative scenario for baryon and lepton asymmetries of the Universe.


title: Spontaneously Broken Erlangen Program Offers a Bridge Between the Einstein and the Yang-Mills Theories

abstract: We shall give dynamics to our spacetime manifold by first identifying the local affine symmetry as the characterizing symmetry for our geometry \'a la Felix Klein, and then by prescribing 16 gauge vector bosons to this symmetry \'a la Yang and Mills. The locally affine symmetric Yang-Mills Lagrangian in the presence of a background world metric, and the corresponding equations of motion, are respectively constructed and derived. Spontaneous breaking of the local affine symmetry to the local Lorentz symmetry is achieved by classical solutions to the equations of motion. In these classical solutions, the 16 gauge vector bosons are shown to select the Schwarzschild metric as one among the admissible background world metrics. Classical gravity is expressed by a spontaneously broken Erlangen program.


title: Improving Schema Matching with Linked Data

abstract: With today's public data sets containing billions of data items, more and more companies are looking to integrate external data with their traditional enterprise data to improve business intelligence analysis. These distributed data sources however exhibit heterogeneous data formats and terminologies and may contain noisy data. In this paper, we present a novel framework that enables business users to semi-automatically perform data integration on potentially noisy tabular data. This framework offers an extension to Google Refine with novel schema matching algorithms leveraging Freebase rich types. First experiments show that using Linked Data to map cell values with instances and column headers with types improves significantly the quality of the matching results and therefore should lead to more informed decisions.


title: LHC explores what LEP hinted at: CP-violating type-I 2HDM

abstract: The Large Hadron Collider is shown to have great scope for a light charged Higgs discovery, in the context of the CP-violating type-I two Higgs doublet model. This scenario with similar masses of $H^\pm$ and W was suggested by the puzzling departure from charged current lepton universality found in the LEP data. With the lightest neutral Higgs mass set to 125 GeV, the charged-neutral Higgs associated production mechanism can cause a significant excess in the $\tau \nu b \bar{b}$ events over a vast range of tan beta as long as the Higgs mixing pattern avoids a few limiting cases. Thanks to the low $H^\pm$ mass, the charged Higgs loop can play a striking role in neutral Higgs decays into $\gamma \gamma$, thereby compensating for a suppressed gluon-gluon fusion rate. The effect of scalar-pseudo-scalar mixing on loop-induced Higgs signals is also discussed.


title: The velocity dispersion and mass function of the outer halo globular cluster Palomar 4

abstract: We obtained precise line-of-sight radial velocities of 23 member stars of the remote halo globular cluster Palomar 4 (Pal 4) using the High Resolution Echelle Spectrograph (HIRES) at the Keck I telescope. We also measured the mass function of the cluster down to a limiting magnitude of V~28 mag using archival HST/WFPC2 imaging. We derived the cluster's surface brightness profile based on the WFPC2 data and on broad-band imaging with the Low-Resolution Imaging Spectrometer (LRIS) at the Keck II telescope. We find a mean cluster velocity of 72.55+/-0.22 km/s and a velocity dispersion of 0.87+/-0.18 km/s. The global mass function of the cluster, in the mass range 0.55<=M<=0.85 M_solar, is shallower than a Kroupa mass function and the cluster is significantly depleted in low-mass stars in its center compared to its outskirts. Since the relaxation time of Pal 4 is of the order of a Hubble time, this points to primordial mass segregation in this cluster. Extrapolating the measured mass function towards lower-mass stars and including the contribution of compact remnants, we derive a total cluster mass of 29800 M_solar. For this mass, the measured velocity dispersion is consistent with the expectations of Newtonian dynamics and below the prediction of Modified Newtonian Dynamics (MOND). Pal 4 adds to the growing body of evidence that the dynamics of star clusters in the outer Galactic halo can hardly be explained by MOND.


title: Shaping the galaxy stellar mass function with supernova- and AGN-driven winds

abstract: Cosmological hydrodynamical simulations of galaxy formation in representative regions of the Universe typically need to resort to subresolution models to follow some of the feedback processes crucial for galaxy formation. Here, we show that an energy-driven outflow model in which the wind velocity decreases and the wind mass loading increases in low-mass galaxies, as suggested by observations, can produce a good match to the low-mass end of the observed galaxy stellar mass function. The high-mass end can be recovered simultaneously if feedback from active galactic nuclei (AGN) and a correction for diffuse stellar light plausibly missed in observations are included. At the same time, our model is in good agreement with the stellar mass functions at redshifts z=1 and z=2, and with the observed redshift evolution of the cosmic star formation rate density. In addition, it accurately reproduces the observed gas to stellar mass ratios and specific star formation rates of galaxies as a function of their stellar mass. This agreement with a diverse set of data marks significant progress in hydrodynamically modelling the formation of a representative galaxy population. It also suggests that the mass flux in real galactic winds should strongly increase towards low-mass galaxies. Without this assumption, an overproduction of galaxies at the faint-end of the galaxy luminosity function seems inevitable in our models.


title: WIMP-nucleus scattering in chiral effective theory

abstract: We discuss long-distance QCD corrections to the WIMP-nucleon(s) interactions in the framework of chiral effective theory. For scalar-mediated WIMP-quark interactions, we calculate all the next-to-leading-order corrections to the WIMP-nucleus elastic cross-section, including two-nucleon amplitudes and recoil-energy dependent shifts to the single-nucleon scalar form factors. As a consequence, the scalar-mediated WIMP-nucleus cross-section cannot be parameterized in terms of just two quantities, namely the neutron and proton scalar form factors at zero momentum transfer, but additional parameters appear, depending on the short-distance WIMP-quark interaction. Moreover, multiplicative factorization of the cross-section into particle, nuclear and astro-particle parts is violated. In practice, while the new effects are of the natural size expected by chiral power counting, they become very important in those regions of parameter space where the leading order WIMP-nucleus amplitude is suppressed, including the so-called "isospin-violating dark matter" regime. In these regions of parameter space we find order-of-magnitude corrections to the total scattering rates and qualitative changes to the shape of recoil spectra.


title: Stop searches in 2012

abstract: For this year's 8TeV run of the LHC we lay out different strategies to search for scalar top pairs. We show results for the hadronic and for the semi-leptonic channels based on hadronic top tagging. For the di-lepton channel we illustrate the impact of transverse mass variables. Each of our signal-to-background ratios ranges around unity for a stop mass around 400GeV. The combined signal significances show that dedicated stop searches are becoming sensitive over a non-negligible part of parameter space.