added ccm.py
[dmvccm.git] / DMVCCM.org.~10~
blob362417fa71f43cd5c914c24ba40f1acd80dc62ca
1 # -*- coding: mule-utf-8-unix -*-
2 #+STARTUP: overview
3 #+TAGS: OPTIMIZE PRETTIER
4 #+STARTUP: hidestars
5 #+TITLE: DMV/CCM
6 #+AUTHOR: Kevin Brubeck Unhammer
7 #+EMAIL: K.BrubeckUnhammer at student uva nl 
8 #+LANGUAGE: en
9 #+SEQ_TODO: TOGROK TODO DONE
10 #+OPTIONS: H:4 toc:3
12 * dmvccm
13   DEADLINE: <2008-06-30 Mon>
14 (But absolute, extended, really-quite-dead-now deadline: August 31...)
15 [[file:src/dmv.py][dmv.py]]
16 [[file:src/io.py][io.py]]
17 ** TODO Adjacency and combining it with inner()
18 Each DMV_Rule now has both a probN and a probA, for
19 adjacencies. inner() needs the correct one in each case.
21 Adjacency gives a problem with duplicate words/tags, eg. in the
22 sentence "a a b". If this has the dependency structure b->a_0->a_1,
23 then b is non-adjacent to a_0 and should use probN (for the LRStop and
24 the attachment of a_0), while the other rules should all use
25 probA. But within the e(0,2,b) we can't just say "oh, a has index 0
26 so it's not adjacent to 2", since there's also an a at index 1, and
27 there's also a dependency structure b->a_1->a_0 for that. We want
28 both. And in possibly much more complex versions.
30 Ideas:
31 - I first thought of decorating the individual words/tags in a
32   sentence with their indices, and perhaps just duplicating the
33   relevant rules (one for each index of the duplicate tags). But this
34   gives an explosion in attachment rules (although a contained
35   explosion, within the rules used in a sentence; but most sentences
36   will have at least two NN's so it will be a problem).
37 - Then, I had a /brilliant/ idea. Just let e(), the helper function of
38   inner(), parametrize for an extra pair of boolean values for whether
39   or not we've attached anything to the left or right yet. So now, e()
40   has a chart of the form [s, t, LHS, Lattach, Rattach], and of course
41   e(s,t,LHS) is the sum of the four possible values for
42   (Lattach,Rattach). This makes e() lots more complex and DMV-specific
43   though, so it's been rewritten in inner_dmv() in dmv.py.
44 *** TODO document this adjacency stuff better
45 *** TODO test and debug my brilliant idea
46 *** DONE implement my brilliant idea.
47     CLOSED: [2008-06-01 Sun 17:19]
48 [[file:src/dmv.py::def%20e%20s%20t%20LHS%20Lattach%20Rattach][e(sti) in dmv.py]]
50 *** DONE [#A] test inner() on sentences with duplicate words
51 Works with eg. the sentence "h h h"
54 ** TODO [#A] P_STOP for IO/EM
55 [[file:src/dmv.py::DMV%20probabilities][dmv-P_STOP]]
56 Remember: The P_STOP formula is upside-down (left-to-right also).
57 (In the article..not the thesis)
59 Remember: Initialization makes some "short-cut" rules, these will also
60 have to be updated along with the other P_STOP updates:
61 - b[(NOBAR, n_h), 'h'] = 1.0       # always
62 - b[(RBAR, n_h), 'h'] = h_ .probA  # h_ is RBAR stop rule
63 - b[(LRBAR, n_h), 'h'] = h_ .probA * _ h_ .probA
65 *** How is the P_STOP formula different given other values for dir and adj?
66 (Presumably, the P_STOP formula where STOP is True is just the
67 rule-probability of _h_ -> STOP h_ or h_ -> h STOP, but how does
68 adjacency fit in here?)
70 (And P_STOP(-STOP|...) = 1 - P_STOP(STOP|...) )
71 ** TODO P_CHOOSE for IO/EM
72 Write the formulas! should be easy?
73 ** Initialization   
74 [[file:~/Documents/Skole/V08/Probability/dmvccm/src/dmv.py::Initialization%20todo][dmv-inits]]
76 We do have to go through the corpus, since the probabilities are based
77 on how far away in the sentence arguments are from their heads.
78 *** TODO Separate initialization to another file?                     :PRETTIER:
79 (It's rather messy.)
80 *** TOGROK CCM Initialization    
81 P_SPLIT used here... how, again?
82 *** DONE DMV Initialization probabilities
83 (from initialization frequency)
84 *** DONE DMV Initialization frequencies    
85     CLOSED: [2008-05-27 Tue 20:04]
86 **** P_STOP    
87 P_STOP is not well defined by K&M. One possible interpretation given
88 the sentence [det nn vb nn] is
89 - f_STOP( STOP|det, L, adj) +1
90 - f_STOP(-STOP|det, L, adj) +0  
91 - f_STOP( STOP|det, L, non_adj) +1
92 - f_STOP(-STOP|det, L, non_adj) +0
93 - f_STOP( STOP|det, R, adj) +0
94 - f_STOP(-STOP|det, R, adj) +1
96 - f_STOP( STOP|nn, L, adj) +0
97 - f_STOP(-STOP|nn, L, adj) +1
98 - f_STOP( STOP|nn, L, non_adj) +1  # since there's at least one to the left
99 - f_STOP(-STOP|nn, L, non_adj) +0
101 **** P_CHOOSE
102 Go through the corpus, counting distances between heads and
103 arguments. In [det nn vb nn], we give 
104 - f_CHOOSE(nn|det, R) +1/1 + C
105 - f_CHOOSE(vb|det, R) +1/2 + C
106 - f_CHOOSE(nn|det, R) +1/3 + C
107   - If this were the full corpus, P_CHOOSE(nn|det, R) would have
108     (1+1/3+2C) / sum_a f_CHOOSE(a|det, R)
110 The ROOT gets "each argument with equal probability", so in a sentence
111 of three words, 1/3 for each (in [nn vb nn], 'nn' gets 2/3). Basically
112 just a frequency count of the corpus...
113 ** [#C] Deferred
114 *** TODO when reestimating P_STOP etc, remove rules with p < epsilon  :OPTIMIZE:
115 *** TODO inner_dmv, short ranges and impossible attachment            :OPTIMIZE:
116 If s-t <= 2, there can be only one attachment below, so don't recurse
117 with both Lattach=True and Rattach=True.
119 If s-t <= 1, there can be no attachment below, so only recurse with
120 Lattach=False, Rattach=False.
122 Put this in the loop under rewrite rules (could also do it in the STOP
123 section, but that would only have an effect on very short sentences).
124 *** TOGROK Some (tagged) sentences are bound to come twice            :OPTIMIZE:
125 Eg, first sort and count, so that the corpus
126 [['nn','vbd','det','nn'],
127  ['vbd','nn','det','nn'],
128  ['nn','vbd','det','nn']]
129 becomes
130 [(['nn','vbd','det','nn'],2),
131  (['vbd','nn','det','nn'],1)]
132 and then in each loop through sentences, make sure we handle the
133 frequency correctly.
134           
135 Is there much to gain here?
137 *** TOGROK tags as numbers or tags as strings?                        :OPTIMIZE:
138 Need to clean up the representation.
140 Stick with tag-strings in initialization then switch to numbers for
141 IO-algorithm perhaps? Can probably afford more string-matching in
142 initialization..
143 *** TOGROK Is the E-step in DMV just inner() on the full sentence? 
144 and What exactly is the M-step of DMV? 
145 *** COMMENT 
146 E: «For the initial symbols, I think we're supposed to
147 implement someone-or-other's POS tagger and use the parts of speech as
148 our tags. (K&M say they used parts of speech, anyway, and we can't use
149 the ones from the annotated corpus or else we won't be unsupervised
150 anymore.) I think you're right about how the tree is formed. The only
151 thing I'm not sure about is whether those left and right marks are
152 supposed to be part of the tree. I guess not because in a well-formed
153 tree, every word needs a stop on both sides, so actually all nodes
154 would be left and right marked in the end, which is the same as not
155 using them at all. So I guess they're relevant in the E step of EM,
156 but not the M step.» [[https://mail.google.com/mail/%3Ffs%3D1&tf%3D1&source%3Datom&view%3Dcv&search%3Dall&th%3D119b3e3d7d8f1d1f&shva%3D1&ui%3D1&disablechatbrowsercheck%3D1][gmail]]
158 K: About initialization, when they say they start with an M-step and get
159 a harmonic distribution (where close dependencies have higher
160 probabilities than far-away ones), I guess we could do this either in
161 a function of its own, or as a special case of the IO-algorithm -- I'm
162 not sure how different the harmonizing step will be from the regular
163 M-step. But I'm pretty sure harmonizing means having to go through the
164 whole corpus, since that's the only way we can find out distances for
165 each dependency (without having actual distance-numbers in the rules
166 in the first place). If sentence s is ABCD, rules from A to B should
167 have higher probability than rules from A to D. Assuming we find some
168 average distance between A and B, and A and D, etc. throughout the
169 corpus, we then have to turn those numbers into probabilities that sum
170 to 1; do you have any idea how to do that?
172 E: I think what it means to start with an M step is that we set the
173 probabilities without regard for the initial corpus. They say that
174 they start with an initial guess at "posterior distributions". I bet
175 the word "posterior" is important, but I don't know what it means
176 here. Do you?
177 *** TODO Corpus access
178 *** TOGROK sentences or rules as the "outer loop"?                    :OPTIMIZE:
179 In regard to the E/M-step, finding P_STOP, P_CHOOSE.
182 * Python-stuff
183 - [[file:src/pseudo.py][pseudo.py]]
184 - http://nltk.org/doc/en/structured-programming.html recursive dynamic
185 - http://nltk.org/doc/en/advanced-parsing.html 
186 - http://jaynes.colorado.edu/PythonIdioms.html