fixed a little bug in root reestimation (forgot to divide by len(corpus)=f_T_q(ROOT))
authorKevin Brubeck Unhammer <pixiemotion@gmail.com>
Thu, 18 Sep 2008 09:05:31 +0000 (18 11:05 +0200)
committerKevin Brubeck Unhammer <pixiemotion@gmail.com>
Thu, 18 Sep 2008 09:05:31 +0000 (18 11:05 +0200)
15 files changed:
DMVCCM.html
DMVCCM.org
report/compile.sh [new file with mode: 0755]
report/getbib.sh [new file with mode: 0755]
report/report.pdf [new file with mode: 0644]
report/report.tex [copied from tex/formulas.tex with 61% similarity]
report/statistical.bib [new file with mode: 0644]
src/cnf_dmv.py
src/loc_h_dmv.py
src/loc_h_dmv.pyc
src/loc_h_harmonic.py
src/main.py
src/wsjdep.py
tex/formulas.pdf
tex/formulas.tex

index 9f31d4b..d03cf89 100755 (executable)
@@ -6,7 +6,7 @@ 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-29 15:41:07 CEST"/>
+<meta name="generated" content="2008-09-11 12:01:19 CEST"/>
 <meta name="author" content="Kevin Brubeck Unhammer"/>
 <style type="text/css">
   html { font-family: Times, serif; font-size: 12pt; }
