%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	Final version (almost) -- for publication in IJCAI 97
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\documentstyle[ijcai97]{article}
%\documentstyle[twocolumn,fleqn]{article}
%\documentstyle[aaai]{article}

\input epsf

%\include{psfig}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  Line Spacing (e.g., \ls{1} for single, \ls{2} for double, even \ls{1.5})
%%  This macro was borrowed from Jim Kurose

% \newcommand{\ls}[1]
%   {\dimen0=\fontdimen6\the\font
%    \lineskip=#1\dimen0
%    \advance\lineskip.5\fontdimen5\the\font
%    \advance\lineskip-\dimen0
%    \lineskiplimit=.9\lineskip
%    \baselineskip=\lineskip
%    \advance\baselineskip\dimen0
%    \normallineskip\lineskip
%    \normallineskiplimit\lineskiplimit
%    \normalbaselineskip\baselineskip
%    \ignorespaces
%   }

%%** you'll want this if you have anything but single spacing
%% Fixes the bad spacing in footnotes

\newcommand{\fn}[1]
           {\footnote{\ls{1.0}#1}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Style

% Horizontal
%\textwidth      7.15truein
%\oddsidemargin  -0.30truein %-0.35truein
%\evensidemargin -0.30truein %-0.315truein
%
%% Vertical
%\textheight     8.75truein
%\topmargin      -0.75truein
%\headheight     0.5truein
%\headsep        0.375truein
%\footheight     0.25truein
%\footskip       0.50truein
%
%\setlength{\parindent}{20.0pt}

\begin{document}

%\ls{2}

\title{ Translingual Information Retrieval: \\
A Comparative Evaluation
}
% \author{
%{\bf Jaime Carbonell} \\
%{\bf Yiming Yang} \\
%{\bf Robert Frederking} \\
%{\bf Ralf Brown} \\
%{\bf Yibing Geng} \\
%{\bf Daniel Lee}
% }
% \date {}

\author{
Carbonell, Jaime G.; Yang, Yiming; Frederking, Robert E.; \\
{\bf Brown, Ralf D.; Geng, Yibing; Lee, Danny} \\ \\
Language Technologies Institute, Carnegie Mellon University \\
5000 Forbes Avenue, Pittsburgh, PA  15213  USA \\ \\
% Content Areas:  Information retrieval and gathering \\
% Tracking Number: A896
}
\date {}
\title{Translingual Information Retrieval: \\
A Comparative Evaluation
}

\maketitle

%\newpage
\begin{abstract}
Translingual information retrieval (TIR) consists of providing a query in
one language and searching document collections in one or more
different languages.  This paper introduces new TIR methods and
reports on comparative TIR experiments with these new methods and
with previously reported ones in a realistic setting.  Methods
fall into two categories: query translation based, and statistical-IR
approaches establishing translingual associations.
The results show that using bilingual corpora for automated extraction
of term equivalences in context outperforms other methods.
Translingual versions of the Generalized Vector Space Model (GVSM) and
Latent Semantic Indexing (LSI) perform relatively well, 
as does translingual pseudo relevance feedback (PRF). All showed
relatively small performance loss between monolingual and translingual
versions.  Query translation based on a general machine-readable
bilingual dictionary -- heretofore the most popular method -- did not 
match the performance of other, more sophisticated methods.  Also, the
previous very high LSI results in the literature were disconfirmed 
by more realistic relevance-based evaluations.


% \begin{abstract} -- OLD
% Translingual information retrieval consists of
% providing a query in one language 
% and searching document collections in one or more different languages.
% A set of experiments in a realistic retrieval context to
% evaluate a variety of machine-translation-based and IR-based
% translingual retrieval methods, including Latent Semantic Indexing (LSI)
% are presented.  The results show the Generalized Vector Space Model
% retrieves translingually about 85\% of the same documents as for
% monolingual retrieval.  LSI performed about the 80\% level;
% corpus-based query-term translation performed
% about 70\%; and translingual pseudo-relevance feedback performed 
% about 65\% on our ranked retrieval task of the most relevant 150 
% to 200 documents.  

% \begin{abstract} -- VERY OLD 
% Translingual information retrieval consists of
% providing a query in one language 
% and searching document collections in one or more different languages.
% A set of experiments in a realistic retrieval context to
% evaluate a variety of machine-translation-based and IR-based
% translingual retrieval methods, including Latent Semantic Indexing (LSI)
% are presented.  The results indicate that the best IR-based methods 
% dominate term-based machine translations of the query,
% with the Generalized Vector Space Model performing as well as LSI.  
% However, neither translingual LSI nor machine translation behave
% the same in the reported realistic query-based retrieval tasks as 
% they had in earlier more artificial studies (Dumais 1966).

% 150 words max.  Paper is 5000 words max.  (About 6.5 pages)
\end{abstract}

%Title and abstract separate from body of paper

%\newpage

% This level of spacing gives us just under 40 lines per page
%\ls{1.2}

\section{Introduction}

Translingual information retrieval (TIR) is starting to receive considerable
attention in recent years with the increased accessibility of ever-more-diverse
on-line international text collections, including centrally the World
Wide Web. In spite of
some pioneering work \cite{salt70,duma96,davis:trec4,hull:sigir96}, evaluations of
different TIR techniques in realistic retrieval tasks are rare.
This paper reports our evaluation results of both newly developed
TIR techniques and reimplementations of previously reported
techniques.

Translingual information retrieval (aka ``multilingual'' or 
``crosslingual'' IR) consists of providing a query in one language 
and searching document collections in one or more different languages.
One can envision many ways to bridge the language barrier between 
query and collection. In this paper,  we focus on query translation
and methods based on automatically establishing translingual associations
between queries and documents without need of translating either.



%  jgc:
%  6. Add references to literature, including citation, review
%	of other work, etc.  This is the part that was lost
%	Yiming will need to provide info to Bob
%	(all the bibliography references exist in tir.bib )

\section{MT-Based Methods for TIR}

The {\em machine translation methods} for TIR require that either the 
query be translated
into the target language, and the translation be used to search the
target-language collection, or the collection be translated into the
source language, and the original query be used to search.  
Let us consider the pros and cons of each approach:
\begin{itemize}
\item {\em Translation Accuracy} -- Both human and machine translation
\cite{carb85mt,nire91mtbook} require context to achieve accuracy.
Translating isolated words in a query is unreliable, % at best, 
due to unresolved lexical ambiguity.  Translating documents
should yield greater accuracy.
%  but in practice, current
% MT systems' output remains far from perfect.

\item {\em Retrieval Accuracy} -- Since documents contain far
more information than queries, random translation errors should
cause less degradation for the IR task in documents than
in queries.  Hence for both this reason and the above,
document translation is in principle preferable.  In fact, preliminary
findings by Dumais {\it et al} \cite{duma96} support this
line of reasoning.

\item {\em Practicality} -- Many document collections
are very large.  Most are searched remotely.  Some are
proprietary; individual documents may be read or downloaded, but the entire
collection may not be copied or translated.  Even if these problems
were surmountable, translating the collection may
require inordinately long computation and massive storage,
not to mention re-indexing the translated collection.
% Hence, translating the collection 
% at run time is at best impractical, and only pre-translation
% and pre-reindexing (at significant storage cost) presents
% a viable alternative.
\end{itemize}

Because of the above practicality constraint, we report only on
translating the query for TIR.  If the query were formulated
as phrases, as a full sentence, or as a paragraph, we could apply MT systems 
far more reliably.  However, experience shows that
users typically prefer to give isolated words, or
at best short phrases to an IR system.\footnote{LYCOS reports
that their typical user queries for general web search
are only one to three words long, although they are
occasionally reformulated into longer queries.}  The question
is how to best translate a set of isolated words.  Full
fledged MT is not applicable.  	Instead, we investigated
three approaches:

\begin{enumerate}
\item {\em Dictionary Term Translation} -- Look up each query term
in a general-purpose bilingual dictionary, and use 
all its possible translations.  This is a form of
query expansion upon translation.

\item {\em Corpus-based Term Translation} -- Use a sentence-aligned
bilingual training corpus to find the terms that co-occur in context across
languages, thus creating a corpus-based term-equivalence matrix.

\item {\em Corpus-based Term-to-Sentence} -- Use the
same type of aligned bilingual training corpus to extract full sentences that
in the target language co-occur with query terms in the source language.
%essentially a translingual adaptation of local context query
%enhancement.
%% , with the added benefit of avoiding part of the translation process. 
Term-to-sentence expansion may enhance recall, but at a cost in precision.
%adds many potentially-irrelevant terms to the translated query.


\end{enumerate}

All three MT-based methods used variations of the 
Pangloss Example-Based Machine Translation engine (PanEBMT) \cite{brown96},
however only corpus-based term translation (called EBT below, for
``Example-Based Term'' translation) is further described since it produced better results.



\subsection{PanEBMT Translations}

In general, EBMT systems \cite{brown96,nagao-ebmt} use a large corpus
of example pairs of previously translated sentences, in order to find
close matches and translations of words and phrases in context.  The
PanEBMT parallel corpus was derived %% via a sentence-aligning process
primarily from the Spanish and English portions of the UN Multilingual
Corpus \cite{GraffFinch94}, with an admixture of texts from the
Pan-American Health Organization and ARPA MT evaluations.  The total
corpus contains some 685,000 sentence pairs after removing duplicated
Spanish sentences.  PanEBMT translates by finding the set of matches to
a new text string (word, phrase or sentence) in the indexed bilingual
corpus.  Then the translations corresponding to these matches are
combined into candidate translations of the new text.  Because queries
contain more isolated terms than phrases or sentences, our
query-translation experiment is unable to exploit the power of EBMT.

% \subsection{Dictionary-Based Term Translation (DMT)}
% 
% For English-Spanish term translation we used a version of the
% machine-readable Collins Spanish-English Dictionary.  Its performance
% should not be taken as the maximum achievable by this technique, since
% we had to invert the dictionary, which substantially reduces the vocabulary
% (from 51,500 to 27,200 words), and did not have time to improve the
% inverted dictionary.

\subsection{Corpus-based Term Translation}

In order to create domain-specific or corpus-specific bilingual
dictionaries automatically, we start from a large sentence-aligned
bilingual corpus and generate a large term co-occurrence table
combined with a thresholding scheme\cite{Brown97}. The result was used
as the dictionary for corpus-based (example-based) term substitution MT (EBT).

Co-occurrence dictionary generation is performed in two phases: First
the co-occurrence matrix (indexed by source-language words on one axis
and target-language words on the other) is generated.  Each cell in
the matrix represents the number of times the source-language word
occurred in the same sentence pair as the target-language word.  Given
this matrix, we compute the conditional probability that if the term
occurs in one language its counterpart (i.e. its candidate
translation) also occurs in the other language.  If this probability is
above a threshold, then the term translation is added into the
dictionary.  Should a term in one language co-occur with several terms in
the other language with sufficient frequency to pass the conditional
probability threshold, {\em all} are stored as candidate translations.

% \subsection{Corpus-driven Term-to-Sentence Translation (SMT)}
%
% Since full-scale EBMT requires phrasal and sentential units, we
% Attempted a much looser form of EBMT for query translation.
% The corpus-driven term-to-sentence substitution method of query
% translation determines the
% most relevant corpus sentence(s) for a set of terms in the query
% and returns the translations of those sentences from the bilingual
% EBMT corpus.  The relevance measure is an analogue of TF-IDF, and the $N$
% highest-scoring sentence pairs by this measure are selected for
% retrieval.
% 
% This algorithm represents a modest addition to the
% existing PanEBMT engine, as it had not previously been used for
% term-weighted retrievals.  The existing inverted indices are used to
% determine which sentences contain each term in the input query, and
% these occurrences are summed, weighting by the inverse word frequency
% within the entire corpus, and dividing by the corpus sentence length.

% Once the $N$ highest-scoring source-language sentences have been
% found, the sentence pairs are retrieved from the EBMT corpus and the
% target-language half of each pair is output as part of the new query to
% be used for document retrieval.

% \subsection{Dictionary-Based Term Translation (DMT)}
% 
% For English-Spanish term translation we used a version of the
% machine-readable Collins Spanish-English Dictionary.  Its performance
% should not be taken as the maximum achievable by this technique, since
% we had to invert the dictionary, which substantially reduces the vocabulary
% (from 51,500 to 27,200 words), and did not have time to improve the
% inverted dictionary.


% The filter method applies two kinds of thresholds, ensuring a minimum 
%co-occurrence frequency for the source-target term pairs and a minimum
%number of 
%(one symmetric, the other asymmetric) to
%the matrix, and declares a word pair to be a valid translation if the words
%co-occur a sufficient number of times (normally 2 or 3) and either
%threshold test is successful. 
%For a given word pair in which the source word occurs $S$ times, the
%target word occurs $T$ times, and the words co-occur $C$ times, the pair
%is considered a translation if \\
%  $C / S >= thresh$ and $C / T >= thresh$,\\
%  $C / S >= thresh1$ and $C / T >= thresh2$, or\\
%  $C / S >= thresh2$ and $C / T >= thresh1$\\
%where $thresh$ is the symmetric threshold and
%$thresh1$ and $thresh2$ are the asymmetric threshold (the latter accounts
%for words which are polysemous in one language but not the other).

% This method has the nice property that adjusting these thresholds
% allows us to tune a trade-off:  stricter thresholds prevent spurious
% translations, but significantly reduce the possible translations;
% more lenient thresholds produce better yields, at the cost of allowing
% more spurious translations. 

% \subsection{Corpus-driven Term-to-Sentence Translation (SMT)}
%
% Since full-scale EBMT requires phrasal and sentential units, we
% Attempted a much looser form of EBMT for query translation.
% The corpus-driven term-to-sentence substitution method of query
% translation determines the
% most relevant corpus sentence(s) for a set of terms in the query
% and returns the translations of those sentences from the bilingual
% EBMT corpus.  The relevance measure is an analogue of TF-IDF, and the $N$
% highest-scoring sentence pairs by this measure are selected for
% retrieval.
% 
% This algorithm represents a modest addition to the
% existing PanEBMT engine, as it had not previously been used for
% term-weighted retrievals.  The existing inverted indices are used to
% determine which sentences contain each term in the input query, and
% these occurrences are summed, weighting by the inverse word frequency
% within the entire corpus, and dividing by the corpus sentence length.

% Once the $N$ highest-scoring source-language sentences have been
% found, the sentence pairs are retrieved from the EBMT corpus and the
% target-language half of each pair is output as part of the new query to
% be used for document retrieval.


\section{IR-based Methods for TIR}

We extended three monolingual retrieval methods to
translingual retrieval: pseudo-relevance feedback
(PRF)\cite{buckley:trec3}, the general vector space model
(GVSM)\cite{wong:sigir85}, and the latent semantic indexing (LSI)
approach\cite{deerwester90}.  In each case, a translingual semantic
correspondence between queries and documents 
is established based on a document-aligned bilingual
training corpus, without requiring sentence-level alignment,
bilingual dictionaries or machine translation.

\subsection{Pseudo-Relevance Feedback}

Relevance feedback (RF) is an approach to query expansion in
monolingual text retrieval\cite{Salton89}.  It requires a user to
judge interactively which retrieved documents are relevant, and uses
the relevance judgments to expand the original query for additional
search.  By ``pseudo-relevance feedback'' (PRF) 
we mean using the top-ranking
documents obtained in an initial retrieval without human judgements,
assuming that a significant fraction of top-ranked documents will be
relevant.  Both RF and PRF are query expansion techniques
similar to case-based IR \cite{rissland95}, and both
typically improve performance in monolingual retrieval compared to not
using them.  The adaptation of PRF to translingual retrieval is
relatively simple if a bilingual corpus is available.  That is, we
find the top-ranking documents for a query in the source language,
substitute the corresponding documents in the target language, and use
these documents to form the corresponding query in the target
language.  Figure \ref{PRFarch} illustrates the data flow for
translingual RF and PRF.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  INCLUDE HERE A COPY OF THE FIGURE FROM TEXAS DARPA RF/PRF for TIR
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent
\begin{centering} \noindent
\begin{figure}[htb]
\epsfxsize=3.25in 
\epsfysize=2.75in 
\epsfbox{/afs/cs/project/cmt-50/translingual/slides/trf.eps}
\caption{Data flow for translingual relevance feedback and pseudo-relevance feedback}
\label{PRFarch}
\end{figure}
\end{centering}

All the IR techniques discussed here, including the
PRF approach are variants of the vector
space model (VSM)\cite{Salton89} where both queries and documents are
represented using vectors of term weights.  To
allow clear theoretical comparison of these IR-based methods, let us
define the notation for VSM (including PRF): 
$$\begin{array} {c} \vec{q} = (q_1, q_2, \ldots, q_m)^t \\ \vec{d} =
(d_1, d_2, \ldots, d_m)^t \\ sim(\vec{q}, \vec{d}) = \cos(\vec{q},
\vec{d}) = {\sum_{i = 1}^m {q_i d_i} \over {\sqrt{\sum_{i = 1}^m
{q_i^2}} \sqrt{\sum_{i = 1}^m {d_i^2}}}}
\end{array}$$ 
where $\vec{q}$ is the query, $\vec{d}$ is a document in a corpus, $m$
is the number of unique terms (words or phrases) in the corpus, and
$q_i$ and $d_i$ are the term weights in the query and the document,
respectively.

\subsection{Generalized Vector Space Model}

  A criticism of conventional VSM is that it uses terms as an
  orthogonal basis of the vector space, but terms are often not
  semantically independent.  Wong {\it et al} proposed an
  alternative, namely the ``generalized vector space
  model'' (GVSM) \cite{wong:sigir85}, also referred to as ``the dual space''
  \cite{sheridan:sigir96}.  The idea is to use documents as the
  basis for representing terms instead of using terms.

  Consider a term-document matrix, $A_{m \times n}$, as a training
  corpus where $m$ is the size of the vocabulary, and $n$ is the
  number of unique documents in this corpus.  One can view this matrix
  as a way to represent documents (the columns) using terms, and
  to represent terms (the rows) using documents.  The former
  view corresponds to the conventional vector space model, and the
  latter view corresponds to the dual space.  Each row vector of $A$
  reflects the term usage in the corpus, i.e., the {\em pattern} of
  this term distributed over documents.  

 Matrix $A$ can be used for query transformation by computing
  $\vec{q^\prime} = A^t \vec{q}$ where $\vec{q}$ is the original query
  vector whose dimensions are unique terms, and $\vec{q^\prime}$ is
  the transformed vector whose dimensions are unique documents.  The
  transformation is equivalent to weighting the {\em distribution
  pattern} of each term using its weight in the original query, and
  summing up the weighted patterns to obtain a new representation of
  the query.  Similar to query transformation, a document can also be
  transformed into a vector in the dual space by computing
  $\vec{d^\prime} = A^t \vec{d}$ where $\vec{d}$ is the document
  vector in the conventional VSM.  The retrieval criterion in GVSM for
  monolingual retrieval is defined to be: $$sim(\vec{q}, \vec{d}) =
  \cos(A^t \vec{q}, A^t \vec{d}).$$

Here we propose a novel extension of the monolingual GVSM for
translingual retrieval.  Assuming a bilingual corpus for training, we
form two matrices, $A$ and $B$, where $A$ is a term-document matrix
for the training documents in the source language (also the language
of the queries), $B$ is a term-document matrix for the training
documents in the target language, and the corresponding columns of $A$
and $B$ are the matching pairs of documents in the bilingual
corpus. We use $A$ for query transformation and $B$ target-language
document transformation.  The retrieval criterion is defined to be:
$$sim(\vec{q}, \vec{d}) = \cos(A^t \vec{q}, B^t \vec{d})$$ Since
matrix $A$ and $B$ share the same dual space, the transformations $A^t
\vec{q}$ and $B^t \vec{d}$ give the query and the document a common
basis (presenting distribution patterns of terms over documents)
on which they can be compared.  This is how the translingual
correspondence is established.

The computation in GVSM consists of the transformation ($A^t
\vec{q}$ and $B^t \vec{d}$) and the cosine computation.  The time
complexity of the first part is similar to the computation in VSM.  It
is proportional to the number of non-zero elements in a query or
document vector, $O(kn)$ where $k$
is the average number of unique terms per query or document, and $n$
is the number of document pairs in the bilingual training corpus.
The time complexity in the second part,
is $O(n)$ per document, or $O(nl)$ for a
test corpus of $l$ documents.  It is possible to significantly reduce
this complexity in large problems by aggressively removing
non-influential elements from the transformed document vectors
\cite{yang:sigir95}.

\subsection{Latent Semantic Indexing}

Latent Semantic Indexing\cite{deerwester90} (LSI) is a one-step 
extension of GVSM.  The
claim is that neither terms nor documents are the optimal choice for the
orthogonal basis of a semantic space, and that a reduced vector space
consisting of the most meaningful linear combinations of documents
would be a better representative basis for the content of documents.  

In monolingual retrieval, LSI uses the term-document matrix ($A$)
for training, the same as in GVSM.  It computes the
orthogonal dimensions (``the latent semantic structures'') in matrix
$A$, and selects the principal dimensions as the new basis for a
reduce vector space.  The monolingual LSI retrieval criterion is
defined to be: 
$$\begin{array} {c} A = U \Sigma V^t \\ L = U
\Sigma^{-1} \\ sim(\vec{q}, \vec{d}) = \cos(L^t \vec{q}, L^t
\vec{d})
\end{array}$$ 
where matrices $U$ and $V$ contain a set of $p$ orthogonal singular
vectors each (one for the representation of terms, and another for the
representation of documents).  Matrix $\Sigma$ is $p$-diagonal,
containing the singular values indicating the importance of the
corresponding singular vectors in matrices $U$ and $V$.  Matrix $L$
contains the weighted singular vectors in $U$, where the weights are
the corresponding singular values in $\Sigma$. This matrix can be
viewed as a reduced version of matrix $A$.  That is, both $A$ and $L$
use their row vectors to represent terms, but the term vectors in $L$
are much shorter than the term vectors in $A$.  The dimensions in $L$
are linear combinations of documents, while the dimensions in $A$ are
individual documents.

The translingual LSI model \cite{duma96} is similar to the
model for monolingual LSI, except that a bilingual document
corpus is needed for training instead of a monolingual corpus.  Let
$\vec{q}$ be a query in the source language, $\vec{d}$ be a document
in the target language, and $\left[\begin{array} {c} A \\ B
\end{array} \right]$ be the matrix of bilingual document pairs where
$A$ and $B$ are the same as defined in GVSM.  Then the  translingual LSI
retrieval criterion is defined to be:

$$\begin{array}{c}
   \left[ \begin{array} {c}
	 	A \\ B 
	   \end{array} 
   \right] = U_2 \Sigma_2 V_2^t \\ 
   L_2 = U_2 \Sigma_2^{-1} \\
   sim(\vec{q}, \vec{d}) = \cos(L_2^t \vec{q}, L_2^t \vec{d})
\end{array}$$ 
where $U_2$, $V_2$, $\Sigma_2$ and $L_2$ are the matrices computed
using the singular value decomposition of the bilingual input matrix .

LSI has a quadratic time complexity of $O(n^\prime p)$ where $n^\prime =
\max\{m, n\}$ is the larger number between the size ($m$) of the joint
vocabulary of both languages and the number ($n$) of document pairs in
the bilingual training corpus; $p$ is the number of orthogonal
dimensions (singular vectors) computed in the singular value
decomposition.  Thus the scalability of this method to a large corpus would
be much more limited than the VSM or GVSM approach if a large number of
singular vectors is necessary for good retrieval performance.

\subsection{The Scientific Challenge}

The similarities and differences between the three models mentioned
above can be seen in their retrieval criteria: 
$$\begin{array}{rl} 
VSM: & sim(\vec{q}, \vec{d}) = \cos(\vec{q}, \vec{d}) \\ 
GVSM: & sim(\vec{q}, \vec{d}) = \cos(A^t \vec{q}, B^t \vec{d}) \\ 
LSI: & sim(\vec{q}, \vec{d}) = \cos(L_2^t \vec{q}, L_2^t \vec{d})
\end{array}$$
The fundamental difference, in theory, is the choice of the basis for
the similarity comparison between queries and documents.  VSM 
assumes semantic independence of terms in its basis.
GVSM uses documents instead, assuming
documents are semantically independent.  LSI computes the orthogonal
dimensions in a training corpus, and chooses the principal dimensions
as the basis of a reduced vector space.  GVSM and LSI are close
variants in the sense that
both exploit the dual space. The only difference is whether to use the
original dimensions (document vectors) or the reduced dimensions (the
orthogonal singular vectors) as the basis for the vector space.  Which
model best represents the semantic space of documents and queries is a
scientifically challenging question.  

Given the methods,
empirical validation is important.  For monolingual retrieval,
performance improvement of GVSM over VSM was observed on small
collections \cite{wong:sigir85}; improvement of LSI over VSM was
observed sometimes but not always \cite{deerwester90}.  
Until our work reported below, there has not been
a comparison between GVSM and LSI, in either
monolingual or translingual retrieval.

\section{Empirical Evaluation}

%  jgc:
%   3. Do the write-up on the experiments
% 	a. Describe the corpus, queries, etc.
%		[including MED data set, and our derivation of UN texts (ref)]
% 	b. Describe the evaluation methods used (11-pt, overlap, ...)
% 	    including what we use to compare against and why
% 	c. Present results in tables/graphs and explain them
% 	d. Draw observations and conclusions from results


We carried out a comparative evaluation of the six translingual
IR methods described above (the three term-based MT methods,
PRF, GVSM, and LSI) on a realistic retrieval task.
The large UN Multilingual Corpus\cite{GraffFinch94} from the 
Linguistic Data Consortium was available to us, but,
among other problems, there were no queries or human relevance
judgements available for training and evaluation.
We conducted our experiments on a subset of this corpus, consisting
of 2255 document pairs pertaining to UNICEF reports and deliberations.
Each document pair consists of an English document and its corresponding
Spanish translation.  1134 document pairs were randomly selected and
used for translingual training. The remaining 1121 pairs were set aside 
for testing. The average (monolingual) document is 9 paragraphs long.
Altogether, the training and test sets in both languages 
consist of almost 2 million words of text.

We conducted our experiments as follows:  First, we created
30 queries in English, germane to the UNICEF subcollection.
The average query length was 11 words.  Second, we obtained
human relevance judgements on the cross product of the 30
queries and 1121 test documents (33,630 samples in all), and used these 
as our gold standard for testing\footnote{An initial set of
experiments was conducted before these judgements were available, as
described below.}. 
Third, we trained each method to find translingual equivalences
using paired documents, without queries; hence no
relevance judgements were required for training.
Fourth, we tested each method {\it monolingually}
on the test set to obtain ranked lists of retrieved
documents.  Fifth, we applied the
translingual version of our methods.  Finally, we evaluated the
results by comparing the retrieval degradation when moving
from monolingual to translingual IR for all the methods.

We optimized each method for monolingual retrieval, with
respect to its performance on 11-point average precision using
the full human relevance judgements on the 30 queries for the test
corpus.  Optimizations include the settings on TF and IDF weights for
cosine-similarity scoring, setting thresholds on pseudo-relevance
feedback, setting cutoff levels for number of non-influential elements for GVSM
(200 was optimal), and
determining the optimal number of singular vectors in LSI (also 200, coincidentally).
When each retrieval method was performing at optimum on
monolingual retrieval, we tested that method with exactly
the same parameter settings on translingual retrieval.  

We carried out two sets of experiments.
The first comparison focuses
on overlap between monolingually-retrieved documents and translingual
retrievals, based on the parallel corpus to establish correspondences.
The central tenet of the first evaluation was that
perfect translingual retrieval would retrieve
exactly the corresponding set of documents as monolingual retrieval,
but in the target language.  Hence, monolingual versus translingual comparison
was our primary effectiveness measure.
The second comparison is a direct evaluation of monolingual and of
translingual retrieval using human relevance judgements and computing
precision and recall scores in the traditional IR manner \cite{Salton83}.


% \subsection{Monolingual Baseline}
%
% Before proceeding with the translingual IR experiments, we performed
% a sanity check on our methods by testing them on the monolingual
% MED collection, a classic test set used in text retrieval
% research, with available queries and human relevance judgements.
% (MED is described in Deerwester {\it et al} \cite{deerwester90}, p. 400).
% This experiment is totally separate from our primary translingual
% results described below.
% We  used the SMART system\cite{Salton89} as our IR infrastructure for
% all of our experiments. (``SMART.basic'' is the standard VSM
% retrieval method without PRF used in the query-translation method.)
%
% A recall-precision graph for the monolingual methods is shown
% in Figure \ref{fML}.  Our primary evaluation method is the
% standard one in modern IR, averaging the precision at 11 
% evenly-spaced levels of recall (from 0\% to 100\%) \cite{Salton89}.
% From this graph, it is clear that PRF, GVSM and LSI  outperform 
% SMART.basic, and that their monolingual performance is very similar
% to each other.  The ratio of their 11-point precision
% averages compared to SMART.basic are 120.1\% for GVSM, 121.7\% for LSI, and
% 123.9\% for PRF.

% \noindent
% \begin{centering} \noindent
% \begin{figure}[htb]
% \epsfxsize=3.25in
% \epsfysize=2.3in
% \epsfbox{mlFig1.eps}
% \caption{Monolingual recall/precision graph, 
% SMART basic plus IR-based methods }
% \label{fML}
% \end{figure}
% \end{centering}
%%Figure 1: Monolingual recall/precision graphs, 
%%SMART.basic plus IR-based methods

% No te that the good performance of LSI is very sensitive to the number
% of singular vectors used.  LSI's performance varied from 75.26\% (worse
% than SMART.basic) to a high of
% 121.7\%  as the number of singular vectors varied.  Throughout these
% experiments, we evaluated
% each method under those conditions where it performed best.  For
% monolingual LSI,
% this was with 50 singular vectors.

% Not true, by new data: $SMART < VSM = GVSM = LSI$
% 1: Monolingual: $SMART < GVSM < LSI ~= PRF$ \\


\subsection{Initial Evaluation}

% \subsubsection{Corpus and Query Preparations}
%
% Our first task to prepare for translingual experimentation was 
% the extraction of the UNICEF English-Spanish bilingual sub-corpus from the 
% large UN multilingual corpus (about 500 megabytes of data per language).
% The original UN corpus is a heterogeneous mixture of all sorts of documents.
% Using formatting codes and alignment methods, we then extracted and segmented 
% the UNICEF portion into distinct documents: 1134 for training and
% reserving 1121 for testing. The test set contains 817k English and 
% 959k Spanish words, with 9.5k paragraphs each.  We constructed
% 30 English queries comprising of 10 to 15 words each.

% \subsubsection{Experimental and Evaluation Methods}

Before we had relevance judgements available, we carried out an
initial set of experiments, using two novel evaluation methods.
Each of the retrieval methods was trained on the same bilingual training data.
We then ran each of the translingual methods using English queries to
retrieve Spanish documents, and compared the Spanish documents
retrieved translingually to the English documents retrieved monolingually 
by each method.

The results were 
compared using both an 11-point average precision and an overlap measure.
``Precision'' in this case was measured by comparing the top $L2$ of the
translingually-retrieved ranked list
against the top $L1$ of the corresponding monolingually-retrieved ranked list, and taking
the monolingually-retrieved documents as relevant to the query.
The overlap measure was simply the percentage of identical
documents present in the top $L1$ ranked documents retrieved
monolingually and the top $L2$ translingually, for a given $L1$ and $L2$.
We calculated both measures in order to minimize any artifact of
our evaluation method.  

% \subsubsection{Translingual Experiment Results}

\noindent
\begin{centering} \noindent
\begin{figure}[htb]
\epsfxsize=3.25in 
\epsfysize=2.7in
\epsfbox{tlFig2new.eps}
\caption{11-pt. ave. precision vs. rank limit threshold}
\label{fTL11pt}
\end{figure}
\end{centering}
% Figure 2: Translingual 11-pt. ave. precision vs. rank limit threshold
% graph, IR-based methods and MT

\noindent
\begin{centering} \noindent
\begin{figure}[htb]
\epsfxsize=3.25in 
\epsfysize=2.7in
\epsfbox{tlFig3new.eps}
\caption{Overlap \% vs. rank limit threshold}
\label{fTLOverlap}
\end{figure}
\end{centering}
% Figure 3: Translingual overlap \% vs. rank limit threshold graph

The translingual results are presented in Figures \ref{fTL11pt} and \ref{fTLOverlap}.  Figure \ref{fTL11pt}
presents the 11-point average precision for each method plotted
against the number of reference documents used ($L1$).  $L2$ is four
times $L1$ in each case, in an attempt to make the second ranked list
sufficiently long.
% (essentially approximating an infinite $L2$).  
% The ``NEW''
% versus ``OLD'' graph
% annotations are explained in the ``Discussion'' section below.
Figure \ref{fTLOverlap} presents the overlap measure for each method, again versus
$L1$.  Here we use $L2 = L1$, as per our definition of overlap.
As mentioned above, we only report the results of the corpus-based EBT method in these
graphs, for brevity, given that it performed best among the MT methods.

% *** IS THIS STILL TRUE??
From these figures, we see that GVSM outperformed
the other methods in terms of these document overlap measures.
All the methods have a large overlap between their monolingual and
translingual retrievals, which is a good sign.
Moreover, the graphs of the two evaluation methods
are remarkably consistent.
%, which supports our belief
%that both measures are valid.

\subsection{Evaluation with Human Judgements}

For our second comparison, we evaluated each method, monolingually and
translingually, using human relevance judgements.
The corresponding 11-point average precision
values in the table in figure \ref{table1} below.  For comparison, we also include
corresponding translingual results reported by other researchers.
Because the methods have been run on different corpora
with different queries, direct comparisons on absolute
11-point-precision recall figures are not meaningful.
However, the ratio of translingual IR (TIR) over monolingual IR results
may be more indicative of the relative power of the TIR methods.
We encourage direct comparisons on the same corpus.
We also present our results in the standard recall-precision graphs for monolingual
and translingual IR in figures \ref{fMLRP} and \ref{fTLRP}, respectively.


% NOTE THIS TABLE PROBABLY NEEDS TO BE REFORMATTED TO FIT
% IN ONE COLUMN OF THE 2-COLUMN IJCAI FORMAT -- OR ELSE
% HAVE IT CUT ACROSS BOTH (though that is probably disallowed)

\begin{figure*}
\begin{center}
\begin{tabular}{||lllll||}
%\multicolumn{5}{c}{Table 3. Results of TIR methods (with ntc.ntc weighting)} \\
\hline \hline 
%------------------------------------------------------------------------------
Site    & Method        & (Monolingual) IR      & TIR           & TIR/MIR \\ \hline
%------------------------------------------------------------------------------
CMU     & Dict Q-tran    & .4721 (SMART.basic)  & .2898         & 61\%  \\
CMU     & EBT Q-tran     & .4721 (SMART.basic)  & .4318         & 91\%  \\
CMU     & PRF Q-exp      & .4487                & .4043         & 90\%  \\
CMU     & GVSM QD-tran (SP=200)   & .4008                & .3804         & 95\%  \\
CMU     & LSI QD-tran (200 SVs) & .3689         & .3093         & 84\%  \\ \hline
%------------------------------------------------------------------------------
UMASS   & CorpusPhrase Q-exp    & .20           & .1358         & 68\%    \\
ETH     & LSI thesaurus Q-exp   & .527          & .212-.278     & 40-53\% \\
        & (LSI thesaurus + RF)  & ?             & ?             & (68\% ) \\
XEROX   & Dict Q-tran           & .393          & .235          & 60\%    \\
NMSU    & Dict Q-tran           & ?             & ?             & 40-50\%? \\
%------------------------------------------------------------------------------
\hline \hline
\end{tabular}
\end{center}
\caption{Results of TIR methods (with ntc.ntc weighting)}
\label{table1}
\end{figure*}

As the table in figure \ref{table1} shows, example-based term (EBT)
translation (a.k.a. corpus-based term translations),
never before tried for TIR, exhibits top absolute performance, whereas 
general-purpose machine-readable dictionary (MRD) query-translation
exhibits the worst performance.  In spite of the similarity between 
these methods (both translate the query), the former
is trained to the corpus and exploits context, and is therefore
much superior.  This result indicates that the most popular TIR
method reported in the literature (MRD-based query translation)
may be the simplest, but its performance leaves much to be desired.

Pseudo-relevance feedback also performed well in absolute
terms, indicating that if the user were willing to provide true relevance
judgements, full relevance feedback could become the top-performing
method for TIR.

%(Note that the improvement of EBT and PRF from the first experiment to
%the second is a true improvement, resulting from the optimizations
%described above, and in no way invalidates the methodology of the
%first experiment.  These two methods really did advance from worst to best.
%This also suggests that further investment in
%improving TIR performance is warranted.)

GVSM, never before tried for TIR, performed relatively well and
showed the least degradation from MIR to TIR.  LSI did not
perform according to expectations from the literature.  In earlier
less realistic experiments (with queries formulated directly from
documents), LSI had performed better \cite{duma96}.

\noindent
\begin{centering} \noindent
\begin{figure}[htb]
\epsfxsize=3.25in 
\epsfysize=2.7in
\epsfbox{extraFigML.eps}
\caption{Recall-Precision performance of MIR methods}
\label{fMLRP}
\end{figure}
\end{centering}

\noindent
\begin{centering} \noindent
\begin{figure}[htb]
\epsfxsize=3.25in 
\epsfysize=2.7in
\epsfbox{extraFigTL.eps}
\caption{Recall-Precision performance of TIR methods}
\label{fTLRP}
\end{figure}
\end{centering}


% \subsection{Discussion}
%
%
%\subsubsection{MT-based Retrieval Results}
%
%%As mentioned above, EBMT was ineffective due to incoherent queries
%%Tuned TMT!!
%As mentioned above,
%in initial studies, DMT and SMT both gave significantly worse results
%than TMT.  We believe this is primarily due to
%the ability to tune the TMT
%
%thresholds to find the best performance for a given corpus.
%(As noted above, the DMT dictionary was also definitely suboptimal.)
%% We intend to investigate ...
%% $SMT << DMT << TMT$
%% For English and Spanish (in either direction), a minimum co-occurrence
%% count of 2 and a threshold of 0.5 (i.e.  at least half of the
%% occurrences of a word must co-occur with the candidate translation)
%% yields less than 10\% incorrect translations.  
%The ``9213'' version of TMT used in
%^this paper was generated using a threshold of 0.25 and
%.20/0.50, yielding a dictionary of 27,445 words
%with an error rate of approximately 15\%-18\%; this combination proved
%best among those tested.  
%
%\subsubsection{``NEW'' vs. ``OLD'' Document Sets}
%
% Figure 4: (optional) graph: Effect of old vs. new data set on PRF/VSM, GVSM, and
% LSI performance.
% Only PRF/VSM seemed sensitive to OLD/NEW distinction [only on fake trial]

% Figure 5: (optional) table: ranking of different methods,
% 11pt. ave. precision, on *fake* UNICEF trials [using whole doc as query, like LSI paper!]
% 
%  real data:
%        EBMT.word   0.9804   (based on medium(``9213'') sized dictionary)
%        TIR's PRF/VSM   0.4914   (based on 'old' training set)
%        TIR's PRF/VSM   0.8756   (based on NEW training set)
% 	GVSM 0.8715 (OLD SET)
% 	LSI  0.9455 (OLD SET, 50 SV)
% It also shows that PRF/VSM was sensitive to the difference in doc sets for
% the *fake* experiment, but not in the real trials.
%Also in initial studies, the original ``OLD'' set described above gave
%poor results for PRF.  The single-section documents
%were still too long and too diverse in their topics.  We broke them
%up into smaller documents consisting of aligned paragraphs, 
% which produced a much larger set of documents
%only to discover in further tests that
%only the PRF was affected, and primarily in the artificial situation
%used in the initial study.  As elsewhere, we used the best
%conditions for PRF, which is the ``NEW'' document set.
%
%
%
%\subsubsection{Previous TIR Work}
%
%The Davis and Dunning\cite{davis:trec4} study is not directly comparable
%to this work,
%since our study does not have ground truth available, and we
%implemented somewhat different techniques.  It is worth noting, however, that our results are much more
%encouraging than theirs for the feasibility of translingual IR.
%
%The Translingual LSI study\cite{duma96} was not performed in a
%realistic environment, as no actual queries or relevance judgements
%were used.  Our results seem to indicate that GVSM is at least as good
%as LSI in translingual retrieval performance, but may be
%cheaper to compute, or easier to scale to large corpora.  Interestingly,
%we were able to essentially
%replicate the reported Translingual LSI results in a similar task (not
%described in this paper),
%using our UN-based document set.
%The translingual GVSM method does still
%make use of an important insight from Translingual LSI: that using a bilingual document
%set during the basis computation provides the required translingual information.
% \subsection{Initial IR Results}
% 
% In initial studies, original ``old'' set gave bad results.  Single documents
% were too diverse in their topics.  Needed to break them up.
%  Now new
% set is too big (for LSI!); produce ``large'', ``medium'', and
% ``small''.
% [only mention in discussion section on LSI]


% Figure 5: (optional) table: ranking of different methods,
% 11pt. ave. precision, on *fake* UNICEF trials [using whole doc as query, like LSI paper!]
% 
%  real data:
%        EBMT.word   0.9804   (based on medium(``9213'') sized dictionary)
%        TIR's PRF/VSM   0.4914   (based on 'old' training set)
%        TIR's PRF/VSM   0.8756   (based on NEW training set)
% 	GVSM 0.8715 (OLD SET)
% 	LSI  0.9455 (OLD SET, 50 SV)
% It also shows that PRF/VSM was sensitive to the difference in doc sets for
% the *fake* experiment, but not in the real trials.

% To test methods before queries were ready, conducted ``fake'' tests.
% These duplicated Translingual-LSI results! (same methodology with different corpus).




\section{Conclusions} % and Future Work}

