Ok, so I misunderstood the word adjacent all along. Redone now.
[dmvccm.git] / DMVCCM.html
blob32b59843c3a0104a9c8fdd984902dc621637726b
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
3 <html xmlns="http://www.w3.org/1999/xhtml"
4 lang="en" xml:lang="en">
5 <head>
6 <title>DMV/CCM &ndash; todo-list / progress</title>
7 <meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
8 <meta name="generator" content="Org-mode"/>
9 <meta name="generated" content="2008/06/06 19:12:56"/>
10 <meta name="author" content="Kevin Brubeck Unhammer"/>
11 <link rel="stylesheet" type="text/css" href="http://www.student.uib.no/~kun041/org.css">
12 </head><body>
13 <h1 class="title">DMV/CCM &ndash; todo-list / progress</h1>
16 <div id="table-of-contents">
17 <h2>Table of Contents</h2>
18 <div id="text-table-of-contents">
19 <ul>
20 <li><a href="#sec-1">1 dmvccm report and project</a></li>
21 <li><a href="#sec-2">2 Adjacency and combining it with inner()</a></li>
22 <li><a href="#sec-3">3 [#A] P_STOP for IO/EM</a></li>
23 <li><a href="#sec-4">4 P_CHOOSE for IO/EM</a></li>
24 <li><a href="#sec-5">5 Initialization </a></li>
25 <li><a href="#sec-6">6 [#C] Deferred</a></li>
26 <li><a href="#sec-7">7 Expectation Maximation in IO/DMV-terms</a></li>
27 <li><a href="#sec-8">8 Python-stuff</a></li>
28 <li><a href="#sec-9">9 Git</a></li>
29 </ul>
30 </div>
31 </div>
33 <div id="outline-container-1" class="outline-2">
34 <h2 id="sec-1">1 dmvccm report and project</h2>
35 <div id="text-1">
37 <p><span class="timestamp-kwd">DEADLINE: </span> <span class="timestamp">2008-06-30 Mon</span><br/>
38 But absolute, extended, really-quite-dead-now deadline: August
39 31&hellip;
40 </p><ul>
41 <li>
42 <a href="src/dmv.py">dmv.py</a>
43 </li>
44 <li>
45 <a href="src/io.py">io.py</a>
46 </li>
47 <li>
48 <a href="src/harmonic.py">harmonic.py</a>
49 </li>
50 </ul>
51 </div>
53 </div>
55 <div id="outline-container-2" class="outline-2">
56 <h2 id="sec-2">2 <span class="todo">TODO</span> Adjacency and combining it with inner()</h2>
57 <div id="text-2">
59 <p>Each DMV_Rule now has both a probN and a probA, for
60 adjacencies. inner() needs the correct one in each case.
61 </p>
62 <p>
63 Adjacency gives a problem with duplicate words/tags, eg. in the
64 sentence "a a b". If this has the dependency structure b-&gt;a<sub>0</sub>-&gt;a<sub>1</sub>,
65 then b is non-adjacent to a<sub>0</sub> and should use probN (for the LRStop and
66 the attachment of a<sub>0</sub>), while the other rules should all use
67 probA. But within the e(0,2,b) we can't just say "oh, a has index 0
68 so it's not adjacent to 2", since there's also an a at index 1, and
69 there's also a dependency structure b-&gt;a<sub>1</sub>-&gt;a<sub>0</sub> for that. We want
70 both. And in possibly much more complex versions.
71 </p>
72 <p>
73 Ideas:
74 </p><ul>
75 <li>
76 I first thought of decorating the individual words/tags in a
77 sentence with their indices, and perhaps just duplicating the
78 relevant rules (one for each index of the duplicate tags). But this
79 gives an explosion in attachment rules (although a contained
80 explosion, within the rules used in a sentence; but most sentences
81 will have at least two NN's so it will be a problem).
82 </li>
83 <li>
84 Then, I had a <i>brilliant</i> idea. Just let e(), the helper function of
85 inner(), parametrize for an extra pair of boolean values for whether
86 or not we've attached anything to the left or right yet ("yet"
87 meaning "below"). So now, e() has a chart of the form [s, t, LHS,
88 Lattach, Rattach], and of course e(s,t,LHS) is the sum of the four
89 possible values for (Lattach,Rattach). This makes e() lots more
90 complex and DMV-specific though, so it's been rewritten in
91 inner_dmv() in dmv.py.
92 </li>
93 <li>
94 But, the problem is that we still need to be able get inner
95 probabilites for only trees where the h at location loc_h is the
96 root of the dependency. The previous idea does not give that. So I
97 made <i>another</i> version of inner() that parametrizes for loc_h in the
98 chart (instead of Lattach and Rattach). loc_h also lets us check
99 whether we need probN or probA, in a much simpler fashion than the
100 Lattach / Rattach version.
101 </li>
102 <li id="sec-2.1"><span class="todo">TODO</span> document this adjacency stuff better<br/>
103 </li>
104 <li id="sec-2.2"><span class="todo">TODO</span> [#A] test and debug my brilliant idea<br/>
105 <ul>
106 <li id="sec-2.2.1">Works on simple 'h h' sentence, but not with P_STOP, why?<br/>
107 </li>
108 </ul>
109 </li>
110 <li id="sec-2.3"><span class="done">DONE</span> implement my brilliant idea.<br/>
111 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-01 Sun 17:19</span><br/>
112 <a href="src/dmv.py">e(sti) in dmv.py</a>
114 </li>
115 <li id="sec-2.4"><span class="done">DONE</span> [#A] test inner() on sentences with duplicate words<br/>
116 Works with eg. the sentence "h h h"
119 </li>
120 </ul>
121 </div>
123 </div>
125 <div id="outline-container-3" class="outline-2">
126 <h2 id="sec-3">3 <span class="todo">TODO</span> [#A] P_STOP for IO/EM</h2>
127 <div id="text-3">
129 <p><a href="src/dmv.py">dmv-P_STOP</a>
130 Remember: The P<sub>STOP</sub> formula is upside-down (left-to-right also).
131 (In the article..not the thesis)
132 </p>
134 Remember: Initialization makes some "short-cut" rules, these will also
135 have to be updated along with the other P<sub>STOP</sub> updates:
136 </p><ul>
137 <li>
138 b[(NOBAR, n<sub>h</sub>), 'h'] = 1.0 # always
139 </li>
140 <li>
141 b[(RBAR, n<sub>h</sub>), 'h'] = h_.probA # h_ is RBAR stop rule
142 </li>
143 <li>
144 b[(LRBAR, n<sub>h</sub>), 'h'] = h_.probA * _ h_.probA
146 </li>
147 <li id="sec-3.1">How is the P_STOP formula different given other values for dir and adj?<br/>
148 Assuming this:
149 <ul>
150 <li>
151 P<sub>STOP</sub>(STOP|h,L,non_adj) = &sum;<sub>corpus</sub> &sum;<sub>s&lt;loc(h)</sub> &sum;<sub>t</sub>
152 inner(s,t,(LRBAR,h)&hellip;) / &sum;<sub>corpus</sub> &sum;<sub>s&lt;loc(h)</sub> &sum;<sub>t</sub> inner(s,t,(RBAR,h)&hellip;)
153 </li>
154 <li>
155 P<sub>STOP</sub>(STOP|h,L,adj) = &sum;<sub>corpus</sub> &sum;<sub>s=loc(h)</sub> &sum;<sub>t</sub>
156 inner(s,t,(LRBAR,h)&hellip;) / &sum;<sub>corpus</sub> &sum;<sub>s=loc(h)</sub> &sum;<sub>t</sub> inner(s,t,(RBAR,h)&hellip;)
157 </li>
158 <li>
159 P<sub>STOP</sub>(STOP|h,R,non_adj) = &sum;<sub>corpus</sub> &sum;<sub>s</sub> &sum;<sub>t&gt;loc(h)</sub>
160 inner(s,t,(LRBAR,h)&hellip;) / &sum;<sub>corpus</sub> &sum;<sub>s</sub> &sum;<sub>t&gt;loc(h)</sub> inner(s,t,(RBAR,h)&hellip;)
161 </li>
162 <li>
163 P<sub>STOP</sub>(STOP|h,R,adj) = &sum;<sub>corpus</sub> &sum;<sub>s</sub> &sum;<sub>t=loc(h)</sub>
164 inner(s,t,(LRBAR,h)&hellip;) / &sum;<sub>corpus</sub> &sum;<sub>s</sub> &sum;<sub>t=loc(h)</sub> inner(s,t,(RBAR,h)&hellip;)
168 </li>
169 </ul>
171 <p>(And P<sub>STOP</sub>(-STOP|&hellip;) = 1 - P<sub>STOP</sub>(STOP|&hellip;) )
172 </p></li>
173 </ul>
174 </div>
176 </div>
178 <div id="outline-container-4" class="outline-2">
179 <h2 id="sec-4">4 <span class="todo">TODO</span> P_CHOOSE for IO/EM</h2>
180 <div id="text-4">
182 <p>Write the formulas! should be easy?
183 </p></div>
185 </div>
187 <div id="outline-container-5" class="outline-2">
188 <h2 id="sec-5">5 Initialization </h2>
189 <div id="text-5">
191 <p><a href="/Users/kiwibird/Documents/Skole/V08/Probability/dmvccm/src/dmv.py">dmv-inits</a>
192 </p>
194 We do have to go through the corpus, since the probabilities are based
195 on how far away in the sentence arguments are from their heads.
196 </p><ul>
197 <li id="sec-5.1"><span class="todo">TODO</span> Separate initialization to another file? &nbsp;&nbsp;&nbsp;<span class="tag">PRETTIER</span><br/>
198 (It's rather messy.)
199 </li>
200 <li id="sec-5.2"><span class="todo">TOGROK</span> CCM Initialization <br/>
201 P<sub>SPLIT</sub> used here&hellip; how, again?
202 </li>
203 <li id="sec-5.3"><span class="done">DONE</span> DMV Initialization probabilities<br/>
204 (from initialization frequency)
205 </li>
206 <li id="sec-5.4"><span class="done">DONE</span> DMV Initialization frequencies <br/>
207 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-05-27 Tue 20:04</span><br/>
208 <ul>
209 <li id="sec-5.4.1">P_STOP <br/>
210 P<sub>STOP</sub> is not well defined by K&amp;M. One possible interpretation given
211 the sentence [det nn vb nn] is
212 <pre>
213 f_{STOP}( STOP|det, L, adj) +1
214 f_{STOP}(-STOP|det, L, adj) +0
215 f_{STOP}( STOP|det, L, non_adj) +1
216 f_{STOP}(-STOP|det, L, non_adj) +0
217 f_{STOP}( STOP|det, R, adj) +0
218 f_{STOP}(-STOP|det, R, adj) +1
220 f_{STOP}( STOP|nn, L, adj) +0
221 f_{STOP}(-STOP|nn, L, adj) +1
222 f_{STOP}( STOP|nn, L, non_adj) +1 # since there's at least one to the left
223 f_{STOP}(-STOP|nn, L, non_adj) +0
224 </pre>
225 <ul>
226 <li id="sec-5.4.1.1"><span class="todo">TODO</span> tweak<br/>
227 <pre>
228 f[head, 'STOP', 'LN'] += (i_h &lt;= 1) # first two words
229 f[head, '-STOP', 'LN'] += (not i_h &lt;= 1)
230 f[head, 'STOP', 'LA'] += (i_h == 0) # very first word
231 f[head, '-STOP', 'LA'] += (not i_h == 0)
232 f[head, 'STOP', 'RN'] += (i_h &gt;= n - 2) # last two words
233 f[head, '-STOP', 'RN'] += (not i_h &gt;= n - 2)
234 f[head, 'STOP', 'RA'] += (i_h == n - 1) # very last word
235 f[head, '-STOP', 'RA'] += (not i_h == n - 1)
236 </pre>
238 <pre>
239 # this one requires some additional rewriting since it
240 # introduces divisions by zero
241 f[head, 'STOP', 'LN'] += (i_h == 1) # second word
242 f[head, '-STOP', 'LN'] += (not i_h &lt;= 1) # not first two
243 f[head, 'STOP', 'LA'] += (i_h == 0) # first word
244 f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
245 f[head, 'STOP', 'RN'] += (i_h == n - 2) # second-to-last
246 f[head, '-STOP', 'RN'] += (not i_h &gt;= n - 2) # not last two
247 f[head, 'STOP', 'RA'] += (i_h == n - 1) # last word
248 f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
249 </pre>
251 <pre>
252 f[head, 'STOP', 'LN'] += (i_h == 1) # second word
253 f[head, '-STOP', 'LN'] += (not i_h == 1) # not second
254 f[head, 'STOP', 'LA'] += (i_h == 0) # first word
255 f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
256 f[head, 'STOP', 'RN'] += (i_h == n - 2) # second-to-last
257 f[head, '-STOP', 'RN'] += (not i_h == n - 2) # not second-to-last
258 f[head, 'STOP', 'RA'] += (i_h == n - 1) # last word
259 f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
260 </pre>
262 "all words take the same number of arguments" interpreted as
263 <pre>
264 for all heads:
265 p_STOP(head, 'STOP', 'LN') = 0.3
266 p_STOP(head, 'STOP', 'LA') = 0.5
267 p_STOP(head, 'STOP', 'RN') = 0.4
268 p_STOP(head, 'STOP', 'RA') = 0.7
269 </pre>
270 (which we easily may tweak in init_zeros())
271 </li>
272 </ul>
273 </li>
274 <li id="sec-5.4.2">P_CHOOSE<br/>
275 Go through the corpus, counting distances between heads and
276 arguments. In [det nn vb nn], we give
277 <ul>
278 <li>
279 f<sub>CHOOSE</sub>(nn|det, R) +1/1 + C
280 </li>
281 <li>
282 f<sub>CHOOSE</sub>(vb|det, R) +1/2 + C
283 </li>
284 <li>
285 f<sub>CHOOSE</sub>(nn|det, R) +1/3 + C
286 <ul>
287 <li>
288 If this were the full corpus, P<sub>CHOOSE</sub>(nn|det, R) would have
289 (1+1/3+2C) / sum_a f<sub>CHOOSE</sub>(a|det, R)
291 </li>
292 </ul>
293 </li>
294 </ul>
296 <p>The ROOT gets "each argument with equal probability", so in a sentence
297 of three words, 1/3 for each (in [nn vb nn], 'nn' gets 2/3). Basically
298 just a frequency count of the corpus&hellip;
299 </p></li>
300 </ul>
301 </li>
302 </ul>
303 </div>
305 </div>
307 <div id="outline-container-6" class="outline-2">
308 <h2 id="sec-6">6 [#C] Deferred</h2>
309 <div id="text-6">
311 <ul>
312 <li id="sec-6.1"><span class="todo">TODO</span> inner_dmv() should disregard rules with heads not in sent &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span><br/>
313 If the sentence is "nn vbd det nn", we should not even look at rules
314 where
315 <pre>
316 rule.head() not in "nn vbd det nn".split()
317 </pre>
318 This is ruled out by getting rules from g.rules(LHS, sent).
321 Also, we optimize this further by saying we don't even recurse into
322 attachment rules where
323 <pre>
324 rule.head() not in sent[ s :r+1]
325 rule.head() not in sent[r+1:t+1]
326 </pre>
327 meaning, if we're looking at the span "vbd det", we only use
328 attachment rules where both daughters are members of ['vbd','det']
329 (although we don't (yet) care about removing rules that rewrite to the
330 same tag if there are no duplicate tags in the span, etc., that would
331 be a lot of trouble for little potential gain).
332 </p></li>
333 <li id="sec-6.2"><span class="todo">TODO</span> when reestimating P_STOP etc, remove rules with p &lt; epsilon &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span><br/>
334 </li>
335 <li id="sec-6.3"><span class="todo">TODO</span> inner_dmv, short ranges and impossible attachment &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span><br/>
336 If s-t &lt;= 2, there can be only one attachment below, so don't recurse
337 with both Lattach=True and Rattach=True.
340 If s-t &lt;= 1, there can be no attachment below, so only recurse with
341 Lattach=False, Rattach=False.
342 </p>
344 Put this in the loop under rewrite rules (could also do it in the STOP
345 section, but that would only have an effect on very short sentences).
346 </p></li>
347 <li id="sec-6.4"><span class="todo">TODO</span> clean up the module files &nbsp;&nbsp;&nbsp;<span class="tag">PRETTIER</span><br/>
348 Is there better way to divide dmv and harmonic? There's a two-way
349 dependency between the modules. Guess there could be a third file that
350 imports both the initialization and the actual EM stuff, while a file
351 containing constants and classes could be imported by all others:
352 <pre>
353 dmv.py imports dmv_EM.py imports dmv_classes.py
354 dmv.py imports dmv_inits.py imports dmv_classes.py
355 </pre>
357 </li>
358 <li id="sec-6.5"><span class="todo">TOGROK</span> Some (tagged) sentences are bound to come twice &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span><br/>
359 Eg, first sort and count, so that the corpus
360 [['nn','vbd','det','nn'],
361 ['vbd','nn','det','nn'],
362 ['nn','vbd','det','nn']]
363 becomes
364 [(['nn','vbd','det','nn'],2),
365 (['vbd','nn','det','nn'],1)]
366 and then in each loop through sentences, make sure we handle the
367 frequency correctly.
370 Is there much to gain here?
371 </p>
372 </li>
373 <li id="sec-6.6"><span class="todo">TOGROK</span> tags as numbers or tags as strings? &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span><br/>
374 Need to clean up the representation.
377 Stick with tag-strings in initialization then switch to numbers for
378 IO-algorithm perhaps? Can probably afford more string-matching in
379 initialization..
380 </p></li>
381 </ul>
382 </div>
384 </div>
386 <div id="outline-container-7" class="outline-2">
387 <h2 id="sec-7">7 Expectation Maximation in IO/DMV-terms</h2>
388 <div id="text-7">
390 <p>inner(s,t,LHS) calculates the expected number of trees headed by LHS
391 from s to t (sentence positions). This uses the P_STOP and P_CHOOSE
392 values, which have been conveniently distributed into CNF rules as
393 probN and probA (non-adjacent and adjacent probabilites).
394 </p>
396 When re-estimating, we use the expected values from inner() to get new
397 values for P_STOP and P_CHOOSE. When we've re-estimated for the entire
398 corpus, we distribute P_STOP and P_CHOOSE into the CNF rules again, so
399 that in the next round we use new probN and probA to find
400 inner-probabilites.
401 </p>
403 The distribution of P_STOP and P_CHOOSE into CNF rules also happens in
404 init_normalize() (here along with the creation of P_STOP and
405 P_CHOOSE); P_STOP is used to create CNF rules where one branch of the
406 rule is STOP, P_CHOOSE is used to create rules of the form
407 <pre>
408 h -&gt; h _a_
409 h_ -&gt; h_ _a_
410 </pre>
411 </p>
413 Since "adjacency" is not captured in regular CNF rules, we need two
414 probabilites for each rule, and inner() has to know when to use which.
415 </p>
416 <ul>
417 <li id="sec-7.1"><span class="todo">TODO</span> Corpus access<br/>
418 </li>
419 <li id="sec-7.2"><span class="todo">TOGROK</span> sentences or rules as the "outer loop"? &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span><br/>
420 In regard to the E/M-step, finding P<sub>STOP</sub>, P<sub>CHOOSE</sub>.
423 </li>
424 </ul>
425 </div>
427 </div>
429 <div id="outline-container-8" class="outline-2">
430 <h2 id="sec-8">8 Python-stuff</h2>
431 <div id="text-8">
433 <ul>
434 <li>
435 <a href="src/pseudo.py">pseudo.py</a>
436 </li>
437 <li>
438 <a href="http://nltk.org/doc/en/structured-programming.html">http://nltk.org/doc/en/structured-programming.html</a> recursive dynamic
439 </li>
440 <li>
441 <a href="http://nltk.org/doc/en/advanced-parsing.html">http://nltk.org/doc/en/advanced-parsing.html</a>
442 </li>
443 <li>
444 <a href="http://jaynes.colorado.edu/PythonIdioms.html">http://jaynes.colorado.edu/PythonIdioms.html</a>
448 </li>
449 </ul>
450 </div>
452 </div>
454 <div id="outline-container-9" class="outline-2">
455 <h2 id="sec-9">9 Git</h2>
456 <div id="text-9">
458 <p>Setting up a new project:
459 <pre>
460 git init
461 git add .
462 git commit -m "first release"
463 </pre>
464 </p>
466 Later on: (<code>-a</code> does <code>git rm</code> and <code>git add</code> automatically)
467 <pre>
468 git init
469 git commit -a -m "some subsequent release"
470 </pre>
471 </p>
473 Then push stuff up to the remote server:
474 <pre>
475 git push git+ssh://username@repo.or.cz/srv/git/dmvccm.git master
476 </pre>
477 </p>
479 (<code>eval `ssh-agent`</code> and <code>ssh-add</code> to avoid having to type in keyphrase all
480 the time)
481 </p>
483 Make a copy of the (remote) master branch:
484 <pre>
485 git clone git://repo.or.cz/dmvccm.git
486 </pre>
487 </p>
489 Make and name a new branch in this folder
490 <pre>
491 git checkout -b mybranch
492 </pre>
493 </p>
495 To save changes in <code>mybranch</code>:
496 <pre>
497 git commit -a
498 </pre>
499 </p>
501 Go back to the master branch (uncommitted changes from <code>mybranch</code> are
502 carried over):
503 <pre>
504 git checkout master
505 </pre>
506 </p>
508 Try out:
509 <pre>
510 git add --interactive
511 </pre>
512 </p>
514 Good tutorial:
515 <a href="http://www-cs-students.stanford.edu/~blynn//gitmagic/">http://www-cs-students.stanford.edu/~blynn//gitmagic/</a>
516 </p></div>
517 </div>
518 <div id="postamble"><p class="author"> Author: Kevin Brubeck Unhammer
519 <a href="mailto:K.BrubeckUnhammer at student uva nl ">&lt;K.BrubeckUnhammer at student uva nl &gt;</a>
520 </p>
521 <p class="date"> Date: 2008/06/06 19:12:56</p>
522 </div><p class="postamble">Skrive vha. emacs + <a href='http://orgmode.org/'>org-mode</a></p></body>
523 </html>