Modeling Change Over Time: Dynamic Probabilistic Systems

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

Modeling Change Over Time: Dynamic Probabilistic Systems

Introduction to Artificial Intelligence · Chapter 7: Machine Learning, NLP, and PerceptionSection 7.8 · lesson 56 of 6915 min · free with a free account

← Reasoning Under Uncertainty: Probabilistic FoundationsNext lesson: How Machines Understand Spoken Language →

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

Tracking hidden states over time with HMMs, Kalman and particle filters.

  • Describe the Markov and sensor assumptions and the three ingredients of a temporal model
  • Apply the forward algorithm to filter a hidden Markov model one reading at a time
  • Distinguish filtering, prediction, smoothing and finding the most likely sequence with the Viterbi algorithm
  • Compare Kalman filters, dynamic Bayesian networks and particle filters for different tracking problems

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

Opening Question

Guessing Rain From Umbrellas

You work in an office with no windows. You can't see the weather, but you can see whether each colleague walks in carrying an umbrella. One umbrella is weak evidence. A string of umbrellas over several days is stronger, and today's weather is closely tied to yesterday's. So how sure can you be that it's raining right now? To answer well, you have to combine what you see with how the world tends to change.

Where It Applies

Hidden States That Change Over Time

Many real systems look like this: a patient's condition over a hospital stay, the health of a machine, a moving object's position, or the words in a sentence. The true state is hidden, it changes with time, and all we get are noisy readings. Dynamic probabilistic models are built for this job: probability models that evolve step by step.

Two Assumptions

Markov and Sensor Assumptions

Time is divided into steps. At each step there's a hidden state X, which we want to know, and an evidence variable E, which we observe. Two assumptions make this manageable. The Markov assumption: the next state depends only on the current state, not the whole history. The present summarizes the past. A model that looks back two steps is second-order, and it can be rewritten as first-order by bundling two steps into one state. The sensor assumption: each reading depends only on the state at that moment. And if the rules don't change over time, the process is stationary, and the same probabilities are used at every step.

Model Ingredients

Prior, Transition and Sensor Models

A temporal model then needs just three ingredients. A prior: the belief at the start. Here, rain on day zero has probability 0.5. A transition model: the chance of each state, given the one before. Rain follows rain with probability 0.8, and follows sun with probability 0.3. And a sensor model: the chance of each reading, given the state. An umbrella shows up 90 percent of the time in rain, and 20 percent in sun.

Markov Chain Forecast

Settling at a 0.6 Chance of Rain

If the state could be seen directly, this would be a plain Markov chain. Start on a rainy day, and forecast. One day later, rain has probability 0.8. Then 0.7, 0.65, 0.625, and 0.6125. The pattern is 0.6, plus 0.4 times one half to the k. The chain forgets where it started, and settles at 0.6: its long-run, or stationary, chance of rain. That forgetting matters later. The further ahead we predict, the less today's evidence helps.

Four Inference Tasks

Filtering, Prediction, Smoothing and Best Path

Given a model and a sequence of readings, four questions come up. Filtering: what's the state now, given all the evidence so far? How likely is rain today, given the umbrellas until today? Prediction: what will the state be later? How likely is rain in three days? Smoothing: what was a past state, now that more evidence has arrived? Was it raining on Monday, given umbrellas through Wednesday? And the most likely sequence: which whole path of states best explains the evidence? Filtering is the everyday task for anything that must act now, like a monitor or a tracker. Smoothing gives better estimates of the past, but only after a delay.

Forward Algorithm

Predict, Update and Normalize

A hidden Markov model, or HMM, is a temporal model with a single discrete hidden variable. The weather example is an HMM with two states. Filtering keeps a belief: the probability of each state, given the evidence so far. Each new reading updates it in three moves. Predict: push the old belief through the transition model. Each state's predicted probability sums, over previous states, the old belief times the transition chance. Update: multiply each prediction by the chance of the new reading in that state. Normalize: divide by the total, so the beliefs add up to one. Each step needs only the last belief and the newest reading.

Worked Example

Three Days of Umbrella Readings

The readings: umbrella on day one, umbrella on day two, and no umbrella on day three. Day one. Predicted rain is 0.8 times a half, plus 0.3 times a half: 0.55. Times 0.9 gives 0.495. Sun gives 0.09. Normalize: 0.495 over 0.585 is 0.846. Day two, another umbrella. The prediction is 0.723, and after the update, rain reaches 0.922. Day three, no umbrella. That reading has chance 0.1 in rain, and 0.8 in sun. The prediction, 0.761, falls to just 0.285. Each step costs about S times S multiplications, for S states, however many days have passed, so filtering runs in real time. And normalizing keeps the numbers from shrinking toward zero.

