Discovering Unexpected Information on the basis ofPopularity/Unpopularity Analysis of Coordinate Objects
and their Relationships
Kosetsu Tsukuda

Hiroaki Ohshima

Graduate School ofInformatics, Kyoto University
Yoshida-Honmachi, Sakyo,
Kyoto, Japan

Graduate School ofInformatics, Kyoto University
Yoshida-Honmachi, Sakyo,
Kyoto, Japantsukuda@dl.kuis.kyotoohshima@dl.kuis.kyotou.ac.jp
u.ac.jp
Mitsuo Yamamoto
Hirotoshi Iwasaki
Katsumi Tanaka
Denso IT Laboratory
Shibuya-ku, Tokyo, Japan

Denso IT Laboratory
Shibuya-ku, Tokyo, Japanmiyamamoto@ditlab.co.jp

hiwasaki@d-itlab.co.jp

Graduate School ofInformatics, Kyoto University
Yoshida-Honmachi, Sakyo,
Kyoto, Japantanaka@dl.kuis.kyotou.ac.jp

ABSTRACT

General Terms

Although many studies have addressed the problem of finding Web
pages seeking relevant and popular information from a query, very
few have focused on the discovery of unexpected information. This
paper provides and evaluates methods for discovering unexpected
information for a keyword query. For example, if the user inputs“Michael Jackson,” our system first discovers the unexpected related term “karate” and then returns the unexpected information“Michael Jackson is good at karate.” Discovering unexpected information is useful in many situations. For example, when a user isbrowsing a news article on the Web, unexpected information about
a person associated with the article can pique the user’s interest. If
a user is sightseeing or driving, providing unexpected, additional
information about a building or the region is also useful. Our approach collects terms related to a keyword query and evaluates thedegree of unexpectedness of each related term for the query on thebasis of (i) the relationships of coordinate terms of both the keyword query and related terms, and (ii) the degree of popularity ofeach related term. Experimental results show that considering these
two factors are effective for discovering unexpected information.

Algorithms, Experimentation

Categories and Subject Descriptors
H.3.3 [Information Systems]: Information Storage and Retrieval—
Information Search and Retrieval

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
SAC’13 March 18-22, 2013, Coimbra, Portugal.
Copyright 2013 ACM 978-1-4503-1656-9/13/03 ...$10.00.

Keywords
Coordinate term, Wikipedia, unexpected information

1.

INTRODUCTION

Search engines such as Google1 , Yahoo2 , and Bing3 return search
results ranked by relevance and popularity relative to the input query.
In most cases, higher ranked Web pages include more relevant andpopular information. Some research has proposed innovative methods for documents retrieval. For example, BM25 [18] has been proposed as a state-of-the-art text-based ranking function, and HITS [11]and PageRank [3] are link-based ranking algorithms. On the basisof these studies, many additional studies have reported improved
methods for the retrieval of appropriate query results [6, 8, 9, 20].
A disadvantage of these studies is that they do not address unexpected information. To the best of our knowledge, there have beenvery few studies that focus on discovering unexpected informationon the Web [12, 14, 15], although there has been a great deal of research focused on extracting unexpected or unusual frequent rulesin the field of data mining [2, 16, 17]. When a user queries a searchengine, the retrieved Web pages contain a wide variety of information relative to the query. These pages can contain details ranging
from well-known to unexpected information. For example, for thequery “Michael Jackson,” it is well known that “Michael Jackson isa singer,” but it is generally unknown that “Michael Jackson is goodat karate.” The user can find common known information about aquery easily because it is often included in the top ranked searchengine result pages (SERP); however, comparatively less known
information would likely appear in lower ranked Web pages. Even1

http://www.google.com
http://www.yahoo.com
3
http://www.bing.com
2

if top ranked Web pages include unexpected information, it is usually buried in a lot of other information and is difficult for the user
to find.
Discovering relevant unexpected information relative to a keyword query is useful in certain situations. For instance, when auser searches the Web for information about a specific person, finding unexpected information can pique the user’s interest. Similarly,
if unexpected information about a person or incident is displayedwhen a user is browsing a news article, the information can alsopique the users’ interest. Moreover, when a user is sightseeing or
driving, showing unexpected information about a building or thesurrounding area may come in handy. Hence our objective is to
discover unexpected information relative to keywords, such as specific people, facilities, or regions.
In this research, we target information that contains two objects.
For example, in the information “Michael Jackson is a singer,” oneobject is “Michael Jackson” and the other is “singer.” We denote an
object given as a keyword query as a “theme term” and an object
that is related to the theme term as a “related term.” Detailed explanations of theme terms and related terms are provided in Section 3.
Our approach has three steps. First, given a query keyword (themeterm) q, we collect its related terms Lq = {e1 , e2 , · · · en }. We use
Wikipedia4 to collect a very large set of related terms. Next, weevaluate the degree of unexpectedness of each related term ei for q
on the basis of relationships of coordinate terms of q and ei , and thedegree of popularity of ei . We hypothesize that when the objects
are popular but the relationship between the objects is unpopular,
the information is unexpected. In our method, we utilize the link
structure between terms in Wikipedia and the super-sub relation between terms. Finally, we extract a sentence from a Wikipedia article
that includes a related term with a high degree of unexpectedness
and present it to a user as unexpected information.
We conducted an experiment using 75 queries in five domains:
the names of people, regions, products, facilities, and organizations. Our results show the effectiveness of our algorithm considering the popularity of related terms of a theme term and theunpopularity of the term-relationships.
The remainder of this paper is organized as follows. Section 2
surveys related work. Section 3 explains the hypothesis of unexpected information as used in this research. Section 4 proposes
methods for calculating the degree of unexpectedness for each related term for a query. Section 5 describes the experimental set-up
and reports the results. A summary of the research and plans for
future studies are presented in Section 6.

