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">
6 <title>DMV/CCM
– 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/08/01 21:56:44"/>
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 <!-- override with local style.css: -->
13 <link rel=
"stylesheet" type=
"text/css" href=
"./style.css">
15 <script type=
"text/Javascript">
16 function toggleSemester (semID) {
17 var sem = document.getElementById(semID);
19 for(i=
0;i
<cN.length;i++){
20 if (cN[i].className==
"outline-4") {
21 cN[i].
className=
"outline-4-hidden";
23 else if(cN[i].className==
"outline-4-hidden") {
24 cN[i].
className=
"outline-4";
30 <h1 class=
"title">DMV/CCM
– todo-list / progress
</h1>
31 <div id=
"table-of-contents">
32 <h2>Table of Contents
</h2>
33 <div id=
"text-table-of-contents">
35 <li><a href=
"#sec-1">1 DMV/CCM report and project
</a></li>
36 <li><a href=
"#sec-2">2 Notation
</a></li>
37 <li><a href=
"#sec-3">3 Testing the dependency parsed WSJ
</a>
39 <li><a href=
"#sec-3.1">3.1 [#A] Should
<code>def evaluate
</code> use add_root?
</a></li>
42 <li><a href=
"#sec-4">4 [#C] Alternative CNF for DMV
</a>
44 <li><a href=
"#sec-4.1">4.1 Do we use special P_ROOT rules?
</a></li>
45 <li><a href=
"#sec-4.2">4.2 complete programming the dmv2cnf versions of dmv.py and harmonic.py
</a></li>
46 <li><a href=
"#sec-4.3">4.3 move as much as possible into common_dmv.py
</a></li>
47 <li><a href=
"#sec-4.4">4.4 dmv2cnf re-estimation formulas
</a></li>
48 <li><a href=
"#sec-4.5">4.5 dmv2cnf IO formulas
</a></li>
51 <li><a href=
"#sec-5">5 Combine CCM with DMV
</a></li>
52 <li><a href=
"#sec-6">6 Reestimate P_ORDER ?
</a></li>
53 <li><a href=
"#sec-7">7 Most Probable Parse
</a>
55 <li><a href=
"#sec-7.1">7.1 Find MPP with CCM
</a></li>
56 <li><a href=
"#sec-7.2">7.2 Find Most Probable Parse of given test sentence, in DMV
</a></li>
59 <li><a href=
"#sec-8">8 Initialization
</a>
61 <li><a href=
"#sec-8.1">8.1 CCM Initialization
</a></li>
64 <li><a href=
"#sec-9">9 [#C] Deferred
</a>
66 <li><a href=
"#sec-9.1">9.1 Clean up reestimation code
</a></li>
67 <li><a href=
"#sec-9.2">9.2 [#A] compare speed of w_left/right(
…) and w(LEFT/RIGHT,
…)
</a></li>
68 <li><a href=
"#sec-9.3">9.3 when reestimating P_STOP etc, remove rules with p
< epsilon
</a></li>
69 <li><a href=
"#sec-9.4">9.4 inner_dmv, short ranges and impossible attachment
</a></li>
70 <li><a href=
"#sec-9.5">9.5 clean up the module files
</a></li>
71 <li><a href=
"#sec-9.6">9.6 Some (tagged) sentences are bound to come twice
</a></li>
72 <li><a href=
"#sec-9.7">9.7 tags as numbers or tags as strings?
</a></li>
75 <li><a href=
"#sec-10">10 Adjacency and combining it with the inside-outside algorithm
</a>
77 <li><a href=
"#sec-10.1">10.1 Possible alternate type of adjacency
</a></li>
80 <li><a href=
"#sec-11">11 Python-stuff
</a></li>
81 <li><a href=
"#sec-12">12 Git
</a></li>
86 <div id=
"outline-container-1" class=
"outline-2">
87 <h2 id=
"sec-1">1 DMV/CCM report and project
</h2>
92 DMV-
<a href=
"tex/formulas.pdf">formulas.pdf
</a> – <i>clear
</i> information =D
95 <a href=
"src/main.py">main.py
</a> – evaluation
98 <a href=
"src/wsjdep.py">wsjdep.py
</a> – corpus
101 <a href=
"src/loc_h_dmv.py">loc_h_dmv.py
</a> – DMV-IO and reestimation
104 <a href=
"src/loc_h_harmonic.py">loc_h_harmonic.py
</a> – DMV initialization
107 <a href=
"src/common_dmv.py">common_dmv.py
</a> – various functions used by loc_h_dmv and others
110 <a href=
"src/io.py">io.py
</a> – non-DMV IO
116 <p><a href=
"http://www.student.uib.no/~kun041/dmvccm/DMVCCM_archive.html">Archived entries
</a> from this file.
121 <div id=
"outline-container-2" class=
"outline-2">
122 <h2 id=
"sec-2">2 Notation
</h2>
126 old notes: new notes: in tex/code (constants): in Klein thesis:
127 --------------------------------------------------------------------------------------
128 _h_ _h_ SEAL bar over h
129 h_ h
>< RGOL right-under-left-arrow over h
130 h h
> GOR right-arrow over h
132 ><h LGOR left-under-right-arrow over h
133 <h GOL left-arrow over h
135 These are represented in the code as pairs
<code>(s_h,h)
</code>, where
<code>h
</code> is an
136 integer (POS-tag) and
<code>s_h
</code> ∈ <code>{SEAL,RGOL,GOR,LGOR,GOL}
</code>.
139 <code>P_ATTACH
</code> and
<code>P_CHOOSE
</code> are synonymous, I try to use the
142 P_GO_AT(a|h,dir,adj) := P_ATTACH(a|h,dir)*(
1-P_STOP(STOP|h,dir,adj)
146 (precalculated after each reestimation with
<code>g.p_GO_AT = make_GO_AT(g.p_STOP,g.p_ATTACH)
</code>)
152 <div id=
"outline-container-3" class=
"outline-2">
153 <h2 id=
"sec-3">3 Testing the dependency parsed WSJ
</h2>
156 <p><a href=
"src/wsjdep.py">wsjdep.py
</a> uses NLTK (sort of) to get a dependency parsed version of
157 WSJ10 into the format used in mpp() in loc_h_dmv.py.
160 As a default,
<code>WSJDepCorpusReader
</code> looks for the file
<code>wsj.combined
.10.dep
</code> in
161 <code>../corpus/wsjdep
</code>.
164 Only
<code>sents()
</code>,
<code>tagged_sents()
</code> and
<code>parsed_sents()
</code> (plus a new function
165 <code>tagonly_sents()
</code>) are implemented, the other NLTK corpus functions are
166 ..um.. undefined
…
170 <div id=
"outline-container-3.1" class=
"outline-3">
171 <h3 id=
"sec-3.1">3.1 <span class=
"todo">TODO
</span> [#A] Should
<code>def evaluate
</code> use add_root?
</h3>
174 <p><a href=
"src/main.py">main.py
</a> evaluate
175 <a href=
"src/wsjdep.py">wsjdep.py
</a> add_root
178 (just has to count how many pairs are in there; Precision and Recall)
184 <div id=
"outline-container-4" class=
"outline-2">
185 <h2 id=
"sec-4">4 <span class=
"todo">TODO
</span> [#C] Alternative CNF for DMV
</h2>
190 <a name=
"dmv2cnf"> </a>
193 <a href=
"src/cnf_dmv.py">cnf_dmv.py
</a>
196 <a href=
"src/cnf_harmonic.py">cnf_harmonic.py
</a>
201 <p>See section
5 of
<a href=
"tex/formulas.pdf">formulas.pdf
</a>.
204 Given a grammar with certain p_ATTACH, p_STOP and p_ROOT, we get:
206 >>> print testgrammar_h():
207 h
>< --
> h
> STOP [
0.30]
208 h
>< --
> >h
> STOP [
0.40]
209 _h_ --
> STOP h
>< [
1.00]
210 _h_ --
> STOP
<h
>< [
1.00]
211 >h
> --
> h
> _h_ [
1.00]
212 >h
> --
> >h
> _h_ [
1.00]
213 <h
>< --
> _h_ h
>< [
0.70]
214 <h
>< --
> _h_
<h
>< [
0.60]
215 ROOT --
> STOP _h_ [
1.00]
222 <div id=
"outline-container-4.1" class=
"outline-3">
223 <h3 id=
"sec-4.1">4.1 <span class=
"todo">TOGROK
</span> Do we use special P_ROOT rules?
</h3>
226 <p>P
<sub>ROOT
</sub> doesn't care about adjacency anyway, so I guess it doesn't
227 matter if we just sum over all head
<b>types
</b> in a sentence.
235 <div id=
"outline-container-4.2" class=
"outline-3">
236 <h3 id=
"sec-4.2">4.2 <span class=
"todo">TODO
</span> complete programming the dmv2cnf versions of dmv.py and harmonic.py
</h3>
243 <div id=
"outline-container-4.3" class=
"outline-3">
244 <h3 id=
"sec-4.3">4.3 <span class=
"todo">TODO
</span> move as much as possible into common_dmv.py
</h3>
247 <p><a href=
"src/common_dmv.py">common_dmv.py
</a>
250 …and improve cnf vs loc_h classes (at
<i>least
</i> give them different names)
255 <div id=
"outline-container-4.4" class=
"outline-3">
256 <h3 id=
"sec-4.4">4.4 <span class=
"todo">TODO
</span> dmv2cnf re-estimation formulas
</h3>
259 <p><a href=
"tex/formulas.tex">tex
</a>
262 The reestimation function still has to sum over the various
263 possibilities of N's and A's; but it seems to be simpler than the
264 loc_h-method altogether.
267 Question: Would it be the same thing to reestimate using completely
268 regular IO reestimation?
273 <div id=
"outline-container-4.5" class=
"outline-3">
274 <h3 id=
"sec-4.5">4.5 <span class=
"done">DONE
</span> dmv2cnf IO formulas
</h3>
277 <p><span class=
"timestamp-kwd">CLOSED:
</span> <span class=
"timestamp">2008-
07-
30 Wed
00:
40</span><br/>
283 <div id=
"outline-container-5" class=
"outline-2">
284 <h2 id=
"sec-5">5 <span class=
"todo">TOGROK
</span> Combine CCM with DMV
</h2>
289 <a name=
"comboquestions"> </a>
292 Questions about the
<code>P_COMBO
</code> info in
<a href=
"http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf">Klein's thesis
</a>:
295 Page
109 (pdf:
125): We have to premultiply
"all our probabilities"
296 by the CCM base product
<i>Π<sub><i,j
></sub> P
<sub>SPAN
</sub>(
α(i,j,s)|false)P
<sub>CONTEXT
</sub>(
β(i,j,s)|false)
</i>; which
297 probabilities are included under
"all"? I'm assuming this includes
298 <code>P_ATTACH
</code> since each time
<code>P_ATTACH
</code> is used,
<i>φ</i> is multiplied in
299 (pp
.110-
111 ibid.); but
<i>φ</i> is not used for STOPs, so should we not
300 have our CCM product multiplied in there? How about
<code>P_ROOT
</code>?
301 (Guessing
<code>P_ORDER
</code> is way out of the question
…)
304 For the outside probabilities, is it correct to assume we multiply
305 in
<i>φ(j,k)
</i> or
<i>φ(k,i)
</i> when calculating
<code>inner(i,j...)
</code>? (Eg., only
306 for the outside part, not for the whole range.) I don't understand
307 the notation in
<code>O()
</code> on p
.103.
314 <div id=
"outline-container-6" class=
"outline-2">
315 <h2 id=
"sec-6">6 <span class=
"todo">TOGROK
</span> Reestimate P_ORDER ?
</h2>
322 <div id=
"outline-container-7" class=
"outline-2">
323 <h2 id=
"sec-7">7 Most Probable Parse
</h2>
329 <div id=
"outline-container-7.1" class=
"outline-3">
330 <h3 id=
"sec-7.1">7.1 <span class=
"todo">TOGROK
</span> Find MPP with CCM
</h3>
337 <div id=
"outline-container-7.2" class=
"outline-3">
338 <h3 id=
"sec-7.2">7.2 <span class=
"done">DONE
</span> Find Most Probable Parse of given test sentence, in DMV
</h3>
341 <p><span class=
"timestamp-kwd">CLOSED:
</span> <span class=
"timestamp">2008-
07-
23 Wed
10:
56</span><br/>
342 inner() optionally keeps track of the highest probability children of
343 any node in
<code>mpptree
</code>. Say we're looking for
<code>inner(i,j,(s_h,h),loc_h)
</code> in
344 a certain sentence, and we find some possible left and right children,
345 we add to
<code>mpptree[i,j,(s_h,h),loc_h]
</code> the triple
<code>(p, L, R)
</code> where
<code>L
</code> and
346 <code>R
</code> are of the same form as the key (
<code>i,j,(s_h,h),loc_h
</code>) and
<code>p
</code> is the
347 probability of this node rewriting to
<code>L
</code> and
<code>R
</code>,
348 eg.
<code>inner(L)*inner(R)*p_GO_AT
</code> or
<code>p_STOP
</code> or whatever. We only add this
349 entry to
<code>mpptree
</code> if there wasn't a higher-probability entry there
353 Then, after
<code>inner_sent
</code> makes an
<code>mpptree
</code>, we find the
<i>relevant
</i>
354 head-argument pairs by searching through the tree using a queue,
355 adding the
<code>L
</code> and
<code>R
</code> keys of any entry to the queue as we find them
356 (skipping
<code>STOP
</code> keys), and adding any attachment entries to a set of
357 triples
<code>(head,argument,dir)
</code>. Thus we have our most probable parse,
360 set([( ROOT, (vbd,
2),RIGHT),
361 ((vbd,
2),(nn,
1),LEFT),
362 ((vbd,
2),(nn,
3),RIGHT),
363 ((nn,
1),(det,
0),LEFT)])
370 <div id=
"outline-container-8" class=
"outline-2">
371 <h2 id=
"sec-8">8 Initialization
</h2>
374 <p><a href=
"/Users/kiwibird/Documents/Skole/V08/Probability/dmvccm/src/dmv.py">dmv-inits
</a>
377 We go through the corpus, since the probabilities are based on how far
378 away in the sentence arguments are from their heads.
382 <div id=
"outline-container-8.1" class=
"outline-3">
383 <h3 id=
"sec-8.1">8.1 <span class=
"todo">TOGROK
</span> CCM Initialization
</h3>
386 <p>P
<sub>SPLIT
</sub> used here
… how, again?
392 <div id=
"outline-container-9" class=
"outline-2">
393 <h2 id=
"sec-9">9 [#C] Deferred
</h2>
396 <p><a href=
"http://wiki.python.org/moin/PythonSpeed/PerformanceTips">http://wiki.python.org/moin/PythonSpeed/PerformanceTips
</a> Eg., use
397 map/reduce/filter/[i for i in [i's]]/(i for i in [i's]) instead of
398 for-loops; use local variables for globals (global variables or or
403 <div id=
"outline-container-9.1" class=
"outline-3">
404 <h3 id=
"sec-9.1">9.1 <span class=
"todo">TODO
</span> Clean up reestimation code
<span class=
"tag">PRETTIER
</span></h3>
411 <div id=
"outline-container-9.2" class=
"outline-3">
412 <h3 id=
"sec-9.2">9.2 <span class=
"todo">TODO
</span> [#A] compare speed of w_left/right(
…) and w(LEFT/RIGHT,
…)
<span class=
"tag">OPTIMIZE
</span></h3>
419 <div id=
"outline-container-9.3" class=
"outline-3">
420 <h3 id=
"sec-9.3">9.3 <span class=
"todo">TODO
</span> when reestimating P_STOP etc, remove rules with p
< epsilon
<span class=
"tag">OPTIMIZE
</span></h3>
427 <div id=
"outline-container-9.4" class=
"outline-3">
428 <h3 id=
"sec-9.4">9.4 <span class=
"todo">TODO
</span> inner_dmv, short ranges and impossible attachment
<span class=
"tag">OPTIMIZE
</span></h3>
431 <p>If s-t
<=
2, there can be only one attachment below, so don't recurse
432 with both Lattach=True and Rattach=True.
435 If s-t
<=
1, there can be no attachment below, so only recurse with
436 Lattach=False, Rattach=False.
439 Put this in the loop under rewrite rules (could also do it in the STOP
440 section, but that would only have an effect on very short sentences).
445 <div id=
"outline-container-9.5" class=
"outline-3">
446 <h3 id=
"sec-9.5">9.5 <span class=
"todo">TODO
</span> clean up the module files
<span class=
"tag">PRETTIER
</span></h3>
449 <p>Is there better way to divide dmv and harmonic? There's a two-way
450 dependency between the modules. Guess there could be a third file that
451 imports both the initialization and the actual EM stuff, while a file
452 containing constants and classes could be imported by all others:
454 dmv.py imports dmv_EM.py imports dmv_classes.py
455 dmv.py imports dmv_inits.py imports dmv_classes.py
462 <div id=
"outline-container-9.6" class=
"outline-3">
463 <h3 id=
"sec-9.6">9.6 <span class=
"todo">TOGROK
</span> Some (tagged) sentences are bound to come twice
<span class=
"tag">OPTIMIZE
</span></h3>
466 <p>Eg, first sort and count, so that the corpus
467 [['nn','vbd','det','nn'],
468 ['vbd','nn','det','nn'],
469 ['nn','vbd','det','nn']]
471 [(['nn','vbd','det','nn'],
2),
472 (['vbd','nn','det','nn'],
1)]
473 and then in each loop through sentences, make sure we handle the
477 Is there much to gain here?
483 <div id=
"outline-container-9.7" class=
"outline-3">
484 <h3 id=
"sec-9.7">9.7 <span class=
"todo">TOGROK
</span> tags as numbers or tags as strings?
<span class=
"tag">OPTIMIZE
</span></h3>
487 <p>Need to clean up the representation.
490 Stick with tag-strings in initialization then switch to numbers for
491 IO-algorithm perhaps? Can probably afford more string-matching in
498 <div id=
"outline-container-10" class=
"outline-2">
499 <h2 id=
"sec-10">10 Adjacency and combining it with the inside-outside algorithm
</h2>
502 <p>Each DMV_Rule has both a probN and a probA, for adjacencies. inner()
503 and outer() needs the correct one in each case.
506 In each inner() call, loc_h is the location of the head of this
507 dependency structure. In each outer() call, it's the head of the
<i>Node
</i>,
508 the structure we're looking outside of.
511 We call inner() for each location of a head, and on each terminal,
512 loc_h must equal
<code>i
</code> (and
<code>loc_h+
1</code> equal
<code>j
</code>). In the recursive attachment
513 calls, we use the locations (sentence indices) of words to the left or
514 right of the head in calls to inner().
<i>loc_h lets us check whether we need probN or probA
</i>.
518 <div id=
"outline-container-10.1" class=
"outline-3">
519 <h3 id=
"sec-10.1">10.1 Possible alternate type of adjacency
</h3>
522 <p>K
&M's adjacency is just whether or not an argument has been generated
523 in the current direction yet. One could also make a stronger type of
524 adjacency, where h and a are not adjacent if b is in between, eg. with
525 the sentence
"a b h" and the structure ((h-
>a), (a-
>b)), h is
526 K
&M-adjacent to a, but not next to a, since b is in between. It's easy
527 to check this type of adjacency in inner(), but it needs new rules for
534 <div id=
"outline-container-11" class=
"outline-2">
535 <h2 id=
"sec-11">11 Python-stuff
</h2>
538 <p>Make those debug statements steal a bit less attention in emacs:
540 (font-lock-add-keywords
541 'python-mode ; not really regexp, a bit slow
542 '((
"^\\( *\\)\\(\\if +'.+' +in +io.DEBUG. *\\(
543 \\1 .+$\\)+\\)" 2 font-lock-preprocessor-face t)))
544 (font-lock-add-keywords
546 '((
"\\<\\(\\(io\\.\\)?debug(.+)\\)" 1 font-lock-preprocessor-face t)))
551 <a href=
"src/pseudo.py">pseudo.py
</a>
554 <a href=
"http://nltk.org/doc/en/structured-programming.html">http://nltk.org/doc/en/structured-programming.html
</a> recursive dynamic
557 <a href=
"http://nltk.org/doc/en/advanced-parsing.html">http://nltk.org/doc/en/advanced-parsing.html
</a>
560 <a href=
"http://jaynes.colorado.edu/PythonIdioms.html">http://jaynes.colorado.edu/PythonIdioms.html
</a>
570 <div id=
"outline-container-12" class=
"outline-2">
571 <h2 id=
"sec-12">12 Git
</h2>
574 <p>Repository web page:
<a href=
"http://repo.or.cz/w/dmvccm.git">http://repo.or.cz/w/dmvccm.git
</a>
577 Setting up a new project:
581 git commit -m
"first release"
585 Later on: (
<code>-a
</code> does
<code>git rm
</code> and
<code>git add
</code> automatically)
588 git commit -a -m
"some subsequent release"
592 Then push stuff up to the remote server:
594 git push git+ssh://username@repo.or.cz/srv/git/dmvccm.git master
598 (
<code>eval `ssh-agent`
</code> and
<code>ssh-add
</code> to avoid having to type in keyphrase all
602 Make a copy of the (remote) master branch:
604 git clone git://repo.or.cz/dmvccm.git
608 Make and name a new branch in this folder
610 git checkout -b mybranch
614 To save changes in
<code>mybranch
</code>:
620 Go back to the master branch (uncommitted changes from
<code>mybranch
</code> are
629 git add --interactive
634 <a href=
"http://www-cs-students.stanford.edu/~blynn//gitmagic/">http://www-cs-students.stanford.edu/~blynn//gitmagic/
</a>
637 <div id=
"postamble"><p class=
"author"> Author: Kevin Brubeck Unhammer
638 <a href=
"mailto:K.BrubeckUnhammer at student uva nl "><K.BrubeckUnhammer at student uva nl
></a>
640 <p class=
"date"> Date:
2008/
08/
01 21:
56:
44</p>
641 </div><div class=
"post-postamble" id=
"nn-postamble">Skrive vha. emacs +
<a href='http://orgmode.org/'
>org-mode
</a></div></body>