why is cnf-reestimate so slow??

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

[[file:src/main.py][main.py]]
[[file:src/wsjdep.py][wsjdep.py]] 
[[file:src/loc_h_dmv.py][loc_h_dmv.py]]

Meta-todo: 
- make test battery
- change the h's to h_l in [[file:tex/formulas.pdf][formulas.pdf]]

[[file:DMVCCM.html][DMVCCM.html]]

* DMV/CCM report and project
- DMV-[[file:tex/formulas.pdf][formulas.pdf]]  -- /clear/ information =D
- [[file:src/main.py][main.py]] -- evaluation 
- [[file:src/wsjdep.py][wsjdep.py]] -- corpus
- [[file:src/loc_h_dmv.py][loc_h_dmv.py]] -- DMV-IO and reestimation
- [[file:src/loc_h_harmonic.py][loc_h_harmonic.py]] -- DMV initialization
- [[file:src/common_dmv.py][common_dmv.py]] -- various functions used by loc_h_dmv and others
- [[file:src/io.py][io.py]] -- non-DMV IO
# - [[file:src/cnf_harmonic.py][cnf_harmonic.py]]
# - [[file:src/cnf_dmv.py][cnf_dmv.py]]


[[http://www.student.uib.no/~kun041/dmvccm/DMVCCM_archive.html][Archived entries]] from this file.
* Notation
: old notes:   new notes:   in tex/code (constants):    in Klein thesis:
:--------------------------------------------------------------------------------------
: _h_            _h_            SEAL                    bar over h
:  h_             h><           RGOL                    right-under-left-arrow over h
:  h              h>            GOR                     right-arrow over h
:
:               ><h             LGOR                    left-under-right-arrow over h
:                <h             GOL                     left-arrow over h
These are represented in the code as pairs =(s_h,h)=, where =h= is an
integer (POS-tag) and =s_h= \in ={SEAL,RGOL,GOR,LGOR,GOL}=.

=P_ATTACH= and =P_CHOOSE= are synonymous, I try to use the
former. Also, 
: P_GO_AT(a|h,dir,adj) := P_ATTACH(a|h,dir)*(1-P_STOP(STOP|h,dir,adj)

(precalculated after each reestimation with =g.p_GO_AT = make_GO_AT(g.p_STOP,g.p_ATTACH)=)
** 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} ] ]
* Testing the dependency parsed WSJ
[[file:src/wsjdep.py][wsjdep.py]] uses NLTK (sort of) to get a dependency parsed version of
WSJ10 into the format used in mpp() in loc_h_dmv.py.

As a default, =WSJDepCorpusReader= looks for the file =wsj.combined.10.dep= in
=../corpus/wsjdep=.

Only =sents()=, =tagged_sents()= and =parsed_sents()= (plus a new function
=tagonly_sents()=) are implemented, the other NLTK corpus functions are
..um.. undefined...
** TODO [#A] Should =def evaluate= use add_root?
[[file:src/main.py::def%20evaluate%20g%20tagonly_sents%20parsed_sents][main.py]] evaluate
[[file:src/wsjdep.py][wsjdep.py]] add_root

(just has to count how many pairs are in there; Precision and Recall)
* TODO [#C] Alternative CNF for DMV

# <<dmv2cnf>>
- [[file:src/cnf_dmv.py][cnf_dmv.py]]
- [[file:src/cnf_harmonic.py][cnf_harmonic.py]]

See section 5 of [[file:tex/formulas.pdf][formulas.pdf]].

Given a grammar with certain p_ATTACH, p_STOP and p_ROOT, we get:
:>>> print testgrammar_h():
:  h>< -->   h>  STOP   [0.30]
:  h>< -->  >h>  STOP   [0.40]
: _h_  --> STOP    h><  [1.00]
: _h_  --> STOP   <h><  [1.00]
: >h>  -->   h>   _h_   [1.00]
: >h>  -->  >h>   _h_   [1.00]
: <h>< -->  _h_    h><  [0.70]
: <h>< -->  _h_   <h><  [0.60]
:ROOT  --> STOP   _h_   [1.00]


** TODO program reestimation for cnf_dmv
Not sure how this should be done; we could either do it the way it's
done in Klein and Manning, or take it all the way into Lari &
Young. Possibly do both, to find this stupid bug...
** TODO dmv2cnf re-estimation formulas
[[file:tex/formulas.tex][tex]] 

The reestimation function still has to sum over the various
possibilities of N's and A's; but it seems to be simpler than the
loc_h-method altogether.

Question: Would it be the same thing to reestimate using completely
regular IO reestimation? 
** TODO move as much as possible into common_dmv.py
[[file:src/common_dmv.py][common_dmv.py]]

...and improve cnf vs loc_h classes (at /least/ give them different names)
** 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
for-loops; use local variables for globals (global variables or or
functions), etc.
** TODO Clean up reestimation code                                    :PRETTIER:
** TODO [#A] compare speed of w_left/right(...) and w(LEFT/RIGHT, ...) :OPTIMIZE:
** 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 =i= (and =loc_h+1= equal =j=). 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.
* 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/