%* Last edited: Apr  7 17:12 1998 (emiller)
%File: AAAI.inst
% These are the instructions for authors of proceedings, working notes,
% and technical reports to be published or distributed by 
% AAAI or the AAAI Press. These instructions are  generic. 
% Consequently, they do not include specific dates, page charges, and so forth. 
% Please consult your specific written conference instructions for 
% details regarding your submission.
%
% Acknowledgments
% The preparation of  the \LaTeX{} and Bib\TeX{} files that
% implement these instructions was supported by Schlumberger 
% Palo Alto Research, AT\&T Bell
% Laboratories, Morgan Kaufmann Publishers, and AAAI Press.
% 
% These instructions were last revised on 1 March 1997. They have been
% copyrighted by the American Association for Artificial Intelligence,
% and are being made available solely for the use and benefit of
% authors preparing papers for AAAI Press publications. No other use
% of these instructions may be made without permission
% in writing from AAAI.

%\documentstyle[aaai,epsf,authdate]{article}
\documentstyle[aaai,epsf]{article}

%\documentstyle[doublespace,epsf]{article}
%\documentstyle[authdate,doublespace,epsf]{article}

%\setlength{\oddsidemargin}{0.0in}     % 1.25in left margin 
%\setlength{\evensidemargin}{0.0in}    % 1.25in left margin (even pages)
%\setlength{\topmargin}{0.0in}           % 1in top margin
%\setlength{\textwidth}{6.5in}           % 6.0in text - 1.25in rt margin
%\setlength{\textheight}{8.3in}            % Body ht for 1in margins
%\addtolength{\topmargin}{-\headheight}  % No header, so compensate
%\addtolength{\topmargin}{-\headsep}     % for header height and separation
\renewcommand{\topfraction}{.8}         % entire page cannot be floats
\renewcommand{\textfraction}{0.20}      % 20% must be text
\renewcommand{\floatpagefraction}{0.80} % 80% of page must be float
\textfloatsep 15pt plus 2pt minus 4 pt 
\floatsep 5pt plus 2pt minus 4 pt 
\intextsep 5pt plus 3pt minus 4 pt 

%\bibliographystyle{authdate}
%\begin{document}

%\thanks{Copyright  \copyright 1998, American
%Association for Artificial Intelligence  (www.aaai.org). All rights
%reserved.}

\title{Ambiguity and Constraint in Mathematical Expression Recognition}
\author{Erik G. Miller \and Paul A. Viola \\ 
Massachusetts Institute of  Technology\\ 
Artificial Intelligence Laboratory \\ 
545 Technology Square, Office 707\\ 
Cambridge, MA 02139\\
emiller@ai.mit.edu~~~~~viola@ai.mit.edu}

\begin{document}
\maketitle
\begin{abstract}
  The problem of recognizing mathematical expressions differs
    significantly from the recognition of standard prose. While in prose
    significant constraints can be put on the interpretation of a character
    by the characters immediately preceding and following it, few such
    simple constraints are present in a mathematical expression. In order
    to make the problem tractable, effective methods of recognizing
    mathematical expressions will need to put intelligent constraints on
    the possible interpretations.  The authors present preliminary results
    on a system for the recognition of both handwritten and typeset
    mathematical expressions.  While previous systems perform character
    recognition out of context, the current system maintains ambiguity of
    the characters until context can be used to disambiguate the
    interpretation. In addition, the system limits the number of
    potentially valid interpretations by decomposing the expressions into a
    sequence of compatible convex regions.  The system uses A-star to search
    for the best possible interpretation of an expression.  We provide a
    new lower bound estimate on the cost to goal that improves performance
    significantly.  
\end{abstract}

\newcommand{\term}[1]{'#1'}

\section{Introduction} 


Handwriting recognition has greatly improved in recent years, in both the
handprinting and cursive domains, yielding commercial systems for a wide
variety of applications (for example \cite{yaeger-lyon-webb-96}).  
\insert\footins{\noindent \footnotesize{Copyright \copyright 1998, American
Association for Artificial Intelligence (www.aaai.org).  All rights
reserved.}}
It may
appear that the problem of mathematical expression recognition is
essentially equivalent to the recognition of standard prose, but there are
critical differences which distinguish the two problems and preclude us
from applying the standard solutions of handwriting recognition to
mathematical expressions.

\section{Mathematical Expression Recognition}

A mathematical expression is a binary image in which collections of black
pixels represent symbols which are at different scales and positions:
\begin{center}
{\LARGE \fbox{ $  5 e^x  $ } } --OR--
\fbox{\epsfysize=.18in
        \epsffile{5ex.ps}}
