Reasoning Under Uncertainty: Probabilistic Foundations

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 7.7 Free with a free account

Reasoning Under Uncertainty: Probabilistic Foundations

Introduction to Artificial Intelligence · Chapter 7: Machine Learning, NLP, and PerceptionSection 7.7 · lesson 55 of 6913 min · free with a free account

← Classifying Data with Support Vector MachinesNext lesson: Modeling Change Over Time: Dynamic Probabilistic Systems →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

Computing query probabilities from evidence with exact and sampling methods.

  • Compute a conditional probability from a full joint distribution by marginalizing and normalizing
  • Compare enumeration and variable elimination as exact inference methods for Bayesian networks
  • Explain how rejection sampling and likelihood weighting estimate probabilities, and why rare evidence hurts rejection
  • Distinguish causal, diagnostic and intercausal reasoning, including explaining away

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,667 words). Read along, or search it.

Opening Question

Is the Security Alert Real

A security monitor raises an alert. What's the probability that something is really wrong? And how should that answer change when you learn one more fact, like a technician reporting a hardware fault? Answering questions like these, with numbers, is probabilistic inference.

Key Terms

Query, Evidence and Hidden Variables

Earlier lessons gave us the rules of probability, Bayes' rule, and Bayesian networks to write uncertain knowledge down. This lesson is about using them. Inference computes the probability of something we care about, the query, given what we've observed, the evidence. Every other variable in the model is hidden, and must be accounted for.

Running Example

Attack, Fault, Alert and Ticket

One small example runs through the whole lesson. A system can be under attack, with probability 0.1, or suffer a hardware fault, with probability 0.2. The two are independent. Either one can make the monitor raise an alert. With both, the alert sounds 95 percent of the time. With an attack alone, 90 percent. With a fault alone, 70. With neither, 5. And an alert makes a user complaint, a ticket, more likely: 0.8 with an alert, and 0.1 without.

Full Joint Distribution

Eight Rows That Sum to One

A full joint distribution lists the probability of every complete combination of values. Any question about the model can be answered from it. For Attack, Fault and Alert, the network multiplies the prior of Attack, the prior of Fault, and the alert's chance given both. Attack, fault and alert: 0.1, times 0.2, times 0.95, is 0.019. The eight rows run down to the most common case: no attack, no fault, no alert, at 0.684. All eight add up to one.

Two Operations

Summing Out and Conditioning

Two operations do all the work. Marginalization, or summing out: to get one variable's probability, add every entry that agrees with it. The chance of an alert adds up the four alert rows. That's 0.253, about one time in four. Conditioning accounts for evidence: keep only the rows that match it, then divide by their total, so they add up to one again.

Worked Example

Attack Given the Alert Is 0.36

Given that the alert has sounded, keep its four rows, and divide each by 0.253. Attack and fault becomes 0.075. Attack alone, 0.285. Fault alone, 0.498. And neither, 0.142. Add the two attack rows: the probability of an attack, given the alert, is 0.36. The alert raised it from 0.1. Likewise, a fault given the alert is about 0.573. The general recipe: for each value of the query, add up the joint entries that match the evidence, then scale the results by alpha, so they total one.

Quick Check

Fault Given a Silent Alert

Quick check. This time, the alert stays silent. Using the same eight joint rows, what's the probability of a hardware fault now? Pause, and work it out. About 0.074. The no-alert rows total 0.747. The two with a fault add to 0.055, and dividing gives 0.074. Stopping at 0.055 forgets to rescale. And it isn't unchanged: silence is evidence too, and it makes a fault less likely than its prior of 0.2.

Scaling Problem

Two to the n Table Entries

The recipe is correct, but the joint table is far too big for a real problem. With n yes-or-no variables, it has two to the n entries. A Bayesian network avoids that. If each variable has at most three parents, it needs no more than n times eight probabilities. Ten variables: 1,024 entries, against 80. Twenty: over a million, against 160. Thirty: about a billion, against 240. The network stores the model compactly. The next methods answer queries without ever building the full table.

Exact Method One

Enumeration for a Ticket

