EVALUATING RERANKING METHODS USING WIKIPEDIAFEATURES
Koji Kurakado
Graduate School of Information Science and Electrical Engineering, Kyushu University, Fukuoka City, Fukuoka, Japan

Tetsuya Oishi† , Ryuzo Hasegawa‡, Hiroshi Fujita‡ , Miyuki Koshimura‡† Research Institute for Information Technology, Kyushu University, Fukuoka, Japan‡ Faculty of Information Science and Electrical Engineering, Kyushu University, Fukuoka, Japan

Keywords:

Wikipedia, Reranking, Link analysis.

Abstract:

Many people these days access a vast document on the Web very often with the help of search engines such as
Google. However, even if we use the search engine, it is often the case that we cannot find desired information
easily. In this paper, we extract related words for the search query by analyzing link information and category
structure. we aim to assist the user in retrieving web pages by reranking search results.

1

INTRODUCTION

In recent years, many people got possible to access
Web very easily thanks to the vast spread of internet
as well as the availability of convenient search engines. For instance, Google1,Yahoo2 are commonly
used. Given a few keywords, these systems retrieve
such Web pages that users want to see from among
the huge databases residing on the internet. Google,
in particular, successfully presents us the most suitable pages on the first page of the retrieval results byapplying the PageRank algorithm (Page et al., 1998)
which evaluates relevance of pages based on pagelinks.
Nevertheless, since the Web sources are so enormous and constantly increasing, it is often the casethat we are not satisfied with the results given by
them. To solve the problem, we propose reranking
methods based on Wikipedia. Wikipedia attracts attention on the field of NLP and Data-Mining, becauseof its impressive characteristics.
We implement a reranking system that extracts related words from a given search query. The system
uses Wikipedia’s link information and category structures.
Wikipedia is a Wiki-based huge Web encyclopedia. As a corpus for knowledge extraction, Wikipedia
1 http://www.Google.co.jp/
2 http://www.Yahoo.co.jp/376

has several useful features. Thus, there have been various Wikipedia studies.
Semantic relatedness measurement is one of
the most major Wikipedia studies. Strube andPonzetto (Ponzetto and Strube, 2006) were the firstto compute measures of semantic relatedness using
Wikipedia. Their approach uses the category hierarchy of Wikipedia. Gabrilovich and Markovitch(Gabrilovich and Markovitch, 2007) proposed the Explicit Semantic Analysis (ESA) method. ESA represents the meaning of texts in a high-dimensional
space of concepts derived from Wikipedia page. The
semantic relatedness between two words is computed by the cosine similarity between the two vectors. They achieve the most accurate results using
the gWordSimilarity-353 test collectionh (Finkelstein
et al., 2002). Witten and Milne (Witten and Milne,2008) proposed a new method based on link cooccurrence. Although the accuracy of this approachis a little worse than ESA, it requires far less data
and resources. Chernov et al. (Chernov et al., 2006)
extracted a category set by using links that direct toor refer to pages included in categories. According
to their results, inlinks have superior performance incomparison to outlinks.
Researches that try to extract useful knowledge
from Wikipedia are called ”Wikipedia Mining” by
Japanese researchers. Nakayama et al. (Nakayama
et al., 2007) proposed a method, named pfibf, to com-

Kurakado K., Oishi T., Hasegawa R., Fujita H. and Koshimura M..
EVALUATING RERANKING METHODS USING WIKIPEDIA FEATURES.
DOI: 10.5220/0003183003760381
In Proceedings of the 3rd International Conference on Agents and Artificial Intelligence (ICAART-2011), pages 376-381
ISBN: 978-989-8425-40-9
Copyright c 2011 SCITEPRESS (Science and Technology Publications, Lda.)

EVALUATING RERANKING METHODS USING WIKIPEDIA FEATURES