\end{center}
Our goal is to take a mathematical expression and return a semantic
interpretation:
\begin{center}
{\Large \fbox{\tt 5 * (e~\^~x)}}
\end{center}
This representation can be used for document retrieval or an interactive
algebraic manipulation
system\cite{Fateman96,Okamoto92,LeeWang97,LeeLee94,Lavirotte97,Martin67}.

We adopt a generative model approach for the recognition of mathematical
expressions.  Several authors~\cite{Winkler95,Hull96,Chou89} have noted that
{\em stochastic context-free grammars} (SCFG's) represent a good generative
model for most types of mathematical expressions\footnote{ A stochastic
  context free grammar associates a probability with each production and as
  a result every valid expression can be assigned a non-zero probability.}.
SCFG's enable modeling of many types of relationships such as the pairing
of parentheses, braces, and brackets, and the association of an integral
sign ($\int$) with its differential such as $dx$.  In order to model the
spatial layout of symbols in a mathematical expression, the spatial layout
rules for various productions (like exponentiation) must be also specified,
as in~\cite{Hull96}.  Recognition inverts the generative process and
produce the appropriate semantics\footnote{Others have used stochastic
  grammars as models of generic problems in visual recognition
  \cite{Mjolsness90}.}.

Context-free grammars have proven to be very useful in the parsing of
programming languages \cite{Hopcroft79}.  Recently stochastic context free
grammars have also been applied successfully to the parsing of natural
languages \cite{charniak-93}.  In a programming language the symbols are perfectly
unambiguous and linearly ordered.  But in an image of a mathematical expression
each symbol is ambiguous and there is no natural ordering.  As we will see,
both ambiguity and ordering are critical issues which, if not handled
effectively, will lead to algorithms which are intractable.

In this paper we present a new approach for limiting the number of possible
parses.  We also present a new method for dealing with character ambiguity
so that characters can be interpreted in context rather than in isolation,
and so that no probability threshold must be applied in the character
recognition process.  The search for the most likely interpretation is
performed using A-star search (following the work of \cite{Hull96}).  We
propose a new underestimate to the goal that significantly reduces
computation time.

\subsection{Polynomial Time Parsing}

The parsing of programming languages is a solved problem.  The
Cocke-Younger-Kasami (CYK) algorithm~\cite{Hopcroft79}, a dynamic
programming algorithm, is cubic in the number of characters.  The first
step of CYK is to build a table (or ``chart'') with one entry for every
sub-sequence of symbols.  Each sub-sequence can be indexed by its starting
symbol, a number between 1 and $N$, and its ending symbol, also between 1
and $N$.  There are approximately $\frac{N^2}{2}$ such entries.  The
algorithm then attempts to find the most likely interpretation for each
sub-sequence, an inherently recursive process in which the interpretation
of a long sequence is dependent on the interpretation of shorter
constituent sub-sequences.  The key to computational efficiency is the
observation that a particular sub-sequence will be the constituent of many
larger sub-sequences, yet the computation need only be done once.

The computational efficiency afforded by the CYK algorithm depends on the
existence of a decomposition of the problem into a polynomial number of
unique sub-problems.  This polynomial nature is a direct result of the
linear ordering of text.  If such a linear sequence exists we can with
impunity limit the set of sub-problems to the set of all consecutive
sub-sequences of characters.  Mathematical expressions, which are
collections of symbols arranged in two dimensions, do not have a
straightforward decomposition into a polynomial number of subsets.  

Take for example the expression shown in Figure~\ref{fig:Difficult}.
Written out in Matlab syntax, which relies on a linear ordering of symbols,
it would be ``e~\^~x~*~(A~/~B)''.  In the linear form we can conclude that
'x' is part of the exponential because it is separated from the fraction by
a parenthesis.  In the graphical form 'x' is equally close to the 'A' and
the 'e'.  There is almost no local information from which we can conclude
attachment.  In this case we must rely on contextual information, in the
form of a graphical SCFG, to make the attachment.  Like CYK parsing, in
order to find the best possible parse of a mathematical expression we must
enumerate all possible subsets of symbols.  Since there is no simple linear
constraint we must find some other constraints on the number of allowable
subsets. Other authors have dealt with this issue in several ways.

\begin{figure}[                hbtp]
  \begin{center}
    \leavevmode
    {\epsfysize=.8in
        \epsffile{../thesis/ps_files/exp.eps}}
  \end{center}
  \caption{A simple expression which is difficult to decompose into a small number of subsets.}
  \label{fig:Difficult}
\end{figure}

\subsection{Rectilinear mathematical expressions}

Chou~\cite{Chou89} presents a system in which expressions are represented
as rectangular arrays of terminal symbols. He limits the number of
potential parses dramatically by requiring that the baselines of characters
be within one pixel of their expected location. While this works well for
the simulated data presented, it cannot be expected to extend to
handwritten input, since the variation in handwritten input is frequently
more than a pixel.

\subsection{A recognizer with moderate positional flexibility}
Winkler et al.~\cite{Winkler95} describe a more flexible system in which 
two subexpressions can be considered as part of a larger expression as
long as the second expression is within certain pre-defined regions relative
to the first expression. However, this system imposes severe limits on the 
distance which a symbol can be from another symbol while still being
part of a common subexpression. We wish to avoid this type of limit, as
we believe it will rule out the true answer in some situations. This system
also decides on characters out of context, 
which has problems that are discussed below.

\subsection{Modeling positions of characters as Gaussian variables}
Hull~\cite{Hull96} comes closer to our desired goal, by allowing more
general positioning of terminals and subexpressions relative to each other.
The probability that two subexpressions are in a particular relationship
relative to each other (e.g. one is the subscript of the other) is defined
by a two dimensional Gaussian distribution around the expected position of
the second expression. Hence, the further the second expression is from the
center of the Gaussian defining that relationship, the lower the
probability of that particular operation.

With this more flexible model of character positions, there are no rigid
geometric constraints which can be used to automatically prune away the
exponential number of symbol subsets.  Instead Hull's algorithm attempts to
enumerate all possible subsets, and prunes away those that are very
unlikely.  Because of the potentially exponential number of subsets, Hull
uses A-star search to order the enumeration of subsets. Our implementation
also uses an implementation of A-star search, explained below.

% CUT THIS
%Hull's algorithm begins by enumerating all subsets of size 1. Restricting
%attention to the most likely of these, the algorithm then forms all subsets
%of size 3 (by combining each remaining subset of size 2 with all the
%remaining symbols).  Once again only the most likely subsets are retained.
%By combining pairs of retained subsets, all subsets of size are formed.
%This process continues until there is a single subset of size $N$
%containing all of the symbols.  Without pruning, this agglomerative
%approach will eventually generate all $2^N$ possible subsets\footnote{In
%  fact careful bookkeeping is necessary to insure that many of these
%  subsets are not encountered many times.  Without bookkeeping $N^N$
%  non-unique subsets will be generated.}.  Several heuristics prevent this
%process from exploding: a threshold on likelihood which throws out unlikely
%subsets when they are small, and a greedy ordering of the search which
%focuses attention on the most likely subsets before examining less likely
%subsets.  This is essentially best first search with a pruning criteria.

\subsubsection{A-Star Search}

A-star search is similar to best-first search, but in addition requires
that one produce an underestimate of the ``distance'' to the goal (a full
parse) from a given sub-parse. To apply A-star in a probabilistic setting,
one conventionally uses the negative log likelihood as the notion of
distance. The probability of an interpretation of an image is the product
of the unconditional terminal probabilities multiplied by the probabilities
which stem from the geometry rules. The unconditional terminal
probabilities are an underestimate of the cost to achieve the final
goal~--~an interpretation of the entire image.  This underestimate 
is added to the negative log likelihood of a sub-parse in order to
evaluate whether the sub-parse is a good candidate for expansion.

%Hull's A-star search uses an underestimate of the cost to parse the
%remaining portion of the observed image given a particular sub-parse. He
%does this by using a conservative estimate of the maximum likelihood
%probability for each pixel in the remainder of the image.

We compute the A-star estimate by accumulating maximum likelihood estimates
of the terminals. Hence, the A-star penalty is computed as:

\[
\sum \limits _{c\in \cal{C}} \min \limits _{t\in \cal{T}} \left(-\ln Pr\left(c=t\right)\right)
\]

where $\cal{C}$ is the set of uninterpreted connected components
(terminals) and $\cal{T}$ represents all possible characters in the
grammar.

% CUT THIS
%For a given sub-parse, Hull's underestimate of the
%``distance'' to a full parse is the negative log likelihood of the
%remaining characters appearing as they do given that there was no shot
%noise in the remainder of the image. This gives a useful but weak
%constraint on the search for good parses.
%
%Like Hull we use an A-star search to explore the space of possible
%interpretations.  We incorporate the negative log likelihood generated by
%our character recognizer as an integral part of our conservative completion
%estimate. Intuitively, the idea is that for a partially completed parse,
%one will incur a penalty in parsing the remaining characters which is {\em
%  at least as large} as the the sum of the {\em minimum} negative log
%likelihoods of the remaining characters. This is similar to Hull's idea,
%except that he has thrown away the information for the original character
%recognizer.
%
%This is made a bit clearer
%be transforming into log probabilities.  In that case the log probability of a
%complete interpretation is the sum of the log probabilities of a partial
%interpretation and the interpretation of the remaining parts of the image.
%We can estimate the log probability of the partial interpretation is easily
%available.  The log probability of the remaining interpretation can be
%estimated in two parts: the log probability of the unconditional terminal
%probabilities {\em plus} the log probability of the generated expression.  


\section{Convex Hulls: A new pruning criterion}

\begin{figure}
        \centerline{\epsfysize=0.8in \epsffile{../thesis/ps_files/convex_hull_example.ps}}
        \caption{An expression where convex hulls are useful for pruning
          interpretations.  Note that the probability that the enclosed
          characters are in fact the expression $A^2$ is reasonable.  But
          this subset is eliminated because their convex hull intersects
          the fraction symbol.}
        \label{fig:convex_hull_example}
\end{figure}

As a second method for pruning the search space of parses, we attempt to
prune away possible subsets based on a simple geometric test: a subset of
characters is {\em not allowed} if the convex hull of the subset contains a
character that is not part of the subset\footnote{This rigid rule could be
  converted to a soft constraint in our probabilistic framework.}.  We
define the convex hull of the character to be the smallest convex polygon
that contains all of the pixels which define the character (for handwritten
text the convex hull is the smallest convex polygon which contains all of
the strokes defining the character).  The convex hull of a set of
characters is the convex hull of the union of the convex hulls of each
character in the set (see Figure~\ref{fig:convex_hull_example}).

There are several justifications for this criterion: 
\begin{itemize}

\item It is consistent with the layout rules for typeset expressions and is
  not violated for any of our test data.   In fact, we are unaware of a
  typeset expression for which the constraint is violated.

\item For linear text this criteria is identical to the constraint that
  subsets must contain consecutive symbols.  Any non-consecutive subset
  will have a convex hull that contains a character which is not in the
  set.

\item The algorithms necessary for computing with convex hulls are very
  efficient.  A convex hull of a point set can be computed in $O(n \log
  n)$, where $n$ is the number of points~\cite{CLR91}.  Computing the
  convex hull union of two convex hulls is $O(m + l)$, where $l$ and $m$
  are the number of vertices in the convex hulls.  The intersection of two
  convex hulls can be found in $O(m + l)$ also.


\end{itemize}

Unfortunately it is possible to construct an artificial arrangement of
two dimensional symbols for which this criterion yields no
pruning\footnote{Take a set of very small symbols arranged uniformly
on the circumference of a very large circle.  The convex hull of every
possible subset of symbols is allowable.}.  But, for many two
dimensional mathematical expressions there are roughly $N^3$ allowable
subsets.

Furthermore, some valid expressions violate the convex hull rule described
above.  This could be at least partially remedied by eroding characters a
small amount before the convex hull test is performed.  The preliminary
convex hull results are encouraging (See
Figure~\ref{fig:performance_increase}).

\section{Maintaining ambiguity of character identification}

In addition to dealing with all of the possible arrangements of symbols and
deducing the operations based on relative positions, we must tackle the
problem of disambiguating individual characters.  As already suggested,
ambiguity makes recognition of the whole expression difficult.  We
categorize the problems caused by ambiguity into three groups.

The first we call the ``q-9'' problem, and it is illustrated in
Figure~\ref{fig:three_q_squared}.  There are pairs of characters which are,
without context, impossible to distinguish.  Accurate recognition requires
that multiple character hypotheses be maintained until the ambiguity can be
resolved from context.   There are many examples of confusable characters,
even when the characters are written quite carefully.  For sloppily handwritten text
the overlap among character classes becomes quite large.

\begin{figure}
        \centerline{\epsfysize=1.4in \epsffile{../thesis/ps_files/three_q_squared.ps}}
        \caption{\em {\bf A.} The isolated analysis of a character has
        inherent ambiguities which cannot be resolved without
        context. {\bf B.} Clearly the context here suggests that the
        character is the letter 'q'. {\bf C.} The context in this
        figure suggests the character is the digit '9'.}
        \label{fig:three_q_squared}
\end{figure}

The second type of problem caused by ambiguity we call the ``threshold
problem''.  This is illustrated in Figure~\ref{fig:e_plus_3}. It shows an
example of a situation in which the constraints provided by the grammar
could allow us to successfully interpret the '+', even though out of
context, it would appear extremely unlikely to be a '+'. Any system which
discards hypotheses based on a probability threshold runs the risk of
missing a correct recognition in such cases.

The third type of problem arising from ambiguity is ``interpretation
explosion''.  When multiple hypotheses are maintained for a single
character the number of possible parses grows rapidly.  For example, the
geometric measures of grammar classes such as ``exponentiation expression''
depend upon the baseline of the base of the exponent. When we maintain
ambiguity in the individual characters we must also maintain ambiguity in
these dependent higher level classes. This causes the size of the grammar
to grow by a factor which is roughly equal to the number of character
classes for which we maintain ambiguity. This can make the grammar
impractically large. Below, we discuss a compromise between committing to a
character {\em out of context} (to be avoided) and maintaining all possible
character hypotheses during the parsing process (too complex).

Returning for a moment to previous work, we note that Hull performs a
pre-processing step that recognizes each of the characters in the
expression.  Because this recognition takes place before parsing, it does
not make use of available contextual information.  He is thus vulnerable to
the ``q-9'' problem discussed above.

The following simple analysis demonstrates the necessity of maintaining
multiple character hypotheses in developing a robust system. Suppose we
have a system for which isolated character recognition is correct with
probability $R$.  If an expression consists of $t$ characters, we have
probability $R^t$ of correctly recognizing all of the characters without
contextual information.  With $R=0.95$ and $t=20$, we obtain a surprisingly
low probability, $0.95^{20} \approx 0.36$, of getting every character
right.  This is an {\em upper bound} on the probability we will correctly
parse the entire expression (it is possible that the parse might fail for
other reasons).  Obviously, this upper bound will only shrink if we
recognize larger expressions or allow a more varied set of characters.

The system described in~\cite{Chou89} maintains ambiguity, but in a
limited sense.  For each character it retains only those
interpretations which are above a certain
likelihood.  His character models are Gaussian; he proposes a
threshold at three standard deviations from the mean.  While this may
seem like a conservative threshold, a similar analysis shows that in a
20 character expression, on average one correct character will be
eliminated for more than 5 percent of expressions, since
$1-99.74^{20}\approx 0.0507$.  Also, this scheme may lead to keeping
around large number of character hypotheses in handwriting
recognition, where the characters have large variations.

\begin{figure}
        \centerline{\epsfysize=0.6in
        \epsffile{../thesis/ps_files/e_plus_3.ps}} \caption{An example
        of an expression with a very noisy character. The '+' is very
        difficult to interpret correctly without the context, but with
        constraints provided by the grammar could potentially be
        correctly identified.}  \label{fig:e_plus_3}
\end{figure}


\subsubsection{A Compromise: Maintaining a Hypothesis for Each Character
  Class}


Many of the terminals in our grammar are in the same syntactic class.  As a
result a grammatical analysis can never resolve ambiguity between
them.  So for example if a character is slightly more likely to be a 'b'
than an 'h' there is no syntactic information that can resolve this
ambiguity\footnote{Other forms of contextual
  information might be useful for this sort of problem.  We are currently
  exploring this possibility.}.  We can save a lot of effort by simply
deciding at the outset that the terminal is a 'b'.  On the other hand, as
we saw in Figure~\ref{fig:e_plus_3} the ambiguity in the central symbol can
be resolved through syntactical analysis.  In this case it is important
that multiple hypotheses be maintained.

As a middle ground, between maintaining hypotheses for all possible
terminal symbols and committing to the single most likely character, we
define classes of characters which play the same syntactic role in the
grammar.  Since the characters in these classes are grammatically
equivalent, no constraint from the SCFG can ever be used to disambiguate
members of the class.  Only the single most likely interpretation for each
syntactic class need be maintained.

The concept of syntactic class must be expanded to account for the fact
that characters which are traditionally considered syntactically equivalent
(like 'p' and 'P') may behave differently with respect to the geometric
aspects of the grammar. An example is shown in Figure~\ref{fig:Pf_example},
where the most likely {\em out of context} interpretation of the leftmost
character is {\em lowercase} 'p'.  There is no advantage in maintaining the
hypothesis that the character is a 'q'; it has low probability and all of
the important spatial properties of the glyph as a 'p' (its baseline, for
example) are the same as if it were a 'q'.  This is not true for the
interpretation as a 'P' however, since the baseline under this
interpretation would be higher. And in this case, it turns out that the
most likely {\em context-dependent} interpretation is as a 'P', not as a
'p'.

\begin{figure}
        \centerline{\epsfysize=0.8in \epsffile{../thesis/ps_files/Pf_example.ps}}
        \caption{The first character (a ``p'' or a ``P''?) can only be
          resolved by considering its relationship to the subsequent character.}
        \label{fig:Pf_example}
\end{figure}

This leads to {\em four} terminal classes of {\em letters} (a single class
traditionally) for which we maintain
hypotheses throughout the interpretation process. These classes are
ascending letters, descending letters, small letters (neither ascending nor
descending), and large letters (both ascending and descending). ``P'',
``p'', ``e'', and ``Q'' represent examples from each respective class.
Other authors have used similar classes but not to maintain different
classification hypotheses \cite{Winkler95}.

In addition to these separate letter classes which are based strictly on
their geometric properties, other classes were defined based on their
non-spatial role in the grammar.  For example, other syntactic terminal
classes include: ``zero'', non-zero digits, left parentheses, right
parentheses, and fractions.  Each of these plays a distinctively different
role in the grammar of a mathematical expression.  In all, a separate
hypothesis for each of the 14 different terminal classes is maintained.

\subsection{A New Approach}

Hence, our approach contains three innovations. The first is the geometric
convex hull constraint, which limits the growth of the number of possible
parses of the expression. The second is a new (but still conservative)
A-star completion estimate. The third is the bookkeeping necessary to
maintain an hypothesis for each character class, which allows us to
interpret individual characters using greater contextual information. We
now describe some implementation details of a preliminary system.

\section{Implementation}

Certain assumptions were made in order to get a preliminary system
working. In the typeset version of the
system, it is assumed that all characters are distinct and do not
overlap. We make no attempt to deal with scanner distortion. In fact,
all of the typeset examples in this paper were generated on-line and are 
essentially distortion-free.

\subsection{Overview}
The typeset system takes a binary image as input.  A simple connected
components algorithm is run on the image, generating a list of terminals.
A character recognizer based on the Hausdorff
distance~\cite{huttenlocher-93} is used to generate probabilities that each
connected component or pair of connected components is a particular
character. The set of terminals for the initial system is, according to
class:

\begin{itemize}
\item ascender letters: $b,d,h,i,k,l,t,\delta, A$-$Z$ (except $Q$),
\item descender letters: $g,p,q,y,\gamma$,
\item small letters: $a,c,e,m,n,o,r,s,u,v,w,x,z,\alpha$,
\item ascender/descenders: $f,j,Q,\beta$,
\item binary operators: $+,-,=$,
\item zero: $0$,
\item non-zero digits: $1$-$9$,
\item other symbols (each its own class): $(,),[,],\{,\}$, fraction symbol.
\end{itemize}

While the grammar is much too large to include here (80 classes, 200
productions), it is worth mentioning the following:

\begin{itemize}
\item It is represented in Chomsky Normal Form. This facilitates the
coding of the grammar.
\item It contains productions supporting exponentiation, subscripting,
  fractions, ``loose'' concatenation (multiplication), and ``tight''
  concatenation (the appending of digits in a number).
\item The {\em a priori} probability of each operation is the
  same. Probabilities
of operations are assigned only according to the geometry of the layout and
the probability of their sub-parses.
\end{itemize}

After the program has calculated the probability of each character being in
each class, the program starts the dynamic programming process
which is closely related to the CYK algorithm mentioned before. The
first step in this process is to build the previously mentioned
``table'' in which there is one entry for every sub-sequence of
characters. This can be done in order from the shorter sequences to
the longer sequences, by first computing the probability of each
sequence of length 1, then from these computing the probability of
each sequence of length 2, and so on.

In our implementation, we limit the size of the parse table using a very
conservative restriction on the distance between sub-sequences as an
initial filter and the convex hull criterion described previously as a
second filter. When we finish building the table, the entry which has the
full number of characters and the highest probability represents the best
legal parse of the given mathematical expression.

\def\rowtitle#1{\bf\parbox{0.85in}{\begin{sloppypar}\vspace{0.02in}{#1}\vspace{0.02in}\end{sloppypar}}} 

\newcommand{\minmax}{\parbox[t]{0.8in}{Min x, max x,\\ min y, max y,\\ 
    centroid\\}} 

\newcommand{\data}[3] {\parbox[t]{0.8in}{Prob: #1
    \\Baseline: #2 \\Pt-size: #3\\}} \newcommand{\mytitle}[1]
{\parbox[t]{1in}{#1}}

\begin{figure*}
{\scriptsize
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline

 & {\bf Trmnl 1} & {\bf Trmnl 2} & {\bf Trmnl 3} & {\bf Trmnls 1,2} &
 {\bf Trmnls 2,3} & {\bf Trmnls 1-3} \\ \hline 

\rowtitle{Global properties of the connected component set} & \minmax & \minmax & \minmax &
\minmax & \minmax & \minmax \\ \hline 

\rowtitle{As a small letter} & \data{0.1}{47}{12} &\data{0.05}{55}{13}  &\data{0.05}{52}{10}  & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0}
\\ \hline 

\rowtitle{As a large letter} & \data{0.01}{45}{8} &\data{0.02}{53}{9}  &\data{0.01}{50}{9}  & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0}
\\ \hline 

\rowtitle{As a digit} & \data{0.03}{47}{9} &\data{0.02}{55}{11}  &\data{0.01}{52}{11}  & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0}
\\ \hline 

\rowtitle{As an exponentiation}  & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0} & \data{0.001}{47}{12} &\data{0.00007}{55}{13}  &\data{0.0003}{47}{12} 
\\ \hline 
\rowtitle{As subscript}  & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0} & \data{0.0}{0.0}{0.0} & \data{0.00005}{47}{12} &\data{0.002}{55}{13}  &\data{0.00000043}{47}{12} 
\\ \hline 
\end{tabular}
\caption{Part of a parse table used to do dynamic programming.}
\end{center}
}
\label{fig:bigtable}
\end{figure*}

