From 65e9744d5b8cda576efaa04405366c28030d2901 Mon Sep 17 00:00:00 2001 From: Kevin Brubeck Unhammer Date: Mon, 16 Jun 2008 00:06:59 +0200 Subject: [PATCH] PSTOP done, PCHOOSE close to done--but still gives certain p's > 1.0, needs debugging --- DMVCCM.html | 423 +++++++++++++++++++++++++++++++---------------------- DMVCCM.org | 122 ++++++--------- DMVCCM.org_archive | 81 +++++++++- src/dmv.py | 59 +++++--- src/dmv.pyc | Bin 24992 -> 24352 bytes 5 files changed, 412 insertions(+), 273 deletions(-) diff --git a/DMVCCM.html b/DMVCCM.html index e72cb06..a202c0e 100755 --- a/DMVCCM.html +++ b/DMVCCM.html @@ -6,26 +6,59 @@ lang="en" xml:lang="en"> DMV/CCM – todo-list / progress - +

DMV/CCM – todo-list / progress

1 dmvccm report and project
2 outer probabilities
3 [#B] P_STOP and P_CHOOSE for IO/EM (reestimation)
2 P_STOP and P_CHOOSE for IO/EM (reestimation) +
- 2.1 [#A] P_CHOOSE formula:
- 2.2 P_STOP formulas for various dir and adj:
+
3 outer probabilities
4 Find Most Probable Parse of given test sentence
5 Combine CCM with DMV
5 Combine CCM with DMV +
- 5.1 Make inner() and outer() also allow left-first attachment
+
6 Get a dependency parsed version of WSJ to test with
7 Initialization
8 [#C] Deferred
9 Adjacency and combining it with the inside-outside algorithm
7 Initialization +
+
8 [#C] Deferred +
+
9 Adjacency and combining it with the inside-outside algorithm +
- 9.1 Possible alternate type of adjacency
+
10 Expectation Maximation in IO/DMV-terms
11 Python-stuff
12 Git

(But absolute, extended, really-quite-dead-now deadline: August 31…) +

+Archived entries from this file.

2 DONE outer probabilities

2 P_STOP and P_CHOOSE for IO/EM (reestimation)

dmv-P_STOP +Remember: The P_STOP formula is upside-down (left-to-right also). +(In the article..not the thesis) +

+ +

2.1 TODO [#A] P_CHOOSE formula:

+ +

+Note taken on 2008-06-15 Sun 23:41
+Mostly done, although there is something odd with either the formulas +or the way I calculate them; I get probabilities more than 1.0 after +doing r.probN = (1-p_stopN)*p_choose and r.probA = (1-p_stopA)*p_choose. + +

+ +

Assuming this: +

+ ++ + + + + + + +

P_CHOOSE(a : h,R) =	∑_corpus ∑_s=loc(h) ∑_{t > loc(h)} ∑_{loc(h) < r <= t} c(s, r-1, h_, …) * c(r,t,_a_,…)
	∑_corpus ∑_s=loc(h) ∑_{t > loc(h)} c(s,t,h, …)

P_CHOOSE(a : h,L) =	∑_corpus ∑_s<loc(h) ∑_t>=loc(h) ∑_r<loc(h) c(s,r,_a_, …) * c(r+1, t, h_, …)
	∑_corpus ∑_s<loc(h) ∑_t>=loc(h) c(s,t,h_,…)

+ +t >= loc(h) since there are many possibilites for right-attachments +below, and each of them alone gives a lower probability (through +multiplication) to the upper tree (so add them all) + +

+The reason we have to check both children of the attachments is that we +have to make sure they are contiguous (otherwise we would have no way +of ruling out eg. h_->_b_,_b_->b_->_a_, where h_ covers s and t,_b_ is +from s to x<r and _ a_ is from s to r). +

+ +

2.2 DONE P_STOP formulas for various dir and adj:

+ +

CLOSED: 2008-06-15 Sun 23:40
+Assuming this: +

+ ++ + + + + + + + + + + + + +

P_STOP(STOP : h,L,non_adj) =	∑_corpus ∑_s<loc(h) ∑_t>=loc(h) c(s,t,_h_, …)
	∑_corpus ∑_s<loc(h) ∑_t>=loc(h) c(s,t,h_, …)

P_STOP(STOP : h,L,adj) =	∑_corpus ∑_s=loc(h) ∑_t>=loc(h) c(s,t,_h_, …)
	∑_corpus ∑_s=loc(h) ∑_t>=loc(h) c(s,t,h_, …)

P_STOP(STOP : h,R,non_adj) =	∑_corpus ∑_s=loc(h) ∑_t>loc(h) c(s,t,h_, …)
	∑_corpus ∑_s=loc(h) ∑_t>loc(h) c(s,t,h, …)

P_STOP(STOP : h,R,adj) =	∑_corpus ∑_s=loc(h) ∑_t=loc(h) c(s,t,h_, …)
	∑_corpus ∑_s=loc(h) ∑_t=loc(h) c(s,t,h, …)

+ + +

+(And P_STOP(-STOP|…) = 1 - P_STOP(STOP|…) ) +

+ +

3 DONE outer probabilities

CLOSED: 2008-06-12 Thu 11:11
There are 6 different configurations here, based on what the above @@ -197,81 +316,7 @@ Also, unlike in -

3 TODO [#B] P_STOP and P_CHOOSE for IO/EM (reestimation)

- -

dmv-P_STOP -Remember: The P_STOP formula is upside-down (left-to-right also). -(In the article..not the thesis) -

P_STOP formulas for various dir and adj:
-Assuming this: - - -- - - - - - - - - - - - - -

P_STOP(STOP : h,L,non_adj) =	∑_corpus ∑_s<loc(h) ∑_t>=loc(h) c(s,t,_h_, …)
	∑_corpus ∑_s<loc(h) ∑_t>=loc(h) c(s,t,h_, …)

P_STOP(STOP : h,L,adj) =	∑_corpus ∑_s=loc(h) ∑_t>=loc(h) c(s,t,_h_, …)
	∑_corpus ∑_s=loc(h) ∑_t>=loc(h) c(s,t,h_, …)

P_STOP(STOP : h,R,non_adj) =	∑_corpus ∑_s=loc(h) ∑_t>loc(h) c(s,t,h_, …)
	∑_corpus ∑_s=loc(h) ∑_t>loc(h) c(s,t,h, …)

P_STOP(STOP : h,R,adj) =	∑_corpus ∑_s=loc(h) ∑_t=loc(h) c(s,t,h_, …)
	∑_corpus ∑_s=loc(h) ∑_t=loc(h) c(s,t,h, …)

- - -

-(And P_STOP(-STOP|…) = 1 - P_STOP(STOP|…) ) -

P_CHOOSE formula:
-Assuming this: - - -- - - - - - - -

P_CHOOSE(a : h,R) =	∑_corpus ∑_s=loc(h) ∑_{t > loc(h)} ∑_{loc(h) < r <= t} c(s, r-1, h_, …) * c(r,t,_a_,…)
	∑_corpus ∑_s=loc(h) ∑_{t > loc(h)} c(s,t,h, …)

P_CHOOSE(a : h,L) =	∑_corpus ∑_s<loc(h) ∑_t>=loc(h) ∑_r<loc(h) c(s,r,_a_, …) * c(r+1, t, h_, …)
	∑_corpus ∑_s<loc(h) ∑_t>=loc(h) c(s,t,h_,…)

- -t >= loc(h) since there are many possibilites for right-attachments -below, and each of them alone gives a lower probability (through -multiplication) to the upper tree (so add them all) - -

-The reason we have to check both children of the attachments is that we -have to make sure they are contiguous (otherwise we would have no way -of ruling out eg. h_->_b_,_b_->b_->_a_, where h_ covers s and t,_b_ is -from s to x<r and _ a_ is from s to r). -

DONE [#A] How do we only count from completed trees?
-CLOSED: 2008-06-13 Fri 11:40
-Use c(s,t,Node); inner * outer / P_sent - -
DONE [#A] c(s,t,Node)
-CLOSED: 2008-06-13 Fri 11:38
-= inner * outer / P_sent -
-implemented as inner * outer / inner_sent -
-

@@ -301,11 +346,15 @@ for rewrites, for loc_dep select the one that has the highest p

Page 108 (pdf: 124) of Klein's thesis gives info about this. -

TODO Make inner() and outer() also allow left-first attachment
-Using P_ORDER(left-first | w) etc. -

+ +

5.1 TODO Make inner() and outer() also allow left-first attachment

+ +

Using P_ORDER(left-first | w) etc. +

@@ -327,22 +376,50 @@ Using P_ORDER(left-first | w) etc.

We go through the corpus, since the probabilities are based on how far away in the sentence arguments are from their heads. -

TOGROK CCM Initialization
-P_SPLIT used here… how, again? -
DONE Separate initialization to another file? PRETTIER
-CLOSED: 2008-06-08 Sun 12:51
+
+ + +
+
7.1 TOGROK CCM Initialization
+
+ +
P_SPLIT used here… how, again? +
+ +
+ +
+
7.2 DONE Separate initialization to another file? PRETTIER
+
+ +
CLOSED: 2008-06-08 Sun 12:51
harmonic.py -
DONE DMV Initialization probabilities
-(from initialization frequency) -
DONE DMV Initialization frequencies
-CLOSED: 2008-05-27 Tue 20:04
-
- P_STOP
  -P_STOP is not well defined by K&M. One possible interpretation given +
  + + + +
  +
  7.3 DONE DMV Initialization probabilities
  +
  + +
  (from initialization frequency) +
  + +
  + +
  +
  7.4 DONE DMV Initialization frequencies
  +
  + +
  CLOSED: 2008-05-27 Tue 20:04
  +
  +
  + +
  +
  7.4.1 P_STOP
  +
  + +
  P_STOP is not well defined by K&M. One possible interpretation given the sentence [det nn vb nn] is
  f_{STOP}( STOP|det, L, adj) +1 @@ -357,7 +434,7 @@ the sentence [det nn vb nn] is f_{STOP}( STOP|nn, L, non_adj) +1 # since there's at least one to the left f_{STOP}(-STOP|nn, L, non_adj) +0
  -
  +
  
  TODO tweak
  
  f[head, 'STOP', 'LN'] += (i_h <= 1) # first two words @@ -405,11 +482,17 @@ for all heads: (which we easily may tweak in init_zeros())
  
  - -
  P_CHOOSE
  -Go through the corpus, counting distances between heads and +
  + +
  + +
  +
  7.4.2 P_CHOOSE
  +
  + +
  Go through the corpus, counting distances between heads and arguments. In [det nn vb nn], we give -
  +
  
  f_CHOOSE(nn|det, R) +1/1 + C
  @@ -436,10 +519,8 @@ just a frequency count of the corpus… In a sense there are no terminal probabilities, since an h can only rewrite to an 'h' anyway (it's just a check for whether, at this location in the sentence, we have the right POS-tag). -
  -
  - -
  +
  +
  @@ -453,13 +534,24 @@ map/reduce/filter/[i for i in [i's]]/(i for i in [i's]) instead of for-loops; use local variables for globals (global variables or or functions), etc.
  -
  - TODO when reestimating P_STOP etc, remove rules with p < epsilon OPTIMIZE
    -
  - TODO inner_dmv, short ranges and impossible attachment    OPTIMIZE
    -If s-t <= 2, there can be only one attachment below, so don't recurse -with both Lattach=True and Rattach=True. + + +
    +
    8.1 TODO when reestimating P_STOP etc, remove rules with p < epsilon    OPTIMIZE
    +
    + +
    + +
    + +
    +
    8.2 TODO inner_dmv, short ranges and impossible attachment    OPTIMIZE
    +
    + +
    If s-t <= 2, there can be only one attachment below, so don't recurse +with both Lattach=True and Rattach=True. +
    
    If s-t <= 1, there can be no attachment below, so only recurse with Lattach=False, Rattach=False. @@ -467,9 +559,15 @@ Lattach=False, Rattach=False.
    Put this in the loop under rewrite rules (could also do it in the STOP section, but that would only have an effect on very short sentences). -
  - TODO clean up the module files PRETTIER
    -Is there better way to divide dmv and harmonic? There's a two-way +
    + + + +
    +
    8.3 TODO clean up the module files PRETTIER
    +
    + +
    Is there better way to divide dmv and harmonic? There's a two-way dependency between the modules. Guess there could be a third file that imports both the initialization and the actual EM stuff, while a file containing constants and classes could be imported by all others: @@ -477,10 +575,16 @@ containing constants and classes could be imported by all others: dmv.py imports dmv_EM.py imports dmv_classes.py dmv.py imports dmv_inits.py imports dmv_classes.py +
    +
    -
  - TOGROK Some (tagged) sentences are bound to come twice OPTIMIZE
    -Eg, first sort and count, so that the corpus + + +
    +
    8.4 TOGROK Some (tagged) sentences are bound to come twice OPTIMIZE
    +
    + +
    Eg, first sort and count, so that the corpus [['nn','vbd','det','nn'], ['vbd','nn','det','nn'], ['nn','vbd','det','nn']] @@ -489,60 +593,25 @@ becomes (['vbd','nn','det','nn'],1)] and then in each loop through sentences, make sure we handle the frequency correctly. - +
    
    Is there much to gain here?
    -
  - TOGROK tags as numbers or tags as strings? OPTIMIZE
    -Need to clean up the representation. + + + +
    +
    8.5 TOGROK tags as numbers or tags as strings? OPTIMIZE
    +
    + +
    Need to clean up the representation. +
    
    Stick with tag-strings in initialization then switch to numbers for IO-algorithm perhaps? Can probably afford more string-matching in initialization.. -
  - DONE if loc_h == t, no need to try right-attachment rules &v.v. OPTIMIZE
    -CLOSED: 2008-06-10 Tue 14:34
    -(and if loc_h == s, no need to try left-attachment rules.) - -
    -Modest speed increase (5%). -
  - DONE io.debug parameters should not call functions OPTIMIZE
    -CLOSED: 2008-06-10 Tue 12:26
    -Exchanged all io.debug(str,'level') calls with statements of the form: -
```
-if 'level' in io.DEBUG:
-    print str
-
```
    - -
    -and got an almost threefold speed increase on inner(). -
  - DONE inner_dmv() should disregard rules with heads not in sent OPTIMIZE
    -CLOSED: 2008-06-08 Sun 10:18
    -If the sentence is "nn vbd det nn", we should not even look at rules -where -
```
- rule.head() not in "nn vbd det nn".split()
-
```
    -This is ruled out by getting rules from g.rules(LHS, sent). - -
    -Also, we optimize this further by saying we don't even recurse into -attachment rules where -
```
- rule.head() not in sent[ s :r+1]
- rule.head() not in sent[r+1:t+1]
-
```
    -meaning, if we're looking at the span "vbd det", we only use -attachment rules where both daughters are members of ['vbd','det'] -(although we don't (yet) care about removing rules that rewrite to the -same tag if there are no duplicate tags in the span, etc., that would -be a lot of trouble for little potential gain). -
  +
  @@ -564,17 +633,21 @@ We call inner() for each location of a head, and on each terminal, loc_h must equal s (and t). In the recursive attachment calls, we use the locations (sentence indices) of words to the left or right of the head in calls to inner(). loc_h lets us check whether we need probN or probA. -
  - Possible alternate type of adjacency
    -K&M's adjacency is just whether or not an argument has been generated +
    + + +
    +
    9.1 Possible alternate type of adjacency
    +
    + +
    K&M's adjacency is just whether or not an argument has been generated in the current direction yet. One could also make a stronger type of adjacency, where h and a are not adjacent if b is in between, eg. with the sentence "a b h" and the structure ((h->a), (a->b)), h is K&M-adjacent to a, but not next to a, since b is in between. It's easy to check this type of adjacency in inner(), but it needs new rules for P_STOP reestimation. -
  +
  @@ -722,6 +795,6 @@ Good tutorial:
  Author: Kevin Brubeck Unhammer <K.BrubeckUnhammer at student uva nl >
  -
  Date: 2008/06/15 17:59:26
  +
  Date: 2008/06/15 23:58:29
  
  Skrive vha. emacs + org-mode
  diff --git a/DMVCCM.org b/DMVCCM.org index 650c1e8..957d440 100755 --- a/DMVCCM.org +++ b/DMVCCM.org @@ -6,12 +6,11 @@ #+TITLE: DMV/CCM -- todo-list / progress #+AUTHOR: Kevin Brubeck Unhammer #+EMAIL: K.BrubeckUnhammer at student uva nl -#+OPTIONS: H:4 -#+OPTIONS: toc:3 #+OPTIONS: ^:{} #+LANGUAGE: en #+SEQ_TODO: TOGROK TODO DONE + * dmvccm report and project DEADLINE: <2008-06-30 Mon> - [[file:src/dmv.py][dmv.py]] @@ -19,6 +18,51 @@ - [[file:src/harmonic.py::harmonic%20py%20initialization%20for%20dmv][harmonic.py]] (But absolute, extended, really-quite-dead-now deadline: August 31...) + +[[http://www.student.uib.no/~kun041/dmvccm/DMVCCM_archive.html][Archived entries]] from this file. +* P_STOP and P_CHOOSE for IO/EM (reestimation) +[[file:src/dmv.py::DMV%20probabilities][dmv-P_STOP]] +Remember: The P_{STOP} formula is upside-down (left-to-right also). +(In the article..not the [[http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf][thesis]]) + +** TODO [#A] P_CHOOSE formula: + - Note taken on [2008-06-15 Sun 23:41] \\ + Mostly done, although there is something odd with either the formulas + or the way I calculate them; I get probabilities more than 1.0 after + doing r.probN = (1-p_stopN)*p_choose and r.probA = (1-p_stopA)*p_choose. + +Assuming this: + +| P_{CHOOSE}(a : h,R) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t > loc(h)} \sum_{loc(h) < r <= t} c(s, r-1, h_, ...) * c(r,t,_a_,...) | +| | \sum_{corpus} \sum_{s=loc(h)} \sum_{t > loc(h)} c(s,t,h, ...) | +| | | +| P_{CHOOSE}(a : h,L) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{r=loc(h)} c(s,t,h_,...) | +t >= loc(h) since there are many possibilites for right-attachments +below, and each of them alone gives a lower probability (through +multiplication) to the upper tree (so add them all) + +The reason we have to check /both/ children of the attachments is that we +have to make sure they are contiguous (otherwise we would have no way +of ruling out eg. h_->_b_,_b_->b_->_a_, where h_ covers *s* and *t*,_b_ is +from *s* to *x=loc(h)} c(s,t,_h_, ...) | +| | \sum_{corpus} \sum_{s=loc(h)} c(s,t,h_, ...) | +| | | +| P_{STOP}(STOP : h,L,adj) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>=loc(h)} c(s,t,_h_, ...) | +| | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>=loc(h)} c(s,t,h_, ...) | +| | | +| P_{STOP}(STOP : h,R,non_adj) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>loc(h)} c(s,t,h_, ...) | +| | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>loc(h)} c(s,t,h, ...) | +| | | +| P_{STOP}(STOP : h,R,adj) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t=loc(h)} c(s,t,h_, ...) | +| | \sum_{corpus} \sum_{s=loc(h)} \sum_{t=loc(h)} c(s,t,h, ...) | + +(And P_{STOP}(-STOP|...) = 1 - P_{STOP}(STOP|...) ) * DONE outer probabilities CLOSED: [2008-06-12 Thu 11:11] # <> @@ -115,52 +159,6 @@ sentence. \Tree [.{$h$} {$_{r} h _{s-1}$\\ L} [.{$_{s} \ulcorner a\urcorner _t$\\ Node} ] ] -* TODO [#B] P_STOP and P_CHOOSE for IO/EM (reestimation) -[[file:src/dmv.py::DMV%20probabilities][dmv-P_STOP]] -Remember: The P_{STOP} formula is upside-down (left-to-right also). -(In the article..not the [[http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf][thesis]]) - -** P_STOP formulas for various dir and adj: -Assuming this: - -| P_{STOP}(STOP : h,L,non_adj) = | \sum_{corpus} \sum_{s=loc(h)} c(s,t,_h_, ...) | -| | \sum_{corpus} \sum_{s=loc(h)} c(s,t,h_, ...) | -| | | -| P_{STOP}(STOP : h,L,adj) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>=loc(h)} c(s,t,_h_, ...) | -| | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>=loc(h)} c(s,t,h_, ...) | -| | | -| P_{STOP}(STOP : h,R,non_adj) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>loc(h)} c(s,t,h_, ...) | -| | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>loc(h)} c(s,t,h, ...) | -| | | -| P_{STOP}(STOP : h,R,adj) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t=loc(h)} c(s,t,h_, ...) | -| | \sum_{corpus} \sum_{s=loc(h)} \sum_{t=loc(h)} c(s,t,h, ...) | - -(And P_{STOP}(-STOP|...) = 1 - P_{STOP}(STOP|...) ) -** P_CHOOSE formula: -Assuming this: - -| P_{CHOOSE}(a : h,R) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t > loc(h)} \sum_{loc(h) < r <= t} c(s, r-1, h_, ...) * c(r,t,_a_,...) | -| | \sum_{corpus} \sum_{s=loc(h)} \sum_{t > loc(h)} c(s,t,h, ...) | -| | | -| P_{CHOOSE}(a : h,L) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{r=loc(h)} c(s,t,h_,...) | -t >= loc(h) since there are many possibilites for right-attachments -below, and each of them alone gives a lower probability (through -multiplication) to the upper tree (so add them all) - -The reason we have to check /both/ children of the attachments is that we -have to make sure they are contiguous (otherwise we would have no way -of ruling out eg. h_->_b_,_b_->b_->_a_, where h_ covers *s* and *t*,_b_ is -from *s* to *x 0.0: p_stopN = f[dir+'NSTOP','num',h] / p_stopN + p_stopA = f[dir+'ASTOP','den',h] if p_stopA > 0.0: p_stopA = f[dir+'ASTOP','num',h] / p_stopA - if r.L() == STOP or r.R() == STOP: + if r.L() == STOP or r.R() == STOP: # stop rules if 'reest' in io.DEBUG: print "p(STOP|%d=%s,%s,N): %.4f (was: %.4f)"%(h,g.numtag(h),dir, p_stopN, r.probN) print "p(STOP|%d=%s,%s,A): %.4f (was: %.4f)"%(h,g.numtag(h),dir, p_stopA, r.probA) r.probN = p_stopN r.probA = p_stopA - else: # attachments + + else: # attachment rules pchoose = f[dir+'CHOOSE','den',h] if pchoose > 0.0: if head(r.R()) == h: # left attachment a = head(r.L()) elif head(r.L()) == h: # right attachment a = head(r.R()) - pchoose = f['LCHOOSE','num',h, a] / pchoose + pchoose = f[dir+'CHOOSE','num',h, a] / pchoose if 'reest' in io.DEBUG: print "p(%d=%s|%d=%s,%s): %.4f"%(a,g.numtag(a),h,g.numtag(h),dir, pchoose) - r.probA = (1-p_stopA) * pchoose r.probN = (1-p_stopN) * pchoose + r.probA = (1-p_stopA) * pchoose @@ -636,9 +648,11 @@ def testgrammar(): def testreestimation(): io.DEBUG.add('reest') g = testgrammar() - if not reestimate(g, testcorpus) == {('LNSTOP', 'den', 3): 12.212773236178391, ('RCHOOSE', 'num', 4, 4): 21.165993113329321, ('RASTOP', 'den', 2): 4.0, ('RNSTOP', 'num', 4): 2.5553487221351365, ('LNSTOP', 'den', 2): 1.274904052793207, ('LCHOOSE', 'num', 0, 4): 61.684182043830802, ('LASTOP', 'num', 1): 14.999999999999995, ('RASTOP', 'den', 3): 15.0, ('RCHOOSE', 'num', 4, 2): 14.336991917519207, ('LCHOOSE', 'num', 0, 1): 37.021815131880523, ('LASTOP', 'num', 4): 16.65701084787457, ('RCHOOSE', 'num', 0, 1): 7.0, ('LASTOP', 'num', 0): 4.1600647714443468, ('LCHOOSE', 'num', 2, 4): 24.584578647023847, ('LNSTOP', 'den', 4): 6.0170669155897105, ('RCHOOSE', 'num', 3, 2): 12.459705909121311, ('LASTOP', 'num', 3): 2.7872267638216113, ('RCHOOSE', 'num', 3, 1): 33.272425367699817, ('RCHOOSE', 'num', 3, 0): 31.14144593225323, ('LASTOP', 'num', 2): 2.9723139990470515, ('LCHOOSE', 'den', 4): 6.0170669155897105, ('LCHOOSE', 'num', 4, 2): 9.1747523009571736, ('LCHOOSE', 'num', 2, 1): 19.69614336189014, ('LASTOP', 'den', 2): 4.0, ('RCHOOSE', 'den', 4): 2.8705211946979836, ('RNSTOP', 'den', 3): 12.945787931730905, ('RCHOOSE', 'num', 4, 1): 18.8586091476162, ('LCHOOSE', 'num', 4, 4): 38.665348775409555, ('LASTOP', 'den', 3): 14.999999999999996, ('RCHOOSE', 'den', 3): 12.945787931730905, ('LCHOOSE', 'num', 0, 2): 11.067546558158417, ('RNSTOP', 'den', 2): 0.0, ('LCHOOSE', 'num', 3, 0): 7.0000000000000009, ('LASTOP', 'den', 0): 8.0, ('RCHOOSE', 'den', 2): 0.0, ('LCHOOSE', 'den', 1): 0.0, ('RASTOP', 'num', 4): 19.44465127786486, ('RNSTOP', 'den', 1): 3.1966410324085777, ('LASTOP', 'den', 1): 14.999999999999995, ('RCHOOSE', 'den', 1): 3.1966410324085777, ('LCHOOSE', 'den', 0): 4.6540557322109795, ('RASTOP', 'num', 3): 4.1061665495365558, ('RNSTOP', 'den', 0): 4.8282499043902476, ('LNSTOP', 'num', 4): 5.3429891521254289, ('RCHOOSE', 'num', 4, 3): 17.107681762009616, ('RCHOOSE', 'den', 0): 4.8282499043902476, ('LCHOOSE', 'den', 3): 12.212773236178391, ('RASTOP', 'num', 2): 4.0, ('LCHOOSE', 'num', 2, 3): 13.357495028303836, ('RCHOOSE', 'num', 0, 3): 7.0, ('LASTOP', 'den', 4): 22.0, ('LCHOOSE', 'den', 2): 1.274904052793207, ('RASTOP', 'num', 1): 12.400273895299103, ('LNSTOP', 'num', 2): 1.0276860009529487, ('RCHOOSE', 'num', 1, 0): 35.275732604734458, ('LCHOOSE', 'num', 4, 0): 38.815876450753834, ('RCHOOSE', 'num', 0, 2): 5.4153585824117219, ('RASTOP', 'num', 0): 3.1717500956097533, ('RCHOOSE', 'num', 1, 3): 44.726704286252108, ('LNSTOP', 'num', 3): 12.212773236178391, ('LCHOOSE', 'num', 4, 1): 79.825243724755524, ('RASTOP', 'den', 4): 22.0, ('RNSTOP', 'den', 4): 2.8705211946979836, ('LNSTOP', 'num', 0): 3.8399352285556518, ('RCHOOSE', 'num', 4, 0): 25.799832884567792, ('LCHOOSE', 'num', 0, 3): 29.062168307358732, ('LNSTOP', 'num', 1): 0.0, ('RCHOOSE', 'num', 0, 4): 17.272366992134707, ('LCHOOSE', 'num', 3, 4): 22.334127121479728, ('RCHOOSE', 'num', 3, 4): 68.67411582483453, ('RNSTOP', 'num', 0): 4.8282499043902476, ('LCHOOSE', 'num', 3, 2): 3.0, ('LCHOOSE', 'num', 2, 0): 13.84015209565697, ('RCHOOSE', 'num', 1, 2): 19.929658772364007, ('LCHOOSE', 'num', 3, 1): 48.942276305039663, ('RNSTOP', 'num', 1): 2.5997261047008959, ('LNSTOP', 'den', 1): 0.0, ('RCHOOSE', 'num', 1, 4): 84.97599440279366, ('RASTOP', 'den', 0): 8.0, ('RNSTOP', 'num', 2): 0.0, ('LNSTOP', 'den', 0): 4.6540557322109795, ('LCHOOSE', 'num', 4, 3): 58.697169235084786, ('RASTOP', 'den', 1): 15.0, ('RNSTOP', 'num', 3): 10.893833450463443}: - print "sthg different in reestimation" - + f = reestimate(g, testcorpus) + f_stops = {('LNSTOP', 'den', 3): 12.212773236178391, ('RASTOP', 'den', 2): 4.0, ('RNSTOP', 'num', 4): 2.5553487221351365, ('LNSTOP', 'den', 2): 1.274904052793207, ('LASTOP', 'num', 1): 14.999999999999995, ('RASTOP', 'den', 3): 15.0, ('LASTOP', 'num', 4): 16.65701084787457, ('LASTOP', 'num', 0): 4.1600647714443468, ('LNSTOP', 'den', 4): 6.0170669155897105, ('LASTOP', 'num', 3): 2.7872267638216113, ('LASTOP', 'num', 2): 2.9723139990470515, ('LASTOP', 'den', 2): 4.0, ('RNSTOP', 'den', 3): 12.945787931730905, ('LASTOP', 'den', 3): 14.999999999999996, ('RNSTOP', 'den', 2): 0.0, ('LASTOP', 'den', 0): 8.0, ('RASTOP', 'num', 4): 19.44465127786486, ('RNSTOP', 'den', 1): 3.1966410324085777, ('LASTOP', 'den', 1): 14.999999999999995, ('RASTOP', 'num', 3): 4.1061665495365558, ('RNSTOP', 'den', 0): 4.8282499043902476, ('LNSTOP', 'num', 4): 5.3429891521254289, ('RASTOP', 'num', 2): 4.0, ('LASTOP', 'den', 4): 22.0, ('RASTOP', 'num', 1): 12.400273895299103, ('LNSTOP', 'num', 2): 1.0276860009529487, ('RASTOP', 'num', 0): 3.1717500956097533, ('LNSTOP', 'num', 3): 12.212773236178391, ('RASTOP', 'den', 4): 22.0, ('RNSTOP', 'den', 4): 2.8705211946979836, ('LNSTOP', 'num', 0): 3.8399352285556518, ('LNSTOP', 'num', 1): 0.0, ('RNSTOP', 'num', 0): 4.8282499043902476, ('RNSTOP', 'num', 1): 2.5997261047008959, ('LNSTOP', 'den', 1): 0.0, ('RASTOP', 'den', 0): 8.0, ('RNSTOP', 'num', 2): 0.0, ('LNSTOP', 'den', 0): 4.6540557322109795, ('RASTOP', 'den', 1): 15.0, ('RNSTOP', 'num', 3): 10.893833450463443} + for k,v in f_stops.iteritems(): + if not f[k] == v: + print "Regression!(?) Something changed in the P_STOP reestimation" def testgrammar_a(): # Non, Adj @@ -687,6 +701,7 @@ def testreestimation_h(): g = testgrammar_h() reestimate(g,['h h h'.split()]) + def regression_tests(): def test(wanted, got): if not wanted == got: @@ -712,12 +727,14 @@ def regression_tests(): if __name__ == "__main__": io.DEBUG.clear() - +# io.DEBUG.add('reest_attach') # import profile # profile.run('testreestimation()') import timeit print timeit.Timer("dmv.testreestimation()",'''import dmv reload(dmv)''').timeit(1) - regression_tests() + print "TODO: P_CHOOSE can not be right... (certain p's > 1.0)" +if __name__ == "__main__": + regression_tests() diff --git a/src/dmv.pyc b/src/dmv.pyc index a439638ce3fc43a71c8eaa90db867fed850a2bcd..905217767ca80bae4cce9e2f89194d927767b50a 100644 GIT binary patch delta 3512 zcwU88eQaA-6~FgA``OR-OPthk;-D?j7 zF8H&|L6l)y@sW~5&A`h(Vs&mX=I}9@<4DC%Dln8Eds{0~eH?orjs_zRANsZ35{oH# zLN?KWfl4Inbt2?V7TY@9Rs|j2^3Z+AhIIfoE{dB}8euL(b)hzP!2?GYJfzSL5i}BG zs&(B%&I;7QX^uq7Fj6B4-Odj!KFH559)tELZnj!Cu`ZAe-kK@33B#?;PcsMWYQn~P zQm!J_uMo!9Y^8ZM#kT)@R$icIzu9HTys&1%*O9XLe-j>Je~$Mx*ZGFPw}pLgr04G1 zT#HuD*3PxKcCN#g---H+LI!t_c6S z=7IK#Yj*K*GP{@{v*0%!YsLM#1&n+!IlXdY^bK0o1Ms?($rSZuO4n2A`67}O^I7gL z#^r2bN!I0D9$t#;p-)UFwV2$k%6(v<70p)6jqe)#7cj``D4aEuv;0 zO6=+#JE9$i_pQ!JH0-v$*LoE{2KXg3cn0ZiF!vVH5IzS_=}GfPVezqH`WP#XjZOt= zKW!%h4bqKtkhZ~78wpS!yzc>|gGOjO?c;;Aiv|r=I}JPRAPpJlsz(R=Wb6tZWiO6z zqQ7E)gi0S{L;H4BC4%*&@>mEDK`og3#6?k4;t*R`{GrRz(&f6MxjnZDfx_&<4DeUunt<#BP8c1SvT$& zIEmNb2nHu$ag2Zrx1`_dO9n{ZOYIN>W|$!>P7hY773VAL7k8$sHp!SOY+k6{2yj|} zs@4WQ2ti9oumbWL0sU`$9+DL>vc+?pc{?@WyxIT{nNgbOu?=v^0DElz_Kso%>SIb( z<)!=Y&0t*{)t|dBrRNIy0ruwplWb<9i%P6C(bE8@5h43Z>CAELWlv005))8g#Stu5 zE%l1IAY@#tLQi(?-Lc>PuU`M|AZ~8d47dbtW^Zyo5Y8o7oA9&*8&agbcd9jvN}NPzHIPY$O6kVb-EuAq#1-l&hOFiTZPnn?2VCN7_a@94~vYPRGkumd&}=C<~5P)sAR`BW;s5IwX6rE=S1r z+T?KT!8nKGu2J^XDR(;|2C5d+P zbKGpwYFXJrn;kcEW)+T@)9`frQrh z(zQPfKC>;Ml~SL$uKh5W$YF<|KQ%llB(#s-x%!>Sw>$~$V(E7W zM?Tz~(Eek|I@c6Duv1EeT~MOzsuHa}^ug)nD@ie-MbCWno8R655oy?eW9y}cgm&^@ zgFA-baV50o{J`5UpKeZQ*)x|9_jNLyq{;L z4%Qt_F%LK>csnXP(afMZ4Q5bz1RsBZW*$roj}HY866FCfI{IakMZIvmsBA{`>&D^J zFcVsT0uP@M&IwK{kv7ts3Mej@KNCcN<7OZ zk9?l~1c1BzMFbplH=j;jSn0g`3EF-Zu_w`-LxW!$%8$_e)Ck}oN1NzH#?77b{~W3zI%cNEr{b`(V-r(T)BEIfDlg{?y8N|_yp+@C^?`u_IhM{W=_$y; z@!q05A`cF1W5Huj?|9Z(UtDkHj5Fb%p}C0WIW$I?D`+mUza5*VDjQC1-*pteg|h_zJk-23*veOnl_xhJ{j zo%5aV{M@(q=tX?=7dU(7W2fz{rmogO6#YqtMPN-7pUM6Jqp$;o4D3zq) zx}oFssS#+1-}V1T#C7k8+^hav53$@ce%;tJ-UiD6>v_~OPEZf{ZS=U=30MRoZ$tmg zEcqq2`@Rf2g`Xz+^vX`?#sd~2EC{#A{5552sq*_(w-xEwo?13Pgh&cYe6FTgpt%#ef&aT4s3K%2(@=7MDs zc5`h8c-X)$3D?t2t1seOn%+``&(nsMK3qe;-BMl2%Aii40j0B27}ykKhGo`Tzl=tV zd|Y%kCYrD&YoR&L+Qbjq=dI1$x^qok#KI1Fz{3060WGoefsjyu|D%pS8zqDSHZ&}= zDfHX!XJg_v_NWbSB6sVzMW6NC(Wns%26mODJ4(~cIvu6?8qH}PjKJjiO+1i=^*_)){sSzv2Zf?a)URBiLn|#D5>vEesD8D?^cO1g&b4B>w_BG%BZhxuk3r0 zHT+szA$HKaZN;>*J>0YcW?`a%jg#cSDcFKbpqH===`aPkm`kY`dRv4&*ovJ}I-ia- zzOv{)+dsqKqK{iLsi`Bea3=#ZF)++Vg1`4MEDJ0z8|8f_I@X&n!)#7Tbf6;_dIoKR zUv^rI&)GY?46Z;x@@Ks1#7TxiU3smZpKrQB69E zNPcq^oxyR>3_V z3mS>lWT6&7*1?(MG>i1D5p)-8Q3bOS%}iI1B^thH4LC-k0UR+^v_xWRO4X^+HGZiU zPuQer(5X5bbDXA3Ll)u7K@+jZb+l6ieS!O- zd7V$~T2xK=jmftQM8HVDxxQ$glJNC6F5}^w&C2To|8AjI*Af237~prRE9>V+X1_X6 z^|jL_L~-7E?vIyuuOv$1Yjb}pf1!-17cVrAD3b%98t0BD5v6sm?&I%2yPPP;syhF> z)0IJ#$LCHR-1?D+C?_jU?rZEY5#_+x^dH_kMu=iB{nu=DQ8Q6)%)a|{$FIypahNI# zcJ>w!rR~K2iDf^kBuaMR$c;CDe+%4RnY_B8>4Swtc{d^dx4*eoL6lS55{nmgd5Lo8 zF8f(Rlxw^EJDx2l7R=yohy_J;pGTBGAJ}v1?Qwv9?~~{EoIhwKO7dvwrJo&6rt3D$ zPr6-IYWYTXIZ-xeOh0G+$s!uqFh4@Bzgo5S_zI%b{rddz(QOd%)7I(NH=ax-%I>!h zPhIQ>kjGvaJYno>fm(PIuDp43Bh;(WerxIZ1ftA+$@R|9XKRV#zM13wFtL#+p`Tv6 zdSNw0Y1?uA;k{kUh_Y$Z%(!kN%}Mo38J4&)darH0&0R z;0k2LcTw!~=uD*ZBLjYlKH3$=FVeqvt;C0DN%v;ciwx>CJw-&!Vlk)IiG5#_A z&*mQ#@rSI8z7^bpiBS>L!!G;2v-FKEHTW$3Y)dyi(08Kpv`AOY{;

DMV/CCM – todo-list / progress

Table of Contents

2 DONE outer probabilities

2 P_STOP and P_CHOOSE for IO/EM (reestimation)

2.1 TODO [#A] P_CHOOSE formula:

2.2 DONE P_STOP formulas for various dir and adj:

3 DONE outer probabilities

3 TODO [#B] P_STOP and P_CHOOSE for IO/EM (reestimation)

5.1 TODO Make inner() and outer() also allow left-first attachment

7.1 TOGROK CCM Initialization

7.2 DONE Separate initialization to another file? PRETTIER

7.3 DONE DMV Initialization probabilities

7.4 DONE DMV Initialization frequencies

7.4.1 P_STOP

7.4.2 P_CHOOSE

8.1 TODO when reestimating P_STOP etc, remove rules with p < epsilon OPTIMIZE

8.2 TODO inner_dmv, short ranges and impossible attachment OPTIMIZE

8.3 TODO clean up the module files PRETTIER

8.4 TOGROK Some (tagged) sentences are bound to come twice OPTIMIZE

8.5 TOGROK tags as numbers or tags as strings? OPTIMIZE

9.1 Possible alternate type of adjacency