pute related words by analyzing the link structure of
Wikipedia pages. They construct a huge scale association thesaurus. Ito et al. (Ito et al., 2008) proposed
the method that constructs an association thesaurus,
too. Their approach computes semantic relatedness
by using link co-occurrence. They mention that themethod is more scalable than pfibf in spite of theirhigh accuracy close to that of pfibf. The method issimilar to Milne’s in that they use co-occurrence. Although the accuracy of this method is a little worse
than Milne’s, we consider the comparison should bemade in the same environment. So, we cannot saythat one is better than the other.
Nakayama et al. (Nakatani et al., 2009) proposed an evaluation method of search results by analyzing the link information and category structure of
Wikipedia. They extract a category domain of queryand evaluate search results by using terms includedin the domain. Hori et al. (Hori et al., 2010) use
Wikipedia as a source for query expansion.

2

RERANKING WEB SITESIn this section, we describe our reranking methods
based on Wikipedia. We calculate the evaluation
value for each site to which the search engine returns.
Then we rerank the search result in descending orderaccording to the evaluation value.
We select four features from Wikipedia for reranking: inlink, outlink, link co-occurrence, category.
Here we propose a web page evaluation method thatuses each of the above features.
An inlink of a Wikipedia page is a link pointing tothat particular page. An outlink of a Wikipedia pageis a link from that particular page to other page. For
example, If page A contains a link directing to page
B, A has an outlink to B, and B has an inlink from A.
In the following, we first show an approach that
expands the category a search query belongs to. We
consider not only the categories a query belongs to but
also those related to the original categories as a category set for the query. Second, we explain the web
page evaluation model that uses each of the features.

Nakayama et al. consider that they cannot getenough information from the category that the query
originally belongs to. So, they regard the categories
that contain a lot of inlinks to the query as those thequery belongs to.
Suppose that c is a Wikipedia category and size(c)is the total number of pages belonging to c. In addition, the number of pages in c from which the query
has inlinks is expressed as in(c). CScorein (c) is defined as follows:in(c)CScorein(c) =(1)size(c)We also use the technique that expands the category a query belongs to. Moreover, we propose themethods that uses outlink, link co-occurrence, or acategory structure.
Expanding Categories based on Outlink
The method using outlink is very simple. We regard the categories that contain a lot of outlinks to thequery as those the query belongs to. Thus, the score
CScoreout (c) is calculated as follows:
CScoreout (c) = out(c)(2)

where out(c) is the number of pages in c to which thequery has outlinks.
Expanding Categories based on Link
Co-occurrence
Thinking simply, link co-occurrence means that link
A and link B appear in the same page. However, twolinks co-occur if they appear in a window of K sentences (window K in short).
Meanwhile, Wikipedia has the hierarchical paragraph from level2 to level4. For example, theWikipedia page of “Computer” has level2 paragraph“Function”. And level3 paragraphs “Control unit”
and “Memory” belong to “Function”.
Thus, we proposed three methods as follows:
1. Two links co-occur if they appear in the samepage.
2. Two links co-occur if they appear in a window K.

2.1 Expanding Categories to which a
Query Belongs

3. Two links co-occur if they appear in the same
paragraph whose level is highest and that contains
more sentences than a window K.

A Wikipedia page belongs to one or more categories.
In addition, unlike a thesaurus such as WordNet, thecategory structure of Wikipedia is not just hierarchical. It can be thought of as consisting of overlapping
trees.

Now, we show an example of the third method.
Suppose that the size K of a window is 10 , the pageof “Computer” contains 100 sentences , paragraph“Function” contains 15 sentences, paragraph “Memory” contains 5 sentences and that there is an inlink to“DRAM” in paragraph “Memory”.

377

ICAART 2011 - 3rd International Conference on Agents and Artificial IntelligenceFirst, we look at paragraph “Memory” with thehighest level. Then, since the number of sentencesof paragraph “Memory” is less than that of a window
K, we look at paragraph “Function”, whose level is
one higher than “Memory”. Since the number of sentences of “Function” is larger than that of a window
K, the links in “Function” co-occur with “DRAM”.
The score CScoreco (c) is calculated as follows:
CScoreco (c) =co(c)size(c)(3)where co(c) is the number of pages in c that co-occur
with the target page of a query.
Expanding Categories based on Category TreeOn the category tree of Wikipedia, the categories ina near position have high relevance each other. Thus,
we calculate the score CScorecat (c) as follows:
CScorecat (c) =12length(c)(4)

