text:
@inproceedings{10.5555/2073876.2073877,
author = {Ali, R. Ayesha and Richardson, Thomas S.},
title = {Markov Equivalence Classes for Maximal Ancestral Graphs},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Ancestral graphs provide a class of graphs that can encode conditional independence relations that arise in directed acyclic graph (DAG) models with latent and selection variables, corresponding to marginalization and conditioning. However, for any ancestral graph, there may be several other graphs to which it is Markov equivalent. We introduce a simple representation of a Markov equivalence class of ancestral graphs, thereby facilitating the model search process for some given data. More specifically, we define a join operation on ancestral graphs which will associate a unique graph with an equivalence class. We also extend the separation criterion for ancestral graphs (which is an extension of d-separation) and provide a proof of the pairwise Markov property for joined ancestral graphs. Proving the pairwise Markov property is the first step towards developing a global Markov property for these graphs. The ultimate goal of this work is to obtain a full characterization of the structure of Markov equivalence classes for maximal ancestral graphs, thereby extending analogous results for DAGs given by Frydenberg (1990), Verma and Pearl (1991), Chickering (1995) and Andersson et al. (1997).},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {1–9},
numpages = {9},
keywords = {maximal ancestral graphs, DAG models, joined graphs, latent and selection variables, Markov equivalence},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073878,
author = {Anguelov, Dragomir and Biswas, Rahul and Koller, Daphne and Limketkai, Benson and Thrun, Sebastian},
title = {Learning Hierarchical Object Maps of Non-Stationary Environments with Mobile Robots},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Building models, or maps, of robot environments is a highly active research area; however, most existing techniques construct unstructured maps and assume static environments. In this paper, we present an algorithm for learning object models of non-stationary objects found in office-type environments. Our algorithm exploits the fact that many objects found in office environments look alike (e.g., chairs, recycling bins). It does so through a two-level hierarchical representation, which links individual objects with generic shape templates of object classes. We derive an approximate EM algorithm for learning shape pararneters at both levels of the hierarchy, using local occupancy grid maps for representing shape. Additionally, we develop a Bayesian model selection algorithm that enables the robot to estimate the total number of objects and object templates in the environment. Experimental results using a real robot equipped with a laser range finder indicate that our approach performs well at learning object-based maps of simple office environments. The approach outperforms a previously developed non-hierarchical algorithm that models objects jects but lacks class templates.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {10–17},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073879,
author = {Aron, Ionut and Van Hentenryck, Pascal},
title = {A Constraint Satisfaction Approach to the Robust Spanning Tree Problem with Interval Data},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Robust optimization is one of the fundamental approaches to deal with uncertainty in combinatorial optimization. This paper considers the robust spanning tree problem with interval data, which arises in a variety of telecommunication applications. It proposes a constraint satisfaction approach using a combinatorial lower bound, a pruning component that removes infeasible and suboptimal edges, as well as a search strategy exploring the most uncertain edges first. The resulting algorithm is shown to produce very dramatic improvements over the mathematical programming approach of Yaman et al. and to enlarge considerably the class of problems amenable to effective solutions.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {18–25},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073880,
author = {Auvray, Vincent and Wehenkel, Louis},
title = {On the Construction of the Inclusion Boundary Neighbourhood for Markov Equivalence Classes of Bayesian Network Structures},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {The problem of learning Markov equivalence classes of Bayesian network structures may be solved by searching for the maximum of a scoring metric in a space of these classes. This paper deals with the definition and analysis of one such search space. We use a theoretically motivated neighbourhood, the inclusion boundary, and represent equivalence classes by essential graphs. We show that this search space is connected and that the score of the neighbours can be evaluated incrementally. We devise a practical way of building this neighbourhood for an essential graph that is purely graphical and does not explicitely refer to the underlying independences. We find that its size can be intractable, depending on the complexity of the essential graph of the equivalence class. The emphasis is put on the potential use of this space with greedy hillclimbing search.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {26–35},
numpages = {10},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073881,
author = {Bach, Francis R. and Jordan, Michael I.},
title = {Tree-Dependent Component Analysis},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We present a generalization of independent component analysis (ICA), where instead of looking for a linear transform that makes the data components independent, we look for a transform that makes the data components well fit by a tree-structured graphical model. Treating the problem as a semiparametric statistical problem, we show that the optimal transform is found by minimizing a contrast function based on mutual information, a function that directly extends the contrast function used for classical ICA. We provide two approximations of this contrast function, one using kernel density estimation, and another using kernel generalized variance. This tree-dependent component analysis framework leads naturally to an efficient general multivariate density estimation technique where only bivariate density estimation needs to be performed.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {36–44},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073882,
author = {Benferhat, Salem and Dubois, Didier and Kaci, Souhila and Prade, Henri},
title = {Bipolar Possibilistic Representations},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Recently, it has been emphasized that the possibility theory framework allows us to distinguish between i) what is possible because it is not ruled out by the available knowledge, and ii) what is possible for sure. This distinction may be useful when representing knowledge, for modelling values which are not impossible because they are consistent with the available knowledge on the one hand, and values guaranteed to be possible because reported from observations on the other hand. It is also of interest when expressing preferences, to point out values which are positively desired among those which are not rejected. This distinction can be encoded by two types of constraints expressed in terms of necessity measures and in terms of guaranteed possibility functions, which induce a pair of possibility distributions at the semantic level. A consistency condition should ensure that what is claimed to be guaranteed as possible is indeed not impossible. The present paper investigates the representation of this bipolar view, including the case when it is stated by means of conditional measures, or by means of comparative context-dependent constraints. The interest of this bipolar framework, which has been recently stressed for expressing preferences, is also pointed out in the representation of diagnostic knowledge.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {45},
numpages = {1},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073883,
author = {Blei, David M. and Bagnell, J. Andrew and McCallum, Andrew K.},
title = {Learning with Scope, with Application to Information Extraction and Classification},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In probabilistic approaches to classification and information extraction, one typically builds a statistical model of words under the assumption that future data will exhibit the same regularities as the training data. In many data sets, however, there are scopelimited features whose predictive power is only applicable to a certain subset of the data. For example, in information extraction from web pages, word formatting may be indicative of extraction category in different ways on different web pages. The difficulty with using such features is capturing and exploiting the new regularities encountered in previously unseen data. In this paper, we propose a hierarchical probabilistic model that uses both local/scope-limited features, such as word formatting, and global features, such as word content. The local regularities are modeled as an unobserved random parameter which is drawn once for each local data set. This random parameter is estimated during the inference process and then used to perform classification with both the local and global features- a procedure which is akin to automatically retuning the classifier to the local regularities on each newly encountered web page. Exact inference is intractable and we present approximations via point estimates and variational methods. Empirical results on large collections of web data demonstrate that this method significantly improves performance from traditional models of global features alone.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {53–60},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073884,
author = {Bonet, Blai and Pearl, Judea},
title = {Qualitative MDPs and POMDPs: An Order-of-Magnitude Approximation},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We develop a qualitative theory of Markov Decision Processes (MDPS) and Partially Observable MDPS that can be used to model sequential decision making tasks when only qualitative information is available. Our approach is based upon an order-of-magnitude approximation of both probabilities and utilities, similar to ε-semantics. The result is a qualitative theory that has close ties with the standard maximum-expected-utility theory and is amenable to general planning techniques.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {61–68},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073885,
author = {Brafman, Ronen I. and Domshlak, Carmel},
title = {Introducing Variable Importance Tradeoffs into CP-Nets},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {The ability to make decisions and to assess potential courses of action is a comer-stone of many AI applications, and usually this requires explicit information about the decision-maker's preferences. In many applications, preference elicitation is a serious bottleneck. The user either does not have the time, the knowledge, or the expert support required to specify complex multi-attribute utility functions. In such cases, a method that is based on intuitive, yet expressive, preference statements is required. In this paper we suggest the use of TCP-nets, an enhancement of CP-nets, as a tool for representing, and reasoning about qualitative preference statements. We present and motivate this framework, define its semantics, and show how it can be used to perform constrained optimization.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {69–76},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073886,
author = {Bresina, John and Dearden, Richard and Meuleau, Nicolas and Ramakrishnan, Sailesh and Smith, David and washington, Rich},
title = {Planning under Continuous Time and Resource Uncertainty: A Challenge for AI},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We outline a class of problems, typical of Mars rover operations, that are problematic for current methods of planning under uncertainty. The existing methods fail because they suffer from one or more of the following limitations: 1) they rely on very simple models of actions and time, 2) they assume that uncertainty is manifested in discrete action outcomes, 3) they are only practical for very small problems. For many real world oroblems, these assumptions fail to hold. In particular, when planning the activities for a Mars rover, none of the above assumptions is valid: 1) actions can be concurrent and have differing durations, 2) there is uncertainty concerning action durations and consumption of continuous resources like power, and 3) typical daily plans involve on the order of a hundred actions. This class of problems may be of particular interest to the UAI community because both classical and decision-theoretic planning techniques may be useful in solving it. We describe the rover problem, discuss previous work on planning under uncertainty, and present a detailed, but very small, example illustrating some of the difficulties of finding good plans.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {77–84},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073887,
author = {Brito, Carlos and Pearl, Judea},
title = {Generalized Instrumental Variables},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {This paper concerns the assessment of direct causal effects from a combination of: (i) nonexperimental data, and (ii) qualitative domain knowledge. Domain knowledge is encoded in the form of a directed acyclic graph (DAG), in which all interactions are assumed linear, and some variables are presumed to be unobserved. We provide a generalization of the well-known method of Instrumental Variables, which allows its application to models with few conditional independeces.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {85–93},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073888,
author = {Chickering, David Maxwell and Meek, Christopher},
title = {Finding Optimal Bayesian Networks},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In this paper, we derive optimality results for greedy Bayesian-network search algorithms that perform single-edge modifications at each step and use asymptotically consistent scoring criteria. Our results extend those of Meek (1997) and Chickering (2002), who demonstrate that in the limit of large datasets, if the generative distribution is perfect with respect to a DAG defined over the observable variables, such search algorithms will identify this optimal (i.e. generative) DAG model. We relax their assumption about the generative distribution, and assume only that this distribution satisfies the composition property over the observable variables, which is a more realistic assumption for real domains. Under this assumption, we guarantee that the search algorithms identify an inclusion-optimal model; that is, a model that (1) contains the generative distribution and (2) has no sub-model that contains this distribution. In addition, we show that the composition property is guaranteed to hold whenever the dependence relationships in the generative distribution can be characterized by paths between singleton elements in some generative graphical model (e.g. a DAG, a chain graph, or a Markov network) even when the generative model includes unobserved variables, and even when the observed data is subject to selection bias.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {94–102},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073889,
author = {Conitzer, Vincent and Sandholm, Tuomas},
title = {Complexity of Mechanism Design},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {The aggregation of conflicting preferences is a central problem in multiagent systems. The key difficulty is that the agents may report their preferences insincerely. Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully and a (socially) desirable outcome is chosen. We propose an approach where a mechanism is automatically created for the preference aggregation setting at hand. This has several advantages, but the downside is that the mechanism design optimization problem needs to be solved anew each time. Focusing-on settings where side payments are not possible, we show that the mechanism design problem is NP-complete for deterministic mechanisms. This holds both for dominantstrategy implementation and for Bayes-Nash implementation. We then show that if we allow randomized mechanisms, the mechanism design problem becomes tractable. In other words, the coordinator can tackle the computational complexity introduced by its uncertainty the agents face additional uncertainty. This comes at no loss, and in some cases at a gain, in the (social) objective.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {103–110},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073890,
author = {Corduneanu, Adrian and Jaakkola, Tommi},
title = {Continuation Methods for Mixing Heterogeneous Sources},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {A number of modern learning tasks involve estimation from heterogeneous information sources. This includes classification with labeled and unlabeled data as well as other problems with analogous structure such as competitive (game theoretic) problems. The associated estimation problems can be typically reduced to solving a set of fixed point equations (consistency conditions). We introduce a general method for combining a preferred information source with another in this setting by evolving continuous paths of fixed points at intermediate allocations. We explicitly identify critical points along the unique paths to either increase the stability of estimation or to ensure a significant departure from the initial source. The homotopy continuation approach is guaranteed to terminate at the second source, and involves no combinatorial effort. We illustrate the power of these ideas both in classification tasks with labeled and unlabeled data, as well as in the context of a competitive (min-max) formulation of DNA sequence motif discovery.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {111–118},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073891,
author = {Davies, Scott and Moore, Andrew},
title = {Interpolating Conditional Density Trees},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Joint distributions over many variables are frequently modeled by decomposing them into products of simpler, lower-dimensional conditional distributions, such as in sparsely connected Bayesian networks. However, automatically learning such models can be very computationally expensive when there are many datapoints and many continuous variables with complex nonlinear relationships, particularly when no good ways of decomposing the joint distribution are known a priori. In such situations, previous research has generally focused on the use of discretization techniques in which each continuous variable has a single discretization that is used throughout the entire network.In this paper, we present and compare a wide variety of tree-based algorithms for learning and evaluating conditional density estimates over continuous variables. These trees can be thought of as discretizations that vary according to the particular interactions being modeled; however, the density within a given leaf of the tree need not be assumed constant, and we show that such nonuniform leaf densities lead to more accurate density estimation. We have developed Bayesian network structure-learning algorithms that employ these tree-based conditional density representations. and we show that they can be used to practically learn complex joint prob ability models over dozens of continuous variables from thousands of datapoints. We focus on finding models that are simultaneously accurate, fast to learn, and fast to evaluate once they are learned.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {119–127},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073892,
author = {Dechter, Rina and Kask, Kalev and Mateescu, Robert},
title = {Iterative Join-Graph Propagation},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {The paper presents an iterative version of join-tree clustering that applies the message passing of join-tree clustering algorithm to join-graphs rather than to join-trees, iteratively. It is inspired by the success of Pearl's belief propagation algorithm (BP) as an iterative approximation scheme on one hand, and by a recently introduced mini-clustering (MC(i)) success as an anytime approximation method, on the other. The proposed Iterative Join-graph Propagation (IJGP) belongs to the class of generalized belief propagation methods, recently proposed using analogy with algorithms in statistical physics. Empirical evaluation of this approach on a number of problem classes demonstrates that even the most time-efficient variant is almost always superior to IBP and MC(i), and is sometimes more accurate by as much as several orders of magnitude.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {128–136},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073893,
author = {Dom, Byron E.},
title = {An Information-Theoretic External Cluster-Validity Measure},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In this paper we propose a measure of similarity/ association between two partitions of a set of objects. Our motivation is the desire to use the measure to characterize the quality or accuracy of clustering algorithms by somehow comparing the clusters they produce with "ground truth" consisting of classes assigned by manual means or some other means in whose veracity there is confidence. Such measures are referred to as "external". Our measure also allows clusterings with different numbers of clusters to be compared in a quantitative and principled way. Our evaluation scheme quantitatively measures how useful the cluster labels are as predictors of their class labels. It computes the reduction in the number of bits that would be required to encode (comress) the class labels if both the encoder and decoder have free access to the cluster labels. To achieve this encoding the estimated conditional probabilities of the class labels given the cluster labels must also be encoded. In addition to defining the measure we compare it to other commonly used external measures and demonstrate its superiority as judged by certain criteria.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {137–145},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073894,
author = {Eiter, Thomas and Lukasiewicz, Thomas},
title = {Causes and Explanations in the Structural-Model Approach},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In this paper, we continue our research on the algorithmic aspects of Halpern and Pearl's causes and explanations in the structural-model approach. To this end, we present new characterizations of weak causes for certain classes of causal models, which show that under suitable restrictions deciding causes and explanations is tractable. To our knowledge, these are the first explicit tractability results for the structural model approach.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {146–153},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073895,
author = {Finney, Sarah and Gardiol, Natalia H. and Kaelbling, Leslie Pack and Oates, Tim},
title = {The Thing That We Tried Didn't Work Very Well: Deictic Representation in Reinforcement Learning},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Most reinforcement learning methods operate on propositional representations of the world state. Such representations are often intractably large and generalize poorly. Using a deictic representation is believed to be a viable alternative: they promise generalization while allowing the use of existing reinforcement-learning methods. Yet, there are few experiments on learning with deictic representations reported in the literature. In this paper we explore the effectiveness of two forms of deictic representation and a na\"{\i}ve propositional representation in a simple blocks-world domain. We find, empirically, that the deictic representations actually worsen learning performance. We conclude with a discussion of possible causes of these results and strategies for more effective learning in domains with objects.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {154–161},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073896,
author = {Geiger, Dan and Meek, Christopher and Sturmfels, Bernd},
title = {Factorization of Discrete Probability Distributions},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We formulate necessary and sufficient conditions for an arbitrary discrete probability distribution to factor according to an undirected graphical model, or a log-linear model, or other more general exponential models. This result generalizes the well known Hammersley-Clifford Theorem.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {162–169},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073897,
author = {Giang, Phan H. and Shenoy, Prakash P.},
title = {Statistical Decisions Using Likelihood Information without Prior Probabilities},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {This paper presents a decision-theoretic approach to statistical inference that satisfies the Likelihood Principle (LP) without using prior information. Unlike the Bayesian approach, which also satisfies LP, we do not assume knowledge of the prior distribution of the unknown parameter. With respect to information that can be obtained from an experiment, our solution is more efficient than Wald's minimax solution. However, with respect to information assumed to be known before the experiment, our solution demands less input than the Bayesian solution.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {170–178},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073898,
author = {Goodman, Joshua},
title = {Reduction of Maximum Entropy Models to Hidden Markov Models},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We show that maximum entropy (maxent) models can be modeled with certain kinds of HMMs, allowing us to construct maxent models with hidden variables, hidden state sequences, or other characteristics. The models can be trained using the forward-backward algorithm. While the results are primarily of theoretical interest, unifying apparently unrelated concepts, we also give experimental results for a maxent model with a hidden variable on a word disambiguation task; the model outperforms standard techniques.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {179–186},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073899,
author = {Gr\"{u}nwald, Peter D. and Halpern, Joseph Y.},
title = {Updating Probabilities},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a "naive space", which does not take into account the protocol used, can often lead to counterintuitive results. Here we examine why. A criterion known as CAR ("coarsening at random") in the statistical literature characterizes when "naive" conditioning in a naive space works. We show that the CAR condition holds rather infrequently. We then consider more generalized notions of update such as Jeffrey conditioning and minimizing relative entropy (MRE). We give a generalization of the CAR condition that characterizes when Jeffrey conditioning leads to appropriate answers, but show that there are no such conditions for MRE. This generalizes and interconnects previous results obtained in the literature on CAR and MRE.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {187–196},
numpages = {10},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073900,
author = {Guestrin, Carlos and Gordon, Geoffrey},
title = {Distributed Planning in Hierarchical Factored MDPs},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We present a principled and efficient planning algorithm for collaborative multiagent dynamical systems. All computation, during both the planning and the execution phases, is distributed among the agents; each agent only needs to model and plan for a small part of the system. Each of these local subsystems is small, but once they are combined they can represent an exponentially larger problem. The subsystems are connected through a subsystem hierarchy. Coordination and communication between the agents is not imposed, but derived directly from the structure of this hierarchy. A globally consistent plan is achieved by a message passing algorithm, where messages correspond to natural local reward functions and are computed by local linear programs; another message passing algorithm allows us to execute the resulting policy. When two portions of the hierarchy share the same structure, our algorithm can reuse plans and messages to speed up computation.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {197–206},
numpages = {10},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073901,
author = {Halpern, Joseph Y. and Pucella, Riccardo},
title = {Reasoning about Expectation},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Expectation is a central notion in probability theory. The notion of expectation also makes sense for other notions of uncertainty. We introduce a propositional logic for reasoning about expectation, where the semantics depends on the underlying representation of uncertainty. We give sound and complete axiomatizations for the logic in the case that the underlying representation is (a) probability, (b) sets of probability measures, (c) belief functions, and (d) possibility measures. We show that this logic is more expressive than the corresponding logic for reasoning about likelihood in the case of sets of probability measures, but equi-expressive in the case of probability, belief, and possibility. Finally, we show that satisfiability for these logics is NP-complete, no harder than satisfiability for propositional logic.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {207–215},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073902,
author = {Heskes, Tom and Zoeter, Onno},
title = {Expectation Propagation for Approximate Inference in Dynamic Bayesian Networks},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We describe expectation propagation for approximate inference in dynamic Bayesian networks as a natural extension of Pearl's exact belief propagation. Expectation propagation is a greedy algorithm, converges in many practical cases, but not always. We derive a double-loop algorithm, guaranteed to converge to a local minimum of a Bethe free energy. Furthermore, we show that stable fixed points of (damped) expectation propagation correspond to local minima of this free energy, but that the converse need not be the case. We illustrate the algorithms by applying t,hem to switching linear dynamical systems and discuss implications for approximate inference in general Bayesian networks.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {216–223},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073903,
author = {Horvitz, Eric and Koch, Paul and Kadie, Carl M. and Jacobs, Andy},
title = {Coordinate: Probabilistic Forecasting of Presence and Availability},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We present methods employed in COORDINATE, a prototype service that supports collaboration and communication by learning predictive models that provide forecasts of users' presence and availability. We describe how data is collected about user activity and proximity from multiple devices, in addition to analysis of the content of users' calendars, the time of day, and day of week. We review applications of presence forecasting embedded in the PRIORITIES application and then present details of the COORDINATE service that was informed by the earlier efforts.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {224–233},
numpages = {10},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073904,
author = {Jensen, Finn V. and Vomlelov\'{a}, Marta},
title = {Unconstrained Influence Diagrams},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We extend the language of influence diagrams to cope with decision scenarios where the order of decisions and observations is not determined. As the ordering of decisions is dependent on the evidence, a step-strategy of such a scenario is a sequence of dependent choices of the next action. A strategy is a step-strategy together with selection functions for decision actions. The structure of a step-strategy can be represented as a DAG with nodes labeled with action variables. We introduce the concept of GS-DAG: a DAG incurporating an optimal step-strategy for any instantiation. We give a method for constructing GS-DAGs, and we show how to use a GS-DAG for determining an optimal strategy. Finally we discuss how analysis of relevant past can be used to reduce the size of the GS-DAG.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {234–241},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073905,
author = {Kadie, Carl M. and Meek, Christopher and Heckerman, David},
title = {CFW: A Collaborative Filtering System Using Posteriors over Weights of Evidence},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We describe CFW, a computationally efficient algorithm for collaborative filtering that uses posteriors over weights of evidence. In experiments on real data, we show that this method predicts as well or better than other methods in situations where the size of the user query is small. The new approach works particularly well when the user's query contains low frequency (unpopular) items. The approach complements that of dependency networks which perform well when the size of the query is large. Also in this paper, we argue that the use of posteriors over weights of evidence is a natural way to recommend similar items--a task that is somewhat different from the usual collaborative-filtering task.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {242–250},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073906,
author = {Kayaalp, Mehmet and Cooper, Gregory F.},
title = {A Bayesian Network Scoring Metric That is Based on Globally Uniform Parameter Priors},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We introduce a new Bayesian network (BN) scoring metric called the Global Uniform (GU) metric. This metric is based on a particular type of default parameter prior. Such priors may be useful when a BN developer is not willing or able to specify domain-specific parameter priors. The GU parameter prior specifies that every prior joint probability distribution P consistent with a BN structure S is considered to be equally likely. Distribution P is consistent with S if P includes just the set of independence relations defined by S.We show that the GU metric addresses some undesirable behavior of the BDeu and K2 Bayesian network scoring metrics, which also use particular forms of default parameter priors. A closed form formula for computing GU for special classes of BNs is derived. Efficiently computing GU for an arbitrary BN remains an open problem.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {251–258},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073907,
author = {Kearns, Michael and Mansour, Yishay},
title = {Efficient Nash Computation in Large Population Games with Bounded Influence},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We introduce a general representation of large-population games in which each player's influence on the others is centralized and limited, but may otherwise be arbitrary. This representation significantly generalizes the class known as congestion games in a natural way. Our main results are provably correct and efficient algorithms for computing and learning approximate Nash equilibria in this general framework.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {259–266},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073908,
author = {Ko\v{c}ka, Tom\'{a}\v{s} and Zhang, Nevin L.},
title = {Dimension Correction for Hierarchical Latent Class Models},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Model complexity is an important factor to consider when selecting among graphical models. When all variables are observed, the complexity of a model can be measured by its standard dimension, i.e. the number of independent parameters. When hidden variables are present, however, standard dimension might no longer be appropriate. One should instead use effective dimension (Geiger et al. 1996). This paper is concerned with the computation of effective dimension. First we present an upper bound on the effective dimension of a latent class (LC) model. This bound is tight and its computation is easy. We then consider a generalization of LC models called hierarchical latent class (HLC) models (Zhang 2002). We show that the effective dimension of an HLC model can be obtained from the effective dimensions of some related LC models. We also demonstrate empirically that using effective dimension in place of standard dimension improves the quality of models learned from data.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {267–274},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073909,
author = {Kutin, Samuel and Niyogi, Partha},
title = {Almost-Everywhere Algorithmic Stability and Generalization Error},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We explore in some detail the notion of algorithmic stability as a viable framework for analyzing the generalization error of learning algorithms. We introduce the new notion of training stability of a learning algorithm and show that, in a general setting, it is sufficient for good bounds on generalization error. In the PAC setting, training stability is both necessary and sufficient for learnability.The approach based on training stability makes no reference to VC dimension or VC entropy. There is no need to prove uniform convergence, and generalization error is bounded directly via an extended McDiarmid inequality. As a result it potentially allows us to deal with a broader class of learning algorithms than Empirical Risk Minimization.We also explore the relationships among VC dimension, generalization error, and various notions of stability. Several examples of learning algorithms are considered.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {275–282},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073910,
author = {Lagoudakis, Michail G. and Parr, Ronald},
title = {Value Function Approximation in Zero-Sum Markov Games},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {This paper investigates value function approximation in the context of zero-sum Markov games, which can be viewed as a generalization of the Markov decision process (MDP) framework to the two-agent case. We generalize error bounds from MDPs to Markov games and describe generalizations of reinforcement learning algorithms to Markov games. We present a generalization of the optimal stopping problem to a two-player simultaneous move Markov game. For this special problem, we provide stronger bounds and can guarantee convergence for LSTD and temporal difference learning with linear value function approximation. We demonstrate the viability of value function approximation for Markov games by using the Least squares policy iteration (LSPI) algorithm to learn good policies for a soccer domain and a flow control problem.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {283–292},
numpages = {10},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073911,
author = {Leisink, Martijn A. R. and Kappen, Hilbert J.},
title = {Computer Generated Higher Order Expansions},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In this article we show the rough outline of a computer algorithm to generate lower bounds on the exponential function of (in principle) arbitrary precision. We implemented this to generate all necessary analytic terms for the Boltzmann machine partition function thus leading to lower bounds of any order. It turns out that the extra variational parameters can be optimized analytically. We show that bounds upto nineth order are still reasonably calculable in practical situations. The generated terms can also be used as extra correction terms (beyond TAP)in mean field expansions.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {293–300},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073912,
author = {Lerner, Uri and Moses, Brooks and Scott, Maricia and McIlraith, Sheila and Koller, Daphne},
title = {Monitoring a Complex Physical System Using a Hybrid Dynamic Bayes Net},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {The Reverse Water Gas Shift system (RWGS) is a complex physical system designed to produce oxygen from the carbon dioxide atmosphere on Mars. If sent to Mars, it would operate without human supervision, thus requiring a reliable automated system for monitoring and control. The RWGS presents many challenges typical of real-world systems, including: noisy and biased sensors, nonlinear behavior, effects that are manifested over different time granularities, and unobservability of many important quantities. In this paper we model the RWGS using a hybrid (discrete/continuous) Dynamic Bayesian Network (DBN), where the state at each time slice contains 33 discrete and 184 continuous variables. We show how the system state can be tracked using probabilistic inference over the model. We discuss how to deal with the various challenges presented by the RWGS, providing a suite of techniques that are likely to be useful in a wide range of applications. In particular, we describe a general framework for dealing with nonlinear behavior using numerical integration techniques, extending the successful Unscented Filter. We also show how to use a fixed-point computation to deal with effects that develop at different time scales, specifically rapid changes occurring during slowly changing processes. We test our model using real data collected from the RWGS, demonstrating the feasibility of hybrid DBNs for monitoring complex real-world physical systems.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {301–310},
numpages = {10},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073913,
author = {Madani, Omid},
title = {Polynomial Value Iteration Algorithms for Deterministic MDPs},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Value iteration is a commonly used and empirically competitive method in solving many Markov decision process problems. However, it is known that value iteration has only pseudopolynomial complexity in general. We establish a somewhat surprising polynomial bound for value iteration on deterministic Markov decision (DMDP) problems. We show that the basic value iteration procedure converges to the highest average reward cycle on a DMDP problem in θ(n2) iterations, or θ(mn2) total time, where n denotes the number of states, and m the number of edges. We give two extensions of value iteration that solve the DMDP in θ(mn) time. We explore the analysis of policy iteration algorithms and report on an empirical study of value iteration showing that its convergence is much faster on random sparse graphs.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {311–318},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073914,
author = {Marthi, Bhaskara and Pasula, Hanna and Russell, Stuart and Peres, Yuval},
title = {Decayed MCMC Iltering},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Filtering--estimating the state of a partially observable Markov process from a sequence of observations-is one of the most widely studied problems in control theory, AI, and computational statistics. Exact computation of the posterior distribution is generally intractable for large discrete systems and for nonlinear continuous systems, so a good deal of effort has gone into developing robust approximation algorithms. This paper describes a simple stochastic approximation algorithm for filtering called decayed MCMC. The algorithm applies Markov chain Monte Carlo sampling to the space of state trajectories using a proposal distribution that favours flips of more recent state variables. The formal analysis of the algorithm involves a generalization of standard coupling arguments for MCMC convergence. We prove that for any ergodic underlying Markov process, the convergence time of decayed MCMC with inversepolynomial decay remains bounded as the length of the observation sequence grows. We show experimentally that decayed MCMC is at least competitive with other approximation algorithms such as particle filtering.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {319–326},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073915,
author = {McBurney, Peter and Parsons, Simon},
title = {Formalizing Scenario Analysis},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We propose a formal treatment of scenarios in the context of a dialectical argumentation formalism for qualitative reasoning about uncertain propositions. Our formalism extends prior work in which arguments for and against uncertain propositions were presented and compared in interaction spaces called Agoras. We now define the notion of a scenario in this framework and use it to define a set of qualitative uncertainty labels for propositions across a collection of scenarios. This work is intended to lead to a formal theory of scenarios and scenario analysis.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {327–334},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073916,
author = {Meek, Christopher and Thiesson, Bo and Heckerman, David},
title = {Staged Mixture Modelling and Boosting},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In this paper, we introduce and evaluate a data-driven staged mixture modeling tcchnique for building density, regression, and classification models. Our basic approach is to sequentially add components to a finite mixture model using the structural expectation maximization (SEM) algorithm. We show that our technique is qualitatively similar to boosting. This correspondence is a natural byproduct of the fact that we use the SEM algorithm to sequentially fit the mixture model. Finally, in our experimental evaluation, we demonstrate the effectiveness of our approach on a variety of prediction and density estimation tasks using real-world data.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {335–343},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073917,
author = {Mettu, Ramgopal R. and Plaxton, C. Greg},
title = {Optimal Time Bounds for Approximate Clustering},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Clustering is a fundamental problem in unsupervised learning, and has been studied widely both as a problem of learning mixture models and as an optimization problem. In this paper, we study clustering with respect the k-median objective function, a natural formulation of clustering in which we attempt to minimize the average distance to cluster centers. One of the main contributions of this paper is a simple but powerful sampling technique that we call successive sampling that could be of independent interest. We show that our sampling procedure can rapidly identify a small set of points (of size just O(klogn/k)) that summarize the input points for the purpose of clustering. Using successive sampling, we develop an algorithm for the k-median problem that runs in O(nk) time for a wide range of values of k and is guaranteed, with high probability, to return a solution with cost at most a constant factor times optimal. We also establish a lower bound of Ω(nk) on any randomized constant-factor approximation algorithm for the k-median problem that succeeds with even a negligible (say 1/100) probability. The best previous upper bound for the problem was \~{O}(nk), where the \~{O}-notation hides polylogarithmic factors in n and k. The best previous lower bound of Ω(nk) applied only to deterministic k-median algorithms. While we focus our presentation on the k-median objective, all our upper bounds are valid for the k-means objective as well. In this context our algorithm compares favorably to the widely used k-means heuristic, which requires O(nk) time for just one iteration and provides no useful approximation guarantees.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {344–351},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073918,
author = {Minka, Thomas and Lafferty, John},
title = {Expectation-Propagation for the Generative Aspect Model},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {The generative aspect model is an extension of the multinomial model for text that allows word probabilities to vary stochastically across documents. Previous results with aspect models have been promising, but hindered by the computational difficulty of carrying out inference and learning. This paper demonstrates that the simple variational methods of Blei et al. (2001) can lead to inaccurate inferences and biased learning for the generative aspect model. We develop an alternative approach that leads to higher accuracy at comparable cost. An extension of Expectation-Propagation is used for inference and then embedded in an EM algorithm for learning. Experimental results are presented for both synthetic and real data sets.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {352–359},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073919,
author = {Moore, Andrew and Schneider, Jeff},
title = {Real-Valued All-Dimensions Search: Low-Overhead Rapid Searching over Subsets of Attributes},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {This paper is about searching the combinatorial space of contingency tables during the inner loop of a nonlinear statistical optimization. Examples of this operation in various data analytic communities include searching for nonlinear combinations of attributes that contribute significantly to a regression (Statistics), searching for items to include in a decision list (machine learning) and association rule hunting (Data Mining).This paper investigates a new, efficient approach to this class of problems, called RADSEARCH (Real-valued All-Dimensions-tree Search). RADSEARCH finds the global optimum, and this gives us the opportunity to empirically evaluate the question: apart from algorithmic elegance what does this attention to optimality buy us?We compare RADSEARCH with other recent successful search algorithms such as CN2, PRIM, APriori, OPUS and DenseMiner. Finally, we introduce RADREG, a new regression algorithm for learning real-valued outputs based on RADSEARCHing for highorder interactions.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {360–369},
numpages = {10},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073920,
author = {Ng, Brenda and Peshkin, Leonid and Pfeffer, Avi},
title = {Factored Particles for Scalable Monitoring},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Exact monitoring in dynamic Bayesian networks is intractable, so approximate algorithms are necessary. This paper presents a new family of approximate monitoring algorithms that combine the best qualities of the particle filtering and Boyen-Koller methods. Our algorithms maintain an approximate representation the belief state in the form of sets of factored particles, that correspond to samples of clusters of state variables. Empirical results show that our algorithms outperform both ordinary particle filtering and the Boyen-Koller algorithm on large systems.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {370–377},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073921,
author = {Nodelman, Uri and Shelton, Christian R. and Koller, Daphne},
title = {Continuous Time Bayesian Networks},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In this paper we present a language for finite state continuous time Bayesian networks (CTBNs), which describe structured stochastic processes that evolve over continuous time. The state of the system is decomposed into a set of local variables whose values change over time. The dynamics of the system are described by specifying the behavior of each local variable as a function of its parents in a directed (possibly cyclic) graph. The model specifies, at any given point in time, the distribution over two aspects: when a local variable changes its value and the next value it takes. These distributions are determined by the variable's current value and the current values of its parents in the graph. More formally, each variable is modelled as a finite state continuous time Markov process whose transition intensities are functions of its parents. We present a probabilistic semantics for the language in terms of the generative model a CTBN defines over sequences of events. We list types of queries one might ask of a CTBN, discuss the conceptual and computational difficulties associated with exact inference, and provide an algorithm for approximate inference which takes advantage of the structure within the process.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {378–387},
numpages = {10},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073922,
author = {Park, James D.},
title = {MAP Complexity Results and Approximation Methods},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {MAP is the problem of nding a most probable instantiation of a set of variables in a Bayesian network, given some evidence. MAP appears to be a signi cantly harder problem than the related problems of computing the probability of evidence (Pr), or MPE (a special case of MAP). Because of the complexity of MAP, and the lack of viable algorithms to approximate it, MAP computations are generally avoided by practitioners.This paper investigates the complexity of MAP. We show that MAP is complete for NPPP. We also provide negative complexity results for elimination based algorithms. It turns out that MAP remains hard even when MPE, and Pr are easy. We show that MAP is NP-complete when the networks are restricted to polytrees, and even then can not be e ectively approximated.Because there is no approximation algorithm with guaranteed results, we investigate best effort approximations. We introduce a generic MAP approximation framework. As one instantiation of it, we implement local search coupled with belief propagation (BP) to approximate MAP. We show how to extract approximate evidence retraction information from belief propagation which allows us to perform e cient local search. This allows MAP approximation even on networks that are too complex to even exactly solve the easier problems of computing Pr or MPE. Experimental results indicate that using BP and local search provides accurate MAP estimates in many cases.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {388–396},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073923,
author = {Pavlenko, Tatjana and von Rosen, Dietrich},
title = {Bayesian Network Classifiers in a High Dimensional Framework},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We present a growing dimension asymptotic formalism. The perspective in this paper is classification theory and we show that it can accommodate probabilistic networks classifiers, including naive Bayes model and its augmented version. When represented as a Bayesian network these classifiers have an important advantage: The corresponding discriminant function turns out to be a specialized case of a generalized additive model, which makes it possible to get closed form expressions for the asymptotic misclassification probabilities used here as a measure of classification accuracy. Moreover, in this paper we propose a new quantity for assessing t,he discriminative power of a set, of features which is then used to elaborate the augmented naive Bayes classifier. The result is a weighted form of the augmented naive Bayes that distributes weights among the sets of features according to their discriminative power. We derive the asymptotic distribution of the sample based discriminative power and show that it is seriously overestimated in a high dimensional case. We then apply this result, to find the optimal, in a sense of minimum misclassification probability, type of weighting.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {397–404},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073924,
author = {Pennock, David M. and Debnath, Sandip and Glover, Eric J. and Giles, C. Lee},
title = {Modeling Information Incorporation in Markets, with Application to Detecting and Explaining Events},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We develop a model of how information flows into a market, and derive algorithms for automatically detecting and explaining relevant events. We analyze data from twenty-two "political stock markets" (i.e., betting markets on political outcomes) on the Iowa Electronic Market (IEM). We prove that, under certain efficiency assumptions, prices in such betting markets will on average approach the correct outcomes over time, and show that IEM data conforms closely to the theory. We present a simple model of a betting market where information is revealed over time, and show a qualitative correspondence between the model and real market data. We also present an algorithm for automatically detecting significant events and generating semantic explanations of their origin. The algorithm operates by discovering significant changes in vocabulary on online news sources (using expected entropy loss) that align with major price spikes in related betting markets.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {405–413},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073925,
author = {Porter, Ryan and Ronen, Amir and Shoham, Yoav and Tennenholtz, Moshe},
title = {Mechanism Design with Execution Uncertainty},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We introduce the notion of fault tolerant mechanism design, which extends the standard game theoretic framework of mechanism design to allow for uncertainty about execution. Specifically, we define the problem of task allocation in which the private information of the agents is not only their costs to attempt the tasks, but also their probabilities of failure. For several different instances of this setting we present technical results, including positive ones in the form of mechanisms that are incentive compatible, individually rational and efficient, and negative ones in the form of impossibility theorems.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {414–421},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073926,
author = {Renooij, Silja and van der Gaag, Linda C.},
title = {From Qualitative to Quantitative Probabilistic Networks},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Quantification is well known to be a major obstacle in the construction of a probabilistic network, especially when relying on human experts for this purpose. The construction of a qualitative probabilistic network has been proposed as an initial step in a network's quantification, since the qualitative network can be used to gain preliminary insight in the projected network's reasoning behaviour. We extend on this idea and present a new type of network in which both signs and numbers are specified; we further present an associated algorithm for probabilistic inference. Building upon these semi-qualitative networks, a probabilistic network can be quantified and studied in a stepwise manner. As a result, modelling inadequacies can be detected and amended at an early stage in the quantification process.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {422–429},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073927,
author = {da Rocha, Jos\'{e} Carlos Ferreira and Cozman, Fabio Gagliardi},
title = {Inference with Separately Specified Sets of Probabilities in Credal Networks},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We present new algorithms for inference in credal networks -- directed acyclic graphs associated with sets of probabilities. Credal networks are here interpreted as encoding strong independence relations among variables. We first present a theory of credal networks based on separately specified sets of probabilities. We also show that inference with polytrees is NP-hard in this setting. We then introduce new techniques that reduce the computational effort demanded by inference, particularly in polytrees, by exploring separability of credal sets.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {430–437},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073928,
author = {Rusakov, Dmitry and Geiger, Dan},
title = {Asymptotic Model Selection for Naive Bayesian Networks},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We develop a closed form asymptotic formula to compute the marginal likelihood of data given a naive Bayesian network model with two hidden states and binary features. This formula deviates from the standard BIC score. Our work provides a concrete example that the BIC score is generally not valid for statistical models that belong to a stratified exponential family. This stands in contrast to linear and curved exponential families, where the BIC score has been proven to provide a correct approximation for the marginal likelihood.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {438–455},
numpages = {18},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073929,
author = {Schapire, Robert E.},
title = {Advances in Boosting},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Boosting is a general method of generating many simple classification rules and combining them into a single, highly accurate rule. This paper reviews the AdaBoost boosting algorithm and some of its underlying theory, and then looks at some of the challenges of applying AdaBoost to bidding in complicated auctions and to human-computer spoken-dialogues systems.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {446–452},
numpages = {7},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073930,
author = {Shani, Guy and Brafman, Ronen I. and Heckerman, David},
title = {An MDP-Based Recommender System},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Typical Recommender systems adopt a static view of the recommendation process and treat it as a prediction problem. We argue that it is more appropriate to view the problem of generating recommendations as a sequential decision problem and, consequently, that Markov decision processes (MDP) provide a more appropriate model for Recommender systems. MDPs introduce two benefits: they take into account the long-term effects of each recommendation, and they take into account the expected value of each recommendation. To succeed in practice, an MDP-based Recommender system must employ a strong initial model; and the bulk of this paper is concerned with the generation of such a model. In particular, we suggest the use of an n-gram predictive model for generating the initial MDP. Our n-gram model induces a Markovchain model of user behavior whose predictive accuracy is greater than that of existing predictive models. We describe our predictive model in detail and evaluate its performance on real data. In addition, we show how the model can be used in an MDP-based Recommender system.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {453–460},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073931,
author = {Shelton, Christian R.},
title = {Reinforcement Learning with Partially Known World Dynamics},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Reinforcement learning would enjoy better success on real-world problems if domain knowledge could be imparted to the algorithm by the modelers. Most problems have both hidden state and unknown dynamics. Partially observable Markov decision processes (POMDPs) allow for the modeling of both. Unfortunately, they do not provide a natural framework in which to specify knowledge about the domain dynamics. The designer must either admit to knowing nothing about the dynamics or completely specify the dynamics (thereby turning it into a planning problem). We propose a new framework called a partially known Markov decision process (PKMDP) which allows the designer to specify known dynamics while still leaving portions of the environment's dynamics unknown. The model represents not only the environment dynamics but also the agent's knowledge of the dynamics. We present a reinforcement learning algorithm for this model based on importance sampling. The algorithm incorporates planning based on the known dynamics and learning about the unknown dynamics. Our results clearly demonstrate the ability to add domain knowledge and the resulting benefits for learning.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {461–468},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073932,
author = {Steck, Harald and Jaakkola, Tommi S.},
title = {Unsupervised Active Learning in Large Domains},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Active learning is a powerful approach to analyzing data effectively. We show that the feasibility of active learning depends crucially on the choice of measure with respect to which the query is being optimized. The standard information gain, for example, does not permit an accurate evaluation with a small committee, a representative subset of the model space. We propose a surrogate measure requiring only a small committec and discuss the properties of this new measure. We devise, in addition, a bootstrap approach for committee selection. The advantages of this approach are illustrated in the context of recovering (regulatory) network models.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {469–476},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073933,
author = {Takikawa, Masami and D'Ambrosio, Bruce and Wright, Ed},
title = {Real-Time Inference with Large-Scale Temporal Bayes Nets},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {An increasing number of applications require real-time reasoning under uncertainty with streaming input. The temporal (dynamic) Bayes net formalism provides a powerful representational framework for such applications. However, existing exact inference algorithms for dynamic Bayes nets do not scale to the size of models required for real world applications which often contain hundreds or even thousands of variables for each time slice. In addition, existing algorithms were not developed with real-time processing in mind. We have developed a new computational approach to support real-time exact inference in large temporal Bayes nets. Our approach tackles scalability by recognizing that the complexity of the inference depends on the number of interface nodes between time slices and by exploiting the distinction between static and dynamic nodes in order to reduce the number of interface nodes and to factorize their joint probability distribution. We approach the real-time issue by organizing temporal Bayes nets into static representations, and then using the symbolic probabilistic inference algorithm to derive analytic expressions for the static representations. The parts of these expressions that do not change at each time step are pre-computed. The remaining parts are compiled into efficient procedural code so that the memory and CPU resources required by the inference are small and fixed.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {477–484},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073934,
author = {Taskar, Ben and Abbeel, Pieter and Koller, Daphne},
title = {Discriminative Probabilistic Models for Relational Data},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In many supervised learning tasks, the entities to be labeled are related to each other in complex ways and their labels are not independent. For example, in hypertext classification, the labels of linked pages are highly correlated. A standard approach is to classify each entity independently, ignoring the correlations between them. Recently, Probabilistic Relational Models, a relational version of Bayesian networks, were used to define a joint probabilistic model for a collection of related entities. In this paper, we present an alternative framework that builds on (conditional) Markov networks and addresses two limitations of the previous approach. First, undirected models do not impose the acyclicity constraint that hinders representation of many important relational dependencies in directed models. Second, undirected models are well suited for discriminative training, where we optimize the conditional likelihood of the labels given the features, which generally improves classification accuracy. We show how to train these models effectively, and how to use approximate probabilistic inference over the learned model for collective classification of multiple related entities. We provide experimental results on a webpage classification task, showing that accuracy can be significantly improved by modeling relational dependencies.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {485–492},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073935,
author = {Tatikonda, Sekhar C. and Jordan, Michael I.},
title = {Loopy Belief Propagation and Gibbs Measures},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We address the question of convergence in the loopy belief propagation (LBP) algorithm. Specifically, we relate convergence of LBP to the existence of a weak limit for a sequence of Gibbs measures defined on the LBP's associated computation tree. Using tools from the theory of Gibbs measures we develop easily testable sufficient conditions for convergence. The failure of convergence of LBP implies the existence of multiple phases for the associated Gibbs specification. These results give new insight into the mechanics of the algorithm.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {493–500},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073936,
author = {Thi\'{e}baux, Sylvie and Kabanza, Froduald and Slaney, John},
title = {Anytime State-Based Solution Methods for Decision Processes with Non-Markovian Rewards},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {A popular approach to solving a decision process with non-Markovian rewards (NMRDP) is to exploit a compact representation of the reward function to automatically translate the NMRDP into an equivalent Markov decision process (MDP) amenable to our favorite MDP solution method. The contribution of this paper is a representation of non-Markovian reward functions and a translation into MDP aimed at making the best possible use of state-based anytime algorithms as the solution method. By explicitly constructing and exploring only parts of the state space, these algorithms are able to trade computation time for policy quality, and have proven quite effective in dealing with large MDPs. Our representation extends future linear temporal logic (FLTL) to express rewards. Our translation has the effect of embedding modelchecking in the solution method. It results in an MDP of the minimal size achievable without stepping outside the anytime framework, and consequently in better policies by the deadline.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {501–510},
numpages = {10},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073937,
author = {Thrun, Sebastian},
title = {Particle Filters in Robotics},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In recent years, particle filters have solved several hard perceptual problems in robotics. Early successes of particle filters were limited to low-dimensional estimation problems, such as the problem of robot localization in environments with known maps. More recently, researchers have begun exploiting structural properties of robotic domains that have led to successful particle filter applications in spaces with as many as 100,000 dimensions. The fact that every model--no mater how detailed--fails to capture the full complexity of even the most simple robotic environments has lead to specific tricks and techniques essential for the success of particle filters in robotic domains. This article surveys some of these recent innovations, and provides pointers to in-depth articles on the use of particle filters in robotics.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {511–518},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073938,
author = {Tian, Jin and Pearl, Judea},
title = {On the Testable Implications of Causal Models with Hidden Variables},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {The validity of a causal model can be tested only if the model imposes constraints on the probability distribution that governs the generated data. In the presence of unmeasured variables, causal models may impose two types of constraints: conditional independencies, as read through the d-separation criterion, and functional constraints, for which no general criterion is available. This paper offers a systematic way of identifying functional constraints and, thus, facilitates the task of testing causal models as well as inferring such models from data.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {519–527},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073939,
author = {Vomlel, Jifi},
title = {Exploiting Functional Dependence in Bayesian Network Inference},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {In this paper we propose an efficient method for Bayesian network inference in models with functional dependence. We generalize the multiplicative factorization method originally designed by Takikawa and D'Ambrosio (1999) for models with independence of causal influence. Using a hidden variable, we transform a probability potential into a product of two-dimensional potentials. The multiplicative factorization yields more efficient inference. For example, in junction tree propagation it helps to avoid large cliques. In order to keep potentials small, the number of states of the hidden variable should be minimized. We transform this problem into a combinatorial problem of minimal base in a particular space. We present an example of a computerized adaptive test, in which the factorization method is significantly more efficient than previous inference methods.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {528–535},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073940,
author = {Wainwright, Martin J. and Jaakkola, Tommi S. and Willsky, Alan S.},
title = {A New Class of Upper Bounds on the Log Partition Function},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Bounds on the log partition function are important in a variety of contexts, including approximate inference, model fitting, decision theory, and large deviations analysis [11, 5, 4]. We introduce a new class of upper bounds on the log partition function, based on convex combinations of distributions in the exponential domain, that is applicable to an arbitrary undirected graphical model. In the special case of convex combinations of tree-structured distributions, we obtain a family of variational problems, similar to the Bethe free energy, but distinguished by the following desirable properties: (i) they are convex, and have a unique global minimum; and (ii) the global minimum gives an upper bound on the log partition function. The global minimum is defined by stationary conditions very similar to those defining fixed points of belief propagation (BP) or tree-based reparameterization [see 13, 14]. As with BP fixed points, the elements of the minimizing argument can be used as approximations to the marginals of the original model. The analysis described here can be extended to structures of higher treewidth (e.g., hypertrees), thereby making connections with more advanced approximations (e.g., Kikuchi and variants [15, 10]).},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {536–543},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073941,
author = {Wakker, Peter P.},
title = {Decision-Principles to Justify Carnap's Updating Method and to Suggest Corrections of Probability Judgments},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {This paper uses decision-theoretic principles to obtain new insights into the assessment and updating of probabilities. First, a new foundation of Bayesianism is given. It does not require infinite atomless uncertainties as did Savage's classical result, and can therefore be applied to any finite Bayesian network. It neither requires linear utility as did de Finetti's classical result, and therefore allows for the empirically and normatively desirable risk aversion. Finally, by identifying and fixing utility in an elementary manner, our result can readily be applied to identify methods of probability updating. Thus, a decision-theoretic foundation is given to the computationally efficient method of inductive reasoning developed by Rudolf Carnap. Finally, recent empirical findings on probability assessments are discussed. It leads to suggestions for correcting biases in probability assessments, and for an alternative to the Dempster-Shafer belief functions that avoids the reduction to degeneracy after multiple updatings.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {544–551},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073942,
author = {Wang, Yang and Tan, Tele},
title = {Adaptive Foreground and Shadow Detection in Image Sequences},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {This paper presents a novel method of foreground segmentation that distinguishes moving objects from their moving cast shadows in monocular image sequences. The models of background, edge information, and shadow are set up and adaptively updated. A Bayesian belief network is proposed to describe the relationships among the segmentation label, background, intensity, and edge information. The notion of Markov random field is used to encourage the spatial connectivity of the segmented regions. The solution is obtained by maximizing the posterior possibility density of the segmentation field.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {552–559},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073943,
author = {Wiegerinck, Wim and Heskes, Tom},
title = {IPF for Discrete Chain Factor Graphs},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Iterative Proportional Fitting (IPF), combined with EM, is commonly used as an algorithm for likelihood maximization in undirected graphical models. In this paper, we present two iterative algorithms that generalize upon IPF. The first one is for likelihood maximization in discrete chain factor graphs, which we define as a wide class of discrete variable models including undirected graphical models and Bayesian networks, but also chain graphs and sigmoid belief networks. The second one is for conditional likelihood maximization in standard undirected models and Bayesian networks. In both algorithms, the iteration steps are expressed in closed form. Numerical simulations show that the algorithms are competitive with state of the art methods.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {560–567},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073944,
author = {Yoon, SungWook and Fern, Alan and Givan, Robert},
title = {Inductive Policy Selection for First-Order MDPs},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {We select policies for large Markov Decision Processes (MDPs) with compact first-order representations. We find policies that generalize well as the number of objects in the domain grows, potentially without bound. Existing dynamic-programming approaches based on flat, propositional, or first-order representations either are impractical here or do not naturally scale as the number of objects grows without bound. We implement and evaluate an alternative approach that induces first-order policies using training data constructed by solving small problem instances using PGraphplan (Blurn & Langford, 1999). Our policies are represented as ensembles of decision lists, using a taxonomic concept language. This approach extends the work of Martin and Geffner (2000) to stochastic domains, ensemble learning, and a wider variety of problems. Empirically, we find "good" policies for several stochastic first-order MDPs that are beyond the scope of previous approaches. We also discuss the application of this work to the relational reinforcement-learning problem.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {568–576},
numpages = {9},
location = {Alberta, Canada},
series = {UAI'02}
}

@inproceedings{10.5555/2073876.2073945,
author = {Zaffalon, Marco and Hutter, Marcus},
title = {Robust Feature Selection by Mutual Information Distributions},
year = {2002},
isbn = {1558608974},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {Mutual information is widely used in artificial intelligence, in a descriptive way, to measure the stochastic dependence of discrete random variables. In order to address questions such as the reliability of the empirical value, one must consider sample-to-population inferential approaches. This paper deals with the distribution of mutual information, as obtained in a Bayesian framework by a second-order Dirichlet prior distribution. The exact analytical expression for the mean and an analytical approximation of the variance are reported. Asymptotic approximations of the distribution are proposed. The results are applied to the problem of selecting features for incremental learning and classification of the naive Bayes classifier. A fast, newly defined method is shown to outperform the traditional approach based on empirical mutual information on a number of real data sets. Finally, a theoretical development is reported that allows one to efficiently extend the above methods to incomplete samples in an easy and effective way.},
booktitle = {Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence},
pages = {577–584},
numpages = {8},
location = {Alberta, Canada},
series = {UAI'02}
}

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr

branch_name: refs/heads/main

extension: bib


text:
DESCRIPTION = "Task package for Java GTK applications"
PR = "r0"
LICENSE = "MIT"

inherit task

RDEPENDS_${PN} = "\
    classpath-awt \
    librxtx-java \
    librxtx-jni \
    libswt3.4-gtk-java \
    logic-analyzer \
 "

license: MIT

repository: overo/overo-oe-natty

license_type: permissive

repo_name: overo/overo-oe-natty

branch_name: HEAD

extension: bb


text:
#
# libxfont_1.4.7.bb
#
SUMMARY = "XFont: X Font rasterisation library"

DESCRIPTION = "libXfont provides various services for X servers, most \
notably font selection and rasterisation (through external libraries \
such as freetype)."

require xorg-lib-common.inc

LICENSE = "MIT & MIT-style & BSD"
LIC_FILES_CHKSUM = "file://COPYING;md5=a46c8040f2f737bcd0c435feb2ab1c2c"

DEPENDS += "freetype xtrans fontsproto libfontenc zlib"
PROVIDES = "xfont"

PE = "1"

XORG_PN = "libXfont"

BBCLASSEXTEND = "native"

SRC_URI[md5sum] = "b21ee5739d5d2e5028b302fbf9fe630b"
SRC_URI[sha256sum] = "d16ea3541835d296b19cfb05d7e64fc62173d8e7eb93284402ec761b951d1543"

#
# debian
#
inherit debian-package
DEBIAN_SECTION = "x11"
DPR = "0"

# There is no debian patch
DEBIAN_PATCH_TYPE = "nopatch"

repository: takuya-t/meta-debian

repo_name: takuya-t/meta-debian

branch_name: refs/heads/daisy


text:
@article{pmid30660105,
 abstract = {Synthetic proteins with high affinity and selectivity for a protein target can be used as research tools, biomarkers, and pharmacological agents, but few methods exist to design such proteins de novo. To this end, the In-Silico Protein Synthesizer (InSiPS) was developed to design synthetic binding proteins (SBPs) that bind pre-determined targets while minimizing off-target interactions. InSiPS is a genetic algorithm that refines a pool of random sequences over hundreds of generations of mutation and selection to produce SBPs with pre-specified binding characteristics. As a proof of concept, we design SBPs against three yeast proteins and demonstrate binding and functional inhibition of two of three targets in vivo. Peptide SPOT arrays confirm binding sites, and a permutation array demonstrates target specificity. Our foundational approach will support the field of de novo design of small binding polypeptide motifs and has robust applicability while offering potential advantages over the limited number of techniques currently available.},
 author = {Daniel Burnside and Andrew Schoenrock and Houman Moteshareie and Mohsen Hooshyar and Prabh Basra and Maryam Hajikarimlou and Kevin Dick and Brad Barnes and Tom Kazmirchuk and Matthew Jessulat and Sylvain Pitre and Bahram Samanfar and Mohan Babu and James R Green and Alex Wong and Frank Dehne and Kyle K Biggar and Ashkan Golshani},
 doi = {10.1016/j.isci.2018.11.038},
 journal = {iScience},
 month = {January},
 nlmuniqueid = {101724038},
 pages = {375-387},
 pii = {S2589-0042(18)30228-1},
 pmc = {PMC6348295},
 pubmed = {30660105},
 title = {In Silico Engineering of Synthetic Binding Proteins from Random Amino Acid Sequences.},
 volume = {11},
 year = {2019}
}

repository: zqzneptune/BabuLab

repo_name: zqzneptune/BabuLab

branch_name: refs/heads/master


text:
SECTION = "devel"
DESCRIPTION = "GNU Make examines the timestamps on a set of \
interdependent files, and, if necessary, issues commands \
to bring them up-to-date."
LICENSE = "GPL"
SRC_URI = "${GNU_MIRROR}/make/make-${PV}.tar.bz2 \
	   file://SCCS.patch;patch=1"

inherit autotools

repository: Terentyev/familiar-linux

repo_name: Terentyev/familiar-linux


text:
@incollection{NIPS2019_9500,
 author = {Yadav, Chhavi and Bottou, Leon},
 booktitle = {Advances in Neural Information Processing Systems 32},
 editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d' Alché-Buc and E. Fox and R. Garnett},
 pages = {13443--13452},
 publisher = {Curran Associates, Inc.},
 title = {Cold Case: The Lost MNIST Digits},
 url = {http://papers.nips.cc/paper/9500-cold-case-the-lost-mnist-digits.pdf},
 year = {2019}
}

repository: infinite-pursuits/academic-kickstart

repo_name: infinite-pursuits/academic-kickstart