[AI] 3. Bayes Network

Why do AI systems need probability when dealing with real world?

Because the real world contains uncertainty caused by:

• Partial observability: We cannot observe everything

• Noisy sensors: Observations may be inaccurate

• Immense complexity: Completely modelling or predicting the world may be too difficult

• Lack of knowledge of world dynamics: Unexpected events may occur

Probabilistic assertions summarise the effects of incomplete knowledge and limited effort.

How does an agent make decisions under uncertainty?

We combine:

• Probability: How likely an outcome is

• Utility: How desirable that outcome is

Then choose the action that maximise expected utility: a*

So the agent considers both how likely each outcome is and how good or bad it would be

What are the basic laws of discrete probability ?

What is a sample space (Omega) and what conditions must a discrete probability model satisfy?

The simple space, Omega, is the set of all possible outcomes.

Example: In the picture

What is an event and how do we calculate the probability of an event?

• Event is any subset of the sample space, omega (subset of possible outcomes)

• Probability of event is the sum of the probability of all outcomes belonging to the event

→ A = {1,5,3} , rolling a die in odd

→ P(A) = 1/6 + 1/6 + 1/6 =0.5

*6 because a die has 6 possibilities

What is a random variable and what is its range?

• Random variable: variable represent the uncertain aspect of the world. Represented by capital letter, T,D,X,etc

• Formally, it is a deterministic function of an outcome, w

• Range or domain: Set of possible values of random variable

Examples:

• Odd = {True, False}

• T = {Hot, Cold}

• D = [0, ♾) for travel time

• Location of ghost, L = {(0,0),(0,1),…}

What is the difference between an outcome(w), a random variable (X) and a value(x)?

• w = an actual underlying outcome

• X = A function or property, we are interested in

• x = A possible value of X

Example : If the die outcome is w=5 and X=Odd, then Odd(5)=true

→ So 5 is the outcome, Odd is the random variable , and true is its value

What is the probability distribution of random variable, X and what is the difference between P(X=x) and P(x)?

• A probability distribution of X: gives the probability for every possible value of X

• P(X=x) : probability of one particular value

• P(X) : Entire probability distribution usually represented as vector or table

What is a joint probability distribution?

• Joint distribution : probability distribution involving two or more random variables simultaneously

• Combine their values

• All entries sum to 1

Example: P(T,W)

• Gives probabilities for every combination of Temperature and Weather, such as:

• P(T=hot, W=sunny) = 0.45

Can we obtain joint distribution from marginal distributions?

No, because marginals don’t contain enough info abt how they interact.

Except if the marginals are independent, then we can obtain their joint

Can we obtain marginals distribution from joint distribution?

Yes, because we know how they interact. Thus, to obtain the marginals must eliminate other variables

What is marginal distribution and Marginalization?

• marginal distribution: distribution of a subset of variables from a joint, e.g. P(T) and P(W) are marginals of P(T,W)

• Marginalization: summing out unwanted variables, equations 👆🏻

How many entries are in a full joint distribution (size of joint) of n variables and range size,d?

• n: # of variables

• d: set of highest possible outcomes between random variables

• d^n

• Joijnt distribution grow exponentially with the # of variables

Example: n = 2 (T,W), d = 4 (sun, rain, fog, meteor)

→ 4² = 8

When are 2 random variables X and Y independent?

When:

P(x,y) = P(x)P(y)

Equivalently:

P(x|y) = P(x)

Knowing one gives no information about the other

How do you calculate probability of an event in joint distribution ?

Solve the example:

• probability that its hot and sunny

• Probability that its hot

• Probability that its hot OR not foggy

Add the probabilities of all entries satisfying the event

Examples:

• probability that its hot and sunny: 0.45

• Probability that its hot: 0.45+0.02+0.03+0.0=0.5

• Probability that its hot OR not foggy: 0.45+0.15+0.02+0.08+0.03+0.0+0.0=0.73

*only (cold,foggy) is excluded because oppose to either hot or foggy

Which one has higher probability?

1. Sunny vs rainy

2. Foggy vs hot

3. Cold and foggy vs rainy

4. If its rainy then cold (cold | rainy) vs sunny

1. Sunny vs rainy: 0.6 vs 0.1 : SUNNY

