before trying new pchoose reestimation

[dmvccm.git] / DMVCCM.org

# -*- coding: mule-utf-8-unix -*-

#+STARTUP: overview
#+TAGS: OPTIMIZE PRETTIER
#+STARTUP: hidestars
#+TITLE: DMV/CCM -- todo-list / progress
#+AUTHOR: Kevin Brubeck Unhammer
#+EMAIL: K.BrubeckUnhammer at student uva nl 
#+OPTIONS: ^:{} 
#+LANGUAGE: en
#+SEQ_TODO: TOGROK TODO DONE


* dmvccm report and project
  DEADLINE: <2008-06-30 Mon>
- [[file:src/dmv.py][dmv.py]]
- [[file:src/io.py][io.py]]
- [[file:src/harmonic.py::harmonic%20py%20initialization%20for%20dmv][harmonic.py]]

(But absolute, extended, really-quite-dead-now deadline: August 31...)

[[http://www.student.uib.no/~kun041/dmvccm/DMVCCM_archive.html][Archived entries]] from this file.
* P_STOP and P_CHOOSE for IO/EM (reestimation)
[[file:src/dmv.py::DMV%20probabilities][dmv-P_STOP]]
Remember: The P_{STOP} formula is upside-down (left-to-right also).
(In the article..not the [[http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf][thesis]])

** TOGROK L&Y formula (20) or c()-formula?
At first glance, I've been doing \\
c(s,r,_a_) / [ c(r+1,t, h_) * c(s,t, h_) ] \\
<=>
| 1/P_sent * e(s,r,_a_) * f(s,r,_a_)                                           |
| /                                                                            |
| [ 1/P_sent * e(r+1,t,h_) * f(r+t,t,h_) * 1/P_sent * e(s,t, h_) * f(s,t,h_) ] |

while L&Y uses
| w_sent = 1/P_sent * prob(h_->_a_ h_) * e(s,r,_a_) * e(r+1,t, h_) * f(s,t,h_) |
| /                                                                            |
| v_sent = 1/P_sent * e(s,t,h_) * f(s,t,h_) = c(s,t,h_)                        |

Just for completion: \\
PSTOP =eg. c(s,t,_h_) / c(s,t,h_) for certain s,t \\
<=>
| 1/P_sent * e(s,t,_h_) * f(s,t,_h_) |
| /                                  |
| 1/P_sent * e(s,t, h_) * f(s,t, h_) |

vs what seems to be the direct L&Y translation:

| 1/P_sent * prob(_ h_ -> STOP h_) * e(s,t,h_) * f(s,t,_h_) |
| /                                                         |
| 1/P_sent * e(s,t,_h_) * f(s,t,_h_)                        |

...but if we used that, e(s,t,h_) would cancel out and we'd just be
dividing the outer scores * rule-probability.. hmm.. Also, there's the
problem of what 'rule-probability' means here, since there's on the
one hand the CNF-rule probability, and on the other hand PSTOP and
PCHOOSE -- in stop rules, PSTOP is the rule-probability, while for
attachment rules, it's PCHOOSE*(1-PSTOP). 
** TODO [#A] P_CHOOSE formula:
   - Note taken on [2008-06-16 Mon 12:33] \\
     Implemented as assumed below, but this does not give 1-summing
     probabilities, why? Are we checking the right configurations? Eg,
     is it enough to just check c(s,t,h_), c(s,r,_a_) and
     c(r+1,t,h_) for left attachments??

So far assuming this:

| P_{CHOOSE}(a : h,R) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t > loc(h)} \sum_{loc(h) < r <= t} c(r,t,_a_)               |
|                       | \sum_{corpus} \sum_{s=loc(h)} \sum_{t > loc(h)} \sum_{loc(h) < r <= t} c(s,t,h) * c(s, r-1, h_) |
|                       |                                                                                                 |
| P_{CHOOSE}(a : h,L) = | \sum_{corpus} \sum_{s<loc(h)} \sum_{t>=loc(h)} \sum_{r<loc(h)} c(s,r,_a_)                       |
|                       | \sum_{corpus} \sum_{s<loc(h)} \sum_{t>=loc(h)} \sum_{r<loc(h)} c(s,t,h_) * c(r+1, t, h_)        |
t >= loc(h) since there are many possibilites for right-attachments
below, and each of them alone gives a lower probability (through
multiplication) to the upper tree (so add them all)

The reason we have to check /both/ children of the attachments is that we
have to make sure they are contiguous (otherwise we would have no way
of ruling out eg. h_->_b_,_b_->b_->_a_, where h_ covers *s* and *t*,_b_ is
from *s* to *x<r* and _ a_ is from *s* to *r*).
*** TOGROK Problem with this formula:
On calculating P_{CHOOSE}(det | vbd, L) from the 1-sentence corpus
"det nn vbd", there are two ways in which 'det' could be left
attached; one is where it is attached non-adjacently (after 'vbd' has
attached 'nn'):
:>>> c_L = c(0,0,(SEAL,g.tagnum('det')),0,g,'det nn vbd'.split(),{},{})
:>>> c_L
:0.62669683257918563 # so far so good
:
:>>> c_R = c(1,2,(RGO_L,g.tagnum('vbd')),2,g,'det nn vbd'.split(),{},{})
:>>> c_R
:0.11312217194570134 # still seeems an OK probability
:
:>>> c_M = c(0,2,(RGO_L,g.tagnum('vbd')),2,g,'det nn vbd'.split(),{},{})
:>>> c_M
:0.31674208144796384 # and this seems good
:
:>>> c_L / (c_R * c_M)
:17.490571428571432  # but this is Way off...

** DONE P_STOP formulas for various dir and adj:
   CLOSED: [2008-06-15 Sun 23:40]
Assuming this:

| P_{STOP}(STOP : h,L,non_adj) = | \sum_{corpus} \sum_{s<loc(h)} \sum_{t>=loc(h)} c(s,t,_h_) |
|                                | \sum_{corpus} \sum_{s<loc(h)} \sum_{t>=loc(h)} c(s,t,h_)  |
|                                |                                                           |
| P_{STOP}(STOP : h,L,adj) =     | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>=loc(h)} c(s,t,_h_) |
|                                | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>=loc(h)} c(s,t,h_)  |
|                                |                                                           |
| P_{STOP}(STOP : h,R,non_adj) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>loc(h)} c(s,t,h_)   |
|                                | \sum_{corpus} \sum_{s=loc(h)} \sum_{t>loc(h)} c(s,t,h)    |
|                                |                                                           |
| P_{STOP}(STOP : h,R,adj) =     | \sum_{corpus} \sum_{s=loc(h)} \sum_{t=loc(h)} c(s,t,h_)   |
|                                | \sum_{corpus} \sum_{s=loc(h)} \sum_{t=loc(h)} c(s,t,h)    |
 
