Author name cluster

Hei Chan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

ICAPS Conference 2007 Conference Paper

Online Planning for Resource Production in Real-Time Strategy Games

Hei Chan
Alan Fern
Soumya Ray
Nick Wilson
Chris Ventura

Planning in domains with temporal and numerical properties is an important research problem. One application of this is the resource production problem in real-time strategy (RTS) games, where players attempt to achieve the goal of producing a certain amount of resources as fast as possible. In this paper, we develop an online planner for resource production in the RTS game of Wargus, where the preconditions and effects of the actions obey many properties that are common across RTS games. Our planner is based on a computationally efficient action-selection mechanism, which at each decision epoch creates a possibly sub-optimal concurrent plan from the current state to the goal and then begins executing the initial set of actions. The plan is formed via a combination of means-ends analysis, scheduling, and a bounded search over sub-goals that are not required for goal achievement but may improve makespan. Experiments in the RTS game of Wargus show that the online planner is highly competitive with a human expert and often performs significantly better than state-of-the-art planning algorithms for this domain.

Details

UAI Conference 2006 Conference Paper

On the Robustness of Most Probable Explanations

Hei Chan
Adnan Darwiche

In Bayesian networks, a Most Probable Explanation (MPE) is a complete variable instantiation with a highest probability given the current evidence. In this paper, we discuss the problem of finding robustness conditions of the MPE under single parameter changes. Specifically, we ask the question: How much change in a single network parameter can we afford to apply while keeping the MPE unchanged? We will describe a procedure, which is the first of its kind, that computes this answer for each parameter in the Bayesian network variable in time O(n exp(w)), where n is the number of network variables and w is its treewidth.

Details

UAI Conference 2005 Conference Paper

On Bayesian Network Approximation by Edge Deletion

Adnan Darwiche
Hei Chan
Arthur Choi

We consider the problem of deleting edges from a Bayesian network for the purpose of simplifying models in probabilistic inference. In particular, we propose a new method for deleting network edges, which is based on the evidence at hand. We provide some interesting bounds on the KL-divergence between original and approximate networks, which highlight the impact of given evidence on the quality of approximation and shed some light on good and bad candidates for edge deletion. We finally demonstrate empirically the promise of the proposed edge deletion technique as a basis for approximate inference.

Details

AIJ Journal 2005 Journal Article

On the revision of probabilistic beliefs using uncertain evidence

Hei Chan
Adnan Darwiche

We revisit the problem of revising probabilistic beliefs using uncertain evidence, and report results on several major issues relating to this problem: how should one specify uncertain evidence? How should one revise a probability distribution? How should one interpret informal evidential statements? Should, and do, iterated belief revisions commute? And what guarantees can be offered on the amount of belief change induced by a particular revision? Our discussion is focused on two main methods for probabilistic revision: Jeffrey's rule of probability kinematics and Pearl's method of virtual evidence, where we analyze and unify these methods from the perspective of the questions posed above.

Details DOI

IJCAI Conference 2005 Conference Paper

Sensitivity Analysis in Markov Networks

Hei Chan
Adnan

This paper explores the topic of sensitivity analysis in Markov networks, by tackling questions similar to those arising in the context of Bayesian networks: the tuning of parameters to satisfy query constraints, and the bounding of query changes when perturbing network parameters. Even though the distribution induced by a Markov network corresponds to ratios of multi-linear functions, whereas the distribution induced by a Bayesian network corresponds to multi-linear functions, the results we obtain for Markov networks are as effective computationally as those obtained for Bayesian networks. This similarity is due to the fact that conditional probabilities have the same functional form in both Bayesian and Markov networks, which turns out to be the more influential factor. The major difference we found, however, is in how changes in parameter values should be quantified, as such parameters are interpreted differently in Bayesian networks and Markov networks.

PDF

UAI Conference 2004 Conference Paper

Sensitivity Analysis in Bayesian Networks: From Single to Multiple Parameters

Hei Chan
Adnan Darwiche

Previous work on sensitivity analysis in Bayesian networks has focused on single parameters, where the goal is to understand the sensitivity of queries to single parameter changes, and to identify single parameter changes that would enforce a certain query constraint. In this paper, we expand the work to multiple parameters which may be in the CPT of a single variable, or the CPTs of multiple variables. Not only do we identify the solution space of multiple parameter changes that would be needed to enforce a query constraint, but we also show how to find the optimal solution, that is, the one which disturbs the current probability distribution the least (with respect to a specific measure of disturbance). We characterize the computational complexity of our new techniques and discuss their applications to developing and debugging Bayesian networks, and to the problem of reasoning about the value (reliability) of new information.

Details

IJCAI Conference 2003 Conference Paper

On the Revision of Probabilistic Beliefs using Uncertain Evidence

Hei Chan
Adnan Darwiche

We revisit the problem of revising probabilistic beliefs using uncertain evidence, and report results on four major issues relating to this problem: How to specify uncertain evidence? How to revise a distribution? Should, and do, iterated belief revisions commute? And how to provide guarantees on the amount of belief change induced by a revision? Our discussion is focused on two main methods for probabilistic revision: Jeffrey's rule of probability kinematics and Pearl's method of virtual evidence, where we analyze and unify these methods from the perspective of the questions posed above.

PDF

UAI Conference 2003 Conference Paper

Reasoning about Bayesian Network Classifiers

Hei Chan
Adnan Darwiche

Bayesian network classifiers are used in many fields, and one common class of classifiers are naive Bayes classifiers. In this paper, we introduce an approach for reasoning about Bayesian network classifiers in which we explicitly convert them into Ordered Decision Diagrams (ODDs), which are then used to reason about the properties of these classifiers. Specifically, we present an algorithm for converting any naive Bayes classifier into an ODD, and we show theoretically and experimentally that this algorithm can give us an ODD that is tractable in size even given an intractable number of instances. Since ODDs are tractable representations of classifiers, our algorithm allows us to efficiently test the equivalence of two naive Bayes classifiers and characterize discrepancies between them. We also show a number of additional results including a count of distinct classifiers that can be induced by changing some CPT in a naive Bayes classifier, and the range of allowable changes to a CPT which keeps the current classifier unchanged.

Details

UAI Conference 2001 Conference Paper

When do Numbers Really Matter?

Hei Chan
Adnan Darwiche

Common wisdom has it that small distinctions in the probabilities quantifying a Bayesian network do not matter much for the resultsof probabilistic queries. However, one can easily develop realistic scenarios under which small variations in network probabilities can lead to significant changes in computed queries. A pending theoretical question is then to analytically characterize parameter changes that do or do not matter. In this paper, we study the sensitivity of probabilistic queries to changes in network parameters and prove some tight bounds on the impact that such parameters can have on queries. Our analytical results pinpoint some interesting situations under which parameter changes do or do not matter. These results are important for knowledge engineers as they help them identify influential network parameters. They are also important for approximate inference algorithms that preprocessnetwork CPTs to eliminate small distinctions in probabilities.

Details