report almost done
authorKevin Brubeck Unhammer <pixiemotion@gmail.com>
Sun, 21 Sep 2008 10:42:19 +0000 (21 12:42 +0200)
committerKevin Brubeck Unhammer <pixiemotion@gmail.com>
Sun, 21 Sep 2008 10:42:19 +0000 (21 12:42 +0200)
report/report.pdf
report/report.tex
src/loc_h_dmv.py
src/loc_h_dmv.pyc
src/loc_h_harmonic.py
src/main.py
tex/formulas.pdf
tex/formulas.tex

dissimilarity index 68%
index 004465e..950dd07 100644 (file)
Binary files a/report/report.pdf and b/report/report.pdf differ
index 44fced8..9640790 100644 (file)
@@ -1,4 +1,4 @@
-% Created 2008-06-13 Fri 17:05
+% merged Kevin's & Emily's reports 2008-09-21 Sun 10:39 with Emerge
 
 \documentclass[11pt,a4paper]{article}
 \usepackage[utf8]{inputenc}
 \tableofcontents
 
 \section{Introduction}
+\citet{klein-thesis} describes two models for the unsupervised
+learning of syntactic structure. One is the Constituent Context Model
+(CCM), which uses the context as well as the content of a substring to determine whether it
+is a constituent. The context of a substring is defined to be the words
+immediately preceding and following the substring. The intuition is that context can be a reliable cue for constituentness because when a long phrase is a constituent, there is often a similar case where a single word will serve as a constituent in the same context. Thus to determine the
+likelihood that a substring is a constituent, this model considers both
+the likelihood of the substring itself as a constituent and the
+likelihood of its context as the context of a constituent.
+
+The other is a Dependency Model with Valence (DMV), which uses a form
+of Dependency Grammar. Here sentence structure is represented as pairs
+of heads and dependents (arguments), although it is also possible to
+represent this as a CFG (see \citet[p.~106]{klein-thesis}).
+
+Apart from identity of the argument, probabilities are conditional on
+direction of attachment. A valence condition is introduced by using
+stopping probabilities: a head may take zero, one or more dependents
+before ``stopping'', and there are different probabilities for
+stopping without taking arguments (\emph{adjacently}) versus after
+taking one or more (\emph{non-adjacently}).
+
+Versions of the inside-outside algorithm for PCFG's \citep{lari-csl90}
+are used for running estimation maximation on both these probabilistic
+models. We tried implementing both the CCM and the DMV. Below we give
+the details of how this was done, along with the results.
+
 \section{The Constituent Context Model}