Quick Check

A Third Umbrella on Day Three

Quick check. Change day three: suppose a third umbrella appears instead. Start from 0.922 after day two, as before. What's the filtered chance of rain on day three? Pause, and work it out. About 0.93. Predict: 0.761. Update: times 0.9 is 0.685, and sun's share gives 0.048. Normalize: 0.935. 0.76 is only the prediction, before the reading counts. And the belief isn't stuck: each umbrella still nudges it up, a little less each time.

Prediction and Smoothing

The Forward-Backward Algorithm

Prediction repeats the predict step, with no new evidence. From day three's 0.285, rain goes 0.442, 0.521, 0.561, and on toward 0.6. The evidence fades, and the forecast drifts to the long-run value, just like the plain chain. Smoothing adds a second, backward pass. A backward message summarizes how well each state explains the later readings. Multiply forward by backward, and normalize: that's the forward-backward algorithm. Day one rises from 0.846 to 0.880, because day two's umbrella supports more rain. Day two falls from 0.922 to 0.827. Day three has no later evidence, so it stays at 0.285.

Most Likely Sequence

Viterbi Finds Rain, Rain, Sun

The most likely state at each step isn't always on the most likely sequence, because the best sequence must also make sense from step to step. The Viterbi algorithm finds that sequence. It's the forward algorithm with each sum replaced by a maximum, remembering which predecessor gave it. Day one: the best score for rain is 0.5 times 0.8 times 0.9: 0.36. Day two: rain is best reached from rain: 0.36 times 0.8 times 0.9, which is 0.2592. Day three: sun is best, also reached from rain: 0.2592 times 0.2 times 0.8, or 0.0415. Follow the stored arrows back from the best final score: rain, rain, sun. Both algorithms take time proportional to the days, times S squared.

Learning Parameters

Counting Transitions and Baum-Welch

So far the probabilities were given. In practice, they're estimated from data. If the true states are known, count and divide. Ten days of known weather: rain, rain, rain, sun, sun, rain, sun, sun, sun, rain. Rain occurs four times before another day. Twice rain follows it, so rain after rain is 2 over 4: 0.5. Sun occurs five times, and rain follows twice: 2 over 5, 0.4. Ten days is far too few. Real models use thousands of steps. If only the readings are known, use expectation-maximization, which for HMMs is the Baum-Welch algorithm. It runs forward-backward to get expected counts, then re-estimates, again and again. Each round improves the fit, but it can stop at a local optimum, so the starting guess matters.

Continuous States

Kalman Filter Mean and Variance

An HMM has a few discrete states, but many quantities are continuous: a temperature, a position, a speed. The Kalman filter handles them. It assumes the state changes in a linear way, plus random noise, and that the noise is Gaussian, a bell curve, both in the change and in the sensor. Then the belief stays Gaussian, so the filter keeps just two numbers: the mean, its best estimate, and the variance, its uncertainty. Predict: move the mean by the dynamics. The variance grows, because our knowledge is older. Update: blend in the measurement, z. The gain, K, is the predicted variance, over the predicted variance plus the sensor's noise variance. The new mean is the prediction, plus K times the measurement's surprise. The new variance is one minus K, times the predicted variance.

Worked Example

Gain Balances Prediction and Reading

Track a slowly drifting quantity. Start at mean 20, variance 4. Each step adds drift variance 1, and the sensor's noise variance is 4. Step one: predicted variance 5. The reading is 24, the gain is five ninths, so the mean moves to 22.22, and the variance falls to 2.22. Step two: reading 22, mean 22.12, variance 1.78. Step three: reading 23, mean 22.48, variance 1.64. The uncertainty shrinks from 4 toward about 1.6, because each measurement adds information. The gain sets the balance. With a very accurate sensor, noise 1, the gain is 0.83: trust the reading. With noise 25, it's 0.17: keep the prediction. For linear dynamics with Gaussian noise, the Kalman filter is exact. The extended Kalman filter handles mildly non-linear cases by straightening them near the estimate.

Quick Check

New Mean After a Reading of 30

Quick check. A Kalman filter predicts a mean of 26, with variance 3. The sensor's noise variance is 1, and it reads 30. What's the new mean? Pause, and work it out. Twenty-nine. The gain is 3 over 3 plus 1: 0.75. The surprise is 30 minus 26, 4, and 0.75 times 4 is 3. Twenty-six plus three. Twenty-eight just averages the two, which ignores that the sensor is more trusted. Thirty trusts the sensor completely, which only a noiseless sensor deserves.

