Estimating Point-of-View-based Similarity
using POV Reinforcement and Similarity Propagation

Kenji Nagamatsu
Hidehiko Tanaka
The University of Tokyo

Abstract

fnaga,tanakag@mtl.t.u-tokyo.ac.jp

This paper proposes a similarity measure which takes account of pointof-views (abbreviated to POV, hereafter) in the calculation of similarity
values. So far many researches on similarity measures have been performed but none takes account of POVs. The similarity measure proposed in this paper is based on co-occurrence probabilities of words andthis makes it possible to obtain preferable precision even if POVs are notgiven. This method consists of two parts of processes, POV reinforcement and similarity propagation. First, the POV reinforcement process,which a ects the similarity between words, modi es the weights of links
according to the relatedness between the link and the POV word. Second, the similarity propagation process propagates the weights of links
and de nes a similarity value for word pairs which do not actually cooccur in the corpus. Using those two processes this method becomescapable both to take POVs into consideration and to cope with thesparseness of corpora to some degree. This paper, however, focuses on
the POV reinforcement and evaluates the e ectiveness of the method.

1 Introduction
Rapid growth of computer networks has increased the number of machine-readable
texts and also made it possible for us to use various search engines to get desired
documents. They are, however, keyword-based and strict. Even if some documents are related to a user's interest, he or she cannot obtain them as long as
they do not contain the keywords given in advance. Otherwise he or she will
be handed too many documents which contain just the keywords but are notnecessarily related to his or her interest.
To solve these problems, it is necessary to take account of similarity between
words or concepts and to make use of the measure in search processing. However,
because there are many similar words in a text, employing a similarity measurealone only will expand the range of relatedness and produce more and more results.
When considering meanings of words, we, human beings, do not consider thewhole meanings at a time, rather some interesting aspects of their concepts justthe same as we look at a landscape from some point-of-view. Hence in similarityof words it is required to take account of their POVs. This makes it possible both
to expand the range of matching in some situations and to restrict the range inothers. Expectation is that employing valid POVs has both the expansion and therestriction be suitable and search processing produces more appropriate results.
This paper proposes a similarity measure between words which measure takes
account of the e ect of POVs. So far many researches on concept (or word) similarity have been performed but none handles POVs in their similarity measures.
The proposed method utilizes co-occurrence probability-based similarity as a basis

and extends this fundamental measure by weighting the values according to therelevance between input words and POV words. This fundamental measure andits evaluation with some traditional similarity measures are described in 2. The
main part of the method, which handles the e ect by POVs, consists of two processes, POV reinforcement and similarity propagation. The explanation for theseprocesses and some related issues are presented in 3 and 3.2. Finally 4 shows theresult of some experiments, which indicates the e ectiveness of this method, and5 discusses the problems of the method as well as its advantages.

2 Fundamental Similarity Measures
This section gives an overview of similarity measures (2.1) and evaluates the abilityof some fundamental measures with a large amount of word pairs (2.2 and 2.3).

2.1 Classi cation of Similarity Measures
Similarity of words or concepts is a fundamental measure in natural language
processing because it can be used in various processing. For example, in disambiguation of word senses it can help to detect appropriate word senses by selecting
most similar word senses to the senses of context words. In sentence production
similarity measures can also help to keep coherence of word sequences. The factthat most researches on similarity measures have been performed with relation to
the word sense disambiguation indicates the signi cance of similarity measures.
The similarity measures researched so far are classi ed as follows.
1. Similarity based on the structure of thesauruses or taxonomies(Agirre 1995)(Resnik 1995)
Because thesauruses or taxonomies contain even infrequently used words (orconcepts), the similarity measures of this type can de ne similarity values
to most word pairs. The range of the word pairs they can handle is, thus,
broad. In contrast, these measures are also considered as class-based andthe degree of similarity is rather loose (they tend to judge the words orconcepts in a same class as similar).
2. Similarity based on the statistical information extracted from corpora(Dagan 1994)(Iwayama 1994)(Yang 1994)(Karov 1996)
The range of the word pairs they can handle depends on the size of corpora
used to extract the statistical information. In most cases, however, theproblem of data sparseness arises. The main concern in these measures is
how to estimate the values of unseen word pairs (Dagan 1994).
3. Similarity based on network structures (Kozima 1993)(Niwa 1994)
Similarity values are de ned on links in the network and a total value in apath, maybe processed somewhat, is interpreted as a similarity value.
4. Feature-based similarity
In these measures each word (or concept) has a set of features which aresemantically related to the word. Those features may be actual semantic features or co-occurrence words. The number of shared features is interpreted
as a similarity value.