+\subsection{Basics}
+The CCM model \citep{klein-thesis, km-ccm} is a generative model over a set of Part Of Speech (POS) tags $\mathbb{T}$ and a beginning/end of sentence symbol $\diamond$.
+The CCM model has two parameters:
+\begin{itemize}
+\item $P_{SPAN}(\alpha | c)$ is the probability of generating a span $\alpha$ given that it is/is not a constituent; $\alpha \in \mathbb{T}^*, c \in \{\text{true}, \text{false}\}$.
+\item $P_{CONTEXT}(\beta | c)$ is the probability of generating a context $\beta$ given that the span it surrounds is/is not a constituent; $\beta \in (\mathbb{T}\cup\diamond)^2,c \in \{\text{true}, \text{false}\}$.
+\end{itemize}
+The probability of a sentence $s$ with bracketing $B$ is the probability of that bracketing times the probability of the span and the context for each substring of $s$. The probability of bracketings are the fixed distribution $P_\text{bin}$, which assigns equal weight to all bracketings that correspond to binary trees. For a sentence $s$ of length $n$, we index spaces between words in the sentence, including the leading space (0) and the trailing space ($n$). Let $\langle i,j\rangle_s$ be the substring from $i$ to $j$, and $\rangle i,j\langle_s$ be the context of that substring. Then we have: $$P(s,B)=P_{\text{bin}}(B)\displaystyle\prod_{\{\langle i,j\rangle_s\}}P_{\text{SPAN}}(\langle i,j\rangle_s|B_{ij})P_{\text{CONTEXT}}(\rangle i,j\langle_s|B_{ij})$$
+
+\subsection{Reestimation}
+We use the EM algorithm to induce our model parameters. Given the parameters $P_{\text{SPAN}}$ and $P_{\text{CONTEXT}}$, we wish to first find the likelihoods of completions for all sentences in a corpus given the current parameter values, and then find new parameters that maximize the corpus likelihood given the previously predicted completions. Because enumerating all bracketings for all sentences in computationally infeasible, we use a dynamic programming algorithm similar to the inside-outside algorithm.
+
+We begin by rewriting the probability $P(s,B)$ given above:
+$$P(s,B)=P_{\text{bin}}(B)\displaystyle\prod_{\{\langle i,j\rangle_s\}}P_{\text{SPAN}}(\langle i,j\rangle_s|\text{false})P_{\text{CONTEXT}}(\rangle i,j\langle_s|\text{false}) \times$$$$ \prod_{\{\langle i,j\rangle_s\in B\}}\frac{P_{\text{SPAN}}(\langle i,j\rangle_s|\text{true})P_{\text{CONTEXT}}(\rangle i,j\langle_s|\text{true})}{P_{\text{SPAN}}(\langle i,j\rangle_s|\text{false})P_{\text{CONTEXT}}(\rangle i,j\langle_s|\text{false})}$$
+We can then condense this by letting $$\phi(i,j,s)=\frac{P_{\text{SPAN}}(\langle i,j\rangle_s|\text{true})P_{\text{CONTEXT}}(\rangle i,j\langle_s|\text{true})}{P_{\text{SPAN}}(\langle i,j\rangle_s|\text{false})P_{\text{CONTEXT}}(\rangle i,j\langle_s|\text{false})}$$
+Further, note that $P_{\text{bin}}$ is constant for all bracketings of a sentence. We can thus also write $$K(s)=P_{\text{bin}}(B)\displaystyle\prod_{\{\langle i,j\rangle_s\}}P_{\text{SPAN}}(\langle i,j\rangle_s|\text{false})P_{\text{CONTEXT}}(\rangle i,j\langle_s|\text{false})$$ and $K(s)$ is constant for a given sentence.
+We thus have a condensed formulation of $P(s,B)$:
+$$P(s,B)=K(s) \prod_{\{\langle i,j\rangle_s\in B\}}\phi(i,j,s)$$
+
+In the spirit of the inside-outside algorithm, we can use a dynamic programming algorithm to calculate the product of $\phi(i,j,s)$ for a sentence. We wish to calculate the products of the $\phi(i,j,s)$ both inside and outside a given interval $\langle i,j\rangle$. Let $\mathcal{T}(m)$ be the set of binary tree structures with $m$ leaves. We then define $$I(i,j,s)=\displaystyle\sum_{T\in \mathcal{T}(j-i)}\prod_{\langle a,b\rangle:\langle a-i,b-i\rangle\in T}\phi(a,b,s)$$
+To calculate I, we want to find a recursive decomposition. In the case where $j=i$, there can be no constituents between $i$ and $j$, so we have $I(i,i,s)=0$. In the case where $j=i+1$, there is necessary exactly one constituent between $i$ and $j$ because all one-word substrings are constituents, so $I(i,i+1,s)=\phi(i,i+1,s)$. In the case where $j>i+1$, any constituent spanning from $i$ to $j$ must also contain subconstituents from $i$ to $k$ and from $k$ to $j$. Thus
+$$I(i,j,s)=\displaystyle\sum_{i<k<j}\sum_{T\in\mathcal{T}(k-i)}\sum_{T'\in\mathcal{T}(j-k)}\phi(i,j,s)\prod_{\langle a,b\rangle:\langle a-i,b-i\rangle\in T}\phi(a,b,s)\prod_{\langle a',b'\rangle:\langle a'-k,b'-k\rangle\in T'}\phi(a',b',s)$$
+$$=\phi(i,j,s)\displaystyle\sum_{i<k<j}\sum_{T\in\mathcal{T}(k-i)}\sum_{T'\in\mathcal{T}(j-k)}\prod_{\langle a,b\rangle:\langle a-i,b-i\rangle\in T}\phi(a,b,s)\prod_{\langle a',b'\rangle:\langle a'-k,b'-k\rangle\in T'}\phi(a',b',s)$$
+$$=\phi(i,j,s)\displaystyle\sum_{i<k<j}I(i,k,s)I(k,j,s)$$
+
+In summary, we have a recursive decomposition for I:
+$$I(i,j,s) = \begin{cases} 
+               \phi(i,j,s)\displaystyle\sum_{i<k<j}I(i,k,s)I(k,j,s) & \text{if } j-i>1 \\
+               \phi(i,j,s) & \text{if } j-i=1 \\
+               0 & \text{if } j-i = 0
+       \end{cases}$$
+
+Similarly, we define the outside probability
+$$O(i,j,s) = \begin{cases}
+               \displaystyle\sum_{0\leq k<i}I(k,i,s)\phi(k,j,s)O(k,j,s) + \sum_{j<k\leq n} I(j,k,s)\phi(i,k,s)O(i,k,s) &
+                       \text{if } j-i < n \\
+               1 & \text{if } j-i = n
+       \end{cases}$$
+
+To reestimate the parameters $P_{\text{SPAN}}$ and $P_{\text{CONTEXT}}$, we wish to know $P_{\text{BRACKET}}(i,j,s)$, the fraction of bracketings of $s$ that contain $\langle i,j\rangle$ as a constituent:
+$$P_{\text{BRACKET}}(i,j,s)=\frac{\displaystyle\sum_{\{B:B_{ij}=\text{true}\}}P(s,B)}{\displaystyle\sum_{B}P(s,B)}$$
+We can rewrite this in terms of our inside and outside probabilities:
+$$\displaystyle\sum_{\{B:B_{ij}=\text{true}\}}P(s,B)=K(s)I(i,j,s)O(i,j,s)$$
+and
+$$\displaystyle\sum_{B}P(s,B)=K(s)I(0,n,s)O(0,n,s)$$
+But the $K(s)$ terms cancel, and $O(0,n,s)=1$, so we find that $$P_{\text{BRACKET}}(i,j,s)=\frac{I(i,j,s)O(i,j,s)}{I(0,n,s)}$$
+
+From $P_{\text{BRACKET}}$ we can calculate the next iteration of the model parameters $P_{\text{SPAN}}$ and $P_{\text{CONTEXT}}$. First, for a sentence $s$ of length $n_s$, note that the number of spans in the sentence is $N_s=(n_s+1)(n_s+2)/2$, which includes the spans of length 0. Furthemore, let $\#_s(\gamma)$ be the number of times that $\gamma$ appears in $s$, where $\gamma$ can be either a span or a context.
+
+We begin with
+$$P_{\text{SPAN}}(\alpha|c)=\displaystyle\sum_{s\in C}P(\alpha|c,s)P(s)=\frac{1}{|C|}\sum_{s\in C}P(\alpha|c,s)$$
+This reduction works for $P_{\text{CONTEXT}}$ as well, so we have reduced the problem of calculating $P_{\text{SPAN}}$ and $P_{\text{CONTEXT}}$ on the corpus as a whole to calculating it for each sentence.
+
+Let us begin by calculating $P_{\text{SPAN}}(\alpha|\text{true},s)$. By Bayes' Theorem, $$P_{\text{SPAN}}(\alpha|\text{true},s)=\frac{P_{\text{SPAN}}(\text{true}|\alpha,s)P_{\text{SPAN}}(\alpha|s)}{P_{\text{SPAN}}(\text{true}|s)}$$
+We can compute each of the quantities on the right hand side:
+$$P_{\text{SPAN}}(\alpha|s)=\frac{\#_s(\alpha)}{N_s}$$
+$$P_{\text{SPAN}}(\text{true}|s)=\frac{2n_s-1}{N_s}$$
+$$P_{\text{SPAN}}(\text{true}|\alpha,s)=\frac{1}{\#_s(\alpha)}\displaystyle\sum_{\langle i,j\rangle=\alpha}P_{\text{BRACKET}}(i,j,s)$$
+
+Thus we find that
+$$P_{\text{SPAN}}(\alpha|\text{true},s)=\frac{1}{\#_s(\alpha)}\displaystyle\sum_{\langle i,j\rangle=\alpha}P_{\text{BRACKET}}(i,j,s)\frac{\#_s(\alpha)}{N_s}\frac{N_s}{2n_s-1}=\frac{1}{2n_s-1}\displaystyle\sum_{\langle i,j\rangle=\alpha}P_{\text{BRACKET}}(i,j,s)$$
+
+A similar calculation shows that $$P_{\text{CONTEXT}}(\beta|\text{true},s)=\frac{1}{2n_s-1}\displaystyle\sum_{\rangle i,j\langle=\beta}P_{\text{BRACKET}}(i,j,s)$$
+
+Now let us consider $P_{\text{SPAN}}(\alpha|\text{false},s)$. Again by Bayes' Theorem we have $$P_{\text{SPAN}}(\alpha|\text{false},s)=\frac{P_{\text{SPAN}}(\text{false}|\alpha,s)P_{\text{SPAN}}(\alpha|s)}{P_{\text{SPAN}}(\text{false}|s)}$$
+
+$P_{\text{SPAN}}(\alpha|s)$ is as before. $P_{\text{SPAN}}(\text{false}|s)=1-P_{\text{SPAN}}(\text{true}|s)$. And $P_{\text{SPAN}}(\text{false}|\alpha,s)=1-P_{\text{SPAN}}(\text{true}|\alpha,s)$. Thus 
+$$P_{\text{SPAN}}(\alpha|\text{false},s)=\frac{(1-\frac{1}{\#_s(\alpha)}\displaystyle\sum_{\langle i,j\rangle=\alpha}P_{\text{BRACKET}}(i,j,s))\frac{2n_s-1}{N_s}}{1-\frac{2n_s-1}{N_s}}$$$$=\frac{\#(\alpha)-\Sigma_{<i,j>=\alpha}P_{BRACKET}(i,j,s)}{N_s-2n_s+1}$$
+
+Similarly, we have $$P_{CONTEXT}(\beta|false,s) = \frac{\#(\beta)-\Sigma_{>i,j<=\beta}P_{BRACKET}(i,j,s)}{N_s-2n_s+1}$$
+
+From these, we can calculate the new parameters $P_{\text{SPAN}}$ and $P_{\text{CONTEXT}}$ as above.
+
+\subsection{Initialization}
+We initialize the model with a distribution $P_{\text{SPLIT}}$ over trees. $P_{\text{SPLIT}}$ is calculated as follows: for a string of $n$ words, choose a split point at random, then recursively build trees on either side of that split by further random splitting. We initialize the model using $P_{\text{BRACKET}}(i,j,s)=P_{\text{SPLIT}}(i,j,n_s)$. However, we also apply smoothing, adding small constant counts $m_\text{true}$ and $m_\text{false}$ of each span and context as a constituent and distituent, respectively. $m_\text{true}$ should be smaller than $m_\text{false}$, as there are more distituent spans than constituent spans. However, \citet{klein-thesis} and \citet{km-ccm} give different values for these constants, and in any case they must vary in relation to the size of the corpus used. Let $\#_\alpha$ and $\#_\beta$ be the number of unique spans and contexts in the corpus. We initialize the model:
+\begin{itemize}
+\item $P_{SPAN}(\alpha|true)= \frac {(\displaystyle\sum_{s\in C}\displaystyle\sum_{<i,j>=\alpha}P_{\text{SPLIT}}(i,j,n_s))+m_\text{true}}
+       {(\displaystyle\sum_{s\in C}2n_s-1)+m_\text{true} \#_\alpha}$
+\item $P_{SPAN}(\alpha|false)= \frac {(\displaystyle\sum_{s\in C}\displaystyle\sum_{<i,j>=\alpha}1-P_{\text{SPLIT}}(i,j,n_s))+m_\text{false}}
+       {(\displaystyle\sum_{s\in C}N_s-(2n_s-1))+m_\text{false} \#_\alpha}$
+\item $P_{CONTEXT}(\beta|true)= \frac {(\displaystyle\sum_{s\in C}\displaystyle\sum_{>i,j<=\beta}P_{\text{SPLIT}}(i,j,n_s))+m_\text{true}}
+       {(\displaystyle\sum_{s\in C}2n_s-1)+m_\text{true} \#_\beta}$
+\item $P_{CONTEXT}(\beta|false)= \frac {(\displaystyle\sum_{s\in C}\displaystyle\sum_{>i,j<=\beta}1-P_{\text{SPLIT}}(i,j,s))+m_\text{false}}
+       {(\displaystyle\sum_{s\in C}N_s-(2n_s-1))+m_\text{false} \#_\beta}$
+\end{itemize}
+
 \subsection{Results}
+We have not yet tested the CCM model on the Wall Street Journal corpus.
+
 \section{A Dependency Model with Valence}
-This is an attempt at fleshing out the details of the inside-outside
-algorithm \citep{lari-csl90} applied to the DMV model of
-\citet{klein-thesis}.
+The DMV is a \emph{head-outward process}. Given a certain head (eg. a
+verb), we first attach possible arguments in one direction (eg. nouns
+to the right), then stop in that direction, then possibly attach
+arguments in the other direction, then stop. The probabilities of a
+certain head attaching any arguments in a direction sum to one
+\citep[see~$P(D(h))$~in][p.~87]{klein-thesis} -- modelled as a PCFG,
+however \citep[p.~83,~figure~6.4]{klein-thesis}, probabilities may sum
+to less than one given a certain left-hand side symbol.
+
+In the following sections we try to flesh out the details of the
+inside-outside algorithm \citep{lari-csl90} applied to the DMV model
+of \citet{klein-thesis}. We have three parameters which are
+reestimated using the inside-outside algorithm:
+
+\begin{itemize}
+\item $P_{ATTACH}(a|h,dir)$ is the probability of attaching an
+  argument with tag $a$, given that we are attaching in direction
+  $dir$ from head $h$. Here $a,h \in \mathbb{T},
+  dir\in\{left,right\}$.
+\item $P_{STOP}(stop|h,dir,adj)$ is the probability of stopping (which
+  happens after argument attachment), given that we are attaching from
+  head $h$ in direction $dir$. Adjacency $adj$ is whether or not we
+  have attached anything yet in that direction.
+\item $P_{ROOT}(h)$ is the probability of the special ROOT symbol
+  heading $h$; in the original model this is modelled using a right
+  stop, a left stop, and an attachment
+  \citep[p.~105,~figure~A.2]{klein-thesis}; we conflated these
+  into one additional parameter.
+\end{itemize}
+
+
+
+
 
 \newcommand{\LOC}[1]{\textbf{#1}}
 \newcommand{\GOR}[1]{\overrightarrow{#1}}
@@ -66,8 +210,8 @@ $\LOC{w}$ on the right. To simplify, $loc_l(\LOC{w}):=loc(\LOC{w})$ and
 $loc_r(\LOC{w}):=loc(\LOC{w})+1$. We write $\LOC{h}$ if this is a head
 in the rule being used, $\LOC{a}$ if it is an attached argument.
 
-There are som notational differences between \citet{klein-thesis}
-\citet{km-dmv}:
+There are som notational differences between the thesis
+\citet{klein-thesis} and the ACL paper \citet{km-dmv}:
 
 \begin{tabular}{cc}
 Paper: & Thesis: \\
@@ -170,7 +314,6 @@ of having a stop above, where we use $\SEAL{w}$:
 
 
 \subsection{Reestimating the rules} 
-% TODO: fix stop and attachment formulas so they divide before summing
 
 \subsubsection{$c$ and $w$ (helper formulas used below)}
 $c_s(\SMTR{\LOC{w}} : i, j)$ is ``the expected fraction of parses of
@@ -188,34 +331,34 @@ $w_s$ is $w_{q}$ from \citet[p.~41]{lari-csl90}, generalized to $\SMTR{h}$ and $
 \begin{align*}
   w_s(\SEAL{a} & : \SMTR{\LOC{h}}, left, i, j) = \\
   & 1/P_s \sum_{k:i<k<j} ~ \sum_{\LOC{a}:i\leq loc_l(\LOC{a})<k} 
-          & P_{STOP}(\neg stop|h, left, adj(k, \LOC{h})) P_{CHOOSE}(a|h, left) \\
+          & P_{STOP}(\neg stop|h, left, adj(k, \LOC{h})) P_{ATTACH}(a|h, left) \\
   &       & P_{INSIDE_s}(\SEAL{\LOC{a}}, i, k) P_{INSIDE_s}(\SMTR{\LOC{h}}, k, j) P_{OUTSIDE_s}(\SMTR{\LOC{h}}, i, j) 
 \end{align*}
 \begin{align*}
   w_s(\SEAL{a} & : \SMTR{\LOC{h}}, right,  i, j) = \\
   & 1/P_s \sum_{k:i<k<j} ~ \sum_{\LOC{a}:k\leq loc_l(\LOC{a})<j} 
-          & P_{STOP}(\neg stop|h, right, adj(k, \LOC{h})) P_{CHOOSE}(a|h, right) \\
+          & P_{STOP}(\neg stop|h, right, adj(k, \LOC{h})) P_{ATTACH}(a|h, right) \\
   &       & P_{INSIDE_s}(\SMTR{\LOC{h}}, i, k) P_{INSIDE_s}(\SEAL{\LOC{a}}, k, j) P_{OUTSIDE_s}(\SMTR{\LOC{h}}, i, j) 
 \end{align*}
 
-Let $\hat{P}$ be the new STOP/CHOOSE-probabilities (since the old $P$
+Let $\hat{P}$ be the new STOP/ATTACH-probabilities (since the old $P$
 are used in $P_{INSIDE}$ and $P_{OUTSIDE}$).
 
 \subsubsection{Attachment reestimation} 
 
-$\hat{a}$ is given in \citet[p.~41]{lari-csl90}. Here $i<loc_l(\LOC{h})$
-since we want trees with at least one attachment:
+This is based on $\hat{a}$, given in \citet[p.~41]{lari-csl90}. Here
+$i<loc_l(\LOC{h})$ since we want trees with at least one attachment:
 \begin{align*}
-  \hat{a} (a | \SMTR{h}, left) =  \frac
-  { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i<loc_l(\LOC{h})} \sum_{j\geq loc_r(\LOC{h})} w_s(\SEAL{a} : \SMTR{\LOC{h}}, left, i, j) }
-  { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i<loc_l(\LOC{h})} \sum_{j\geq loc_r(\LOC{h})} c_s(\SMTR{\LOC{h}} : i, j) }
+  \hat{P}_{ATTACH} (a | h, left) = \frac
+  { \sum_{s \in S} \sum_{\LOC{h} \in s} \sum_{i<loc_l(\LOC{h})} \sum_{j\geq loc_r(\LOC{h})} [w_s(\SEAL{a} : \GOL{\LOC{h}}, left, i, j) + w_s(\SEAL{a} : \RGOL{\LOC{h}}, left, i, j) ]}
+  { \sum_{s \in S} \sum_{\LOC{h} \in s} \sum_{i<loc_l(\LOC{h})} \sum_{j\geq loc_r(\LOC{h})} [c_s(\GOL{\LOC{h}} : i, j) + c_s(\RGOL{\LOC{h}} : i, j) ]}
 \end{align*}
 
-Here $j>loc_r(\SMTR{\LOC{h}})$ since we want at least one attachment:
+Here $j>loc_r(\LOC{h})$ since we want at least one attachment:
 \begin{align*}
-  \hat{a} (a | \SMTR{h}, right) = \frac
-  { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i\leq loc_l(\LOC{h})} \sum_{j>loc_r(\LOC{h})} w_s(\SEAL{a} : \SMTR{\LOC{h}}, right, i, j) }
-  { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i\leq loc_l(\LOC{h})} \sum_{j>loc_r(\LOC{h})} c_s(\SMTR{\LOC{h}} : i, j) }
+  \hat{P}_{ATTACH} (a | h, right) = \frac
+  { \sum_{s \in S} \sum_{\LOC{h} \in s} \sum_{i\leq loc_l(\LOC{h})} \sum_{j>loc_r(\LOC{h})} [w_s(\SEAL{a} : \LGOR{\LOC{h}}, right, i, j) + w_s(\SEAL{a} : \GOR{\LOC{h}}, right, i, j) ]}
+  { \sum_{s \in S} \sum_{\LOC{h} \in s} \sum_{i\leq loc_l(\LOC{h})} \sum_{j>loc_r(\LOC{h})} [c_s(\LGOR{\LOC{h}} : i, j) + c_s(\GOR{\LOC{h}} : i, j) ]}
 \end{align*}
 
 For the first/lowest attachments, $w_s$ and $c_s$ have zero probability
@@ -224,52 +367,44 @@ this is implicit in $P_{INSIDE}$.
 
 
 
-\begin{align*}
-  \hat{P}_{CHOOSE} (a | h, left) = 
-  \hat{a} (a | \GOL{h}, left) 
-  + \hat{a} (a | \RGOL{h}, left) 
-\end{align*}
-\begin{align*}
-  \hat{P}_{CHOOSE} (a | h, right) = 
-  \hat{a} (a | \GOR{h},right) 
-  + \hat{a} (a | \LGOR{h},right) 
-\end{align*}
-
 \subsubsection{Stop reestimation} 
 The following is based on \citet[p.~88]{klein-thesis}. For the
-non-adjacent rules, $i<loc_l(\LOC{h})$ on the left and $j>loc_r(\LOC{h})$ on the
-right, while for the adjacent rules these are equal (respectively).
+non-adjacent rules, $i<loc_l(\LOC{h})$ on the left and
+$j>loc_r(\LOC{h})$ on the right, while for the adjacent rules these
+are equal (respectively)\footnote{For left-stopping with right-first
+  attachments, $j \geq loc_r(\LOC{h})$ since we may have
+  right-attachments below, for left-stopping with left-first
+  attachments we only need $j=loc_r(\LOC{h})$.}.
 
 To avoid some redundancy below, define a helper function $\hat{d}$ as follows:
 \begin{align*}
-  \hat{d}(\SMTR{h},\SDTR{h},\XI,\XJ) = \frac
+  \hat{d}(\SMTR{h},\XI,\XJ) = 
   { \sum_{s \in S} \sum_{\SMTR{\LOC{h}}:\LOC{h} \in s} \sum_{i:i \XI loc_l(\LOC{h})} \sum_{j:j \XJ loc_r(\LOC{h})} c_s(\SMTR{\LOC{h}} : i, j) }
-  { \sum_{s \in S} \sum_{\SDTR{\LOC{h}}:\LOC{h} \in s} \sum_{i:i \XI loc_l(\LOC{h})} \sum_{j:j \XJ loc_r(\LOC{h})} c_s(\SDTR{\LOC{h}} : i, j) }
 \end{align*}
 
 Then these are our reestimated stop probabilities:
 \begin{align*}
-  \hat{P}_{STOP} (STOP|h, left, non\text{-}adj) =
-  \hat{d}(\SEAL{h}, \RGOL{h},<,\geq)  +
-  \hat{d}(\LGOR{h}, \GOL{h},<,=)
+  \hat{P}_{STOP} (STOP|h, left, non\text{-}adj) = \frac
+  { \hat{d}(\SEAL{h},<,\geq) + \hat{d}(\LGOR{h},<,=) }
+  { \hat{d}(\RGOL{h},<,\geq) + \hat{d}(\GOL{h},<,=) }
 \end{align*}
 
 \begin{align*}
-  \hat{P}_{STOP} (STOP|h, left, adj) =
-  \hat{d}(\SEAL{h}, \RGOL{h},=,\geq)  +
-  \hat{d}(\LGOR{h}, \GOL{h},=,=)
+  \hat{P}_{STOP} (STOP|h, left, adj) = \frac
+  { \hat{d}(\SEAL{h},=,\geq) + \hat{d}(\LGOR{h},=,=) }
+  { \hat{d}(\RGOL{h},=,\geq) + \hat{d}(\GOL{h},=,=) }
 \end{align*}
 
 \begin{align*}
-  \hat{P}_{STOP} (STOP|h, right, non\text{-}adj) =
-  \hat{d}(\RGOL{h}, \GOR{h},=,>)  +
-  \hat{d}(\SEAL{h}, \LGOR{h},\leq,>)
+  \hat{P}_{STOP} (STOP|h, right, non\text{-}adj) = \frac
+  { \hat{d}(\RGOL{h},=,>)  + \hat{d}(\SEAL{h},\leq,>) }
+  { \hat{d}(\GOR{h},=,>)  + \hat{d}(\LGOR{h},\leq,>) }
 \end{align*}
 
 \begin{align*}
-  \hat{P}_{STOP} (STOP|h, right, adj) =
-  \hat{d}(\RGOL{h}, \GOR{h},=,=)  +
-  \hat{d}(\SEAL{h}, \LGOR{h},\leq,=)
+  \hat{P}_{STOP} (STOP|h, right, adj) = \frac
+  { \hat{d}(\RGOL{h},=,=)  + \hat{d}(\SEAL{h},\leq,=) }
+  { \hat{d}(\GOR{h},=,=)  + \hat{d}(\LGOR{h},\leq,=) }
 \end{align*}
 
 
@@ -296,12 +431,12 @@ tree, meaning we divide by $1$ per sentence\footnote{Assuming each
 \subsection{Alternate CNF-like rules}
 Since the IO algorithm as described in \citet{lari-csl90} is made for
 rules in Chomsky Normal Form (CNF), we have an alternate grammar
-(figure \ref{cnf-like}) for running testing purposes, 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.
+(table \ref{tab:cnf-like}) for running 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]
+\begin{table*}[ht]
   \centering
   \begin{tabular} % four left-aligned math tabs, one vertical line
     { >{$}l<{$} >{$}l<{$} >{$}l<{$} | >{$}l<{$} }
@@ -326,8 +461,8 @@ CNF, since it includes some unary rewrite rules.
   \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-like}
-\end{figure}
+    $h$.}\label{tab:cnf-like}
+\end{table*}
 
 The inside probabilities are the same as those given in
 \citet{lari-csl90}, with the following exceptions:
@@ -353,14 +488,14 @@ to $P_{OUTSIDE}(\SDTR{h},i,j)$ (eg. $f(s,t,i)$).
 This grammar gave the same results for inside and outside
 probabilities when run over our corpus.
 
-\subsection{TODO: Initialization}
+\subsection{Initialization}
 \citet{klein-thesis} describes DMV initialization using a ``harmonic
 distribution'' for the initial probabilities, where the probability of
 one word heading another is higher if they appear closer to one
 another.
 
-There are several ways this could be implemented. We initialized
-attachment probabilities with the following formula:
+There are several ways this could be implemented. We initialized attachment
+probabilities with the following formula:
 
 \begin{align*}
   P_{ATTACH}(a|h,right) = \frac
@@ -386,37 +521,95 @@ border\footnote{For non-adjacent stopping we checked for occurence at
   {C_{M} + \sum_{s \in S}\sum_{\LOC{h} \in s} C_S+C_N}
 \end{align*}
 
-\subsection{TODO: Results}
-We tried various values for the initialization constants $C_A, C_M, C_S$
-and $C_N$; but it was hard to find any clear pattern for what worked
-best
+Tweaking the initialization constants $C_A, C_M, C_S$ and $C_N$
+allowed us to easily try different inital distributions (eg. to modify
+the initial grammar in the direction of a uniform distribution). The
+next section discusses the effect of these
 
-% todo: check ~/dmv__zero_harmonic_c.txt and paste here
-We compared with a dependency parsed version of the WSJ-10
-corpus. Since single word sentences were not POS-tagged there, these
+\subsection{TODO: Results}
+We compared the results of the implementation with a dependency parsed
+version of the WSJ-10 corpus (converted from the manually annotated
+version). Since single word sentences were not POS-tagged there, these
 were skipped. Also, the dependency parsed WSJ-10 did not have ROOT
-nodes, thus we both checked precision and recall without our ROOT
-dependency, and with a ROOT link added to the parses (where possible;
-221 parses had several heads that were not dependents, here we skipped
-the parses).
-
-Table \ref{tab:dmv-wsj} shows the results of 40 iterations on the full
-WSJ-10 corpus, compared with the dependency parsed version.
-\begin{table*}
+nodes; so we calculated precision and recall both without counting our
+ROOT links, and with counting ROOT links, by adding these to the gold
+parses where possible\footnote{221 parses in the dependency parsed
+  WSJ-10 had several tokens appearing as heads without appearing as
+  dependents in the same parse, here we skipped the parses when
+  calculating with ROOT links.}.
+
+\begin{table*}[hb]
   \centering
-  \begin{tabular}{cccccc}
-    & Rooted  & & & Unrooted & \\
-    P & R & F1 & P & R & F1 
+  \begin{tabular}{l|ccc}
+    Model                         & P             & R              & F1          \\
+    \hline 
+    LBRANCH/RHEAD                 & 25.6          & 32.6           & 28.7        \\
+    RANDOM                        & 31.0          & 39.4           & 34.7        \\ 
+    RBRANCH/LHEAD                 & 55.1          & 70.0           & 61.7        \\
+    K\&M's DMV                    & 46.6          & 59.2           & 52.1        \\
+    Our DMV:                                                                     \\
+    $C_A=0; C_S=1;C_N=0.1;C_M=1$    & 23.7 (23.7)   & 24.8 (24.5)    & 24.2 (24.1) \\ 
+    $C_A=0; C_S=1;C_N=0.1;C_M=10$   & 26.7 (31.6)   & 25.5 (30.5)    & 26.1 (31.0) \\ 
+    $C_A=10;C_S=1;C_N=0.1;C_M=10$   & 24.5 (29.6)   & 25.6 (30.6)    & 25.0 (30.1) \\
+    $C_A=10;C_S=1;C_N=3  ;C_M=10$   & 24.9 (30.0)   & 26.0 (31.0)    & 25.5 (30.5) \\
+    $C_A=15;C_S=3;C_N=1  ;C_M=20$   & 25.6 (30.6)   & 26.7 (31.7)    & 26.2 (31.2) \\
   \end{tabular}
-  \caption{DMV results on the WSJ-10}
+  \caption{DMV results on the WSJ-10 for various initialization values (numbers in parentheses are when counting added ROOT links)}
   \label{tab:dmv-wsj}
 \end{table*}
 
+We tried various values for the initialization constants; but it was
+hard to find any clear pattern for what worked best.
+%$C_N$ values of 10 or less worked well, 
+% todo!!
+
+Table \ref{tab:dmv-wsj} shows the results of running our
+implementation on the WSJ-10 corpus, compared with the dependency
+parsed version, for given values of the initialization constants. The
+EM hilltop seemed to be reached after about 30 iterations for our best
+results (sooner for the worse results). As the table indicates
+(especially the numbers for ``rooted'' evaluation), different initial
+settings can lead to very different results\footnote{One alternative
+  idea we still haven't tried is basing initial DMV stopping
+  probabilities on \emph{distance} from sentence start/end, instead of
+  the ``binary'' test given above.}.
+
+
+The numbers are not completely comparable though, since our corpus was
+6268 sentences, while \citet{km-dmv} report 7422 sentences; also it is
+not clear whether their DMV-experiment was run using automatically
+induced word classes \citep[Sch├╝tze, 1995, in][p.~8]{km-dmv} or on the
+tagset used to manually annotate the WSJ-10.
+
+In the stochastic grammars given by the model after EM, the POS class
+$VBD$ (past tense verb) had the highest probability of being attached
+to by ROOT, followed by $VBZ$ (3sg present) and $VBP$ (non-3sg
+present); which looks promising. Interestingly, on fourth place we see
+the tag $:$, and on sixth, $``$. Results might have been different
+with such tokens stripped from the corpus and the evaluation standard,
+we haven't tried this yet\footnote{A ROOT attachment to $:$ does make
+  sense though, in the same way that a comma might be the head of a
+  conjunction. Our evaluation standard almost always
+  % 97 per cent of the time..
+  puts colons as dependents of the phrase head (often an NP
+  fragment).}.
+
+Just like \citet[p.~89]{klein-thesis} our algorithm chose determiners
+to be the heads of nouns, rather than the opposite.
+% Also, in general
+% non-adjacent stopping was a lot more likely than adjacent stopping, a
+% situation given by the DMV model. 
+
+% \section{The combined model (?)}
+% \subsection{Results (?)}
 
-\section{The combined model (?)}
-\subsection{Results (?)}
-\section{Conclusion}
 
+\section{Conclusion}
+From our implementations it seems that these processes capture some of
+the statistical regularities in language, eg. the strong likelihood of
+verbal sentence heads; however, our evaluations show that we did not
+manage to replicate Klein \& Manning's parsing results, let alone
+improve on them.
 
 
 \nocite{lari-csl90}
index b6f9ac0..6c97920 100644 (file)
@@ -39,7 +39,8 @@ class DMV_Grammar(io.Grammar):
             return "%d=%s" % (n, self.numtag(n))
         def p(dict,key):
             if key in dict:
-                if dict[key] > 1.0: raise Exception, "probability > 1.0:%s"%key
+                if dict[key] > 1.00000001: # stupid floating point comparisons
+                    raise Exception, "probability > 1.0:%s=%s"%(key,dict[key])
                 return dict[key]
             else: return 0.0
         def no_zeroL(str,tagstr,prob):
index dcdc0ba..0081392 100644 (file)
Binary files a/src/loc_h_dmv.pyc and b/src/loc_h_dmv.pyc differ
index 352a5c6..c7b0b5d 100644 (file)
@@ -3,10 +3,10 @@
 from loc_h_dmv import * # better way to do this?
 
 # todo: tweak these
-HARMONIC_C = 0.0
-STOP_C = 1.0
-NSTOP_C = 1.0
-FSTOP_MIN = 1.0
+HARMONIC_C = 0.0 # C_A in report.pdf
+STOP_C = 1.0     # C_S in report.pdf
+NSTOP_C = 1.0    # C_N in report.pdf
+FSTOP_MIN = 1.0  # C_M in report.pdf
 
 FNONSTOP_MIN = 0.0 # for OLD_STOP_CALC. 0.0 on FSTOP_MIN gives many
                    # zero-probabilities for OLD_STOP_CALC
index 94c490f..2ff12f9 100644 (file)
@@ -15,10 +15,10 @@ def initialize_loc_h(tagonlys):
 #     loc_h_harmonic.HARMONIC_C = 380.111684914
 #     loc_h_harmonic.FSTOP_MIN = 13.5744632704
 #     loc_h_harmonic.FNONSTOP_MIN = 34.8939452454
-    loc_h_harmonic.HARMONIC_C = 0.0 # random.random() # 509.63
-    loc_h_harmonic.FSTOP_MIN = 1.0 # random.random() # 13.08 
-    loc_h_harmonic.STOP_C = 1.0 # random.random()
-    loc_h_harmonic.NSTOP_C = 1.0 # random.random()
+    loc_h_harmonic.HARMONIC_C = 20.0 * random.random() # 509.63
+    loc_h_harmonic.FSTOP_MIN = 10.0 # random.random() # 13.08 
+    loc_h_harmonic.STOP_C = 3.0 * random.random() 
+    loc_h_harmonic.NSTOP_C = 1.0 # 5 * random.random() # 0.1
 
     loc_h_harmonic.RIGHT_FIRST = 1.0
     loc_h_harmonic.OLD_STOP_CALC = False
@@ -43,21 +43,36 @@ def initialize_cnf(tagonlys):
     
 
 def test_likelihood(reestimate, initialize, inner_sent,
-                    corpus_size=20, corpus_offset=1000, iterations=4, eval=False):
+                    corpus_size=20, corpus_offset=1000, iterations=4, EVAL=False):
     def run_IO(g, iterations, tagonlys, tags_and_parses):
         sumlog,msg = corpus_likelihood(g, tagonlys)
         print msg
-        if eval: print evaluate(g, tags_and_parses) 
+        if EVAL:
+            E = evaluate(g, tags_and_parses)
+            print E
         for i in range(iterations):
             g = reestimate(g, tagonlys)
-            print "reestimation number %d done"%i
-            if eval: print evaluate(g, tags_and_parses)
-            
+            print "reestimation number %d done\n"%i
+            if EVAL:
+                E = evaluate(g, tags_and_parses)
+                print E
             prev_sumlog = sumlog
             sumlog,msg = corpus_likelihood(g, tagonlys)
             if sumlog < prev_sumlog:
                 raise Exception, msg+"but previous was %s"%prev_sumlog
             print msg
+            # since I want to be able to do stuff with it afterwards:
+            from pickle import dump # let us say g = pickle.load(open('..','rb'))
+            filehandler = open('current_grammar.obj','w')
+            dump(g, filehandler)
+            
+        if EVAL:
+            import pprint
+            print "underproposed:"
+            pprint.pprint(E.underproposed)
+            print "overproposed:"
+            pprint.pprint(E.overproposed)
+        
         return g
 
     def corpus_likelihood(g, tagsonly):
@@ -70,7 +85,7 @@ def test_likelihood(reestimate, initialize, inner_sent,
             else:
                 sumlog += log(p_sent)
         avg = sumlog / len(tagsonly)
-        return (sumlog, "Sum of log P_{sentence}: %.4f (should move towards 0), avg: %s\n"%(sumlog,avg))
+        return (sumlog, "Sum of log P_{sentence}: %.4f (should move towards 0), avg: %s"%(sumlog,avg))
 
     reader = WSJDepCorpusReader(None)
     tagonlys = reader.tagonly_sents()[corpus_offset:corpus_offset+corpus_size]
@@ -79,69 +94,93 @@ def test_likelihood(reestimate, initialize, inner_sent,
 #     from loc_h_dmv import testcorpus
 #     tagonlys = testcorpus
     
-    print "initializing %d sentences..." % corpus_size,
+    print "\ninitializing %d sentences..." % corpus_size,
     g = initialize(tagonlys)
     print "initialized"
     
     g = run_IO(g, iterations, tagonlys, tags_and_parses) # make iterations argument, todo
+    
     return g
 
 
+class Evaluation():
+    "Just a class to hold evaluation-relevant information, sum it up, and print it."
+    def __init__(self):
+        self.underproposed, self.overproposed = {}, {}
+        self.R, self.R_r, self.P, self.P_r = {}, {}, {}, {}
+        for nd in ['num', 'den']:
+            self.R[nd], self.R_r[nd], self.P[nd], self.P_r[nd] = 0, 0, 0, 0
+
+        self.unrooted = 0 # parses where we couldn't add_root
+        self._precision, self._recall, self._precision_r, self._recall_r = 0.0, 0.0, 0.0, 0.0
+        self._F1, self._F1_r = 0.0, 0.0
+        
+    def calc_F1_P_R(self):
+        "F1 = (2 * P * R)/(P + R), harmonic avg. of P and R"
+        self._recall = float(self.R['num']) / float(self.R['den'])
+        self._precision = float(self.P['num']) / float(self.P['den'])
+        self._recall_r = float(self.R['num']+self.R_r['num']) / \
+            float(self.R['den']+self.R_r['den'])
+        self._precision_r = float(self.P['num']+self.P_r['num']) / \
+            float(self.P['den']+self.P_r['den'])
+
+        if (self._precision + self._recall) > 0.0:
+            self._F1 = (2 * self._recall * self._precision) / (self._precision + self._recall)
+        if (self._precision_r + self._recall_r) > 0.0:
+            self._F1_r = (2 * self._recall_r * self._precision_r) / (self._precision_r + self._recall_r)
+        
+    def __str__(self):
+        self.calc_F1_P_R()
+        R_rnum = self.R['num']+self.R_r['num']
+        R_rden = self.R['den']+self.R_r['den']
+        P_rnum = self.P['num']+self.P_r['num']
+        P_rden = self.P['den']+self.P_r['den']
+        str_vals = (self.R['num'],self.R['den'],self._recall,    R_rnum,R_rden,self._recall_r,
+                    self.P['num'],self.P['den'],self._precision, P_rnum,P_rden,self._precision_r,
+                    self._F1, self._F1_r, self.unrooted)
+        return '''R:  %5d/%5d = %s | R_r:  %5d/%5d = %s
+P:  %5d/%5d = %s | P_r:  %5d/%5d = %s
+F1:               %s | F1_r:               %s (unrooted gold parses: %d)'''%str_vals
+                
+        
+
 def evaluate(g, tagged_and_parsed_sents):
-    '''
-    tagged_and_parsed_sents is a list of pairs:
+    ''' tagged_and_parsed_sents is a list of pairs:
     (tagonly_sent, parsed_sent)
 
     R_num += 1 if pair from parsed is in mpp
     R_den += 1 per pair from parsed
 
     P_num += 1 if pair from mpp is in parsed
-    P_den += 1 per pair from mpp 
-
-    F1 = (2 * P * R)/(P + R), harmonisk snitt av P og R
-    '''
+    P_den += 1 per pair from mpp '''
     from loc_h_dmv import mpp
     from wsjdep import add_root
-
-    R, R_r, P, P_r = {}, {}, {}, {}
-    for nd in ['num', 'den']:
-        R[nd], R_r[nd], P[nd], P_r[nd] = 0, 0, 0, 0
-    unrooted = 0 # parses where we couldn't add_root
+    E = Evaluation()
 
     for sent, gold_parse in tagged_and_parsed_sents:
         mpp_sent = mpp(g, sent)
         try: gold_parse = add_root(gold_parse)
-        except ValueError: unrooted += 1
+        except ValueError: E.unrooted += 1
 
         for pair in gold_parse:
-            dict = R
-            if pair[0] == MPPROOT: dict = R_r
+            dict = E.R
+            if pair[0] == MPPROOT: dict = E.R_r
             dict['den'] += 1
             if pair in mpp_sent: dict['num'] += 1
+            else:
+                try: E.underproposed[pair] += 1
+                except KeyError: E.underproposed[pair] = 1
 
         for pair in mpp_sent:
-            dict = P
-            if pair[0] == MPPROOT: dict = P_r
+            dict = E.P
+            if pair[0] == MPPROOT: dict = E.P_r
             dict['den'] += 1
             if pair in gold_parse: dict['num'] += 1
-        
-    recall = float(R['num']) / float(R['den'])
-    precision = float(P['num']) / float(P['den'])
-    recall_r = float(R['num']+R_r['num']) / float(R['den']+R_r['den'])
-    precision_r = float(P['num']+P_r['num']) / float(P['den']+P_r['den'])
-    F1, F1_r = 0.0, 0.0
-    if (precision + recall) > 0.0:
-        F1 = (2 * recall * precision) / (precision + recall)
-    if (precision_r + recall_r) > 0.0:
-        F1_r = (2 * recall_r * precision_r) / (precision_r + recall_r)
-
-    str_vals = (R['num'],R['den'],recall, R['num']+R_r['num'], R['den']+R_r['den'], recall_r,
-                P['num'],P['den'],precision, P['num']+P_r['num'], P['den']+P_r['den'], precision_r,
-                F1, F1_r, unrooted)
-    return '''Recall: %d/%d = %.4f\tRecall_r: %d/%d = %.4f
-Precision: %d/%d = %.4f\tPrecision_r: %d/%d = %.4f
-F1: \t\t%.4f\t\tF1_r: \t\t%.4f (unrooted gold parses: %d)'''%str_vals
-
+            else:
+                try: E.overproposed[pair] += 1
+                except KeyError: E.overproposed[pair] = 1
+            
+    return E
 
 
 
@@ -203,7 +242,7 @@ def rnd_grammars_test():
                             corpus_size=6268,
                             iterations=0,
                             corpus_offset=0,
-                            eval=True)
+                            EVAL=True)
         rnd_grammars0 += [(g, g.HARMONIC_C, g.STOP_C, g.NSTOP_C, g.FSTOP_MIN)]
 
     rnd_grammars1 = [(test_likelihood(loc_h_dmv.reestimate,
@@ -212,7 +251,7 @@ def rnd_grammars_test():
                                       corpus_size=6268,
                                       iterations=1,
                                       corpus_offset=0,
-                                      eval=True),
+                                      EVAL=True),
                       H,S,N,M)
                     for g,H,S,N,M in rnd_grammars0]
     rnd_grammars2 = [(test_likelihood(loc_h_dmv.reestimate,
@@ -221,15 +260,40 @@ def rnd_grammars_test():
                                       corpus_size=6268,
                                       iterations=1,
                                       corpus_offset=0,
-                                      eval=True),
+                                      EVAL=True),
                       H,S,N,M)
                     for g,H,S,N,M in rnd_grammars1]
 
 if __name__ == "__main__":
     print "main.py:"
     
-#     compare_loc_h_cnf()
+    if False:
+        rnd_grammars_test()
+    else:
+        import loc_h_dmv
+        reload(loc_h_dmv)
+        print "\ntrying reestimate v.1 ##############################"
+        g = test_likelihood(loc_h_dmv.reestimate,
+                            initialize_loc_h,
+                            loc_h_dmv.inner_sent,
+                            corpus_size=6268,
+                            iterations=50,
+                            corpus_offset=0,
+                            EVAL=True)
+        print g 
+
+#         print "\ntrying reestimate v.2 ##############################"
+#         g = test_likelihood(loc_h_dmv.reestimate2,
+#                             initialize_loc_h,
+#                             loc_h_dmv.inner_sent,
+#                             corpus_size=5,
+#                             iterations=4,
+#                             corpus_offset=0)
+#         print "main.py: done"
+#         print g
+
 
+#     compare_loc_h_cnf()
 #     import cnf_dmv
 #     reload(cnf_dmv)
 #     print "\ntrying cnf-reestimate ##############################"
@@ -238,27 +302,3 @@ if __name__ == "__main__":
 #                         cnf_dmv.inner_sent,
 #                         corpus_size=5,
 #                         iterations=4)
-
-    rnd_grammars_test()
-
-#     import loc_h_dmv
-#     reload(loc_h_dmv)
-#     print "\ntrying reestimate v.1 ##############################"
-#     g = test_likelihood(loc_h_dmv.reestimate,
-#                         initialize_loc_h,
-#                         loc_h_dmv.inner_sent,
-#                         corpus_size=6268,
-#                         iterations=100,
-#                         corpus_offset=0,
-#                         eval=True)
-#     print g 
-
-#     print "\ntrying reestimate v.2 ##############################"
-#     g = test_likelihood(loc_h_dmv.reestimate2,
-#                         initialize_loc_h,
-#                         loc_h_dmv.inner_sent,
-#                         corpus_size=5,
-#                         iterations=4,
-#                         corpus_offset=0)
-#     print "main.py: done"
-#     print g
index 7840131..7acb519 100644 (file)
Binary files a/tex/formulas.pdf and b/tex/formulas.pdf differ
index b1be8f3..e82b910 100644 (file)
@@ -457,6 +457,42 @@ regular IO algorithm to be run.
 
 
 
+\section{Initialization}
+\citet{klein-thesis} describes DMV initialization using a ``harmonic
+distribution'' for the initial probabilities, where the probability of
+one word heading another is higher if they appear closer to one
+another.
+
+There are several ways this could be implemented. We initialized
+attachment probabilities with the following formula:
+
+\begin{align*}
+  P_{ATTACH}(a|h,right) = \frac
+  {\sum_{s \in S}\sum_{\LOC{h} \in s} \sum_{\LOC{a} \in s:loc(\LOC{a})>loc(\LOC{h})} 1/(loc(\LOC{a})-loc(\LOC{h})) + C_A} 
+  {\sum_{s \in S}\sum_{\LOC{h} \in s} \sum_{\LOC{w} \in s:loc(\LOC{w})>loc(\LOC{h})} 1/(loc(\LOC{w})-loc(\LOC{h})) + C_A}
+\end{align*}
+
+The probability of stopping adjacently (left or right) was increased
+whenever a word occured at a (left or right) sentence
+border\footnote{For non-adjacent stopping we checked for occurence at
+  the second(-to-last) position.}:
+
+\begin{align*}
+  f(stop:\LOC{h},left,adj)=\begin{cases}
+    C_S \text{, if } loc(\LOC{h}) = 0,\\
+    0 \text{, otherwise}
+  \end{cases}
+\end{align*}
+
+\begin{align*}
+  P_{STOP}(stop|h,left,adj) = \frac
+  {C_{M} + \sum_{s \in S}\sum_{\LOC{h} \in s} f(stop:\LOC{h},left,adj)} 
+  {C_{M} + \sum_{s \in S}\sum_{\LOC{h} \in s} C_S+C_N}
+\end{align*}
+
+Tweaking the initialization constants $C_A, C_M, C_S$ and $C_N$
+allowed us to easily try different inital distributions.
+
 
 \bibliography{./statistical.bib}
 \bibliographystyle{plainnat}