@@ -45,27 +45,27 @@ lang="en" xml:lang="en">
 <li><a href="#sec-3.1">3.1 [#A] Should <code>def evaluate</code> use add_root?</a></li>
 </ul>
 </li>
-<li><a href="#sec-4">4 [#C] Alternative CNF for DMV</a>
+<li><a href="#sec-4">4 Combine CCM with DMV</a></li>
+<li><a href="#sec-5">5 Reestimate P_ORDER ?</a></li>
+<li><a href="#sec-6">6 Most Probable Parse</a>
 <ul>
-<li><a href="#sec-4.1">4.1 [#A] Make and implement an equivalent grammar that's <i>pure</i> 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>
+<li><a href="#sec-6.1">6.1 Find MPP with CCM</a></li>
+<li><a href="#sec-6.2">6.2 Find Most Probable Parse of given test sentence, in DMV</a></li>
 </ul>
 </li>
-<li><a href="#sec-5">5 Combine CCM with DMV</a></li>
-<li><a href="#sec-6">6 Reestimate P_ORDER ?</a></li>
-<li><a href="#sec-7">7 Most Probable Parse</a>
+<li><a href="#sec-7">7 Initialization   </a>
 <ul>
-<li><a href="#sec-7.1">7.1 Find MPP with CCM</a></li>
-<li><a href="#sec-7.2">7.2 Find Most Probable Parse of given test sentence, in DMV</a></li>
+<li><a href="#sec-7.1">7.1 CCM Initialization    </a></li>
 </ul>
 </li>
-<li><a href="#sec-8">8 Initialization   </a>
+<li><a href="#sec-8">8 [#C] Alternative CNF for DMV</a>
 <ul>
-<li><a href="#sec-8.1">8.1 CCM Initialization    </a></li>
+<li><a href="#sec-8.1">8.1 [#A] Make and implement an equivalent grammar that's <i>pure</i> CNF</a></li>
+<li><a href="#sec-8.2">8.2 [#A] convert L&amp;Y-based reestimation into P_ATTACH and P_STOP values</a></li>
+<li><a href="#sec-8.3">8.3 [#C] move as much as possible into common_dmv.py</a></li>
+<li><a href="#sec-8.4">8.4 L&amp;Y-based reestimation for cnf_dmv</a></li>
+<li><a href="#sec-8.5">8.5 dmv2cnf re-estimation formulas</a></li>
+<li><a href="#sec-8.6">8.6 inner and outer for cnf_dmv.py, also cnf_harmonic.py </a></li>
 </ul>
 </li>
 <li><a href="#sec-9">9 [#C] Deferred</a>
@@ -94,7 +94,8 @@ lang="en" xml:lang="en">
 <h2 id="sec-1">1 DMV/CCM report and project</h2>
 <div id="text-1">
 
-<ul>
+<p><span class="timestamp-kwd">DEADLINE: </span> <span class="timestamp">2008-09-21 Sun</span><br/>
+</p><ul>
 <li>
 DMV-<a href="tex/formulas.pdf">formulas.pdf</a>  &ndash; <i>clear</i> information =D
 </li>
@@ -197,11 +198,120 @@ Only <code>sents()</code>, <code>tagged_sents()</code> and <code>parsed_sents()<
 </div>
 
 <div id="outline-container-4" class="outline-2">
-<h2 id="sec-4">4 <span class="todo">TODO</span> [#C] Alternative CNF for DMV</h2>
+<h2 id="sec-4">4 <span class="todo">TOGROK</span> Combine CCM with DMV</h2>
 <div id="text-4">
 
 
 <p>
+<a name="comboquestions">&nbsp;</a>
+</p>
+<p>
+Questions about the <code>P_COMBO</code> info in <a href="http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf">Klein's thesis</a>:
+</p><ul>
+<li>
+Page 109 (pdf: 125): We have to premultiply "all our probabilities"
+by the CCM base product <i>&Pi;<sub>&lt;i,j&gt;</sub>   P<sub>SPAN</sub>(&alpha;(i,j,s)|false)P<sub>CONTEXT</sub>(&beta;(i,j,s)|false)</i>; which
+probabilities are included under "all"? I'm assuming this includes
+<code>P_ATTACH</code> since each time <code>P_ATTACH</code> is used, <i>&phi;</i> is multiplied in
+(pp.110-111 ibid.); but <i>&phi;</i> is not used for STOPs, so should we not
+have our CCM product multiplied in there? How about <code>P_ROOT</code>?
+(Guessing <code>P_ORDER</code> is way out of the question&hellip;)
+</li>
+<li>
+For the outside probabilities, is it correct to assume we multiply
+in <i>&phi;(j,k)</i> or <i>&phi;(k,i)</i> when calculating <code>inner(i,j...)</code>? (Eg., only
+for the outside part, not for the whole range.) I don't understand
+the notation in <code>O()</code> on p.103.
+</li>
+</ul>
+</div>
+
+</div>
+
+<div id="outline-container-5" class="outline-2">
+<h2 id="sec-5">5 <span class="todo">TOGROK</span> Reestimate P_ORDER ?</h2>
+<div id="text-5">
+
+</div>
+
+</div>
+
+<div id="outline-container-6" class="outline-2">
+<h2 id="sec-6">6 Most Probable Parse</h2>
+<div id="text-6">
+
+
+</div>
+
+<div id="outline-container-6.1" class="outline-3">
+<h3 id="sec-6.1">6.1 <span class="todo">TOGROK</span> Find MPP with CCM</h3>
+<div id="text-6.1">
+
+</div>
+
+</div>
+
+<div id="outline-container-6.2" class="outline-3">
+<h3 id="sec-6.2">6.2 <span class="done">DONE</span> Find Most Probable Parse of given test sentence, in DMV</h3>
+<div id="text-6.2">
+
+<p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-07-23 Wed 10:56</span><br/>
+inner() optionally keeps track of the highest probability children of
+any node in <code>mpptree</code>. Say we're looking for <code>inner(i,j,(s_h,h),loc_h)</code> in
+a certain sentence, and we find some possible left and right children,
+we add to <code>mpptree[i,j,(s_h,h),loc_h]</code> the triple <code>(p, L, R)</code> where <code>L</code> and
+<code>R</code> are of the same form as the key (<code>i,j,(s_h,h),loc_h</code>) and <code>p</code> is the
+probability of this node rewriting to <code>L</code> and <code>R</code>,
+eg. <code>inner(L)*inner(R)*p_GO_AT</code> or <code>p_STOP</code> or whatever. We only add this
+entry to <code>mpptree</code> if there wasn't a higher-probability entry there
+before.
+</p>
+<p>
+Then, after <code>inner_sent</code> makes an <code>mpptree</code>, we find the <i>relevant</i>
+head-argument pairs by searching through the tree using a queue,
+adding the <code>L</code> and <code>R</code> keys of any entry to the queue as we find them
+(skipping <code>STOP</code> keys), and adding any attachment entries to a set of
+triples <code>(head,argument,dir)</code>. Thus we have our most probable parse,
+eg.
+<pre class="example">
+ set([( ROOT, (vbd,2),RIGHT),
+      ((vbd,2),(nn,1),LEFT),
+      ((vbd,2),(nn,3),RIGHT),
+      ((nn,1),(det,0),LEFT)])
+</pre>
+</p></div>
+</div>
+
+</div>
+
+<div id="outline-container-7" class="outline-2">
+<h2 id="sec-7">7 Initialization   </h2>
+<div id="text-7">
+
+<p><a href="/Users/kiwibird/Documents/Skole/V08/Probability/dmvccm/src/dmv.py">dmv-inits</a>
+</p>
+<p>
+We go through the corpus, since the probabilities are based on how far
+away in the sentence arguments are from their heads.
+</p>
+</div>
+
+<div id="outline-container-7.1" class="outline-3">
+<h3 id="sec-7.1">7.1 <span class="todo">TOGROK</span> CCM Initialization    </h3>
+<div id="text-7.1">
+
+<p>P<sub>SPLIT</sub> used here&hellip; how, again?
+</p></div>
+</div>
+
+</div>
+
+<div id="outline-container-8" class="outline-2">
+<h2 id="sec-8">8 <span class="todo">TODO</span> [#C] Alternative CNF for DMV</h2>
+<div id="text-8">
+
+
+<p>
 <a name="dmv2cnf">&nbsp;</a>
 </p><ul>
 <li>
@@ -233,9 +343,9 @@ ROOT  --&gt; STOP   _h_   [1.00]
 
 </div>
 
-<div id="outline-container-4.1" class="outline-3">
-<h3 id="sec-4.1">4.1 <span class="todo">TODO</span> [#A] Make and implement an equivalent grammar that's <i>pure</i> CNF</h3>
-<div id="text-4.1">
+<div id="outline-container-8.1" class="outline-3">
+<h3 id="sec-8.1">8.1 <span class="todo">TODO</span> [#A] Make and implement an equivalent grammar that's <i>pure</i> CNF</h3>
+<div id="text-8.1">
 
 <p>&hellip;since I'm not sure about my unary reestimation rules (section 5 of
 <a href="tex/formulas.pdf">formulas</a>).
@@ -296,160 +406,51 @@ numbering more than n<sub>tags</sub><sup>2</sup>.
 
 </div>
 
-<div id="outline-container-4.2" class="outline-3">
-<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 id="outline-container-8.2" class="outline-3">
+<h3 id="sec-8.2">8.2 <span class="todo">TOGROK</span> [#A] convert L&amp;Y-based reestimation into P_ATTACH and P_STOP values</h3>
+<div id="text-8.2">
 
 <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> [#C] move as much as possible into common_dmv.py</h3>
-<div id="text-4.3">
+<div id="outline-container-8.3" class="outline-3">
+<h3 id="sec-8.3">8.3 <span class="todo">TODO</span> [#C] move as much as possible into common_dmv.py</h3>
+<div id="text-8.3">
 
 <p><a href="src/common_dmv.py">common_dmv.py</a>
 </p></div>
 
 </div>
 
-<div id="outline-container-4.4" class="outline-3">
-<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">
+<div id="outline-container-8.4" class="outline-3">
+<h3 id="sec-8.4">8.4 <span class="done">DONE</span> L&amp;Y-based reestimation for cnf_dmv</h3>
+<div id="text-8.4">
 
 <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 re-estimation formulas</h3>
-<div id="text-4.5">
+<div id="outline-container-8.5" class="outline-3">
+<h3 id="sec-8.5">8.5 <span class="done">DONE</span> dmv2cnf re-estimation formulas</h3>
+<div id="text-8.5">
 
 <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 id="outline-container-8.6" class="outline-3">
+<h3 id="sec-8.6">8.6 <span class="done">DONE</span> inner and outer for cnf_dmv.py, also cnf_harmonic.py </h3>
+<div id="text-8.6">
 
 </div>
 </div>
 
 </div>
 
-<div id="outline-container-5" class="outline-2">
-<h2 id="sec-5">5 <span class="todo">TOGROK</span> Combine CCM with DMV</h2>
-<div id="text-5">
-
-
-<p>
-<a name="comboquestions">&nbsp;</a>
-</p>
-<p>
-Questions about the <code>P_COMBO</code> info in <a href="http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf">Klein's thesis</a>:
-</p><ul>
-<li>
-Page 109 (pdf: 125): We have to premultiply "all our probabilities"
-by the CCM base product <i>&Pi;<sub>&lt;i,j&gt;</sub>   P<sub>SPAN</sub>(&alpha;(i,j,s)|false)P<sub>CONTEXT</sub>(&beta;(i,j,s)|false)</i>; which
-probabilities are included under "all"? I'm assuming this includes
-<code>P_ATTACH</code> since each time <code>P_ATTACH</code> is used, <i>&phi;</i> is multiplied in
-(pp.110-111 ibid.); but <i>&phi;</i> is not used for STOPs, so should we not
-have our CCM product multiplied in there? How about <code>P_ROOT</code>?
-(Guessing <code>P_ORDER</code> is way out of the question&hellip;)
-</li>
-<li>
-For the outside probabilities, is it correct to assume we multiply
-in <i>&phi;(j,k)</i> or <i>&phi;(k,i)</i> when calculating <code>inner(i,j...)</code>? (Eg., only
-for the outside part, not for the whole range.) I don't understand
-the notation in <code>O()</code> on p.103.
-</li>
-</ul>
-</div>
-
-</div>
-
-<div id="outline-container-6" class="outline-2">
-<h2 id="sec-6">6 <span class="todo">TOGROK</span> Reestimate P_ORDER ?</h2>
-<div id="text-6">
-
-</div>
-
-</div>
-
-<div id="outline-container-7" class="outline-2">
-<h2 id="sec-7">7 Most Probable Parse</h2>
-<div id="text-7">
-
-
-</div>
-
-<div id="outline-container-7.1" class="outline-3">
-<h3 id="sec-7.1">7.1 <span class="todo">TOGROK</span> Find MPP with CCM</h3>
-<div id="text-7.1">
-
-</div>
-
-</div>
-
-<div id="outline-container-7.2" class="outline-3">
-<h3 id="sec-7.2">7.2 <span class="done">DONE</span> Find Most Probable Parse of given test sentence, in DMV</h3>
-<div id="text-7.2">
-
-<p><span class="timestamp-kwd">CLOSED: </span> <span class="timestamp">2008-07-23 Wed 10:56</span><br/>
-inner() optionally keeps track of the highest probability children of
-any node in <code>mpptree</code>. Say we're looking for <code>inner(i,j,(s_h,h),loc_h)</code> in
-a certain sentence, and we find some possible left and right children,
-we add to <code>mpptree[i,j,(s_h,h),loc_h]</code> the triple <code>(p, L, R)</code> where <code>L</code> and
-<code>R</code> are of the same form as the key (<code>i,j,(s_h,h),loc_h</code>) and <code>p</code> is the
-probability of this node rewriting to <code>L</code> and <code>R</code>,
-eg. <code>inner(L)*inner(R)*p_GO_AT</code> or <code>p_STOP</code> or whatever. We only add this
-entry to <code>mpptree</code> if there wasn't a higher-probability entry there
-before.
-</p>
-<p>
-Then, after <code>inner_sent</code> makes an <code>mpptree</code>, we find the <i>relevant</i>
-head-argument pairs by searching through the tree using a queue,
-adding the <code>L</code> and <code>R</code> keys of any entry to the queue as we find them
-(skipping <code>STOP</code> keys), and adding any attachment entries to a set of
-triples <code>(head,argument,dir)</code>. Thus we have our most probable parse,
-eg.
-<pre class="example">
- set([( ROOT, (vbd,2),RIGHT),
-      ((vbd,2),(nn,1),LEFT),
-      ((vbd,2),(nn,3),RIGHT),
-      ((nn,1),(det,0),LEFT)])
-</pre>
-</p></div>
-</div>
-
-</div>
-
-<div id="outline-container-8" class="outline-2">
-<h2 id="sec-8">8 Initialization   </h2>
-<div id="text-8">
-
-<p><a href="/Users/kiwibird/Documents/Skole/V08/Probability/dmvccm/src/dmv.py">dmv-inits</a>
-</p>
-<p>
-We go through the corpus, since the probabilities are based on how far
-away in the sentence arguments are from their heads.
-</p>
-</div>
-
-<div id="outline-container-8.1" class="outline-3">
-<h3 id="sec-8.1">8.1 <span class="todo">TOGROK</span> CCM Initialization    </h3>
-<div id="text-8.1">
-
-<p>P<sub>SPLIT</sub> used here&hellip; how, again?
-</p></div>
-</div>
-
-</div>
-
 <div id="outline-container-9" class="outline-2">
 <h2 id="sec-9">9 [#C] Deferred</h2>
 <div id="text-9">
@@ -698,11 +699,8 @@ 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-29 15:41:07 CEST</p>
-<p>HTML generated by org-mode 6.06b in emacs 22<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">
+<p class="date"> Date: 2008-09-11 12:01:19 CEST</p>
+<p>HTML generert av <a href='http://orgmode.org/'>org-mode</a> 6.06b in emacs 22<p>
+</div><script src="./post-script.js" type="text/JavaScript">
 </script></body>
 </html>
index 15a507d..dc9fdf4 100755 (executable)
 [[file:src/wsjdep.py][wsjdep.py]] 
 [[file:src/loc_h_dmv.py][loc_h_dmv.py]]
 
-Trying out /not/ dividing by sum_hat_a now (in reestimate2), see how
-that goes...
-
 Meta-todo: 
-- 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
+- fix stop and attachment formulas so they divide before summing
+  - both in formulas.tex and in code
+  - and check with other values for P_ORDER
 
 [[file:DMVCCM.html][DMVCCM.html]]
 
 * DMV/CCM report and project
+  DEADLINE: <2008-09-21 Sun>
 - DMV-[[file:tex/formulas.pdf][formulas.pdf]]  -- /clear/ information =D
 - [[file:src/main.py][main.py]] -- evaluation, corpus likelihoods
 - [[file:src/wsjdep.py][wsjdep.py]] -- corpus
@@ -110,6 +107,55 @@ Only =sents()=, =tagged_sents()= and =parsed_sents()= (plus a new function
 [[file:src/wsjdep.py][wsjdep.py]] add_root
 
 (just has to count how many pairs are in there; Precision and Recall)
+* TOGROK Combine CCM with DMV
+
+# <<comboquestions>>
+
+Questions about the =P_COMBO= info in [[http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf][Klein's thesis]]:
+- Page 109 (pdf: 125): We have to premultiply "all our probabilities"
+  by the CCM base product /\Pi_{<i,j>}
+  P_{SPAN}(\alpha(i,j,s)|false)P_{CONTEXT}(\beta(i,j,s)|false)/; which
+  probabilities are included under "all"? I'm assuming this includes
+  =P_ATTACH= since each time =P_ATTACH= is used, /\phi/ is multiplied in
+  (pp.110-111 ibid.); but /\phi/ is not used for STOPs, so should we not
+  have our CCM product multiplied in there? How about =P_ROOT=?
+  (Guessing =P_ORDER= is way out of the question...)
+- For the outside probabilities, is it correct to assume we multiply
+  in /\phi(j,k)/ or /\phi(k,i)/ when calculating =inner(i,j...)=? (Eg., only
+  for the outside part, not for the whole range.) I don't understand
+  the notation in =O()= on p.103.
+* TOGROK Reestimate P_ORDER ?
+* Most Probable Parse
+** TOGROK Find MPP with CCM
+** DONE Find Most Probable Parse of given test sentence, in DMV
+  CLOSED: [2008-07-23 Wed 10:56]
+inner() optionally keeps track of the highest probability children of
+any node in =mpptree=. Say we're looking for =inner(i,j,(s_h,h),loc_h)= in
+a certain sentence, and we find some possible left and right children,
+we add to =mpptree[i,j,(s_h,h),loc_h]= the triple =(p, L, R)= where =L= and
+=R= are of the same form as the key (=i,j,(s_h,h),loc_h=) and =p= is the
+probability of this node rewriting to =L= and =R=,
+eg. =inner(L)*inner(R)*p_GO_AT= or =p_STOP= or whatever. We only add this
+entry to =mpptree= if there wasn't a higher-probability entry there
+before.
+
+Then, after =inner_sent= makes an =mpptree=, we find the /relevant/
+head-argument pairs by searching through the tree using a queue,
+adding the =L= and =R= keys of any entry to the queue as we find them
+(skipping =STOP= keys), and adding any attachment entries to a set of
+triples =(head,argument,dir)=. Thus we have our most probable parse,
+eg.
+: set([( ROOT, (vbd,2),RIGHT),
+:      ((vbd,2),(nn,1),LEFT),
+:      ((vbd,2),(nn,3),RIGHT),
+:      ((nn,1),(det,0),LEFT)])
+* Initialization   
+[[file:~/Documents/Skole/V08/Probability/dmvccm/src/dmv.py::Initialization%20todo][dmv-inits]]
+
+We go through the corpus, since the probabilities are based on how far
+away in the sentence arguments are from their heads.
+** TOGROK CCM Initialization    
+P_{SPLIT} used here... how, again?
 * TODO [#C] Alternative CNF for DMV
 
 # <<dmv2cnf>>
@@ -189,55 +235,6 @@ Sum over the various rules? Or something? Must think of this.
 ** 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
-
-# <<comboquestions>>
-
-Questions about the =P_COMBO= info in [[http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf][Klein's thesis]]:
-- Page 109 (pdf: 125): We have to premultiply "all our probabilities"
-  by the CCM base product /\Pi_{<i,j>}
-  P_{SPAN}(\alpha(i,j,s)|false)P_{CONTEXT}(\beta(i,j,s)|false)/; which
-  probabilities are included under "all"? I'm assuming this includes
-  =P_ATTACH= since each time =P_ATTACH= is used, /\phi/ is multiplied in
-  (pp.110-111 ibid.); but /\phi/ is not used for STOPs, so should we not
-  have our CCM product multiplied in there? How about =P_ROOT=?
-  (Guessing =P_ORDER= is way out of the question...)
-- For the outside probabilities, is it correct to assume we multiply
-  in /\phi(j,k)/ or /\phi(k,i)/ when calculating =inner(i,j...)=? (Eg., only
-  for the outside part, not for the whole range.) I don't understand
-  the notation in =O()= on p.103.
-* TOGROK Reestimate P_ORDER ?
-* Most Probable Parse
-** TOGROK Find MPP with CCM
-** DONE Find Most Probable Parse of given test sentence, in DMV
-  CLOSED: [2008-07-23 Wed 10:56]
-inner() optionally keeps track of the highest probability children of
-any node in =mpptree=. Say we're looking for =inner(i,j,(s_h,h),loc_h)= in
-a certain sentence, and we find some possible left and right children,
-we add to =mpptree[i,j,(s_h,h),loc_h]= the triple =(p, L, R)= where =L= and
-=R= are of the same form as the key (=i,j,(s_h,h),loc_h=) and =p= is the
-probability of this node rewriting to =L= and =R=,
-eg. =inner(L)*inner(R)*p_GO_AT= or =p_STOP= or whatever. We only add this
-entry to =mpptree= if there wasn't a higher-probability entry there
-before.
-
-Then, after =inner_sent= makes an =mpptree=, we find the /relevant/
-head-argument pairs by searching through the tree using a queue,
-adding the =L= and =R= keys of any entry to the queue as we find them
-(skipping =STOP= keys), and adding any attachment entries to a set of
-triples =(head,argument,dir)=. Thus we have our most probable parse,
-eg.
-: set([( ROOT, (vbd,2),RIGHT),
-:      ((vbd,2),(nn,1),LEFT),
-:      ((vbd,2),(nn,3),RIGHT),
-:      ((nn,1),(det,0),LEFT)])
-* Initialization   
-[[file:~/Documents/Skole/V08/Probability/dmvccm/src/dmv.py::Initialization%20todo][dmv-inits]]
-
-We go through the corpus, since the probabilities are based on how far
-away in the sentence arguments are from their heads.
-** TOGROK CCM Initialization    
-P_{SPLIT} used here... how, again?
 * [#C] Deferred
 http://wiki.python.org/moin/PythonSpeed/PerformanceTips Eg., use
 map/reduce/filter/[i for i in [i's]]/(i for i in [i's]) instead of
diff --git a/report/compile.sh b/report/compile.sh
new file mode 100755 (executable)
index 0000000..18413ab
--- /dev/null
@@ -0,0 +1,2 @@
+#!/bin/sh
+/usr/texbin/latex report && /usr/texbin/bibtex report && /usr/texbin/pdflatex report && open report.pdf
diff --git a/report/getbib.sh b/report/getbib.sh
new file mode 100755 (executable)
index 0000000..0d24f43
--- /dev/null
@@ -0,0 +1,3 @@
+#!/bin/sh
+mv statistical.bib statistical.bib$(date +%Y%m%d)
+wget http://bibsonomy.org/bib/user/unhammer/statistical?bibtex.entriesPerPage=100 -O statistical.bib 
diff --git a/report/report.pdf b/report/report.pdf
new file mode 100644 (file)
index 0000000..d5bf696
Binary files /dev/null and b/report/report.pdf differ
similarity index 61%
copy from tex/formulas.tex
copy to report/report.tex
index e8d3c4a..0b02970 100644 (file)
@@ -1,4 +1,5 @@
 % Created 2008-06-13 Fri 17:05
+
 \documentclass[11pt,a4paper]{article}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
 
 \usepackage{array} % for a tabular with math in it
 
-\title{DMV formulas}
-\author{Kevin Brubeck Unhammer}
-\date{21 August 2008}
+\title{The DMV and CCM models}
+\author{Emily Morgan \& Kevin Brubeck Unhammer}
+\date{15 September 2008}
 
 \begin{document}
 
 \maketitle
 
+\tableofcontents
+
+\section{Introduction}
+\section{The Constituent Context Model}
+\subsection{Results}
+\section{A Dependency Model with Valence}
 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}}}
@@ -48,7 +53,7 @@ algorithm \citep{lari-csl90} applied to the DMV model of
 \newcommand{\SMTR}[1]{\dddot{#1}}
 \newcommand{\SDTR}[1]{\ddot{#1}}
 
-\section{Note on notation}
+\subsection{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
@@ -61,8 +66,8 @@ $\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}:
+There are som notational differences between \citet{klein-thesis}
+\citet{km-dmv}:
 
 \begin{tabular}{cc}
 Paper: & Thesis: \\
@@ -71,13 +76,13 @@ $w\urcorner$ & $\RGOL{w}$ \\
 $\ulcorner{w}\urcorner$ & $\SEAL{w}$ \\
 \end{tabular}
 
-I use $\SMTR{w}$ (or $\SDTR{w}$) to signify one of either $w, \GOR{w},
+We 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} 
+\subsection{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(\LOC{a})<j$ while for left attachments,
@@ -91,7 +96,7 @@ is not yet generalized to both directions.)
 
 
 
-\subsection{Sentence probability}
+\subsubsection{Sentence probability}
 
 $P_s$ is the sentence probability, based on 
 \citet[p.~38]{lari-csl90}. Since the ROOT rules are different from the
@@ -100,7 +105,7 @@ rest, we sum them explicitly in this definition:
   P_s = \sum_{\LOC{w} \in s} P_{ROOT}(\LOC{w}) P_{INSIDE}(\SEAL{\LOC{w}}, 0, len(s))
 \end{align*} 
 
-\section{Outside probabilities}
+\subsection{Outside probabilities}
 
 \begin{align*}
   P_{OUTSIDE_s}(ROOT, i, j) = \begin{cases}
@@ -164,16 +169,17 @@ of having a stop above, where we use $\SEAL{w}$:
 \end{align*}
 
 
-\section{Reestimating the rules} % todo
+\subsection{Reestimating the rules} 
+% TODO: fix stop and attachment formulas so they divide before summing
 
-\subsection{$c$ and $w$ (helper formulas used below)}
-% todo: left out rule-probability! wops (also, make P_{fooside}
-% sentence-specific)
-
-$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}:
+\subsubsection{$c$ and $w$ (helper formulas used below)}
+$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}\footnote{In terms of regular EM,
+  this is the count of trees ($f_{T_q}(x)$ in
+  \citet[p.~46]{prescher-em}) in which the node extended from $i$ to
+  $j$.}:
 \begin{align*}
   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*}
@@ -195,7 +201,7 @@ $w_s$ is $w_{q}$ from \citet[p.~41]{lari-csl90}, generalized to $\SMTR{h}$ and $
 Let $\hat{P}$ be the new STOP/CHOOSE-probabilities (since the old $P$
 are used in $P_{INSIDE}$ and $P_{OUTSIDE}$).
 
-\subsection{Attachment reestimation} 
+\subsubsection{Attachment reestimation} 
 
 $\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:
@@ -219,25 +225,17 @@ this is implicit in $P_{INSIDE}$.
 
 
 \begin{align*}
-  \hat{P}_{CHOOSE} (a | h, left) = \frac
-  { \hat{a} (a | \GOL{h}, left) }
-  { \sum_{w} \hat{a} (w | \GOL{h}, left) }
-  +
-  \frac
-  { \hat{a} (a | \RGOL{h}, left) }
-  { \sum_{w} \hat{a} (w | \RGOL{h}, left) }
+  \hat{P}_{CHOOSE} (a | h, left) = 
+  \hat{a} (a | \GOL{h}, left) 
+  + \hat{a} (a | \RGOL{h}, left) 
 \end{align*}
 \begin{align*}
-  \hat{P}_{CHOOSE} (a | h, right) = \frac
-  { \hat{a} (a | \GOR{h},right) }
-  { \sum_{w} \hat{a} (w | \GOR{h},right) }
-  +
-  \frac
-  { \hat{a} (a | \LGOR{h},right) }
-  { \sum_{w} \hat{a} (w | \LGOR{h},right) }
+  \hat{P}_{CHOOSE} (a | h, right) = 
+  \hat{a} (a | \GOR{h},right) 
+  + \hat{a} (a | \LGOR{h},right) 
 \end{align*}
 
-\subsection{Stop reestimation} 
+\subsubsection{Stop reestimation} 
 The following is based on \citet[p.~88]{klein-thesis}. For 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).
@@ -275,23 +273,33 @@ Then these are our reestimated stop probabilities:
 \end{align*}
 
 
-\subsection{Root reestimation} % todo grok: no \sum_{i} \sum_{j} ? 
+\subsubsection{Root reestimation} 
+Following \citet[p.~46]{prescher-em}, to find the reestimated
+probability of a PCFG rule, we first find the new treebank frequencies
+$f_{T_P}(tree)=P(tree)/P_s$, then for a rule $X' \rightarrow X$ we
+divide the new frequencies of the trees which use this rule and by
+those of the trees containing the node $X'$. $ROOT$ appears once per
+tree, meaning we divide by $1$ per sentence\footnote{Assuming each
+  tree has frequency $1$.}, so $\hat{P}_{ROOT}(h)=\sum_{tree:ROOT
+  \rightarrow \SEAL{h} \text{ used in } tree} f_{T_P}(tree)=\sum_{tree:ROOT
+  \rightarrow \SEAL{h} \text{ used in } tree} P(tree)/P_s$, which turns into:
+
 \begin{align*}
   \hat{P}_{ROOT} (h) = \frac
-  {\sum_{s\in S} P_{ROOT}(h) P_{INSIDE_s}(\SEAL{h}, 0, len(s)) }
-  {\sum_{s\in S} P_s}
+  {\sum_{s\in S} 1 / P_s \cdot \sum_{\LOC{h}\in s} P_{ROOT}(\LOC{h}) P_{INSIDE_s}(\SEAL{h}, 0, len(s))}
+  {\sum_{s\in S} 1}
 \end{align*}
 
 
 
 
-\section{Alternate CNF-like rules}
+\subsection{Alternate CNF-like rules}
 Since the IO algorithm as described in \citet{lari-csl90} is made for
-rules in CNF, we have an alternate grammar (figure \ref{cnf-like}) for
-running parallell tests where we don't have to sum over the different
-$loc(h)$ in IO. This is not yet generalized to include left-first
-attachment. It is also not quite CNF, since it includes some unary
-rewrite rules.
+rules in Chomsky Normal Form (CNF), we have an alternate grammar
+(figure \ref{cnf-like}) for running testing purposes, where we don't
+have to sum over the different $loc(h)$ in IO. This is not yet
+generalized to include left-first attachment. It is also not quite
+CNF, since it includes some unary rewrite rules.
 
 \begin{figure}[htp]
   \centering
@@ -324,13 +332,14 @@ rewrite rules.
 The inside probabilities are the same as those given in
 \citet{lari-csl90}, with the following exceptions:
 
-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}$.
+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}$.
 
 Similarly, the outside probabilities are the same as those for pure
 CNF rules, with the exception that we add the unary rewrite
@@ -341,94 +350,82 @@ probabilities
 \end{align*}
 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}:
+This grammar gave the same results for inside and outside
+probabilities when run over our corpus.
+
+\subsection{TODO: Initialization}
+\citet{klein-thesis} describes DMV initialization using a ``harmonic
+distribution'' for the initial probabilities, where the probability of
+one word heading another is higher if they appear closer to one
+another.
+
+There are several ways this could be implemented. We initialized
+attachment probabilities with the following formula:
+
 \begin{align*}
-  \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) }
+  P_{ATTACH}(a|h,right) = \frac
+  {\sum_{s \in S}\sum_{\LOC{h} \in s} \sum_{\LOC{a} \in s:loc(\LOC{a})>loc(\LOC{h})} 1/(loc(\LOC{a})-loc(\LOC{h})) + C_A} 
+  {\sum_{s \in S}\sum_{\LOC{h} \in s} \sum_{\LOC{w} \in s:loc(\LOC{w})>loc(\LOC{h})} 1/(loc(\LOC{w})-loc(\LOC{h})) + C_A}
 \end{align*}
-(the denominator is unchanged, but the numerator sums $w_s$ defined
-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?
+The probability of stopping adjacently (left or right) was increased
+whenever a word occured at a (left or right) sentence
+border\footnote{For non-adjacent stopping we checked for occurence at
+  the second(-to-last) position.}:
 
+\begin{align*}
+  f(stop:\LOC{h},left,adj)=\begin{cases}
+    1 \text{, if } loc(\LOC{h}) = 0,\\
+    0 \text{, otherwise}
+  \end{cases}
+\end{align*}
 
-\section{Pure CNF rules}
-Alternatively, one may use the ``pure CNF'' grammar of figure
-\ref{cnf-T} and figure \ref{cnf-NT}, below (not yet
-implemented). Using the harmonic distribution to initialize this will
-still yield a mass-deficient grammar, but at least this allows the
-regular IO algorithm to be run.
+\begin{align*}
+  P_{STOP}(stop|h,left,adj) = \frac
+  {C_S + \sum_{s \in S}\sum_{\LOC{h} \in s} f(stop:\LOC{h},left,adj)} 
+  {C_S + C_N + \sum_{s \in S}\sum_{\LOC{h} \in s} 1}
+\end{align*}
 
-\begin{figure}[htp]
+\subsection{TODO: Results}
+We tried various values for the initialization constants $C_A, C_S$
+and $C_N$; but it was hard to find any clear pattern for what worked
+best. 
+
+% todo: check ~/dmv__zero_harmonic_c.txt and paste here
+We compared with a dependency parsed version of the WSJ-10
+corpus. Since single word sentences were not POS-tagged there, these
+were skipped. Also, the dependency parsed WSJ-10 did not have ROOT
+nodes, thus we both checked precision and recall without our ROOT
+dependency, and with a ROOT link added to the parses (where possible;
+221 parses had several heads that were not dependents, here we skipped
+the parses).
+
+Table \ref{tab:dmv-wsj} shows the results of 40 iterations on the full
+WSJ-10 corpus, compared with the dependency parsed version.
+\begin{table*}
   \centering
-  \begin{tabular} % four left-aligned math tabs, one vertical line
-    { >{$}l<{$} >{$}l<{$} >{$}l<{$} | >{$}l<{$} }
-    \multicolumn{3}{c}{Rule} & \multicolumn{1}{c}{$P_{RULE}$ ($b[i,m]$ in \citet{lari-csl90})}\\ 
-    \hline{}
-    
-    h    \rightarrow&   \text{``h''}&         &1 \\
-    &&&\\
-    \SEAL{h}   \rightarrow&   \text{``h''}&         &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, adj) \\
-    &&&\\
-    ROOT  \rightarrow&   \text{``h''}&         &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, adj) \cdot  P_{ROOT}(h) \\
+  \begin{tabular}{cccccc}
+    & Rooted  & & & Unrooted & \\
+    P & R & F1 & P & R & F1 
   \end{tabular}
-  \caption{Terminals of pure CNF rules, defined for all POS-tags
-    $h$.}\label{cnf-T}
-\end{figure}
+  \caption{DMV results on the WSJ-10}
+  \label{tab:dmv-wsj}
+\end{table*}
 
-\begin{figure}[htp]
-  \centering
-  \begin{tabular} % four left-aligned math tabs, one vertical line
-    { >{$}l<{$} >{$}l<{$} >{$}l<{$} | >{$}l<{$} }
-    \multicolumn{3}{c}{Rule} & \multicolumn{1}{c}{$P_{RULE}$ ($a[i,j,k]$ in \citet{lari-csl90})}\\ 
-    \hline{}
-    
-    \SEAL{h}   \rightarrow&    h &\SEAL{a}   &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, non\text{-}adj) \\
-    &&&\cdot  P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \\[3.5pt]
-    \SEAL{h}   \rightarrow&    h &\GOR{.h}   &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, non\text{-}adj) \\[3.5pt]
-    \GOR{.h}   \rightarrow& \SEAL{a} &\SEAL{b} &P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \\
-    &&&\cdot  P_{ATTACH}(b|h, right)\cdot P_{STOP}(\neg stop|h, right, non\text{-}adj) \\[3.5pt]
-    \GOR{.h}   \rightarrow& \SEAL{a} &\GOR{h} &P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \\[3.5pt]
-    \GOR{h}   \rightarrow& \SEAL{a} &\SEAL{b} &P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, non\text{-}adj) \\
-    &&&\cdot  P_{ATTACH}(b|h, right)\cdot P_{STOP}(\neg stop|h, right, non\text{-}adj) \\[3.5pt]
-    \GOR{h}   \rightarrow& \SEAL{a} &\GOR{h} &P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, non\text{-}adj) \\[3.5pt]
-    \SEAL{h}   \rightarrow& \SEAL{a} &h &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{STOP}(stop|h, right, adj) \\
-    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \\[3.5pt]
-    \SEAL{h}   \rightarrow& \GOL{h.} &h &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{STOP}(stop|h, right, adj) \\[3.5pt]
-    \GOL{h.}   \rightarrow& \SEAL{b} &\SEAL{a} &P_{ATTACH}(b|h, left)\cdot P_{STOP}(\neg stop|h, left, non\text{-}adj) \\
-    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \\[3.5pt]
-    \GOL{h.}   \rightarrow& \GOL{h} &\SEAL{a} &P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \\[3.5pt]
-    \GOL{h}   \rightarrow& \SEAL{a} &\SEAL{b} &P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, non\text{-}adj) \\
-    &&&\cdot  P_{ATTACH}(b|h, left)\cdot P_{STOP}(\neg stop|h, left, non\text{-}adj) \\[3.5pt]
-    \GOL{h}   \rightarrow& \GOL{h} &\SEAL{a} &P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, non\text{-}adj) \\[3.5pt]
-    \SEAL{h}   \rightarrow& \GOL{h.} &\SEAL{\GOR{h}} &P_{STOP}(stop|h, left, non\text{-}adj) \\[3.5pt]
-    \SEAL{h}   \rightarrow& \SEAL{a} &\SEAL{\GOR{h}} &P_{STOP}(stop|h, left, non\text{-}adj) \\
-    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \\[3.5pt]
-    \SEAL{\GOR{h}}  \rightarrow& h &\GOR{.h} &P_{STOP}(stop|h, right, non\text{-}adj) \\[3.5pt]
-    \SEAL{\GOR{h}}  \rightarrow& h &\SEAL{a} &P_{STOP}(stop|h, right, non\text{-}adj) \\
-    &&&\cdot  P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \\[3.5pt]
-    ROOT  \rightarrow& h &\SEAL{a} &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, non\text{-}adj) \\
-    &&&\cdot  P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \cdot  P_{ROOT}(h) \\[3.5pt]
-    ROOT  \rightarrow& h &\GOR{.h} &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, non\text{-}adj) \cdot  P_{ROOT}(h) \\[3.5pt]
-    ROOT  \rightarrow& \SEAL{a} &h &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{STOP}(stop|h, right, adj) \\
-    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \cdot  P_{ROOT}(h) \\[3.5pt]
-    ROOT  \rightarrow& \GOL{h.} &h &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{STOP}(stop|h, right, adj) \cdot  P_{ROOT}(h) \\[3.5pt]
-    ROOT  \rightarrow& \GOL{h.} &\SEAL{\GOR{h}} &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{ROOT}(h) \\[3.5pt]
-    ROOT  \rightarrow& \SEAL{a} &\SEAL{\GOR{h}} &P_{STOP}(stop|h, left, non\text{-}adj) \\
-    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \cdot  P_{ROOT}(h) \\[3.5pt]
-  \end{tabular}
-  \caption{Non-terminals of pure CNF rules, defined for all POS-tags
-    $h$, $a$ and $b$.}\label{cnf-NT}
-\end{figure}
 
+\section{The combined model (?)}
+\subsection{Results (?)}
+\section{Conclusion}
 
 
 
+\nocite{lari-csl90}
+\nocite{klein-thesis}
+\nocite{km-dmv}
 \bibliography{./statistical.bib}
 \bibliographystyle{plainnat}
 
-\end{document}
\ No newline at end of file
+\end{document}
+
+
+
diff --git a/report/statistical.bib b/report/statistical.bib
new file mode 100644 (file)
index 0000000..ee7813d
--- /dev/null
@@ -0,0 +1,235 @@
+@phdthesis{klein-thesis,
+        title = {{The Unsupervised Learning of Natural Language Structure}},
+        author = {Dan Klein},
+        school = {Stanford University},
+        year = 2005,
+        biburl = {http://www.bibsonomy.org/bibtex/2f6777dff0e2773f224f8989b4c189e17/unhammer},
+       keywords = {DG statistical unsupervised parsing NLP}
+}
+
+@inproceedings{km-ccm,
+        title = {A Generative Constituent-Context Model for Improved Grammar Induction.},
+        author = {Dan Klein and Christopher D. Manning},
+        booktitle = {ACL},
+        pages = {128-135},
+        year = 2002,
+        url = {http://dblp.uni-trier.de/db/conf/acl/acl2002.html#KleinM02},
+        ee = {http://www.aclweb.org/anthology/P02-1017.pdf},
+       date = {2003-08-27},
+       biburl = {http://www.bibsonomy.org/bibtex/2880755e3cc5b4c0e2b0cf1c599d93565/unhammer},
+       keywords = {statistical haveread NLP syllabus parsing grammar_induction}
+}
+
+@inproceedings{km-dmv,
+        title = {Corpus-Based Induction of Syntactic Structure: Models of Dependency and Constituency.},
+        author = {Dan Klein and Christopher D. Manning},
+        booktitle = {ACL},
+        pages = {478-485},
+        year = 2004,
+        url = {http://dblp.uni-trier.de/db/conf/acl/acl2004.html#KleinM04},
+        ee = {http://acl.ldc.upenn.edu/acl2004/main/pdf/341_pdf_2-col.pdf},
+       date = {2005-01-14},
+       biburl = {http://www.bibsonomy.org/bibtex/250c1e45dc65ad24b16a624e74231d951/unhammer},
+       keywords = {syllabus statistical dependency haveread NLP grammar_induction}
+}
+
+@article{zuidema-acquisition,
+        title = {Children's grammars grow more abstract with age - Evidence from an automatic procedure for identifying the productive units of language},
+        author = {Gideon Borensztajn and Willem Zuidema and Rens Bod},
+        year = 2008,
+        url = {http://staff.science.uva.nl/~gideon/borbodzui08cogsci-def.pdf},
+        description = {«...confirms the progressive abstraction hypothesis: abstraction, defined as the relative number of non-terminal leaves in multi-word constructions, increases with age. We show that it does so independently of sentence length. Complex constructions lose their lexical parts to specialized lexical rewrite rules, and in the process the constructicon becomes more abstract \r
+... \r
+our version of the progressive abstraction hypothesis now becomes _falsifiable_»},
+       biburl = {http://www.bibsonomy.org/bibtex/2e99bc92dec88420adfc4520f4a1f7a34/unhammer},
+       keywords = {CxG statistical corpus language_acquisition}
+}
+
+@article{venkatapathy2005rcn,
+        title = {{Relative compositionality of noun+ verb multiword expressions in Hindi}},
+        author = {Sriram Venkatapathy and Aaravind K. Joshi and Preeti Agarwala},
+        journal = {Proceedings of International Conference on Natural Language Processing (ICON’05), Kanpur},
+        year = 2005,
+        url = {http://www.iiit.net/techreports/2007_81.pdf},
+        abstract = {Measuring the relative compositionality of Multi-word expressions (MWEs) is crucial to Natural Language Processing. Hindi contains a rich set of Noun+Verb MWEs and hence, it is very important to handle them. Very limited work was done previously towards characterizing the MWEs in Hindi of Noun+Verb type. Also, various statistical measures which are used to measure the compositionality of different kinds of collocations in English cannot be applied straight-away to Hindi due to insufficient corpus and resources. In this paper, we analyze in detail the types of Noun+Verb expressions in Hindi. We then propose an approach to measure their relative compositionality automatically using maximum entropy model (MaxEnt). MaxEnt integrates various measures representing the properties of the Noun+Verb expressions in Hindi. Some of the measures used by the MaxEnt are computed by mapping them to Verb-Noun expressions in English.},
+       biburl = {http://www.bibsonomy.org/bibtex/274d4d47eda67a81ff4246103ff973200/unhammer},
+       keywords = {NLP corpus compositionality statistical complex_predicates syntax}
+}
+
+@unpublished{baayen_R,
+        title = {Practical Data Analysis for the Language Sciences with R},
+        address = {Cambridge, MA},
+        author = {R. Harald Baayen},
+        publisher = {Cambridge University Press.},
+        year = 2008,
+        biburl = {http://www.bibsonomy.org/bibtex/24763ed773860ebad4db237c39867b9f0/unhammer},
+       keywords = {statistical R analysis corpus}
+}
+
+@article{li2003ela,
+        title = {{An Expert Lexicon Approach to Identifying English Phrasal Verbs}},
+        author = {W. Li and X. Zhang and C. Niu and Y. Jiang and R. Srihari},
+        journal = {Proc. of the 41st Annual Meeting of the ACL},
+        pages = {513--20},
+        year = 2003,
+        url = {http://acl.ldc.upenn.edu/acl2003/main/pdfs/Li.pdf},
+        biburl = {http://www.bibsonomy.org/bibtex/2cb838b337a5802053bc31f3f4a9d85bd/unhammer},
+       keywords = {parser morphology NLP syntax lexicon phrasal_verbs statistical particle_verbs}
+}
+
+@phdthesis{bod1995els,
+        title = {{Enriching linguistics with statistics: performance models of natural language}},
+        author = {R. Bod},
+        year = 1995,
+        biburl = {http://www.bibsonomy.org/bibtex/27ae06b227a849412bdebccec068d7a38/unhammer},
+       keywords = {STSG performance statistical syllabus syntax haveread DOP}
+}
+
+@article{bresnan2008gge,
+        title = {{Gradient grammar: An effect of animacy on the syntax of give in New Zealand and American English}},
+        author = {J. Bresnan and J. Hay},
+        journal = {Lingua},
+        number = 2,
+        pages = {245--259},
+        publisher = {Elsevier},
+        volume = 118,
+        year = 2008,
+        biburl = {http://www.bibsonomy.org/bibtex/243e3d7fd8482a45ffe570a807879d558/unhammer},
+       keywords = {semantics grammar statistical toread syntax animacy}
+}
+
+@article{bod1992cml,
+        title = {{A computational model of language performance: Data Oriented Parsing}},
+        author = {R. Bod},
+        journal = {Proceedings of the 14th conference on Computational linguistics-Volume 3},
+        pages = {855--859},
+        publisher = {Association for Computational Linguistics Morristown, NJ, USA},
+        year = 1992,
+        description = {The original...},
+       biburl = {http://www.bibsonomy.org/bibtex/2f4c5696f56e671cd983a8a39c5e5eb2d/unhammer},
+       keywords = {toread parsing statistical DOP}
+}
+
+@article{way-lfg-dop,
+        title = {A hybrid architecture for robust MT using LFG-DOP},
+        author = {Andy Way},
+        journal = {Journal of Experimental & Theoretical Artificial Intelligence},
+        number = 3,
+        pages = {441--471},
+        publisher = {Taylor and Francis Ltd},
+        volume = 11,
+        year = 1999,
+        url = {http://www.nclt.dcu.ie/lfg-dop/pubs/Way_99.ps},
+        abstract = {We develop a model for machine translation (MT) based on data-oriented parsing (DOP) allied to the syntactic representations of lexical functional grammar (LFG). We begin by showing that in themselves, none of the main paradigmatic approaches to MT currently suffice to the standard required. Nevertheless, each of these approaches contains elements which if properly harnessed should lead to an overall improvement in translation performance. It is in this new hybrid spirit that our search for a better solution to the problems of MT can be seen. We summarize the original DOP model of Bod, as well as the DOT model of translation of Poutsma on which it is based. We demonstrate that DOT is not guaranteed to produce the correct translation, despite provably deriving the most probable translation. We go on to critically evaluate previous attempts at LFG-MT, commenting briefly on particular problem cases for such systems. We then show how the LFG-DOP model of Bod and Kaplan can be extended to serve as a novel hybrid model for MT which promises to improve upon DOT, as well as the pure LFG-based translation model.},
+       biburl = {http://www.bibsonomy.org/bibtex/290fdf61c16719f525c67d9781f370996/unhammer},
+       keywords = {toread statistical DOP MT LFG}
+}
+
+@article{goodman2002epd,
+        title = {Efficient Parsing of DOP with PCFG-Reductions},
+        author = {J. Goodman},
+        journal = {Bod et al. 2002b},
+        year = 2002,
+        url = {http://research.microsoft.com/~joshuago/dop-csli.ps},
+        biburl = {http://www.bibsonomy.org/bibtex/2f76839ea98f36073ef2f989cd7795d99/unhammer},
+       keywords = {PCFG toread syllabus NLP statistical DOP parsing}
+}
+
+@article{collins-hdsnlp,
+        title = {Head-Driven Statistical Models for Natural Language Parsing.},
+        author = {Michael Collins},
+        journal = {Computational Linguistics},
+        number = 4,
+        pages = {589-637},
+        volume = 29,
+        year = 2003,
+        url = {http://dblp.uni-trier.de/db/journals/coling/coling29.html#Collins03},
+        date = {2004-03-26},
+       biburl = {http://www.bibsonomy.org/bibtex/2b61315e8ab92f576ae3de7cb87c5460b/unhammer},
+       keywords = {head-driven NLP statistical toread}
+}
+
+@article{prescher-em,
+        title = {A Tutorial on the Expectation-Maximization Algorithm Including Maximum-Likelihood Estimation and EM Training of Probabilistic Context-Free Grammars},
+        author = {Detlef Prescher},
+        journal = {CoRR},
+        note = {informal publication},
+        pages = 49,
+        volume = {abs/cs/0412015},
+        year = 2004,
+        url = {http://dblp.uni-trier.de/db/journals/corr/corr0412.html#abs-cs-0412015},
+        ee = {http://arxiv.org/abs/cs/0412015},
+       date = {2008-01-02},
+       description = {dblp},
+       biburl = {http://www.bibsonomy.org/bibtex/27684ca4c422922d880e247ce5ebceb2b/unhammer},
+       keywords = {syllabus statistical EM ML}
+}
+
+@article{carroll1992tel,
+        title = {Two experiments on learning probabilistic dependency grammars from corpora},
+        author = {G. Carroll and E. Charniak},
+        journal = {Working Notes of the Workshop Statistically-Based NLP Techniques},
+        pages = {1--13},
+        year = 1992,
+        url = {http://citeseer.ist.psu.edu/cache/papers/cs/483/ftp:zSzzSzftp.cs.brown.eduzSzpubzSztechreportszSz92zSzcs92-16.pdf/carroll92two.pdf},
+        biburl = {http://www.bibsonomy.org/bibtex/2ab653bd555bdafc6dc761ce6e32bba44/unhammer},
+       keywords = {statistical toread corpus syllabus ML grammar}
+}
+
+@article{lari-csl90,
+        title = {The estimation of stochastic context-free grammars using the Inside-Outside algorithm},
+        author = {K. Lari and S. J. Young},
+        journal = {Computer Speech and Language},
+        pages = {35--56},
+        volume = 4,
+        year = 1990,
+        biburl = {http://www.bibsonomy.org/bibtex/2b9f6798bb092697da7042ca3f5dee795/unhammer},
+       keywords = {NLP EM toread algorithm statistical}
+}
+
+@article{eslick2005lnl,
+        title = {Langutils--A natural language toolkit for Common Lisp},
+        author = {Ian Eslick and Hugo Liu},
+        journal = {Proceedings of the International Conference on Lisp},
+        year = 2005,
+        url = {http://www.media.mit.edu/~hugo/publications/papers/ILC2005-langutils.pdf},
+        biburl = {http://www.bibsonomy.org/bibtex/2136f2687f142217d6bafa05ae549c17f/unhammer},
+       keywords = {toread lisp statistical corpus NLP}
+}
+
+@book{manning99foundations,
+        title = {Foundations of Statistical Natural Language Processing},
+        author = {Christopher D. Manning and Hinrich Schütze},
+        howpublished = {Hardcover},
+        month = {June},
+        publisher = {{The MIT Press}},
+        year = 1999,
+        isbn = {0262133601},
+       biburl = {http://www.bibsonomy.org/bibtex/29b2ddcf0d31e9f0d787b2bce8803fa96/unhammer},
+       keywords = {syllabus statistical NLP}
+}
+
+@book{Cha93,
+        title = {{Statistical Language Learning}},
+        address = {Cambridge MA},
+        author = {E. Charniak},
+        publisher = {MIT Press},
+        year = 1993,
+        biburl = {http://www.bibsonomy.org/bibtex/26dcaa41af94bd8a97936cf1f17e8284a/unhammer},
+       keywords = {NLP syllabus statistical toread}
+}
+
+@article{rayson1997sdu,
+        title = {{Social differentiation in the use of English vocabulary: Some analyses of the conversational component of the British National Corpus}},
+        author = {P. RAYSON and G. LEECH and M. HODGES},
+        journal = {International journal of corpus linguistics},
+        number = 1,
+        pages = {133--152},
+        publisher = {Benjamins Publishing},
+        volume = 2,
+        year = 1997,
+        description = {Gender, age, social class etc. and their differences in vocabulary use.},
+       biburl = {http://www.bibsonomy.org/bibtex/227d5ef4b1e88811468424646245685b8/unhammer},
+       keywords = {linguistics corpus statistical imported sociolinguistics gender}
+}
+
index 6627d87..ddbcd92 100755 (executable)
@@ -388,8 +388,7 @@ def reest_freq(g, corpus):
             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',ROOT] += p_sent
+                f['num',LHS,L,R] += r.p() * e_g(0, len(sent), R, sent) / p_sent
                 continue # !!! o/w we add wrong values to it below
             if L == STOP or R == STOP:
                 w = w1_g
@@ -407,7 +406,7 @@ def reestimate(g, corpus):
     print "applying f to rules"
     for r in g.all_rules():
         if r.LHS() == ROOT:
-            r.prob = f['den',ROOT]
+            r.prob = 1.0
         else:
             r.prob = f['den',r.LHS(),r.L(),r.R()]
         if r.prob > 0.0:
index 6f34f9b..99b6879 100644 (file)
@@ -34,13 +34,18 @@ def make_GO_AT(p_STOP,p_ATTACH):
 
 class DMV_Grammar(io.Grammar):
     def __str__(self):
+        LJUST = 47
         def t(n):
             return "%d=%s" % (n, self.numtag(n))
         def p(dict,key):
-            if key in dict:
-                return dict[key]
-            else:
-                return 0.0
+            if key in dict: return dict[key]
+            else: return 0.0
+        def no_zeroL(str,tagstr,prob):
+            if prob > 0.0: return (str%(tagstr,prob)).ljust(LJUST)
+            else: return "".ljust(LJUST)
+        def no_zeroR(str,tagstr,prob):
+            if prob > 0.0: return str%(tagstr,prob)
+            else: return ""
         def p_a(a,h):
             p_L = p(self.p_ATTACH,(a,h,LEFT))
             p_R = p(self.p_ATTACH,(a,h,RIGHT))
@@ -48,24 +53,28 @@ class DMV_Grammar(io.Grammar):
                 return ''
             else:
                 if p_L > 0.0:
-                    str = "p_ATTACH[ %s|%s,L] = %.4f" % (t(a), t(h), p_L)
+                    str = "p_ATTACH[%s|%s,L] = %s" % (t(a), t(h), p_L)
+                    str = str.ljust(LJUST)
                 else:
                     str = ''
                 if p_R > 0.0:
-                    str = str.ljust(40)
-                    str += "p_ATTACH[ %s|%s,R] = %.4f" % (t(a), t(h), p_R)
-            return str+'\n'
+                    str = str.ljust(LJUST)
+                    str += "p_ATTACH[%s|%s,R] = %s" % (t(a), t(h), p_R)
+            return '\n'+str
 
         root, stop, att, ord = "","","",""
         for h in self.headnums():
-            root += "p_ROOT[%s] = %.4f\n" % (t(h), p(self.p_ROOT, (h)))
-            stop += "p_STOP[stop|%s,L,adj] = %.4f\t" % (t(h), p(self.p_STOP, (h,LEFT,ADJ)))
-            stop += "p_STOP[stop|%s,R,adj] = %.4f\n" % (t(h), p(self.p_STOP, (h,RIGHT,ADJ)))
-            stop += "p_STOP[stop|%s,L,non] = %.4f\t" % (t(h), p(self.p_STOP, (h,LEFT,NON)))
-            stop += "p_STOP[stop|%s,R,non] = %.4f\n" % (t(h), p(self.p_STOP, (h,RIGHT,NON)))
+            root += no_zeroL("\np_ROOT[%s] = %s", t(h), p(self.p_ROOT, (h)))
+            stop += '\n'
+            stop += no_zeroL("p_STOP[stop|%s,L,adj] = %s", t(h), p(self.p_STOP, (h,LEFT,ADJ)))
+            stop += no_zeroR("p_STOP[stop|%s,R,adj] = %s", t(h), p(self.p_STOP, (h,RIGHT,ADJ)))
+            stop += '\n'
+            stop += no_zeroL("p_STOP[stop|%s,L,non] = %s", t(h), p(self.p_STOP, (h,LEFT,NON)))
+            stop += no_zeroR("p_STOP[stop|%s,R,non] = %s", t(h), p(self.p_STOP, (h,RIGHT,NON)))
             att  += ''.join([p_a(a,h) for a in self.headnums()])
-            ord  += "p_ORDER[ left-first|%s ] = %.4f\t" % (t(h), p(self.p_ORDER, (GOL,h)))
-            ord  += "p_ORDER[right-first|%s ] = %.4f\n" % (t(h), p(self.p_ORDER, (GOR,h)))
+            ord  += '\n'
+            ord  += no_zeroL("p_ORDER[ left-first|%s ] = %s", t(h), p(self.p_ORDER, (GOL,h)))
+            ord  += no_zeroR("p_ORDER[right-first|%s ] = %s", t(h), p(self.p_ORDER, (GOR,h)))
         return root + stop + att + ord 
 
     def __init__(self, numtag, tagnum, p_ROOT, p_STOP, p_ATTACH, p_ORDER):
@@ -83,11 +92,11 @@ class DMV_Grammar(io.Grammar):
         ch_key = tuple(sent_nums)
         try:
             ichart = self._icharts[ch_key]
-        except:
+        except KeyError:
             ichart = {}
         try:
             ochart = self._ocharts[ch_key]
-        except:
+        except KeyError:
             ochart = {}
         return (ichart, ochart)
 
@@ -102,7 +111,7 @@ class DMV_Grammar(io.Grammar):
     def p_GO_AT_or0(self, a, h, dir, adj):
         try:
             return self.p_GO_AT[a, h, dir, adj]
-        except:
+        except KeyError:
             return 0.0
     
 
@@ -174,6 +183,10 @@ def inner(i, j, node, loc_h, g, sent, ichart, mpptree=None):
                 if 'INNER' in DEBUG:
                     print "%s%s (%.1f) from %d to %d" % (tab(),node_str((s_h,h)),loc_h,i,j)
                 if s_h == SEAL:
+                    if h == POS(ROOT): # only used in testing, o/w we use inner_sent
+                        h = sent_nums[loc_h]
+                        if i != 0 or j != len(sent): raise ValueError
+                        else: return g.p_ROOT[h] * e(i,j,(SEAL,h),loc_h,n_t+1)
                     p_RGOL = g.p_STOP[h,  LEFT, adj(i,loc_h)] * e(i,j,(RGOL,h),loc_h,n_t+1)
                     p_LGOR = g.p_STOP[h, RIGHT, adj(j,loc_h)] * e(i,j,(LGOR,h),loc_h,n_t+1)
                     p = p_RGOL + p_LGOR
@@ -269,7 +282,7 @@ def outer(i,j,w_node,loc_w, g, sent, ichart, ochart):
     def e(i,j,LHS,loc_h): # P_{INSIDE}
         try:
             return ichart[i,j,LHS,loc_h]
-        except:
+        except KeyError:
             return inner(i,j,LHS,loc_h,g,sent,ichart) 
 
     def f(i,j,w_node,loc_w):
@@ -345,7 +358,7 @@ def reest_zeros(h_nums):
     '''A dict to hold numerators and denominators for our 6+ reestimation
 formulas. '''
     # todo: p_ORDER?
-    fr = { ('ROOT','den'):0.0 } # holds sum over p_sent
+    fr = { ('ROOT','den'):0.0 } # holds sum over f_sent!! not p_sent...
     for h in h_nums:
         fr['ROOT','num',h] = 0.0 
         for s_h in [GOR,GOL,RGOL,LGOR]:
@@ -381,14 +394,14 @@ def reest_freq(g, corpus):
     def f(i,j,LHS,loc_h,sent): # P_{OUTSIDE}
         try:
             return ochart[i,j,LHS,loc_h]
-        except:
+        except KeyError:
             return outer(i,j,LHS,loc_h,g,sent,ichart,ochart)
     # end reest_freq.f()
 
     def e(i,j,LHS,loc_h,sent): # P_{INSIDE}
         try:
             return ichart[i,j,LHS,loc_h]
-        except:
+        except KeyError:
             return inner(i,j,LHS,loc_h,g,sent,ichart) 
     # end reest_freq.e()
 
@@ -410,11 +423,11 @@ def reest_freq(g, corpus):
                 p_L = e(i,k, (SEAL,a), loc_a, sent)
                 p = p_L * p_out * p_R * p_rule
                 try:    a_k[a] += p
-                except: a_k[a]  = p
+                except KeyError: a_k[a]  = p
 
         for a,p in a_k.iteritems():
             try:    fr['hat_a','num',a,x] += p / p_sent
-            except: fr['hat_a','num',a,x]  = p / p_sent
+            except KeyError: fr['hat_a','num',a,x]  = p / p_sent
     # end reest_freq.w_left() 
 
     def w_right(i,j, x,loc_h,sent,sent_nums):
@@ -435,11 +448,11 @@ def reest_freq(g, corpus):
                 p_R = e(k,j, (SEAL,a),loc_a, sent)
                 p = p_L * p_out * p_R * p_rule 
                 try:    a_k[a] += p
-                except: a_k[a]  = p
+                except KeyError: a_k[a]  = p
 
         for a,p in a_k.iteritems():
             try:    fr['hat_a','num',a,x] += p / p_sent
-            except: fr['hat_a','num',a,x]  = p / p_sent
+            except KeyError: fr['hat_a','num',a,x]  = p / p_sent
     # end reest_freq.w_right()
 
     # in reest_freq:    
@@ -449,13 +462,14 @@ def reest_freq(g, corpus):
         ichart = {}
         ochart = {}
         p_sent = inner_sent(g, sent, ichart)
-        fr['ROOT','den'] += p_sent
+        fr['ROOT','den'] += 1 # divide by p_sent per h!
         
         sent_nums = g.sent_nums(sent)
         
         for loc_h,h in locs(sent_nums,0,len(sent)+1): # locs-stop is exclusive, thus +1
             # root:
-            fr['ROOT','num',h] += g.p_ROOT[h] * e(0,len(sent), (SEAL,h),loc_h, sent)
+            fr['ROOT','num',h] += g.p_ROOT[h] * e(0,len(sent), (SEAL,h),loc_h, sent) \
+                / p_sent
             
             loc_l_h = loc_h
             loc_r_h = loc_l_h+1 
@@ -538,8 +552,8 @@ def reest_head(h, fr, g, p_ROOT, p_STOP, p_ATTACH):
     # remove 0-prob stuff? todo
     try:
         p_ROOT[h] = fr['ROOT','num',h] / fr['ROOT','den']
-    except:
-        p_ROOT[h] = fr['ROOT','den']
+    except KeyError:
+        p_ROOT[h] = 0.0
     
     for dir in [LEFT,RIGHT]:
         for adj in [ADJ, NON]: # p_STOP
@@ -553,26 +567,15 @@ def reest_head(h, fr, g, p_ROOT, p_STOP, p_ATTACH):
 
         for s_h in dirseal(dir): # make hat_a for p_ATTACH
             x = (s_h,h)
-            hat_a = {}
-            
             p_c = fr['hat_a','den',x]
-            for w in g.headnums():
-                try:
-                    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])
-
+            
             for a in g.headnums():
                 if (a,h,dir) not in p_ATTACH:
                     p_ATTACH[a,h,dir] = 0.0
                 try: # (a,x) might not be in hat_a
-                    p_ATTACH[a,h,dir] += hat_a[a,x] / sum_hat_a
-                except:
-                    pass
+                    p_ATTACH[a,h,dir] += fr['hat_a','num',a,x] / p_c 
+                except KeyError: pass
+                except ZeroDivisionError: pass
 
 
 
@@ -601,7 +604,7 @@ def locs_a(a, sent_nums, start, stop):
 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) 
+    except KeyError: p = inner(i,j,x,loc_h,g,sent,ichart) 
     g.set_iochart(s_n,ichart,ochart)
     return p
 
@@ -614,7 +617,7 @@ def inner_sent2(g, sent):
 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) 
+    except KeyError: p = inner(i,j,w_node,loc_w,g,sent,ichart,ochart) 
     g.set_iochart(s_n,ichart,ochart)
     return p
 
@@ -655,10 +658,10 @@ def c2(x,loc_h,i,j,g,s_n,sent):
     
     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)
+        except KeyError: 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) 
+        except KeyError: return inner(i,j,x,loc_h,g,sent,ichart) 
 
     p_sent = inner_sent(g, sent, ichart)
     if not p_sent > 0.0:
@@ -678,10 +681,10 @@ def w2(a, x,loc_h, dir, i, j, g, s_n,sent):
     
     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)
+        except KeyError: 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) 
+        except KeyError: return inner(i,j,x,loc_h,g,sent,ichart) 
 
     h = POS(x)
     p_sent = inner_sent(g, sent, ichart)
@@ -734,29 +737,25 @@ def hat_a2(a, x, dir, g, corpus): # attachment helper
     return num/den
 
 def reest_root2(h,g,corpus):
-    num, den = 0.0, 0.0
+    sum = 0.0
+    corpus_size = 0.0
     for s_n,sent in [(g.sent_nums(sent),sent) for sent in corpus]:
+        num, den = 0.0, 0.0
+        corpus_size += 1.0
         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)
+                inner(0, len(s_n), (SEAL,h), loc_h, g, sent, ichart) 
         g.set_iochart(s_n, ichart, ochart)
-    return num / den
+        sum += num / den
+    return sum / corpus_size
 
 def reest_head2(h, g, corpus, p_ROOT, p_STOP, p_ATTACH):
     print "h: %d=%s ..."%(h,g.numtag(h)),
     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 not ("0.0"=="%s"%den or "1.0"=="%s"%den):
-            print "in reest_head2:div, got den=%s"%den
-#         return num # todo: test without division by sum_hat_a
-        if den > 0.0: return num / den
-        else:
-            if num > 0.0: raise ValueError
-            return den
     
     p_STOP[h, LEFT,NON] = \
         hat_d((SEAL,h),(RGOL,h),xlt,  xgteq) + \
@@ -771,19 +770,17 @@ def reest_head2(h, g, corpus, p_ROOT, p_STOP, p_ATTACH):
         hat_d((RGOL,h),( GOR,h),xeq,  xeq) + \
         hat_d((SEAL,h),(LGOR,h),xlteq,xeq)
     print "stops done...",
+
     p_ROOT[h] = reest_root2(h,g,corpus)
     print "root done...",
+    
     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()]) )
+            hat_a(a, (GOL,h),LEFT) + \
+            hat_a(a,(RGOL,h),LEFT)
         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()]) )
+            hat_a(a, (GOR,h),RIGHT) + \
+            hat_a(a,(LGOR,h),RIGHT)
 
     print "attachment done"
         
@@ -888,7 +885,8 @@ def testgrammar():
     loc_h_harmonic.FNONSTOP_MIN = 25
     loc_h_harmonic.FSTOP_MIN = 5
     loc_h_harmonic.RIGHT_FIRST = 1.0 
-
+    loc_h_harmonic.OTHER_STOP_CALC = False
+    
     return loc_h_harmonic.initialize(testcorpus)
 
 def testreestimation2():
@@ -1097,7 +1095,7 @@ if __name__ == "__main__":
     q_tree[4] = 2.7213e-06 # same as 1-3
     q_tree[5] = 9.738e-06
     q_tree[6] = 2.268e-06
-    q_tree[7] = 1.086e-06   # n <- v -> n
+    q_tree[7] = 1.086e-05   # n <- v -> n (e-05!!!)
     f_T_q = {}
     for i,q_t in q_tree.iteritems():
         f_T_q[i] = q_t / q_sent
@@ -1107,39 +1105,65 @@ if __name__ == "__main__":
     print sum([f for f in f_T_q.values()])
     
     def treediv(num,den):
-        return sum([f_T_q[i] for i in num ]) / \
-        sum([f_T_q[i] for i in den ])
+        return \
+            sum([f_T_q[i] for i in num ]) / \
+            sum([f_T_q[i] for i in den ])
     g2 = {}
-    g2['root --> _n_'] = treediv( (1,2,3,4,5,6), (1,2,3,4,5,6,7) )
-    g2['root --> _v_'] = treediv( (7,), (1,2,3,4,5,6,7) )
-    g2['_n_ --> STOP n><'] = treediv( (1,2,3,4,5,6,7,1,2,3,4,5,6,7),
-                                      (1,2,3,4,5,6,7,1,2,3,4,5,6,7))
-    g2['_v_ --> STOP v><'] = treediv( (1,2,3,4,5,6,7),
-                                      (1,2,3,4,5,6,7) )
-    nlrtrees = (1,2,3,4,5,6,7,1,2,3,4,5,6,7,
-                3,4,4,5,6)
-    g2['n>< --> _n_ n><'] = treediv( (4,6), nlrtrees )
-    g2['n>< --> _v_ n><'] = treediv( (3,4,5), nlrtrees )
-    g2['n>< --> n> STOP'] = treediv( (1,2,3,4,5,6,7,1,2,3,4,5,6,7),
-                                     nlrtrees )
-    vlrtrees = (1,2,3,4,5,6,7,
-                7,5)
-    g2['v>< --> _n_ v><'] = treediv( (5,7), vlrtrees )
-    g2['v>< --> v> STOP'] = treediv( (1,2,3,4,5,6,7), vlrtrees )
-    nrtrees = (1,2,3,4,5,6,7,1,2,3,4,5,6,7,
-               1,1,2,3,6)
-    g2['n> --> n> _n_'] = treediv( (1,3), nrtrees )
-    g2['n> --> n> _v_'] = treediv( (1,2,6), nrtrees )
-    vrtrees = (1,2,3,4,5,6,7,
-               7,2)
-    g2['v> --> v> _n_'] = treediv( (2,7), vrtrees )
-
-    g2[' v|n,R '] = treediv( (1,  2,  6),
-                             (1,1,2,3,6) )
-    g2[' n|n,R '] = treediv( (1,    3),
-                             (1,1,2,3,6) )
+#     g2['root --> _n_'] = treediv( (1,2,3,4,5,6), (1,2,3,4,5,6,7) )
+#     g2['root --> _v_'] = treediv( (7,), (1,2,3,4,5,6,7) )
+#     g2['_n_ --> STOP n><'] = treediv( (1,2,3,4,5,6,7,1,2,3,4,5,6,7),
+#                                       (1,2,3,4,5,6,7,1,2,3,4,5,6,7))
+
+#     g2['_n_ --> STOP n>< NON'] = treediv( (3,4,5,6),
+#                                           (3,4,5,6,4) )
+
+#     g2['_v_ --> STOP v><'] = treediv( (1,2,3,4,5,6,7),
+#                                       (1,2,3,4,5,6,7) )
+#     nlrtrees = (1,2,3,4,5,6,7,1,2,3,4,5,6,7,
+#                 3,4,4,5,6)
+#     g2['n>< --> _n_ n><'] = treediv( (  4,  6), nlrtrees )
+#     g2['n>< --> _v_ n><'] = treediv( (3,4,5), nlrtrees )
+#     g2['n>< --> n> STOP'] = treediv( (1,2,3,4,5,6,7,1,2,3,4,5,6,7),
+#                                      nlrtrees )
+
+#     g2['n>< --> n> STOP ADJ'] = treediv( (      4,5,  7,1,2,3,4,5,6,7),
+#                                          nlrtrees )
+#     g2['n>< --> n> STOP NON'] = treediv( (1,2,3,    6),
+#                                          nlrtrees )
+
+#     vlrtrees = (1,2,3,4,5,6,7,
+#                 7,5)
+#     g2['v>< --> _n_ v><'] = treediv( (5,7), vlrtrees )
+#     g2['v>< --> v> STOP'] = treediv( (1,2,3,4,5,6,7), vlrtrees )
+#     nrtrees = (1,2,3,4,5,6,7,1,2,3,4,5,6,7,
+#                1,1,2,3,6)
+#     g2['n> --> n> _n_'] = treediv( (1,3), nrtrees )
+#     g2['n> --> n> _v_'] = treediv( (1,2,6), nrtrees )
+
+#     g2['n> --> n> _n_ NON'] = treediv( (1,), nrtrees )
+#     g2['n> --> n> _n_ ADJ'] = treediv( (      3,), nrtrees )
+#     g2['n> --> n> _v_ ADJ'] = treediv( (  1,2,  6), nrtrees )
+
+#     vrtrees = (1,2,3,4,5,6,7,
+#                7,2)
+#     g2['v> --> v> _n_'] = treediv( (2,7), vrtrees )
+
+#     g2[' v|n,R '] = treediv( (1,  2,  6),
+#                              (1,1,2,3,6) )
+#     g2[' n|n,R '] = treediv( (1,    3),
+#                              (1,1,2,3,6) )
+    
+    g2[' stop|n,R,non '] = treediv( (  1,2,3,6),
+                                    (1,1,2,3,6) )
+    g2[' v|n,left '] = treediv( (    3,4,5),
+                                (6,4,3,4,5) )
+    g2[' n|n,left '] = treediv( (6,4),
+                                (6,4,3,4,5) )
     
     pprint.pprint(g2)
     g3 = reestimate2(g, ['n v n'.split()])
     print g3
+    g4 = reestimate2(g, ['n v n'.split()])
+    print g4
+
     
dissimilarity index 66%
index e0854ad..328748c 100644 (file)
Binary files a/src/loc_h_dmv.pyc and b/src/loc_h_dmv.pyc differ
index 7d90fbc..1b3eb1e 100644 (file)
@@ -2,10 +2,11 @@
 
 from loc_h_dmv import * # better way to do this?
 
-# todo: tweak these
+# todo: tweak these (0.0 on FSTOP_MIN gives too many zero-probabilities though)
 HARMONIC_C = 0.0
-FNONSTOP_MIN = 25
-FSTOP_MIN = 5
+FNONSTOP_MIN = 0.0
+FSTOP_MIN = 1.0
+OTHER_STOP_CALC = True
 
 RIGHT_FIRST = 1.0 # apparently right-first is best for DMV-only 
 
@@ -72,7 +73,7 @@ def init_freq(corpus, tags):
     f = init_zeros(tags)
     
     for sent in corpus: # sent is ['VBD', 'NN', ...]
-        n = len(sent)
+        n = len(sent) - 1
         # NOTE: head in DMV_Rule is a number, while this is the string
         for loc_h, head in enumerate(sent): 
             # todo grok: how is this different from just using straight head
@@ -80,15 +81,24 @@ def init_freq(corpus, tags):
             f['ROOT', head] += 1
             f['sum', 'ROOT'] += 1
             
-            # True = 1, False = 0. todo: make prettier
-            f[head,  'STOP',  LEFT,NON] += (loc_h == 1)     # second word
-            f[head, '-STOP',  LEFT,NON] += (not loc_h == 1) # not second
-            f[head,  'STOP',  LEFT,ADJ] += (loc_h == 0)     # first word
-            f[head, '-STOP',  LEFT,ADJ] += (not loc_h == 0) # not first
-            f[head,  'STOP', RIGHT,NON] += (loc_h == n - 2)     # second-to-last
-            f[head, '-STOP', RIGHT,NON] += (not loc_h == n - 2) # not second-to-last
-            f[head,  'STOP', RIGHT,ADJ] += (loc_h == n - 1)     # last word
-            f[head, '-STOP', RIGHT,ADJ] += (not loc_h == n - 1) # not last
+            if OTHER_STOP_CALC:
+                f[head,  'STOP',  LEFT,NON] += (loc_h == 1)     # second word
+                f[head, '-STOP',  LEFT,NON] += (loc_h  > 1)     # after second
+                f[head,  'STOP',  LEFT,ADJ] += (loc_h == 0)     # first word
+                f[head, '-STOP',  LEFT,ADJ] += (loc_h  > 0)     # not first
+                f[head,  'STOP', RIGHT,NON] += (loc_h == n - 1) # second-to-last
+                f[head, '-STOP', RIGHT,NON] += (loc_h  < n - 1) # before second-to-last
+                f[head,  'STOP', RIGHT,ADJ] += (loc_h == n)     # last word
+                f[head, '-STOP', RIGHT,ADJ] += (loc_h  < n)     # not last
+            else: # note: int(True) == 1
+                f[head,  'STOP',  LEFT,NON] += (loc_h == 1)     # second word
+                f[head, '-STOP',  LEFT,NON] += (not loc_h == 1) # not second
+                f[head,  'STOP',  LEFT,ADJ] += (loc_h == 0)     # first word
+                f[head, '-STOP',  LEFT,ADJ] += (not loc_h == 0) # not first
+                f[head,  'STOP', RIGHT,NON] += (loc_h == n - 1)     # second-to-last
+                f[head, '-STOP', RIGHT,NON] += (not loc_h == n - 1) # not second-to-last
+                f[head,  'STOP', RIGHT,ADJ] += (loc_h == n)         # last word
+                f[head, '-STOP', RIGHT,ADJ] += (not loc_h == n)     # not last
             
             # this is where we make the "harmonic" distribution. quite.
             for loc_a, arg in enumerate(sent):
@@ -105,7 +115,6 @@ def init_freq(corpus, tags):
                 # todo, optimization: possible to do both directions
                 # at once here, and later on rule out the ones we've
                 # done? does it actually speed things up?
-
     return f 
 
 def init_normalize(f, tags, numtag, tagnum):
@@ -121,9 +130,13 @@ def init_normalize(f, tags, numtag, tagnum):
         # p_STOP = STOP / (STOP + NOT_STOP)
         for dir in [LEFT,RIGHT]:
             for adj in [NON,ADJ]:
-                p_STOP[h, dir, adj] = \
-                    float(f[head, 'STOP', dir, adj]) / \
-                    (f[head, 'STOP', dir, adj] + f[head, '-STOP', dir, adj])
+                den = f[head, 'STOP', dir, adj] + f[head, '-STOP', dir, adj]
+                if den > 0.0:
+                    p_STOP[h, dir, adj] = float(f[head, 'STOP', dir, adj]) / float(den)
+                else:
+                    p_STOP[h, dir, adj] = 1.0
+                    
+                    
             
         p_ORDER[GOR, h] = RIGHT_FIRST
         p_ORDER[GOL, h] = 1 - RIGHT_FIRST
@@ -144,6 +157,11 @@ def initialize(corpus):
     # f: frequency counts used in initialization, mostly distances
     f = init_freq(corpus, tags)
     g = init_normalize(f, tags, numtag, tagnum)
+
+    g.HARMONIC_C = HARMONIC_C # for evaluations in main.py, todo: remove
+    g.FNONSTOP_MIN = FNONSTOP_MIN
+    g.FSTOP_MIN = FSTOP_MIN
+    
     return g
 
 
@@ -155,27 +173,8 @@ def initialize(corpus):
 
 if __name__ == "__main__":
     print "--------initialization testing------------"
-    g2 = initialize([['foo', 'two','foo','foo'],
-                     ['zero', 'one','two','three']])
+    g2 = initialize([ ['Leftmost', 'Midleft','Midright','Rightmost']])
     print g2
     
-
-##### todo: grok why there's so little difference in probN and probA values
-#     for (n,s) in [(95,5),(5,5)]:
-#         FNONSTOP_MIN = n
-#         FSTOP_MIN = s
-        
-#         testcorpus = [s.split() for s in ['det nn vbd c nn vbd nn','det nn vbd c nn vbd pp nn',
-#                                           'det nn vbd nn','det nn vbd c nn vbd pp nn', 
-#                                           'det nn vbd nn','det nn vbd c nn vbd pp nn', 
-#                                           'det nn vbd nn','det nn vbd c nn vbd pp nn', 
-#                                           'det nn vbd nn','det nn vbd c nn vbd pp nn', 
-#                                           'det nn vbd pp nn','det nn vbd det nn', ]]
-#         g = initialize(testcorpus)
-
-    
     
 
-def tagset_brown():
-    "472 tags, takes a while to extract with tagset(), hardcoded here."
-    return set(['BEDZ-NC', 'NP$', 'AT-TL', 'CS', 'NP+HVZ', 'IN-TL-HL', 'NR-HL', 'CC-TL-HL', 'NNS$-HL', 'JJS-HL', 'JJ-HL', 'WRB-TL', 'JJT-TL', 'WRB', 'DOD*', 'BER*-NC', ')-HL', 'NPS$-HL', 'RB-HL', 'FW-PPSS', 'NP+HVZ-NC', 'NNS$', '--', 'CC-TL', 'FW-NN-TL', 'NP-TL-HL', 'PPSS+MD', 'NPS', 'RBR+CS', 'DTI', 'NPS-TL', 'BEM', 'FW-AT+NP-TL', 'EX+BEZ', 'BEG', 'BED', 'BEZ', 'DTX', 'DOD*-TL', 'FW-VB-NC', 'DTS', 'DTS+BEZ', 'QL-HL', 'NP$-TL', 'WRB+DOD*', 'JJR+CS', 'NN+MD', 'NN-TL-HL', 'HVD-HL', 'NP+BEZ-NC', 'VBN+TO', '*-TL', 'WDT-HL', 'MD', 'NN-HL', 'FW-BE', 'DT$', 'PN-TL', 'DT-HL', 'FW-NR-TL', 'VBG', 'VBD', 'VBN', 'DOD', 'FW-VBG-TL', 'DOZ', 'ABN-TL', 'VB+JJ-NC', 'VBZ', 'RB+CS', 'FW-PN', 'CS-NC', 'VBG-NC', 'BER-HL', 'MD*', '``', 'WPS-TL', 'OD-TL', 'PPSS-HL', 'PPS+MD', 'DO*', 'DO-HL', 'HVG-HL', 'WRB-HL', 'JJT', 'JJS', 'JJR', 'HV+TO', 'WQL', 'DOD-NC', 'CC-HL', 'FW-PPSS+HV', 'FW-NP-TL', 'MD+TO', 'VB+IN', 'JJT-NC', 'WDT+BEZ-TL', '---HL', 'PN$', 'VB+PPO', 'BE-TL', 'VBG-TL', 'NP$-HL', 'VBZ-TL', 'UH', 'FW-WPO', 'AP+AP-NC', 'FW-IN', 'NRS-TL', 'ABL', 'ABN', 'TO-TL', 'ABX', '*-HL', 'FW-WPS', 'VB-NC', 'HVD*', 'PPS+HVD', 'FW-IN+AT', 'FW-NP', 'QLP', 'FW-NR', 'FW-NN', 'PPS+HVZ', 'NNS-NC', 'DT+BEZ-NC', 'PPO', 'PPO-NC', 'EX-HL', 'AP$', 'OD-NC', 'RP', 'WPS+BEZ', 'NN+BEZ', '.-TL', ',', 'FW-DT+BEZ', 'RB', 'FW-PP$-NC', 'RN', 'JJ$-TL', 'MD-NC', 'VBD-NC', 'PPSS+BER-N', 'RB+BEZ-NC', 'WPS-HL', 'VBN-NC', 'BEZ-HL', 'PPL-NC', 'BER-TL', 'PP$$', 'NNS+MD', 'PPS-NC', 'FW-UH-NC', 'PPS+BEZ-NC', 'PPSS+BER-TL', 'NR-NC', 'FW-JJ', 'PPS+BEZ-HL', 'NPS$', 'RB-TL', 'VB-TL', 'BEM*', 'MD*-HL', 'FW-CC', 'NP+MD', 'EX+HVZ', 'FW-CD', 'EX+HVD', 'IN-HL', 'FW-CS', 'JJR-HL', 'FW-IN+NP-TL', 'JJ-TL-HL', 'FW-UH', 'EX', 'FW-NNS-NC', 'FW-JJ-NC', 'VBZ-HL', 'VB+RP', 'BEZ-NC', 'PPSS+HV-TL', 'HV*', 'IN', 'PP$-NC', 'NP-NC', 'BEN', 'PP$-TL', 'FW-*-TL', 'FW-OD-TL', 'WPS', 'WPO', 'MD+PPSS', 'WDT+BER', 'WDT+BEZ', 'CD-HL', 'WDT+BEZ-NC', 'WP$', 'DO+PPSS', 'HV-HL', 'DT-NC', 'PN-NC', 'FW-VBZ', 'HVD', 'HVG', 'NN+BEZ-TL', 'HVZ', 'FW-VBD', 'FW-VBG', 'NNS$-TL', 'JJ-TL', 'FW-VBN', 'MD-TL', 'WDT+DOD', 'HV-TL', 'NN-TL', 'PPSS', 'NR$', 'BER', 'FW-VB', 'DT', 'PN+BEZ', 'VBG-HL', 'FW-PPL+VBZ', 'FW-NPS-TL', 'RB$', 'FW-IN+NN', 'FW-CC-TL', 'RBT', 'RBR', 'PPS-TL', 'PPSS+HV', 'JJS-TL', 'NPS-HL', 'WPS+BEZ-TL', 'NNS-TL-HL', 'VBN-TL-NC', 'QL-TL', 'NN+NN-NC', 'JJR-TL', 'NN$-TL', 'FW-QL', 'IN-TL', 'BED-NC', 'NRS', '.-HL', 'QL', 'PP$-HL', 'WRB+BER', 'JJ', 'WRB+BEZ', 'NNS$-TL-HL', 'PPSS+BEZ', '(', 'PPSS+BER', 'DT+MD', 'DOZ-TL', 'PPSS+BEM', 'FW-PP$', 'RB+BEZ-HL', 'FW-RB+CC', 'FW-PPS', 'VBG+TO', 'DO*-HL', 'NR+MD', 'PPLS', 'IN+IN', 'BEZ*', 'FW-PPL', 'FW-PPO', 'NNS-HL', 'NIL', 'HVN', 'PPSS+BER-NC', 'AP-TL', 'FW-DT', '(-HL', 'DTI-TL', 'JJ+JJ-NC', 'FW-RB', 'FW-VBD-TL', 'BER-NC', 'NNS$-NC', 'JJ-NC', 'NPS$-TL', 'VB+VB-NC', 'PN', 'VB+TO', 'AT-TL-HL', 'BEM-NC', 'PPL-TL', 'ABN-HL', 'RB-NC', 'DO-NC', 'BE-HL', 'WRB+IN', 'FW-UH-TL', 'PPO-HL', 'FW-CD-TL', 'TO-HL', 'PPS+BEZ', 'CD$', 'DO', 'EX+MD', 'HVZ-TL', 'TO-NC', 'IN-NC', '.', 'WRB+DO', 'CD-NC', 'FW-PPO+IN', 'FW-NN$-TL', 'WDT+BEZ-HL', 'RP-HL', 'CC', 'NN+HVZ-TL', 'FW-NNS-TL', 'DT+BEZ', 'WPS+HVZ', 'BEDZ*', 'NP-TL', ':-TL', 'NN-NC', 'WPO-TL', 'QL-NC', 'FW-AT+NN-TL', 'WDT+HVZ', '.-NC', 'FW-DTS', 'NP-HL', ':-HL', 'RBR-NC', 'OD-HL', 'BEDZ-HL', 'VBD-TL', 'NPS-NC', ')', 'TO+VB', 'FW-IN+NN-TL', 'PPL', 'PPS', 'PPSS+VB', 'DT-TL', 'RP-NC', 'VB', 'FW-VB-TL', 'PP$', 'VBD-HL', 'DTI-HL', 'NN-TL-NC', 'PPL-HL', 'DOZ*', 'NR-TL', 'WRB+MD', 'PN+HVZ', 'FW-IN-TL', 'PN+HVD', 'BEN-TL', 'BE', 'WDT', 'WPS+HVD', 'DO-TL', 'FW-NN-NC', 'WRB+BEZ-TL', 'UH-TL', 'JJR-NC', 'NNS', 'PPSS-NC', 'WPS+BEZ-NC', ',-TL', 'NN$', 'VBN-TL-HL', 'WDT-NC', 'OD', 'FW-OD-NC', 'DOZ*-TL', 'PPSS+HVD', 'CS-TL', 'WRB+DOZ', 'CC-NC', 'HV', 'NN$-HL', 'FW-WDT', 'WRB+DOD', 'NN+HVZ', 'AT-NC', 'NNS-TL', 'FW-BEZ', 'CS-HL', 'WPO-NC', 'FW-BER', 'NNS-TL-NC', 'BEZ-TL', 'FW-IN+AT-T', 'ABN-NC', 'NR-TL-HL', 'BEDZ', 'NP+BEZ', 'FW-AT-TL', 'BER*', 'WPS+MD', 'MD-HL', 'BED*', 'HV-NC', 'WPS-NC', 'VBN-HL', 'FW-TO+VB', 'PPSS+MD-NC', 'HVZ*', 'PPS-HL', 'WRB-NC', 'VBN-TL', 'CD-TL-HL', ',-NC', 'RP-TL', 'AP-HL', 'FW-HV', 'WQL-TL', 'FW-AT', 'NN', 'NR$-TL', 'VBZ-NC', '*', 'PPSS-TL', 'JJT-HL', 'FW-NNS', 'NP', 'UH-HL', 'NR', ':', 'FW-NN$', 'RP+IN', ',-HL', 'JJ-TL-NC', 'AP-NC', '*-NC', 'VB-HL', 'HVZ-NC', 'DTS-HL', 'FW-JJT', 'FW-JJR', 'FW-JJ-TL', 'FW-*', 'RB+BEZ', "''", 'VB+AT', 'PN-HL', 'PPO-TL', 'CD-TL', 'UH-NC', 'FW-NN-TL-NC', 'EX-NC', 'PPSS+BEZ*', 'TO', 'WDT+DO+PPS', 'IN+PPO', 'AP', 'AT', 'DOZ-HL', 'FW-RB-TL', 'CD', 'NN+IN', 'FW-AT-HL', 'PN+MD', "'", 'FW-PP$-TL', 'FW-NPS', 'WDT+BER+PP', 'NN+HVD-TL', 'MD+HV', 'AT-HL', 'FW-IN+AT-TL'])
index 238b0dd..3facf68 100644 (file)
@@ -5,34 +5,57 @@
 # try storing those icharts in some loc_h_dmv global, and see if it's
 # faster using space rather than time.
 
-from common_dmv import MPPROOT, GOR, test, node_str
+from common_dmv import MPPROOT, test, node_str
 from wsjdep import WSJDepCorpusReader
-
+#HARMONIC_C: 509.637290698, FNONSTOP_MIN: 30.1124584139, FSTOP_MIN: 13.0830178845
 def initialize_loc_h(tagonlys):
     import loc_h_harmonic # since we need to change constants (is there a better way?)
-    loc_h_harmonic.HARMONIC_C = 0.0
-    loc_h_harmonic.FNONSTOP_MIN = 25
-    loc_h_harmonic.FSTOP_MIN = 5
-    loc_h_harmonic.RIGHT_FIRST = 1.0 
-    return loc_h_harmonic.initialize(tagonlys)
+    reload(loc_h_harmonic)
+    import random
+#     loc_h_harmonic.HARMONIC_C = 380.111684914
+#     loc_h_harmonic.FSTOP_MIN = 13.5744632704
+#     loc_h_harmonic.FNONSTOP_MIN = 34.8939452454
+    loc_h_harmonic.HARMONIC_C = 0 # 509.63 #1000.0 * random.random()
+    loc_h_harmonic.FSTOP_MIN = 13.08 #20.0 * random.random()
+    loc_h_harmonic.FNONSTOP_MIN = 30.11 #50.0 * random.random() + loc_h_harmonic.FSTOP_MIN
+
+    loc_h_harmonic.RIGHT_FIRST = 1.0
+    loc_h_harmonic.OTHER_STOP_CALC = False
+    print '''
+HARMONIC_C: %s, FNONSTOP_MIN: %s, FSTOP_MIN: %s
+RIGHT_FIRST: %s, OTHER_STOP_CALC: %s'''%(loc_h_harmonic.HARMONIC_C,
+                                         loc_h_harmonic.FNONSTOP_MIN,
+                                         loc_h_harmonic.FSTOP_MIN,
+                                         loc_h_harmonic.RIGHT_FIRST,
+                                         loc_h_harmonic.OTHER_STOP_CALC)
+    g = loc_h_harmonic.initialize(tagonlys)
+    return g
 
 def initialize_cnf(tagonlys):
     import cnf_harmonic # since we need to change constants (is there a better way?)
+    reload(cnf_harmonic)
     cnf_harmonic.HARMONIC_C = 0.0
     cnf_harmonic.FNONSTOP_MIN = 25
     cnf_harmonic.FSTOP_MIN = 5
     return cnf_harmonic.initialize(tagonlys)
     
 
-def test_likelihood(reestimate, initialize, inner_sent, corpus_size=20, corpus_offset=1000):
+def test_likelihood(reestimate, initialize, inner_sent,
+                    corpus_size=20, corpus_offset=1000, iterations=4, eval=False):
     def run_IO(g, iterations, tagonlys, tags_and_parses):
-        print corpus_likelihood(g, tagonlys)
-        # print evaluate(g, tags_and_parses) #
+        sumlog,msg = corpus_likelihood(g, tagonlys)
+        print msg
+        if eval: print evaluate(g, tags_and_parses) 
         for i in range(iterations):
             g = reestimate(g, tagonlys)
             print "reestimation number %d done"%i
-            # print evaluate(g, tags_and_parses) #
-            print corpus_likelihood(g, tagonlys) 
+            if eval: print evaluate(g, tags_and_parses)
+            
+            prev_sumlog = sumlog
+            sumlog,msg = corpus_likelihood(g, tagonlys)
+            if sumlog < prev_sumlog:
+                raise Exception, msg+"but previous was %s"%prev_sumlog
+            print msg
         return g
 
     def corpus_likelihood(g, tagsonly):
@@ -44,7 +67,8 @@ def test_likelihood(reestimate, initialize, inner_sent, corpus_size=20, corpus_o
                 print "%s had zero probability!"%sent
             else:
                 sumlog += log(p_sent)
-        return "Sum of log P_{sentence}: %.4f (should move towards 0)\n"%sumlog
+        avg = sumlog / len(tagsonly)
+        return (sumlog, "Sum of log P_{sentence}: %.4f (should move towards 0), avg: %s\n"%(sumlog,avg))
 
     reader = WSJDepCorpusReader(None)
     tagonlys = reader.tagonly_sents()[corpus_offset:corpus_offset+corpus_size]
@@ -57,7 +81,7 @@ def test_likelihood(reestimate, initialize, inner_sent, corpus_size=20, corpus_o
     g = initialize(tagonlys)
     print "initialized"
     
-    g = run_IO(g, 4, tagonlys, tags_and_parses)
+    g = run_IO(g, iterations, tagonlys, tags_and_parses) # make iterations argument, todo
     return g
 
 
@@ -75,37 +99,46 @@ def evaluate(g, tagged_and_parsed_sents):
     F1 = (2 * P * R)/(P + R), harmonisk snitt av P og R
     '''
     from loc_h_dmv import mpp
+    from wsjdep import add_root
 
-    recall_num = 0
-    recall_den = 0
-    precision_num = 0
-    precision_den = 0
-    
-    for sent, parse in tagged_and_parsed_sents:
+    R, R_r, P, P_r = {}, {}, {}, {}
+    for nd in ['num', 'den']:
+        R[nd], R_r[nd], P[nd], P_r[nd] = 0, 0, 0, 0
+    unrooted = 0 # parses where we couldn't add_root
+
+    for sent, gold_parse in tagged_and_parsed_sents:
         mpp_sent = mpp(g, sent)
-        for pair in parse:
-            recall_den += 1
-            if pair in mpp_sent: recall_num += 1
+        try: gold_parse = add_root(gold_parse)
+        except ValueError: unrooted += 1
+
+        for pair in gold_parse:
+            dict = R
+            if pair[0] == MPPROOT: dict = R_r
+            dict['den'] += 1
+            if pair in mpp_sent: dict['num'] += 1
+
         for pair in mpp_sent:
-            if pair[0] == MPPROOT:
-                continue # todo: add ROOT to parses? (see below)
-            precision_den += 1
-            if pair in parse: precision_num += 1
-
-#             try:
-#                 rooted_parse = add_root(parse) # use? todo
-#             except:
-#                 print "No single possible root, todo what?"
+            dict = P
+            if pair[0] == MPPROOT: dict = P_r
+            dict['den'] += 1
+            if pair in gold_parse: dict['num'] += 1
         
-    recall = float(recall_num) / float(recall_den)
-    precision = float(precision_num) / float(precision_den)
-    F1 = 0.0
+    recall = float(R['num']) / float(R['den'])
+    precision = float(P['num']) / float(P['den'])
+    recall_r = float(R['num']+R_r['num']) / float(R['den']+R_r['den'])
+    precision_r = float(P['num']+P_r['num']) / float(P['den']+P_r['den'])
+    F1, F1_r = 0.0, 0.0
     if (precision + recall) > 0.0:
         F1 = (2 * recall * precision) / (precision + recall)
+    if (precision_r + recall_r) > 0.0:
+        F1_r = (2 * recall_r * precision_r) / (precision_r + recall_r)
 
-    return '''Recall: %d/%d = %.4f
-Precision: %d/%d = %.4f
-F1: \t\t%.4f'''%(recall_num,recall_den,recall,precision_num,precision_den, precision, F1)
+    str_vals = (R['num'],R['den'],recall, R['num']+R_r['num'], R['den']+R_r['den'], recall_r,
+                P['num'],P['den'],precision, P['num']+P_r['num'], P['den']+P_r['den'], precision_r,
+                F1, F1_r, unrooted)
+    return '''Recall: %d/%d = %.4f\tRecall_r: %d/%d = %.4f
+Precision: %d/%d = %.4f\tPrecision_r: %d/%d = %.4f
+F1: \t\t%.4f\t\tF1_r: \t\t%.4f (unrooted gold parses: %d)'''%str_vals
 
 
 
@@ -134,6 +167,7 @@ def compare_loc_h_cnf():
 
     
     import loc_h_dmv, cnf_dmv
+    from common_dmv import GOR
     for sent in tagonlys:
         ochart_l, ochart_c, ichart_l, ichart_c = {},{},{},{}
         i_l = loc_h_dmv.inner_sent(g_l, sent, ichart_l)
@@ -149,27 +183,78 @@ def compare_loc_h_cnf():
 
 # end compare_loc_h_cnf()
 
+
+def init_nothing(g,H,N,S):
+    print '''
+HARMONIC_C: %s, FNONSTOP_MIN: %s, FSTOP_MIN: %s'''%(H,N,S)
+    return lambda corpus:g
+
+def rnd_grammars_test():
+    import loc_h_dmv
+    reload(loc_h_dmv)
+
+    rnd_grammars0 = []
+    for i in xrange(20):
+        g = test_likelihood(loc_h_dmv.reestimate,
+                            initialize_loc_h,
+                            loc_h_dmv.inner_sent,
+                            corpus_size=6268,
+                            iterations=0,
+                            corpus_offset=0,
+                            eval=True)
+        rnd_grammars0 += [(g, g.HARMONIC_C, g.FNONSTOP_MIN, g.FSTOP_MIN)]
+
+    rnd_grammars1 = [(test_likelihood(loc_h_dmv.reestimate,
+                                      init_nothing(g,H,N,S),
+                                      loc_h_dmv.inner_sent,
+                                      corpus_size=6268,
+                                      iterations=1,
+                                      corpus_offset=0,
+                                      eval=True),
+                      H,N,S)
+                    for g,H,N,S in rnd_grammars0]
+    rnd_grammars2 = [(test_likelihood(loc_h_dmv.reestimate,
+                                      init_nothing(g,H,N,S),
+                                      loc_h_dmv.inner_sent,
+                                      corpus_size=6268,
+                                      iterations=1,
+                                      corpus_offset=0,
+                                      eval=True),
+                      H,N,S)
+                    for g,H,N,S in rnd_grammars1]
+
 if __name__ == "__main__":
     print "main.py:"
+    
 #     compare_loc_h_cnf()
 
 #     import cnf_dmv
+#     reload(cnf_dmv)
 #     print "\ntrying cnf-reestimate ##############################"
 #     g = test_likelihood(cnf_dmv.reestimate,
 #                         initialize_cnf,
 #                         cnf_dmv.inner_sent,
-#                         corpus_size=20)
+#                         corpus_size=5,
+#                         iterations=4)
 
     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)
+#     reload(loc_h_dmv)
+#     rnd_grammars_test()
+    print "\ntrying reestimate v.1 ##############################"
+    g = test_likelihood(loc_h_dmv.reestimate,
+                        initialize_loc_h,
+                        loc_h_dmv.inner_sent,
+                        corpus_size=5,
+                        iterations=4,
+                        corpus_offset=0,
+                        eval=True)
+    print g 
+
     print "\ntrying reestimate v.2 ##############################"
     g = test_likelihood(loc_h_dmv.reestimate2,
                         initialize_loc_h,
                         loc_h_dmv.inner_sent,
-                        corpus_size=5)
-
+                        corpus_size=5,
+                        iterations=4,
+                        corpus_offset=0)
     print "main.py: done"
index eeb6a66..8dd59bf 100644 (file)
@@ -1,5 +1,6 @@
 from nltk.corpus.reader.util import *
 from nltk.corpus.reader.bracket_parse import BracketParseCorpusReader
+from common_dmv import MPPROOT
 
 class WSJDepCorpusReader(BracketParseCorpusReader):
     ''' Reader for the dependency parsed WSJ10. Will not include one-word
@@ -160,15 +161,15 @@ def add_root(parse):
     for (head,loc_h) in set([h for h,a in parse]):
         if (head,loc_h) not in set([a for h,a in parse]):
             if rooted:
-                raise ValueError, "Several possible roots in parse"
+                raise ValueError, "Several possible roots in parse: %s"%(list(parse),)
             else:
                 rooted = (head,loc_h)
 
     if not rooted:
         raise ValueError, "No root in parse!"
-
-    parse.add( (('ROOT',-1), rooted) )
-    return parse 
+    
+    rootpair = (MPPROOT, rooted)
+    return parse.union(set([ rootpair ]))
 
 if __name__ == "__main__":
     print "WSJDepCorpusReader tests:"
dissimilarity index 72%
index 86b7012..7840131 100644 (file)
Binary files a/tex/formulas.pdf and b/tex/formulas.pdf differ
index e8d3c4a..b1be8f3 100644 (file)
@@ -1,4 +1,7 @@
 % Created 2008-06-13 Fri 17:05
+
+% todo: fix stop and attachment formulas so they divide before summing
+
 \documentclass[11pt,a4paper]{article}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
@@ -170,10 +173,13 @@ of having a stop above, where we use $\SEAL{w}$:
 % todo: left out rule-probability! wops (also, make P_{fooside}
 % sentence-specific)
 
-$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}:
+$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}\footnote{In terms of regular EM,
+  this is the count of trees ($f_{T_q}(x)$ in
+  \citet[p.~46]{prescher-em}) in which the node extended from $i$ to
+  $j$.}:
 \begin{align*}
   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*}
@@ -219,22 +225,14 @@ this is implicit in $P_{INSIDE}$.
 
 
 \begin{align*}
-  \hat{P}_{CHOOSE} (a | h, left) = \frac
-  { \hat{a} (a | \GOL{h}, left) }
-  { \sum_{w} \hat{a} (w | \GOL{h}, left) }
-  +
-  \frac
-  { \hat{a} (a | \RGOL{h}, left) }
-  { \sum_{w} \hat{a} (w | \RGOL{h}, left) }
+  \hat{P}_{CHOOSE} (a | h, left) = 
+  \hat{a} (a | \GOL{h}, left) 
+  + \hat{a} (a | \RGOL{h}, left) 
 \end{align*}
 \begin{align*}
-  \hat{P}_{CHOOSE} (a | h, right) = \frac
-  { \hat{a} (a | \GOR{h},right) }
-  { \sum_{w} \hat{a} (w | \GOR{h},right) }
-  +
-  \frac
-  { \hat{a} (a | \LGOR{h},right) }
-  { \sum_{w} \hat{a} (w | \LGOR{h},right) }
+  \hat{P}_{CHOOSE} (a | h, right) = 
+  \hat{a} (a | \GOR{h},right) 
+  + \hat{a} (a | \LGOR{h},right) 
 \end{align*}
 
 \subsection{Stop reestimation} 
@@ -275,13 +273,45 @@ Then these are our reestimated stop probabilities:
 \end{align*}
 
 
-\subsection{Root reestimation} % todo grok: no \sum_{i} \sum_{j} ? 
+\subsection{Root reestimation} 
+Following \citet[p.~46]{prescher-em}, to find the reestimated
+probability of a PCFG rule, we first find the new treebank frequencies
+$f_{T_P}(tree)=P(tree)/P_s$, then for a rule $X' \rightarrow X$ we
+divide the new frequencies of the trees which use this rule and by
+those of the trees containing the node $X'$. $ROOT$ appears once per
+tree, meaning we divide by $1$ per sentence\footnote{Assuming each
+  tree has frequency $1$.}, so $\hat{P}_{ROOT}(h)=\sum_{tree:ROOT
+  \rightarrow \SEAL{h} \text{ used in } tree} f_{T_P}(tree)=\sum_{tree:ROOT
+  \rightarrow \SEAL{h} \text{ used in } tree} P(tree)/P_s$, which turns into:
+
 \begin{align*}
   \hat{P}_{ROOT} (h) = \frac
-  {\sum_{s\in S} P_{ROOT}(h) P_{INSIDE_s}(\SEAL{h}, 0, len(s)) }
-  {\sum_{s\in S} P_s}
+  {\sum_{s\in S} 1 / P_s \cdot \sum_{\LOC{h}\in s} P_{ROOT}(\LOC{h}) P_{INSIDE_s}(\SEAL{h}, 0, len(s))}
+  {\sum_{s\in S} 1}
 \end{align*}
 
+% todo: the following just didn't turn out right, but it ought to be
+% possible to use this to check the CNF-like unary attachments...
+%
+% The root attachment is just a unary PCFG rule $ROOT \rightarrow
+% \SEAL{h}$. Modifiying binary rule reestimation from
+% \citet[p.~41]{lari-csl90} to unary rules gives:
+
+% \begin{align*}
+%   \hat{P}_{RULE}(ROOT \rightarrow \SEAL{h}) = \frac
+%   { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} 1/P_s \cdot P_{RULE}(ROOT \rightarrow \SEAL{h})P_{INSIDE_s}(\SEAL{h}, i, j)P_{OUTSIDE_s}(ROOT, i, j) }
+%   { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} c_s(\SEAL{h}, i, j) }
+% \end{align*}
+
+% Since $P_{OUTSIDE}(ROOT, i, j)$ is $1$ if $i=0$ and $j=len(s)$, and $0$ otherwise, this reduces into:
+
+% \begin{align*}
+%   \hat{P}_{RULE}(ROOT \rightarrow \SEAL{h}) = \frac
+%   { \sum_{s\in S} 1/P_s \cdot P_{RULE}(ROOT \rightarrow \SEAL{h})P_{INSIDE_s}(\SEAL{h}, 0, len(s)) }
+%   { \sum_{s\in S} 1/P_s \cdot P_{INSIDE_s}(\SEAL{h}, 0, len(s)) }
+% \end{align*}
+
+