% jgc:
%   4. Write overall conclusions, including next steps in
% 	the investigation

% [Repeat conclusions from above, to highlight]
% [something from Yiming??]

This paper reports a thorough
evaluation of multiple methods for translingual retrieval in
a query-based retrieval task.  We believe that the evaluation
methodology used here may be generally useful when costly human
relevance judgements are unavailable.
Our experimental results indicate that:
\begin{itemize}
\item Translingual retrieval is viable by a number of
different techniques, ranging from term-based query translation 
and pseudo-relevance feedback to generalized vector spaces
and latent semantic indexing.

\item In the translingual retrieval test, example-based MT
establishing corpus-based term equivalences performed best, followed
by PRF, GVSM, LSI and MRD-based query translation.  However, in terms
of performance relative to monolingual retrieval, GVSM performed best.

\item MRD-based query translation, though popular in the
literature, should be re-examined as the TIR method of choice
given the results in this paper. 

\item It appears that Translingual LSI is not as good in a realistic
setting with actual queries and 11-point-average precision evaluations
as in the preliminary Dumais {\it et al} study, although LSI does
perform better that simple MRD-based query translation.
\end{itemize}

It is worth noting that GVSM is simple to compute and easy to scale
up, somewhat better than LSI, and its performance is not crucially
dependent on the exact value of a tuned parameter 
(such as the number of singular vectors of LSI).
% We also discovered that our overlap and 11-point average precision 
% measures seem to give the same basic results.  We only know this
% from doing these experiments; it was not guaranteed.  This redundancy 
% gives us more confidence that our results are meaningful.
More work is clearly called for in further evaluating the GVSM method
and corpus-based term-translation in other realistic contexts, and
investigating whether other forms
of tunable MT-based translingual IR could be made to perform reasonably well,
especially in situations where translating the collection does not
pose serious problems.

