started on pure cnf version, see sec6 of formulas.pdf
[dmvccm.git] / DMVCCM.org.~14~
blobe30cc76a863cfc813915e1b85dc751a7e65d00dc
1 # -*- coding: mule-utf-8-unix -*-
2 #+OPTIONS: ^:{} H:4 toc:3
3 #+STARTUP: overview
4 #+TAGS: OPTIMIZE PRETTIER
5 #+STARTUP: hidestars
6 #+TITLE: DMV/CCM -- todo-list / progress
7 #+AUTHOR: Kevin Brubeck Unhammer
8 #+EMAIL: K.BrubeckUnhammer at student uva nl 
9 #+LANGUAGE: en
10 #+SEQ_TODO: TOGROK TODO DONE
13 * dmvccm report and project
14   DEADLINE: <2008-06-30 Mon>
15 But absolute, extended, really-quite-dead-now deadline: August
16 31... 
17 - [[file:src/dmv.py][dmv.py]]
18 - [[file:src/io.py][io.py]]
19 - [[file:src/harmonic.py::harmonic%20py%20initialization%20for%20dmv][harmonic.py]]
20 * TODO Adjacency and combining it with inner()
21 Each DMV_Rule now has both a probN and a probA, for
22 adjacencies. inner() needs the correct one in each case.
24 Adjacency gives a problem with duplicate words/tags, eg. in the
25 sentence "a a b". If this has the dependency structure b->a_{0}->a_{1},
26 then b is non-adjacent to a_{0} and should use probN (for the LRStop and
27 the attachment of a_{0}), while the other rules should all use
28 probA. But within the e(0,2,b) we can't just say "oh, a has index 0
29 so it's not adjacent to 2", since there's also an a at index 1, and
30 there's also a dependency structure b->a_{1}->a_{0} for that. We want
31 both. And in possibly much more complex versions.
33 Ideas:
34 - I first thought of decorating the individual words/tags in a
35   sentence with their indices, and perhaps just duplicating the
36   relevant rules (one for each index of the duplicate tags). But this
37   gives an explosion in attachment rules (although a contained
38   explosion, within the rules used in a sentence; but most sentences
39   will have at least two NN's so it will be a problem).
40 - Then, I had a /brilliant/ idea. Just let e(), the helper function of
41   inner(), parametrize for an extra pair of boolean values for whether
42   or not we've attached anything to the left or right yet ("yet"
43   meaning "below"). So now, e() has a chart of the form [s, t, LHS,
44   Lattach, Rattach], and of course e(s,t,LHS) is the sum of the four
45   possible values for (Lattach,Rattach). This makes e() lots more
46   complex and DMV-specific though, so it's been rewritten in
47   inner_dmv() in dmv.py.
48 ** TODO document this adjacency stuff better
49 ** TODO test and debug my brilliant idea
50 ** DONE implement my brilliant idea.
51     CLOSED: [2008-06-01 Sun 17:19]
52 [[file:src/dmv.py::def%20e%20s%20t%20LHS%20Lattach%20Rattach][e(sti) in dmv.py]]
54 ** DONE [#A] test inner() on sentences with duplicate words
55 Works with eg. the sentence "h h h"
58 * TODO [#A] P_STOP for IO/EM
59 [[file:src/dmv.py::DMV%20probabilities][dmv-P_STOP]]
60 Remember: The P_{STOP} formula is upside-down (left-to-right also).
61 (In the article..not the thesis)
63 Remember: Initialization makes some "short-cut" rules, these will also
64 have to be updated along with the other P_{STOP} updates:
65 - b[(NOBAR, n_{h}), 'h'] = 1.0       # always
66 - b[(RBAR, n_{h}), 'h'] = h_.probA  # h_ is RBAR stop rule
67 - b[(LRBAR, n_{h}), 'h'] = h_.probA * _ h_.probA
69 ** How is the P_STOP formula different given other values for dir and adj?
70 (Presumably, the P_{STOP} formula where STOP is True is just the
71 rule-probability of _ h_ -> STOP h_ or h_ -> h STOP, but how does
72 adjacency fit in here?)
74 (And P_{STOP}(-STOP|...) = 1 - P_{STOP}(STOP|...) )
75 * TODO P_CHOOSE for IO/EM
76 Write the formulas! should be easy?
77 * Initialization   
78 [[file:~/Documents/Skole/V08/Probability/dmvccm/src/dmv.py::Initialization%20todo][dmv-inits]]
80 We do have to go through the corpus, since the probabilities are based
81 on how far away in the sentence arguments are from their heads.
82 ** TODO Separate initialization to another file?                      :PRETTIER:
83 (It's rather messy.)
84 ** TOGROK CCM Initialization    
85 P_{SPLIT} used here... how, again?
86 ** DONE DMV Initialization probabilities
87 (from initialization frequency)
88 ** DONE DMV Initialization frequencies    
89    CLOSED: [2008-05-27 Tue 20:04]
90 *** P_STOP    
91 P_{STOP} is not well defined by K&M. One possible interpretation given
92 the sentence [det nn vb nn] is
93 : f_{STOP}( STOP|det, L, adj) +1
94 : f_{STOP}(-STOP|det, L, adj) +0  
95 : f_{STOP}( STOP|det, L, non_adj) +1
96 : f_{STOP}(-STOP|det, L, non_adj) +0
97 : f_{STOP}( STOP|det, R, adj) +0
98 : f_{STOP}(-STOP|det, R, adj) +1
100 : f_{STOP}( STOP|nn, L, adj) +0
101 : f_{STOP}(-STOP|nn, L, adj) +1
102 : f_{STOP}( STOP|nn, L, non_adj) +1  # since there's at least one to the left
103 : f_{STOP}(-STOP|nn, L, non_adj) +0
104 **** TODO tweak
105 # <<pstoptweak>>
106 :            f[head,  'STOP', 'LN'] += (i_h <= 1)     # first two words
107 :            f[head, '-STOP', 'LN'] += (not i_h <= 1)     
108 :            f[head,  'STOP', 'LA'] += (i_h == 0)     # very first word
109 :            f[head, '-STOP', 'LA'] += (not i_h == 0)     
110 :            f[head,  'STOP', 'RN'] += (i_h >= n - 2) # last two words
111 :            f[head, '-STOP', 'RN'] += (not i_h >= n - 2) 
112 :            f[head,  'STOP', 'RA'] += (i_h == n - 1) # very last word
113 :            f[head, '-STOP', 'RA'] += (not i_h == n - 1) 
115 :            # this one requires some additional rewriting since it
116 :            # introduces divisions by zero
117 :            f[head,  'STOP', 'LN'] += (i_h == 1)     # second word
118 :            f[head, '-STOP', 'LN'] += (not i_h <= 1) # not first two
119 :            f[head,  'STOP', 'LA'] += (i_h == 0)     # first word
120 :            f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
121 :            f[head,  'STOP', 'RN'] += (i_h == n - 2)     # second-to-last
122 :            f[head, '-STOP', 'RN'] += (not i_h >= n - 2) # not last two
123 :            f[head,  'STOP', 'RA'] += (i_h == n - 1)     # last word
124 :            f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
126 :            f[head,  'STOP', 'LN'] += (i_h == 1)     # second word
127 :            f[head, '-STOP', 'LN'] += (not i_h == 1) # not second
128 :            f[head,  'STOP', 'LA'] += (i_h == 0)     # first word
129 :            f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
130 :            f[head,  'STOP', 'RN'] += (i_h == n - 2)     # second-to-last
131 :            f[head, '-STOP', 'RN'] += (not i_h == n - 2) # not second-to-last
132 :            f[head,  'STOP', 'RA'] += (i_h == n - 1)     # last word
133 :            f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
134 vs 
135 "all words take the same number of arguments" interpreted as
136 :for all heads:
137 :    p_STOP(head, 'STOP', 'LN') = 0.3
138 :    p_STOP(head, 'STOP', 'LA') = 0.5
139 :    p_STOP(head, 'STOP', 'RN') = 0.4
140 :    p_STOP(head, 'STOP', 'RA') = 0.7
141 (which we easily may tweak in init_zeros())
142 *** P_CHOOSE
143 Go through the corpus, counting distances between heads and
144 arguments. In [det nn vb nn], we give 
145 - f_{CHOOSE}(nn|det, R) +1/1 + C
146 - f_{CHOOSE}(vb|det, R) +1/2 + C
147 - f_{CHOOSE}(nn|det, R) +1/3 + C
148   - If this were the full corpus, P_{CHOOSE}(nn|det, R) would have
149     (1+1/3+2C) / sum_a f_{CHOOSE}(a|det, R)
151 The ROOT gets "each argument with equal probability", so in a sentence
152 of three words, 1/3 for each (in [nn vb nn], 'nn' gets 2/3). Basically
153 just a frequency count of the corpus...
154 * [#C] Deferred
155 ** TODO inner_dmv() should disregard rules with heads not in sent     :OPTIMIZE:
156 If the sentence is "nn vbd det nn", we should not even look at rules
157 where
158 : rule.head() not in "nn vbd det nn".split()
159 This is ruled out by getting rules from g.rules(LHS, sent).
161 Also, we optimize this further by saying we don't even recurse into
162 attachment rules where
163 : rule.head() not in sent[ s :r+1]
164 : rule.head() not in sent[r+1:t+1]
165 meaning, if we're looking at the span "vbd det", we only use
166 attachment rules where both daughters are members of ['vbd','det']
167 (although we don't (yet) care about removing rules that rewrite to the
168 same tag if there are no duplicate tags in the span, etc., that would
169 be a lot of trouble for little potential gain).
170 ** TODO when reestimating P_STOP etc, remove rules with p < epsilon   :OPTIMIZE:
171 ** TODO inner_dmv, short ranges and impossible attachment             :OPTIMIZE:
172 If s-t <= 2, there can be only one attachment below, so don't recurse
173 with both Lattach=True and Rattach=True.
175 If s-t <= 1, there can be no attachment below, so only recurse with
176 Lattach=False, Rattach=False.
178 Put this in the loop under rewrite rules (could also do it in the STOP
179 section, but that would only have an effect on very short sentences).
180 ** TODO clean up the module files                                     :PRETTIER:
181 Is there better way to divide dmv and harmonic? There's a two-way
182 dependency between the modules. Guess there could be a third file that
183 imports both the initialization and the actual EM stuff, while a file
184 containing constants and classes could be imported by all others:
185 : dmv.py imports dmv_EM.py imports dmv_classes.py
186 : dmv.py imports dmv_inits.py imports dmv_classes.py
188 ** TOGROK Some (tagged) sentences are bound to come twice             :OPTIMIZE:
189 Eg, first sort and count, so that the corpus
190 [['nn','vbd','det','nn'],
191  ['vbd','nn','det','nn'],
192  ['nn','vbd','det','nn']]
193 becomes
194 [(['nn','vbd','det','nn'],2),
195  (['vbd','nn','det','nn'],1)]
196 and then in each loop through sentences, make sure we handle the
197 frequency correctly.
198           
199 Is there much to gain here?
201 ** TOGROK tags as numbers or tags as strings?                         :OPTIMIZE:
202 Need to clean up the representation.
204 Stick with tag-strings in initialization then switch to numbers for
205 IO-algorithm perhaps? Can probably afford more string-matching in
206 initialization..
207 * Expectation Maximation in IO/DMV-terms
208 inner(s,t,LHS) calculates the expected number of trees headed by LHS
209 from s to t (sentence positions). This uses the P_STOP and P_CHOOSE
210 values, which have been conveniently distributed into CNF rules as
211 probN and probA (non-adjacent and adjacent probabilites).
213 When re-estimating, we use the expected values from inner() to get new
214 values for P_STOP and P_CHOOSE. When we've re-estimated for the entire
215 corpus, we distribute P_STOP and P_CHOOSE into the CNF rules again, so
216 that in the next round we use new probN and probA to find
217 inner-probabilites.
219 The distribution of P_STOP and P_CHOOSE into CNF rules also happens in
220 init_normalize() (here along with the creation of P_STOP and
221 P_CHOOSE); P_STOP is used to create CNF rules where one branch of the
222 rule is STOP, P_CHOOSE is used to create rules of the form 
223 : h  -> h  _a_
224 : h_ -> h_ _a_
226 Since "adjacency" is not captured in regular CNF rules, we need two
227 probabilites for each rule, and inner() has to know when to use which.
229 ** TODO Corpus access
230 ** TOGROK sentences or rules as the "outer loop"?                     :OPTIMIZE:
231 In regard to the E/M-step, finding P_{STOP}, P_{CHOOSE}.
234 * Python-stuff
235 - [[file:src/pseudo.py][pseudo.py]]
236 - http://nltk.org/doc/en/structured-programming.html recursive dynamic
237 - http://nltk.org/doc/en/advanced-parsing.html 
238 - http://jaynes.colorado.edu/PythonIdioms.html