Moisés Goldszmidt

UAI Conference 2008 Conference Paper

CT-NOR: Representing and Reasoning About Events in Continuous Time

• Aleksandr Simma
• Moisés Goldszmidt
• John MacCormick
• Paul Barham 0001
• Richard Black
• Rebecca Isaacs
• Richard Mortier

We present a generative model for representing and reasoning about the relationships among events in continuous time. We apply the model to the domain of networked and distributed computing environments where we fit the parameters of the model from timestamp observations, and then use hypothesis testing to discover dependencies between the events and changes in behavior for monitoring and diagnosis. After introducing the model, we present an EM algorithm for fitting the parameters and then present the hypothesis testing approach for both dependence discovery and change-point detection. We validate the approach for both tasks using real data from a trace of network events at Microsoft Research Cambridge. Finally, we formalize the relationship between the proposed model and the noisy-or gate for cases when time can be discretized.

UAI Conference 2007 Conference Paper

Making life better one large system at a time: Challenges for UAI research

• Moisés Goldszmidt

AIJ Journal 2000 Journal Article

Stochastic dynamic programming with factored representations

• Craig Boutilier
• Richard Dearden
• Moisés Goldszmidt

Markov decision processes (MDPs) have proven to be popular models for decision-theoretic planning, but standard dynamic programming algorithms for solving MDPs rely on explicit, state-based specifications and computations. To alleviate the combinatorial problems associated with such methods, we propose new representational and computational techniques for MDPs that exploit certain types of problem structure. We use dynamic Bayesian networks (with decision trees representing the local families of conditional probability distributions) to represent stochastic actions in an MDP, together with a decision-tree representation of rewards. Based on this representation, we develop versions of standard dynamic programming algorithms that directly manipulate decision-tree representations of policies and value functions. This generally obviates the need for state-by-state computation, aggregating states at the leaves of these trees and requiring computations only for each aggregate state. The key to these algorithms is a decision-theoretic generalization of classic regression analysis, in which we determine the features relevant to predicting expected value. We demonstrate the method empirically on several planning problems, showing significant savings for certain types of domains. We also identify certain classes of problems for which this technique fails to perform well and suggest extensions and related ideas that may prove useful in such circumstances. We also briefly describe an approximation scheme based on this approach.

UAI Conference 1999 Conference Paper

Continuous Value Function Approximation for Sequential Bidding Policies

• Craig Boutilier
• Moisés Goldszmidt
• Bikash Sabata

Market-based mechanisms such as auctions are being studied as an appropriate means for resource allocation in distributed and mulitagent decision problems. When agents value resources in combination rather than in isolation, they must often deliberate about appropriate bidding strategies for a sequence of auctions offering resources of interest. We briefly describe a discrete dynamic programming model for constructing appropriate bidding policies for resources exhibiting both complementarities and substitutability. We then introduce a continuous approximation of this model, assuming that money (or the numeraire good) is infinitely divisible. Though this has the potential to reduce the computational cost of computing policies, value functions in the transformed problem do not have a convenient closed form representation. We develop {em grid-based} approximation for such value functions, representing value functions using piecewise linear approximations. We show that these methods can offer significant computational savings with relatively small cost in solution quality.

UAI Conference 1999 Conference Paper

Data Analysis with Bayesian Networks: A Bootstrap Approach

• Nir Friedman
• Moisés Goldszmidt
• Abraham J. Wyner

In recent years there has been significant progress in algorithms and methods for inducing Bayesian networks from data. However, in complex data analysis problems, we need to go beyond being satisfied with inducing networks with high scores. We need to provide confidence measures on features of these networks: Is the existence of an edge between two nodes warranted? Is the Markov blanket of a given node robust? Can we say something about the ordering of the variables? We should be able to address these questions, even when the amount of data is not enough to induce a high scoring network. In this paper we propose Efron's Bootstrap as a computationally efficient approach for answering these questions. In addition, we propose to use these confidence measures to induce better structures from the data, and to detect the presence of latent variables.

ICML Conference 1998 Conference Paper

Bayesian Network Classification with Continuous Attributes: Getting the Best of Both Discretization and Parametric Fitting

• Nir Friedman
• Moisés Goldszmidt
• Thomas J. Lee

UAI Conference 1997 Conference Paper

Sequential Update of Bayesian Network Structure

