DMV/CCM – todo-list / progress

4 TOGROK Find Most Probable Parse of given test sentence

We could probably do it pretty easily from the chart:

@@ -155,25 +283,25 @@ for rewrites, for loc_dep select the one that has the highest p

4 TOGROK Combine CCM with DMV

5 TOGROK Combine CCM with DMV

5 TODO Get a dependency parsed version of WSJ to test with

6 TODO Get a dependency parsed version of WSJ to test with

6 Initialization

7 Initialization

dmv-inits

@@ -181,20 +309,20 @@ for rewrites, for loc_dep select the one that has the highest p We do have to go through the corpus, since the probabilities are based on how far away in the sentence arguments are from their heads.

TOGROK CCM Initialization
+
TOGROK CCM Initialization
P_SPLIT used here… how, again?
DONE Separate initialization to another file? PRETTIER
+
DONE Separate initialization to another file? PRETTIER
CLOSED: 2008-06-08 Sun 12:51
harmonic.py
DONE DMV Initialization probabilities
+
DONE DMV Initialization probabilities
(from initialization frequency)
DONE DMV Initialization frequencies
+
DONE DMV Initialization frequencies
CLOSED: 2008-05-27 Tue 20:04
- P_STOP
  +
- P_STOP
  P_STOP is not well defined by K&M. One possible interpretation given the sentence [det nn vb nn] is
```
@@ -211,7 +339,7 @@ the sentence [det nn vb nn] is
  f_{STOP}(-STOP|nn, L, non_adj) +0
 
```
  - TODO tweak
    +
  - TODO tweak
```
             f[head,  'STOP', 'LN'] += (i_h <= 1)     # first two words
             f[head, '-STOP', 'LN'] += (not i_h <= 1)     
@@ -259,7 +387,7 @@ for all heads:
 
```
- P_CHOOSE
  +
- P_CHOOSE
  Go through the corpus, counting distances between heads and arguments. In [det nn vb nn], we give

