- title: 'The 28th Uncertainty in Artificial Intelligence Conference: Preface' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/freitas12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/freitas12a/freitas12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-freitas12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 1-4 id: freitas12a issued: date-parts: - 2012 - 8 - 14 firstpage: 1 lastpage: 4 published: 2012-08-14 00:00:00 +0000 - title: 'The Do-Calculus Revisited' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/pearl12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/pearl12a/pearl12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-pearl12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Judea family: Pearl editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 5-12 id: pearl12a issued: date-parts: - 2012 - 8 - 14 firstpage: 5 lastpage: 12 published: 2012-08-14 00:00:00 +0000 - title: 'Learning to Rank With Bregman Divergences and Monotone Retargeting' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/acharyya12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/acharyya12a/acharyya12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-acharyya12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Sreangsu family: Acharyya - given: Oluwasanmi family: Koyejo - given: Joydeep family: Ghosh editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 13-22 id: acharyya12a issued: date-parts: - 2012 - 8 - 14 firstpage: 13 lastpage: 22 published: 2012-08-14 00:00:00 +0000 - title: 'Markov Determinantal Point Processes' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/affandi12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/affandi12a/affandi12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-affandi12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Raja Hafiz family: Affandi - given: Alex family: Kulesza - given: Emily B. family: Fox editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 23-32 id: affandi12a issued: date-parts: - 2012 - 8 - 14 firstpage: 23 lastpage: 32 published: 2012-08-14 00:00:00 +0000 - title: 'Toward Large-Scale Agent Guidance in an Urban Taxi Service' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/agussurja12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/agussurja12a/agussurja12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-agussurja12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Lucas family: Agussurja - given: Hoong Chuin family: Lau editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 33-40 id: agussurja12a issued: date-parts: - 2012 - 8 - 14 firstpage: 33 lastpage: 40 published: 2012-08-14 00:00:00 +0000 - title: 'Uncertain Congestion Games with Assorted Human Agent Populations' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/ahmed12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/ahmed12a/ahmed12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-ahmed12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Asrar family: Ahmed - given: Pradeep family: Varakantham - given: Shih-Fen family: Cheng editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 41-50 id: ahmed12a issued: date-parts: - 2012 - 8 - 14 firstpage: 41 lastpage: 50 published: 2012-08-14 00:00:00 +0000 - title: 'Budget Optimization for Sponsored Search: Censored Learning in MDPs' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/amin12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/amin12a/amin12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-amin12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Kareem family: Amin - given: Michael family: Kearns - given: Peter family: Key - given: Anton family: Schwaighofer editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 51-60 id: amin12a issued: date-parts: - 2012 - 8 - 14 firstpage: 51 lastpage: 60 published: 2012-08-14 00:00:00 +0000 - title: 'Variational Dual-Tree Framework for Large-Scale Transition Matrix Approximation' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/amizadeh12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/amizadeh12a/amizadeh12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-amizadeh12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Saeed family: Amizadeh - given: Bo family: Thiesson - given: Milos family: Hauskrecht editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 61-70 id: amizadeh12a issued: date-parts: - 2012 - 8 - 14 firstpage: 61 lastpage: 70 published: 2012-08-14 00:00:00 +0000 - title: 'Exploiting Uniform Assignments in First-Order MPE' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/apsel12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/apsel12a/apsel12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-apsel12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Udi family: Apsel - given: Ronen I. family: Brafman editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 71-80 id: apsel12a issued: date-parts: - 2012 - 8 - 14 firstpage: 71 lastpage: 80 published: 2012-08-14 00:00:00 +0000 - title: 'Plackett-Luce regression: A new Bayesian model for polychotomous data' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/archambeau12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/archambeau12a/archambeau12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-archambeau12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Cedric family: Archambeau - given: Francois family: Caron editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 81-89 id: archambeau12a issued: date-parts: - 2012 - 8 - 14 firstpage: 81 lastpage: 89 published: 2012-08-14 00:00:00 +0000 - title: 'Deterministic MDPs with Adversarial Rewards and Bandit Feedback' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/arora12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/arora12a/arora12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-arora12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Raman family: Arora - given: Ofer family: Dekel - given: Ambuj family: Tewari editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 90-99 id: arora12a issued: date-parts: - 2012 - 8 - 14 firstpage: 90 lastpage: 99 published: 2012-08-14 00:00:00 +0000 - title: 'Video In Sentences Out' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/barbu12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/barbu12a/barbu12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-barbu12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Andrei family: Barbu - given: Alexander family: Bridge - given: Zachary family: Burchill - given: Dan family: Coroian - given: Sven family: Dickinson - given: Sanja family: Fidler - given: Aaron family: Michaux - given: Sam family: Mussman - given: Siddharth family: Narayanaswamy - given: Dhaval family: Salvi - given: Lara family: Schmidt - given: Jiangnan family: Shangguan - given: Jeffrey Mark family: Siskind - given: Jarrell family: Waggoner - given: Song family: Wang - given: Jinlian family: Wei - given: Yifan family: Yin - given: Zhiqi family: Zhang editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 100-110 id: barbu12a issued: date-parts: - 2012 - 8 - 14 firstpage: 100 lastpage: 110 published: 2012-08-14 00:00:00 +0000 - title: 'Causal Inference by Surrogate Experiments: z-Identifiability' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/bareinboim12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/bareinboim12a/bareinboim12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-bareinboim12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Elias family: Bareinboim - given: Judea family: Pearl editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 111-118 id: bareinboim12a issued: date-parts: - 2012 - 8 - 14 firstpage: 111 lastpage: 118 published: 2012-08-14 00:00:00 +0000 - title: 'An Efficient Message-Passing Algorithm for the M-Best MAP Problem' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/batra12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/batra12a/batra12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-batra12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Dhruv family: Batra editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 119-128 id: batra12a issued: date-parts: - 2012 - 8 - 14 firstpage: 119 lastpage: 128 published: 2012-08-14 00:00:00 +0000 - title: 'Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/broeck12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/broeck12a/broeck12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-broeck12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Guy Van den family: Broeck - given: Arthur family: Choi - given: Adnan family: Darwiche editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 129-139 id: broeck12a issued: date-parts: - 2012 - 8 - 14 firstpage: 129 lastpage: 139 published: 2012-08-14 00:00:00 +0000 - title: 'Leveraging Side Observations in Stochastic Bandits' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/caron12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/caron12a/caron12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-caron12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Stephane family: Caron - given: Branislav family: Kveton - given: Marc family: Lelarge - given: Smriti family: Bhagat editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 140-149 id: caron12a issued: date-parts: - 2012 - 8 - 14 firstpage: 140 lastpage: 149 published: 2012-08-14 00:00:00 +0000 - title: 'Interdependent Defense Games: Modeling Interdependent Security under Deliberate Attacks' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/chan12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/chan12a/chan12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-chan12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Hau family: Chan - given: Michael family: Ceyko - given: Luis E. family: Ortiz editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 150-160 id: chan12a issued: date-parts: - 2012 - 8 - 14 firstpage: 150 lastpage: 160 published: 2012-08-14 00:00:00 +0000 - title: 'Decentralized Data Fusion and Active Sensing with Mobile Sensors for Modeling and Predicting Spatiotemporal Traffic Phenomena' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/chen12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/chen12a/chen12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-chen12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Jie family: Chen - given: Kian Hsiang family: Low - given: Colin Keng-Yan family: Tan - given: Ali family: Oran - given: Patrick family: Jaillet - given: John family: Dolan - given: Gaurav family: Sukhatme editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 161-171 id: chen12a issued: date-parts: - 2012 - 8 - 14 firstpage: 161 lastpage: 171 published: 2012-08-14 00:00:00 +0000 - title: 'Bayesian Structure Learning for Markov Random Fields with a Spike and Slab Prior' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/chen12b.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/chen12b/chen12b.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-chen12b.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Yutian family: Chen - given: Max family: Welling editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 172-182 id: chen12b issued: date-parts: - 2012 - 8 - 14 firstpage: 172 lastpage: 182 published: 2012-08-14 00:00:00 +0000 - title: 'Designing Informative Securities' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/chen12c.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/chen12c/chen12c.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-chen12c.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Yiling family: Chen - given: Mike family: Ruberry - given: Jennifer Wortman family: Vaughan editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 183-193 id: chen12c issued: date-parts: - 2012 - 8 - 14 firstpage: 183 lastpage: 193 published: 2012-08-14 00:00:00 +0000 - title: 'Lifted Relational Variational Inference' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/choi12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/choi12a/choi12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-choi12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Jaesik family: Choi - given: Eyal family: Amir editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 194-204 id: choi12a issued: date-parts: - 2012 - 8 - 14 firstpage: 194 lastpage: 204 published: 2012-08-14 00:00:00 +0000 - title: 'A Bayesian Approach to Constraint Based Causal Inference' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/claassen12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/claassen12a/claassen12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-claassen12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Tom family: Claassen - given: Tom family: Heskes editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 205-214 id: claassen12a issued: date-parts: - 2012 - 8 - 14 firstpage: 205 lastpage: 214 published: 2012-08-14 00:00:00 +0000 - title: 'Scaling Up Decentralized MDPs Through Heuristic Search' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/dibangoye12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/dibangoye12a/dibangoye12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-dibangoye12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Jilles S. family: Dibangoye - given: Christopher family: Amato - given: Arnoud family: Doniec editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 215-224 id: dibangoye12a issued: date-parts: - 2012 - 8 - 14 firstpage: 215 lastpage: 224 published: 2012-08-14 00:00:00 +0000 - title: 'Graph-Coupled HMMs for Modeling the Spread of Infection' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/dong12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/dong12a/dong12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-dong12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Wen family: Dong - given: Alex family: Pentland - given: Katherine A. family: Heller editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 225-234 id: dong12a issued: date-parts: - 2012 - 8 - 14 firstpage: 225 lastpage: 234 published: 2012-08-14 00:00:00 +0000 - title: 'DBN-Based Combinatorial Resampling for Articulated Object Tracking' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/dubuisson12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/dubuisson12a/dubuisson12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-dubuisson12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Severine family: Dubuisson - given: Christophe family: Gonzales - given: Xuan Son family: NGuyen editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 235-244 id: dubuisson12a issued: date-parts: - 2012 - 8 - 14 firstpage: 235 lastpage: 244 published: 2012-08-14 00:00:00 +0000 - title: 'Sample-efficient Nonstationary Policy Evaluation for Contextual Bandits' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/dudik12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/dudik12a/dudik12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-dudik12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Miroslav family: Dudik - given: Dumitru family: Erhan - given: John family: Langford - given: Lihong family: Li editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 245-252 id: dudik12a issued: date-parts: - 2012 - 8 - 14 firstpage: 245 lastpage: 252 published: 2012-08-14 00:00:00 +0000 - title: 'Uniform Solution Sampling Using a Constraint Solver As an Oracle' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/ermon12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/ermon12a/ermon12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-ermon12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Stefano family: Ermon - given: Carla P. family: Gomes - given: Bart family: Selman editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 253-262 id: ermon12a issued: date-parts: - 2012 - 8 - 14 firstpage: 253 lastpage: 262 published: 2012-08-14 00:00:00 +0000 - title: 'Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/freno12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/freno12a/freno12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-freno12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Antonino family: Freno - given: Mikaela family: Keller - given: Gemma C. family: Garriga - given: Marc family: Tommasi editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 263-272 id: freno12a issued: date-parts: - 2012 - 8 - 14 firstpage: 263 lastpage: 272 published: 2012-08-14 00:00:00 +0000 - title: 'Mechanism Design for Cost Optimal PAC Learning in the Presence of Strategic Noisy Annotators' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/garg12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/garg12a/garg12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-garg12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Dinesh family: Garg - given: Sourangshu family: Bhattacharya - given: S. family: Sundararajan - given: Shirish family: Shevade editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 273-283 id: garg12a issued: date-parts: - 2012 - 8 - 14 firstpage: 273 lastpage: 283 published: 2012-08-14 00:00:00 +0000 - title: 'Combining local search techniques and path following for bimatrix games' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/gatti12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/gatti12a/gatti12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-gatti12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Nicola family: Gatti - given: Giorgio family: Patrini - given: Marco family: Rocco - given: Tuomas family: Sandholm editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 284-293 id: gatti12a issued: date-parts: - 2012 - 8 - 14 firstpage: 284 lastpage: 293 published: 2012-08-14 00:00:00 +0000 - title: 'Generalized Belief Propagation on Tree Robust Structured Region Graphs' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/gelfand12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/gelfand12a/gelfand12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-gelfand12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Andrew E. family: Gelfand - given: Max family: Welling editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 294-303 id: gelfand12a issued: date-parts: - 2012 - 8 - 14 firstpage: 294 lastpage: 303 published: 2012-08-14 00:00:00 +0000 - title: 'Exploiting compositionality to explore a large space of model structures' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/grosse12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/grosse12a/grosse12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-grosse12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Roger family: Grosse - given: Ruslan R family: Salakhutdinov - given: William T. family: Freeman - given: Joshua B. family: Tenenbaum editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 304-313 id: grosse12a issued: date-parts: - 2012 - 8 - 14 firstpage: 304 lastpage: 313 published: 2012-08-14 00:00:00 +0000 - title: 'A Slice Sampler for Restricted Hierarchical Beta Process with Applications to Shared Subspace Learning' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/gupta12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/gupta12a/gupta12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-gupta12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Sunil Kumar family: Gupta - given: Dinh Q. family: Phung - given: Svetha family: Venkatesh editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 314-323 id: gupta12a issued: date-parts: - 2012 - 8 - 14 firstpage: 314 lastpage: 323 published: 2012-08-14 00:00:00 +0000 - title: 'Semantic Understanding of Professional Soccer Commentaries' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/hajishirzi12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/hajishirzi12a/hajishirzi12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-hajishirzi12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Hannaneh family: Hajishirzi - given: Mohammad family: Rastegari - given: Ali family: Farhadi - given: Jessica K. family: Hodgins editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 324-333 id: hajishirzi12a issued: date-parts: - 2012 - 8 - 14 firstpage: 324 lastpage: 333 published: 2012-08-14 00:00:00 +0000 - title: 'Weighted Sets of Probabilities and MinimaxWeighted Expected Regret: New Approaches for Representing Uncertainty and Making Decisions' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/halpern12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/halpern12a/halpern12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-halpern12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Joseph Y. family: Halpern - given: Samantha family: Leung editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 334-343 id: halpern12a issued: date-parts: - 2012 - 8 - 14 firstpage: 334 lastpage: 343 published: 2012-08-14 00:00:00 +0000 - title: 'Selecting Computations: Theory and Applications' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/hay12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/hay12a/hay12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-hay12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Nicholas family: Hay - given: Stuart family: Russell - given: David family: Tolpin - given: Solomon Eyal family: Shimony editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 344-353 id: hay12a issued: date-parts: - 2012 - 8 - 14 firstpage: 344 lastpage: 353 published: 2012-08-14 00:00:00 +0000 - title: 'Tightening Fractional Covering Upper Bounds on the Partition Function for High-Order Region Graphs' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/hazan12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/hazan12a/hazan12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-hazan12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Tamir family: Hazan - given: Jian family: Peng - given: Amnon family: Shashua editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 354-364 id: hazan12a issued: date-parts: - 2012 - 8 - 14 firstpage: 354 lastpage: 364 published: 2012-08-14 00:00:00 +0000 - title: 'Inferring Strategies from Limited Reconnaissance in Real-time Strategy Games' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/hostetler12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/hostetler12a/hostetler12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-hostetler12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Jesse family: Hostetler - given: Ethan W. family: Dereszynski - given: Thomas G. family: Dietterich - given: Alan family: Fern editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 365-374 id: hostetler12a issued: date-parts: - 2012 - 8 - 14 firstpage: 365 lastpage: 374 published: 2012-08-14 00:00:00 +0000 - title: 'Optimally-Weighted Herding is Bayesian Quadrature' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/huszar12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/huszar12a/huszar12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-huszar12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Ferenc family: Huszar - given: David family: Duvenaud editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 375-384 id: huszar12a issued: date-parts: - 2012 - 8 - 14 firstpage: 375 lastpage: 384 published: 2012-08-14 00:00:00 +0000 - title: 'Causal Discovery of Linear Cyclic Models from Multiple Experimental Data Sets with Overlapping Variables' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/hyttinen12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/hyttinen12a/hyttinen12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-hyttinen12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Antti family: Hyttinen - given: Frederick family: Eberhardt - given: Patrik O. family: Hoyer editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 385-394 id: hyttinen12a issued: date-parts: - 2012 - 8 - 14 firstpage: 385 lastpage: 394 published: 2012-08-14 00:00:00 +0000 - title: 'Join-graph based cost-shifting schemes' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/ihler12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/ihler12a/ihler12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-ihler12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Alexander T. family: Ihler - given: Natalia family: Flerova - given: Rina family: Dechter - given: Lars family: Otten editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 395-404 id: ihler12a issued: date-parts: - 2012 - 8 - 14 firstpage: 395 lastpage: 404 published: 2012-08-14 00:00:00 +0000 - title: 'Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/iyer12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/iyer12a/iyer12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-iyer12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Rishabh family: Iyer - given: Jeff A. family: Bilmes editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 405-415 id: iyer12a issued: date-parts: - 2012 - 8 - 14 firstpage: 405 lastpage: 415 published: 2012-08-14 00:00:00 +0000 - title: 'Incentive Decision Processes' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/reddi12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/reddi12a/reddi12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-reddi12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Sashank J. family: Reddi - given: Emma family: Brunskill editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 416-425 id: reddi12a issued: date-parts: - 2012 - 8 - 14 firstpage: 416 lastpage: 425 published: 2012-08-14 00:00:00 +0000 - title: 'Active Imitation Learning via Reduction to I.I.D. Active Learning' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/judah12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/judah12a/judah12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-judah12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Kshitij family: Judah - given: Alan family: Fern - given: Thomas G. family: Dietterich editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 426-435 id: judah12a issued: date-parts: - 2012 - 8 - 14 firstpage: 426 lastpage: 435 published: 2012-08-14 00:00:00 +0000 - title: 'A Theory of Goal-Oriented MDPs with Dead Ends' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/kolobov12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/kolobov12a/kolobov12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-kolobov12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Andrey family: Kolobov - given: family: Mausam - given: Daniel family: Weld editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 436-445 id: kolobov12a issued: date-parts: - 2012 - 8 - 14 firstpage: 436 lastpage: 445 published: 2012-08-14 00:00:00 +0000 - title: 'Dynamic Stochastic Orienteering Problems for Risk-Aware Applications' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/lau12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/lau12a/lau12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-lau12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Hoong Chuin family: Lau - given: William family: Yeoh - given: Pradeep family: Varakantham - given: Duc Thien family: Nguyen - given: Huaxing family: Chen editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 446-456 id: lau12a issued: date-parts: - 2012 - 8 - 14 firstpage: 446 lastpage: 456 published: 2012-08-14 00:00:00 +0000 - title: 'Computing Optimal Security Strategies for Interdependent Assets' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/letchford12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/letchford12a/letchford12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-letchford12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Joshua family: Letchford - given: Yevgeniy family: Vorobeychik editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 457-466 id: letchford12a issued: date-parts: - 2012 - 8 - 14 firstpage: 457 lastpage: 466 published: 2012-08-14 00:00:00 +0000 - title: 'Nested Dictionary Learning for Hierarchical Organization of Imagery and Text' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/li12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/li12a/li12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-li12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Lingbo family: Li - given: XianXing family: Zhang - given: Mingyuan family: Zhou - given: Lawrence family: Carin editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 467-476 id: li12a issued: date-parts: - 2012 - 8 - 14 firstpage: 467 lastpage: 476 published: 2012-08-14 00:00:00 +0000 - title: 'Learning Mixtures of Submodular Shells with Application to Document Summarization' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/lin12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/lin12a/lin12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-lin12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Hui family: Lin - given: Jeff A. family: Bilmes editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 477-488 id: lin12a issued: date-parts: - 2012 - 8 - 14 firstpage: 477 lastpage: 488 published: 2012-08-14 00:00:00 +0000 - title: 'Crowdsourcing Control: Moving Beyond Multiple Choice' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/lin12b.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/lin12b/lin12b.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-lin12b.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Christopher H. family: Lin - given: family: Mausam - given: Daniel family: Weld editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 489-498 id: lin12b issued: date-parts: - 2012 - 8 - 14 firstpage: 489 lastpage: 498 published: 2012-08-14 00:00:00 +0000 - title: 'Response Aware Model-Based Collaborative Filtering' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/ling12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/ling12a/ling12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-ling12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Guang family: Ling - given: Haiqin family: Yang - given: Michael R. family: Lyu - given: Irwin family: King editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 499-508 id: ling12a issued: date-parts: - 2012 - 8 - 14 firstpage: 499 lastpage: 508 published: 2012-08-14 00:00:00 +0000 - title: 'Graphical-model Based Multiple Testing under Dependence, with Applications to Genome-wide Association Studies' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/liu12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/liu12a/liu12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-liu12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Jie family: Liu - given: Chunming family: Zhang - given: Catherine family: McCarty - given: Peggy family: Peissig - given: Elizabeth family: Burnside - given: David family: Page editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 509-520 id: liu12a issued: date-parts: - 2012 - 8 - 14 firstpage: 509 lastpage: 520 published: 2012-08-14 00:00:00 +0000 - title: 'Belief Propagation for Structured Decision Making' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/liu12b.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/liu12b/liu12b.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-liu12b.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Qiang family: Liu - given: Alexander T. family: Ihler editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 521-530 id: liu12b issued: date-parts: - 2012 - 8 - 14 firstpage: 521 lastpage: 530 published: 2012-08-14 00:00:00 +0000 - title: 'Closed-Form Learning of Markov Networks from Dependency Networks' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/lowd12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/lowd12a/lowd12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-lowd12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Daniel family: Lowd editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 531-540 id: lowd12a issued: date-parts: - 2012 - 8 - 14 firstpage: 531 lastpage: 540 published: 2012-08-14 00:00:00 +0000 - title: 'Bayesian Vote Manipulation: Optimal Strategies and Impact on Welfare' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/lu12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/lu12a/lu12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-lu12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Tyler family: Lu - given: Pingzhong family: Tang - given: Ariel D. family: Procaccia - given: Craig family: Boutilier editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 541-551 id: lu12a issued: date-parts: - 2012 - 8 - 14 firstpage: 541 lastpage: 551 published: 2012-08-14 00:00:00 +0000 - title: 'Heuristic Ranking in Tightly Coupled Probabilistic Description Logics' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/lukasiewicz12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/lukasiewicz12a/lukasiewicz12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-lukasiewicz12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Thomas family: Lukasiewicz - given: Maria Vanina family: Martinez - given: Giorgio family: Orsi - given: Gerardo I. family: Simari editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 552-561 id: lukasiewicz12a issued: date-parts: - 2012 - 8 - 14 firstpage: 552 lastpage: 561 published: 2012-08-14 00:00:00 +0000 - title: 'Sparse Q-learning with Mirror Descent' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/mahadevan12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/mahadevan12a/mahadevan12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-mahadevan12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Sridhar family: Mahadevan - given: Bo family: Liu editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 562-571 id: mahadevan12a issued: date-parts: - 2012 - 8 - 14 firstpage: 562 lastpage: 571 published: 2012-08-14 00:00:00 +0000 - title: 'Multi-objective Influence Diagrams' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/marinescu12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/marinescu12a/marinescu12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-marinescu12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Radu family: Marinescu - given: Abdul family: Razak - given: Nic family: Wilson editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 572-581 id: marinescu12a issued: date-parts: - 2012 - 8 - 14 firstpage: 572 lastpage: 581 published: 2012-08-14 00:00:00 +0000 - title: 'Unsupervised Joint Alignment and Clustering using Bayesian Nonparametrics' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/mattar12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/mattar12a/mattar12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-mattar12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Marwan A. family: Mattar - given: Allen R. family: Hanson - given: Erik G. family: Learned-Miller editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 582-591 id: mattar12a issued: date-parts: - 2012 - 8 - 14 firstpage: 582 lastpage: 591 published: 2012-08-14 00:00:00 +0000 - title: 'Hokusai - Sketching Streams in Real Time' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/matusevych12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/matusevych12a/matusevych12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-matusevych12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Sergiy family: Matusevych - given: Alex family: Smola - given: Amr family: Ahmed editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 592-601 id: matusevych12a issued: date-parts: - 2012 - 8 - 14 firstpage: 592 lastpage: 601 published: 2012-08-14 00:00:00 +0000 - title: 'The Complexity of Approximately Solving Influence Diagrams' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/maua12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/maua12a/maua12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-maua12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Denis D. family: Maua - given: Cassio Polpo prefix: de family: Campos - given: Marco family: Zaffalon editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 602-611 id: maua12a issued: date-parts: - 2012 - 8 - 14 firstpage: 602 lastpage: 611 published: 2012-08-14 00:00:00 +0000 - title: 'Learning STRIPS Operators from Noisy and Incomplete Observations' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/mourao12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/mourao12a/mourao12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-mourao12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Kira family: Mourao - given: Luke S. family: Zettlemoyer - given: Ronald P. A. family: Petrick - given: Mark family: Steedman editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 612-621 id: mourao12a issued: date-parts: - 2012 - 8 - 14 firstpage: 612 lastpage: 621 published: 2012-08-14 00:00:00 +0000 - title: 'Markov Chains on Orbits of Permutation Groups' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/niepert12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/niepert12a/niepert12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-niepert12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Mathias family: Niepert editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 622-632 id: niepert12a issued: date-parts: - 2012 - 8 - 14 firstpage: 622 lastpage: 632 published: 2012-08-14 00:00:00 +0000 - title: 'Local Structure Discovery in Bayesian Networks' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/niinimaki12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/niinimaki12a/niinimaki12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-niinimaki12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Teppo family: Niinimaki - given: Pekka family: Parviainen editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 633-642 id: niinimaki12a issued: date-parts: - 2012 - 8 - 14 firstpage: 633 lastpage: 642 published: 2012-08-14 00:00:00 +0000 - title: 'Hilbert Space Embeddings of POMDPs' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/nishiyama12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/nishiyama12a/nishiyama12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-nishiyama12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Yu family: Nishiyama - given: Abdeslam family: Boularias - given: Arthur family: Gretton - given: Kenji family: Fukumizu editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 643-652 id: nishiyama12a issued: date-parts: - 2012 - 8 - 14 firstpage: 643 lastpage: 652 published: 2012-08-14 00:00:00 +0000 - title: 'Exploiting Structure in Cooperative Bayesian Games' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/oliehoek12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/oliehoek12a/oliehoek12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-oliehoek12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Frans A. family: Oliehoek - given: Shimon family: Whiteson - given: Matthijs T. J. family: Spaan editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 653-663 id: oliehoek12a issued: date-parts: - 2012 - 8 - 14 firstpage: 653 lastpage: 663 published: 2012-08-14 00:00:00 +0000 - title: 'A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/otten12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/otten12a/otten12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-otten12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Lars family: Otten - given: Rina family: Dechter editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 664-673 id: otten12a issued: date-parts: - 2012 - 8 - 14 firstpage: 664 lastpage: 673 published: 2012-08-14 00:00:00 +0000 - title: 'A Spectral Algorithm for Latent Junction Trees' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/parikh12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/parikh12a/parikh12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-parikh12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Ankur P. family: Parikh - given: Le family: Song - given: Mariya family: Ishteva - given: Gabi family: Teodoru - given: Eric P. family: Xing editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 674-683 id: parikh12a issued: date-parts: - 2012 - 8 - 14 firstpage: 674 lastpage: 683 published: 2012-08-14 00:00:00 +0000 - title: 'A Model-Based Approach to Rounding in Spectral Clustering' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/poon12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/poon12a/poon12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-poon12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Leonard K. M. family: Poon - given: April H. family: Liu - given: Tengfei family: Liu - given: Nevin Lianwen family: Zhang editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 684-693 id: poon12a issued: date-parts: - 2012 - 8 - 14 firstpage: 684 lastpage: 693 published: 2012-08-14 00:00:00 +0000 - title: 'A Maximum Likelihood Approach For Selecting Sets of Alternatives' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/procaccia12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/procaccia12a/procaccia12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-procaccia12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Ariel D. family: Procaccia - given: Sashank J. family: Reddi - given: Nisarg family: Shah editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 694-703 id: procaccia12a issued: date-parts: - 2012 - 8 - 14 firstpage: 694 lastpage: 703 published: 2012-08-14 00:00:00 +0000 - title: 'New Advances and Theoretical Insights into EDML' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/refaat12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/refaat12a/refaat12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-refaat12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Khaled S. family: Refaat - given: Arthur family: Choi - given: Adnan family: Darwiche editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 704-713 id: refaat12a issued: date-parts: - 2012 - 8 - 14 firstpage: 704 lastpage: 713 published: 2012-08-14 00:00:00 +0000 - title: 'Active Learning with Distributional Estimates' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/roeder12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/roeder12a/roeder12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-roeder12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Jens family: Roeder - given: Boaz family: Nadler - given: Kevin family: Kunzmann - given: Fred A. family: Hamprecht editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 714-724 id: roeder12a issued: date-parts: - 2012 - 8 - 14 firstpage: 714 lastpage: 724 published: 2012-08-14 00:00:00 +0000 - title: 'Integrated Nested Laplace Approximation for Bayesian Nonparametric Phylodynamics' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/palacios12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/palacios12a/palacios12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-palacios12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Julia A. family: Palacios - given: Vladimir N. family: Minin editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 725-734 id: palacios12a issued: date-parts: - 2012 - 8 - 14 firstpage: 725 lastpage: 734 published: 2012-08-14 00:00:00 +0000 - title: 'From imprecise probability assessments to conditional probabilities with quasi additive classes of conditioning events' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/sanfilippo12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/sanfilippo12a/sanfilippo12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-sanfilippo12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Giuseppe family: Sanfilippo editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 735-744 id: sanfilippo12a issued: date-parts: - 2012 - 8 - 14 firstpage: 735 lastpage: 744 published: 2012-08-14 00:00:00 +0000 - title: 'Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/savchynskyy12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/savchynskyy12a/savchynskyy12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-savchynskyy12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Bogdan family: Savchynskyy - given: Stefan family: Schmidt - given: Joerg family: Kappes - given: Christoph family: Schnoerr editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 745-754 id: savchynskyy12a issued: date-parts: - 2012 - 8 - 14 firstpage: 745 lastpage: 754 published: 2012-08-14 00:00:00 +0000 - title: 'Predicting the behavior of interacting humans by fusing data from multiple sources' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/schlicht12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/schlicht12a/schlicht12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-schlicht12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Erik J. family: Schlicht - given: Ritchie family: Lee - given: David H. family: Wolpert - given: Mykel J. family: Kochenderfer - given: Brendan family: Tracey editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 755-763 id: schlicht12a issued: date-parts: - 2012 - 8 - 14 firstpage: 755 lastpage: 763 published: 2012-08-14 00:00:00 +0000 - title: 'Latent Composite Likelihood Learning for the Structured Canonical Correlation Model' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/silva12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/silva12a/silva12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-silva12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Ricardo family: Silva editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 764-773 id: silva12a issued: date-parts: - 2012 - 8 - 14 firstpage: 764 lastpage: 773 published: 2012-08-14 00:00:00 +0000 - title: 'Spectrum Identification using a Dynamic Bayesian Network Model of Tandem Mass Spectra' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/singh12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/singh12a/singh12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-singh12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Ajit P. family: Singh - given: John family: Halloran - given: Jeff A. family: Bilmes - given: Katrin family: Kirchoff - given: William S. family: Noble editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 774-784 id: singh12a issued: date-parts: - 2012 - 8 - 14 firstpage: 774 lastpage: 784 published: 2012-08-14 00:00:00 +0000 - title: 'Detecting Change-Points in Time Series by Maximum Mean Discrepancy of Ordinal Pattern Distributions' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/sinn12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/sinn12a/sinn12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-sinn12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Mathieu family: Sinn - given: Ali family: Ghodsi - given: Karsten family: Keller editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 785-793 id: sinn12a issued: date-parts: - 2012 - 8 - 14 firstpage: 785 lastpage: 793 published: 2012-08-14 00:00:00 +0000 - title: 'Efficiently Searching for Frustrated Cycles in MAP Inference' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/sontag12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/sontag12a/sontag12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-sontag12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: David family: Sontag - given: Do Kook family: Choe - given: Yitao family: Li editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 794-803 id: sontag12a issued: date-parts: - 2012 - 8 - 14 firstpage: 794 lastpage: 803 published: 2012-08-14 00:00:00 +0000 - title: 'An Approximate Solution Method for Large Risk-Averse Markov Decision Processes' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/petrik12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/petrik12a/petrik12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-petrik12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Marek family: Petrik - given: Dharmashankar family: Subramanian editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 804-813 id: petrik12a issued: date-parts: - 2012 - 8 - 14 firstpage: 804 lastpage: 813 published: 2012-08-14 00:00:00 +0000 - title: 'Probability and Asset Updating using Bayesian Networks for Combinatorial Prediction Markets' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/sun12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/sun12a/sun12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-sun12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Wei family: Sun - given: Robin family: Hanson - given: Kathryn Blackmond family: Laskey - given: Charles family: Twardy editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 814-823 id: sun12a issued: date-parts: - 2012 - 8 - 14 firstpage: 814 lastpage: 823 published: 2012-08-14 00:00:00 +0000 - title: 'Fast Exact Inference for Recursive Cardinality Models' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/tarlow12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/tarlow12a/tarlow12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-tarlow12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Daniel family: Tarlow - given: Kevin family: Swersky - given: Richard S. family: Zemel - given: Ryan Prescott family: Adams - given: Brendan J. family: Frey editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 824-833 id: tarlow12a issued: date-parts: - 2012 - 8 - 14 firstpage: 824 lastpage: 833 published: 2012-08-14 00:00:00 +0000 - title: 'Value Function Approximation in Noisy Environments Using Locally Smoothed Regularized Approximate Linear Programs' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/taylor12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/taylor12a/taylor12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-taylor12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Gavin family: Taylor - given: Ron family: Parr editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 834-841 id: taylor12a issued: date-parts: - 2012 - 8 - 14 firstpage: 834 lastpage: 841 published: 2012-08-14 00:00:00 +0000 - title: 'Factorized Multi-Modal Topic Model' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/virtanen12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/virtanen12a/virtanen12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-virtanen12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Seppo family: Virtanen - given: Yangqing family: Jia - given: Arto family: Klami - given: Trevor family: Darrell editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 842-850 id: virtanen12a issued: date-parts: - 2012 - 8 - 14 firstpage: 842 lastpage: 850 published: 2012-08-14 00:00:00 +0000 - title: 'Latent Dirichlet Allocation Uncovers Spectral Characteristics of Drought Stressed Plants' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/wahabzada12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/wahabzada12a/wahabzada12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-wahabzada12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Mirwaes family: Wahabzada - given: Kristian family: Kersting - given: Christian family: Bauckhage - given: Christoph family: Roemer - given: Agim family: Ballvora - given: Francisco family: Pinto - given: Uwe family: Rascher - given: Jens family: Leon - given: Lutz family: Ploemer editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 851-861 id: wahabzada12a issued: date-parts: - 2012 - 8 - 14 firstpage: 851 lastpage: 861 published: 2012-08-14 00:00:00 +0000 - title: 'Dynamic Teaching in Sequential Decision Making Environments' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/walsh12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/walsh12a/walsh12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-walsh12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Thomas J. family: Walsh - given: Sergiu family: Goschin editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 862-871 id: walsh12a issued: date-parts: - 2012 - 8 - 14 firstpage: 862 lastpage: 871 published: 2012-08-14 00:00:00 +0000 - title: 'Fast Graph Construction Using Auction Algorithm' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/wang12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/wang12a/wang12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-wang12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Jun family: Wang - given: Yinglong family: Xia editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 872-881 id: wang12a issued: date-parts: - 2012 - 8 - 14 firstpage: 872 lastpage: 881 published: 2012-08-14 00:00:00 +0000 - title: 'A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/welling12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/welling12a/welling12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-welling12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Max family: Welling - given: Andrew E. family: Gelfand - given: Alexander T. family: Ihler editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 882-891 id: welling12a issued: date-parts: - 2012 - 8 - 14 firstpage: 882 lastpage: 891 published: 2012-08-14 00:00:00 +0000 - title: 'Self-Confirming Price Prediction Strategies for Simultaneous One-Shot Auctions' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/wellman12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/wellman12a/wellman12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-wellman12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Michael P. family: Wellman - given: Eric family: Sodomka - given: Amy family: Greenwald editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 892-901 id: wellman12a issued: date-parts: - 2012 - 8 - 14 firstpage: 892 lastpage: 901 published: 2012-08-14 00:00:00 +0000 - title: 'Latent Structured Ranking' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/weston12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/weston12a/weston12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-weston12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Jason family: Weston - given: John family: Blitzer editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 902-912 id: weston12a issued: date-parts: - 2012 - 8 - 14 firstpage: 902 lastpage: 912 published: 2012-08-14 00:00:00 +0000 - title: 'Non-Convex Rank Minimization via an Empirical Bayesian Approach' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/wipf12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/wipf12a/wipf12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-wipf12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: David family: Wipf editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 913-922 id: wipf12a issued: date-parts: - 2012 - 8 - 14 firstpage: 913 lastpage: 922 published: 2012-08-14 00:00:00 +0000 - title: 'An Improved Admissible Heuristic for Learning Optimal Bayesian Networks' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/yuan12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/yuan12a/yuan12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-yuan12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Changhe family: Yuan - given: Brandon family: Malone editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 923-932 id: yuan12a issued: date-parts: - 2012 - 8 - 14 firstpage: 923 lastpage: 932 published: 2012-08-14 00:00:00 +0000 - title: 'FHHOP: A Factored Hybrid Heuristic Online Planning Algorithm for Large POMDPs' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/zhang12a.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/zhang12a/zhang12a.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-zhang12a.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Zhongzhang family: Zhang - given: Xiaoping family: Chen editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 933-942 id: zhang12a issued: date-parts: - 2012 - 8 - 14 firstpage: 933 lastpage: 942 published: 2012-08-14 00:00:00 +0000 - title: 'Guess Who Rated This Movie: Identifying Users Through Subspace Clustering' 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.' volume: R10 URL: https://proceedings.mlr.press/r10/zhang12b.html PDF: https://raw.githubusercontent.com/mlresearch/r10/main/assets/zhang12b/zhang12b.pdf edit: https://github.com/mlresearch//r10/edit/gh-pages/_posts/2012-08-14-zhang12b.md series: 'Proceedings of Machine Learning Research' container-title: 'Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence' publisher: 'PMLR' author: - given: Amy family: Zhang - given: Nadia family: Fawaz - given: Stratis family: Ioannidis - given: Andrea family: Montanari editor: - given: Nando prefix: de family: Freitas - given: Kevin family: Murphy page: 943-952 id: zhang12b issued: date-parts: - 2012 - 8 - 14 firstpage: 943 lastpage: 952 published: 2012-08-14 00:00:00 +0000