where length(c) is the number of paths from c to thecategory a target page of query belongs to. We calculate length(c) only about the categories cq the query
belongs to, and parent categories of cq , and children
categories of cq , and the categories that have common
parents with cq .

2.2 Web Site Evaluation based on
Wikipedia Features
We evaluate web sites using the entries of Wikipedia
included in the web sites. We compute a level expressing how much each entry of Wikipedia is related to the query according to the model that uses
Wikipedia features. When a site includes a lot ofhighly related entries, we consider the site is important. The evaluation method based on the hypothesis that Wikipedia is a reliable corpus and the
Wikipedia’s entries closely related with query is important.
When a web site contains the entries of Wikipedia
w(s) = {t1 ,t2 , . . . ,tn }, the score SiteScore(s) is calculated as follows:
SiteScore(s) =∑ Score(t)(5)

t∈w(s)

where Score(t) is a related level of the Wikipedia’s
entry t with the query q. It is calculated according to
the model described next.

Calculating a Score based on Inlink
The score calculated by using inlink Scorein(p) is calculated as follows:
inlink(p)Scorein (p) =(6)linknum(p)where inlink(p) is the number of inlinks from a pageof Wikipedia p to query q. linknum(p) is the total
number of links included in p.
Calculating Scores based on Outlink
To do this, we consider two cases as follows:(1) based on TF-IDF(2) based on the vector of TF-IDF
The score of (1), Scoreoutt f id f (p), is calculated as follows:
outlink(p)|W |Scoreoutt f id f (p) =
· log
(7)
linknum(q)|P|where outlink(p) is the number of outlinks fromquery q to a page of Wikipedia p. |W | is the total
number of links in Wikipedia. |P| is the document
frequency of the entry of Wikipedia p.
Next, the method (2) is used by (Witten and Milne,
2008; Nakayama et al., 2007). Calculating TF-IDF ina page, they extract a vector of weighted links. After extracting the vectors for each page, relatedness
between two pages can be calculated comparing theirvectors by using cosine metrics. Thus, the score of(2), Scoreoutt f id f vec (p), is calculated as follows:∑nk=1 l pk lqk
qScoreoutt f id f vec (p) = q2∑nk=1 l 2pk ∑nk=1 lqk(8)where v p = {l p1 , l p2 , . . . , l pn } is the vector of page p.
Calculating Scores based on Link Co-occurrence
To do this, we consider three cases as follows:(1) using cosine metrics(2) using the second-order co-occurrence (Schutze
and Pedersen, 1997)(3) based on Normalized Google Distance (Cilibrasi
et al., 2007)
The score of (1), cooOccur(p), is calculated asfollows:
cooOccur(p)Scorecocos (c) = p(9)f (p) · f (q)where f (p) is the term frequency of a page p.
cooOccur(p) is the number of pages that co-occur
with the target page of a query.

378

EVALUATING RERANKING METHODS USING WIKIPEDIA FEATURES

Next, the method (2) is used by (Ito et al.,2008). They create a vector of link first-order cooccurrence. A first-order co-occurrence is calculated
like cooOccur(p) by cosine metrics . vi, which is
the link vector of page p, is defined by the following
formula: v p = {c p1 , c p2 , . . . , c pn } where c pi is a firstorder co-occurrence between page p and i. Thus, thescore of (2) Scorecocosvec (p) is calculated as follows:∑nk=1 c pk cqk
qScorecocosvec (p) = q∑nk=1 c2pk ∑nk=1 c2qk

(10)

The method (3) is used by (Witten and Milne,2008). They use Normalized Google Distance model.
Thus, the score of (3) Scorecongd (p) is calculated asfollows:log(max(|P|, |Q|)) − log(|P ∩ Q|)
Scorecongd (p) =log(|W |) − log(min(|P|, |Q|))(11)
where |P ∩ Q| is the number of a page including boththe links of p and q.
Calculating Scores based on Category
To do this, we consider two cases as follows:(1) using a set of categories to which the original
query belongs(2) using a set of categories that are expanded by themethod described in section 3.1.
The score of (1), Scorecat (p), is calculated as follows:
Scorecat (p) =∑c∈Csetb(p, c)size(c)(q)(12)

