C5W3L05 Error Analysis of Beam Search

In the third course of this sequence of five courses, you saw how error analysis can help you focus your time on doing the most useful work for your project. Now, beam search is an approximate search algorithm, also called a heuristic search algorithm. And so it doesn't always output the most likely sentence. It's only keeping track of B equals 3 or 10 or 100 top possibilities. So what if beam search makes a mistake? In this video you learn how error analysis interacts with beam search and how you can figure out whether it is the beam search algorithm that's causing problems and worth spending time on, or whether it might be your RNN model that is causing problems and worth spending time on. Let's take a look at how to do error analysis with beam search. Let's use this example of Jane Vezir frequent subtorn. So let's say that in your machine translation dev set, your development set, the human provided this translation. Jane visits Africa in September. And I'm going to call this Y star. So this is a pretty good translation written by a human. But let's say that when you run beam search on your learned RNN model, on your learned translation model, it ends up with this translation which we call Y hat. Jane visited Africa last September, which is a much worse translation of the French sentence that she changes the meaning. So it's not a good translation. Now your model has two main components. There is a neural network model, the sequence to sequence model, um, you know, which I'm going to call that's your RNN model. It's really an encoder and a decoder and you have your beam search Alphabet which you're running with some beam width B and want to be nice if you could attribute this error, this not very good translation to one of these two components. Was it the RNN or really the neural network that is more to blame, or is it the beam search algorithm that is more to blame? And what you saw in the third cause of the sequence is that it's always tempting to compare, collect more training data. That never hurts. So similar way it's always tempting to increase the beam width. You know, that never hurts or pretty much never hurts. But just as getting more training data by itself might not get you to the level of performance you want, um, in the same way increasing the beam width by itself might not get you to where you want to go. And so, but how do you decide whether or not improving the search algorithm is a good use of your time? So here's how you can break the problem down and figure out what's actually a good use of your time. Now, the rnn, the neural network, which is called rnn, really means the encoder and the decoder. It computes P of y given x. So for example, for a sentence, Jane visits Africa in September, you plug in Jane visits Africa. Again, I'm ignoring upper versus lowercase for now, right? And so on. And this computes P of Y given X. So it turns out that the most useful thing for you to do at this point is to compute, using this model, to compute P of Y star given X, as well as to compute P of Y hat given X using your RNN model and then to see which of these two is. So it's possible that the left side is bigger than the right hand side. It's also possible that P of Y is less than P of Y hat actually less than or equal to. And depending on which of these two cases hold true, you'll be able to more clearly ascribe this particular error, this particular bad translation to one of the RNN or the Beam Search algorithm being at greater fault. So let's figure out the logic behind this. Here are the two sentences from the previous slide. And remember, we're going to compute P of Y given X and P of Y hat given X, and see which of these two and see which of these two is bigger. So they're going to be two cases. In case one, P of Y given X as output by the RNN model is greater than P of Y hat given X. What does this mean? Well, the beam search algorithm chose Y hat, right? The way you got Y hat was you had an RNN that was computing P of Y given X. And Beam Search's job was to try to find the value of Y that gives that argmax. But in this case, Y actually attains a higher value for P of Y given X dented Y hat. So what this allows you to conclude is Beam Search is failing to actually give you the value of Y that maximizes P of Y given X. Because, you know, the one job that Beam Search had was to find the value of Y that makes this really big. But it chose Y hat, but Y actually gets a much bigger value. So in this case, you could conclude that Beam Search is at fault. Now, how about the other case in case 2, P of Y given X is less than or equal to P of Y hat given X, right? And then, you know, either this or this has got to be true. So either case one or case two has to hold true. What can you conclude under case two. Well, in our example, Y is a better translation than Y Y hat. But according to the rnn, P of Y is less than P of Y hat. So saying that Y is a less likely output than Y hat. So in this case, it seems that the RNN model is at fault, and it might be worth spending more time working on the rnn. There's some subtleties here pertaining to the length normalization that I'm glossing over. If the there's some subtleties pertaining to length normalization that I'm glossing over. And if you are using some sort of length normalization, instead of evaluating these probabilities, you should be evaluating the optimization objective that takes into account length normalization, but ignoring that complication for now, in this case, what this tells you is that even though Y is a better translation, the RNN ascribed Y a lower probability than the inferior translation. So in this case, I would say the RNN model is at fault. So the error analysis process looks as follows. You go through the development set and find the mistakes that the algorithm made in the development set. And so in this example, let's say that P of Y given x was 2 by 10 to the minus 10, whereas p of y hat given x was 1 by 10 to the minus 10. Using the logic from the previous slide, in this case we see that beam search actually chose Y hat, which has a lower probability than Y. So I would say beam search is at fault. So I abbreviate that B, and then you go through a second mistake or second bad output by the algorithm. Look at these probabilities, and maybe for the second example you think the model is at fault. I'm gonna abbreviate the RNN model with R and you go through more examples and sometimes the beam search is at fault, sometimes the model is at fault, and so on. And through this process, you can then carry out error analysis to figure out what fraction of errors are due to beam search versus the RNN model. And with an error analysis process like this, for every example in your dev set where the algorithm gives a much worse example where the algorithm gives a much worse output than the human translation, you can try to ascribe the error to either the search algorithm or to the objective function or to the RNN model that generates the objective function that beam search is supposed to be maximizing. And through this you can try to figure out which of these two components is responsible for more errors. And only if you find that beam search is responsible for a lot of errors, then maybe it's worth working hard to increase the beam width. Whereas in contrast, if you find that the RNN model is at fault, then then you could do a deeper layer of analysis to try to figure out if you want to add regularization or get more training data or try different network architecture or something else. And so a lot of the techniques that you saw in the third course in the third course in the sequence would be applicable there. So that's it for error analysis using beam search. I found this particular error analysis process very useful whenever you have a approximate optimization algorithm such as beam search that is working to optimize some sort of objective, some sort of cost function that is output by a learning algorithm such as a sequence to sequence model and sequence sequence RNN that we've been discussing in these lectures. So with that, I hope that you'll be more efficient at making these types of models work well for your applications.