Exact method one: enumeration. It follows the recipe, but computes each joint entry from the network's tables, instead of storing it. A ticket arrives. What's the probability of an attack? Fault and alert are hidden, so each value of Attack needs a sum over four combinations. Each term multiplies four numbers. For attack, fault and alert, it's 0.1 times 0.2 times 0.95 times 0.8: 0.0152. The attack terms add to 0.0737, and the no-attack terms to 0.2034. Together, 0.2771: the chance of a ticket. Scale, and the probability of an attack given a ticket is about 0.266. That's less than an alert gave, because a ticket is a weaker clue.

Exact Method Two

Variable Elimination Removes Repetition

Enumeration repeats work: the same partial products appear in many terms, and the number of terms grows exponentially with the hidden variables. Variable elimination removes the repetition. Each table becomes a factor, and hidden variables are eliminated one at a time: multiply the factors that mention it, then add over its values. Eliminate Alert first. For each attack and fault pair, weight the alert chance by 0.8, and the no-alert chance by 0.1. Then eliminate Fault, weighting by 0.2 and 0.8. That leaves 0.737 for an attack, and 0.226 without. Finish: multiply by the attack prior, and scale. The answer, 0.266, matches enumeration exactly, but each partial result was computed only once.

Limits of Exact Inference

NP-Hard Except on Polytrees

In this tiny network the saving is small. In a network shaped like a chain, it's dramatic: the work grows in step with the variables, instead of doubling with each one. But even the best exact method has a limit. Inference in general Bayesian networks is NP-hard: no known algorithm is fast on every network. It's efficient on polytrees, where only one path joins any two variables. For heavily connected networks, we turn to approximation.

Approximate Inference

Drawing One Sample in Order

Approximate inference generates random samples from the network, and counts. More samples give better estimates, converging to the exact value. To draw one sample, visit each variable after its parents, and flip a biased coin. Attack: draw 0.43. That's above 0.1, so no attack. Fault: draw 0.12, below 0.2, so there's a fault. Alert, given a fault and no attack, has chance 0.70. Draw 0.55: the alert sounds. Ticket: draw 0.31, below 0.8, so a ticket. That's one sample. Counting how often an event occurs, across many samples, estimates its probability.

Sampling With Evidence

Rejection Versus Likelihood Weighting

Rejection sampling estimates a conditional probability. Generate samples as before, and throw away every one that disagrees with the evidence. Among the survivors, count how often the query is true. For attack given a ticket, only samples with a ticket survive: 27.7 percent, so 10,000 samples leave about 2,770. Likelihood weighting wastes nothing. It fixes the evidence at its observed value, and samples only the other variables. Each sample gets a weight: the chance of the evidence, given its sampled parents. With a ticket observed, a sample with an alert weighs 0.8, and one without, 0.1. The estimate is the weight of the samples where the query is true, divided by the total weight.

Experiment Results

Rare Evidence Starves Rejection

In one experiment, each method estimated attack given a ticket 400 times, at several sample sizes. Both centered on 0.266. For rejection sampling, the middle 80 percent of estimates spanned 0.21 with 100 samples, and 0.022 with 10,000. A hundred times more samples gave about ten times less spread. Here the evidence is common, so likelihood weighting was only slightly tighter. Rare evidence changes everything. Take attack, no alert, and a ticket, which has probability 0.0009. The query is a fault, exactly 0.111. With 1,000 samples, rejection keeps about one, and 38 percent of runs keep none. Likelihood weighting keeps all of them, landing between 0.101 and 0.122. Weighting has its own weakness: with lots of evidence, a few samples can carry nearly all the weight. Markov chain Monte Carlo methods, like Gibbs sampling, change one variable at a time.

Reasoning Directions

Causal, Diagnostic and Intercausal

The same network supports three directions of reasoning. Causal, or predictive, reasoning runs along the arrows, from causes to effects. If there's an attack, an alert has probability 0.91, up from 0.253. Diagnostic reasoning runs against the arrows, from effects back to causes. Given an alert, an attack has probability 0.36, up from 0.1. Intercausal reasoning links two causes of one effect. The alert sounded, and a fault is confirmed. Now an attack has probability only 0.131, down from 0.36.