where Cset (q) = {c1 , c2 , . . . , cn } is the set of categories
to which a query originally belongs. b(p, c) is a
Boolean value. If a page p belongs to a category c,b(p, c) becomes 1. Otherwise, b(p, c) becomes 0.
Next, the score of (2), Scorecatex (p), is calculated
as follows:b(p, c) ·CScore(c)Scorecatex (p) = ∑(13)size(c)
c∈C
(q)
setex

where Csetex (q) is the top K categories in descendingorder of CScore(c).

3EXPERIMENTS

In this section, we evaluate and compare our methods
in terms of their performance in improving the search
results for the initial query.
We used the Japanese Wikipedia database dump
from 28 March 2010 in our experiment. We also

use “Google Japanese search” in our experiment. We
asked 6 evaluators to make 51 queries that contain atleast one entry of Wikipedia and goals. They consistof 17 queries with at most three words for each. In
addition, if the query contains a word which appears
in disambiguation pages, we ask evaluators to select aconcept. Next, we evaluated 100 web sites on a scaleof 1 to 4 as follows: 4:“Highly relevant”, 3:“Relevant”, 2:“Partially relevant” and 1:“No relevant”.
We remove web sites that do not contain morethan 50 entries of Wikipedia from search results.
Many sites that we remove are the html documentsthat we fail to parse. As a result, the average numberof the search results become 93.86 sites. While theaverage number of sites evaluated as 3 or 4 is 18.02,
the average number of sites evaluated as 4 is 6.34.
Moreover, even if a site contains 500 or more entries
of Wikipedia, we analyze up to 500 words in the site
so that a long document does not have an advantage.
The accuracy of the results is measured by precision at K, and MAP (Mean Average Precision). Precision at K is precision of top K results. K is set to 10
in this experiment. MAP is an average of AP(Average
Precision). AP is the average of ratios of the numberof documents that user judges relevant to the number of whole given documents. Since these evaluation
methods require that a documents is either relevant or
irrelevant, we calculate both results for the strict relevance that we regard 4 as relevant and the relaxed
relevance that we regard 3 and 4 as relevant.

4

RESULTS AND DISCUSSION

We have proposed several methods in section 3. In
this section, we first evaluate category expansion
methods. Second, we evaluate methods based on
Wikipedia features. Finally, we compare our methods
with Google search results. When we evaluate a combination of each method, we normalize each vector
according to cosine normalization and add vectors.
Evaluation of Category Expansion Methods. Table
1 shows the results of category expansion methods in
section 3.1. Where P@10 is the result for precision
at K with the relaxed relevance (3 + 4). P@10H and
MAPH are the results for the strict relevance (4). The
window size of link co-occurrence is set to 10. Here,
we use the top 20 categories in descending order ofscore. Query in Table 1 is the method using a set of
categories to which a query originally belongs.
In comparison with other methods that use onlya single feature, outlink method is more accurate. In
addition, the co-occur method using paragraph performed less accurately than the method using sen-

379

ICAART 2011 - 3rd International Conference on Agents and Artificial Intelligencetence. Since we count all words in a paragraph that
contains K and more sentences, there is the variation of the number of the co-occurrence links among
pages. Moreover, the variation gives bad influence inthe result.
It also shows that a combination of outlink andcategory is the best accurate method. Outlink
achieves good results, while global information of
category improves the outlink method. Since themethod is more accurate than a method using a set of
categories to which a query originally belongs , category expansion methods are effective.

Table 2: P@10 and MAP : the methods based on Wikipedia
features.
category
inlinkoutlink1(tfidf)
outlink2(tfidfVec)
co-occur1(cosine)
co-occur2(second)
co-occur3(NGD)
outlink1+category
outlink 1+co-occur 1

P@10
0.306
0.301
0.31
0.301
0.299
0.267
0.284
0.318
0.321

P@10 H
0.122
0.127
0.129
0.126
0.121
0.108
0.119
0.133
0.136

MAP MAP H
0.329 0.197
0.321 0.208
0.334 0.222
0.318 0.2
0.318 0.192
0.283 0.159
0.297 0.179
0.344 0.224
0.342 0.225

count
4433
804
143
83694
6271
166867
6271
4521
6321

