| blob | a09c831ec2f2539438bca680c56d8c006e67da19 |
5 <head>
12 </head><body>
20 <ul>
23 <ul>
26 <ul>
28 </ul>
29 </li>
31 </ul>
32 </li>
36 <ul>
38 </ul>
39 </li>
42 <ul>
47 <ul>
50 </ul></li>
51 </ul>
52 </li>
54 <ul>
55 <li><a href="#sec-8.1">8.1 when reestimating P_STOP etc, remove rules with p < epsilon</a></li>
60 </ul>
61 </li>
63 <ul>
65 </ul>
66 </li>
70 </ul>
71 </div>
72 </div>
78 <p><span class="timestamp-kwd">DEADLINE: </span> <span class="timestamp">2008-06-30 Mon</span><br/>
79 </p><ul>
80 <li>
82 </li>
83 <li>
85 </li>
86 <li>
89 </li>
90 </ul>
93 </p>
94 <p>
95 <a href="http://www.student.uib.no/~kun041/dmvccm/DMVCCM_archive.html">Archived entries</a> from this file.
96 </p></div>
98 </div>
106 (In the article..not the <a href="http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf">thesis</a>)
107 </p>
109 </div>
120 <tbody>
123 </tbody>
124 </table>
127 <p>
128 while L&Y uses
131 <tbody>
132 <tr><td>w_sent = 1/P_sent * prob(h_->_a_ h_) * e(s,r,_a_) * e(r+1,t, h_) * f(s,t,h_)</td></tr>
134 </tbody>
135 </table>
138 <p>
139 Just for completion: <br/>
140 PSTOP =eg. c(s,t,_h_) / c(s,t,h_) for certain s,t <br/>
144 <tbody>
147 </tbody>
148 </table>
151 <p>
152 vs what seems to be the direct L&Y translation:
153 </p>
156 <tbody>
159 </tbody>
160 </table>
163 <p>
164 …but if we used that, e(s,t,h_) would cancel out and we'd just be
165 dividing the outer scores * rule-probability.. hmm.. Also, there's the
166 problem of what 'rule-probability' means here, since there's on the
167 one hand the CNF-rule probability, and on the other hand PSTOP and
168 PCHOOSE – in stop rules, PSTOP is the rule-probability, while for
169 attachment rules, it's PCHOOSE*(1-PSTOP).
170 </p></div>
172 </div>
178 <ul>
179 <li>
181 Implemented as assumed below, but this does not give 1-summing
182 probabilities, why? Are we checking the right configurations? Eg,
183 is it enough to just check c(s,t,h_), c(s,r,_a_) and
184 c(r+1,t,h_) for left attachments??
186 </li>
187 </ul>
189 <p>So far assuming this:
190 </p>
193 <tbody>
194 <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(r,t,_a_)</td></tr>
195 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t > loc(h)</sub> ∑<sub>loc(h) < r <= t</sub> c(s,t,h) * c(s, r-1, h_)</td></tr>
196 <tr><td></td><td></td></tr>
197 <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_)</td></tr>
198 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s<loc(h)</sub> ∑<sub>t>=loc(h)</sub> ∑<sub>r<loc(h)</sub> c(s,t,h_) * c(r+1, t, h_)</td></tr>
199 </tbody>
200 </table>
202 t >= loc(h) since there are many possibilites for right-attachments
203 below, and each of them alone gives a lower probability (through
204 multiplication) to the upper tree (so add them all)
206 <p>
208 have to make sure they are contiguous (otherwise we would have no way
211 </p>
212 </div>
219 "det nn vbd", there are two ways in which 'det' could be left
220 attached; one is where it is attached non-adjacently (after 'vbd' has
221 attached 'nn'):
222 <pre>
224 >>> c_L
225 0.62669683257918563 # so far so good
228 >>> c_R
229 0.11312217194570134 # still seeems an OK probability
232 >>> c_M
233 0.31674208144796384 # and this seems good
235 >>> c_L / (c_R * c_M)
236 17.490571428571432 # but this is Way off...
237 </pre>
238 </p>
239 </div>
240 </div>
242 </div>
245 <h3 id="sec-2.3">2.3 <span class="done">DONE</span> P_STOP formulas for various dir and adj:</h3>
248 <p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-15 Sun 23:40</span><br/>
249 Assuming this:
250 </p>
253 <tbody>
254 <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>
255 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s<loc(h)</sub> ∑<sub>t>=loc(h)</sub> c(s,t,h_)</td></tr>
256 <tr><td></td><td></td></tr>
257 <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>
258 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t>=loc(h)</sub> c(s,t,h_)</td></tr>
259 <tr><td></td><td></td></tr>
260 <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>
261 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t>loc(h)</sub> c(s,t,h)</td></tr>
262 <tr><td></td><td></td></tr>
263 <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>
264 <tr><td></td><td>∑<sub>corpus</sub> ∑<sub>s=loc(h)</sub> ∑<sub>t=loc(h)</sub> c(s,t,h)</td></tr>
265 </tbody>
266 </table>
269 <p>
271 </p></div>
272 </div>
274 </div>
280 <p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-12 Thu 11:11</span><br/>
282 There are 6 different configurations here, based on what the above
283 (mother) node is, and what the Node for which we're computing is.
284 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>
286 of the mother of Node.
287 </p>
288 <ul>
289 <li>
290 mother is a RIGHT-stop:
291 <ul>
292 <li>
294 </li>
295 <li>
297 </li>
298 </ul>
299 </li>
300 <li>
301 mother is a LEFT-stop:
302 <ul>
303 <li>
305 </li>
306 <li>
309 </li>
310 </ul>
311 </li>
312 <li>
313 Node is on the LEFT branch (mom.L == Node)
314 <ul>
315 <li>
316 and mother is a LEFT attachment:
317 <ul>
318 <li>
320 </li>
321 <li>
324 </li>
325 <li>
327 </li>
328 <li>
330 </li>
331 </ul>
332 </li>
333 <li>
334 and mother is a RIGHT attachment:
335 <ul>
336 <li>
338 </li>
339 <li>
342 </li>
343 <li>
345 </li>
346 <li>
349 </li>
350 </ul>
351 </li>
352 </ul>
353 </li>
354 <li>
355 Node is on the RIGHT branch (mom.R == Node)
356 <ul>
357 <li>
358 and mother is a LEFT attachment:
359 <ul>
360 <li>
362 </li>
363 <li>
366 </li>
367 <li>
369 </li>
370 <li>
372 </li>
373 </ul>
374 </li>
375 <li>
376 and mother is a RIGHT attachment:
377 <ul>
378 <li>
380 </li>
381 <li>
384 </li>
385 <li>
387 </li>
388 <li>
391 </li>
392 </ul>
393 </li>
394 </ul>
395 </li>
396 </ul>
399 </p>
400 <p>
401 <pre>
402 in notes: in code (constants): in Klein thesis:
403 -------------------------------------------------------------------
404 _h_ SEAL bar over h
405 h_ RGO_L right-under-left-arrow over h
406 h GO_R right-arrow over h
408 LGO_R left-under-right-arrow over h
409 GO_L left-arrow over h
410 </pre>
411 </p>
412 <p>
413 Also, unlike in <a href="http://bibsonomy.org/bibtex/2b9f6798bb092697da7042ca3f5dee795">Lari & Young</a>, non-ROOT ('S') symbols may cover the
415 sentence.
416 </p>
418 </div>
420 </div>
423 <h2 id="sec-4">4 <span class="todo">TOGROK</span> Find Most Probable Parse of given test sentence</h2>
426 <p>We could probably do it pretty easily from the chart:
427 </p><ul>
428 <li>
429 for all loc_h, select the (0,len(sent),ROOT,loc_h) that has the highest p
430 </li>
431 <li>
432 for stops, just keep going
433 </li>
434 <li>
435 for rewrites, for loc_dep select the one that has the highest p
436 </li>
437 </ul>
438 </div>
440 </div>
446 <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.
447 </p>
448 </div>
451 <h3 id="sec-5.1">5.1 <span class="todo">TODO</span> Make inner() and outer() also allow left-first attachment</h3>
455 </p></div>
456 </div>
458 </div>
461 <h2 id="sec-6">6 <span class="todo">TODO</span> Get a dependency parsed version of WSJ to test with</h2>
464 </div>
466 </div>
473 </p>
474 <p>
475 We go through the corpus, since the probabilities are based on how far
476 away in the sentence arguments are from their heads.
477 </p>
478 </div>
485 </p></div>
487 </div>
490 <h3 id="sec-7.2">7.2 <span class="done">DONE</span> Separate initialization to another file? <span class="tag">PRETTIER</span></h3>
493 <p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-06-08 Sun 12:51</span><br/>
495 </p></div>
497 </div>
503 <p>(from initialization frequency)
504 </p></div>
506 </div>
512 <p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-05-27 Tue 20:04</span><br/>
513 </p>
514 </div>
521 the sentence [det nn vb nn] is
522 <pre>
523 f_{STOP}( STOP|det, L, adj) +1
524 f_{STOP}(-STOP|det, L, adj) +0
525 f_{STOP}( STOP|det, L, non_adj) +1
526 f_{STOP}(-STOP|det, L, non_adj) +0
527 f_{STOP}( STOP|det, R, adj) +0
528 f_{STOP}(-STOP|det, R, adj) +1
530 f_{STOP}( STOP|nn, L, adj) +0
531 f_{STOP}(-STOP|nn, L, adj) +1
532 f_{STOP}( STOP|nn, L, non_adj) +1 # since there's at least one to the left
533 f_{STOP}(-STOP|nn, L, non_adj) +0
534 </pre>
535 </p><ul>
537 <pre>
540 f[head, 'STOP', 'LA'] += (i_h == 0) # very first word
541 f[head, '-STOP', 'LA'] += (not i_h == 0)
544 f[head, 'STOP', 'RA'] += (i_h == n - 1) # very last word
545 f[head, '-STOP', 'RA'] += (not i_h == n - 1)
546 </pre>
547 vs
548 <pre>
549 # this one requires some additional rewriting since it
550 # introduces divisions by zero
551 f[head, 'STOP', 'LN'] += (i_h == 1) # second word
553 f[head, 'STOP', 'LA'] += (i_h == 0) # first word
554 f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
555 f[head, 'STOP', 'RN'] += (i_h == n - 2) # second-to-last
557 f[head, 'STOP', 'RA'] += (i_h == n - 1) # last word
558 f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
559 </pre>
560 vs
561 <pre>
562 f[head, 'STOP', 'LN'] += (i_h == 1) # second word
563 f[head, '-STOP', 'LN'] += (not i_h == 1) # not second
564 f[head, 'STOP', 'LA'] += (i_h == 0) # first word
565 f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
566 f[head, 'STOP', 'RN'] += (i_h == n - 2) # second-to-last
567 f[head, '-STOP', 'RN'] += (not i_h == n - 2) # not second-to-last
568 f[head, 'STOP', 'RA'] += (i_h == n - 1) # last word
569 f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
570 </pre>
571 vs
572 "all words take the same number of arguments" interpreted as
573 <pre>
574 for all heads:
575 p_STOP(head, 'STOP', 'LN') = 0.3
576 p_STOP(head, 'STOP', 'LA') = 0.5
577 p_STOP(head, 'STOP', 'RN') = 0.4
578 p_STOP(head, 'STOP', 'RA') = 0.7
579 </pre>
580 (which we easily may tweak in init_zeros())
581 </li>
582 </ul>
583 </div>
585 </div>
591 <p>Go through the corpus, counting distances between heads and
592 arguments. In [det nn vb nn], we give
593 </p><ul>
594 <li>
596 </li>
597 <li>
599 </li>
600 <li>
602 <ul>
603 <li>
607 </li>
608 </ul>
609 </li>
610 </ul>
614 just a frequency count of the corpus…
615 </p>
616 <p>
618 rewrite to an 'h' anyway (it's just a check for whether, at this
619 location in the sentence, we have the right POS-tag).
620 </p></div>
621 </div>
622 </div>
624 </div>
630 <p><a href="http://wiki.python.org/moin/PythonSpeed/PerformanceTips">http://wiki.python.org/moin/PythonSpeed/PerformanceTips</a> Eg., use
631 map/reduce/filter/[i for i in [i's]]/(i for i in [i's]) instead of
632 for-loops; use local variables for globals (global variables or or
633 functions), etc.
634 </p>
636 </div>
639 <h3 id="sec-8.1">8.1 <span class="todo">TODO</span> when reestimating P_STOP etc, remove rules with p < epsilon <span class="tag">OPTIMIZE</span></h3>
642 </div>
644 </div>
647 <h3 id="sec-8.2">8.2 <span class="todo">TODO</span> inner_dmv, short ranges and impossible attachment <span class="tag">OPTIMIZE</span></h3>
651 with both Lattach=True and Rattach=True.
652 </p>
653 <p>
655 Lattach=False, Rattach=False.
656 </p>
657 <p>
658 Put this in the loop under rewrite rules (could also do it in the STOP
659 section, but that would only have an effect on very short sentences).
660 </p></div>
662 </div>
665 <h3 id="sec-8.3">8.3 <span class="todo">TODO</span> clean up the module files <span class="tag">PRETTIER</span></h3>
668 <p>Is there better way to divide dmv and harmonic? There's a two-way
669 dependency between the modules. Guess there could be a third file that
670 imports both the initialization and the actual EM stuff, while a file
671 containing constants and classes could be imported by all others:
672 <pre>
673 dmv.py imports dmv_EM.py imports dmv_classes.py
674 dmv.py imports dmv_inits.py imports dmv_classes.py
675 </pre>
676 </p>
677 </div>
679 </div>
682 <h3 id="sec-8.4">8.4 <span class="todo">TOGROK</span> Some (tagged) sentences are bound to come twice <span class="tag">OPTIMIZE</span></h3>
685 <p>Eg, first sort and count, so that the corpus
686 [['nn','vbd','det','nn'],
687 ['vbd','nn','det','nn'],
688 ['nn','vbd','det','nn']]
689 becomes
690 [(['nn','vbd','det','nn'],2),
691 (['vbd','nn','det','nn'],1)]
692 and then in each loop through sentences, make sure we handle the
693 frequency correctly.
694 </p>
695 <p>
696 Is there much to gain here?
697 </p>
698 </div>
700 </div>
703 <h3 id="sec-8.5">8.5 <span class="todo">TOGROK</span> tags as numbers or tags as strings? <span class="tag">OPTIMIZE</span></h3>
706 <p>Need to clean up the representation.
707 </p>
708 <p>
709 Stick with tag-strings in initialization then switch to numbers for
710 IO-algorithm perhaps? Can probably afford more string-matching in
711 initialization..
712 </p></div>
713 </div>
715 </div>
721 <p>Each DMV_Rule has both a probN and a probA, for adjacencies. inner()
722 and outer() needs the correct one in each case.
723 </p>
724 <p>
725 In each inner() call, loc_h is the location of the head of this
727 the structure we're looking outside of.
728 </p>
729 <p>
730 We call inner() for each location of a head, and on each terminal,
731 loc_h must equal s (and t). In the recursive attachment calls, we use
732 the locations (sentence indices) of words to the left or right of the
734 </p>
735 </div>
742 in the current direction yet. One could also make a stronger type of
743 adjacency, where h and a are not adjacent if b is in between, eg. with
745 K&M-adjacent to a, but not next to a, since b is in between. It's easy
746 to check this type of adjacency in inner(), but it needs new rules for
747 P_STOP reestimation.
748 </p></div>
749 </div>
751 </div>
757 <p>outer(s,t,Node) and inner(s,t,Node) calculates the expected number of
759 the P_STOP and P_CHOOSE values, which have been conveniently
760 distributed into CNF rules as probN and probA (non-adjacent and
761 adjacent probabilites).
762 </p>
763 <p>
764 When re-estimating, we use the expected values from outer() and
765 inner() to get new values for P_STOP and P_CHOOSE. When we've
766 re-estimated for the entire corpus, we distribute P_STOP and P_CHOOSE
767 into the CNF rules again, so that in the next round we use new probN
768 and probA to find outer- and inner-probabilites.
769 </p>
770 <p>
771 The distribution of P_STOP and P_CHOOSE into CNF rules also happens in
772 init_normalize() (here along with the creation of P_STOP and
773 P_CHOOSE); P_STOP is used to create CNF rules where one branch of the
774 rule is STOP, P_CHOOSE is used to create rules of the form
775 <pre>
776 h -> h _a_
777 h_ -> h_ _a_
778 </pre>
779 </p>
780 <p>
781 Since "adjacency" is not captured in regular CNF rules, we need two
782 probabilites for each rule, and outer() and inner() have to know when
783 to use which.
784 </p>
786 </div>
788 </div>
794 <p>Make those debug statements steal a bit less attention in emacs:
795 <pre>
796 (font-lock-add-keywords
797 'python-mode ; not really regexp, a bit slow
798 '(("^\\( *\\)\\(\\if +'.+' +in +io.DEBUG. *\\(
800 (font-lock-add-keywords
801 'python-mode
803 </pre>
804 </p>
805 <ul>
806 <li>
808 </li>
809 <li>
810 <a href="http://nltk.org/doc/en/structured-programming.html">http://nltk.org/doc/en/structured-programming.html</a> recursive dynamic
811 </li>
812 <li>
813 <a href="http://nltk.org/doc/en/advanced-parsing.html">http://nltk.org/doc/en/advanced-parsing.html</a>
814 </li>
815 <li>
816 <a href="http://jaynes.colorado.edu/PythonIdioms.html">http://jaynes.colorado.edu/PythonIdioms.html</a>
820 </li>
821 </ul>
822 </div>
824 </div>
830 <p>Repository web page: <a href="http://repo.or.cz/w/dmvccm.git">http://repo.or.cz/w/dmvccm.git</a>
831 </p>
832 <p>
833 Setting up a new project:
834 <pre>
835 git init
836 git add .
837 git commit -m "first release"
838 </pre>
839 </p>
840 <p>
842 <pre>
843 git init
844 git commit -a -m "some subsequent release"
845 </pre>
846 </p>
847 <p>
848 Then push stuff up to the remote server:
849 <pre>
850 git push git+ssh://username@repo.or.cz/srv/git/dmvccm.git master
851 </pre>
852 </p>
853 <p>
854 (<code>eval `ssh-agent`</code> and <code>ssh-add</code> to avoid having to type in keyphrase all
855 the time)
856 </p>
857 <p>
858 Make a copy of the (remote) master branch:
859 <pre>
860 git clone git://repo.or.cz/dmvccm.git
861 </pre>
862 </p>
863 <p>
864 Make and name a new branch in this folder
865 <pre>
866 git checkout -b mybranch
867 </pre>
868 </p>
869 <p>
871 <pre>
872 git commit -a
873 </pre>
874 </p>
875 <p>
877 carried over):
878 <pre>
879 git checkout master
880 </pre>
881 </p>
882 <p>
883 Try out:
884 <pre>
885 git add --interactive
886 </pre>
887 </p>
888 <p>
889 Good tutorial:
890 <a href="http://www-cs-students.stanford.edu/~blynn//gitmagic/">http://www-cs-students.stanford.edu/~blynn//gitmagic/</a>
891 </p></div>
892 </div>
894 <a href="mailto:K.BrubeckUnhammer at student uva nl "><K.BrubeckUnhammer at student uva nl ></a>
895 </p>
897 </div><p class="postamble">Skrive vha. emacs + <a href='http://orgmode.org/'>org-mode</a></p></body>
898 </html>