Transcript Document

On the Role of Multiply
Sectioned Bayesian
Networks to Cooperative
Multiagent Systems
Presented By: Yasser EL-Manzalawy
Reference
• Y. Xiang and V. Lesser, On the Role of
Multiply Sectioned Bayesian Networks to
Cooperative Multiagent Systems. IEEE
Trans. Systems, Man, and Cybernetics-Part
A, Vol.33, No.4, 489-501, 2003
Structure of the presentation
•
•
•
•
•
Motivation
Introduction of the background knowledge
Detail information about the constraints
A small set of high level choices
How those choices logically imply all the
constraints
Motivation
• What’s an agent?
– Program that takes sensory input from the
environment, and produces output actions that
affect it.
– If the agent works in uncertain environment,
then the agent can represent its believes about
the environment as a Bayesian Network.
Motivation
• What’s a Multi-Agent System (MAS)?
– Multi-Agent System is a set of agents and the
environment they interact.
environment
Agent
Agent
Agent
Agent
Agent
Agent
Motivation
• In MAS, each agent can only observe and
reason about a subdomain.
• Agents are assumed to cooperate in order to
achieve a common global goal.
• For uncertain domains, agent believes can
be represented as a BN (subnet).
Several Issues Arise!
Motivation
• How should the domain be partitioned into subdomains?
• How should each agent represent its knowledge about a
subdomain?
• How should the knowledge of each agent relate to that of
others?
• How should the agents be organized in their activities?
• What information should they exchange and how, in order
to accomplish their task with a limited amount of
communication?
• Can they achieve the same level of accuracy in estimating
the state of the domain as that of a single centralized
agent?
Motivation
• MSBN provides a solution to these issues.
• Applying MSBN implies some technical
constraints.
Are these constraints necessary?
Example
Introduction and Background
• Definition: A Bayesian Network is a triplet
(V,G,P) where V is a set of domain variables, G
is a DAG whose nodes are labeled by elements of
V , and P is a joint probability distribution (jpd)
over V, specified in terms of a distribution for
each variable x V conditioned on the parents
 (x ) of in G.
Introduction and Background
• Definition: Let G = (V,E) be a connected graph
sectioned into subgraphs {Gi  (Vi , Ei )}. Let the
subgraphs be organized into an undirected tree
 where each node is uniquely labeled by a Gi