2.

RELATED WORKIn the field of information retrieval, there are many methods for
returning a list of search results ranked by relevance and popularity[3, 6, 8, 9, 11, 18, 20]. In most cases, the top ranked documents
tend to include relevant and popular (well-known, major) information for the query. However, finding unexpected information by
applying these methods is difficult.
In the field of information extraction, many studies have proposed techniques for finding useful knowledge from the Web [1, 4,
7]. Some studies used machine learning [4, 5], while others utilize
syntactical pattern matching [7] or a bootstrapping technique [1].
These studies address discovering generally known and popular information rather than unexpected information because the objective
is to create a computer-understandable knowledge base to realize
much more effective retrieval of Web information.
To the best of our knowledge, very few studies focus on discov4

http://ja.wikipedia.org/

ering unexpected information [12, 14, 15]. Noda et al.[15] useda relationship between categories in Wikipedia to discover unexpected knowledge. Using their method, a user can find that “TaroAso” belongs to the category “Japan’s premier” and to the category“participant in an Olympic shooting event.” Only Taro Aso belongs
to the two categories, and the fact “Taro Aso is a Japan’s premierand a participant in an Olympic shooting event.” is unexpected. In
Wikipedia, articles do not belong to many categories, and therefore, their approach is limited. Nadamoto et al.[14] proposed amethod for searching for a user’s unawareness of information incommunity-type content, such as blogs and social networking services. They refer to such information as a “content hole” and define
seven types of content holes [13]. Liu et al.[12] proposed methods
to help a company find unexpected information from competitors’
Web sites by comparing their Web sites with that of the competitors. This approach compares sites for information such as important keywords and outgoing links and displays the differences to theuser. Their objective was to discover unexpected information thatis not included in a particular Web site or bulletin board system.
Our objective is to discover unexpected information for a keyword
for an unrestricted search.
In the field of association rule mining, the frequency-based rulefor discovering information becomes less interesting because mostfrequency rules are obvious. Instead, discovering unexpected patterns has received increasing attention [17, 16, 2]. However, wecannot use these approaches because they involve well-structured
rules and have clear syntax and semantics. Because information on
the Web is not fully structured, a different approach is required to
discover unexpected information from the Web.

3.

UNEXPECTED INFORMATION

We target information that contains two objects. Here an object
is an essential element that, when combined with another essential element (object), constructs the information. For example, inthe case of the information “Michael Jackson is good at karate,”“Michael Jackson” and “karate” are objects because they are important elements. This information could be shown when the user conducts a Web search with the query “Michael Jackson,” or browses a
news article about “Michael Jackson.” In these situations, we findunexpected information about the input keyword “Michael Jackson.” We denote the object that is given as an input keyword as
a “theme term,” and we refer to an object related to a theme term
as a “related term.” There are various types of related terms forthe theme term “Michael Jackson,” for example “singer,” “THIS IS
IT,” “Stevie Wonder,” among many others.
When two terms have a common hypernym, they are coordinate terms. For instance, “Michael Jackson” and “Stevie Wonder” are coordinate terms because they have a common hypernym,“singer.” “Michael Jackson” and “Maria Sharapova” are also coordinate terms because of the common hypernym, “human beings.”
However, “Stevie Wonder” is an appropriate coordinate term because “Michael Jackson” and “Stevie Wonder” have many common
hypernyms in addition to “singer,” for example “male” and “vegetarian.” On the other hand, “Maria Sharapova” is a less-appropriate
coordinate term. There are degrees of difference among the coordinate terms of a theme term. In this paper, we denote a termthat has many hypernyms with a term as an “appropriate coordinate term,” and a term that has few hypernyms with a term as a“less-appropriate coordinate term.”
To describe the type of information people perceive unexpected
as something relative to the theme term, its related term, and theircoordinate terms, we inspect four examples, each with the theme
term “Michael Jackson.” The information “Michael Jackson won aMichael Jackson
Mariah Carey

Michael Jackson
Indiana
Mariah Carey

GrammyAward

New York

Stevie Wonder

Stevie Wonder

Madonna

Madonna

MichiganFigure 1: Related term “Grammy Award” is also related toappropriate coordinate terms of “Michael Jackson.”Figure 3: appropriate coordinate terms of “Michael Jackson”
include appropriate coordinate terms of “Indiana” as a relatedterm.

Michael Jackson
Michael Jackson
Mariah Carey

Indiana
Mariah Carey

Stevie Wonder

karatejudo

karateStevie Wonder

sumo

