# 8 – NLPND POS 07 Solution How Many Paths V1

Correct. The answer is 81. And the reason is that we have three possibilities for game, three for will, three for spot, and three for Will. Here are the 81 possibilities. So this is not so bad. We could check 81 products of four things and find the largest one. But what if we have say 30 parts of speech and we need to take a sentence of 10 words. Then we have 30 to the 10 possibilities. That starts being pretty large. In general, it’s exponential and we don’t want to have to check exponentially many things. We need to have a smarter algorithm. So, here’s another way to see this 81 combinations as paths. Here we have our sentence, and here we have our states. The start state and then three choices for each word and then the end state. This gives us the three times three times three times three, which is 81. Notice that each combination of four states also gives us a path from left to right. For example, the combination noun, modal, verb, noun, gives us this path over here. Unless we called that for each element in the path vertices and edges, we have a corresponding probability which comes from the emission and the transition probability tables. And then, we multiply these probabilities to get the total probability of the path. So, at the end of the day, what we have to do is find the path from left to right, that gives us the highest probability. We’ll do that in the next video.