started on pure cnf version, see sec6 of formulas.pdf
authorKevin Brubeck Unhammer <pixiemotion@gmail.com>
Fri, 29 Aug 2008 13:58:48 +0000 (29 15:58 +0200)
committerKevin Brubeck Unhammer <pixiemotion@gmail.com>
Fri, 29 Aug 2008 13:58:48 +0000 (29 15:58 +0200)
DMVCCM.html
DMVCCM.org
src/pcnf_dmv.py [new file with mode: 0755]
src/pcnf_harmonic.py [new file with mode: 0644]
tex/compile.sh
tex/formulas.pdf
tex/formulas.tex

index d3f6766..9f31d4b 100755 (executable)
@@ -6,9 +6,30 @@ 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/21 16:39:45"/>
+<meta name="generated" content="2008-08-29 15:41:07 CEST"/>
 <meta name="author" content="Kevin Brubeck Unhammer"/>
-<link rel="stylesheet" type="text/css" href="http://www.student.uib.no/~kun041/org.css">
+<style type="text/css">
+  html { font-family: Times, serif; font-size: 12pt; }
+  .title  { text-align: center; }
+  .todo   { color: red; }
+  .done   { color: green; }
+  .tag    { background-color:lightblue; font-weight:normal }
+  .target { }
+  .timestamp { color: grey }
+  .timestamp-kwd { color: CadetBlue }
+  p.verse { margin-left: 3% }
+  pre {
+       border: 1pt solid #AEBDCC;
+       background-color: #F3F5F7;
+       padding: 5pt;
+       font-family: courier, monospace;
+        font-size: 90%;
+        overflow:auto;
+  }
+  table { border-collapse: collapse; }
+  td, th { vertical-align: top; }
+  dt { font-weight: bold; }
+</style><link rel="stylesheet" type="text/css" href="http://www.student.uib.no/~kun041/org.css">
 <!-- override with local style.css: -->
 <link rel="stylesheet" type="text/css" href="./style.css">
 </head><body>
