### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 683 at UMass(16)

### View Full Document

## 23

## 0

## Popular in Course

## Popular in Department

This 22 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 23 views.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 683 at UMass(16)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Victor Lesser CMPSCI 683 Fall 2004 Continuation of Inference in Belief Networks Automated Belief propagation in PolyTrees V Les DEM HUN 2 Victor Lesser CMPSCI 683 Fall 2004 Continuation of Inference in Belief Networks Automated Belief propagation in PolyTrees V Les DEM HUN 2 Network construction Conditional independence of a node and its predecessors given its parents The absence of a link between two variables does not guarantee their independence Effective inference needs to exploit all available conditional independences Which set of nodes X are conditionally independent of another set Y given a set of evidence nodes E PXYE PXE PYE Limits propagation of information Comes directly from structure of network v Lessei saaa mm a Definition If X Y and E are three disjoint subsets of nodes in a DAG then E is said to d separate X from Y if every undirected path from X to Y is blocked by E A path is blocked if it contains a node Z such that 1 Z has one incoming and one outgoing arrow or 2 Z has two outgoing arrows or 3 Z has two incoming arrows and neither Z nor any of its descendants is in E v Lessei saaa mm A v umvcsmmm 5 Property of belief networks ifX and Y are d separated by E then X and Y are conditionally independent given E An ifandonlyif relationship between the graph and the probabilistic model cannot always be achieved v msucsmmm 5 Whether there is Gas in the car and whetherthe car Radio plays are independent given evidence about whether the SparPlugs fire ignition case 1 man POM PGI PGIR PGI v maussmmm 7 Gas and Radio are conditionalIyindependent if it is known if the battery works caseZ PRBG POUR PGBRPGB v nssuc b a STARTSKM OVES lNZ EUTALSO W E FOR CASE 3 Gasand Rado are independent given no evidence at all But theyare dependent given evidence about whetherthe car Stals For example it the cardoes not start then the radio playing is increased evidence that we are out olgas Gas and Radio are also dependent given evidence about whether the car Moves because that is enabled bythe car starting PGaisadioPGas PRadiolGasPRadio PGasl RadioStart not PGaslStart v Mammal s o BNs are fairly expressive and easily engineered representation for knowledge in probabilistic domains 0 They facilitate the development of inference algorithms 0 They are particularly suited for parallelization Current inference algorithms are efficient and can solve large realworld problems v umvcsmmm tn Topology trees sinIyconnected sparsely connected DAGs Size number of nodes Type of variables discrete cont functional noisylogical mixed v msucsmmm Network dynamics static dynamic it Polytree belief network where nodes are singly connected 39Ex1ct inference Linen in size of network Mnlticonnected belief network This is a DAG but not a polytree Enct infenenee Worst use NP hard v Mammal Hi A12 A A1 A A A5 MW 7 E5 Hi H2 3 ANN A AZ ha AA Aj 12 is atury Mixed v ussucsmmm 13 What is pY5Y1Y4 7 De nemmstPTspY5Y4Y3Y2Y1 YI yz 7 pY5Y3Y4pY4pY3Y1Y2 pY2 pY1 r pY5Y1Y4 pY5Y1Y4pY1Y4 r Usecmosum owrmi ngva abls ys A 7 pY5Y1Y4 SumY2Y3 pY5Y4Y3Y2Y1 r aSuming van39abls take on only truth or falsity l pY5Y1Y4 pY5Y3Yl Y4 PY5 not Y3 Y1Y4 y5 7 Connect to mmms of Y5 not aheadypartof expmon by marginalization sums pY5Y3Y1Y4 v msucsmmm M SUMY3p SlY3 Yll4pY3lY1Y4 7 Ps ldPglsdP ld y1 y1 SUMY3ij5lY3 Y4p YSlYl Y4 7 Y1 conditionally independent of Y5 giVenY3 7 Y3 repments all the contributions d Y1 to Y5 3 Y4 7 Cm 1 nmieixmniimmlly inmmmenloiml desimiants given its mums SUMY3 pY5lY3 Y4 pY3lY1 Y5 7 Y4 conditionally independent of Y3 given Y1 7 Ca 3 Y3 not admmhnt of Y5 whichdseparats Y1 and Y4 v maussmmm 5 SUMY3 pY5lY3Y4 Sum Y2pY3 Y2 lY1 y y 7 Connect mums on3 notalmadyjnnof 1 2 expenion SUMY3 pY5lY3 Y4 Sum Y2 y3 y4 pY3lYlY2 9Y2lYl psiasjld PSil Syd psjd product rule YS 39 SUMY3 pY5lY3 Y4 SUMY2 pY3lY1Y2M 7 Y2 independent of Y1 pY2Y1pY2 7 De nilion of Bayman network v nssuc m 5 What is pY1Y5 Y1 Y2 7 pY1Y5pY1Y5pY5 r pYlY2Y3Y4Y5 in terms of cpt r pY5Y3Y4pY3Y1Y2pY1pY2pY4 y3 4 pY1Y5 pY5Y1pY1pY5 J r Bayes Rule ys o K pY5Y1pY1 v ussucsmmm 17 v 55 K pY5YlpY1 K SUMME15Y3pY31Y1gtpY1 7 Connectw WparmtonSnotahmdypa ofexpreshn 7 Ps l SUMdPg d Pd 7 Y1 oondiu39omlly independent of Ys givenY 7 pY5Y3YlpY5Y3 y3 K quot SUMY3 SUMY4pY 5 Y3 Y4EY41Y3pY31Y1 W1 7 Connectw Y4 parentonS nommdypanotexpmhn 7 my SUMdPg d Pd Y5 K quot SUMY3 SUMCMMY5 Y3 Y4pY4pY31Y 1 W1 7 Y4 independent om pY4lY3 pm mam mm m K SUMY3 SUMY4pY5Y3Y4pY4pY3Y1J pY1 Y1 Ya 39 K SUMY3 SUMY4p Y5iY3 Y4p Y4SUMY2p Y 3 Y1Y2JY21Yl pYl y3 y4 r Connecttn Y2 parent on3 not alseadypartof expession 7 Psilsj SUMdPsi sj d Pd Isj i YS 39 K SUMY3 SUMY4pY5Y3 Y4pY4SUMY2pY3i Y1 mm pm 7 Y2 independent of Y1 r Expession that an be calculated fromcpt v mievc b 19 Can remove a lot of recalculationmultiplications in expression K SUMY3 SUMY4pY5Y3Y4pY4SUMY2pY31Y1Y2pY2 pY1 Sumrmtions over each Wniahle are done only for those pom39ons of the expression that depend on miable Save results of inner summing to avoid Iepeated calculation 7 Cleate mermaiiane Functions 7 F Y2Y 3Y1 SUMY 2pY31Y1Y2pY 2 v mammal 2n v hisaic b Ifthere is evidence both above and below PY3Y5Y2 we squatsiiis evidaioe into above giani below 539 portions and us aversion o1 aayss misio wrns W5 5 12539iQs39pQis39 2539 is39 wemat l as a nonnaliling ado and Wine 17 iz 42 Mia 4 iQ rMQix u dseparaes mm f so Wins 4999 WW i We cdmlatethe am prohahimy in his prom as part oiihsiopdown pioceduieloi almlating no is iiis ssoomi prohahimy is mlmlatai may byms bottomup procsiims 2i v niiaic b Most probable explanation MPE or most likely hypothesis The immntiation of 1111 ll remaining variablu U with she highm Folnlility given the evidence MPEU i e argmixu Pue Maximum a postetioii MAP The immntiation of some variables V with ll highest prolnbility given the evidence MAPV i e arguing Pve Nobe that die assignment m A in MAPAie m39ght be coupleme different fromthe assignment Ain MAPAB i e sum aver Wines ni39 E vs individml Wines ni39 E Odmr queriu probability of an arbiirarylogical exprusion over query variables decision policiu infnmniion value seeking evidence inforrmtion gailnring planning etc 22 v hisaic b Ifthere is evidence both above and below PY3Y5Y2 we squatsiiis evidaioe into above giani below 539 portions and us aversion o1 aayss misio wrns W5 5 12539iQs39pQis39 2539 is39 wemat l as a nonnaliling ado and Wine 17 iz 42 Mia 4 iQ rMQix u dseparaes mm f so Wins 4999 WW i We cdmlatethe am prohahimy in his prom as part oiihsiopdown pioceduieloi almlating no is iiis ssoomi prohahimy is mlmlatai may byms bottomup procsiims 2i v niiaic b Most probable explanation MPE or most likely hypothesis The immntiation of 1111 ll remaining variablu U with she highm Folnlility given the evidence MPEU i e argmixu Pue Maximum a postetioii MAP The immntiation of some variables V with ll highest prolnbility given the evidence MAPV i e arguing Pve Nobe that die assignment m A in MAPAie m39ght be coupleme different fromthe assignment Ain MAPAB i e sum aver Wines ni39 E vs individml Wines ni39 E Odmr queriu probability of an arbiirarylogical exprusion over query variables decision policiu infnmniion value seeking evidence inforrmtion gailnring planning etc 22 M Conditional probability Inatix e The evidence Be1x Px i e Postenor distn39bution of x M Mix 2 WW v maussmmm 23 do coo e ee39 6 Represents the causal evidence e39 Represents the evidential evidence Need to compute Begtlt v mieic b 24 Belx Px l e Pe in Pfxle Bayes rule Pe l e ocPe lx ePx l e Normalization ocPe l xPxl e x desep ee39 a Mx 7600 v msucsmmm 25 Mx represents the degree to which x might explain the evidential support Pe39IX rrX represents the direct causal support for x PXle Both Mx and not can be calculated in terms of the A and n values ofthe neighbors of x v nssevc t 25 i Oumjw yg Mx Pe x 2PM xyPyx Y 2Pe yPyx ydisepm39 y 2 mm x Y My39M y x v 5555555555 m 27 gPxuePme M 2PxuPue udisepxe u 2PM u7ru 39Mm v aaaaaaaaaa m 28 i Oumjw yg Mx Pe x 2PM xyPyx Y 2Pe yPyx ydisepm39 y 2 mm x Y My39M y x v 5555555555 m 27 gPxuePme M 2PxuPue udisepxe u 2PM u7ru 39Mm v aaaaaaaaaa m 28 Jru gt MW y Jrx Belx MK 4 My X 4 My Each node must combine the impact of messagesfrom several children Each node must distribute a separate 1 message to each child v ussucsmmm an v Mummy 31 The evidence E can be decomposed into two subsets o E the subset of E that can be accessed from X through its parents 0 F717 the subset of E that can be accessed from X 1 through its children M msucsmmm 32 The current strength of the causal support 7r contributed by each incoming link UI gt X xU PltU ext The current strength of the diagnostic support A contributed by each outgoing link x gt Y I AyJOc 136 l x The fixed conditional probability matrix Px l u1K u v Lessev csasa mm 33 Step 1 Belief updating Inspect msgs from parents amp children and compute Belc aAcJrc where MI 511me nltxgt 2 m l ulK woman mm Step 2 Bottomup propagation Compute A msgs to send up A xU is the msg X sends to parent U 1x l5 2 MO 2 PXlU1Un H xUk gtlt UFK 1 k l Bis an arbitrary constant factor out contributions to belx from Ui v Lessev csasa mm 34 Step 3 TopDown Propagation Computer msgs to send down MM is sent from x to child Y In Xi um MM 2 PXiU1U n MU knot u un i a Bel x factor out contributions to belx from YJ 1 X Boundary Conditions 1 Rootaxixi istheprior prob dist 2 childless nodeMX111 3 Evidence node 1m o1m v msucsmmm 35 Puma mm mm MUM A qumiluh m Magma fr A A min V V Equalimiioi mg Equation rm pWe i Wilt Emmi in 71M A vii v Fquanrm fnr purst i r pxly xi i 39m V M L xm Vim 35 Step 3 TopDown Propagation Computer msgs to send down MM is sent from x to child Y In Xi um MM 2 PXiU1U n MU knot u un i a Bel x factor out contributions to belx from YJ 1 X Boundary Conditions 1 Rootaxixi istheprior prob dist 2 childless nodeMX111 3 Evidence node 1m o1m v msucsmmm 35 Puma mm mm MUM A qumiluh m Magma fr A A min V V Equalimiioi mg Equation rm pWe i Wilt Emmi in 71M A vii v Fquanrm fnr purst i r pxly xi i 39m V M L xm Vim 35

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.