| blob | d7d08d1ab1a46073a975daf3be5929faf2b3b21b |
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>
64 (mother) node is, and what the Node for which we're computing is.
65 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>
67 of the mother rule.
68 </p>
69 <ul>
70 <li>
71 mother is a RIGHT-stop:
72 <ul>
73 <li>
75 </li>
76 <li>
78 </li>
79 </ul>
80 </li>
81 <li>
82 mother is a LEFT-stop:
83 <ul>
84 <li>
86 </li>
87 <li>
90 </li>
91 </ul>
92 </li>
93 <li>
94 Node is on the LEFT branch (mom.L == Node)
95 <ul>
96 <li>
97 and mother is a LEFT attachment:
98 <ul>
99 <li>
101 </li>
102 <li>
105 </li>
106 <li>
108 </li>
109 <li>
111 </li>
112 </ul>
113 </li>
114 <li>
115 and mother is a RIGHT attachment:
116 <ul>
117 <li>
119 </li>
120 <li>
123 </li>
124 <li>
126 </li>
127 <li>
130 </li>
131 </ul>
132 </li>
133 </ul>
134 </li>
135 <li>
136 Node is on the RIGHT branch (mom.R == Node)
137 <ul>
138 <li>
139 and mother is a LEFT attachment:
140 <ul>
141 <li>
143 </li>
144 <li>
147 </li>
148 <li>
150 </li>
151 <li>
153 </li>
154 </ul>
155 </li>
156 <li>
157 and mother is a RIGHT attachment:
158 <ul>
159 <li>
161 </li>
162 <li>
165 </li>
166 <li>
168 </li>
169 <li>
172 </li>
173 </ul>
174 </li>
175 </ul>
176 </li>
177 </ul>
180 </p>
183 </div>
185 </div>
188 <h2 id="sec-3">3 <span class="todo">TODO</span> [#B] P_STOP and P_CHOOSE for IO/EM (reestimation)</h2>
193 (In the article..not the thesis)
194 </p>
195 <ul>
196 <li id="sec-3.1"><span class="todo">TOGROK</span> [#A] How do we only count from completed trees?<br/>
197 The chart from inner() contains several entries where the only ways to
198 reach them (from above) are through nodes that have zero probability;
199 we don't want these to give counts for reestimation.
201 <p>
202 prune() weeds out entries with only zero-probability mothers (or
203 grandmothers), but is incredibly slow (reestimating with pruning takes
204 almost 50 times longer).
205 </p>
206 <p>
207 Another solution is to add
208 </p></li>
210 Assuming this:
211 <ul>
212 <li>
213 P<sub>STOP</sub>(STOP|h,L,non_adj) = ∑<sub>corpus</sub> ∑<sub>s<loc(h)</sub> ∑<sub>t</sub>
215 inner(s,t,h_, …)
216 </li>
217 <li>
218 P<sub>STOP</sub>(STOP|h,L,adj) = ∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t</sub>
220 inner(s,t,h_, …)
221 </li>
222 <li>
223 P<sub>STOP</sub>(STOP|h,R,non_adj) = ∑<sub>corpus</sub> ∑<sub>s</sub> ∑<sub>t>loc(h)</sub>
225 inner(s,t,h_, …)
226 </li>
227 <li>
228 P<sub>STOP</sub>(STOP|h,R,adj) = ∑<sub>corpus</sub> ∑<sub>s</sub> ∑<sub>t=loc(h)</sub>
230 inner(s,t,h_, …)
232 </li>
233 </ul>
236 </p></li>
238 Assuming this:
239 <ul>
240 <li>
241 P<sub>CHOOSE</sub>(a|h,L) = ∑<sub>corpus</sub> ∑<sub>s<loc(h)</sub> ∑<sub>t>=loc(h)</sub> ∑<sub>r<t</sub>
242 inner(s,r,_a_, …) / ∑<sub>corpus</sub> ∑<sub>s<loc(h)</sub> ∑<sub>t>=loc(h)</sub>
243 inner(s,t,h_,…)
244 <ul>
245 <li>
246 t >= loc(h) since there are many possibilites for
247 right-attachments below, and each of them alone gives a lower
248 probability (through multiplication) to the upper tree (so sum
249 them all)
250 </li>
251 </ul>
252 </li>
253 <li>
254 P<sub>CHOOSE</sub>(a|h,R) = ∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>r>s</sub>
256 inner(s,t,h, …)
258 </li>
259 </ul>
260 </li>
261 </ul>
262 </div>
264 </div>
267 <h2 id="sec-4">4 <span class="todo">TOGROK</span> Find Most Probable Parse of given test sentence</h2>
270 <p>We could probably do it pretty easily from the chart:
271 </p><ul>
272 <li>
273 for all loc_h, select the (0,len(sent),ROOT,loc_h) that has the highest p
274 </li>
275 <li>
276 for stops, just keep going
277 </li>
278 <li>
279 for rewrites, for loc_dep select the one that has the highest p
280 </li>
281 </ul>
282 </div>
284 </div>
290 </div>
292 </div>
295 <h2 id="sec-6">6 <span class="todo">TODO</span> Get a dependency parsed version of WSJ to test with</h2>
298 </div>
300 </div>
307 </p>
308 <p>
309 We do have to go through the corpus, since the probabilities are based
310 on how far away in the sentence arguments are from their heads.
311 </p><ul>
314 </li>
315 <li id="sec-7.2"><span class="done">DONE</span> Separate initialization to another file? <span class="tag">PRETTIER</span><br/>
316 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-08 Sun 12:51</span><br/>
318 </li>
320 (from initialization frequency)
321 </li>
323 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-05-27 Tue 20:04</span><br/>
324 <ul>
327 the sentence [det nn vb nn] is
328 <pre>
329 f_{STOP}( STOP|det, L, adj) +1
330 f_{STOP}(-STOP|det, L, adj) +0
331 f_{STOP}( STOP|det, L, non_adj) +1
332 f_{STOP}(-STOP|det, L, non_adj) +0
333 f_{STOP}( STOP|det, R, adj) +0
334 f_{STOP}(-STOP|det, R, adj) +1
336 f_{STOP}( STOP|nn, L, adj) +0
337 f_{STOP}(-STOP|nn, L, adj) +1
338 f_{STOP}( STOP|nn, L, non_adj) +1 # since there's at least one to the left
339 f_{STOP}(-STOP|nn, L, non_adj) +0
340 </pre>
341 <ul>
343 <pre>
346 f[head, 'STOP', 'LA'] += (i_h == 0) # very first word
347 f[head, '-STOP', 'LA'] += (not i_h == 0)
350 f[head, 'STOP', 'RA'] += (i_h == n - 1) # very last word
351 f[head, '-STOP', 'RA'] += (not i_h == n - 1)
352 </pre>
353 vs
354 <pre>
355 # this one requires some additional rewriting since it
356 # introduces divisions by zero
357 f[head, 'STOP', 'LN'] += (i_h == 1) # second word
359 f[head, 'STOP', 'LA'] += (i_h == 0) # first word
360 f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
361 f[head, 'STOP', 'RN'] += (i_h == n - 2) # second-to-last
363 f[head, 'STOP', 'RA'] += (i_h == n - 1) # last word
364 f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
365 </pre>
366 vs
367 <pre>
368 f[head, 'STOP', 'LN'] += (i_h == 1) # second word
369 f[head, '-STOP', 'LN'] += (not i_h == 1) # not second
370 f[head, 'STOP', 'LA'] += (i_h == 0) # first word
371 f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
372 f[head, 'STOP', 'RN'] += (i_h == n - 2) # second-to-last
373 f[head, '-STOP', 'RN'] += (not i_h == n - 2) # not second-to-last
374 f[head, 'STOP', 'RA'] += (i_h == n - 1) # last word
375 f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
376 </pre>
377 vs
378 "all words take the same number of arguments" interpreted as
379 <pre>
380 for all heads:
381 p_STOP(head, 'STOP', 'LN') = 0.3
382 p_STOP(head, 'STOP', 'LA') = 0.5
383 p_STOP(head, 'STOP', 'RN') = 0.4
384 p_STOP(head, 'STOP', 'RA') = 0.7
385 </pre>
386 (which we easily may tweak in init_zeros())
387 </li>
388 </ul>
389 </li>
391 Go through the corpus, counting distances between heads and
392 arguments. In [det nn vb nn], we give
393 <ul>
394 <li>
396 </li>
397 <li>
399 </li>
400 <li>
402 <ul>
403 <li>
407 </li>
408 </ul>
409 </li>
410 </ul>
414 just a frequency count of the corpus…
415 </p></li>
416 </ul>
417 </li>
418 </ul>
419 </div>
421 </div>
427 <p><a href="http://wiki.python.org/moin/PythonSpeed/PerformanceTips">http://wiki.python.org/moin/PythonSpeed/PerformanceTips</a> Eg., use
428 map/reduce/filter/[i for i in [i's]]/(i for i in [i's]) instead of
429 for-loops; use local variables for globals (global variables or or
430 functions), etc.
431 </p>
432 <ul>
433 <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/>
434 </li>
435 <li id="sec-8.2"><span class="todo">TODO</span> inner_dmv, short ranges and impossible attachment <span class="tag">OPTIMIZE</span><br/>
437 with both Lattach=True and Rattach=True.
439 <p>
441 Lattach=False, Rattach=False.
442 </p>
443 <p>
444 Put this in the loop under rewrite rules (could also do it in the STOP
445 section, but that would only have an effect on very short sentences).
446 </p></li>
447 <li id="sec-8.3"><span class="todo">TODO</span> clean up the module files <span class="tag">PRETTIER</span><br/>
448 Is there better way to divide dmv and harmonic? There's a two-way
449 dependency between the modules. Guess there could be a third file that
450 imports both the initialization and the actual EM stuff, while a file
451 containing constants and classes could be imported by all others:
452 <pre>
453 dmv.py imports dmv_EM.py imports dmv_classes.py
454 dmv.py imports dmv_inits.py imports dmv_classes.py
455 </pre>
457 </li>
458 <li id="sec-8.4"><span class="todo">TOGROK</span> Some (tagged) sentences are bound to come twice <span class="tag">OPTIMIZE</span><br/>
459 Eg, first sort and count, so that the corpus
460 [['nn','vbd','det','nn'],
461 ['vbd','nn','det','nn'],
462 ['nn','vbd','det','nn']]
463 becomes
464 [(['nn','vbd','det','nn'],2),
465 (['vbd','nn','det','nn'],1)]
466 and then in each loop through sentences, make sure we handle the
467 frequency correctly.
469 <p>
470 Is there much to gain here?
471 </p>
472 </li>
473 <li id="sec-8.5"><span class="todo">TOGROK</span> tags as numbers or tags as strings? <span class="tag">OPTIMIZE</span><br/>
474 Need to clean up the representation.
476 <p>
477 Stick with tag-strings in initialization then switch to numbers for
478 IO-algorithm perhaps? Can probably afford more string-matching in
479 initialization..
480 </p></li>
481 <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/>
482 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-10 Tue 14:34</span><br/>
483 (and if loc_h == s, no need to try left-attachment rules.)
485 <p>
486 Modest speed increase (5%).
487 </p></li>
488 <li id="sec-8.7"><span class="done">DONE</span> io.debug parameters should not call functions <span class="tag">OPTIMIZE</span><br/>
489 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-10 Tue 12:26</span><br/>
490 Exchanged all io.debug(str,'level') calls with statements of the form:
491 <pre>
492 if 'level' in io.DEBUG:
493 print str
494 </pre>
496 <p>
497 and got an almost threefold speed increase on inner().
498 </p></li>
499 <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/>
500 <span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-08 Sun 10:18</span><br/>
501 If the sentence is "nn vbd det nn", we should not even look at rules
502 where
503 <pre>
504 rule.head() not in "nn vbd det nn".split()
505 </pre>
506 This is ruled out by getting rules from g.rules(LHS, sent).
508 <p>
509 Also, we optimize this further by saying we don't even recurse into
510 attachment rules where
511 <pre>
512 rule.head() not in sent[ s :r+1]
514 </pre>
515 meaning, if we're looking at the span "vbd det", we only use
516 attachment rules where both daughters are members of ['vbd','det']
517 (although we don't (yet) care about removing rules that rewrite to the
518 same tag if there are no duplicate tags in the span, etc., that would
519 be a lot of trouble for little potential gain).
520 </p></li>
521 </ul>
522 </div>
524 </div>
530 <p>Each DMV_Rule now has both a probN and a probA, for
531 adjacencies. inner() needs the correct one in each case.
532 </p>
533 <p>
534 Adjacency gives a problem with duplicate words/tags, eg. in the
541 both. And in possibly much more complex versions.
542 </p>
543 <p>
544 So now we call inner() for each location of a head, and on each
545 terminal, loc_h must equal s (and t). In the recursive attachment
546 calls, we use the locations (sentence indices) of words to the left or
547 right of the head in calls to inner(). loc_h lets us check whether we
548 need probN or probA.
549 </p>
550 <p>
551 In each inner() call, loc_h is the location of the root of this
552 dependency structure.
553 </p><ul>
555 K&M's adjacency is just whether or not an argument has been generated
556 in the current direction yet. One could also make a stronger type of
557 adjacency, where h and a are not adjacent if b is in between, eg. with
559 K&M-adjacent to a, but not next to a, since b is in between. It's easy
560 to check this type of adjacency in inner(), but it needs new rules for
561 P_STOP reestimation.
562 </li>
563 </ul>
564 </div>
566 </div>
572 <p>inner(s,t,LHS) calculates the expected number of trees headed by LHS
573 from s to t (sentence positions). This uses the P_STOP and P_CHOOSE
574 values, which have been conveniently distributed into CNF rules as
575 probN and probA (non-adjacent and adjacent probabilites).
576 </p>
577 <p>
578 When re-estimating, we use the expected values from inner() to get new
579 values for P_STOP and P_CHOOSE. When we've re-estimated for the entire
580 corpus, we distribute P_STOP and P_CHOOSE into the CNF rules again, so
581 that in the next round we use new probN and probA to find
582 inner-probabilites.
583 </p>
584 <p>
585 The distribution of P_STOP and P_CHOOSE into CNF rules also happens in
586 init_normalize() (here along with the creation of P_STOP and
587 P_CHOOSE); P_STOP is used to create CNF rules where one branch of the
588 rule is STOP, P_CHOOSE is used to create rules of the form
589 <pre>
590 h -> h _a_
591 h_ -> h_ _a_
592 </pre>
593 </p>
594 <p>
595 Since "adjacency" is not captured in regular CNF rules, we need two
596 probabilites for each rule, and inner() has to know when to use which.
597 </p>
598 <ul>
600 </li>
601 <li id="sec-10.2"><span class="todo">TOGROK</span> sentences or rules as the "outer loop"? <span class="tag">OPTIMIZE</span><br/>
605 </li>
606 </ul>
607 </div>
609 </div>
615 <p>Make those debug statements steal a bit less attention in emacs:
616 <pre>
617 (font-lock-add-keywords
618 'python-mode ; not really regexp, a bit slow
619 '(("^\\( *\\)\\(\\if +'.+' +in +io.DEBUG. *\\(
621 (font-lock-add-keywords
622 'python-mode
624 </pre>
625 </p>
626 <ul>
627 <li>
629 </li>
630 <li>
631 <a href="http://nltk.org/doc/en/structured-programming.html">http://nltk.org/doc/en/structured-programming.html</a> recursive dynamic
632 </li>
633 <li>
634 <a href="http://nltk.org/doc/en/advanced-parsing.html">http://nltk.org/doc/en/advanced-parsing.html</a>
635 </li>
636 <li>
637 <a href="http://jaynes.colorado.edu/PythonIdioms.html">http://jaynes.colorado.edu/PythonIdioms.html</a>
641 </li>
642 </ul>
643 </div>
645 </div>
651 <p>Repository web page: <a href="http://repo.or.cz/w/dmvccm.git">http://repo.or.cz/w/dmvccm.git</a>
652 </p>
653 <p>
654 Setting up a new project:
655 <pre>
656 git init
657 git add .
658 git commit -m "first release"
659 </pre>
660 </p>
661 <p>
663 <pre>
664 git init
665 git commit -a -m "some subsequent release"
666 </pre>
667 </p>
668 <p>
669 Then push stuff up to the remote server:
670 <pre>
671 git push git+ssh://username@repo.or.cz/srv/git/dmvccm.git master
672 </pre>
673 </p>
674 <p>
675 (<code>eval `ssh-agent`</code> and <code>ssh-add</code> to avoid having to type in keyphrase all
676 the time)
677 </p>
678 <p>
679 Make a copy of the (remote) master branch:
680 <pre>
681 git clone git://repo.or.cz/dmvccm.git
682 </pre>
683 </p>
684 <p>
685 Make and name a new branch in this folder
686 <pre>
687 git checkout -b mybranch
688 </pre>
689 </p>
690 <p>
692 <pre>
693 git commit -a
694 </pre>
695 </p>
696 <p>
698 carried over):
699 <pre>
700 git checkout master
701 </pre>
702 </p>
703 <p>
704 Try out:
705 <pre>
706 git add --interactive
707 </pre>
708 </p>
709 <p>
710 Good tutorial:
711 <a href="http://www-cs-students.stanford.edu/~blynn//gitmagic/">http://www-cs-students.stanford.edu/~blynn//gitmagic/</a>
712 </p></div>
713 </div>
715 <a href="mailto:K.BrubeckUnhammer at student uva nl "><K.BrubeckUnhammer at student uva nl ></a>
716 </p>
718 </div><p class="postamble">Skrive vha. emacs + <a href='http://orgmode.org/'>org-mode</a></p></body>
719 </html>