Earley Parsing Algorithm in Natural Language Processing

[00:00:00]This video covers another form of constituency parsing called Earley parsing.

[00:00:05]I'll introduce the intuition behind Earley parsing, followed by the algorithm itself.

[00:00:10]Then I'll walk through a case example, to show how we could use Earley parsing to parse a short sentence.

[00:00:18]Earley parsing is another dynamic programming approach to constituency parsing.

[00:00:23]Unlike CKY, which is a bottom-up approach, Earley parsing is a top-down approach.

[00:00:28]It's more efficient than CKY because it allows you to fill a table in a single sweep rather than looping back around at the same level like we needed to do with CKY to check to see if any more constituents were matched.

[00:00:40]The entries in an Earley parsing table can contain three types of information: a subtree that corresponds to a single production rule, information about how much progress has been made in completing that subtree, and the position of that subtree with respect to the entire input sentence.

[00:00:59]Entries containing that information are usually referred to as states, and those states include structures that are referred to in Earley parsing as dotted rules. Basically a dotted rule just uses a dot to indicate progress towards completing a specific production rule.

[00:01:15]A state's position is also indicated with respect to the input as a whole, so there will be both a start index and an end index. These indices might be the same if the state is only concerned with an individual word or the state might span the entire input if it's representing a complete parse of the input.

[00:01:35]Some examples of what those states might look like are shown here. In the first case, we're saying that a top-down prediction for the start symbol is a verb phrase.

[00:01:44]The indices, zero and zero, mean that the constituent predicted by the state should begin at the start of the input string, and the dot currently lies at the start of the input as well, rather than within it.

[00:01:55]So the next word we'll by trying to match is "book."

[00:02:00]In the second case, we're saying that a top-down prediction for a noun phrase is a determiner followed by a nominal.

[00:02:06]The indices, one and two, indicate that the constituent predicted by the state should begin after the first word and the dot currently lies after the second word in the input.

[00:02:17]So the next word we'll be trying to match is "flight," and we'll be looking for a nominal.

[00:02:23]In the third case, we're saying that a top-down prediction for a verb phrase is a verb followed by a noun phrase.

[00:02:30]The indices, zero and three, indicate that the constituent predicted by the state should begin at the start of the string and the dot currently lies at the end of the string.

[00:02:39]It looks like the dot in the production rule is also at the end of the rule, so this rule has been successfully matched.

[00:02:46]This means that we've discovered a verb phrase subtree that spans the entire input phrase.

[00:03:01]These operators are the predictor, the scanner, and the completer, and I'll describe each of them in more detail in the next few slides.

[00:03:11]Operators can add new states to the chart, but no states are ever removed and the algorithm never backtracks.

[00:03:17]If we are able to complete a start state, that is move the dot to the end of the production rule for a start state, then we have a successful parse.

[00:03:31]The predictor can be applied to any state that has a non-terminal constituent immediately to the right of its dot, and the new states added by the predictor are added to the same chart entry as the generating state and they should also begin and end at the same points as the generating state.

[00:03:45]So, for example, a production rule with a dot followed by a verb phrase with a non-terminal constituent could have the predictor operation applied to it and result in a bunch of new production rules for verb phrases added to the table.

[00:03:57]If the dot followed the verb phrase in that same statement, though, the predictor operation could not be applied.

[00:04:06]The scanner operator can be applied when there is a non-terminal non-constituent to the right of the dot--- in other words, a part of speech category.

[00:04:15]This operator looks at the current input and adds a state that corresponds to that input word itself to the table.

[00:04:21]For example, if the category "verb" is to the right of a dot and "verb" is a part of speech category, then we'll check to see if our current input word matches a verb.

[00:04:30]If it does we'll add a state indicating that to the table with a dot to the right of the word, since we already matched it.

[00:04:39]Finally, the completer operator can be applied to a state when the dot is all the way at the right end of the production rule.

[00:04:46]When this is the case, it means that the parser has completed a subtree corresponding to the production rule.

[00:04:52]This means that we need to go back and find the other states that were searching for that subtree and create new states that are copies that have their dots advanced accordingly.

[00:05:01]For example, the completer might be able to complete the state specified when it encounters the state.

[00:05:09]We can walk through an Earley parsing example now to see how this works in more concrete terms.

[00:05:14]So let's start out at chart entry zero, so the beginning of our input string, "book that flight."

[00:05:19]We have some part of speech categories and some production rules. We'll go ahead and begin at the start state, gamma generates a sentence, with a dot before the sentence.

[00:05:30]We'll check our production rules and see that we can predict that a sentence generates a noun phrase followed by a verb phrase, and a sentence also generates a verb phrase. From those states, S1 and S2, we can also predict that a noun phrase generates a determiner followed by a nominal, a verb phrase generates a verb, and a verb phrase generates a verb followed by a noun phrase.

[00:05:52]We can't add any more states, because the dots for states three through five have part of speech labels to the right of them.

[00:06:03]that means we can apply the scanner operation to states three through five and correspondingly move ahead in our input.

[00:06:10]The next word in our input is "book," and we see that it can indeed be generated by a verb, although not by a determiner, so we'll add a state six, which will indicate that a verb generates the word "book," and we'll move the dot after the word "book" to indicate that we've already seen that word.

[00:06:27]Now, when we process state six, we can't use a predictor or a scanner operator because the dot is all the way at the end of the input, so we'll use the completer operator. We see that having a complete verb entry can lead to having a complete verb phrase entry, so we'll go ahead and add that.

[00:06:44]It will also allow us to move forward in the production rule where a verb phrase generates a verb followed by a noun phrase, so we'll add an updated state corresponding to that rule as well.

[00:06:54]Finally, having a completed verb phrase in state seven allows us to complete state two, so we'll add a completed version of that state to the table as well.

[00:07:04]So now we're done processing state eight and we have a non-terminal constituent to the right of our dot so we can go ahead and apply the predictor rule here.

[00:07:12]We see that a noun phrase can generate a determiner followed by a nominal so we'll add that as state ten.

[00:07:20]Finally, although we have a completion of the sentence subtree in state nine, we can't actually call this a successful parse of the entire input, because we haven't made it through the entire input yet, as we can see by our start and end indicators.

[00:07:33]Instead, it's a successful parse of the single word sentence "book," which isn't what we're looking for here, so we'll move on, and when we process state ten, we see that we have a part of speech tag to the right of the dot so we can apply our scanner operation.

[00:07:49]We'll go ahead and do that and we see that the next word in our input is a determiner which matches what we're looking for, so we'll add a state indicating that a determiner generates "that" to the table.

[00:08:00]We'll also advance the dot forward in our input string.

[00:08:04]Then we can take this new information in state eleven and apply the completer operation to move the noun phrase production rule forward.

[00:08:12]We can't use that information to advance any other existing subtree, so we'll move on to processing state twelve.

[00:08:18]We see that we have a non-terminal constituent to the right of the dot, so we apply the predictor and find that a nominal generates a noun, so we add that state. We move on to processing state thirteen and we see that a part of speech tag is to the right of the dot, so we apply the scanner and see that the next word in our input, "flight," matches a noun.

[00:08:41]So we add that info to the table and move the dot forward in our input string.

[00:08:46]We process state fourteen, and finally, we can apply the completer operation to complete state thirteen, so we go ahead and add an updated version of that with the dot to the right of noun.

[00:08:57]We process the newly added state fifteen and find that we can apply the completer operation to complete state twelve, so we'll add an updated version of that as state sixteen. Then we'll process state sixteen and find that we can apply the completer operation to complete state eight, so we'll add an updated version of that as state seventeen.

[00:09:17]We'll process state seventeen and find that we can apply the completer operation to complete state two, so we'll add an updated version of that as state eighteen, and finally, we process state eighteen and we find that this time we can apply the completer operation to the entire input string, completing state zero because its completion spans the entire input string, so we have a successful parse with the states you see here all contributing to it.

[00:09:47]Now, just like we saw with CKY, what you just saw functioned as a recognizer. It let us know whether a successful parse existed for the input string, but didn't tell us what that parse actually was.

[00:10:00]If we want to retrieve the actual parse trees produced by the Earley parser, we need the completer operator to also add backpointers to indicate where the completed operations came from.

[00:10:11]Then once we encounter a completed sentence node in the chart, we can just follow those pointers backwards to retrieve the parse.

[00:10:21]We can visualize that, just like you see here.

[00:10:23]We can see that we reached state eighteen by applying a completer to state seventeen, which we reached by applying completers to state six and sixteen.

[00:10:32]We reached state six through a scanner and state sixteen through a completer applied to states eleven and fifteen.

[00:10:39]We reached state eleven through a scanner and state fifteen through a completer applied to state fourteen.

[00:10:46]Finally, we reached state fourteen through a scanner. We could also use this information to fill in a hierarchical parse tree beginning at the sentence node and branching downwards, just like you see here.