loc_h_dmv reestimation conforms to formulas.pdf, but cnf_ version still differs somehow
authorKevin Brubeck Unhammer <pixiemotion@gmail.com>
Wed, 27 Aug 2008 19:51:43 +0000 (27 21:51 +0200)
committerKevin Brubeck Unhammer <pixiemotion@gmail.com>
Wed, 27 Aug 2008 19:51:43 +0000 (27 21:51 +0200)
13 files changed:
DMVCCM.html
DMVCCM.org
src/cnf_dmv.py
src/common_dmv.py
src/io.py
src/io.pyc
src/loc_h_dmv.py
src/loc_h_dmv.pyc
src/main.py
tex/compile.sh.~1~ [deleted file]
tex/formulas.pdf
tex/formulas.skim
tex/formulas.tex

index 63b658b..d3f6766 100755 (executable)
@@ -6,26 +6,11 @@ lang="en" xml:lang="en">
 <title>DMV/CCM &ndash; todo-list / progress</title>
 <meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
 <meta name="generator" content="Org-mode"/>
-<meta name="generated" content="2008/08/01 21:56:44"/>
+<meta name="generated" content="2008/08/21 16:39:45"/>
 <meta name="author" content="Kevin Brubeck Unhammer"/>
 <link rel="stylesheet" type="text/css" href="http://www.student.uib.no/~kun041/org.css">
 <!-- override with local style.css: -->
 <link rel="stylesheet" type="text/css" href="./style.css">
-
-<script type="text/Javascript">
-function toggleSemester (semID) {
-    var sem = document.getElementById(semID);
-    cN = sem.childNodes;
-    for(i=0;i<cN.length;i++){
-        if (cN[i].className=="outline-4") {
-            cN[i].className="outline-4-hidden";
-        } 
-        else if(cN[i].className=="outline-4-hidden") {
-            cN[i].className="outline-4";
-        }
-    }
-} 
-</script>
 </head><body>
 <h1 class="title">DMV/CCM &ndash; todo-list / progress</h1>
 <div id="table-of-contents">