• Nir Friedman
• Moisés Goldszmidt

UAI Conference 1996 Conference Paper

Context-Specific Independence in Bayesian Networks

• Craig Boutilier
• Nir Friedman
• Moisés Goldszmidt
• Daphne Koller

Bayesian networks provide a language for qualitatively representing the conditional independence properties of a distribution. This allows a natural and compact representation of the distribution, eases knowledge acquisition, and supports effective inference algorithms. It is well-known, however, that there are certain independencies that we cannot capture qualitatively within the Bayesian network structure: independencies that hold only in certain contexts, i.e., given a specific assignment of values to certain variables. In this paper, we propose a formal notion of context-specific independence (CSI), based on regularities in the conditional probability tables (CPTs) at a node. We present a technique, analogous to (and based on) d-separation, for determining when such independence holds in a given network. We then focus on a particular qualitative representation scheme---tree-structured CPTs---for capturing CSI. We suggest ways in which this representation can be used to support effective inference algorithms. In particular, we present a structural decomposition of the resulting network which can improve the performance of clustering algorithms, and an alternative algorithm based on cutset conditioning.

ICML Conference 1996 Conference Paper

Discretizing Continuous Attributes While Learning Bayesian Networks

• Nir Friedman
• Moisés Goldszmidt

UAI Conference 1996 Conference Paper

Learning Bayesian Networks with Local Structure

• Nir Friedman
• Moisés Goldszmidt

AIJ Journal 1996 Journal Article

Qualitative probabilities for default reasoning, belief revision, and causal modeling

• Moisés Goldszmidt
• Judea Pearl

This paper presents a formalism that combines useful properties of both logic and probabilities. Like logic, the formalism admits qualitative sentences and provides symbolic machinery for deriving deductively closed beliefs and, like probability, it permits us to express if-then rules with different levels of firmness and to retract beliefs in response to changing observations. Rules are interpreted as order-of-magnitude approximations of conditional probabilities which impose constraints over the rankings of worlds. Inferences are supported by a unique priority ordering on rules which is syntactically derived from the knowledge base. This ordering accounts for rule interactions, respects specificity considerations and facilitates the construction of coherent states of beliefs. Practical algorithms are developed and analyzed for testing consistency, computing rule ordering, and answering queries. Imprecise observations are incorporated using qualitative versions of Jeffrey's rule and Bayesian updating, with the result that coherent belief revision is embodied naturally and tractably. Finally, causal rules are interpreted as imposing Markovian conditions that further constrain world rankings to reflect the modularity of causal organizations. These constraints are shown to facilitate reasoning about causal projections, explanations, actions and change.

UAI Conference 1995 Conference Paper

Fast Belief Update Using Order-of-Magnitude Probabilities

• Moisés Goldszmidt

We present an algorithm, called Predict, for updating beliefs in causal networks quantified with order-of-magnitude probabilities. The algorithm takes advantage of both the structure and the quantification of the network and presents a polynomial asymptotic complexity. Predict exhibits a conservative behavior in that it is always sound but not always complete. We provide sufficient conditions for completeness and present algorithms for testing these conditions and for computing a complete set of plausible values. We propose Predict as an efficient method to estimate probabilistic values and illustrate its use in conjunction with two known algorithms for probabilistic inference. Finally, we describe an application of Predict to plan evaluation, present experimental results, and discuss issues regarding its use with conditional logics of belief, and in the characterization of irrelevance.

UAI Conference 1994 Conference Paper

Action Networks: A Framework for Reasoning about Actions and Change under Uncertainty

• Adnan Darwiche
• Moisés Goldszmidt

This work proposes action networks as a semantically well-founded framework for reasoning about actions and change under uncertainty. Action networks add two primitives to probabilistic causal networks: controllable variables and persistent variables. Controllable variables allow the representation of actions as directly setting the value of specific events in the domain, subject to preconditions. Persistent variables provide a canonical model of persistence according to which both the state of a variable and the causal mechanism dictating its value persist over time unless intervened upon by an action (or its consequences). Action networks also allow different methods for quantifying the uncertainty in causal relationships, which go beyond traditional probabilistic quantification. This paper describes both recent results and work in progress.

UAI Conference 1994 Conference Paper

On the Relation between Kappa Calculus and Probabilistic Reasoning

• Adnan Darwiche
• Moisés Goldszmidt

