@Proceedings{UAI2012, title = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, editor = {Nando Freitas and Kevin Murphy}, publisher = {PMLR}, series = {Proceedings of Machine Learning Research}, volume = R10 } @InProceedings{pmlr-vR10-freitas12a, title = {The 28th Uncertainty in Artificial Intelligence Conference: Preface}, author = {de Freitas, Nando and Murphy, Kevin}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {1--4}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/freitas12a/freitas12a.pdf}, url = {https://proceedings.mlr.press/r10/freitas12a.html}, abstract = {Proceedings of the Twenty—Eighth Conference Edited by Nando de Freitas Kevin Murphy Uncertainty in Artificial Intelligence Uncertainty in Artificial Intelligence Proceedings of the Twenty—Eighth Conference (2012) August 15–17, 2012 Catalina Island, United States Edited by Kevin Murphy, Google Research, United States Nando de Freitas, University of British Columbia, Canada Conference Chair Fabio Gagliardi Cozman, Universidade de S{\ a}o Paulo, Brazil Local Arrangements Chair David Heckerman, Microsoft Research, United States Sponsored by Microsoft Research, Google, Artificial Intelligence Journal, Pascal2 Network, Charles River Analytics, IBM Research AUAI Press Corvallis, Oregon The cover design is used with permission from Elsevier. Published by AUAI Press for Association for Uncertainty in Artificial Intelligence http://auai.org Editorial Office: P.O. Box 866 Corvallis, Oregon 97339 USA Copyright (c) 2012 by AUAI Press All rights reserved Printed in the United States of America No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, mechanical, photocopying, recording, or other— wise—without the prior written permission of the publisher. ISBN 978—0—9749039—8—9}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-pearl12a, title = {The Do-Calculus Revisited}, author = {Pearl, Judea}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {5--12}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/pearl12a/pearl12a.pdf}, url = {https://proceedings.mlr.press/r10/pearl12a.html}, abstract = {The do-calculus was developed in 1995 to facilitate the identification of causal effects in non-parametric models. The completeness proofs of [Huang and Valtorta, 2006] and [Shpitser and Pearl, 2006] and the graphical criteria of [Tian and Shpitser, 2010] have laid this identification problem to rest. Recent explorations unveil the usefulness of the do-calculus in three additional areas: mediation analysis [Pearl, 2012], transportability [Pearl and Bareinboim, 2011] and metasynthesis. Meta-synthesis (freshly coined) is the task of fusing empirical results from several diverse studies, conducted on heterogeneous populations and under different conditions, so as to synthesize an estimate of a causal relation in some target environment, potentially different from those under study. The talk surveys these results with emphasis on the challenges posed by meta-synthesis. For background material, see http://bayes.cs.ucla.edu/csl_papers.html}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-acharyya12a, title = {Learning to Rank With Bregman Divergences and Monotone Retargeting}, author = {Acharyya, Sreangsu and Koyejo, Oluwasanmi and Ghosh, Joydeep}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {13--22}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/acharyya12a/acharyya12a.pdf}, url = {https://proceedings.mlr.press/r10/acharyya12a.html}, abstract = {This paper introduces a novel approach for learning to rank (LETOR) based on the notion of monotone retargeting. It involves minimizing a divergence between all monotonic increasing transformations of the training scores and a parameterized prediction function. The minimization is both over the transformations as well as over the parameters. It is applied to Bregman divergences, a large class of "distance like" functions that were recently shown to be the unique class that is statistically consistent with the normalized discounted gain (NDCG) criterion [19]. The algorithm uses alternating projection style updates, in which one set of simultaneous projections can be computed independent of the Bregman divergence and the other reduces to parameter estimation of a generalized linear model. This results in easily implemented, efficiently parallelizable algorithm for the LETOR task that enjoys global optimum guarantees under mild conditions. We present empirical results on benchmark datasets showing that this approach can outperform the state of the art NDCG consistent techniques.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-affandi12a, title = {{M}arkov Determinantal Point Processes}, author = {Affandi, Raja Hafiz and Kulesza, Alex and Fox, Emily B.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {23--32}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/affandi12a/affandi12a.pdf}, url = {https://proceedings.mlr.press/r10/affandi12a.html}, abstract = {A determinantal point process (DPP) is a random process useful for modeling the combinatorial problem of subset selection. In particular, DPPs encourage a random subset Y to contain a diverse set of items selected from a base set Y. For example, we might use a DPP to display a set of news headlines that are relevant to a user’s interests while covering a variety of topics. Suppose, however, that we are asked to sequentially select multiple diverse sets of items, for example, displaying new headlines day-by-day. We might want these sets to be diverse not just individually but also through time, offering headlines today that are unlike the ones shown yesterday. In this paper, we construct a Markov DPP (M-DPP) that models a sequence of random sets {Yt}. The proposed M-DPP defines a stationary process that maintains DPP margins. Crucially, the induced union process Zt = Yt u Yt-1 is also marginally DPP-distributed. Jointly, these properties imply that the sequence of random sets are encouraged to be diverse both at a given time step as well as across time steps. We describe an exact, efficient sampling procedure, and a method for incrementally learning a quality measure over items in the base set Y based on external preferences. We apply the M-DPP to the task of sequentially displaying diverse and relevant news articles to a user with topic preferences.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-agussurja12a, title = {Toward Large-Scale Agent Guidance in an Urban Taxi Service}, author = {Agussurja, Lucas and Lau, Hoong Chuin}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {33--40}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/agussurja12a/agussurja12a.pdf}, url = {https://proceedings.mlr.press/r10/agussurja12a.html}, abstract = {Empty taxi cruising represents a wastage of resources in the context of urban taxi services. In this work, we seek to minimize such wastage. An analysis of a large trace of taxi operations reveals that the services’ inefficiency is caused by drivers’ greedy cruising behavior. We model the existing system as a continuous time Markov chain. To address the problem, we propose that each taxi be equipped with an intelligent agent that will guide the driver when cruising for passengers. Then, drawing from AI literature on multiagent planning, we explore two possible ways to compute such guidance. The first formulation assumes fully cooperative drivers. This allows us, in principle, to compute systemwide optimal cruising policy. This is modeled as a Markov decision process. The second formulation assumes rational drivers, seeking to maximize their own profit. This is modeled as a stochastic congestion game, a specialization of stochastic games. Nash equilibrium policy is proposed as the solution to the game, where no driver has the incentive to singly deviate from it. Empirical result shows that both formulations improve the efficiency of the service significantly.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-ahmed12a, title = {Uncertain Congestion Games with Assorted Human Agent Populations}, author = {Ahmed, Asrar and Varakantham, Pradeep and Cheng, Shih-Fen}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {41--50}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/ahmed12a/ahmed12a.pdf}, url = {https://proceedings.mlr.press/r10/ahmed12a.html}, abstract = {Congestion games model a wide variety of real-world resource congestion problems, such as selfish network routing, traffic route guidance in congested areas, taxi fleet optimization and crowd movement in busy areas. However, existing research in congestion games assumes: (a) deterministic movement of agents between resources; and (b) perfect rationality (i.e. maximizing their own expected value) of all agents. Such assumptions are not reasonable in dynamic domains where decision support has to be provided to humans. For instance, in optimizing the performance of a taxi fleet serving a city, movement of taxis can be involuntary or nondeterministic (decided by the specific customer who hires the taxi) and more importantly, taxi drivers may not follow advice provided by the decision support system (due to bounded rationality of humans). To that end, we contribute: (a) a general framework for representing congestion games under uncertainty for populations with assorted notions of rationality. (b) a scalable approach for solving the decision problem for perfectly rational agents which are in the mix with boundedly rational agents; and (c) a detailed evaluation on a synthetic and realworld data set to illustrate the usefulness of our new approach with respect to key social welfare metrics in the context of an assorted human-agent population. An interesting result from our experiments on a real-world taxi fleet optimization problem is that it is better (in terms of revenue and operational efficiency) for taxi drivers to follow perfectly rational strategies irrespective of the percentage of drivers not following the advice.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-amin12a, title = {Budget Optimization for Sponsored Search: Censored Learning in MDPs}, author = {Amin, Kareem and Kearns, Michael and Key, Peter and Schwaighofer, Anton}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {51--60}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/amin12a/amin12a.pdf}, url = {https://proceedings.mlr.press/r10/amin12a.html}, abstract = {We consider the budget optimization problem faced by an advertiser participating in repeated sponsored search auctions, seeking to maximize the number of clicks attained under that budget. We cast the budget optimization problem as a Markov Decision Process (MDP) with censored observations, and propose a learning algorithm based on the wellknown Kaplan-Meier or product-limit estimator. We validate the performance of this algorithm by comparing it to several others on a large set of search auction data from Microsoft adCenter, demonstrating fast convergence to optimal performance.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-amizadeh12a, title = {Variational Dual-Tree Framework for Large-Scale Transition Matrix Approximation}, author = {Amizadeh, Saeed and Thiesson, Bo and Hauskrecht, Milos}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {61--70}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/amizadeh12a/amizadeh12a.pdf}, url = {https://proceedings.mlr.press/r10/amizadeh12a.html}, abstract = {In recent years, non-parametric methods utilizing random walks on graphs have been used to solve a wide range of machine learning problems, but in their simplest form they do not scale well due to the quadratic complexity. In this paper, a new dual-tree based variational approach for approximating the transition matrix and efficiently performing the random walk is proposed. The approach exploits a connection between kernel density estimation, mixture modeling, and random walk on graphs in an optimization of the transition matrix for the data graph that ties together edge transitions probabilities that are similar. Compared to the de facto standard approximation method based on k-nearestneighbors, we demonstrate order of magnitudes speedup without sacrificing accuracy for Label Propagation tasks on benchmark data sets in semi-supervised learning.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-apsel12a, title = {Exploiting Uniform Assignments in First-Order {MPE}}, author = {Apsel, Udi and Brafman, Ronen I.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {71--80}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/apsel12a/apsel12a.pdf}, url = {https://proceedings.mlr.press/r10/apsel12a.html}, abstract = {The MPE (Most Probable Explanation) query plays an important role in probabilistic inference. MPE solution algorithms for probabilistic relational models essentially adapt existing belief assessment method, replacing summation with maximization. But the rich structure and symmetries captured by relational models together with the properties of the maximization operator offer an opportunity for additional simplification with potentially significant computational ramifications. Specifically, these models often have groups of variables that define symmetric distributions over some population of formulas. The maximizing choice for different elements of this group is the same. If we can realize this ahead of time, we can significantly reduce the size of the model by eliminating a potentially significant portion of random variables. This paper defines the notion of uniformly assigned and partially uniformly assigned sets of variables, shows how one can recognize these sets efficiently, and how the model can be greatly simplified once we recognize them, with little computational effort. We demonstrate the effectiveness of these ideas empirically on a number of models.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-archambeau12a, title = {Plackett-Luce regression: A new {B}ayesian model for polychotomous data}, author = {Archambeau, Cedric and Caron, Francois}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {81--89}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/archambeau12a/archambeau12a.pdf}, url = {https://proceedings.mlr.press/r10/archambeau12a.html}, abstract = {Multinomial logistic regression is one of the most popular models for modelling the effect of explanatory variables on a subject choice between a set of specified options. This model has found numerous applications in machine learning, psychology or economy. Bayesian inference in this model is non trivial and requires, either to resort to a MetropolisHastings algorithm, or rejection sampling within a Gibbs sampler. In this paper, we propose an alternative model to multinomial logistic regression. The model builds on the Plackett-Luce model, a popular model for multiple comparisons. We show that the introduction of a suitable set of auxiliary variables leads to an Expectation-Maximization algorithm to find Maximum A Posteriori estimates of the parameters. We further provide a full Bayesian treatment by deriving a Gibbs sampler, which only requires to sample from highly standard distributions. We also propose a variational approximate inference scheme. All are very simple to implement. One property of our Plackett-Luce regression model is that it learns a sparse set of feature weights. We compare our method to sparse Bayesian multinomial logistic regression and show that it is competitive, especially in presence of polychotomous data.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-arora12a, title = {Deterministic MDPs with Adversarial Rewards and Bandit Feedback}, author = {Arora, Raman and Dekel, Ofer and Tewari, Ambuj}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {90--99}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/arora12a/arora12a.pdf}, url = {https://proceedings.mlr.press/r10/arora12a.html}, abstract = {We consider a Markov decision process with deterministic state transition dynamics, adversarially generated rewards that change arbitrarily from round to round, and a bandit feedback model in which the decision maker only observes the rewards it receives. In this setting, we present a novel and efficient online decision making algorithm named MarcoPolo. Under mild assumptions on the structure of the transition dynamics, we prove that MarcoPolo enjoys a regret of O(T^(3/4)sqrt(log(T))) against the best deterministic policy in hindsight. Specifically, our analysis does not rely on the stringent unichain assumption, which dominates much of the previous work on this topic.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-barbu12a, title = {Video In Sentences Out}, author = {Barbu, Andrei and Bridge, Alexander and Burchill, Zachary and Coroian, Dan and Dickinson, Sven and Fidler, Sanja and Michaux, Aaron and Mussman, Sam and Narayanaswamy, Siddharth and Salvi, Dhaval and Schmidt, Lara and Shangguan, Jiangnan and Siskind, Jeffrey Mark and Waggoner, Jarrell and Wang, Song and Wei, Jinlian and Yin, Yifan and Zhang, Zhiqi}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {100--110}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/barbu12a/barbu12a.pdf}, url = {https://proceedings.mlr.press/r10/barbu12a.html}, abstract = {We present a system that produces sentential descriptions of video: who did what to whom, and where and how they did it. Action class is rendered as a verb, participant objects as noun phrases, properties of those objects as adjectival modifiers in those noun phrases, spatial relations between those participants as prepositional phrases, and characteristics of the event as prepositional-phrase adjuncts and adverbial modifiers. Extracting the information needed to render these linguistic entities requires an approach to event recognition that recovers object tracks, the trackto-role assignments, and changing body posture.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-bareinboim12a, title = {Causal Inference by Surrogate Experiments: z-Identifiability}, author = {Bareinboim, Elias and Pearl, Judea}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {111--118}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/bareinboim12a/bareinboim12a.pdf}, url = {https://proceedings.mlr.press/r10/bareinboim12a.html}, abstract = {We address the problem of estimating the effect of intervening on a set of variables X from experiments on a different set, Z, that is more accessible to manipulation. This problem, which we call z-identifiability, reduces to ordinary identifiability when Z = empty and, like the latter, can be given syntactic characterization using the do-calculus [Pearl, 1995; 2000]. We provide a graphical necessary and sufficient condition for z-identifiability for arbitrary sets X,Z, and Y (the outcomes). We further develop a complete algorithm for computing the causal effect of X on Y using information provided by experiments on Z. Finally, we use our results to prove completeness of do-calculus relative to z-identifiability, a result that does not follow from completeness relative to ordinary identifiability.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-batra12a, title = {An Efficient Message-Passing Algorithm for the M-Best {MAP} Problem}, author = {Batra, Dhruv}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {119--128}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/batra12a/batra12a.pdf}, url = {https://proceedings.mlr.press/r10/batra12a.html}, abstract = {Much effort has been directed at algorithms for obtaining the highest probability configuration in a probabilistic random field model known as the maximum a posteriori (MAP) inference problem. In many situations, one could benefit from having not just a single solution, but the top M most probable solutions known as the M-Best MAP problem. In this paper, we propose an efficient message-passing based algorithm for solving the M-Best MAP problem. Specifically, our algorithm solves the recently proposed Linear Programming (LP) formulation of M-Best MAP [7], while being orders of magnitude faster than a generic LP-solver. Our approach relies on studying a particular partial Lagrangian relaxation of the M-Best MAP LP which exposes a natural combinatorial structure of the problem that we exploit.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-broeck12a, title = {Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference}, author = {Broeck, Guy Van den and Choi, Arthur and Darwiche, Adnan}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {129--139}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/broeck12a/broeck12a.pdf}, url = {https://proceedings.mlr.press/r10/broeck12a.html}, abstract = {We propose an approach to lifted approximate inference for first-order probabilistic models, such as Markov logic networks. It is based on performing exact lifted inference in a simplified first-order model, which is found by relaxing first-order constraints, and then compensating for the relaxation. These simplified models can be incrementally improved by carefully recovering constraints that have been relaxed, also at the first-order level. This leads to a spectrum of approximations, with lifted belief propagation on one end, and exact lifted inference on the other. We discuss how relaxation, compensation, and recovery can be performed, all at the firstorder level, and show empirically that our approach substantially improves on the approximations of both propositional solvers and lifted belief propagation.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-caron12a, title = {Leveraging Side Observations in Stochastic Bandits}, author = {Caron, Stephane and Kveton, Branislav and Lelarge, Marc and Bhagat, Smriti}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {140--149}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/caron12a/caron12a.pdf}, url = {https://proceedings.mlr.press/r10/caron12a.html}, abstract = {This paper considers stochastic bandits with side observations, a model that accounts for both the exploration/exploitation dilemma and relationships between arms. In this setting, after pulling an arm i, the decision maker also observes the rewards for some other actions related to i. We will see that this model is suited to content recommendation in social networks, where users’ reactions may be endorsed or not by their friends. We provide efficient algorithms based on upper confidence bounds (UCBs) to leverage this additional information and derive new bounds improving on standard regret guarantees. We also evaluate these policies in the context of movie recommendation in social networks: experiments on real datasets show substantial learning rate speedups ranging from 2.2x to 14x on dense networks.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-chan12a, title = {Interdependent Defense Games: Modeling Interdependent Security under Deliberate Attacks}, author = {Chan, Hau and Ceyko, Michael and Ortiz, Luis E.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {150--160}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/chan12a/chan12a.pdf}, url = {https://proceedings.mlr.press/r10/chan12a.html}, abstract = {We propose interdependent defense (IDD) games, a computational game-theoretic framework to study aspects of the interdependence of risk and security in multi-agent systems under deliberate external attacks. Our model builds upon interdependent security (IDS) games, a model due to Heal and Kunreuther that considers the source of the risk to be the result of a fixed randomizedstrategy. We adapt IDS games to model the attacker’s deliberate behavior. We define the attacker’s pure-strategy space and utility function and derive appropriate cost functions for the defenders. We provide a complete characterization of mixed-strategy Nash equilibria (MSNE), and design a simple polynomial-time algorithm for computing all of them, for an important subclass of IDD games. In addition, we propose a randominstance generator of (general) IDD games based on a version of the real-world Internet-derived Autonomous Systems (AS) graph (with around 27K nodes and 100K edges), and present promising empirical results using a simple learning heuristics to compute (approximate) MSNE in such games.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-chen12a, title = {Decentralized Data Fusion and Active Sensing with Mobile Sensors for Modeling and Predicting Spatiotemporal Traffic Phenomena}, author = {Chen, Jie and Low, Kian Hsiang and Tan, Colin Keng-Yan and Oran, Ali and Jaillet, Patrick and Dolan, John and Sukhatme, Gaurav}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {161--171}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/chen12a/chen12a.pdf}, url = {https://proceedings.mlr.press/r10/chen12a.html}, abstract = {The problem of modeling and predicting spatiotemporal traffic phenomena over an urban road network is important to many traffic applications such as detecting and forecasting congestion hotspots. This paper presents a decentralized data fusion and active sensing (D2FAS) algorithm for mobile sensors to actively explore the road network to gather and assimilate the most informative data for predicting the traffic phenomenon. We analyze the time and communication complexity of D2FAS and demonstrate that it can scale well with a large number of observations and sensors. We provide a theoretical guarantee on its predictive performance to be equivalent to that of a sophisticated centralized sparse approximation for the Gaussian process (GP) model: The computation of such a sparse approximate GP model can thus be parallelized and distributed among the mobile sensors (in a Google-like MapReduce paradigm), thereby achieving efficient and scalable prediction. We also theoretically guarantee its active sensing performance that improves under various practical environmental conditions. Empirical evaluation on real-world urban road network data shows that our D2FAS algorithm is significantly more time-efficient and scalable than state-oftheart centralized algorithms while achieving comparable predictive performance.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-chen12b, title = {{B}ayesian Structure Learning for {M}arkov Random Fields with a Spike and Slab Prior}, author = {Chen, Yutian and Welling, Max}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {172--182}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/chen12b/chen12b.pdf}, url = {https://proceedings.mlr.press/r10/chen12b.html}, abstract = {In recent years a number of methods have been developed for automatically learning the (sparse) connectivity structure of Markov Random Fields. These methods are mostly based on L1-regularized optimization which has a number of disadvantages such as the inability to assess model uncertainty and expensive crossvalidation to find the optimal regularization parameter. Moreover, the model’s predictive performance may degrade dramatically with a suboptimal value of the regularization parameter (which is sometimes desirable to induce sparseness). We propose a fully Bayesian approach based on a "spike and slab" prior (similar to L0 regularization) that does not suffer from these shortcomings. We develop an approximate MCMC method combining Langevin dynamics and reversible jump MCMC to conduct inference in this model. Experiments show that the proposed model learns a good combination of the structure and parameter values without the need for separate hyper-parameter tuning. Moreover, the model’s predictive performance is much more robust than L1-based methods with hyper-parameter settings that induce highly sparse model structures.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-chen12c, title = {Designing Informative Securities}, author = {Chen, Yiling and Ruberry, Mike and Vaughan, Jennifer Wortman}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {183--193}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/chen12c/chen12c.pdf}, url = {https://proceedings.mlr.press/r10/chen12c.html}, abstract = {We create a formal framework for the design of informative securities in prediction markets. These securities allow a market organizer to infer the likelihood of events of interest as well as if he knew all of the traders’ private signals. We consider the design of markets that are always informative, markets that are informative for a particular signal structure of the participants, and informative markets constructed from a restricted selection of securities. We find that to achieve informativeness, it can be necessary to allow participants to express information that may not be directly of interest to the market organizer, and that understanding the participants’ signal structure is important for designing informative prediction markets.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-choi12a, title = {Lifted Relational Variational Inference}, author = {Choi, Jaesik and Amir, Eyal}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {194--204}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/choi12a/choi12a.pdf}, url = {https://proceedings.mlr.press/r10/choi12a.html}, abstract = {Hybrid continuous-discrete models naturally represent many real-world applications in robotics, finance, and environmental engineering. Inference with large-scale models is challenging because relational structures deteriorate rapidly during inference with observations. The main contribution of this paper is an efficient relational variational inference algorithm that factors largescale probability models into simpler variational models, composed of mixtures of iid (Bernoulli) random variables. The algorithm takes probability relational models of largescale hybrid systems and converts them to a close-to-optimal variational models. Then, it efficiently calculates marginal probabilities on the variational models by using a latent (or lifted) variable elimination or a lifted stochastic sampling. This inference is unique because it maintains the relational structure upon individual observations and during inference steps.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-claassen12a, title = {A {B}ayesian Approach to Constraint Based Causal Inference}, author = {Claassen, Tom and Heskes, Tom}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {205--214}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/claassen12a/claassen12a.pdf}, url = {https://proceedings.mlr.press/r10/claassen12a.html}, abstract = {We target the problem of accuracy and robustness in causal inference from finite data sets. Some state-of-the-art algorithms produce clear output complete with solid theoretical guarantees but are susceptible to propagating erroneous decisions, while others are very adept at handling and representing uncertainty, but need to rely on undesirable assumptions. Our aim is to combine the inherent robustness of the Bayesian approach with the theoretical strength and clarity of constraint-based methods. We use a Bayesian score to obtain probability estimates on the input statements used in a constraint-based procedure. These are subsequently processed in decreasing order of reliability, letting more reliable decisions take precedence in case of con icts, until a single output model is obtained. Tests show that a basic implementation of the resulting Bayesian Constraint-based Causal Discovery (BCCD) algorithm already outperforms established procedures such as FCI and Conservative PC. It can also indicate which causal decisions in the output have high reliability and which do not.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-dibangoye12a, title = {Scaling Up Decentralized MDPs Through Heuristic Search}, author = {Dibangoye, Jilles S. and Amato, Christopher and Doniec, Arnoud}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {215--224}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/dibangoye12a/dibangoye12a.pdf}, url = {https://proceedings.mlr.press/r10/dibangoye12a.html}, abstract = {Decentralized partially observable Markov decision processes (Dec-POMDPs) are rich models for cooperative decision-making under uncertainty, but are often intractable to solve optimally (NEXP-complete). The transition and observation independent Dec-MDP is a general subclass that has been shown to have complexity in NP, but optimal algorithms for this subclass are still inefficient in practice. In this paper, we first provide an updated proof that an optimal policy does not depend on the histories of the agents, but only the local observations. We then present a new algorithm based on heuristic search that is able to expand search nodes by using constraint optimization. We show experimental results comparing our approach with the state-of-the-art DecMDP and Dec-POMDP solvers. These results show a reduction in computation time and an increase in scalability by multiple orders of magnitude in a number of benchmarks.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-dong12a, title = {Graph-Coupled HMMs for Modeling the Spread of Infection}, author = {Dong, Wen and Pentland, Alex and Heller, Katherine A.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {225--234}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/dong12a/dong12a.pdf}, url = {https://proceedings.mlr.press/r10/dong12a.html}, abstract = {We develop Graph-Coupled Hidden Markov Models (GCHMMs) for modeling the spread of infectious disease locally within a social network. Unlike most previous research in epidemiology, which typically models the spread of infection at the level of entire populations, we successfully leverage mobile phone data collected from 84 people over an extended period of time to model the spread of infection on an individual level. Our model, the GCHMM, is an extension of widely-used Coupled Hidden Markov Models (CHMMs), which allow dependencies between state transitions across multiple Hidden Markov Models (HMMs), to situations in which those dependencies are captured through the structure of a graph, or to social networks that may change over time. The benefit of making infection predictions on an individual level is enormous, as it allows people to receive more personalized and relevant health advice.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-dubuisson12a, title = {{DBN}-Based Combinatorial Resampling for Articulated Object Tracking}, author = {Dubuisson, Severine and Gonzales, Christophe and NGuyen, Xuan Son}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {235--244}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/dubuisson12a/dubuisson12a.pdf}, url = {https://proceedings.mlr.press/r10/dubuisson12a.html}, abstract = {Particle Filter is an effective solution to track objects in video sequences in complex situations. Its key idea is to estimate the density over the possible states of the object using a weighted sample whose elements are called particles. One of its crucial step is a resampling step in which particles are resampled to avoid some degeneracy problem. In this paper, we introduce a new resampling method called Combinatorial Resampling that exploits some features of articulated objects to resample over an implicitly created sample of an exponential size better representing the density to estimate. We prove that it is sound and, through experimentations both on challenging synthetic and real video sequences, we show that it outperforms all classical resampling methods both in terms of the quality of its results and in terms of response times.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-dudik12a, title = {Sample-efficient Nonstationary Policy Evaluation for Contextual Bandits}, author = {Dudik, Miroslav and Erhan, Dumitru and Langford, John and Li, Lihong}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {245--252}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/dudik12a/dudik12a.pdf}, url = {https://proceedings.mlr.press/r10/dudik12a.html}, abstract = {We present and prove properties of a new offline policy evaluator for an exploration learning setting which is superior to previous evaluators. In particular, it simultaneously and correctly incorporates techniques from importance weighting, doubly robust evaluation, and nonstationary policy evaluation approaches. In addition, our approach allows generating longer histories by careful control of a bias-variance tradeoff, and further decreases variance by incorporating information about randomness of the target policy. Empirical evidence from synthetic and realworld exploration learning problems shows the new evaluator successfully unifies previous approaches and uses information an order of magnitude more efficiently.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-ermon12a, title = {Uniform Solution Sampling Using a Constraint Solver As an Oracle}, author = {Ermon, Stefano and Gomes, Carla P. and Selman, Bart}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {253--262}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/ermon12a/ermon12a.pdf}, url = {https://proceedings.mlr.press/r10/ermon12a.html}, abstract = {We consider the problem of sampling from solutions defined by a set of hard constraints on a combinatorial space. We propose a new sampling technique that, while enforcing a uniform exploration of the search space, leverages the reasoning power of a systematic constraint solver in a black-box scheme. We present a series of challenging domains, such as energy barriers and highly asymmetric spaces, that reveal the difficulties introduced by hard constraints. We demonstrate that standard approaches such as Simulated Annealing and Gibbs Sampling are greatly affected, while our new technique can overcome many of these difficulties. Finally, we show that our sampling scheme naturally defines a new approximate model counting technique, which we empirically show to be very accurate on a range of benchmark problems.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-freno12a, title = {Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data}, author = {Freno, Antonino and Keller, Mikaela and Garriga, Gemma C. and Tommasi, Marc}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {263--272}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/freno12a/freno12a.pdf}, url = {https://proceedings.mlr.press/r10/freno12a.html}, abstract = {Generative models for graphs have been typically committed to strong prior assumptions concerning the form of the modeled distributions. Moreover, the vast majority of currently available models are either only suitable for characterizing some particular network properties (such as degree distribution or clustering coefficient), or they are aimed at estimating joint probability distributions, which is often intractable in large-scale networks. In this paper, we first propose a novel network statistic, based on the Laplacian spectrum of graphs, which allows to dispense with any parametric assumption concerning the modeled network properties. Second, we use the defined statistic to develop the Fiedler random graph model, switching the focus from the estimation of joint probability distributions to a more tractable conditional estimation setting. After analyzing the dependence structure characterizing Fiedler random graphs, we evaluate them experimentally in edge prediction over several real-world networks, showing that they allow to reach a much higher prediction accuracy than various alternative statistical models.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-garg12a, title = {Mechanism Design for Cost Optimal {PAC} Learning in the Presence of Strategic Noisy Annotators}, author = {Garg, Dinesh and Bhattacharya, Sourangshu and Sundararajan, S. and Shevade, Shirish}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {273--283}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/garg12a/garg12a.pdf}, url = {https://proceedings.mlr.press/r10/garg12a.html}, abstract = {We consider the problem of Probably Approximate Correct (PAC) learning of a binary classifier from noisy labeled examples acquired from multiple annotators (each characterized by a respective classification noise rate). First, we consider the complete information scenario, where the learner knows the noise rates of all the annotators. For this scenario, we derive sample complexity bound for the Minimum Disagreement Algorithm (MDA) on the number of labeled examples to be obtained from each annotator. Next, we consider the incomplete information scenario, where each annotator is strategic and holds the respective noise rate as a private information. For this scenario, we design a cost optimal procurement auction mechanism along the lines of Myerson’s optimal auction design framework in a non-trivial manner. This mechanism satisfies incentive compatibility property, thereby facilitating the learner to elicit true noise rates of all the annotators.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-gatti12a, title = {Combining local search techniques and path following for bimatrix games}, author = {Gatti, Nicola and Patrini, Giorgio and Rocco, Marco and Sandholm, Tuomas}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {284--293}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/gatti12a/gatti12a.pdf}, url = {https://proceedings.mlr.press/r10/gatti12a.html}, abstract = {Computing a Nash equilibrium (NE) is a central task in computer science. An NE is a particularly appropriate solution concept for two-agent settings because coalitional deviations are not an issue. However, even in this case, finding an NE is PPAD-complete. In this paper, we combine path following algorithms with local search techniques to design new algorithms for finding exact and approximate NEs. We show that our algorithms largely outperform the state of the art and that almost all the known benchmark game classes are easily solvable or approximable (except for the GAMUT CovariantGameRand class).}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-gelfand12a, title = {Generalized Belief Propagation on Tree Robust Structured Region Graphs}, author = {Gelfand, Andrew E. and Welling, Max}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {294--303}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/gelfand12a/gelfand12a.pdf}, url = {https://proceedings.mlr.press/r10/gelfand12a.html}, abstract = {This paper provides some new guidance in the construction of region graphs for Generalized Belief Propagation (GBP). We connect the problem of choosing the outer regions of a LoopStructured Region Graph (SRG) to that of finding a fundamental cycle basis of the corresponding Markov network. We also define a new class of tree-robust Loop-SRG for which GBP on any induced (spanning) tree of the Markov network, obtained by setting to zero the off-tree interactions, is exact. This class of SRG is then mapped to an equivalent class of tree-robust cycle bases on the Markov network. We show that a treerobust cycle basis can be identified by proving that for every subset of cycles, the graph obtained from the edges that participate in a single cycle only, is multiply connected. Using this we identify two classes of tree-robust cycle bases: planar cycle bases and "star" cycle bases. In experiments we show that tree-robustness can be successfully exploited as a design principle to improve the accuracy and convergence of GBP.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-grosse12a, title = {Exploiting compositionality to explore a large space of model structures}, author = {Grosse, Roger and Salakhutdinov, Ruslan R and Freeman, William T. and Tenenbaum, Joshua B.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {304--313}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/grosse12a/grosse12a.pdf}, url = {https://proceedings.mlr.press/r10/grosse12a.html}, abstract = {The recent proliferation of richly structured probabilistic models raises the question of how to automatically determine an appropriate model for a dataset. We investigate this question for a space of matrix decomposition models which can express a variety of widely used models from unsupervised learning. To enable model selection, we organize these models into a context-free grammar which generates a wide variety of structures through the compositional application of a few simple rules. We use our grammar to generically and efficiently infer latent components and estimate predictive likelihood for nearly 2500 structures using a small toolbox of reusable algorithms. Using a greedy search over our grammar, we automatically choose the decomposition structure from raw data by evaluating only a small fraction of all models. The proposed method typically finds the correct structure for synthetic data and backs off gracefully to simpler models under heavy noise. It learns sensible structures for datasets as diverse as image patches, motion capture, 20 Questions, and U.S. Senate votes, all using exactly the same code.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-gupta12a, title = {A Slice Sampler for Restricted Hierarchical Beta Process with Applications to Shared Subspace Learning}, author = {Gupta, Sunil Kumar and Phung, Dinh Q. and Venkatesh, Svetha}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {314--323}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/gupta12a/gupta12a.pdf}, url = {https://proceedings.mlr.press/r10/gupta12a.html}, abstract = {Hierarchical beta process has found interesting applications in recent years. In this paper we present a modified hierarchical beta process prior with applications to hierarchical modeling of multiple data sources. The novel use of the prior over a hierarchical factor model allows factors to be shared across different sources. We derive a slice sampler for this model, enabling tractable inference even when the likelihood and the prior over parameters are non-conjugate. This allows the application of the model in much wider contexts without restrictions. We present two different data generative models a linear GaussianGaussian model for real valued data and a linear Poisson-gamma model for count data. Encouraging transfer learning results are shown for two real world applications text modeling and content based image retrieval.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-hajishirzi12a, title = {Semantic Understanding of Professional Soccer Commentaries}, author = {Hajishirzi, Hannaneh and Rastegari, Mohammad and Farhadi, Ali and Hodgins, Jessica K.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {324--333}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/hajishirzi12a/hajishirzi12a.pdf}, url = {https://proceedings.mlr.press/r10/hajishirzi12a.html}, abstract = {This paper presents a novel approach to the problem of semantic parsing via learning the correspondences between complex sentences and rich sets of events. Our main intuition is that correct correspondences tend to occur more frequently. Our model benefits from a discriminative notion of similarity to learn the correspondence between sentence and an event and a ranking machinery that scores the popularity of each correspondence. Our method can discover a group of events (called macro-events) that best describes a sentence. We evaluate our method on our novel dataset of professional soccer commentaries. The empirical results show that our method significantly outperforms the state-of-theart.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-halpern12a, title = {Weighted Sets of Probabilities and MinimaxWeighted Expected Regret: New Approaches for Representing Uncertainty and Making Decisions}, author = {Halpern, Joseph Y. and Leung, Samantha}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {334--343}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/halpern12a/halpern12a.pdf}, url = {https://proceedings.mlr.press/r10/halpern12a.html}, abstract = {We consider a setting where an agent’s uncertainty is represented by a set of probability measures, rather than a single measure. Measure-bymeasure updating of such a set of measures upon acquiring new information is well-known to suffer from problems; agents are not always able to learn appropriately. To deal with these problems, we propose using weighted sets of probabilities: a representation where each measure is associated with a weight, which denotes its significance. We describe a natural approach to updating in such a situation and a natural approach to determining the weights. We then show how this representation can be used in decision-making, by modifying a standard approach to decision making-minimizing expected regret-to obtain minimax weighted expected regret (MWER).We provide an axiomatization that characterizes preferences induced by MWER both in the static and dynamic case.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-hay12a, title = {Selecting Computations: Theory and Applications}, author = {Hay, Nicholas and Russell, Stuart and Tolpin, David and Shimony, Solomon Eyal}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {344--353}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/hay12a/hay12a.pdf}, url = {https://proceedings.mlr.press/r10/hay12a.html}, abstract = {Sequential decision problems are often approximately solvable by simulating possible future action sequences. Metalevel decision procedures have been developed for selecting which action sequences to simulate, based on estimating the expected improvement in decision quality that would result from any particular simulation; an example is the recent work on using bandit algorithms to control Monte Carlo tree search in the game of Go. In this paper we develop a theoretical basis for metalevel decisions in the statistical framework of Bayesian selection problems, arguing (as others have done) that this is more appropriate than the bandit framework. We derive a number of basic results applicable to Monte Carlo selection problems, including the first finite sampling bounds for optimal policies in certain cases; we also provide a simple counterexample to the intuitive conjecture that an optimal policy will necessarily reach a decision in all cases. We then derive heuristic approximations in both Bayesian and distribution-free settings and demonstrate their superiority to bandit-based heuristics in one-shot decision problems and in Go.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-hazan12a, title = {Tightening Fractional Covering Upper Bounds on the Partition Function for High-Order Region Graphs}, author = {Hazan, Tamir and Peng, Jian and Shashua, Amnon}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {354--364}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/hazan12a/hazan12a.pdf}, url = {https://proceedings.mlr.press/r10/hazan12a.html}, abstract = {In this paper we present a new approach for tightening upper bounds on the partition function. Our upper bounds are based on fractional covering bounds on the entropy function, and result in a concave program to compute these bounds and a convex program to tighten them. To solve these programs effectively for general region graphs we utilize the entropy barrier method, thus decomposing the original programs by their dual programs and solve them with dual block optimization scheme. The entropy barrier method provides an elegant framework to generalize the message-passing scheme to high-order region graph, as well as to solve the block dual steps in closed-form. This is a key for computational relevancy for large problems with thousands of regions.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-hostetler12a, title = {Inferring Strategies from Limited Reconnaissance in Real-time Strategy Games}, author = {Hostetler, Jesse and Dereszynski, Ethan W. and Dietterich, Thomas G. and Fern, Alan}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {365--374}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/hostetler12a/hostetler12a.pdf}, url = {https://proceedings.mlr.press/r10/hostetler12a.html}, abstract = {In typical real-time strategy (RTS) games, enemy units are visible only when they are within sight range of a friendly unit. Knowledge of an opponent’s disposition is limited to what can be observed through scouting. Information is costly, since units dedicated to scouting are unavailable for other purposes, and the enemy will resist scouting attempts. It is important to infer as much as possible about the opponent’s current and future strategy from the available observations. We present a dynamic Bayes net model of strategies in the RTS game Starcraft that combines a generative model of how strategies relate to observable quantities with a principled framework for incorporating evidence gained via scouting. We demonstrate the model’s ability to infer unobserved aspects of the game from realistic observations.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-huszar12a, title = {Optimally-Weighted Herding is {B}ayesian Quadrature}, author = {Huszar, Ferenc and Duvenaud, David}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {375--384}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/huszar12a/huszar12a.pdf}, url = {https://proceedings.mlr.press/r10/huszar12a.html}, abstract = {Herding and kernel herding are deterministic methods of choosing samples which summarise a probability distribution. A related task is choosing samples for estimating integrals using Bayesian quadrature. We show that the criterion minimised when selecting samples in kernel herding is equivalent to the posterior variance in Bayesian quadrature. We then show that sequential Bayesian quadrature can be viewed as a weighted version of kernel herding which achieves performance superior to any other weighted herding method. We demonstrate empirically a rate of convergence faster than O(1/N). Our results also imply an upper bound on the empirical error of the Bayesian quadrature estimate.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-hyttinen12a, title = {Causal Discovery of Linear Cyclic Models from Multiple Experimental Data Sets with Overlapping Variables}, author = {Hyttinen, Antti and Eberhardt, Frederick and Hoyer, Patrik O.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {385--394}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/hyttinen12a/hyttinen12a.pdf}, url = {https://proceedings.mlr.press/r10/hyttinen12a.html}, abstract = {Much of scientific data is collected as randomized experiments intervening on some and observing other variables of interest. Quite often, a given phenomenon is investigated in several studies, and different sets of variables are involved in each study. In this article we consider the problem of integrating such knowledge, inferring as much as possible concerning the underlying causal structure with respect to the union of observed variables from such experimental or passive observational overlapping data sets. We do not assume acyclicity or joint causal sufficiency of the underlying data generating model, but we do restrict the causal relationships to be linear and use only second order statistics of the data. We derive conditions for full model identifiability in the most generic case, and provide novel techniques for incorporating an assumption of faithfulness to aid in inference. In each case we seek to establish what is and what is not determined by the data at hand.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-ihler12a, title = {Join-graph based cost-shifting schemes}, author = {Ihler, Alexander T. and Flerova, Natalia and Dechter, Rina and Otten, Lars}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {395--404}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/ihler12a/ihler12a.pdf}, url = {https://proceedings.mlr.press/r10/ihler12a.html}, abstract = {We develop several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: minibucket elimination and message-passing updates for linear programming relaxations. Both methods are quite similar, and offer useful perspectives for the other; our hybrid approaches attempt to balance the advantages of each. We demonstrate the power of our hybrid algorithms through extensive empirical evaluation. Most notably, a Branch and Bound search guided by the heuristic function calculated by one of our new algorithms has recently won first place in the PASCAL2 inference challenge.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-iyer12a, title = {Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications}, author = {Iyer, Rishabh and Bilmes, Jeff A.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {405--415}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/iyer12a/iyer12a.pdf}, url = {https://proceedings.mlr.press/r10/iyer12a.html}, abstract = {We extend the work of Narasimhan and Bilmes [30] for minimizing set functions representable as a dierence between submodular functions. Similar to [30], our new algorithms are guaranteed to monotonically reduce the objective function at every step. We empirically and theoretically show that the per-iteration cost of our algorithms is much less than [30], and our algorithms can be used to efficiently minimize a dierence between submodular functions under various combinatorial constraints, a problem not previously addressed. We provide computational bounds and a hardness result on the multiplicative inapproximability of minimizing the dierence between submodular functions. We show, however, that it is possible to give worst-case additive bounds by providing a polynomial time computable lower-bound on the minima. Finally we show how a number of machine learning problems can be modeled as minimizing the dierence between submodular functions. We experimentally show the validity of our algorithms by testing them on the problem of feature selection with submodular cost features.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-reddi12a, title = {Incentive Decision Processes}, author = {Reddi, Sashank J. and Brunskill, Emma}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {416--425}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/reddi12a/reddi12a.pdf}, url = {https://proceedings.mlr.press/r10/reddi12a.html}, abstract = {We consider Incentive Decision Processes, where a principal seeks to reduce its costs due to another agent’s behavior, by offering incentives to the agent for alternate behavior. We focus on the case where a principal interacts with a greedy agent whose preferences are hidden and static. Though IDPs can be directly modeled as partially observable Markov decision processes (POMDP), we show that it is possible to directly reduce or approximate the IDP as a polynomially-sized MDP: when this representation is approximate, we prove the resulting policy is boundedly-optimal for the original IDP. Our empirical simulations demonstrate the performance benefit of our algorithms over simpler approaches, and also demonstrate that our approximate representation results in a significantly faster algorithm whose performance is extremely close to the optimal policy for the original IDP.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-judah12a, title = {Active Imitation Learning via Reduction to I.I.D. Active Learning}, author = {Judah, Kshitij and Fern, Alan and Dietterich, Thomas G.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {426--435}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/judah12a/judah12a.pdf}, url = {https://proceedings.mlr.press/r10/judah12a.html}, abstract = {In standard passive imitation learning, the goal is to learn a target policy by passively observing full execution trajectories of it. Unfortunately, generating such trajectories can require substantial expert effort and be impractical in some cases. In this paper, we consider active imitation learning with the goal of reducing this effort by querying the expert about the desired action at individual states, which are selected based on answers to past queries and the learner’s interactions with an environment simulator. We introduce a new approach based on reducing active imitation learning to i.i.d. active learning, which can leverage progress in the i.i.d. setting. Our first contribution, is to analyze reductions for both non-stationary and stationary policies, showing that the label complexity (number of queries) of active imitation learning can be substantially less than passive learning. Our second contribution, is to introduce a practical algorithm inspired by the reductions, which is shown to be highly effective in four test domains compared to a number of alternatives.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-kolobov12a, title = {A Theory of Goal-Oriented MDPs with Dead Ends}, author = {Kolobov, Andrey and Mausam and Weld, Daniel}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {436--445}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/kolobov12a/kolobov12a.pdf}, url = {https://proceedings.mlr.press/r10/kolobov12a.html}, abstract = {Stochastic Shortest Path (SSP) MDPs is a problem class widely studied in AI, especially in probabilistic planning. They describe a wide range of scenarios but make the restrictive assumption that the goal is reachable from any state, i.e., that dead-end states do not exist. Because of this, SSPs are unable to model various scenarios that may have catastrophic events (e.g., an airplane possibly crashing if it flies into a storm). Even though MDP algorithms have been used for solving problems with dead ends, a principled theory of SSP extensions that would allow dead ends, including theoretically sound algorithms for solving such MDPs, has been lacking. In this paper, we propose three new MDP classes that admit dead ends under increasingly weaker assumptions. We present Value Iteration-based as well as the more efficient heuristic search algorithms for optimally solving each class, and explore theoretical relationships between these classes. We also conduct a preliminary empirical study comparing the performance of our algorithms on different MDP classes, especially on scenarios with unavoidable dead ends.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-lau12a, title = {Dynamic Stochastic Orienteering Problems for Risk-Aware Applications}, author = {Lau, Hoong Chuin and Yeoh, William and Varakantham, Pradeep and Nguyen, Duc Thien and Chen, Huaxing}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {446--456}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/lau12a/lau12a.pdf}, url = {https://proceedings.mlr.press/r10/lau12a.html}, abstract = {Orienteering problems (OPs) are a variant of the well-known prize-collecting traveling salesman problem, where the salesman needs to choose a subset of cities to visit within a given deadline. OPs and their extensions with stochastic travel times (SOPs) have been used to model vehicle routing problems and tourist trip design problems. However, they suffer from two limitations travel times between cities are assumed to be time independent and the route provided is independent of the risk preference (with respect to violating the deadline) of the user. To address these issues, we make the following contributions: We introduce (1) a dynamic SOP (DSOP) model, which is an extension of SOPs with dynamic (time-dependent) travel times; (2) a risk-sensitive criterion to allow for different risk preferences; and (3) a local search algorithm to solve DSOPs with this risk-sensitive criterion. We evaluated our algorithms on a real-world dataset for a theme park navigation problem as well as synthetic datasets employed in the literature.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-letchford12a, title = {Computing Optimal Security Strategies for Interdependent Assets}, author = {Letchford, Joshua and Vorobeychik, Yevgeniy}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {457--466}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/letchford12a/letchford12a.pdf}, url = {https://proceedings.mlr.press/r10/letchford12a.html}, abstract = {We introduce a novel framework for computing optimal randomized security policies in networked domains which extends previous approaches in several ways. First, we extend previous linear programming techniques for Stackelberg security games to incorporate benefits and costs of arbitrary security configurations on individual assets. Second, we offer a principled model of failure cascades that allows us to capture both the direct and indirect value of assets, and extend this model to capture uncertainty about the structure of the interdependency network. Third, we extend the linear programming formulation to account for exogenous (random) failures in addition to targeted attacks. The goal of our work is two-fold. First, we aim to develop techniques for computing optimal security strategies in realistic settings involving interdependent security. To this end, we evaluate the value of our technical contributions in comparison with previous approaches, and show that our approach yields much better defense policies and scales to realistic graphs. Second, our computational framework enables us to attain theoretical insights about security on networks. As an example, we study how allowing security to be endogenous impacts the relative resilience of different network topologies.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-li12a, title = {Nested Dictionary Learning for Hierarchical Organization of Imagery and Text}, author = {Li, Lingbo and Zhang, XianXing and Zhou, Mingyuan and Carin, Lawrence}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {467--476}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/li12a/li12a.pdf}, url = {https://proceedings.mlr.press/r10/li12a.html}, abstract = {A tree-based dictionary learning model is developed for joint analysis of imagery and associated text. The dictionary learning may be applied directly to the imagery from patches, or to general feature vectors extracted from patches or superpixels (using any existing method for image feature extraction). Each image is associated with a path through the tree (from root to a leaf), and each of the multiple patches in a given image is associated with one node in that path. Nodes near the tree root are shared between multiple paths, representing image characteristics that are common among different types of images. Moving toward the leaves, nodes become specialized, representing details in image classes. If available, words (text) are also jointly modeled, with a path-dependent probability over words. The tree structure is inferred via a nested Dirichlet process, and a retrospective stick-breaking sampler is used to infer the tree depth and width.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-lin12a, title = {Learning Mixtures of Submodular Shells with Application to Document Summarization}, author = {Lin, Hui and Bilmes, Jeff A.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {477--488}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/lin12a/lin12a.pdf}, url = {https://proceedings.mlr.press/r10/lin12a.html}, abstract = {We introduce a method to learn a mixture of submodular "shells" in a large-margin setting. A submodular shell is an abstract submodular function that can be instantiated with a ground set and a set of parameters to produce a submodular function. A mixture of such shells can then also be so instantiated to produce a more complex submodular function. What our algorithm learns are the mixture weights over such shells. We provide a risk bound guarantee when learning in a large-margin structured-prediction setting using a projected subgradient method when only approximate submodular optimization is possible (such as with submodular function maximization). We apply this method to the problem of multi-document summarization and produce the best results reported so far on the widely used NIST DUC-05 through DUC-07 document summarization corpora.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-lin12b, title = {Crowdsourcing Control: Moving Beyond Multiple Choice}, author = {Lin, Christopher H. and Mausam and Weld, Daniel}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {489--498}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/lin12b/lin12b.pdf}, url = {https://proceedings.mlr.press/r10/lin12b.html}, abstract = {To ensure quality results from crowdsourced tasks, requesters often aggregate worker responses and use one of a plethora of strategies to infer the correct answer from the set of noisy responses. However, all current models assume prior knowledge of all possible outcomes of the task. While not an unreasonable assumption for tasks that can be posited as multiple-choice questions (e.g. n-ary classification), we observe that many tasks do not naturally fit this paradigm, but instead demand a free-response formulation where the outcome space is of infinite size (e.g. audio transcription). We model such tasks with a novel probabilistic graphical model, and design and implement LazySusan, a decision-theoretic controller that dynamically requests responses as necessary in order to infer answers to these tasks. We also design an EM algorithm to jointly learn the parameters of our model while inferring the correct answers to multiple tasks at a time. Live experiments on Amazon Mechanical Turk demonstrate the superiority of LazySusan at solving SAT Math questions, eliminating 83.2% of the error and achieving greater net utility compared to the state-ofthe-art strategy, majority-voting. We also show in live experiments that our EM algorithm outperforms majority-voting on a visualization task that we design.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-ling12a, title = {Response Aware Model-Based Collaborative Filtering}, author = {Ling, Guang and Yang, Haiqin and Lyu, Michael R. and King, Irwin}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {499--508}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/ling12a/ling12a.pdf}, url = {https://proceedings.mlr.press/r10/ling12a.html}, abstract = {Previous work on recommender systems mainly focus on fitting the ratings provided by users. However, the response patterns, i.e., some items are rated while others not, are generally ignored. We argue that failing to observe such response patterns can lead to biased parameter estimation and sub-optimal model performance. Although several pieces of work have tried to model users’ response patterns, they miss the effectiveness and interpretability of the successful matrix factorization collaborative filtering approaches. To bridge the gap, in this paper, we unify explicit response models and PMF to establish the Response Aware Probabilistic Matrix Factorization (RAPMF) framework. We show that RAPMF subsumes PMF as a special case. Empirically we demonstrate the merits of RAPMF from various aspects.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-liu12a, title = {Graphical-model Based Multiple Testing under Dependence, with Applications to Genome-wide Association Studies}, author = {Liu, Jie and Zhang, Chunming and McCarty, Catherine and Peissig, Peggy and Burnside, Elizabeth and Page, David}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {509--520}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/liu12a/liu12a.pdf}, url = {https://proceedings.mlr.press/r10/liu12a.html}, abstract = {Large-scale multiple testing tasks often exhibit dependence, and leveraging the dependence between individual tests is still one challenging and important problem in statistics. With recent advances in graphical models, it is feasible to use them to perform multiple testing under dependence. We propose a multiple testing procedure which is based on a Markov-random-field-coupled mixture model. The ground truth of hypotheses is represented by a latent binary Markov random field, and the observed test statistics appear as the coupled mixture variables. The parameters in our model can be automatically learned by a novel EM algorithm. We use an MCMC algorithm to infer the posterior probability that each hypothesis is null (termed local index of significance), and the false discovery rate can be controlled accordingly. Simulations show that the numerical performance of multiple testing can be improved substantially by using our procedure. We apply the procedure to a real-world genome-wide association study on breast cancer, and we identify several SNPs with strong association evidence.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-liu12b, title = {Belief Propagation for Structured Decision Making}, author = {Liu, Qiang and Ihler, Alexander T.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {521--530}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/liu12b/liu12b.pdf}, url = {https://proceedings.mlr.press/r10/liu12b.html}, abstract = {Variational inference algorithms such as belief propagation have had tremendous impact on our ability to learn and use graphical models, and give many insights for developing or understanding exact and approximate inference. However, variational approaches have not been widely adoped for decision making in graphical models, often formulated through influence diagrams and including both centralized and decentralized (or multi-agent) decisions. In this work, we present a general variational framework for solving structured cooperative decision-making problems, use it to propose several belief propagation-like algorithms, and analyze them both theoretically and empirically.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-lowd12a, title = {Closed-Form Learning of {M}arkov Networks from Dependency Networks}, author = {Lowd, Daniel}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {531--540}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/lowd12a/lowd12a.pdf}, url = {https://proceedings.mlr.press/r10/lowd12a.html}, abstract = {Markov networks (MNs) are a powerful way to compactly represent a joint probability distribution, but most MN structure learning methods are very slow, due to the high cost of evaluating candidates structures. Dependency networks (DNs) represent a probability distribution as a set of conditional probability distributions. DNs are very fast to learn, but the conditional distributions may be inconsistent with each other and few inference algorithms support DNs. In this paper, we present a closed-form method for converting a DN into an MN, allowing us to enjoy both the efficiency of DN learning and the convenience of the MN representation. When the DN is consistent, this conversion is exact. For inconsistent DNs, we present averaging methods that significantly improve the approximation. In experiments on 12 standard datasets, our methods are orders of magnitude faster than and often more accurate than combining conditional distributions using weight learning.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-lu12a, title = {{B}ayesian Vote Manipulation: Optimal Strategies and Impact on Welfare}, author = {Lu, Tyler and Tang, Pingzhong and Procaccia, Ariel D. and Boutilier, Craig}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {541--551}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/lu12a/lu12a.pdf}, url = {https://proceedings.mlr.press/r10/lu12a.html}, abstract = {Most analyses of manipulation of voting schemes have adopted two assumptions that greatly diminish their practical import. First, it is usually assumed that the manipulators have full knowledge of the votes of the nonmanipulating agents. Second, analysis tends to focus on the probability of manipulation rather than its impact on the social choice objective (e.g., social welfare). We relax both of these assumptions by analyzing optimal Bayesian manipulation strategies when the manipulators have only partial probabilistic information about nonmanipulator votes, and assessing the expected loss in social welfare (in the broad sense of the term). We present a general optimization framework for the derivation of optimal manipulation strategies given arbitrary voting rules and distributions over preferences. We theoretically and empirically analyze the optimal manipulability of some popular voting rules using distributions and real data sets that go well beyond the common, but unrealistic, impartial culture assumption. We also shed light on the stark difference between the loss in social welfare and the probability of manipulation by showing that even when manipulation is likely, impact to social welfare is slight (and often negligible).}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-lukasiewicz12a, title = {Heuristic Ranking in Tightly Coupled Probabilistic Description Logics}, author = {Lukasiewicz, Thomas and Martinez, Maria Vanina and Orsi, Giorgio and Simari, Gerardo I.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {552--561}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/lukasiewicz12a/lukasiewicz12a.pdf}, url = {https://proceedings.mlr.press/r10/lukasiewicz12a.html}, abstract = {The Semantic Web effort has steadily been gaining traction in the recent years. In particular,Web search companies are recently realizing that their products need to evolve towards having richer semantic search capabilities. Description logics (DLs) have been adopted as the formal underpinnings for Semantic Web languages used in describing ontologies. Reasoning under uncertainty has recently taken a leading role in this arena, given the nature of data found on theWeb. In this paper, we present a probabilistic extension of the DL EL++ (which underlies the OWL2 EL profile) using Markov logic networks (MLNs) as probabilistic semantics. This extension is tightly coupled, meaning that probabilistic annotations in formulas can refer to objects in the ontology. We show that, even though the tightly coupled nature of our language means that many basic operations are data-intractable, we can leverage a sublanguage of MLNs that allows to rank the atomic consequences of an ontology relative to their probability values (called ranking queries) even when these values are not fully computed. We present an anytime algorithm to answer ranking queries, and provide an upper bound on the error that it incurs, as well as a criterion to decide when results are guaranteed to be correct.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-mahadevan12a, title = {Sparse Q-learning with Mirror Descent}, author = {Mahadevan, Sridhar and Liu, Bo}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {562--571}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/mahadevan12a/mahadevan12a.pdf}, url = {https://proceedings.mlr.press/r10/mahadevan12a.html}, abstract = {This paper explores a new framework for reinforcement learning based on online convex optimization, in particular mirror descent and related algorithms. Mirror descent can be viewed as an enhanced gradient method, particularly suited to minimization of convex functions in highdimensional spaces. Unlike traditional gradient methods, mirror descent undertakes gradient updates of weights in both the dual space and primal space, which are linked together using a Legendre transform. Mirror descent can be viewed as a proximal algorithm where the distance generating function used is a Bregman divergence. A new class of proximal-gradient based temporal-difference (TD) methods are presented based on different Bregman divergences, which are more powerful than regular TD learning. Examples of Bregman divergences that are studied include p-norm functions, and Mahalanobis distance based on the covariance of sample gradients. A new family of sparse mirror-descent reinforcement learning methods are proposed, which are able to find sparse fixed points of an l1-regularized Bellman equation at significantly less computational cost than previous methods based on second-order matrix methods. An experimental study of mirror-descent reinforcement learning is presented using discrete and continuous Markov decision processes.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-marinescu12a, title = {Multi-objective Influence Diagrams}, author = {Marinescu, Radu and Razak, Abdul and Wilson, Nic}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {572--581}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/marinescu12a/marinescu12a.pdf}, url = {https://proceedings.mlr.press/r10/marinescu12a.html}, abstract = {We describe multi-objective influence diagrams, based on a set of p objectives, where utility values are vectors in Rp, and are typically only partially ordered. These can still be solved by a variable elimination algorithm, leading to a set of maximal values of expected utility. If the Pareto ordering is used this set can often be prohibitively large. We consider approximate representations of the Pareto set based on e-coverings, allowing much larger problems to be solved. In addition, we define a method for incorporating user tradeoffs, which also greatly improves the efficiency.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-mattar12a, title = {Unsupervised Joint Alignment and Clustering using {B}ayesian Nonparametrics}, author = {Mattar, Marwan A. and Hanson, Allen R. and Learned-Miller, Erik G.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {582--591}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/mattar12a/mattar12a.pdf}, url = {https://proceedings.mlr.press/r10/mattar12a.html}, abstract = {Joint alignment of a collection of functions is the process of independently transforming the functions so that they appear more similar to each other. Typically, such unsupervised alignment algorithms fail when presented with complex data sets arising from multiple modalities or make restrictive assumptions about the form of the functions or transformations, limiting their generality. We present a transformed Bayesian infinite mixture model that can simultaneously align and cluster a data set. Our model and associated learning scheme offer two key advantages: the optimal number of clusters is determined in a data-driven fashion through the use of a Dirichlet process prior, and it can accommodate any transformation function parameterized by a continuous parameter vector. As a result, it is applicable to a wide range of data types, and transformation functions. We present positive results on synthetic two-dimensional data, on a set of one-dimensional curves, and on various image data sets, showing large improvements over previous work. We discuss several variations of the model and conclude with directions for future work.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-matusevych12a, title = {Hokusai - Sketching Streams in Real Time}, author = {Matusevych, Sergiy and Smola, Alex and Ahmed, Amr}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {592--601}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/matusevych12a/matusevych12a.pdf}, url = {https://proceedings.mlr.press/r10/matusevych12a.html}, abstract = {We describe Hokusai, a real time system which is able to capture frequency information for streams of arbitrary sequences of symbols. The algorithm uses the CountMin sketch as its basis and exploits the fact that sketching is linear. It provides real time statistics of arbitrary events, e.g. streams of queries as a function of time. We use a factorizing approximation to provide point estimates at arbitrary (time, item) combinations. Queries can be answered in constant time.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-maua12a, title = {The Complexity of Approximately Solving Influence Diagrams}, author = {Maua, Denis D. and de Campos, Cassio Polpo and Zaffalon, Marco}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {602--611}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/maua12a/maua12a.pdf}, url = {https://proceedings.mlr.press/r10/maua12a.html}, abstract = {Influence diagrams allow for intuitive and yet precise description of complex situations involving decision making under uncertainty. Unfortunately, most of the problems described by influence diagrams are hard to solve. In this paper we discuss the complexity of approximately solving influence diagrams. We do not assume no-forgetting or regularity, which makes the class of problems we address very broad. Remarkably, we show that when both the tree-width and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-mourao12a, title = {Learning {STRIPS} Operators from Noisy and Incomplete Observations}, author = {Mourao, Kira and Zettlemoyer, Luke S. and Petrick, Ronald P. A. and Steedman, Mark}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {612--621}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/mourao12a/mourao12a.pdf}, url = {https://proceedings.mlr.press/r10/mourao12a.html}, abstract = {Agents learning to act autonomously in real-world domains must acquire a model of the dynamics of the domain in which they operate. Learning domain dynamics can be challenging, especially where an agent only has partial access to the world state, and/or noisy external sensors. Even in standard STRIPS domains, existing approaches cannot learn from noisy, incomplete observations typical of real-world domains. We propose a method which learns STRIPS action models in such domains, by decomposing the problem into first learning a transition function between states in the form of a set of classifiers, and then deriving explicit STRIPS rules from the classifiers’ parameters. We evaluate our approach on simulated standard planning domains from the International Planning Competition, and show that it learns useful domain descriptions from noisy, incomplete observations.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-niepert12a, title = {{M}arkov Chains on Orbits of Permutation Groups}, author = {Niepert, Mathias}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {622--632}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/niepert12a/niepert12a.pdf}, url = {https://proceedings.mlr.press/r10/niepert12a.html}, abstract = {We present a novel approach to detecting and utilizing symmetries in probabilistic graphical models with two main contributions. First, we present a scalable approach to computing generating sets of permutation groups representing the symmetries of graphical models. Second, we introduce orbital Markov chains, a novel family of Markov chains leveraging model symmetries to reduce mixing times. We establish an insightful connection between model symmetries and rapid mixing of orbital Markov chains. Thus, we present the first lifted MCMC algorithm for probabilistic graphical models. Both analytical and empirical results demonstrate the effectiveness and efficiency of the approach.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-niinimaki12a, title = {Local Structure Discovery in {B}ayesian Networks}, author = {Niinimaki, Teppo and Parviainen, Pekka}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {633--642}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/niinimaki12a/niinimaki12a.pdf}, url = {https://proceedings.mlr.press/r10/niinimaki12a.html}, abstract = {Learning a Bayesian network structure from data is an NP-hard problem and thus exact algorithms are feasible only for small data sets. Therefore, network structures for larger networks are usually learned with various heuristics. Another approach to scaling up the structure learning is local learning. In local learning, the modeler has one or more target variables that are of special interest; he wants to learn the structure near the target variables and is not interested in the rest of the variables. In this paper, we present a score-based local learning algorithm called SLL. We conjecture that our algorithm is theoretically sound in the sense that it is optimal in the limit of large sample size. Empirical results suggest that SLL is competitive when compared to the constraint-based HITON algorithm. We also study the prospects of constructing the network structure for the whole node set based on local results by presenting two algorithms and comparing them to several heuristics.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-nishiyama12a, title = {{H}ilbert Space Embeddings of POMDPs}, author = {Nishiyama, Yu and Boularias, Abdeslam and Gretton, Arthur and Fukumizu, Kenji}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {643--652}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/nishiyama12a/nishiyama12a.pdf}, url = {https://proceedings.mlr.press/r10/nishiyama12a.html}, abstract = {A nonparametric approach for policy learning for POMDPs is proposed. The approach represents distributions over the states, observations, and actions as embeddings in feature spaces, which are reproducing kernel Hilbert spaces. Distributions over states given the observations are obtained by applying the kernel Bayes’ rule to these distribution embeddings. Policies and value functions are defined on the feature space over states, which leads to a feature space expression for the Bellman equation. Value iteration may then be used to estimate the optimal value function and associated policy. Experimental results confirm that the correct policy is learned using the feature space representation.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-oliehoek12a, title = {Exploiting Structure in Cooperative {B}ayesian Games}, author = {Oliehoek, Frans A. and Whiteson, Shimon and Spaan, Matthijs T. J.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {653--663}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/oliehoek12a/oliehoek12a.pdf}, url = {https://proceedings.mlr.press/r10/oliehoek12a.html}, abstract = {Cooperative Bayesian games (BGs) can model decision-making problems for teams of agents under imperfect information, but require space and computation time that is exponential in the number of agents. While agent independence has been used to mitigate these problems in perfect information settings, we propose a novel approach for BGs based on the observation that BGs additionally possess a different types of structure, which we call type independence. We propose a factor graph representation that captures both forms of independence and present a theoretical analysis showing that non-serial dynamic programming cannot effectively exploit type independence, while Max-Sum can. Experimental results demonstrate that our approach can tackle cooperative Bayesian games of unprecedented size.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-otten12a, title = {A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models}, author = {Otten, Lars and Dechter, Rina}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {664--673}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/otten12a/otten12a.pdf}, url = {https://proceedings.mlr.press/r10/otten12a.html}, abstract = {We study the problem of complexity estimation in the context of parallelizing an advanced Branch and Bound-type algorithm over graphical models. The algorithm’s pruning power makes load balancing, one crucial element of every distributed system, very challenging. We propose using a statistical regression model to identify and tackle disproportionally complex parallel subproblems, the cause of load imbalance, ahead of time. The proposed model is evaluated and analyzed on various levels and shown to yield robust predictions. We then demonstrate its effectiveness for load balancing in practice.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-parikh12a, title = {A Spectral Algorithm for Latent Junction Trees}, author = {Parikh, Ankur P. and Song, Le and Ishteva, Mariya and Teodoru, Gabi and Xing, Eric P.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {674--683}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/parikh12a/parikh12a.pdf}, url = {https://proceedings.mlr.press/r10/parikh12a.html}, abstract = {Latent variable models are an elegant framework for capturing rich probabilistic dependencies in many applications. However, current approaches typically parametrize these models using conditional probability tables, and learning relies predominantly on local search heuristics such as Expectation Maximization. Using tensor algebra, we propose an alternative parameterization of latent variable models (where the model structures are junction trees) that still allows for computation of marginals among observed variables. While this novel representation leads to a moderate increase in the number of parameters for junction trees of low treewidth, it lets us design a local-minimum-free algorithm for learning this parameterization. The main computation of the algorithm involves only tensor operations and SVDs which can be orders of magnitude faster than EM algorithms for large datasets. To our knowledge, this is the first provably consistent parameter learning technique for a large class of low-treewidth latent graphical models beyond trees. We demonstrate the advantages of our method on synthetic and real datasets.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-poon12a, title = {A Model-Based Approach to Rounding in Spectral Clustering}, author = {Poon, Leonard K. M. and Liu, April H. and Liu, Tengfei and Zhang, Nevin Lianwen}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {684--693}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/poon12a/poon12a.pdf}, url = {https://proceedings.mlr.press/r10/poon12a.html}, abstract = {In spectral clustering, one defines a similarity matrix for a collection of data points, transforms the matrix to get the Laplacian matrix, finds the eigenvectors of the Laplacian matrix, and obtains a partition of the data using the leading eigenvectors. The last step is sometimes referred to as rounding, where one needs to decide how many leading eigenvectors to use, to determine the number of clusters, and to partition the data points. In this paper, we propose a novel method for rounding. The method differs from previous methods in three ways. First, we relax the assumption that the number of clusters equals the number of eigenvectors used. Second, when deciding the number of leading eigenvectors to use, we not only rely on information contained in the leading eigenvectors themselves, but also use subsequent eigenvectors. Third, our method is model-based and solves all the three subproblems of rounding using a class of graphical models called latent tree models. We evaluate our method on both synthetic and real-world data. The results show that our method works correctly in the ideal case where between-clusters similarity is 0, and degrades gracefully as one moves away from the ideal case.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-procaccia12a, title = {A Maximum Likelihood Approach For Selecting Sets of Alternatives}, author = {Procaccia, Ariel D. and Reddi, Sashank J. and Shah, Nisarg}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {694--703}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/procaccia12a/procaccia12a.pdf}, url = {https://proceedings.mlr.press/r10/procaccia12a.html}, abstract = {We consider the problem of selecting a subset of alternatives given noisy evaluations of the relative strength of different alternatives. We wish to select a k-subset (for a given k) that provides a maximum likelihood estimate for one of several objectives, e.g., containing the strongest alternative. Although this problem is NP-hard, we show that when the noise level is sufficiently high, intuitive methods provide the optimal solution. We thus generalize classical results about singling out one alternative and identifying the hidden ranking of alternatives by strength. Extensive experiments show that our methods perform well in practical settings.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-refaat12a, title = {New Advances and Theoretical Insights into {EDML}}, author = {Refaat, Khaled S. and Choi, Arthur and Darwiche, Adnan}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {704--713}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/refaat12a/refaat12a.pdf}, url = {https://proceedings.mlr.press/r10/refaat12a.html}, abstract = {EDML is a recently proposed algorithm for learning MAP parameters in Bayesian networks. In this paper, we present a number of new advances and insights on the EDML algorithm. First, we provide the multivalued extension of EDML, originally proposed for Bayesian networks over binary variables. Next, we identify a simplified characterization of EDML that further implies a simple fixed-point algorithm for the convex optimization problem that underlies it. This characterization further reveals a connection between EDML and EM: a fixed point of EDML is a fixed point of EM, and vice versa. We thus identify also a new characterization of EM fixed points, but in the semantics of EDML. Finally, we propose a hybrid EDML/EM algorithm that takes advantage of the improved empirical convergence behavior of EDML, while maintaining the monotonic improvement property of EM.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-roeder12a, title = {Active Learning with Distributional Estimates}, author = {Roeder, Jens and Nadler, Boaz and Kunzmann, Kevin and Hamprecht, Fred A.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {714--724}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/roeder12a/roeder12a.pdf}, url = {https://proceedings.mlr.press/r10/roeder12a.html}, abstract = {Active Learning (AL) is increasingly important in a broad range of applications. Two main AL principles to obtain accurate classification with few labeled data are refinement of the current decision boundary and exploration of poorly sampled regions. In this paper we derive a novel AL scheme that balances these two principles in a natural way. In contrast to many AL strategies, which are based on an estimated class conditional probability ^p(y|x), a key component of our approach is to view this quantity as a random variable, hence explicitly considering the uncertainty in its estimated value. Our main contribution is a novel mathematical framework for uncertainty-based AL, and a corresponding AL scheme, where the uncertainty in ^p(y|x) is modeled by a second-order distribution. On the practical side, we show how to approximate such second-order distributions for kernel density classification. Finally, we find that over a large number of UCI, USPS and Caltech4 datasets, our AL scheme achieves significantly better learning curves than popular AL methods such as uncertainty sampling and error reduction sampling, when all use the same kernel density classifier.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-palacios12a, title = {Integrated Nested {L}aplace Approximation for {B}ayesian Nonparametric Phylodynamics}, author = {Palacios, Julia A. and Minin, Vladimir N.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {725--734}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/palacios12a/palacios12a.pdf}, url = {https://proceedings.mlr.press/r10/palacios12a.html}, abstract = {The goal of phylodynamics, an area on the intersection of phylogenetics and population genetics, is to reconstruct population size dynamics from genetic data. Recently, a series of nonparametric Bayesian methods have been proposed for such demographic reconstructions. These methods rely on prior specifications based on Gaussian processes and proceed by approximating the posterior distribution of population size trajectories via Markov chain Monte Carlo (MCMC) methods. In this paper, we adapt an integrated nested Laplace approximation (INLA), a recently proposed approximate Bayesian inference for latent Gaussian models, to the estimation of population size trajectories. We show that when a genealogy of sampled individuals can be reliably estimated from genetic data, INLA enjoys high accuracy and can replace MCMC entirely. We demonstrate significant computational efficiency over the state-of-the-art MCMC methods. We illustrate INLA-based population size inference using simulations and genealogies of hepatitis C and human influenza viruses.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-sanfilippo12a, title = {From imprecise probability assessments to conditional probabilities with quasi additive classes of conditioning events}, author = {Sanfilippo, Giuseppe}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {735--744}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/sanfilippo12a/sanfilippo12a.pdf}, url = {https://proceedings.mlr.press/r10/sanfilippo12a.html}, abstract = {In this paper, starting from a generalized coherent (i.e. avoiding uniform loss) intervalvalued probability assessment on a finite family of conditional events, we construct conditional probabilities with quasi additive classes of conditioning events which are consistent with the given initial assessment. Quasi additivity assures coherence for the obtained conditional probabilities. In order to reach our goal we define a finite sequence of conditional probabilities by exploiting some theoretical results on g-coherence. In particular, we use solutions of a finite sequence of linear systems.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-savchynskyy12a, title = {Efficient {MRF} Energy Minimization via Adaptive Diminishing Smoothing}, author = {Savchynskyy, Bogdan and Schmidt, Stefan and Kappes, Joerg and Schnoerr, Christoph}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {745--754}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/savchynskyy12a/savchynskyy12a.pdf}, url = {https://proceedings.mlr.press/r10/savchynskyy12a.html}, abstract = {We consider the linear programming relaxation of an energy minimization problem for Markov Random Fields. The dual objective of this problem can be treated as a concave and unconstrained, but non-smooth function. The idea of smoothing the objective prior to optimization was recently proposed in a series of papers. Some of them suggested the idea to decrease the amount of smoothing (so called temperature) while getting closer to the optimum. However, no theoretical substantiation was provided. We propose an adaptive smoothing diminishing algorithm based on the duality gap between relaxed primal and dual objectives and demonstrate the efficiency of our approach with a smoothed version of Sequential Tree-Reweighted Message Passing (TRW-S) algorithm. The strategy is applicable to other algorithms as well, avoids adhoc tuning of the smoothing during iterations, and provably guarantees convergence to the optimum.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-schlicht12a, title = {Predicting the behavior of interacting humans by fusing data from multiple sources}, author = {Schlicht, Erik J. and Lee, Ritchie and Wolpert, David H. and Kochenderfer, Mykel J. and Tracey, Brendan}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {755--763}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/schlicht12a/schlicht12a.pdf}, url = {https://proceedings.mlr.press/r10/schlicht12a.html}, abstract = {Multi-fidelity methods combine inexpensive low-fidelity simulations with costly but highfidelity simulations to produce an accurate model of a system of interest at minimal cost. They have proven useful in modeling physical systems and have been applied to engineering problems such as wing-design optimization. During human-in-the-loop experimentation, it has become increasingly common to use online platforms, like Mechanical Turk, to run low-fidelity experiments to gather human performance data in an efficient manner. One concern with these experiments is that the results obtained from the online environment generalize poorly to the actual domain of interest. To address this limitation, we extend traditional multi-fidelity approaches to allow us to combine fewer data points from high-fidelity human-in-the-loop experiments with plentiful but less accurate data from low-fidelity experiments to produce accurate models of how humans interact. We present both model-based and model-free methods, and summarize the predictive performance of each method under dierent conditions.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-silva12a, title = {Latent Composite Likelihood Learning for the Structured Canonical Correlation Model}, author = {Silva, Ricardo}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {764--773}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/silva12a/silva12a.pdf}, url = {https://proceedings.mlr.press/r10/silva12a.html}, abstract = {Latent variable models are used to estimate variables of interest quantities which are observable only up to some measurement error. In many studies, such variables are known but not precisely quantifiable (such as "job satisfaction" in social sciences and marketing, "analytical ability" in educational testing, or "inflation" in economics). This leads to the development of measurement instruments to record noisy indirect evidence for such unobserved variables such as surveys, tests and price indexes. In such problems, there are postulated latent variables and a given measurement model. At the same time, other unantecipated latent variables can add further unmeasured confounding to the observed variables. The problem is how to deal with unantecipated latents variables. In this paper, we provide a method loosely inspired by canonical correlation that makes use of background information concerning the "known" latent variables. Given a partially specified structure, it provides a structure learning approach to detect "unknown unknowns," the confounding effect of potentially infinitely many other latent variables. This is done without explicitly modeling such extra latent factors. Because of the special structure of the problem, we are able to exploit a new variation of composite likelihood fitting to efficiently learn this structure. Validation is provided with experiments in synthetic data and the analysis of a large survey done with a sample of over 100,000 staff members of the National Health Service of the United Kingdom.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-singh12a, title = {Spectrum Identification using a Dynamic {B}ayesian Network Model of Tandem Mass Spectra}, author = {Singh, Ajit P. and Halloran, John and Bilmes, Jeff A. and Kirchoff, Katrin and Noble, William S.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {774--784}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/singh12a/singh12a.pdf}, url = {https://proceedings.mlr.press/r10/singh12a.html}, abstract = {Shotgun proteomics is a high-throughput technology used to identify unknown proteins in a complex mixture. At the heart of this process is a prediction task, the spectrum identification problem, in which each fragmentation spectrum produced by a shotgun proteomics experiment must be mapped to the peptide (protein subsequence) which generated the spectrum. We propose a new algorithm for spectrum identification, based on dynamic Bayesian networks, which significantly outperforms the de-facto standard tools for this task: SEQUEST and Mascot.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-sinn12a, title = {Detecting Change-Points in Time Series by Maximum Mean Discrepancy of Ordinal Pattern Distributions}, author = {Sinn, Mathieu and Ghodsi, Ali and Keller, Karsten}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {785--793}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/sinn12a/sinn12a.pdf}, url = {https://proceedings.mlr.press/r10/sinn12a.html}, abstract = {As a new method for detecting change-points in high-resolution time series, we apply Maximum Mean Discrepancy to the distributions of ordinal patterns in different parts of a time series. The main advantage of this approach is its computational simplicity and robustness with respect to (non-linear) monotonic transformations, which makes it particularly well-suited for the analysis of long biophysical time series where the exact calibration of measurement devices is unknown or varies with time. We establish consistency of the method and evaluate its performance in simulation studies. Furthermore, we demonstrate the application to the analysis of electroencephalography (EEG) and electrocardiography (ECG) recordings.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-sontag12a, title = {Efficiently Searching for Frustrated Cycles in {MAP} Inference}, author = {Sontag, David and Choe, Do Kook and Li, Yitao}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {794--803}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/sontag12a/sontag12a.pdf}, url = {https://proceedings.mlr.press/r10/sontag12a.html}, abstract = {Dual decomposition provides a tractable framework for designing algorithms for finding the most probable (MAP) configuration in graphical models. However, for many real-world inference problems, the typical decomposition has a large integrality gap, due to frustrated cycles. One way to tighten the relaxation is to introduce additional constraints that explicitly enforce cycle consistency. Earlier work showed that cluster-pursuit algorithms, which iteratively introduce cycle and other higherorder consistency constraints, allows one to exactly solve many hard inference problems. However, these algorithms explicitly enumerate a candidate set of clusters, limiting them to triplets or other short cycles. We solve the search problem for cycle constraints, giving a nearly linear time algorithm for finding the most frustrated cycle of arbitrary length. We show how to use this search algorithm together with the dual decomposition framework and clusterpursuit. The new algorithm exactly solves MAP inference problems arising from relational classification and stereo vision.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-petrik12a, title = {An Approximate Solution Method for Large Risk-Averse {M}arkov Decision Processes}, author = {Petrik, Marek and Subramanian, Dharmashankar}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {804--813}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/petrik12a/petrik12a.pdf}, url = {https://proceedings.mlr.press/r10/petrik12a.html}, abstract = {Stochastic domains often involve risk-averse decision makers. While recent work has focused on how to model risk in Markov decision processes using risk measures, it has not addressed the problem of solving large risk-averse formulations. In this paper, we propose and analyze a new method for solving large risk-averse MDPs with hybrid continuous-discrete state spaces and continuous action spaces. The proposed method iteratively improves a bound on the value function using a linearity structure of the MDP. We demonstrate the utility and properties of the method on a portfolio optimization problem.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-sun12a, title = {Probability and Asset Updating using {B}ayesian Networks for Combinatorial Prediction Markets}, author = {Sun, Wei and Hanson, Robin and Laskey, Kathryn Blackmond and Twardy, Charles}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {814--823}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/sun12a/sun12a.pdf}, url = {https://proceedings.mlr.press/r10/sun12a.html}, abstract = {A market-maker-based prediction market lets forecasters aggregate information by editing a consensus probability distribution either directly or by trading securities that pay off contingent on an event of interest. Combinatorial prediction markets allow trading on any event that can be specified as a combination of a base set of events. However, explicitly representing the full joint distribution is infeasible for markets with more than a few base events. A factored representation such as a Bayesian network (BN) can achieve tractable computation for problems with many related variables. Standard BN inference algorithms, such as the junction tree algorithm, can be used to update a representation of the entire joint distribution given a change to any local conditional probability. However, in order to let traders reuse assets from prior trades while never allowing assets to become negative, a BN based prediction market also needs to update a representation of each user’s assets and find the conditional state in which a user has minimum assets. Users also find it useful to see their expected assets given an edit outcome. We show how to generalize the junction tree algorithm to perform all these computations.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-tarlow12a, title = {Fast Exact Inference for Recursive Cardinality Models}, author = {Tarlow, Daniel and Swersky, Kevin and Zemel, Richard S. and Adams, Ryan Prescott and Frey, Brendan J.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {824--833}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/tarlow12a/tarlow12a.pdf}, url = {https://proceedings.mlr.press/r10/tarlow12a.html}, abstract = {Cardinality potentials are a generally useful class of high order potential that affect probabilities based on how many of D binary variables are active. Maximum a posteriori (MAP) inference for cardinality potential models is well-understood, with efficient computations taking O(DlogD) time. Yet efficient marginalization and sampling have not been addressed as thoroughly in the machine learning community. We show that there exists a simple algorithm for computing marginal probabilities and drawing exact joint samples that runs in O(Dlog2 D) time, and we show how to frame the algorithm as efficient belief propagation in a low order tree-structured model that includes additional auxiliary variables. We then develop a new, more general class of models, termed Recursive Cardinality models, which take advantage of this efficiency. Finally, we show how to do efficient exact inference in models composed of a tree structure and a cardinality potential. We explore the expressive power of Recursive Cardinality models and empirically demonstrate their utility.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-taylor12a, title = {Value Function Approximation in Noisy Environments Using Locally Smoothed Regularized Approximate Linear Programs}, author = {Taylor, Gavin and Parr, Ron}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {834--841}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/taylor12a/taylor12a.pdf}, url = {https://proceedings.mlr.press/r10/taylor12a.html}, abstract = {Recently, Petrik et al. demonstrated that L1Regularized Approximate Linear Programming (RALP) could produce value functions and policies which compared favorably to established linear value function approximation techniques like LSPI. RALP’s success primarily stems from the ability to solve the feature selection and value function approximation steps simultaneously. RALP’s performance guarantees become looser if sampled next states are used. For very noisy domains, RALP requires an accurate model rather than samples, which can be unrealistic in some practical scenarios. In this paper, we demonstrate this weakness, and then introduce Locally Smoothed L1-Regularized Approximate Linear Programming (LS-RALP). We demonstrate that LS-RALP mitigates inaccuracies stemming from noise even without an accurate model. We show that, given some smoothness assumptions, as the number of samples increases, error from noise approaches zero, and provide experimental examples of LS-RALP’s success on common reinforcement learning benchmark problems.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-virtanen12a, title = {Factorized Multi-Modal Topic Model}, author = {Virtanen, Seppo and Jia, Yangqing and Klami, Arto and Darrell, Trevor}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {842--850}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/virtanen12a/virtanen12a.pdf}, url = {https://proceedings.mlr.press/r10/virtanen12a.html}, abstract = {Multi-modal data collections, such as corpora of paired images and text snippets, require analysis methods beyond single-view component and topic models. For continuous observations the current dominant approach is based on extensions of canonical correlation analysis, factorizing the variation into components shared by the different modalities and those private to each of them. For count data, multiple variants of topic models attempting to tie the modalities together have been presented. All of these, however, lack the ability to learn components private to one modality, and consequently will try to force dependencies even between minimally correlating modalities. In this work we combine the two approaches by presenting a novel HDP-based topic model that automatically learns both shared and private topics. The model is shown to be especially useful for querying the contents of one domain given samples of the other.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-wahabzada12a, title = {Latent {D}irichlet Allocation Uncovers Spectral Characteristics of Drought Stressed Plants}, author = {Wahabzada, Mirwaes and Kersting, Kristian and Bauckhage, Christian and Roemer, Christoph and Ballvora, Agim and Pinto, Francisco and Rascher, Uwe and Leon, Jens and Ploemer, Lutz}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {851--861}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/wahabzada12a/wahabzada12a.pdf}, url = {https://proceedings.mlr.press/r10/wahabzada12a.html}, abstract = {Understanding the adaptation process of plants to drought stress is essential in improving management practices, breeding strategies as well as engineering viable crops for a sustainable agriculture in the coming decades. Hyper-spectral imaging provides a particularly promising approach to gain such understanding since it allows to discover non-destructively spectral characteristics of plants governed primarily by scattering and absorption characteristics of the leaf internal structure and biochemical constituents. Several drought stress indices have been derived using hyper-spectral imaging. However, they are typically based on few hyper-spectral images only, rely on interpretations of experts, and consider few wavelengths only. In this study, we present the first data-driven approach to discovering spectral drought stress indices, treating it as an unsupervised labeling problem at massive scale. To make use of short range dependencies of spectral wavelengths, we develop an online variational Bayes algorithm for latent Dirichlet allocation with convolved Dirichlet regularizer. This approach scales to massive datasets and, hence, provides a more objective complement to plant physiological practices. The spectral topics found conform to plant physiological knowledge and can be computed in a fraction of the time compared to existing LDA approaches.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-walsh12a, title = {Dynamic Teaching in Sequential Decision Making Environments}, author = {Walsh, Thomas J. and Goschin, Sergiu}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {862--871}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/walsh12a/walsh12a.pdf}, url = {https://proceedings.mlr.press/r10/walsh12a.html}, abstract = {We describe theoretical bounds and a practical algorithm for teaching a model by demonstration in a sequential decision making environment. Unlike previous efforts that have optimized learners that watch a teacher demonstrate a static policy, we focus on the teacher as a decision maker who can dynamically choose different policies to teach different parts of the environment. We develop several teaching frameworks based on previously defined supervised protocols, such as Teaching Dimension, extending them to handle noise and sequences of inputs encountered in an MDP.We provide theoretical bounds on the learnability of several important model classes in this setting and suggest a practical algorithm for dynamic teaching.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-wang12a, title = {Fast Graph Construction Using Auction Algorithm}, author = {Wang, Jun and Xia, Yinglong}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {872--881}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/wang12a/wang12a.pdf}, url = {https://proceedings.mlr.press/r10/wang12a.html}, abstract = {In practical machine learning systems, graph based data representation has been widely used in various learning paradigms, ranging from unsupervised clustering to supervised classification. Besides those applications with natural graph or network structure data, such as social network analysis and relational learning, many other applications often involve a critical step in converting data vectors to an adjacency graph. In particular, a sparse subgraph extracted from the original graph is often required due to both theoretic and practical needs. Previous study clearly shows that the performance of different learning algorithms, e.g., clustering and classification, benefits from such sparse subgraphs with balanced node connectivity. However, the existing graph construction methods are either computationally expensive or with unsatisfactory performance. In this paper, we utilize a scalable method called auction algorithm and its parallel extension to recover a sparse yet nearly balanced subgraph with significantly reduced computational cost. Empirical study and comparison with the state-ofart approaches clearly demonstrate the superiority of the proposed method in both efficiency and accuracy.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-welling12a, title = {A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation}, author = {Welling, Max and Gelfand, Andrew E. and Ihler, Alexander T.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {882--891}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/welling12a/welling12a.pdf}, url = {https://proceedings.mlr.press/r10/welling12a.html}, abstract = {We introduce a new cluster-cumulant expansion (CCE) based on the fixed points of iterative belief propagation (IBP). This expansion is similar in spirit to the loop-series (LS) recently introduced in [1]. However, in contrast to the latter, the CCE enjoys the following important qualities: 1) it is defined for arbitrary state spaces 2) it is easily extended to fixed points of generalized belief propagation (GBP), 3) disconnected groups of variables will not contribute to the CCE and 4) the accuracy of the expansion empirically improves upon that of the LS. The CCE is based on the same M{ö}bius transform as the Kikuchi approximation, but unlike GBP does not require storing the beliefs of the GBP-clusters nor does it suffer from convergence issues during belief updating.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-wellman12a, title = {Self-Confirming Price Prediction Strategies for Simultaneous One-Shot Auctions}, author = {Wellman, Michael P. and Sodomka, Eric and Greenwald, Amy}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {892--901}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/wellman12a/wellman12a.pdf}, url = {https://proceedings.mlr.press/r10/wellman12a.html}, abstract = {Bidding in simultaneous auctions is challenging because an agent’s value for a good in one auction may depend on the uncertain outcome of other auctions: the so-called exposure problem. Given the gap in understanding of general simultaneous auction games, previous works have tackled this problem with heuristic strategies that employ probabilistic price predictions. We define a concept of self-confirming prices, and show that within an independent private value model, Bayes-Nash equilibrium can be fully characterized as a profile of optimal price prediction strategies with self-confirming predictions. We exhibit practical procedures to compute approximately optimal bids given a probabilistic price prediction, and near self-confirming price predictions given a price-prediction strategy. An extensive empirical game-theoretic analysis demonstrates that self-confirming price prediction strategies are effective in simultaneous auction games with both complementary and substitutable preference structures.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-weston12a, title = {Latent Structured Ranking}, author = {Weston, Jason and Blitzer, John}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {902--912}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/weston12a/weston12a.pdf}, url = {https://proceedings.mlr.press/r10/weston12a.html}, abstract = {Many latent (factorized) models have been proposed for recommendation tasks like collaborative filtering and for ranking tasks like document or image retrieval and annotation. Common to all those methods is that during inference the items are scored independently by their similarity to the query in the latent embedding space. The structure of the ranked list (i.e. considering the set of items returned as a whole) is not taken into account. This can be a problem because the set of top predictions can be either too diverse (contain results that contradict each other) or are not diverse enough. In this paper we introduce a method for learning latent structured rankings that improves over existing methods by providing the right blend of predictions at the top of the ranked list. Particular emphasis is put on making this method scalable. Empirical results on large scale image annotation and music recommendation tasks show improvements over existing approaches.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-wipf12a, title = {Non-Convex Rank Minimization via an Empirical {B}ayesian Approach}, author = {Wipf, David}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {913--922}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/wipf12a/wipf12a.pdf}, url = {https://proceedings.mlr.press/r10/wipf12a.html}, abstract = {In many applications that require matrix solutions of minimal rank, the underlying cost function is non-convex leading to an intractable, NP-hard optimization problem. Consequently, the convex nuclear norm is frequently used as a surrogate penalty term for matrix rank. The problem is that in many practical scenarios there is no longer any guarantee that we can correctly estimate generative low-rank matrices of interest, theoretical special cases notwithstanding. Consequently, this paper proposes an alternative empirical Bayesian procedure build upon a variational approximation that, unlike the nuclear norm, retains the same globally minimizing point estimate as the rank function under many useful constraints. However, locally minimizing solutions are largely smoothed away via marginalization, allowing the algorithm to succeed when standard convex relaxations completely fail. While the proposed methodology is generally applicable to a wide range of low-rank applications, we focus our attention on the robust principal component analysis problem (RPCA), which involves estimating an unknown low-rank matrix with unknown sparse corruptions. Theoretical and empirical evidence are presented to show that our method is potentially superior to related MAP-based approaches, for which the convex principle component pursuit (PCP) algorithm (Candes et al., 2011) can be viewed as a special case.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-yuan12a, title = {An Improved Admissible Heuristic for Learning Optimal {B}ayesian Networks}, author = {Yuan, Changhe and Malone, Brandon}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {923--932}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/yuan12a/yuan12a.pdf}, url = {https://proceedings.mlr.press/r10/yuan12a.html}, abstract = {Recently two search algorithms, A* and breadth-first branch and bound (BFBnB), were developed based on a simple admissible heuristic for learning Bayesian network structures that optimize a scoring function. The heuristic represents a relaxation of the learning problem such that each variable chooses optimal parents independently. As a result, the heuristic may contain many directed cycles and result in a loose bound. This paper introduces an improved admissible heuristic that tries to avoid directed cycles within small groups of variables. A sparse representation is also introduced to store only the unique optimal parent choices. Empirical results show that the new techniques significantly improved the efficiency and scalability of A* and BFBnB on most of datasets tested in this paper.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-zhang12a, title = {{FHHOP}: A Factored Hybrid Heuristic Online Planning Algorithm for Large POMDPs}, author = {Zhang, Zhongzhang and Chen, Xiaoping}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {933--942}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/zhang12a/zhang12a.pdf}, url = {https://proceedings.mlr.press/r10/zhang12a.html}, abstract = {Planning in partially observable Markov decision processes (POMDPs) remains a challenging topic in the artificial intelligence community, in spite of recent impressive progress in approximation techniques. Previous research has indicated that online planning approaches are promising in handling large-scale POMDP domains efficiently as they make decisions "on demand" instead of proactively for the entire state space. We present a Factored Hybrid Heuristic Online Planning (FHHOP) algorithm for large POMDPs. FHHOP gets its power by combining a novel hybrid heuristic search strategy with a recently developed factored state representation. On several benchmark problems, FHHOP substantially outperformed state-of-the-art online heuristic search approaches in terms of both scalability and quality.}, note = {Reissued by PMLR on 04 October 2026.} } @InProceedings{pmlr-vR10-zhang12b, title = {Guess Who Rated This Movie: Identifying Users Through Subspace Clustering}, author = {Zhang, Amy and Fawaz, Nadia and Ioannidis, Stratis and Montanari, Andrea}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {943--952}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/zhang12b/zhang12b.pdf}, url = {https://proceedings.mlr.press/r10/zhang12b.html}, abstract = {It is often the case that, within an online recommender system, multiple users share a common account. Can such shared accounts be identified solely on the basis of the userprovided ratings? Once a shared account is identified, can the different users sharing it be identified as well? Whenever such user identification is feasible, it opens the way to possible improvements in personalized recommendations, but also raises privacy concerns. We develop a model for composite accounts based on unions of linear subspaces, and use subspace clustering for carrying out the identification task. We show that a significant fraction of such accounts is identifiable in a reliable manner, and illustrate potential uses for personalized recommendation.}, note = {Reissued by PMLR on 04 October 2026.} }