[Chat log from a Google Hangout a few days ago. I thought I'd already posted this but apparently not!]
Schemes for revision:
(1) If we detect an error, do some kind of global search to fix it, using the work we've already done. Either hill-climbing starting with the current partial parse (and working only on the words we've touched so far), or else use dynamic programming on what we have so far but with the confident arcs frozen in place (cf. He He's recent method - I can send this to you). In both cases, there might be penalties for deviating from the current parse.
Also, in both cases we have to be careful because we are not trying to find a full parse, but rather a partial parse of the sort that MaltParser could have gotten to if it had picked the right moves. Probably we preserve the stack/buffer boundary although that's an interesting question.
(2) The only kinds of revision operators are to manage the beam. So we can go back and resurrect hypotheses that we previously pruned.
Ideally we'd like to share substructure among the hypotheses. One way of doing this is packed forests. A more modest way is to decide which edges to lock because we're confident, which means that the sentence is already chunked; then when going back to an earlier step, we can work forward but now use the chunks as if they were words (i.e., the previous confident steps are effectively redone for free).
[For left-to-right parsing, packed forests are handled by a tree-structured stack: http://acl.cs.qc.cuny.edu/~lhuang/papers/fastbeam.pdf . But I don't think we should do this unless ZPar supports it. The edge locking is more manageable and it's easier to see how to integrate it with revisions, but it requires a classifier to tell us which edges we are confident in.]
(3) A reasonable set of operators to undo and redo stuff.
This will require operators like unshift.
It probably breaks some of the invariants of arc-eager parsing, because you might unshift a word that already has right children, resulting in a word on the buffer that has right children (in effect, a phrase).
Another kind of operator is to delete an arc (where should this be possible?). And another might be to add or revise an arc, which forces you to remove any arcs that it crosses (so this starts to look like the hill-climbing method, except that fixing up the parse after these changes would be done by using arc-eager-type actions plus actions like unshift).
Maybe automatic removal of arcs is accompanied by unshifting the resulting fragments, so that we can then try to reassemble them.
But this breaks another invariant, because now we end up with something on the stack being a left child of a later element of the buffer rather than the first one.
Actually, it now looks like architecture 2. is a special case, where backtracking consists of removing some edges and unshifting accordingly.
I recommend trying to design as follows:
Design an arc-eager parser where the input already tells you that some arcs are present, possibly also that some arcs or groups of arcs are absent. (Example of a group of arc being absent: "D has no right children other than the ones I told you about" -- one might want to specify this in the input without explicitly listing all the non-children.)
So, if you do left-to-right parsing with this constraints, you should be able to parse faster because some of the edges are already known.
One "dumb" approach would be to just do ordinary arc-eager parsing, but to forbid any actions that would be incompatible with the arc constraints in the input. So sometimes you will be doing a 2-way or 1-way classification of actions rather than a 4-way classification as usual -- and if it's 1-way then there's nothing to do since you know what the answer must be.
In this case you don't have to change the representations or actions at all!
It's just the old arc-eager parser showing respect to constraints in the input.
Designing this version just really requires you to generalize the current oracle -- which asks whether a given action would be compatible with the parse so far (to the left) -- now we want to know if the action is compatible with the parse so far plus everything we were told in the input about arcs that must be present or absent in the future, too.
That might be an interesting puzzle.
This "dumb" approach is still one word at a time. We can probably speed it up by saying that the elements on the stack and buffer include trees that have been pre-assembled in the input; this basically stops us from having to even figure out that the 1-way classifications are 1-way because we don't see them at all (those decisions have already been made and incorporated into the trees), so the parser would take sublinear time.
So now, we can implement revision schemes on top of this -- a revision operator jumps from the current configuration of the parser to a new configuration, where both configurations are of the sort allowed by our new parser, such that some of the arcs are known to be present or absent based on stuff that we did and chose not to revise.
It doesn't have to jump all the way back to the beginning of the sentence, although that's an easy option. It can jump to an intermediate configuration of the sort we've been discussing, as if the new parser had already done some of its work. The revision operator just has to make sure that the configuration is valid, i.e., that it's something we could have gotten by parsing from the beginning with the current constraints, and that the current constraints are feasible (i.e., there is some parse consistent with them).
[Chat log from a Google Hangout a few days ago. I thought I'd already posted this but apparently not!]
Schemes for revision:
(1) If we detect an error, do some kind of global search to fix it, using the work we've already done. Either hill-climbing starting with the current partial parse (and working only on the words we've touched so far), or else use dynamic programming on what we have so far but with the confident arcs frozen in place (cf. He He's recent method - I can send this to you). In both cases, there might be penalties for deviating from the current parse.
Also, in both cases we have to be careful because we are not trying to find a full parse, but rather a partial parse of the sort that MaltParser could have gotten to if it had picked the right moves. Probably we preserve the stack/buffer boundary although that's an interesting question.
(2) The only kinds of revision operators are to manage the beam. So we can go back and resurrect hypotheses that we previously pruned.
Ideally we'd like to share substructure among the hypotheses. One way of doing this is packed forests. A more modest way is to decide which edges to lock because we're confident, which means that the sentence is already chunked; then when going back to an earlier step, we can work forward but now use the chunks as if they were words (i.e., the previous confident steps are effectively redone for free).
[For left-to-right parsing, packed forests are handled by a tree-structured stack: http://acl.cs.qc.cuny.edu/~lhuang/papers/fastbeam.pdf . But I don't think we should do this unless ZPar supports it. The edge locking is more manageable and it's easier to see how to integrate it with revisions, but it requires a classifier to tell us which edges we are confident in.]
(3) A reasonable set of operators to undo and redo stuff.
This will require operators like unshift.
It probably breaks some of the invariants of arc-eager parsing, because you might unshift a word that already has right children, resulting in a word on the buffer that has right children (in effect, a phrase).
Another kind of operator is to delete an arc (where should this be possible?). And another might be to add or revise an arc, which forces you to remove any arcs that it crosses (so this starts to look like the hill-climbing method, except that fixing up the parse after these changes would be done by using arc-eager-type actions plus actions like unshift).
Maybe automatic removal of arcs is accompanied by unshifting the resulting fragments, so that we can then try to reassemble them.
But this breaks another invariant, because now we end up with something on the stack being a left child of a later element of the buffer rather than the first one.
Actually, it now looks like architecture 2. is a special case, where backtracking consists of removing some edges and unshifting accordingly.
I recommend trying to design as follows:
Design an arc-eager parser where the input already tells you that some arcs are present, possibly also that some arcs or groups of arcs are absent. (Example of a group of arc being absent: "D has no right children other than the ones I told you about" -- one might want to specify this in the input without explicitly listing all the non-children.)
So, if you do left-to-right parsing with this constraints, you should be able to parse faster because some of the edges are already known.
One "dumb" approach would be to just do ordinary arc-eager parsing, but to forbid any actions that would be incompatible with the arc constraints in the input. So sometimes you will be doing a 2-way or 1-way classification of actions rather than a 4-way classification as usual -- and if it's 1-way then there's nothing to do since you know what the answer must be.
In this case you don't have to change the representations or actions at all!
It's just the old arc-eager parser showing respect to constraints in the input.
Designing this version just really requires you to generalize the current oracle -- which asks whether a given action would be compatible with the parse so far (to the left) -- now we want to know if the action is compatible with the parse so far plus everything we were told in the input about arcs that must be present or absent in the future, too.
That might be an interesting puzzle.
This "dumb" approach is still one word at a time. We can probably speed it up by saying that the elements on the stack and buffer include trees that have been pre-assembled in the input; this basically stops us from having to even figure out that the 1-way classifications are 1-way because we don't see them at all (those decisions have already been made and incorporated into the trees), so the parser would take sublinear time.
So now, we can implement revision schemes on top of this -- a revision operator jumps from the current configuration of the parser to a new configuration, where both configurations are of the sort allowed by our new parser, such that some of the arcs are known to be present or absent based on stuff that we did and chose not to revise.
It doesn't have to jump all the way back to the beginning of the sentence, although that's an easy option. It can jump to an intermediate configuration of the sort we've been discussing, as if the new parser had already done some of its work. The revision operator just has to make sure that the configuration is valid, i.e., that it's something we could have gotten by parsing from the beginning with the current constraints, and that the current constraints are feasible (i.e., there is some parse consistent with them).