Bayesian NetworksCS182/CogSci110/Ling109Spring 2007Leon [email protected]. belief nets, bayes netsBayes NetsBayes NetsRepresentation of probabilistic informationRepresentation of probabilistic information–reasoning with uncertaintyreasoning with uncertaintyExample tasksExample tasks–Diagnose a disease from symptomsDiagnose a disease from symptoms–Predict real-world information from noisy Predict real-world information from noisy sensorssensors–Process speechProcess speech–Parse natural languageParse natural languageThis lectureThis lectureBasic probabilityBasic probability–distributionsdistributions–conditional distributionsconditional distributions–Bayes' ruleBayes' ruleBayes netsBayes nets–representationrepresentation–independenceindependence–algorithmsalgorithms–specific types of netsspecific types of netsMarkov chains, HMMsMarkov chains, HMMsProbabilityProbabilityRandom VariablesRandom Variables–Boolean/DiscreteBoolean/DiscreteTrue/falseTrue/falseCloudy/rainy/sunnyCloudy/rainy/sunnye.g. die roll, coin flipe.g. die roll, coin flip–ContinuousContinuous[0,1] (i.e. 0.0 <= x <= 1.0)[0,1] (i.e. 0.0 <= x <= 1.0)e.g. thrown dart position, amount of rainfalle.g. thrown dart position, amount of rainfallUnconditional ProbabilityUnconditional ProbabilityProbability DistributionProbability Distribution–In absence of any other infoIn absence of any other info–Sums to 1Sums to 1–for discrete variable, it's a tablefor discrete variable, it's a table–E.g. E.g. P(Sunny) = .65 (thus, P(Sunny) = .65 (thus, P(¬Sunny) = .35)P(¬Sunny) = .35)–for discrete variables, it's a tablefor discrete variables, it's a tableWeather sunny cloudy rainy snowyP(Weather) 0.65 0.19 0.14 0.02Die 1 2 3 4 5 6P(Die) 1/6 1/6 1/6 1/6 1/6 1/6Continuous ProbabilityContinuous ProbabilityProbability Density FunctionProbability Density Function–Continuous variablesContinuous variables–E.g. Uniform, Gaussian, Poisson…E.g. Uniform, Gaussian, Poisson…Joint ProbabilityJoint ProbabilityProbability of several variables being set at the same timeProbability of several variables being set at the same time–e.g. P(Weather,Season)e.g. P(Weather,Season)Still sums to 1Still sums to 12-D table2-D tableP(Weather, Season)P(Weather, Season)Full Joint is a joint of all variables in modelFull Joint is a joint of all variables in modelCan get “marginal” of one variableCan get “marginal” of one variable–sum over the ones we don't care aboutsum over the ones we don't care aboutsunny cloudy rainy snowysummer 0.45 0.04 0.01 00.5winter 0.2 0.15 0.13 0.020.50.65 0.19 0.14 0.02 1Conditional ProbabilityConditional ProbabilityP(Y | X) is probability of Y given that all P(Y | X) is probability of Y given that all we know is the value of Xwe know is the value of X–E.g. P(cavity | toothache) = .8E.g. P(cavity | toothache) = .8thus P(thus P(¬cavity | toothache) = .2¬cavity | toothache) = .2Product RuleProduct Rule–P(X, Y) = P(Y | X) P(X)P(X, Y) = P(Y | X) P(X)–P(Y | X) = P(X, Y) / P(X)P(Y | X) = P(X, Y) / P(X)((normalizer normalizer to add up to 1to add up to 1))Y XConditional Probability Conditional Probability ExampleExampleP(disease=true) = 0.001 ; P(disease=false) = 0.999P(disease=true) = 0.001 ; P(disease=false) = 0.999test 99% accurate:test 99% accurate:Compute joint probabilitiesCompute joint probabilities–P(test=positive, disease=true) = 0.001 * 0.99 = 0.00099P(test=positive, disease=true) = 0.001 * 0.99 = 0.00099–P(test=positive, disease=false) = 0.999 * 0.01 = 0.00999P(test=positive, disease=false) = 0.999 * 0.01 = 0.00999–P(test=positive) = 0.00099 + 0.00999 = 0.01098P(test=positive) = 0.00099 + 0.00999 = 0.01098P(test | disease) true falsepositive 0.99 0.01negative 0.01 0.99Bayes' RuleBayes' RuleResult of product ruleResult of product rule–P(X, Y) = P(Y | X) P(X)P(X, Y) = P(Y | X) P(X) = P(X | Y) P(Y) = P(X | Y) P(Y)P(X | Y) = P(Y | X) P(X) / P(Y)P(X | Y) = P(Y | X) P(X) / P(Y)P(disease | test) = P(test | disease) * P(disease | test) = P(test | disease) * P(disease) / P(test) P(disease) / P(test)Conditional Probability Conditional Probability Example (Revisited)Example (Revisited)P(disease=true) = 0.001 ; P(disease=false) = 0.999P(disease=true) = 0.001 ; P(disease=false) = 0.999test 99% accurate:test 99% accurate:P(disease=true | test=positive)P(disease=true | test=positive) = P(disease=true, test=positive) / P(test=positive) = P(disease=true, test=positive) / P(test=positive) = 0.00099 / 0.01098 = 0.0901 = 9%= 0.00099 / 0.01098 = 0.0901 = 9%P(test | disease) true falsepositive 0.99 0.01negative 0.01 0.99Important equationsImportant equationsP(X,Y) = P(X | Y) P(Y)P(X,Y) = P(X | Y) P(Y) = P(Y | X) P(X) = P(Y | X) P(X)P(Y | X) = P(X | Y) P(Y) / P(X)P(Y | X) = P(X | Y) P(Y) / P(X)Chain Rule of ProbabilityChain Rule of ProbabilityP(xP(x11,x,x22,x,x33,…,x,…,xkk) = ) = P(xP(x11)P(x)P(x22|x|x11)P(x)P(x33|x|x11,x,x22)…P(x)…P(xkk|x|x11,x,x22,…,x,…,xk-1k-1)) P(x1,x2,x3)P(x1,x2)Bayes NetsBayes NetsDiseaseTest resultP(disease) probabilityTRUE 0.001FALSE 0.999P(test | disease) true falsepositive 0.99 0.01negative 0.01 0.99Causal reasoningCausal reasoningDiseaseTest resultDiseaseTest result≠Causal reasoningCausal reasoningDiseaseTest resultnot just probabilistic not just probabilistic reasoningreasoningcausal reasoningcausal reasoning–arrow direction has arrow direction has important meaningimportant meaningmanipulating manipulating causes changes causes changes outcomesoutcomesmanipulating manipulating outcomes does not outcomes does not change causeschange causesBayes NetsBayes NetsDiseaseTest resultShaded means Shaded means observedobserved–we know the value we know the value of the variableof the variable–then we calculate then we calculate P(net | observed)P(net | observed)Example: Markov ChainExample: Markov ChainJoint probability = P(A,B,C,D)Joint probability = P(A,B,C,D)= P(A)P(B|A)P(C|A,B)P(D|A,B,C)= P(A)P(B|A)P(C|A,B)P(D|A,B,C)(by C.R.)(by C.R.)A B C DExample: Markov ChainExample: Markov ChainJoint probability = P(A,B,C,D)Joint probability = P(A,B,C,D)= P(A)P(B|A)P(C|A,B)P(D|A,B,C)= P(A)P(B|A)P(C|A,B)P(D|A,B,C)(by C.R.)(by C.R.)A B C DP(D|A,B,C) = P(D|C)P(D|A,B,C) = P(D|C)Example: Markov ChainExample: Markov ChainJoint probability