\subsection{Building the Table}

% Warning I could not get the reference to the table above to work.  I hard
% coded it as 6 below.

Figure~6 shows how the parse table is generated for a sample
mathematical expression show in Figure~\ref{fig:abc}.  The table contains
one column for each subset of terminals, and one row for each possible
interpretation for that subset.  The input to the parsing algorithm is a
set of connected components.  Associated with each component is a
probability vector, containing the conditional probability for each
possible terminal symbol.  As a first step only the most likely terminal
from each syntactic class is retained.  For example, the most likely
interpretation for the leftmost component is as an \term{a}.  Nevertheless
several other hypotheses are maintained: as an ascender it is most likely
to be an \term{O}; as a descender it is most likely to be a \term{q}; as an
ascender/descender it is most likely to be a \term{Q}\footnote{This is a
  very unlikely hypothesis, but it is the best in that class.}, and so on.
In addition to computing these probabilities, we compute certain
interpretation-dependent quantities of the characters such as the baseline
and the point size. They are interpretation-dependent since they are
different for different rows of the table.  Finally, we also compute global
properties of the current connected component group. These properties
include the minimum and maximum coordinates, the centroid, the convex hull,
and so forth.  These global properties only need to be computed once per
connected component group, since they are invariant to the interpretation
of the group.

