%* Last edited: Jul 21 13:52 1997 (viola)
%\documentstyle[doublespace,authdate]{article}

\documentstyle[11pt,epsf,psfig,authdate,fancyheadings]{article}

\psfigurepath{/homes/viola/funding/scientific_notebook/figures}

\input{macros}
\input{new-macros}
\input{defs}

\showlabelsfalse

\renewcommand{\figures}[3]{
    \begin{figure}[tb!]
        \centering#1\maybepicout{#3} \caption{#2} \label{#3} \end{figure}}

\setlength\topmargin{-0.65in} 
\setlength\oddsidemargin{0.4in}
\setlength\evensidemargin{0.4in}
\setlength\textheight{8.75in} 
\setlength\textwidth{5.6in}
\setlength{\parskip}{\medskipamount}

\lhead{}
\chead{{\bf \sf PROJECT DESCRIPTION}}
\rhead{}
\lfoot{NSF Form 1360}
% \cfoot{NSF Career Development Grant}
\rfoot{\bf Paul Viola (MIT)}
\setlength{\headsep}{0.3in}
\setlength{\footskip}{0.7in}
\setlength{\headrulewidth}{1pt}
\setlength{\footrulewidth}{1pt}

\begin{document}
\pagestyle{fancy}

\bibliographystyle{authdate}

\begin{center}
\vskip 0.1in 
{\LARGE \bf The Natural Log}\\
\vskip 10pt
{\large A proposal for a research project on adaptive user interfaces.}\\
\end{center}

\section{Overview}

We propose research in three distinct areas: i) recognition of
potentially ambiguous handwritten text, equations and diagrams,  ii)
information retrieval from very large databases based on semantic content,
and iii) human computer interfaces.
Success in these areas will require contributions from a diverse set of
disciplines including machine learning, artificial intelligence, neural
networks, linguistics, and algorithmic complexity.  I have experience in
many of these areas and researchers at MIT provide great collaborative
potential in others.

In order to focus our research efforts, we propose to construct a new type
of intelligent computer interface for use in science and engineering, the
{\em Natural Log}.  The Natural Log is a notebook-sized flat display that
combines the merits of a technical notebook with the those of a consulting
expert.  It uses handwriting input to accept text, diagrams, and formulae
and combines this with a powerful information retrieval capability that
allow access to textbooks, previous work, and tools such as circuit
simulators and numerical analysis packages.  The Natural Log's greatest
value is that it can become an active participant in the users' thought
process.  As you take notes, the Natural Log reads and interprets your
writing.  It retrieves relevant documents from an on-line library or from
any part of the World Wide Web.  As you enter an equation or a table of
data, the Natural Log corrects your algebra, offers
simulations of physical or economic systems, or supplies statistical
analysis.  

We intend to explore the applicability of the Natural Log to
education and instruction in science, mathematics, and engineering where it
could be used as a computerized tutor.  Clearly the
process of solving and then writing up an assignment is an invaluable part
of learning. It is our hope that the type of immediate feedback
available from the Natural Log will be of equal value.  Much like a
human tutor, the Natural Log may delay the onset of frustration and
provide related, motivating information.  We intend to provide access to 
on-line information from MIT classes including textbooks, videos of
classes, assignments, solutions, and previous exams.  One important aspect
of our research is automatic indexing of such data 
based on its semantic
content.  A semantic index allows the Natural Log to
automatically provide information that is applicable to the lesson at hand,
and also allow for a free-form exploration of related subjects.

The remainder of this document is divided into three parts: the first
section contains our vision for the Natural Log; the second contains a
description of the scientific challenges that arise; and the third contains
a description of the educational impact of the project.

\section {Scenario}

\figures{ \fbox{\PSW{NotebookPage.ps}} } {An example page from an actual research
  notebook.} {Fig:NotebookPage}

