Answers.Body: <p>Welcome to AI.SE @vdbuss, and great first question!</p>
  
  <p>This point is touched on in Section 15.2.3 (page 576 in my copy), in the second paragraph, and there's a good exercise at the end of the chapter (15.4) that is designed to get you to think through exactly why these are different procedures. If you want to really absorb it, I suggest trying to work out that exercise! If you want the quick answer, read on.</p>
  
  <p>The basic action of filtering is to generate a probability distribution <span class="math-container">$P(X_{t+1} | e_{1:t+1})$</span> using <em>only two pieces of information</em>, specifically the current state distribution <span class="math-container">$P(X_{t} | e_{1:t})$</span>, and the new piece of evidence <span class="math-container">$e_{t+1}$</span>. So, when computing the most likely sequence, the algorithm <em>cannot</em> take into account the sequences that are actually <em>possible</em>, while Vitirbi can.</p>
  
  <p>Here's a simple example: suppose I tell you that I'm going to drop you in a maze at one of two locations. I drop you near the top right corner with probability 0.75, and near the bottom left corner with probability 0.25. Suppose further that a <a href="https://en.wikipedia.org/wiki/Grue_(monster)" rel="nofollow noreferrer">Grue</a> is known (with certainty) to live somewhere near the bottom left corner. Using filtering, your maximum aposterori estimate for your location after being dropped in the maze (<span class="math-container">$t=1$</span>) is that you are in the top right corner. You then move 1 step to the right and can see a Grue. Clearly your estimate for your position in the second timestep <span class="math-container">$(t=2)$</span> must be the bottom left, because Grues only live there. But, you definitely can't end up moving to the bottom left by moving right from the top right, so your sequence has probability zero overall, despite using the maximum aposterori estimate for position at every step. To avoid this, Vitirbi uses a linear amount of extra space to select the maximum aposterori <em>sequence</em>, which in this case is clearly that you are near the bottom left in both timesteps.  </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-19T00:12:21.950Z
Answers.LastActivityDate: 2019-06-19T00:12:21.950Z
Answers.UserDisplayName: John Doucette
Body: <p>In Chapter 15 of Russel and Norvig's <em>Artificial Intelligence -- A Modern Approach (Third Edition)</em>, they describe three basic tasks in temporal inference: </p>
  
  <ol>
  <li>Filtering, </li>
  <li>Likelihood, and </li>
  <li>Finding the Most Likely Sequence.</li>
  </ol>
  
  <p>My question is on the difference between the first and third task.  Finding the Most Likely Sequence determines, given evidences <span class="math-container">$e_1,\dots,e_n$</span>, the most likely sequence of states <span class="math-container">$S_1,\dots,S_n$</span>.  This is done using the Viterbi algorithm.  On the other hand, Filtering provides the probability distribution on states after seeing <span class="math-container">$e_1,\dots,e_n$</span>.  You could then pick the state with the highest probability, call it <span class="math-container">$S'_n$</span>. I am guessing that <span class="math-container">$S'_n$</span> should always be equal to <span class="math-container">$S_n$</span>.  Likewise, you can already do the same after any prefix <span class="math-container">$e_1,\dots,e_i$</span>, again picking the most likely state <span class="math-container">$S'_i$</span>.  I would love to have a simple example where <span class="math-container">$S'_1,\dots,S'_n$</span> is not equal to the sequence <span class="math-container">$S_1,\dots,S_n$</span> produced by the  Viterbi algorithm.</p>
  
Tags: <probability>
Title: Viterbi versus filtering
UserDisplayName: vdbuss
ThreadText: # Viterbi versus filtering
  
  (Asked by: username_0 on 2019-06-18)
  
  In Chapter 15 of Russel and Norvig's *Artificial Intelligence -- A Modern Approach (Third Edition)*, they describe three basic tasks in temporal inference:
  
  1. Filtering,
  2. Likelihood, and
  3. Finding the Most Likely Sequence.
  
  My question is on the difference between the first and third task. Finding the Most Likely Sequence determines, given evidences $e\_1,\dots,e\_n$, the most likely sequence of states $S\_1,\dots,S\_n$. This is done using the Viterbi algorithm. On the other hand, Filtering provides the probability distribution on states after seeing $e\_1,\dots,e\_n$. You could then pick the state with the highest probability, call it $S'\_n$. I am guessing that $S'\_n$ should always be equal to $S\_n$. Likewise, you can already do the same after any prefix $e\_1,\dots,e\_i$, again picking the most likely state $S'\_i$. I would love to have a simple example where $S'\_1,\dots,S'\_n$ is not equal to the sequence $S\_1,\dots,S\_n$ produced by the Viterbi algorithm.
  
  **Tags:** probability
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-06-19. Score: 2
  
  Welcome to AI.SE @vdbuss, and great first question!
  
  This point is touched on in Section 15.2.3 (page 576 in my copy), in the second paragraph, and there's a good exercise at the end of the chapter (15.4) that is designed to get you to think through exactly why these are different procedures. If you want to really absorb it, I suggest trying to work out that exercise! If you want the quick answer, read on.
  
  The basic action of filtering is to generate a probability distribution $P(X\_{t+1} | e\_{1:t+1})$ using *only two pieces of information*, specifically the current state distribution $P(X\_{t} | e\_{1:t})$, and the new piece of evidence $e\_{t+1}$. So, when computing the most likely sequence, the algorithm *cannot* take into account the sequences that are actually *possible*, while Vitirbi can.
  
  Here's a simple example: suppose I tell you that I'm going to drop you in a maze at one of two locations. I drop you near the top right corner with probability 0.75, and near the bottom left corner with probability 0.25. Suppose further that a [Grue](https://en.wikipedia.org/wiki/Grue_(monster)) is known (with certainty) to live somewhere near the bottom left corner. Using filtering, your maximum aposterori estimate for your location after being dropped in the maze ($t=1$) is that you are in the top right corner. You then move 1 step to the right and can see a Grue. Clearly your estimate for your position in the second timestep $(t=2)$ must be the bottom left, because Grues only live there. But, you definitely can't end up moving to the bottom left by moving right from the top right, so your sequence has probability zero overall, despite using the maximum aposterori estimate for position at every step. To avoid this, Vitirbi uses a linear amount of extra space to select the maximum aposterori *sequence*, which in this case is clearly that you are near the bottom left in both timesteps.
  
  
  ---
  
  