(And P_{STOP}(-STOP|...) = 1 - P_{STOP}(STOP|...) )
* DONE outer probabilities
  CLOSED: [2008-06-12 Thu 11:11]
# <<outer>>
There are 6 different configurations here, based on what the above
(mother) node is, and what the Node for which we're computing is.
Here *r* is not between *s* and *t* as in inner(), but an /outer/ index. *loc_N*
is the location of the Node head in the sentence, *loc_m* for the head
of the mother of Node.

+ mother is a RIGHT-stop:
  - outer(*s, t*, mom.LHS, *loc_N*), no inner-call
  - adjacent iff *t* == *loc_m*
+ mother is a  LEFT-stop:
  - outer(*s, t*, mom.LHS, *loc_N*), no inner-call
  - adjacent iff *s* == *loc_m*

+ Node is on the LEFT branch (mom.L == Node)
  * and mother is a LEFT attachment:
    - *loc_N* will be in the LEFT branch, can be anything here.
    - In the RIGHT, non-attached, branch we find inner(*t+1, r*, mom.R,
      *loc_m*) for all possible *loc_m* in the right part of the sentence.
    - outer(*s, r*, mom.LHS, *loc_m*).
    - adjacent iff *t+1* == *loc_m*
  * and mother is a RIGHT attachment:
    - *loc_m* = *loc_N*. 
    - In the RIGHT, attached, branch we find inner(*t+1, r*, mom.R, *loc_R*) for
      all possible *loc_R* in the right part of the sentence.
    - outer(*s, r*, mom.LHS, *loc_N*).
    - adjacent iff *t* == *loc_m*

+ Node is on the RIGHT branch (mom.R == Node)
  * and mother is a LEFT attachment:
    - *loc_m* = *loc_N*. 
    - In the LEFT, attached, branch we find inner(*r, s-1*, mom.L, *loc_L*) for
      all possible *loc_L* in the left part of the sentence.
    - outer(*r, t*, mom.LHS, *loc_m*).
    - adjacent iff *s* == *loc_m*
  * and mother is a RIGHT attachment:
    - *loc_N* will be in the RIGHT branch, can be anything here.
    - In the LEFT, non-attached, branch we find inner(*r, s-1*, mom.L, *loc_m*) for
      all possible *loc_m* in the left part of the sentence.
    - outer(*r, t*, mom.LHS, *loc_N*).
    - adjacent iff *s-1* == *loc_m*

