@Proceedings{UAI2009, title = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, editor = {Jeff Bilmes and Andrew Y. Ng}, publisher = {PMLR}, series = {Proceedings of Machine Learning Research}, volume = R7 } @InProceedings{pmlr-vR7-allahverdyan09a, title = {On Maximum a Posteriori Estimation of Hidden {M}arkov Processes}, author = {Allahverdyan, Armen and Galstyan, Aram}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {1--9}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/allahverdyan09a/allahverdyan09a.pdf}, url = {https://proceedings.mlr.press/r7/allahverdyan09a.html}, abstract = {We present a theoretical analysis of Maximum a Posteriori (MAP) sequence estimation for binary symmetric hidden Markov processes. We reduce the MAP estimation to the energy minimization of an appropriately defined Ising spin model, and focus on the performance of MAP as characterized by its accuracy and the number of solutions corresponding to a typical observed sequence. It is shown that for a finite range of sufficiently low noise levels, the solution is uniquely related to the observed sequence, while the accuracy degrades linearly with increasing the noise strength. For intermediate noise values, the accuracy is nearly noise-independent, but now there are exponentially many solutions to the estimation problem, which is reflected in non-zero ground-state entropy for the Ising model. Finally, for even larger noise intensities, the number of solutions reduces again, but the accuracy is poor. It is shown that these regimes are different thermodynamic phases of the Ising model that are related to each other via first-order phase transitions.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-andrade09a, title = {Lower Bound {B}ayesian Networks - Efficient Inference of Lower Bounds on Probability Distributions}, author = {Andrade, Daniel and Sick, Bernhard}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {10--18}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/andrade09a/andrade09a.pdf}, url = {https://proceedings.mlr.press/r7/andrade09a.html}, abstract = {We present a new method to propagate lower bounds on conditional probability distribu- tions in conventional Bayesian networks. Our method guarantees to provide outer approx- imations 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 prov- able exact for trees with binary variables, and results which are competitive to existing ap- proximations in credal networks for all other network structures. Our method is not lim- ited 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-asuncion09a, title = {On Smoothing and Inference for Topic Models}, author = {Asuncion, Arthur and Welling, Max and Smyth, Padhraic and Teh, Yee Whye}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {19--26}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/asuncion09a/asuncion09a.pdf}, url = {https://proceedings.mlr.press/r7/asuncion09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-bartlett09a, title = {{REGAL}: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs}, author = {Bartlett, Peter and Tewari, Ambuj}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {27--34}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/bartlett09a/bartlett09a.pdf}, url = {https://proceedings.mlr.press/r7/bartlett09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-bellare09a, title = {Alternating Projections for Learning with Expectation Constraints}, author = {Bellare, Kedar and Druck, Gregory and McCallum, Andrew}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {35--42}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/bellare09a/bellare09a.pdf}, url = {https://proceedings.mlr.press/r7/bellare09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-beygelzimer09a, title = {Conditional Probability Tree Estimation Analysis and Algorithms}, author = {Beygelzimer, Alina and Langford, John and Lifshits, Yury and Sorkin, Gregory and Strehl, Alex}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {43--50}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/beygelzimer09a/beygelzimer09a.pdf}, url = {https://proceedings.mlr.press/r7/beygelzimer09a.html}, abstract = {We consider the problem of estimating the conditional probability of a label in time $O(\log n)$, where $n$ is the number of possible labels. We analyze a natural reduction of this problem to a set of binary regression problems organized in a tree structure, proving a regret bound that scales with the depth of the tree. Motivated by this analysis, we propose the first online algorithm which provably constructs a logarithmic depth tree on the set of labels to solve this problem. We test the algorithm empirically, showing that it works succesfully on a dataset with roughly $10^6$ labels.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-bonet09a, title = {Deterministic POMDPs Revisited}, author = {Bonet, Blai}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {51--58}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/bonet09a/bonet09a.pdf}, url = {https://proceedings.mlr.press/r7/bonet09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-bouchard-cote09a, title = {Optimization of Structured Mean Field Objectives}, author = {Bouchard-C{\^o}t{\'e}, Alexandre and Jordan, Mike}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {59--66}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/bouchard-cote09a/bouchard-cote09a.pdf}, url = {https://proceedings.mlr.press/r7/bouchard-cote09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-boyd-graber09a, title = {Multilingual Topic Models for Unaligned Text}, author = {Boyd-Graber, Jordan and Blei, David}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {67--74}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/boyd-graber09a/boyd-graber09a.pdf}, url = {https://proceedings.mlr.press/r7/boyd-graber09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-bradley09a, title = {Convex Coding}, author = {Bradley, David and Bagnell, J. Andrew}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {75--82}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/bradley09a/bradley09a.pdf}, url = {https://proceedings.mlr.press/r7/bradley09a.html}, 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 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 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-vigorito09a, title = {Temporal Difference Networks for Dynamical Systems with Continuous Observations and Actions}, author = {Vigorito, Christopher M.}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {83--90}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/vigorito09a/vigorito09a.pdf}, url = {https://proceedings.mlr.press/r7/vigorito09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-cohn09a, title = {Mean Field Variational Approximation for Continuous-Time {B}ayesian Networks}, author = {Cohn, Ido and El-hay, Tal and Friedman, Nir and Kupferman, Raz}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {91--100}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/cohn09a/cohn09a.pdf}, url = {https://proceedings.mlr.press/r7/cohn09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-conitzer09a, title = {Prediction Markets, Mechanism Design, and Cooperative Game Theory}, author = {Conitzer, Vincent}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {101--108}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/conitzer09a/conitzer09a.pdf}, url = {https://proceedings.mlr.press/r7/conitzer09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-cortes09a, title = {$L_2$ Regularization for Learning Kernels}, author = {Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {109--116}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/cortes09a/cortes09a.pdf}, url = {https://proceedings.mlr.press/r7/cortes09a.html}, 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-negativelinear combi- nations of p base kernels, constrained by a trace or L1 regularization. This paper studies the prob- lem of learning kernels with the same family of kernels but with an L2 regularization instead, and for regression problems. We analyze the prob- lem of learning kernels with ridge regression. We derive the form of the solution of the optimiza- tion problem and give an efficient iterative algo- rithm for computing that solution. We present a novel theoretical analysis of the problem based on stability and give learning bounds for orthog- onal kernels that contain only an additive term O( p p/m) when compared to the standard ker- nel ridge regression stability bound. We also re- port 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-cozman09a, title = {Complexity Analysis and Variational Inference for Interpretation-based Probabilistic Description Logic}, author = {Cozman, Fabio and Polastro, Rodrigo}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {117--125}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/cozman09a/cozman09a.pdf}, url = {https://proceedings.mlr.press/r7/cozman09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-crowley09a, title = {Seeing the Forest Despite the Trees: Large Scale Spatial-Temporal Decision Making}, author = {Crowley, Mark and Poole, David and Nelson, John}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {126--134}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/crowley09a/crowley09a.pdf}, url = {https://proceedings.mlr.press/r7/crowley09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-daume09a, title = {{B}ayesian Multitask Learning with Latent Hierarchies}, author = {Daume, Hal}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {135--142}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/daume09a/daume09a.pdf}, url = {https://proceedings.mlr.press/r7/daume09a.html}, abstract = {We learn multiple hypotheses for related tasks under a latent hierarchical relationship between tasks. We exploit the intuition that for domain adaptation, we wish to share classifier structure, but for multitask learning, we wish to share covariance structure. Our hierarchical model is seen to subsume several previously proposed multitask learning models and performs well on three distinct real-world data sets.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-doshi-velez09a, title = {Correlated Non-Parametric Latent Feature Models}, author = {Doshi-Velez, Finale and Ghahramani, Zoubin}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {143--150}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/doshi-velez09a/doshi-velez09a.pdf}, url = {https://proceedings.mlr.press/r7/doshi-velez09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-dudik09a, title = {A Sampling-Based Approach to Computing Equilibria in Succinct Extensive-Form Games}, author = {Dudik, Miroslav and Gordon, Geoffrey}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {151--160}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/dudik09a/dudik09a.pdf}, url = {https://proceedings.mlr.press/r7/dudik09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-fan09a, title = {Learning Continuous-Time Social Network Dynamics}, author = {Fan, Yu and Shelton, Christian}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {161--168}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/fan09a/fan09a.pdf}, url = {https://proceedings.mlr.press/r7/fan09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-finegold09a, title = {Robust Graphical Modelling with t-Distributions}, author = {Finegold, Michael and Drton, Mathias}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {169--176}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/finegold09a/finegold09a.pdf}, url = {https://proceedings.mlr.press/r7/finegold09a.html}, abstract = {Graphical Gaussian models have proven to be useful tools for exploring network structures based on multivariate data. Applications to studies of gene expression have generated substantial interest in these models, and resulting recent progress includes the development of fitting methodology involving penalization of the likelihood function. In this paper we advocate the use of the multivariate t and related distributions for more robust inference of graphs. In particular, we demonstrate that penalized likelihood inference combined with an application of the EM algorithm provides a simple and computationally efficient approach to model selection in the t-distribution case. 1}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-fritz09a, title = {Generating Optimal Plans in Highly-Dynamic Domains}, author = {Fritz, Christian and McIlraith, Sheila}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {177--184}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/fritz09a/fritz09a.pdf}, url = {https://proceedings.mlr.press/r7/fritz09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-gomez09a, title = {Approximate inference on planar graphs using Loop Calculus and Belief Propagation}, author = {G{\'o}mez, Vicen{\c{c}} and Kappen, Bert and Chertkov, Misha}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {185--192}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/gomez09a/gomez09a.pdf}, url = {https://proceedings.mlr.press/r7/gomez09a.html}, abstract = {We introduce novel results for approximate inference on planar graphical models using the loop calculus framework. The loop calculus (Chertkov and Chernyak, 2006) allows to express the exact partition function of a graphical model as a finite sum of terms that can be evaluated once the belief propagation (BP) solution is known. In general, full summation over all correction terms is intractable. We develop an algorithm for the approach presented in (Certkov et al., 2008) which represents an efficient truncation scheme on planar graphs and a new representation of the series in terms of Pfaffians of matrices. We analyze the performance of the algorithm for the partition function approximation for models with binary variables and pairwise interactions on grids and other planar graphs. We study in detail both the loop series and the equivalent Pfaffian series and show that the first term of the Pfaffian series for the general, intractable planar model, can provide very accurate approximations. The algorithm outperforms previous truncation schemes of the loop series and is competitive with other state-of-the-art methods for approximate inference.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-ganchev09a, title = {Censored Exploration and the Dark Pool Problem}, author = {Ganchev, Kuzman and Kearns, Michael and Nevmyvaka, Yuriy and Wortman, Jennifer}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {193--202}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/ganchev09a/ganchev09a.pdf}, url = {https://proceedings.mlr.press/r7/ganchev09a.html}, abstract = {Dark pools are a recent type of stock exchange in which information about outstanding orders is deliberately hidden in order to minimize the market impact of large-volume trades. The success and proliferation of dark pools have created challenging and interesting problems in algorithmic trading—in particular, the problem of optimizing the allocation of a large trade over multiple competing dark pools. In this work, we formalize this optimization as a problem of multi-venue exploration from censored data, and provide a provably efficient and near-optimal algorithm for its solution. Our algorithm and its analysis have much in common with well-studied algorithms for managing the exploration–exploitation trade-off in reinforcement learning. We also provide an extensive experimental evaluation of our algorithm using dark pool execution data from a large brokerage.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-gonzalez09a, title = {Distributed Parallel Inference on Large Factor Graphs}, author = {Gonzalez, Joseph and Low, Yucheng and Guestrin, Carlos and O'Hallaron, David}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {203--212}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/gonzalez09a/gonzalez09a.pdf}, url = {https://proceedings.mlr.press/r7/gonzalez09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-gordon09a, title = {First-Order Mixed Integer Linear Programming}, author = {Gordon, Geoffrey and Hong, Sue Ann and Dudik, Miroslav}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {213--222}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/gordon09a/gordon09a.pdf}, url = {https://proceedings.mlr.press/r7/gordon09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-hoffman09a, title = {New inference strategies for solving {M}arkov Decision Processes using reversible jump {MCMC}}, author = {Hoffman, Matt and Kueck, Hendrik and de Freitas, Nando and Doucet, Arnaud}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {223--231}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/hoffman09a/hoffman09a.pdf}, url = {https://proceedings.mlr.press/r7/hoffman09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-hooper09a, title = {Improved Mean and Variance Approximations for Belief Net Response via Network Doubling}, author = {Hooper, Peter and Abbasi-Yadkori, Yasin and Hoehn, Bret and Greiner, Russell}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {232--239}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/hooper09a/hooper09a.pdf}, url = {https://proceedings.mlr.press/r7/hooper09a.html}, abstract = {A Bayesian belief network models a joint distribution with an directed acyclic graph representing dependencies among variables and network parameters characterizing con- ditional distributions. The parameters are viewed as random variables to quantify un- certainty 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 ran- dom 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 ap- proximations for both query mean and vari- ance. 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-hoyer09a, title = {{B}ayesian Discovery of Linear Acyclic Causal Models}, author = {Hoyer, Patrik and Hyttinen, Antti}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {240--248}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/hoyer09a/hoyer09a.pdf}, url = {https://proceedings.mlr.press/r7/hoyer09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-janzing09a, title = {Identifying confounders using additive noise models}, author = {Janzing, Dominik and Peters, Jonas and Mooij, Joris and Schoelkopf, Bernhard}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {249--257}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/janzing09a/janzing09a.pdf}, url = {https://proceedings.mlr.press/r7/janzing09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-jebara09a, title = {{MAP} Estimation, Message Passing, and Perfect Graphs}, author = {Jebara, Tony}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {258--267}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/jebara09a/jebara09a.pdf}, url = {https://proceedings.mlr.press/r7/jebara09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-jiang09a, title = {Temporal Action-Graph Games: A New Representation for Dynamic Games}, author = {Jiang, Albert Xin and Leyton-Brown, Kevin and Pfeffer, Avi}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {268--276}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/jiang09a/jiang09a.pdf}, url = {https://proceedings.mlr.press/r7/jiang09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-kersting09a, title = {Counting Belief Propagation}, author = {Kersting, Kristian and Ahmadi, Babak and Natarajan, Sriraam}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {277--284}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/kersting09a/kersting09a.pdf}, url = {https://proceedings.mlr.press/r7/kersting09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-kiselyov09a, title = {Monolingual Probabilistic Programming Using Generalized Coroutines}, author = {Kiselyov, Oleg and Shan, Chung-chieh}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {285--292}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/kiselyov09a/kiselyov09a.pdf}, url = {https://proceedings.mlr.press/r7/kiselyov09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-kisynski09a, title = {Constraint Processing in Lifted Probabilistic Inference}, author = {Kisynski, Jacek and Poole, David}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {293--302}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/kisynski09a/kisynski09a.pdf}, url = {https://proceedings.mlr.press/r7/kisynski09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-kleinberg09a, title = {The Temporal Logic of Causal Structures}, author = {Kleinberg, Samantha and Mishra, Bud}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {303--312}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/kleinberg09a/kleinberg09a.pdf}, url = {https://proceedings.mlr.press/r7/kleinberg09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-kumar09a, title = {{MAP} Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts}, author = {Kumar, M. Pawan and Koller, Daphne}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {313--320}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/kumar09a/kumar09a.pdf}, url = {https://proceedings.mlr.press/r7/kumar09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-kurihara09a, title = {Quantum Annealing for Clustering}, author = {Kurihara, Kenichi and Tanaka, Shu and Miyashita, Seiji}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {321--328}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/kurihara09a/kurihara09a.pdf}, url = {https://proceedings.mlr.press/r7/kurihara09a.html}, abstract = {This paper studies quantum annealing (QA) for clustering, which can be seen as an extension of simulated annealing (SA). We derive a QA algorithm for clustering and propose an annealing schedule, which is crucial in practice. Experiments show the proposed QA algorithm finds better clustering assignments than SA. Furthermore, QA is as easy as SA to implement.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-li09a, title = {Improving Compressed Counting}, author = {Li, Ping}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {329--338}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/li09a/li09a.pdf}, url = {https://proceedings.mlr.press/r7/li09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-littman09a, title = {A {B}ayesian Sampling Approach to Exploration in Reinforcement Learning}, author = {Littman, Michael and Li, Lihong and Nouri, Ali and Wingate, David and Asmuth, John}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {339--346}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/littman09a/littman09a.pdf}, url = {https://proceedings.mlr.press/r7/littman09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-liu09a, title = {Multi-Task Feature Learning Via Efficient $L_{2,1}$-Norm Minimization}, author = {Liu, Jun and Ji, Shuiwang and Ye, Jieping}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {347--356}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/liu09a/liu09a.pdf}, url = {https://proceedings.mlr.press/r7/liu09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-lubin09a, title = {Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions}, author = {Lubin, Benjamin and Parkes, David}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {357--366}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/lubin09a/lubin09a.pdf}, url = {https://proceedings.mlr.press/r7/lubin09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-lyu09a, title = {Interpretation and Generalization of Score Matching}, author = {Lyu, Siwei}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {367--374}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/lyu09a/lyu09a.pdf}, url = {https://proceedings.mlr.press/r7/lyu09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-mansour09a, title = {Multiple Source Adaptation and the Renyi Divergence}, author = {Mansour, Yishay and Mohri, Mehryar and Rostamizadeh, Afshin}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {375--382}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/mansour09a/mansour09a.pdf}, url = {https://proceedings.mlr.press/r7/mansour09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-mao09a, title = {Domain Knowledge Uncertainty and Probabilistic Parameter Constraints}, author = {Mao, Yi and Lebanon, Guy}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {383--390}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/mao09a/mao09a.pdf}, url = {https://proceedings.mlr.press/r7/mao09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-marlin09a, title = {Group Sparse Priors for Covariance Estimation}, author = {Marlin, Benjamin and Schmidt, Mark and Murphy, Kevin}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {391--400}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/marlin09a/marlin09a.pdf}, url = {https://proceedings.mlr.press/r7/marlin09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-meltzer09a, title = {Convergent message passing algorithms - a unifying view}, author = {Meltzer, Talya and Globerson, Amir and Weiss, Yair}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {401--409}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/meltzer09a/meltzer09a.pdf}, url = {https://proceedings.mlr.press/r7/meltzer09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-meshi09a, title = {Convexifying the Bethe Free Energy}, author = {Meshi, Ofer and Jaimovich, Ariel and Globerson, Amir and Friedman, Nir}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {410--418}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/meshi09a/meshi09a.pdf}, url = {https://proceedings.mlr.press/r7/meshi09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-minka09a, title = {Virtual Vector Machine for {B}ayesian Online Classification}, author = {Minka, Thomas and Xiang, Rongjing and Qi, Alan}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {419--426}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/minka09a/minka09a.pdf}, url = {https://proceedings.mlr.press/r7/minka09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-mostafavi09a, title = {Using the Gene Ontology Hierarchy when Predicting Gene Function}, author = {Mostafavi, Sara and Morris, Quaid}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {427--435}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/mostafavi09a/mostafavi09a.pdf}, url = {https://proceedings.mlr.press/r7/mostafavi09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-niepert09a, title = {Inference Algorithms and Matrix Representations for Probabilistic Conditional Independence}, author = {Niepert, Mathias}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {436--443}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/niepert09a/niepert09a.pdf}, url = {https://proceedings.mlr.press/r7/niepert09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-parviainen09a, title = {Exact Structure Discovery in {B}ayesian Networks with Less Space}, author = {Parviainen, Pekka and Koivisto, Mikko}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {444--451}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/parviainen09a/parviainen09a.pdf}, url = {https://proceedings.mlr.press/r7/parviainen09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-regan09a, title = {Regret-based Reward Elicitation for {M}arkov Decision Processes}, author = {Regan, Kevin and Boutilier, Craig}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {452--459}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/regan09a/regan09a.pdf}, url = {https://proceedings.mlr.press/r7/regan09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-rendle09a, title = {{BPR}: {B}ayesian Personalized Ranking from Implicit Feedback}, author = {Rendle, Steffen and Freudenthaler, Christoph and Gantner, Zeno and Schmidt-Thieme, Lars}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {460--469}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/rendle09a/rendle09a.pdf}, url = {https://proceedings.mlr.press/r7/rendle09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-richardson09a, title = {A factorization criterion for acyclic directed mixed graphs}, author = {Richardson, Thomas}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {470--478}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/richardson09a/richardson09a.pdf}, url = {https://proceedings.mlr.press/r7/richardson09a.html}, abstract = {Acyclic directed mixed graphs, also known as semi-Markov models represent the conditional independence structure induced on an observed margin by a DAG model with latent variables. In this paper we present a factorization criterion for these models that is equivalent to the global Markov property given by (the natural extension of) d-separation.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-ryabko09a, title = {Characterizing predictable classes of processes}, author = {Ryabko, Daniil}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {479--486}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/ryabko09a/ryabko09a.pdf}, url = {https://proceedings.mlr.press/r7/ryabko09a.html}, abstract = {The problem is sequence prediction in the following setting. A sequence x1,..., xn,... of discrete-valued observations is generated according to some unknown probabilistic law (measure) mu. After observing each outcome, it is required to give the conditional probabilities of the next observation. The measure mu belongs to an arbitrary class C of stochastic processes. We are interested in predictors $\rho$ whose conditional probabilities converge to the ’true’ mu-conditional probabilities if any $\mu \in C$ is chosen to generate the data. We show that if such a predictor exists, then a predictor can also be obtained as a convex combination of a countably many elements of C. In other words, it can be obtained as a Bayesian predictor whose prior is concentrated on a countable set. This result is established for two very different measures of performance of prediction, one of which is very strong, namely, total variation, and the other is very weak, namely, prediction in expected average Kullback-Leibler divergence.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-sato09a, title = {Quantum Annealing for Variational {B}ayes Inference}, author = {Sato, Issei and Kurihara, Kenichi and Tanaka, Shu and Nakagawa, Hiroshi and Miyashita, Seiji}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {487--494}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/sato09a/sato09a.pdf}, url = {https://proceedings.mlr.press/r7/sato09a.html}, abstract = {This paper presents studies on a deterministic annealing algorithm based on quantum annealing for variational Bayes (QAVB) inference, which can be seen as an extension of the simulated annealing for variational Bayes (SAVB) inference. QAVB is as easy as SAVB to implement. Experiments revealed QAVB finds a better local optimum than SAVB in terms of the variational free energy in latent Dirichlet allocation (LDA).}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-schmidt09a, title = {Modeling Discrete Interventional Data using Directed Cyclic Graphical Models}, author = {Schmidt, Mark and Murphy, Kevin}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {495--503}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/schmidt09a/schmidt09a.pdf}, url = {https://proceedings.mlr.press/r7/schmidt09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-sen09a, title = {Bisimulation-based Approximate Lifted Inference}, author = {Sen, Prithviraj and Deshpande, Amol and Getoor, Lise}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {504--513}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/sen09a/sen09a.pdf}, url = {https://proceedings.mlr.press/r7/sen09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-shimizu09a, title = {A direct method for estimating a causal ordering in a linear non-{G}aussian acyclic model}, author = {Shimizu, Shohei and Hyv{\"a}rinen, Aapo and Kawahara, Yoshinobu and Washio, Takashi}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {514--521}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/shimizu09a/shimizu09a.pdf}, url = {https://proceedings.mlr.press/r7/shimizu09a.html}, abstract = {Structural equation models and Bayesian networks have been widely used to ana- lyze causal relations between continuous vari- ables. In such frameworks, linear acyclic models are typically used to model the data- generating process of variables. Recently, it was shown that use of non-Gaussianity iden- tifies a causal ordering of variables in a linear acyclic model without using any prior knowl- edge on the network structure, which is not the case with conventional methods. How- ever, existing estimation methods are based on iterative search algorithms and may not converge to a correct solution in a finite num- ber of steps. In this paper, we propose a new direct method to estimate a causal ordering based on non-Gaussianity. In contrast to the previous methods, our algorithm requires no algorithmic parameters and is guaranteed to converge to the right solution within a small fixed number of steps if the data strictly fol- lows the model.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-shpitser09a, title = {Effects of Treatment on the Treated: Identification and Generalization}, author = {Shpitser, Ilya and Pearl, Judea}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {522--529}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/shpitser09a/shpitser09a.pdf}, url = {https://proceedings.mlr.press/r7/shpitser09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-taylor09a, title = {Products of Hidden {M}arkov Models: It Takes N>1 to Tango}, author = {Taylor, Graham and Hinton, Geoffrey}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {530--537}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/taylor09a/taylor09a.pdf}, url = {https://proceedings.mlr.press/r7/taylor09a.html}, abstract = {Products of Hidden Markov Models (PoHMMs) are an interesting class of generative models which have received little attention since their introduction. This may be 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 di- vergence 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-thimm09a, title = {Measuring Inconsistency in Probabilistic Knowledge Bases}, author = {Thimm, Matthias}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {538--545}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/thimm09a/thimm09a.pdf}, url = {https://proceedings.mlr.press/r7/thimm09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-tian09a, title = {Computing Posterior Probabilities of Structural Features in {B}ayesian Networks}, author = {Tian, Jin and He, Ru}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {546--555}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/tian09a/tian09a.pdf}, url = {https://proceedings.mlr.press/r7/tian09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-truyen09a, title = {Ordinal {B}oltzmann Machines for Collaborative Filtering}, author = {Truyen, Tran The and Phung, Dinh and Venkatesh, Svetha}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {556--564}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/truyen09a/truyen09a.pdf}, url = {https://proceedings.mlr.press/r7/truyen09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-vembu09a, title = {Probabilistic Structured Predictors}, author = {Vembu, Shankar and G{\"a}rtner, Thomas and Boley, Mario}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {565--572}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/vembu09a/vembu09a.pdf}, url = {https://proceedings.mlr.press/r7/vembu09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-verma09a, title = {Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?}, author = {Verma, Nakul and Kpotufe, Samory and Dasgupta, Sanjoy}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {573--582}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/verma09a/verma09a.pdf}, url = {https://proceedings.mlr.press/r7/verma09a.html}, abstract = {Recent theory work has found that a special type of spatial partition tree – called a ran- dom projection tree – is adaptive to the in- trinsic dimension of the data from which it is built. Here we examine this same ques- tion, with a combination of theory and ex- periments, 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 struc- ture that can be empirically verified, (ii) the extent to which a spatial partition can ex- ploit such structure, and (iii) the implications for standard statistical tasks such as regres- sion, vector quantization, and nearest neigh- bor search.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-vorobeychik09a, title = {Simulation-Based Game Theoretic Analysis of Keyword Auctions with Low-Dimensional Bidding Strategies}, author = {Vorobeychik, Yevgeniy}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {583--590}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/vorobeychik09a/vorobeychik09a.pdf}, url = {https://proceedings.mlr.press/r7/vorobeychik09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-walsh09a, title = {Exploring compact reinforcement-learning representations with linear regression}, author = {Walsh, Thomas and Szita, Istvan and Diuk, Carlos and Littman, Michael}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {591--598}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/walsh09a/walsh09a.pdf}, url = {https://proceedings.mlr.press/r7/walsh09a.html}, 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 computational and storage 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-welling09a, title = {Herding Dynamic Weights for Partially Observed Random Field Models}, author = {Welling, Max}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {599--606}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/welling09a/welling09a.pdf}, url = {https://proceedings.mlr.press/r7/welling09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-wingate09a, title = {The Infinite Latent Events Model}, author = {Wingate, David and Goodman, Noah and Roy, Daniel and Tenenbaum, Josh}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {607--614}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/wingate09a/wingate09a.pdf}, url = {https://proceedings.mlr.press/r7/wingate09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-yang09a, title = {A {B}ayesian Framework for Community Detection Integrating Content and Link}, author = {Yang, Tianbao and Jin, Rong and Chi, Yun and Zhu, Shenghuo}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {615--622}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/yang09a/yang09a.pdf}, url = {https://proceedings.mlr.press/r7/yang09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-yu09a, title = {The Entire Quantile Path of a Risk-Agnostic {SVM} Classifier}, author = {Yu, Jin and Vishwanathan, S V N and Zhang, Jian}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {623--630}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/yu09a/yu09a.pdf}, url = {https://proceedings.mlr.press/r7/yu09a.html}, 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 \in [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 \in [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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-yuan09a, title = {Most Relevant Explanation: Properties, Algorithms, and Evaluations}, author = {Yuan, Changhe and Liu, Xiaolu and Lu, Tsai-Ching and Lim, Heejin}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {631--638}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/yuan09a/yuan09a.pdf}, url = {https://proceedings.mlr.press/r7/yuan09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-zadeh09a, title = {A Uniqueness Theorem for Clustering}, author = {Zadeh, Reza Bosagh and Ben-David, Shai}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {639--646}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/zadeh09a/zadeh09a.pdf}, url = {https://proceedings.mlr.press/r7/zadeh09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR7-zhang09a, title = {On the Identifiability of the Post-Nonlinear Causal Model}, author = {Zhang, Kun and Hyv{\"a}rinen, Aapo}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {647--655}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/zhang09a/zhang09a.pdf}, url = {https://proceedings.mlr.press/r7/zhang09a.html}, 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. 1}, note = {Reissued by PMLR on 04 October 2026.} }