?  search:
summary | log | graphiclog1 | graphiclog2 | refs | edit | fork

6c5149bc30e5f13f3a313b92e3e2b39596504c96
[dmvccm.git] / src / loc_h_dmv.py
blob6c5149bc30e5f13f3a313b92e3e2b39596504c96
1 # loc_h_dmv.py
2 #
3 # dmv reestimation and inside-outside probabilities using loc_h, and
4 # no CNF-style rules
5
6 #import numpy # numpy provides Fast Arrays, for future optimization
7 import io
8 from common_dmv import *
9
10 ### todo: debug with @accepts once in a while, but it's SLOW
11 # from typecheck import accepts, Any
12
13 if __name__ == "__main__":
14 print "loc_h_dmv module tests:"
15
16 def adj(middle, loc_h):
17 "middle is eg. k when rewriting for i<k<j (inside probabilities)."
18 return middle == loc_h or middle == loc_h+1 # ADJ == True
19
20 def make_GO_AT(p_STOP,p_ATTACH):
21 p_GO_AT = {}
22 for (a,h,dir), p_ah in p_ATTACH.iteritems():
23 p_GO_AT[a,h,dir, NON] = p_ah * (1-p_STOP[h, dir, NON])
24 p_GO_AT[a,h,dir, ADJ] = p_ah * (1-p_STOP[h, dir, ADJ])
25 return p_GO_AT
26
27 class DMV_Grammar(io.Grammar):
28 def __str__(self):
29 def t(n):
30 return "%d=%s" % (n, self.numtag(n))
31 def p(dict,key):
32 if key in dict:
33 return dict[key]
34 else:
35 return 0.0
36 def p_a(a,h):
37 p_L = p(self.p_ATTACH,(a,h,LEFT))
38 p_R = p(self.p_ATTACH,(a,h,RIGHT))
39 if p_L == 0.0 and p_R == 0.0:
40 return ''
41 else:
42 if p_L > 0.0:
43 str = "p_ATTACH[ %s|%s,L] = %.4f" % (t(a), t(h), p_L)
44 else:
45 str = ''
46 if p_R > 0.0:
47 str = str.ljust(40)
48 str += "p_ATTACH[ %s|%s,R] = %.4f" % (t(a), t(h), p_R)
49 return str+'\n'
50
51 root, stop, att, ord = "","","",""
52 for h in self.headnums():
53 root += "p_ROOT[%s] = %.4f\n" % (t(h), p(self.p_ROOT, (h)))
54 stop += "p_STOP[stop|%s,L,adj] = %.4f\t" % (t(h), p(self.p_STOP, (h,LEFT,ADJ)))
55 stop += "p_STOP[stop|%s,R,adj] = %.4f\n" % (t(h), p(self.p_STOP, (h,RIGHT,ADJ)))
56 stop += "p_STOP[stop|%s,L,non] = %.4f\t" % (t(h), p(self.p_STOP, (h,LEFT,NON)))
57 stop += "p_STOP[stop|%s,R,non] = %.4f\n" % (t(h), p(self.p_STOP, (h,RIGHT,NON)))
58 att += ''.join([p_a(a,h) for a in self.headnums()])
59 ord += "p_ORDER[ left-first|%s ] = %.4f\t" % (t(h), p(self.p_ORDER, (GOL,h)))
60 ord += "p_ORDER[right-first|%s ] = %.4f\n" % (t(h), p(self.p_ORDER, (GOR,h)))
61 return root + stop + att + ord
62
63 def __init__(self, numtag, tagnum, p_ROOT, p_STOP, p_ATTACH, p_ORDER):
64 io.Grammar.__init__(self, numtag, tagnum)
65 self.p_ROOT = p_ROOT # p_ROOT[w] = p
66 self.p_ORDER = p_ORDER # p_ORDER[seals, w] = p
67 self.p_STOP = p_STOP # p_STOP[w, LEFT, NON] = p (etc. for LA,RN,RA)
68 self.p_ATTACH = p_ATTACH # p_ATTACH[a, h, LEFT] = p (etc. for R)
69 # p_GO_AT[a, h, LEFT, NON] = p (etc. for LA,RN,RA)
70 self.p_GO_AT = make_GO_AT(self.p_STOP, self.p_ATTACH)
71
72 def p_GO_AT_or0(self, a, h, dir, adj):
73 try:
74 return self.p_GO_AT[a, h, dir, adj]
75 except:
76 return 0.0
77
78
79 def locs(sent_nums, start, stop):
80 '''Return the between-word locations of all words in some fragment of
81 sent. We make sure to offset the locations correctly so that for
82 any w in the returned list, sent[w]==loc_w.
83
84 start is inclusive, stop is exclusive, as in klein-thesis and
85 Python's list-slicing.'''
86 for i0,w in enumerate(sent_nums[start:stop]):
87 loc_w = i0+start
88 yield (loc_w, w)
89
90 ###################################################
91 # P_INSIDE (dmv-specific) #
92 ###################################################
93
94 #@accepts(int, int, (int, int), int, Any(), [str], {tuple:float}, IsOneOf(None,{}))
95 def inner(i, j, node, loc_h, g, sent, ichart={}, mpptree=None):
96 ''' The ichart is of this form:
97 ichart[i,j,LHS, loc_h]
98 where i and j are between-word positions.
99
100 loc_h gives adjacency (along with k for attachment rules), and is
101 needed in P_STOP reestimation.
102 '''
103 sent_nums = g.sent_nums(sent)
104
105 def terminal(i,j,node, loc_h, tabs):
106 if not i <= loc_h < j:
107 if 'INNER' in DEBUG:
108 print "%s*= 0.0 (wrong loc_h)" % tabs
109 return 0.0
110 elif POS(node) == sent_nums[i] and node in g.p_ORDER:
111 # todo: add to ichart perhaps? Although, it _is_ simple lookup..
112 prob = g.p_ORDER[node]
113 else:
114 if 'INNER' in DEBUG:
115 print "%sLACKING TERMINAL:" % tabs
116 prob = 0.0
117 if 'INNER' in DEBUG:
118 print "%s*= %.4f (terminal: %s -> %s_%d)" % (tabs,prob, node_str(node), sent[i], loc_h)
119 return prob
120
121 def e(i,j, (s_h,h), loc_h, n_t):
122 def to_mpp(p, L, R):
123 if mpptree:
124 key = (i,j, (s_h,h), loc_h)
125 if key not in mpptree:
126 mpptree[key] = (p, L, R)
127 elif mpptree[key][0] < p:
128 mpptree[key] = (p, L, R)
129
130 def tab():
131 "Tabs for debug output"
132 return "\t"*n_t
133
134 if (i, j, (s_h,h), loc_h) in ichart:
135 if 'INNER' in DEBUG:
136 print "%s*= %.4f in ichart: i:%d j:%d node:%s loc:%s" % (tab(),ichart[i, j, (s_h,h), loc_h], i, j,
137 node_str((s_h,h)), loc_h)
138 return ichart[i, j, (s_h,h), loc_h]
139 else:
140 # Either terminal rewrites, using p_ORDER:
141 if i+1 == j and (s_h == GOR or s_h == GOL):
142 return terminal(i, j, (s_h,h), loc_h, tab())
143 else: # Or not at terminal level yet:
144 if 'INNER' in DEBUG:
145 print "%s%s (%.1f) from %d to %d" % (tab(),node_str((s_h,h)),loc_h,i,j)
146 if s_h == SEAL:
147 p_RGOL = g.p_STOP[h, LEFT, adj(i,loc_h)] * e(i,j,(RGOL,h),loc_h,n_t+1)
148 p_LGOR = g.p_STOP[h, RIGHT, adj(j,loc_h)] * e(i,j,(LGOR,h),loc_h,n_t+1)
149 p = p_RGOL + p_LGOR
150 to_mpp(p_RGOL, STOPKEY, (i,j, (RGOL,h),loc_h))
151 to_mpp(p_LGOR, (i,j, (RGOL,h),loc_h), STOPKEY )
152 if 'INNER' in DEBUG:
153 print "%sp= %.4f (STOP)" % (tab(), p)
154 elif s_h == RGOL or s_h == GOL:
155 p = 0.0
156 if s_h == RGOL:
157 p = g.p_STOP[h, RIGHT, adj(j,loc_h)] * e(i,j, (GOR,h),loc_h,n_t+1)
158 to_mpp(p, (i,j, (GOR,h),loc_h), STOPKEY)
159 for k in xgo_left(i, loc_h): # i < k <= loc_l(h)
160 p_R = e(k, j, ( s_h,h), loc_h, n_t+1)
161 if p_R > 0.0:
162 for loc_a,a in locs(sent_nums, i, k):
163 p_ah = g.p_GO_AT_or0(a, h, LEFT, adj(k,loc_h))
164 if p_ah > 0.0:
165 p_L = e(i, k, (SEAL,a), loc_a, n_t+1)
166 p_add = p_L * p_ah * p_R
167 p += p_add
168 to_mpp(p_add,
169 (i, k, (SEAL,a), loc_a),
170 (k, j, ( s_h,h), loc_h))
171 if 'INNER' in DEBUG:
172 print "%sp= %.4f (ATTACH)" % (tab(), p)
173 elif s_h == GOR or s_h == LGOR:
174 p = 0.0
175 if s_h == LGOR:
176 p = g.p_STOP[h, LEFT, adj(i,loc_h)] * e(i,j, (GOL,h),loc_h,n_t+1)
177 to_mpp(p, (i,j, (GOL,h),loc_h), STOPKEY)
178 for k in xgo_right(loc_h, j): # loc_l(h) < k < j
179 p_L = e(i, k, ( s_h,h), loc_h, n_t+1)
180 if p_L > 0.0:
181 for loc_a,a in locs(sent_nums,k,j):
182 p_ah = g.p_GO_AT_or0(a, h, RIGHT, adj(k,loc_h))
183 p_R = e(k, j, (SEAL,a), loc_a, n_t+1)
184 p_add = p_L * p_ah * p_R
185 p += p_add
186 to_mpp(p_add,
187 (i, k, ( s_h,h), loc_h),
188 (k, j, (SEAL,a), loc_a))
189
190 if 'INNER' in DEBUG:
191 print "%sp= %.4f (ATTACH)" % (tab(), p)
192 # elif s_h == GOL: # todo
193
194 ichart[i, j, (s_h,h), loc_h] = p
195 return p
196 # end of e-function
197
198 inner_prob = e(i,j,node,loc_h, 0)
199 if 'INNER' in DEBUG:
200 print debug_ichart(g,sent,ichart)
201 return inner_prob
202 # end of dmv.inner(i, j, node, loc_h, g, sent, ichart={})
203
204
205 def debug_ichart(g,sent,ichart):
206 str = "---ICHART:---\n"
207 for (s,t,LHS,loc_h),v in ichart.iteritems():
208 str += "%s -> %s_%d ... %s_%d (loc_h:%s):\t%.4f\n" % (node_str(LHS,g.numtag),
209 sent[s], s, sent[s], t, loc_h, v)
210 str += "---ICHART:end---\n"
211 return str
212
213
214 def inner_sent(g, sent, ichart={}):
215 return sum([g.p_ROOT[w] * inner(0, len(sent), (SEAL,w), loc_w, g, sent, ichart)
216 for loc_w,w in locs(g.sent_nums(sent),0,len(sent))])
217
218
219
220
221
222 ###################################################
223 # P_OUTSIDE (dmv-specific) #
224 ###################################################
225
226 #@accepts(int, int, (int, int), int, Any(), [str], {tuple:float}, {tuple:float})
227 def outer(i,j,w_node,loc_w, g, sent, ichart={}, ochart={}):
228 ''' http://www.student.uib.no/~kun041/dmvccm/DMVCCM.html#outer
229
230 w_node is a pair (seals,POS); the w in klein-thesis is made up of
231 POS(w) and loc_w
232 '''
233 sent_nums = g.sent_nums(sent)
234 if POS(w_node) not in sent_nums[i:j]:
235 # sanity check, w must be able to dominate sent[i:j]
236 return 0.0
237
238 # local functions:
239 def e(i,j,LHS,loc_h): # P_{INSIDE}
240 try:
241 return ichart[i,j,LHS,loc_h]
242 except:
243 return inner(i,j,LHS,loc_h,g,sent,ichart)
244
245 def f(i,j,w_node,loc_w):
246 if not (i <= loc_w < j):
247 return 0.0
248 if (i,j,w_node,loc_w) in ochart:
249 return ochart[i,j, w_node,loc_w]
250 if w_node == ROOT:
251 if i == 0 and j == len(sent):
252 return 1.0
253 else: # ROOT may only be used on full sentence
254 return 0.0
255 # but we may have non-ROOTs (stops) over full sentence too:
256 w = POS(w_node)
257 s_w = seals(w_node)
258
259 # todo: try either if p_M > 0.0: or sum(), and speed-test them
260
261 if s_w == SEAL: # w == a
262 # todo: do the i<sent<j check here to save on calls?
263 p = g.p_ROOT[w] * f(i,j,ROOT,loc_w)
264 # left attach
265 for k in xgt(j, sent): # j<k<len(sent)+1
266 for loc_h,h in locs(sent_nums,j,k):
267 p_wh = g.p_GO_AT_or0(w, h, LEFT, adj(j, loc_h))
268 for s_h in [RGOL, GOL]:
269 p += f(i,k,(s_h,h),loc_h) * p_wh * e(j,k,(s_h,h),loc_h)
270 # right attach
271 for k in xlt(i): # k<i
272 for loc_h,h in locs(sent_nums,k,i):
273 p_wh = g.p_GO_AT_or0(w, h, RIGHT, adj(i, loc_h))
274 for s_h in [LGOR, GOR]:
275 p += e(k,i,(s_h,h), loc_h) * p_wh * f(k,j,(s_h,h), loc_h)
276
277 elif s_w == RGOL or s_w == GOL: # w == h, left stop + left attach
278 if s_w == RGOL:
279 s_h = SEAL
280 else: # s_w == GOL
281 s_h = LGOR
282 p = g.p_STOP[w, LEFT, adj(i,loc_w)] * f(i,j,( s_h,w),loc_w)
283 for k in xlt(i): # k<i
284 for loc_a,a in locs(sent_nums,k,i):
285 p_aw = g.p_GO_AT_or0(a, w, LEFT, adj(i, loc_w))
286 p += e(k,i, (SEAL,a),loc_a) * p_aw * f(k,j,w_node,loc_w)
287
288 elif s_w == GOR or s_w == LGOR: # w == h, right stop + right attach
289 if s_w == GOR:
290 s_h = RGOL
291 else: # s_w == LGOR
292 s_h = SEAL
293 p = g.p_STOP[w, RIGHT, adj(j,loc_w)] * f(i,j,( s_h,w),loc_w)
294 for k in xgt(j, sent): # j<k<len(sent)+1
295 for loc_a,a in locs(sent_nums,j,k):
296 p_ah = g.p_GO_AT_or0(a, w, RIGHT, adj(j, loc_w))
297 p += f(i,k,w_node,loc_w) * p_ah * e(j,k,(SEAL,a),loc_a)
298
299 ochart[i,j,w_node,loc_w] = p
300 return p
301 # end outer.f()
302
303 return f(i,j,w_node,loc_w)
304 # end outer(i,j,w_node,loc_w, g,sent, ichart,ochart)
305
306
307
308
309 ###################################################
310 # Reestimation: #
311 ###################################################
312
313 def reest_zeros(h_nums):
314 '''A dict to hold numerators and denominators for our 6+ reestimation
315 formulas. '''
316 # todo: p_ORDER?
317 fr = { ('ROOT','den'):0.0 } # holds sum over p_sent
318 for h in h_nums:
319 fr['ROOT','num',h] = 0.0
320 for s_h in [GOR,GOL,RGOL,LGOR]:
321 x = (s_h,h)
322 fr['hat_a','den',x] = 0.0 # = c()
323 # not all arguments are attached to, so we just initialize
324 # fr['hat_a','num',a,(s_h,h)] as they show up, in reest_freq
325 for adj in [NON, ADJ]:
326 for nd in ['num','den']:
327 fr['STOP',nd,x,adj] = 0.0
328 return fr
329
330 def reest_freq(g, corpus):
331 fr = reest_zeros(g.headnums())
332 ichart = {}
333 ochart = {}
334 p_sent = None # 50 % speed increase on storing this locally
335
336 # local functions altogether 2x faster than global
337 def c(i,j,LHS,loc_h,sent):
338 if not p_sent > 0.0:
339 return p_sent
340
341 p_in = e(i,j, LHS,loc_h,sent)
342 if not p_in > 0.0:
343 return p_in
344
345 p_out = f(i,j, LHS,loc_h,sent)
346 return p_in * p_out / p_sent
347 # end reest_freq.c()
348
349 def f(i,j,LHS,loc_h,sent): # P_{OUTSIDE}
350 try:
351 return ochart[i,j,LHS,loc_h]
352 except:
353 return outer(i,j,LHS,loc_h,g,sent,ichart,ochart)
354 # end reest_freq.f()
355
356 def e(i,j,LHS,loc_h,sent): # P_{INSIDE}
357 try:
358 return ichart[i,j,LHS,loc_h]
359 except:
360 return inner(i,j,LHS,loc_h,g,sent,ichart)
361 # end reest_freq.e()
362
363 def w_left(i,j, x,loc_h,sent,sent_nums):
364 h = POS(x)
365 if not p_sent > 0.0:
366 return p_sent
367
368 for k in xtween(i, j):
369 p_out = f(i,j, x,loc_h, sent)
370 if not p_out > 0.0:
371 continue
372 p_R = e(k,j, x,loc_h, sent)
373 if not p_R > 0.0:
374 continue
375
376 for loc_a,a in locs(sent_nums, i,k): # i<=loc_l(a)<k
377 p_rule = g.p_GO_AT_or0(a, h, LEFT, adj(k, loc_h))
378 p_L = e(i,k, (SEAL,a), loc_a, sent)
379 p = p_L * p_out * p_R * p_rule / p_sent
380 try:
381 fr['hat_a','num',a,x] += p
382 except:
383 fr['hat_a','num',a,x] = p
384 # end reest_freq.w_left()
385
386 def w_right(i,j, x,loc_h,sent,sent_nums):
387 h = POS(x)
388 if not p_sent > 0.0:
389 return p_sent
390
391 for k in xtween(i, j):
392 p_out = f(i,j, x,loc_h, sent)
393 if not p_out > 0.0:
394 continue
395 p_L = e(i,k, x,loc_h, sent)
396 if not p_L > 0.0:
397 continue
398
399 for loc_a,a in locs(sent_nums, k,j): # k<=loc_l(a)<j
400 p_rule = g.p_GO_AT_or0(a, h, RIGHT, adj(k, loc_h))
401 p_R = e(k,j, (SEAL,a),loc_a, sent)
402 p = p_L * p_out * p_R * p_rule / p_sent
403 try:
404 fr['hat_a','num',a,x] += p
405 except:
406 fr['hat_a','num',a,x] = p
407 # end reest_freq.w_right()
408
409 # in reest_freq:
410 for sent in corpus:
411 if 'REEST' in DEBUG:
412 print sent
413 ichart = {}
414 ochart = {}
415 p_sent = inner_sent(g, sent, ichart)
416 fr['ROOT','den'] += p_sent
417
418 sent_nums = g.sent_nums(sent)
419
420 for loc_h,h in locs(sent_nums,0,len(sent)+1): # locs-stop is exclusive, thus +1
421 # root:
422 fr['ROOT','num',h] += g.p_ROOT[h] * e(0,len(sent), (SEAL,h),loc_h, sent)
423
424 loc_l_h = loc_h
425 loc_r_h = loc_l_h+1
426
427 # left non-adjacent stop:
428 for i in xlt(loc_l_h):
429 fr['STOP','num',(GOL,h),NON] += c(loc_l_h, j, (LGOR, h),loc_h, sent)
430 fr['STOP','den',(GOL,h),NON] += c(loc_l_h, j, (GOL, h),loc_h, sent)
431 for j in xgteq(loc_r_h, sent):
432 fr['STOP','num',(RGOL,h),NON] += c(i, j, (SEAL, h),loc_h, sent)
433 fr['STOP','den',(RGOL,h),NON] += c(i, j, (RGOL, h),loc_h, sent)
434 # left adjacent stop, i = loc_l_h
435 fr['STOP','num',(GOL,h),ADJ] += c(loc_l_h, loc_r_h, (LGOR, h),loc_h, sent)
436 fr['STOP','den',(GOL,h),ADJ] += c(loc_l_h, loc_r_h, (GOL, h),loc_h, sent)
437 for j in xgteq(loc_r_h, sent):
438 fr['STOP','num',(RGOL,h),ADJ] += c(loc_l_h, j, (SEAL, h),loc_h, sent)
439 fr['STOP','den',(RGOL,h),ADJ] += c(loc_l_h, j, (RGOL, h),loc_h, sent)
440 # right non-adjacent stop:
441 for j in xgt(loc_r_h, sent):
442 fr['STOP','num',(GOR,h),NON] += c(loc_l_h, j, (RGOL, h),loc_h, sent)
443 fr['STOP','den',(GOR,h),NON] += c(loc_l_h, j, (GOR, h),loc_h, sent)
444 for i in xlteq(loc_l_h):
445 fr['STOP','num',(LGOR,h),NON] += c(loc_l_h, j, (SEAL, h),loc_h, sent)
446 fr['STOP','den',(LGOR,h),NON] += c(loc_l_h, j, (LGOR, h),loc_h, sent)
447 # right adjacent stop, j = loc_r_h
448 fr['STOP','num',(GOR,h),ADJ] += c(loc_l_h, loc_r_h, (RGOL, h),loc_h, sent)
449 fr['STOP','den',(GOR,h),ADJ] += c(loc_l_h, loc_r_h, (GOR, h),loc_h, sent)
450 for i in xlteq(loc_l_h):
451 fr['STOP','num',(LGOR,h),ADJ] += c(loc_l_h, j, (SEAL, h),loc_h, sent)
452 fr['STOP','den',(LGOR,h),ADJ] += c(loc_l_h, j, (LGOR, h),loc_h, sent)
453
454 # left attachment:
455 if 'REEST_ATTACH' in DEBUG:
456 print "Lattach %s: for i < %s"%(g.numtag(h),sent[0:loc_h+1])
457 for s_h in [RGOL, GOL]:
458 x = (s_h, h)
459 for i in xlt(loc_l_h): # i < loc_l(h)
460 if 'REEST_ATTACH' in DEBUG:
461 print "\tfor j >= %s"%sent[loc_h:len(sent)]
462 for j in xgteq(loc_r_h, sent): # j >= loc_r(h)
463 fr['hat_a','den',x] += c(i,j, x,loc_h, sent) # v_q in L&Y
464 if 'REEST_ATTACH' in DEBUG:
465 print "\t\tc( %d , %d, %s, %s, sent)=%.4f"%(i,j,node_str(x),loc_h,fr['hat_a','den',x])
466 w_left(i, j, x,loc_h, sent,sent_nums) # compute w for all a in sent
467
468 # right attachment:
469 if 'REEST_ATTACH' in DEBUG:
470 print "Rattach %s: for i <= %s"%(g.numtag(h),sent[0:loc_h+1])
471 for s_h in [GOR, LGOR]:
472 x = (s_h, h)
473 for i in xlteq(loc_l_h): # i <= loc_l(h)
474 if 'REEST_ATTACH' in DEBUG:
475 print "\tfor j > %s"%sent[loc_h:len(sent)]
476 for j in xgt(loc_r_h, sent): # j > loc_r(h)
477 fr['hat_a','den',x] += c(i,j, x,loc_h, sent) # v_q in L&Y
478 if 'REEST_ATTACH' in DEBUG:
479 print "\t\tc( %d , %d, %s, %s, sent)=%.4f"%(loc_h,j,node_str(x),loc_h,fr['hat_a','den',x])
480 w_right(loc_l_h,j, x,loc_h, sent,sent_nums) # compute w for all a in sent
481
482 # end for loc_h,h
483 # end for sent
484
485 return fr
486
487 def reestimate(g, corpus):
488 fr = reest_freq(g, corpus)
489 p_ROOT, p_STOP, p_ATTACH = {},{},{}
490
491 for h in g.headnums():
492 reest_head(h, fr, g, p_ROOT, p_STOP, p_ATTACH)
493
494 g.p_STOP = p_STOP
495 g.p_ATTACH = p_ATTACH
496 g.p_GO_AT = make_GO_AT(p_STOP,p_ATTACH)
497 g.p_ROOT = p_ROOT
498 return fr
499
500
501 def reest_head(h, fr, g, p_ROOT, p_STOP, p_ATTACH):
502 "Given a single head, update g with the reestimated probability."
503 # remove 0-prob stuff? todo
504 try:
505 p_ROOT[h] = fr['ROOT','num',h] / fr['ROOT','den']
506 except:
507 p_ROOT[h] = fr['ROOT','den']
508
509 for dir in [LEFT,RIGHT]:
510 for adj in [ADJ, NON]: # p_STOP
511 p_STOP[h, dir, adj] = 0.0
512 for s_h in dirseal(dir):
513 x = (s_h,h)
514 p = fr['STOP','den', x, adj]
515 if p > 0.0:
516 p = fr['STOP', 'num', x, adj] / p
517 p_STOP[h, dir, adj] += p
518
519 for s_h in dirseal(dir): # make hat_a for p_ATTACH
520 x = (s_h,h)
521 hat_a = {}
522
523 p_c = fr['hat_a','den',x]
524 for a in g.headnums():
525 try:
526 hat_a[a,x] = fr['hat_a','num',a,x] / p_c
527 except:
528 pass
529
530 sum_hat_a = sum([hat_a[w,x] for w in g.headnums()
531 if (w,x) in hat_a])
532
533 for a in g.headnums():
534 if (a,h,dir) not in p_ATTACH:
535 p_ATTACH[a,h,dir] = 0.0
536 try: # (a,x) might not be in hat_a
537 p_ATTACH[a,h,dir] += hat_a[a,x] / sum_hat_a
538 except:
539 pass
540
541
542
543
544
545
546
547
548 ###################################################
549 # Most Probable Parse: #
550 ###################################################
551
552 STOPKEY = (-1,-1,STOP,-1)
553 ROOTKEY = (-1,-1,ROOT,-1)
554
555 def make_mpptree(g, sent):
556 '''Tell inner() to make an mpptree, connect ROOT to this. (Logically,
557 this should be part of inner_sent though...)'''
558 ichart = {}
559 mpptree = { ROOTKEY:(0.0, ROOTKEY, None) }
560 for loc_w,w in locs(g.sent_nums(sent),0,len(sent)):
561 p = g.p_ROOT[w] * inner(0, len(sent), (SEAL,w), loc_w, g, sent, ichart, mpptree)
562 L = ROOTKEY
563 R = (0,len(sent), (SEAL,w), loc_w)
564 if mpptree[ROOTKEY][0] < p:
565 mpptree[ROOTKEY] = (p, L, R)
566 return mpptree
567
568 def parse_mpptree(mpptree, sent):
569 '''mpptree is a dict of the form {k:(p,L,R),...}; where k, L and R
570 are `keys' of the form (i,j,node,loc).
571
572 returns an mpp of the form [((head, loc_h),(arg, loc_a)), ...],
573 where head and arg are tags.'''
574 # local functions for clear access to mpptree:
575 def k_node(key):
576 return key[2]
577 def k_POS(key):
578 return POS(k_node(key))
579 def k_seals(key):
580 return seals(k_node(key))
581 def k_locnode(key):
582 return (k_node(key),key[3])
583 def k_locPOS(key):
584 return (k_POS(key),key[3])
585 def k_terminal(key):
586 s_k = k_seals(key) # i+1 == j
587 return key[0] + 1 == key[1] and (s_k == GOR or s_k == GOL)
588 def t_L(tree_entry):
589 return tree_entry[1]
590 def t_R(tree_entry):
591 return tree_entry[2]
592
593 # arbitrarily, "ROOT attaches to right". We add it here to
594 # avoid further complications:
595 firstkey = t_R(mpptree[ROOTKEY])
596 deps = set([ (k_locPOS(ROOTKEY), k_locPOS(firstkey), RIGHT) ])
597 q = [firstkey]
598
599 while len(q) > 0:
600 k = q.pop()
601 if k_terminal(k):
602 continue
603 else:
604 L = t_L( mpptree[k] )
605 R = t_R( mpptree[k] )
606 if k_locnode( k ) == k_locnode( L ): # Rattach
607 deps.add((k_locPOS( k ), k_locPOS( R ), LEFT))
608 q.extend( [L, R] )
609 elif k_locnode( k ) == k_locnode( R ): # Lattach
610 deps.add((k_locPOS( k ), k_locPOS( L ), RIGHT))
611 q.extend( [L, R] )
612 elif R == STOPKEY:
613 q.append( L )
614 elif L == STOPKEY:
615 q.append( R )
616 return deps
617
618 def mpp(g, sent):
619 tagf = g.numtag # localized function, todo: speed-test
620 mpptree = make_mpptree(g, sent)
621 return set([((tagf(h), loc_h), (tagf(a), loc_a))
622 for (h, loc_h),(a,loc_a),dir in parse_mpptree(mpptree,sent)])
623
624
625 ########################################################################
626 # testing functions: #
627 ########################################################################
628
629 testcorpus = [s.split() for s in ['det nn vbd c vbd','vbd nn c vbd',
630 'det nn vbd', 'det nn vbd c pp',
631 'det nn vbd', 'det vbd vbd c pp',
632 'det nn vbd', 'det nn vbd c vbd',
633 'det nn vbd', 'det nn vbd c vbd',
634 'det nn vbd', 'det nn vbd c vbd',
635 'det nn vbd', 'det nn vbd c pp',
636 'det nn vbd pp', 'det nn vbd', ]]
637
638 def testgrammar():
639 import loc_h_harmonic
640 reload(loc_h_harmonic)
641
642 # make sure these are the way they were when setting up the tests:
643 loc_h_harmonic.HARMONIC_C = 0.0
644 loc_h_harmonic.FNONSTOP_MIN = 25
645 loc_h_harmonic.FSTOP_MIN = 5
646 loc_h_harmonic.RIGHT_FIRST = 1.0
647
648 return loc_h_harmonic.initialize(testcorpus)
649
650 def ig(s,t,LHS,loc_h):
651 return inner(s,t,LHS,loc_h,testgrammar(),'det nn vbd'.split(),{})
652
653 def testreestimation():
654 g = testgrammar()
655 print g
656 # DEBUG.add('REEST_ATTACH')
657 f = reestimate(g, testcorpus)
658 print g
659 testreestimation_regression(f)
660 return f
661
662 def testreestimation_regression(fr):
663 f_stops = {('STOP', 'den', (RGOL,3),NON): 12.212773236178391, ('STOP', 'den', (GOR,2),ADJ): 4.0, ('STOP', 'num', (GOR,4),NON): 2.5553487221351365, ('STOP', 'den', (RGOL,2),NON): 1.274904052793207, ('STOP', 'num', (RGOL,1),ADJ): 14.999999999999995, ('STOP', 'den', (GOR,3),ADJ): 15.0, ('STOP', 'num', (RGOL,4),ADJ): 16.65701084787457, ('STOP', 'num', (RGOL,0),ADJ): 4.1600647714443468, ('STOP', 'den', (RGOL,4),NON): 6.0170669155897105, ('STOP', 'num', (RGOL,3),ADJ): 2.7872267638216113, ('STOP', 'num', (RGOL,2),ADJ): 2.9723139990470515, ('STOP', 'den', (RGOL,2),ADJ): 4.0, ('STOP', 'den', (GOR,3),NON): 12.945787931730905, ('STOP', 'den', (RGOL,3),ADJ): 14.999999999999996, ('STOP', 'den', (GOR,2),NON): 0.0, ('STOP', 'den', (RGOL,0),ADJ): 8.0, ('STOP', 'num', (GOR,4),ADJ): 19.44465127786486, ('STOP', 'den', (GOR,1),NON): 3.1966410324085777, ('STOP', 'den', (RGOL,1),ADJ): 14.999999999999995, ('STOP', 'num', (GOR,3),ADJ): 4.1061665495365558, ('STOP', 'den', (GOR,0),NON): 4.8282499043902476, ('STOP', 'num', (RGOL,4),NON): 5.3429891521254289, ('STOP', 'num', (GOR,2),ADJ): 4.0, ('STOP', 'den', (RGOL,4),ADJ): 22.0, ('STOP', 'num', (GOR,1),ADJ): 12.400273895299103, ('STOP', 'num', (RGOL,2),NON): 1.0276860009529487, ('STOP', 'num', (GOR,0),ADJ): 3.1717500956097533, ('STOP', 'num', (RGOL,3),NON): 12.212773236178391, ('STOP', 'den', (GOR,4),ADJ): 22.0, ('STOP', 'den', (GOR,4),NON): 2.8705211946979836, ('STOP', 'num', (RGOL,0),NON): 3.8399352285556518, ('STOP', 'num', (RGOL,1),NON): 0.0, ('STOP', 'num', (GOR,0),NON): 4.8282499043902476, ('STOP', 'num', (GOR,1),NON): 2.5997261047008959, ('STOP', 'den', (RGOL,1),NON): 0.0, ('STOP', 'den', (GOR,0),ADJ): 8.0, ('STOP', 'num', (GOR,2),NON): 0.0, ('STOP', 'den', (RGOL,0),NON): 4.6540557322109795, ('STOP', 'den', (GOR,1),ADJ): 15.0, ('STOP', 'num', (GOR,3),NON): 10.893833450463443}
664 for k,v in f_stops.iteritems():
665 if not k in fr:
666 print '''Regression in P_STOP reestimation, should be fr[%s]=%.4f,
667 but %s not in fr'''%(k,v,k)
668 elif not "%.10f"%fr[k] == "%.10f"%v:
669 print '''Regression in P_STOP reestimation, should be fr[%s]=%.4f,
670 got fr[%s]=%.4f.'''%(k,v,k,fr[k])
671
672 def testmpp_regression(mpptree,k_n):
673 mpp = {ROOTKEY: (2.877072116829971e-05, STOPKEY, (0, 3, (2, 3), 1)),
674 (0, 1, (1, 1), 0): (0.1111111111111111, (0, 1, (0, 1), 0), STOPKEY),
675 (0, 1, (2, 1), 0): (0.049382716049382713, STOPKEY, (0, 1, (1, 1), 0)),
676 (0, 3, (1, 3), 1): (0.00027619892321567721,
677 (0, 1, (2, 1), 0),
678 (1, 3, (1, 3), 1)),
679 (0, 3, (2, 3), 1): (0.00012275507698474543, STOPKEY, (0, 3, (1, 3), 1)),
680 (1, 3, (0, 3), 1): (0.025280986819448362,
681 (1, 2, (0, 3), 1),
682 (2, 3, (2, 4), 2)),
683 (1, 3, (1, 3), 1): (0.0067415964851862296, (1, 3, (0, 3), 1), STOPKEY),
684 (2, 3, (1, 4), 2): (0.32692307692307693, (2, 3, (0, 4), 2), STOPKEY),
685 (2, 3, (2, 4), 2): (0.037721893491124266, STOPKEY, (2, 3, (1, 4), 2))}
686 for k,(v,L,R) in mpp.iteritems():
687 k2 = k[0:k_n] # 3 if the new does not check loc_h
688 if type(k)==str:
689 k2 = k
690 if k2 not in mpptree:
691 print "mpp regression, %s missing"%(k2,)
692 else:
693 vnew = mpptree[k2][0]
694 if not "%.10f"%vnew == "%.10f"%v:
695 print "mpp regression, wanted %s=%.5f, got %.5f"%(k2,v,vnew)
696
697
698 def testgrammar_a():
699 h, a = 0, 1
700 p_ROOT, p_STOP, p_ATTACH, p_ORDER = {},{},{},{}
701 p_ROOT[h] = 0.9
702 p_ROOT[a] = 0.1
703 p_STOP[h,LEFT,NON] = 1.0
704 p_STOP[h,LEFT,ADJ] = 1.0
705 p_STOP[h,RIGHT,NON] = 0.4 # RSTOP
706 p_STOP[h,RIGHT,ADJ] = 0.3 # RSTOP
707 p_STOP[a,LEFT,NON] = 1.0
708 p_STOP[a,LEFT,ADJ] = 1.0
709 p_STOP[a,RIGHT,NON] = 0.4 # RSTOP
710 p_STOP[a,RIGHT,ADJ] = 0.3 # RSTOP
711 p_ATTACH[a,h,LEFT] = 1.0 # not used
712 p_ATTACH[a,h,RIGHT] = 1.0 # not used
713 p_ATTACH[h,a,LEFT] = 1.0 # not used
714 p_ATTACH[h,a,RIGHT] = 1.0 # not used
715 p_ATTACH[h,h,LEFT] = 1.0 # not used
716 p_ATTACH[h,h,RIGHT] = 1.0 # not used
717 p_ORDER[(GOR, h)] = 1.0
718 p_ORDER[(GOL, h)] = 0.0
719 p_ORDER[(GOR, a)] = 1.0
720 p_ORDER[(GOL, a)] = 0.0
721 g = DMV_Grammar({h:'h',a:'a'}, {'h':h,'a':a}, p_ROOT, p_STOP, p_ATTACH, p_ORDER)
722 # these probabilities are impossible so add them manually:
723 g.p_GO_AT[a,a,LEFT,NON] = 0.4 # Lattach
724 g.p_GO_AT[a,a,LEFT,ADJ] = 0.6 # Lattach
725 g.p_GO_AT[h,a,LEFT,NON] = 0.2 # Lattach to h
726 g.p_GO_AT[h,a,LEFT,ADJ] = 0.1 # Lattach to h
727 g.p_GO_AT[a,a,RIGHT,NON] = 1.0 # Rattach
728 g.p_GO_AT[a,a,RIGHT,ADJ] = 1.0 # Rattach
729 g.p_GO_AT[h,a,RIGHT,NON] = 1.0 # Rattach to h
730 g.p_GO_AT[h,a,RIGHT,ADJ] = 1.0 # Rattach to h
731 g.p_GO_AT[h,h,LEFT,NON] = 0.2 # Lattach
732 g.p_GO_AT[h,h,LEFT,ADJ] = 0.1 # Lattach
733 g.p_GO_AT[a,h,LEFT,NON] = 0.4 # Lattach to a
734 g.p_GO_AT[a,h,LEFT,ADJ] = 0.6 # Lattach to a
735 g.p_GO_AT[h,h,RIGHT,NON] = 1.0 # Rattach
736 g.p_GO_AT[h,h,RIGHT,ADJ] = 1.0 # Rattach
737 g.p_GO_AT[a,h,RIGHT,NON] = 1.0 # Rattach to a
738 g.p_GO_AT[a,h,RIGHT,ADJ] = 1.0 # Rattach to a
739 return g
740
741
742 def testgrammar_h():
743 h = 0
744 p_ROOT, p_STOP, p_ATTACH, p_ORDER = {},{},{},{}
745 p_ROOT[h] = 1.0
746 p_STOP[h,LEFT,NON] = 1.0
747 p_STOP[h,LEFT,ADJ] = 1.0
748 p_STOP[h,RIGHT,NON] = 0.4
749 p_STOP[h,RIGHT,ADJ] = 0.3
750 p_ATTACH[h,h,LEFT] = 1.0 # not used
751 p_ATTACH[h,h,RIGHT] = 1.0 # not used
752 p_ORDER[(GOR, h)] = 1.0
753 p_ORDER[(GOL, h)] = 0.0
754 g = DMV_Grammar({h:'h'}, {'h':h}, p_ROOT, p_STOP, p_ATTACH, p_ORDER)
755 g.p_GO_AT[h,h,LEFT,NON] = 0.6 # these probabilities are impossible
756 g.p_GO_AT[h,h,LEFT,ADJ] = 0.7 # so add them manually...
757 g.p_GO_AT[h,h,RIGHT,NON] = 1.0
758 g.p_GO_AT[h,h,RIGHT,ADJ] = 1.0
759 return g
760
761
762
763 def testreestimation_h():
764 DEBUG.add('REEST')
765 g = testgrammar_h()
766 reestimate(g,['h h h'.split()])
767
768
769 def test(wanted, got):
770 if not wanted == got:
771 raise Warning, "Regression! Should be %s: %s" % (wanted, got)
772
773 def regression_tests():
774 testmpp_regression(make_mpptree(testgrammar(), testcorpus[2]),4)
775 h = 0
776
777 test("0.120",
778 "%.3f" % inner(0, 2, (SEAL,h), 0, testgrammar_h(), 'h h'.split(),{}))
779 test("0.063",
780 "%.3f" % inner(0, 2, (SEAL,h), 1, testgrammar_h(), 'h h'.split(),{}))
781 test("0.1842",
782 "%.4f" % inner_sent(testgrammar_h(), 'h h h'.split()))
783
784 test("0.1092",
785 "%.4f" % inner(0, 3, (SEAL,0), 0, testgrammar_h(), 'h h h'.split(),{}))
786 test("0.0252",
787 "%.4f" % inner(0, 3, (SEAL,0), 1, testgrammar_h(), 'h h h'.split(),{}))
788 test("0.0498",
789 "%.4f" % inner(0, 3, (SEAL,h), 2, testgrammar_h(), 'h h h'.split(),{}))
790
791 test("0.58" ,
792 "%.2f" % outer(1, 3, (RGOL,h), 2, testgrammar_h(),'h h h'.split(),{},{}))
793 test("0.61" , # ftw? can't be right... there's an 0.4 shared between these two...
794 "%.2f" % outer(1, 3, (RGOL,h), 1, testgrammar_h(),'h h h'.split(),{},{}))
795
796 test("0.00" ,
797 "%.2f" % outer(1, 3, (RGOL,h), 0, testgrammar_h(),'h h h'.split(),{},{}))
798 test("0.00" ,
799 "%.2f" % outer(1, 3, (RGOL,h), 3, testgrammar_h(),'h h h'.split(),{},{}))
800
801 test("0.1089" ,
802 "%.4f" % outer(0, 1, (GOR,h), 0,testgrammar_a(),'h a'.split(),{},{}))
803 test("0.3600" ,
804 "%.4f" % outer(0, 2, (GOR,h), 0,testgrammar_a(),'h a'.split(),{},{}))
805 test("0.0000" ,
806 "%.4f" % outer(0, 3, (GOR,h), 0,testgrammar_a(),'h a'.split(),{},{}))
807
808 # todo: add more of these tests...
809
810 if __name__ == "__main__":
811 DEBUG.clear()
812
813 # import profile
814 # profile.run('testreestimation()')
815
816 # import timeit
817 # print timeit.Timer("loc_h_dmv.testreestimation()",'''import loc_h_dmv
818 # reload(loc_h_dmv)''').timeit(1)
819
820 regression_tests()
821
822 # print "mpp-test:"
823 # import pprint
824 # for s in testcorpus:
825 # print "sent:%s\nparse:set(\n%s)"%(s,pprint.pformat(list(mpp(testgrammar(), s)),
826 # width=40))
827
828
829 # import pprint
830 # pprint.pprint( testreestimation())
831
832
833
834 def testIO():
835 g = testgrammar()
836 inners = [(sent, inner_sent(g, sent, {})) for sent in testcorpus]
837 return inners
838
DMVCCM parser