Video 8-6: Probabilistic Parsing

0:02 So let's look at these algorithms that can uh fill these two magic boxes. In particular, determine given this a sequence what's the most likely derivation. Okay, I mentioned before that the theory of formal languages helps us and we can indeed recycle most of the ideas there. So let's uh do a little refresher on what what you would normally do in some undergrad TCS module. You would talk about contextf free grammarss and then you would also ask the question uh given a grammar and a string is that string part of the language generated by the grammar yes or no and then you would say ah in a general contextf free grammar ooh that seems not so easy to do let's not do that even and instead you would look at chsky normal forms uh that just makes the whole description of parsing much easier and maybe I can come back to a little bit why um that's that's the part that you usually don't talk about in in undergrad modules uh to not scare people away from this lovely area. Uh Shamsky normal form basically says we can without loss of generality assume that the grammar has only two types of rules. Either a non- terminal is replaced by a single terminal or the non- terminal is replaced by two other non- terminals.

1:25 In particular, um there's a few things that are not allowed. And the proof for that this without loss of generality assumption is true essentially tells you how to get rid of each of the unwanted features a grammar might have. And by just doing them the elimination in the right order so that later elimination steps don't reintroduce the trouble you've got rid of earlier you can turn a grammar effectively into one in Shamsky normal form. uh formally the theorem that you probably have have seen at some point if you had such a module is given in arbitrary contextf free grammar except that here in this version I'm not allowing the grammar to produce the empty string just because if this is what you want to have there's no way to produce the empty string right you you have no way to express that that's kind of easy to do if you wanted to you could generalize and say ah okay if the language contains this empty string I'm going to have one separate rule outside of these that produces the empty string. But I can only do that from the start symbol and then I'm done. Or I branch off in the part that's equivalent to the grammar without the empty string.

2:43 And that can be using only these types of rules. For RNA structures, we don't really need empty strings, right? We're not super interested in predicting the the most likely structure of nothing. it's not so uh relevant. So if you're given an arbitrary grammar, you can find another one that has the same language. Uh no need to say that twice. And the rules are of this particular form. Non- terminal goes to two non- terminals or non- terminal goes to a single terminal. That's just this pattern in formally written.

3:22 I don't care about the algorithm so much. um just uh if if you've if you've done it, maybe you re you recognize it again. If you've never done it, I think it's a a fun one to look at, but we don't need it here, so forget about it.

3:41 Now, what's the benefit of having these uh these restricted rules? Um, one big benefit is that uh if you start from a certain non- terminal, either you're already done, you're producing a single terminal string or you're producing two terminal strings from these other non- terminals, but neither of them can be empty. Okay? So, whenever you apply one rule, you make strict progress towards producing a final string. You cannot in particular have a loop that brings you back to where you started. Derivations are always finite in Shamsky normal form. There's no way to go in a loop without making the string you produce ever longer. So in a way you could say the number of rules that you use is somehow a bounded function of the size of the final string.

4:35 And I guess you can even say it's linear because uh these rules you can only have as many as you have terminals. And these rules form a binary tree. So there are uh n minus one of these if you have n symbols in the end. It's very rigid. That's why it makes parsing easier. Uh the algorithm to do the parsing is called ck. cocka younger kasami after the inventors and is given a a grammar in chumpsky normal form and a a terminal string and the easiest version says let's it's just deciding is that string in the language of the grammar or not and um I'm presenting this here uh as if this was a very surprising idea I don't know u you solve the more general problem where you don't just ask can I go from the start symbol to the entire string. But you ask the question, can I go from all of these non- terminals to all of the possible substrings of that string?

5:43 Clearly, if you solve that question, you've solved the original one because that's just inserting certain values. You start from S and you go to everything.

5:56 But it turns out that this has a nice structure so that you can reuse bits. And it smells a lot like uh a classic design algorithm design technique.

6:07 Every derivation whatever it produces at the end has to start with the first rule. What rule does it start with so that we generate exactly that string if it's even possible? Well, I don't know. So I'm going to guess and we only have two different types of rules. That could be the first rule. So I'm going to go through two different cases. If my first rule is supposed to look like this, I'd better be already in the case that I have a single terminal to produce. And so, uh, I get this single E terminal from A if and only if such a rule exists in my grammar. That's it. And uh for the other types of rules, I can generate from a this substring if and only if there's some way to go from a to b c and then from b to the left part and from c to the right part. What I don't know a priory is one which rule should I use if a has several such and where's the cut point k this I don't know maybe there's only a single k that works but there will be one and so I'm just going to try all okay this is dynamic programming in case you haven't recognized um the way I describe it here in this slightly funny way is that if you if you look at the classic uh uh textbooks etc for theoretical computer science for this um formal languages and parsing they often present this algorithm without saying that it's dynamic programming which I find rather funny I don't know um maybe it's it's uh funny if you're teaching algorithms all day long now the running time for this as for any dynamic programming algorithm is deter is determined by the number of sub problems times the time you need to solve one uh the number of sub problems essentially comes from this double indices all subwords that's quadratic and then we have another factor n for trying all split points so the the way to usually draw this uh maybe I should have have this picture if a is to produce this substring from wi to wj exclusive then uh the First step would be go from A to B and then there's some way to split this tree around K, right? So that B produces the left half and C produces the right half.

8:44 And to try all of these, uh, you need another factor n. And there's a factor for the size of the grammar. If we're if we're strict, this determines whether or not a certain string is producible. You can say the dynamic programming table here is is boolean. It has yes or no for each of these uh sub problems. But of course, um if the answer is yes, you can also do a standard back trace through this dynamic programming table and that tells you which rules you use to get there. So in other words, it can give you a leftmost derivation by the standard trace reconstruction.

