Probabilistic Graphical Models for Learning, Explained

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

Probabilistic Graphical Models for Learning

Introduction to Artificial Intelligence · Chapter 5: Neural Networks and Learning ArchitecturesSection 5.1 · lesson 32 of 6916 min · free with a free account

← Sequential Decision Making with Markov ProcessesNext lesson: How Neural Networks Drive Machine Learning →

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

Bayesian and Markov networks, conditional independence, and learning from data.

  • Build a Bayesian network with conditional probability tables and compute joint probabilities
  • Explain conditional independence, d-separation patterns, and explaining away
  • Compare Bayesian networks with Markov networks and their potentials
  • Learn table entries by counting with smoothing and describe how structure is learned

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 (2,194 words). Read along, or search it.

Opening Problem

Diagnosing a Patient With a Cough

Ravi walks into a clinic with a cough. Is it a cold? An allergy? Something more serious? Each clue shifts the odds: a fever, a smoking history, an X-ray result. And the clues are tangled up with one another. How can a computer hold all of that at once, and update its beliefs as each new clue arrives? Probabilistic graphical models answer with a picture: a circle for each quantity, and a line for each direct effect. That picture is more than an illustration. It's a compact recipe for the probabilities, and a guide for learning them from data.

Motivation

Why Full Joint Tables Explode

Why draw it at all? Suppose we track n yes-or-no quantities, like symptoms and diseases. Writing down their full joint behavior takes one probability for every combination: 2 to the n, minus 1 numbers. Five quantities need 31 numbers. Ten need over a thousand. Thirty need more than a billion. A network where each node has at most three parents needs at most eight numbers per node: at most 240 for thirty quantities. For a tiny problem, the network is no better. But the gap opens up fast. The saving comes from the real world: most quantities don't depend directly on most others. Once we know whether a patient has lung disease, the cough no longer depends on whether they smoke.

Definition

Bayesian Networks as Directed Graphs

A Bayesian network is a directed graph with no loops. Each node is a variable. Here's a small one for diagnosis. Smoking raises the chance of lung disease. And lung disease causes two things: a cough, and an abnormal X-ray. An arrow from one node to another means a direct influence. The node at the tail is called a parent of the node at the head. So lung disease has one parent: Smoker. Cough has one parent too: lung disease. Smoking doesn't affect the cough directly. Only through the disease.

Conditional Probability Tables

Seven Numbers Describe the Network

Each node also keeps a table: its conditional probability table. It gives the node's probability for every combination of its parents' values. Smoker has no parents, so its table is a single number: twenty percent of patients smoke. Lung disease has one row for each Smoker value: ten percent for smokers, and two and a half percent for everyone else. Cough: eighty percent with the disease, fifteen percent without. Abnormal X-ray: ninety percent with it, five percent without. Count them up. Seven numbers describe this whole network.

Key Rule

Joint Probability as a Product of Tables

Here's the key rule. The probability of any complete situation is the product of each node's table entry, given its parents. Take a smoker with lung disease, who coughs and has an abnormal X-ray. Multiply: 0.2, times 0.1, times 0.8, times 0.9. That's 0.0144, about one and a half percent. Now a non-smoker with no disease, no cough and a normal X-ray: 0.8, times 0.975, times 0.85, times 0.95. About 0.63. Seven stored numbers give the probability of all sixteen situations. A full table of four yes-or-no variables would need fifteen.

Conditional Independence

Parents Screen Off Everything Else

Why is it enough for each node to look only at its parents? Because of conditional independence. Two variables are conditionally independent given a third, if once the third is known, learning one tells you nothing more about the other. In our network, cough and an abnormal X-ray are linked, because both are signs of lung disease. A cough lifts the chance of an abnormal X-ray from about eight percent to about twenty. But once we know whether the patient has the disease, a cough says nothing further about the X-ray. Everything a node depends on is screened off by its parents. That's why the rule works.

Information Flow

Chains, Common Causes, and Common Effects

Three small patterns describe how information flows through a network. A chain: smoker, to disease, to cough. The ends are linked. But once the middle is known, it blocks the path. A common cause: disease, pointing to both the cough and the X-ray. Again, knowing the middle blocks the path. A common effect: a cold and an allergy, both pointing to sneezing. This one is reversed. The two causes are independent, until we learn about the sneeze. Then they become linked. The general rule for reading paths like these is called d-separation.

Explaining Away

An Allergy Lowers the Chance of a Cold