We expect the Natural Log to be useful in science, engineering, education, 
finance, and architecture.  In
order to better describe the potential scope of the Natural Log, let us
analyze a section from an actual research notebook~--~
Figure~\ref{Fig:NotebookPage} shows a scanned section.  On this page the
student is attempting to more fully understand the notion of function
optimization using gradient descent.  He starts out by writing something of
a conjecture: that gradient descent is the ``perfect'' technique when the
function to be minimized is quadratic.  The student then goes on to define
a particular function $c(x) = \alpha x^2$ and attempts to show that his
conjecture is correct.  His next step is to compute the gradient (or
derivative) of $c(x)$.  Notice for clarity he has stated, and enclosed in a
box, the definition of gradient descent.  He then shows that a single step
of gradient descent will take a sub-optimal solution $\hat{x}=k$ to the
optimal solution $\hat{x}=0$.  The student then goes on to analyze a
similar situation where the cost function is the log of an 
exponential\footnote{This type of cost function appears frequently in statistical
  analysis, but the details do not matter here.}.  In order to get a feeling
for the problem he draws a simple qualitative graph of the new cost
function.

The thought process reflected in this notebook is useful for making
progress on difficult problems.
It is the same process that is taught in undergraduate classes where 
the act of writing out the question, stating assumptions and then
manipulating equations is critical for learning.  As an assignment, a
problem such as this is not considered difficult because the student has
been given all of the information he might need: the problem, related
definitions, and possible approaches.  Imagine instead that the user is
simply exploring, doing research, or working on a new type of problem.
Since the guidance of the instructor is absent, much of the information
which makes this problem easy is now missing.  This need not be so.

If the student were to use a system like the Natural Log,
critical related information would always be easily accessible.  For
example, as the user writes out the initial problem statement, the
Natural Log attempts to recognize the text.  The text is then
used to query  on-line resources.
For example, the initial statement could be used to retrieve
information about quadratic functions, function minimization, or
the definition of gradient.


As the student writes out the equation $ c = \alpha x^2 $, the Natural Log
will not only recognize the characters but also determine that this is an
equation.  The interpretation of hand-drawn equations is difficult because
the semantics arise from the geometric relationships between
component characters.  For example, the ``2'' is an exponent because it is
smaller, higher and to the right of the ``x''.  
Once the geometry of an equation is interpreted, the Natural Log can
simplify algebra, 
correct errors, or compute derivatives using the functionality in tools
such as Maple, Mathematica, or Matlab.

Finally at the bottom of the page we see that the student has sketched a
graph of the equation $ c = | x | $.  While this is a simple type of plot,
other graphs might be much more complex.  Whenever a graph of a function is
required, the Natural Log could be used to automatically generate one.
A user need only roughly sketch the axes of the graph, select an equation
and the graph would appear.  

This example scenario is a simple but powerful demonstration of the types
of facilities we can easily foresee including in the Natural Log.  There
are several other very different types of user interactions which we intend
to support.  For example, at the MIT Artificial Intelligence Laboratory
Stahovich, Davis, and Shrobe have worked on a system that can interpret
drawings of mechanical devices, understand their function and suggest
design changes \cite{stahovich-davis-shrobe-96}.  Focusing mostly on higher
level reasoning, their system could not handle ``natural'' looking diagrams
but instead used a special type of drawing program in which there was
little or no ambiguity.  We hope to collaborate with them to build a more
natural tool for mechanical device design.

Along similar lines Koile has constructed a system that can analyze
architectural designs of homes for properties such as ``privacy''
\cite{Koile}.  Her system lacks a user-friendly interface and each plan must
be entered in a painstaking fashion.  Architects typically design buildings
by producing a series of rough sketches.  In collaboration with Koile we
hope to use the Natural Log so that sketches of a floor plan
might be analyzed early in the design process.

\section{Proposed Research Areas}

What prevents us from constructing the Natural Log today?  The simplest
answer is that computers are not intelligent enough to do the task.
Successful software exists that can recognize handwritten words and
characters.  There has been less work on the automatic recognition of
diagrams and equations (see \cite{SaundMoran} for example).  Most current
systems are either confused by or ignore diagrams and equations.  User
input can be ``cleaned up'' so that the lines are straight, but a diagram
representing a mechanical device or electrical circuit remains just a
collection of lines to a computer.  In order to move to complex automatic
analysis, it is necessary that our computers 
have the ability to extract semantic meaning from
drawings and equations.
Construction of the Natural Log will be no easy task.  The
successful system will require two critical components: handwritten text,
equation and diagram recognition and a comprehensive natural language
retrieval system for on-line textbooks, articles and the web.

\subsection{Handwritten Input}