[[file:outer_attachments.jpg]]

: in notes:   in code (constants):    in Klein thesis:
:-------------------------------------------------------------------
: _h_         SEAL                    bar over h
:  h_         RGO_L                   right-under-left-arrow over h
:  h          GO_R                    right-arrow over h
:
:             LGO_R                   left-under-right-arrow over h
:             GO_L                    left-arrow over h

Also, unlike in [[http://bibsonomy.org/bibtex/2b9f6798bb092697da7042ca3f5dee795][Lari & Young]], non-ROOT ('S') symbols may cover the
whole sentence, but ROOT may /only/ appear if it covers the whole
sentence.
** COMMENT qtrees, tex
\usepackage{qtree}
\usepackage{amssymb}

\newcommand{\GOR}[1]{\overrightarrow{#1}}
\newcommand{\RGOL}[1]{\overleftarrow{\overrightarrow{#1}}}

\newcommand{\SEAL}[1]{\overline{#1}}

\newcommand{\LGOR}[1]{\overrightarrow{\overleftarrow{#1}}}
\newcommand{\GOL}[1]{\overleftarrow{#1}}

\Tree [.{$\RGOL{h}$} [.{$_s \SEAL{a} _t$\\
  Node} ] {$_{t+1} \RGOL{h} _r$\\
  R} ]
\Tree [.{$\GOR{h}$} {$_{s} \GOR{h} _{t}$\\
  Node} [.{$_{t+1} \SEAL{a} _r$\\
  R} ] ]
\Tree [.{$\RGOL{h}$} [.{$_r \SEAL{a} _{s-1}$\\
  L} ] {$_{s} \RGOL{h} _t$\\
  Node} ]
\Tree [.{$\GOR{h}$} {$_{r} \GOR{h} _{s-1}$\\
  L} [.{$_{s} \SEAL{a} _t$\\
  Node} ] ]


\Tree [.{$h\urcorner$} [.{$_s \ulcorner a\urcorner _t$\\
  Node} ] {$_{t+1} h\urcorner _r$\\
  R} ]
\Tree [.{$h$} {$_{s} h _{t}$\\
  Node} [.{$_{t+1} \ulcorner a\urcorner _r$\\
  R} ] ]
\Tree [.{$h\urcorner$} [.{$_r \ulcorner a\urcorner _{s-1}$\\
  L} ] {$_{s} h\urcorner _t$\\
  Node} ]
\Tree [.{$h$} {$_{r} h _{s-1}$\\
  L} [.{$_{s} \ulcorner a\urcorner _t$\\
  Node} ] ]

* TOGROK Find Most Probable Parse of given test sentence
We could probably do it pretty easily from the chart:
- for all loc_h, select the (0,len(sent),ROOT,loc_h) that has the highest p
- for stops, just keep going
- for rewrites, for loc_dep select the one that has the highest p
* TOGROK Combine CCM with DMV
Page 108 (pdf: 124) of [[http://www.eecs.berkeley.edu/~klein/papers/klein_thesis.pdf][Klein's thesis]] gives info about this.
** TODO Make inner() and outer() also allow left-first attachment
Using P_{ORDER}(/left-first/ | w) etc.
* TODO Get a dependency parsed version of WSJ to test with
* 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?
** DONE Separate initialization to another file?                      :PRETTIER:
   CLOSED: [2008-06-08 Sun 12:51]
[[file:src/harmonic.py::harmonic%20py%20initialization%20for%20dmv][harmonic.py]]
** DONE DMV Initialization probabilities
(from initialization frequency)
** DONE DMV Initialization frequencies    
   CLOSED: [2008-05-27 Tue 20:04]
*** P_STOP    
P_{STOP} is not well defined by K&M. One possible interpretation given
the sentence [det nn vb nn] is
: f_{STOP}( STOP|det, L, adj) +1
: f_{STOP}(-STOP|det, L, adj) +0  
: f_{STOP}( STOP|det, L, non_adj) +1
: f_{STOP}(-STOP|det, L, non_adj) +0
: f_{STOP}( STOP|det, R, adj) +0
: f_{STOP}(-STOP|det, R, adj) +1
:
: f_{STOP}( STOP|nn, L, adj) +0
: f_{STOP}(-STOP|nn, L, adj) +1
: f_{STOP}( STOP|nn, L, non_adj) +1  # since there's at least one to the left
: f_{STOP}(-STOP|nn, L, non_adj) +0
**** TODO tweak
# <<pstoptweak>>
:            f[head,  'STOP', 'LN'] += (i_h <= 1)     # first two words
:            f[head, '-STOP', 'LN'] += (not i_h <= 1)     
:            f[head,  'STOP', 'LA'] += (i_h == 0)     # very first word
:            f[head, '-STOP', 'LA'] += (not i_h == 0)     
:            f[head,  'STOP', 'RN'] += (i_h >= n - 2) # last two words
:            f[head, '-STOP', 'RN'] += (not i_h >= n - 2) 
:            f[head,  'STOP', 'RA'] += (i_h == n - 1) # very last word
:            f[head, '-STOP', 'RA'] += (not i_h == n - 1) 
vs
:            # this one requires some additional rewriting since it
:            # introduces divisions by zero
:            f[head,  'STOP', 'LN'] += (i_h == 1)     # second word
:            f[head, '-STOP', 'LN'] += (not i_h <= 1) # not first two
:            f[head,  'STOP', 'LA'] += (i_h == 0)     # first word
:            f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
:            f[head,  'STOP', 'RN'] += (i_h == n - 2)     # second-to-last
:            f[head, '-STOP', 'RN'] += (not i_h >= n - 2) # not last two
:            f[head,  'STOP', 'RA'] += (i_h == n - 1)     # last word
:            f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
vs
:            f[head,  'STOP', 'LN'] += (i_h == 1)     # second word
:            f[head, '-STOP', 'LN'] += (not i_h == 1) # not second
:            f[head,  'STOP', 'LA'] += (i_h == 0)     # first word
:            f[head, '-STOP', 'LA'] += (not i_h == 0) # not first
:            f[head,  'STOP', 'RN'] += (i_h == n - 2)     # second-to-last
:            f[head, '-STOP', 'RN'] += (not i_h == n - 2) # not second-to-last
:            f[head,  'STOP', 'RA'] += (i_h == n - 1)     # last word
:            f[head, '-STOP', 'RA'] += (not i_h == n - 1) # not last
vs 
"all words take the same number of arguments" interpreted as
:for all heads:
:    p_STOP(head, 'STOP', 'LN') = 0.3
:    p_STOP(head, 'STOP', 'LA') = 0.5
:    p_STOP(head, 'STOP', 'RN') = 0.4
:    p_STOP(head, 'STOP', 'RA') = 0.7
(which we easily may tweak in init_zeros())
*** P_CHOOSE
Go through the corpus, counting distances between heads and
arguments. In [det nn vb nn], we give 
- f_{CHOOSE}(nn|det, R) +1/1 + C
- f_{CHOOSE}(vb|det, R) +1/2 + C
- f_{CHOOSE}(nn|det, R) +1/3 + C
  - If this were the full corpus, P_{CHOOSE}(nn|det, R) would have
    (1+1/3+2C) / sum_a f_{CHOOSE}(a|det, R)

The ROOT gets "each argument with equal probability", so in a sentence
of three words, 1/3 for each (in [nn vb nn], 'nn' gets 2/3). Basically
just a frequency count of the corpus...

In a sense there are no terminal probabilities, since an /h/ can only
rewrite to an 'h' anyway (it's just a check for whether, at this
location in the sentence, we have the right POS-tag).
* [#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
for-loops; use local variables for globals (global variables or or
functions), etc.

** TODO when reestimating P_STOP etc, remove rules with p < epsilon   :OPTIMIZE:
** TODO inner_dmv, short ranges and impossible attachment             :OPTIMIZE:
If s-t <= 2, there can be only one attachment below, so don't recurse
with both Lattach=True and Rattach=True.

If s-t <= 1, there can be no attachment below, so only recurse with
Lattach=False, Rattach=False.

Put this in the loop under rewrite rules (could also do it in the STOP
section, but that would only have an effect on very short sentences).
** TODO clean up the module files                                     :PRETTIER:
Is there better way to divide dmv and harmonic? There's a two-way
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:
: dmv.py imports dmv_EM.py imports dmv_classes.py
: dmv.py imports dmv_inits.py imports dmv_classes.py

** TOGROK Some (tagged) sentences are bound to come twice             :OPTIMIZE:
Eg, first sort and count, so that the corpus
[['nn','vbd','det','nn'],
 ['vbd','nn','det','nn'],
 ['nn','vbd','det','nn']]
becomes
[(['nn','vbd','det','nn'],2),
 (['vbd','nn','det','nn'],1)]
and then in each loop through sentences, make sure we handle the
frequency correctly.
          
Is there much to gain here?

** TOGROK tags as numbers or tags as strings?                         :OPTIMIZE:
Need to clean up the representation.

Stick with tag-strings in initialization then switch to numbers for
IO-algorithm perhaps? Can probably afford more string-matching in
initialization..
* Adjacency and combining it with the inside-outside algorithm
Each DMV_Rule has both a probN and a probA, for adjacencies. inner()
and outer() needs the correct one in each case.

In each inner() call, loc_h is the location of the head of this
dependency structure. In each outer() call, it's the head of the /Node/,
the structure we're looking outside of.

We call inner() for each location of a head, and on each terminal,
loc_h must equal s (and t). In the recursive attachment calls, we use
the locations (sentence indices) of words to the left or right of the
head in calls to inner(). /loc_h lets us check whether we need probN or
probA/.
** Possible alternate type of adjacency
K&M's adjacency is just whether or not an argument has been generated
in the current direction yet. One could also make a stronger type of
adjacency, where h and a are not adjacent if b is in between, eg. with
the sentence "a b h" and the structure ((h->a), (a->b)), h is
K&M-adjacent to a, but not next to a, since b is in between. It's easy
to check this type of adjacency in inner(), but it needs new rules for
P_STOP reestimation.
* Expectation Maximation in IO/DMV-terms
outer(s,t,Node) and inner(s,t,Node) calculates the expected number of
trees (CNF-)headed by Node from *s* to *t* (sentence positions). This uses
the P_STOP and P_CHOOSE values, which have been conveniently
distributed into CNF rules as probN and probA (non-adjacent and
adjacent probabilites).

When re-estimating, we use the expected values from outer() and
inner() to get new values for P_STOP and P_CHOOSE. When we've
re-estimated for the entire corpus, we distribute P_STOP and P_CHOOSE
into the CNF rules again, so that in the next round we use new probN
and probA to find outer- and inner-probabilites.

The distribution of P_STOP and P_CHOOSE into CNF rules also happens in
init_normalize() (here along with the creation of P_STOP and
P_CHOOSE); P_STOP is used to create CNF rules where one branch of the
rule is STOP, P_CHOOSE is used to create rules of the form 
: h  -> h  _a_
: h_ -> h_ _a_

Since "adjacency" is not captured in regular CNF rules, we need two
probabilites for each rule, and outer() and inner() have to know when
to use which.


* Python-stuff
# <<python>>
Make those debug statements steal a bit less attention in emacs:
:(font-lock-add-keywords
: 'python-mode                   ; not really regexp, a bit slow
: '(("^\\( *\\)\\(\\if +'.+' +in +io.DEBUG. *\\(
:\\1    .+$\\)+\\)" 2 font-lock-preprocessor-face t)))
:(font-lock-add-keywords
: 'python-mode
: '(("\\<\\(\\(io\\.\\)?debug(.+)\\)" 1 font-lock-preprocessor-face t)))

- [[file:src/pseudo.py][pseudo.py]]
- http://nltk.org/doc/en/structured-programming.html recursive dynamic
- http://nltk.org/doc/en/advanced-parsing.html 
- http://jaynes.colorado.edu/PythonIdioms.html



* Git
Repository web page: http://repo.or.cz/w/dmvccm.git

Setting up a new project:
: git init
: git add .
: git commit -m "first release"

Later on: (=-a= does =git rm= and =git add= automatically)
: git init
: git commit -a -m "some subsequent release"

Then push stuff up to the remote server:
: git push git+ssh://username@repo.or.cz/srv/git/dmvccm.git master

(=eval `ssh-agent`= and =ssh-add= to avoid having to type in keyphrase all
the time)

Make a copy of the (remote) master branch:
: git clone git://repo.or.cz/dmvccm.git 

Make and name a new branch in this folder
: git checkout -b mybranch

To save changes in =mybranch=:
: git commit -a 

Go back to the master branch (uncommitted changes from =mybranch= are
carried over):
: git checkout master

Try out:
: git add --interactive

Good tutorial:
http://www-cs-students.stanford.edu/~blynn//gitmagic/