src/io.py.~14~

   1 ##################################################################
   2 #                            Changes:                            #
   3 ##################################################################
   4 # 2008-05-24, KBU:
   5 # - more elaborate pseudo-code in the io()-function
   6 #
   7 # 2008-05-25, KBU:
   8 # - CNF_Rule has a function LHS() which returns head, in DMV_Rule this
   9 #   returns the pair of (bars, head).
  10 #
  11 # 2008-05-27
  12 # - CNF_Rule has __eq__ and __ne__ defined, so that we can use == and
  13 #   != on two such rules
  14
  15
  16 # import numpy # numpy provides Fast Arrays, for future optimization
  17 # import pprint # for pretty-printing
  18
  19 DEBUG = 0
  20
  21 # some of dmv-module bleeding in here... todo: prettier (in inner())
  22 NOBAR = 0
  23 STOP = (NOBAR, -2)
  24
  25 def debug(string):
  26     '''Easily turn on/off inline debug printouts with this global. There's
  27 a lot of cluttering debug statements here, todo: clean up'''
  28     if DEBUG:
  29         print string
  30
  31
  32 class Grammar():
  33     '''The PCFG used in the I/O-algorithm.
  34
  35     Public members:
  36     numtag, p_terminals
  37
  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.)'''
  41     def all_rules(self):
  42         return self.__p_rules
  43
  44     def rules(self, LHS):
  45         return [rule for rule in self.all_rules() if rule.LHS() == LHS]
  46
  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
  52         self.numtag = numtag
  53
  54
  55
  56
  57 class CNF_Rule():
  58     '''A single CNF rule in the PCFG, of the form
  59     LHS -> L R
  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()
  67     def __str__(self):
  68         return "%s -> %s %s [%.2f]" % (self.LHS(), self.L(), self.R(), self.prob)
  69     def __init__(self, LHS, L, R, prob):
  70         self.__LHS = LHS
  71         self.__R = R
  72         self.__L = L
  73         self.prob = prob
  74     def p(self, *arg):
  75         "Return a probability, doesn't care about attachment..."
  76         return self.prob
  77     def LHS(self):
  78         return self.__LHS
  79     def L(self):
  80         return self.__L
  81     def R(self):
  82         return self.__R
  83
  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.
  87
  88     Returns a pair of the inner probability and the chart
  89
  90     For DMV, LHS is a pair (bar, h), but this function ought to be
  91     agnostic about that.
  92
  93     e() is an internal function, so the variable chart (a dictionary)
  94     is available to all calls of e().
  95
  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
  98     optimize)
  99     '''
 100
 101     def O(s):
 102         return sent[s]
 103
 104     def e(s,t,LHS):
 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)]
 111         else:
 112             debug( "trying from %d to %d with %s" % (s,t,LHS) )
 113             if s == t:
 114                 if (LHS, O(s)) in g.p_terminals:
 115                     prob = g.p_terminals[LHS, O(s)] # b[LHS, O(s)]
 116                 else:
 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
 121                 return prob
 122             else:
 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 )
 128                     L = rule.L()
 129                     R = rule.R()
 130                     for r in range(s, t): # summing over r = s to r = t-1
 131                         p_L = e(s, r, L)
 132                         p_R = e(r + 1, t, R)
 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)]
 137     # end of e-function
 138
 139     inner_prob = e(s,t,LHS)
 140     if DEBUG:
 141         print "---CHART:---"
 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)]
 146
 147
 148
 149
 150
 151
 152
 153
 154 if __name__ == "__main__":
 155     print "IO-module tests:"
 156     b = {}
 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'
 165
 166     g = Grammar([s,np,vp,vp2], b, {0:'s',1:'np',2:'vp',3:'n',4:'p',5:'v'})
 167
 168     print "The rules:"
 169     for i in range(0,5):
 170         for r in g.rules(i):
 171             print r
 172     print ""
 173
 174     test1 = inner(0,0, 1, g, ['n'], {})
 175     if test1[0] != 0.7:
 176         print "should be 0.70 : %.2f" % test1[0]
 177         print ""
 178
 179     DEBUG = 1
 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]
 185
 186
 187 ##################################################################
 188 #            just junk from here on down:                        #
 189 ##################################################################
 190
 191 # def io(corpus):
 192 #     "(pseudo-code / wishful thinking) "
 193 #     g = initialize(corpus) # or corpus.tagset ?
 194
 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.
 198
 199 #     # --- Maximation: ---
 200 #     #
 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:
 206 #         rule.num = 0
 207 #         rule.den = 0
 208 #     for pre_term in range(len(g.p_terminals)):
 209 #         ptnum[pre_term] = 0
 210 #         ptden[pre_term] = 0
 211
 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
 224 #             #       loop then?
 225 #             rule.prob = rule.num / rule.den
 226 #         for pre_term in range(len(g.p_terminals)): # Equation 21
 227 #             num = 0
 228 #             den = 0
 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])
 233
 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]
 238
 239
 240 #     # --- Expectation: ---
 241 #     for sent in corpus: # Equation 11
 242 #         inside = inner(0, len(sent), ROOT, g, sent)
 243 #         P[sent] = inside[0]
 244
 245 #     # todo: set inner.chart to {} again, how?
 246
 247 #     # todo: need a old-P new-P distinction to check if we're below
 248 #     # threshold difference
 249 #     return "todo"
 250
 251 # def w(s,t, LHS,L,R, g, sent, P_sent):
 252 #     w = 0
 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)
 256 #     return w / P_sent
 257
 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
 260
 261
 262
 263
 264