DMVCCM.org

   1 # -*- coding: mule-utf-8-unix -*-
   2
   3 #+STARTUP: overview
   4 #+TAGS: OPTIMIZE PRETTIER
   5 #+STARTUP: hidestars
   6 #+TITLE: DMV/CCM -- todo-list / progress
   7 #+AUTHOR: Kevin Brubeck Unhammer
   8 #+EMAIL: K.BrubeckUnhammer at student uva nl
   9 #+OPTIONS: H:4
  10 #+OPTIONS: toc:3
  11 #+OPTIONS: ^:{}
  12 #+LANGUAGE: en
  13 #+SEQ_TODO: TOGROK TODO DONE
  14
  15 * dmvccm report and project
  16   DEADLINE: <2008-06-30 Mon>
  17 - [[file:src/dmv.py][dmv.py]]
  18 - [[file:src/io.py][io.py]]
  19 - [[file:src/harmonic.py::harmonic%20py%20initialization%20for%20dmv][harmonic.py]]
  20
  21 (But absolute, extended, really-quite-dead-now deadline: August 31...)
  22 * DONE outer probabilities
  23   CLOSED: [2008-06-12 Thu 11:11]
  24 # <<outer>>
  25 There are 6 different configurations here, based on what the above
  26 (mother) node is, and what the Node for which we're computing is.
  27 Here *r* is not between *s* and *t* as in inner(), but an /outer/ index. *loc_N*
  28 is the location of the Node head in the sentence, *loc_m* for the head
  29 of the mother of Node.
  30
  31 + mother is a RIGHT-stop:
  32   - outer(*s, t*, mom.LHS, *loc_N*), no inner-call
  33   - adjacent iff *t* == *loc_m*
  34 + mother is a  LEFT-stop:
  35   - outer(*s, t*, mom.LHS, *loc_N*), no inner-call
  36   - adjacent iff *s* == *loc_m*
  37
  38 + Node is on the LEFT branch (mom.L == Node)
  39   * and mother is a LEFT attachment:
  40     - *loc_N* will be in the LEFT branch, can be anything here.
  41     - In the RIGHT, attached, branch we find inner(*t+1, r*, mom.R, *loc_m*) for
  42       all possible *loc_m* in the right part of the sentence.
  43     - outer(*s, r*, mom.LHS, *loc_m*).
  44     - adjacent iff *t+1* == *loc_m*
  45   * and mother is a RIGHT attachment:
  46     - *loc_m* = *loc_N*.
  47     - In the RIGHT, attached, branch we find inner(*t+1, r*, mom.R, *loc_R*) for
  48       all possible *loc_R* in the right part of the sentence.
  49     - outer(*s, r*, mom.LHS, *loc_N*).
  50     - adjacent iff *t* == *loc_m*
  51
  52 + Node is on the RIGHT branch (mom.R == Node)
  53   * and mother is a LEFT attachment:
  54     - *loc_m* = *loc_N*.
  55     - In the LEFT, attached, branch we find inner(*r, s-1*, mom.L, *loc_L*) for
  56       all possible *loc_L* in the left part of the sentence.
  57     - outer(*r, t*, mom.LHS, *loc_m*).
  58     - adjacent iff *s* == *loc_m*
  59   * and mother is a RIGHT attachment:
  60     - *loc_N* will be in the RIGHT branch, can be anything here.
  61     - In the RIGHT, attached, branch we find inner(*r, s-1*, mom.L, *loc_m*) for
  62       all possible *loc_m* in the right part of the sentence.
  63     - outer(*r, t*, mom.LHS, *loc_N*).
  64     - adjacent iff *s-1* == *loc_m*
  65
  66 [[file:outer_attachments.jpg]]
  67
  68 : in notes:   in code (constants):    in Klein thesis:
  69 :-------------------------------------------------------------------
  70 : _h_         SEAL                    bar over h
  71 :  h_         RGO_L                   right-under-left-arrow over h
  72 :  h          GO_R                    right-arrow over h
  73 :
  74 :             LGO_R                   left-under-right-arrow over h
  75 :             GO_L                    left-arrow over h
  76
  77 Also, unlike in [[http://bibsonomy.org/bibtex/2b9f6798bb092697da7042ca3f5dee795][Lari & Young]], non-ROOT ('S') symbols may cover the
  78 whole sentence, but ROOT may /only/ appear if it covers the whole
  79 sentence.
  80 ** COMMENT qtrees, tex
  81 \usepackage{qtree}
  82 \usepackage{amssymb}
  83
  84 \newcommand{\GOR}[1]{\overrightarrow{#1}}
  85 \newcommand{\RGOL}[1]{\overleftarrow{\overrightarrow{#1}}}
  86
  87 \newcommand{\SEAL}[1]{\overline{#1}}
  88
  89 \newcommand{\LGOR}[1]{\overrightarrow{\overleftarrow{#1}}}
  90 \newcommand{\GOL}[1]{\overleftarrow{#1}}
  91
  92 \Tree [.{$\RGOL{h}$} [.{$_s \SEAL{a} _t$\\
  93   Node} ] {$_{t+1} \RGOL{h} _r$\\
  94   R} ]
  95 \Tree [.{$\GOR{h}$} {$_{s} \GOR{h} _{t}$\\
  96   Node} [.{$_{t+1} \SEAL{a} _r$\\
  97   R} ] ]
  98 \Tree [.{$\RGOL{h}$} [.{$_r \SEAL{a} _{s-1}$\\
  99   L} ] {$_{s} \RGOL{h} _t$\\
 100   Node} ]
 101 \Tree [.{$\GOR{h}$} {$_{r} \GOR{h} _{s-1}$\\
 102   L} [.{$_{s} \SEAL{a} _t$\\
 103   Node} ] ]
 104
 105
 106 \Tree [.{$h\urcorner$} [.{$_s \ulcorner a\urcorner _t$\\
 107   Node} ] {$_{t+1} h\urcorner _r$\\
 108   R} ]
 109 \Tree [.{$h$} {$_{s} h _{t}$\\
 110   Node} [.{$_{t+1} \ulcorner a\urcorner _r$\\
 111   R} ] ]
 112 \Tree [.{$h\urcorner$} [.{$_r \ulcorner a\urcorner _{s-1}$\\
 113   L} ] {$_{s} h\urcorner _t$\\
 114   Node} ]
 115 \Tree [.{$h$} {$_{r} h _{s-1}$\\
 116   L} [.{$_{s} \ulcorner a\urcorner _t$\\
 117   Node} ] ]
 118 * TODO [#B] P_STOP and P_CHOOSE for IO/EM (reestimation)
 119 [[file:src/dmv.py::DMV%20probabilities][dmv-P_STOP]]
 120 Remember: The P_{STOP} formula is upside-down (left-to-right also).
 121 (In the article..not the [[http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf][thesis]])
 122
 123 ** P_STOP formulas for various dir and adj:
 124 Assuming this:
 125 - P_{STOP}(STOP|h,L,non_adj) = \sum_{corpus} \sum_{s<loc(h)} \sum_{t}
 126   c(s,t,_h_, ...) / \sum_{corpus} \sum_{s<loc(h)} \sum_{t}
 127   c(s,t,h_, ...)
 128 - P_{STOP}(STOP|h,L,adj) = \sum_{corpus} \sum_{s=loc(h)} \sum_{t}
 129   c(s,t,_h_, ...) / \sum_{corpus} \sum_{s=loc(h)} \sum_{t}
 130   c(s,t,h_, ...)
 131 - P_{STOP}(STOP|h,R,non_adj) = \sum_{corpus} \sum_{s=loc(h)} \sum_{t>loc(h)}
 132   c(s,t,h_, ...) / \sum_{corpus} \sum_{s=loc(h)} \sum_{t>loc(h)}
 133   c(s,t,h, ...)
 134 - P_{STOP}(STOP|h,R,adj) = \sum_{corpus} \sum_{s=loc(h)} \sum_{t=loc(h)}
 135   c(s,t,h_, ...) / \sum_{corpus} \sum_{s=loc(h)} \sum_{t=loc(h)}
 136   c(s,t,h, ...)
 137
 138 (And P_{STOP}(-STOP|...) = 1 - P_{STOP}(STOP|...) )
 139 ** P_CHOOSE formula:
 140 Assuming this:
 141 - P_{CHOOSE}(a|h,L) = \sum_{corpus} \sum_{s<loc(h)} \sum_{t>=loc(h)} \sum_{r<t}
 142   c(s,r,_a_, ...) / \sum_{corpus} \sum_{s<loc(h)} \sum_{t>=loc(h)}
 143   c(s,t,h_,...)
 144   - t >= loc(h) since there are many possibilites for
 145     right-attachments below, and each of them alone gives a lower
 146     probability (through multiplication) to the upper tree (so sum
 147     them all)
 148 - P_{CHOOSE}(a|h,R) = \sum_{corpus} \sum_{s=loc(h)} \sum_{r>s}
 149   c(s,r,_a_,...) / \sum_{corpus} \sum_{s=loc(h)} \sum_{t}
 150   c(s,t,h, ...)
 151 ** DONE [#A] How do we only count from completed trees?
 152    CLOSED: [2008-06-13 Fri 11:40]
 153 Use c(s,t,Node); inner * outer / P_sent
 154
 155 ** DONE [#A] c(s,t,Node)
 156   CLOSED: [2008-06-13 Fri 11:38]
 157 = inner * outer / P_sent
 158
 159 implemented as inner * outer / inner_sent
 160
 161 * TOGROK Find Most Probable Parse of given test sentence
 162 We could probably do it pretty easily from the chart:
 163 - for all loc_h, select the (0,len(sent),ROOT,loc_h) that has the highest p
 164 - for stops, just keep going
 165 - for rewrites, for loc_dep select the one that has the highest p
 166 * TOGROK Combine CCM with DMV
 167 Page 108 (pdf: 124) of [[http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf][Klein's thesis]] gives info about this.
 168 ** TODO Make inner() and outer() also allow left-first attachment
 169 Using P_{ORDER}(/left-first/ | w) etc.
 170 * TODO Get a dependency parsed version of WSJ to test with
 171 * Initialization
 172 [[file:~/Documents/Skole/V08/Probability/dmvccm/src/dmv.py::Initialization%20todo][dmv-inits]]
 173
 174 We go through the corpus, since the probabilities are based on how far
 175 away in the sentence arguments are from their heads.
 176 ** TOGROK CCM Initialization
 177 P_{SPLIT} used here... how, again?
 178 ** DONE Separate initialization to another file?                      :PRETTIER:
 179    CLOSED: [2008-06-08 Sun 12:51]
 180 [[file:src/harmonic.py::harmonic%20py%20initialization%20for%20dmv][harmonic.py]]
 181 ** DONE DMV Initialization probabilities
 182 (from initialization frequency)
 183 ** DONE DMV Initialization frequencies
 184    CLOSED: [2008-05-27 Tue 20:04]
 185 *** P_STOP
 186 P_{STOP} is not well defined by K&M. One possible interpretation given
 187 the sentence [det nn vb nn] is
 188 : f_{STOP}( STOP|det, L, adj) +1
 189 : f_{STOP}(-STOP|det, L, adj) +0
 190 : f_{STOP}( STOP|det, L, non_adj) +1
 191 : f_{STOP}(-STOP|det, L, non_adj) +0
 192 : f_{STOP}( STOP|det, R, adj) +0
 193 : f_{STOP}(-STOP|det, R, adj) +1
 194 :
 195 : f_{STOP}( STOP|nn, L, adj) +0
 196 : f_{STOP}(-STOP|nn, L, adj) +1
 197 : f_{STOP}( STOP|nn, L, non_adj) +1  # since there's at least one to the left
 198 : f_{STOP}(-STOP|nn, L, non_adj) +0
 199 **** TODO tweak
 200 # <<pstoptweak>>
 201 :            f[head,  'STOP', 'LN'] += (i_h <= 1)     # first two words
 202 :            f[head, '-STOP', 'LN'] += (not i_h <= 1)
 203 :            f[head,  'STOP', 'LA'] += (i_h == 0)     # very first word
 204 :            f[head, '-STOP', 'LA'] += (not i_h == 0)
 205 :            f[head,  'STOP', 'RN'] += (i_h >= n - 2) # last two words
 206 :            f[head, '-STOP', 'RN'] += (not i_h >= n - 2)
 207 :            f[head,  'STOP', 'RA'] += (i_h == n - 1) # very last word
 208 :            f[head, '-STOP', 'RA'] += (not i_h == n - 1)
 209 vs
 210 :            # this one requires some additional rewriting since it
 211 :            # introduces divisions by zero
 212 :            f[head,  'STOP', 'LN'] += (i_h == 1)     # second word
 213 :            f[head, '-STOP', 'LN'] += (not i_h <= 1) # not first two
 214 :            f[head,  'STOP', 'LA'] += (i_h == 0)     # first word
 215 :            f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
 216 :            f[head,  'STOP', 'RN'] += (i_h == n - 2)     # second-to-last
 217 :            f[head, '-STOP', 'RN'] += (not i_h >= n - 2) # not last two
 218 :            f[head,  'STOP', 'RA'] += (i_h == n - 1)     # last word
 219 :            f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
 220 vs
 221 :            f[head,  'STOP', 'LN'] += (i_h == 1)     # second word
 222 :            f[head, '-STOP', 'LN'] += (not i_h == 1) # not second
 223 :            f[head,  'STOP', 'LA'] += (i_h == 0)     # first word
 224 :            f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
 225 :            f[head,  'STOP', 'RN'] += (i_h == n - 2)     # second-to-last
 226 :            f[head, '-STOP', 'RN'] += (not i_h == n - 2) # not second-to-last
 227 :            f[head,  'STOP', 'RA'] += (i_h == n - 1)     # last word
 228 :            f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
 229 vs
 230 "all words take the same number of arguments" interpreted as
 231 :for all heads:
 232 :    p_STOP(head, 'STOP', 'LN') = 0.3
 233 :    p_STOP(head, 'STOP', 'LA') = 0.5
 234 :    p_STOP(head, 'STOP', 'RN') = 0.4
 235 :    p_STOP(head, 'STOP', 'RA') = 0.7
 236 (which we easily may tweak in init_zeros())
 237 *** P_CHOOSE
 238 Go through the corpus, counting distances between heads and
 239 arguments. In [det nn vb nn], we give
 240 - f_{CHOOSE}(nn|det, R) +1/1 + C
 241 - f_{CHOOSE}(vb|det, R) +1/2 + C
 242 - f_{CHOOSE}(nn|det, R) +1/3 + C
 243   - If this were the full corpus, P_{CHOOSE}(nn|det, R) would have
 244     (1+1/3+2C) / sum_a f_{CHOOSE}(a|det, R)
 245
 246 The ROOT gets "each argument with equal probability", so in a sentence
 247 of three words, 1/3 for each (in [nn vb nn], 'nn' gets 2/3). Basically
 248 just a frequency count of the corpus...
 249
 250 In a sense there are no terminal probabilities, since an /h/ can only
 251 rewrite to an 'h' anyway (it's just a check for whether, at this
 252 location in the sentence, we have the right POS-tag).
 253 * [#C] Deferred
 254 http://wiki.python.org/moin/PythonSpeed/PerformanceTips Eg., use
 255 map/reduce/filter/[i for i in [i's]]/(i for i in [i's]) instead of
 256 for-loops; use local variables for globals (global variables or or
 257 functions), etc.
 258
 259 ** TODO when reestimating P_STOP etc, remove rules with p < epsilon   :OPTIMIZE:
 260 ** TODO inner_dmv, short ranges and impossible attachment             :OPTIMIZE:
 261 If s-t <= 2, there can be only one attachment below, so don't recurse
 262 with both Lattach=True and Rattach=True.
 263
 264 If s-t <= 1, there can be no attachment below, so only recurse with
 265 Lattach=False, Rattach=False.
 266
 267 Put this in the loop under rewrite rules (could also do it in the STOP
 268 section, but that would only have an effect on very short sentences).
 269 ** TODO clean up the module files                                     :PRETTIER:
 270 Is there better way to divide dmv and harmonic? There's a two-way
 271 dependency between the modules. Guess there could be a third file that
 272 imports both the initialization and the actual EM stuff, while a file
 273 containing constants and classes could be imported by all others:
 274 : dmv.py imports dmv_EM.py imports dmv_classes.py
 275 : dmv.py imports dmv_inits.py imports dmv_classes.py
 276
 277 ** TOGROK Some (tagged) sentences are bound to come twice             :OPTIMIZE:
 278 Eg, first sort and count, so that the corpus
 279 [['nn','vbd','det','nn'],
 280  ['vbd','nn','det','nn'],
 281  ['nn','vbd','det','nn']]
 282 becomes
 283 [(['nn','vbd','det','nn'],2),
 284  (['vbd','nn','det','nn'],1)]
 285 and then in each loop through sentences, make sure we handle the
 286 frequency correctly.
 287
 288 Is there much to gain here?
 289
 290 ** TOGROK tags as numbers or tags as strings?                         :OPTIMIZE:
 291 Need to clean up the representation.
 292
 293 Stick with tag-strings in initialization then switch to numbers for
 294 IO-algorithm perhaps? Can probably afford more string-matching in
 295 initialization..
 296 ** DONE if loc_h == t, no need to try right-attachment rules &v.v.    :OPTIMIZE:
 297    CLOSED: [2008-06-10 Tue 14:34]
 298 (and if loc_h == s, no need to try left-attachment rules.)
 299
 300 Modest speed increase (5%).
 301 ** DONE io.debug parameters should not call functions                 :OPTIMIZE:
 302    CLOSED: [2008-06-10 Tue 12:26]
 303 Exchanged all io.debug(str,'level') calls with statements of the form:
 304 :if 'level' in io.DEBUG:
 305 :    print str
 306
 307 and got an almost threefold speed increase on inner().
 308 ** DONE inner_dmv() should disregard rules with heads not in sent     :OPTIMIZE:
 309    CLOSED: [2008-06-08 Sun 10:18]
 310 If the sentence is "nn vbd det nn", we should not even look at rules
 311 where
 312 : rule.head() not in "nn vbd det nn".split()
 313 This is ruled out by getting rules from g.rules(LHS, sent).
 314
 315 Also, we optimize this further by saying we don't even recurse into
 316 attachment rules where
 317 : rule.head() not in sent[ s :r+1]
 318 : rule.head() not in sent[r+1:t+1]
 319 meaning, if we're looking at the span "vbd det", we only use
 320 attachment rules where both daughters are members of ['vbd','det']
 321 (although we don't (yet) care about removing rules that rewrite to the
 322 same tag if there are no duplicate tags in the span, etc., that would
 323 be a lot of trouble for little potential gain).
 324 * Adjacency and combining it with the inside-outside algorithm
 325 Each DMV_Rule has both a probN and a probA, for adjacencies. inner()
 326 and outer() needs the correct one in each case.
 327
 328 In each inner() call, loc_h is the location of the head of this
 329 dependency structure. In each outer() call, it's the head of the /Node/,
 330 the structure we're looking outside of.
 331
 332 We call inner() for each location of a head, and on each terminal,
 333 loc_h must equal s (and t). In the recursive attachment calls, we use
 334 the locations (sentence indices) of words to the left or right of the
 335 head in calls to inner(). /loc_h lets us check whether we need probN or
 336 probA/.
 337 ** Possible alternate type of adjacency
 338 K&M's adjacency is just whether or not an argument has been generated
 339 in the current direction yet. One could also make a stronger type of
 340 adjacency, where h and a are not adjacent if b is in between, eg. with
 341 the sentence "a b h" and the structure ((h->a), (a->b)), h is
 342 K&M-adjacent to a, but not next to a, since b is in between. It's easy
 343 to check this type of adjacency in inner(), but it needs new rules for
 344 P_STOP reestimation.
 345 * Expectation Maximation in IO/DMV-terms
 346 outer(s,t,Node) and inner(s,t,Node) calculates the expected number of
 347 trees (CNF-)headed by Node from *s* to *t* (sentence positions). This uses
 348 the P_STOP and P_CHOOSE values, which have been conveniently
 349 distributed into CNF rules as probN and probA (non-adjacent and
 350 adjacent probabilites).
 351
 352 When re-estimating, we use the expected values from outer() and
 353 inner() to get new values for P_STOP and P_CHOOSE. When we've
 354 re-estimated for the entire corpus, we distribute P_STOP and P_CHOOSE
 355 into the CNF rules again, so that in the next round we use new probN
 356 and probA to find outer- and inner-probabilites.
 357
 358 The distribution of P_STOP and P_CHOOSE into CNF rules also happens in
 359 init_normalize() (here along with the creation of P_STOP and
 360 P_CHOOSE); P_STOP is used to create CNF rules where one branch of the
 361 rule is STOP, P_CHOOSE is used to create rules of the form
 362 : h  -> h  _a_
 363 : h_ -> h_ _a_
 364
 365 Since "adjacency" is not captured in regular CNF rules, we need two
 366 probabilites for each rule, and outer() and inner() have to know when
 367 to use which.
 368
 369
 370 * Python-stuff
 371 # <<python>>
 372 Make those debug statements steal a bit less attention in emacs:
 373 :(font-lock-add-keywords
 374 : 'python-mode                   ; not really regexp, a bit slow
 375 : '(("^\\( *\\)\\(\\if +'.+' +in +io.DEBUG. *\\(
 376 :\\1    .+$\\)+\\)" 2 font-lock-preprocessor-face t)))
 377 :(font-lock-add-keywords
 378 : 'python-mode
 379 : '(("\\<\\(\\(io\\.\\)?debug(.+)\\)" 1 font-lock-preprocessor-face t)))
 380
 381 - [[file:src/pseudo.py][pseudo.py]]
 382 - http://nltk.org/doc/en/structured-programming.html recursive dynamic
 383 - http://nltk.org/doc/en/advanced-parsing.html
 384 - http://jaynes.colorado.edu/PythonIdioms.html
 385
 386
 387
 388 * Git
 389 Repository web page: http://repo.or.cz/w/dmvccm.git
 390
 391 Setting up a new project:
 392 : git init
 393 : git add .
 394 : git commit -m "first release"
 395
 396 Later on: (=-a= does =git rm= and =git add= automatically)
 397 : git init
 398 : git commit -a -m "some subsequent release"
 399
 400 Then push stuff up to the remote server:
 401 : git push git+ssh://username@repo.or.cz/srv/git/dmvccm.git master
 402
 403 (=eval `ssh-agent`= and =ssh-add= to avoid having to type in keyphrase all
 404 the time)
 405
 406 Make a copy of the (remote) master branch:
 407 : git clone git://repo.or.cz/dmvccm.git
 408
 409 Make and name a new branch in this folder
 410 : git checkout -b mybranch
 411
 412 To save changes in =mybranch=:
 413 : git commit -a
 414
 415 Go back to the master branch (uncommitted changes from =mybranch= are
 416 carried over):
 417 : git checkout master
 418
 419 Try out:
 420 : git add --interactive
 421
 422 Good tutorial:
 423 http://www-cs-students.stanford.edu/~blynn//gitmagic/