and each link between Gk and Gm is labeled by the
non-empty interface Vk  Vm such that for each
i and j , Vi  V j is contained in each subgraph on
the path between Gi and G j in . Then  is a
hypertree over G. Each Gi is a hypernode and
each interface is a hyperlink.
Introduction and Background
Introduction and Background
hypernode
a, b
hyperlink
Introduction and Background
• Definition: Let G be a directed graph such that a
hypertree over G exists. A node x contained in
more than one subgraph with its parents  (x) in G
is a d-sepnode if there exists at least one
subgraph that contains  (x) . An interface I is a
d-sepset if every x  I is a d-sepnode.
Introduction and Background
• Definition: A hypertree MSDAG , G   G
where each G is a DAG, is a connected DAG
such that (1) there exists a hypertree  over ,
and (2) each hyperlink in  is a d-sepset.
i
i
i
Introduction and Background
• Note: DAGs in MSDAG tree may be
multiply connected.
Introduction and Background
• A potential over a set of variables is an
non-negative distribution of at least one
positive parameter.
• One can always convert a potential into a
conditional probability by dividing each
potential value with a proper sum: an
operation termed normalization.
• A uniform potential is one with all its
potential values being 1.
Introduction and Background
Introduction and Background
• Definition: An MSBN is a triplet (V,G,P). V   V is the
domain where each V is a set of variables. G   G (a
hypertree MSDAG) is the structure where nodes of each
DAG G are labeled by elements of V . Let x be a
variable and  (x) be all the parents of x in G. For each x ,
exactly one of its occurrences (in a G containing {x}   ( x) )
is assigned P( x /  ( x)) , and each occurrence in other DAGs
is assigned a uniform potential. P   P is the jpd, where
each P is the product of the potentials associated with
nodes in G . A triplet (V , G , P ) is called a subnet of M. Two
subnets S and S are said to be adjacent if G and G are
adjacent on the hypertree MSDAG
i
i
i
i
i
i
i
i
i i
i
i
i
i
j
i
i
i
j
Introduction and Background
•
•
•
•
Communication Graph
Cluster Graph
Junction Graph
Junction Tree
Introduction and Background
Cluster
Separator
Introduction and Background
d,e
d,f
d
d
d
b,c,d
d
d
d
d,g
(a) Strong Degenerate Loop
d,e,i
d
d,i
b,c,d,i
d
a,b
a,e
e
b
b,c,d
c
c,e
(c) Strong Nondegenerate Loop
d,f,h
a,b,f
d,h
b,f
d,g,h
b,c,d,f
(b) Weak Degenerate Loop
a
a,f
a,e,f
e,f
c,f
c,e,f
(d) Week Nondegenerate Loop
High Level Choices (Basic Commitments)
• BC1: Each agent’s belief is represented by
Bayesian probability
• BC2: Ai and Aj can communicate directly only
with their intersecting variables
• BC3: A simpler agent organization, i.e., tree, is
preferred when degenerate loops exist in the CG
• BC4: A DAG is used to structure each individual
agent’s knowledge
• BC5: Within each agent’s subdomain, the JPD is
consistent with the agent’s belief. For shared
nodes, the JPD supplements each agent’s
knowledge with others’
Seven Constraints
1. Each agent’s belief is represented by Bayesian
probability
2. The domain is decomposed into subdomains
3. Subdomains are organized into a hyptertree
structure
4. The dependency structure of each subdomain is
represented by a DAG
5. The union of DAGs for all subdomains is a
connected DAG
6. Each hyperlink is a d-sepset
7. The JPD can be expressed as in definition of
MSBN
• Lemma 9: Let s be a strictly positive initial state of Mas3. There
exists an infinite set S. Each element s’∈S is an initial state of Mas3
identical to s in P(a), P(b|a), P(c|a) but distinct in P(d|b,c) such that
the message P2(b|d=d0) produced from s’ is identical to that
produced from s, and so is the message P2(c|d=d0)
A0
a
a
a,b
b
b
a,c
c
c
A2
d
b,c,d
Figure 1
Mas3: a multiagent
system of 3 agents.
A1
Proof: Denote P2(b=b0|d=d0) from state s by P2(b0|d0), P2’(b=b0|d=d0) from
state s’ by P2’(b0|d0). P2(b0|d0) can be expanded as:
 P (b , d ) 
P2 (b 0 , d 0 )
P2 (b 0 | d 0 ) 
 1  2 1 0 
P2 (b 0 , d 0 )  P2 (b1 , d 0 )  P2 (b 0 , d 0 ) 
 P (b , c , d )  P2 (b1 , c1 , d 0 ) 
 1  2 1 0 0

 P2 (b 0 , c 0 , d 0 )  P2 (b 0 , c1 , d 0 ) 
1
1

P (d | b , c )P (b , c )  P2 (d 0 | b1 , c1 )P2 (b1 , c1 ) 
 1  2 0 1 0 2 1 0

 P2 (d 0 | b 0 , c 0 )P2 (b 0 , c 0 )  P2 (d 0 | b 0 , c1 )P2 (b 0 , c1 ) 
1

P2' (d 0 | b1 , c 0 )P2 (b1 , c 0 )  P2' (d 0 | b1 , c1 )P2 (b1 , c1 ) 
'
P2 (b 0 | d 0 )  1  '

'
 P2 (d 0 | b 0 , c 0 )P2 (b 0 , c 0 )  P2 (d 0 | b 0 , c1 )P2 (b 0 , c1 ) 
1
For P2(b|d0)=P2’(b|d0), we have:
P2' (d 0 | b1 , c 0 )P2 (b1 , c 0 )  P2' (d 0 | b1 , c1 )P2 (b1 , c1 )
P2 (b1 , d 0 )

P2' (d 0 | b 0 , c 0 )P2 (b 0 , c 0 )  P2' (d 0 | b 0 , c1 )P2 (b 0 , c1 )
P2 (b 0 , d 0 )
Similarly,
P2' (d 0 | b 0 , c1 )P2 (b 0 , c1 )  P2' (d 0 | b1 , c1 )P2 (b1 , c1 )
P2 (c1 , d 0 )