That third pattern is the surprising one, and it has a name: explaining away. Say colds and allergies are each fairly unlikely, and unrelated. Before any symptoms, the chance of a cold is ten percent. Now the patient is sneezing. Both causes become more likely, and the chance of a cold jumps to about forty-four percent. Then we learn the patient has an allergy. The allergy explains the sneezing, and the chance of a cold falls back to about thirteen percent. Learning about one cause shifted our belief in the other, through their shared effect. For a network this tiny, these numbers come from adding up joint probabilities. Larger networks need the systematic methods of a later topic.

Quick Check

A Burglar, an Alarm, and a Phone Call

Quick check. A burglar can set off a house alarm. And when the alarm rings, a neighbor phones you. You already know the alarm went off. Then the neighbor calls. Does her call change how likely a burglary is? More likely, less likely, or just as likely? Pause, and decide. It stays just as likely. This is a chain: burglary, then the alarm, then the call. The call depends on burglary only through the alarm, and the alarm is already known. The middle blocks the path. The tempting answer is more likely. That's right only if you hadn't heard about the alarm yet. Then her call would be real news.

Markov Networks

Undirected Graphs With Clique Potentials

Not every relationship has a direction. Neighboring pixels in a photo tend to share a color, but neither one causes the other. A Markov network, also called a Markov random field, uses an undirected graph: plain lines instead of arrows. With no arrows, there are no conditional tables. Instead, each clique, a group of nodes all connected to each other, gets a potential. A potential is a non-negative score for how compatible each combination of values is. A bigger score means a more favored combination. Multiply the potentials to score a whole situation. Then divide by the sum of those scores over every situation, the normalizing constant Z, to get a probability.

Worked Example

Three Pixels and a Normalizing Constant

Here's a tiny one: three pixels in a row, each black or white, with a line between the first two, and a line between the last two. Each line scores three when its two pixels match, and one when they differ. All three the same, like black, black, black, scores three times three: nine. One break, like black, black, white, scores three times one: three. Two breaks, like black, white, black, scores just one. Add up all eight situations, and Z is thirty-two. So each smooth pattern gets nine thirty-seconds, about twenty-eight percent. Each two-break pattern gets about three percent. And as before, once the middle pixel is known, the two ends are independent. The middle separates them.

Comparison

Bayesian Versus Markov Networks

So how do the two kinds of network compare? A Bayesian network uses arrows, with no loops. A Markov network uses plain lines, and loops are allowed. Bayesian tables hold real probabilities: each row sums to one. Markov potentials are just scores, so they need Z, which can be expensive to compute. Bayesian networks fit clear cause and effect: diagnosis, spam filtering, fault finding. Markov networks fit mutual influence: images, grids and social links.

Maximum Likelihood

Seven Heads in Ten Flips

Now, learning. Suppose we know the arrows, but we need the numbers in the tables. We learn them from records of past cases. The guiding idea is maximum likelihood: choose the numbers that make the data we actually saw as probable as possible. Flip a coin ten times, and see seven heads. If heads has probability p, that exact sequence has probability p to the seventh, times one minus p, cubed. Try p of one half: about 0.00098. Point six: 0.0018. Point seven: 0.0022. And point eight drops back, to 0.0017. The peak is at 0.7: exactly the observed fraction, seven out of ten.

Parameter Learning

Table Entries as Count Ratios

The same holds for every table entry, when every variable is observed. The best estimate is a count ratio. Divide the records with that value and that parent setting, by all the records with that parent setting. Here are a thousand patient records. Two hundred are smokers, so P of smoker is 0.20. Of those two hundred smokers, twenty have lung disease: 0.10. Of the eight hundred non-smokers, also twenty: 0.025. Of the forty with the disease, thirty-two cough: 0.80. Of the nine hundred sixty without it, a hundred forty-four cough: 0.15. The X-ray rows are counted the same way. That's where the network's tables came from.

Common Pitfall

Zero Counts and Smoothing

Counting has one trap. If a combination never appears in the data, its estimate is exactly zero. Say the word lottery appears in none of fifty genuine emails. Then P of lottery, given genuine, is zero. And one zero wipes out a whole product. Any email containing lottery becomes impossible to be genuine, however strong the other evidence. The usual remedy is smoothing: add a small pseudo-count. For a yes-or-no variable, add one to the count, and two to the total. That gives one over fifty-two, about 0.019, instead of zero. Data with missing values needs more advanced estimation methods.

Structure Learning

Constraint-Based and Score-Based Methods

Often even the arrows are unknown. Learning the structure means deciding which edges the data support. Constraint-based methods test which variables look independent in the data, and keep only the edges consistent with those tests. If cough and X-ray look independent once disease is known, no edge is needed between them. Score-based methods give each candidate network a score that rewards fit to the data, and penalizes complexity. Then they search, adding, deleting or reversing one edge at a time while the score improves. It's the local search from earlier in the course. The penalty matters. More edges always fit the training data better, so without it, the search would join everything to everything, and overfit.