Madonna
MadonnaFigure 2: Related terms “Indiana” and “karate” are not related
to appropriate coordinate terms of “Michael Jackson.”Grammy Award” is not unexpected to most people as many prominent artists have won the award. That is, appropriate coordinate
terms of “Michael Jackson” also have the term “Grammy Award”
as a related term (See Figure 1). For the information “MichaelJackson is from Indiana” and “Michael Jackson is good at karate,”appropriate coordinate terms of “Michael Jackson” may not have“Indiana” or “karate” as related terms, as is shown in Figure 2.
Although these two examples have the same structure, the information “Michael Jackson is from Indiana” may not be common
knowledge but it is not entirely unexpected. All singers are froma certain place; therefore, this information is just an example ofthe same. That is, appropriate coordinate terms of “Michael Jackson” have appropriate coordinate terms of “Indiana” as their related terms (See Figure 3). In contrast, most people do not expect
Euro-American singers to be good at Japanese martial arts. Consequently, the degree of unexpectedness of the information “MichaelJackson is good at karate,” is quite high. That is, appropriate coordinate terms of “Michael Jackson” do not have appropriate coordinate terms of “karate” as their related terms (See Figure 4).
We also consider the information “Michael Jackson bought an R360.” Here, “R-360” is a game machine. In this case, appropriate
coordinate terms of “Michael Jackson” do not have appropriate coordinate terms of “R-360” as their related terms. Although thisinformation has the same structure as “Michael Jackson is good at
karate,” the degree of unexpectedness of this information would be
low because the term “R-360” is not generally known and therefore the degree of popularity is low. That is, we hypothesize thatpeople do not perceive information as unexpected if it includes an
unknown related term. Therefore, we also need to consider the degree of popularity of each related term.
In our approach, we regard unexpected information as information in which coordinate terms of a theme term do not have a relationship with a well-recognized related term and its coordinate
terms. Given a theme term q and its related term ei , we define afunction Rel (q, ei ) that represents the degree of relationship between q and ei . The function Cog(ei ) represents the popularity
degree of ei . We then define a function f that combines these functions and calculate the degree of unexpectedness of the pair of q
and ei : Unexp(q, ei ) = f (Rel (q, ei ), Cog(ei )).

4.

CALCULATING THE DEGREE OF UNEXPECTEDNESSFigure 4: appropriate coordinate terms of “Michael Jackson”
do not include appropriate coordinate terms of “karate” as arelated term.

Given a theme term, the degree of unexpectedness of each related
term is calculated as follows:
1. Collect a set of related terms Lq = {e1 , e2 , · · · en } for atheme term q.
2. Collect hypernyms and coordinate terms of q and those ofeach related term.
3. Calculate the strength of a relationship Rel (q, ei ) between q
and each related term.
4. Calculate the degree of popularity Cog(ei ) for each relatedterm.
5. Calculate the degree of unexpectedness Unexp(q, ei ) of eachrelated term for q.
In the following subsections, we explain each step in detail.

4.1

Collecting a set of related terms

In this paper, we regard anchor texts in a Wikipedia article ofthe theme term q as the related terms for q. Anchor texts are used
to link related Wikipedia articles. In the case of “Michael Jackson,” there are a total of 819 anchor texts; for example, “Thriller,”“Paul McCartney” and “PlayStation 3,” all appear as anchor texts.
We focus on Wikipedia articles for three reasons. The first reason is that there are fewer noise terms in Wikipedia articles as theygenerally focus on information about a theme term q. The second
reason is that Wikipedia articles primarily contain objective information. We are not targeting unexpected information derived frompersonal opinions or impressions; we are only interested in information written from an objective perspective. The third reason isthat, as a matter of policy, Wikipedia does not link to a term if theterm is not directly related to the title of an article. Therefore, wecollect all Wikipedia anchor texts in an article of q as related terms
for q.

4.2

Collecting hypernyms and coordinate terms

To collect coordinate terms, we used an open source “hypernym/hyponym extraction tool,”5 on the Japanese Wikipedia. This5

http://nlpwww.nict.go.jp/hyponymy/index.html

…

MichaelJacksonGrammy Awardaward

karateAmericanstatevegetarian

James Dean

male

…

…
Indianacountry
Americasporthuman beings

Barack Obama
Maria
Sharapova

Hawaii…

Before explaining our proposed method in detail, we will describe it visually. In Figure 5, vertices represent terms and the edges
represent their relationships. The graph is constructed from the following vertices. We denote the set of hypernyms of term t withhyper (t), the set of hyponyms of t with hypo(t), and the set of
related terms of t with rel (t).

member of
USA for Africa…

Calculating the degree of relevance between
a subject term and its related term

Academy Award
Diana
Ross

singer

…

4.3

Michigan
Stevie Wonder…

tool contains 223, 772 hypernyms and 2, 751, 046 hyponyms. Thesehierarchized terms are category names and nouns that occur in thetitles of Wikipedia articles. Using this data, we can easily extract
hypernyms of a term and coordinate terms that have hypernyms incommon with the term. For instance, “Michael Jackson” has a total of 69 hypernyms such as “singer” and “Guinness world record
holder.” If a term has at least one common hypernym with “MichaelJackson,” the term is a coordinate term of “Michael Jackson.”

Tennis• Q = {q}AD˛• Hq = {x|x ∈ hyper (q)}AD
˛

Figure 5: An example of the graph for a theme term “MichaelJackson.”• Cq = {x|x ∈ hypo(y), y ∈ Hq , x ∈/ Q}AD˛• (x, y) where x ∈ Cq , y ∈ Lq , and y = rel (x)AD˛→ place name → Indiana.” On the other hand, there are no paths toreach “karate” from appropriate coordinate terms, even through thehypernyms of “karate.” Although there may be a few paths fromless-appropriate coordinate terms directly or through the hypernyms, we assume that it is difficult to reach “karate” from “MichaelJackson” and that there is potential for an unexpected term; forexample “Michael Jackson → human beings → Jean Cocteau →sumo → Japanese sport → karate.”
To evaluate the strength of the relationship between a theme termand each of its related terms, we first construct a graph as describedabove. We regard the presence or absence of the relationship between a theme term and its related term as the presence or absenceof a path between these two terms. We calculate the degree of association of the pair by considering the strength of the relationshipbetween them as the ease in reaching the related term from a theme
term. The more difficult it is to reach a related term from a theme
term, the lower the degree of association.
In the next subsections, we divide the graph into three subgraphs
and evaluate the degree of association of related terms.