2. Foggy vs hot : 0.3 vs 0.5 : HOT

3. Cold and foggy vs rainy : 0.27 vs 0.1 : COLD&FOGGY

4. If its rainy then cold (cold | rainy) vs sunny : (cold&rain / rain = 0.08/0.1=0.8) vs 0.6 : RAINY THEN COLD

*#4 is conditional probability

What is conditional probability?

• probability of A given that B has occurred:

P(A|B) = P(A,B) / P(B)

Solve this conditional probability : P(W=sun | T=cold)

P(sun,cold) =0.15

P(cold)= 0.5

=> 0.15/0.5=0.3

What is normalization?

• normalization: rescaling values , so that distribution’s sum become 1

• Multiply every entry by alpha

Normalize the example in red box

• sum of all entries= 0.15+0.08+0.27+0=0.5

• a = 1/0.5=2

• 0.15×2=0.3

• 0.08×2=0.16

• 0.27×2=0.54

• 0.0×2=0

What is conditional distribution?

• conditional distribution: a distribution over one set of variables given values of another set of

• E.g. P(W|T)

• based on the example, table on the left is the joint distribution

• From joint, the given variable (T) must disjoint its values ( hot and cold)

• Then normalize them to sum 1

• The right tables are 2 disjoint distribution

What is the product rule?

Product rule: reconstruct joint distribution from conditional and marginals probabilities

From the conditional distribution and marginal distribution given, construct a joint distribution

Based on the marginals and conditional distribution, find the higher probability:-

1. Sunny and hot vs sunny and cold?

2. Sunny vs foggy?

Based on the marginals and conditional distribution, find the higher probability:-

1. hot|sunny vs cold|sunny?

2. hot|not foggy vs cold|not foggy?

What is the chain rule?

Chain rule: express joint distribution as product of conditional distributions

What is probability inference?

• probability inference: computing a desired probability from a probability model

• —> usually P(query|evidence)

• e.g. P(class on time|no holidays) = 0.9

• These represent agent’s beliefs given the evidence

• e.g. P(class on time|no holidays, 10 a.m, raining) = 0.85

• More new evidence, changing agent’s beliefs

What is Query, Evidence, and Hidden variables?

• Query variable, Q: variable(s) we want to know

• Evidence variable , E: variable(s) that we know/observed

• Hidden variable, H: unobserved variable that is neither query nor evidence

What are 3 steps of inference by enumeration?

1. Select entries consistent with evidence

2. Sum out the hidden variables

3. Normalize

Based on the table of P(Season, | sun), what are Q, E, H?

• Q = Season

• E = Weather sun

• Hidden = Temp

• To calculate, sum out Temp and normalize

Calculate P(Season|sun)

1. Enumerate options with sun: P(summer, hot, sun) , P(summer, cold, sun) , P(winter, hot, sun) , P(winter, cold sun)

2. Sum out hidden variables:

• P(summer, sun) = P(summer, hot, sun) + P(summer, cold, sun) =0.35+0.10=0.45

• P(winter, sun) = P(winter, hot, sun) + P(winter, cold sun) =0.1+0.15=0.25

3. Normalize:

   • P(Season|sun) = {summer: 0.45/(0.45+0.25) , winter: 0.25/(0.45+0.25)}

   • P(Season|sun) = {summer:0.64, winter:0.36}

What is the main problem of inference by enumeration using a full joint distribution?

• it is the exponential number of variables

• d: range(size of domain) for each variable

• n: # of variables

• d^n is the entries of joint distribution

• Time complexity: O(d^n) :exponential in # of var

• Space complexity: O(d^n) : to store joint dist

What is Bayes’ Rule?

• Bayes’ Rule let us obtain one conditional probability from its reverse

What are likelihood, evidence , posterior, prior from the equation of Bayes Rule ?

• likelihood: P(b|a)

• evidence: P(b)

• prior/ unconditional probability : P(a)

• posterior / conditional probability w evidence b: P(a|b)

• Posterior = (Likelihood x Prior) / Evidence

List out the likelihood, evidence ,prior ,and posterior of P(Test|Disease)

• Often one cond prob is trickier to get than another

• P(Test|Disease) is easier to get than P(Disease|Test) from clinical records

• Prior: P(Test = positive )