It is our goal to construct a system that will accept unconstrained
handwritten text.  There has been a great deal of research in this area,
and many commercial systems are available.  Research has been divided on
the basis of input: pen-based or optical.  Pen-based systems have attained
high recognition rates from natural handwriting~--~the commercial system
available with the new Apple Newton is especially impressive
\cite{yaeger-lyon-webb-96}.  Optical systems, in part because they have
less information, are not as successful with unconstrained input.  They
have, however, achieved useful levels of performance in limited domains
such as the recognition of handwritten addresses on envelopes
\cite{palumbo-srihari-96}.

We have begun work on the recognition of handwriting using an approach
which is a synthesis of techniques from character recognition and vision.
Simard et al. proposed a system for optical digit recognition that could
learn automatically from examples and could easily take advantage of {\em a
priori} information \cite{Simard-LeCun-Denker}.  Their system is a variant
of nearest neighbor classification, where a character is recognized by
finding the most similar example from the training set.  
Nearest neighbor classification is
quite simple, and reasonably efficient, but requires the user to define a
metric for the comparison of example characters.  
The most widely used metric is
the sum of the squares of the differences between pixels.  This is
equivalent to treating each character as a single vector in a high
dimensional ``character space'', where the components of the vector are the
values of the pixels in the image.  The sum of squares of the differences
between pixels is then simply the squared length of the difference vector
between two characters.

\figures{ \fbox{\pstiny{ThickNine.ps}} \fbox{\pstiny{ThickFour.ps}}
  \fbox{\pstiny{ThinFour.ps}} } {One type of inconsequential difference is pen
  width.  Under a vector difference model the thick four looks more like a
  thick nine than a thin four.} {fig:CharDiffs}

Vector distance is usually a poor choice for classifying characters.  Many
changes in a character do not effect its identity, like scale, small
rotations, and the thickness of the pen used to write the character (see
Figure~\ref{fig:CharDiffs}).  But sum of squared differences does not
differentiate between inconsequential differences such as these and
important differences.  Simard's insight was to take the vector difference
between two characters and to project it onto a sub-space where only {\em
  consequential} differences remain.  The distance in this sub-space is the
Tangent distance\footnote{Simard et al.'s derivation of this insight is
  more complex than this, but their results can be reinterpreted in this
  fashion.}.

The Tangent distance is quite similar to the use of the Mahalanobis
distance for classification \cite{DudaHart}.  The Mahalanobis distance is 
non-isometric, shrinking distance in some axes while
stretching it in others.  
These axes 
are determined by fitting a gaussian distribution to the data.  In
contrast, for the Tangent distance these axes are computed from the
characters themselves using {\em a priori} information.  Both the Mahalanobis and
the Tangent distance are linear techniques and as such they are only valid
when the set of inconsequential variation is also linear.  Since many
inconsequential variations are non-linear in image space,  both approaches are
only approximate.

Unlike approaches that measure images, the Natural Log is a pen-based
system which measures a {\em trajectory} of pen positions versus time.
This representation is called a stroke.  Excluding velocity, the two
representations for a character are almost equivalent: a stroke can be
converted to an image, and in many cases an image can be converted to a
stroke.  But these representations are quite different mathematically.  The
manifold of strokes which have been scaled, rotated or translated is {\em
  linear} in stroke space\footnote{This was originally observed by Ullman
  and Basri in the context of 3D object models
  \cite{UllmanLinearCombination}.}.  As a result, the linearity of the
Mahalanobis and Tangent distance is not a drawback.

\figures{ \fbox{\psW{AllChars.ps}}  } 
{ Examples of the different characters recognized by our demonstration
  program.  } {fig:EMChars}

