report almost done

[dmvccm.git] / tex / formulas.tex

% Created 2008-06-13 Fri 17:05

% todo: fix stop and attachment formulas so they divide before summing

\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{DMV formulas}
\author{Kevin Brubeck Unhammer}
\date{21 August 2008}

\begin{document}

\maketitle

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}.

\tableofcontents

\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}}

\section{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.

Notational differences between the thesis \citep{klein-thesis} and the
paper \citep{km-dmv}:

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

I 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''.}.


\section{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.)





\subsection{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*} 

\section{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*}


\section{Reestimating the rules} % todo

\subsection{$c$ and $w$ (helper formulas used below)}
% todo: left out rule-probability! wops (also, make P_{fooside}
% sentence-specific)

$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_{CHOOSE}(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_{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$
are used in $P_{INSIDE}$ and $P_{OUTSIDE}$).

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

Here $j>loc_r(\SMTR{\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) }
\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}$.



\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*}

\subsection{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).

To avoid some redundancy below, define a helper function $\hat{d}$ as follows:
\begin{align*}
  \hat{d}(\SMTR{h},\SDTR{h},\XI,\XJ) = \frac
  { \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},<,=)
\end{align*}

\begin{align*}
  \hat{P}_{STOP} (STOP|h, left, adj) =
  \hat{d}(\SEAL{h}, \RGOL{h},=,\geq)  +
  \hat{d}(\LGOR{h}, \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,>)
\end{align*}

\begin{align*}
  \hat{P}_{STOP} (STOP|h, right, adj) =
  \hat{d}(\RGOL{h}, \GOR{h},=,=)  +
  \hat{d}(\SEAL{h}, \LGOR{h},\leq,=)
\end{align*}


\subsection{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*}

% todo: the following just didn't turn out right, but it ought to be
% possible to use this to check the CNF-like unary attachments...
%
% The root attachment is just a unary PCFG rule $ROOT \rightarrow
% \SEAL{h}$. Modifiying binary rule reestimation from
% \citet[p.~41]{lari-csl90} to unary rules gives:

% \begin{align*}
%   \hat{P}_{RULE}(ROOT \rightarrow \SEAL{h}) = \frac
%   { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} 1/P_s \cdot P_{RULE}(ROOT \rightarrow \SEAL{h})P_{INSIDE_s}(\SEAL{h}, i, j)P_{OUTSIDE_s}(ROOT, i, j) }
%   { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} c_s(\SEAL{h}, i, j) }
% \end{align*}

% Since $P_{OUTSIDE}(ROOT, i, j)$ is $1$ if $i=0$ and $j=len(s)$, and $0$ otherwise, this reduces into:

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





\section{Alternate CNF-like rules}
Since the IO algorithm as described in \citet{lari-csl90} is made for
rules in CNF, we have an alternate grammar (figure \ref{cnf-like}) for
running parallell 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]
  \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{cnf-like}
\end{figure}

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)$).

The reestimation just needs to be expanded to allow unary stop rules,
this is similar to the formula for binary rules in
\citet[p.~41]{lari-csl90}:
\begin{align*}
  \hat{P}_{RULE}(\SMTR{h} \rightarrow \SDTR{h}) = \frac
  { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} 1/P_s \cdot P_{RULE}(\SMTR{h}\rightarrow \SDTR{h})P_{INSIDE}(\SDTR{h}, i, j)P_{OUTSIDE}(\SMTR{h}, i, j) }
  { \sum_{s\in S} \sum_{i<len(s)} \sum_{j>i} c_s(\SMTR{h}, i, j) }
\end{align*}
(the denominator is unchanged, but the numerator sums $w_s$ defined
for unary rules; $\SMTR{h}\rightarrow \SDTR{h}$ is meant to include both left and
right stop rules).

% todo: add ROOT rule to CNF grammar?


\section{Pure CNF rules}
Alternatively, one may use the ``pure CNF'' grammar of figure
\ref{cnf-T} and figure \ref{cnf-NT}, below (not yet
implemented). Using the harmonic distribution to initialize this will
still yield a mass-deficient grammar, but at least this allows the
regular IO algorithm to be run.

\begin{figure}[htp]
  \centering
  \begin{tabular} % four left-aligned math tabs, one vertical line
    { >{$}l<{$} >{$}l<{$} >{$}l<{$} | >{$}l<{$} }
    \multicolumn{3}{c}{Rule} & \multicolumn{1}{c}{$P_{RULE}$ ($b[i,m]$ in \citet{lari-csl90})}\\ 
    \hline{}
    
    h    \rightarrow&   \text{``h''}&         &1 \\
    &&&\\
    \SEAL{h}   \rightarrow&   \text{``h''}&         &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, adj) \\
    &&&\\
    ROOT  \rightarrow&   \text{``h''}&         &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, adj) \cdot  P_{ROOT}(h) \\
  \end{tabular}
  \caption{Terminals of pure CNF rules, defined for all POS-tags
    $h$.}\label{cnf-T}
