% This is based on the sigproc-sp.tex -FILE FOR V2.6SP OF 
% ACM_PROC_ARTICLE-SP.CLS OCTOBER 2002
%
% ----------------------------------------------------------------------------
% It is an example which *does* use the .bib file (from which the .bbl file
% is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission,
% you need to 'insert'  your .bbl file into your source .tex file so as to 
% provide ONE 'self-contained' source file.
%
% For tracking purposes - this is V2.6SP - OCTOBER 2002

\documentclass{acm_proc_article-sp}

\usepackage{rotating}
\usepackage{subfigure}

\newif\ifdraft
\drafttrue
\newif\ifoldversion
\oldversionfalse

\AtBeginDocument{
\ifdraft
\typeout{WARNING: margin notes visible}
\fi
\ifoldversion
\typeout{WARNING: generating old version}
\fi
}

\newcommand{\marnote}[1]{%
\footnote{#1}
}

\begin{document}

\title{Empirical Development of \\ an Exponential Probabilistic Model for Text 
Retrieval}
%\subtitle{Using Textual Analysis to Build a Better Model}

\numberofauthors{2}

%\author{
%\alignauthor Jaime Teevan\\
%       \affaddr{MIT AI Lab}\\
%       \affaddr{200 Technology Square}\\
%       \affaddr{Cambridge, MA 02139}\\
%       \email{teevan@ai.mit.edu}
%\alignauthor David Karger\\
%       \affaddr{MIT LCS}\\
%       \affaddr{200 Technology Square}\\
%       \affaddr{Cambridge, MA 02139}\\
%       \email{karger@theory.lcs.mit.edu}
%}

%\date{30 July 1999}

\maketitle

\begin{abstract}

Much work in information retrieval has focused on using a model
of documents and queries to derive retrieval algorithms.
Models are a useful alternative to the heuristic development of retrieval 
algorithms because they make explicit the assumptions of the model developer, 
allowing the assumptions to be examined and refined independent of the 
particular retrieval algorithm.  Unfortunately, in many cases these models are 
improved on by intuition, and their assumptions are not carefully tested against 
actual data.  Thus, when a model based retrieval algorithm fails, it is not 
clear whether the fault is in the algorithm or the underlying model.

In this paper, we devise a generative document model via analysis of actual 
corpora and queries.  Our thesis is that a model so developed will be more 
accurate, and thus more useful in retrieval, as well as other applications, than 
a heuristic model.  We test this hypothesis by learning from the corpus the best 
document model within a na\"{\i}ve Bayesian framework, and investigating both 
how closely this learned model matches the data and how well it can be used to 
perform retrieval.

\end{abstract}

% A category with the (minimum) three required fields
%\category{}{}{}
%A category including the fourth, optional field follows...
\category{H.3.3}{Information Storage and Retrieval}{Information Search and 
Retrieval}[retrieval models]

\terms{Theory, Experimentation}

\keywords{Information Retrieval, Formal Models, Machine Learning} 

\section{Introduction}

Information retrieval is about determining which documents are
relevant to a user's information need.  In early work on information
retrieval, this determination was based on heuristic
judgments~\cite{luhn:tf} -- for example, that documents containing the
user's query terms are likely to be relevant -- followed by heuristic
tweaking of parameters (such as term weights) to make the system work.
Subsequently, attempts were made to avoid, or at least make explicit,
these heuristic judgments by developing models of queries and
documents that could be used to deduce appropriate retrieval
strategies.  Examples of such models include the multinomial and
2-Poisson models.  These are both \emph{probabilistic models} that
posit that relevant and irrelevant documents are generated from
certain probability distributions, use these distributions to
determine probabilities of relevance for each document, returning
documents with high relevance probabilities (in accordance with the
Probability Ranking Principle \cite{kieth:IR}).

While probabilistic models are intuitively appealing and easy to work with,
relatively little attempt has been made to test the accuracy of their
assumptions against actual data.  Often a model is developed without
reference to data; the only actual interaction with text is
when testing a particular retrieval system based on the model
(e.g.,~\cite{griff:cluster,kwok:sim,rob:poisson}).  At that point it
is difficult to decide whether unsatisfactory retrieval is due to the
retrieval system or the underlying model.

We are interested in developing a generative model that, instead of
directly improving retrieval, better describes text.  Our hope
is that improvements in a generative model will propogate through
any model-based retrieval algorithm, yielding better performance in
retrieval.  This hope is not always fulfilled, as has been illustrated
by the relatively unsuccessful attempts to allow for term dependencies
in retrieval \cite{sj:dev}.  But by focusing on a few empirically
inaccurate and easily correctable flaws in current models, we find
we are able to improve our model's performance on certain retrieval
tasks.  Even when performance does not improve, generative models provide a
useful approach to understanding text.  They can be tested against
actual corpora, generalized to other applications, and may
even, in their characterization of text, suggest promising
performance-improving heuristics.

We believe that the best way to improve on a generative model is to
examine a corpus and modify the model to better match the actual
statistical properties of text. We are of course unable to avoid
all unfounded assumptions.  For example, we restrict ourselves
throughout the course of our analysis to na\"{\i}ve Bayesian models.
However, we significantly relax some of the assumptions of standard
probabilistic models and explore a much larger space of possible models.

We begin by discussing relevant work in model based retrieval.
We then give a brief background of Bayesian machine learning and na\"{\i}ve
Bayesian retrieval.  In Section~\ref{sec:mult} we examine the well-known
multinomial model, which assumes that terms in a document follow a
multinomial distribution.  This model diverges in basic ways from the
actual statistics of text, and we highlight some of these ways.  We 
then show in Section~\ref{sec:textmodel} how to identify,
via examination of the corpus, a better model chosen from a class
known as the \emph{one-parameter exponential families}, which includes
the multinomial model as one instance. We conclude with a discussion of
how to use this improved model for retrieval and present experimental
results.

\section{Related Work}

While textual analysis is not currently a driving force behind the
development of IR systems, early systems were often built by first
studying the statistical properties of text.  For example, Sparck
Jones \cite{sj:stat} suggested using the inverse document frequency
for term weighting, now a common practice, based on textual
analysis. At the time large test sets were not available, so the
analysis was performed on a very small scale.  Sparck Jones's analysis
was done on three corpora of only a couple hundred documents
each. Recently, people have revisited textual analysis on newer and
larger data sets.  For example, Grieff \cite{gre:analysis} suggested
new improvements to tf.idf by studying 85,000 Associated Press
articles from TREC 1.  However, despite the fact that probabilistic
models have explicit assumptions that should make textual analysis
straightforward, this recent work has not been within a probabilistic
framework.

There are a number of probabilistic models, such as a binomial model
\cite{fuhr:prob} and the 2-Poisson model \cite{rob:poisson} where the
statistical properties of the text corpus are fundamental to the
model.  More recently, work has been done on language models
\cite{ponte:lm} and other variants of the traditional probabilistic
models \cite{ng:rel}.  While these models do attempt to minimize
unfounded assumptions, the decision of how to build on the previous
models is often not based on textual analysis. For example, Jin,
Hauptmann and Zhai \cite{jin:title} suggest using the probability that
a query would be the title of a document to rank documents, without
actually investigating whether queries look anything like document
titles.

In our work, we use textual analysis to understand and explore models
within a na\"{\i}ve Bayesian framework.  This framework has been well
studied and Lewis gives a good overview of na\"{\i}ve Bayes retrieval
and classification~\cite{lewis:forty}.  One common model within this
framework is the multinomial model.  While it is not popular for
information retrieval, it has been explored for that use \cite{kalt:newProb}
and it is common in text classification \cite{lewis:forty}.
The work we present here differs from these
models because we do not restrict our model to a particular (e.g.,
multinomial) family of distributions, but rather derive the best
family of distributions directly from the text.  New approaches have
been taken to derive the model \emph{parameters} from the
text~\cite{Zhai:two}, but they do 
not attempt to derive the actual \emph{model} from the text.

Our approach uses relevance judgments on past queries in a principled way to devise 
a retrieval strategy for future queries, and thus serves as an interesting instance 
of cross query learning.  Similarly, Fitzpatrick and Dent~\cite{fitzpatrick:query} 
use textually similar past queries for relevance feedback.  In contrast to this work, 
rather than using topically related past queries, we use all of the past queries to 
teach us about the overall document model for relevant documents.

\section{A Brief Bayesian Tutorial}
\label{sec:ml}

Our approach is motivated by the standard Bayesian machine learning
framework.  In this section, we discuss that framework in order to lay
the groundwork for our approach.  Those familiar with Bayesian machine
learning can safely skip this section.  Due to space constraints, we
focus on the ``what'' and give short shrift to the ``why'' of this
approach; such material can be found in several
sources~\cite{bern:bt,heck:tutorial}.

Our probabilistic approach begins with the assumption that relevant
and irrelevant documents for a query are drawn from two distinct
probability distributions.  Formally, if we let $\mathbf{d}$ denote a
random document drawn from a distribution, and let variable $r=1$ if a
document is relevant and 0 otherwise, then $\Pr(\mathbf{d} \mid r=1)$
(resp. $\Pr(\mathbf{d} \mid r=0)$) denotes the probability that a
randomly generated relevant (resp. irrelevant) document turns out to
be $\mathbf{d}$,

The Probability Ranking Principle~\cite{kieth:IR} suggests that
documents should be ranked for the user in order of their
probabilities of relevance, $\Pr(r=1 \mid \mathbf{d})$.  A standard
application of Bayes Law shows that this ranking is independent of
$\Pr(r=1)$ and monotonic in a \emph{ranking value (RV)}
\[
\frac{\Pr(\mathbf{d}\mid r=0)}{\Pr(\mathbf{d}\mid r=1)}.
\]

In practice, while the probability distributions above are assumed to
\emph{exist}, they are not \emph{known} at the time of
retrieval. Bayesian machine learning provides a principled way to
estimate these distributions based on data such as an input query or
labeled documents.  To estimate the desired distributions, we assume
that the correct distribution is one member of some specific
\emph{family} of distributions and, based on the query-related
information provided, we attempt to choose a plausible
distribution from that family.

Two questions must be answered to use this approach: (i) what family
of distributions is used (a modelling question) and (ii) which
distribution to choose from the family given the data (a model-fitting
question).  As an example of what \emph{not} to do, we might declare
our relevant-document distribution to be a uniform distribution on the
set of labelled relevant documents.  This is an extreme example of
\emph{over-fitting}: we get a distribution that perfectly explains the
labelled documents we have seen, but assigns probability zero to any
document we have not seen.  Such a distribution is useless for
predicting the relevance of other documents.

To avoid overfitting, the standard approach in machine learning is to
use a \emph{prior}.  This is a probability distribution \emph{over
possibile probability distributions}.  In other words, we label the
possible probability distributions by some parameter $\theta$, then
specify a prior $\Pr(\theta)$.  When presented with some labelled data
$D$ drawn from the unknown distribution, we choose as a plausible
distribution the most likely value of $\theta$, i.e. $\mbox{argmax}_\theta
\Pr(\theta \mid D)$.  This may be algorithmically challenging, but is
well specified.  The approx is referred to as \emph{Maximum A
Posteriori (MAP)} estimation.

Ignoring algorithmic issues, then, the only thing needed in a
Bayesian machine learning approach to labelling documents is a prior
over probability distributions of relevant documents and a prior over
probablity distributions of irrelevant documents.

\section{Example: Multinomial Model}
\label{sec:mult}


As a concrete example, the multinomial
model~\cite{kalt:newProb,lewis:forty} assumes that the family of
probability distributions is precisely the set of multinomial
distributions over words -- that is, that a document is generated by
repeated independent sampling from a probability distribution of words
in the corpus.  Under such a model, the probability distribution for
the number of times $d_t$ that feature $t$ appears in a document is
\begin{equation}
\Pr(d_t\mid r=x) = {\ell \choose d_t}
\left(\theta_t^{r=x}\right)^{d_t}
\left(1-\theta_t^{r=x}\right)^{\ell-d_t},
\label{eqn:mult}
\end{equation}
where $\ell$ represents the document length (note the distributions
for distinct terms are not independent, as they must some to the
specified docoument length).  Within this family, a particular
distribution is chosen for each feature $t$ by setting the parameter
$\theta^{r=x}_t$.

Given some labeled relevant documents, one can hypothesize that the
``correct'' multinomial distribution is one where the probability of
each term is equal to its empirical probability of occurrence in the
labeled documents.  Unfortunately, this sets the probability of any
unseen word to 0, which cause any new document with a new word to get
probability 0, an example of overfitting.  To avoid this, one uses a
prior that (in addition to restricting to multinomial distributions)
rules out 0-probabilities on terms, instead giving prior probability
to distributions that give each term in the corpus some small chance
of appearing (e.g.,~\cite{nigam:EMtoClassify1}).


\subsection{Evaluating the Multinomial Model}

The multinomial model is very simple, but not very good.  To understand
how good it is, we first clarify
``goodness.''  Clearly, the quality of predictions made using the
model (family of distributions) depends on how well the distribution
selected from the model matches the actual (unknown) distribution.
If the chosen distribution is very different from the target,
predictions using it are unlikely to be accurate.  A bad match may
arise from learning the distribution poorly, but a more fundamental barrier
arises if the family contains no distributions similar to the real
distributions---in that case, no learning algorithm could find a good one.
The gap between true distributions and model distributions is known as
\emph{bias} and is one of the two sources of error in a learning
algorithm (the other, \emph{variance}, reflects flaws in the choice of
a distribution from the model).

The standard way to measure the fit of a distribution to some data
is to ask how likely that data was to be generated by the
distribution.  In this framework, the best fit distribution in the
model is the one that assigns the maximum probability to the observed
data; the higher the probability, the better the fit.  This
distribution is known as the \emph{maximum likelihood (ML)}
distribution.  We can therefore evaluate the fit of a model to the
data by finding the maximum likelihood distribution for the model.

Note that this approach makes no mention of the prior.  This is
because our goal here is to investigate the \emph{existence} of a good
distribution in the model; we do not aim to use the distribution for
anything else.

For the multinomial model, it is well known that the maximum
likelihood parameter setting, for $\theta_t$, in the absence of a
prior, is the average rate of appearance of the feature in the labeled
data. This means that $\theta_t$ is the total number of occurrences of
the term divided by the sum of document lengths.

\subsection{Results of the Evaluation}

In a preliminary study, we evaluated how well the multinomial
distribution actually captured the statistical properties of a
particular corpus: the TREC documents from CDs 1 and 2 of the
series. We fit a multinomial model to these documents and then
compared the fit model to reality.  Since the multinomial distribution
depends on the length of a document as well as its probability
parameter, we focused on two sets of 10,000 and 25,000 documents of
similar length, thereby eliminating any length effects.  We found
substantial mismatches in a number of basic properties.

Our overall goal was to determine how similar to multinomial
distributions the observed distributions of terms in documents were.
Unfortunately even if each term was drawn from a multinomial
distribution, its \emph{empirical} distribution might not look
multinomial.

To get around this problem, we average the observed distributions of
many ``similar'' terms.  As discussed above, the maximum likelihood
multinomial-model parameter setting for a term is the average rate of
occurrence of the term in the data (ie, the fraction of terms that are
the specified term).  Under a multinomial distribution, the actual
rate of occurrence of a term will be tightly concentrated around its
expected number of occurrences.  It follows that most of the terms
appearing at a given rate in the corpus share roughly identical
parameter values in the multinomial model.  If we aggregate these
terms, we should smooth out the noise of individual empirical term
distributions and recover a distribution close to the true one.  (We
omit formal details due to lack of space.)  For this reason we binned
terms with similar occurrence rates, and compared their average
distribution with what the multinomial model predicts.

Figure~\ref{fig:tail} shows the average term distribution for terms
that empirically appeared approximately once every 100,000 words and
the term distribution the multinomial model would expect for terms with
the same rate of occurrence.  Since the multinomial distribution is roughly
exponential, it appears as a nearly straight line on a log scale.  On
the other hand, the tail for the empirical term distribution is much
heavier. The probability of multiple occurrences of a term in a
document is much higher than would be expected in a multinomial model,
while the probability of a term occurring alone is empirically lower
than would be expected.  The multinomial model assumes that whether a
term occurs again in a document independent of whether it has already
occurred in that document, while clearly from Figure~\ref{fig:tail}
this is an inaccurate assumption. This behavior, also called
``burstiness'', has been observed by other researches such as Katz
\cite{katz:nl} and Church and Gale \cite{church:poisson}.\footnote{%
While the empirical term distribution is not multinomial, the log of
the term frequency distribution actually does look significantly more
like a multinomial distribution. It appears almost straight on a
$\log$-$\log$ scale.  Applying the machine-learning paradigm to this
multinomially distributied quantity yields a variant of the standard
vector space model, in which the ``weight'' of a term is set
proportional to the log of its occurence count.}
 
\begin{figure}[htbp]
\centering
\epsfig{file=imgs/tail-mult.eps, width=7cm}
\caption{The empirical term distribution compared with what is
expected for the multinomial model.  Term
occurrence appears to be more clustered in reality than the
multinomial model expects.}
\label{fig:tail}
\end{figure}


\section{Candidates for a Better Model}

Given the failure of the multinomial model to match the text, we
sought a better model.  However, we did want to preserve two important
features of the multinomial model.  First, computations over it, and
in particular retreival algorithms using it, are very efficient.
Second, its relatively ``small'' collection of distributions prevents
overfitting (it is always possible to reduce the bias of a model by
adding distributions; we wish to avoid that route).  We therefore
chose to focus on \emph{na\"{\i}ve Bayesian models}~\cite{lewis:forty}
constructed from \emph{One parameter exponential families}.

\subsection{Na\"{\i}ve Bayesian Retrieval}
\label{nb:naive}

While all probabilistic models assume that a document can be
statistically described by certain features, and that the occurrence
of those features is sufficient to determine whether the document is
relevant or not, a na\"{\i}ve Bayesian model further assumes that
document features are independent, given a relevance judgement.  All
interactions between features are ignored.  This implies that the
probability of a document is equal to the product of its feature
probabilities and allows for efficient retrieval implementations. Many
probabilistic IR models, can be expressed within the na\"{\i}ve
Bayesian framework.

If document $\mathbf{d}$ has $T$ features, with the $t$th feature
represented as $d_t$, the probability of observing the document given
a certain relevance judgment is thus
\begin{align*}
\Pr(\mathbf{d}\mid r=x) &= \prod_{t=0}^T \Pr(d_t\mid r=x),
\end{align*}
where $\Pr(d_t\mid r=x)$ denotes the probability of seeing $d_t$
occurrences of feature $t$. While the independence assumption is
obviously an oversimplification, it is common and useful because the
number of features typically used to describe a document is very
large.  Having to account for all possible interactions between
features would require an infeasible amount of time and space, as well
as an infeasible amount of data to estimate those interactions.

While the feature set could be anything, in our analysis, we restrict
the feature set to be words.  Note that this same analysis could be
done just as easily with whatever feature set we should choose to
define, although the resulting statistical properties of that feature
set would likely be different.

\paragraph{Efficiency.}

By assuming that all features are independent, we can simplify our
ranking value considerably.
\begin{align*}
RV &= \frac{\Pr(\mathbf{d}\mid r=1)}{\Pr(\mathbf{d}\mid r=0)} \\
&= \prod_{t=0}^T \frac{\Pr(d_t\mid r=1)}{\Pr(d_t\mid r=0)}.
\end{align*}
Taking the logarithm of this quantity (which helps avoid numerical
instability caused by multiplying numerous small quantites) produces a
sum of ``term scores'' that can be evaluated in much the same way as a
traditional vector space model.  Although the above shows a score per
term in the corpus, as is observed
elsewhere~\cite{rob:poisson}, it is possible to factor out the
contributions of 0-occurrence terms to the probability and be left
with a sum only over terms appearing in the document.

\paragraph{Relation to the Multinomial Model}

It should be noted that the multinomial model discussed above is
does \emph{not} fit our definition of a naive Bayesian model.  Once
the document length $\ell$ is fixed, a large number of occurrences of
one term leaves fewer spaces for other terms to occur, so distinct
term occurrence counts are not independent.

However, the closely related \emph{Poisson model}, in which each term
has an (independent) Poisson distribution (with the same parameters as
in the multinomial model) does fit the Naive Bayes framework.
Like other Na\:{\i}ve Bayesian Models, the Poisson model does not
produce documents of a fixed length, rather, it produces a
distribution over document lengths.

\paragraph{Coping with length.}

The fact that Na\"{\i}ve Bayesian models produce documents of varying
lengths can have some undesirable consequences.  In particular, the
relevant and irrelevant document distributions may induce different
document-length distributions, leading to questionable deductions such
as ``short documents are more likely to be relevant than long ones.''
While such a conclusion may be supportable, some prefer to apply
``length normalization'' to eliminate this dependence.  From the Naive
Bayesian model, one can derive in a principled fashion an
``appropriate'' and tractable length normalization scheme by
conditioning the probability distributions on the desired length of a
document.  Because of the law of large numbers, the distribution of
document lengths will be normal, and can be estimated by finding the
mean and variance of the relevantand irrelevant documents.  Thus each
document can be normalized with respect to document length by
multiplying it by this length factor.  At the present time, we have
not investigated this experimentally; instead, for the remainder of
the paper, we shall simply ignore this length issue.

\subsection{Exponential Distributions}

Having chosen the Naive Bayesian framework, we still need to define a
family from which we can select (independent) probability
distributions for the individual terms.  

In an initial decision, we choose to limit to the possible
distribution families to ones that could describe each term with a
single parameter.  This restriction ruled out many plausible
distribution families, such as mixture models.  However, restricting
ourselves in this way reduced the risk of over-fitting, as there were
less parameters to estimate with the same amount of data, and made for
a simple and efficient model that translates easily into a vector
space model.

Narrowing further, we chose the set of \emph{one-parameter exponential
families}.  Exponential families are popular models in machine
learning because they are quite general (the Poisson, Binomial,
Uniform, and Gaussian families are all exponential families) but can
still be optimized efficiently.  Thus, much work has been done on how
to best work with such families.  For our application, they support
efficient retrieval with the same complexity as standard models.

A one parameter exponential family takes the form
\begin{equation}
\Pr(d_t\mid \phi_t) = f(d_t)g(\phi_t)e^{\phi_th(d_t)},
\label{eq:exp}
\end{equation}
where $g(\phi_t)$ is a normalizing constant equal to the inverse of
$\int f(d_t) \text{exp}\left(\phi_th(d_t)\right)dd_t$. Recall that
$d_t$ is the number of occurrences of term $t$.  The functions $f$ and
$h$ define the specific exponential family. For example, for a
binomial model, $f(d_t)={\ell \choose d_t}$ and $h(d_t)=d_t$. For a
Poisson model $f(d_t)=(d_t!)^{-1}$ and $h(d_t)=d_t$.  A particular
distribution is specified from the family by setting the parameter
$\phi_t$.  We emphasize: the model is determined once by specifying
$f$ and $h$, which then become constants.  Learning is performed by
fitting the $\phi_t$ parameters.



\section{Hyper-Learning a Better Model}
\label{sec:textmodel}

Instead of imposing a particular exponential family, such as the
Poisson family, on the term distributions, we propose that the
``right'' distribution family should be determined experimentally,
prior to retrieval, directly from the data (the text, past queries and
relevance judgments).  This process, of examining the entire corpus to
set the ``hyper-parameters'' $f$ and $h$ in our model, is similar in
style to learning the parameters $\phi_t$ from labelled relevant
documents; to distinguish this process from the process of learning
the specific term distributions, necessary at query time, we call the
preliminary process \emph{hyper-learning}.  Given a hyper-learned
model, it is necessary at retrieval time to then learn the parameters
that define the specific term distributions within the family as
relate to the query (e.g., $\theta_t$ from Equation~\ref{eqn:mult} in
the case of the multinomial model).  In this section we describe the
hyper-learning process. By hyper-learning a better distribution
family, we were able to create a new model that put increases the
burstiness of term occurrences, and thus more accurately predicts the
existence of our data.

\subsection{Finding the Best Family}

As was discussed above, a standard measure of ``fit'' between a given
distribution and some data is the probability the distribution assigns
to the data; within a distribution, the ``best fit'' distribution is
the one that assigns Maximum Likelihood (ML) to the data.  Formally,
the quality of a particular model is equal to the maximum likelihood
value we can achieve by choosing the specific term distributions by
setting of $\phi_t$ parameters.  If we define $Q(f,h,\mathbf{\phi_t})$
to be the likelihood assigned to the data by a particular collection
of distributions from the model defined by $f$ and $h$, then the best
fit within the model is
$\max_{\mathbf{\phi_t}}Q(f,h,\mathbf{\phi_t})$.  If we want to find
the best model, i.e. the one containing the best distribution for the
data, then we wish to maximize the above quantity over choices of $f$
and $h$.  It is easy to see that we can conflate these two
maximizations and find our best model by taking the values $f$ and $h$
from
\[
\mbox{argmax}_{f,h,\mathbf{\phi_t}} Q(f,h,\mathbf{\phi_t}).
\]
By setting $\mathbf{\phi_t}$ to be the maximum likelihood value we
risk over-fitting.  While this would not be a good setting for
retrieval, it is acceptable because we are trying to find the model
that best describes our data.

Let us first consider the problem of finding the best model to explain
a particular set of documents, such as documents relevant to a
particular query.  Recall that the probability of observing a
particular document can be expressed as $\prod_{t=0}^T \Pr(d_t\mid
\phi_t)$.  To find the probability of the entire document set we need
to find the product of $\Pr(d_t\mid \phi_t)$ over all terms and over
all documents.  This can be expressed more succinctly because $d_t$ is
always a non-negative integer, and, in fact, is almost always
zero. Therefor, without losing almost any information, we can only
consider the cases where $d_t$ is less than some small integer
$k$. Grouping together for each term $t$ the times it occurs $i$
times, we can express the probability of observing the entire document
set as
\begin{align*}
Q &= \prod_{t=0}^T \prod_{i=0}^k
{\Pr(i\mid \phi_t)}^{n_i^t},
\end{align*}
where $n_i^t$ refers to the number of times term $t$ occurs $i$ times. Because 
the probabilities of term occurrences are small, we work with the log of this 
value,
\begin{align*}
\log(Q) &= \sum_{t=0}^T \sum_{i=0}^k
{n_i^t} \log({\Pr(i\mid \phi_t)}).
\end{align*}
Finding $f$ and $h$ is simply a matter of finding the $2(k+1)$ values
the two functions take at each possible $i$ to maximize this value. In
our experiments, we take $k$ to be 5, as even a $k$ of 2 correctly
describes 99.9\% of all term occurrences.

Our approach remains much the same when we want to find the best model to 
explain a \emph{collection} of document sets. We aim to fix values $f$ and $h$ 
that explains \emph{all} of these document sets.  However, we naturally allow 
that each document set may reflect a different distribution drawn from the 
model.  Thus, we use a \emph{distinct} parameter $\phi_t^R$ for term $t$ in 
\emph{each} document set.  Formally, if $\cal R$ represents the class of 
document sets, and $R\in{\cal R}$ is a particular document set, the objective 
function $Q$ becomes
\[
Q=\prod_{R \in \cal R} \prod_{\mathbf{d} \in R} \Pr(\mathbf{d}
\mid \phi_t^R).
\]
This equation can be mapped back to the ``single document set'' equation if we 
simply pretend that a given corpus term actually turns into a distinct term in 
each set.  Thus, we focus our discussion on the notationally simpler single-set 
formula, knowing that it applies equally to studying a collection of document 
sets.

The problem of optimizing $Q$ is a large multivariate optimization problem.  
There is no obvious analytic solution, so we turn to computational methods.  As 
a proof of concept, we use a simple gradient ascent method.  As we will see, $Q$ 
is convex in the parameters $\phi_t$ but non-convex in the values $f$ and $h$.  
Thus, we cannot guarantee that gradient ascent finds a globally optimum model. 
In the future, we hope to combine a more sophisticated non-convex optimization 
algorithm on the $f$ and $h$ values with the fast and simple convex optimization 
of the $\phi_t$ values.

For the moment, we take an iterative approach.  Given some fixed $f$ and $h$ 
values, it is straightforward to find the (globally) optimum $\phi_t$ values.  
We then hold the $\phi_t$ values fixed and seek (locally) optimum $f$ and $h$ 
values given those $\phi_t$ values.  We iterate this procedure until it 
converges.

\subsubsection{The Best $\phi_t$ Given $f$ and $h$}
\label{sec:findphi}

The probability of observing each document, and thus the objective $Q$, is 
concave with respect to each parameter $\phi_t$. We can prove concavity by 
showing that the second derivative of $\log(Q)$ with respect to $\phi_t$,
\begin{align*}
\frac{d^2\log(Q)}{{d\phi_t}^2} &=
- N \sum_{i=0}^k {h(i)}^2 \Pr( i \mid  \phi_t)  \\
& + N \left(\sum_{i=0}^k h(i) \Pr(i\mid  \phi_t) \right)^2,  \\
\intertext{is negative.  Since $\sum_{i=0}^k {h(i)} \Pr( i \mid  \phi_t)$ is 
equal to the expectation of $h(i)$, $E[h(i)]$, we can rewrite the second 
derivative as}
&= -N( E[h(i)^2] - E[h(i)]^2) \\
&= -N \text{Var}[h(i)].
\end{align*}
Since variance is always positive, the second derivative with respect to 
$\phi_t$ is always negative, and $\log(Q)$ is concave with respect to $\phi_t$.

Because $\log(Q)$ is concave with respect to $\phi_t$, if we know the functions 
$f$ and $h$, we can find the most likely $\phi_t$ for each term using convex 
optimization. To find $\phi_t$ we do a simple bisection search to find where 
first the derivative of $\log(Q)$ with respect to $\phi_t$,
\begin{align*}
\frac{d \log(Q)}{d \phi_t} &=
\sum_{i=0}^k h(i) \left( n_i^t - N \Pr(i\mid \phi_t) \right),
\end{align*}
is equal to zero.

\subsubsection{The Best $f$ and $h$ Given $\phi_t$}

Unlike for $\phi_t$, the objective function is \emph{not} convex in $f$ and $h$, 
as can be seen in Figure~\ref{fig:deltafh}. Nonetheless, to find $f$ and $h$ we 
do a simple gradient ascent to a local optimum, using
\begin{align*}
\frac{d \log(Q)}{d h(i)} &=
\sum_{t=0}^T \phi_t
\left( n_i^t - N \Pr(i\mid \phi_t) \right)
\intertext{and}
\frac{d \log(Q)}{d f(i)} &=
\frac{1}{f(i)}\sum_{t=0}^T
\left( n_i^t - N \Pr(i\mid \phi_t) \right),
\end{align*}
the gradient functions, to aid our search.

\begin{figure}[htbp]
\centering
\begin{turn}{-90}
\epsfig{file=imgs/deltafh.ps, width=5cm}
\end{turn}
\caption{The probability of the data is not convex with respect to $f$
and $h$.  The graph plots the log-likelihood of the data under a
convex combination of two distinct $f$ and $h$ values that achieved
local maxima by optimizing from two different starting points.}
\label{fig:deltafh}
\end{figure}

Because $\log(Q)$ is not convex with respect to $f$ and $h$, the
starting point is very important.  If we did not start somewhere good,
we very well might converge to a poor local maximum.  We began our
hyper-learning with the Poisson family (exponential-family cousin of
the multinomial family) as our starting point, setting
$f(i)=(i!)^{-1}$ and $h(i)=i$.

\subsubsection{Data Set}

We hyper-learned the family of term distributions over sets of
relevant documents. Each set was comprised of the relevant documents
for a particular query from TREC 1 and 2 (queries 51-150).  The query
result sets ranged from containing just tens of documents and under a
thousand unique terms, to containing almost a thousand documents and
tens of thousands of unique terms.

We used sets of relevant documents for several reasons.  First, as we
will discuss in Section~\ref{sec:est}, we considered the problem of
understanding of the family of distributions capturing relevant document 
sets more interesting for retrieval purposes.
Additionally, because relevant document sets are considerably smaller
than irrelevant document sets they also are considerably more varied
within a given corpus.  The largely overlapping irrelevant document
sets would not allow us to generalize well.  The smaller 
size of relevant document sets also made them more computationally feasible 
to work with.

Hyper-learning over all 100 document sets would have left us with no
test data.  Instead, we learned the best $f$ and $h$ for randomly
selected ``training'' subset of up to 40 of the total 100 relevant
document sets.  This allowed us to test the learned model on the
remaining ``testing'' document sets, and prove that our model would
not overfit new queries.  The functions $f$ and $h$ did not change
drastically when hyper-learned on larger document sets (e.g., when
increasing from a set of 30 to a set of 40), so it is likely that
including all 100 would not have provided much additional information.
 
\subsubsection{The Hyper-Learned Families}

The functions $f$ and $h$ that we found as a result of hyper-learning
over 40 relevant document sets can be seen in Table~\ref{tab:fh}. The
hyper-learned function $f$ fell off much faster than its Poisson
starting point, as can be seen in Figure~\ref{fig:learned.ps}.
Because $f$ is just a scalar in Equation~\ref{eq:exp}, changes to its
shape do not have a drastic effect on individual term distributions.
However, $f$ is the least term-dependent portion, and as such, its
quick drop off probably reflects the quick drop off common to
all terms between the probability of a term occurring zero times and a
term occurring once or more.

%\begin{table}
%\centering
%\begin{tabular}{|r||c|c|}
%\hline
%$d_t$ & $f$ & $h$ \\
%\hline \hline
%0 & 1.1378 & -1.1211 \\ \hline
%1 & 0.0307 & 2.1291 \\ \hline
%2 & 0.0049 & 3.1803 \\ \hline
%3 & 0.0015 & 3.6476 \\ \hline
%4 & 0.0007 & 3.9024 \\ \hline
%5 & 0.0014 & 4.0801 \\ \hline
%\end{tabular}
%\caption{The hyper-learned values for $f$ and $h$.
%\label{tab:fh}}
%\end{table}

\begin{table}
\centering
\begin{tabular}{|r||c|c|c|c|c|c|}
\hline
$d_t$ & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline \hline
f & 1.1378 & 0.0307 & 0.0049 & 0.0015 & 0.0007 & 0.0014 \\ \hline 
h & -1.1211 & 2.1291 & 3.1803 & 3.6476 & 3.9024 & 4.0801 \\ \hline
\end{tabular}
\caption{The hyper-learned values for $f$ and $h$.
\label{tab:fh}}
\end{table}

The slope of the function $h$ decreased considerably from its Poisson
starting point, and its curve became concave, can also be seen in
Figure~\ref{fig:learned.ps}.  Because $h$ is in the exponent of
Equation~\ref{eq:exp}, changes to it do have a significant effect on
the resulting term distribution.  The decreased slope and concavity
probably reflect a de-emphasis on high term occurrences, correcting
the Poisson model for the ``burstiness'' we observed.

\begin{figure}[htbp]
\centering
\mbox{
\subfigure{\epsfig{file=imgs/learned_f.eps, width=4cm}}\quad
\subfigure{\epsfig{file=imgs/learned_h.eps, width=4cm}}
}
\caption{The functions that define the hyper-learned family, compared with the Poisson.}
\label{fig:learned.ps}
\end{figure}

Figure~\ref{fig:tail} shows an example distribution, illustrating that 
the new distribution family more closely matches our data.  As expected from our 
textual analysis, we find a term distribution that has a heavier tail than 
predicted by the Poisson model.  Using the family hyper-learnedover 60 query 
result sets, we can predict the existance of the other 60 result sets by 
computing the maximum likelihood $\mathbf{\phi_t}$ from a subset of the
documents, and thenusing those specific term distributions to find the
probability of the remaining documents.  We find that the average log
probability of observing an unobserved relevant document set is much higher
using the hyper-learned family (-187,811) than using the Poisson family
(-231,368).

\section{Retrieving with the new model}

We performed retrieval with the hyper-learned family of one parameter 
exponential distributions.  We found that by improving on the Poisson generative
model by hyper-learning from the text a better family of distributions, we were also
able to improve on retrieval performance.  In
this section we first discuss how we estimated the model parameters 
($\mathbf{\phi_t}$) to perform the queries and then we present our results.

\subsection{Estimating the Distributions}
\label{sec:est}

To be able to rank a
document we needed to specify both the relevant and irrelevant probability 
distributions for a term.  We took a different approach to estimating the
relevant and irrelevant distributions, and we discuss both processes separately
here.

\subsubsection{Relevant Distributions}

In our estimation of the specific relevant term distributions (defined by 
$\mathbf{\phi_t}$) within our hyper-learned model, we assume we have observed 
some labeled information.  This can either be a description of an information
need (e.g., a keyword query), which we treat as a labeled relevant document,
or actual labeled relevant documents.

For distributions in the one-parameter exponential family, all observations can 
be summarized, to the extent that they affect the parameter $\phi_t$, with two 
\emph{sufficient statistics}, $\tau_1$ and $\tau_2$~\cite{bern:bt}.  The 
statistic $\tau_1$ represents the number of observations that have
been made, and $\tau_2$ represents the sum of all $h$ values observed. 
Using this framework we can easily incorporate a prior by observing a certain 
number of ``virtual documents'' with the corpus statistics,
and including these observations in our sufficient statistics.

The probability of $\phi_t$ based on the sufficient statistics is
\begin{equation}
\Pr(\phi_t) = \left[K(\tau_1,\tau_2)\right]^{-1}
\left[\sum_{i=0}^k f(i) e^{\phi_t h(i)}\right]^{-\tau_1} e^{\phi_t\tau_2},
\label{eq:phi}
\end{equation}
where $K(\tau_1,\tau_2)$ is the integral with respect to $\phi_t$ that  
normalizes  the probability to sum to 1. This intregal is difficult
to compute, but becomes irrelevant when we find the MAP estimate 
(most likely value) for $\phi_t$ by taking the derivative of Equation~\ref{eq:phi},
\begin{align*}
\frac{d\Pr(\phi_t)}{d\phi_t} = \Pr(\phi_t)\left(\tau_2-\tau_1\left(
\frac{\sum_{i=0}^kf(i) h(i) e^{\phi_t h(i)}}
{\sum_{i=0}^kf(i) e^{\phi_t h(i)}}\right)\right),
\end{align*}
and set it equal to zero.  It is zero when
\begin{align*}
\frac{\sum_{i=0}^kf(i) h(i) e^{\phi_t h(i)}}
{\sum_{i=0}^kf(i) e^{\phi_t h(i)}} = \frac{\tau_2}{\tau_1}.
\end{align*}
While there is also no obvious analytic solution for this problem, we can make a 
table of left hand side values as a function of $\phi_t$.  Once we observe our 
sufficient statistics, $\tau_1$ and $\tau_2$, we can use them to find the 
correct $\phi_t$ via table lookup.

Note that while we do not use it in our experiments, the Bayesian
machine learning framework also provides a natural way to apply 
automatic relevance feedback.  To do so, we could modify the framework to seek
not just the MAP value of $\phi_t$ based on our initial observations about 
the relevant term distributions, 
but the joint MAP value of $\phi_t$ and a \emph{relevance judgment for
each unlabelled document}.  The parameter estimate $\phi_t$ and the 
relevance judgments would feed off each other: a given $\phi_t$ would 
make documents that match the $\phi_t$ distribution look relevant,
while labeling certain documents as relevant would push $\phi_t$
towards a value that generates those kinds of documents.  For example,
Nigam et al., implemented a multinomial model for classification that
relied on only a few labeled documents, but used Expectation
Maximization (EM) to include information from unlabeled 
documents~\cite{nigam:EMtoClassify1}.  We conjecture that our model,
more accurate than the multinomial, would improve the performance of the
Nigam et al. scheme.

\subsubsection{Irrelevant Distributions}
\label{nb:irrelevant}

In order to find our ranking value, we also needed the term distributions
within the irrelevant documents.
We did not assume that we were provided with any labeled information about
the irrelevant distributions.  Instead, because most documents in a corpus
are not relevant to any given query, we decided that it was close
enough to assume that the feature distributions across the irrelevant
documents were the same as the distributions across the entire corpus.
This is not necessarily the case, particularly for the most interesting
features in the relevant documents.  For example, a very
interesting relevant features such as those selected for a keyword query
could possibly not occur in any irrelevant documents.
However, our focus in hyper-learning distribution families was for query result 
sets.  We focused less attention on understanding the distributions for the
irrelevant documents.  Additionally, assuming that all documents are
irrelevant allowed us to estimate the irrelevant distributions before retrieval
time, directly from the corpus.

The whole-corpus problem is in fact somewhat different.  Unlike 
result sets for unknown future queries, the entire corpus is available in 
advance, and provides us with a large amount of information for estimating.  It is 
therefore less important to have an entire \emph{family} of 
distributions for the corpus and select the best actual distributions.  Since we 
were \emph{not} working with a family, we abandoned the restriction to an 
exponential family, and used the empirical distribution for each term in the 
corpus as our irrelevant document distribution.

\subsection{Results}

We first show a proof of concept that our model does improve retrieval when
we can make a good estimate of the term distributions.  We then discuss how
the model can be used in a more typical environment, where the only information
provided about the relevant distributions is a short query, and retrieval must
be done in real time.

\subsubsection{Using Labeled Documents}

As proof of concept, we wanted to get a good idea of how our model worked when
we actually had a good estimate of the term distributions. However, we also wanted
to be sure it generalized. One way to do this is, similar to relevance feedback,
to assume that there are a number of labeled relevant documents, use them to estimate
the distributions, and then test over the remaining documents.  This is the framework 
that matches most directly the standard machine learning model from Section~\ref{sec:ml}.
The occurrences pattern of a document feature in the labeled documents is used to 
MAP-estimate its probability distribution in relevant documents.  In IR, the
number of labeled documents used for estimating the relevant feature distributions 
ranges, and can be as many as half of the relevant documents \cite{kalt:newProb}.

We evaluated a model hyper-learned over 26 queries on the remaining 74
queries from TREC 1 and 2. We used 20 randomly selected relevant documents for our training,
and assumed, as a prior, that we had observed 10 documents with the corpus distribution.
Figure~\ref{fig:results} shows the performance of the hyper-learned model
compared with the Poisson model.  The new model out-performs
the Poisson model in all areas of the precision-recall curve.  The average
precision for the hyper-learned model (0.1643) is higher than that for the Poisson
model (0.1411).
\begin{figure}[htbp]
\centering
\epsfig{file=imgs/results.76.eps, width=7cm}
\caption{Precision-recall curves for retrieval using the hyper-learned model compared
with Poisson model, using 20 training documents per query.}
\label{fig:results}
\end{figure}

\subsubsection{Using a Query}

A more common way for an information need to be specified is through a query.  When
the only information we have about the relevant term distributions is a query,
we can rank documents using the following vector space type calculation,
\begin{align*}
RV =& \sum_{t\in d} \left[ \log\left(\frac{n_t^0}{n_t^{d_t}}\right) + \log\left(\frac{f(d_t)}{f(0)}\right)
+ (h(x)-h(0))\bar{h}_t\right] + \\ & \sum_{t \in q} \left[(h(d_t)-h(0))\frac{h(q_t)}{c+1}\right].
\end{align*}
where $c$ represents the number of observations we've made for our prior, and $\bar{h}_t$ 
is our belief about term $t$ assuming it doesn't appear in the query.

This ranking value highlights the na\"{\i}ve Bayesian model's problem with length.  All 
documents are given a default value regardless of whether the query term has occurred in it or not,
and that value is affected by the number of terms in the document.  In the case where we have a decent idea
about the term distribution in relevant documents, this is often overpowered by the strength of
the evidence in which terms occur or not.  But in the case where we only know the query, it isn't,
and retrieval performance is abismal.

\begin{figure}[htbp]
\centering
\epsfig{file=imgs/results.vs.eps, width=7cm}
\caption{Precision-recall curves for retrieval using the hyper-learned model and Poisson model
using only short queries.  Compared with tf.idf.}
\label{fig:vsresults}
\end{figure}

This document value can be sidestepped if, instead, we assume that we don't learn anything
about the terms that do \emph{not} occur in the query. As can be seen in Figure~\ref{fig:vsresults},
performance is comparable to tf.idf \cite{mckeown:sum}, slightly worse in areas of high precision, 
and better in areas of low 
precision (and always better than the Poisson model).  By tweaking the way the query is 
incorporated more, we could probably get better performance. Because a query is not a document, 
it is not necessarily right to treat it as such. However, it would be good to come up
with a good model for the query instead.

% This table is now out of date, because of a change in meaning of \bar{h}.
% Shouldn't be re-included without fixing that.
%\begin{table}
%\centering
%\begin{tabular}{|l||l|}
%\hline
%1 & $1.6251 \bar{h_t} - 0.1519 + \log(n_0^t/n_1^t)$ \\ \hline
%2 & $2.1507 \bar{h_t} + 1.3919 + \log(n_0^t/n_2^t)$ \\ \hline
%3 & $2.3843 \bar{h_t} + 2.0553 + \log(n_0^t/n_3^t)$ \\ \hline
%4 & $2.5118 \bar{h_t} + 2.3495 + \log(n_0^t/n_4^t)$ \\ \hline
%5+ & $2.6006 \bar{h_t} + 3.9264 + \log(n_0^t/n_{5+}^t)$ \\ \hline
%\end{tabular}
%\caption{The corresponding term weights for a vector space model,
%assuming the query term occurs only once. The value for $\bar{h}$ is the
%average observed $h_t$ for that term, $\sum_{d\in D}h(d_t)/n$.\label{tab:vector}}
%\end{table}

\section{Conclusions and Future Work}

By working with the statistical properties of text, we were able to learn a 
na\"{\i}ve Bayesian model that more closely matched the corpus than a 
multinomial or Poisson model. We discussed what was involved in learning such a 
model, and how we used it for retrieval. In learning more likely term 
distribution families, we were not only able to better describe our data, but we 
were also able to improve retrieval quality.


We used a simple gradient ascent method to hyper-learn the best distribution 
family for our model. There is still work to be done to find even better 
distribution families by hyper-learning global maxima for $f$ and $h$.  The best 
values would not be dependent on our starting point.  Improving our search for 
the best distribution family will involve investigating some more sophisticated 
search functions, and arriving at an even better understand of our search space.  
Once we have good values for $f$ and $h$ learned from a variety of different 
text corpora, we would like to generalize them into analytic functions.  This 
could allow us to make retrieval more efficient.  We have also not yet tested
normalizing for document length during retrieval, and intend to pursue this.

\section{Acknowledgements}

\emph{Removed for anonimity.}
%We would like to thank Stephen Robertson and Tommi Jaakola for their help with 
%this work.

\bibliographystyle{abbrv}
\bibliography{main}
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!

\end{document}