@@ -26,7 +47,7 @@ lang="en" xml:lang="en">
 </li>
 <li><a href="#sec-4">4 [#C] Alternative CNF for DMV</a>
 <ul>
-<li><a href="#sec-4.1">4.1 [#A] Make and implement an equivalent grammar that's really CNF</a></li>
+<li><a href="#sec-4.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>
@@ -116,7 +137,7 @@ DMV-<a href="tex/formulas.pdf">formulas.pdf</a>  &ndash; <i>clear</i> informatio
 <h2 id="sec-2">2 Notation</h2>
 <div id="text-2">
 
-<p><pre>
+<p><pre class="example">
  old notes:   new notes:   in tex/code (constants):    in Klein thesis:
 --------------------------------------------------------------------------------------
  _h_            _h_            SEAL                    bar over h
@@ -132,7 +153,7 @@ integer (POS-tag) and <code>s_h</code> &isin; <code>{SEAL,RGOL,GOR,LGOR,GOL}</co
 <p>
 <code>P_ATTACH</code> and <code>P_CHOOSE</code> are synonymous, I try to use the
 former. Also, 
-<pre>
+<pre class="example">
  P_GO_AT(a|h,dir,adj) := P_ATTACH(a|h,dir)*(1-P_STOP(STOP|h,dir,adj)
 </pre>
 </p>
@@ -196,7 +217,7 @@ Only <code>sents()</code>, <code>tagged_sents()</code> and <code>parsed_sents()<
 </p>
 <p>
 Given a grammar with certain p_ATTACH, p_STOP and p_ROOT, we get:
-<pre>
+<pre class="example">
 &gt;&gt;&gt; print testgrammar_h():
   h&gt;&lt; --&gt;   h&gt;  STOP   [0.30]
   h&gt;&lt; --&gt;  &gt;h&gt;  STOP   [0.40]
@@ -213,12 +234,65 @@ 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 really CNF</h3>
+<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">
 
 <p>&hellip;since I'm not sure about my unary reestimation rules (section 5 of
 <a href="tex/formulas.pdf">formulas</a>).
-</p></div>
+</p>
+<p>
+For any rule where LHS is <code>_h_</code> we also have a corresponding one with
+LHS <code>ROOT</code>, only difference being that we multiply in <code>p_ROOT(h)</code>.
+</p>
+<p>
+For any rule where LHS is <code>.h&gt;</code>, we use adjacent probabilities for the
+left child; if LHS is <code>&lt;h.</code> we use adjacent probabilities for the right
+child. Only <code>_h_</code> and <code>_h&gt;_</code> (plus <code>ROOT</code>) get to introduce the pre-terminal
+<code>h</code> (where <code>h</code>, <code>ROOT</code> and <code>_h_</code> all rewrite to the terminal
+<code>'h'</code>), and only <code>_h_</code> and <code>_h&gt;_</code> (plus <code>ROOT</code>) act as STOP
+rules (eg. get to multiply in <code>p(STOP)</code>).
+</p>
+<p>
+<pre class="example">
+  h   --&gt;  'h'         1
+ _h_  --&gt;  'h'         p(STOP|h,L,adj) * p(STOP|h,R,adj)
+ ROOT --&gt;  'h'         p(STOP|h,L,adj) * p(STOP|h,R,adj) * p_ROOT(h)
+
+ _h_  --&gt;   h    _a_   p(STOP|h,L,adj) * p(STOP|h,R,non) * p(a|h,R)*p(-STOP|h,R,adj)
+ _h_  --&gt;   h    .h&gt;   p(STOP|h,L,adj) * p(STOP|h,R,non) 
+ .h&gt;  --&gt;  _a_   _b_   p(a|h,R)*p(-STOP|h,R,adj) * p(b|h,R)*p(-STOP|h,R,non)
+ .h&gt;  --&gt;  _a_    h&gt;   p(a|h,R)*p(-STOP|h,R,adj) 
+  h&gt;  --&gt;  _a_   _b_   p(a|h,R)*p(-STOP|h,R,non) * p(b|h,R)*p(-STOP|h,R,non)
+  h&gt;  --&gt;  _a_    h&gt;   p(a|h,R)*p(-STOP|h,R,non) 
+
+ _h_  --&gt;  _a_    h    p(STOP|h,L,non) * p(STOP|h,R,adj) * p(a|h,L)*p(-STOP|h,L,adj)
+ _h_  --&gt;  &lt;h.    h    p(STOP|h,L,non) * p(STOP|h,R,adj) 
+ &lt;h.  --&gt;  _b_   _a_   p(b|h,L)*p(-STOP|h,L,non) * p(a|h,L)*p(-STOP|h,L,adj)
+ &lt;h.  --&gt;  &lt;h    _a_                               p(a|h,L)*p(-STOP|h,L,adj) 
+ &lt;h   --&gt;  _a_   _b_   p(a|h,L)*p(-STOP|h,L,non) * p(b|h,L)*p(-STOP|h,L,non)
+ &lt;h   --&gt;  &lt;h    _a_   p(a|h,L)*p(-STOP|h,L,non) 
+
+ _h_  --&gt;  &lt;h.    _h&gt;_ p(STOP|h,L,non)
+ _h_  --&gt;  _a_    _h&gt;_ p(STOP|h,L,non) * p(a|h,L)*p(-STOP|h,L,adj)
+ _h&gt;_ --&gt;   h     .h&gt;  p(STOP|h,R,non) 
+ _h&gt;_ --&gt;   h     _a_  p(STOP|h,R,non) * p(a|h,R)*p(-STOP|h,R,adj)
+
+ ROOT --&gt;   h    _a_   p(STOP|h,L,adj) * p(STOP|h,R,non) * p(a|h,R)*p(-STOP|h,R,adj) * p_ROOT(h)
+ ROOT --&gt;   h    .h&gt;   p(STOP|h,L,adj) * p(STOP|h,R,non) * p_ROOT(h)
+
+ ROOT --&gt;  _a_    h    p(STOP|h,L,non) * p(STOP|h,R,adj) * p(a|h,L)*p(-STOP|h,L,adj) * p_ROOT(h)
+ ROOT --&gt;  &lt;h.    h    p(STOP|h,L,non) * p(STOP|h,R,adj) * p_ROOT(h)
+
+ ROOT --&gt;  &lt;h.   _h&gt;_  p(STOP|h,L,non) * p_ROOT(h)
+ ROOT --&gt;  _a_   _h&gt;_  p(STOP|h,L,non) * p(a|h,L)*p(-STOP|h,L,adj) * p_ROOT(h)
+
+</pre>
+</p>
+<p>
+Since we have rules rewriting <code>h</code> to <code>a</code> and <code>b</code>, we have a rule-set
+numbering more than n<sub>tags</sub><sup>2</sup>.
+</p>
+</div>
 
 </div>
 
@@ -343,7 +417,7 @@ adding the <code>L</code> and <code>R</code> keys of any entry to the queue as w
 (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>
+<pre class="example">
  set([( ROOT, (vbd,2),RIGHT),
       ((vbd,2),(nn,1),LEFT),
       ((vbd,2),(nn,3),RIGHT),
@@ -437,7 +511,7 @@ section, but that would only have an effect on very short sentences).
 dependency between the modules. Guess there could be a third file that
 imports both the initialization and the actual EM stuff, while a file
 containing constants and classes could be imported by all others:
-<pre>
+<pre class="example">
  dmv.py imports dmv_EM.py imports dmv_classes.py
  dmv.py imports dmv_inits.py imports dmv_classes.py
 </pre>
@@ -523,7 +597,7 @@ P_STOP reestimation.
 <div id="text-11">
 
 <p>Make those debug statements steal a bit less attention in emacs:
-<pre>
+<pre class="example">
 (font-lock-add-keywords
  'python-mode                   ; not really regexp, a bit slow
  '(("^\\( *\\)\\(\\if +'.+' +in +io.DEBUG. *\\(
@@ -562,7 +636,7 @@ P_STOP reestimation.
 </p>
 <p>
 Setting up a new project:
-<pre>
+<pre class="example">
  git init
  git add .
  git commit -m "first release"
@@ -570,14 +644,14 @@ Setting up a new project:
 </p>
 <p>
 Later on: (<code>-a</code> does <code>git rm</code> and <code>git add</code> automatically)
-<pre>
+<pre class="example">
  git init
  git commit -a -m "some subsequent release"
 </pre>
 </p>
 <p>
 Then push stuff up to the remote server:
-<pre>
+<pre class="example">
  git push git+ssh://username@repo.or.cz/srv/git/dmvccm.git master
 </pre>
 </p>
@@ -587,32 +661,32 @@ the time)
 </p>
 <p>
 Make a copy of the (remote) master branch:
-<pre>
+<pre class="example">
  git clone git://repo.or.cz/dmvccm.git 
 </pre>
 </p>
 <p>
 Make and name a new branch in this folder
-<pre>
+<pre class="example">
  git checkout -b mybranch
 </pre>
 </p>
 <p>
 To save changes in <code>mybranch</code>:
-<pre>
+<pre class="example">
  git commit -a 
 </pre>
 </p>
 <p>
 Go back to the master branch (uncommitted changes from <code>mybranch</code> are
 carried over):
-<pre>
+<pre class="example">
  git checkout master
 </pre>
 </p>
 <p>
 Try out:
-<pre>
+<pre class="example">
  git add --interactive
 </pre>
 </p>
@@ -624,7 +698,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/21 16:39:45</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>
index edbe3d8..8bbe9af 100755 (executable)
@@ -131,18 +131,51 @@ Given a grammar with certain p_ATTACH, p_STOP and p_ROOT, we get:
 ...since I'm not sure about my unary reestimation rules (section 5 of
 [[file:tex/formulas.pdf][formulas]]).
 
-:  h>< -->   h>  STOP 
-:  h>< -->  >h>  STOP 
-: _h_  --> STOP    h><
-: _h_  --> STOP   <h><
-: >h>  -->   h>   _a_ 
-: >h>  -->  >h>   _a_ 
-: <h>< -->  _a_    h><
-: <h>< -->  _a_   <h><
-: ROOT -->  _a_   <h>< p_ROOT(h) * p_ATTACH(a|h,L) 
-: ROOT -->  _a_    h>  p_ROOT(h) * p_ATTACH(a|h,R) 
-: ROOT -->   h         p_ROOT(h)
+For any rule where LHS is =_h_= we also have a corresponding one with
+LHS =ROOT=, only difference being that we multiply in =p_ROOT(h)=.
+
+For any rule where LHS is =.h>=, we use adjacent probabilities for the
+left child; if LHS is =<h.= we use adjacent probabilities for the right
+child. Only =_h_= and =_h>_= (plus =ROOT=) get to introduce the pre-terminal
+=h= (where =h=, =ROOT= and =_h_= all rewrite to the terminal
+@<code>'h'@</code>), and only =_h_= and =_h>_= (plus =ROOT=) act as STOP
+rules (eg. get to multiply in =p(STOP)=).
+
+:  h   -->  'h'         1
+: _h_  -->  'h'         p(STOP|h,L,adj) * p(STOP|h,R,adj)
+: ROOT -->  'h'         p(STOP|h,L,adj) * p(STOP|h,R,adj) * p_ROOT(h)
+:
+: _h_  -->   h    _a_   p(STOP|h,L,adj) * p(STOP|h,R,non) * p(a|h,R)*p(-STOP|h,R,adj)
+: _h_  -->   h    .h>   p(STOP|h,L,adj) * p(STOP|h,R,non) 
+: .h>  -->  _a_   _b_   p(a|h,R)*p(-STOP|h,R,adj) * p(b|h,R)*p(-STOP|h,R,non)
+: .h>  -->  _a_    h>   p(a|h,R)*p(-STOP|h,R,adj) 
+:  h>  -->  _a_   _b_   p(a|h,R)*p(-STOP|h,R,non) * p(b|h,R)*p(-STOP|h,R,non)
+:  h>  -->  _a_    h>   p(a|h,R)*p(-STOP|h,R,non) 
+:
+: _h_  -->  _a_    h    p(STOP|h,L,non) * p(STOP|h,R,adj) * p(a|h,L)*p(-STOP|h,L,adj)
+: _h_  -->  <h.    h    p(STOP|h,L,non) * p(STOP|h,R,adj) 
+: <h.  -->  _b_   _a_   p(b|h,L)*p(-STOP|h,L,non) * p(a|h,L)*p(-STOP|h,L,adj)
+: <h.  -->  <h    _a_                               p(a|h,L)*p(-STOP|h,L,adj) 
+: <h   -->  _a_   _b_   p(a|h,L)*p(-STOP|h,L,non) * p(b|h,L)*p(-STOP|h,L,non)
+: <h   -->  <h    _a_   p(a|h,L)*p(-STOP|h,L,non) 
+:
+: _h_  -->  <h.    _h>_ p(STOP|h,L,non)
+: _h_  -->  _a_    _h>_ p(STOP|h,L,non) * p(a|h,L)*p(-STOP|h,L,adj)
+: _h>_ -->   h     .h>  p(STOP|h,R,non) 
+: _h>_ -->   h     _a_  p(STOP|h,R,non) * p(a|h,R)*p(-STOP|h,R,adj)
+:
+: ROOT -->   h    _a_   p(STOP|h,L,adj) * p(STOP|h,R,non) * p(a|h,R)*p(-STOP|h,R,adj) * p_ROOT(h)
+: ROOT -->   h    .h>   p(STOP|h,L,adj) * p(STOP|h,R,non) * p_ROOT(h)
+:
+: ROOT -->  _a_    h    p(STOP|h,L,non) * p(STOP|h,R,adj) * p(a|h,L)*p(-STOP|h,L,adj) * p_ROOT(h)
+: ROOT -->  <h.    h    p(STOP|h,L,non) * p(STOP|h,R,adj) * p_ROOT(h)
+:
+: ROOT -->  <h.   _h>_  p(STOP|h,L,non) * p_ROOT(h)
+: ROOT -->  _a_   _h>_  p(STOP|h,L,non) * p(a|h,L)*p(-STOP|h,L,adj) * p_ROOT(h)
+:
 
+Since we have rules rewriting =h= to =a= and =b=, we have a rule-set
+numbering more than n_{tags}^{2}.
 
 ** TOGROK [#A] convert L&Y-based reestimation into P_ATTACH and P_STOP values
 Sum over the various rules? Or something? Must think of this.
diff --git a/src/pcnf_dmv.py b/src/pcnf_dmv.py
new file mode 100755 (executable)
index 0000000..5bdbff7
--- /dev/null
@@ -0,0 +1,520 @@
+# pcnf_dmv.py
+
+#import numpy # numpy provides Fast Arrays, for future optimization
+import io
+
+from common_dmv import *
+SEALS = [GOR, RGOL, SEAL, NGOR, NRGOL] # overwriting here
+
+
+if __name__ == "__main__":
+    print "pcnf_dmv module tests:"
+
+def make_GO_AT(p_STOP,p_ATTACH):
+    p_GO_AT = {}
+    for (a,h,dir), p_ah in p_ATTACH.iteritems():
+        p_GO_AT[a,h,dir, NON] = p_ah * (1-p_STOP[h, dir, NON])
+        p_GO_AT[a,h,dir, ADJ] = p_ah * (1-p_STOP[h, dir, ADJ])
+    return p_GO_AT
+
+class PCNF_DMV_Grammar(io.Grammar):
+    '''The DMV-PCFG.
+
+    Public members:
+    p_STOP, p_ROOT, p_ATTACH, p_terminals
+    These are changed in the Maximation step, then used to set the
+    new probabilities of each PCNF_DMV_Rule.
+
+    __p_rules is private, but we can still say stuff like:
+    for r in g.all_rules():
+        r.prob = (1-p_STOP[...]) * p_ATTACH[...]
+    '''
+    def __str__(self):
+        str = ""
+        for r in self.all_rules():
+            str += "%s\n" % r.__str__(self.numtag)
+        return str
+
+    def LHSs(self):
+        return [ROOT] + [(s_h,h)
+                         for h in self.headnums()
+                         for s_h in SEALS]
+    
+    def sent_rules(self, sent_nums):
+        sent_nums_stop = sent_nums + [POS(STOP)]
+        return [ r for LHS in self.LHSs()
+                   for r in self.arg_rules(LHS, sent_nums)
+                 if  POS(r.L()) in sent_nums_stop
+                 and POS(r.R()) in sent_nums_stop ]
+
+    # used in outer:
+    def mothersR(self, w_node, argnums):
+        '''For all LHS and x, return all rules of the form 'LHS->x w_node'.'''
+        if w_node not in self.__mothersR:
+            self.__mothersR[w_node] = [r for LHS in self.LHSs()
+                                       for r in self.rules(LHS)
+                                       if r.R() == w_node]
+        argnums.append(POS(STOP))
+        return [r for r in self.__mothersR[w_node]
+                if POS(r.L()) in argnums]
+
+    def mothersL(self, w_node, argnums):
+        '''For all LHS and x, return all rules of the form 'LHS->w_node x'.'''
+        if w_node not in self.__mothersL:
+            self.__mothersL[w_node] = [r for LHS in self.LHSs()
+                                       for r in self.rules(LHS)
+                                       if r.L() == w_node] 
+        argnums.append(POS(STOP))
+        return [r for r in self.__mothersL[w_node]
+                if POS(r.R()) in argnums]
+
+    
+    # used in inner:
+    def arg_rules(self, LHS, argnums):
+        return [r for r in self.rules(LHS)
+                if (POS(r.R()) in argnums
+                    or POS(r.L()) in argnums)]
+
+
+    def make_all_rules(self):
+        self.new_rules([r for LHS in self.LHSs()
+                        for r in self._make_rules(LHS, self.headnums())])
+
+    def _make_rules(self, LHS, argnums):
+        '''This is where the PCNF grammar is defined. Also, s_dir_typ shows how
+        useful it'd be to split up the seals into direction and
+        type... todo?'''
+        h = POS(LHS)
+        if LHS == ROOT:
+            return [PCNF_DMV_Rule(LEFT, LHS, (SEAL,h), STOP, self.p_ROOT[h])
+                    for h in set(argnums)]
+        s_h = seals(LHS)
+        if s_h == GOR:
+            return [] # only terminals from here on
+        s_dir_type = {  # seal of LHS
+            RGOL: (RIGHT, 'STOP'), NGOR:  (RIGHT, 'ATTACH'),
+            SEAL: (LEFT, 'STOP'),  NRGOL: (LEFT, 'ATTACH')  }
+        dir_s_adj = { # seal of h_daughter
+            RIGHT: [(GOR, True),(NGOR, False)] ,
+            LEFT:  [(RGOL,True),(NRGOL,False)] }
+        dir,type = s_dir_type[s_h]
+        rule = {
+            'ATTACH': [PCNF_DMV_Rule(dir, LHS, (s, h), (SEAL,a), self.p_GO_AT[a,h,dir,adj])
+                       for a in set(argnums) if (a,h,dir) in self.p_ATTACH
+                       for s, adj in dir_s_adj[dir]] ,
+            'STOP':   [PCNF_DMV_Rule(dir, LHS, (s, h), STOP, self.p_STOP[h,dir,adj])
+                       for s, adj in dir_s_adj[dir]] }
+        return rule[type]
+        
+
+    def __init__(self, numtag, tagnum, p_ROOT, p_STOP, p_ATTACH, p_terminals):
+        io.Grammar.__init__(self, numtag, tagnum, [], p_terminals)
+        self.p_STOP = p_STOP
+        self.p_ATTACH = p_ATTACH
+        self.p_ROOT = p_ROOT
+        self.p_GO_AT = make_GO_AT(self.p_STOP, self.p_ATTACH)
+        self.make_all_rules()
+        self.__mothersL = {}
+        self.__mothersR = {}
+        
+
+class PCNF_DMV_Rule(io.PCNF_Rule):
+    '''A single PCNF rule in the PCFG, of the form 
+    LHS -> L R
+    where LHS, L and R are 'nodes', eg. of the form (seals, head).
+    
+    Public members:
+    prob
+    
+    Private members:
+    __L, __R, __LHS
+    
+    Different rule-types have different probabilities associated with
+    them, see formulas.pdf
+    '''
+    def seals(self):
+        return seals(self.LHS())
+    
+    def POS(self):
+        return POS(self.LHS())
+    
+    def __init__(self, dir, LHS, h_daughter, a_daughter, prob):
+        self.__dir = dir
+        if dir == LEFT:
+            L, R = a_daughter, h_daughter
+        elif dir == RIGHT:
+            L, R = h_daughter, a_daughter
+        else:
+            raise ValueError, "dir must be LEFT or RIGHT, given: %s"%dir
+        for b_h in [LHS, L, R]:
+            if seals(b_h) not in SEALS:
+                raise ValueError("seals must be in %s; was given: %s"
+                                 % (SEALS, seals(b_h)))
+        io.PCNF_Rule.__init__(self, LHS, L, R, prob)
+    
+    def adj(self):
+        "'undefined' for ROOT"
+        if self.__dir == LEFT:
+            return seals(self.R()) == RGOL
+        else: # RIGHT
+            return seals(self.L()) == GOR
+
+    def __str__(self, tag=lambda x:x):
+        if self.adj(): adj_str = "adj"
+        else: adj_str = "non_adj"
+        if self.LHS() == ROOT: adj_str = ""
+        return "%s --> %s %s\t[%.2f] %s" % (node_str(self.LHS(), tag),
+                                            node_str(self.L(), tag),
+                                            node_str(self.R(), tag),
+                                            self.prob,
+                                            adj_str)
+    
+
+    
+
+
+
+
+###################################
+# dmv-specific version of inner() #
+###################################
+def inner(i, j, LHS, g, sent, ichart={}):
+    ''' A PCNF rewrite of io.inner(), to take STOP rules into accord. '''
+    def O(i,j):
+        return sent[i]
+    
+    sent_nums = g.sent_nums(sent)
+    
+    def e(i,j,LHS, n_t):
+        def tab():
+            "Tabs for debug output"
+            return "\t"*n_t
+        if (i, j, LHS) in ichart:
+            if 'INNER' in DEBUG:
+                print "%s*= %.4f in ichart: i:%d j:%d LHS:%s" % (tab(), ichart[i, j, LHS], i, j, node_str(LHS))
+            return ichart[i, j, LHS]
+        else:
+            # if seals(LHS) == RGOL then we have to STOP first
+            if i == j-1 and seals(LHS) == GOR:
+                if (LHS, O(i,j)) in g.p_terminals:
+                    prob = g.p_terminals[LHS, O(i,j)] # "b[LHS, O(s)]" in Lari&Young
+                else:
+                    prob = 0.0 
+                    if 'INNER' in DEBUG:
+                        print "%sLACKING TERMINAL:" % tab()
+                if 'INNER' in DEBUG:
+                    print "%s*= %.4f (terminal: %s -> %s)" % (tab(),prob, node_str(LHS), O(i,j)) 
+                return prob
+            else:
+                p = 0.0 # "sum over j,k in a[LHS,j,k]"
+                for rule in g.arg_rules(LHS, sent_nums): 
+                    if 'INNER' in DEBUG:
+                        print "%ssumming rule %s i:%d j:%d" % (tab(),rule,i,j)
+                    L = rule.L()
+                    R = rule.R()
+                    # if it's a STOP rule, rewrite for the same xrange:
+                    if (L == STOP) or (R == STOP):
+                        if L == STOP:
+                            pLR = e(i, j, R, n_t+1)
+                        elif R == STOP:
+                            pLR = e(i, j, L, n_t+1)
+                        p += rule.p() * pLR
+                        if 'INNER' in DEBUG:
+                            print "%sp= %.4f (STOP)" % (tab(), p) 
+                            
+                    elif j > i+1 and seals(LHS) != GOR:
+                        # not a STOP, attachment rewrite:
+                        for k in xtween(i, j): # i<k<j
+                            p_L = e(i, k, L, n_t+1)
+                            p_R = e(k, j, R, n_t+1)
+                            p += rule.p() * p_L * p_R
+                            if 'INNER' in DEBUG:
+                                print "%sp= %.4f (ATTACH, p_L:%.4f, p_R:%.4f, rule:%.4f)" % (tab(), p,p_L,p_R,rule.p()) 
+                ichart[i, j, LHS] = p
+                return p
+    # end of e-function
+            
+    inner_prob = e(i,j,LHS, 0)
+    if 'INNER' in DEBUG:
+        print debug_ichart(g,sent,ichart)
+    return inner_prob
+# end of pcnf_dmv.inner(i, j, LHS, g, sent, ichart={})
+
+
+def debug_ichart(g,sent,ichart):
+    str = "---ICHART:---\n"
+    for (i,j,LHS),v in ichart.iteritems():
+        if type(v) == dict: # skip 'tree'
+            continue
+        str += "%s -> %s ... %s: \t%.4f\n" % (node_str(LHS,g.numtag),
+                                              sent[i], sent[j-1], v)
+    str += "---ICHART:end---\n"
+    return str
+
+
+def inner_sent(g, sent, ichart={}):
+    return sum([inner(0, len(sent), ROOT, g, sent, ichart)]) 
+
+
+#######################################
+# pcnf_dmv-specific version of outer() # 
+#######################################
+def outer(i,j,w_node, g, sent, ichart={}, ochart={}):
+    def e(i,j,LHS):
+        # or we could just look it up in ichart, assuming ichart to be done
+        return inner(i, j, LHS, g, sent, ichart)
+    
+    sent_nums = g.sent_nums(sent)
+    if POS(w_node) not in sent_nums[i:j]:
+        # sanity check, w must be able to dominate sent[i:j]
+        return 0.0
+    
+    def f(i,j,w_node):
+        if (i,j,w_node) in ochart:
+            return ochart[(i, j, w_node)]
+        if w_node == ROOT:
+            if i == 0 and j == len(sent):
+                return 1.0
+            else: # ROOT may only be used on full sentence
+                return 0.0 # but we may have non-ROOTs over full sentence too
+
+        p = 0.0
+
+        for rule in g.mothersL(w_node, sent_nums): # rule.L() == w_node
+            if 'OUTER' in DEBUG: print "w_node:%s (L) ; %s"%(node_str(w_node),rule)
+            if rule.R() == STOP:
+                p0 = f(i,j,rule.LHS()) * rule.p()
+                if 'OUTER' in DEBUG: print p0
+                p += p0
+            else:
+                for k in xgt(j,sent): # i<j<k
+                    p0 = f(i,k, rule.LHS() ) * rule.p() * e(j,k, rule.R() )
+                    if 'OUTER' in DEBUG: print p0
+                    p += p0        
+
+        for rule in g.mothersR(w_node, sent_nums): # rule.R() == w_node
+            if 'OUTER' in DEBUG: print "w_node:%s (R) ; %s"%(node_str(w_node),rule)
+            if rule.L() == STOP:
+                p0 = f(i,j,rule.LHS()) * rule.p()
+                if 'OUTER' in DEBUG: print p0
+                p += p0
+            else:
+                for k in xlt(i): # k<i<j
+                    p0 = e(k,i, rule.L() ) * rule.p() * f(k,j, rule.LHS() )
+                    if 'OUTER' in DEBUG: print p0
+                    p += p0
+
+        ochart[i,j,w_node] = p
+        return p
+
+    
+    return f(i,j,w_node)
+# end outer(i,j,w_node, g,sent, ichart,ochart)
+
+
+
+##############################
+#      reestimation, todo:   #
+##############################
+def reest_zeros(rules):
+    f = { ('den',ROOT) : 0.0 }
+    for r in rules:
+        for nd in ['num','den']:
+            f[nd, r.LHS(), r.L(), r.R()] = 0.0
+    return f
+
+def reest_freq(g, corpus):
+    ''' P_STOP(-STOP|...) = 1 - P_STOP(STOP|...) '''
+    f = reest_zeros(g.all_rules())
+    ichart = {}
+    ochart = {}
+    
+    p_sent = None # 50 % speed increase on storing this locally
+
+    def c_g(i,j,LHS,sent): 
+        if p_sent == 0.0:
+            return 0.0
+        return e_g(i,j,LHS,sent) * f_g(i,j,LHS,sent) / p_sent
+        
+    def w1_g(i,j,rule,sent): # unary (stop) rules, LHS -> child_node
+        if   rule.L() == STOP: child = rule.R()
+        elif rule.R() == STOP: child = rule.L()
+        else: raise ValueError, "expected a stop rule: %s"%(rule,)
+
+        if p_sent == 0.0: return 0.0
+        
+        p_out = f_g(i,j,rule.LHS(),sent)
+        if p_out == 0.0: return 0.0
+        
+        return rule.p() * e_g(i,j,child,sent) * p_out / p_sent
+
+    def w_g(i,j,rule,sent):
+        if p_sent == 0.0 or i+1 == j: return 0.0
+        
+        p_out = f_g(i,j,rule.LHS(),sent)
+        if p_out == 0.0: return 0.0
+        
+        p = 0.0
+        for k in xtween(i,j):
+            p += rule.p() * e_g(i,k,rule.L(),sent) * e_g(k,j,rule.R(),sent) * p_out
+        return p / p_sent
+
+    def f_g(i,j,LHS,sent): 
+        if (i,j,LHS) in ochart:
+#             print ".",
+            return ochart[i,j,LHS]
+        else:
+            return outer(i,j,LHS,g,sent,ichart,ochart)
+        
+    def e_g(i,j,LHS,sent): 
+        if (i,j,LHS) in ichart:
+#             print ".",
+            return ichart[i,j,LHS]
+        else:
+            return inner(i,j,LHS,g,sent,ichart) 
+        
+    for s_num,sent in enumerate(corpus):
+        if s_num%5==0: print "s.num %d"%s_num,
+        if 'REEST' in DEBUG: print sent
+        ichart = {}
+        ochart = {}
+        # since we keep re-using p_sent, it seems better to have
+        # sentences as the outer loop; o/w we'd have to keep every chart
+        p_sent = inner_sent(g, sent, ichart)
+        
+        sent_nums = g.sent_nums(sent)
+        sent_rules = g.sent_rules(sent_nums)
+        for r in sent_rules:
+            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
+                continue # !!! o/w we add wrong values to it below
+            if L == STOP or R == STOP:
+                w = w1_g
+            else:
+                w = w_g
+            for i in xlt(len(sent)):
+                for j in xgt(i, sent):
+                    f['num',LHS,L,R] +=   w(i,j, r,   sent)
+                    f['den',LHS,L,R] += c_g(i,j, LHS, sent) # v_q
+    print ""
+    return f
+
+def reestimate(g, corpus):
+    f = reest_freq(g, corpus)
+    print "applying f to rules"
+    for r in g.all_rules():
+        if r.LHS() == ROOT:
+            r.prob = f['den',ROOT]
+        else:
+            r.prob = f['den',r.LHS(),r.L(),r.R()]
+        if r.prob > 0.0:
+            r.prob = f['num',r.LHS(),r.L(),r.R()] / r.prob
+    return g
+
+
+##############################
+#     Testing functions:     #
+##############################
+def testgrammar():
+    # make sure we use the same data:
+    from loc_h_dmv import testcorpus
+    
+    import pcnf_harmonic
+    reload(pcnf_harmonic)
+    return pcnf_harmonic.initialize(testcorpus)
+
+def testreestimation():
+    from loc_h_dmv import testcorpus
+    g = testgrammar()
+    g = reestimate(g, testcorpus[0:4])
+    return g
+
+def testgrammar_a():                            # Non, Adj
+    _h_ = PCNF_DMV_Rule((SEAL,0), STOP,    ( RGOL,0), 1.0, 1.0) # LSTOP
+    h_S = PCNF_DMV_Rule(( RGOL,0),(GOR,0),  STOP,    0.4, 0.3) # RSTOP
+    h_A = PCNF_DMV_Rule(( RGOL,0),(SEAL,0),( RGOL,0),0.2, 0.1) # Lattach
+    h_Aa= PCNF_DMV_Rule(( RGOL,0),(SEAL,1),( RGOL,0),0.4, 0.6) # Lattach to a
+    h   = PCNF_DMV_Rule((GOR,0),(GOR,0),(SEAL,0),    1.0, 1.0) # Rattach
+    ha  = PCNF_DMV_Rule((GOR,0),(GOR,0),(SEAL,1),    1.0, 1.0) # Rattach to a
+    rh  = PCNF_DMV_Rule(   ROOT,   STOP,    (SEAL,0),  0.9, 0.9) # ROOT
+
+    _a_ = PCNF_DMV_Rule((SEAL,1), STOP,    ( RGOL,1), 1.0, 1.0) # LSTOP
+    a_S = PCNF_DMV_Rule(( RGOL,1),(GOR,1),  STOP,    0.4, 0.3) # RSTOP
+    a_A = PCNF_DMV_Rule(( RGOL,1),(SEAL,1),( RGOL,1),0.4, 0.6) # Lattach
+    a_Ah= PCNF_DMV_Rule(( RGOL,1),(SEAL,0),( RGOL,1),0.2, 0.1) # Lattach to h
+    a   = PCNF_DMV_Rule((GOR,1),(GOR,1),(SEAL,1),    1.0, 1.0) # Rattach
+    ah  = PCNF_DMV_Rule((GOR,1),(GOR,1),(SEAL,0),    1.0, 1.0) # Rattach to h
+    ra  = PCNF_DMV_Rule(   ROOT,   STOP,    (SEAL,1),  0.1, 0.1) # ROOT
+
+    p_rules = [ h_Aa, ha, a_Ah, ah, ra, _a_, a_S, a_A, a, rh, _h_, h_S, h_A, h ]
+
+    
+    b  = {}
+    b[(GOR, 0), 'h'] = 1.0
+    b[(GOR, 1), 'a'] = 1.0
+    
+    return PCNF_DMV_Grammar({0:'h',1:'a'}, {'h':0,'a':1},
+                           None,None,None,b)
+
+def testgrammar_h():
+    h = 0
+    p_ROOT, p_STOP, p_ATTACH, p_ORDER = {},{},{},{}
+    p_ROOT[h] = 1.0
+    p_STOP[h,LEFT,NON] = 1.0
+    p_STOP[h,LEFT,ADJ] = 1.0
+    p_STOP[h,RIGHT,NON] = 0.4
+    p_STOP[h,RIGHT,ADJ] = 0.3
+    p_ATTACH[h,h,LEFT] = 1.0  # not used
+    p_ATTACH[h,h,RIGHT] = 1.0 # not used
+    p_terminals  = {}
+    p_terminals[(GOR, 0), 'h'] = 1.0
+
+    g = PCNF_DMV_Grammar({h:'h'}, {'h':h}, p_ROOT, p_STOP, p_ATTACH, p_terminals)
+
+    g.p_GO_AT[h,h,LEFT,NON] = 0.6 # these probabilities are impossible
+    g.p_GO_AT[h,h,LEFT,ADJ] = 0.7 # so add them manually...
+    g.p_GO_AT[h,h,RIGHT,NON] = 1.0
+    g.p_GO_AT[h,h,RIGHT,ADJ] = 1.0
+    g.make_all_rules()
+    return g
+    
+
+def testreestimation_h():
+    DEBUG.add('REEST')
+    g = testgrammar_h()
+    return reestimate(g,['h h h'.split()])
+
+def regression_tests():
+    test("0.1830", # = .120 + .063, since we have no loc_h
+         "%.4f" % inner(0, 2, (SEAL,0), testgrammar_h(), 'h h'.split(), {}))
+        
+    test("0.1842", # = .0498 + .1092 +.0252 
+         "%.4f" % inner(0, 3, (SEAL,0), testgrammar_h(), 'h h h'.split(), {}))
+    test("0.1842",
+         "%.4f" % inner_sent(testgrammar_h(), 'h h h'.split()))
+
+    test("0.61" ,
+         "%.2f" % outer(1, 3, ( RGOL,0), testgrammar_h(),'h h h'.split(),{},{}))
+    test("0.58" ,
+         "%.2f" % outer(1, 3, (NRGOL,0), testgrammar_h(),'h h h'.split(),{},{}))
+    
+    
+if __name__ == "__main__":
+    DEBUG.clear()
+
+#     import profile
+#     profile.run('testreestimation()')
+
+#    DEBUG.add('reest_attach')
+#     import timeit
+#     print timeit.Timer("pcnf_dmv.testreestimation_h()",'''import pcnf_dmv
+# reload(pcnf_dmv)''').timeit(1)
+
+if __name__ == "__main__":
+    regression_tests()
+#     g = testgrammar()
+#     print g
+
diff --git a/src/pcnf_harmonic.py b/src/pcnf_harmonic.py
new file mode 100644 (file)
index 0000000..577cf69
--- /dev/null
@@ -0,0 +1,73 @@
+# pcnf_harmonic.py, initialization for pcnf_dmv.py
+
+from pcnf_dmv import * # better way to do this?
+from loc_h_harmonic import taglist, init_freq # neutral as regards cnf/loc_h
+
+# todo: tweak this
+HARMONIC_C = 0.0
+FNONSTOP_MIN = 25
+FSTOP_MIN = 5
+
+##############################
+#      Initialization        #
+##############################
+def init_normalize(f, tags, tagnum, numtag):
+    '''Use frequencies (and sums) in f to return create p_STOP and
+    p_ATTACH; at the same time adding the context-free rules to the
+    grammar using these probabilities. 
+
+    Return a usable grammar.'''
+    p_rules = []
+    p_STOP, p_ROOT, p_ATTACH, p_terminals = {},{},{},{}
+    for h, head in numtag.iteritems():
+        p_ROOT[h] = float(f['ROOT', head]) / f['sum', 'ROOT']
+        
+        # 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])
+
+        p_terminals[(GOR, h), head] = 1.0
+        
+        for dir in [LEFT, RIGHT]:
+            for arg, val in f[head, dir].iteritems():
+                p_ATTACH[tagnum[arg], h, dir] = float(val) / f[head,'sum',dir]
+    
+    return PCNF_DMV_Grammar(numtag, tagnum, p_ROOT, p_STOP, p_ATTACH, p_terminals)
+
+
+def initialize(corpus):
+    '''Return an initialized PCNF_DMV_Grammar
+    corpus is a list of lists of tags.'''
+    tags = taglist(corpus)
+    tagnum, numtag = {}, {}
+    for num, tag in enumerate(tags):
+        tagnum[tag] = num
+        numtag[num] = tag
+    # f: frequency counts used in initialization, mostly distances
+    f = init_freq(corpus, tags)
+    g = init_normalize(f, tags, tagnum, numtag)
+    return g
+
+
+if __name__ == "__main__":
+    print "--------initialization testing------------"
+    print initialize([['foo', 'two','foo','foo'],
+                      ['zero', 'one','two','three']])
+    
+    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)
+
+    
+
index bf25f96..4b05f97 100755 (executable)
@@ -1,2 +1,2 @@
 #!/bin/sh
-latex formulas && bibtex formulas && pdflatex formulas && open formulas.pdf
+/usr/texbin/latex formulas && /usr/texbin/bibtex formulas && /usr/texbin/pdflatex formulas && open formulas.pdf
dissimilarity index 73%
index 0ead8c7..79d84e9 100644 (file)
Binary files a/tex/formulas.pdf and b/tex/formulas.pdf differ
index 740ee3e..5eb562e 100644 (file)
@@ -285,12 +285,13 @@ Then these are our reestimated stop probabilities:
 
 
 
-\section{Alternate CNF rules}
+\section{Alternate CNF-like rules}
 Since the IO algorithm as described in \citet{lari-csl90} is made for
-pure CNF style rules, we have an alternate grammar (figure \ref{cnf})
-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.
+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.
 
 \begin{figure}[htp]
   \centering
@@ -317,7 +318,7 @@ not yet generalized to include left-first attachment.
   \end{tabular}
   \caption{Alternate CFG rules (where a child node has an arrow below,
     we use non-adjacent probabilities), defined for all words/POS-tags
-    $h$.}\label{cnf}
+    $h$.}\label{cnf-like}
 \end{figure}
 
 The inside probabilities are the same as those given in
@@ -355,6 +356,78 @@ right stop rules).
 % todo: add ROOT rule to CNF grammar?
 
 
+\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{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}$ ($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) \\
+  \end{tabular}
+  \caption{Terminals of pure CNF rules, defined for all POS-tags
+    $h$.}\label{cnf-T}
+\end{figure}
+
+\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}
+
+
+
+
 \bibliography{./statistical.bib}
 \bibliographystyle{plainnat}