Explaining Away

Competing Causes After an Alert

Causal reasoning is usually easiest, because the tables are written in that direction. Diagnostic reasoning is what we usually want. It needs Bayes' rule, so priors matter. Attacks are rare, and alerts have other causes: 0.91 becomes 0.36. Intercausal reasoning is the surprising one. Attack and fault start out independent: knowing about a fault leaves an attack at 0.1. But once the alert is observed, they compete. A confirmed fault already explains the alert, so the attack is less needed. That's explaining away. And if engineers find no fault, the attack becomes the leading explanation: 0.667.

Quick Check

Smoke Alarm and Burnt Toast

Quick check. A smoke alarm can be set off by a real fire, or by burnt toast. It goes off. Then you smell toast burning in the kitchen. What happens to the probability of a real fire? Pause, and decide. It falls. The toast already explains the alarm, so a fire is less needed as an explanation. That's intercausal reasoning: explaining away. Staying the same is tempting, because toast and fire are independent. But once the alarm is observed, evidence about one cause changes belief in the other.

Back to the Alert

One More Fact Moves the Answer

Back to the monitor's alert. Before it sounded, an attack had a ten percent chance. The alert alone raises that to 36 percent. One more fact moves it again. A confirmed fault drops it to 13 percent. Finding no fault lifts it to 67 percent. And a ticket on its own gives only 27 percent. Every one of those answers comes from the same recipe: sum out the hidden variables, and condition on the evidence.

Key Takeaways

From Joint Tables to Sampling

To sum up. The full joint distribution answers any query: marginalize by adding entries, condition by keeping and rescaling. But it grows as two to the n. Enumeration is exact but repeats work. Variable elimination computes each partial result once. Exact inference is hard in general, but efficient on polytrees. Sampling estimates answers. Rejection discards samples that miss the evidence, and likelihood weighting weights them all. Rare evidence hurts rejection most. And reasoning runs along the arrows, against them, or between causes, where one cause can explain away another.

Think About It

Sampling Rare Evidence on a Budget

Here's something to think about. Some evidence has a probability of 0.02, and you can afford 5,000 samples. About how many would rejection sampling keep? Is that enough, and which method would you use instead?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Reasoning Under Uncertainty: Probabilistic Foundations

How do you compute a conditional probability from a full joint distribution?
Keep the joint entries that match the evidence, add up the ones that also match each value of the query, and divide by the total of the matching entries so the results sum to one. For example, if the alert rows total 0.253 and the rows with both an attack and an alert total 0.091, the probability of an attack given the alert is about 0.36. That division is the normalization step, often written as alpha.
What is the difference between enumeration and variable elimination?
Both are exact inference methods for Bayesian networks, but variable elimination avoids repeated work. Enumeration sums products of conditional probabilities over every combination of hidden variables, so identical partial products are recomputed and the number of terms grows exponentially. Variable elimination treats each table as a factor and removes hidden variables one at a time, multiplying the factors that mention a variable and summing over its values, so each partial result is computed once.
When should you use likelihood weighting instead of rejection sampling?
Likelihood weighting is usually the better choice when the evidence is unlikely. Rejection sampling discards every sample that disagrees with the evidence, so evidence with probability 0.0009 leaves about one of 1,000 samples. Likelihood weighting fixes the evidence variables, samples only the others, and weights each sample by the probability of the evidence given its sampled parents, so no sample is wasted. Its weakness is that with a lot of evidence, a few samples can carry most of the weight.
What is the difference between causal and diagnostic reasoning in a Bayesian network?
Causal, or predictive, reasoning runs along the arrows, from causes to effects, while diagnostic reasoning runs against them, from effects back to causes. If an attack has a prior of 0.1, learning of an attack raises the chance of an alert from 0.253 to 0.91. Seeing an alert raises the chance of an attack only to 0.36, because diagnosis needs Bayes' rule, and the low prior and the alert's other causes, such as a hardware fault, hold it down.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →