Active Edges
Abstract:In this lecture we move from passive chart parsing to active chart parsing. Active chart parsing is based on a very simple idea. A passive chart, like the one we worked with in the previous chapter, is used to keep a record of
complete constituents that we have found. (For example, on a passive chart we can record the information that the string between nodes 2 and 4 is an NP.) In an active chart we additionally record
hypotheses --- that is, we record what it is we are actually looking for, and how much of it we have found so far. Such information is recorded in
↗active edge s (or
↗active arc s).
In this lecture we move from passive chart parsing to active chart parsing. Active chart parsing is based on a very simple idea. A passive chart, like the one we worked with in the previous chapter, is used to keep a record of
complete constituents that we have found. (For example, on a passive chart we can record the information that the string between nodes 2 and 4 is an NP.) In an active chart we additionally record
hypotheses --- that is, we record what it is we are actually looking for, and how much of it we have found so far. Such information is recorded in
↗active edge s (or
↗active arc s).
Here's an example of an active edge:
Figure 3: Active Edge Example 1 An example of an active edge. |
This is an arc between nodes 0 and 2. The important thing to note is the arc label: S→NP.VP This says: "I am trying to build an s, consisting of an np followed by a vp. So far I have found an np arc, and I'm still looking for the vp." So the insignificant looking `.' in the middle of the rule is very important: it marks the boundary between what we have found so far, and what we are still looking for.
Here's another example:
Figure 6: Active Edge Example 2 An example of an active edge. |
This says: "I am trying to build an s, consisting of an np followed by a vp, starting at node 0. So far I have neither found the np nor the vp that I need."
Here's another example:
Figure 9: Active Edge Example 3 An example of an active edge. |
This says: "I am trying to build a vp, consisting of a dv followed by an np followed by a pp, starting at node 4. So far I have found a dv arc and an np arc, and I'm still looking for the pp." The np-arc ends in node 8, so the pp-arc will have to start in node 8.
Here's another example:
Figure 12: Active Edge Example 4 An example of an active edge. |
This says: "
I am trying to build a vp consisting of a tv followed by an np starting at node 4 --- and I've done it!" Note that the `.' is at the
end of the arc label. This means that everything we need to find has been found. Such an arc is called a
↗passive edge , or a
↗passive arc . It records
complete information. In effect, these are the arcs we are used to from the previous chapter, though we didn't use the `.' notation there.
One final example:
Figure 15: Active Edge Example 5 An example of an active edge. |
This says: "I am trying to build an s consisting of an np and a vp starting at node 0 --- and I've done it! I've found both the np and the vp, and moreover, I've done it in a way that the arc goes all the way from the first to the last node. This means I've recognized the sentence!."