Transcript Sensitivity Analysis - Computer Science & Engineering

Sensitivity Analysis
Reference
 Bayesian Networks and Decision Graphs
Finn V. Jensen
 Expert Systems and Probabilistic Network Models
Enrique Castillo, Jose Manuel Gutierrez, and Ali D. Hadi
 Omniseer Project

Sensitivity Analysis
Given a Bayesian network and evidence e, and some
hypotheses h1 ,..., hn

Sensitivity to evidence

Sensitivity to parameter
Sensitivity to evidence

Which evidence is in favor of /against/irrelevant
for hi

Which evidence discriminate hi from h j ?
Sensitivity to evidence
How to measure the sensitivity

Normalized likelihoods
p ( e' | h )
, e'  e
p ( e)

Bayes factors
p(e | h )
p(e, h) p(h) p(h | e) p(e) p(h) p(h | e)(1  p(h))



p(e | h) p(h) p(e, h) p(h) p(h | e) p(e) p(h)(1  p(h | e))

Fraction of achieved probability
p ( h | e' )
, e'  e
p ( h | e)
Sensitivity to evidence
Definition
Let e be evidence and h a hypothesis. Suppose that we want to
investigate how sensitive the result p(h|e) is to the particular
set e.
We say that evidence e'  e is sufficient if p(h|e’) is almost
equal to p(h|e’). We then also say that e\e’ is redundant. The
term almost equal can be made precise by selecting a threshold 1
and requiring that p(h | e' )  1  1 . Note that p(h | e' ) is the
p ( h | e)
p ( h | e)
fraction between the two likelihood ratios.
e’ is minimal sufficient if it is sufficient, but no proper subset of
e’ is so.
e’ is crucial if it is a subset of any sufficient set.
e’ is important if the probability of h changes too much without
it. To be more precise, if p(h | e \ e' )  1  2 , where 2 is some
p ( h | e)
threshold.
Sensitivity to parameters
how much the posterior probability of some event of interest
changes with respect to the value of some parameter in the
Bayesian network
 We assume that the event of interest is the value of a target
variable. The parameter is either a conditional probability or an
unconditional prior probability

Sensitivity to parameters
Theorem and Corollaries

Theorm 1: Let BN be a Bayesian network over the universe U. Let t be a
parameter and let e be evidence entered in BN. Then, assuming
proportional scaling, we have p ( e)( t )  t  

Proof: The probability of an instantiation (x1,…,xn) is
n
n
i 1
i 1
p( x1 ,..., xn )   p( xi |  i )   ixi i .

Note that all the parameters appearing in the above product are associated
with different variables, and some of them may be specified numerically.
Thus p(x1,…,xn) is a monomial of degree less than or equal to the number
of symbolic nodes.
Sensitivity to parameters
Theorem and Corollaries


Corollary 1: Let BN be a Bayesian network over the universe U. Let t be a set of
parameter for different distributions, and let e be evidence entered into BN. Then,
assuming proportional scaling, P(e)(t) is a multi-linear polynomial over t
Proof: let t=(x,y). From the previous theorem, we have
p ( e)( x, y )   x ( y ) x   x ( y )   y ( x ) y   y ( x )
Let x  0, yields  x ( y )   y (0) y   y (0)
(1)
Let x  1, yields  x ( y )   x ( y )   y (1) y   y (1)
By (1),  x ( y )   y (1) y   y (1)   y (0) y   y (0)
( 2)
(3)
combing (1)and (3), get
p ( e)( x, y )  (( y (1)   y (0)) y   y (1)   y (0)) x   y (0) y   y (0)
is
p ( e)( x, y )  xy  x  y  

If we have more than two parameters, we let t=(x,y), where y is a set of parameters.
And repeat the arguments above.
Sensitivity to parameters
Theorem and Corollaries


Corollary 2: Let BN be a Bayesian network over the universe U. Let t be
a set of parameters for different distributions. Let a be a state of
and let e be evidence. Then P(a|e)(t) is a fraction of two multi-linear
polynomials over t.
p ( a , e)
Proof: Corollary 1 and fundamental rule
p ( a | e) 
p ( e)
Sensitivity to parameters
One-way sensitivity analysis


Let t be a parameter for BN and let e be evidence. Let a be a state of the
target node. In one-way sensitivity analysis, we wish to determine p(e) and
p(a,e) as functions of t.
Let t0 be the initial value of t.
p(e)( t0 )  t0   , p(a, e)( t0 )   ' t0   '

Let t1 be the second value of t
p(e)(t1 )  t1   , p(a, e)(t1 )   ' t1   '

Combing Corollary 2, we have
p(a | e)( t0 ) 
't   '
t  
Sensitivity Analysis in Our
Project
 Project
Introduction
Project Overview
Massive
Data
Events
Messages
Tasks
Documents
Bayesian Networks
<Date>2002-09-20</Date>
<Person>John Doe</Person>
<Place>London</Place>
…
Tagged messages
<Date>2002-09-27</Date>
<Person>John Doe</Person>
Matcher
BN
Fragments
…
Modified Text
Instantiated Fragments
Bayesian
Reasoning Service
Value of Information
Composer
Situation Specific
Scenarios
Sensitivity Analyzer
Surprise Detector
Bayesian Network Fragment Matching Example
1) Report Date: 1
April, 2003. FBI: Abdul
Ramazi is the owner of
the Select Gourmet
Foods shop in
Springfield Mall.
Springfield, VA. (Phone
number 703-659.2317).
First Union National
Bank lists Select
Gourmet Foods as
holding account number
1070173749003. Six
checks totaling $35,000
have been deposited in
this account in the past
four months and are
recorded as having been
drawn on accounts at the
Pyramid Bank of Cairo,
Egypt and the Central
Bank of Dubai, United
Arab Emirates. Both of
these banks have just
been listed as possible
conduits in money
laundering schemes.
<Protege:Person
rdf:about="&Protege;Omniseer_00135"
…..
Protege:familyName="Ramazi"
Protege:givenName="Abdulla“rrdfs:label="Abdull
a Ramazi"/>
…..
<Protege:Bank
rdf:about="&Protege;Omniseer_00614"
Protege:alternateName="Pyramid Bank of Cairo"
rdfs:label="Pyramid Bank of Cairo">
<Protege:address
rdf:resource="&Protege;Omniseer_00594"/>
<Protege:note
rdf:resource="&Protege;Omniseer_00625"/>
</Protege:Bank>
….
<Protege:Report
rdf:about="&Protege;Omniseer_00626"
Protege:abstract="Ramazi's deposit in the past 4
months (1)"
rdfs:label="Ramazi's deposit in the past 4 months
(1)">
PartiallyInstantiated
Bayesian
Network
Fragment
<Protege:reportedFrom
rdf:resource="&Protege;Omniseer_00501"/>
<Protege:detail
rdf:resource="&Protege;Omniseer_00602"/>
<Protege:detail
rdf:resource="&Protege;Omniseer_00612"/>
</Protege:Report>
</rdf:RDF>
BN Fragment
Repository
Bayesian Network Fragment Composition Example
.....
+
Fragments
Situation-Specific Scenario
Protégé overview
What
is Protégé ?
A tool which allows the user to:
construct a domain ontology
customize data entry forms
enter data
OpenCyc overview
What is OpenCyc ?
o
The open source version of the Cyc
technology
o
World's largest and most complete general
knowledge base and commonsense reasoning
engine
OpenCyc overview --- cont.
Where can we use OpenCyc ?
o
o
o
o
speech understanding
database integration
rapid development of an ontology in a vertical
area
email prioritizing, routing, summarization, and
annotating
OpenCyc overview --- cont.
What does OpenCyc
look like ?
OpenCyc overview --- cont.
More Detail Here
RDF overview
What is RDF?
 Stands
for Resource Description Framework
 Recommended
(W3C)
 Model
by the World Wide Web Consortium
meta-data about the resources of the web
RDF overview --- Cont.
What does RDF file look like?
Basically, there are two kinds of file in RDF system

RDFS file
--- The schema file

RDF file
--- The file containing all instances
RDF overview --- Cont.
RDFS file
<?xml version='1.0' encoding='ISO-8859-1'?>
<!DOCTYPE rdf:RDF [
<!ENTITY rdf 'http://www.w3.org/1999/02/22-rdf-syntax-ns#'> <!ENTITY a
'http://protege.stanford.edu/system#'>
<!ENTITY Protege
'http://protege.stanford.edu/Protege#'>
<!ENTITY rdfs 'http://www.w3.org/TR/1999/PR-rdfschema-19990303#'>]>
<rdf:RDF xmlns:rdf="&rdf;"
xmlns:a="&a;"
xmlns:Protege="&Protege;"
xmlns:rdfs="&rdfs;">
<rdfs:Class rdf:about="&Protege;Action"
rdfs:label="Action">
<rdfs:subClassOf rdf:resource="&rdfs;Resource"/>
</rdfs:Class>
<rdfs:Class rdf:about="&Protege;Address" rdfs:label="Address">
<rdfs:subClassOf rdf:resource="&Protege;Location"/>
</rdfs:Class>
<rdfs:Class rdf:about="&Protege;Agency" rdfs:label="Agency">
<rdfs:subClassOf rdf:resource="&Protege;Legal_Entity"/>
</rdfs:Class>
RDF overview --- Cont.
RDF file
<rdf:RDF xmlns:rdf="&rdf;"
xmlns:Protege="&Protege;"
xmlns:rdfs="&rdfs;">
<Protege:Landmines rdf:about="&Protege;Omniseer_00088"
Protege:mines_type="arid mines" Protege:quantity="16"
rdfs:label="arid
mines"/>
<Protege:Military_Reservation rdf:about="&Protege;Omniseer_00114"
Protege:name="Camp George West"
rdfs:label="Camp George
West"/>
<Protege:Date rdf:about="&Protege;Omniseer_00118"
Protege:day="20"
Protege:full_date="4/20/2003"
Protege:month="4"
Protege:year="2003"
rdfs:label="4/20/2003"/>
Protégé GUI—Class Design
Protégé GUI—Instance View
Sensitivity Analysis in Our Project
Sensitivity analysis assesses how much the posterior probability
of some event of interest changes with respect to the value of
some parameter in the model
 We assume that the event of interest is the value of a target
variable. The parameter is either a conditional probability or an
unconditional prior probability
 If the sensitivity of the target variable having a particular value
is low, then the analyst can be confident in the results, even if
the analyst is not very confident in the precise value of the
parameter
 If the sensitivity of the target variable to a parameter is very
high, it is necessary to inform the analyst of the need to qualify
the conclusion reached or to expend more resources to become
more confident in the exact value of the parameter

Example: Case Study #4
Computing Sensitivity 2
Example: Case Study #4
Computing Sensitivity
In the context of the information already acquired, i.e., travel to dangerous places,
large transfers of money, etc., the parameter that links financial irregularities to
being a suspect is much more important for assessing the belief in Ramazi being a
terrorist than the parameter that links dangerous travel to being a suspect. The
analyst may want to concentrate on assessing the first parameter precisely.
Sensitivity Analysis: Formal Definition
Let the evidence be a set of findings: e  {Vi  vi | i  I }
 Let t be a parameter in the situation-specific scenario
 Then, P (e)(t )  t   [Castillo et al., 1997; Jensen, 2000]
 α and β can be determined by computing P(e) for two values
of t
 More generally, if t is a set of parameters, then P(e)(t) is a
linear function in each parameter in t, i.e., it is a multi-linear
function of t
 Recall that P(a | b) P(a, b) P(b)
 Then, P( A  a | e)(t )  P( A  a, e)(t ) P(e)(t )
 We can therefore compute the sensitivity of a target variable V
to a parameter t by repeating the same computation with two
values for the evidence set, viz. e and e  {V  v}

Algorithm and Implementation

Bucket Elimination

Goal-oriented Symbolic propagation
Differential Approach to Inference in BN
A Differential Approach to Inference in Bayesian Networks
Adnan Darwiche
 A Computational Architecture for N-way Sensitivity
Analysis of Bayesian Networks
Veerle M. H. Coupé, Finn V. Jensen, Uffe Kjærulff & Linda C.
van der Gaag
