There was some heated discussion on CYK and unit production rules during today's ELPL lab session. In essence, the CYK algorithm expects all the grammar rules to be in the form A -> B C except for when words (terminals) are produced in which case it expects them to be in the form A -> a. This is known as the Chomsky Normal Form (CNF),
However, as we have all seen, our treebanks are not like that; there are some unit productions. I spent some time making up variations of CYK that would work with less strict assumptions but to no avail. It really felt that the problem isn't something that can be easily overcome with a simple hack. From what I could tell, there was some deeply ingrained constraint that probably makes it impossible for any simple modification of CYK to work with a grammar like the one we have.
Still, not all hope is lost. Wikipedia says:
However, this transcription to the CNF might introduce new symbols or merge existing ones. That could pose a problem with the evaluation later because the parsing is expected to produce syntax trees that use the same terminology as the ones in the training dataset.
But! If I understand the algorithm correctly, the only contentious point is when eliminating rules of the form A -> B C D ... which introduces new symbols. Luckily, we don't have any rules in that form.
So, we could just go through the grammar and each time we find a unit rule, A -> B, we remove it. Then, for each rule in the form B -> u (where u is a string that can be composed of terminal and non-terminal symbols) we add the rule A -> u, unless it's one of those unit rules we removed before. This is repeated until no unit rules are left.
A possible issue with the above approach is how to deal with the frequencies / probabilities of these rules. How are we supposed to decide the probabilities of the new rules based on the removed ones? Other than this one thorn, do you think this is a good solution?
However, as we have all seen, our treebanks are not like that; there are some unit productions. I spent some time making up variations of CYK that would work with less strict assumptions but to no avail. It really felt that the problem isn't something that can be easily overcome with a simple hack. From what I could tell, there was some deeply ingrained constraint that probably makes it impossible for any simple modification of CYK to work with a grammar like the one we have.
Still, not all hope is lost. Wikipedia says:
Any context-free grammar can be represented in CNFI suppose that, by extension, this must be true for PCFGs as well. So, in essence, we should be able to find an algorithm to transcribe our syntax trees and/or grammar to this form, with no loss of information, right? It seems that this might be our best bet. Wikipedia again suggests one. The same algorithm (and some motivation on why it works) can be found in Michael Sipser's "Introduction to the Theory of Computation".
However, this transcription to the CNF might introduce new symbols or merge existing ones. That could pose a problem with the evaluation later because the parsing is expected to produce syntax trees that use the same terminology as the ones in the training dataset.
But! If I understand the algorithm correctly, the only contentious point is when eliminating rules of the form A -> B C D ... which introduces new symbols. Luckily, we don't have any rules in that form.
So, we could just go through the grammar and each time we find a unit rule, A -> B, we remove it. Then, for each rule in the form B -> u (where u is a string that can be composed of terminal and non-terminal symbols) we add the rule A -> u, unless it's one of those unit rules we removed before. This is repeated until no unit rules are left.
A possible issue with the above approach is how to deal with the frequencies / probabilities of these rules. How are we supposed to decide the probabilities of the new rules based on the removed ones? Other than this one thorn, do you think this is a good solution?
According to Gideon in an e-mail to me:
ReplyDeleteThe unary non-terminals only appear at the start of a tree (TOP -> something). And right before terminals. In both cases they are restricted to one occurence only. Thus solution:
Instead of only adding terminal producing non-terminals in row 1 of CYK, also check if these non-terminals can be produced by other non-terminals in a unary way, and add these. For the non-terminals added this way, add an annotation indicating which other non-terminal it belongs to. Now you can run your CYK algoritm like you would otherwise. When doing the tree reconstruction and probability calculation, you simply have to take into account the annotations of the non-terminals in the first row of the piramid matrix.
This makes sure you do not change the probabilities, nor do you hack anything out of the trees.
Lotsa love,
Tijmen
Thanks Tijmen, we'll probably do it this way then.
ReplyDelete