2.2 Selectivity of Similarity Measures
Before considering the similarity measure based on POV, it is necessary to clarify
the ability of some fundamental similarity measures described in the previous
section. With the result this evaluation the most promising measure is adopted
as the base of the proposed method.
In many researches the evaluation of similarity measures depends on humanbeings' judgment. In this case the measures are estimated by the score subjects
judged for output values of the measures or by the correlation between two judgments of subjects and similarity measures. Scoring similarity of word pairs byhand, however, costs a lot. In contrast to this approach this paper adopt anothertype of evaluation employing coverage and selectivity of similarity measures.
When some threshold of a similarity measure is determined, the measure canjudge each pair of words as similar or as not similar. At this point the coverageof a word pair set by the similarity measure is de ned as the proportion of thenumber of word pairs judged as similar to the size of the set (total number ofword pairs in the set).
Employing this coverage ratio, selectivity of a similarity measure is describedas follows. First, two groups of word pairs are prepared. One group, synonym
set, contains pairs of synonyms which are similar in human beings' judgment.
The other group, non-synonym set, contains pairs of non-synonyms which are notsimilar to each other. In practice, however, non-synonym set is approximatedwith word pairs randomly selected from a dictionary. When some threshold of asimilarity measure is determined, two coverage ratios for those two sets can becomputed and the relationship between the two coverage ratios is plotted withthe threshold being a parameter (see Figure 1 and 2 as examples). This plotted
relationship is de ned as the selectivity of the similarity measure. In the graphs,
the lower a data sequence is located, the higher the selectivity of the similarity
measure becomes.

2.3 Evaluation of Fundamental Similarity Measures
In this section some fundamental similarity measures are evaluated employing theselectivity. Evaluated measures are three, depth, link#, and cooccur. These are
not the latest measures but are commonly used and o er bases of more advanced
measures.
depth represents the similarity measure which uses the depth of the most
speci c common ancestors(MSCA). Given two concepts, MSCA are the concepts
which subsume both the concepts and are located at the deepest position in ataxonomic structure. Formally,

Simdepth (w1 ; w2) =

max

( )

d(MSCA(c1 ; c2))
( 2 ) (d(c1 ) + d(c2 ))=2

8c1 2C w1 ;8c 2 2C w

(1)

, where C (w) denotes the concept set of a word w and d(c) denotes the depth of
a concept c in a taxonomy.
link# represents the traditional edge counting method, which de ne the similarity value of a word pair (w1; w2 ) by the length of the shortest path from one

coverage of non-synonym pairs
100.00%coverage of non-synonym pairs
100.00%90.00%
80.00%
depth
link#
70.00%
cooccur
60.00%

depth
link#cooccur

50.00%

10.00%

40.00%
30.00%

1.00%

0.10%
20%

20.00%

30%

40%

50%
60%
70%
coverage of synonym pairs

80%

90%

10.00%
80%

100%

Figure 1: Selectivity of fundamental
similarity measures

82%

84%

86%

88%
90%
92%
94%
coverage of synonym pairs

96%

98%

100%

Figure 2: Magni ed version of Figure 1of the concepts of w1 to one of the concepts of w2 . Formally,

Simlink# (w1 ; w2) =

max

( )

1

(2)

( ) l(c1 ; c2 ) + 1

8c1 2C w1 ;8c2 2C w2, where l(c1 ; c2 ) denotes the shortest path length between concepts c1 and c2 in ataxonomy.
cooccur represents the similarity measure which uses co-occurrence probability between words. Formally,

Simcooccur(w1 ; w2 ) =X( )P r(wjw1 ) + P r(wjw2 )( )8w 2C o w1 \C o w2(3)2