@@ -41,11 +26,12 @@ function toggleSemester (semID) {
 </li>
 <li><a href="#sec-4">4 [#C] Alternative CNF for DMV</a>
 <ul>
-<li><a href="#sec-4.1">4.1 Do we use special P_ROOT rules?</a></li>
-<li><a href="#sec-4.2">4.2 complete programming the dmv2cnf versions of dmv.py and harmonic.py </a></li>
-<li><a href="#sec-4.3">4.3 move as much as possible into common_dmv.py</a></li>
-<li><a href="#sec-4.4">4.4 dmv2cnf re-estimation formulas</a></li>
-<li><a href="#sec-4.5">4.5 dmv2cnf IO formulas</a></li>
+<li><a href="#sec-4.1">4.1 [#A] Make and implement an equivalent grammar that's really CNF</a></li>
+<li><a href="#sec-4.2">4.2 [#A] convert L&amp;Y-based reestimation into P_ATTACH and P_STOP values</a></li>
+<li><a href="#sec-4.3">4.3 [#C] move as much as possible into common_dmv.py</a></li>
+<li><a href="#sec-4.4">4.4 L&amp;Y-based reestimation for cnf_dmv</a></li>
+<li><a href="#sec-4.5">4.5 dmv2cnf re-estimation formulas</a></li>
+<li><a href="#sec-4.6">4.6 inner and outer for cnf_dmv.py, also cnf_harmonic.py </a></li>
 </ul>
 </li>
 <li><a href="#sec-5">5 Combine CCM with DMV</a></li>
@@ -92,16 +78,18 @@ function toggleSemester (semID) {
 DMV-<a href="tex/formulas.pdf">formulas.pdf</a>  &ndash; <i>clear</i> information =D
 </li>
 <li>
-<a href="src/main.py">main.py</a> &ndash; evaluation 
+<a href="src/main.py">main.py</a> &ndash; evaluation, corpus likelihoods
 </li>
 <li>
 <a href="src/wsjdep.py">wsjdep.py</a> &ndash; corpus
+
 </li>
 <li>
 <a href="src/loc_h_dmv.py">loc_h_dmv.py</a> &ndash; DMV-IO and reestimation
 </li>
 <li>
 <a href="src/loc_h_harmonic.py">loc_h_harmonic.py</a> &ndash; DMV initialization
+
 </li>
 <li>
 <a href="src/common_dmv.py">common_dmv.py</a> &ndash; various functions used by loc_h_dmv and others
@@ -109,6 +97,12 @@ DMV-<a href="tex/formulas.pdf">formulas.pdf</a>  &ndash; <i>clear</i> informatio
 <li>
 <a href="src/io.py">io.py</a> &ndash; non-DMV IO
 
+</li>
+<li>
+<a href="src/cnf_dmv.py">cnf_dmv.py</a> &ndash; cnf-like implementation of DMV
+</li>
+<li>
+<a href="src/cnf_harmonic.py">cnf_harmonic.py</a> &ndash; initialization for cnf_dmv
 
 </li>
 </ul>
@@ -216,66 +210,59 @@ ROOT  --&gt; STOP   _h_   [1.00]
 </pre>
 </p>
 
-
 </div>
 
 <div id="outline-container-4.1" class="outline-3">
-<h3 id="sec-4.1">4.1 <span class="todo">TOGROK</span> Do we use special P_ROOT rules?</h3>
+<h3 id="sec-4.1">4.1 <span class="todo">TODO</span> [#A] Make and implement an equivalent grammar that's really CNF</h3>
 <div id="text-4.1">
 
-<p>P<sub>ROOT</sub> doesn't care about adjacency anyway, so I guess it doesn't
-matter if we just sum over all head <b>types</b> in a sentence.
-</p>
-<p>
-Or?
+<p>&hellip;since I'm not sure about my unary reestimation rules (section 5 of
+<a href="tex/formulas.pdf">formulas</a>).
 </p></div>
 
 </div>
 
 <div id="outline-container-4.2" class="outline-3">
-<h3 id="sec-4.2">4.2 <span class="todo">TODO</span> complete programming the dmv2cnf versions of dmv.py and harmonic.py </h3>
+<h3 id="sec-4.2">4.2 <span class="todo">TOGROK</span> [#A] convert L&amp;Y-based reestimation into P_ATTACH and P_STOP values</h3>
 <div id="text-4.2">
 
-</div>
+<p>Sum over the various rules? Or something? Must think of this.
+</p></div>
 
 </div>
 
 <div id="outline-container-4.3" class="outline-3">
-<h3 id="sec-4.3">4.3 <span class="todo">TODO</span> move as much as possible into common_dmv.py</h3>
+<h3 id="sec-4.3">4.3 <span class="todo">TODO</span> [#C] move as much as possible into common_dmv.py</h3>
 <div id="text-4.3">
 
 <p><a href="src/common_dmv.py">common_dmv.py</a>
-</p>
-<p>
-&hellip;and improve cnf vs loc_h classes (at <i>least</i> give them different names)
 </p></div>
 
 </div>
 
 <div id="outline-container-4.4" class="outline-3">
-<h3 id="sec-4.4">4.4 <span class="todo">TODO</span> dmv2cnf re-estimation formulas</h3>
+<h3 id="sec-4.4">4.4 <span class="done">DONE</span> L&amp;Y-based reestimation for cnf_dmv</h3>
 <div id="text-4.4">
 
-<p><a href="tex/formulas.tex">tex</a> 
-</p>
-<p>
-The reestimation function still has to sum over the various
-possibilities of N's and A's; but it seems to be simpler than the
-loc_h-method altogether.
-</p>
-<p>
-Question: Would it be the same thing to reestimate using completely
-regular IO reestimation? 
+<p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-08-21 Thu 16:35</span><br/>
 </p></div>
 
 </div>
 
 <div id="outline-container-4.5" class="outline-3">
-<h3 id="sec-4.5">4.5 <span class="done">DONE</span> dmv2cnf IO formulas</h3>
+<h3 id="sec-4.5">4.5 <span class="done">DONE</span> dmv2cnf re-estimation formulas</h3>
 <div id="text-4.5">
 
-<p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-07-30 Wed 00:40</span><br/>
+<p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-08-21 Thu 16:36</span><br/>
 </p></div>
+
+</div>
+
+<div id="outline-container-4.6" class="outline-3">
+<h3 id="sec-4.6">4.6 <span class="done">DONE</span> inner and outer for cnf_dmv.py, also cnf_harmonic.py </h3>
+<div id="text-4.6">
+
+</div>
 </div>
 
 </div>
@@ -637,6 +624,10 @@ Good tutorial:
 <div id="postamble"><p class="author"> Author: Kevin Brubeck Unhammer
 <a href="mailto:K.BrubeckUnhammer at student uva nl ">&lt;K.BrubeckUnhammer at student uva nl &gt;</a>
 </p>
-<p class="date"> Date: 2008/08/01 21:56:44</p>
-</div><div class="post-postamble" id="nn-postamble">Skrive vha. emacs + <a href='http://orgmode.org/'>org-mode</a></div></body>
+<p class="date"> Date: 2008/08/21 16:39:45</p>
+</div><div class="post-postamble" id="nn-postamble">
+Skrive vha. emacs + <a href='http://orgmode.org/'>org-mode</a>
+</div>
+<script src="./post-script.js" type="text/JavaScript">
+</script></body>
 </html>
index 776eaa7..edbe3d8 100755 (executable)
 [[file:src/loc_h_dmv.py][loc_h_dmv.py]]
 
 Meta-todo: 
-- make test battery
-- change the h's to h_l in [[file:tex/formulas.pdf][formulas.pdf]]
+- debug reestimate2 which stores charts for all sentences and has
+  arguments as the outer loop
+  - have to fix the lack of attachment probabilities...
+- fix cnf outer
 
 [[file:DMVCCM.html][DMVCCM.html]]
 
 * DMV/CCM report and project
 - DMV-[[file:tex/formulas.pdf][formulas.pdf]]  -- /clear/ information =D
-- [[file:src/main.py][main.py]] -- evaluation 
+- [[file:src/main.py][main.py]] -- evaluation, corpus likelihoods
 - [[file:src/wsjdep.py][wsjdep.py]] -- corpus
+
 - [[file:src/loc_h_dmv.py][loc_h_dmv.py]] -- DMV-IO and reestimation
 - [[file:src/loc_h_harmonic.py][loc_h_harmonic.py]] -- DMV initialization
+
 - [[file:src/common_dmv.py][common_dmv.py]] -- various functions used by loc_h_dmv and others
 - [[file:src/io.py][io.py]] -- non-DMV IO
-# - [[file:src/cnf_harmonic.py][cnf_harmonic.py]]
-# - [[file:src/cnf_dmv.py][cnf_dmv.py]]
 
+- [[file:src/cnf_dmv.py][cnf_dmv.py]] -- cnf-like implementation of DMV
+- [[file:src/cnf_harmonic.py][cnf_harmonic.py]] -- initialization for cnf_dmv
 
 [[http://www.student.uib.no/~kun041/dmvccm/DMVCCM_archive.html][Archived entries]] from this file.
 * Notation
@@ -123,24 +127,31 @@ Given a grammar with certain p_ATTACH, p_STOP and p_ROOT, we get:
 : <h>< -->  _h_   <h>< [0.60]
 :ROOT  --> STOP   _h_  [1.00]
 
-
-** TODO program reestimation for cnf_dmv
-Not sure how this should be done; we could either do it the way it's
-done in Klein and Manning, or take it all the way into Lari &
-Young. Possibly do both, to find this stupid bug...
-** TODO dmv2cnf re-estimation formulas
-[[file:tex/formulas.tex][tex]] 
-
-The reestimation function still has to sum over the various
-possibilities of N's and A's; but it seems to be simpler than the
-loc_h-method altogether.
-
-Question: Would it be the same thing to reestimate using completely
-regular IO reestimation? 
-** TODO move as much as possible into common_dmv.py
+** TODO [#A] Make and implement an equivalent grammar that's /pure/ CNF
+...since I'm not sure about my unary reestimation rules (section 5 of
+[[file:tex/formulas.pdf][formulas]]).
+
+:  h>< -->   h>  STOP 
+:  h>< -->  >h>  STOP 
+: _h_  --> STOP    h><
+: _h_  --> STOP   <h><
+: >h>  -->   h>   _a_ 
+: >h>  -->  >h>   _a_ 
+: <h>< -->  _a_    h><
+: <h>< -->  _a_   <h><
+: ROOT -->  _a_   <h>< p_ROOT(h) * p_ATTACH(a|h,L) 
+: ROOT -->  _a_    h>  p_ROOT(h) * p_ATTACH(a|h,R) 
+: ROOT -->   h         p_ROOT(h)
+
+
+** TOGROK [#A] convert L&Y-based reestimation into P_ATTACH and P_STOP values
+Sum over the various rules? Or something? Must think of this.
+** TODO [#C] move as much as possible into common_dmv.py
 [[file:src/common_dmv.py][common_dmv.py]]
-
-...and improve cnf vs loc_h classes (at /least/ give them different names)
+** DONE L&Y-based reestimation for cnf_dmv
+   CLOSED: [2008-08-21 Thu 16:35]
+** DONE dmv2cnf re-estimation formulas
+   CLOSED: [2008-08-21 Thu 16:36]
 ** DONE inner and outer for cnf_dmv.py, also cnf_harmonic.py 
 * TOGROK Combine CCM with DMV
 
index d596dec..6627d87 100755 (executable)
@@ -54,6 +54,7 @@ class CNF_DMV_Grammar(io.Grammar):
             self.__mothersR[w_node] = [r for LHS in self.LHSs()
                                        for r in self.rules(LHS)
                                        if r.R() == w_node]
+        argnums.append(POS(STOP))
         return [r for r in self.__mothersR[w_node]
                 if POS(r.L()) in argnums]
 
@@ -63,6 +64,7 @@ class CNF_DMV_Grammar(io.Grammar):
             self.__mothersL[w_node] = [r for LHS in self.LHSs()
                                        for r in self.rules(LHS)
                                        if r.L() == w_node] 
+        argnums.append(POS(STOP))
         return [r for r in self.__mothersL[w_node]
                 if POS(r.R()) in argnums]
 
@@ -315,7 +317,7 @@ def outer(i,j,w_node, g, sent, ichart={}, ochart={}):
 #      reestimation, todo:   #
 ##############################
 def reest_zeros(rules):
-    f = {}
+    f = { ('den',ROOT) : 0.0 }
     for r in rules:
         for nd in ['num','den']:
             f[nd, r.LHS(), r.L(), r.R()] = 0.0
@@ -371,8 +373,8 @@ def reest_freq(g, corpus):
         else:
             return inner(i,j,LHS,g,sent,ichart) 
         
-    for sn,sent in enumerate(corpus):
-        if sn%1==0: print "sentence number %d"%sn
+    for s_num,sent in enumerate(corpus):
+        if s_num%5==0: print "s.num %d"%s_num,
         if 'REEST' in DEBUG: print sent
         ichart = {}
         ochart = {}
@@ -383,12 +385,11 @@ def reest_freq(g, corpus):
         sent_nums = g.sent_nums(sent)
         sent_rules = g.sent_rules(sent_nums)
         for r in sent_rules:
-            print r
             LHS, L, R = r.LHS(), r.L(), r.R()
             if 'REEST' in DEBUG: print r
             if LHS == ROOT: 
                 f['num',LHS,L,R] += r.p() * e_g(0, len(sent), R, sent)
-                f['den',LHS,L,R] += p_sent
+                f['den',ROOT] += p_sent
                 continue # !!! o/w we add wrong values to it below
             if L == STOP or R == STOP:
                 w = w1_g
@@ -397,21 +398,25 @@ def reest_freq(g, corpus):
             for i in xlt(len(sent)):
                 for j in xgt(i, sent):
                     f['num',LHS,L,R] +=   w(i,j, r,   sent)
-                    f['den',LHS,L,R] += c_g(i,j, LHS, sent)
+                    f['den',LHS,L,R] += c_g(i,j, LHS, sent) # v_q
+    print ""
     return f
 
 def reestimate(g, corpus):
     f = reest_freq(g, corpus)
     print "applying f to rules"
     for r in g.all_rules():
-        r.prob = f['den',r.LHS(),r.L(),r.R()]
+        if r.LHS() == ROOT:
+            r.prob = f['den',ROOT]
+        else:
+            r.prob = f['den',r.LHS(),r.L(),r.R()]
         if r.prob > 0.0:
             r.prob = f['num',r.LHS(),r.L(),r.R()] / r.prob
-    return f
+    return g
 
 
 ##############################
-#     testing functions:     #
+#     Testing functions:     #
 ##############################
 def testgrammar():
     # make sure we use the same data:
@@ -424,8 +429,8 @@ def testgrammar():
 def testreestimation():
     from loc_h_dmv import testcorpus
     g = testgrammar()
-    f = reestimate(g, testcorpus[0:4])
-    return (f,g)
+    g = reestimate(g, testcorpus[0:4])
+    return g
 
 def testgrammar_a():                            # Non, Adj
     _h_ = CNF_DMV_Rule((SEAL,0), STOP,    ( RGOL,0), 1.0, 1.0) # LSTOP
@@ -512,4 +517,4 @@ if __name__ == "__main__":
     regression_tests()
 #     g = testgrammar()
 #     print g
-    print "TODO!!!! fix outer (also, make mothersL and R faster somehow)"
+
index 92fddb9..2490962 100644 (file)
@@ -48,6 +48,9 @@ def xgt(gt, sent):
     lt = len(sent) + 1 
     return xrange(gt+1, lt) 
 
+def xeq(eq, sent=[]):
+    return [eq]
+
 def xgteq(gteq, sent):
     '''Include the position "behind" the last word, ie. len(sent).'''
     lt = len(sent) + 1 
index 7eec28f..0853544 100644 (file)
--- a/src/io.py
+++ b/src/io.py
@@ -50,6 +50,9 @@ class Grammar():
         else:
             return self.__tagnum[tag]
 
+    def get_nums_tags(self):
+        return (self.__numtag,self.__tagnum)
+
     def __init__(self, numtag, tagnum, p_rules=[], p_terminals=[]):
         '''rules and p_terminals should be arrays, where p_terminals are of
         the form [preterminal, terminal], and rules are CNF_Rule's.'''        
index d9d4fe6..d85f16d 100644 (file)
Binary files a/src/io.pyc and b/src/io.pyc differ
index 52620fd..1319783 100644 (file)
@@ -2,8 +2,16 @@
 # 
 # dmv reestimation and inside-outside probabilities using loc_h, and
 # no CNF-style rules
+#
+# Table of Contents:
+# 1. Grammar-class and related functions
+# 2. P_INSIDE / inner() and inner_sent()
+# 3. P_OUTSIDE / outer()
+# 4. Reestimation v.1: sentences as outer loop
+# 5. Reestimation v.2: head-types as outer loop
+# 6. Most Probable Parse
+# 7. Testing functions
 
-#import numpy # numpy provides Fast Arrays, for future optimization
 import io
 from common_dmv import *
 
@@ -68,7 +76,29 @@ class DMV_Grammar(io.Grammar):
         self.p_ATTACH = p_ATTACH # p_ATTACH[a, h, LEFT] = p (etc. for R)
                                  # p_GO_AT[a, h, LEFT, NON] = p (etc. for LA,RN,RA)
         self.p_GO_AT = make_GO_AT(self.p_STOP, self.p_ATTACH)
-    
+        # these are used in reestimate2():
+        self.reset_iocharts()
+        
+    def get_iochart(self, sent_nums):
+        ch_key = tuple(sent_nums)
+        try:
+            ichart = self._icharts[ch_key]
+        except:
+            ichart = {}
+        try:
+            ochart = self._ocharts[ch_key]
+        except:
+            ochart = {}
+        return (ichart, ochart)
+
+    def set_iochart(self, sent_nums, ichart, ochart):
+        self._icharts[tuple(sent_nums)] = ichart
+        self._ocharts[tuple(sent_nums)] = ochart
+
+    def reset_iocharts(self):
+        self._icharts = {}
+        self._ocharts = {}
+
     def p_GO_AT_or0(self, a, h, dir, adj):
         try:
             return self.p_GO_AT[a, h, dir, adj]
@@ -307,14 +337,10 @@ def outer(i,j,w_node,loc_w, g, sent, ichart={}, ochart={}):
 
 
 ###################################################
-#                  Reestimation:                  #
+#              Reestimation v.1:                  #
+#           Sentences as outer loop               #
 ###################################################
 
-# todo: it seems we have to rewrite attachment reestimation so that we
-# have 'a´ as the outer loop, then sentences... but this means running
-# through sentences several times, and that would require storing
-# inner probabilites...agh!
-
 def reest_zeros(h_nums):
     '''A dict to hold numerators and denominators for our 6+ reestimation
 formulas. '''
@@ -332,6 +358,7 @@ formulas. '''
                     fr['STOP',nd,x,adj] = 0.0
     return fr
 
+
 def reest_freq(g, corpus):
     fr = reest_zeros(g.headnums())
     ichart = {}
@@ -483,28 +510,27 @@ def reest_freq(g, corpus):
                     if 'REEST_ATTACH' in DEBUG:
                         print "\tfor j > %s"%sent[loc_h:len(sent)]
                     for j in xgt(loc_r_h, sent): # j > loc_r(h) 
-                        fr['hat_a','den',x] += c(i,j, x,loc_h, sent) # v_q in L&Y 
+                        fr['hat_a','den',x] += c(i,j, x,loc_h, sent) # v_q in L&Y
                         if 'REEST_ATTACH' in DEBUG:
                             print "\t\tc( %d , %d, %s, %s, sent)=%.4f"%(loc_h,j,node_str(x),loc_h,fr['hat_a','den',x])
-                        w_right(loc_l_h,j, x,loc_h, sent,sent_nums) # compute w for all a in sent
-
+                        w_right(i,j, x,loc_h, sent,sent_nums) # compute w for all a in sent
         # end for loc_h,h
     # end for sent
     
     return fr
 
-def reestimate(g, corpus):
-    fr = reest_freq(g, corpus)
+def reestimate(old_g, corpus):
+    fr = reest_freq(old_g, corpus)
     p_ROOT, p_STOP, p_ATTACH = {},{},{}
 
-    for h in g.headnums():
-        reest_head(h, fr, g, p_ROOT, p_STOP, p_ATTACH)
+    for h in old_g.headnums():
+        # reest_head changes p_ROOT, p_STOP, p_ATTACH
+        reest_head(h, fr, old_g, p_ROOT, p_STOP, p_ATTACH)
+    p_ORDER = old_g.p_ORDER
+    numtag, tagnum = old_g.get_nums_tags()
     
-    g.p_STOP = p_STOP
-    g.p_ATTACH = p_ATTACH
-    g.p_GO_AT = make_GO_AT(p_STOP,p_ATTACH)
-    g.p_ROOT = p_ROOT
-    return fr
+    new_g = DMV_Grammar(numtag, tagnum, p_ROOT, p_STOP, p_ATTACH, p_ORDER)
+    return new_g
 
 
 def reest_head(h, fr, g, p_ROOT, p_STOP, p_ATTACH):
@@ -530,12 +556,13 @@ def reest_head(h, fr, g, p_ROOT, p_STOP, p_ATTACH):
             hat_a = {}
             
             p_c = fr['hat_a','den',x]
-            for a in g.headnums():
+            for w in g.headnums():
                 try:
-                    hat_a[a,x] = fr['hat_a','num',a,x] / p_c
+                    hat_a[w,x] = fr['hat_a','num',w,x] / p_c
                 except:
                     pass
-                
+
+            # this has to happen after all_w hat_a[w,x] are done:
             sum_hat_a = sum([hat_a[w,x] for w in g.headnums()
                              if (w,x) in hat_a])
 
@@ -551,7 +578,209 @@ def reest_head(h, fr, g, p_ROOT, p_STOP, p_ATTACH):
 
         
         
+###################################################
+#              Reestimation v.2:                  #
+#            Heads as outer loop                  #
+###################################################
+
+def locs_h(h, sent_nums):
+    '''Return the between-word locations of all tokens of h in sent.'''
+    return [loc_w for loc_w,w in locs(sent_nums, 0, len(sent_nums))
+            if w == h]
+
+def locs_a(a, sent_nums, start, stop):
+    '''Return the between-word locations of all tokens of h in some
+    fragment of sent. We make sure to offset the locations correctly
+    so that for any w in the returned list, sent[w]==loc_w.
+    
+    start is inclusive, stop is exclusive, as in klein-thesis and
+    Python's list-slicing (eg. return left-loc).'''
+    return [loc_w for loc_w,w in locs(sent_nums, start, stop)
+            if w == a]
+
+def inner2(i, j, node, loc_h, g, sent):
+    ichart,ochart = g.get_iochart(s_n)
+    try: p = ichart[i,j,x,loc_h]
+    except: p = inner(i,j,x,loc_h,g,sent,ichart) 
+    g.set_iochart(s_n,ichart,ochart)
+    return p
+
+def inner_sent2(g, sent):
+    ichart,ochart = g.get_iochart(s_n)
+    p = inner_sent(g,sent,ichart)
+    g.set_iochart(s_n,ichart,ochart)
+    return p
+
+def outer2(i, j,w_node,loc_w, g, sent):
+    ichart,ochart = g.get_iochart(s_n)
+    try: p = ochart[i,j,w_node,loc_w]
+    except: p = inner(i,j,w_node,loc_w,g,sent,ichart,ochart) 
+    g.set_iochart(s_n,ichart,ochart)
+    return p
+
+def reestimate2(old_g, corpus):
+    p_ROOT, p_STOP, p_ATTACH = {},{},{}
+    
+    for h in old_g.headnums():
+        # reest_head changes p_ROOT, p_STOP, p_ATTACH
+        reest_head2(h, old_g, corpus, p_ROOT, p_STOP, p_ATTACH)
+    p_ORDER = old_g.p_ORDER
+    numtag, tagnum = old_g.get_nums_tags()
+    
+    new_g = DMV_Grammar(numtag, tagnum, p_ROOT, p_STOP, p_ATTACH, p_ORDER)
+    return new_g
+
+def hat_d2(xbar, x, xi, xj, g, corpus): # stop helper
+    def c(x,loc_x,i,j): return c2(x,loc_x,i,j,g,s_n,sent)
+    
+    h = POS(x)
+    if h != POS(xbar): raise ValueError
+    
+    num, den = 0.0, 0.0
+    for s_n,sent in [(g.sent_nums(sent),sent) for sent in corpus]:
+        for loc_h in locs_h(h,s_n):
+            loc_l_h, loc_r_h = loc_h, loc_h + 1
+            for i in xi(loc_l_h):
+                for j in xj(loc_r_h, s_n):
+#                     print "s:%s %d,%d"%(sent,i,j)
+                    num += c(xbar,loc_h,i,j) 
+                    den += c(x,loc_h,i,j)    
+    if den == 0.0:
+        return den                
+    return num/den # eg. SEAL/RGOL, xbar/x 
+    
+
+def c2(x,loc_h,i,j,g,s_n,sent):
+    ichart,ochart = g.get_iochart(s_n)
+    
+    def f(i,j,x,loc_h): # P_{OUTSIDE}
+        try: return ochart[i,j,x,loc_h]
+        except: return outer(i,j,x,loc_h,g,sent,ichart,ochart)
+    def e(i,j,x,loc_h): # P_{INSIDE}
+        try: return ichart[i,j,x,loc_h]
+        except: return inner(i,j,x,loc_h,g,sent,ichart) 
+
+    p_sent = inner_sent(g, sent, ichart)
+    if not p_sent > 0.0:
+        return p_sent
+    
+    p_in = e(i,j, x,loc_h)
+    if not p_in > 0.0: 
+        return p_in
+    
+    p_out = f(i,j, x,loc_h)
 
+    g.set_iochart(s_n,ichart,ochart)
+    return p_in * p_out / p_sent
+
+def w2(a, x,loc_h, dir, i, j, g, s_n,sent):
+    ichart,ochart = g.get_iochart(s_n)
+    
+    def f(i,j,x,loc_h): # P_{OUTSIDE}
+        try: return ochart[i,j,x,loc_h]
+        except: return outer(i,j,x,loc_h,g,sent,ichart,ochart)
+    def e(i,j,x,loc_h): # P_{INSIDE}
+        try: return ichart[i,j,x,loc_h]
+        except: return inner(i,j,x,loc_h,g,sent,ichart) 
+
+    h = POS(x)
+    p_sent = inner_sent(g, sent, ichart)
+    
+    if dir == LEFT:
+        L, R = (SEAL,a),x
+    else:
+        L, R = x,(SEAL,a)
+    w_sum = 0.0
+    
+    for k in xtween(i,j):
+        if dir == LEFT:
+            start, stop = i, k
+        else:
+            start, stop = k, j
+        for loc_a in locs_a(a, s_n, start, stop):
+            if dir == LEFT:
+                loc_L, loc_R = loc_a, loc_h
+            else:
+                loc_L, loc_R = loc_h, loc_a
+            p = g.p_GO_AT_or0(a,h,dir,adj(k,loc_h))
+            in_L = e(i,k,L,loc_L) 
+            in_R = e(k,j,R,loc_R) 
+            out =  f(i,j,x,loc_h)
+            w_sum += p * in_L * in_R * out
+            
+    g.set_iochart(s_n,ichart,ochart)
+    return w_sum/p_sent
+
+def hat_a2(a, x, dir, g, corpus): # attachment helper
+    def w(a,x,loc_x,dir,i,j): return w2(a,x,loc_x,dir,i,j,g,s_n,sent)
+    def c(x,loc_x,i,j): return c2(x,loc_x,i,j,g,s_n,sent)
+
+    h = POS(x)
+    if dir == LEFT:
+        xi, xj = xlt, xgteq
+    else:
+        xi, xj = xlteq, xgt 
+    den, num = 0.0, 0.0
+    
+    for s_n,sent in [(g.sent_nums(sent),sent) for sent in corpus]:
+        for loc_h in locs_h(h,s_n):
+            loc_l_h, loc_r_h = loc_h, loc_h + 1
+            for i in xi(loc_l_h):
+                for j in xj(loc_r_h,sent):
+                    num += w(a, x,loc_h, dir, i,j)
+                    den += c(x,loc_h, i,j)
+    if den == 0.0:
+        return den
+    return num/den
+
+def reest_root2(h,g,corpus):
+    num, den = 0.0, 0.0
+    for s_n,sent in [(g.sent_nums(sent),sent) for sent in corpus]:
+        ichart, ochart = g.get_iochart(s_n)
+        den += inner_sent(g, sent, ichart)
+        for loc_h in locs_h(h,s_n):
+            num += \
+                g.p_ROOT[h] * \
+                inner(0, len(s_n), (SEAL,h), loc_h, g, sent, ichart)
+        g.set_iochart(s_n, ichart, ochart)
+    return num / den
+
+def reest_head2(h, g, corpus, p_ROOT, p_STOP, p_ATTACH):
+    def hat_d(xbar,x,xi,xj): return hat_d2(xbar,x,xi,xj, g, corpus)
+    def hat_a(a, x, dir  ): return hat_a2(a, x, dir,   g, corpus)
+    def div(num,den):
+        if den > 0.0: return num / den
+        else: return den
+    
+    p_STOP[h, LEFT,NON] = \
+        hat_d((SEAL,h),(RGOL,h),xlt,  xgteq) + \
+        hat_d((LGOR,h),( GOL,h),xlt,  xeq) 
+    p_STOP[h, LEFT,ADJ] = \
+        hat_d((SEAL,h),(RGOL,h),xeq,  xgteq) + \
+        hat_d((LGOR,h),( GOL,h),xeq,  xeq)
+    p_STOP[h,RIGHT,NON] = \
+        hat_d((RGOL,h),( GOR,h),xeq,  xgt) + \
+        hat_d((SEAL,h),(LGOR,h),xlteq,xgt)
+    p_STOP[h,RIGHT,ADJ] = \
+        hat_d((RGOL,h),( GOR,h),xeq,  xeq) + \
+        hat_d((SEAL,h),(LGOR,h),xlteq,xeq)
+
+    p_ROOT[h] = reest_root2(h,g,corpus)
+    
+    for a in g.headnums():
+        p_ATTACH[a,h,LEFT] = \
+            div( hat_a(a, (GOL,h),LEFT),
+                 sum([hat_a(w, (GOL,h),LEFT) for w in g.headnums()]) ) + \
+            div( hat_a(a,(RGOL,h),LEFT),
+                 sum([hat_a(w,(RGOL,h),LEFT) for w in g.headnums()]) )
+        p_ATTACH[a,h,RIGHT] = \
+            div( hat_a(a, (GOR,h),RIGHT),
+                 sum([hat_a(w, (GOR,h),RIGHT) for w in g.headnums()]) ) + \
+            div( hat_a(a,(LGOR,h),RIGHT),
+                 sum([hat_a(w,(LGOR,h),RIGHT) for w in g.headnums()]) )
+
+            
+        
 
 
 ###################################################
@@ -656,27 +885,16 @@ def testgrammar():
 
     return loc_h_harmonic.initialize(testcorpus)
 
-def ig(s,t,LHS,loc_h):
-    return inner(s,t,LHS,loc_h,testgrammar(),'det nn vbd'.split(),{})
+def testreestimation2():
+    g2 = testgrammar()
+    reestimate2(g2, testcorpus)
+    return g2
 
 def testreestimation():
     g = testgrammar()
-    print g
-#    DEBUG.add('REEST_ATTACH')
-    f = reestimate(g, testcorpus)
-    print g
-    testreestimation_regression(f)
-    return f
-
-def testreestimation_regression(fr):
-    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}
-    for k,v in f_stops.iteritems():
-        if not k in fr:
-            print '''Regression in P_STOP reestimation, should be fr[%s]=%.4f,
-but %s not in fr'''%(k,v,k)
-        elif not "%.10f"%fr[k] == "%.10f"%v:
-            print '''Regression in P_STOP reestimation, should be fr[%s]=%.4f,
-got fr[%s]=%.4f.'''%(k,v,k,fr[k])
+    g = reestimate(g, testcorpus)
+    return g
+
 
 def testmpp_regression(mpptree,k_n):
     mpp = {ROOTKEY: (2.877072116829971e-05, STOPKEY, (0, 3, (2, 3), 1)),
@@ -815,6 +1033,27 @@ def regression_tests():
          "%.4f" % outer(0, 3, (GOR,h),  0,testgrammar_a(),'h a'.split(),{},{}))
 
     # todo: add more of these tests...
+    
+
+
+def compare_grammars(g1,g2):
+    result = ""
+    for d1,d2 in [(g1.p_ATTACH,g2.p_ATTACH),(g1.p_STOP,g2.p_STOP),
+                  (g1.p_ORDER, g2.p_ORDER), (g1.p_ROOT,g2.p_ROOT) ]:
+        for k,v in d1.iteritems():
+            if k not in d2:
+                result += "\nreestimate1[%s]=%s missing from reestimate2"%(k,v)
+            elif "%s"%d2[k] != "%s"%v:
+                result += "\nreestimate1[%s]=%s while \nreestimate2[%s]=%s."%(k,v,k,d2[k])
+        for k,v in d2.iteritems():
+            if k not in d1:
+                result += "\nreestimate2[%s]=%s missing from reestimate1"%(k,v)
+    return result
+
+def testIO():
+    g = testgrammar()
+    inners = [(sent, inner_sent(g, sent, {})) for sent in testcorpus]
+    return inners
 
 if __name__ == "__main__":
     DEBUG.clear()
@@ -833,15 +1072,7 @@ if __name__ == "__main__":
 #     for s in testcorpus:
 #         print "sent:%s\nparse:set(\n%s)"%(s,pprint.pformat(list(mpp(testgrammar(), s)),
 #                                                     width=40))
-    
-    
-#     import pprint
-#     pprint.pprint( testreestimation())
-    
-
-
-def testIO():
-    g = testgrammar()
-    inners = [(sent, inner_sent(g, sent, {})) for sent in testcorpus]
-    return inners
 
+    g1 = testreestimation()
+    g2 = testreestimation2()
+    print compare_grammars(g1,g2)
index 4ca3600..1d73c10 100644 (file)
Binary files a/src/loc_h_dmv.pyc and b/src/loc_h_dmv.pyc differ
index b843739..b4058f6 100644 (file)
@@ -24,38 +24,41 @@ def initialize_cnf(tagonlys):
     return cnf_harmonic.initialize(tagonlys)
     
 
-def test_likelihood(reestimate, initialize, inner_sent):
-    def run_IO(iterations, tagonlys, tags_and_parses):
+def test_likelihood(reestimate, initialize, inner_sent, corpus_size=20, corpus_offset=1000):
+    def run_IO(g, iterations, tagonlys, tags_and_parses):
         print corpus_likelihood(g, tagonlys)
-        #print evaluate(g, tags_and_parses)
+        # print evaluate(g, tags_and_parses) #
         for i in range(iterations):
-            f = reestimate(g, tagonlys)
+            g = reestimate(g, tagonlys)
             print "reestimation number %d done"%i
-            #print evaluate(g, tags_and_parses)
-            print corpus_likelihood(g, tagonlys)
+            # print evaluate(g, tags_and_parses) #
+            print corpus_likelihood(g, tagonlys) 
+        return g
 
     def corpus_likelihood(g, tagsonly):
         from math import log
         sumlog = 0.0
         for sent in tagsonly:
-            p_sent = inner_sent(g, sent)
+            p_sent = inner_sent(g, sent, {})
             if p_sent == 0.0:
                 print "%s had zero probability!"%sent
             else:
                 sumlog += log(p_sent)
-        return "Sum of log P_{sentence}: %.4f\n"%sumlog
+        return "Sum of log P_{sentence}: %.4f (should move towards 0)\n"%sumlog
 
     reader = WSJDepCorpusReader(None)
-    corpus_size = 100
-    tagonlys = reader.tagonly_sents()[1000:1000+corpus_size]
-    tags_and_parses = reader.tagged_and_parsed_sents()[1000:1000+corpus_size]
+    tagonlys = reader.tagonly_sents()[corpus_offset:corpus_offset+corpus_size]
+    tags_and_parses = reader.tagged_and_parsed_sents()[corpus_offset:corpus_offset+corpus_size]
 
-    print "initializing %d sentences"%corpus_size
+#     from loc_h_dmv import testcorpus
+#     tagonlys = testcorpus
+    
+    print "initializing %d sentences..." % corpus_size,
     g = initialize(tagonlys)
     print "initialized"
     
-    run_IO(4, tagonlys, tags_and_parses)
-
+    g = run_IO(g, 4, tagonlys, tags_and_parses)
+    return g
 
 
 def evaluate(g, tagged_and_parsed_sents):
@@ -110,7 +113,8 @@ F1: \t\t%.4f'''%(recall_num,recall_den,recall,precision_num,precision_den, preci
 def compare_loc_h_cnf():
     reader = WSJDepCorpusReader(None)
     corpus_size = 200
-    tagonlys = reader.tagonly_sents()[1000:1000+corpus_size]
+    corpus_offset = 1000
+    tagonlys = reader.tagonly_sents()[corpus_offset:corpus_offset+corpus_size]
 
     import loc_h_harmonic, cnf_harmonic
     g_l = loc_h_harmonic.initialize(tagonlys)
@@ -131,14 +135,15 @@ def compare_loc_h_cnf():
     
     import loc_h_dmv, cnf_dmv
     for sent in tagonlys:
-        i_l = loc_h_dmv.inner_sent(g_l, sent, {})
-        i_c = cnf_dmv.inner_sent(g_c, sent, {})
+        ochart_l, ochart_c, ichart_l, ichart_c = {},{},{},{}
+        i_l = loc_h_dmv.inner_sent(g_l, sent, ichart_l)
+        i_c = cnf_dmv.inner_sent(g_c, sent, ichart_c)
         test( "%s"%i_l, "%s"%i_c, "i_l","i_c")
         
         for loc_w,w in enumerate(sent):
             w_node = (GOR, g_l.tagnum(w))
-            o_l = loc_h_dmv.outer(loc_w,loc_w+1,w_node,loc_w, g_l, sent, {},{})
-            o_c =   cnf_dmv.outer(loc_w,loc_w+1,w_node,       g_c, sent, {},{})
+            o_l = loc_h_dmv.outer(loc_w,loc_w+1,w_node,loc_w, g_l, sent, ichart_l,ochart_l)
+            o_c =   cnf_dmv.outer(loc_w,loc_w+1,w_node,       g_c, sent, ichart_c,ochart_c)
             print "%s, %s, %s"%(sent,node_str(w_node),loc_w)
             test("%s"%o_l, "%s"%o_c, "o_l(0,1,(GOR,%s),%d,...)"%(w,loc_w),"o_c")
 
@@ -146,13 +151,25 @@ def compare_loc_h_cnf():
 
 if __name__ == "__main__":
     print "main.py:"
-    #compare_loc_h_cnf()
+#     compare_loc_h_cnf()
+
     import cnf_dmv
-    test_likelihood(cnf_dmv.reestimate,
-                    initialize_cnf,
-                    cnf_dmv.inner_sent)
-#     import loc_h_dmv
-#     test_likelihood(loc_h_dmv.reestimate,
-#                     initialize_loc_h,
-#                     loc_h_dmv.inner_sent)
+    print "\ntrying cnf-reestimate ##############################"
+    g = test_likelihood(cnf_dmv.reestimate,
+                        initialize_cnf,
+                        cnf_dmv.inner_sent,
+                        corpus_size=20)
+
+    import loc_h_dmv
+    print "\ntrying reestimate v.1 ##############################"
+    g = test_likelihood(loc_h_dmv.reestimate,
+                        initialize_loc_h,
+                        loc_h_dmv.inner_sent,
+                        corpus_size=20)
+    print "\ntrying reestimate v.2 ##############################"
+    g = test_likelihood(loc_h_dmv.reestimate2,
+                        initialize_loc_h,
+                        loc_h_dmv.inner_sent,
+                        corpus_size=20)
+
     print "main.py: done"
diff --git a/tex/compile.sh.~1~ b/tex/compile.sh.~1~
deleted file mode 100755 (executable)
index 8a2dfd9..0000000
+++ /dev/null
@@ -1,2 +0,0 @@
-#!/bin/sh
-latex DMVCCM && pdflatex DMVCCM && open DMVCCM.pdf
dissimilarity index 82%
index fe1901c..0ead8c7 100644 (file)
Binary files a/tex/formulas.pdf and b/tex/formulas.pdf differ
index b97c277..df1dfcc 100644 (file)
Binary files a/tex/formulas.skim and b/tex/formulas.skim differ
index 20607c9..740ee3e 100644 (file)
 
 \title{DMV formulas}
 \author{Kevin Brubeck Unhammer}
-\date{2 July 2008}
+\date{21 August 2008}
 
 \begin{document}
 
 \maketitle
+
+This is an attempt at fleshing out the details of the inside-outside
+algorithm \citep{lari-csl90} applied to the DMV model of
+\citet{klein-thesis}.
+
 \tableofcontents
 
+\newcommand{\LOC}[1]{\textbf{#1}}
 \newcommand{\GOR}[1]{\overrightarrow{#1}}
 \newcommand{\RGOL}[1]{\overleftarrow{\overrightarrow{#1}}}
 \newcommand{\SEAL}[1]{\overline{#1}}
 \newcommand{\GOL}[1]{\overleftarrow{#1}}
 \newcommand{\LN}[1]{\underleftarrow{#1}}
 \newcommand{\RN}[1]{\underrightarrow{#1}}
+\newcommand{\XI}{\lessdot}
+\newcommand{\XJ}{\gtrdot}
+\newcommand{\SMTR}[1]{\dddot{#1}}
+\newcommand{\SDTR}[1]{\ddot{#1}}
 
 \section{Note on notation}
 $i, j, k$ are sentence positions (between words), where $i$ and $j$
 are always the start and end, respectively, for what we're calculating
 ($k$ is between $i$ and $j$ for $P_{INSIDE}$, to their right or left
-for $P_{OUTSIDE}$). $s \in S$ are sentences in the corpus. $w$ is a
-word at a certain sentence location. If $w$ is between $i$ and $i+1$,
-$loc(w)=i$ following \citet{klein-thesis}, meaning $i$ is adjacent to
-$w$ on the left, while $j=loc(w)+1$ means that $j$ is adjacent to $h$
-on the right. To simplify, $loc_l(w):=loc(w)$ and
-$loc_r(w):=loc(w)+1$. We write $h$ if this is a
-head in the rule being used, $a$ if it is an attached argument.
+for $P_{OUTSIDE}$). $s \in S$ are sentences in the corpus. $\LOC{w}$
+is a word token (actually POS-token) of type $w$ at a certain sentence
+location. If $\LOC{w}$ is between $i$ and $i+1$, $loc(\LOC{w})=i$
+following \citet{klein-thesis}, meaning $i$ is adjacent to $\LOC{w}$
+on the left, while $j=loc(\LOC{w})+1$ means that $j$ is adjacent to
+$\LOC{w}$ on the right. To simplify, $loc_l(\LOC{w}):=loc(\LOC{w})$ and
+$loc_r(\LOC{w}):=loc(\LOC{w})+1$. We write $\LOC{h}$ if this is a head
+in the rule being used, $\LOC{a}$ if it is an attached argument.
 
 Notational differences between the thesis \citep{klein-thesis} and the
 paper \citep{km-dmv}:
@@ -60,17 +71,17 @@ $w\urcorner$ & $\RGOL{w}$ \\
 $\ulcorner{w}\urcorner$ & $\SEAL{w}$ \\
 \end{tabular}
 
-$x$ can mean $w, \GOR{w}, \RGOL{w}$ or $\SEAL{w}$\footnote{This means
-  that in the implementation, each such $x$ is represented by the
-  triplet of the actual POS-tag, its sentence location, and the
-  ``level of seals''.}.
+I use $\SMTR{w}$ (or $\SDTR{w}$) to signify one of either $w, \GOR{w},
+\RGOL{w}, \LGOR{w}, \GOL{w}$ or $\SEAL{w}$\footnote{This means that
+  $\SMTR{\LOC{w}}$ is the triplet of the actual POS-tag, its sentence
+  location as a token, and the ``level of seals''.}.
 
 
 \section{Inside probabilities} 
 $P_{INSIDE}$ is defined in \citet[pp.~106-108]{klein-thesis}, the only
 thing we need to add is that for right attachments,
-$i \leq loc_l(w)<k \leq loc_l(a)<j$ while for left attachments,
-$i \leq loc_l(a)<k \leq loc_l(w)<j$. 
+$i \leq loc_l(w)<k \leq loc_l(\LOC{a})<j$ while for left attachments,
+$i \leq loc_l(\LOC{a})<k \leq loc_l(w)<j$. 
 
 (For now, let
 \[ \forall{w}[P_{ORDER}(right\text{-}first|w)=1.0] \] since the DMV implementation
@@ -86,7 +97,7 @@ $P_s$ is the sentence probability, based on
 \citet[p.~38]{lari-csl90}. Since the ROOT rules are different from the
 rest, we sum them explicitly in this definition:
 \begin{align*}
-  P_s = \sum_{w \in s} P_{ROOT}(w) P_{INSIDE}(\SEAL{w}, 0, len(s))
+  P_s = \sum_{\LOC{w} \in s} P_{ROOT}(\LOC{w}) P_{INSIDE}(\SEAL{\LOC{w}}, 0, len(s))
 \end{align*} 
 
 \section{Outside probabilities}
@@ -101,54 +112,55 @@ rest, we sum them explicitly in this definition:
 For $P_{OUTSIDE}(\SEAL{w}, i, j)$, $w$ is attached to under something
 else ($\SEAL{w}$ is what we elsewhere call $\SEAL{a}$). Adjacency is
 thus calculated on the basis of $h$, the head of the rule. If we are
-attached to from the left we have $i \leq  loc_l(w) < j \leq  loc_l(h) < k$, while
-from the right we have $k \leq  loc_l(h) < i \leq  loc_l(w) < j$:
+attached to from the left we have $i \leq  loc_l(\LOC{w}) < j \leq  loc_l(\LOC{h}) < k$, while
+from the right we have $k \leq  loc_l(\LOC{h}) < i \leq  loc_l(\LOC{w}) < j$:
 \begin{align*}
-  P_{OUTSIDE}&(\SEAL{w}, i, j) = \\
+  P_{OUTSIDE}&(\SEAL{\LOC{w}}, i, j) = \\
   & P_{ROOT}(w) P_{OUTSIDE}(ROOT, i, j) + \\
-  & [ \sum_{k > j} ~ \sum_{h:j\leq loc_l(h)<k} \sum_{x \in \{\RGOL{h},\GOL{h}\}} P_{STOP}(\neg stop|h, left,  adj(j, h)) P_{ATTACH}(w|h, left) \\
-  & \qquad \qquad \qquad \qquad \qquad P_{OUTSIDE}(x, i, k) P_{INSIDE}(x, j, k) ] ~ + \\
-  & [ \sum_{k < i} ~ \sum_{h:k\leq loc_l(h)<i} \sum_{x \in \{\LGOR{h},\GOR{h}\}} P_{STOP}(\neg stop|h, right, adj(i, h)) P_{ATTACH}(w|h, right) \\
-  & \qquad \qquad \qquad \qquad \qquad P_{INSIDE}(x, k, i) P_{OUTSIDE}(x, k, j) ] 
+  & [ \sum_{k > j} ~ \sum_{\LOC{h}:j\leq loc_l(\LOC{h})<k} \sum_{\SMTR{\LOC{h}} \in \{\RGOL{\LOC{h}},\GOL{\LOC{h}}\}} P_{STOP}(\neg stop|h, left,  adj(j, \LOC{h})) P_{ATTACH}(w|h, left) \\
+  & \qquad \qquad \qquad \qquad \qquad P_{OUTSIDE}(\SMTR{\LOC{h}}, i, k) P_{INSIDE}(\SMTR{\LOC{h}}, j, k) ] ~ + \\
+  & [ \sum_{k < i} ~ \sum_{\LOC{h}:k\leq loc_l(\LOC{h})<i} \sum_{\SMTR{\LOC{h}} \in \{\LGOR{\LOC{h}},\GOR{\LOC{h}}\}} P_{STOP}(\neg stop|h, right, adj(i, \LOC{h})) P_{ATTACH}(w|h, right) \\
+  & \qquad \qquad \qquad \qquad \qquad P_{INSIDE}(\SMTR{\LOC{h}}, k, i) P_{OUTSIDE}(\SMTR{\LOC{h}}, k, j) ] 
 \end{align*}
 
 For $\RGOL{w}$ we know it is either under a left stop rule or it is
-the right daughter of a left attachment rule ($k \leq  loc_l(a) < i \leq  loc_l(w)
-< j$), and these are adjacent if the start point ($i$) equals
-$loc_l(w)$:
+the right daughter of a left attachment rule ($k \leq loc_l(\LOC{a}) <
+i \leq loc_l(\LOC{w}) < j$), and these are adjacent if the start point
+($i$) equals $loc_l(\LOC{w})$:
 \begin{align*}
-  P_{OUTSIDE}(\RGOL{w}, i, j) = & P_{STOP}(stop|w, left, adj(i,
-  w))P_{OUTSIDE}(\SEAL{w}, i, j) ~ + \\
-  & [ \sum_{k < i} ~ \sum_{a:k\leq loc_l(a)<i} P_{STOP}(\neg stop|w, left, adj(i, w)) P_{ATTACH}(a|w, left) \\
-  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{INSIDE}(\SEAL{a}, k, i) P_{OUTSIDE}(\RGOL{w}, k, j) ]
+  P_{OUTSIDE}(\RGOL{\LOC{w}}, i, j) = & P_{STOP}(stop|w, left, adj(i,
+  \LOC{w}))P_{OUTSIDE}(\SEAL{\LOC{w}}, i, j) ~ + \\
+  & [ \sum_{k < i} ~ \sum_{\LOC{a}:k\leq loc_l(\LOC{a})<i} P_{STOP}(\neg stop|w, left, adj(i, \LOC{w})) P_{ATTACH}(a|w, left) \\
+  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{INSIDE}(\SEAL{\LOC{a}}, k, i) P_{OUTSIDE}(\RGOL{\LOC{w}}, k, j) ]
 \end{align*}
 
 For $\GOR{w}$ we are either under a right stop or the left daughter of
-a right attachment rule ($i \leq  loc_l(w) < j \leq  loc_l(a) < k$), adjacent iff
-the the end point ($j$) equals $loc_r(w)$:
+a right attachment rule ($i \leq loc_l(\LOC{w}) < j \leq
+loc_l(\LOC{a}) < k$), adjacent iff the the end point ($j$) equals
+$loc_r(\LOC{w})$:
 \begin{align*}
-  P_{OUTSIDE}(\GOR{w}, i, j) = & P_{STOP}(stop|w, right, adj(j,
-  w))P_{OUTSIDE}(\RGOL{w}, i, j) ~ + \\
-  & [ \sum_{k > j} ~ \sum_{a:j\leq loc_l(a)<k} P_{STOP}(\neg stop|w, right, adj(j, w)) P_{ATTACH}(a|w, right) \\
-  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{OUTSIDE}(\GOR{w}, i, k) P_{INSIDE}(\SEAL{a}, j, k) ]
+  P_{OUTSIDE}(\GOR{\LOC{w}}, i, j) = & P_{STOP}(stop|w, right, adj(j,
+  \LOC{w}))P_{OUTSIDE}(\RGOL{\LOC{w}}, i, j) ~ + \\
+  & [ \sum_{k > j} ~ \sum_{\LOC{a}:j\leq loc_l(\LOC{a})<k} P_{STOP}(\neg stop|w, right, adj(j, \LOC{w})) P_{ATTACH}(a|w, right) \\
+  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{OUTSIDE}(\GOR{\LOC{w}}, i, k) P_{INSIDE}(\SEAL{\LOC{a}}, j, k) ]
 \end{align*}
 
 $\GOL{w}$ is just like $\RGOL{w}$, except for the outside probability
 of having a stop above, where we use $\LGOR{w}$:
 \begin{align*}
-  P_{OUTSIDE}(\GOL{w}, i, j) = & P_{STOP}(stop|w, left, adj(i,
-  w))P_{OUTSIDE}(\LGOR{w}, i, j) ~ + \\
-  & [ \sum_{k < i} ~ \sum_{a:k\leq loc_l(a)<i} P_{STOP}(\neg stop|w, left, adj(i, w)) P_{ATTACH}(a|w, left) \\
-  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{INSIDE}(\SEAL{a}, k, i) P_{OUTSIDE}(\GOL{w}, k, j) ]
+  P_{OUTSIDE}(\GOL{\LOC{w}}, i, j) = & P_{STOP}(stop|w, left, adj(i,
+  \LOC{w}))P_{OUTSIDE}(\LGOR{\LOC{w}}, i, j) ~ + \\
+  & [ \sum_{k < i} ~ \sum_{\LOC{a}:k\leq loc_l(\LOC{a})<i} P_{STOP}(\neg stop|w, left, adj(i, \LOC{w})) P_{ATTACH}(a|w, left) \\
+  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{INSIDE}(\SEAL{\LOC{a}}, k, i) P_{OUTSIDE}(\GOL{\LOC{w}}, k, j) ]
 \end{align*}
 
 $\LGOR{w}$ is just like $\GOR{w}$, except for the outside probability
 of having a stop above, where we use $\SEAL{w}$:
 \begin{align*}
-  P_{OUTSIDE}(\LGOR{w}, i, j) = & P_{STOP}(stop|w, right, adj(j,
-  w))P_{OUTSIDE}(\SEAL{w}, i, j) ~ + \\
-  & [ \sum_{k > j} ~ \sum_{a:j\leq loc_l(a)<k} P_{STOP}(\neg stop|w, right, adj(j, w)) P_{ATTACH}(a|w, right) \\
-  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{OUTSIDE}(\LGOR{w}, i, k) P_{INSIDE}(\SEAL{a}, j, k) ]
+  P_{OUTSIDE}(\LGOR{\LOC{w}}, i, j) = & P_{STOP}(stop|w, right, adj(j,
+  \LOC{w}))P_{OUTSIDE}(\SEAL{\LOC{w}}, i, j) ~ + \\
+  & [ \sum_{k > j} ~ \sum_{\LOC{a}:j\leq loc_l(\LOC{a})<k} P_{STOP}(\neg stop|w, right, adj(j, \LOC{w})) P_{ATTACH}(a|w, right) \\
+  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{OUTSIDE}(\LGOR{\LOC{w}}, i, k) P_{INSIDE}(\SEAL{\LOC{a}}, j, k) ]
 \end{align*}
 
 
@@ -158,29 +170,26 @@ of having a stop above, where we use $\SEAL{w}$:
 % todo: left out rule-probability! wops (also, make P_{fooside}
 % sentence-specific)
 
-$c_s(x : i, j)$ is ``the expected fraction of parses of $s$ with a
-node labeled $x$ extending from position $i$ to position $j$''
+$c_s(\SMTR{\LOC{w}} : i, j)$ is ``the expected fraction of parses of $s$ with a
+node labeled $\SMTR{w}$ extending from position $i$ to position $j$''
 \citep[p.~88]{klein-thesis}, here defined to equal $v_{q}$ of
 \citet[p.~41]{lari-csl90}:
 \begin{align*}
-  c_s(x : i, j) = P_{INSIDE_s}(x, i, j) P_{OUTSIDE_s}(x, i, j) / P_s
+  c_s(\SMTR{\LOC{w}} : i, j) = P_{INSIDE_s}(\SMTR{\LOC{w}}, i, j) P_{OUTSIDE_s}(\SMTR{\LOC{w}}, i, j) / P_s
 \end{align*}
 
-$w_s$ is $w_{q}$ from \citet[p.~41]{lari-csl90}, generalized to $x$
-\footnote{$x$ here includes a ``level of seals'', to look up the
-  $P_{STOP}$ and $P_{CHOOSE}$ formulas we of course only need the POS
-  of $x$.}  and $dir$:
+$w_s$ is $w_{q}$ from \citet[p.~41]{lari-csl90}, generalized to $\SMTR{h}$ and $dir$:
 \begin{align*}
-  w_s(\SEAL{a} & : x, left, i, j) = \\
-  & 1/P_s \sum_{k:i<k<j} ~ \sum_{a:i\leq loc_l(a)<k} 
-          & P_{STOP}(\neg stop|x, left, adj(k, x)) P_{CHOOSE}(a|x, left) \\
-  &       & P_{INSIDE_s}(\SEAL{a}, i, k) P_{INSIDE_s}(x, k, j) P_{OUTSIDE_s}(x, i, j) 
+  w_s(\SEAL{a} & : \SMTR{\LOC{h}}, left, i, j) = \\
+  & 1/P_s \sum_{k:i<k<j} ~ \sum_{\LOC{a}:i\leq loc_l(\LOC{a})<k} 
+          & P_{STOP}(\neg stop|h, left, adj(k, \SMTR{\LOC{h}})) P_{CHOOSE}(a|h, left) \\
+  &       & P_{INSIDE_s}(\SEAL{\LOC{a}}, i, k) P_{INSIDE_s}(\SMTR{\LOC{h}}, k, j) P_{OUTSIDE_s}(\SMTR{\LOC{h}}, i, j) 
 \end{align*}
 \begin{align*}
-  w_s(\SEAL{a} & : x, right,  i, j) = \\
-  & 1/P_s \sum_{k:i<k<j} ~ \sum_{a:k\leq loc_l(a)<j} 
-          & P_{STOP}(\neg stop|x, right, adj(k, x)) P_{CHOOSE}(a|x, right) \\
-  &       & P_{INSIDE_s}(x, i, k) P_{INSIDE_s}(\SEAL{a}, k, j) P_{OUTSIDE_s}(x, i, j) 
+  w_s(\SEAL{a} & : \SMTR{\LOC{h}}, right,  i, j) = \\
+  & 1/P_s \sum_{k:i<k<j} ~ \sum_{\LOC{a}:k\leq loc_l(\LOC{a})<j} 
+          & P_{STOP}(\neg stop|h, right, adj(k, \SMTR{\LOC{h}})) P_{CHOOSE}(a|h, right) \\
+  &       & P_{INSIDE_s}(\SMTR{\LOC{h}}, i, k) P_{INSIDE_s}(\SEAL{\LOC{a}}, k, j) P_{OUTSIDE_s}(\SMTR{\LOC{h}}, i, j) 
 \end{align*}
 
 Let $\hat{P}$ be the new STOP/CHOOSE-probabilities (since the old $P$
@@ -188,23 +197,23 @@ are used in $P_{INSIDE}$ and $P_{OUTSIDE}$).
 
 \subsection{Attachment reestimation} 
 
-$\hat{a}$ is given in \citet[p.~41]{lari-csl90}. Here $i<loc_l(h)$
+$\hat{a}$ is given in \citet[p.~41]{lari-csl90}. Here $i<loc_l(\LOC{h})$
 since we want trees with at least one attachment:
 \begin{align*}
-  \hat{a} (a | x, left) =  \frac
-  { \sum_{s \in S} \sum_{h \in s} \sum_{i<loc_l(h)} \sum_{j\geq loc_r(h)} w_s(\SEAL{a} : x, left, i, j) }
-  { \sum_{s \in S} \sum_{h \in s} \sum_{i<loc_l(h)} \sum_{j\geq loc_r(h)} c_s(x : i, j) }
+  \hat{a} (a | \SMTR{h}, left) =  \frac
+  { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i<loc_l(\LOC{h})} \sum_{j\geq loc_r(\LOC{h})} w_s(\SEAL{a} : \SMTR{\LOC{h}}, left, i, j) }
+  { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i<loc_l(\LOC{h})} \sum_{j\geq loc_r(\LOC{h})} c_s(\SMTR{\LOC{h}} : i, j) }
 \end{align*}
 
-Here $j>loc_r(h)$ since we want at least one attachment:
+Here $j>loc_r(\SMTR{\LOC{h}})$ since we want at least one attachment:
 \begin{align*}
-  \hat{a} (a | x, right) = \frac
-  { \sum_{s \in S} \sum_{h \in s} \sum_{i\leq loc_l(h)} \sum_{j>loc_r(h)} w_s(\SEAL{a} : x, right, i, j) }
-  { \sum_{s \in S} \sum_{h \in s} \sum_{i\leq loc_l(h)} \sum_{j>loc_r(h)} c_s(x : i, j) }
+  \hat{a} (a | \SMTR{h}, right) = \frac
+  { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i\leq loc_l(\LOC{h})} \sum_{j>loc_r(\LOC{h})} w_s(\SEAL{a} : \SMTR{\LOC{h}}, right, i, j) }
+  { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i\leq loc_l(\LOC{h})} \sum_{j>loc_r(\LOC{h})} c_s(\SMTR{\LOC{h}} : i, j) }
 \end{align*}
 
-For the first/lowest attachments, $w$ and $c$ have zero probability
-where $i<loc_l(h)$ (for $\GOR{h}$) or $j>loc_r(h)$ (for $\GOL{h}$),
+For the first/lowest attachments, $w_s$ and $c_s$ have zero probability
+where $i<loc_l(\LOC{h})$ (for $\GOR{h}$) or $j>loc_r(\LOC{h})$ (for $\GOL{h}$),
 this is implicit in $P_{INSIDE}$.
 
 
@@ -230,65 +239,39 @@ this is implicit in $P_{INSIDE}$.
 
 \subsection{Stop reestimation} 
 The following is based on \citet[p.~88]{klein-thesis}. For the
-non-adjacent rules, $i<loc_l(h)$ on the left and $j>loc_r(h)$ on the
+non-adjacent rules, $i<loc_l(\LOC{h})$ on the left and $j>loc_r(\LOC{h})$ on the
 right, while for the adjacent rules these are equal (respectively).
 
 To avoid some redundancy below, define a helper function $\hat{d}$ as follows:
 \begin{align*}
-  \hat{d}(x,left,non\text{-}adj) = { \sum_{s \in S} \sum_{h \in s} \sum_{i<loc_l(h)} \sum_{j\geq loc_r(h)} c_s(x : i,       j) }
-\end{align*}
-\begin{align*}
-  \hat{d}(x,left,           adj) = { \sum_{s \in S} \sum_{h \in s}                 \sum_{j\geq loc_r(h)} c_s(x : loc_l(h), j) }
-\end{align*}
-\begin{align*}
-  \hat{d}(x,right,non\text{-}adj) = { \sum_{s \in S} \sum_{h \in s} \sum_{i\leq loc_l(h)} \sum_{j> loc_r(h)} c_s(x : i,      j) }
-\end{align*}
-\begin{align*}
-  \hat{d}(x,right,           adj) = { \sum_{s \in S} \sum_{h \in s} \sum_{i\leq loc_l(h)}                  c_s(x : i,      loc_r(h)) }
+  \hat{d}(\SMTR{h},\SDTR{h},\XI,\XJ) = \frac
+  { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i:i \XI loc_l(\LOC{h})} \sum_{j:j \XJ loc_r(\LOC{h})} c_s(\SMTR{\LOC{h}} : i, j) }
+  { \sum_{s \in S} \sum_{\SDTR{\LOC{h}}:\LOC{h} \in s} \sum_{i:i \XI loc_l(\LOC{h})} \sum_{j:j \XJ loc_r(\LOC{h})} c_s(\SDTR{\LOC{h}} : i, j) }
 \end{align*}
 
+Then these are our reestimated stop probabilities:
 \begin{align*}
   \hat{P}_{STOP} (STOP|h, left, non\text{-}adj) =
-  \frac
-  { \hat{d}(\SEAL{h},left,non\text{-}adj) }
-  { \hat{d}(\RGOL{h},left,non\text{-}adj) } 
-  +
-  \frac
-  { \hat{d}(\LGOR{h},left,non\text{-}adj) }
-  { \hat{d}(\GOL{h},left,non\text{-}adj) }
+  \hat{d}(\SEAL{h}, \RGOL{h},<,\geq)  +
+  \hat{d}(\LGOR{h}, \GOL{h},<,=)
 \end{align*}
 
 \begin{align*}
-  \hat{P}_{STOP} (STOP|h, left, adj) = 
-  \frac
-  { \hat{d}(\SEAL{h},left,adj) }
-  { \hat{d}(\RGOL{h},left,adj) }
-  +
-  \frac
-  { \hat{d}(\LGOR{h},left,adj) }
-  { \hat{d}(\GOL{h},left,adj) } 
+  \hat{P}_{STOP} (STOP|h, left, adj) =
+  \hat{d}(\SEAL{h}, \RGOL{h},=,\geq)  +
+  \hat{d}(\LGOR{h}, \GOL{h},=,=)
 \end{align*}
 
 \begin{align*}
-  \hat{P}_{STOP} (STOP|h, right, non\text{-}adj) = 
-  \frac
-  { \hat{d}(\RGOL{h},right,non\text{-}adj) }
-  { \hat{d}(\GOR{h},right,non\text{-}adj) }
-  +
-  \frac
-  { \hat{d}(\SEAL{h},right,non\text{-}adj) }
-  { \hat{d}(\LGOR{h},right,non\text{-}adj) } 
+  \hat{P}_{STOP} (STOP|h, right, non\text{-}adj) =
+  \hat{d}(\RGOL{h}, \GOR{h},=,>)  +
+  \hat{d}(\SEAL{h}, \LGOR{h},\leq,>)
 \end{align*}
 
 \begin{align*}
-  \hat{P}_{STOP} (STOP|h, right, adj) = 
-  \frac
-  { \hat{d}(\RGOL{h},right,adj) }
-  { \hat{d}(\GOR{h},right,adj) }
-  +
-  \frac
-  { \hat{d}(\SEAL{h},right,adj) }
-  { \hat{d}(\LGOR{h},right,adj) } 
+  \hat{P}_{STOP} (STOP|h, right, adj) =
+  \hat{d}(\RGOL{h}, \GOR{h},=,=)  +
+  \hat{d}(\SEAL{h}, \LGOR{h},\leq,=)
 \end{align*}
 
 
@@ -340,10 +323,10 @@ not yet generalized to include left-first attachment.
 The inside probabilities are the same as those given in
 \citet{lari-csl90}, with the following exceptions:
 
-When calculating $P_{INSIDE}(x, i, j)$ and summing through possible
-rules which rewrite $x$, if a rule is of the form $x \rightarrow
-STOP ~ x'$ or $x \rightarrow x' ~ STOP$, we add $P_{RULE}\cdot
-P_{INSIDE}(x', i, j)$ (that is, rewrite for the same sentence range);
+When calculating $P_{INSIDE}(\SMTR{h}, i, j)$ and summing through possible
+rules which rewrite $\SMTR{h}$, if a rule is of the form $\SMTR{h} \rightarrow
+STOP ~ \SDTR{h}$ or $\SMTR{h} \rightarrow \SDTR{h} ~ STOP$, we add $P_{RULE}\cdot
+P_{INSIDE}(\SDTR{h}, i, j)$ (that is, rewrite for the same sentence range);
 and, as a consequence of these unary rules: for ``terminal rules''
 ($P_{ORDER}$) to be applicable, not only must $i = j-1$, but also the
 left-hand side symbol of the rule must be of the form $\GOR{h}$.
@@ -352,21 +335,21 @@ Similarly, the outside probabilities are the same as those for pure
 CNF rules, with the exception that we add the unary rewrite
 probabilities
 \begin{align*}
-  \sum_{x'} [&P_{OUTSIDE}(x,i,j)\cdot P_{RULE}(x' \rightarrow x ~ STOP) \\
-          + &P_{OUTSIDE}(x,i,j)\cdot P_{RULE}(x' \rightarrow STOP ~ x)]
+  \sum_{\SMTR{h}} [&P_{OUTSIDE}(\SMTR{h},i,j)\cdot P_{RULE}(\SMTR{h} \rightarrow \SDTR{h} ~ STOP) \\
+          + &P_{OUTSIDE}(\SMTR{h},i,j)\cdot P_{RULE}(\SMTR{h} \rightarrow STOP ~ \SDTR{h})]
 \end{align*}
-to $P_{OUTSIDE}(x,i,j)$ (eg. $f(s,t,i)$).
+to $P_{OUTSIDE}(\SDTR{h},i,j)$ (eg. $f(s,t,i)$).
 
 The reestimation just needs to be expanded to allow unary stop rules,
 this is similar to the formula for binary rules in
 \citet[p.~41]{lari-csl90}:
 \begin{align*}
-  \hat{P}_{RULE}(x' \rightarrow x) = \frac
-  { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} 1/P_s \cdot P_{RULE}(x'\rightarrow x)P_{INSIDE}(x, i, j)P_{OUTSIDE}(x', i, j) }
-  { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} c_s(x', i, j) }
+  \hat{P}_{RULE}(\SMTR{h} \rightarrow \SDTR{h}) = \frac
+  { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} 1/P_s \cdot P_{RULE}(\SMTR{h}\rightarrow \SDTR{h})P_{INSIDE}(\SDTR{h}, i, j)P_{OUTSIDE}(\SMTR{h}, i, j) }
+  { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} c_s(\SMTR{h}, i, j) }
 \end{align*}
 (the denominator is unchanged, but the numerator sums $w_s$ defined
-for unary rules; $x'\rightarrow x$ is meant to include both left and
+for unary rules; $\SMTR{h}\rightarrow \SDTR{h}$ is meant to include both left and
 right stop rules).
 
 % todo: add ROOT rule to CNF grammar?