> nnwX(rPNG
IHDRbKGD]=tEXtComment Image generated by AFPL Ghostscript (device=pnmraw)
Vd_cmPPJCmp0712`AIDATx^]O3Y
J"D. BkPU".l/Nҕ JMeqFlZ73ׂхk(ݔx&f&d'~>=yc;z33"FVAoh̬OC{bxO[6Eƺ;07AihXV>Ȳ"e
};KޘAyِ6lG3;{%{nďѨ_֡\F3(_iRODé/y4w,6UK̬
?C}FrpOd1>h84lNc4llL*ϭ.t8_2toRMZC`
F(Ч0h}
F(Ч0h}>QS4Wq,a}G]l
3zڠa4>QOc1a4>QOc1a4./5iL/oxbrE#!7VǺr}8V4tγ̊ƊsUcE+ UP>8%O]TIXf(khԯ
'@35q]PDU%ea}+ɨbD#Ki(>UU,35Buh(/5;ʕ2XCXzhLd[f5\FY:>,TE2[eeJC#0xFQe*s !ۏ!Ob·v)StiFҲ26_\0M~=YF5$%I*n[lCYC2Co.Ѹf1+jL熆el
кsCeh
5ZsC#=F7fѺ.LS RKynhHL1h ^SJsJ)s%%WI(D?MBNazF Ax%) c*Kӌ^ @bJ/3>ҕ2Xb!'cSım
?lQmo4{ũ6ҷǋMvIX f{8E,&q;"NuG4֡],i{Z@F\ж"\v6!sdi$ò+Ib!cA[V*#Lz{$&9 @Z~7/iw"M6R_rmQ,8X*tވ:T1p64Öw83oĮEnY1m^6#ǇmJyv,Fa@Hm#yO fIM'ȅը6רDfb)AѨ`ch@j霁c4a:lƥ72ؙtJuv/~QB4USvRmeFI5uUohRPkJ{9{T*FmɊ"56g19$֔cdQxIUȫ6%3IhF\N`:t(~C?on@_{vK"QtT
yOm5kMыh_1R@ Oo%~
*hҡ:݅I@#j!`_䯵*S=>42^OxHG<~wk4xJCpM1D]x5ס/gQr"+NUEHZ?̂Ku:bV$U:_ꉠqOѢOn:&4a6ద\?5 W3&׃HNz{AUr\SǜYn(J4YUcGj}?q䠩t}#Ki5ELU}r
h̎7ISc~SeIe#(D\S>Lc2
)rThOCzUX怣T{xvk{Br6!HJŀo;,\J* ;G*_!ʋv\CƓ$b}WfYEX^
GcwY7z\9a>$+[\QU֒.9hLV,GQ(ԑhL{bQdr9rD#eTGI*271!a#ǒ* (#%
S&lڽr`__LL7]
x1(
C#Rumb/䀡1ȸU;vcK%RF065+ѧF3 LOrx(4R,v[N˴lTW >eoJ+t,q}Q1H}%mYcqE龃ho}*h@YExv5dXQltG6U
F+u
_.
ʐE[IEEt!8
HS5gvbLG9l 4ă,_7%b^He` 4O!d5
R֒
e`:CCo\8vIұ8BV@0eД2t)#4G%SB/xCj%8T&
}&;U]\аe6Qe1豤RՁp/pPS@h$w2xhO%CID04 }2lOۀx2mL%ڎj#(4Lߛ_oIz4ovh܍!QasmxDCA!ߓ!Mbt 9CKTiJe T04.յuWCPiWOr[an cB80Oф8+1uM)SdxegHטj#РY_ }%[3nHAwspx,rxR[JD q:=rAҒkk9рݵѯ5x=h6`G1?TZ4bsͬŏ5픒f<'CRN{
?CZVSz /yiyZ<~ED4j[OTp0eJumxh6(o)>Ru=aSѥZGQ~禰TZ]6~AVߠWp:arͩI*aXS/A^U6Ʃ&&~=6HY94bA456WFq
NĭKInK%eZaTa6/eY]9gs
ł'a%վcgqIY4$FFvg4l!r'3,%c]R*\)PY7v@4i!%
w]Hǵ0{Q2Zp'A2!;_on(Vi
xR*cVs\rke++5uUL,~:әcz70nٜΤۦ@5Jn,)؟A c.E ǉ#? +Y Iuw(<4/xeย3A" Gd`c}Bq/w],ܗ
3h(^ՠ'B
4$UhР@Bg7!@^Mc}?܌c)++=kx>]@~;1Tݿ;E?V!wa[ȓXQd5Ȇ*7ȝr>Ho/EUllpK+I^LJ8֍'
~$&0)v{\Udjc̒?˼J״XG<&ӑ.!&i,_60Dgyh)r5ӥ{>^+:;c{ YVo !GETrg:;`ri,^hfc,,
HYFAü'@GXz$/"ù]`b
˪Njv~$n'k,>3{Ȯ#(?9Nkg٧ :;pֿq#m7c.&3Oĵŉ/.$F`$/$;p^elӯec/~7;Zџڏ4p
r^K<vWcg/xOwIfLyY#5Y~V%aޙqF1
t$d@L, Dl&\:_?ZJ*$T$b+= 8B^UȲ/*=BlOT!
*AcxIĻ=^&0\R2?[tlB,M!8
YHF1QxQ\}ʾBGyE@$cwMIHIageo;[dy5γ8<82Ձ6S@}Gfb?j?ʊrrSI?coճ}AEARȿgZrx+EP^Qz*W}OlDBQǛiE߾bm3})v0]V/"f}H0Jty$8q_ )cc4FxmƅG5KJͩ_(izmdQe%u%Z,RRJ6}gsQ!(i03ԯ╽N TRJ6SXZbԯmbۓ]CNDG4gVt,BڦTD vP6$.4~Ͷ%.5HQRY3;)lT!Tnf°jiI
];svN+RJ4;]!mSZM3%~/6ptInlwdMvmLbE2@w[~ae)iv)%^ˏ2XT?
SeI
]K?Ե4;.jXRL]Iݓ"s.6=WNMOB{upˣ%uBNZ'Rs,#k+W}2HšIENDB`n ?XsI3HPNG
IHDR`PLTE !!!""")))222333888\2u2DDDHHHUUUfffhhhwww**88
ffDDddww͊bKGD37^=tEXtComment Image generated by AFPL Ghostscript (device=pnmraw)
Vd_cmPPJCmp0712HsIDATx^\4(q]u[$oVM9=gٞIꆺJdVWw )+J"jA(XKCwKlEyצld^hP*N9C٢V%K%_z+a4lXs)AY@x^9t;e#Y*We{Gu@!P)_wvZ%Jx =~b8e(XQ;t;eYjR9E(Cyj,
TLAD*Q*z]ꫬJT)u
2qSUW'vf<[ELQR@yx\Ty;e("˙.CCLwI{5ժJGA;E9ml+p2sq4wSUơ^^}g_vbW^ү~ͱrmV=E/J{/8VS7S]q=0lCQ(ĩsuav/[7,_;I}V fPc=]ԵrviQwH}fPPr%}ûwUԵZVkAȳPo1Qw膗[e3(rhe)ԃ9)ZUo~(ekeQ6kre'5HdQwkwL+sAƚ(S%%(_9u=ʨ{BZC>ecMArHRKă(QEQ5@.lhb[+RZ9hd)(~"&(_jtQwk#mc[+ӭ
J\Z%.rŭDիHu%(k
ɎQwk;zu]q7>l 9fQKԃ9ʑwCԽ=3DD{Lsy*KD=ʓ%uGu3e:)Xp=Ȏ&jQlIc4+9%7Xn,= H(.IENDB`n? X\\N33PNG
IHDR`PLTE !!!""")))222333888\DDDHHHUUUfffhhhwww""22DDDww
**88ff
3ddww͊͊YbKGD:N =tEXtComment Image generated by AFPL Ghostscript (device=pnmraw)
Vd_cmPPJCmp0712HsIDATx^ w6URҐ%=3ms[`сFB,~vזfFBW7w )KqKW)\0BX.g!Djawd^W>b&\Y3r
Hy=G
/#E\!AA#EQTm>5*84Â,ڮaa4?dWFu!eQq/XK;ӡ/s:\@bhmCK؇v¾@ի>
EGv
t2
Ѽ@A_jy
?cꢴ8E_Z)W`vҴPФ8p_cE^ˤu"_܆ VPEhEVF+#\;֔S=4~sq緤[+GGsyGf
>ʣݴ'6+Wge5}sFwZ}>BFm
dm^%LrGA^}@+ kRɗK1
qjlyYV seGKӎ:QWcLuQTPdbc*~0ꔥlNc>'E6VXȾZA#9Șr\#]Lw"`!j*vuKtg,EG9cј\vBGʡGE6VXȾ.z;ȧ`NyRK$QVpE]ZrmJBhQ0؊Fƚ:
2k"r&Zኺɵ
*g3ԱVXS'*Z%F+dO5+6+6ҳHUO%u
Ѷy2WuN86*ldE
_r$"*꒭Ȩcp  pJ?<M+kt2Qm.8pKn{R{NH8Fzo%'$MXnH@Zvu6nIENDB`n ؋ha#8?]6PNG
IHDR`PLTE !!!""")))222333888\2u2DDDHHHUUUfffhhhwww
**88
ffddww͊CbKGD0=tEXtComment Image generated by AFPL Ghostscript (device=pnmraw)
Vd_cmPPJCmp0712HsIDATx^\6uIICZ26$_W/dcar9g3ѵdz#䓻xJW+r#B;P,U=F2o*G=UÜ،IJ0k9aXo;1?>S8mP_simnQ{)7K0Ƒ&^`c)1_jmƩ=6e셆FNLYM?ʩ /'TrY@b(1єOl=t$T$/~i̻n:\)h$KUG
#= !,z`C5J, {6`n
C9vM01Ϋ`m1Ⱦ'?܆u(zh]p)?b)ܰMIk2_y2[[9f(?˧銗V8onW[V#zZΔY!Q^جz/h
j#)Qv˗S,UBy16EYGH'ar(8:,꙾ӰaШdKe)߶!zCTdKx s=qQLءCS֒/Q$L [EQ2ѱC%K_J0({%PްZB%K_'0(SШdKe(oXPQCS֒/9Kk)ʖe(oXPQ,G<߱;<WESk5=Q8^qQ]CwEguu20GCc\
{pe5(
*bAB jXG@YPKޱx)a/,E?4ʶ[jZ9S6(M JXES6D)K<؊%]ԝZC"͆&(U
EH5h_sȪYTl5J;˵ Tac[+ӭ
JZ%.růDիHuo%,krl܂EyZάFE]_]dc1\cAr%̢~[#7eQws>mEu7C{)ǬEˊwF_t>QW(3㟏$u?s\z1ZHyCbRf)(^SXIENDB`n FuSNPNG
IHDRzU#PLTE !!!""")))222333777888;;;D!e!2u2@@@DDDHHHUUUXXXfffhhhwww ""2233XXDDww͊ObKGD37^=tEXtComment Image generated by AFPL Ghostscript (device=pnmraw)
Vd_cmPPJCmp0712HsIDATx^\&%kG؇}%6oA{sn܅38#!\R)\"@`2#VH6P5BMh0W4֊$w"kp{]Gu
2jԖY=fw.AFOd)7,J q=qy5m:dԂfe6LYY/TeУ.+ix}ujʢXP͢l#{SNPv)P6VC;P֒/A=Ӗ04lsFɖarVC)dKxl q2[eXvZ%Jx %nVVDكGynס픵dK _, se4"euh;eYj/8QdKˊ({P3]+ס픵dK { sȖ+APv,MU;<܉7oRd^c"ԾXf5j2}=)S=ou_[[PGJZ}OB.
a=T_R^*m+cIåOaLj) 0<<{Z xlZ6e[MoWPD[471BCcǮc(8Y]2r)MEO+j:gV]N5UPQFʉrg
=ȥL(6eKiQ}y3e=._mPWEM1K:[Dyh%p1Fxl颲a}U^͊rOTr.eSLIeӕꀾ1r)˺G۱'5v[DFPncӹ=<5(=]VOB(~_(<}*z`VG!~8$8 }ۗg_?<+Cr1/n{R!fiƦQKqRUkmŌt_)TaKebQ^u\]yEs^ŀ+2UddmK[vpkTւGQωTvT)7C:23kTB_x2'R1DRBeeqүOyS$ 
'Sg$..FJ8Xkn1uîQס~$ )4[_'jxu{h\4V8
JT)o+TOU2F2_zQk3X6(*V2KxKI݂My˵4c#{ȳzgcSB~ԩ_OGi7M묨ۡ;S0D/Hu=a<7E73vxއ(بcǏ}2
Q>vxއ(بcǏ}2
Q>vx7~s1QL
Mu`Z@"IENDB`n.sɇYPNG
IHDRwpbKGD]=tEXtComment Image generated by AFPL Ghostscript (device=pnmraw)
Vd_cmPPJCmp0712`IDATx^]s*Uftn \  L&OIK0忄KTIgWC/ 936b?VJ{x={ eJIҤ$KHp%~F$c3(
j@&bƚzbcMٸnU
y!wwYYe\"(eOA
z<&Z:(J[bЂD5bCSͧ>!%?~^KV^yZjk^ņޙ)NCD)miɹ˒{T=E
R@Y
sk`Y#%EǏt=\EElXIґI?ANt{0Ozly3<ED鑜gS\֕V`1)n9^%.\b=ćv!
yƔ<eګ$~qif=5kfPgzrgrHB5̔lhe >ɍSv$lT<ܬDd8܅R&uv(Ås L>sq`iOS URF?
f.5o*<KLkAb00l80bf*LUNEۛa';&b/k)1O
Ć&%CE> Sүϩ`cۙkTCHZ=xeL?%TF[iVa+5l{?V~,IM$yO;Ne*
>W'fX9H2jM^Jm~E[7ciʘkZjf @M'Dt߸;M FܯU8VsD{ԗ;mmt$>>'7nGxfnfopLu)cM,
EWBn@46c4B0β#4m)pĘYTTTn[A5ܕRӐamzuE
$(`ҬKѰA/qyGAI`)k^fRcg84`LLަx9TH:#؈㡭 !Fג\ltL#۱,F}4.62[\X0wXZ)Y
_`in;b7ҳ,.'"!I]~
CAwڵcn^Qnsw CWs\z!gZؙm"^ISZucgˍAxņG7
gl,vfgG27F5ol\u3~2x7MFYg6+FQg;
+h!WL4Wl{ȍB6Sb\ڠE w19`nnkhpCv)=fV蜡sl/gqpX
eBE6Wl8hQ p0;ff:w3jfб4BBC6]ےf_Ulۻ6ր;Z!(Euu5e
hֱla1\PB'ׇ'HAk%=L_M3du}9gqOl``voL>1,`]QFK $'ekAtphrf?J`߃v3wdl3hp>s?\G"3!W}XՏA7)ؐB͒Z眫:Kbke{RoPnkh/
KbV+g[=j[TT)J9И[3cOUɆ%uO+`6caz ]l܌)jz\6Q
s+7Ѧq:a_ѐ*@M W_5cJZتL ]v`Xp.~klMxT^L$LVȣJ^cP<_d{09?.^V
,aبa^Rz`Vu5#kl
GRuUl>"8p3
"L0 R?ƿfjRb
Wa۫j{Z;贻
a:]r0,Ca'!CJ2LբO)&}*ٗIS'%8u<%BN0TgZ;XZ yjMq`OVh=]'UwG`U7"攴n9/hz[94K
<9@kwW9{Ft2e^}^`cl7v[iCuJN%5@ySǍ:!<U4X~fr(?)Ő
eymEyuH Km[S09ٱUC94v]zI{=q3Yroh]\x4J\y}((
e^dK_Pv8{ɒIV@rҺVa6Jy\J)6dOj^yg"gI)1ܶ1RRW0?1,tm)"y"l_So?Thh~.S\b2
`W'gfkQihMU6se/:r0qKPvx*FڶGT*<6s"i]atw]_!66F3T"5(2*`crAe=+F!VZ}4P%LMNu ä~l\7N'T/b7`s*I.juTջQhTvhX ae
8; ,FQ(HS^;&lJ
8 璊+>I쫯C:Qa<6_8
o
͡b滤J
X8Nc678tq'JGd)IpHVi@m"4v^6썦[[p{KoNK}gBm;)`b%o
/77[? >.fRfH7ъVq@t~ # b=sLADa
Xw6xK҃V{1@>[O*\=z$V[[8Z6
?Szj.wː*(`c#D7]{xV8]lh?`N4/,_l,<~]1aRP/6{slJU_le9,>h(S<$y*?4)LfSIENDB`n]8%lPNG
IHDR~bKGD]=tEXtComment Image generated by AFPL Ghostscript (device=pnmraw)
Vd_cmPPJCmp0712`IDATx^]MQ>VPŊ] ҽ@m<
xHHH £DCr)HM[HY=!6IV ٛ(lMձퟲ}~==ssͽTWu~w'r)
=_LDw롟EUg%zja&<ͪ,FkÐ"\AgYnޫ,+T^c]}.B_ 5D}wA3N.>MAD&i+;[>w`
r%Pm辂FjV6tbƹbPźoZ9~R*E*N&{ՄKSN{9H8_Fأ4T
AGnn=GkȉMd^WN8Zv߲qvϭV
痋M3Z?>_>/~7L\G'2o(tۜ&7#a46քU&H?Cixx+L,1;\psq0\RDNgZ̞KDmF͖5b'`&zmfx1QAYwalP{Ӈe>&<=e=<
_KBFTzfԠ=ݽOf&%N̫oCb6^YmR#Q//ږXZ"1ʲ*Zn=Kȃj7e'b{{nZB$m֥244Fx~ww$؈'ܷJ*5U#4"lށ
ȍ=c,j~GKv mY>APB(#(8p_{ ٖ9_{!jpXev(.`VlFi=m$t Nn$ܐ
m}zH'~b[7'I?y{,#v%d>l4WTb$Ǵ/G'7X`j$f_9IĽ'8cdKswa>C+H?fe~TF;){\XNr*}bޏ,(V,Jx'A/@#} ˸0f{%S 3r`_Ʒ!@"/w!6u_>Ih
tŜjU{NUm5_Zd˄MY{s$5zRd@gXݛՑyp,M1ນ)>g>,M17v1̲snܖě>t"`o>dHg;ŕ)^0x?{NaPef6>k>H1Yt\Ca?}_Gգ}@U4,qYMtypH믙AfbXǝJwn[s'b{saZ=H!ɁVRuЇ]D,LiYed\)ߌzQ`趫h'bN?'u"L="+ۓ׆
PBxl[UV{W<(O\>,OUnq/Y:Ϝn$³;&
oW7Zj7{M^ɜ:URZJ&S~ʑm*`B8aLĹB&MAwկ?ُ#p"~Oa%Ď>hkǬ14˂zpv"yC?ZU}GC_yGcx4ɷ?DdbaTK`7! CO?ohņJàj>}OSr}N4/зX,e;=ruÍ2Ӊؗ}^WoxGhO?zO
c6oiuӓ}2>= u /F{`7E;QkJxWxSm
.sx@;CGRnYT?oJ!˩F$*Щn#^WJL b'hx ($v`9"zoz7C]1
+ѷk
)gΔio>Ӓrx%{Vfj
&t
Oeĥ)ϱV{7!È8{'tݞ4qk>2
"bɝe!~uW:1E0a!v[o~T^#Ipa~ébi?TTz:O.qhZX!u7e<ʯwoFxKv/gS>j{~,}\~`uI%px#_Q5Y #Akc>>+(4f!F!T,˩5N`5 sh>>Ěz6A#>$ⴈ
>b,2c{QoI~+18@l@j"Ӹř)Z6'6Bn:ȵ_hrho2ouXyX7!jƞu?AHҰ$#[ un6A`ՄM!>+0!S2;0/}7
e!Q2̹*_B%Gh3a~/^};&csk{~_[RK"nr<YBI_*ȷ$cAb$죟T)$a/:.5aR/OFy7zB&ZyiM*:dj筨\$*+fd>zrڄA75C(w(^u>Z7aOHFS6qHD3ͫ؎&FԱoIhb_Їl)4C> Qb^0\vt7Ζm@4{59qg@S֮2^[o#Hc!Zd_7{b2"508M0նFh7F7
fe&0]lJT蚉0E]~Ն#j$W[Jo?eJ[)+UbzӪp+} ٲqͫoeaj}2c#em5s"!q;Qv5ZvՅ/4h堑osxnuNd/(?o78 UvQDU2w0$}&XһFǜe/dv6Sѯ9m&i 6#'] >M,
5oN)%\x.teY\vD5~s߸TW&)Xk)ӟ'l2X7/Q$4?b g⧬~lL0EEzĺ6 D wGxտ6I!5eH#y22E8&Ѡ6%y$>Usq<\(՜.I7zܻFw}泄qqL+2flڃ}`b=kDX ә"W
^+Hц;#O4
ViIr
YI
ŦxFBQ>t
bA/$\@xl29UZ,
!lLQ)ǤzqKDL3Sj_+yՐ8 &r֣Wi=+'WdgIe
M0!fVXvjf%cq4%+:2/,Jb^M1^BaδfAĜ^w!bc@k]شu;.ԃM(Wd;y\c¼r` O_Y+8aizW*[yq@;c[ʺw8f}&A
2qj"Z&ƖJ\$5{ɣ~"LTb>n_xmttŌLHq"0G4HT#G
gD,itODMǩ^?Yj8(fbnt]#u D;>L_C,4/ևT?(6Ù/Gc$80uLŤՅt ޔyzSȞ\Aԟ2T1, Q/
&;D@$ꜧe $ЄSƲ35K낊09"Q"Y [fhni+ q7O39"/eh׀GU_x':IENDB`}(
`/0DArial~w0:A 0"DSymbol~w0:A 0@.
@n?" dd@ @@``!Z
`b$nwX(rb$$aab$?XsI3H b$X\\N33G 'b$؋ha#8?]6 N0b$FuSN \9b$.sɇYCb$8%le\0AA@ʚ;ʚ;g4@d@d :A 0.ppp@<4ddddL$ 0}w0___PPT10
___PPT9xpX?
%@wUncertainty
Chapter 13OutlineSUncertainty
Probability
Syntax and Semantics
Inference
Independence and Bayes' RuleHUncertaintybLet action At = leave for airport t minutes before flight
Will At get me there on time?
Problems:
partial observability (road state, other drivers' plans, etc.)
noisy sensors (traffic reports)
uncertainty in action outcomes (flat tire, etc.)
immense complexity of modeling and predicting traffic
Hence a purely logical approach either
risks falsehood: A25 will get me there on time , or
leads to conclusions that are too weak for decision making:
A25 will get me there on time if there's no accident on the bridge and it doesn't rain and my tires remain intact etc etc.
(A1440 might reasonably be said to get me there on time but I'd have to stay overnight in the airport & )
~YPPP" P(Pq" PP
(
\

d,m
o Methods for handling uncertainty!!(Default or nonmonotonic logic:
Assume my car does not have a flat tire
Assume A25 works unless contradicted by evidence
Issues: What assumptions are reasonable? How to handle contradiction?
Rules with fudge factors:
A25 !0.3 get there on time
Sprinkler ! 0.99 WetGrass
WetGrass ! 0.7 Rain
Issues: Problems with combination, e.g., Sprinkler causes Rain??
Probability
Model agent's degree of belief
Given the available evidence,
A25 will get me there on time with probability 0.04
x PZPGPPPNPPPtP 0
'G
b
b
b
) ?
2 >ProbabilityProbabilistic assertions summarize effects of
laziness: failure to enumerate exceptions, qualifications, etc.
ignorance: lack of relevant facts, initial conditions, etc.
Subjective probability:
Probabilities relate propositions to agent's own state of knowledge
e.g., P(A25  no reported accidents) = 0.06
These are not assertions about the world
Probabilities of propositions change with new evidence:
e.g., P(A25  no reported accidents, 5 a.m.) = 0.15
/P~PPPDP/PP*PPoP
9 4
R
"
C
*"Making decisions under uncertaintyNSuppose I believe the following:
P(A25 gets me there on time  & ) = 0.04
P(A90 gets me there on time  & ) = 0.70
P(A120 gets me there on time  & ) = 0.95
P(A1440 gets me there on time  & ) = 0.9999
Which action to choose?
Depends on my preferences for missing flight vs. time spent waiting, etc.
Utility theory is used to represent and infer preferences
Decision theory = probability theory + utility theory
"ZZZLZrZ"
(
(
'
(2( SyntaxBasic element: random variable
Similar to propositional logic: possible worlds defined by assignment of values to random variables.
Boolean random variables
e.g., Cavity (do I have a cavity?)
Discrete random variables
e.g., Weather is one of <sunny,rainy,cloudy,snow>
Domain values must be exhaustive and mutually exclusive
Elementary proposition constructed by assignment of a value to a
random variable: e.g., Weather = sunny, Cavity = false
(abbreviated as cavity)
Complex propositions formed from elementary propositions and standard logical connectives e.g., Weather = sunny Cavity = false
PPePPP$PP2P8PPPPPe8Y `S
Syntax8Atomic event: A complete specification of the state of the world about which the agent is uncertain
E.g., if the world consists of only two Boolean variables Cavity and Toothache, then there are 4 distinct atomic events:
Cavity = false Toothache = false
Cavity = false Toothache = true
Cavity = true Toothache = false
Cavity = true Toothache = true
Atomic events are mutually exclusive and exhaustive
ePzPP5PM: ,! !5 Axioms of probabilityFor any propositions A, B
0 d" P(A) d" 1
P(true) = 1 and P(false) = 0
P(A B) = P(A) + P(B)  P(A B)
>M``,(
)
Prior probabilityPrior or unconditional probabilities of propositions
e.g., P(Cavity = true) = 0.1 and P(Weather = sunny) = 0.72 correspond to belief prior to arrival of any (new) evidence
Probability distribution gives values for all possible assignments:
P(Weather) = <0.72,0.1,0.08,0.1> (normalized, i.e., sums to 1)
Joint probability distribution for a set of random variables gives the probability of every atomic event on those random variables
P(Weather,Cavity) = a 4 2 matrix of values:
Weather = sunny rainy cloudy snow
Cavity = true 0.144 0.02 0.016 0.02
Cavity = false 0.576 0.08 0.064 0.08
Every question about a domain can be answered by the joint distribution
6PxPPEP?PPP/PPxPPIP
N
f b $$((((((((((#((((#((,,I00P<
Conditional probabilityConditional or posterior probabilities
e.g., P(cavity  toothache) = 0.8
i.e., given that toothache is all I know
(Notation for conditional distributions:
P(Cavity  Toothache) = 2element vector of 2element vectors)
If we know more, e.g., cavity is also given, then we have
P(cavity  toothache,cavity) = 1
New evidence may be irrelevant, allowing simplification, e.g.,
P(cavity  toothache, sunny) = P(cavity  toothache) = 0.8
This kind of inference, sanctioned by domain knowledge, is crucial
(PMPP*PAP;P"PAP;PDP * A Dt.jtHXConditional probabilityDefinition of conditional probability:
P(a  b) = P(a b) / P(b) if P(b) > 0
Product rule gives an alternative formulation:
P(a b) = P(a  b) P(b) = P(b  a) P(a)
A general version holds for whole distributions, e.g.,
P(Weather,Cavity) = P(Weather  Cavity) P(Cavity)
(View as a set of 4 2 equations, not matrix mult.)
Chain rule is derived by successive application of product rule:
P(X1, & ,Xn) = P(X1,...,Xn1) P(Xn  X1,...,Xn1)
= P(X1,...,Xn2) P(Xn1  X1,...,Xn2) P(Xn  X1,...,Xn1)
= &
= i= 1^n P(Xi  X1, & ,Xi1)
(P)PP0P*PP8P2P6PPBPP($%8 b
$$$$$$$$
((8((,,,,,
,,,,
,,,,,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,,,,,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,.,,0b04
44444444
4444
4444
444P(8< 0OI<
Inference by enumerationStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
3ZZSZIb,bbj
j $b$((vI,Inference by enumerationxStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
3ZZZIb,bbj
j $b$(( (()((((I,*Inference by enumerationzStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
3ZZZIb,bbj
j $b$(( (()((((((I,+Inference by enumerationStart with the joint probability distribution:
Can also compute conditional probabilities:
P(cavity  toothache) = P(cavity toothache)
P(toothache)
= 0.016+0.064
0.108 + 0.012 + 0.016 + 0.064
= 0.4
aZZZd
N>b O
NormalizationDenominator can be viewed as a normalization constant
P(Cavity  toothache) = , P(Cavity,toothache)
= , [P(Cavity,toothache,catch) + P(Cavity,toothache, catch)]
= , [<0.108,0.016> + <0.012,0.064>]
= , <0.12,0.08> = <0.6,0.4>
General idea: compute distribution on query variable by fixing evidence variables and summing over hidden variables9P1PPtPbB?f:
Inference by enumeration, contd.\Typically, we are interested in
the posterior joint distribution of the query variables} $\mbf{Y}$
given specific values $\mbf{e}$ for the evidence variables} $\mbf{E}$
Let the hidden variables} be $\mbf{H} = \mbf{X}  \mbf{Y}  \mbf{E}$
Then the required summation of joint entries is done by summing out
the hidden variables:
\pv(\mbf{Y}\mbf{E}= \mbf{e}) = \pv(\mbf{Y},\mbf{E}= \mbf{e})
= \mysum_{\smbf{h}} \pv(\mbf{Y},\mbf{E}= \mbf{e},\mbf{H}= \mbf{h})
The terms in the summation are joint entries because $\mbf{Y}$, $\mbf{E}$, and $\mbf{H}$ together exhaust the set of random variables
Obvious problems:
1) Worstcase time complexity $O(d^n)$ where $d$ is the largest arity
2) Space complexity $O(d^n)$ to store the joint distribution
3) How to find the numbers for $O(d^n)$ entries???
xSPPPL7f_!#b
<
cDIndependenceA and B are independent iff
P(AB) = P(A) or P(BA) = P(B) or P(A, B) = P(A) P(B)
P(Toothache, Catch, Cavity, Weather)
= P(Toothache, Catch, Cavity) P(Weather)
32 entries reduced to 12; for n independent biased coins, O(2n) !O(n)
Absolute independence powerful but rare
Dentistry is a large field with hundreds of variables, none of which are independent. What to do?
P?PPPPPGPP)PPcP !
b)cbD DConditional independence{$\pv(Toothache,Cavity,Catch)$ has $2^3  1$ = 7 independent entries
If I have a cavity, the probability that the probe catches in it
doesn't depend on whether I have a toothache:
(1) $P(catchtoothache,cavity) = P(catchcavity)$
The same independence holds if I haven't got a cavity:
(2) $P(catchtoothache,\lnot cavity) = P(catch\lnot cavity)$
$Catch$ is conditionally independent} of $Toothache$ given $Cavity$:
$\pv(CatchToothache,Cavity) = \pv(CatchCavity)$
Equivalent statements:
$\pv(ToothacheCatch,Cavity) = \pv(ToothacheCavity)$
$\pv(Toothache,CatchCavity) = \pv(ToothacheCavity)\pv(CatchCavity)$
.PoC
U! $Conditional independence contd.$Write out full joint distribution using chain rule:
P(Toothache, Catch, Cavity)
= P(Toothache  Catch, Cavity) P(Catch, Cavity)
= P(Toothache  Catch, Cavity) P(Catch  Cavity) P(Cavity)
= P(Toothache  Cavity) P(Catch  Cavity) P(Cavity)
I.e., 2 + 2 + 1 = 5 independent numbers
In most cases, the use of conditional independence reduces the size of the representation of the joint distribution from exponential in n to linear in n.
Conditional independence is our most basic and robust form of knowledge about uncertain environments.
5PPP*PPPPgP5
*
e61Bayes' Rule Product rule $P(a\land b) = P(ab)P(b) = P(ba)P(a)$
{}\implies \mbox{Bayes' rule }} P(ab) = \frac{P(ba)P(a)}{P(b)}
or in distribution form
\pv(YX) = \frac{\pv(XY)\pv(Y)}{\pv(X)} = \pv(XY)\pv(Y)
Useful for assessing diagnostic} probability from causal} probability:
P(CauseEffect) = \frac{P(EffectCause)P(Cause)}{P(Effect)}
E.g., let $M$ be meningitis, $S$ be stiff neck:
P(ms) = \frac{P(sm)P(m)}{P(s)} = \frac{0.8 \times 0.0001}{0.1} = 0.0008
Note: posterior probability of meningitis still very small!
^PG
L&7j(Bayes' Rule and conditional independence$4P(Cavity  toothache catch)
= P(toothache catch  Cavity) P(Cavity)
= P(toothache  Cavity) P(catch  Cavity) P(Cavity)
This is an example of a nave Bayes model:
P(Cause,Effect1, & ,Effectn) = P(Cause) iP(EffectiCause)
Total number of parameters is linear in n
ZdZ,Z=Z/Z
b
"#3Summary@Probability is a rigorous formalism for uncertain knowledge
Joint probability distribution specifies probability of every atomic event
Queries can be answered by summing over atomic events
For nontrivial domains, we must find a way to reduce the joint size
Independence and conditional independence provide the tools
vAZ= }
` 33` Sf3f` 33g` f` www3PP` ZXdbmo` \ғ3y`Ӣ` 3f3ff` 3f3FKf` hk]wwwfܹ` ff>>\`Y{ff` R>& {p_/̴>?" dd@,?" dd@ " @ ` n?" dd@ @@``PR @ ` `p>>f(
6Hxw `}w
T Click to edit Master title style!
!
0ww `w
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
0Hw ^ `w
>*
0/w ^ w
@*
0 ?w ^ `w
@*H
0h ? 3380___PPT10. = Default Design$ $(
r
Sw>w
r
S\&w `
w
H
0h ? 3380___PPT10. =0
@0(
x
c$䢇 `}
x
c$p `
H
0h ? 3380___PPT10.:EF
PF(
x
c$ `}
c$Mu `
"p`PpH
0h ? 3380___PPT10.wE0
$0(
$x
$ c$ `}
x
$ c$ u `
H
$0h ? 3380___PPT10.>E0
(0(
(x
( c$p `}
x
( c$u `
H
(0h ? 3380___PPT10.>E
,(
,x
, c$4 `}
x
, c$u `
X
,
C0Aaxiom3venn` NH
,0h ? 3380___PPT10.2AE
H@0(
0x
0 c$mu `}
x
0 c$u `u
LB
0
c$D
@
LB
0
c$D
0H
00h ? 3380___PPT10.2AE
40(
4x
4 c$8u `}
u
x
4 c$u `u
H
40h ? 33___PPT10i.CE+D=' =
@B +
80(
8x
8 c$u `}
u
x
8 c$O `u
H
80h ? 33___PPT10i.CE+D=' =
@B +
<(
<x
< c$pu `}
u
x
< c$0u `u
\
<
C4Adentistjoint@PPH
<0h ? 3380___PPT10.FE
p(
px
p c$ ! `}
x
p c$ `
^
p
C6Adentistjoint1@PPH
p0h ? 3380___PPT10.FE
t(
tx
t c$h4u `}
u
x
t c$ܚ `u
^
t
C6Adentistjoint2@P H
t0h ? 3380___PPT10.FE>
x>(
x^
x
C6Adentistjoint3@PPx
x c$4B1 `}
1
x
x c$hG1 `1
LB
x
c$D
LB
x
c$DH
x0h ? 3380___PPT10.FE
(
^

C6Adentistjoint4PJx
 c$ `}
w
x
 c$lwb `
H
0h ? 3380___PPT10.FE0
@P0(
Px
P c$ `}
x
P c$@o `
H
P0h ? 3380___PPT10.FE
PT(
Tx
T c$ `}
x
T c$ `
j
T
CBA*weatherindependencePMH
T0h ? 3380___PPT10.^HE0
`X0(
Xx
X c$< `}
x
X c$sb `
H
X0h ? 3380___PPT10.^HE0
p\0(
\x
\ c$W `}
x
\ c$sb `
H
\0h ? 3380___PPT10.^HE0
`0(
`x
` c$ `}
x
` c$mb `
H
`0h ? 3380___PPT10.^HE
d(
dx
d c$b `}
b
x
d c$lb `b
X
d
C0Anaivebayes H
d0h ? 3380___PPT10.^HE0
h0(
hx
h c$ b `}
b
x
h c$b `b
H
h0h ? 3380___PPT10.^HErp}ŉK+c۞lӸCۿ7իm~(
`/0DArial~w0:A 0"DSymbol~w0:A 0@.
@n?" dd@
Onscreen ShowNUSY{
ArialSymbolDefault DesignUncertaintyOutlineUncertainty!Methods for handling uncertaintyProbability#Making decisions under uncertaintySyntaxSyntaxAxioms of probabilityPrior probabilityConditional probabilityConditional probabilityInference Root EntrydO)GNz@PicturessCurrent UserPSummaryInformation(d(
`/0DArial~w0:A 0"DSymbol~w0:A 0@.
@n?" dd@ @@``!Z
`b$nwX(rb$$aab$?XsI3H b$X\\N33G 'b$؋ha#8?]6 N0b$FuSN \9b$.sɇYCb$8%le\0AA@!ʚ;ʚ;g4@d@d :A 0.ppp@<4ddddL$ 0}w&0___PPT10
___PPT9X8?
%Uncertainty
Chapter 13OutlineSUncertainty
Probability
Syntax and Semantics
Inference
Independence and Bayes' RuleHUncertaintybLet action At = leave for airport t minutes before flight
Will At get me there on time?
Problems:
partial observability (road state, other drivers' plans, etc.)
noisy sensors (traffic reports)
uncertainty in action outcomes (flat tire, etc.)
immense complexity of modeling and predicting traffic
Hence a purely logical approach either
risks falsehood: A25 will get me there on time , or
leads to conclusions that are too weak for decision making:
A25 will get me there on time if there's no accident on the bridge and it doesn't rain and my tires remain intact etc etc.
(A1440 might reasonably be said to get me there on time but I'd have to stay overnight in the airport & )
~YPPP" P(Pq" PP
(
\

d,m
o Methods for handling uncertainty!!(Default or nonmonotonic logic:
Assume my car does not have a flat tire
Assume A25 works unless contradicted by evidence
Issues: What assumptions are reasonable? How to handle contradiction?
Rules with fudge factors:
A25 !0.3 get there on time
Sprinkler ! 0.99 WetGrass
WetGrass ! 0.7 Rain
Issues: Problems with combination, e.g., Sprinkler causes Rain??
Probability
Model agent's degree of belief
Given the available evidence,
A25 will get me there on time with probability 0.04
x PZPGPPPNPPPtP 0
'G
b
b
b
) ?
2 >ProbabilityProbabilistic assertions summarize effects of
laziness: failure to enumerate exceptions, qualifications, etc.
ignorance: lack of relevant facts, initial conditions, etc.
Subjective probability:
Probabilities relate propositions to agent's own state of knowledge
e.g., P(A25  no reported accidents) = 0.06
These are not assertions about the world
Probabilities of propositions change with new evidence:
e.g., P(A25  no reported accidents, 5 a.m.) = 0.15
/P~PPPDP/PP*PPoP
9 4
R
"
C
*"Making decisions under uncertaintyNSuppose I believe the following:
P(A25 gets me there on time  & ) = 0.04
P(A90 gets me there on time  & ) = 0.70
P(A120 gets me there on time  & ) = 0.95
P(A1440 gets me there on time  & ) = 0.9999
Which action to choose?
Depends on my preferences for missing flight vs. time spent waiting, etc.
Utility theory is used to represent and infer preferences
Decision theory = probability theory + utility theory
"ZZZLZrZ"
(
(
'
(2( SyntaxBasic element: random variable
Similar to propositional logic: possible worlds defined by assignment of values to random variables.
Boolean random variables
e.g., Cavity (do I have a cavity?)
Discrete random variables
e.g., Weather is one of <sunny,rainy,cloudy,snow>
Domain values must be exhaustive and mutually exclusive
Elementary proposition constructed by assignment of a value to a
random variable: e.g., Weather = sunny, Cavity = false
(abbreviated as cavity)
Complex propositions formed from elementary propositions and standard logical connectives e.g., Weather = sunny Cavity = false
PPePPP$PP2P8PPPPPe8Y `S
Syntax8Atomic event: A complete specification of the state of the world about which the agent is uncertain
E.g., if the world consists of only two Boolean variables Cavity and Toothache, then there are 4 distinct atomic events:
Cavity = false Toothache = false
Cavity = false Toothache = true
Cavity = true Toothache = false
Cavity = true Toothache = true
!"#$%&'()*+,./0123456789;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopq
PowerPoint Document(:YDocumentSummaryInformation8 @@``!Z
`b$nwX(rb$$aab$?XsI3H b$X\\N33G 'b$؋ha#8?]6 N0b$FuSN \9b$.sɇYCb$8%le\0AA@ʚ;ʚ;g4@d@d :A 0.ppp@<4ddddL$ 0}w0___PPT10
___PPT9X,?
%wUncertainty
Chapter 13OutlineSUncertainty
Probability
Syntax and Semantics
Inference
Independence and Bayes' RuleHUncertaintybLet action At = leave for airport t minutes before flight
Will At get me there on time?
Problems:
partial observability (road state, other drivers' plans, etc.)
noisy sensors (traffic reports)
uncertainty in action outcomes (flat tire, etc.)
immense complexity of modeling and predicting traffic
Hence a purely logical approach either
risks falsehood: A25 will get me there on time , or
leads to conclusions that are too weak for decision making:
A25 will get me there on time if there's no accident on the bridge and it doesn't rain and my tires remain intact etc etc.
(A1440 might reasonably be said to get me there on time but I'd have to stay overnight in the airport & )
~YPPP" P(Pq" PP
(
\

d,m
o Methods for handling uncertainty!!(Default or nonmonotonic logic:
Assume my car does not have a flat tire
Assume A25 works unless contradicted by evidence
Issues: What assumptions are reasonable? How to handle contradiction?
Rules with fudge factors:
A25 !0.3 get there on time
Sprinkler ! 0.99 WetGrass
WetGrass ! 0.7 Rain
Issues: Problems with combination, e.g., Sprinkler causes Rain??
Probability
Model agent's degree of belief
Given the available evidence,
A25 will get me there on time with probability 0.04
x PZPGPPPNPPPtP 0
'G
b
b
b
) ?
2 >ProbabilityProbabilistic assertions summarize effects of
laziness: failure to enumerate exceptions, qualifications, etc.
ignorance: lack of relevant facts, initial conditions, etc.
Subjective probability:
Probabilities relate propositions to agent's own state of knowledge
e.g., P(A25  no reported accidents) = 0.06
These are not assertions about the world
Probabilities of propositions change with new evidence:
e.g., P(A25  no reported accidents, 5 a.m.) = 0.15
/P~PPPDP/PP*PPoP
9 4
R
"
C
*"Making decisions under uncertaintyNSuppose I believe the following:
P(A25 gets me there on time  & ) = 0.04
P(A90 gets me there on time  & ) = 0.70
P(A120 gets me there on time  & ) = 0.95
P(A1440 gets me there on time  & ) = 0.9999
Which action to choose?
Depends on my preferences for missing flight vs. time spent waiting, etc.
Utility theory is used to represent and infer preferences
Decision theory = probability theory + utility theory
"ZZZLZrZ"
(
(
'
(2( SyntaxBasic element: random variable
Similar to propositional logic: possible worlds defined by assignment of values to random variables.
Boolean random variables
e.g., Cavity (do I have a cavity?)
Discrete random variables
e.g., Weather is one of <sunny,rainy,cloudy,snow>
Domain values must be exhaustive and mutually exclusive
Elementary proposition constructed by assignment of a value to a
random variable: e.g., Weather = sunny, Cavity = false
(abbreviated as cavity)
Complex propositions formed from elementary propositions and standard logical connectives e.g., Weather = sunny Cavity = false
PPePPP$PP2P8PPPPPe8Y `S
Syntax8Atomic event: A complete specification of the state of the world about which the agent is uncertain
E.g., if the world consists of only two Boolean variables Cavity and Toothache, then there are 4 distinct atomic events:
Cavity = false Toothache = false
Cavity = false Toothache = true
Cavity = true Toothache = false
Cavity = true Toothache = true
Atomic events are mutually exclusive and exhaustive
ePzPP5PM: ,! !5 Axioms of probabilityFor any propositions A, B
0 d" P(A) d" 1
P(true) = 1 and P(false) = 0
P(A B) = P(A) + P(B)  P(A B)
>M``,(
)
Prior probabilityPrior or unconditional probabilities of propositions
e.g., P(Cavity = true) = 0.1 and P(Weather = sunny) = 0.72 correspond to belief prior to arrival of any (new) evidence
Probability distribution gives values for all possible assignments:
P(Weather) = <0.72,0.1,0.08,0.1> (normalized, i.e., sums to 1)
Joint probability distribution for a set of random variables gives the probability of every atomic event on those random variables
P(Weather,Cavity) = a 4 2 matrix of values:
Weather = sunny rainy cloudy snow
Cavity = true 0.144 0.02 0.016 0.02
Cavity = false 0.576 0.08 0.064 0.08
Every question about a domain can be answered by the joint distribution
6PxPPEP?PPP/PPxPPIP
N
f b $$((((((((((#((((#((,,I00P<
Conditional probabilityConditional or posterior probabilities
e.g., P(cavity  toothache) = 0.8
i.e., given that toothache is all I know
(Notation for conditional distributions:
P(Cavity  Toothache) = 2element vector of 2element vectors)
If we know more, e.g., cavity is also given, then we have
P(cavity  toothache,cavity) = 1
New evidence may be irrelevant, allowing simplification, e.g.,
P(cavity  toothache, sunny) = P(cavity  toothache) = 0.8
This kind of inference, sanctioned by domain knowledge, is crucial
(PMPP*PAP;P"PAP;PDP * A Dt.jtHXConditional probabilityDefinition of conditional probability:
P(a  b) = P(a b) / P(b) if P(b) > 0
Product rule gives an alternative formulation:
P(a b) = P(a  b) P(b) = P(b  a) P(a)
A general version holds for whole distributions, e.g.,
P(Weather,Cavity) = P(Weather  Cavity) P(Cavity)
(View as a set of 4 2 equations, not matrix mult.)
Chain rule is derived by successive application of product rule:
P(X1, & ,Xn) = P(X1,...,Xn1) P(Xn  X1,...,Xn1)
= P(X1,...,Xn2) P(Xn1  X1,...,Xn2) P(Xn  X1,...,Xn1)
= &
= i= 1^n P(Xi  X1, & ,Xi1)
(P)PP0P*PP8P2P6PPBPP($%8 b
$$$$$$$$
((8((,,,,,
,,,,
,,,,,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,,,,,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,.,,0b04
44444444
4444
4444
444P(8< 0OI<
Inference by enumerationStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
3ZZSZIb,bbj
j $b$((vI,Inference by enumerationxStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
3ZZZIb,bbj
j $b$(( (()((((I,*Inference by enumerationzStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
3ZZZIb,bbj
j $b$(( (()((((((I,+Inference by enumerationStart with the joint probability distribution:
Can also compute conditional probabilities:
P(cavity  toothache) = P(cavity toothache)
P(toothache)
= 0.016+0.064
0.108 + 0.012 + 0.016 + 0.064
= 0.4
aZZZd
N>b O
NormalizationDenominator can be viewed as a normalization constant
P(Cavity  toothache) = , P(Cavity,toothache)
= , [P(Cavity,toothache,catch) + P(Cavity,toothache, catch)]
= , [<0.108,0.016> + <0.012,0.064>]
= , <0.12,0.08> = <0.6,0.4>
General idea: compute distribution on query variable by fixing evidence variables and summing over hidden variables9P1PPtPbB?f:
Inference by enumeration, contd.Typically, we are interested in the posterior joint distribution of the query variables \mbf{Y}
given specific values \mbf{e} for the evidence variables $\mbf{E}$
Let the hidden variables be $\mbf{H} = \mbf{X}  \mbf{Y}  \mbf{E}$
Then the required summation of joint entries is done by summing out
the hidden variables:
\pv(\mbf{Y}\mbf{E}= \mbf{e}) = \pv(\mbf{Y},\mbf{E}= \mbf{e})
= \mysum_{\smbf{h}} \pv(\mbf{Y},\mbf{E}= \mbf{e},\mbf{H}= \mbf{h})
The terms in the summation are joint entries because $\mbf{Y}$, $\mbf{E}$, and $\mbf{H}$ together exhaust the set of random variables
Obvious problems:
Worstcase time complexity O(dn) where d is the largest arity
Space complexity O(dn) to store the joint distribution
How to find the numbers for O(dn) entries???
PHPP"P" PH2"
(
>
Y"b
<
_?IndependenceA and B are independent iff
P(AB) = P(A) or P(BA) = P(B) or P(A, B) = P(A) P(B)
P(Toothache, Catch, Cavity, Weather)
= P(Toothache, Catch, Cavity) P(Weather)
32 entries reduced to 12; for n independent biased coins, O(2n) !O(n)
Absolute independence powerful but rare
Dentistry is a large field with hundreds of variables, none of which are independent. What to do?
P?PPPPPGPP)PPcP !
b)cbD DConditional independence{$\pv(Toothache,Cavity,Catch)$ has $2^3  1$ = 7 independent entries
If I have a cavity, the probability that the probe catches in it
doesn't depend on whether I have a toothache:
(1) $P(catchtoothache,cavity) = P(catchcavity)$
The same independence holds if I haven't got a cavity:
(2) $P(catchtoothache,\lnot cavity) = P(catch\lnot cavity)$
$Catch$ is conditionally independent} of $Toothache$ given $Cavity$:
$\pv(CatchToothache,Cavity) = \pv(CatchCavity)$
Equivalent statements:
$\pv(ToothacheCatch,Cavity) = \pv(ToothacheCavity)$
$\pv(Toothache,CatchCavity) = \pv(ToothacheCavity)\pv(CatchCavity)$
.PoC
U! $Conditional independence contd.$Write out full joint distribution using chain rule:
P(Toothache, Catch, Cavity)
= P(Toothache  Catch, Cavity) P(Catch, Cavity)
= P(Toothache  Catch, Cavity) P(Catch  Cavity) P(Cavity)
= P(Toothache  Cavity) P(Catch  Cavity) P(Cavity)
I.e., 2 + 2 + 1 = 5 independent numbers
In most cases, the use of conditional independence reduces the size of the representation of the joint distribution from exponential in n to linear in n.
Conditional independence is our most basic and robust form of knowledge about uncertain environments.
5PPP*PPPPgP5
*
e61Bayes' Rule Product rule $P(a\land b) = P(ab)P(b) = P(ba)P(a)$
{}\implies \mbox{Bayes' rule }} P(ab) = \frac{P(ba)P(a)}{P(b)}
or in distribution form
\pv(YX) = \frac{\pv(XY)\pv(Y)}{\pv(X)} = \pv(XY)\pv(Y)
Useful for assessing diagnostic} probability from causal} probability:
P(CauseEffect) = \frac{P(EffectCause)P(Cause)}{P(Effect)}
E.g., let $M$ be meningitis, $S$ be stiff neck:
P(ms) = \frac{P(sm)P(m)}{P(s)} = \frac{0.8 \times 0.0001}{0.1} = 0.0008
Note: posterior probability of meningitis still very small!
^PG
L&7j(Bayes' Rule and conditional independence$4P(Cavity  toothache catch)
= P(toothache catch  Cavity) P(Cavity)
= P(toothache  Cavity) P(catch  Cavity) P(Cavity)
This is an example of a nave Bayes model:
P(Cause,Effect1, & ,Effectn) = P(Cause) iP(EffectiCause)
Total number of parameters is linear in n
ZdZ,Z=Z/Z
b
"#3Summary@Probability is a rigorous formalism for uncertain knowledge
Joint probability distribution specifies probability of every atomic event
Queries can be answered by summing over atomic events
For nontrivial domains, we must find a way to reduce the joint size
Independence and conditional independence provide the tools
vAZ= }
@
@P@(
Px
P c$ `}
P c$@o `
0H
P0h ? 3380___PPT10.FErzAmCen SEKEROh+'04`h
UncertaintyMinYen KanMinYen Kan8nMicrosoft PowerPointP@?71 @ ի@"'lG0g @ !'@"Arial. 2
PZUncertainty,""""."System@@"Arial. 2
Chapter 13
.՜.+,0
Atomic events are mutually exclusive and exhaustive
ePzPP5PM: ,! !5 Axioms of probabilityFor any propositions A, B
0 d" P(A) d" 1
P(true) = 1 and P(false) = 0
P(A B) = P(A) + P(B)  P(A B)
>M``,(
)
Prior probabilityPrior or unconditional probabilities of propositions
e.g., P(Cavity = true) = 0.1 and P(Weather = sunny) = 0.72 correspond to belief prior to arrival of any (new) evidence
Probability distribution gives values for all possible assignments:
P(Weather) = <0.72,0.1,0.08,0.1> (normalized, i.e., sums to 1)
Joint probability distribution for a set of random variables gby enumerationInference by enumerationInference by enumerationInference by enumerationNormalization!Inference by enumeration, contd.
IndependenceConditional independence Conditional independence contd.Bayes' Rule)Bayes' Rule and conditional independenceSummaryFonts UsedDesign Template
Slide Titles(_XSadi Evren SEKERSadi Evrives the probability of every atomic event on those random variables
P(Weather,Cavity) = a 4 2 matrix of values:
Weather = sunny rainy cloudy snow
Cavity = true 0.144 0.02 0.016 0.02
Cavity = false 0.576 0.08 0.064 0.08
Every question about a domain can be answered by the joint distribution
6PxPPEP?PPP/PPxPPIP
N
f b $$((((((((((#((((#((,,I00P<
Conditional probabilityConditional or posterior probabilities
e.g., P(cavity  toothache) = 0.8
i.e., given that toothache is all I know
(Notation for conditional distributions:
P(Cavity  Toothache) = 2element vector of 2element vectors)
If we know more, e.g., cavity is also given, then we have
P(cavity  toothache,cavity) = 1
New evidence may be irrelevant, allowing simplification, e.g.,
P(cavity  toothache, sunny) = P(cavity  toothache) = 0.8
This kind of inference, sanctioned by domain knowledge, is crucial
(PMPP*PAP;P"PAP;PDP * A Dt.jtHXConditional probabilityDefinition of conditional probability:
P(a  b) = P(a b) / P(b) if P(b) > 0
Product rule gives an alternative formulation:
P(a b) = P(a  b) P(b) = P(b  a) P(a)
A general version holds for whole distributions, e.g.,
P(Weather,Cavity) = P(Weather  Cavity) P(Cavity)
(View as a set of 4 2 equations, not matrix mult.)
Chain rule is derived by successive application of product rule:
P(X1, & ,Xn) = P(X1,...,Xn1) P(Xn  X1,...,Xn1)
= P(X1,...,Xn2) P(Xn1  X1,...,Xn2) P(Xn  X1,...,Xn1)
= &
= i= 1^n P(Xi  X1, & ,Xi1)
(P)PP0P*PP8P2P6PPBPP($%8 b
$$$$$$$$
((8((,,,,,
,,,,
,,,,,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,,,,,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,.,,0b04
44444444
4444
4444
444P(8< 0OI<
Inference by enumerationStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
3ZZSZIb,bbj
j $b$((vI,Inference by enumerationxStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
3ZZZIb,bbj
j $b$(( (()((((I,*Inference by enumerationzStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
3ZZZIb,bbj
j $b$(( (()((((((I,+Inference by enumerationStart with the joint probability distribution:
Can also compute conditional probabilities:
P(cavity  toothache) = P(cavity toothache)
P(toothache)
= 0.016+0.064
0.108 + 0.012 + 0.016 + 0.064
= 0.4
aZZZd
N>b O
NormalizationDenominator can be viewed as a normalization constant
P(Cavity  toothache) = , P(Cavity,toothache)
= , [P(Cavity,toothache,catch) + P(Cavity,toothache, catch)]
= , [<0.108,0.016> + <0.012,0.064>]
= , <0.12,0.08> = <0.6,0.4>
General idea: compute distribution on query variable by fixing evidence variables and summing over hidden variables9P1PPtPbB?f:
Inference by enumeration, contd.Typically, we are interested in
the posterior joint distribution of the query variables Y
given specific values e for the evidence variables E
Let the hidden variables be H = X  Y  E
Then the required summation of joint entries is done by summing out the hidden variables:
P(Y  E = e) = P(Y,E = e) = hP(Y,E= e, H = h)
The terms in the summation are joint entries because Y, E and H together exhaust the set of random variables
Obvious problems:
Worstcase time complexity O(dn) where d is the largest arity
Space complexity O(dn) to store the joint distribution
How to find the numbers for O(dn) entries?P2PP" PJ ^b
6C
(
>
+ ?IndependenceA and B are independent iff
P(AB) = P(A) or P(BA) = P(B) or P(A, B) = P(A) P(B)
P(Toothache, Catch, Cavity, Weather)
= P(Toothache, Catch, Cavity) P(Weather)
32 entries reduced to 12; for n independent biased coins, O(2n) !O(n)
Absolute independence powerful but rare
Dentistry is a large field with hundreds of variables, none of which are independent. What to do?
P?PPPPPGPP)PPcP !
b)cbD DConditional independenceP(Toothache, Cavity, Catch) has 23 1 = 7 independent entries
If I have a cavity, the probability that the probe catches in it doesn't depend on whether I have a toothache:
(1) P(catch  toothache, cavity) = P(catch  cavity)
The same independence holds if I haven't got a cavity:
(2) P(catch  toothache,cavity) = P(catch  cavity)
Catch is conditionally independent of Toothache given Cavity:
P(Catch  Toothache,Cavity) = P(Catch  Cavity)
Equivalent statements:
P(Toothache  Catch, Cavity) = P(Toothache  Cavity)
P(Toothache, Catch  Cavity) = P(Toothache  Cavity) P(Catch  Cavity)
@PPpP5PP8P6PP?P1PPP~P
p8
$$((,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,HM$Conditional independence contd.$Write out full joint distribution using chain rule:
P(Toothache, Catch, Cavity)
= P(Toothache  Catch, Cavity) P(Catch, Cavity)
= P(Toothache  Catch, Cavity) P(Catch  Cavity) P(Cavity)
= P(Toothache  Cavity) P(Catch  Cavity) P(Cavity)
I.e., 2 + 2 + 1 = 5 independent numbers
In most cases, the use of conditional independence reduces the size of the representation of the joint distribution from exponential in n to linear in n.
Conditional independence is our most basic and robust form of knowledge about uncertain environments.
5PPP*PPPPgP5
*
e61Bayes' RuleProduct rule P(ab) = P(a  b) P(b) = P(b  a) P(a)
Bayes' rule: P(a  b) = P(b  a) P(a) / P(b)
or in distribution form
P(YX) = P(XY) P(Y) / P(X) = P(XY) P(Y)
Useful for assessing diagnostic probability from causal probability:
P(CauseEffect) = P(EffectCause) P(Cause) / P(Effect)
E.g., let M be meningitis, S be stiff neck:
P(ms) = P(sm) P(m) / P(s) = 0.8 0.0001 / 0.1 = 0.0008
Note: posterior probability of meningitis still very small!
65P1PPPPPFPfP;P=P$
!C"b=p
>G1^(Bayes' Rule and conditional independence$4P(Cavity  toothache catch)
= P(toothache catch  Cavity) P(Cavity)
= P(toothache  Cavity) P(catch  Cavity) P(Cavity)
This is an example of a nave Bayes model:
P(Cause,Effect1, & ,Effectn) = P(Cause) iP(EffectiCause)
Total number of parameters is linear in n
ZdZ,Z=Z/Z
b
"#3Summary@Probability is a rigorous formalism for uncertain knowledge
Joint probability distribution specifies probability of every atomic event
Queries can be answered by summing over atomic events
For nontrivial domains, we must find a way to reduce the joint size
Independence and conditional independence provide the tools
vAZ= }
@
@P@(
Px
P c$ `}
P c$@o `
0H
P0h ? 3380___PPT10.FE0
`X0(
Xx
X c$< `}
x
X c$sb `
H
X0h ? 3380___PPT10.^HE0
`0(
`x
` c$ `}
x
` c$mb `
H
`0h ? 3380___PPT10.^HEr C2jmC(
`/0DArial~w0:A 0"DSymbol~w0:A 0@.
@n?" dd@ @@``!Z
`b$nwX(rb$$aab$?XsI3H b$X\\N33G 'b$؋ha#8?]6 N0b$FuSN \9b$.sɇYCb$8%le\0AA@!ʚ;ʚ;g4@d@d :A 0.ppp@<4ddddL$ 0}w&0___PPT10
___PPT9X8?
%Uncertainty
Chapter 13OutlineSUncertainty
Probability
Syntax and Semantics
Inference
Independence and Bayes' RuleHUncertaintybLet action At = leave for airport t minutes before flight
Will At get me there on time?
Problems:
partial observability (road state, other drivers' plans, etc.)
noisy sensors (traffic reports)
uncertainty in action outcomes (flat tire, etc.)
immense complexity of modeling and predicting traffic
Hence a purely logical approach either
risks falsehood: A25 will get me there on time , or
leads to conclusions that are too weak for decision making:
A25 will get me there on time if there's no accident on the bridge and it doesn't rain and my tires remain intact etc etc.
(A1440 might reasonably be said to get me there on time but I'd have to stay overnight in the airport & )
~YPPP" P(Pq" PP
(
\

d,m
o Methods for handling uncertainty!!(Default or nonmonotonic logic:
Assume my car does not have a flat tire
Assume A25 works unless contradicted by evidence
Issues: What assumptions are reasonable? How to handle contradiction?
Rules with fudge factors:
A25 !0.3 get there on time
Sprinkler ! 0.99 WetGrass
WetGrass ! 0.7 Rain
Issues: Problems with combination, e.g., Sprinkler causes Rain??
Probability
Model agent's degree of belief
Given the available evidence,
A25 will get me there on time with probability 0.04
x PZPGPPPNPPPtP 0
'G
b
b
b
) ?
2 >ProbabilityProbabilistic assertions summarize effects of
laziness: failure to enumerate exceptions, qualifications, etc.
ignorance: lack of relevant facts, initial conditions, etc.
Subjective probability:
Probabilities relate propositions to agent's own state of knowledge
e.g., P(A25  no reported accidents) = 0.06
These are not assertions about the world
Probabilities of propositions change with new evidence:
e.g., P(A25  no reported accidents, 5 a.m.) = 0.15
/P~PPPDP/PP*PPoP
9 4
R
"
C
*"Making decisions under uncertaintyNSuppose I believe the following:
P(A25 gets me there on time  & ) = 0.04
P(A90 gets me there on time  & ) = 0.70
P(A120 gets me there on time  & ) = 0.95
P(A1440 gets me there on time  & ) = 0.9999
Which action to choose?
Depends on my preferences for missing flight vs. time spent waiting, etc.
Utility theory is used to represent and infer preferences
Decision theory = probability theory + utility theory
"ZZZLZrZ"
(
(
'
(2( SyntaxBasic element: random variable
Similar to propositional logic: possible worlds defined by assignment of values to random variables.
Boolean random variables
e.g., Cavity (do I have a cavity?)
Discrete random variables
e.g., Weather is one of <sunny,rainy,cloudy,snow>
Domain values must be exhaustive and mutually exclusive
Elementary proposition constructed by assignment of a value to a
random variable: e.g., Weather = sunny, Cavity = false
(abbreviated as cavity)
Complex propositions formed from elementary propositions and standard logical connectives e.g., Weather = sunny Cavity = false
PPePPP$PP2P8PPPPPe8Y `S
Syntax8Atomic event: A complete specification of the state of the world about which the agent is uncertain
E.g., if the world consists of only two Boolean variables Cavity and Toothache, then there are 4 distinct atomic events:
Cavity = false Toothache = false
Cavity = false Toothache = true
Cavity = true Toothache = false
Cavity = true Toothache = true
Atomic events are mutually exclusive and exhaustive
ePzPP5PM: ,! !5 Axioms of probabilityFor any propositions A, B
0 d" P(A) d" 1
P(true) = 1 and P(false) = 0
P(A B) = P(A) + P(B)  P(A B)
>M``,(
)
Prior probabilityPrior or unconditional probabilities of propositions
e.g., P(Cavity = true) = 0.1 and P(Weather = sunny) = 0.72 correspond to belief prior to arrival of any (new) evidence
Probability distribution gives values for all possible assignments:
P(Weather) = <0.72,0.1,0.08,0.1> (normalized, i.e., sums to 1)
Joint probability distribution for a set of random variables gives the probability of every atomic event on those random variables
P(Weather,Cavity) = a 4 2 matrix of values:
Weather = sunny rainy cloudy snow
Cavity = true 0.144 0.02 0.016 0.02
Cavity = false 0.576 0.08 0.064 0.08
Every question about a domain can be answered by the joint distribution
6PxPPEP?PPP/PPxPPIP
N
f b $$((((((((((#((((#((,,I00P<
Conditional probabilityConditional or posterior probabilities
e.g., P(cavity  toothache) = 0.8
i.e., given that toothache is all I know
(Notation for conditional distributions:
P(Cavity  Toothache) = 2element vector of 2element vectors)
If we know more, e.g., cavity is also given, then we have
P(cavity  toothache,cavity) = 1
New evidence may be irrelevant, allowing simplification, e.g.,
P(cavity  toothache, sunny) = P(cavity  toothache) = 0.8
This kind of inference, sanctioned by domain knowledge, is crucial
(PMPP*PAP;P"PAP;PDP * A Dt.jtHXConditional probabilityDefinition of conditional probability:
P(a  b) = P(a b) / P(b) if P(b) > 0
Product rule gives an alternative formulation:
P(a b) = P(a  b) P(b) = P(b  a) P(a)
A general version holds for whole distributions, e.g.,
P(Weather,Cavity) = P(Weather  Cavity) P(Cavity)
(View as a set of 4 2 equations, not matrix mult.)
Chain rule is derived by successive application of product rule:
P(X1, & ,Xn) = P(X1,...,Xn1) P(Xn  X1,...,Xn1)
= P(X1,...,Xn2) P(Xn1  X1,...,Xn2) P(Xn  X1,...,Xn1)
= &
= i= 1^n P(Xi  X1, & ,Xi1)
(P)PP0P*PP8P2P6PPBPP($%8 b
$$$$$$$$
((8((,,,,,
,,,,
,,,,,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,,,,,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,,,,,,,,
,,,,
,,,,
,.,,0b04
44444444
4444
4444
444P(8< 0OI<
Inference by enumerationStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
3ZZSZIb,bbj
j $b$((vI,Inference by enumerationxStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
3ZZZIb,bbj
j $b$(( (()((((I,*Inference by enumerationzStart with the joint probability distribution:
For any proposition , sum the atomic events where it is true: P() = :^% P()
P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
3ZZZIb,bbj
j $b$(( (()((((((I,+Inference by enumerationStart with the joint probability distribution:
Can also compute conditional probabilities:
P(cavity  toothache) = P(cavity toothache)
P(toothache)
= 0.016+0.064
0.108 + 0.012 + 0.016 + 0.064
= 0.4
aZZZd
N>b O
NormalizationDenominator can be viewed as a normalization constant
P(Cavity  toothache) = , P(Cavity,toothache)
= , [P(Cavity,toothache,catch) + P(Cavity,toothache, catch)]
= , [<0.108,0.016> + <0.012,0.064>]
= , <0.12,0.08> = <0.6,0.4>
General idea: compute distribution on query variable by fixing evidence variables and summing over hidden variables9P1PPtPbB?f:
Inference by enumeration, contd.Typically, we are interested in
the posterior joint distribution of the query variables Y
given specific values e for the evidence variables E
Let the hidden variables be H = X  Y  E
Then the required summation of joint entries is done by summing out the hidden variables:
P(Y  E = e) = P(Y,E = e) = hP(Y,E= e, H = h)
The terms in the summation are joint entries because Y, E and H together exhaust the set of random variables
Obvious problems:
Worstcase time complexity O(dn) where d is the largest arity
Space complexity O(dn) to store the joint distribution
How to find the numbers for O(dn) entries?P2PP" PJ ^b
6C
(
>
+ ?IndependenceA and B are independent iff
P(AB) = P(A) or P(BA) = P(B) or P(A, B) = P(A) P(B)
P(Toothache, Catch, Cavity, Weather)
= P(Toothache, Catch, Cavity) P(Weather)
32 entries reduced to 12; for n independent biased coins, O(2n) !O(n)
Absolute independence powerful but rare
Dentistry is a large field with hundreds of variables, none of which are independent. What to do?
P?PPPPPGPP)PPcP !
b)cbD DConditional independenceP(Toothache, Cavity, Catch) has 23 1 = 7 independent entries
If I have a cavity, the probability that the probe catches in it doesn't depend on whether I have a toothache:
(1) P(catch  toothache, cavity) = P(catch  cavity)
The same independence holds if I haven't got a cavity:
(2) P(catch  toothache,cavity) = P(catch  cavity)
Catch is conditionally independent of Toothache given Cavity:
P(Catch  Toothache,Cavity) = P(Catch  Cavity)
Equivalent statements:
P(Toothache  Catch, Cavity) = P(Toothache  Cavity)
P(Toothache, Catch  Cavity) = P(Toothache  Cavity) P(Catch  Cavity)
@PPpP5PP8P6PP?P1PPP~P
p8
$$((,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,HM$Conditional independence contd.$Write out full joint distribution using chain rule:
P(Toothache, Catch, Cavity)
= P(Toothache  Catch, Cavity) P(Catch, Cavity)
= P(Toothache  Catch, Cavity) P(Catch  Cavity) P(Cavity)
= P(Toothache  Cavity) P(Catch  Cavity) P(Cavity)
I.e., 2 + 2 + 1 = 5 independent numbers
In most cases, the use of conditional independence reduces the size of the representation of the joint distribution from exponential in n to linear in n.
Conditional independence is our most basic and robust form of knowledge about uncertain environments.
5PPP*PPPPgP5
*
e61Bayes' RuleProduct rule P(ab) = P(a  b) P(b) = P(b  a) P(a)
Bayes' rule: P(a  b) = P(b  a) P(a) / P(b)
or in distribution form
P(YX) = P(XY) P(Y) / P(X) = P(XY) P(Y)
Useful for assessing diagnostic probability from causal probability:
P(CauseEffect) = P(EffectCause) P(Cause) / P(Effect)
E.g., let M be meningitis, S be stiff neck:
P(ms) = P(sm) P(m) / P(s) = 0.8 0.0001 / 0.1 = 0.0008
Note: posterior probability of meningitis still very small!
65P1PPPPPFPfP;P=P$
!C"b=p
>G1^(Bayes' Rule and conditional independence$4P(Cavity  toothache catch)
= P(toothache catch  Cavity) P(Cavity)
= P(toothache  Cavity) P(catch  Cavity) P(Cavity)
This is an example of a nave Bayes model:
P(Cause,Effect1, & ,Effectn) = P(Cause) iP(EffectiCause)
Total number of parameters is linear in n
ZdZ,Z=Z/Z
b
"#3Summary@Probability is a rigorous formalism for uncertain knowledge
Joint probability distribution specifies probability of every atomic event
Queries can be answered by summing over atomic events
For nontrivial domains, we must find a way to reduce the joint size
Independence and conditional independence provide the tools
vAZ= }
rmX