close to finishing pCHOOSE

[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: H:4 
#+OPTIONS: toc:3
#+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...)
* 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} ] ]
* TODO [#B] 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]])

** P_STOP formulas for various dir and adj:
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|...) )
** P_CHOOSE formula:
Assuming this:

| P_{CHOOSE}(a : h,R) = | \sum_{corpus} \sum_{s=loc(h)} \sum_{t > loc(h)} \sum_{loc(h) < r <= t} c(s, r-1, h_, ...) * c(r,t,_a_,...) |
|                       | \sum_{corpus} \sum_{s=loc(h)} \sum_{t > loc(h)} c(s,t,h, ...)                                              |
|                       |                                                                                                            |
| P_{CHOOSE}(a : h,L) = | \sum_{corpus} \sum_{s<loc(h)} \sum_{t>=loc(h)} \sum_{r<loc(h)} c(s,r,_a_, ...) * c(r+1, t, h_, ...)        |
|                       | \sum_{corpus} \sum_{s<loc(h)} \sum_{t>=loc(h)} c(s,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*).
** DONE [#A] How do we only count from completed trees?
   CLOSED: [2008-06-13 Fri 11:40]
Use c(s,t,Node); inner * outer / P_sent

** DONE [#A] c(s,t,Node)
  CLOSED: [2008-06-13 Fri 11:38]
= inner * outer / P_sent

implemented as inner * outer / inner_sent

* 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..
** DONE if loc_h == t, no need to try right-attachment rules &v.v.    :OPTIMIZE:
   CLOSED: [2008-06-10 Tue 14:34]
(and if loc_h == s, no need to try left-attachment rules.)

Modest speed increase (5%).
** DONE io.debug parameters should not call functions                 :OPTIMIZE:
   CLOSED: [2008-06-10 Tue 12:26]
Exchanged all io.debug(str,'level') calls with statements of the form:
:if 'level' in io.DEBUG:
:    print str

and got an almost threefold speed increase on inner().
** DONE inner_dmv() should disregard rules with heads not in sent     :OPTIMIZE:
   CLOSED: [2008-06-08 Sun 10:18]
If the sentence is "nn vbd det nn", we should not even look at rules
where
: rule.head() not in "nn vbd det nn".split()
This is ruled out by getting rules from g.rules(LHS, sent).

Also, we optimize this further by saying we don't even recurse into
attachment rules where
: rule.head() not in sent[ s :r+1]
: rule.head() not in sent[r+1:t+1]
meaning, if we're looking at the span "vbd det", we only use
attachment rules where both daughters are members of ['vbd','det']
(although we don't (yet) care about removing rules that rewrite to the
same tag if there are no duplicate tags in the span, etc., that would
be a lot of trouble for little potential gain).
* 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/