• Likelihood: P(Disease|Test)

• Evidence: P(Disease = true)

• Posterior: P(Test|Disease)

e.g. P(Disease=true|Test=positive)

What is the intuition behind Bayes Rule?

• Start with prior belief ,P(a) and update with observed evidence, b to obtain posterior, P(a|b)

Example of medical diagnostic:

• Disease = Covid or not Covid , Test = Positive or Negative

• Solve P(Covid|Positive)

• Why do we still need to get the test even though it is negative ?

• Because the posterior also depends on prior probability of the disease and test/evidence probability, not only P(positive |covid)

• P(covid|positive) = 0.008 is VERY SMALL

• due to high false positive P(negative |covid)=0.2 and very small P(covid)=0.0001

  
  

Example of Hodu and Maru:

• assume there is 2 dogs {Hodu and Maru} and they could be {Maltese or Poodle}

• One of them is poodle

• What is the probability of having 2 Poodles?

• event a, P(a): at least one of them is poodle = { (P,P),(P,M),(M,P)}

• event b, P(b): both are poodle = {(P,P)}

• Total of possible outcomes: 4 includes (M,M)

• P(a) = ¾ , P(b) = ¼ , P(a|b) = 1/1

• Probability get 2 poodles given at least one is poodle → P(b|a) = [ P(a|b)P(b) ] / P(a) = (1 × ¼ )/( ¾ )= 1/3

What is conditional independence?

• given P(x|y,z) = P(x|z) : x is conditionally independent of y given z

What is the difference of independence and conditional independence?

• Independence: P(X|Y) = P(X) : Y gives no info of X

• Conditional Independence: P(X|Y,Z) = P(X|Z) : once Z is known, Y gives no additional info of X

• Independence is rare while conditional independence is more related

Why is Independence powerful but conditional independence is nore useful in practice?

• Independence can greatly reduce representation size but complete independence is RARE!

• Conditional independence is more common in real world problems

What is independence of random variables?

• Independence: no relation between 2 or more random variables

  
  

What is Ghostbusters game about?

• Given a grid, ghost is somewhere in the grid

• Find the ghost by choosing the square and get a clue how far it is from the ghost

• Noisy sensor tell how close a is to the ghost:

  on the ghost: Red

  1-2 away: Orange

  3-4 away: Yellow

  5+ away: Green

• Thus, you will get updated of the probability of ghost on each square

What are the random variables and range of ghostbusters model?

• G has uniform prior, P(G) = 0.11

• while sensor readings follow posterior,P((C x,y) | G) which the color is depend on distance from ghost

What is the sensor model of Ghostbusters model?

How to get location of ghost given colour of measured at square x,y , P(G|C)?

Are sensor readings such as C(1,1) = yellow and C(1,2) = orange independent?

• Not necessarily

• Both depend on the same hidden variable, which is ghost location ,G

• They are conditionally independent given G

• P(C1,1 | G, C1,2) = P(C1,1| G)

What is the size of joint distribution of ghostbuster model?

Why does knowing G make one sensoring irrelevant to predicting another?

• Once ghost location G is known, each sensor’s probability depends only on its distance from G

• Thus, another sensor reading provides no additional information

• For example, P(C1,1 | G, C1,2) → Once G is known, Information of C1,2 is irrelevant to C1,1

• Causing C1,1 to be the conditional independence to C1,2 given G

How does join distribution decomposed by chain rule/ without simplification of conditional independence?

How does conditional independence simplify the Ghostbusters joint distribution?

What is Naïve Bayes model?

A model with:

• One query( class or category variable)

• Other variables acting as evidence

• Evidence variables conditionally independent given the query variable

How is Bayesian Network represented?

• Nodes = Random variables

• Domains = Possible values

• Directed arcs = Direct influences or interactions X → Y

• e.g. Cavity → Toothache , Cavity → Catch

• No arc can encode independence

• e.g . No influence btw Weather and other variables, No direct influence btw Toothache and Catch

• P(X|Y) quantifies X’s influence on Y

What type of graph is Bayesian Network?

Directed Acyclic Graph (DAG)

What is CPT?

• Conditional Probability Table (CPT)

• Gives conditional probability distribution of each node given its parent variables

• Each row comes to one

What are the two components of a Bayesian Network?