Search Space

Too Many Structures to Check

And why search, instead of trying every structure? Count them. With two variables, there are three possible networks. With three variables, twenty-five. With five, over twenty-nine thousand. With ten variables, about four point two times ten to the eighteenth. No computer can check them all. There's also a limit on what data can reveal. A chain, a common cause, and the reversed chain all say the same thing: the ends are independent, given the middle. So data alone can't always tell which way an arrow points. And a learned arrow shows a pattern, not a cause. Showing cause takes more evidence, such as experiments, or expert knowledge.

Quick Check

Smoothing a Word Never Seen

Quick check. A filter is trained on forty genuine emails, and none of them contain the word prize. Using smoothing for a yes-or-no word, what should P of prize, given genuine, be? Zero out of forty, one out of forty-one, or one out of forty-two? Pause, and decide. One out of forty-two, about 0.024. Add one to the count of zero, and two to the total of forty. The two keeps both answers, prize and no prize, summing to one: forty-one forty-seconds, plus one forty-second. Zero is the trap smoothing exists to avoid. And forty-one adds a pseudo-count to only one of the two outcomes.

Application

Clues Raise Disease Probability to 91 Percent

Let's put the learned medical network to work. Overall, four percent of patients have lung disease. The patient coughs. The chance of disease rises to about eighteen percent. The X-ray is abnormal too. Now it's eighty percent. Cough and X-ray are independent given the disease, so their effects simply multiply. And the patient smokes: about ninety-one percent. Each clue makes the diagnosis more certain, and no single one is decisive. These are hand calculations for a tiny network; real diagnostic networks have hundreds of variables.

Application

A Spam Filter as a Network

A spam filter is a network too: one parent, the email's spam status, and one child for each watched word. Counting a thousand training emails, four hundred of them spam, gives the tables. Free appears in sixty percent of spam, and five percent of genuine mail. Winner: thirty percent of spam, half a percent of genuine. Meeting: two percent of spam, thirty percent of genuine. An email with free and winner, but no meeting, scores about seven hundred times higher as spam: about ninety-nine point eight five percent spam. An email with only meeting is about one percent spam: almost certainly genuine. The structure assumes words are independent, given the spam status. That's only roughly true. Free and winner often travel together, so the filter can be overconfident.

Key Takeaways

Graphical Models Summed Up

To recap. A Bayesian network draws direct influences as arrows, with a probability table at each node. The joint probability is the product of those tables, thanks to conditional independence. Chains and common causes block a path when the middle is known; common effects open it. Markov networks use plain lines and potential scores, divided by Z. With all variables observed, learning a table is counting, plus smoothing. Structure is learned by testing or by scoring, and arrows aren't proof of cause.

Reflection

Umbrellas Do Not Cause Rain

Here's something to think about. A network learned from data contains an arrow from carries an umbrella, to rain. Why shouldn't you conclude that carrying umbrellas causes rain? And which way would you draw the arrow, if you were the expert?

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 Probabilistic Graphical Models for Learning

What is a Bayesian network?
A Bayesian network is a directed graph with no loops in which each node is a variable, each arrow shows a direct influence, and each node stores a conditional probability table given its parents. The probability of any complete situation is the product of each node's table entry. A four-variable diagnosis network needs only seven numbers, while a full joint table would need fifteen.
What is explaining away in a Bayesian network?
Explaining away happens when two independent causes of a shared effect become linked once the effect is observed. If colds and allergies both cause sneezing, seeing a sneeze raises the chance of a cold, but then learning the patient has an allergy lowers it again, because the allergy already explains the sneeze. It is the common-effect pattern in d-separation.
What is the difference between a Bayesian network and a Markov network?
A Bayesian network uses directed arrows with no loops and stores real conditional probabilities at each node. A Markov network, or Markov random field, uses undirected lines, allows loops, and gives each clique a non-negative potential score, which must be divided by a normalizing constant Z to get probabilities. Bayesian networks suit cause and effect; Markov networks suit mutual influence, such as neighboring pixels.
How do you learn the probability tables of a Bayesian network from data?
With every variable observed, the maximum likelihood estimate of each table entry is a count ratio: records with that value and parent setting, divided by records with that parent setting. If 20 of 200 smokers have lung disease, the estimate is 0.10. Smoothing avoids zero estimates; for a yes-or-no variable, add one to the count and two to the total.

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 →