9 – NLPND POS 08 Quiz How Many Paths Now V1

So, here we are, we have our diagram, which is called a Trellis diagram. And in here, we’re going to find the path of the highest probability. Let’s recall that transition and emission probability tables. We’ll record the emission probabilities and we won’t record the transmission ones yet because they will look too messy. But we’ll simplify this graph a bit. First, let’s remove all the edges of probability zero. And now, let’s remove all the vertices with probability zero. The reason is that, any path that goes through these edges or vertices will have probability zero as a probability that, that path gives of the sentence, is the product of all the probabilities at the edges and vertices. And finally, since we need the path to go from start to finish, we’ll remove the edges that don’t take us to the end. And now, we need to find the maximum probability path in this Trellis, a much simpler one. So, here’s a quiz, how many paths do we have to check now?