| blob | e72cb06fc87845159b2be6c3c4432b0db7c2bc9c |
5 <head>
12 </head><body>
19 <ul>
32 </ul>
33 </div>
34 </div>
40 <p><span class="timestamp-kwd">DEADLINE: </span> <span class="timestamp">2008-06-30 Mon</span><br/>
41 </p><ul>
42 <li>
44 </li>
45 <li>
47 </li>
48 <li>
51 </li>
52 </ul>
55 </p></div>
57 </div>
63 <p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-12 Thu 11:11</span><br/>
65 There are 6 different configurations here, based on what the above
66 (mother) node is, and what the Node for which we're computing is.
67 Here <b>r</b> is not between <b>s</b> and <b>t</b> as in inner(), but an <i>outer</i> index. <b>loc_N</b>
69 of the mother of Node.
70 </p>
71 <ul>
72 <li>
73 mother is a RIGHT-stop:
74 <ul>
75 <li>
77 </li>
78 <li>
80 </li>
81 </ul>
82 </li>
83 <li>
84 mother is a LEFT-stop:
85 <ul>
86 <li>
88 </li>
89 <li>
92 </li>
93 </ul>
94 </li>
95 <li>
96 Node is on the LEFT branch (mom.L == Node)
97 <ul>
98 <li>
99 and mother is a LEFT attachment:
100 <ul>
101 <li>
103 </li>
104 <li>
107 </li>
108 <li>
110 </li>
111 <li>
113 </li>
114 </ul>
115 </li>
116 <li>
117 and mother is a RIGHT attachment:
118 <ul>
119 <li>
121 </li>
122 <li>
125 </li>
126 <li>
128 </li>
129 <li>
132 </li>
133 </ul>
134 </li>
135 </ul>
136 </li>
137 <li>
138 Node is on the RIGHT branch (mom.R == Node)
139 <ul>
140 <li>
141 and mother is a LEFT attachment:
142 <ul>
143 <li>
145 </li>
146 <li>
149 </li>
150 <li>
152 </li>
153 <li>
155 </li>
156 </ul>
157 </li>
158 <li>
159 and mother is a RIGHT attachment:
160 <ul>
161 <li>
163 </li>
164 <li>
167 </li>
168 <li>
170 </li>
171 <li>
174 </li>
175 </ul>
176 </li>
177 </ul>
178 </li>
179 </ul>
182 </p>
183 <p>
184 <pre>
185 in notes: in code (constants): in Klein thesis:
186 -------------------------------------------------------------------
187 _h_ SEAL bar over h
188 h_ RGO_L right-under-left-arrow over h
189 h GO_R right-arrow over h
191 LGO_R left-under-right-arrow over h
192 GO_L left-arrow over h
193 </pre>
194 </p>
195 <p>
196 Also, unlike in <a href="http://bibsonomy.org/bibtex/2b9f6798bb092697da7042ca3f5dee795">Lari & Young</a>, non-ROOT ('S') symbols may cover the
198 sentence.
199 </p>
200 </div>
202 </div>
205 <h2 id="sec-3">3 <span class="todo">TODO</span> [#B] P_STOP and P_CHOOSE for IO/EM (reestimation)</h2>
210 (In the article..not the <a href="http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf">thesis</a>)
211 </p>
212 <ul>
214 Assuming this:
218 <tbody>
219 <tr><td>P<sub>STOP</sub>(STOP : h,L,non_adj) =</td><td>∑<sub>corpus</sub> ∑<sub>s<loc(h)</sub> ∑<sub>t>=loc(h)</sub> c(s,t,_h_, …)</td></tr>
220 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s<loc(h)</sub> ∑<sub>t>=loc(h)</sub> c(s,t,h_, …)</td></tr>
221 <tr><td></td><td></td></tr>
222 <tr><td>P<sub>STOP</sub>(STOP : h,L,adj) =</td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t>=loc(h)</sub> c(s,t,_h_, …)</td></tr>
223 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t>=loc(h)</sub> c(s,t,h_, …)</td></tr>
224 <tr><td></td><td></td></tr>
225 <tr><td>P<sub>STOP</sub>(STOP : h,R,non_adj) =</td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t>loc(h)</sub> c(s,t,h_, …)</td></tr>
226 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t>loc(h)</sub> c(s,t,h, …)</td></tr>
227 <tr><td></td><td></td></tr>
228 <tr><td>P<sub>STOP</sub>(STOP : h,R,adj) =</td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t=loc(h)</sub> c(s,t,h_, …)</td></tr>
229 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t=loc(h)</sub> c(s,t,h, …)</td></tr>
230 </tbody>
231 </table>
234 <p>
236 </p></li>
238 Assuming this:
242 <tbody>
243 <tr><td>P<sub>CHOOSE</sub>(a : h,R) =</td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t > loc(h)</sub> ∑<sub>loc(h) < r <= t</sub> c(s, r-1, h_, …) * c(r,t,_a_,…)</td></tr>
244 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t > loc(h)</sub> c(s,t,h, …)</td></tr>
245 <tr><td></td><td></td></tr>
246 <tr><td>P<sub>CHOOSE</sub>(a : h,L) =</td><td>∑<sub>corpus</sub> ∑<sub>s<loc(h)</sub> ∑<sub>t>=loc(h)</sub> ∑<sub>r<loc(h)</sub> c(s,r,_a_, …) * c(r+1, t, h_, …)</td></tr>
247 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s<loc(h)</sub> ∑<sub>t>=loc(h)</sub> c(s,t,h_,…)</td></tr>
248 </tbody>
249 </table>
251 t >= loc(h) since there are many possibilites for right-attachments
252 below, and each of them alone gives a lower probability (through
253 multiplication) to the upper tree (so add them all)
255 <p>
257 have to make sure they are contiguous (otherwise we would have no way
260 </p></li>
261 <li id="sec-3.3"><span class="done">DONE</span> [#A] How do we only count from completed trees?<br/>
262 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-13 Fri 11:40</span><br/>
263 Use c(s,t,Node); inner * outer / P_sent
265 </li>
267 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-13 Fri 11:38</span><br/>
268 = inner * outer / P_sent
270 <p>
271 implemented as inner * outer / inner_sent
272 </p>
273 </li>
274 </ul>
275 </div>
277 </div>
280 <h2 id="sec-4">4 <span class="todo">TOGROK</span> Find Most Probable Parse of given test sentence</h2>
283 <p>We could probably do it pretty easily from the chart:
284 </p><ul>
285 <li>
286 for all loc_h, select the (0,len(sent),ROOT,loc_h) that has the highest p
287 </li>
288 <li>
289 for stops, just keep going
290 </li>
291 <li>
292 for rewrites, for loc_dep select the one that has the highest p
293 </li>
294 </ul>
295 </div>
297 </div>
303 <p>Page 108 (pdf: 124) of <a href="http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf">Klein's thesis</a> gives info about this.
304 </p><ul>
305 <li id="sec-5.1"><span class="todo">TODO</span> Make inner() and outer() also allow left-first attachment<br/>
307 </li>
308 </ul>
309 </div>
311 </div>
314 <h2 id="sec-6">6 <span class="todo">TODO</span> Get a dependency parsed version of WSJ to test with</h2>
317 </div>
319 </div>
326 </p>
327 <p>
328 We go through the corpus, since the probabilities are based on how far
329 away in the sentence arguments are from their heads.
330 </p><ul>
333 </li>
334 <li id="sec-7.2"><span class="done">DONE</span> Separate initialization to another file? <span class="tag">PRETTIER</span><br/>
335 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-08 Sun 12:51</span><br/>
337 </li>
339 (from initialization frequency)
340 </li>
342 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-05-27 Tue 20:04</span><br/>
343 <ul>
346 the sentence [det nn vb nn] is
347 <pre>
348 f_{STOP}( STOP|det, L, adj) +1
349 f_{STOP}(-STOP|det, L, adj) +0
350 f_{STOP}( STOP|det, L, non_adj) +1
351 f_{STOP}(-STOP|det, L, non_adj) +0
352 f_{STOP}( STOP|det, R, adj) +0
353 f_{STOP}(-STOP|det, R, adj) +1
355 f_{STOP}( STOP|nn, L, adj) +0
356 f_{STOP}(-STOP|nn, L, adj) +1
357 f_{STOP}( STOP|nn, L, non_adj) +1 # since there's at least one to the left
358 f_{STOP}(-STOP|nn, L, non_adj) +0
359 </pre>
360 <ul>
362 <pre>
365 f[head, 'STOP', 'LA'] += (i_h == 0) # very first word
366 f[head, '-STOP', 'LA'] += (not i_h == 0)
369 f[head, 'STOP', 'RA'] += (i_h == n - 1) # very last word
370 f[head, '-STOP', 'RA'] += (not i_h == n - 1)
371 </pre>
372 vs
373 <pre>
374 # this one requires some additional rewriting since it
375 # introduces divisions by zero
376 f[head, 'STOP', 'LN'] += (i_h == 1) # second word
378 f[head, 'STOP', 'LA'] += (i_h == 0) # first word
379 f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
380 f[head, 'STOP', 'RN'] += (i_h == n - 2) # second-to-last
382 f[head, 'STOP', 'RA'] += (i_h == n - 1) # last word
383 f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
384 </pre>
385 vs
386 <pre>
387 f[head, 'STOP', 'LN'] += (i_h == 1) # second word
388 f[head, '-STOP', 'LN'] += (not i_h == 1) # not second
389 f[head, 'STOP', 'LA'] += (i_h == 0) # first word
390 f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
391 f[head, 'STOP', 'RN'] += (i_h == n - 2) # second-to-last
392 f[head, '-STOP', 'RN'] += (not i_h == n - 2) # not second-to-last
393 f[head, 'STOP', 'RA'] += (i_h == n - 1) # last word
394 f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
395 </pre>
396 vs
397 "all words take the same number of arguments" interpreted as
398 <pre>
399 for all heads:
400 p_STOP(head, 'STOP', 'LN') = 0.3
401 p_STOP(head, 'STOP', 'LA') = 0.5
402 p_STOP(head, 'STOP', 'RN') = 0.4
403 p_STOP(head, 'STOP', 'RA') = 0.7
404 </pre>
405 (which we easily may tweak in init_zeros())
406 </li>
407 </ul>
408 </li>
410 Go through the corpus, counting distances between heads and
411 arguments. In [det nn vb nn], we give
412 <ul>
413 <li>
415 </li>
416 <li>
418 </li>
419 <li>
421 <ul>
422 <li>
426 </li>
427 </ul>
428 </li>
429 </ul>
433 just a frequency count of the corpus…
434 </p>
435 <p>
437 rewrite to an 'h' anyway (it's just a check for whether, at this
438 location in the sentence, we have the right POS-tag).
439 </p></li>
440 </ul>
441 </li>
442 </ul>
443 </div>
445 </div>
451 <p><a href="http://wiki.python.org/moin/PythonSpeed/PerformanceTips">http://wiki.python.org/moin/PythonSpeed/PerformanceTips</a> Eg., use
452 map/reduce/filter/[i for i in [i's]]/(i for i in [i's]) instead of
453 for-loops; use local variables for globals (global variables or or
454 functions), etc.
455 </p>
456 <ul>
457 <li id="sec-8.1"><span class="todo">TODO</span> when reestimating P_STOP etc, remove rules with p < epsilon <span class="tag">OPTIMIZE</span><br/>
458 </li>
459 <li id="sec-8.2"><span class="todo">TODO</span> inner_dmv, short ranges and impossible attachment <span class="tag">OPTIMIZE</span><br/>
461 with both Lattach=True and Rattach=True.
463 <p>
465 Lattach=False, Rattach=False.
466 </p>
467 <p>
468 Put this in the loop under rewrite rules (could also do it in the STOP
469 section, but that would only have an effect on very short sentences).
470 </p></li>
471 <li id="sec-8.3"><span class="todo">TODO</span> clean up the module files <span class="tag">PRETTIER</span><br/>
472 Is there better way to divide dmv and harmonic? There's a two-way
473 dependency between the modules. Guess there could be a third file that
474 imports both the initialization and the actual EM stuff, while a file
475 containing constants and classes could be imported by all others:
476 <pre>
477 dmv.py imports dmv_EM.py imports dmv_classes.py
478 dmv.py imports dmv_inits.py imports dmv_classes.py
479 </pre>
481 </li>
482 <li id="sec-8.4"><span class="todo">TOGROK</span> Some (tagged) sentences are bound to come twice <span class="tag">OPTIMIZE</span><br/>
483 Eg, first sort and count, so that the corpus
484 [['nn','vbd','det','nn'],
485 ['vbd','nn','det','nn'],
486 ['nn','vbd','det','nn']]
487 becomes
488 [(['nn','vbd','det','nn'],2),
489 (['vbd','nn','det','nn'],1)]
490 and then in each loop through sentences, make sure we handle the
491 frequency correctly.
493 <p>
494 Is there much to gain here?
495 </p>
496 </li>
497 <li id="sec-8.5"><span class="todo">TOGROK</span> tags as numbers or tags as strings? <span class="tag">OPTIMIZE</span><br/>
498 Need to clean up the representation.
500 <p>
501 Stick with tag-strings in initialization then switch to numbers for
502 IO-algorithm perhaps? Can probably afford more string-matching in
503 initialization..
504 </p></li>
505 <li id="sec-8.6"><span class="done">DONE</span> if loc_h == t, no need to try right-attachment rules &v.v. <span class="tag">OPTIMIZE</span><br/>
506 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-10 Tue 14:34</span><br/>
507 (and if loc_h == s, no need to try left-attachment rules.)
509 <p>
510 Modest speed increase (5%).
511 </p></li>
512 <li id="sec-8.7"><span class="done">DONE</span> io.debug parameters should not call functions <span class="tag">OPTIMIZE</span><br/>
513 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-10 Tue 12:26</span><br/>
514 Exchanged all io.debug(str,'level') calls with statements of the form:
515 <pre>
516 if 'level' in io.DEBUG:
517 print str
518 </pre>
520 <p>
521 and got an almost threefold speed increase on inner().
522 </p></li>
523 <li id="sec-8.8"><span class="done">DONE</span> inner_dmv() should disregard rules with heads not in sent <span class="tag">OPTIMIZE</span><br/>
524 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-08 Sun 10:18</span><br/>
525 If the sentence is "nn vbd det nn", we should not even look at rules
526 where
527 <pre>
528 rule.head() not in "nn vbd det nn".split()
529 </pre>
530 This is ruled out by getting rules from g.rules(LHS, sent).
532 <p>
533 Also, we optimize this further by saying we don't even recurse into
534 attachment rules where
535 <pre>
536 rule.head() not in sent[ s :r+1]
538 </pre>
539 meaning, if we're looking at the span "vbd det", we only use
540 attachment rules where both daughters are members of ['vbd','det']
541 (although we don't (yet) care about removing rules that rewrite to the
542 same tag if there are no duplicate tags in the span, etc., that would
543 be a lot of trouble for little potential gain).
544 </p></li>
545 </ul>
546 </div>
548 </div>
554 <p>Each DMV_Rule has both a probN and a probA, for adjacencies. inner()
555 and outer() needs the correct one in each case.
556 </p>
557 <p>
558 In each inner() call, loc_h is the location of the head of this
560 the structure we're looking outside of.
561 </p>
562 <p>
563 We call inner() for each location of a head, and on each terminal,
564 loc_h must equal s (and t). In the recursive attachment calls, we use
565 the locations (sentence indices) of words to the left or right of the
567 </p><ul>
569 K&M's adjacency is just whether or not an argument has been generated
570 in the current direction yet. One could also make a stronger type of
571 adjacency, where h and a are not adjacent if b is in between, eg. with
573 K&M-adjacent to a, but not next to a, since b is in between. It's easy
574 to check this type of adjacency in inner(), but it needs new rules for
575 P_STOP reestimation.
576 </li>
577 </ul>
578 </div>
580 </div>
586 <p>outer(s,t,Node) and inner(s,t,Node) calculates the expected number of
588 the P_STOP and P_CHOOSE values, which have been conveniently
589 distributed into CNF rules as probN and probA (non-adjacent and
590 adjacent probabilites).
591 </p>
592 <p>
593 When re-estimating, we use the expected values from outer() and
594 inner() to get new values for P_STOP and P_CHOOSE. When we've
595 re-estimated for the entire corpus, we distribute P_STOP and P_CHOOSE
596 into the CNF rules again, so that in the next round we use new probN
597 and probA to find outer- and inner-probabilites.
598 </p>
599 <p>
600 The distribution of P_STOP and P_CHOOSE into CNF rules also happens in
601 init_normalize() (here along with the creation of P_STOP and
602 P_CHOOSE); P_STOP is used to create CNF rules where one branch of the
603 rule is STOP, P_CHOOSE is used to create rules of the form
604 <pre>
605 h -> h _a_
606 h_ -> h_ _a_
607 </pre>
608 </p>
609 <p>
610 Since "adjacency" is not captured in regular CNF rules, we need two
611 probabilites for each rule, and outer() and inner() have to know when
612 to use which.
613 </p>
615 </div>
617 </div>
623 <p>Make those debug statements steal a bit less attention in emacs:
624 <pre>
625 (font-lock-add-keywords
626 'python-mode ; not really regexp, a bit slow
627 '(("^\\( *\\)\\(\\if +'.+' +in +io.DEBUG. *\\(
629 (font-lock-add-keywords
630 'python-mode
632 </pre>
633 </p>
634 <ul>
635 <li>
637 </li>
638 <li>
639 <a href="http://nltk.org/doc/en/structured-programming.html">http://nltk.org/doc/en/structured-programming.html</a> recursive dynamic
640 </li>
641 <li>
642 <a href="http://nltk.org/doc/en/advanced-parsing.html">http://nltk.org/doc/en/advanced-parsing.html</a>
643 </li>
644 <li>
645 <a href="http://jaynes.colorado.edu/PythonIdioms.html">http://jaynes.colorado.edu/PythonIdioms.html</a>
649 </li>
650 </ul>
651 </div>
653 </div>
659 <p>Repository web page: <a href="http://repo.or.cz/w/dmvccm.git">http://repo.or.cz/w/dmvccm.git</a>
660 </p>
661 <p>
662 Setting up a new project:
663 <pre>
664 git init
665 git add .
666 git commit -m "first release"
667 </pre>
668 </p>
669 <p>
671 <pre>
672 git init
673 git commit -a -m "some subsequent release"
674 </pre>
675 </p>
676 <p>
677 Then push stuff up to the remote server:
678 <pre>
679 git push git+ssh://username@repo.or.cz/srv/git/dmvccm.git master
680 </pre>
681 </p>
682 <p>
683 (<code>eval `ssh-agent`</code> and <code>ssh-add</code> to avoid having to type in keyphrase all
684 the time)
685 </p>
686 <p>
687 Make a copy of the (remote) master branch:
688 <pre>
689 git clone git://repo.or.cz/dmvccm.git
690 </pre>
691 </p>
692 <p>
693 Make and name a new branch in this folder
694 <pre>
695 git checkout -b mybranch
696 </pre>
697 </p>
698 <p>
700 <pre>
701 git commit -a
702 </pre>
703 </p>
704 <p>
706 carried over):
707 <pre>
708 git checkout master
709 </pre>
710 </p>
711 <p>
712 Try out:
713 <pre>
714 git add --interactive
715 </pre>
716 </p>
717 <p>
718 Good tutorial:
719 <a href="http://www-cs-students.stanford.edu/~blynn//gitmagic/">http://www-cs-students.stanford.edu/~blynn//gitmagic/</a>
720 </p></div>
721 </div>
723 <a href="mailto:K.BrubeckUnhammer at student uva nl "><K.BrubeckUnhammer at student uva nl ></a>
724 </p>
726 </div><p class="postamble">Skrive vha. emacs + <a href='http://orgmode.org/'>org-mode</a></p></body>
727 </html>