\figures{ \fbox{\psW{EM3vs3.ps}}  } 
{ A comparison of two different ``3'''s.  At the upper left is the raw
  input.  Moving to the right and down, axes of variability are sequentially
  removed.  Notice that in the final image the two characters are almost identical.} {fig:EM3vs3}

We use a combination of Mahalanobis distance and Tangent distance to
recognize strokes.  In other words some of the axes of variation are
determined using {\em a priori} information like rotation, scale, and
translation.  Other axes are determined by fitting a gaussian to a
collection of characters (these axes are the eigenvectors of the covariance
matrix of the data).  This approach has allowed us to build a recognizer
for twenty five different characters (see Figure~\ref{fig:EMChars} for some
of the characters).  One way to visualize the approach is to look at the
difference between characters after the allowed axes of variation have been
removed.  Figure~\ref{fig:EM3vs3} shows a series of comparisons between two
``3'''s.  In the upper left are the two strokes in their original form.  In
each subsequent figure one additional axis of allowed variation has been
removed.  Notice that eventually the two characters appear almost
identical.

\figures{ \fbox{\psW{NlogSnapshot.ps}}  } 
{ A snapshot of the equation demonstration program.  The user has just
  completed an equation.  The box at the top right shows the current
  interpretation: ``Integrate[Exp[x], x]''.  The box just below that shows
  one possible simplification: ``Exp[x]''.     } {fig:NlogSnap}

The character recognizer works in real-time and has been used as part of a
demonstration system, NLOG, which recognizes equations (see
Figure~\ref{fig:NlogSnap}).  In NLOG  users can write out very simple
equations using twenty five symbols including digits, some letters, and a
number of mathematical operators.  The program then recognizes and parses
the expression where possible (not every type of equation is currently
supported).  The resulting equation can be sent to a Mathematica kernel
that performs algebraic simplification.

\subsubsection{Scope of Future Research}

Our research in the area of handwriting interpretation is in its early
stages.  Not surprisingly the current demo has limited functionality and
makes a large number of errors.  Nevertheless it has pointed out a number
of issues for future research:

{\bf Isolated Character Recognition:} Isolated character recognition performance
is currently about 90\% for writers on whom the system was
trained---perhaps only 75\% percent for new writers.  One major focus for
our research will be improving this performance.  Currently the system
models each character as a single ``average'' character plus allowed axes
of variation.  
Frequently different users will write a single character in very different ways.
Performance should improve if we include multiple models for each
character.  
Both the fact that multiple models are necessary and the models themselves
will be determined automatically from the data.  In order to solve this
problem we take a density
modeling approach
(recent work by \cite{Tipping-Bishop97} provides a theoretical mechanism
for this inference).

{\bf Statistical Models for Disambiguation:} Some characters will never be
easily distinguished, for example a 'zero' and the letter 'o'.  Both
speech and handwriting systems use
statistical language models to differentiate such characters.  
For example, these models can be used to rule out
the possibility that the 'o' in ``for'' is a 'zero'.  Language models are
typically extensions of Markov Models for the production of words and
characters (see \cite{Brown-deSouza-Mercer-Pietra-Lai92} for example).  We
hope to build similar statistical models for other types of handwritten
input like equations, and diagrams.  There is one immediate
difficulty that arises when applying such models: while Markov models are
tractable for linear sequences, like language, they are intractable for more
complex spatial structures.  Inference using Markov models for two
dimensional images is well known to be computationally expensive
\cite{geman-geman}.  We have recently proposed an efficient mechanism for
performing statistical inference on two dimensional images
\cite{DebVio97}.   
One measure of the quality of a statistical model is to draw
samples from that model.  A good language
model will generate samples that look like English text.  A good image
model should generate images that look natural.  Our system can generate
images that are much more realistic  than previous approaches\footnote{See {\tt
    http://www.ai.mit.edu/people/jsd/jsd.doit/Research/TextureSynthesis}
  for many example syntheses.}.   We will extend this model so that it can
be used on the geometric distributions that appear in equations and
diagrams.  

{\bf Contextual Reasoning:} In the final analysis many
types of equations and diagrams may remain ambiguous,  such as
``$sin(x)$''.  Is this the function $sin()$ applied to the argument $x$?  Or
is it the product $s * i * n(x)$?   In many cases
statistical models can be used to decide on the correct
interpretation---$sin(x)$ may be more likely than $s * i * n(x)$.  But such
a model cannot be an unchanging function of time.  The correct
interpretation depends on the local context.  If the previous few equations
involved the variables $s$, $i$ and $x$ and the function $n()$, then the
correct interpretation is likely to be different than if the previous lines
referred to $cos(x)$ and $tan(x)$.  We will construct a representation for
this contextual information so that it can be used by our statistical
models.  Optimal recognition performance then becomes a matter of
retrieving the correct contextual model.

\subsection{Semantic Indices for Very Large Databases} 

After text, equations, and diagrams have been interpreted,  the Natural Log
will be able to retrieve relevant information from a large database of
textbooks, articles, and the World Wide Web.  This information need not be
entirely text-based.  The Natural Log will also be able to retrieve
applicable computational and analysis tools such as circuit simulators,
statistical tests,  and algebraic manipulation tools.  This information
will be retrieved automatically (or perhaps semi-automatically) based on
the contextual information.  

Naturally, we would like to apply techniques from natural language
understanding to this problem.  Unfortunately, the sheer size of the data
to be represented makes this difficult.  At a bare minimum, we wish to
process at least 100,000 documents, each of which may contain any of up to
100,000 different words.  Current natural language systems require
significant computation and would have
difficulty processing this much data.

\subsubsection{The Vector Space Model}

Our current work attempts to improve upon Latent Semantic Indexing (LSI), a
technique that uses The Vector Space Model (VSM) as a
representational basis \cite{gs71}.  
In VSM, a document is represented as a vector 
where each component
is a count of occurrences of a particular word
\footnote{In practice, suffixes are removed and counts are
weighted by their natural frequency \cite{frakes92}.  This is known to
improve performance significantly (we have incorporated these
methods); however, such details are unimportant for this discussion.}.
A collection of documents is a matrix, $D$, where each column is a
document vector $d_{i}$. Queries are similarly represented, making
queries nothing more than documents. The similarity between
two documents, $d_{i}$ and $d_{j}$, is defined to be their inner
product, $d^{T}_{i}d_{j}$, so scoring the relevance of documents to a
query, $q$, reduces to computing $D^{T}q$. This is essentially the
same approach used by many search engines, from library systems
commonly available in universities to the wildly popular Alta Vista
web search engine.

There are several advantages to this approach beyond its mathematical
simplicity. Above all, it is efficient to compute and store the document
matrix.  The document matrix will be sparse,  because most documents will
contain only a few of the 100,000 possible words (i.e. most of the word counts
will be zero).  Thus algorithms for manipulating
the document matrix are quite efficient.
Nevertheless, VSM makes an important tradeoff by sacrificing a
great deal of document structure. Specifically, VSM removes
information about the order and proximity of terms in a document,
losing context that may disambiguate meaning. LSI is one common method
for improving retrieval performance.

LSI modifies the document matrix so that it retains only the most important
information from the original. In particular, LSI uses the singular value
decomposition of the document matrix $ D = USV^{T} $ where $U$ and $V$
contain orthogonal vectors and $S$ is diagonal (see \cite{gvl} for further
properties and algorithms).  From $S$ and $U$ we can define $\hat{S}_k$ and
$\hat{U}_k$ which contain only the largest $k$ singular values and 
corresponding eigenvectors, respectively.
In LSI, each document is projected into a lower dimensional space
$\hat{D} = \hat{S}^{-1}_{k}\hat{U}^{T}_{k}D$.  The resulting document
matrix $\hat{D}$ is of smaller size but still provably represents the most
variation in the original matrix.  In other words, LSI represents documents as
a linear combination of a few orthogonal ``features''. It is hoped that these
features represent meaningful underlying topics present in the
collection.  Queries are also projected into this space.  Scoring the
relevance of documents to a query is therefore
$D^T\hat{U}_k\hat{S}^{-1}_{k}\hat{U}_k^Tq$.

Though it has resisted a formal justification, experiments have shown
that projection onto $\hat{U}_k$ does improve retrieval performance.
Hypotheses abound, including: i) LSI removes noise from the document
set; ii) LSI finds words that are synonyms; iii) LSI finds clusters of
documents.  Whatever it does, LSI operates in a completely
unsupervised fashion without knowledge of the queries that may be
presented to the system.  