• (x, y) where x ∈ Lc , y ∈ Hlq , and y = hyper (x)AD
˛

4.3.1

• Lq = {x|x ∈ rel(q)}AD
˛• Hlq = {x|x ∈ hyper (y), y ∈ Lq }AD˛• Lc = {x|x ∈ rel (y), y ∈ Cq , x ∈/ Lq }AD˛
In Figure 5, the black circle, white circle, black triangle, white triangle vertices represent a term in Q, Cq , Lq , and Lc , respectively.
A square vertex represents a term in Hq or Hlq .
Edges exist between two terms if and only if one term is a hypernym of the other term or one term is a related term of the otherterm. In the following, (n1 , n2 ) means that there is an edge between
a vertex n1 and a vertex n2 .
• (q, x) where x ∈ Hq AD˛• (x, y) where x ∈ Hq , y ∈ Cq , and y = hypo(x)AD˛• (x, y) where x ∈ Cq , y ∈ Lc , and y = rel (x)AD˛• (x, y) where x ∈ Hlq , y ∈ Lq , and x = hyper (y)AD˛This graph does not include edges between the theme term andits related terms because the objective is to demonstrate the easein reaching all related terms of a theme term. That is, we assume that if it is easy to reach a specific related term from a theme
term, the related term is expected. As we indicated previously, theterm “Grammy Award” is not unexpected for “Michael Jackson.”
As shown in Figure 5, there are many paths to reach “Grammy
Award” from “Michael Jackson” through appropriate coordinate
terms such as “Michael Jackson → singer → Stevie Wonder →Grammy Award” and “Michael Jackson → singer → Mariah Carey→ Grammy Award.” In this case, we think it is easy to reach therelated term. In the case of “Indiana,” there may be very few paths
to directly reach “Indiana” in one step from appropriate coordinate
terms of “Michael Jackson.” However, there are many paths toreach “Indiana” from appropriate coordinate terms through the hypernyms of “Indiana” such as “Michael Jackson → singer → Stevie
Wonder → Michigan → American state → Indiana” and “MichaelJackson → member of USA for Africa → Diana Ross → Michigan

Calculating the degree of coordination to a theme
termFirst, we consider a bipartite graph G1 = (Q∪Cq ∪Hq , E1 ) thatis constructed from q, its hypernyms, and their hyponyms. Here E1
is a set of edges between Hq and Q ∪ Cq . An edge exists betweenhi ∈ Hq and tj ∈ Q ∪ Cq when hi is a hypernym of tj .
We apply the Co-HITS algorithm [6] to the bipartite graph andcalculate the degree of coordination to q for each term in Cq . The
Co-HITS algorithm is an expanded version of the HITS algorithm[11]. In the HITS algorithm, a Web page that provides important
information is called an authority, and a Web page that links toimportant authorities is called a hub. A good hub is a page thatpoints to many good authorities, and a good authority is a pagethat is pointed to by many good hubs. In our bipartite graph, a
hypernym and a hyponym correspond to a hub and an authority,
respectively. We denote the hub score of hi and the authority scoreof tj with xi and yj , respectively, and calculate these scores asfollows:
∑
∑ ht
th
xi =
wji
yj , yj =wij xi ,(1)
tj ∈Q∪Cqhi ∈Hqthhtthwhere wji
and wij
represent the weight of edges, and wji
represents the transition probability from tj to hi . If we apply the HITS
algorithm to the bipartite graph G1 , vertices that have a very large
number of hyponyms, for example “human beings,” have a highscore. Hence each hyponym of “human beings” has a misleading
high score, and terms sharing hypernyms that have many hyponyms
become appropriate coordinate terms of q. To solve this problem,
we use the Co-HITS algorithm expressed as follows:∑thxi = (1 − λh )x0i + λh
wji
yj ,
(2)
tj ∈Q∪Cqyj = (1 − λt )yj0 + λt

∑

ht
wij
xi ,

(3)

where x0i and yj0 represent the initial scores for terms hi and tj ,respectively. In the Co-HITS algorithm, the more edges a vertex
has, the smaller the weights of the edges become. Specifically theht
1weight of the edge from hi to tj is represented by wij= |hypo(h,i )|thand the weight of the edge from tj to hi is represented by wji=
1.
Moreover,the
Co-HITSalgorithm
considerstheinitial|hyper (tj )|score of each vertex. We set the initial value of q as 1 and theinitial values of the remaining vertices as 0 because the objectiveof applying the Co-HITS algorithm is to calculate the degree of
coordination to q. The parameters are λh ∈ [0, 1] and λt ∈ [0, 1].
If we regard an initial score as important, we set their values close
to 0. We set λh = λt = 1 because only the vertex of q has an
initial score and the results did not change significantly when thevalues of the parameters were changed. We regard the convergent
score of yj as the degree of coordination of tj to q.

