Ok, so I misunderstood the word adjacent all along. Redone now.

[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 toc:3 ^:{} 
#+LANGUAGE: en
#+SEQ_TODO: TOGROK TODO DONE

* dmvccm report and project
  DEADLINE: <2008-06-30 Mon>
But absolute, extended, really-quite-dead-now deadline: August
31... 
- [[file:src/dmv.py][dmv.py]]
- [[file:src/io.py][io.py]]
- [[file:src/harmonic.py::harmonic%20py%20initialization%20for%20dmv][harmonic.py]]
* TODO Adjacency and combining it with inner()
Each DMV_Rule now has both a probN and a probA, for
adjacencies. inner() needs the correct one in each case.

Adjacency gives a problem with duplicate words/tags, eg. in the
sentence "a a b". If this has the dependency structure b->a_{0}->a_{1},
then b is non-adjacent to a_{0} and should use probN (for the LRStop and
the attachment of a_{0}), while the other rules should all use
probA. But within the e(0,2,b) we can't just say "oh, a has index 0
so it's not adjacent to 2", since there's also an a at index 1, and
there's also a dependency structure b->a_{1}->a_{0} for that. We want
both. And in possibly much more complex versions.

Ideas:
- I first thought of decorating the individual words/tags in a
  sentence with their indices, and perhaps just duplicating the
  relevant rules (one for each index of the duplicate tags). But this
  gives an explosion in attachment rules (although a contained
  explosion, within the rules used in a sentence; but most sentences
  will have at least two NN's so it will be a problem).
- Then, I had a /brilliant/ idea. Just let e(), the helper function of
  inner(), parametrize for an extra pair of boolean values for whether
  or not we've attached anything to the left or right yet ("yet"
  meaning "below"). So now, e() has a chart of the form [s, t, LHS,
  Lattach, Rattach], and of course e(s,t,LHS) is the sum of the four
  possible values for (Lattach,Rattach). This makes e() lots more
  complex and DMV-specific though, so it's been rewritten in
  inner_dmv() in dmv.py.
- But, the problem is that we still need to be able get inner
  probabilites for only trees where the h at location loc_h is the
  root of the dependency. The previous idea does not give that. So I
  made /another/ version of inner() that parametrizes for loc_h in the
  chart (instead of Lattach and Rattach). loc_h also lets us check
  whether we need probN or probA, in a much simpler fashion than the
  Lattach / Rattach version.
** TODO document this adjacency stuff better
** TODO [#A] test and debug my brilliant idea
*** Works on simple 'h h' sentence, but not with P_STOP, why?
** DONE implement my brilliant idea.
    CLOSED: [2008-06-01 Sun 17:19]
[[file:src/dmv.py::def%20e%20s%20t%20LHS%20Lattach%20Rattach][e(sti) in dmv.py]]

** DONE [#A] test inner() on sentences with duplicate words
Works with eg. the sentence "h h h"


* TODO [#A] P_STOP for IO/EM
[[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 thesis)

Remember: Initialization makes some "short-cut" rules, these will also
have to be updated along with the other P_{STOP} updates:
- b[(NOBAR, n_{h}), 'h'] = 1.0       # always
- b[(RBAR, n_{h}), 'h'] = h_.probA  # h_ is RBAR stop rule
- b[(LRBAR, n_{h}), 'h'] = h_.probA * _ h_.probA

** How is the P_STOP formula different given other values for dir and adj?
Assuming this:
- P_{STOP}(STOP|h,L,non_adj) = \sum_{corpus} \sum_{s<loc(h)} \sum_{t}
  inner(s,t,(LRBAR,h)...) / \sum_{corpus} \sum_{s<loc(h)} \sum_{t} inner(s,t,(RBAR,h)...)
- P_{STOP}(STOP|h,L,adj) = \sum_{corpus} \sum_{s=loc(h)} \sum_{t}
  inner(s,t,(LRBAR,h)...) / \sum_{corpus} \sum_{s=loc(h)} \sum_{t} inner(s,t,(RBAR,h)...)
- P_{STOP}(STOP|h,R,non_adj) = \sum_{corpus} \sum_{s} \sum_{t>loc(h)}
  inner(s,t,(LRBAR,h)...) / \sum_{corpus} \sum_{s} \sum_{t>loc(h)} inner(s,t,(RBAR,h)...)
- P_{STOP}(STOP|h,R,adj) = \sum_{corpus} \sum_{s} \sum_{t=loc(h)}
  inner(s,t,(LRBAR,h)...) / \sum_{corpus} \sum_{s} \sum_{t=loc(h)} inner(s,t,(RBAR,h)...)



(And P_{STOP}(-STOP|...) = 1 - P_{STOP}(STOP|...) )
* TODO P_CHOOSE for IO/EM
Write the formulas! should be easy?
* Initialization   
[[file:~/Documents/Skole/V08/Probability/dmvccm/src/dmv.py::Initialization%20todo][dmv-inits]]

We do have to go through the corpus, since the probabilities are based
on how far away in the sentence arguments are from their heads.
** TODO Separate initialization to another file?                      :PRETTIER:
(It's rather messy.)
** TOGROK CCM Initialization    
P_{SPLIT} used here... how, again?
** 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...
* [#C] Deferred
** TODO inner_dmv() should disregard rules with heads not in sent     :OPTIMIZE:
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).
** 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..
* Expectation Maximation in IO/DMV-terms
inner(s,t,LHS) calculates the expected number of trees headed by LHS
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 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
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 inner() has to know when to use which.

** TODO Corpus access
** TOGROK sentences or rules as the "outer loop"?                     :OPTIMIZE:
In regard to the E/M-step, finding P_{STOP}, P_{CHOOSE}.


* Python-stuff
- [[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
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/