P2' (d 0 | b 0 , c 0 )P2 (b 0 , c 0 )  P2' (d 0 | b1 , c 0 )P2 (b1 , c 0 ) P2 (c 0 , d 0 )
Because P2’(d|b,c) has 4 independent parameters but is constrained by only two
equations, it has infinitely many solutions.
 Lemma 10: Let P and P’ be strictly positive probability distributions over the
DAG of Figure 1 such that they are identical in P(a), P(b|a) and P(c|a) but
distinct in P(d|b,c). Then P(a|d=d0) is distinct from P’(a|d=d0) in general
Proof: The following can be obtained from P and P’:
P(a | d 0 )   P(a | b, c) P(b, c | d 0 )
P (a | d ) 
 P(a, b, c | d)
b,c
b. c
P' (a | d 0 )   P' (a | b, c) P' (b, c | d 0 )
P(a , b, c, d) P(a , b, c, d )P(b, c, d )

b. c
P (d )
P(b, c, d )P(d)
If P(b,c|d0) ≠ P’(b,c|d0), then in general  P(a | b, c, d)P(b, c | d)
 P(a | b, c)P(b, c | d )
P(a|d0) ≠P’(a|d0)
P (b, c | d 0 ) 
P(a , b, c | d ) 
P ( d 0 | b, c ) P (b, c )
P ( d 0 | b, c ) P (b, c )

P(d 0 )
 P(d 0 | b, c) P(b, c)
b ,c
P ' (b, c | d 0 ) 
P ' ( d 0 | b, c ) P (b, c )
P ' ( d 0 | b, c ) P (b, c )

P' (d 0 )
 P' (d 0 | b, c) P(b, c)
b ,c
Because P(d|b,c) ≠P’(d|b,c), in general, it is the case that P(b,c|d0) ≠P’(b,c|d0).
Do you agree???
Theorem 11 : Message passing in Mas3 cannot be coherent in general, no
matter how it is performed
Proof:
1.
By Lemma 9, P2(b|d=d0) and P2(c|d=d0) are insensitive to the initial
states and hence the posteriors P0(a|d=d0) computed from the
messages can not be sensitive to the initial states either
2. However, by Lemma 10, the posterior should be different in general
given different initial states
Hence, correct belief updating cannot be achieved in Mas3
Insight
A0
a
a,b
b
A2
a,c
c
b,c,d
Figure 1
A1


Correct inference requires P(b,c|d0)
However, nondegenerate loop results
in the passing of the marginals of
P(b,c|d0), i.e., P(b|d=d0) and P(c|d=d0)
• We can generalize this analysis to an arbitrary, strong
nondegenerate loop of length 3
• Further generalize this analysis to an arbitrary, strong
nondegenerate loop of length K ≥ 3
Conclusion
Corollary 12: Message passing in a cluster graph
with nondegenerate loops cannot be coherent in
general, no matter how it is performed
•Another conclusion without proof:
A cluster graph with only degenerate loops can
always be treated by first breaking the loops at
appropriate separators. The resultant is a cluster tree
Therefore, we have:
Proposition 13: Let a multiagent system be one that
observes BC 1 through BC 3. Then a tree organization
of agents should be used
Five Basic Commitments
Seven Constraints
1.
Each agent’s belief is
represented by Bayesian
probability

BC1: Each agent’s belief is represented by
Bayesian probability

BC2: Ai and Aj can communicate directly
only with their intersecting variables
2.
The domain is decomposed into
subdomains with RIP

BC3: A simpler agent organization, i.e., tree,
is preferred when degenerate loops exist in
the CG
3.
Subdomains are organized into a
hyptertree structure

BC4: A DAG is used to structure each
individual agent’s knowledge
4.
The dependency structure of
each subdomain is represented
by a DAG

BC5: Within each agent’s subdomain, the
JPD is consistent with the agent’s belief. For
shared nodes, the JPD supplements each
agent’s knowledge with others’
5.
The union of DAGs for all
subdomains is a connected DAG
6.
Each hyperlink is a d-sepset
7.
The JPD can be expressed as in
definition of MSBN
Five Basic Commitments