\end{figure}

\begin{figure}[htp]
  \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{}
    
    \SEAL{h}   \rightarrow&    h &\SEAL{a}   &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, non\text{-}adj) \\
    &&&\cdot  P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \\[3.5pt]
    \SEAL{h}   \rightarrow&    h &\GOR{.h}   &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, non\text{-}adj) \\[3.5pt]
    \GOR{.h}   \rightarrow& \SEAL{a} &\SEAL{b} &P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \\
    &&&\cdot  P_{ATTACH}(b|h, right)\cdot P_{STOP}(\neg stop|h, right, non\text{-}adj) \\[3.5pt]
    \GOR{.h}   \rightarrow& \SEAL{a} &\GOR{h} &P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \\[3.5pt]
    \GOR{h}   \rightarrow& \SEAL{a} &\SEAL{b} &P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, non\text{-}adj) \\
    &&&\cdot  P_{ATTACH}(b|h, right)\cdot P_{STOP}(\neg stop|h, right, non\text{-}adj) \\[3.5pt]
    \GOR{h}   \rightarrow& \SEAL{a} &\GOR{h} &P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, non\text{-}adj) \\[3.5pt]
    \SEAL{h}   \rightarrow& \SEAL{a} &h &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{STOP}(stop|h, right, adj) \\
    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \\[3.5pt]
    \SEAL{h}   \rightarrow& \GOL{h.} &h &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{STOP}(stop|h, right, adj) \\[3.5pt]
    \GOL{h.}   \rightarrow& \SEAL{b} &\SEAL{a} &P_{ATTACH}(b|h, left)\cdot P_{STOP}(\neg stop|h, left, non\text{-}adj) \\
    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \\[3.5pt]
    \GOL{h.}   \rightarrow& \GOL{h} &\SEAL{a} &P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \\[3.5pt]
    \GOL{h}   \rightarrow& \SEAL{a} &\SEAL{b} &P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, non\text{-}adj) \\
    &&&\cdot  P_{ATTACH}(b|h, left)\cdot P_{STOP}(\neg stop|h, left, non\text{-}adj) \\[3.5pt]
    \GOL{h}   \rightarrow& \GOL{h} &\SEAL{a} &P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, non\text{-}adj) \\[3.5pt]
    \SEAL{h}   \rightarrow& \GOL{h.} &\SEAL{\GOR{h}} &P_{STOP}(stop|h, left, non\text{-}adj) \\[3.5pt]
    \SEAL{h}   \rightarrow& \SEAL{a} &\SEAL{\GOR{h}} &P_{STOP}(stop|h, left, non\text{-}adj) \\
    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \\[3.5pt]
    \SEAL{\GOR{h}}  \rightarrow& h &\GOR{.h} &P_{STOP}(stop|h, right, non\text{-}adj) \\[3.5pt]
    \SEAL{\GOR{h}}  \rightarrow& h &\SEAL{a} &P_{STOP}(stop|h, right, non\text{-}adj) \\
    &&&\cdot  P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \\[3.5pt]
    ROOT  \rightarrow& h &\SEAL{a} &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, non\text{-}adj) \\
    &&&\cdot  P_{ATTACH}(a|h, right)\cdot P_{STOP}(\neg stop|h, right, adj) \cdot  P_{ROOT}(h) \\[3.5pt]
    ROOT  \rightarrow& h &\GOR{.h} &P_{STOP}(stop|h, left, adj) \cdot  P_{STOP}(stop|h, right, non\text{-}adj) \cdot  P_{ROOT}(h) \\[3.5pt]
    ROOT  \rightarrow& \SEAL{a} &h &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{STOP}(stop|h, right, adj) \\
    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \cdot  P_{ROOT}(h) \\[3.5pt]
    ROOT  \rightarrow& \GOL{h.} &h &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{STOP}(stop|h, right, adj) \cdot  P_{ROOT}(h) \\[3.5pt]
    ROOT  \rightarrow& \GOL{h.} &\SEAL{\GOR{h}} &P_{STOP}(stop|h, left, non\text{-}adj) \cdot  P_{ROOT}(h) \\[3.5pt]
    ROOT  \rightarrow& \SEAL{a} &\SEAL{\GOR{h}} &P_{STOP}(stop|h, left, non\text{-}adj) \\
    &&&\cdot  P_{ATTACH}(a|h, left)\cdot P_{STOP}(\neg stop|h, left, adj) \cdot  P_{ROOT}(h) \\[3.5pt]
  \end{tabular}
  \caption{Non-terminals of pure CNF rules, defined for all POS-tags
    $h$, $a$ and $b$.}\label{cnf-NT}
\end{figure}



\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}

\end{document}