12 October 2010
Project 2 warning on pruning results
I had a bug in my pruning, and wasn't pruning the right-most cells. (It was an off-by-one error.) Since English is mostly right-branching, the cells that touch the right edge (i.e., end of sentence) are incredibly important, so not pruning them makes life a lot better than otherwise. I'm working on fixing it right now and checking to make sure there aren't other bugs. I'll post a comment to this post when it's done and I've updated the results in the .pdf, but your pruning results should be much worse than what is in the writeup (i.e., with K=2, you should get no parse on 80-something sentences, and your f-score should be in the 10s or 20s).
Project 2 stuff...
I fixed the P2 pdf (just the one linked on the web page, not the one in the .tar.gz file) so that it includes unary productions in the examples. This is only relevant for part 2 -- nothing else changed.
Also, I'm not sure if I included them previously, but here are the links for the online test scripts:
Also, I'm not sure if I included them previously, but here are the links for the online test scripts:
Lecture 11: Incorporating Context
Many languages express some form of agreement. In English it is mostly Subject/Verb agreement (i.e., "He eats a sandwich" versus "They eat a sandwich"). In other languages agreement can be more widespread: Adjective/Noun, Determiner/Noun, Verb/Object, Noun/Relative Clause, etc.
Suppose we want to capture this with a (P)CFG.... the only real way to do this is to expand our set of non-terminals. I.e., we might start with a grammar like:
Which will generate our good sentences, but also bad sentences like "He eat a sandwich" and "They eats a sandwich". We can fix this by adding labels to our non-terminals:
Now life is great: we will no longer produce our bogus sentences. (Note that we would also have to account for "a" being singular, etc...)
Of course there are other phenomena we might want to capture, for instance pronouns sitting in object position have to change case: "A sandwich eats him" not "A sandwich eats he". If we ignore the singular/plural distinction, we can solve this separately.
And so on...
We've now solve the nominative/accusative issue, so we can combine the sing/plur grammar with the nom/acc grammar. The problem is exponential blowup: handling one roughly doubled the size of the grammar, handling the other doubles it again. In general, for every agreement-like phenomenon we want to handle, we'll double the size of our grammar again. This is bad (a) because it makes our grammar huge and (b) because we'll need tons and tons and tons of data to get reliable estimates of these probabilities from a treebank!
(Other English phenomena you might want to capture are selectional preferences -- which are really more semantics issues than syntactic issues; or determiner/noun agreement.)
One solution to this problem is to augment our grammar with features. That is, basically do what linguists do and write "+sing" on the pre-terminal, but not split the grammar into bits. Instead, we need to come up with ways of propagating these features up the tree, and checking for disagreement. This process is known as "unification".
The idea of unification is that everything has a bunch of features with values. Values can be atomic (number=sing) or disjunctions (number={sing,plur}) or variables (number=A). Two values unify basically if they have a non-empty intersection (it's actually more complicated than this, but this is the basic idea). So sing and sing unify and produce sing. Similarly sing and {sing,plur} unify and produce sing. A and sing unify and produce sing with a note off on the side of the page that A=sing. sing and plur don't unify. Our grammar will now encode what unifications happen at each step (eg., when producing a S, you want to unify the number feature of the NP and VP; or when producing a VP, you want to unify the object NP with "case=accusative" and likewise for subject NPs).
Our grammar is now a set of context free productions and unification rules. One nice thing is that chart parsing basically still works, but our parse cells become more complicated because they have to remember the values of features. But at least our grammars don't blow up!
Suppose we want to capture this with a (P)CFG.... the only real way to do this is to expand our set of non-terminals. I.e., we might start with a grammar like:
S -> NP VP NP -> Pro NP -> Det Noun VP -> Verb NP Pro -> he Pro -> they Verb -> eat Verb -> eats Det -> a
Which will generate our good sentences, but also bad sentences like "He eat a sandwich" and "They eats a sandwich". We can fix this by adding labels to our non-terminals:
S -> NP+sing VP+sing S -> NP+plur VP+plur NP+sing -> Pro+sing NP+plur -> Pro+plur NP+sing -> Det Noun+sing NP+plur -> Det Noun+plur VP+sing -> Verb+sing NP VP+plur -> Verb+plur NP Pro+sing -> he Pro+plur -> they Verb+sing -> eats Verb+plur -> eat Det -> a
Now life is great: we will no longer produce our bogus sentences. (Note that we would also have to account for "a" being singular, etc...)
Of course there are other phenomena we might want to capture, for instance pronouns sitting in object position have to change case: "A sandwich eats him" not "A sandwich eats he". If we ignore the singular/plural distinction, we can solve this separately.
S -> NP+nom VP VP -> Verb NP+acc NP+nom -> Pro+nom NP+acc -> Pro+acc NP -> Det Noun Pro+nom -> he Pro+acc -> him Pro+nom -> they Pro+acc -> them
And so on...
We've now solve the nominative/accusative issue, so we can combine the sing/plur grammar with the nom/acc grammar. The problem is exponential blowup: handling one roughly doubled the size of the grammar, handling the other doubles it again. In general, for every agreement-like phenomenon we want to handle, we'll double the size of our grammar again. This is bad (a) because it makes our grammar huge and (b) because we'll need tons and tons and tons of data to get reliable estimates of these probabilities from a treebank!
(Other English phenomena you might want to capture are selectional preferences -- which are really more semantics issues than syntactic issues; or determiner/noun agreement.)
One solution to this problem is to augment our grammar with features. That is, basically do what linguists do and write "+sing" on the pre-terminal, but not split the grammar into bits. Instead, we need to come up with ways of propagating these features up the tree, and checking for disagreement. This process is known as "unification".
The idea of unification is that everything has a bunch of features with values. Values can be atomic (number=sing) or disjunctions (number={sing,plur}) or variables (number=A). Two values unify basically if they have a non-empty intersection (it's actually more complicated than this, but this is the basic idea). So sing and sing unify and produce sing. Similarly sing and {sing,plur} unify and produce sing. A and sing unify and produce sing with a note off on the side of the page that A=sing. sing and plur don't unify. Our grammar will now encode what unifications happen at each step (eg., when producing a S, you want to unify the number feature of the NP and VP; or when producing a VP, you want to unify the object NP with "case=accusative" and likewise for subject NPs).
Our grammar is now a set of context free productions and unification rules. One nice thing is that chart parsing basically still works, but our parse cells become more complicated because they have to remember the values of features. But at least our grammars don't blow up!
07 October 2010
Lecture 10: Statistical Parsing
Context free grammars are great, but as with any X, if X is great, then probabilistic X is greater still!
A probabilistic context free grammar (PCFG) is a CFG with "weights" attached to each of the rules. These weights must be non-negative. For any left-hand-side, the sum of weights must be one. The following is a small PCFG:
Note that for any given LHS (eg., "NP") the sum of weights (probabilities) is one.
The probability of a tree is just the product of probabilities of rules used in that tree.
We can generate random sentences with a PCFG by starting at "S" and then picking a rule at random (weighted by the probabilities) and then recursively generating the corresponding children.
The probability of a sentence under this grammar is obtained by summing (marginalizing) out all the trees that can generate that sentence.
To parse with a PCFG, we just parse with the corresponding CFG, but then weigh items in the chart by their probabilities. If we find a higher-probability derivation of the same item in the chart, we throw out the old one and replace it with the new one. In CKY this is easy.
A treebank is a collection of human-labeled trees. Given a treebank, we can extract the corresponding PCFG by counting productions and normalizing. Most trees are not binary so you need to binarize your rules.
Note on smoothing: you have to smooth if you want your grammar to be able to parse out-of-sample trees. Smoothing can be done just like in HMMs, but you want to be careful not to compute stuff that is irrelevant.
Note on efficiency: The grammars we produce are huge (tens or hundreds of thousands of rules). As a result, paying O(N^3|G|) is often prohibitive, even for N around 30 or 40. A simple solution is pruning: after you process each cell in the chart, throw out it's low probability items. You can either do count-based pruning (only keep the top 5 in each cell), ratio-based pruning (only keep the ones within a factor of 10 probability of the best one), or probability-based pruning (only keep the ones with probability at least 10e-6). Usually the last sucks, but the first two work reasonably well.
A probabilistic context free grammar (PCFG) is a CFG with "weights" attached to each of the rules. These weights must be non-negative. For any left-hand-side, the sum of weights must be one. The following is a small PCFG:
S 0.5 -> NP VP S 0.5 -> VP NP 0.7 -> Det Noun NP 0.2 -> Proper NP 0.1 -> NP PP VP 0.6 -> Verb NP VP 0.3 -> Verb VP 0.1 -> VP PP
Note that for any given LHS (eg., "NP") the sum of weights (probabilities) is one.
The probability of a tree is just the product of probabilities of rules used in that tree.
We can generate random sentences with a PCFG by starting at "S" and then picking a rule at random (weighted by the probabilities) and then recursively generating the corresponding children.
The probability of a sentence under this grammar is obtained by summing (marginalizing) out all the trees that can generate that sentence.
To parse with a PCFG, we just parse with the corresponding CFG, but then weigh items in the chart by their probabilities. If we find a higher-probability derivation of the same item in the chart, we throw out the old one and replace it with the new one. In CKY this is easy.
A treebank is a collection of human-labeled trees. Given a treebank, we can extract the corresponding PCFG by counting productions and normalizing. Most trees are not binary so you need to binarize your rules.
Note on smoothing: you have to smooth if you want your grammar to be able to parse out-of-sample trees. Smoothing can be done just like in HMMs, but you want to be careful not to compute stuff that is irrelevant.
Note on efficiency: The grammars we produce are huge (tens or hundreds of thousands of rules). As a result, paying O(N^3|G|) is often prohibitive, even for N around 30 or 40. A simple solution is pruning: after you process each cell in the chart, throw out it's low probability items. You can either do count-based pruning (only keep the top 5 in each cell), ratio-based pruning (only keep the ones within a factor of 10 probability of the best one), or probability-based pruning (only keep the ones with probability at least 10e-6). Usually the last sucks, but the first two work reasonably well.
04 October 2010
No class Tue 05 Oct 2010
Due to Hal being sick again. Sigh.
So here's a puzzle to entertain you while you're not learning all about treebanking and PCFGs....
Suppose Hal presents symptoms that make it 90% certain that he has some illness X. And suppose that the rate of transmission of X is 5%. Suppose that the average rate of incidence of X in a general population is 0.01%. What is the probability that you would get sick if we had class tomorrow (and you showed up)? There are 45 students in class: what's the probability that at least one would get sick? Finally, suppose that your utility function is defined as U(learn about pcfgs and don't get sick) = +10, U(don't learn and don't get sick) = 0, U(learn and get sick) = -20, U(don't learn and get sick) = -100. (How annoying would that be.) What is the expected utility if I do teach class? What is the expected utility if I cancel class? Am I doing the right thing?
Feel free to post solutions :).
So here's a puzzle to entertain you while you're not learning all about treebanking and PCFGs....
Suppose Hal presents symptoms that make it 90% certain that he has some illness X. And suppose that the rate of transmission of X is 5%. Suppose that the average rate of incidence of X in a general population is 0.01%. What is the probability that you would get sick if we had class tomorrow (and you showed up)? There are 45 students in class: what's the probability that at least one would get sick? Finally, suppose that your utility function is defined as U(learn about pcfgs and don't get sick) = +10, U(don't learn and don't get sick) = 0, U(learn and get sick) = -20, U(don't learn and get sick) = -100. (How annoying would that be.) What is the expected utility if I do teach class? What is the expected utility if I cancel class? Am I doing the right thing?
Feel free to post solutions :).
01 October 2010
Projec 2 is posted, due Oct 19
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!
Subscribe to:
Posts (Atom)