In addition to the terminal classes there are rows in the table for
compound expressions made up of multiple terminals (e.g. exponentiation,
fractions, binary operations, etc.)  There is
zero probability that these expressions can generate an output with a
single component.

The initial state of the system is shown in the first three columns of the
table.  There is one entry for each distinct component in the image.
Parsing is a process by which new columns are added to the table, each
describing a valid subset of components from the original image.  The table
is expanded toward the right, as large collections of components are
enumerated and evaluated.

There are three possible two-character combinations of the three
characters. However, if the two characters fail the convex hull test
described above, as with the ``a'' and the ``d'' in our example, then an
entry in the table will not be made.  Since the two component groups cannot
be interpreted as a single terminal, these rows are flagged as
impossible.  As new columns are added to the table, the
interpretation-dependent and global properties of the group are computed.

The final column in the table shows probabilities of interpretations of the
entire expression.  Column~6 shows that the correct interpretation (as an
exponentiation at the highest level) has the highest probability, so in
this case the procedure worked properly.

\begin{figure}
  \centerline{\epsfysize=1.0in \epsffile{../thesis/ps_files/abc.ps}}
  \caption{The sample mathematical expression used in the description of
    table building. Notice that no entry was made in the table for the
    two-character combination of characters ``a'' and ``d''. This is
    because the a-d pair do not fit the convex hull criterion.}
  \label{fig:abc}