, where Co(w) denotes the co-occurring words with a word w and P r(w jw ) denotes the co-occurrence probability of w conditioned by w. This measure has aname \cooccur" but is a hybrid type of statistics-based and feature-based similarity.
Figure 1 and 2 show the result of the evaluation employing the selectivity.
In this evaluation the synonym set contains 10,297 synonym pairs which was
extracted from the IPAL dictionaries (IPA 1993) , which have a \synonym words"
eld in the word records.
Taxonomy-based similarity measures (depth and link#) use as a taxonomy
the EDR concept dictionary (EDR 1995). The non-synonym set used for thesemeasures are approximated with word pairs randomly selected from the EDR
word dictionary (EDR 1995) , which contains the word entries corresponding to
the concepts in the EDR concept dictionary.
For the co-occurrence-based similarity measure (cooccur), co-occurrence data
were extracted from the corpus CD-Mainichi shimbun (newspaper) DB '94, whichcontains all the articles from this newspaper in 1994. This co-occurrence data contains the co-occurring words and their frequencies for each content word (nouns,
verb, adjectives, and adverbs) in the corpus. The number of the sentences used
for the extraction is 1,019,997(74,793 articles).
Figure 1 and 2 indicates clearly that in taxonomy-based similarity measures(depth and link#) the edge counting method is superior to the depth measure.
00Moreover, the corpus-based similarity, which uses co-occurrence probability extracted from a corpus, is superior to the taxonomy-based measures.
(Resnik 1995) have extended the depth-based similarity measure by employing
information content of concept classes, which was calculated from word frequencies
in a corpus, and concluded that the method was superior to the edge counting
method. On the other hand, the edge counting method has been extended to a
network-based similarity model described earlier. In this way the combination
with statistical information extracted from corpora produces preferable results.
The POV-based similarity method presented in the next section also adopt theco-occurrence probability-based similarity as a basis.

3 Similarity of Words based on POVThis section describes the similarity measure proposed in this paper, which cantake account of the e ect of point-of-views. This similarity measure consists of
two phases, POV reinforcement and similarity propagation. However, this paper
focuses on the POV reinforcement and omits the explanation of the similarity
propagation process. Before describing the POV reinforcement process ( 3.2) asimilarity network with POV, on which the similarity measure is de ned, and themethod of calculating similarity values are explained.

3.1 Similarity Network with POV
As described in 1, human beings' judgment of similarity takes POVs into consideration. Two di erent words may not be similar in general, rather they are
similar under some aspects or POVs. Thus we consider similarity of words as a
triplet Sim(w1 ; w2; w ), where w1 and w2 are called node words (similarity values
are de ned over them) and w is called a POV word.
From this point of view the co-occurrence data used in 2.3 can be also used as
the triplets because the co-occurring words of a node word are thought as POVsof the node. But if the co-occurring words are used as POV words directly, thesparseness problem arises because the co-occurring words don't necessarily containthe POV word given to the calculation. The POV reinforcement process, therefore, employs another type of co-occurrence data. The details will be describedlater in 3.2.
Even if the co-occurrence data cannot be used for the handling of POVs, thesedata can be used for the calculation of basic similarity values. As described in 2.3
the measure utilizing these data has higher selectivity than the other taxonomybased measures. Therefore, as a fundamental structure the similarity measurede ned by the equation (3) is adopted. Sim(w1; w2 ; w ) is, thus, formulated asfollows.
P r(wjw1 ; w ) + P r(w jw2 ; w )Sim(w1 ; w2 ; w ) =(4)2( ) ( )
p

p

p

p

X

p

8w 2C o w1 \C o w2p

, where P r(wjw ; w ) denotes the co-occurrence probability of w conditioned by
w1 which probability is reinforced by a POV word w . This reinforcement is
described in the next section.
0pppov 1

node word
w1

co-occurring words
w1

pov 1

pov

pov2 . . .

w2

pov 1

pov2

pov’ . . .

node word w2

pov2

pov 3
pov word wp

Figure 3: Similarity network with POV and POV reinforcement
The similarity network with POV is constructed as follows. First, the nodesof the network are the words which appears in the co-occurrence data describedin 2.3. Second, every pair of nodes is connected by links which are correspondto the shared co-occurring words (Co(w1) \ Co(w2 )) respectively and each link isgiven a pair of the co-occurrence probability, one for w1 and the other for w2 (seeFigure 3).

3.2 POV Reinforcement
POV reinforcement is the most important process in this similarity measure andresponsible for varying the values of links according to the relatedness to a POV
word.
As described above, the co-occurrence data used in equation (4) cannot be
employed to weight values of links according to POVs. It is because normal
co-occurrence data are collected ignoring the relationship between co-occurringwords. As a result a pair of words shares various POVs in the co-occurrence data.
Therefore, another type of co-occurrence data, called POV co-occurrence data, isrequired.
To extract POV co-occurrence data from a corpus, we make two assumptions.
1) Two words are similar when they occur as the same case role of the same word
(verb, etc.). 2) The POV of this similarity is the verb, etc. itself. For example,
in two sentences 1) \Tom walks." and 2) \A dog walks.", both `Tom' and `dog'
have occurred as agent of the verb `walk'. `Tom' and `dog' are, thus, considered
to be similar under the POV word `walk'.
Following the assumptions, POV co-occurrence data in the form co(w ; w ; r )are extracted from a tagged corpus. This gives co-occurrence frequency that word
w occurs as the case role r of the word w . Employing these data the POV
reinforcement is formulated as follows.
pi

P r(w jw; w ) =p( p ) f (w j w )) 0 1)f (w jw) + P
mic w ;w

(

k

p

k

0

i

( p

mic w ;w

0

0

0

0

( ) f (xjw)(5)

8x2C o w, where f (w jw) denotes the normal co-occurrence frequency of w conditioned
by w and mic(w ; w ) is the mutual information content which is calculated with
0

0

p

0

POV co-occurrence data. is a constant parameter which controls how the relatedness between two POVs w and w a ect the probability of the link. Thismutual information content mic(w ; w ) is approximated as follows with POV
co-occurrence data co(w ; w ; r ).
0

p

0

p

p

i

MIC (w; w ) = log
0k

P r(w; w )P r (w )P r (w )0P co(w; w ; r ) mic(w; w ) = log P co(w; w ; r ) P co(w ; w ; r )
0

0

k

0

i;j

i

j

i;j

k

0

i

(6)

j

Mutual information content(MIC) indicates the degree of co-occurrence. If

MIC (w1 ; w2)  0, the relationship between w1 and w2 is quite meaningful. If
MIC (w1 ; w2)  0, w1 has nothing to do with w2 . And if MIC (w1 ; w2)  0,w1 and w2 occur exclusively. This behavior of MIC is useful for weighting links

according to the relatedness between POVs and links.
When no POV word is given, the equations (4) and (5) become the same as(3). This guarantees that this similarity measure has at least the same ability
shown in the Figure 1 and 2 (cooccur).

4 Experiments
For these experiments POV co-occurrence data were extracted from the EDR
corpus (EDR 1995). This corpus contains 207,802 sentences and all the sentences
are already parsed into semantic frames. From these frames 1,254,851 POV cooccurrence data co are obtained. The normal co-occurrence data are the sameas the data described in 2.3, which were extracted from CD-Mainichi shimbun(newspaper) DB '94.

4.1 Selectivity of the Measure with the POV reinforcement
This experiment evaluates the e ectiveness of the POV reinforcement process.
Because the case where POV words are given explicitly is dicult to control theconditions of the experiment, this experiment evaluated the case explicit POV
words are not given. As described earlier, even if no explicit POV words are
speci ed, the words in a input pair are used as implicit POV words.
Figure 4 and 5 shows the result obtained in the same way as 2.3. In the gures
the multiple versions of the POV-based similarity measure are plotted at = 1:2,
= 1:5 and = 2:0. is the parameter of equation (5).
Table 1 contains coverage of non-synonym pairs for some typical coverage ofsynonym pairs.

4.2 Comparison with Human Judgment
The evaluation by the selectivity of the similarity measures is comprehensive but
only suggests an overall tendency. Therefore, another experiment has been performed. This experiment compares the similarity values computed by the similarity measures with the scores given by subjects.

coverage of non-synonym pairs
100.00%depth
link#cooccur
pov0
pov(1.2)
pov(1.5)
pov(2.0)
10.00%

coverage of non-synonym pairs
100.00%90.00%
depth
80.00%
link#
cooccur
70.00%
pov0
pov(1.2)
60.00%
pov(1.5)
50.00%
pov(2.0)
40.00%
30.00%

1.00%

0.10%
20%

20.00%

30%

40%

50%

60%

70%

80%

90%

100%

10.00%
80%

82%

84%

coverage of synonym pairs

88%

90%

92%

94%

96%

98%

100%

coverage of synonym pairs

Figure 4: Selectivity of the proposed
similarity measure
coverage ofsynonym pairs
80%
90%
95%

86%

POV
= 1:2
4.4%
13.4%
28.8%

Figure 5: Magni ed version of Figure 4

POV
= 1:5
5.6%
11.9%
26.6%

POV
= 2:0 cooccur link#
5.1%
5.2% 10.9%
11.1%
16.8% 24.0%
26.0%
33.0% 33.9%

Table 1: Coverage of non-synonym pairs for typical coverage of synonym pairs
The number of subjects was 14 and they were all members of our laboratory.
They were asked to rate the similarity of each pair of words from 1 (not similar)
to 5 (perfect synonymy). The number of word pairs was 50, which were randomly
selected from synonyms in the IPAL dictionaries.
Table 2 shows the result and contains the correlation factors between thevalues of the similarity measures and the scores given by the subjects.

5 Discussion
5.1 E ectiveness of the POV reinforcement
The result of this experiment (see Figure 5) indicates that by employing the POV
reinforcement the selectivity of the measure becomes higher than the original
cooccur measure (note again that the lower a sequence is located, the higher theselectivity of the measure becomes). This raise originates in the e ect of POVs
= 1:2
0.2051= 2:0 cooccur link# depth
0.19090.1987 0.0822 0.1277

Table 2: Correlation between the similarity measures and the judgment by subjects

alone. Although the measure with the POV reinforcement becomes inferior to theoriginal one in the area where coverage of synonym pairs is small ( 50%), thisis not a problem because similarity measures are used normally at high synonym
coverage ( 80%  90%).
The e ect of the parameter is quite interesting. In proportion as increases
the selectivity also rises in the neighborhood of 90%  92%. However, in the area
below 80% the selectivity becomes declined conversely. This is also observed moreclearly from Table 1. It is considered that there is a optimum value of , however
it is not yet found.

5.2 Comparison with Human Judgment
Table 2 indicates that judgment by the co-occurrence-based similarity measures
resembles that of human beings more than the taxonomy-based similarity measures. All the factors are, however, very small. (Resnik 1995) have presented theresult of a similar experiment to this. There the correlation factor between thehuman judgment and the values of a edge-counting method is 0.6645. In comparison with the result in Table 2, because word pairs used in this experimentwere selected from synonym pairs, it is considered that the di erence among thesimilarity values became small.
Moreover, no e ect of the POV reinforcement on these correlation factors is
recognized. Considering its e ect on the selectivity this is considered to be causedby the process of this experiment.
In either case it is required to perform another experiment thoroughly.

6 Conclusion
This paper has presented the similarity measure which takes account of point-ofviews, focusing on the POV reinforcement process. Although this method consistsof two phases, the POV reinforcement and the similarity propagation, the POV
reinforcement process is the main part, which weights the co-occurrence probabilities of links according to POV words. The result of the evaluation suggeststhat the POV reinforcement have a good e ect on the similarity measure. On
the other, however, the experiment of comparison with human judgment did not
produce satisfactory result.
As a future work, the thorough comparison with human judgment and theevaluation of the similarity propagation process are required. In addition, it isnecessary to evaluate the behavior of the results when this similarity measure isused in practical processing, for example word sense disambiguation.

References
Eneko Agirre and German Rigau. 1995. A Proposal for Word Sense Disambiguation using Conceptual Distance. In Proceedings of 1st International Conference
on Recent Advances in Natural Language Processing.

Ido Dagan and Fernando Pereira. 1994. Similarity-Based Estimation of Word
Cooccurrence Probabilities. In Proceedings of ACL-94.
Japan Electronic Dictionary Research Institute Ltd. 1995. EDR Electronic Dictionary Technical Guide.
Japan Information-technology Promotion Agency. IPAL Japanese Dictionary for
Computer. Technical report.
Yael Karov and Shimon Edelman. 1996. Learning similarity-based word sense
disambiguation. In Proceedings of the Fourth Workshop on Very Large Corpora.
Hideki Kozima and Teiji Furugori. 1993. Similarity between Words Computedby Spreading Activation on an English Dictionary. In Proceedings of the 6th Conference of the European Chapter of the Association for Computational Linguistics(EACL-93), pp. 232{239. ACL.
Yoshiki Niwa and Yoshihiko Nitta. 1994. CO-OCCURRENCE VECTORS FROMCORPORA VS. DISTANCE VECTORS FROM DICTIONARIES. In Proc. COLING 94, Vol. 1, pp. 304{309.
Philip Resnik. 1995. Using Information Content to Evaluate Semantic Similarity
in a Taxonomy. In Proceedings of the 14th International Joint Conference on Arti cial Intelligence, Vol. 1, pp. 448{453.
Yiming Yang and Christopher G. Chute. 1994. An Example-Based Mapping
Method for Text Categorization and Retrieval. ACM Transactions on Information
Systems, Vol. 12, No. 3, pp. 252{277.