\subsubsection{The Optimal Projection Matrix}

We could instead attempt a supervised approach, where we are given a
collection of documents, $D$, a collection of queries, $Q$, and a relevance
matrix $R$ such that $R_{ij} = 1 $ if document $i$ is relevant to query $j$
and $0$ otherwise.  We can use this information to construct an optimal $P$
such that: $D^{T}PP^{T}Q \approx R$.  We find $P$ in two steps: first we
find an $X$ minimizing $\|D^{T}XQ - R\|_{F}$, where $\|\cdot\|_{F}$ denotes
the Frobenius norm of a matrix, then we can attempt to find $P$ by
decomposing $X$ into $PP^{T}$.
Note that $X$ is
the optimal linear transformation of the documents so that when they are
compared to the queries only relevant documents are retrieved.  Since there
is no better {\em linear} transformation it can act as a benchmark for the
VSM retrieval approach.    

Computation of $P$ is not a simple matter.  The matrix $PP^{T}$ is
necessarily symmetric and positive semidefinite.  There is no guarantee
that $X$ will satisfy any of these properties.  In fact, for the
Medline\footnote{
The Medline document collection contains over 1000 documents.  It includes thirty
queries with indications of which documents
have been manually judged relevant to each query.}
document collection $X$ is far from symmetric.  When $X$ is not
symmetric it does not project the documents and the queries in the same way
(as was assumed above).  In order to understand how $X$ acts on documents
and queries we choose to decompose it into two orthogonal projection
matrices with SVD, $X = U_X S_X V_X^{T}$.  The projection matrix for for
$D$ is $U_X S_X^{1/2}$ and the projection matrix for $Q$ is $V_X
S_X^{1/2}$.

