?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
fixed a little bug in root reestimation (forgot to divide by len(corpus)=f_T_q(ROOT))
[dmvccm.git] / DMVCCM.html
blobd03cf89e3c4668aad07e73d1df11d83710bad67e
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-09-11 12:01:19 CEST"/>
10 <meta name="author" content="Kevin Brubeck Unhammer"/>
11 <style type="text/css">
12 html { font-family: Times, serif; font-size: 12pt; }
13 .title { text-align: center; }
14 .todo { color: red; }
15 .done { color: green; }
16 .tag { background-color:lightblue; font-weight:normal }
17 .target { }
18 .timestamp { color: grey }
19 .timestamp-kwd { color: CadetBlue }
20 p.verse { margin-left: 3% }
21 pre {
22 border: 1pt solid #AEBDCC;
23 background-color: #F3F5F7;
24 padding: 5pt;
25 font-family: courier, monospace;
26 font-size: 90%;
27 overflow:auto;
28 }
29 table { border-collapse: collapse; }
30 td, th { vertical-align: top; }
31 dt { font-weight: bold; }
32 </style><link rel="stylesheet" type="text/css" href="http://www.student.uib.no/~kun041/org.css">
33 <!-- override with local style.css: -->
34 <link rel="stylesheet" type="text/css" href="./style.css">
35 </head><body>
36 <h1 class="title">DMV/CCM &ndash; todo-list / progress</h1>
37 <div id="table-of-contents">
38 <h2>Table of Contents</h2>
39 <div id="text-table-of-contents">
40 <ul>
41 <li><a href="#sec-1">1 DMV/CCM report and project</a></li>
42 <li><a href="#sec-2">2 Notation</a></li>
43 <li><a href="#sec-3">3 Testing the dependency parsed WSJ</a>
44 <ul>
45 <li><a href="#sec-3.1">3.1 [#A] Should <code>def evaluate</code> use add_root?</a></li>
46 </ul>
47 </li>
48 <li><a href="#sec-4">4 Combine CCM with DMV</a></li>
49 <li><a href="#sec-5">5 Reestimate P_ORDER ?</a></li>
50 <li><a href="#sec-6">6 Most Probable Parse</a>
51 <ul>
52 <li><a href="#sec-6.1">6.1 Find MPP with CCM</a></li>
53 <li><a href="#sec-6.2">6.2 Find Most Probable Parse of given test sentence, in DMV</a></li>
54 </ul>
55 </li>
56 <li><a href="#sec-7">7 Initialization </a>
57 <ul>
58 <li><a href="#sec-7.1">7.1 CCM Initialization </a></li>
59 </ul>
60 </li>
61 <li><a href="#sec-8">8 [#C] Alternative CNF for DMV</a>
62 <ul>
63 <li><a href="#sec-8.1">8.1 [#A] Make and implement an equivalent grammar that's <i>pure</i> CNF</a></li>
64 <li><a href="#sec-8.2">8.2 [#A] convert L&amp;Y-based reestimation into P_ATTACH and P_STOP values</a></li>
65 <li><a href="#sec-8.3">8.3 [#C] move as much as possible into common_dmv.py</a></li>
66 <li><a href="#sec-8.4">8.4 L&amp;Y-based reestimation for cnf_dmv</a></li>
67 <li><a href="#sec-8.5">8.5 dmv2cnf re-estimation formulas</a></li>
68 <li><a href="#sec-8.6">8.6 inner and outer for cnf_dmv.py, also cnf_harmonic.py </a></li>
69 </ul>
70 </li>
71 <li><a href="#sec-9">9 [#C] Deferred</a>
72 <ul>
73 <li><a href="#sec-9.1">9.1 Clean up reestimation code</a></li>
74 <li><a href="#sec-9.2">9.2 [#A] compare speed of w_left/right(&hellip;) and w(LEFT/RIGHT, &hellip;)</a></li>
75 <li><a href="#sec-9.3">9.3 when reestimating P_STOP etc, remove rules with p &lt; epsilon</a></li>
76 <li><a href="#sec-9.4">9.4 inner_dmv, short ranges and impossible attachment</a></li>
77 <li><a href="#sec-9.5">9.5 clean up the module files</a></li>
78 <li><a href="#sec-9.6">9.6 Some (tagged) sentences are bound to come twice</a></li>
79 <li><a href="#sec-9.7">9.7 tags as numbers or tags as strings?</a></li>
80 </ul>
81 </li>
82 <li><a href="#sec-10">10 Adjacency and combining it with the inside-outside algorithm</a>
83 <ul>
84 <li><a href="#sec-10.1">10.1 Possible alternate type of adjacency</a></li>
85 </ul>
86 </li>
87 <li><a href="#sec-11">11 Python-stuff</a></li>
88 <li><a href="#sec-12">12 Git</a></li>
89 </ul>
90 </div>
91 </div>
92
93 <div id="outline-container-1" class="outline-2">
94 <h2 id="sec-1">1 DMV/CCM report and project</h2>
95 <div id="text-1">
96
97 <p><span class="timestamp-kwd">DEADLINE: </span> <span class="timestamp">2008-09-21 Sun</span><br/>
98 </p><ul>
99 <li>
100 DMV-<a href="tex/formulas.pdf">formulas.pdf</a> &ndash; <i>clear</i> information =D
101 </li>
102 <li>
103 <a href="src/main.py">main.py</a> &ndash; evaluation, corpus likelihoods
104 </li>
105 <li>
106 <a href="src/wsjdep.py">wsjdep.py</a> &ndash; corpus
107
108 </li>
109 <li>
110 <a href="src/loc_h_dmv.py">loc_h_dmv.py</a> &ndash; DMV-IO and reestimation
111 </li>
112 <li>
113 <a href="src/loc_h_harmonic.py">loc_h_harmonic.py</a> &ndash; DMV initialization
114
115 </li>
116 <li>
117 <a href="src/common_dmv.py">common_dmv.py</a> &ndash; various functions used by loc_h_dmv and others
118 </li>
119 <li>
120 <a href="src/io.py">io.py</a> &ndash; non-DMV IO
121
122 </li>
123 <li>
124 <a href="src/cnf_dmv.py">cnf_dmv.py</a> &ndash; cnf-like implementation of DMV
125 </li>
126 <li>
127 <a href="src/cnf_harmonic.py">cnf_harmonic.py</a> &ndash; initialization for cnf_dmv
128
129 </li>
130 </ul>
131
132 <p><a href="http://www.student.uib.no/~kun041/dmvccm/DMVCCM_archive.html">Archived entries</a> from this file.
133 </p></div>
134
135 </div>
136
137 <div id="outline-container-2" class="outline-2">
138 <h2 id="sec-2">2 Notation</h2>
139 <div id="text-2">
140
141 <p><pre class="example">
142 old notes: new notes: in tex/code (constants): in Klein thesis:
143 --------------------------------------------------------------------------------------
144 _h_ _h_ SEAL bar over h
145 h_ h&gt;&lt; RGOL right-under-left-arrow over h
146 h h&gt; GOR right-arrow over h
147
148 &gt;&lt;h LGOR left-under-right-arrow over h
149 &lt;h GOL left-arrow over h
150 </pre>
151 These are represented in the code as pairs <code>(s_h,h)</code>, where <code>h</code> is an
152 integer (POS-tag) and <code>s_h</code> &isin; <code>{SEAL,RGOL,GOR,LGOR,GOL}</code>.
153 </p>
154 <p>
155 <code>P_ATTACH</code> and <code>P_CHOOSE</code> are synonymous, I try to use the
156 former. Also,
157 <pre class="example">
158 P_GO_AT(a|h,dir,adj) := P_ATTACH(a|h,dir)*(1-P_STOP(STOP|h,dir,adj)
159 </pre>
160 </p>
161 <p>
162 (precalculated after each reestimation with <code>g.p_GO_AT = make_GO_AT(g.p_STOP,g.p_ATTACH)</code>)
163 </p>
164 </div>
165
166 </div>
167
168 <div id="outline-container-3" class="outline-2">
169 <h2 id="sec-3">3 Testing the dependency parsed WSJ</h2>
170 <div id="text-3">
171
172 <p><a href="src/wsjdep.py">wsjdep.py</a> uses NLTK (sort of) to get a dependency parsed version of
173 WSJ10 into the format used in mpp() in loc_h_dmv.py.
174 </p>
175 <p>
176 As a default, <code>WSJDepCorpusReader</code> looks for the file <code>wsj.combined.10.dep</code> in
177 <code>../corpus/wsjdep</code>.
178 </p>
179 <p>
180 Only <code>sents()</code>, <code>tagged_sents()</code> and <code>parsed_sents()</code> (plus a new function
181 <code>tagonly_sents()</code>) are implemented, the other NLTK corpus functions are
182 ..um.. undefined&hellip;
183 </p>
184 </div>
185
186 <div id="outline-container-3.1" class="outline-3">
187 <h3 id="sec-3.1">3.1 <span class="todo">TODO</span> [#A] Should <code>def evaluate</code> use add_root?</h3>
188 <div id="text-3.1">
189
190 <p><a href="src/main.py">main.py</a> evaluate
191 <a href="src/wsjdep.py">wsjdep.py</a> add_root
192 </p>
193 <p>
194 (just has to count how many pairs are in there; Precision and Recall)
195 </p></div>
196 </div>
197
198 </div>
199
200 <div id="outline-container-4" class="outline-2">
201 <h2 id="sec-4">4 <span class="todo">TOGROK</span> Combine CCM with DMV</h2>
202 <div id="text-4">
203
204
205 <p>
206 <a name="comboquestions">&nbsp;</a>
207 </p>
208 <p>
209 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>:
210 </p><ul>
211 <li>
212 Page 109 (pdf: 125): We have to premultiply "all our probabilities"
213 by the CCM base product <i>&Pi;<sub>&lt;i,j&gt;</sub> P<sub>SPAN</sub>(&alpha;(i,j,s)|false)P<sub>CONTEXT</sub>(&beta;(i,j,s)|false)</i>; which
214 probabilities are included under "all"? I'm assuming this includes
215 <code>P_ATTACH</code> since each time <code>P_ATTACH</code> is used, <i>&phi;</i> is multiplied in
216 (pp.110-111 ibid.); but <i>&phi;</i> is not used for STOPs, so should we not
217 have our CCM product multiplied in there? How about <code>P_ROOT</code>?
218 (Guessing <code>P_ORDER</code> is way out of the question&hellip;)
219 </li>
220 <li>
221 For the outside probabilities, is it correct to assume we multiply
222 in <i>&phi;(j,k)</i> or <i>&phi;(k,i)</i> when calculating <code>inner(i,j...)</code>? (Eg., only
223 for the outside part, not for the whole range.) I don't understand
224 the notation in <code>O()</code> on p.103.
225 </li>
226 </ul>
227 </div>
228
229 </div>
230
231 <div id="outline-container-5" class="outline-2">
232 <h2 id="sec-5">5 <span class="todo">TOGROK</span> Reestimate P_ORDER ?</h2>
233 <div id="text-5">
234
235 </div>
236
237 </div>
238
239 <div id="outline-container-6" class="outline-2">
240 <h2 id="sec-6">6 Most Probable Parse</h2>
241 <div id="text-6">
242
243
244 </div>
245
246 <div id="outline-container-6.1" class="outline-3">
247 <h3 id="sec-6.1">6.1 <span class="todo">TOGROK</span> Find MPP with CCM</h3>
248 <div id="text-6.1">
249
250 </div>
251
252 </div>
253
254 <div id="outline-container-6.2" class="outline-3">
255 <h3 id="sec-6.2">6.2 <span class="done">DONE</span> Find Most Probable Parse of given test sentence, in DMV</h3>
256 <div id="text-6.2">
257
258 <p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-07-23 Wed 10:56</span><br/>
259 inner() optionally keeps track of the highest probability children of
260 any node in <code>mpptree</code>. Say we're looking for <code>inner(i,j,(s_h,h),loc_h)</code> in
261 a certain sentence, and we find some possible left and right children,
262 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
263 <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
264 probability of this node rewriting to <code>L</code> and <code>R</code>,
265 eg. <code>inner(L)*inner(R)*p_GO_AT</code> or <code>p_STOP</code> or whatever. We only add this
266 entry to <code>mpptree</code> if there wasn't a higher-probability entry there
267 before.
268 </p>
269 <p>
270 Then, after <code>inner_sent</code> makes an <code>mpptree</code>, we find the <i>relevant</i>
271 head-argument pairs by searching through the tree using a queue,
272 adding the <code>L</code> and <code>R</code> keys of any entry to the queue as we find them
273 (skipping <code>STOP</code> keys), and adding any attachment entries to a set of
274 triples <code>(head,argument,dir)</code>. Thus we have our most probable parse,
275 eg.
276 <pre class="example">
277 set([( ROOT, (vbd,2),RIGHT),
278 ((vbd,2),(nn,1),LEFT),
279 ((vbd,2),(nn,3),RIGHT),
280 ((nn,1),(det,0),LEFT)])
281 </pre>
282 </p></div>
283 </div>
284
285 </div>
286
287 <div id="outline-container-7" class="outline-2">
288 <h2 id="sec-7">7 Initialization </h2>
289 <div id="text-7">
290
291 <p><a href="/Users/kiwibird/Documents/Skole/V08/Probability/dmvccm/src/dmv.py">dmv-inits</a>
292 </p>
293 <p>
294 We go through the corpus, since the probabilities are based on how far
295 away in the sentence arguments are from their heads.
296 </p>
297 </div>
298
299 <div id="outline-container-7.1" class="outline-3">
300 <h3 id="sec-7.1">7.1 <span class="todo">TOGROK</span> CCM Initialization </h3>
301 <div id="text-7.1">
302
303 <p>P<sub>SPLIT</sub> used here&hellip; how, again?
304 </p></div>
305 </div>
306
307 </div>
308
309 <div id="outline-container-8" class="outline-2">
310 <h2 id="sec-8">8 <span class="todo">TODO</span> [#C] Alternative CNF for DMV</h2>
311 <div id="text-8">
312
313
314 <p>
315 <a name="dmv2cnf">&nbsp;</a>
316 </p><ul>
317 <li>
318 <a href="src/cnf_dmv.py">cnf_dmv.py</a>
319 </li>
320 <li>
321 <a href="src/cnf_harmonic.py">cnf_harmonic.py</a>
322
323 </li>
324 </ul>
325
326 <p>See section 5 of <a href="tex/formulas.pdf">formulas.pdf</a>.
327 </p>
328 <p>
329 Given a grammar with certain p_ATTACH, p_STOP and p_ROOT, we get:
330 <pre class="example">
331 &gt;&gt;&gt; print testgrammar_h():
332 h&gt;&lt; --&gt; h&gt; STOP [0.30]
333 h&gt;&lt; --&gt; &gt;h&gt; STOP [0.40]
334 _h_ --&gt; STOP h&gt;&lt; [1.00]
335 _h_ --&gt; STOP &lt;h&gt;&lt; [1.00]
336 &gt;h&gt; --&gt; h&gt; _h_ [1.00]
337 &gt;h&gt; --&gt; &gt;h&gt; _h_ [1.00]
338 &lt;h&gt;&lt; --&gt; _h_ h&gt;&lt; [0.70]
339 &lt;h&gt;&lt; --&gt; _h_ &lt;h&gt;&lt; [0.60]
340 ROOT --&gt; STOP _h_ [1.00]
341 </pre>
342 </p>
343
344 </div>
345
346 <div id="outline-container-8.1" class="outline-3">
347 <h3 id="sec-8.1">8.1 <span class="todo">TODO</span> [#A] Make and implement an equivalent grammar that's <i>pure</i> CNF</h3>
348 <div id="text-8.1">
349
350 <p>&hellip;since I'm not sure about my unary reestimation rules (section 5 of
351 <a href="tex/formulas.pdf">formulas</a>).
352 </p>
353 <p>
354 For any rule where LHS is <code>_h_</code> we also have a corresponding one with
355 LHS <code>ROOT</code>, only difference being that we multiply in <code>p_ROOT(h)</code>.
356 </p>
357 <p>
358 For any rule where LHS is <code>.h&gt;</code>, we use adjacent probabilities for the
359 left child; if LHS is <code>&lt;h.</code> we use adjacent probabilities for the right
360 child. Only <code>_h_</code> and <code>_h&gt;_</code> (plus <code>ROOT</code>) get to introduce the pre-terminal
361 <code>h</code> (where <code>h</code>, <code>ROOT</code> and <code>_h_</code> all rewrite to the terminal
362 <code>'h'</code>), and only <code>_h_</code> and <code>_h&gt;_</code> (plus <code>ROOT</code>) act as STOP
363 rules (eg. get to multiply in <code>p(STOP)</code>).
364 </p>
365 <p>
366 <pre class="example">
367 h --&gt; 'h' 1
368 _h_ --&gt; 'h' p(STOP|h,L,adj) * p(STOP|h,R,adj)
369 ROOT --&gt; 'h' p(STOP|h,L,adj) * p(STOP|h,R,adj) * p_ROOT(h)
370
371 _h_ --&gt; h _a_ p(STOP|h,L,adj) * p(STOP|h,R,non) * p(a|h,R)*p(-STOP|h,R,adj)
372 _h_ --&gt; h .h&gt; p(STOP|h,L,adj) * p(STOP|h,R,non)
373 .h&gt; --&gt; _a_ _b_ p(a|h,R)*p(-STOP|h,R,adj) * p(b|h,R)*p(-STOP|h,R,non)
374 .h&gt; --&gt; _a_ h&gt; p(a|h,R)*p(-STOP|h,R,adj)
375 h&gt; --&gt; _a_ _b_ p(a|h,R)*p(-STOP|h,R,non) * p(b|h,R)*p(-STOP|h,R,non)
376 h&gt; --&gt; _a_ h&gt; p(a|h,R)*p(-STOP|h,R,non)
377
378 _h_ --&gt; _a_ h p(STOP|h,L,non) * p(STOP|h,R,adj) * p(a|h,L)*p(-STOP|h,L,adj)
379 _h_ --&gt; &lt;h. h p(STOP|h,L,non) * p(STOP|h,R,adj)
380 &lt;h. --&gt; _b_ _a_ p(b|h,L)*p(-STOP|h,L,non) * p(a|h,L)*p(-STOP|h,L,adj)
381 &lt;h. --&gt; &lt;h _a_ p(a|h,L)*p(-STOP|h,L,adj)
382 &lt;h --&gt; _a_ _b_ p(a|h,L)*p(-STOP|h,L,non) * p(b|h,L)*p(-STOP|h,L,non)
383 &lt;h --&gt; &lt;h _a_ p(a|h,L)*p(-STOP|h,L,non)
384
385 _h_ --&gt; &lt;h. _h&gt;_ p(STOP|h,L,non)
386 _h_ --&gt; _a_ _h&gt;_ p(STOP|h,L,non) * p(a|h,L)*p(-STOP|h,L,adj)
387 _h&gt;_ --&gt; h .h&gt; p(STOP|h,R,non)
388 _h&gt;_ --&gt; h _a_ p(STOP|h,R,non) * p(a|h,R)*p(-STOP|h,R,adj)
389
390 ROOT --&gt; h _a_ p(STOP|h,L,adj) * p(STOP|h,R,non) * p(a|h,R)*p(-STOP|h,R,adj) * p_ROOT(h)
391 ROOT --&gt; h .h&gt; p(STOP|h,L,adj) * p(STOP|h,R,non) * p_ROOT(h)
392
393 ROOT --&gt; _a_ h p(STOP|h,L,non) * p(STOP|h,R,adj) * p(a|h,L)*p(-STOP|h,L,adj) * p_ROOT(h)
394 ROOT --&gt; &lt;h. h p(STOP|h,L,non) * p(STOP|h,R,adj) * p_ROOT(h)
395
396 ROOT --&gt; &lt;h. _h&gt;_ p(STOP|h,L,non) * p_ROOT(h)
397 ROOT --&gt; _a_ _h&gt;_ p(STOP|h,L,non) * p(a|h,L)*p(-STOP|h,L,adj) * p_ROOT(h)
398
399 </pre>
400 </p>
401 <p>
402 Since we have rules rewriting <code>h</code> to <code>a</code> and <code>b</code>, we have a rule-set
403 numbering more than n<sub>tags</sub><sup>2</sup>.
404 </p>
405 </div>
406
407 </div>
408
409 <div id="outline-container-8.2" class="outline-3">
410 <h3 id="sec-8.2">8.2 <span class="todo">TOGROK</span> [#A] convert L&amp;Y-based reestimation into P_ATTACH and P_STOP values</h3>
411 <div id="text-8.2">
412
413 <p>Sum over the various rules? Or something? Must think of this.
414 </p></div>
415
416 </div>
417
418 <div id="outline-container-8.3" class="outline-3">
419 <h3 id="sec-8.3">8.3 <span class="todo">TODO</span> [#C] move as much as possible into common_dmv.py</h3>
420 <div id="text-8.3">
421
422 <p><a href="src/common_dmv.py">common_dmv.py</a>
423 </p></div>
424
425 </div>
426
427 <div id="outline-container-8.4" class="outline-3">
428 <h3 id="sec-8.4">8.4 <span class="done">DONE</span> L&amp;Y-based reestimation for cnf_dmv</h3>
429 <div id="text-8.4">
430
431 <p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-08-21 Thu 16:35</span><br/>
432 </p></div>
433
434 </div>
435
436 <div id="outline-container-8.5" class="outline-3">
437 <h3 id="sec-8.5">8.5 <span class="done">DONE</span> dmv2cnf re-estimation formulas</h3>
438 <div id="text-8.5">
439
440 <p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-08-21 Thu 16:36</span><br/>
441 </p></div>
442
443 </div>
444
445 <div id="outline-container-8.6" class="outline-3">
446 <h3 id="sec-8.6">8.6 <span class="done">DONE</span> inner and outer for cnf_dmv.py, also cnf_harmonic.py </h3>
447 <div id="text-8.6">
448
449 </div>
450 </div>
451
452 </div>
453
454 <div id="outline-container-9" class="outline-2">
455 <h2 id="sec-9">9 [#C] Deferred</h2>
456 <div id="text-9">
457
458 <p><a href="http://wiki.python.org/moin/PythonSpeed/PerformanceTips">http://wiki.python.org/moin/PythonSpeed/PerformanceTips</a> Eg., use
459 map/reduce/filter/[i for i in [i's]]/(i for i in [i's]) instead of
460 for-loops; use local variables for globals (global variables or or
461 functions), etc.
462 </p>
463 </div>
464
465 <div id="outline-container-9.1" class="outline-3">
466 <h3 id="sec-9.1">9.1 <span class="todo">TODO</span> Clean up reestimation code &nbsp;&nbsp;&nbsp;<span class="tag">PRETTIER</span></h3>
467 <div id="text-9.1">
468
469 </div>
470
471 </div>
472
473 <div id="outline-container-9.2" class="outline-3">
474 <h3 id="sec-9.2">9.2 <span class="todo">TODO</span> [#A] compare speed of w_left/right(&hellip;) and w(LEFT/RIGHT, &hellip;) &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span></h3>
475 <div id="text-9.2">
476
477 </div>
478
479 </div>
480
481 <div id="outline-container-9.3" class="outline-3">
482 <h3 id="sec-9.3">9.3 <span class="todo">TODO</span> when reestimating P_STOP etc, remove rules with p &lt; epsilon &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span></h3>
483 <div id="text-9.3">
484
485 </div>
486
487 </div>
488
489 <div id="outline-container-9.4" class="outline-3">
490 <h3 id="sec-9.4">9.4 <span class="todo">TODO</span> inner_dmv, short ranges and impossible attachment &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span></h3>
491 <div id="text-9.4">
492
493 <p>If s-t &lt;= 2, there can be only one attachment below, so don't recurse
494 with both Lattach=True and Rattach=True.
495 </p>
496 <p>
497 If s-t &lt;= 1, there can be no attachment below, so only recurse with
498 Lattach=False, Rattach=False.
499 </p>
500 <p>
501 Put this in the loop under rewrite rules (could also do it in the STOP
502 section, but that would only have an effect on very short sentences).
503 </p></div>
504
505 </div>
506
507 <div id="outline-container-9.5" class="outline-3">
508 <h3 id="sec-9.5">9.5 <span class="todo">TODO</span> clean up the module files &nbsp;&nbsp;&nbsp;<span class="tag">PRETTIER</span></h3>
509 <div id="text-9.5">
510
511 <p>Is there better way to divide dmv and harmonic? There's a two-way
512 dependency between the modules. Guess there could be a third file that
513 imports both the initialization and the actual EM stuff, while a file
514 containing constants and classes could be imported by all others:
515 <pre class="example">
516 dmv.py imports dmv_EM.py imports dmv_classes.py
517 dmv.py imports dmv_inits.py imports dmv_classes.py
518 </pre>
519 </p>
520 </div>
521
522 </div>
523
524 <div id="outline-container-9.6" class="outline-3">
525 <h3 id="sec-9.6">9.6 <span class="todo">TOGROK</span> Some (tagged) sentences are bound to come twice &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span></h3>
526 <div id="text-9.6">
527
528 <p>Eg, first sort and count, so that the corpus
529 [['nn','vbd','det','nn'],
530 ['vbd','nn','det','nn'],
531 ['nn','vbd','det','nn']]
532 becomes
533 [(['nn','vbd','det','nn'],2),
534 (['vbd','nn','det','nn'],1)]
535 and then in each loop through sentences, make sure we handle the
536 frequency correctly.
537 </p>
538 <p>
539 Is there much to gain here?
540 </p>
541 </div>
542
543 </div>
544
545 <div id="outline-container-9.7" class="outline-3">
546 <h3 id="sec-9.7">9.7 <span class="todo">TOGROK</span> tags as numbers or tags as strings? &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span></h3>
547 <div id="text-9.7">
548
549 <p>Need to clean up the representation.
550 </p>
551 <p>
552 Stick with tag-strings in initialization then switch to numbers for
553 IO-algorithm perhaps? Can probably afford more string-matching in
554 initialization..
555 </p></div>
556 </div>
557
558 </div>
559
560 <div id="outline-container-10" class="outline-2">
561 <h2 id="sec-10">10 Adjacency and combining it with the inside-outside algorithm</h2>
562 <div id="text-10">
563
564 <p>Each DMV_Rule has both a probN and a probA, for adjacencies. inner()
565 and outer() needs the correct one in each case.
566 </p>
567 <p>
568 In each inner() call, loc_h is the location of the head of this
569 dependency structure. In each outer() call, it's the head of the <i>Node</i>,
570 the structure we're looking outside of.
571 </p>
572 <p>
573 We call inner() for each location of a head, and on each terminal,
574 loc_h must equal <code>i</code> (and <code>loc_h+1</code> equal <code>j</code>). In the recursive attachment
575 calls, we use the locations (sentence indices) of words to the left or
576 right of the head in calls to inner(). <i>loc_h lets us check whether we need probN or probA</i>.
577 </p>
578 </div>
579
580 <div id="outline-container-10.1" class="outline-3">
581 <h3 id="sec-10.1">10.1 Possible alternate type of adjacency</h3>
582 <div id="text-10.1">
583
584 <p>K&amp;M's adjacency is just whether or not an argument has been generated
585 in the current direction yet. One could also make a stronger type of
586 adjacency, where h and a are not adjacent if b is in between, eg. with
587 the sentence "a b h" and the structure ((h-&gt;a), (a-&gt;b)), h is
588 K&amp;M-adjacent to a, but not next to a, since b is in between. It's easy
589 to check this type of adjacency in inner(), but it needs new rules for
590 P_STOP reestimation.
591 </p></div>
592 </div>
593
594 </div>
595
596 <div id="outline-container-11" class="outline-2">
597 <h2 id="sec-11">11 Python-stuff</h2>
598 <div id="text-11">
599
600 <p>Make those debug statements steal a bit less attention in emacs:
601 <pre class="example">
602 (font-lock-add-keywords
603 'python-mode ; not really regexp, a bit slow
604 '(("^\\( *\\)\\(\\if +'.+' +in +io.DEBUG. *\\(
605 \\1 .+$\\)+\\)" 2 font-lock-preprocessor-face t)))
606 (font-lock-add-keywords
607 'python-mode
608 '(("\\&lt;\\(\\(io\\.\\)?debug(.+)\\)" 1 font-lock-preprocessor-face t)))
609 </pre>
610 </p>
611 <ul>
612 <li>
613 <a href="src/pseudo.py">pseudo.py</a>
614 </li>
615 <li>
616 <a href="http://nltk.org/doc/en/structured-programming.html">http://nltk.org/doc/en/structured-programming.html</a> recursive dynamic
617 </li>
618 <li>
619 <a href="http://nltk.org/doc/en/advanced-parsing.html">http://nltk.org/doc/en/advanced-parsing.html</a>
620 </li>
621 <li>
622 <a href="http://jaynes.colorado.edu/PythonIdioms.html">http://jaynes.colorado.edu/PythonIdioms.html</a>
623
624
625
626 </li>
627 </ul>
628 </div>
629
630 </div>
631
632 <div id="outline-container-12" class="outline-2">
633 <h2 id="sec-12">12 Git</h2>
634 <div id="text-12">
635
636 <p>Repository web page: <a href="http://repo.or.cz/w/dmvccm.git">http://repo.or.cz/w/dmvccm.git</a>
637 </p>
638 <p>
639 Setting up a new project:
640 <pre class="example">
641 git init
642 git add .
643 git commit -m "first release"
644 </pre>
645 </p>
646 <p>
647 Later on: (<code>-a</code> does <code>git rm</code> and <code>git add</code> automatically)
648 <pre class="example">
649 git init
650 git commit -a -m "some subsequent release"
651 </pre>
652 </p>
653 <p>
654 Then push stuff up to the remote server:
655 <pre class="example">
656 git push git+ssh://username@repo.or.cz/srv/git/dmvccm.git master
657 </pre>
658 </p>
659 <p>
660 (<code>eval `ssh-agent`</code> and <code>ssh-add</code> to avoid having to type in keyphrase all
661 the time)
662 </p>
663 <p>
664 Make a copy of the (remote) master branch:
665 <pre class="example">
666 git clone git://repo.or.cz/dmvccm.git
667 </pre>
668 </p>
669 <p>
670 Make and name a new branch in this folder
671 <pre class="example">
672 git checkout -b mybranch
673 </pre>
674 </p>
675 <p>
676 To save changes in <code>mybranch</code>:
677 <pre class="example">
678 git commit -a
679 </pre>
680 </p>
681 <p>
682 Go back to the master branch (uncommitted changes from <code>mybranch</code> are
683 carried over):
684 <pre class="example">
685 git checkout master
686 </pre>
687 </p>
688 <p>
689 Try out:
690 <pre class="example">
691 git add --interactive
692 </pre>
693 </p>
694 <p>
695 Good tutorial:
696 <a href="http://www-cs-students.stanford.edu/~blynn//gitmagic/">http://www-cs-students.stanford.edu/~blynn//gitmagic/</a>
697 </p></div>
698 </div>
699 <div id="postamble"><p class="author"> Author: Kevin Brubeck Unhammer
700 <a href="mailto:K.BrubeckUnhammer at student uva nl ">&lt;K.BrubeckUnhammer at student uva nl &gt;</a>
701 </p>
702 <p class="date"> Date: 2008-09-11 12:01:19 CEST</p>
703 <p>HTML generert av <a href='http://orgmode.org/'>org-mode</a> 6.06b in emacs 22<p>
704 </div><script src="./post-script.js" type="text/JavaScript">
705 </script></body>
706 </html>
DMVCCM parser