\documentstyle[jair,twoside,11pt,theapa,psfig]{article}
% \input epsf %% at top of file
% \input{psfig}

%%% JAIR info
\jairheading{11}{1999}{95-130}{3/98}{7/99}
\ShortHeadings{Information-Based Semantic Similarity}
{Resnik}
\firstpageno{95}


%%% cc2tex global directive
%ccglob{ccfname=clib.24, height=11pt, interval=0}

%%% Definitions
\input{sentence.macros}
\newcommand{\psr}[1]{[{\em #1 --psr}]}
\newcommand{\Ccal}{{\cal C}}
\newcommand{\Rcal}{{\cal R}}
\newcommand{\isa}{\mbox{\sc is-a}}
\newcommand{\wclass}[1]{{\sc #1}}
\newcommand{\Prob}{{\rm p}}
\newcommand{\similarity}{{\rm sim}}
\newcommand{\mx}[1]{\raisebox{-1.5ex}{\shortstack{{\rm max}\\{\small $#1$}}}}
\newcommand{\mn}[1]{\raisebox{-1.5ex}{\shortstack{{\rm min}\\{\small $#1$}}}}
\newcommand{\addcite}[1]{[cite #1]}
\newcommand{\ignore}[1]{}
\newcommand{\la}{$\langle$}
\newcommand{\ra}{$\rangle$}
\newcommand{\Assoc}{{\rm A}}
\newcommand{\Sim}{\mbox{\rm sim}}
\newcommand{\tinytype}{tiny}
\newcommand{\mytabs}{............\=...............\=...............\=...... \kill}


\begin{document}

%\title{Measuring Semantic Similarity using Information Content}
\title{Semantic Similarity in a Taxonomy:  An Information-Based
Measure and its Application to Problems of Ambiguity in Natural Language}

\author{\name Philip Resnik \email resnik@umiacs.umd.edu \\
        \addr Department of Linguistics and \\
        Institute for Advanced Computer Studies \\
        University of Maryland \\
        College Park, MD 20742 USA}

% For research notes, remove the comment character in the line below.
% \researchnote

\maketitle


\begin{abstract}
This article presents a measure of semantic similarity in an {\sc is-a}
taxonomy based on the notion of shared information content.
Experimental evaluation against a benchmark set of human similarity
judgments demonstrates that the measure performs better
than the traditional edge-counting approach.  The article presents
algorithms that take advantage of taxonomic similarity in resolving
syntactic and semantic ambiguity, along with experimental results
demonstrating their effectiveness.
\end{abstract}

\section{Introduction}
\label{sec:introduction}

Evaluating semantic relatedness using network representations is a
problem with a long history in artificial intelligence and psychology,
dating back to the spreading activation approach of Quillian
\citeyear{quillian1968} and Collins and Loftus \citeyear{collins1975}.
Semantic similarity represents a special case of semantic relatedness:
for example, cars and gasoline would seem to be more closely related
than, say, cars and bicycles, but the latter pair are certainly more
similar.  Rada et al. \cite{Rada89b} suggest that the assessment of
similarity in semantic networks can in fact be thought of as involving
just taxonomic ({\sc is-a}) links, to the exclusion of other link
types; that view will also be taken here, although admittedly links
such as {\sc part-of} can also be viewed as attributes that contribute
to similarity \cite<cf.>{smeaton1994,sussna1993}.

Although many measures of similarity are defined in the literature, they
are seldom accompanied by an independent characterization of the
phenomenon they are measuring, particularly when the measure is proposed
in service of a computational application (e.g., similarity of documents
in information retrieval, similarity of cases in case-based reasoning).
Rather, the worth of a similarity measure is in its utility for the
given task.  In the cognitive domain, similarity is treated as a
property characterized by human perception and intuition, in much the
same way as notions like ``plausibility'' and ``typicality.''  As such,
the worth of a similarity measure is in its fidelity to human behavior,
as measured by predictions of human performance on experimental tasks.
The latter view underlies the work in this article, although the results
presented comprise not only direct comparison with human performance but
also practical application to problems in natural language processing.

A natural, time-honored way to evaluate semantic similarity in a
taxonomy is to measure the distance between the nodes corresponding to
the items being compared --- the shorter the path from one node to
another, the more similar they are.  Given multiple paths, one takes the
length of the shortest one \cite{Lee93,Rada89a,Rada89b}.

A widely acknowledged problem with this approach, however, is that it
relies on the notion that links in the taxonomy represent uniform
distances.  Unfortunately, uniform link distance is difficult to
define, much less to control.  In real taxonomies, there is wide
variability in the ``distance'' covered by a single taxonomic link,
particularly when certain sub-taxonomies (e.g., biological categories)
are much denser than others.  For example, in WordNet
\cite{miller1990,fellbaum1998}, a widely used, broad-coverage semantic
network for English, it is not at all difficult to find links that
cover an intuitively narrow distance ({\sc rabbit ears} {\sc is-a}
{\sc television antenna}) or an intuitively wide one ({\sc
phytoplankton} {\sc is-a} {\sc living thing}).  The same kinds of
examples can be found in the Collins COBUILD Dictionary (Sinclair,
ed., 1987)\nocite{sinc1987a}, which identifies superordinate terms for
many words (e.g., {\sc safety valve} {\sc is-a} {\sc valve} seems much
narrower than {\sc knitting machine} {\sc is-a} {\sc machine}).

\ignore{
A second difficulty with edge-counting is its lack of context sensitivity.
How similar are a mouse and a rat?  Both are rodents, so one would typically
evaluate them as quite similar.  Yet someone who is in the business of dealing
with them --- a pet shop owner, perhaps, or a behaviorist --- might well think
of them as quite different.
}

In the first part of this article, I describe an alternative way to
evaluate semantic similarity in a taxonomy, based on the notion of
information content.  Like the edge-counting method, it is
conceptually quite simple.  However, it is not sensitive to the
problem of varying link distances.  In addition, by combining a
taxonomic structure with empirical probability estimates, it provides
a way of adapting a static knowledge structure to multiple contexts.
Section~\ref{sec:proposal} sets up the probabilistic framework and
defines the measure of semantic similarity in information-theoretic
terms, and Section~\ref{sec:evaluation} presents an evaluation of the
similarity measure against human similarity judgments, using the
simple edge-counting method as a baseline.

In the second part of the article,
Sections~\ref{sec:syntactic_ambiguity} and~\ref{sec:noun_groupings}, I
describe two applications of semantic similarity to problems of
ambiguity in natural language.  The first concerns a particular case
of syntactic ambiguity that involves both coordination and nominal
compounds, each of which is a pernicious source of structural
ambiguity in English.  Consider the phrase {\em food handling and
storage procedures}: does it represent a conjunction of {\em food
handling\/} and {\em storage procedures}, or does it refer to the {\em
handling and storage\/} of food?  The second application concerns the
resolution of word sense ambiguity --- not for words in running text,
which is a large open problem \cite<though cf.>{wilks96}, but for
groups of related words as are often discovered by distributional
analysis of text corpora or found in dictionaries and thesauri.
Finally, Section~\ref{sec:related} discusses related
work.

\section{Similarity and Information Content}
\label{sec:proposal}

Let $\Ccal$ be the set of concepts in an {\sc is-a} taxonomy, permitting
multiple inheritance.
\begin{figure}
\hbox{
\centerline{
\psfig{figure=figs/ijcai95/taxonomy.ps,height=1.5in}}
}
\caption{Fragment of the WordNet taxonomy.  Solid lines represent {\sc is-a}
links; dashed lines indicate that some intervening nodes were omitted to
save space. \label{fig:taxonomy}}
\end{figure}
Intuitively, one key to the similarity of two concepts is the extent
to which they share information, indicated in an {\sc is-a} taxonomy
by a highly specific concept that subsumes them both.  The
edge-counting method captures this indirectly, since if the minimal
path of {\sc is-a} links between two nodes is long, that means it is
necessary to go high in the taxonomy, to more abstract concepts, in
order to find a least upper bound.  For example, in WordNet,
\wclass{nickel} and \wclass{dime} are both subsumed by \wclass{coin},
whereas the most specific superclass that \wclass{nickel} and
\wclass{credit card} share is \wclass{medium of exchange} (see
Figure~\ref{fig:taxonomy}). In a feature-based setting
\cite<e.g.,>{tversky1977}, this would be reflected by explicit shared
features: nickels and dimes are both small, round, metallic, and so
on.  These features are captured implicitly by the taxonomy in
categorizing \wclass{nickel} and \wclass{dime} as subordinates of
\wclass{coin}.

By associating probabilities with concepts in the taxonomy, it is
possible to capture the same idea as edge-counting, but avoiding the
unreliability of edge distances.  Let the taxonomy be augmented with a
function $\Prob : \Ccal \rightarrow [0,1]$, such that for any $c \in
\Ccal$, $\Prob(c)$ is the probability of encountering an instance of
concept $c$.  This implies that $\Prob$ is monotonically nondecreasing
as one moves up the taxonomy: if $c_1 \:\isa\: c_2$, then $\Prob(c_1)
\leq \Prob(c_2)$.  Moreover, if the taxonomy has a unique top node
then its probability is 1.

Following the standard argumentation of information theory
\cite{ross1976}, the {\em information content\/} of a concept $c$ can
be quantified as negative the log likelihood, $-\log\Prob(c)$.  Notice
that quantifying information content in this way makes intuitive sense
in this setting: as probability increases, informativeness decreases;
so the more abstract a concept, the lower its information content.
Moreover, if there is a unique top concept, its information content
is~0.

This quantitative characterization of information provides a new way
to measure semantic similarity.  The more information two concepts
share, the more similar they are, and the information shared by two
concepts is indicated by the information content of the concepts that
subsume them in the taxonomy.  Formally, define
\begin{eqnarray}
\mbox{\rm sim}(c_1, c_2) & = &  \mx{c \in S(c_1,c_2)} 
				   \left[ -\log\Prob(c) \right],
\label{eq:siminfo}
\end{eqnarray}
where $S(c_1,c_2)$ is the set of concepts that subsume both $c_1$ and
$c_2$.  A class that achieves the maximum value in
Equation~\ref{eq:siminfo} will be termed a {\em most informative
subsumer}; most often there is a unique most informative subsumer,
although this need not be true in the general case.  Taking the
maximum with respect to information content is analogous to taking the
first intersection in semantic network marker-passing or the shortest
path with respect to edge distance \cite<cf.>{quillian1968,Rada89b};
a generalization from taking the maximum to taking a weighted average
is introduced in Section~\ref{sec:discussion}.

Notice that although similarity is computed by considering all upper
bounds for the two concepts, the information measure has the effect of
identifying minimal upper bounds, since no class is less informative
than its superordinates.  For example, in Figure~\ref{fig:taxonomy},
\wclass{coin}, \wclass{cash}, etc. are all members of
$S(\mbox{\wclass{nickel}},\mbox{\wclass{dime}})$, but the concept that
is structurally the minimal upper bound, \wclass{coin}, will also be
the most informative.  This can make a difference in cases of multiple
inheritance: two distinct ancestor nodes may both be minimal upper
bounds, as measured using distance in the graph, but those two nodes
might have very different values for information content.\ignore{For
example, in Figure~\ref{fig:multiple}, \wclass{metal} and
\wclass{chemical element} are not structurally distinguishable as
upper bounds of \wclass{nickel'} and \wclass{gold'}, but their
information content may in fact be quite different.} Also notice that
in {\sc is-a} taxonomies such as WordNet, where there are multiple
sub-taxonomies but no unique top node, asserting zero similarity for
concepts in separate sub-taxonomies (e.g., {\sc liberty}, {\sc aorta})
is equivalent to unifying the sub-taxonomies by creating a virtual
topmost concept.

In practice, one often needs to measure {\em word similarity\/},
rather than concept similarity.  Using $s(w)$ to represent the set of
concepts in the taxonomy that are senses of word $w$, define
\begin{eqnarray}
\mbox{\rm wsim}(w_1, w_2) & = &  
  \mx{c1,c2} \left[ \mbox{\rm sim}(c_1,c_2) \right],
\label{eq:siminfo_words}
\end{eqnarray}
where $c_1$ ranges over $s(w_1)$ and $c_2$ ranges over $s(w_2)$.  This is
consistent with Rada et al.'s \citeyear{Rada89b} treatment of ``disjunctive
concepts'' using edge-counting: they define the distance between two
disjunctive sets of concepts as the minimum path length from any element of
the first set to any element of the second.  Here, the word similarity is
judged by taking the maximal information content over all concepts of which
both words could be an instance.
\begin{figure}
\hbox{
\centerline{
%\psfig{figure=figs/ijcai95/multiple.ps,height=1.5in}}
\psfig{figure=figs/jair98/doctor.eps,width=3.5in}}
}
\caption{Another fragment of the WordNet taxonomy \label{fig:doctor}}
\end{figure}
To take an example, consider how the word similarity \mbox{wsim({\em
doctor}, {\em nurse})} would be computed, using the taxonomic
information in Figure~\ref{fig:doctor}.  (Note that only noun senses
are considered here.) By Equation~\ref{eq:siminfo_words}, we must
consider all pairs of concepts $\langle c_1, c_2 \rangle$, where $c_1
\in \{\mbox{\sc doctor1},\mbox{\sc doctor2}\}$ and $c_2 \in
\{\mbox{\sc nurse1},\mbox{\sc nurse2}\}$, and for each such pair we
must compute the semantic similarity \mbox{sim($c_1$,$c_2$)} according
to Equation~\ref{eq:siminfo}.  Table~\ref{tbl:doctor} illustrates the
computation.
\begin{table}
\begin{center}
\begin{tabular}{|llcc|} \hline
$c_1$ (description)	& $c_2$ (description)	& subsumer & sim($c_1$,$c_2$) \\
\hline\hline
{\sc doctor1} (medical)	& {\sc nurse1} (medical) 
  & {\sc health\_professional}	& 8.844 \\ \hline
{\sc doctor1} (medical)	& {\sc nurse2} (nanny) 
  & {\sc person}		& 2.005 \\ \hline
{\sc doctor2} (Ph.D.)	& {\sc nurse1} (medical) 
  & {\sc person}		& 2.005 \\ \hline
{\sc doctor2} (Ph.D.)	& {\sc nurse2} (nanny) 
  & {\sc person}		& 2.005 \\ \hline
\end{tabular}
\end{center}
\caption{Computation of similarity for {\em doctor\/} and {\em nurse}
	 \label{tbl:doctor}}
\end{table}

As the table shows, when all the senses for {\em doctor\/} are
considered against all the senses for {\em nurse}, the maximum value
is~8.844, via {\sc health\_professional} as a most informative
subsumer; this is, therefore, the value of word similarity for {\em
doctor\/} and {\em nurse}.\footnote{The taxonomy in
Figure~\ref{fig:doctor} is a fragment of WordNet version 1.6, showing
real quantitative information computed using the method described
below.  The ``nanny'' sense of {\em nurse\/} (nursemaid, a woman who
is the custodian of children) is primarily a British usage.  The
example omits two other senses of {\em doctor\/} in WordNet: a
theologian in the Roman Catholic Church, and a game played by
children.  WordNet does not use node labels like {\sc doctor1}, but I
have created such labels here for the sake of readability.}

\ignore{For example, Figure~\ref{fig:multiple} illustrates how the similarity
of words {\em nickel\/} and {\em gold\/} would be computed: the
information content would be computed for all classes subsuming any
pair in the cross product of \{\wclass{nickel},\wclass{nickel'}\} and
\{\wclass{gold},\wclass{gold'}\}, and the information content of the
most informative subsumer would be used to quantify the similarity of
the two words.}


\section{Evaluation}
\label{sec:evaluation}

This section describes a simple, direct method for evaluating semantic
similarity, using human judgments as the basis for comparison.

\subsection{Implementation}

The work reported here used WordNet's taxonomy of concepts represented
by nouns (and compound nominals) in English.\footnote{{\em Concept} as
used here refers to what Miller et al. \citeyear{miller1990} call a
{\em synset}, essentially a node in the taxonomy.  The experiment
reported in this section used the noun taxonomy from WordNet version
1.4, which has approximately 50,000 nodes.} Frequencies of concepts in
the taxonomy were estimated using noun frequencies from the Brown
Corpus of American English \cite{francis1982}, a large (1,000,000
word) collection of text across genres ranging from news articles to
science fiction.  Each noun that occurred in the corpus was counted as
an occurrence of each taxonomic class containing it.\footnote{Plural
nouns counted as instances of their singular forms.} For example, in
Figure~\ref{fig:taxonomy}, an occurrence of the noun {\em dime} would
be counted toward the frequency of \wclass{dime}, \wclass{coin},
\wclass{cash}, and so forth.  Formally,
\begin{eqnarray}
\mbox{\rm freq}(c) & = & \sum_{n \in \mbox{words}(c)} \mbox{\rm count}(n),
\label{eq:estimation}
\end{eqnarray}
where $\mbox{words}(c)$ is the set of words subsumed by concept $c$.  Concept
probabilities were computed simply as relative frequency:
\begin{eqnarray}
\hat{\Prob}(c) & = & \frac{\mbox{\rm freq}(c)}{N},
\end{eqnarray}
where $N$ was the total number of nouns observed (excluding those not
subsumed by any WordNet class, of course).  Naturally the frequency
estimates in Equation~\ref{eq:estimation} would be improved by taking
into account the intended sense of each noun in the corpus --- for
example, an instance of {\em crane\/} can be a bird or a machine, but
not both.  Sense-tagged corpora are generally not available, however,
and so the frequency estimates are done using this weaker but more
generally applicable technique.

It should be noted that the present method of associating
probabilities with concepts in a taxonomy is not based on the notion
of a single random variable ranging over all concepts --- were that
the case, the ``credit'' for each noun occurrence would be distributed
over all concepts for the noun, and the counts normalized across the
entire taxonomy to sum to~1.  \cite<That is the approach taken
in>[also see Resnik, 1998b \ignore{resnik:wordnet_book} for
discussion.]{resnik:dissertation}\nocite{resnik:wordnet_book} In
assigning taxonomic probabilities for purposes of measuring semantic
similarity, the present model associates a separate, binomially
distributed random variable with each concept.\footnote{This is
similar in spirit to the way probabilities are used in a Bayesian
network.}  That is, from the perspective of any given concept $c$, an
observed noun either is or is not an instance of that concept, with
probabilities $\Prob(c)$ and $1-\Prob(c)$, respectively.  Unlike a
model in which there is a single multinomial variable ranging over the
entire set of concepts, this formulation assigns probability~1 to the
top concept of the taxonomy, leading to the desirable consequence that
its information content is zero.

\subsection{Task}

Although there is no standard way to evaluate computational measures
of semantic similarity, one reasonable way to judge would seem to be
agreement with human similarity ratings.  This can be assessed by
using a computational similarity measure to rate the similarity of a
set of word pairs, and looking at how well its ratings correlate with
human ratings of the same pairs.

An experiment by Miller and Charles \citeyear{miller1991:similarity}
provided appropriate human subject data for the task.  In their study,
38 undergraduate subjects were given 30 pairs of nouns that were
chosen to cover high, intermediate, and low levels of similarity
\cite<as determined using a previous study,>{rubenstein1965}, and
those subjects were asked to rate ``similarity of meaning'' for each
pair on a scale from 0~(no similarity) to 4~(perfect synonymy).  The
average rating for each pair thus represents a good estimate of how
similar the two words are, according to human judgments.\footnote{An
anonymous reviewer points out that human judgments on this task may be
influenced by prototypicality, e.g., the pair {\em bird}/{\em robin}
would likely yield higher ratings than {\em bird}/{\em crane}.  Issues
of this kind are briefly touched on in Section~\ref{sec:related}, but
for the most part they are ignored here since prototypicality, like
topical relatedness, is not captured in most {\sc is-a} taxonomies.}

In order to get a baseline for comparison, I replicated Miller and
Charles's experiment, giving ten subjects the same 30 noun pairs.  The
subjects were all computer science graduate students or postdoctoral
researchers at the University of Pennsylvania, and the instructions
were exactly the same as used by Miller and Charles, the main
difference being that in this replication the subjects completed the
questionnaire by electronic mail (though they were instructed to
complete the whole task in a single uninterrupted sitting).  Five
subjects received the list of word pairs in a random order, and the
other five received the list in the reverse order.  The correlation
between the Miller and Charles mean ratings and the mean ratings in my
replication was .96, quite close to the .97 correlation that Miller
and Charles obtained between their results and the ratings determined
by the earlier study.

For each subject in my replication, I computed how well his or her
ratings correlated with the Miller and Charles ratings.  The average
correlation over the 10 subjects was $r = 0.88$, with a standard
deviation of 0.08.\footnote{Inter-subject correlation in the
replication, estimated using leaving-one-out resampling
\cite{weiss1991}, was $r = .90, {\rm stdev} = 0.07$.} This value
represents an upper bound on what one should expect from a
computational attempt to perform the same task.

For purposes of evaluation, three computational similarity measures
were used.  The first is the similarity measurement using information
content proposed in the previous section.  The second is a variant on
the edge-counting method, converting it from distance to similarity by
subtracting the path length from the maximum possible path length:
\begin{equation}
\mbox{\rm wsim}_{\mbox{edge}}(w_1, w_2) = \\
(2 \times \mbox{\sc max}) - \left[ \mn{c_1,c_2}\mbox{len}(c_1,c_2) \right]
 \label{eq:simedge}
\end{equation}
where $c_1$ ranges over $s(w_1)$, $c_2$ ranges over $s(w_2)$, {\sc
max} is the maximum depth of the taxonomy, and $\mbox{len}(c_1,c_2)$
is the length of the shortest path from $c_1$ to $c_2$ . (Recall that
$s(w)$ denotes the set of concepts in the taxonomy that represent
senses of word $w$.)  If all senses of $w_1$ and $w_2$ are in separate
sub-taxonomies of WordNet their similarity is taken to be zero.  Note
that because correlation is used as the evaluation metric, the
conversion from a distance to a similarity can be viewed as an
expository convenience, and does not affect the results: although the
sign of the correlation coefficient changes from positive to negative,
its magnitude turns out to be just the same regardless of whether or
not the minimum path length is subtracted from $(2 \times \mbox{\sc
max})$.

The third point of comparison is a measure that simply uses the
probability of a concept, rather than the information content, to
define semantic similarity of concepts
\begin{eqnarray}
\mbox{\rm sim}_{\Prob(c)}(c_1, c_2) & = &  \mx{c \in S(c_1,c_2)} 
				   \left[ 1-\Prob(c) \right] 
\end{eqnarray}
and the corresponding measure of word similarity:
\begin{eqnarray}
\mbox{\rm wsim}_{\Prob(c)}(w_1, w_2) & = &  
			\mx{c_1,c_2}  
			  \left[ \mbox{\rm sim}_{\Prob(c)}(c_1,c_2) \right],
  \label{eq:probsim}
\end{eqnarray}
where $c_1$ ranges over $s(w_1)$ and $c_2$ ranges over $s(w_2)$ in
Equation~\ref{eq:probsim}.  The probability-based similarity score is
included in order to assess the extent to which similarity judgments
might be sensitive to frequency {\em per se\/} rather than information
content.  Again, the difference between maximizing $1 - \Prob(c)$ and
minimizing $\Prob(c)$ turns out not to affect the magnitude of the
correlation.  It simply ensures that the value can be interpreted as a
similarity value, with high values indicating similar words.


\subsection{Results}