DMVCCM.html.~2~

   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</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/05/28 13:40:17"/>
  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 </head><body>
  13 <h1 class="title">DMV/CCM</h1>
  14 <div id="table-of-contents">
  15 <h2>Table of Contents</h2>
  16 <div id="text-table-of-contents">
  17 <ul>
  18 <li><a href="#sec-1">1 dmvccm</a>
  19 <ul>
  20 <li><a href="#sec-1.1">1.1 [#A] P<sub>STOP</sub></a>
  21 <ul>
  22 <li><a href="#sec-1.1.1">1.1.1 Remember: The P<sub>STOP</sub> formula is upside-down (left-to-right also)</a></li>
  23 <li><a href="#sec-1.1.2">1.1.2 How is the P<sub>STOP</sub> formula different given other values for dir and adj?</a></li>
  24 </ul>
  25 </li>
  26 <li><a href="#sec-1.2">1.2 P<sub>CHOOSE</sub></a></li>
  27 <li><a href="#sec-1.3">1.3 Some (tagged) sentences are bound to come twice</a></li>
  28 <li><a href="#sec-1.4">1.4 Initialization   </a>
  29 <ul>
  30 <li><a href="#sec-1.4.1">1.4.1 DMV Initialization frequencies    </a></li>
  31 <li><a href="#sec-1.4.2">1.4.2 DMV Initialization probabilities (from initialization frequency)</a></li>
  32 <li><a href="#sec-1.4.3">1.4.3 CCM Initialization    </a></li>
  33 </ul>
  34 </li>
  35 <li><a href="#sec-1.5">1.5 Adjacency and combining it with inner()</a></li>
  36 <li><a href="#sec-1.6">1.6 Is the E-step in DMV just inner() on the full sentence? </a></li>
  37 <li><a href="#sec-1.7">1.7 [#C] Corpus access</a></li>
  38 <li><a href="#sec-1.8">1.8 How do we interpret DMV as an inside/outside process?   </a></li>
  39 <li><a href="#sec-1.9">1.9 Technical: sentences or rules as the "outer loop"?</a></li>
  40 <li><a href="#sec-1.10">1.10 CCM-stuff</a></li>
  41 <li><a href="#sec-1.11">1.11 How do we know whether we are 'adjacent' or not? </a></li>
  42 </ul>
  43 </li>
  44 <li><a href="#sec-2">2 Python-stuff</a></li>
  45 </ul>
  46 </div>
  47 </div>
  48
  49 <div id="outline-container-1" class="outline-2">
  50 <h2 id="sec-1">1 dmvccm</h2>
  51 <div id="text-1">
  52
  53 <p><span class="timestamp-kwd">DEADLINE: </span> <span class="timestamp">2008-06-30 Mon</span><br/>
  54 (But absolute, extended, really-quite-dead-now deadline: August 31&hellip;)
  55 <a href="src/dmv.py">dmv.py</a>
  56 <a href="src/io.py">io.py</a>
  57 </p>
  58 </div>
  59
  60 <div id="outline-container-1.1" class="outline-3">
  61 <h3 id="sec-1.1">1.1 <span class="todo">TODO</span> [#A] P<sub>STOP</sub></h3>
  62 <div id="text-1.1">
  63
  64 <p><a href="src/dmv.py">dmv-P_STOP</a>
  65 </p>
  66 </div>
  67
  68 <div id="outline-container-1.1.1" class="outline-4">
  69 <h4 id="sec-1.1.1">1.1.1 Remember: The P<sub>STOP</sub> formula is upside-down (left-to-right also)</h4>
  70 <div id="text-1.1.1">
  71
  72 </div>
  73
  74 </div>
  75
  76 <div id="outline-container-1.1.2" class="outline-4">
  77 <h4 id="sec-1.1.2">1.1.2 How is the P<sub>STOP</sub> formula different given other values for dir and adj?</h4>
  78 <div id="text-1.1.2">
  79
  80 <p>(Presumably, the P<sub>STOP</sub> formula where STOP is True is just the
  81 rule-probability of <u>h</u> -&gt; STOP h_ or h_ -&gt; h STOP, but how does
  82 adjacency fit in here?)
  83 </p>
  84 <p>
  85 (And P<sub>STOP</sub>(-STOP|&hellip;) = 1 - P<sub>STOP</sub>(STOP|&hellip;) )
  86 </p></div>
  87 </div>
  88
  89 </div>
  90
  91 <div id="outline-container-1.2" class="outline-3">
  92 <h3 id="sec-1.2">1.2 <span class="todo">TODO</span> P<sub>CHOOSE</sub></h3>
  93 <div id="text-1.2">
  94
  95 <p>Write the formulas! should be easy?
  96 </p></div>
  97
  98 </div>
  99
 100 <div id="outline-container-1.3" class="outline-3">
 101 <h3 id="sec-1.3">1.3 <span class="todo">TOGROK</span> Some (tagged) sentences are bound to come twice             &nbsp;&nbsp;&nbsp;<span class="tag">OPTIMIZE</span></h3>
 102 <div id="text-1.3">
 103
 104 <p>Eg, first sort and count, so that the corpus
 105 [['nn','vbd','det','nn'],
 106 ['vbd','nn','det','nn'],
 107 ['nn','vbd','det','nn']]
 108 becomes
 109 [(['nn','vbd','det','nn'],2),
 110 (['vbd','nn','det','nn'],1)]
 111 and then in each loop through sentences, make sure we handle the
 112 frequency correctly.
 113 </p>
 114 <p>
 115 Is there much to gain here?
 116 </p></div>
 117
 118 </div>
 119
 120 <div id="outline-container-1.4" class="outline-3">
 121 <h3 id="sec-1.4">1.4 Initialization   </h3>
 122 <div id="text-1.4">
 123
 124 <p><a href="/Users/kiwibird/Documents/Skole/V08/Probability/dmvccm/src/dmv.py">dmv-inits</a>
 125 </p>
 126 <p>
 127 We do have to go through the corpus, since the probabilities are based
 128 on how far away in the sentence arguments are from their heads.
 129 </p>
 130 </div>
 131
 132 <div id="outline-container-1.4.1" class="outline-4">
 133 <h4 id="sec-1.4.1">1.4.1 <span class="done">DONE</span> DMV Initialization frequencies    </h4>
 134 <div id="text-1.4.1">
 135
 136 <p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-05-27 Tue 20:04</span><br/>
 137 </p>
 138 </div>
 139
 140 <div id="outline-container-1.4.1.1" class="outline-5">
 141 <h5 id="sec-1.4.1.1">1.4.1.1 P<sub>STOP</sub>    </h5>
 142 <div id="text-1.4.1.1">
 143
 144 <p>P<sub>STOP</sub> is not well defined by K&amp;M. One possible interpretation given
 145 the sentence [det nn vb nn] is
 146 </p><ul>
 147 <li>
 148 f<sub>STOP</sub>( STOP|det, L, adj) +1
 149 </li>
 150 <li>
 151 f<sub>STOP</sub>(-STOP|det, L, adj) +0
 152 </li>
 153 <li>
 154 f<sub>STOP</sub>( STOP|det, L, non<sub>adj</sub>) +1
 155 </li>
 156 <li>
 157 f<sub>STOP</sub>(-STOP|det, L, non<sub>adj</sub>) +0
 158 </li>
 159 <li>
 160 f<sub>STOP</sub>( STOP|det, R, adj) +0
 161 </li>
 162 <li>
 163 f<sub>STOP</sub>(-STOP|det, R, adj) +1
 164
 165 </li>
 166 <li>
 167 f<sub>STOP</sub>( STOP|nn, L, adj) +0
 168 </li>
 169 <li>
 170 f<sub>STOP</sub>(-STOP|nn, L, adj) +1
 171 </li>
 172 <li>
 173 f<sub>STOP</sub>( STOP|nn, L, non<sub>adj</sub>) +1  # since there's at least one to the left
 174 </li>
 175 <li>
 176 f<sub>STOP</sub>(-STOP|nn, L, non<sub>adj</sub>) +0
 177
 178 </li>
 179 </ul></div>
 180
 181 </div>
 182
 183 <div id="outline-container-1.4.1.2" class="outline-5">
 184 <h5 id="sec-1.4.1.2">1.4.1.2 P<sub>CHOOSE</sub></h5>
 185 <div id="text-1.4.1.2">
 186
 187 <p>Go through the corpus, counting distances between heads and
 188 arguments. In [det nn vb nn], we give
 189 </p><ul>
 190 <li>
 191 f<sub>CHOOSE</sub>(nn|det, R) +1/1 + C
 192 </li>
 193 <li>
 194 f<sub>CHOOSE</sub>(vb|det, R) +1/2 + C
 195 </li>
 196 <li>
 197 f<sub>CHOOSE</sub>(nn|det, R) +1/3 + C
 198 <ul>
 199 <li>
 200 If this were the full corpus, P<sub>CHOOSE</sub>(nn|det, R) would have
 201 (1+1/3+2C) / sum<sub>a</sub> f<sub>CHOOSE</sub>(a|det, R)
 202
 203 </li>
 204 </ul></li>
 205 </ul>
 206 <p>The ROOT gets "each argument with equal probability", so in a sentence
 207 of three words, 1/3 for each (in [nn vb nn], 'nn' gets 2/3). Basically
 208 just a frequency count of the corpus&hellip;
 209 </p></div>
 210 </div>
 211
 212 </div>
 213
 214 <div id="outline-container-1.4.2" class="outline-4">
 215 <h4 id="sec-1.4.2">1.4.2 <span class="todo">TOGROK</span> DMV Initialization probabilities (from initialization frequency)</h4>
 216 <div id="text-1.4.2">
 217
 218 </div>
 219
 220 </div>
 221
 222 <div id="outline-container-1.4.3" class="outline-4">
 223 <h4 id="sec-1.4.3">1.4.3 <span class="todo">TOGROK</span> CCM Initialization    </h4>
 224 <div id="text-1.4.3">
 225
 226 <p>P<sub>SPLIT</sub> used here&hellip; how, again?
 227 </p>
 228
 229
 230 </div>
 231 </div>
 232
 233 </div>
 234
 235 <div id="outline-container-1.5" class="outline-3">
 236 <h3 id="sec-1.5">1.5 <span class="todo">TOGROK</span> Adjacency and combining it with inner()</h3>
 237 <div id="text-1.5">
 238
 239 </div>
 240
 241 </div>
 242
 243 <div id="outline-container-1.6" class="outline-3">
 244 <h3 id="sec-1.6">1.6 <span class="todo">TOGROK</span> Is the E-step in DMV just inner() on the full sentence? </h3>
 245 <div id="text-1.6">
 246
 247 <p>and What exactly is the M-step of DMV?
 248 </p>
 249 </div>
 250
 251 </div>
 252
 253 <div id="outline-container-1.7" class="outline-3">
 254 <h3 id="sec-1.7">1.7 <span class="todo">TODO</span> [#C] Corpus access</h3>
 255 <div id="text-1.7">
 256
 257 </div>
 258
 259 </div>
 260
 261 <div id="outline-container-1.8" class="outline-3">
 262 <h3 id="sec-1.8">1.8 <span class="todo">TOGROK</span> How do we interpret DMV as an inside/outside process?   </h3>
 263 <div id="text-1.8">
 264
 265 <p>c<sub>s</sub>(x : i, j) is "the expected fraction of parses of s" with x from
 266 i to j; expectation then uses the probabilities gotten from
 267 initialization and previously gained probabilities, but these are of
 268 the form P<sub>STOP</sub> and P<sub>CHOOSE</sub>, how do we translate this to inside
 269 outside, which just uses the probabilities of CFG-rules?
 270 </p>
 271 </div>
 272
 273 </div>
 274
 275 <div id="outline-container-1.9" class="outline-3">
 276 <h3 id="sec-1.9">1.9 Technical: sentences or rules as the "outer loop"?</h3>
 277 <div id="text-1.9">
 278
 279 </div>
 280
 281 </div>
 282
 283 <div id="outline-container-1.10" class="outline-3">
 284 <h3 id="sec-1.10">1.10 CCM-stuff</h3>
 285 <div id="text-1.10">
 286
 287 </div>
 288
 289 </div>
 290
 291 <div id="outline-container-1.11" class="outline-3">
 292 <h3 id="sec-1.11">1.11 <span class="done">DONE</span> How do we know whether we are 'adjacent' or not? </h3>
 293 <div id="text-1.11">
 294
 295
 296 </div>
 297
 298 <div id="outline-container-1.11.0.1" class="outline-5">
 299 <h5 id="sec-1.11.0.1">1.11.0.1 One configuration that I'm fairly certain of: right w/CHOOSE</h5>
 300 <div id="text-1.11.0.1">
 301
 302 <p>if we have
 303 \Tree [<sub>b</sub> [<sub>b</sub> b <u>c</u> ] <u>d</u> ]
 304 then the lower tree [<sub>b</sub> b <u>c</u> ] is adjacent since, working your way up
 305 the tree, no argument has been created to the right "yet"; while the
 306 outer tree [<sub>b</sub> [<sub>b</sub> &hellip; ] <u>d</u> ] is non-adjacent, since there is something in
 307 between&hellip; Is it thus always adjacent to the right if the distance
 308 is 2? (That is, in e(s,t,i) for the adjacent rule: t - s == 2; while
 309 in the non_adj rule: t - s == 4)
 310 </p><ul>
 311 <li id="sec-1.11.0.1.1">Implementing this:<br/>
 312 Two different DMVRules? Or just two different prob-values per rule?
 313 </li>
 314 </ul>
 315 </div>
 316
 317 </div>
 318
 319 <div id="outline-container-1.11.0.2" class="outline-5">
 320 <h5 id="sec-1.11.0.2">1.11.0.2 left w/CHOOSE</h5>
 321 <div id="text-1.11.0.2">
 322
 323 <p>Same deal here?
 324 </p></div>
 325
 326 </div>
 327
 328 <div id="outline-container-1.11.0.3" class="outline-5">
 329 <h5 id="sec-1.11.0.3">1.11.0.3 R/L without CHOOSE, the "sealing operations"</h5>
 330 <div id="text-1.11.0.3">
 331
 332 <p><u>h</u> -&gt; STOP h_ and h_ -&gt; h STOP
 333 </p>
 334 <p>
 335 What is "adjacency" here? That t - s == 1?
 336 </p>
 337
 338
 339
 340 </div>
 341 </div>
 342 </div>
 343
 344 </div>
 345
 346 <div id="outline-container-2" class="outline-2">
 347 <h2 id="sec-2">2 Python-stuff</h2>
 348 <div id="text-2">
 349
 350 <ul>
 351 <li>
 352 <a href="src/pseudo.py">pseudo.py</a>
 353 </li>
 354 <li>
 355 <a href="http://nltk.org/doc/en/structured-programming.html">http://nltk.org/doc/en/structured-programming.html</a> recursive dynamic
 356 </li>
 357 <li>
 358 <a href="http://nltk.org/doc/en/advanced-parsing.html">http://nltk.org/doc/en/advanced-parsing.html</a>
 359
 360
 361 </li>
 362 </ul>
 363 </div>
 364 </div>
 365 <div id="postamble"><p class="author"> Author: Kevin Brubeck Unhammer
 366 <a href="mailto:K.BrubeckUnhammer at student uva nl ">&lt;K.BrubeckUnhammer at student uva nl &gt;</a>
 367 </p>
 368 <p class="date"> Date: 2008/05/28 13:40:17</p>
 369 </div><p class="postamble">Skrive vha. emacs + <a href='http://orgmode.org/'>org-mode</a></p></body>
 370 </html>