\end{figure}

\section{Experiments}
To verify the basic functionality of the system, we performed a simple
series of tests. For each letter $x$ in the system, the following
expressions were used as inputs to the system: $x_x$, $x^x$, $x^{x_x}$, $x
\over x$. Where allowed by the grammar, the digits were also used in these
tests. All of these test images were evaluated correctly by the system.

We attempted to evaluate the effectiveness both of the the convex hull
pruning constraint and A-star search using our underestimate of the
distance to goal.  Without using either type of heuristic, parse times were
very long -- on the order of minutes.  Using both criteria parse times are
in the seconds.  In order to quantify this we created a series of
expressions of varying complexity from 3 terminals to 20 terminals.  On the
left of Figure~\ref{fig:performance_increase} is the performance of the
A-star system with and without the convex hull constraint.  On the right is
the performance using the convex hull constraint with and without the
A-star heuristic\footnote{The points on the two graphs are the same set of
  expressions, the graph on the left contains fewer points because the
  computation time for A-star without convex hull pruning grows far too
  rapidly for us to measure.  We simply gave up after many minutes of run
  time.} .  There is significant improvement in performance using either of
these heuristics, and even greater improvement when both are used.  We
collected data from the system running without either heuristic, but this
curve quickly exists the top of the graph.

% CUT THIS????
It is interesting to note how the system performed on ``illegal'' images,
for example the expression $0^{0_0}$. This input is considered illegal
since our grammar provided no mechanism for subscripting a number.  As a
result the system recognized the input as the expression ``600''.  This can
be understood as follows: since the system could not generate $0_0$, it
apparently concluded that the last two zeroes were effectively the same
size. However, the output $0^{00}$ would also be illegal since a two digit
number cannot begin with a $0$.  The system's fix was to consider all three
digits as being approximately the same size, and then using a much less
likely, but legal interpretation of the first digit, it settled on ``600''
as the best interpretation.  This example illustrates a good deal about the
system's flexibility in generating reasonable answers in tough situations.