Table 3: P@10 and MAP : Google and our methods.
Table 1: P@10 and MAP : category expansion methods.
query
inlinkoutlinkco-occur(all)co-occur(sentence)co-occur(paragraph)outlink+category

P10
0.284
0.29
0.304
0.265
0.281
0.273
0.306

P10 H
0.109
0.121
0.128
0.105
0.109
0.104
0.122

MAP
0.310
0.315
0.325
0.288
0.3
0.296
0.329

MAP H
0.17
0.19
0.196
0.167
0.172
0.167
0.197

Evaluation of the Methods based on Wikipedia
Features. Table 2 shows the results of our methods
using each Wikipedia feature in section 3.3. Wherecount is the average number of related words extracted from Wikipedia. Category in Table 2 corresponds to the method of expanding categories using
outlink and category information. In comparison withother single methods, it identifies outlink as the moreaccurate measure, too. This result demonstrates thatthe complicated methods and methods of using a lotof information are bad. For example, the second order link co-occurrence method and the TF-IDF vector
method are worse than simple methods. Thus it reveals that the number of related words does not reflectaccuracy and deeply related words are very important.
Next, the result shows that a combination of outlink and category or link co-occurrence is the best
accurate method. So, global information of category or link co-occurrence would improve the outlink
method.
Comparison of our Methods with Google. Table 3
shows the results of Google and our methods. Our
methods are considerably worse than Google search
results. However, precision score of the search result
is 18.02/93.86 = 0.192. Thus, our method is effective
in comparison with the case when we select sites at
random.
Table 4 shows the results of Google and our methods when we use only one word query. The average number of the search results become 91.28 sites.
While the average number of sites evaluated as 3 or380

outlink 1
outlink 1+category
outlink 1+co-occur 1
Google

P@10
0.31
0.318
0.321
0.494

P@10 H
0.129
0.133
0.136
0.239

MAP
0.334
0.344
0.342
0.505

MAP H
0.222
0.224
0.225
0.417

Table 4: P@10 and MAP : Google and our methods when
we use only one word query.
category
outlink 1
outlink 1+category
outlink 1+co-occur 1
Google

P@10
0.355
0.347
0.365
0.382
0.439

P@10 H
0.15
0.157
0.167
0.172
0.231

MAP
0.373
0.38
0.394
0.394
0.477

MAP H
0.262
0.314
0.311
0.312
0.474

more is 15.88, the average number of sites evaluatedas 4 is 6.03.
Compared with the case where all queries areused, it is a very good result. The reason for this isthat our methods have some difficulty to recognize
deep semantic relationship between different words
in a query unless the relationship is apparent or verystrong. For example, given a query like “C++, Java”,
our methods works well. But, given a query like
“iPod, backup”, the methods do not work well.
On the other hand, precision score of the search
result is 15.88/91.28 = 0.174. Thus, our method isquite effective in comparison with the case when we
select sites at random. But our method was worse than
Google search result.
Figure 1 shows the graphs of the results. We concentrate on how much the accuracy of the retrieval
results is improved compared to those obtained by anexisting engine. First, we calculate AP for the results
given by Google. Next, each query is classified into
10 classes according to the value of AP, first 0, second 0.1 or less, and so on, and finally 1.0 or less.
Then, we calculate MAP for each class of queries andfor each method being compared. Each MAP valueof the point where AP is less than 0.2 represents theaccuracy of each method when using the queries forEVALUATING RERANKING METHODS USING WIKIPEDIA FEATURES

120

1.0≧
0.9≧
100
0.8≧
0.7≧
80
0.6≧
0.5≧
60
0.4≧
0.3≧
40
0.2≧
0.1≧
20

the numberProposalof query Google

0.6

102 100 102 0.394153 0.477867
97 0.400983 0.467425
100
91

97
91
78
60
34
14
7
3

0.40114878
0.410052
0.400914
0.396087
0.375250.265936
0.186868
0.069683

0.45557
0.437263
0.401373
60
0.359190.283838
0.1880434
0.107945
0.039227 14

0.5
0.4

0.2
7

0.1
3
0