We study the connection between kappa calculus and probabilistic reasoning in diagnosis applications. Specifically, we abstract a probabilistic belief network for diagnosing faults into a kappa network and compare the ordering of faults computed using both methods. We show that, at least for the example examined, the ordering of faults coincide as long as all the causal relations in the original probabilistic network are taken into account. We also provide a formal analysis of some network structures where the two methods will differ. Both kappa rankings and infinitesimal probabilities have been used extensively to study default reasoning and belief revision. But little has been done on utilizing their connection as outlined above. This is partly because the relation between kappa and probability calculi assumes that probabilities are arbitrarily close to one (or zero). The experiments in this paper investigate this relation when this assumption is not satisfied. The reported results have important implications on the use of kappa rankings to enhance the knowledge engineering of uncertainty models.

UAI Conference 1992 Conference Paper

Reasoning with Qualitative Probabilities Can Be Tractable

• Moisés Goldszmidt
• Judea Pearl

We recently described a formalism for reasoning with if-then rules that re expressed with different levels of firmness [18]. The formalism interprets these rules as extreme conditional probability statements, specifying orders of magnitude of disbelief, which impose constraints over possible rankings of worlds. It was shown that, once we compute a priority function Z+ on the rules, the degree to which a given query is confirmed or denied can be computed in O(log n`) propositional satisfiability tests, where n is the number of rules in the knowledge base. In this paper, we show that computing Z+ requires O(n2 X log n) satisfiability tests, not an exponential number as was conjectured in [18], which reduces to polynomial complexity in the case of Horn expressions. We also show how reasoning with imprecise observations can be incorporated in our formalism and how the popular notions of belief revision and epistemic entrenchment are embodied naturally and tractably.

AIJ Journal 1991 Journal Article

On the consistency of defeasible databases

• Moisés Goldszmidt
• Judea Pearl

We propose a norm of consistency for a mixed set of defeasible and strict sentences which, guided by a probabilistic interpretation of these sentences, establishes a clear distinction between exceptions, ambiguities and outright contradictions. A notion of entailment is then defined which represents a minimal core of beliefs that must follow from the database if one is committed to avoid inconsistencies. The paper establishes necessary and sufficient conditions for consistency, and provides a simple decision procedure for testing the consistency of a database or whether a given sentence is entailed by the database. It is also shown that if all sentences are of Horn type, consistency and entailment can be tested in polynomial time. Finally, we discuss procedures for reasoning with inconsistent databases and identifying sentences directly responsible for the inconsistency.

AAAI Conference 1991 Conference Paper

System-Z+: A Formalism for Reasoning with Variable-Strength Defaults

• Moisés Goldszmidt

We develop a formalism for reasoning with defaults that are expressed with different levels of firmness. Necessary and sufficient conditions for consistency are established, and a unique ranking of the rules is found, called Z+, which renders models as normal as possible subject to the consistency conditions. We provide the necessary machinery for testing consistency, computing the Z+ ranking and drawing the set of plausible conclusions it entails.

AAAI Conference 1990 Conference Paper

A Maximum Entropy Approach to Nonmonotonic Reasoning

• Moisés Goldszmidt

This paper describes a probabilistic approach to nonmonotonic reasoning which combines the principle of infinitesimal probabilities with that of maximum entropy, and which sanctions inferences similar to those produced by the principle of minimizing abnormalities. The paper provides a precise formalization of the consequences entailed by a defeasible knowledge base, develops the computational machinery necessary for deriving these consequences, and compares the behavior of the maximum entropy approach to those of e-semantics ([Pearl SSa]) and rational closure ([Lehmann 891).

UAI Conference 1989 Conference Paper

Deciding Consistency of Databases Containing Defeasible and Strict Information

• Moisés Goldszmidt
• Judea Pearl

We propose a norm of consistency for a mixed set of defeasible and strict sentences, based on a probabilistic semantics. This norm establishes a clear distinction between knowledge bases depicting exceptions and those containing outright contradictions. We then define a notion of entailment based also on probabilistic considerations and provide a characterization of the relation between consistency and entailment. We derive necessary and sufficient conditions for consistency, and provide a simple decision procedure for testing consistency and deciding whether a sentence is entailed by a database. Finally, it is shown that if al1 sentences are Horn clauses, consistency and entailment can be tested in polynomial time.