It's all about parsing. The writeup is really long, but don't be too intiminated by it. It's long because I tried to give a lot of debugging help. The project is all about grammars and parsing, so go off and do syntax!
@Souwa: I'm not sure why you'd want to... you're welcome to change it, but then your output won't match mine. Certainly later (in the grammar writing part) you'll want to change it.
For the Chart Parsing part, an example of the output tree is:
-0.7499 (S (S1 (NP Det Noun) (VP VerbT (NP Det Noun))) .)
So should we ignore all the unary rules (e.g., Nbar -> Noun) when we output the tree? Because if we follow the given grammar, there should be (Nbar Noun) in the tree.
@Segan & @Viet-An: This is fixed in the .pdf now. Sorry about that -- it was some weird bug I had. It only affected that part of the assignment, though: the rest is fine.
while working on part 4 of the project, we realized that the binarized version of the wsj.gr contains rules that will make recursion go infinitely long:
1 S S 3 PP PP 16 VP VP 22 ADJP ADJP
the number at the start is the count that it occurred. These rules can cause our algorithm to continue forever... what is the best way to handle these rules? Should we ignore them (since they are very rare) or should we simply stop recursing at a fixed depth like what you mentioned in part 3? How did these rules come about in the first place?
Okay, there are a few questions here.
For the first one (i.e., I don't want CKY to loop forever) I'm going to do the annoying professor thing and answer the question with a question :). What is the probability of these productions? Is it less than one? If you apply a unary rule to some item in a chart, what cell in the chart does the result go into? What is the label of the old item and the new item? How do the probabilities compare (hint: use your answer to the first question I asked)? What does this tell you about optimal parses and loopy rules?
Hopefully that's enough of an answer.
As to how they come about, it's actually kind of complicated. One answer (which is a lie) is that if you're using X-bar theory, then rules like N' -> N' are actually common. Of course the treebank annotation doesn't conform to X-bar theory, so that's a non-answer.
I *think* the real answer has to do with traces and empty categories. The treebank actually includes traces, but I removed them automatically for you (you're welcome!). When I removed them, I only removed the traces and didn't mess with the rest of the tree, so if you had something like (NP (trace) PP) I just mapped that to (NP PP). I think you sometimes get things like (NP (trace) NP), which, when the trace is removed, just beomces (NP NP).
I'm not 100% sure that's the truth, but I think it's right :).
For the section 3. Grammar Writing, should I only modify the basic.gr file? I wonder I can add some features like hw#5 to the grammar(basic.gr) and lexicon(vocab.gr). If it is possible, I think I should submit both files to http://www.cs.utah.edu/~hal/tmp/grammar.pl.
Cool... Oct 19 will be a tough day, CL P2 due and ML midterm...
ReplyDeleteFor the Warm Up part of the project, are we allowed to change some of the "Misc" tags to our own tags in the Vocab.gr file?
ReplyDelete@Souwa: I'm not sure why you'd want to... you're welcome to change it, but then your output won't match mine. Certainly later (in the grammar writing part) you'll want to change it.
ReplyDeleteFor the Chart Parsing part, the tree produced in the example look like this:
ReplyDelete-0.7499 (S (S1 (NP Det Noun) (VP VerbT (NP Det Noun))) .)
So should we ignore all the unary rules (e.g., Nbar -> Noun) when printing out the tree?
For the Chart Parsing part, an example of the output tree is:
ReplyDelete-0.7499 (S (S1 (NP Det Noun) (VP VerbT (NP Det Noun))) .)
So should we ignore all the unary rules (e.g., Nbar -> Noun) when we output the tree? Because if we follow the given grammar, there should be (Nbar Noun) in the tree.
@Segan & @Viet-An: This is fixed in the .pdf now. Sorry about that -- it was some weird bug I had. It only affected that part of the assignment, though: the rest is fine.
ReplyDeleteI received the following question by email:
ReplyDeletewhile working on part 4 of the project, we realized that the binarized version of the wsj.gr contains rules that will make recursion go infinitely long:
1 S S
3 PP PP
16 VP VP
22 ADJP ADJP
the number at the start is the count that it occurred. These rules can cause our algorithm to continue forever... what is the best way to handle these rules? Should we ignore them (since they are very rare) or should we simply stop recursing at a fixed depth like what you mentioned in part 3? How did these rules come about in the first place?
Okay, there are a few questions here.
For the first one (i.e., I don't want CKY to loop forever) I'm going to do the annoying professor thing and answer the question with a question :). What is the probability of these productions? Is it less than one? If you apply a unary rule to some item in a chart, what cell in the chart does the result go into? What is the label of the old item and the new item? How do the probabilities compare (hint: use your answer to the first question I asked)? What does this tell you about optimal parses and loopy rules?
Hopefully that's enough of an answer.
As to how they come about, it's actually kind of complicated. One answer (which is a lie) is that if you're using X-bar theory, then rules like N' -> N' are actually common. Of course the treebank annotation doesn't conform to X-bar theory, so that's a non-answer.
I *think* the real answer has to do with traces and empty categories. The treebank actually includes traces, but I removed them automatically for you (you're welcome!). When I removed them, I only removed the traces and didn't mess with the rest of the tree, so if you had something like (NP (trace) PP) I just mapped that to (NP PP). I think you sometimes get things like (NP (trace) NP), which, when the trace is removed, just beomces (NP NP).
I'm not 100% sure that's the truth, but I think it's right :).
For the section 3. Grammar Writing, should I only modify the basic.gr file?
ReplyDeleteI wonder I can add some features like hw#5 to the grammar(basic.gr) and lexicon(vocab.gr).
If it is possible, I think I should submit both files to http://www.cs.utah.edu/~hal/tmp/grammar.pl.
@Anonymous: no, please feel free to modify the lexicon to your hearts content. just concatenate them and upload them as one big file to grammar.pl.
ReplyDelete