Anecdotal examples of expressions which the system successfully parsed are
given in Figure~\ref{fig:working_examples}. The actual time spent parsing
these expressions on a 266MHz Pentium Pro was approximately 4, 0.2, 16, and
25 seconds. This does not include the time to generate character hypotheses
for the connected components. These examples are not
difficult, but they validate the basic method and show that it is feasible
to do the extra bookkeeping which we have incorporated in this system.  The
only failures in the current typeset system were due to mis-recognition of
characters.

\begin{figure}
  \centerline{\epsfysize=1.8in \epsffile{../thesis/ps_files/performance_increase.ps}}
  \caption{The left graph shows the pruning of the
    search space by the convex hull criterion. The right graph shows the
    performance gained by adding the A-star constraint. The algorithm
    reduces to best-first search without the A-star constraint.
}
  \label{fig:performance_increase}
\end{figure}

\begin{figure}
\begin{center}
{\Large
\fbox{\parbox[t]{1.3in}{$$((t+m)+wt)$$}}
\fbox{\parbox[t]{1.3in}{$$b_f p_a$$}}
\fbox{\parbox[t]{1.3in}{$$k_2^9+{{{3 \over 2}+o^5}\over{e_6+z_7}}$$}}
\fbox{\parbox[t]{1.3in}{$${123 \over {456^7+{{2 \over 4} \over {a+b+c_d}}}}$$}}
}
\end{center}
        \caption{Some of the expressions successfully recognized by the
                 system.}  
        \label{fig:working_examples}
\end{figure}


\section{Future Work}

A major focus in developing this system was to prepare for the migration to
handwritten mathematical expressions.  Our preliminary work with
handwritten expressions is illustrated in Figure~\ref{fig:EqEx}. We show
three examples, the first of which was parsed correctly, the second of
which contains a geometry-based error, and the third of which contains a
character-identification error. We hope that by improving the character
recognizer and learning the parameters of our geometry models that we can
significantly improve the performance of the system in the future. While
the accuracy of the current system needs great improvement, we feel we have
laid the groundwork for a practical system's implementation.

\begin{figure}
  \centerline{\epsfysize=1.8in \epsffile{../thesis/ps_files/EqEx.ps}}
  \caption{Some examples of handwriting and their parses.}
  \label{fig:EqEx}
\end{figure}

\section{Acknowledgments}
We would like to thank Tom Rikert and Nicholas Matsakis for contributions
and discussions related to this work.

%\bibliography{main}
\bibliography{main}
\bibliographystyle{aaai}

\end{document}