We can examine the ``optimal'' projection axes to determine whether they
are similar to the axes selected by LSI.  Figure~\ref{fig:x-pca}a shows the
distribution of Medline documents projected onto the first axis of $U_X$.
Notice that there is a large spike near zero, and a well-separated outlier
spike.  
Subsequent axes of
$U_X$ result in similar distributions.  One way to interpret such axes are
as small clusters of documents: most of the documents have close to zero
dot product and a small cluster of documents have a large dot product.  It
is possible that this axis might correspond to a topic shared by a few
documents.  In contrast, if one were to project the data onto a randomly
selected axis  the resulting distribution is almost gaussian\footnote{
This is predicted by the theoretical analysis of \cite{NN:Diaconis84}.}.
This can be quantified by measuring the kurtosis of the distribution.  For
the medline data the optimal axes yield a kurtosis between 20 and 50 while the
kurtosis of a gaussian is 3.
In contrast, LSI axes yield distributions which are much closer to gaussian.
Figure~\ref{fig:x-pca}b shows the distribution of documents
projected onto the first LSI axis.  This axis yields a distribution with a
much lower kurtosis of 6.9.  This
axis is nothing like a cluster of documents: there is a continuum of dot
product values.


\subsubsection{The TOPIC Representation}

These results strongly suggest that LSI may well be finding projections
which are quite different from the optimal linear projection.
Unfortunately we cannot use the optimal axes, because they are computed
from information which we do not have--a list of documents relevant for
every query.  An alternative might be to search for projection axes with
properties like those of $U_X$.  We conjecture that axes corresponding to a
cluster of documents will yield good performance.   We have experimented
with a number of clustering algorithms but the following simple algorithm
performs equally well:

{\footnotesize

\begin{tt}
\fbox{
\begin{tabular}{rl}
for & each axis you wish to define\\
& Choose a source document\\
& Choose a small number, $k$, of nearest neighbors\\
& Use the centroid of those documents as a projection axis
\end{tabular}
}
\end{tt}
}

We then construct a projection matrix from these vectors, $C$.  For
retrieval, both the document matrix and the query are projected into this
space $D^T C C^T q$.  We call this TOPIC based retrieval because documents
and queries are represented not as a vector of words but instead as a
vector of ``topics''.  The properties of the topic axes are much closer to
the optimal $U_X$ than they are to $\hat{U}_k$.  Figure~\ref{fig:topic}
shows how the collection of documents project onto typical TOPIC vectors.

\figures{ \pswsm{x.ps} \pswsm{pca.ps} } 
{{\bf (A).} Projection of the
  documents onto one of the ``optimal'' linear axes.  The resulting
  distribution has a very high kurtosis (44). {\bf (B).} Projection of the
  documents onto one of the LSI axes.  The resulting
  distribution has a moderate kurtosis of 6.9.} {fig:x-pca}


\figures{ \pswsm{topics.ps} \pswsm{topics2.ps} } {{\bf (A).} The
  distribution of Medline documents when projected onto a TOPIC axis
  (kurtosis=43). {\bf (B).} The distribution of CACM documents (containing
  3200 documents and about fifty queries) using TOPIC
  (kurtosis=25).}
 {fig:topic}