Dynamic Bayesian Networks

Many Variables in Each Time Slice

A dynamic Bayesian network, or DBN, generalizes both. Each time slice holds several variables, arranged as a Bayesian network, and the same links repeat from step to step. HMMs and Kalman filters are special cases. The benefit is compactness. Ten hidden yes-or-no variables, as one HMM state, make 1,024 states, and a transition table of over a million entries. In a DBN where each depends on only three variables from the step before, each needs eight numbers: 80 in total. The catch: variables that start independent become correlated over time, so exact filtering in a big DBN is again enormous. That motivates approximate methods.

Particle Filtering

Predict, Weight and Resample

A particle filter approximates the belief with a cloud of N samples, called particles, each a guess at the hidden state. It needs no belief formulas, so non-linear and non-Gaussian problems are fine. Each step has three moves. Predict: move every particle forward, by sampling from the transition model. Weight: give each particle the probability of the new reading in its state. Resample: draw N fresh particles, in proportion to the weights. Ten particles: six rain, four sun. An umbrella is seen. Rain particles weigh 0.9 and sun 0.2, a total of 6.2. Rain holds 87 percent. After resampling, about nine of ten are rain, close to the exact answer of 0.87 from Bayes' rule.

Error and Weakness

Square Root Error and Particle Depletion

In one experiment, day three's error fell from 0.186 with 10 particles, to 0.052 with 100, and 0.005 with 10,000. Each tenfold increase cut the error by about three, the square root of ten. Cost grows with N, while error shrinks like one over the square root of N. The main weakness is particle depletion. If no particle lands near the true state, after very surprising evidence, the cloud can lose track. More particles, or fresh random ones, help.

Choosing a Method

Matching the Model to the Problem

Choosing a method. A few discrete states: an HMM, with exact forward and Viterbi algorithms. Continuous states, linear, with Gaussian noise: a Kalman filter. Many interacting variables: a DBN. Strongly non-linear or non-Gaussian problems, or a belief too complicated to write down: a particle filter. Back to the windowless office. After two umbrellas and then none, filtering says rain today is only about 28 percent. And smoothing revises yesterday down, to about 83 percent: the missing umbrella hints the rain may have stopped.

Key Takeaways

Temporal Models in Summary

To sum up. Temporal models rest on the Markov and sensor assumptions: each state depends on the one before, and each reading on its own state. Filtering estimates the present, prediction the future, smoothing the past, and Viterbi the best whole path. The forward algorithm predicts, updates and normalizes. A Kalman filter keeps a mean and a variance, and its gain balances prediction against measurement. DBNs model many variables compactly, and particle filters approximate the belief with weighted samples.

Think About It

An Object Hidden Behind a Wall

Here's something to think about. A particle filter tracks an object, and then the object hides behind a wall for several seconds. What happens to the cloud of particles meanwhile? What if the object reappears somewhere unexpected? How would you change the filter?

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 Modeling Change Over Time: Dynamic Probabilistic Systems

What is the difference between filtering, prediction, and smoothing in a hidden Markov model?
Filtering estimates the current hidden state from all evidence so far, prediction estimates a future state, and smoothing estimates a past state using evidence that arrived later. Filtering suits systems that must act now, such as trackers and monitors. Smoothing gives better estimates of the past but needs a delay. Prediction repeats the transition step with no new readings, so the forecast drifts toward the chain's long-run, or stationary, distribution.
How does the forward algorithm update a belief in an HMM?
The forward algorithm updates the belief with three moves per reading: predict, update and normalize. It pushes the old belief through the transition model, multiplies each state's prediction by the probability of the new reading in that state, and divides by the total so the beliefs sum to one. With a 0.55 predicted chance of rain and an umbrella seen 90 percent of the time in rain and 20 percent in sun, rain rises to about 0.846.
How do you calculate the Kalman gain and the updated mean?
The Kalman gain K equals the predicted variance divided by the predicted variance plus the sensor noise variance. The new mean is the predicted mean plus K times the measurement minus the prediction, and the new variance is one minus K times the predicted variance. With a predicted mean of 20, predicted variance 5, sensor noise variance 4 and a reading of 24, K is 5/9, the mean becomes about 22.22 and the variance about 2.22.
When should you use a particle filter instead of a Kalman filter?
A particle filter is a good choice when the dynamics are strongly non-linear, the noise is not Gaussian, or the belief is too complicated to write down. It represents the belief with N samples that are moved forward, weighted by the new reading and resampled. A Kalman filter is exact for linear dynamics with Gaussian noise and keeps only a mean and a variance. Particle filter error shrinks roughly like one over the square root of N.

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 →