7 [#C] Deferred

8 [#C] Deferred

http://wiki.python.org/moin/PythonSpeed/PerformanceTips Eg., use map/reduce/filter/[i for i in [i's]]/(i for i in [i's]) instead of @@ -302,12 +430,9 @@ for-loops; use local variables for globals (global variables or or functions), etc.

TODO if loc_h == t, no need to try right-attachment rules OPTIMIZE
-** TODO if loc_h == s, no need to try left-attachment rules :OPTIMIZE: +
TODO when reestimating P_STOP etc, remove rules with p < epsilon OPTIMIZE
TODO when reestimating P_STOP etc, remove rules with p < epsilon OPTIMIZE
-
TODO inner_dmv, short ranges and impossible attachment 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. @@ -319,7 +444,7 @@ 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
+
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 @@ -330,7 +455,7 @@ containing constants and classes could be imported by all others:
TOGROK Some (tagged) sentences are bound to come twice OPTIMIZE
+
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'], @@ -345,7 +470,7 @@ frequency correctly. Is there much to gain here?
TOGROK tags as numbers or tags as strings? OPTIMIZE
+
TOGROK tags as numbers or tags as strings? OPTIMIZE
Need to clean up the representation.
@@ -353,7 +478,14 @@ Stick with tag-strings in initialization then switch to numbers for IO-algorithm perhaps? Can probably afford more string-matching in initialization..
DONE io.debug parameters should not call functions OPTIMIZE
+
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:
```
@@ -364,7 +496,7 @@ if 'level' in io.DEBUG:
 
 and got an almost threefold speed increase on inner().
 
```
DONE inner_dmv() should disregard rules with heads not in sent OPTIMIZE
+
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 @@ -391,9 +523,9 @@ be a lot of trouble for little potential gain).

8 Adjacency and combining it with inner()

9 Adjacency and combining it with inner()

Each DMV_Rule now has both a probN and a probA, for adjacencies. inner() needs the correct one in each case. @@ -419,7 +551,7 @@ need probN or probA. In each inner() call, loc_h is the location of the root of this dependency structure.

Possible alternate type of adjacency
+
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 @@ -433,9 +565,9 @@ P_STOP reestimation.

9 Expectation Maximation in IO/DMV-terms

10 Expectation Maximation in IO/DMV-terms

inner(s,t,LHS) calculates the expected number of trees headed by LHS from s to t (sentence positions). This uses the P_STOP and P_CHOOSE @@ -464,9 +596,9 @@ Since "adjacency" is not captured in regular CNF rules, we need two probabilites for each rule, and inner() has to know when to use which.

TODO Corpus access
+
TODO Corpus access
TOGROK sentences or rules as the "outer loop"? OPTIMIZE
+
TOGROK sentences or rules as the "outer loop"? OPTIMIZE
In regard to the E/M-step, finding P_STOP, P_CHOOSE. @@ -476,9 +608,9 @@ In regard to the E/M-step, finding P_STOP, P_CHOOSE.

10 Python-stuff

11 Python-stuff

Make those debug statements steal a bit less attention in emacs:

@@ -512,9 +644,9 @@ In regard to the E/M-step, finding P_STOP, P_CHOOSE.

11 Git

12 Git

Repository web page: http://repo.or.cz/w/dmvccm.git

@@ -582,6 +714,6 @@ Good tutorial:

Author: Kevin Brubeck Unhammer <K.BrubeckUnhammer at student uva nl >

Date: 2008/06/10 12:33:43

Date: 2008/06/11 16:40:21

Skrive vha. emacs + org-mode

diff --git a/DMVCCM.org b/DMVCCM.org index 3345b0b..f6b196b 100755 --- a/DMVCCM.org +++ b/DMVCCM.org @@ -17,7 +17,67 @@ - [[file:src/harmonic.py::harmonic%20py%20initialization%20for%20dmv][harmonic.py]] (But absolute, extended, really-quite-dead-now deadline: August 31...) -* TODO [#A] P_STOP and P_CHOOSE for IO/EM (reestimation) +* TODO [#A] outer probabilities +# <> +There are 6 different configurations here, based on what the above +(mother) node is, and what the Node for which we're computing is. +Here *r* is not between *s* and *t* as in inner(), but an /outer/ index. *loc_N* +is the location of the Node head in the sentence, *loc_m* for the head +of the mother rule. + ++ mother is a RIGHT-stop: + - outer(*s, t*, mom.LHS, *loc_N*), no inner-call + - adjacent iff *t* == *loc_m* ++ mother is a LEFT-stop: + - outer(*s, t*, mom.LHS, *loc_N*), no inner-call + - adjacent iff *s* == *loc_m* + ++ Node is on the LEFT branch (mom.L == Node) + * and mother is a LEFT attachment: + - *loc_N* will be in the LEFT branch, can be anything here. + - In the RIGHT, attached, branch we find inner(*t+1, r*, mom.R, *loc_m*) for + all possible *loc_m* in the right part of the sentence. + - outer(*s, r*, mom.LHS, *loc_m*). + - adjacent iff *t+1* == *loc_m* + * and mother is a RIGHT attachment: + - *loc_m* = *loc_N*. + - In the RIGHT, attached, branch we find inner(*t+1, r*, mom.R, *loc_R*) for + all possible *loc_R* in the right part of the sentence. + - outer(*s, r*, mom.LHS, *loc_N*). + - adjacent iff *t* == *loc_m* + ++ Node is on the RIGHT branch (mom.R == Node) + * and mother is a LEFT attachment: + - *loc_m* = *loc_N*. + - In the LEFT, attached, branch we find inner(*r, s-1*, mom.L, *loc_L*) for + all possible *loc_L* in the left part of the sentence. + - outer(*r, t*, mom.LHS, *loc_m*). + - adjacent iff *s* == *loc_m* + * and mother is a RIGHT attachment: + - *loc_N* will be in the RIGHT branch, can be anything here. + - In the RIGHT, attached, branch we find inner(*r, s-1*, mom.L, *loc_m*) for + all possible *loc_m* in the right part of the sentence. + - outer(*r, t*, mom.LHS, *loc_N*). + - adjacent iff *s-1* == *loc_m* + +[[file:outer_attachments.jpg]] + +** COMMENT qtrees + +\Tree [.{$h\urcorner$} [.{$_s \ulcorner a\urcorner _t$\\ + Node} ] {$_{t+1} h\urcorner _r$\\ + R} ] +\Tree [.{$h$} {$_{s} h _{t}$\\ + Node} [.{$_{t+1} \ulcorner a\urcorner _r$\\ + R} ] ] +\Tree [.{$h\urcorner$} [.{$_r \ulcorner a\urcorner _{s-1}$\\ + L} ] {$_{s} h\urcorner _t$\\ + Node} ] +\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 thesis) diff --git a/src/dmv.py b/src/dmv.py index 58c888f..45e0caa 100755 --- a/src/dmv.py +++ b/src/dmv.py @@ -260,7 +260,7 @@ def inner(s, t, LHS, loc_h, g, sent, ichart): ''' A rewrite of io.inner(), to take adjacency into accord. The ichart is now of this form: - ichart[(s,t,LHS, loc_h)] + ichart[s,t,LHS, loc_h] loc_h gives adjacency (along with r and location of other child for attachment rules), and is needed in P_STOP reestimation. @@ -282,9 +282,9 @@ def inner(s, t, LHS, loc_h, g, sent, ichart): if (s, t, LHS, loc_h) in ichart: if 'INNER' in io.DEBUG: - print "%s*= %.4f in ichart: s:%d t:%d LHS:%s loc:%d" % (tab(),ichart[(s, t, LHS, loc_h)], s, t, + print "%s*= %.4f in ichart: s:%d t:%d LHS:%s loc:%d" % (tab(),ichart[s, t, LHS, loc_h], s, t, DMV_Rule.bar_str(LHS), loc_h) - return ichart[(s, t, LHS, loc_h)] + return ichart[s, t, LHS, loc_h] else: if s == t: if not loc_h == s: @@ -331,8 +331,9 @@ def inner(s, t, LHS, loc_h, g, sent, ichart): print "%sp= %.4f (STOP)" % (tab(), p) else: # not a STOP, an attachment rewrite: + rp_ATTACH = rule.p_ATTACH # todo: profile/speedtest for r in xrange(s, t): - p_h = rule.p_ATTACH(r, loc_h, s=s) + p_h = rp_ATTACH(r, loc_h, s=s) if rule.LHS() == L: locs_L = [loc_h] locs_R = locs(head(R), sent_nums, r+1, t, loc_h) @@ -350,14 +351,15 @@ def inner(s, t, LHS, loc_h, g, sent, ichart): p += pL * p_h * pR if 'INNER' in io.DEBUG: print "%sp= %.4f (ATTACH)" % (tab(), p) - ichart[(s, t, LHS, loc_h)] = p + ichart[s, t, LHS, loc_h] = p return p # end of e-function - + inner_prob = e(s,t,LHS,loc_h, 0) + ichart['tree'] = tree if 'INNER' in io.DEBUG: print debug_ichart(g,sent,ichart) - return (inner_prob,tree) + return inner_prob # end of dmv.inner(s, t, LHS, loc_h, g, sent, ichart) @@ -371,12 +373,82 @@ def debug_ichart(g,sent,ichart): def inner_sent(loc_h, g, sent, ichart): - return inner(0, len(sent)-1, ROOT, loc_h, g, sent, ichart)[0] + return inner(0, len(sent)-1, ROOT, loc_h, g, sent, ichart) + +def c(s,t,LHS,loc_h): + return inner() * outer() # divided by sentence probability? todo + +################################### +# dmv-specific version of outer() # +################################### +def outer(s,t,Node,loc_N, g, sent, ochart, ichart): + ''' http://www.student.uib.no/~kun041/dmvccm/DMVCCM.html#outer + ''' + def e(s,t,LHS,loc_h): + # or we could just look it up in ichart, assuming ichart to be done + return inner(s, t, LHS, loc_h, g, sent, ichart) + + T = len(sent)-1 + sent_nums = [i for i,w in enumerate(sent)] + + def f(s,t,Node,loc_N): + if (s,t,Node) in ochart: + return ochart[(s, t, Node,loc_N)] + if s == 0 and t == T: + if Node == ROOT: # that simple, even w/loc_N? todo grok + return 1.0 + else: + return 0.0 + p = 0.0 + + for mom in g.mothersL(Node, sent_nums): # mom.L() == Node + R = mom.R() + mLHS = mom.LHS() + if R == STOP: + p += f(s,t,mLHS,loc_N) * mom.p_STOP(s,t,loc_N) # == loc_m + else: + if bars(mLHS) == RBAR: # left attachment, head(mLHS) == head(L) + for r in xrange(t+1,T+1): # t+1 to lasT + for loc_m in locs(head(mLHS),sent_nums,t+1,r): + p_m = mom.p(t+1 == loc_m) + p += f(s,r,mLHS,loc_m) * p_m * e(t+1,r,R,loc_m) + else: # right attachment, head(mLHS) == head(Node) + loc_m = loc_N + p_m = mom.p( t == loc_m) + for r in xrange(t+1,T+1): # t+1 to lasT + for loc_R in locs(head(mLHS),sent_nums,t+1,r): + p += f(s,r,mLHS,loc_m) * p_m * e(t+1,r,R,loc_R) + + for mom in g.mothersR(Node, sent_nums): + L = mom.L() + mLHS = mom.LHS() + if L == STOP: + p += f(s,t,mLHS,loc_N) * mom.p_STOP(s,t,loc_N) # == loc_m + else: + if bars(mLHS) == RBAR: # left attachment, head(mLHS) == head(Node) + loc_m = loc_N + p_m = mom.p( s == loc_m) + for r in xrange(0,s): # first to s-1 + for loc_L in locs(head(L),sent_nums,r,s-1): + p += e(r,s-1,L, loc_L) * p_m * f(r,t,mLHS,loc_m) + else: # right attachment, head(mLHS) == head(R) + for r in xrange(0,s): # first to s-1 + for loc_m in locs(head(mLHS),sent_nums,r,s-1): + p_m = mom.p(s-1 == loc_m) + p += e(r,s-1,L, loc_m) * p_m * f(r,t,mLHS,loc_m) + ochart[s,t,Node,loc_N] = p + return p + + + return f(s,t,Node,loc_N) +# end outer(s,t,Node,loc_N, g,sent, ochart,ichart) + + ############################## # reestimation, todo: # @@ -394,36 +466,30 @@ def reestimate(g, corpus): P_STOP(-STOP|...) = 1 - P_STOP(STOP|...) ''' f = reestimate_zeros(g.head_nums) for sent in corpus: - #print sent sent_nums = [g.tagnum(w) for i,w in enumerate(sent)] ichart = {} for loc_h,h in zip(xrange(len(sent)), sent_nums): - #print loc_h inner_sent(loc_h, g, sent, ichart) - if 'reest_ichart' in io.DEBUG: - print ("before:",len(ichart)) - #print debug_ichart(g,sent,ichart) - #print debug_ichart(g,sent,ichart) for loc_h,h in zip(xrange(len(sent)), sent_nums): for s in xrange(loc_h): # sA~h96>D|&TY?tlcwu^45 zvB)-JFfs=9hcVGa@hx6|s8R8s8c9&&5B;g}f&S3ML=#PX%-pt1TOY)3&)jqF%$fPl z%y(w@(n);qB)Y7h`~` zz(6=u3w^Z^tA%(S82qvprWC|$!O&m|VS7)k8m0hn7y+&O(2ICIJ*4*Hjr0S{o2?z% zYZ@Lr?S35-^oIL99-*V2S20Zi{RJGeKG$DFJW4t51-zGb``*J7R*nBw#QSNq@Fd=1 z;gUZ!eAdE}ZxLU%zAOD2@h!SoHjW>#`x^SStbwM=SK|fiTzM4nA~`GL__>v=+=ciV zov%88-_VNcuUNWkPT*Dt0b z^@j`70W)wzPc+bQIN85{(AwE>2V#-+(sFcRx%J9bVTEP%^Qtp=C*@jRDbtWQF6G_e zU!t|3OV#bFzyfQ>)q9bTem2mIE9v7vGyNVo;2jfNCALUsJ4fn{U0(NlSbBNrJTw6_ zMb~!iDRDwhgPa?3067IY2MoCAnXbn0W;SUUG|eOJq0spFcra~_8nIzBI2u0?98QLg z9U2{OUB4z|B*yyt6QS_VJ>A_qgM((`aAR`RjExjD@E>_M9alM|hc=Zj_p!ec3Hu`l z&+1%#3Sr0v$qKq|MfojU?5xcWp-l@f5T=#AsO5zM6YPbD38f&Kit$r}sBnaz z6As9{iPH{<+rGI1%&73br)lkVD<@ldzXPV7bFtl!WuiGC>x6jzCBM<2bOSp|9RoC7 zV#Z`N-FDQ+0W;U2=@C<|Z8;;8haF@BCOnWa!PLPlnB6uFbCy}pq{IsEi^7C%hxF!E zy7*@63Eq|m=&=FnHoyWXWj^ISLDn^^nE~2@y(tF|2F&>9yPxlRGBW}HjNGu1-}bM_ zXMnfEg!g~o^IpdHC1ZOF8wFr*<~h4OzWL=jgA-00v!DE1YX5hgI@I6l^vI%2z=BL< z3Z#TgvFt2>1qqmhtZyy@9x>rVRm^3;Z)ZT8r(xr)Kc5Ast-;H=nSuD5>P>yhgP~?l z!NTB+d9(4KgGUz}$Bw*+HyZ8OTG{q52*$MD)J>Wo=oMSMd;vL80}gt4>nbdyceVyf zqI^XoH;9n75n0263cH6~(!L_aG~Hb{X>wD6foAC{X?e{pAb8|xB*oKH(r*sf{iX~n zunPU?Q6BDDCE!9IfBe|0O0a@g4LmAwvvT3G{Ce{uJJA*8b+a>j8+XWHxT$DJP~9P- zM?{kP!)rQ{GELcd^O_@zzz*{CxPUDXu-Y<55w2EsYiMZo8TZUyAGP`_X?d^|-=ntR z%9`i7ZJBoG;_f18SCC04PGWdpj55J3suQR_R8>6J+zqx(V|92ysu-VHS`ov&_WwG-&WP^GhMdr#^ys%Tw>8oeE=puW};MEWjN z&9fx~qODW*ccn4k!D?Q6q|Ao+7m{+rt(;xE=GFrW#K9#%9=)jxd{2u7`9V3HOD=vY z!SuE0kJiq~`5O(6;(+9%c5D965X<@R`^;Px@N0x^)B7RzJ`uZVT>N(RdYoc3v+ z&@lCswlEz5j_AEoL>{uA_og0DGI|XkM4SD>pbnsG*KXol1~3wfrOkAaylrnvH<%*$ z`@Fr$h>Qq-(xP#*7#>Yr-PM$inDoKgG>%c%x)i49<#o4LUlan~XcKS=x|!W=%=jAc zVL4iX_4li)yI5uaaEM6s$a)b+MP%utwhrY~mVd(zrOFlcZ9KSYTp|jz!3O>`%PdkW zVx5Q+BE(_jZu)-XM%ARKsl6V*rfu!(DBIpc@AD|__@u}-G(>EkvHqo_FWAD}AYCd@ zQCBTkjQ)Aj^v&gCf4qP2&JmMFI@{=CxC-x~@58&c#Kn)?xX4%@#AF^*PQ(LqI88aO z8BfIGrYR@b&C?P3qOhtkEk9s76G>zAaBNctJ-O|w`XOD{J-SQpX4$4M)eCi}UgVbs JqUl(y{sJ~>AkP2* delta 2799 zcwUWGZERa-6+Y*^*Vn$Woj7xn#`$R6c5B_v$q4D}kSyKOWLx&7PENHt$p9#6W#GGIL{B-2u)(KXpqwIw81@t10 z(G_(ZAEUpre7yXK_I(X!*W9n;JpI6Z4bybi^BQI;YQBt1<=>dEAm*v${V6_6M}0rR z3*`>~lZcmSseToYma*Yu4PPo_@K1=ZmjB#z1Mv;I-f{-t;_w}Gvn5RDc68(0<@Fuo zi0_aql*0GQ>Ch3xU(>a=X}m$Z+yBVY-Ek4GlrMK=6#jj!Yd3zI_H^ZyrPFu1_SUax zFsooZ;sSu&MS8buJ`l-8?dYRpvp0><#_~?Eo5T=aJU((L0YLK27V<2p*u{Mk6|3Z-`X)wAU7MCFV%QyRUj= z53>m$ea07}e~%b67^}x3JsjJMKc`GA=vh+*gwe_8==s<%PSHEDb{wS-Vx3VAX?q}L z!khu=W_}X|wgCl?JQkPq;8?~6Oc@h6nT6!Kb=P(v%5lO05CiV5k^(dI$Ja5Ca&} z%KsXCPPJwEIATadzleh(G9qmH=Al9LV=Vvf&?8E{ixe3?#k2n6aHsbfITy!7j$R-B z-0nX}BE#u^ADTELn$F9^YeaB8`JW@;js!th?a=^Dq%;C?S5av zHaTHU)q{=buaSvG{!aIe#wgvL-Kne1`J0if-pbM>`z89g`-u=j$ps|?N*a{hPy#3^ zDCsckq0>EkhKJa2ESXJ)v*A=OyqLDb(@FbGGPxMeg{Ky+u+8!;GsohoWHuU}UXpz{ zy<{iZe$h(id+2)4`G?I-7%C+UFeA56U%?U-EH@Yt_ea6$3~mM{s>-0VR&zk#x~p|q zcUZmC82}rcjmKex@yxU{i{q7xlQ!A(ANJ~MuAp)z1<&i0YBq)6{U!Y{1xZ1{I!p@ zjLR+uaXnq@?fmptdrW=e)xKQ4n#!vHY^hgAu9wG+zu&4(pHruDN&!J1Xss6NcM5gU zGoK9=-HriP%H4RIn@rxnLaij;8zeV*@?k7rp&ap&FUiL@x_l{wrjsc))F;Rr!;!kY1p- z`{n||D2b;;G>RCb!Gk+hVxD%zg2lu!IbFZeJ8VS zn0Fy;WjUmbnw@CF|6^-#oIvGlNNw24eh7mYaX>#Hf<8DH3S1KHqytUFWeVQi`^05Y z=l=^@#0yX%YHQ&OJ)b|DxWKAgu-6H8)vO1wTixCp=@R2k5&a_Wg(@-U>B{Jl;RUGj z{}~Yuc^5^T7tzPUmLzs+A(^tBdp*i(HgQpoB`58=e;*FeL-+6NN|~nVH9h7%=51!Z R=`sU;xdhF`M&;E_?LW;?FCG8@ -- 2.11.4.GIT

2 TODO [#A] P_STOP and P_CHOOSE for IO/EM

2 TODO [#A] outer probabilities

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

3 TOGROK Find Most Probable Parse of given test sentence