Qualitative Probabilisti Networks
Silja Renooij a;?;
, Linda C. van der Gaag a;?
and
Simon Parsons b;??
a
Institute of Information and ComputingS ien es, Utre ht University,
P.O. Box 80.089, 3508 TB Utre ht, TheNetherlands
b
Department of Computer S ien e, University of Liverpool,
Chadwi kBuilding, Liverpool L69 7ZF, United Kingdom
Abstra t
Qualitative probabilisti networks arequalitative abstra tionsof probabilisti net-
works,summarisingprobabilisti in uen esbyqualitativesigns.Asqualitativenet-
worksmodelin uen esatthelevelofvariables,knowledgeaboutprobabilisti in u-
en es thathold onlyforspe i values annotbe expressed.The results omputed
from a qualitative network, as a onsequen e, an be weaker than stri tly ne es-
sary and may in fa t be rather uninformative. We extend the basi formalism of
qualitative probabilisti networks by providing forthe in lusionof ontext-spe i
informationaboutin uen esand showthat exploitingthisinformationuponinfer-
en ehasthe abilityto forestallunne essarilyweak results.
Key words: probabilisti reasoning,qualitative reasoning, ontext-spe i
independen e,non-monotoni ity
1 Introdu tion
Probabilisti networks have be ome widely a epted as pra ti al representa-
tionsof knowledgeforreasoning underun ertainty. They ombinea graphi al
?
This resear h has been (partly) supported by the Netherlands Organisation for
S ienti Resear h(NWO).
??
This work waspartly fundedbytheEPSRCundergrant GR/L84117.
Correspondingauthor.
Email addresses: silja s.uu.nl(SiljaRenooij),linda s.uu.nl(LindaC.
vander Gaag),s.d.parsons s .liv.a .uk(SimonParsons).
tween them, with ( onditional) probabilities that represent the un ertainties
involved[17℄.Morespe i ally,thegraphi alrepresentationtakestheformofa
dire tedgraph whereea h variablerepresents avariable,andanar expresses
a possible probabilisti dependen e between the variables; these dependen es
are quanti ed bya onditionalprobabilitydistributionfor ea hvariablegiven
the possible ombinations of values for its prede essors in the digraph. For
reasoning with these probabilities in a mathemati ally orre t way, powerful
algorithmsareavailable.Appli ationsofprobabilisti networks anbefoundin
su h eldsas(medi al)diagnosisandprognosis, planning,monitoring,vision,
informationretrieval, naturallanguagepro essing, and e- ommer e.
Qualitative probabilisti networks are qualitativeabstra tions of probabilisti
networks[21℄,introdu edforprobabilisti reasoning inaqualitativeway.Just
likeaprobabilisti network,aqualitativenetworken odesstatisti alvariables
and the probabilisti relationships between them in a dire ted a y li graph.
Ea hvariableAinthisdigraphon eagainrepresentsavariable.Anar A!B
again expresses a probabilisti in uen e of the variable A on the probability
distributionofthevariableB.Ratherthanquanti edby onditionalprobabil-
itiesas in a probabilisti network, however, the in uen e is summarised by a
qualitativesign. This sign indi ates the dire tionof shift in B's ( umulative)
probability distribution that would be o asioned by an observation for A.
For example, a positive in uen e of A on B expresses that observing higher
values for A renders higher values for B more likely. The signs of a qualita-
tive network have a well-de ned foundation in the mathemati al on ept of
sto hasti dominan e. Building upon this foundation, it is possible to reason
with qualitative signs in a mathemati ally orre t way. To this end, an eÆ-
ient algorithm, based upon the idea of propagating and ombining signs, is
available [5℄.
Qualitativeprobabilisti networks anplay animportantroleinthe onstru -
tion of probabilisti networks for real-life appli ation domains. While on-
stru ting the digraph of a probabilisti network requires onsiderable e ort,
itisgenerally onsideredfeasible. The assessment of allprobabilities required
is a mu h harder task, espe ially if it has to be performed with the help
of human experts. The quanti ation task is, in fa t, often referred to as a
major obsta le in building a probabilisti network [8,10℄. Assessment of the
signs fora qualitativeprobabilisti network tendsto require onsiderably less
e ort fromthe domain experts, however [5℄. Now, by eli itingsigns from do-
main experts for the digraphof a probabilisti network under onstru tion,a
qualitativeprobabilisti network isobtained. This qualitativenetwork an be
used to study and validate the reasoning behaviour of the network prior to
probability assessment. The signs an further be used as onstraints on the
probabilities tobe assessed [7,13℄.
mainatthe highlevelofvariables,asopposed toprobabilisti networkswhere
un ertainties are represented atthe level of the variables'values. Due tothis
oarselevelofrepresentation detail,reasoningwith aqualitativeprobabilisti
networkoftenleadstoresultsthatareweakerthanstri tly ne essaryandmay
infa tberatheruninformative.Tobeable tofullyexploit aqualitativeprob-
abilisti network asoutlinedabove,we feelthat itshould apture and exploit
asmu hqualitativeinformationfromtheappli ationdomainaspossible.First
introdu edby M.P. Wellman [21℄and laterextended byM. Henrionand M.J.
Druzdzel [5,6,9℄, qualitative networks have been re ned to enhan e their ex-
pressiveness,by variousresear hers.S.Parsons[14,16℄introdu edthe on ept
of qualitative derivative where the in uen e of a variable A on a variable B
is summarised by a set of signs, one for ea h value of B; he also studied the
use of other approa hes to un ertain reasoning, su h as order-of-magnitude
reasoning, within qualitativeprobabilisti networks [15℄. S. Renooij and L.C.
vander Gaag[18℄ have enhan edqualitativeprobabilisti networksby adding
a qualitativenotion of strength. Renooij et al. [19℄ further fo used onidenti-
fyingand resolvingtroublesome partsof anetwork.In thispaper, wepropose
addinganotionof ontextasanextensiontothebasi formalismofqualitative
networks inorder to enhan e itsexpressive power.
By means of their digraph, probabilisti networks provide a qualitative rep-
resentation of the onditional independen es that are embedded in a joint
probability distribution. The digraph in essen e aptures independen es be-
tween variables, that is, it models independen es that hold for all values of
the variables involved. The independen es that hold only for spe i values
arenotrepresented inthe digraphbutare aptured insteadby the onditional
probabilitiesasso iatedwiththe variables.Knowledgeoftheselatterindepen-
den es allows further de omposition of onditional probabilities and an be
exploited tospeed up inferen e.Forthis purpose, a notion of ontext-spe i
independen e wasintrodu ed [2,22℄. Context-spe i independen e o urs of-
ten enough that some well-known tools for the onstru tion of probabilisti
networks have in orporated spe ial me hanisms to allow the user to more
easily spe ify the onditional probability distributions for the variables in-
volved [2℄.
Aqualitativeprobabilisti networkalso aptures independen es between vari-
ables by means of itsdigraph. Sin e its qualitativein uen es are spe i ed at
the levelof variablesas well,independen es that hold onlyfor spe i values
of the variablesinvolved annotberepresented. In fa t,qualitativein uen es
impli itly hide su h ontext-spe i independen es: if the in uen e of a vari-
able AonavariableB ispositive inone ontext, thatis,for one ombination
of values for some other variables, and zero in all other ontexts | indi at-
ing independen e | then the in uen e is aptured by a positive sign. Also,
positive and negative in uen es may behidden: if avariableA has a positive
ontext, then the in uen e of A onB is modelledas being ambiguous.
As ontext-spe i independen es basi ally are qualitative by nature, we feel
that they an and should be aptured expli itlyin aqualitative probabilisti
network. For this purpose, we introdu e a notion of ontext-spe i sign. A
ontext-spe i signisbasi allyafun tionassigningdi erentsignstoanin u-
en e for di erent ontexts. Upon inferen e,for ea h in uen e with a ontext-
spe i sign,thesignispropagatedthatisassignedtothe ontext orrespond-
ing to the observed variables' values. We thus extend the basi formalism of
qualitativenetworksbyprovidingforthein lusionof ontext-spe i informa-
tionaboutin uen esandshowthatexploitingthisinformationuponinferen e
an prevent unne essarily weak results.
The paper is organised as follows. In Se tion 2, we provide some preliminar-
ies on erning probabilisti networks and qualitative probabilisti networks.
We present two examples of the type of information that an be hidden in
qualitative in uen es, in Se tion 3. We present our extended formalism and
asso iatedalgorithmforexploiting ontext-spe i informationuponinferen e
in Se tion4. In Se tion5, we dis uss the ontext-spe i informationthat is
hidden in the qualitative abstra tions of two real-lifeprobabilisti networks.
The paperends with some on luding observations in Se tion6.
2 Preliminaries
Before introdu ing qualitative probabilisti networks, we brie y review their
quantitative ounterparts.
2.1 Probabilisti networks
A probabilisti network B = (G;Pr) is a on ise representation of a joint
probabilitydistributionPronaset ofstatisti alvariables.Iten odes thevari-
ables on erned,alongwiththeirprobabilisti interrelationships,inana y li
dire tedgraphG=(V(G);A(G)).Ea hvariableA2V(G)representsastatis-
ti alvariable.Variableswillbeindi atedby apitallettersfromthebeginning
of the alphabet; values of these variables will be denoted by small letters,
possibly with a subs ript. As there is a one-to-one orresponden e between
variables and variables, we will use the terms `variable' and `variable' inter-
hangeably. The probabilisti relationshipsbetween the represented variables
are aptured by the set of ar s A(G) of the digraph. Informallyspeaking, we
take anar A!B in G to represent an in uential relationship between the
ar betweentwovariablesmeansthattheydonotin uen eea hotherdire tly.
More formally,the set of ar s aptures probabilisti independen e amongthe
representedvariablesbymeansofthed-separation riterion.Twovariablesare
said tobe d-separated if all hainsbetween them are blo ked by the available
eviden e. We say that a hain between two variables is blo ked if it in ludes
either an observed variable with at least one outgoing ar or an unobserved
variable with two in oming ar s and no observed des endants; a hain that
is not blo ked is alled a tive. If two variables are d-separated then they are
onsidered onditionallyindependent given the available eviden e[17℄.
Asso iated with ea h variable A2V(G) is a set of onditional probability
distributions Pr (Aj (A))that des ribe the probabilisti relationship of this
variable with its (immediate) prede essors (A) in the digraph. As an illus-
tration,the following exampleintrodu esa smallprobabilisti network.
Example 1 We onsiderthesmallprobabilisti networkshowninFig. 1.The
T F
D A Pr(a)=0:70
Pr(tja)=0:01
Pr(tja)=0:35
Pr(f ja)=0:50
Pr(f ja) =0:45
Pr(djtf)=0:95
Pr(dj
tf)=0:15
Pr(djt
f)=0:80
Pr(dj
t
f)=0:01
Fig. 1.The antibioti s network.
network represents afragment of titious and in omplete medi alknowledge,
pertaining to the e e ts of administering antibioti s on a patient. Variable A
represents whether or not a patient has been taking antibioti s. Variable T
models whether or not the patient issu ering from typhoidfever and variable
D represents presen e or absen e of diarrhoea in the patient. Variable F, to
on lude, des ribes whetheror notthe ompositionofthe ba terial ora in the
patient'sgastrointestinal tra thas hanged. Typhoidfever anda hangein the
patient's ba terial ora are modelled as the possible auses of diarrhoea. An-
tibioti s an ure typhoidfever bykilling the ba teria that ause theinfe tion.
However,antibioti s analso hange the ompositionof thepatient'sba terial
ora, thereby in reasingthe risk of diarrhoea.
A probabilisti network B =(G;Pr) de nes a unique joint probability distri-
butionPr onV(G)with
Pr(V(G))= Y
A2V(G)
Pr(Aj(A))
that respe ts the independen es portrayed in the digraph G. Sin e a prob-
abilisti network aptures a unique distribution, it provides for omputing
these probabilities is known to be NP-hard [3℄. However, various algorithms
are available that have a polynomial runtime omplexity for most realisti
networks [12,17℄.
2.2 Qualitative probabilisti networks
Qualitative probabilisti networks bear a strong resemblan e to their quanti-
tative ounterparts. A qualitativeprobabilisti networkQ=(G;) also om-
prisesana y li digraphG=(V(G);A(G))modellingvariablesand theprob-
abilisti relationshipsbetween them.Theset of ar sA(G)againmodels prob-
abilisti independen e. Instead of onditional probability distributions, how-
ever, aqualitativeprobabilisti network asso iateswithits digrapha set of
qualitativein uen es and qualitative synergies.
A qualitative in uen e between two variablesexpresses howthe values ofone
variable in uen e the probabilities of the values of the other variable. The
dire tionof the shiftin probabilityo asioned is indi ated by the sign of the
in uen e. A positive qualitative in uen e of avariableA ona variable B, for
example,expresses that observinghighervalues forA makeshighervalues for
B more likely, regardless of any other in uen es on B [21℄. Building upon a
total order `>' on the values per variable, we have that higher values for a
variableBaremorelikelygivenhighervaluesforavariableA,ifthe umulative
onditionalprobabilitydistributionF 0
Bja
i
ofvariableBgivena
i
lies,graphi ally
speaking,belowthe umulative onditionalprobabilitydistributionF
Bja
j given
a
j
, for all values a
i
;a
j
of A with a
i
> a
j
. When F 0
Bja
i
lies below F
Bjaj
for all
valuesofB,F 0
Bja
i
issaidtodominateF
Bja
j
by rst-ordersto hasti dominan e
(FSD):
F 0
Bja
i
FSD F
Bja
j
() F 0
Bja
i (b
i )F
Bja
j (b
i
) for allvalues b
i of B:
The on eptof rst-ordersto hasti dominan eunderliestheformalde nition
of qualitativein uen e.
De nition 2 Let G=(V(G);A(G)) be an a y li digraph and let Pr be a
joint probability distribution on V(G) that respe ts the independen es in G.
Let A, B be variables in G with A!B 2A(G). Then, variable A positively
in uen es variable B alongar A!B, written S +
(A;B), i for all values b
i
of B and allvalues a
j
;a
k
of A with a
j
>a
k
, we have that
Pr(B b
i ja
j
x) Pr(B b
i ja
k x)
for any ombination of values x for the set (B)nfAg of prede essors of B
A negative qualitative in uen e, denoted by S , and a zero qualitative in u-
en e,denotedbyS 0
,arede nedanalogously,repla ingintheaboveformula
by and =, respe tively. If the in uen e of variable A on variable B is not
monotoni orif itisunknown, wesaythat itisambiguous,denoted S
?
(A;B).
The `+', ` ', `0' and `?' in the above de nitions are termed the signs of the
qualitativein uen es. Whenever signs are presented by themselves, they will
be a ompanied by quotation marks, as in the previous senten e; signs dis-
playedwithinformulasand tableswillbepresented withoutquotationmarks.
In the remainderof this paper, we assumefor ease ofexpositionthat allvari-
ables arebinary valued,with adenoting A= true,adenoting A= false,and
a>afor any binary variableA. Forillustrativepurposes inexamples,binary
variables oftenhavedi erentvalues thantrue and false; value statements for
these variables however, are again written asa ora . We note that for binary
variables,the de nition of qualitativein uen e an be slightlysimpli ed. For
apositivequalitative in uen e of A onB,for example, we nowhave that
Pr(bjax) Pr (bjax)0
for any ombinationof values x for X =(B)nfAg.
A qualitative in uen e is asso iated with ea h ar in the digraph of a quali-
tative network. Variables, however, not only in uen e ea h other along ar s,
they an alsoexert indire t in uen eson one another. Thede nition of qual-
itative in uen e trivially extends to apture su h indire t in uen es, that is,
in uen esalongone ormorea tive hains.Thesigns ofindire tin uen esare
determined by the properties that the set of in uen es of a qualitative prob-
abilisti network exhibits [21℄. The property of symmetry guarantees that, if
the network in ludes the in uen e S Æ
(A;B), then it also in ludes S Æ
(B;A)
with the same sign Æ. The property of transitivity asserts that qualitativein-
uen es along an a tive hain without any variables with two in omingar s
on the hain, ombine into an indire t in uen e with the sign spe i ed by
the -operator from Table 1. The property of omposition asserts that mul-
tiple qualitative in uen es between two variables along parallel a tive hains
ombineinto a omposite in uen e withthe sign spe i edby the -operator.
From Table 1, we observe that ombining non-ambiguous qualitative in u-
en es with the -operator an yield in uen es with anambiguoussign. Su h
anambiguity,infa t, resultswhenevertwo in uen eswith opposite signs are
ombined.Thetwoin uen es inessen e are on i tingand represent atrade-
o intheappli ationdomain.Theambiguitythatresultsfrom ombiningthe
two in uen es indi ates that the trade-o annot be resolved from the infor-
mationthatisrepresentedinthenetwork.In ontrastwiththe-operator,the
The -and -operators.
+ 0 ? + 0 ?
+ + 0 ? + + ? + ?
+ 0 ? ? ?
0 0 0 0 0 0 + 0 ?
? ? ? 0 ? ? ? ? ? ?
-operator annot introdu e ambiguities upon ombining signs of in uen es
along hains. Notethat, on eanambiguousresultshas arisen,both operators
serve topropagate this ambiguity.
Inadditiontoin uen es,aqualitativeprobabilisti networkin ludessynergies
that model the intera tions withinsmallsets of variables.We distinguish be-
tweenadditivesynergies andprodu tsynergies.Aswewillnotusetheadditive
synergy in the remainder of this paper, we just say that it aptures the joint
in uen e of two variables ona ommonsu essor [21℄. A produ t synergy ex-
presseshow thevalueof one variablein uen es the probabilitiesofthe values
of another variablein viewof a given value for athird variable[6℄.
De nition 3 Let G=(V(G);A(G)) be an a y li digraph and let Pr be a
joint probability distribution on V(G) that respe ts the independen es in G.
Let A, B, C be variables in G with A!C, B !C2A(G). Then, variable
A exhibits a negative produ t synergy on variable B (and vi e versa) given
the value for their ommon su essor C, denoted X (fA;Bg; ), i
Pr( jabx)Pr( ja
bx) Pr( ja
bx)Pr( jabx)
for any ombination of values x for the set (C)nfA;Bg of prede essors of
C other thanA and B.
Positive,zero, and ambiguous produ t synergies are de ned analogously.
Produ t synergies are of importan efor reasoning with aqualitative network
sin e they indu e a qualitative in uen e between the prede essors A and B
of a variable C upon its observation. Su h an indu ed in uen e is oined an
inter ausalin uen e.Thesignofaninter ausal in uen eisdeterminedbythe
produ t synergy that served to indu e it and may di er for the observations
and for the variable C.
Example 4 Thequalitative probabilisti networkshown in Fig. 2is thequal-
itative ounterpart of the antibioti s network dis ussed in Example 1. From
the onditionalprobabilitydistributionsspe i edforthevariableT, weobserve
T F
D +
+ +
;
Fig.2.The qualitativeantibioti s network.
that
Pr(tja) Pr(tja)=0:01 0:350
andtherefore on ludethatS (A;T).Wefurther ndthatS +
(A;F),S +
(T;D),
andS +
(F;D).Either valuefor variableD, in addition,indu es a negative in-
ter ausal in uen e between the variables T and F (indi ated by the dotted
line).
For reasoning with a qualitative probabilisti network, an elegant algorithm
is available from M.J. Druzdzel and M. Henrion [5℄; this algorithm, termed
the sign-propagation algorithm, is summarised in pseudo ode in Fig. 3. The
basi ideaofthe algorithmistotra ethe e e tofobservingavalueforavari-
able upon the probabilities of the values of all other variables inthe network
by message-passingbetweenneighbouringvariables.In essen e, the algorithm
omputes the sign of in uen e along alla tive hains between the newly ob-
served variableand allother variables inthe network, using the propertiesof
symmetry,transitivity and omposition. Forea h variable, itsummarises the
overall in uen e ina node sign that indi atesthe dire tionof the shift inthe
probability distributionof that variableo asioned by the new observation.
The sign-propagation algorithmtakes for itsinput a qualitative probabilisti
network,aset ofpreviouslyobserved variables,avariableforwhi hanewob-
servationhasbe omeavailable,andthesign ofthisobservation,thatis,either
a`+'forthevaluetrueora` 'forthevaluefalse.Priortothea tualpropaga-
tionofthenewobservationby PropagateSign,forallvariablesV
i
thenodesign
sign[V
i
℄ is initialised at `0'. For the newly observed variable the appropriate
pro edure PropagateSign(trail,from,to,messagesign):
sign[to℄ sign[to℄ messagesign;
trail trail[ftog;
for ea h a tive neighbourV
i of to
do linksign sign of (indu ed) in uen e between to and V
i
;
messagesign sign[to℄ linksign;
if V
i
=
2trail andsign[V
i
℄ 6=sign[V
i
℄ messagesign
thenPropagateSign(trail,to,V
i
,messagesign).
Fig. 3.Thesign-propagation pro edure forinferen e ina qualitative network.
sign tothe sign-sumofitsoriginalsign andthe enteredsign. Itthereuponno-
ti esallits(indu ed) neighbours thatitssign has hanged, by passingtoea h
ofthem amessage ontainingasign.This sign isthesign-produ tofthe vari-
able's urrentnode signandthe signlinksign ofthein uen e asso iatedwith
thear orinter ausallinkittraverses.Ea hmessagefurtherre ordsitsorigin;
this information is used to prevent the passing of messages to variables that
were already visited onthe same hain. Uponre eiving a message, a variable
to updates its node sign to the sign-sum of its urrent node sign sign[to℄ and
the sign messagesign from the message it re eives. The variable then sends
a opy of the messageto allitsneighbours that needtore onsider their node
sign. In doing so, the variable hanges the sign inea h opy to the appropri-
ate sign and adds itself as the origin of the opy. Note that as this pro ess is
repeatedthroughoutthe network,the hains alongwhi hmessages havebeen
passed are re orded. Alsonote that, asmessages travel simple hains only, it
is suÆ ient to justre ord the variableson these hains.
During sign-propagation, variables are only visited if they need a hange of
node sign. A node sign an hange atmost twi e,on e from `0'to `+', ` ' or
`?' and then only from `+' or ` ' to `?'. From this observation we have that
no variable is ever a tivated more than twi e upon inferen e. The algorithm
isthereforeguaranteedtohalt.Thetime- omplexityofthe algorithmislinear
inthe number of ar s of the digraph.
We illustratethe sign-propagation algorithmby means of our previousexam-
ple.
Example 5 We onsider on eagain thequalitative Antibioti snetworkfrom
Fig. 2.Suppose thataspe i patient istaking antibioti s.This observationis
enteredintothenetworkbyupdatingthenodesignof variableAtoa`+'.Vari-
ableA thereupon propagates a message withsign + = towards variable
T.T updates itsnodesignto` ' andsendsamessagewithsign += to
variableD. Dupdatesits signto ` '.Itdoesnotpass on asigntovariableF,
sin ethe hainfromA toF through Disblo ked.VariableAalsosendsames-
sage,withsign++=+,to F. Variable F updates itsnode signa ordingly
and passes a messge with sign ++=+ on to variable D. D thus re eives
theadditionalsign`+'.Thissignis ombinedwiththepreviouslyupdated node
sign ` ', whi h results in the ambiguous sign += ? for the variable D.
Note that the ambiguous signarises from the represented trade-o . Also note
that ifthe network would have ontained additional variablesbeyond D, these
variables wouldhave all ended up with a variable sign `?' after inferen e.
Sin e qualitativeprobabilisti networks modelknowledge atthe level of vari-
ables, ontext-spe i information, that is, information that holds only for
spe i valuesofthe variablesinvolved, annotberepresented expli itly.This
information in essen e is hidden in the qualitative in uen es and synergies
of the network. If, for example, the in uen e of a variable A on a variable
B is positive for one ombination of values for the set X of B's prede essors
other than A, and zero for all other ombinations of values for X, then the
in uen e of A on B is positive by de nition. The zero in uen es, indi ating
ontext-spe i independen e, are hidden due to the fa t that the inequality
in the de nition of qualitative in uen e is not stri t. We present an example
illustratingsu h hidden zeroes.
Example 6 We onsider the qualitative network from Fig. 4, whi h repre-
sents a highly simpli ed fragment of knowledge in on ology. It pertains to the
e e ts and ompli ations to be expe tedfrom treatment of oesophageal an er.
The variableL modelsthe life expe tan y of a patient after therapy; the value
l indi ates that the patient will survive for at least one year and the value
l expresses that the patient will die within this year. Variable T models the
therapy instilled; we onsider surgery, modelled by t, and no treatment, mod-
elled by
t, as the only therapeuti alternatives. The e e t to be attained from
surgeryisa ompleteremovalof thetumour,modelledbythevariableR .After
surgery alife-threateningpulmonary ompli ation, modelled byP, may result;
the o urren e of this ompli ation isheavily in uen ed by whether or not the
patient is a smoker, whi h is modelled by the variable S.
We onsider the onditional probabilities from a quanti ed network repre-
senting the same knowledge. We would like to note that these probabilities
serve illustrative purposes only: although not entirely unrealisti , they have
not been spe i ed by domain experts. The probability of attaining a omplete
removal ofthe pesophagealtumouruponsurgery isPr(rjt) =0:45;as without
surgery there an be no removal of the tumour, we have Pr(r j
t) = 0. From
Pr(r jt)Pr(r j
t), wehave thatthevariableT indeedexertsapositivequali-
tativein uen eonR .Theprobabilitiesofa pulmonary ompli ationo urring
T
R P
L
S
+ +
+
+
Fig.4.The qualitativesurgery network.
Pr(p) s s Pr (l) p p
t 0:75 0:00 r 0:15 0:95
t 0:00 0:00 r 0:03 0:50
Fromtherightmosttable weobservethatPr(ljrP)Pr(ljrP)forallvalues
of P and that Pr(l j pR ) Pr (l j pR ) for all values of R . We thus verify
that the variable R exerts a positive in uen e on L, indi ating that su esful
removalofthetunourservestoin reaselifeexpe tan y,andthatthequalitative
in uen e of P on Lisnegative,indi atingthat pulmonary ompli ationsfrom
surgery are indeed life threatening. From the leftmost table, we observe that
Pr(p j sT) Pr(p j sT) for all values of T and Pr(p j tS) Pr(p j
tS) for
all values of S. We thus verify that both T and S exert a positive qualitative
in uen e on the variable P, indi ating that performing surgery and smoking
are risk fa tors for pulmonary ompli ations. The zeroes in the table reveal
that pulmonary ompli ations are likely to o ur only in the presen e of both
risk fa tors. The fa t that the in uen e of T on P is, for example, a tually
zero in the ontext of the value s for the variableS, however, isnot apparent
fromthesignofthein uen e.Notethatthiszeroin uen edoes notarisefrom
the probabilities being zero, but rather from their having thesame value.
The previousexample shows that the levelof representation detailof aquali-
tativenetwork an resultininformationhiding.Ashiddeninformation annot
be exploitedupon reasoning, unne essarily weak answers may result fromin-
feren e with the network.Referring to the previousexample, forinstan e, we
an ompute,usingthestandard onditioningrulefromprobabilitytheory,the
independen es portrayed by the digraphof the example and the probabilities
involved, that performing surgery on a non-smoker has a positive in uen e
on life expe tan y: as Pr (l j ts) = 0:70 and Pr(l j
ts) = 0:50, we have that
Pr(l j ts) Pr(l j
ts). In the qualitative network, however, entering the ob-
servation t for the variable T, in the presen e of s, will result in a `?' for L
duetothe on i tingreasoning hains fromT toL.The`?' forthe variableL
indi ates that the resulting in uen e is unknown. As, from the ontext s, we
know that the in uen e of T on P is zero, and hen e the in uen e of T on L
via P is zero, this result is weaker than stri tly ne essary.
We re allfromthe de nition of qualitativein uen e thatthe sign of anin u-
en e of a variable A on a variable B is independent of the values for the set
X of prede essors of B other than A. A `?' for the in uen e of A on B may
therefore hide the informationthat A has a positive in uen e on B for some
ombinationofvaluesforX andanegativein uen eforanother ombination.
Ifso,the ambiguousin uen e of Aon B is non-monotoni innatureand an
in fa t be looked upon asspe ifyingdi erent signs for di erent ontexts. We
C
?
Fig.5. Thequalitative ervi al metastases network.
present anexample to illustratethis observation.
Example 7 Thequalitative networkfrom Fig. 5 represents another fragment
of knowledge in on ology. It pertains to the metastasis of oesophageal an er.
The variable L represents the lo ation of the primary tumour in a patient's
oesophagus;thevaluelmodelsthatthetumourresidesinthelowertwo-thirdof
theoesophagus andthe value
l expressesthatthe tumour isin theoesophagus'
upper one-third. An oesophageal tumour upon growth typi ally gives rise to
lymphati metastases.Theextentofsu hmetastasesis apturedbythevariable
M. The value m of M indi ates that just the lo al and regional lymph nodes
are a e ted; m denotes that distant lymph nodes are a e ted. Whi h lymph
nodesarelo alorregionalandwhi haredistant dependsonthelo ationof the
primarytumourin theoesophagus.Thelymphnodes inthene k,or ervix, for
example,areregionalforatumourintheupperone-thirdoftheoesophagusand
distant otherwise.variableC represents thepresen e or absen eof metastases
in the ervi allymph nodes.
We onsiderthe onditional probabilitiesfrom a quanti ed networkrepresent-
ing the same knowledge; on e again, these probabilities serve illustrative pur-
posesonly.Theprobabilitiesof thepresen e of ervi almetastases ina patient
are
Pr( ) l
l
m 0:35 0:95
m 0:00 1:00
From these probabilities we observe that the variable L indeed has a negative
in uen e onC, indi ating thattumours in thelowertwo-third of theoesopha-
gusarelesslikelytogiverisetolymphati metastasesinthene kthantumours
that are lo ated in the upper one-thirdof theoesophagus. Thein uen e of the
variable M on C, however, is non-monotoni :
Pr( jml)>Pr( jm l); yet Pr( jm
l)<Pr( jm
l)
While fortumours inthelowertwo-thirdof theoesophagusthelymph nodesin
the ne k are less likely to be a e ted when only lo al and regional metastases
are present, they are more likely to be a e ted in this ase for tumours that
non-monotoni in uen e of M on C hidesa `+' forthe value l of thevariable
L and a ` ' for the ontext
l.
With the two examples above we have illustrated that ontext-spe i infor-
mation about in uen es that is present in the onditional probabilities of a
quanti ed network annot be represented expli itly in a qualitative proba-
bilisti network. Upon abstra ting the quanti ed network to the qualitative
network, the information is e e tively hidden. Of ourse, in real-life appli-
ations of qualitative probabilisti networks, one would build the qualitative
networkdire tlywiththe helpofdomainexperts ratherthan omputeitfrom
analreadyquanti ednetwork.Duringthe onstru tionofthe qualitativenet-
work, however, an expert may express knowledge about non-monotoni ities
and ontext-spe i independen es as dis ussed above.
4 Context-spe i ity and its exploitation
Thelevelofrepresentationdetailofaqualitativeprobabilisti networkenfor es
in uen esand synergiestobeindependentof spe i ontexts. Inthis se tion
we present an extension to the basi formalism of qualitative networks that
allows for asso iating ontext-spe i signs with qualitative in uen es and
synergies.InSe tion4.1,the extendedformalismisintrodu ed;inSe tion4.2,
wedemonstrate,bymeansoftheexamplenetworksfromthepreviousse tion,
that exploiting ontext-spe i information an prevent unne essarily weak
results uponinferen e.
4.1 Context-spe i signs
Beforeintrodu ing ontext-spe i signs,weformallyde nethenotionof on-
textfor qualitative probabilisti networks.
De nition 8 Let G=(V(G);A(G))be ana y li digraph. Let X V(G)be
a set of variables in G alled ontext variables. A ontext
X
for X is a
ombination of values for a subset Y X of the set of ontext variables. For
Y =? wesaythat the ontextis empty,denoted
X
. For Y =X, wesaythat
the ontexts are maximal. The set of all possible ontexts for X is alled the
ontextset for X and is denoted C
X .
The subs ript X for the empty ontext will often be omitted as long as
no onfusion is possible. Note that ontexts may pertain to arbitrary sets of
variables froma qualitativenetwork.
set of ontext variables. For this purpose, we de ne a partial order `>' on
ontexts.
De nition 9 LetG=(V(G);A(G))bean a y li digraphandlet X V(G)
be a set of ontext variables. Let
X
and 0
X
be ombinations of values for the
sets Y X and Y 0
X, respe tively. Then,
X
>
0
X
i Y Y 0
and
X and
0
X
spe ify the same ombination of values for Y 0
.
Wenowde nea ontext-spe i sign tobeasignthat mayvaryfrom ontext
to ontext. A ontext-spe i sign an basi allybe looked uponasa fun tion
Æ:C
X
!f+; ;0;?gfromasetof ontexts C
X
tothe setofallthebasi signs
introdu ed inSe tion 2.
De nition 10 Let Q=(G;) be a qualitative probabilisti network and let
X V(G) be a set of ontext variables. A ontext-spe i sign is a fun tion
Æ:C
X
!f+; ;0;?g forwhi h for any two ontexts
X and
0
X ,
X
>
0
X , the
followingproperty holds:
Æ(
0
X )=Æ
i
; Æ
i
2f+; ;0g =) Æ(
X )2fÆ
i
;0g
Thede nitionof ontext-spe i signinessen e statesthatthesign fora on-
textagrees with the sign ofany larger ontext, inthe sense that signs annot
be omeless onstrainedforin reasing ontexts (a`0'ismore onstrainedthan
a `+' or a ` ', whi h in turn are more onstrained than a `?'). More spe i -
ally, signs annotdisagreeunless they pertainto ontexts that annoto ur
simultaneously.
Forabbreviation,wewillwriteÆ(X)todenotethe ontext-spe i sign Æ that
is de ned on the ontext set C
X
. To avoid an abundan e of bra es, we will
further write Æ(A) instead of Æ(fAg) to indi ate a ontext-spe i sign for a
single ontext variable A. Note that the basi signs from regular qualitative
networks an be looked upon as ontext-spe i signs that are de ned by a
onstant fun tion. By being ontext-independent, they in essen e over all
possible ontexts.
Having introdu ed the notion of ontext-spe i sign, we now extend the ba-
si formalism of qualitative networks by allowing ontext-spe i signs for
qualitativein uen es.
De nition 11 Let G=(V(G);A(G)) be an a y li digraph and let Pr be a
jointprobabilitydistributiononV(G)thatrespe tstheindependen esin G.Let
A, B be variables in G with A!B 2 A(G) and let X =
G
(B)nfAg be the
set of prede essors of B other than A. Then, variable A exerts a qualitative
in uen eof signÆ(X)on variableB, denoted S Æ(X)
(A;B), i for ea h ontext
X
Æ(
X
)=+ i Pr(bja
X x
0
)Pr (bja
X x
0
) for any ombination of values
X x
0
for X;
Æ(
X
)= i Pr(bja
X x
0
)Pr (bja
X x
0
) forany ombination of values
X x
0
for X;
Æ(
X
)=0 i Pr(bja
X x
0
)=Pr(bj a
X x
0
) for any ombination of values
X x
0
for X;
Æ(
X
)= ? otherwise.
Notethat inde ning a ontext-spe i in uen e foran ar between two vari-
ablesA andB, wehave taken theset X of prede essors ofB otherthanA for
the set of ontext variables. This restri tion of the set of ontext variables is
not essential,however, and an belifted whenever desirable. Context-spe i
qualitativesynergies are de ned analogously.
A ontext-spe i sign Æ(X) in essen e has to spe ify a basi sign from the
set f+; ;0;?g for ea h possible ombination ofvaluesin the ontext set C
X .
From the de nition of ontext-spe i signs, however, we have that it is not
ne essary to expli itly indi ate a basi sign for every ontext. The following
example illustratesthis observation.
Example 12 We onsider an in uen e of a variable A on a variableB with
the set of ontext variables X = fD;Eg. Suppose that the sign Æ(X) of the
in uen e is de ned as
Æ()= ?;
Æ(d)=+; Æ(
d)= ; Æ(e)= ?; Æ(e)=+;
Æ(de)=+; Æ(de)=+;Æ(
de)= ; Æ(
de)=0
Fromthede nition of ontext-spe i sign,wehaveforexamplethatÆ(d)=+
enfor es Æ(de) and Æ(de) to be either `+' or `0'. As both de and de indu e the
same sign as d, the signs Æ(de) and Æ(de) reveal that no additional informa-
tion is hidden by the sign Æ(d). Building upon this observation, the fun tion
Æ(X) an be uniquely des ribed by the signs of the smaller ontexts whenever
the larger ontexts are assigned the same sign. The fun tion is therefore fully
des ribed bythe four signs
Æ()= ?; Æ(d)=+; Æ(
d)= ; Æ(e)=+
The sign for the ontext Æ(
de), for example, an be easily derived from these
signs. As Æ(
d)= , we have from the de nition of ontext-spe i signs that
Æ(
de) an be either ` ' or `0'. From Æ(e)=+, we have in addition that Æ(
de)
The ?-operatorfor ombiningsigns.
? + 0 ?
+ + 0 0 +
0 0
0 0 0 0 0
? + 0 ?
should be either `+' or `0'. We on lude that Æ(
de) equals zero. The sign for
the ontext
de is derived in mu h the same way. The sign Æ(e) = ? for the
ontextedoesnotposeany restri tionsonthesignfor
de. ThesignÆ(
d)= ,
however, restri ts the sign Æ(
de) to be either ` ' or `0'. As no sign has been
stated expli itly for the ontext
de, it inherits its sign from
d: Æ(
de)= .
In order to exploit the above observations, we have toprovide for omputing
the unspe i edsign ofa larger ontextfromthesigns ofsmaller ontexts. For
ontexts
X
thatpertaintoasinglevariable,thesignÆ(
X
)istakentobeequal
tothe sign spe i ed for the empty ontext . For ontexts
X
that pertain to
a set Y of two or more variables, we rewrite
X as
0
X
, where is the value
assigned by
X
to some variable C 2 Y and 0
X
assigns the same values to
thevariablesY nfCgas
X
.Wethen ompute the signÆ(
X
)re ursivelyfrom
Æ(
X
)=Æ(
0
X
)?Æ( ),buildingupontheand-operatorfromTable2.Notethat
ifÆ(
0
X
)=Æ( )thenthesignof
X
obviouslyequalsÆ( ).IfoneofÆ(
0
X
)orÆ( )
equalszero,thenÆ(
X
)shouldalsobezero.IfoneofÆ(
0
X
)orÆ( )isa`?',then
the strongest of the two signs is taken for Æ(
X
). If Æ(
0
X
)=+ and Æ( ) = ,
or vi e versa, then Æ(
X
) an only be zero. The pro edure for determining
signs from a partial spe i ation of a ontext-spe i sign is summarised in
pseudo ode inFig. 6.
The standard sign-propagation algorithm for probabilisti inferen e with a
qualitative network, as dis ussed in Se tion 2.2, is easily extended to handle
fun tion ComputeSign(
X
): Æ(X)
if Æ(
X
)is spe i ed
thenreturn Æ(
X );
if X is a singleton
then return Æ(
X );
returnComputeSign(
0
X
) ?ComputeSign( )
where 0
X
and adhere to
X
= 0
X .
Fig.6.Thepro edurefor omputingsignsfromapartiallyspe i ed ontext-spe i
sign.
sign[to℄ sign[to℄ messagesign;
trail trail[ftog;
for ea h a tive neighbour V
i of to
do linksign signof (indu ed) in uen ebetween to and V
i
;
if linksign =Æ(X)
thendetermine the urrent ontext
X
from the observations;
linksign ComputeSign(
X );
messagesign sign[to℄ linksign;
if V
i
=
2trail andsign[V
i
℄ 6= sign[V
i
℄ messagesign
thenPropagateSign(trail,to,V
i
,messagesign)
Fig.7.Theextendedsign-propagationpro edureforhandling ontext-spe i signs.
ontext-spe i signs. The extended algorithm propagates and ombines ba-
si signs only, as does the standard algorithm. Before a sign is propagated
over an in uen e, however, it is investigated whether or not the in uen e's
sign is ontext-spe i . If so, the urrently valid ontext is determined from
the available observations and the basi sign that is either spe i ed or om-
puted for this ontext is propagated. If none of the ontext variables have
been observed, then the sign spe i ed for the empty ontext is propagated.
The extended sign-propagationalgorithmisgiven inFig. 7.We note thatthe
algorithm an handle both ontext-spe i and regularsigns.
4.2 Exploiting ontext-spe i signs
InSe tion3wepresented twoexamplesshowingthat thein uen es ofaqual-
itative probabilisti network an hide ontext-spe i information.Revealing
this hidden information and exploiting it upon inferen e an be worthwhile.
The information that an in uen e is zero for a ertain ontext an be used,
forexample, toimprovethe runtime omplexity ofthe sign-propagation algo-
rithm be ause propagationof a sign along a ertain hain an be stopped as
soonasazeroin uen e isen ounteredonthat hain.More importantly,how-
ever, exploiting ontext-spe i information an prevent on i tingin uen es
arisingduringinferen eand anthereby forestallthegenerationofambiguous
signs. We illustratethis observation by means of anexample.
Example 13 Were onsiderthequalitative surgerynetworkfromFig.4.Sup-
pose thata non-smokerisundergoingsurgery. From Example6 were allthat,
inthe ontextofthe observationsforthe variableS, propagationof theobser-
vationtforthevariableT withthestandardsign-propagationalgorithmresults
inthesign`?'forL.Inessen e,there isnotenoughinformationpresent inthe
R P
L Æ(S) +
+
+
(a)
L M
C Æ(L)
(b)
Fig. 8. A hidden zero revealed, (a), and a non-monotoni ity aptured, (b), by a
ontext-spe i sign.
network to ompute a non-ambiguous sign from the two on i ting reasoning
hainsbetweenT and L. Asa onsequen e, thein uen e ofthe surgery onthe
patient's life expe tan y is unknown.
From theexample, wenowfurther re allthat thepositivequalitative in uen e
fromT onP e e tivelyhidesazeroin uen e.Withournewnotionof ontext-
spe i sign,we anmakethisinformationexpli itbyasso iatingthesignÆ(S)
with the in uen e of T on P, for whi h:
Æ()=+; Æ(s)=0
We thus expli itly in lude the information that non-smoking patients are not
at risk for pulmonary ompli ations after surgery. The extended network is
shown in Fig. 8(a).
We nowre onsider our non-smoking patient undergoingsurgery. Propagating
the observation t for the variable T with the extended sign-propagation algo-
rithm in the ontextof theobservation sresults in thesign (++)(0 )
=+ forthe variableL. Thepreviouslyhidden zero in uen e isexploitedupon
inferen e and we nd that the surgery is likely to in rease the patient's life
expe tan y.
InSe tion3wenotonlydis ussedhiddenzeroin uen es,butalsoarguedthat
positiveandnegativein uen es anbehiddeninthenon-monotoni in uen es
of a qualitative network. As the initial`?'s of these in uen es tend to spread
to major parts of the network upon inferen e, it is worthwhile to resolve the
non-monotoni ities involved whenever possible. Our extended formalism of
qualitativenetworks providesfor expli itly apturing informationabout non-
monotoni itiesby ontext-spe i signs.Thefollowingexampleillustratesthe
basi idea.
Example 14 Were onsider thequalitative ervi almetastases networkfrom
Fig. 5. From Example 7, we re all that the in uen e of the variableM, mod-
elling the extent of lymphati metastases, on the variable C, whi h represents
monotoni . More spe i ally, we have that
Pr( jml)>Pr( jm l) and Pr ( jm
l)<Pr( jm
l):
In the ontext of an observation l, that is, for tumours lo ated in the lower
two-third of the oesophagus, we have that the in uen e is positive, while it is
negative in the ontext
l, that is, for tumours higher up in the oesophagus.
With our new notion of ontext-spe i sign, we an make the hidden infor-
mation expli it. In the extended network, shown in Fig. 8(b),the information
is aptured by the sign Æ(L) with
Æ()= ?; Æ(l)=+; Æ(
l)=
for the in uen e of the variable M on C. It will be evident that the now
expli itly represented information an be exploited upon inferen e.
5 Evaluation of ontext-spe i ity in real-life networks
To get an impression of the ontext-spe i information that is hidden in
real-life qualitative probabilisti networks, we omputed qualitative abstra -
tions of the well-known alarm-network [1℄ and of a probabilisti network
foroesophageal an er, alled theoeso a-network[20℄. Thealarm-network
is reprodu ed in Fig. 9. It onsists of 37, mostly non-binary, variables and
46 ar s; the number of dire t qualitative in uen es in the abstra ted net-
work | using the basi de nition of qualitativein uen e |therefore equals
46. The oeso a-network, shown in Fig. 10, onsists of 42, also mostly non-
binary,variablesand59ar s.In omputingthequalitativeabstra tionsofthe
two networks fromthe onditionalprobabilitiesspe i edfor thenetworks, we
haveassumed thatthe values ofavariable,are ordered fromtop,the smallest
value, tobottom,the largestvalue,asindi ated inFig.9and Fig.10.Table 3
summarises for the abstra ted networks the numbers of dire t in uen es for
Table 3
The numbersof dire t in uen es with `+', ` ', `0' and `?'signs forthe qualitative
alarm-and oeso a-networks.
#dire t in uen es with sign Æ:
+ 0 ? total:
alarm 17 9 0 20 46
oeso a 32 12 0 15 59
The numbers of maximal ontexts
X
overed by the `+', ` ', `0' and `?' signs
(Æ) and theirasso iated ontext-spe i signs (Æ 0
), forthe qualitative alarm-and
oeso a-networks.
# max.
X
withsign Æ 0
:
alarm + 0 ? total:
+ 38 { 21 { 59
Æ: { 40 11 { 51
0 { { { { 0
? 34 24 12 28 108
total: 72 64 44 28 218
# max.
X
withsign Æ 0
:
oeso a + 0 ? total:
+ 74 { 8 { 82
Æ: { 36 8 { 44
0 { { { { 0
? 6 3 2 38 49
total: 80 39 18 38 175
the four di erent basi signs.
The numbers reported in Table 3 pertain tothe basi signs of the qualitative
in uen esasso iatedwith the ar sinthe digraphsofthe networks.Ea hsu h
in uen e, and hen e ea h asso iated basi sign, overs a number of maximal
ontexts. Fora qualitativein uen e asso iatedwith anar A!B,the num-
berof maximal ontexts equals 1ifvariableB has nootherprede essors than
A; the only ontext is the empty ontext. If B does have other prede essors
thenthe numberof maximal ontexts equals the numberof possible ombina-
tions ofvalues for thisset ofprede essors. Forthe alarm-networkthere thus
are 218 maximal ontexts; for the oeso a-network, the number of maximal
ontexts equals 175. For every maximal ontext, we have now omputed the
true ontext-spe i sign from the originalquanti ed network. Table 4 sum-
marises the numbers of ontext-spe i signs overed by the di erent basi
signsinthe twoabstra ted networks. Fromthe tableweobserve,forexample,
that the 17 positive qualitative in uen es from the qualitative alarm net-
work together over 59di erent maximal ontexts. For 38 of these ontexts,
TRUE FALSE
ERRLOWOUTPUT
LOW NORMAL HIGH
HRBP
LOW NORMAL HIGH
HR NORMAL
HIGH CATECHOL
LOW NORMAL HIGH
ARTCO2 ZERO LOW NORMAL HIGH
VENTALV
ZERO LOW NORMAL HIGH
VENTLUNG
ZERO LOW NORMAL HIGH
VENTTUBE
ZERO LOW NORMAL HIGH
VENTMACH
LOW NORMAL HIGH
MINVOLSET TRUE
FALSE DISCONNECT
ZERO LOW NORMAL HIGH
PRESS NORMAL
ESOPHAGEAL ONESIDED
INTUBATION
NORMAL HIGH
SHUNT TRUE
FALSE
PULMEMBOLUS
LOW NORMAL HIGH
PAP
LOW NORMAL HIGH
SAO2
LOW NORMAL HIGH
PVSAT
LOW NORMAL
FIO2
ZERO LOW NORMAL HIGH
MINVOL
TRUE FALSE
KINKEDTUBE
ZERO LOW NORMAL HIGH
EXPCO2 LOW
NORMAL HIGH
TPR TRUE FALSE
ANAPHYLAXIS
LOW NORMAL HIGH
BP
LOW NORMAL HIGH
CO LOW
NORMAL HIGH
STROKEVOLUME TRUE
FALSE LVFAILURE
LOW NORMAL HIGH
LVEDVOLUME TRUE FALSE
HYPOVOLEMIA
LOW NORMAL HIGH
PCWP
LOW NORMAL HIGH
CVP
TRUE FALSE
HISTORY
TRUE FALSE
INSUFFANESTH
LOW NORMAL HIGH
HRSAT TRUE
FALSE ERRCAUTER
LOW NORMAL HIGH
HREKG
Fig.9.The alarm-network (withits priorprobabilities).
22
none x<10%
x>=10%
Weightloss solid
puree liquid none
Passage x<5 5<=x<10 10<=x
Length
x<5 5<=x<10 10<=x non-determ
Gastro-length
T1 T2 T3 T4
Invasion-wall polypoid
scirrheus ulcerating
Shape
polypoid scirrheus ulcerating
Gastro-shape
yes no
Necrosis
yes no non-determ
Gastro-necrosis yes
no Fistula none trachea mediastinum diaphragm heart
Invasion-organs proximal
mid distal
Location
proximal mid distal
Gastro-location
yes no
Metas-truncus N0
N1 M1
Lymph-metas
I IIA IIB III IVA IVB
Stage
yes no
Haema-metas
yes no
Metas-liver
yes no
Lapa-liver
yes no
CT-liver
yes no
Metas-lungs
yes no
X-lungs
yes no
CT-lungs yes
no Metas-loco
yes no non-determ
Endosono-loco yes
no CT-loco
yes no
Metas-cervix
yes no
Physical-exam yes
no
Sono-cervix
yes no non-determ
Endosono-truncus
yes no
CT-truncus
yes no
Lapa-truncus adeno
squamous undifferentiated
Type
adeno squamous undifferentiated
Biopsy
yes no
Lapa-diaphragm none
trachea mediastinum diaphragm heart
CT-organs
yes no
Bronchoscopy yes
no non-determ
Endosono-mediast
yes no non-determ
X-fistula
T1 T2 T3 T4 non-determ
Endosono-wall circular
non-circular Circumf
circular non-circular non-determ
Gastro-circumf
Fig.10.The oeso a-network (with itsprior probabilities).
23
a tually hide azero in uen e, that is,anindependen e.
Forthe qualitativealarm-network,Table 3 shows that35% ofthe in uen es
are positive, 17% are negative, and 48% are ambiguous; the network does
not in ludeany expli itlyspe i ed zeroin uen es. Forthe extended network,
using ontexts, we observe from Table 4 that 32% of the ontext-spe i in-
uen es are positive. Note that 47% of these in uen es are in fa t hidden in
the qualitative alarm-network. 31% of the in uen es in the extended net-
work are negative,20% are zero, and 17% remain ambiguous.Notethat 65%
ofthe ambiguousin uen es inthequalitativealarm-networke e tivelyhide
a positive,negative orzero ontext-spe i in uen e. For the qualitativeoe-
so a-network,Table 3shows that54%of thein uen es are positive,21%are
negative, and 25% are ambiguous; the network does not in lude any expli it
zero in uen es. For the extended network, using ontexts, we nd that 46%
ofthe qualitativein uen es are positive,22%are negative,10% are zero,and
22% remainambiguous.Notethat, althoughthe qualitativeoeso a-network
alsohides ontext-spe i information,itislessprominentthaninthealarm-
network.
We on lude that for both the alarm- and the oeso a-network, the use of
ontext-spe i signsservestoreveala onsiderablenumberofzeroin uen es
andtosubstantiallyde reasethe numberofambiguousin uen es. Similarob-
servationshavebeenfoundforthequalitativeabstra tionsoftwootherreal-life
probabilisti networks, pertainingto Wilson's disease [11℄ and to ventri ular
septal defe t [4℄, respe tively. We feel that by providing for the in lusion of
ontext-spe i informationaboutin uen es,wehavee e tivelyextendedthe
expressivepowerofqualitativeprobabilisti networksforreal-lifeappli ations.
6 Con lusions
Qualitative networks modelthe probabilisti in uen es involved in an appli-
ation domain at the high abstra tion level of variables, asopposed to prob-
abilisti networks where in uen es are represented at the level of values of
variables. Due to this high level of representation detail, knowledge about
probabilisti in uen es that hold only for spe i values of ertain variables
annotbe expressed. Wehaveshown that, asa onsequen e, the results om-
puted from a qualitative network an be weaker than stri tly ne essary. We
havearguedthat someof the knowledge thatishidden inanetworkis infa t
qualitativeinnatureandshouldberepresentedexpli itlytobeexploitedupon
reasoning. To this end, we have extended the formalism of qualitative prob-
abilisti networks with a notion of ontext-spe i ity. By doing so, we have
provided for a ner level of representation detail and thereby enhan ed the
workzero in uen esaswellaspositiveandnegativein uen es an behidden,
in an extended network ontext-spe i signs are used to make these hidden
in uen es expli it.Wehave shown thatthese signs anbespe i edinaneÆ-
ientway.Wehave furthershown thatexploiting ontext-spe i information
an forestall unne essary ambiguous signs duringinferen e.
We have argued that qualitative probabilisti networks an play an impor-
tantrole inthe onstru tion of probabilisti networks for real-lifeappli ation
domains. By rst obtaining a qualitative network from domain experts, the
reasoning behaviour of the proje ted quanti ed network an be studied and
validated.Theeli itedsigns anfurtherbeusedas onstraintsontheprobabili-
tiestobeassessed.Now,re allthatthenotionof ontext-spe i independen e
wasintrodu edbeforefor quanti edprobabilisti networks asa on ept tobe
exploited to speed up probabilisti inferen e. To identify the ontext-spe i
independen es, generally the onditional probability distributions that have
been spe i edfor the network havetobeinspe ted[2℄. Using ontext-spe i
signs in qualitative networks during the onstru tion of a probabilisti net-
work, now brings the additional advantage of ontext-spe i independen e
informationbeing readily available.
Referen es
[1℄ I.A. Beinli h, H.J. Suermondt, R.M. Chavez, and G.F. Cooper. The alarm
monitoringsystem:a asestudywithtwo probabilisti inferen ete hniquesfor
belief networks. In J. Hunter, J. Cookson, and J. Wyatt, editors, Pro eedings
of the Se ond Conferen e on Arti ial Intelligen e in Medi ine,pp. 247 { 256.
Springer-Verlag, Berlin,1989.
[2℄ C. Boutilier, N. Friedman, M. Goldszmidt, and D. Koller. Context-spe i
independen e in Bayesian networks. In E. Horvitz and F.V. Jensen, editors,
Pro eedings of theTwelfth Conferen eon Un ertaintyin Arti ial Intelligen e,
pp.115 { 123.Morgan KaufmannPublishers,San Fran is o, California,1996.
[3℄ G. F. Cooper. The omputational omplexity of probabilisti inferen e using
beliefnetworks. Arti ial Intelligen e,42: 393{405, 1990.
[4℄ V.M.H. Coupe, N.B. Peek, J. Ottenkamp, and J.D.F. Habbema. Using
sensitivity analysis for eÆ ient quanti ation of a belief network. Arti ial
Intelligen e in Medi ine, 17:223 { 247,1999.
[5℄ M.J. Druzdzel and M. Henrion.EÆ ient reasoning inqualitative probabilisti
networks. In Pro eedings of the Eleventh National Conferen e on Arti ial
Intelligen e, pp. 548 { 553. AAAI Press, Menlo Park, California, 1993, pp.
548 {553.
an estor nodes. In D. He kerman and A. Mamdani, editors, Pro eedings of
the Ninth Conferen e on Un ertainty in Arti ial Intelligen e, pp. 317 { 325.
MorganKaufmann Publishers,San Mateo, California,1993.
[7℄ M.J. Druzdzel and L.C. van der Gaag. Eli itation of probabilities for belief
networks: ombining qualitative and quantitative information.In Ph. Besnard
and S. Hanks, editors, Pro eedings of the Eleventh Conferen e on Un ertainty
in Arti ial Intelligen e, pp. 141 { 148. Morgan Kaufmann Publishers, San
Fran is o, California,1995.
[8℄ M.J. Druzdzeland L.C.vanderGaag.\Buildingprobabilisti networks: where
dothenumbers omefrom?"|Guesteditors'introdu tion.IEEETransa tions
on Knowledge and Data Engineering,12: 481 {486, 2000.
[9℄ M. Henrion and M.J. Druzdzel. Qualitative propagation and s enario-based
approa hes to explanation in probabilisti reasoning. In P.P. Bonissone, M.
Henrion, L.N. Kanal, and J.F. Lemmer, editors, Un ertainty in Arti ial
Intelligen e, 6,,pp.17{ 32.ElsevierS ien ePublishers,North-Holland,1991.
[10℄A.L. Jensen. Quanti ation experien e of a DSS for mildew management in
winter wheat. In M.J. Druzdzel, L.C. van der Gaag, M. Henrion, and F.V.
Jensen, editors, Working Notes of the Workshop on Building Probabilisti
Networks: Where Do the Numbers Come From ?, pp. 23 { 31. AAAI Press,
1995.
[11℄M.KorverandP.J.F.Lu as.Convertingarule-basedexpertsystemintoabelief
network. Medi al Informati s, 18:219 { 241,1993.
[12℄S.L. Lauritzen and D.J. Spiegelhalter. Lo al omputations with probabilities
ongraphi alstru tures and theirappli ationto expertsystems.Journal of the
Royal Statisti al So iety,Series B,50: 157 {224, 1988.
[13℄C.-L. Liu and M.P. Wellman. Using qualitative relationships for bounding
probability distributions. In G.F. Cooper and S. Moral, editors, Pro eedings
of the Fourteenth Conferen e on Un ertainty in Arti ial Intelligen e, pp.346
{353. MorganKaufmann Publishers,San Fran is o, California,1998.
[14℄S. Parsons and E.H. Mamdani. Reasoning in networks with qualitative
un ertainty. In D. He kerman and A. Mamdani, editors, Pro eedings of the
Ninth Conferen e on Un ertainty in Arti ial Intelligen e, pp.435 { 442.
MorganKaufmann Publishers,San Mateo, California,1993.
[15℄S. Parsons. Re ning reasoning in qualitative probabilisti networks. In Ph.
Besnard and S. Hanks, editors, Pro eedings of the Eleventh Conferen e
on Un ertainty in Arti ial Intelligen e, pp.427 { 434. Morgan Kaufmann
Publishers,San Fran is o, California,1995.
[16℄S.Parsons. Qualitative Methods for Reasoning under Un ertainty. MITPress,
Cambridge, 2001.
Inferen e.Morgan KaufmannPublishers,PaloAlto, 1988.
[18℄S. Renooij and L.C. van der Gaag. Enhan ing QPNs for trade-o resolution.
InK.B. Laskey and H.Prade, editors,Pro eedings of the Fifteenth Conferen e
on Un ertainty in Arti ial Intelligen e, pp. 559 { 566. Morgan Kaufmann
Publishers,San Fran is o, California,1999.
[19℄S.Renooij, L.C. van derGaag, S.D.Parsons,and S.D.Green. Pivotalpruning
oftrade-o s inQPNs.In G.Boutilierand M. Goldszmidt,editors,Pro eedings
of the Sixteenth Conferen eon Un ertainty in Arti ial Intelligen e,pp.515 {
522.Morgan KaufmannPublishers,San Fran is o, California,2000.
[20℄L.C. van der Gaag, S. Renooij,C.L.M. Witteman, B.M.P. Aleman and B.G.
Taal. Probabilities for a probabilisti network: A ase-study in Oesophageal
Car inoma.Arti ial Intelligen ein Medi ine,2002, to appear.
[21℄M.P. Wellman. Fundamental on epts of qualitative probabilisti networks.
Arti ial Intelligen e,44: 257 {303, 1990.
[22℄N.L. Zhang and D. Poole. On the role of ontext-spe i independen e
in probabilisti inferen e. In T. Dean, editor, Pro eedings of the Sixteenth
International Joint Conferen e on Arti ial Intelligen e, pp. 1288 { 1293.
MorganKaufmann Publishers,San Fran is o,California, 1999.