1.0≧ 0.9≧ 0.8≧ 0.7≧ 0.6≧ 0.5≧ 0.4≧ 0.3≧ 0.2≧ 0.1≧
Proposal

GoogleFigure 1: Reranking results.

which Google returns poor results. Each MAP valueof the point that AP is less than 1.0 represents the accuracy of each method when using all queries.
The point where our method exceeds Google’s AP
is less than 0.6. This means our method is fairly effective when Google’s result is not good.

5

This work was supported by JSPS KAKENHI(21500102).

0.3

0

the number of query

ACKNOWLEDGEMENTS

CONCLUSIONS

We have shown that search results can be improvedby reranking them with various methods based on
Wikipedia features. Experimental results so far indicate the following.
• Category expansion methods are more effective
than a method using a set of categories to which aquery originally belongs.
• Reranking results are improved by deeply related
words but not the number of related words.
• Basically simpler methods work better. However,more sophisticated methods, that are based on local weights of outlinks and inlinks, and global
weights of link co-occurrence and category, work
significantly well.
• Any Wikipedia feature works fairly well to improve search results.
Moreover, it turned out that outlinks are much better than inlinks to be used for weighting in our methods. This is interestingly quite contrary to the resultsby Chernov et al. When extracting statistical information from Wikipedia, we need to carefully choose aneffective model. For this, we think a machine learning technique like Sumida et al. (Sumida et al., 2008)
would be promising.
In the future research, we are going to extract
more useful data by using Wikipedia features andclassify data using the machine learning.

REFERENCES
Chernov, S., Iofciu, T., Nejdl, W., and Zhou, X. (2006).
Extracting semantic relationships between wikipedia
categories. In Proc. of Workshop on Semantic Wikis(SemWiki 2006). Citeseer.
Cilibrasi, R. et al. (2007). The google similarity distance.
IEEE Transactions on knowledge and data engineering, pages 370–383.
Finkelstein, L., Gabrilovich, E., Matias, Y., Rivlin, E.,
Solan, Z., Wolfman, G., and Ruppin., E. (2002).
WordSimilarity-353 Test Collection.
Gabrilovich, E. and Markovitch, S. (2007). Computing semantic relatedness using wikipedia-based explicit semantic analysis. In Proc. of IJCAI-07, pages 6–12.
Hori, K., Oishi, T., Mine, T., Hasegawa, R., Fujita, H.,
and Koshimura., M. (2010). Related Word Extraction from Wikipedia for Web Retrieval Assistance. In
Proc. of ICAART 2010 vol.2, pages 192–199.
Ito, M., Nakayama, K., Hara, T., and Nishio, S. (2008).
Association thesaurus construction methods based onlink co-occurrence analysis for wikipedia. In Proc. of
the 17th ACM conference on Information and knowledge management, pages 817–826. ACM.
Nakatani, M., Jatowt, A., Ohshima, H., and Tanaka,
K. (2009). Quality evaluation of search resultsby typicality and speciality of terms extracted fromwikipedia. In Database Systems for Advanced Applications, pages 570–584. Springer Berlin/Heidelberg.
Nakayama, K., Hara, T., and Nishio, S. (2007). Wikipedia
mining for an association web thesaurus construction.
Web Information Systems Engineering–WISE 2007,
pages 322–334.
Page, L., Brin, S., Motwani, R., and Winograd, T. (1998).
The pagerank citation ranking: Bringing order to the
web.
Ponzetto, S. and Strube, M. (2006). Wikirelate! computing
semantic relatedness using wikipedia. In Proc. AAAI06, pages 1419–1424.
Schutze, H. and Pedersen, J. (1997). A cooccurrencebased thesaurus and two applications to information
retrieval. Information Processing & Management,
33(3):307–318.
Sumida, A., Yoshinaga, N., and Torisawa, K. (2008). Boosting precision and recall of hyponymy relation acquisition from hierarchical layouts in wikipedia. In Proc.
of the LREC 2008.
Witten, I. and Milne, D. (2008). An effective, low-cost measure of semantic relatedness obtained from Wikipedia
links. In Proc. of AAAI Workshop on Wikipedia andArtificial Intelligence: an Evolving Synergy, AAAI
Press, Chicago, USA, pages 25–30.

381