[dmvccm.git] / report / report.tex

% merged Kevin's & Emily's reports 2008-09-21 Sun 10:39 with Emerge

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{hyperref}
\usepackage{natbib}

\usepackage{pslatex}
\usepackage{pdfsync}
\pdfoutput=1

\usepackage{qtree}
\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{avm}
\avmfont{\sc}
\avmoptions{sorted,active}
\avmvalfont{\rm}
\avmsortfont{\scriptsize\it}

\usepackage{array} % for a tabular with math in it

\title{The DMV and CCM models}
\author{Emily Morgan \& Kevin Brubeck Unhammer}
\date{15 September 2008}

\begin{document}

\maketitle

\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}
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}}
\newcommand{\RGOL}[1]{\overleftarrow{\overrightarrow{#1}}}
\newcommand{\SEAL}[1]{\overline{#1}}
\newcommand{\LGOR}[1]{\overrightarrow{\overleftarrow{#1}}}
\newcommand{\GOL}[1]{\overleftarrow{#1}}
\newcommand{\LN}[1]{\underleftarrow{#1}}
\newcommand{\RN}[1]{\underrightarrow{#1}}
\newcommand{\XI}{\lessdot}
\newcommand{\XJ}{\gtrdot}
\newcommand{\SMTR}[1]{\dddot{#1}}
\newcommand{\SDTR}[1]{\ddot{#1}}

\subsection{Note on notation}
$i, j, k$ are sentence positions (between words), where $i$ and $j$
are always the start and end, respectively, for what we're calculating
($k$ is between $i$ and $j$ for $P_{INSIDE}$, to their right or left
for $P_{OUTSIDE}$). $s \in S$ are sentences in the corpus. $\LOC{w}$
is a word token (actually POS-token) of type $w$ at a certain sentence
location. If $\LOC{w}$ is between $i$ and $i+1$, $loc(\LOC{w})=i$
following \citet{klein-thesis}, meaning $i$ is adjacent to $\LOC{w}$
on the left, while $j=loc(\LOC{w})+1$ means that $j$ is adjacent to
$\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 the thesis
\citet{klein-thesis} and the ACL paper \citet{km-dmv}:

\begin{tabular}{cc}
Paper: & Thesis: \\
$w$ & $\GOR{w}$ \\
$w\urcorner$ & $\RGOL{w}$ \\
$\ulcorner{w}\urcorner$ & $\SEAL{w}$ \\
\end{tabular}

We use $\SMTR{w}$ (or $\SDTR{w}$) to signify one of either $w, \GOR{w},
\RGOL{w}, \LGOR{w}, \GOL{w}$ or $\SEAL{w}$\footnote{This means that
  $\SMTR{\LOC{w}}$ is the triplet of the actual POS-tag, its sentence
  location as a token, and the ``level of seals''.}.


\subsection{Inside probabilities} 
$P_{INSIDE}$ is defined in \citet[pp.~106-108]{klein-thesis}, the only
thing we need to add is that for right attachments,
$i \leq loc_l(w)<k \leq loc_l(\LOC{a})<j$ while for left attachments,
$i \leq loc_l(\LOC{a})<k \leq loc_l(w)<j$. 

(For now, let
\[ \forall{w}[P_{ORDER}(right\text{-}first|w)=1.0] \] since the DMV implementation
is not yet generalized to both directions.)





\subsubsection{Sentence probability}

$P_s$ is the sentence probability, based on 
\citet[p.~38]{lari-csl90}. Since the ROOT rules are different from the
rest, we sum them explicitly in this definition:
\begin{align*}
  P_s = \sum_{\LOC{w} \in s} P_{ROOT}(\LOC{w}) P_{INSIDE}(\SEAL{\LOC{w}}, 0, len(s))
\end{align*} 

\subsection{Outside probabilities}

\begin{align*}
  P_{OUTSIDE_s}(ROOT, i, j) = \begin{cases}
    1.0 & \text{ if $i = 0$ and $j = len(s)$,}\\
    0.0 & \text{ otherwise}
  \end{cases}
\end{align*}

For $P_{OUTSIDE}(\SEAL{w}, i, j)$, $w$ is attached to under something
else ($\SEAL{w}$ is what we elsewhere call $\SEAL{a}$). Adjacency is
thus calculated on the basis of $h$, the head of the rule. If we are
attached to from the left we have $i \leq  loc_l(\LOC{w}) < j \leq  loc_l(\LOC{h}) < k$, while
from the right we have $k \leq  loc_l(\LOC{h}) < i \leq  loc_l(\LOC{w}) < j$:
\begin{align*}
  P_{OUTSIDE}&(\SEAL{\LOC{w}}, i, j) = \\
  & P_{ROOT}(w) P_{OUTSIDE}(ROOT, i, j) + \\
  & [ \sum_{k > j} ~ \sum_{\LOC{h}:j\leq loc_l(\LOC{h})<k} \sum_{\SMTR{\LOC{h}} \in \{\RGOL{\LOC{h}},\GOL{\LOC{h}}\}} P_{STOP}(\neg stop|h, left,  adj(j, \LOC{h})) P_{ATTACH}(w|h, left) \\
  & \qquad \qquad \qquad \qquad \qquad P_{OUTSIDE}(\SMTR{\LOC{h}}, i, k) P_{INSIDE}(\SMTR{\LOC{h}}, j, k) ] ~ + \\
  & [ \sum_{k < i} ~ \sum_{\LOC{h}:k\leq loc_l(\LOC{h})<i} \sum_{\SMTR{\LOC{h}} \in \{\LGOR{\LOC{h}},\GOR{\LOC{h}}\}} P_{STOP}(\neg stop|h, right, adj(i, \LOC{h})) P_{ATTACH}(w|h, right) \\
  & \qquad \qquad \qquad \qquad \qquad P_{INSIDE}(\SMTR{\LOC{h}}, k, i) P_{OUTSIDE}(\SMTR{\LOC{h}}, k, j) ] 
\end{align*}

For $\RGOL{w}$ we know it is either under a left stop rule or it is
the right daughter of a left attachment rule ($k \leq loc_l(\LOC{a}) <
i \leq loc_l(\LOC{w}) < j$), and these are adjacent if the start point
($i$) equals $loc_l(\LOC{w})$:
\begin{align*}
  P_{OUTSIDE}(\RGOL{\LOC{w}}, i, j) = & P_{STOP}(stop|w, left, adj(i,
  \LOC{w}))P_{OUTSIDE}(\SEAL{\LOC{w}}, i, j) ~ + \\
  & [ \sum_{k < i} ~ \sum_{\LOC{a}:k\leq loc_l(\LOC{a})<i} P_{STOP}(\neg stop|w, left, adj(i, \LOC{w})) P_{ATTACH}(a|w, left) \\
  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{INSIDE}(\SEAL{\LOC{a}}, k, i) P_{OUTSIDE}(\RGOL{\LOC{w}}, k, j) ]
\end{align*}

For $\GOR{w}$ we are either under a right stop or the left daughter of
a right attachment rule ($i \leq loc_l(\LOC{w}) < j \leq
loc_l(\LOC{a}) < k$), adjacent iff the the end point ($j$) equals
$loc_r(\LOC{w})$:
\begin{align*}
  P_{OUTSIDE}(\GOR{\LOC{w}}, i, j) = & P_{STOP}(stop|w, right, adj(j,
  \LOC{w}))P_{OUTSIDE}(\RGOL{\LOC{w}}, i, j) ~ + \\
  & [ \sum_{k > j} ~ \sum_{\LOC{a}:j\leq loc_l(\LOC{a})<k} P_{STOP}(\neg stop|w, right, adj(j, \LOC{w})) P_{ATTACH}(a|w, right) \\
  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{OUTSIDE}(\GOR{\LOC{w}}, i, k) P_{INSIDE}(\SEAL{\LOC{a}}, j, k) ]
\end{align*}

$\GOL{w}$ is just like $\RGOL{w}$, except for the outside probability
of having a stop above, where we use $\LGOR{w}$:
\begin{align*}
  P_{OUTSIDE}(\GOL{\LOC{w}}, i, j) = & P_{STOP}(stop|w, left, adj(i,
  \LOC{w}))P_{OUTSIDE}(\LGOR{\LOC{w}}, i, j) ~ + \\
  & [ \sum_{k < i} ~ \sum_{\LOC{a}:k\leq loc_l(\LOC{a})<i} P_{STOP}(\neg stop|w, left, adj(i, \LOC{w})) P_{ATTACH}(a|w, left) \\
  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{INSIDE}(\SEAL{\LOC{a}}, k, i) P_{OUTSIDE}(\GOL{\LOC{w}}, k, j) ]
\end{align*}

$\LGOR{w}$ is just like $\GOR{w}$, except for the outside probability
of having a stop above, where we use $\SEAL{w}$:
\begin{align*}
  P_{OUTSIDE}(\LGOR{\LOC{w}}, i, j) = & P_{STOP}(stop|w, right, adj(j,
  \LOC{w}))P_{OUTSIDE}(\SEAL{\LOC{w}}, i, j) ~ + \\
  & [ \sum_{k > j} ~ \sum_{\LOC{a}:j\leq loc_l(\LOC{a})<k} P_{STOP}(\neg stop|w, right, adj(j, \LOC{w})) P_{ATTACH}(a|w, right) \\
  & ~~~~~~~~~~~~~~~~~~~~~~~~~ P_{OUTSIDE}(\LGOR{\LOC{w}}, i, k) P_{INSIDE}(\SEAL{\LOC{a}}, j, k) ]
\end{align*}


\subsection{Reestimating the rules} 

\subsubsection{$c$ and $w$ (helper formulas used below)}
$c_s(\SMTR{\LOC{w}} : i, j)$ is ``the expected fraction of parses of
$s$ with a node labeled $\SMTR{w}$ extending from position $i$ to
position $j$'' \citep[p.~88]{klein-thesis}, here defined to equal
$v_{q}$ of \citet[p.~41]{lari-csl90}\footnote{In terms of regular EM,
  this is the count of trees ($f_{T_q}(x)$ in
  \citet[p.~46]{prescher-em}) in which the node extended from $i$ to
  $j$.}:
\begin{align*}
  c_s(\SMTR{\LOC{w}} : i, j) = P_{INSIDE_s}(\SMTR{\LOC{w}}, i, j) P_{OUTSIDE_s}(\SMTR{\LOC{w}}, i, j) / P_s
\end{align*}

$w_s$ is $w_{q}$ from \citet[p.~41]{lari-csl90}, generalized to $\SMTR{h}$ and $dir$:
\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_{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_{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/ATTACH-probabilities (since the old $P$
are used in $P_{INSIDE}$ and $P_{OUTSIDE}$).

\subsubsection{Attachment reestimation} 

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{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(\LOC{h})$ since we want at least one attachment:
\begin{align*}
  \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
where $i<loc_l(\LOC{h})$ (for $\GOR{h}$) or $j>loc_r(\LOC{h})$ (for $\GOL{h}$),
this is implicit in $P_{INSIDE}$.



\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)\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},\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) }
\end{align*}

Then these are our reestimated stop probabilities:
\begin{align*}
  \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) = \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) = \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) = \frac
  { \hat{d}(\RGOL{h},=,=)  + \hat{d}(\SEAL{h},\leq,=) }
  { \hat{d}(\GOR{h},=,=)  + \hat{d}(\LGOR{h},\leq,=) }
\end{align*}


\subsubsection{Root reestimation} 
Following \citet[p.~46]{prescher-em}, to find the reestimated
probability of a PCFG rule, we first find the new treebank frequencies
$f_{T_P}(tree)=P(tree)/P_s$, then for a rule $X' \rightarrow X$ we
divide the new frequencies of the trees which use this rule and by
those of the trees containing the node $X'$. $ROOT$ appears once per
tree, meaning we divide by $1$ per sentence\footnote{Assuming each
  tree has frequency $1$.}, so $\hat{P}_{ROOT}(h)=\sum_{tree:ROOT
  \rightarrow \SEAL{h} \text{ used in } tree} f_{T_P}(tree)=\sum_{tree:ROOT
  \rightarrow \SEAL{h} \text{ used in } tree} P(tree)/P_s$, which turns into:

\begin{align*}
  \hat{P}_{ROOT} (h) = \frac
  {\sum_{s\in S} 1 / P_s \cdot \sum_{\LOC{h}\in s} P_{ROOT}(\LOC{h}) P_{INSIDE_s}(\SEAL{h}, 0, len(s))}
  {\sum_{s\in S} 1}
\end{align*}




\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
(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{table*}[ht]
  \centering
  \begin{tabular} % four left-aligned math tabs, one vertical line
    { >{$}l<{$} >{$}l<{$} >{$}l<{$} | >{$}l<{$} }
    \multicolumn{3}{c}{Rule} & \multicolumn{1}{c}{$P_{RULE}$ ($a[i,j,k]$ in \citet{lari-csl90})}\\ 
    \hline{}
    
    \RN{\GOR{h}} \rightarrow& \GOR{h} &\SEAL{a}        &P_{STOP}(\neg stop|h, right, adj) \cdot P_{ATTACH}(a|h, right) \\
    &&&\\
    \RN{\GOR{h}} \rightarrow& \RN{\GOR{h}} &\SEAL{a}   &P_{STOP}(\neg stop|h, right, non\text{-}adj) \cdot P_{ATTACH}(a|h, right) \\
    &&&\\
    \RGOL{h} \rightarrow& \GOR{h} &STOP       &P_{STOP}(stop|h, right, adj) \\
    &&&\\
    \RGOL{h} \rightarrow& \RN{\GOR{h}} &STOP  &P_{STOP}(stop|h, right, non\text{-}adj) \\
    &&&\\
    \LN{\RGOL{h}} \rightarrow& \SEAL{a} &\RGOL{h}      &P_{STOP}(\neg stop|h, left, adj) \cdot P_{ATTACH}(a|h, left) \\
    &&&\\
    \LN{\RGOL{h}} \rightarrow& \SEAL{a} &\LN{\RGOL{h}} &P_{STOP}(\neg stop|h, left, non\text{-}adj) \cdot P_{ATTACH}(a|h, left) \\
    &&&\\
    \SEAL{h} \rightarrow& STOP &\RGOL{h}      &P_{STOP}(stop|h, left, adj) \\
    &&&\\
    \SEAL{h} \rightarrow& STOP &\LN{\RGOL{h}} &P_{STOP}(stop|h, left, non\text{-}adj) \\
  \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{tab:cnf-like}
\end{table*}

The inside probabilities are the same as those given in
\citet{lari-csl90}, with the following exceptions:

When calculating $P_{INSIDE}(\SMTR{h}, i, j)$ and summing through
possible rules which rewrite $\SMTR{h}$, if a rule is of the form
$\SMTR{h} \rightarrow STOP ~ \SDTR{h}$ or $\SMTR{h} \rightarrow
\SDTR{h} ~ STOP$, we add $P_{RULE}\cdot P_{INSIDE}(\SDTR{h}, i, j)$
(that is, rewrite for the same sentence range); and, as a consequence
of these unary rules: for ``terminal rules'' ($P_{ORDER}$) to be
applicable, not only must $i = j-1$, but also the left-hand side
symbol of the rule must be of the form $\GOR{h}$.

Similarly, the outside probabilities are the same as those for pure
CNF rules, with the exception that we add the unary rewrite
probabilities
\begin{align*}
  \sum_{\SMTR{h}} [&P_{OUTSIDE}(\SMTR{h},i,j)\cdot P_{RULE}(\SMTR{h} \rightarrow \SDTR{h} ~ STOP) \\
          + &P_{OUTSIDE}(\SMTR{h},i,j)\cdot P_{RULE}(\SMTR{h} \rightarrow STOP ~ \SDTR{h})]
\end{align*}
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{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 (eg. to modify
the initial grammar in the direction of a uniform distribution). The
next section discusses the effect of 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; 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}{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 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{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}
\nocite{klein-thesis}
\nocite{km-dmv}
\bibliography{./statistical.bib}
\bibliographystyle{plainnat}

\end{document}