TOPIC based retrieval has several distinct advantages over LSI.  TOPIC is
efficient to compute, while LSI requires a much more complex eigenvector
computation.  TOPIC preserves the sparse nature of the document matrix,
while LSI does not.  The LSI document matrix, $\hat{D} =
\hat{S}^{-1}_{k}\hat{U}^{T}_{k}D$ has many fewer rows than $D$ but it often
contains far more non-zero entries.  Most of the entries in the TOPIC document
matrix, $C^T D$, are close to zero.  Setting them to zero does not reduce
retrieval performance.  Finally, in several experiments TOPIC has
outperformed LSI on retrieval of relevant documents.
Figures~\ref{fig:medresults} and Figure~\ref{fig:cacmresults} show
precision-recall curves for LSI and TOPIC\footnote{
Following convention, we measure the success of a text retrieval
system using precision-recall curves. Given a query, an text retrieval
system ranks each document in a collection. If we restrict the system
to return only its top $n$ documents, we can determine the proportion
of those $n$ documents returned that are actually relevant.  This is
{\em precision}.  We can also compute what proportion of the total
number of relevant documents existing in the database were actually
returned.  This is {\em recall}.  For each $n$, the average precision
and recall over all of the queries is computed and precision plotted
against recall. On these graphs, a curve which is higher implies that
more relevant documents are retrieved out of a group. }.

\figures{ \psW{medline2.ps} } {A comparison of TOPIC and LSI on Medline.
  The x-axis is recall.  The y-axis is precision.  
  For almost every rate of recall, TOPIC yields higher precision than LSI.}
 {fig:medresults}

\figures{ \psW{cacm.ps} } {A comparison of TOPIC and LSI on CACM.
The x-axis is recall.  The y-axis is precision.  
  For almost every rate of recall, TOPIC yields higher precision than LSI.}
{fig:cacmresults} 

\nocite{ob} 
\nocite{kk}

\subsubsection{Scope of Future Research}

This work has pointed out that representing documents as collections of
topics is better than representing them as collections of words.
Nevertheless, performance is still far from perfect and is in fact just
barely acceptable.  We intend to explore several avenues in an effort to
achieve a significant improvement in performance.

{\bf Formal Analysis:} Our current research, like much work in information
retrieval, is empirical.  We will study the vector space model with an eye
toward a theoretical justification both of LSI and TOPIC.  We believe that
a theory based on information transmission will provide a justification for
TOPIC.  Such theories have been influential in signal and image processing
\cite{RG:Bell-Sejnowski-95,VioSchSej95}.


{\bf More Complex Features:} Potential for improving retrieval using the
Vector Space Model is almost certainly limited.  For example, a VSM
representation can never understand that ``National Football League''
has a special unique meaning that is not entirely a function of its
component words.  One possibility is to augment the VSM representation to
include more complex features constructed from combinations of words or
based on parts of speech.  One immediate difficulty arises from the
explosion of possible features.  While there are roughly 100,000 different
words in a large document database, there is an astronomically large
number of word pairs.  We must somehow select from among these potential
features efficiently.  We have had some initial success extracting
multi-word nouns such as ``Euler's number'' and ``differential equation''
from documents as additional features.  We will also explore the role of
part-of-speech tags.