9:24 Okay, that's CK all old stuff that um maybe you just needed to undust some memories. How can we generalize this if the grammar has probabilities on the rules? Um to describe that properly, I finally need some notation for this. So let's say a derivation is just a sequence of rules with the understanding that really this should be a leftmost derivation. I think in all all the cases where we need it the understanding is you always replace the leftmost non- terminal and you first you use R1 then you use R2 and so on. The probability of such a derivation that's what we used before but uh informally described is the product of the probabilities of each of the rules that I used. Um it's convenient to have this notation leftmost derives.

10:21 Uh so I take some current sentential form and there's in the index a rule and I apply this as a leftmost derivation step. So ah this should have been green to make it extra clear that the X only represents terminal symbols. Then there's a non- terminal a coming that I'm not replacing by gamma. The Greek letters mean any sentential form a mixture of non- terminals and terminals. I can do this for one step or I can do it for an entire sequence an entire derbation sequence of rules.

10:56 Then we can restate the problem from the previous slide as follows. If you're given a contextf free grammar in Shamsky normal form and some string, you can ask is there some derivation for that string in our new notation. Give me some sequence of rules so that the leftmost derivation from S when applying these rules is W or tell me well it's not possible. Okay, that's the same problem we just solved. CYK does this. Now, uh what we'd rather like for our structure prediction problem is what I would call um a vurby parse. And so here the difference is that the input consists of a probabilistic grammar. So we have one more component here namely the probabilities of all the rules and again a word. And now we're not interested in any derivation but in the one that give in one that gives you the largest probability for that derivation subject to producing the string. Okay, so there's potentially many derivations where if you start from the start symbol and you apply the rules, you get W. But we want one that has the maximal probability.

12:16 that's only properly phrased or formalized what I've shown on the tiny example before. That's the problem we'd like to solve. Uh let me make extra clear what we're optimizing here because there's an alternative that might seem also intuitive and sometimes it is useful but in this case I think not. Um at least for the way we we describe the problem. uh there's there's two types of probabilities you could define for a string. One is what we've just used and I call this if you talk about the the value for a given terminal string exactly this thing here. I call that the vurby value. So that's the probability of the most likely derivation for that string. You could also ask if I just keep if I run the grammar freely. I start with the start symbol. I pick a random rule each time applying uh according to the probabilities from the grammar. What is the probability over all of the derivations that there may be to generate my given string?

13:29 And that also can make sense. That's what we call the the probability of that string or the production probability because that's really the probability of that string in the distribution over all strings if you just let the grammar grammar generate freely. It's the same same kind of term with the sum except sum instead of the maximum for us. You can essentially forget this but uh there's variance of the problem where you may need it. Uh essentially as an as an aside, if you want to train the probabilities for the rules and you don't have any ground truth training data. So you don't have sequences with known structures.

14:42 In that case, you can you can do an algorithm that's called expectation maximization, which conceptually is take your grammar, guess some random probabilities for the rules to start with, use that to predict what the structures, in your training data set might be. Then recmp compute your probabilities from that and keep going in the hope that this will converge to something sensible.

15:37 And it turns out if you do that, it's much more robust not to say I'm going to predict a single most likely derivation for my training data from this initially completely stupid grammar where I just picked random probabilities, but then pretend that this is the single and one and only prediction. It turns out it's more robust to use something based on these uh production probabilities where you average overall derivations. That's why this uh this second one is sometimes used there.

16:32 The attack phrase to read up about this if you care is the inside and outside algorithm. uh we're not going to do it here because I think we're already spending enough time on the RNA prediction problem and it's a bit of a I think these expectation maximization algorithms in this context at least don't work so well. Uh but in principle there's a way to do that that's more robust than taking Vurby parses and those want to use these uh summed up probabilities. Okay, we can turn the CYK algorithm that decides the word problem into one that computes vurby values by doing essentially nothing special. we just write where we previously had um here we could set that such a production is possible if either this is true or this is true for one K and one rule A to BC. So if you think about it, you would write this as a big or a logical or of all the options here.

17:54 Uh or in numbers is a bit like maximum. If any of the values is a one, then the or is the maximum of all those otherwise it stays zero. So if you want you can read this algorithm as exactly C YK if you set all the probabilities of rules to just a number one. It's not not a probability then but you could say if the PS are one for rules that exist and zero otherwise then this algorithm computes exactly the 01 version.

18:25 Uh but it turns out the same also works for vurby values. Um maybe with this with this single change I'll comment on. So uh in the same way as before we say we have sub problems for a certain non- terminal and for the for the total word but for contiguous subwords is what we'll need what we'll use it for. And that's the probability of the most likely derivation to go from A to W. Same as before. And then we can go from A to a single symbol exactly when there's this rule. And we can go from A to a certain longer substring if well there's a rule to go from A to two other non- terminals and then a way to go from B to the first half and from C to the second half. But if that is the case, the probability to do exactly that is the probability to first use that rule, then use all these rules and then use all these rules or just multiply them all together.

19:27 And here I take the maximum over all options because I want the most likely part. So the same dynamic programming approach works, the same running time results and the back trace gives me the most likely derivation and I just uh keep track of where the maximum came came from. Okay, so probabilistic parsing isn't hard. At least in Shamsky normal form, it's just the same as standard parsing, but computing some values instead of uh just boolean numbers, boolean functions.