4.3.2 Calculating the degree of relevance between atheme term and each related term (1)To calculate the degree of relevance between a theme term andeach of its related terms, we consider a graph G2 that includes all
vertices in Cq , Lq , and Lc . This graph is a directed graph, and if
the term tj is a related term of ti , there is an edge from ti to tj . We
apply a biased PageRank algorithm to this graph.
PageRank[3] is a method for computing the importance of Web
pages using a Web link structure. The main criterion in PageRank is that a Web page is important if many other important Web
pages link to it. This means that if page u has a link to page v,
the link propagates the importance of u to v. Let r(u) represent
the degree of importance of page u, and let Fu represent the set ofpages linked by page u. We can assume that all links are equal,
therefore, the link (u, v) propagates r(u)/|Fu | units of importancefrom page u to page v. Because r(u) is also recursively determinedby pages that point to u, the PageRank algorithm is computed using
the power method. Let Bv be the set of pages that points to v, N
be the number of all vertices in the graph, and α be the damping
factor, then this simple idea leads to the following equation.
∑ ri (u)
u∈Bv

|Fu |

+

1−α
.
N

(4)

Throughout this paper, we set α to 0.85, following the original
PageRank algorithm. In order to evaluate the ease of reaching eachrelated term from q, we revise Equation 4 on the basis of biased
PageRank:
ri+1 (v) = α∑ ri (u)
u∈Bv

|Fu |

Here, fco (v) is the score of term v calculated in Equation 3. We
apply this process to the graph G2 . A vertex with a low score in Lq
is a term that has a low relationship with q. However, in this step we
can only consider related terms that can be directly reached throughappropriate coordinate terms.

4.3.3

hi ∈Hqri+1 (v) = α