{\bf Extension to Other Types of Documents:} We have recently constructed a
system that performs image database retrieval.  Like text document
retrieval, good image retrieval requires the interpretation of semantic
content.  Our approach, which is reminiscent of VSM, constructs very high
dimensional vectors of features \cite{DebVio97b}\footnote{See {\tt
    http://www.ai.mit.edu/people/jsd/jsd.doit/Research/ImageDatabase/Demo}
  for a demonstration of the system.}.  Retrieval of images is performed
as in VSM, using a dot product.  We intend to explore the role of TOPIC in
image database applications.

We will explore the applicability of our techniques to other types of data
like programs and theorems.

{\bf Document Compression:} One of the largest problems in retrieval is the
huge size of document databases (we have done some experiments with a 3
Gigabyte database).  If it were possible to compress the text,
then part of this difficulty would be removed.  It is important however that
these compressed representations be just as easily compared and retrieved
as the original text.  Recently de~Marken has achieved high compression
rates by removing the redundancies in natural language texts
\cite{demarcken96c}.  The representation that his system constructs reflects
the structure of language and as such is useful for retrieval.  We plan to
collaborate with de~Marken in this area.

{\bf Language Modeling:} Progress in natural language understanding will
have great impact on document retrieval.  Nevertheless because of
computational complexity issues we do not believe natural language
understanding will be possible on huge databases.  Potentially these
systems could however determine that documents are closely related even
though they share few words.  This information could be used in the
construction of TOPIC vectors which could then be used in more efficient
vector-based techniques.   

{\bf Fine Semantic Discrimination:} The different chapters of a textbook on
Differential Equations are all about the same global topic, but each
describes a different sub-topic.  Current retrieval techniques are
overwhelmed by the similarities between these documents and find it
difficult to discover the fine distinctions.  We will explore hierarchical
representations for topics that will expose difference that would be
otherwise overlooked.


\section{Impact on Education}

This project will directly impact the education of students at MIT in many
ways:

{\bf Graduate Education:} The Natural Log has already attracted the
interest of two graduate students who are currently supported with other
funds.  These students have helped significantly in the conception and
early implementation of the handwriting recognition and the natural
language document retrieval systems.  The goals of the Natural Log has
helped them to focus on concrete results and evaluation metrics.  But more
importantly the breadth of the Natural Log has opened their thinking to
other areas of Artificial Intelligence like reasoning and machine
learning.

{\bf Undergraduate Education:} The Natural Log has been an effective
motivational tool for undergraduates.  MIT has two programs which expose
undergraduates to research: the undergraduate research opportunities
program (UROP) and the undergraduate thesis.  Since the conception of the
project six months ago I have had several undergraduates work with me.  They
have immediately responded to the exciting potential of the Natural Log and
have contributed long hours reading papers or writing code.  In our weekly
meetings the students have often surprised me with their accomplishments.  Based on
this positive response, I will attempt to initiate a small seminar focusing
on the science and technology in the Natural Log.

{\bf Teaching Aid:} Throughout the conception of the Natural Log we have
envisioned it both for research and teaching.  The same tools that will
help a researcher solve an unsolved problem can help a student discover the
solution to an assigned problem.  In the final years of this grant we will
have a system that can be tested as an educational tool.  Though it is
tempting to predict that the system will be immediately useful for
students, we expect there to be significant additional work required.  We
will search out collaborators in the areas of course design and pedagogy.


\section{Relationship to Commercial Endeavors}

There has been much commercial interest in pen-based hand-held computers
such as the Newton or the Pilot.  These devices are pioneering attempts in
the effort to build small computers.  But currently there is no commercial
software that attempts to play the role of the Natural Log.  Nevertheless
we expect to benefit from technological advances fostered by these and
related products.  For example we intend to build as little hardware as
possible.  Our focus is on artificial intelligence and machine learning
done with software.  The results of our work will be general purpose
algorithms and insights, not hardware.  We will purchase the best available
pen based computers and where possible use ``off the shelf'' software.  For
example we have evaluated all of the commercially available handwriting
recognition software for use in the Natural Log and none was flexible
enough for our purposes.  We are, however, using commercial mathematical
and simulation software such as Matlab, Mathematica and Spice.

\section{Conclusions}

A successful approach to constructing the Natural Log must combine advances
in machine learning, pattern recognition, linguistics, and algorithms for
ultra-large databases.  Principled solutions to the technical challenges
that we have identified will lead to a very general facility for generating
different types of Natural Logs for many domains.  For example, it should
be possible to create a system to assist a corporate financial officer who
must make a recommendation for an investment.  In this case, the text that
would be indexed would be financial and the operations available would
focus on the estimation of yield and risk.

Preliminary work on the Natural Log has begun.  We are actively studying
handwriting recognition, both of text and figures.  We have also begun work
on the semantic retrieval of text documents.  Though the task ahead is a
large one, we are confident that the Natural Log will eventually become an
valuable tool for the student, scientist or engineer.

\eject 

\lhead{}
\chead{{\bf \sf REFERENCES CITED}}
\rhead{}
\lfoot{NSF Form 1361}
% \cfoot{NSF Career Development Grant}
\rfoot{\bf Paul Viola (MIT)}


{\footnotesize
\bibliography{paper,my,my-papers,irbib,viola,nici-nn}
}

\end{document}