% Future work includes 
% For MT-based methods:
% Try tuning other MT methods, especially since tunable TMT was clearly
% the best.
% Still room for improvement in TMT (concurrence weight).
% DMT: might try improving genl.purpose E-S dictionary.
% SMT:
% We have not yet implemented ...
%  I don't yet use inverse sentence length as part of the
%  weighting, since there is as yet no way to get that without actually
%  reading the sentence pair from the corpus, but I plan to add an EOL
%  marker to the indexing process, which will then give me the sentence
%  length at lookup time.


% \subsection{Integration with SMART}
% 
% When using either query translation method outlined above, the original
% query document is passed to the PanEBMT engine, which translates it in
% the desired manner and returns a result which is then used as the true
% query over the documents in the target language.  The translated query
% may use any of the features SMART provides for monolingual retrievals,
% such as pseudo-relevance feedback or Latent Semantic Indexing.
% 
% PanEBMT is run as a separate process to which the SMART process
% opens a network connection via a Unix socket.  The SMART end of the
% connection sends appropriate commands followed by the query to be
% translated, and collects the returned output from the translation
% request to be used as the actual search query.  This architecture has a
% number of advantages, two primary ones being
% \begin{enumerate}
% \item the EBMT engine may be run on the same machine on which its (very
% large) data files physically reside
% 
% \item the 40-second startup time for PanEBMT need only occur once,
% rather than on every run of SMART
% \end{enumerate}


	
%\newpage

%\bibliographystyle{aaai}
\bibliographystyle{named}
\bibliography{ijcai97}

\end{document}

\begin{figure}[t]
\centerline{\psfig{file=table1.eps,height=2.0in,width=3.3in}}
\label{table1}
\end{figure}
