1 ##################################################################
3 ##################################################################
5 # - more elaborate pseudo-code in the io()-function
8 # - CNF_Rule has a function LHS() which returns head, in DMV_Rule this
9 # returns the pair of (bars, head).
12 # - CNF_Rule has __eq__ and __ne__ defined, so that we can use == and
13 # != on two such rules
16 # import numpy # numpy provides Fast Arrays, for future optimization
17 # import pprint # for pretty-printing
21 # some of dmv-module bleeding in here... todo: prettier (in inner())
26 '''Easily turn on/off inline debug printouts with this global. There's
27 a lot of cluttering debug statements here, todo: clean up'''
33 '''The PCFG used in the I/O-algorithm.
38 Todo: as of now, this allows duplicate rules... should we check
39 for this? (eg. g = Grammar([x,x],[]) where x.prob == 1 may give
40 inner probabilities of 2.)'''
45 return [rule for rule in self.all_rules() if rule.LHS() == LHS]
47 def __init__(self, p_rules, p_terminals, numtag):
48 '''rules and p_terminals should be arrays, where p_terminals are of
49 the form [preterminal, terminal], and rules are CNF_Rule's.'''
50 self.__p_rules = p_rules # todo: could check for summing to 1 (+/- epsilon)
51 self.p_terminals = p_terminals
58 '''A single CNF rule in the PCFG, of the form
60 where these are just integers
61 (where do we save the connection between number and symbol?
62 symbols being 'vbd' etc.)'''
63 def __eq__(self, other):
64 return self.LHS() == other.LHS() and self.R() == other.R() and self.L() == other.L()
65 def __ne__(self, other):
66 return self.LHS() != other.LHS() or self.R() != other.R() or self.L() != other.L()
68 return "%s -> %s %s [%.2f]" % (self.LHS(), self.L(), self.R(), self.prob)
69 def __init__(self, LHS, L, R, prob):
75 "Return a probability, doesn't care about attachment..."
84 def inner(s, t, LHS, g, sent, chart):
85 ''' Give the inner probability of having the node LHS cover whatever's
86 between s and t in sentence sent, using grammar g.
88 Returns a pair of the inner probability and the chart
90 For DMV, LHS is a pair (bar, h), but this function ought to be
93 e() is an internal function, so the variable chart (a dictionary)
94 is available to all calls of e().
96 Since terminal probabilities are just simple lookups, they are not
97 put in the chart (although we could put them in there later to
105 '''Chart has lists of probability and whether or not we've attached
106 yet to L and R, each entry is a list [p, Rattach, Lattach], where if
107 Rattach==True then the rule has a right-attachment or there is one
108 lower in the tree (meaning we're no longer adjacent).'''
109 if (s, t, LHS) in chart:
110 return chart[(s, t, LHS)]
112 debug( "trying from %d to %d with %s" % (s,t,LHS) )
114 if (LHS, O(s)) in g.p_terminals:
115 prob = g.p_terminals[LHS, O(s)] # b[LHS, O(s)]
117 prob = 0.0 # todo: is this the right way to deal with lacking rules?
118 print "\t LACKING TERMINAL:"
119 debug( "\t terminal: %s -> %s : %.1f" % (LHS, O(s), prob) )
120 # terminals have no attachment
123 if (s,t,LHS) not in chart:
124 # by default, not attachment yet
125 chart[(s,t,LHS)] = 0.0 #, False, False]
126 for rule in g.rules(LHS): # summing over j,k in a[LHS,j,k]
127 debug( "\tsumming rule %s" % rule )
130 for r in range(s, t): # summing over r = s to r = t-1
133 p = rule.p("todo","todo")
134 chart[(s, t, LHS)] += p * p_L * p_R
135 debug( "\tchart[(%d,%d,%s)] = %.2f" % (s,t,LHS, chart[(s,t,LHS)]) )
136 return chart[(s, t, LHS)]
139 inner_prob = e(s,t,LHS)
142 for k,v in chart.iteritems():
143 print "\t%s -> %s_%d ... %s_%d : %.1f" % (k[2], O(k[0]), k[0], O(k[1]), k[1], v)
144 print "---CHART:end---"
145 return [inner_prob, chart] # inner_prob == chart[(s,t,LHS)]
154 if __name__ == "__main__":
155 print "IO-module tests:"
157 s = CNF_Rule(0,1,2, 1.0) # s->np vp
158 np = CNF_Rule(1,3,4, 0.3) # np->n p
159 b[1, 'n'] = 0.7 # np->'n'
160 b[3, 'n'] = 1.0 # n->'n'
161 b[4, 'p'] = 1.0 # p->'p'
162 vp = CNF_Rule(2,5,1, 0.1) # vp->v np (two parses use this rule)
163 vp2 = CNF_Rule(2,2,4, 0.9) # vp->vp p
164 b[5, 'v'] = 1.0 # v->'v'
166 g = Grammar([s,np,vp,vp2], b, {0:'s',1:'np',2:'vp',3:'n',4:'p',5:'v'})
174 test1 = inner(0,0, 1, g, ['n'], {})
176 print "should be 0.70 : %.2f" % test1[0]
180 test2 = inner(0,2, 2, g, ['v','n','p'], test1[1])
181 print "should be 0.?? (.09??) : %.2f" % test2[0]
182 print "------ trying the same again:----------"
183 test2 = inner(0,2, 2, g, ['v','n','p'], test2[1])
184 print "should be 0.?? (.09??) : %.2f" % test2[0]
187 ##################################################################
188 # just junk from here on down: #
189 ##################################################################
192 # "(pseudo-code / wishful thinking) "
193 # g = initialize(corpus) # or corpus.tagset ?
195 # P = {('v','n','p'):0.09}
196 # # P is used in v_q, w_q (expectation), so each sentence in the
197 # # corpus needs some initial P.
199 # # --- Maximation: ---
201 # # actually, this step (from Lari & Young) probably never happens
202 # # with DMV, since instead of the a[i,j,k] and b[i,m] vectors, we
203 # # have P_STOP and P_CHOOSE... or, in a sense it happens only we
204 # # calculate P_STOP and P_CHOOSE..somehow.
205 # for rule in g.p_rules:
208 # for pre_term in range(len(g.p_terminals)):
209 # ptnum[pre_term] = 0
210 # ptden[pre_term] = 0
212 # # we could also flip this to make rules the outer loop, then we
213 # # wouldn't have to initialize den/num in loops of their own
214 # for sent in corpus:
215 # for rule in g.p_rules # Equation 20
216 # for s in range(len(sent)):
217 # for t in range(s, len(sent)):
218 # rule.num += w(s,t, rule.LHS(),rule.L,rule.R, g, sent, P[sent])
219 # rule.den += v(s,t, rule.LHS(), g, sent, P[sent])
220 # # todo: do we need a "new-prob" vs "old-prob" distinction here?
221 # probably, since we use inner/outer which checks rule.prob()
222 # # todo: also, this wouldn't work, since for each sentence, we'd
223 # # discard the old probability; should rules be the outer
225 # rule.prob = rule.num / rule.den
226 # for pre_term in range(len(g.p_terminals)): # Equation 21
229 # for s in range(len(sent)):
230 # for t in range(s, len(sent)):
231 # num += v(t,t,pre_term, g, sent, P[sent])
232 # den += v(s,t,pre_term, g, sent, P[sent])
234 # for rule in g.rules:
235 # rule.prob = rule.num / rule.den
236 # for pre_term in range(len(g.p_terminals)):
237 # g.p_terminals[pre_term] = ptnum[pre_term] / ptden[pre_term]
240 # # --- Expectation: ---
241 # for sent in corpus: # Equation 11
242 # inside = inner(0, len(sent), ROOT, g, sent)
243 # P[sent] = inside[0]
245 # # todo: set inner.chart to {} again, how?
247 # # todo: need a old-P new-P distinction to check if we're below
248 # # threshold difference
251 # def w(s,t, LHS,L,R, g, sent, P_sent):
253 # rule = g.rule(LHS, L, R)
254 # for r in range(s, t):
255 # w += rule.prob() * inner(s,r, L, g, sent) * inner(r+1, t, R, g, sent) * outer(s,t,LHS,g,sent)
258 # def v(s,t, LHS, g, sent, P_sent):
259 # return ( inner(s,t, LHS, g, sent) * outer(s,t, LHS, g, sent) ) / P_sent