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:
Any context-free grammar can be represented in CNF
I 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?