BC1: Each agent’s belief is represented by
Bayesian probability

BC2: Ai and Aj can communicate directly
only with their intersecting variables

BC3: A simpler agent organization, i.e., tree,
is preferred when degenerate loops exist in
the CG

BC4: A DAG is used to structure each
individual agent’s knowledge

BC5: Within each agent’s subdomain, the
JPD is consistent with the agent’s belief. For
shared nodes, the JPD supplements each
agent’s knowledge with others’
Seven Constraints
1.
Each agent’s belief is represented by
Bayesian probability
2.
The domain is decomposed into
subdomains with RIP
3.
Subdomains are organized into a
hyptertree structure
4.
The dependency structure of each
subdomain is represented by a DAG
5.
The union of DAGs for all
subdomains is a connected DAG
6.
Each hyperlink is a d-sepset
7.
The JPD can be expressed as in
definition of MSBN
•
Proposition 17: Let a multiagent system over V be
constructed following BC 1 through BC 4. Then
each subdomain Vi is structured as a DAG over Vi
and the union of these DAGs is a connected DAG
over V
•
•
•
Proof:
The connectedness is implied by Proposition 6
If the union of subdomain DAGs is not a DAG, then it has a
directed loop. This contradicts the acyclic interpretation of
dependence in individual DAG models
Five Basic Commitments

BC1: Each agent’s belief is represented by
Bayesian probability

BC2: Ai and Aj can communicate directly
only with their intersecting variables

BC3: A simpler agent organization, i.e., tree,
is preferred when degenerate loops exist in
the CG

BC4: A DAG is used to structure each
individual agent’s knowledge

BC5: Within each agent’s subdomain, the
JPD is consistent with the agent’s belief. For
shared nodes, the JPD supplements each
agent’s knowledge with others’
Seven Constraints
1.
Each agent’s belief is represented by
Bayesian probability
2.
The domain is decomposed into
subdomains with RIP
3.
Subdomains are organized into a
hyptertree structure
4.
The dependency structure of each
subdomain is represented by a DAG
5.
The union of DAGs for all
subdomains is a connected DAG
6.
Each hyperlink is a d-sepset
7.
The JPD can be expressed as in
definition of MSBN
•
•
•
Theorem 18: Let Ψ be a hypertree over a directed graph
G=(V, E). For each hyperlink I which splits Ψ into 2
subtrees over U  V and W  V respectively, U \ I and W
\ I are d-separated by I iff each hyperlink in Ψ is a dsepset
Proposition 14: Let a multiagent system be one that
observes BC 1 through BC 3. Then a junction tree
organization of agents must be used
Proposition 19: Let a multiagent system be constructed
following BC 1 through BC 4. Then it must be structured
as a hypertree MSDAG
Proof of Proposition 19:
From BC 1 through BC 4, it follows that each
subdomain should be structured as a DAG and the
entire domain should be structured as a connected
DAG (Proposition 17). The DAGs should be
organized into a hypertree (Proposition 14). The
interface between adjacent DAGs on the hypertree
should be a d-sepset (Theorem 18). Hence, the
multiagent system should be structured as a
hypertree MSDAG (Definition 3)
Five Basic Commitments

BC1: Each agent’s belief is represented by
Bayesian probability

BC2: Ai and Aj can communicate directly
only with their intersecting variables

BC3: A simpler agent organization, i.e., tree,
is preferred when degenerate loops exist in
the CG

BC4: A DAG is used to structure each
individual agent’s knowledge

BC5: Within each agent’s subdomain, the
JPD is consistent with the agent’s belief. For
shared nodes, the JPD supplements each
agent’s knowledge with others’
Seven Constraints
1.
Each agent’s belief is represented by
Bayesian probability
2.
The domain is decomposed into
subdomains with RIP
3.
Subdomains are organized into a
hyptertree structure
4.
The dependency structure of each
subdomain is represented by a DAG
5.
The union of DAGs for all
subdomains is a connected DAG
6.
Each hyperlink is a d-sepset
7.
The JPD can be expressed as in
definition of MSBN
Conclusion
Theorem 22: Let a multiagent system be
constructed following BC 1 through BC 5.
Then it must be represented as a MSBN or
some equivalent.