where fini (v) is the initial value of vertex v and is defined by:{∑ fco (v)v ∈ Cqt∈Cq fco (t)fini (v) =0v∈/ Cq .

fini (v),t∈Cq fini (t)+ (1 − α) ∑(5)

Calculating the degree of relevance between atheme term and each related term (2)Finally, we evaluate the degree of relevance of each related termei ∈ Lq by considering the coordinate terms of ei . In the second
phase, related terms such as “Indiana” do not have a high scorebecause they are not directly related to appropriate coordinate termsof q. However, as we described, it is possible to reach “Indiana”
from appropriate coordinate terms through its hypernyms such as“American state” and “place name.” The objective of this phase is
to increase the score of such related terms.
Given a related term ei ∈ Lq , we first collect all of its coordinate
terms and hypernyms. We denote the set of ei and all its coordinate
terms as Cei and the set of hypernyms of ei as Hei . In Cei , someterms may be included in graph G2 , but others are not. We construct a bipartite graph that consists of Cei and Hei . Edges exist
between a term ui ∈ Cei and a hypernym vj ∈ Hei when vj is a
hypernym of ui . We apply the Co-HITS algorithm to the bipartite
graph. The initial score of each hypernym is zero. If a vertex in Cei
is included in graph G2 , the initial score of the vertex is the value
calculated by the steps described in Section 4.3.2. If a vertex in Cei
is not included in graph G2 , its initial score is zero. We calculate
the score of each vertex in the following equations:∑vuxi = (1 − λu )x0i + λu
wji
yj ,
(6)
vj ∈Heiyj = (1 − λv )yj0 + λv

∑

uv
wij
xi ,

(7)

ui ∈Cei

where x0i and yj0 represent the initial scores for terms ui and vj , respectively, and xi and yj are the scores of ui and vj , respectively.
vuuv
1= |hypo(v. In this biparMoreover, wij= |hyper1(ui )| and wji
j )|tite graph, the scores of all nodes vj ∈ Hei are equal to 0; therefore,
we set λv as 1. We discuss the effectiveness of the parameter λu in
Section 5. We conduct the operation for each related term of q; letRel (q, ei ) represent the score calculated by Equation 6.

4.4

Calculating the degree of popularity of a
related term

We calculate the degree of popularity of each related term by thefollowing two methods.
The first method regards the PageRank score of articles as the
popularity degree. In the PageRank algorithm, an article that isreferenced by many good articles has a high PageRank score, andwe assume that the title of such an article is generally well known.
Hence we apply the PageRank algorithm to all articles in Wikipedia
on the basis of link structure. The popularity degree of a term corresponds to the PageRank score of an article whose title is the term.
We denote the PageRank score of a term ei as PageRank (ei ).
The second method considers the Web hit count of the term as the
popularity degree. A term with a high hit count potentially infers
frequent use of the term. We get the Web hit count of a term byCategory
PersonRegionProduct
Facility
Organization

Table 1: Examples of queries (English translation).
Query with more than 150 related terms
Query with fewer than 150 related terms
Prince Shotoku, Tamori, Nobita Nobi
Funaki Tomosuke, Higashikuni Shigeko
Monaco, The Rhine, Venus
Ohsu Domain, Kainan Island
Air-bag, Train lunchi, Rocky Joe
Rhythm guitar, Two-legged robot
Nagoya Station, Theater, Tokyo Sky Tree
U.S. Library of Congress, Byodoin
UNIQLO, Japan’s national soccer team, Sanyo Electric Mitsui Group, University cooperative

using the Yahoo! Web Search API6 and denote the hit count of ei
as Hit(ei ).

4.5

Calculating the degree of unexpectedness

Given the theme term q, we can find the strength of a relationship Rel(q, ei ) between q and each of its related terms ei . We
have established that there is higher degree of unexpectedness when
there is a lower relationship value; therefore, we use the inverseof Rel(q, ei ). For the popularity degree of each related term, ahigher popularity degree results in a higher degree of unexpectedness. When we use the PageRank score, the degree of unexpectedness is calculated by the following equation:
1· PageRank (ei ).
Unexp(q, ei ) =Rel (q, ei )(8)

When we use the Web hit count, the degree of unexpectedness iscalculated by the following equation:
Unexp(q, ei ) =1· log10 Hit(ei ).
Rel (q, ei )(9)

We use the logarithm to scale back the influence of the Web hit
count because it differs significantly from one term to another.

5.

EXPERIMENT

We conducted an experiment to examine the effectiveness of our
proposed method. The objective of our experiment is to clarify two
research questions: (1) Is considering the degree of popularity ofrelated terms important to the discovery of unexpected information? (2) Is considering the relationship between coordinate termsof a theme term and coordinate terms of its related terms importantto the discovery of unexpected information?
To answer these questions, we used six proposed methods andcompared them with four simpler methods. The six proposed methods calculate the degree of unexpectedness of each related term byusing Equation 8 or 9. In order to compare the impact of λu inEquation 6, we set λu to 0.25, 0.5, and 0.75. A method using Equation 8 in which λu was set to 0.25 was denoted as PR25 . Similarly,
we denote the other methods as PR50 and PR75 . We denote methods using Equation 9 with λu set to 0.25, 0.5, and 0.75 as HIT25 ,HIT50 , and HIT75 , respectively.
We use three additional simple methods to answer the first research question. In these methods, only the strength of the relationship between a theme term and a related term is evaluated andthe popularity degree of related terms is neglected. The score of related term ei of the theme term q is calculated by U nexp(q, ei ) =1. In these methods, we also set λu to 0.25, 0.5, and 0.75.
Rel(q,ei )We denote each method as REL25 , REL50 , and REL75 .
We also proposed a simple method to answer the second researchquestion. In this method, we get the Web hit count of each pair of(q, ei ) using the Yahoo! Web Search API. The query is “q ∧ei ” for6
http://developer.yahoo.co.jp/webapi/search/websearch/
v1/websearch.html

the pair of (q, ei ), then the related terms are ranked in ascending order. That is, we assume that if a related term has low co-occurrence
frequency with q, the term is unexpected for q. We denote thismethod as TC.
We discover unexpected information relative to a theme termfrom a Wikipedia article where the title of an article is the theme
term. Given a theme term and a related term, we extract a sentencethat includes the related term from the article. If the related term
is included in more than one sentence, we extract the first sentencethat uses the term. In the experiment, described in Section 5.2, thissentence will be used as the corresponding information.

5.1 Query set
We created a query set that consisted of 75 theme terms in fivecategories: names of people, facilities, regions, products, and organizations. Each category included 15 theme terms. Obviously, if auser is not at all familiar with the theme term, all information will
be not unexpected for him. Hence we selected terms that appearedin the top 5% of PageRank scores among all Wikipedia articles.
The number of articles was 17, 325. Moreover, we assumed thatthe fewer the number of related terms, the lower would be the probability of discovering unexpected information. To examine this, wefirst divided the set of articles into two groups: group (a) included
articles that had more than 150 related terms, and group (b) included articles that had less than 150 related terms. There were
4, 854 articles in group (a) and 12, 471 articles in group (b). We
randomly selected 10 articles for each category from group (a). The
remaining five terms in each category were randomly selected fromgroup(b). We used the title of each article as a query, or a theme
term. Examples of the query set are shown in Table 1.

5.2 Procedure
In this experiment, we recruited five evaluators and administereda questionnaire. Two males and a female were in their thirties andtwo females were in their twenties.
We created the questionnaire as follows. First, a theme term wasused with each method. Given a theme term, each of the ten methods returned a ranked list of related terms in descending order by
the degree of unexpectedness. We used the top five related terms
from each method. We pooled the related terms and generated a listof randomly sorted pairs of related terms and the corresponding information. We asked evaluators to label each pair of a related term
and its information on a scale of 1-4 from expected to unexpectedby asking “Do you think this information is unexpected?”
A total of 75 questionnaires were constructed, with each questionnaire corresponding to a single theme term. We then ordered
five sets of questionnaires taking the order effect into consideration.
Five evaluators answered the questionnaires individually. Then we
calculated the average degree of unexpectedness for each piece of
information. For example, for a query “Monaco,” one method detected the related term “Kimiko Date7 ” as a highly unexpected term
7
Kimiko Date is a famous Japanese tennis player and is also a television personality.

Table 2: Performance comparison of each category for ten
methods measured by nDCG
Method
TC
REL25
REL50
REL75
PR25
PR50
PR75
HIT25
HIT50
HIT75

Person
0.705
0.805
0.807
0.807
0.828
0.824
0.818
0.798
0.791
0.790

Region
0.757
0.792
0.803
0.808
0.830
0.830
0.836
0.832
0.834
0.838

Product
0.773
0.837
0.839
0.841
0.846
0.851
0.858
0.843
0.843
0.847

Facility
0.787
0.800
0.800
0.804
0.825
0.821
0.820
0.824
0.823
0.822

Organization
0.780
0.853
0.857
0.852
0.860
0.860
0.854
0.856
0.867
0.872

Average
0.760
0.817
0.821
0.822
0.838
0.837
0.837
0.830
0.832
0.834

and output the corresponding information “Kimiko Date is now living in Monaco.” The five evaluators assessed the unexpectednessof this information as 4, 3, 2, 3, and 2. The average degree of unexpectedness of this information was 2.8.

5.3

Metrics for evaluation

We used Normalized Discounted Cumulated Gain (nDCG)[10]and Normalized Weighted Reciprocal Rank(NWRR)[19] as evaluation metrics.
nDCG is a measure of retrieval effectiveness that utilizes graded
relevance judgments. We used this metric because it is preferable
to rank much and more unexpected information at higher rank.
NWRR only considers a correct answer at the highest rank. In
our experiment, each piece of information has an unexpected scorejudged by evaluators. This score ranges from 1 to 4, and we regard
information with a score larger than the intermediate value of 2.5
as especially unexpected information, or an answer. Due to lack ofspace, we refer the reader to a paper by Sakai [19] for further detailof this metric. In this metric, the score is equal to 1 if a method
can put the most unexpected information for a theme term at rank
1. If the top five pieces of information discovered by a method are
judged not unexpected by evaluators, the NWRR score is 0.

5.4

Experimental results

The nDCG scores for each method and category are shown in
Table 2. In all categories, one of the six proposed methods thatconsidered the popularity degree of related terms resulted in thehighest nDCG. REL25 , REL50 , and REL75 followed those six
methods. The results show that it is important to consider the popularity degree of related terms to discover unexpected information.
The TC method got the lowest scores in all categories. This result shows the importance of considering the relationship between
coordinate terms of both a theme term and its related terms to discover unexpected information. In this experiment, there was not asignificant difference between the methods that used the PageRankscore and methods that used the Web hit count for calculating the
popularity degree of related terms. As for the parameter λu in the
Co-HITS algorithm, too, there was not a significant difference. The
NWRR scores for each method in each category are shown in Table
3. On an average, HIT75 could discover more unexpected information at a higher rank than other methods. TC and REL25 got thehighest scores in the categories of product and person, respectively.
However, the average scores of these two methods were lower thanour six proposed methods and the average nDCG scores were also
lower. These results indicate that we could discover unexpected
information by chance even if we did not consider the degree of
popularity and the relationships between terms. On the other hand,
our proposed methods could discover unexpected information inany category.

Table 3: Performance comparison of each category for ten
methods measured by NWRR
Method
TC
REL25
REL50
REL75
PR25
PR50
PR75
HIT25
HIT50
HIT75

Person
0.307
0.513
0.506
0.506
0.434
0.418
0.421
0.384
0.384
0.400

Region
0
0.118
0.118
0.163
0.184
0.184
0.199
0.165
0.184
0.218

Product
0.478
0.319
0.327
0.332
0.341
0.361
0.361
0.234
0.234
0.234

Facility
0
0.215
0.199
0.194
0.418
0.241
0.241
0.567
0.542
0.513

Organization
0
0.165
0.177
0.177
0.194
0.194
0.194
0.118
0.172
0.241

Average
0.157
0.266
0.266
0.274
0.314
0.280
0.283
0.293
0.303
0.321

We show some examples of information evaluated as unexpected
information in Table 4. For the theme term “Akita Prefecture,” anunexpected related term “lifestyle-related disease” and the corresponding information “In addition to excessive drinking, people
consume too much salt from preserved foods such as pickles andAkita Prefecture has a high rate of death from lifestyle-related disease such as a stroke.” was discovered. In our method, other prefectures in Japan were evaluated as appropriate coordinate termsof “Akita Prefecture,” and disease names were evaluated as appropriate coordinate terms of “lifestyle-related disease.” In general,a prefecture does not have a relationship with a specific disease,and “lifestyle-related disease” is a well-known term. Hence, ourmethod could evaluate the related term as an unexpected term.
Finally, in Table 5, we show the number and ratio of theme terms
in which we could discover at least one piece of unexpected information. On an average, we could discover unexpected informationin 40% of theme terms that had greater than 150 related terms andin 24% of theme terms that had less than 150 related terms. This
result shows that the probability of discovering unexpected information is high if a theme term has many related terms. According
to our observations, there are two principal reasons why our methods could not discover unexpected information. One reason is that
unexpected information is not written in some articles even when
the theme term has many related terms. This tendency was especially true in the building, facility, and organization categories. The
other reason stems from specific characteristics of our method. For
example, the article for “digital camera” includes the information“A digital camera is often abbreviated to Dejikame in Japan, but
Dejikame is a registered trademark of SANYO Electric and othercompanies” and this information seems to be unexpected. The related term in this information is “SANYO Electric,” but it is related
to many other electrical products that are appropriate coordinate
terms of “digital camera.” Therefore, our method could not discover this information.

6.

CONCLUSION

In this paper, we proposed a new method for discovery of unexpected information. In particular, we focused on two aspects: (i) the
relationship between a theme term, its coordinate terms, its related
terms, and their coordinate terms, and (ii) the degree of popularityof each related term. We conducted an experiment to clarify theimportance of considering these two aspects. Our results showedthat the degree of popularity of a related term was highly relevantto the degree of unexpectedness. Moreover, it was also effective
to consider the coordinate terms rather than considering only theco-occurrence frequency of a theme term and its related term.
We would like to explore methods for determining unexpected
information from other information resources. This would enable
us to find a variety of unexpected information; however, we would

Table 4: Examples of discovered unexpected information (English translation).
Theme term
Air-bag

Related term
Fire Defense Law

Horyuji temple

Cultural Property Fire
Prevention Day

Vending machine
MonacoMitsui Group

scenery
Kimiko Date
Tokyo Disneyland

Akita Prefecture

lifestyle-related disease

Train lunch

earthen teapot

Akira Toriyama

Fabre

Nobita Nobi8

first-degree equation

Unexpected information
The air-bag was never developed in Japan because using gunpowder was prohibited by
the Fire Defense Law at the time.
The Law for the Protection of Cultural Properties was established because of a fire disaster,and in response, the government designated January 26 as Cultural Property Fire
Prevention Day.
A light pollution problem and its disadvantageous effect on scenery are pointed out.
Kimiko Date is now living in Monaco.
Sumitomo Mitsui Banking has branches in Tokyo Disneyland andTokyo Disney SEA.
In addition to excessive drinking, people consume too much salt from preserved foods
such as pickles, and Akita Prefecture has a high rate of death from lifestyle-relateddiseases such as a stroke.
In 1992, the Japanese Railway Ministry banned the use of earthenware teapots for hygienic
reasons; glass teapots were introduced.
Akira Toriyama designed the cover and frontispiece of “The Insect World of J. Henri Fabre”
that was edited and translated by Daisaburo Okumoto and published by Shueisha.
He solved a difficult first-degree equation “3/8x = 9/10” and got a score of 100.

need to address the problem of removing noise terms. In addition,
we need to consider the credibility of unexpected information especially when we discover unexpected information from more general
Web pages. False or untrue information is not useful. One method
to verify credibility is to check the publisher of the information. If
the unexpected information has been written by an expert in the domain, it is more likely that the information is credible. We intend
to undertake this work in the future.

Acknowledgements
This work was supported in part by the following projects: Grantsin-Aid for Scientific Research (Nos. 24240013, 24680008) from
MEXT of Japan and JSPS KAKENHI Grant Number 243993.

7.

REFERENCES[1] E. Agichtein and L. Gravano. Snowball: extracting relations fromlarge plain-text collections. In Proc. of ACM DL 2000, pages 85–94,
2000.
[2] G. Berger and A. Tuzhilin. Discovering unexpected patterns in
temporal data using temporal logic. In Temporal Databases Researchand Practice, Lecture Notes in Computer Science 1399, pages
281–309, 1998.
[3] S. Brin and L. Page. The anatomy of a large-scale hypertextual web
search engine. In Proc. of WWW 2007, pages 107–117, 1998.
[4] A. Carlson, J. Betteridge, R. C. Wang, E. R. Hruschka, Jr., and T. M.
Mitchell. Coupled semi-supervised learning for information
extraction. In Proc. of ACM WSDM 2010, pages 101–110, 2010.
[5] M. Craven, D. DiPasquo, D. Freitag, A. McCallum, T. Mitchell,
K. Nigam, and S. Slattery. Learning to construct knowledge bases
from the world wide web. Artif. Intell., 118(1-2):69–113, 2000.
[6] H. Deng, M. R. Lyu, and I. King. A generalized Co-HITS algorithm
and its application to bipartite graphs. In Proc. of ACM SIGKDD
2009, pages 239–248, 2009.
[7] O. Etzioni, M. Cafarella, D. Downey, S. Kok, A.-M. Popescu,
T. Shaked, S. Soderland, D. S. Weld, and A. Yates. Web-scale
information extraction in knowitall: (preliminary results). In Proc. of
WWW 2004, pages 100–110, 2004.
[8] Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen. Combating web
spam with trustrank. In Proc. of VLDB 2004, pages 576–587, 2004.
[9] T. H. Haveliwala. Topic-sensitive pagerank. In Proc. of WWW 2002,
pages 517–526, 2002.
[10] K. Järvelin and J. Kekäläinen. Cumulated gain-based evaluation of ir
techniques. ACM Trans. Inf. Syst., 20(4):422–446, 2002.

Table 5: The number and the ratio of theme terms that could
find unexpected information.
Category
PersonRegionProduct
Facility
Organization

Over 150
60% (6/10)
30% (3/10)
50% (5/10)
40% (4/10)
20% (2/10)

Under 150
60% (3/5)
0% (0/5)
40% (2/5)
0% (0/5)
20% (1/5)

Total
60% (9/15)
20% (3/15)
47% (7/15)
27% (4/15)
20% (3/15)[11] J. M. Kleinberg. Authoritative sources in a hyperlinked environment.
J. ACM, 46:604–632, September 1999.
[12] B. Liu, Y. Ma, and P. S. Yu. Discovering unexpected informationfrom your competitors’ web sites. In Proc. of ACM SIGKDD 2001,
pages 144–153, 2001.
[13] A. Nadamoto, E. Aramaki, T. Abekawa, and Y. Murakami. Searchingfor important but neglected content from community-type-content. In
Proc. of SITIS 2008, pages 161–168, 2008.
[14] A. Nadamoto, E. Aramaki, T. Abekawa, and Y. Murakami. Content
hole search in community-type content. In Proc. of WWW 2009,
pages 1223–1224, 2009.
[15] Y. Noda, Y. Kiyota, and H. Nakagawa. Discovering serendipitous
information from wikipedia by using its network structure. In Proc.
of ICWSM 2010, pages 299–302, 2010.
[16] B. Padmanabhan and A. Tuzhilin. A belief-driven method for
discovering unexpected patterns. In Proc. of ACM SIGKDD 1998,
pages 94–100, 1998.
[17] B. Padmanabhan and A. Tuzhilin. Small is beautiful: discovering theminimal set of unexpected patterns. In Proc. of ACM SIGKDD 2000,
pages 54–63, 2000.
[18] S. E. Robertson and S. Walker. Some simple effective
approximations to the 2-poisson model for probabilistic weighted
retrieval. In Proc. of ACM SIGIR 1994, pages 232–241, 1994.
[19] T. Sakai. On the properties of evaluation metrics for finding one
highly relevant document. Information and Media Technologies,
2(4):1163–1180, 2007.
[20] K. M. Svore and C. J. Burges. A machine learning approach for
improved BM25 retrieval. In Proc. of ACM CIKM 2009, pages
1811–1814, 2009.
8
Nobita Nobi is a famous cartoon character who is not a good student.