COLING 2016
Osaka, Japan

December 2016__

The Role of Wikipedia in Text Analysis and Retrieval

Marius Paşca
Google Inc.
mars@google.com

Overview• Part One: Wikipedia as a Knowledge Resource• Part Two: Role of Wikipedia in Text Analysis• Part Three: Role of Wikipedia in Information Retrieval

1Part One: Wikipedia as a Knowledge Resource• Knowledge resources• Dissecting Wikipedia• Resources derived from Wikipedia

Knowledge Resources•

Created by experts– [Fel98]: C. Fellbaum. WordNet: An Electronic Lexical Database. MIT Press
1998.
– [Len95]: D. Lenat. CYC: A Large-Scale Investment in Knowledge
Infrastructure. Communications of the ACM 1995.

•

Created collaboratively by non-experts– [Rem02]: M. Remy. Wikipedia: The Free Encyclopedia. Journal of Online
Information Review 2002.
– [SLM+02]: P. Singh, T. Lin, E. Mueller, G. Lim, T. Perkins and W. Zhu. Open
Mind Common Sense: Knowledge Acquisition from the General Public. Lecture
Notes In Computer Science 2002.
– [LS04]: H. Liu and P. Singh. ConceptNet – a Practical Commonsense Reasoning
Tool-Kit. BT Technology Journal 2004.

2

Expert Resources•

WordNet– [Fel98]: C. Fellbaum. WordNet: An Electronic Lexical Database. MIT Press
1998.
– lexical database of English created by experts– wide-coverage of upper-level conceptual hierarchies– replicated or extended to other languages•

Cyc– [Len95]: D. Lenat. CYC: A Large-Scale Investment in Knowledge
Infrastructure. Communications of the ACM 1995.
– knowledge repository of common-sense knowledge created by experts over
100+ person-years– terms and assertions capturing ground assertions and (inference) rules

Collaborative, Non-Expert Resources•

Wikipedia– [Rem02]: M. Remy. Wikipedia: The Free Encyclopedia. Journal of Online
Information Review 2002.
– free online encyclopedia developed collaboratively by Web volunteers•

Open Mind– [SLM+02]: P. Singh, T. Lin, E. Mueller, G. Lim, T. Perkins and W. Zhu. Open
Mind Common Sense: Knowledge Acquisition from the General Public. Lecture
Notes In Computer Science 2002.
– collect common-sense knowledge from non-expert Web users– unlike Cyc, collect and represent knowledge in natural language rather than
through formal assertions•

ConceptNet– [LS04]: H. Liu and P. Singh. ConceptNet – a Practical Commonsense Reasoning
Tool-Kit. BT Technology Journal 2004.
– introduced as a successor to Open Mind, as a semantic network encoding
common-sense knowledge represented through lexical concepts and labeled
relations– knowledge sources include Open Mind, Wikipedia, WordNet

3

Part One: Wikipedia as a Knowledge Resource• Knowledge resources• Dissecting Wikipedia• Resources derived from Wikipedia

Wikipedia on Wikipedia

4

Dissecting Wikipedia Articles
Textualcontent

Infoboxes
Prominent
properties(attributes)
and values

5Language Versions(wikipedia.org)

Articlesin otherlanguages

Links to Other Articles

Outgoing internal links pointing
to other Wikipedia articles

6Categories

Category Pages

7

Category Network

Category network• Edges from articles to their parent categories, and fromcategories to their own parent categories

Disambiguation Pages

8

Connecting Phrases to Articles(Not) Connecting Phrases to (Missing) Articles

(

)

9

Part One: Wikipedia as a Knowledge Resource• Knowledge resources• Dissecting Wikipedia• Resources derived from Wikipedia

Knowledge Resources•

Derived from Wikipedia– [BLK+09] C. Bizer, J. Lehmann, G. Kobilarov, S. Auer et al. DBpedia – A
Crystallization Point for the Web of Data. Journal of Web Semantics 2009.
– [BEP+08]: K. Bollacker, C. Evans, P. Paritosh et al. Freebase: A Collaboratively
Created Graph Database for Structuring Human Knowledge. SIGMOD-08.
– [VK14]: D. Vrandecic and M. Krotzsch. Wikidata: A Free Collaborative
Knowledgebase. Communications of the ACM 2014.

10

Deriving from Wikipedia
Compositional topic

Compositional article

Next Part• Part One: Wikipedia as a Knowledge Resource• Part Two: Role of Wikipedia in Text Analysis• Part Three: Role of Wikipedia in Information Retrieval

11Role of Wikipedia in Text Analysis
Methods for:...
• coreference resolution• word sense disambiguation• entity disambiguation and linking• information extraction...

Role of Wikipedia in Text Analysis•[PS06]: S. Ponzetto and M. Strube. Exploiting Semantic Role Labeling, WordNet andWikipedia for Coreference Resolution. HLT-NAACL-06.

•[Mih07]: R. Mihalcea. Using Wikipedia for Automatic Word Sense Disambiguation. NAACLHLT-07.

•[PS07]: S. Ponzetto and M. Strube. Deriving a Large Scale Taxonomy from Wikipedia. AAAI07.

•[WW07]: F. Wu and D. Weld. Autonomously Semantifying Wikipedia. CIKM-07.

•[SKW07]: F. Suchanek, G. Kasneci and G. Weikum. Yago: a Core of Semantic Knowledge
Unifying WordNet and Wikipedia. WWW-07.

•[WW08]: F. Wu and D. Weld. Automatically Refining the Wikipedia Infobox Ontology.
WWW-08.

•[NS08]: V. Nastase and M. Strube. Decoding Wikipedia Categories for Knowledge
Acquisition. AAAI-08.

•[SSW09]: F. Suchanek, M. Sozio and G. Weikum. Sofie: A Self-Organizing Framework for
Information Extraction. WWW-09.

–

–

–
–

–

–

–

–

determine the relative and combined impact in the task of coreference resolution, for featuresderived from different resources

over a small evaluation set, validate the hypothesis that manually-created mappings from Wikipedia
articles to corresponding WordNet synsets can improve the outcome of word sense disambiguation

apply filters to network of Wikipedia categories to extract hierarchy of categories
extend Wikipedia infoboxes with attributes and values inferred from text

map Wikipedia categories to WordNet to generate hybrid resource of concepts and relations

extend Wikipedia infoboxes with additional attributes and values, by mapping templates of Wikipedia
infoboxes to WordNetfrom categories and category network, derive relations among categories or instances, including
attributes of categories

extend existing repositories of relations like Wikipedia, with facts acquired from unstructured text12Role of Wikipedia in Text Analysis•[YTK+09]: I. Yamada, K. Torisawa, J. Kazama, K. Kuroda, M. Murata, S. De Saeger, F. Bondand A. Sumida. Hypernym Discovery Based on Distributional Similarity and Hierarchical
Structures. ACL-IJCNLP-09.
–•[YOM+09]: Y. Yan, N. Okazako, Y. Matsuo et al. Unsupervised Relation Extraction by Mining
Wikipedia Texts Using Information from the Web. ACL-IJCNLP-09.
–•

extract IsA pairs from Web documents, by using lexico-syntactic patterns and distributional
similarities, and attach extracted pairs to Wikipedia categories

identify relevant relations for Wikipedia categories, from parsed Wikipedia articles and from Web
documents via search engines[PN09]: S. Ponzetto and R. Navigli. Large-Scale Taxonomy Mapping for Restructuring andIntegrating Wikipedia. IJCAI-09.
–

map Wikipedia categories to WordNet synsets, and use mappings to restructure the hierarchy
generated in [PS07]•[BZ10]: R. Blanco and H. Zaragoza. Finding Support Sentences for Entities. SIGIR-10.

•[WW10]: F. Wu and D. Weld. Open Information Extraction Using Wikipedia. ACL-10.

•[NP10]: R. Navigli and S. Ponzetto. BabelNet: Building a Very Large Multilingual Semantic
Network. ACL-10.

•[TP10]: P. Talukdar and F. Pereira. Experiments in Graph-Based Semi-Supervised Learning
Methods for Class-Instance Acquisition. ACL-10.

–
–

–

–

loosely identify the relation between given a query and a given instance, in the form of explanatory
sentences collected from Wikipedia articles
from unstructured text, extract relations whose types are derived from Wikipedia

link Wikipedia articles to WordNet concepts and apply machine translation, to create a multi-lingual
repository of relations

extract IsA pairs from manually-created or automatically-extracted repositories, via graphpropagation, by incorporating structured data derived from Wikipedia

Role of Wikipedia in Text Analysis•[RRD+11]: L. Ratinov, D. Roth, D. Downey and M. Anderson. Local and Global Algorithms for
Disambiguation to Wikipedia. ACL-11.

•[RR12]: L. Ratinov and D. Roth. Learning-based Multi-Sieve Co-reference Resolution with
Knowledge. EMNLP-CoNLL-12.

•[HSB+13]: J. Hoffart, F. Suchanek, K. Berberich and G. Weikum. YAGO2: a Spatially andTemporally Enhanced Knowledge Base from Wikipedia. Artificial Intelligence 2013.

•[FVP+14]: T. Flati, D. Vannella, T. Pasini and R. Navigli. Two Is Bigger (and Better) Than One:the Wikipedia Bitaxonomy Project. ACL-14.

•[DGH+14]: X. Dong, E. Gabrilovich, G. Heitz, W. Horn, N. Lao and K. Murphy. Knowledge Vault:
A Web-Scale Approach to Probabilistic Knowledge Fusion. KDD-14.

•[VMT+15]: N. Voskarides, E. Meij, M. Tsagkias, M. de Rijke and W. Weerkamp. Learning toExplain Entity Relationships in Knowledge Graphs. ACL-15.

–

–

–

–

–

–

compare the impact of algorithms for disambiguating instances mentioned in a document relative toarticles in Wikipedia, using evidence available locally for each mention vs. globally for all mentions

improve coreference resolution via context-sensitive disambiguation of mentions in text tocorresponding Wikipedia articles

combine WordNet, Wikipedia and other sources into hierarchically organized instances and theirrelations, where the data is anchored in time and spacefrom network of Wikipedia articles and Wikipedia categories, extract hierarchy of articles andcategories

create a knowledge repository, based on relations extracted from Web documents and knowledge
from available repositories

from Web documents, extract textual descriptions of relations between entries in pairs of entries
from a knowledge repository

13

Role of Wikipedia in Text Analysis•[BM16] S. Banerjee and P. Mitra. WikiWrite: Generating Wikipedia Articles
Automatically. IJCAI-16.
–•

given a new topic not already in Wikipedia, generate a new article whose sections are derived fromsections of existing topics similar to the new topic, and filled in with summaries of Web text
fragments[RBN16] A. Raganato, C. Delli Bovi and R. Navigli. Automatic Construction and Evaluation of a
Large Semantically Enriched Wikipedia. IJCAI-16.
–

create links between mentions within Wikipedia articles not already linked, and their corresponding
Wikipedia articles

Coreference Resolution•[PS06]: S. Ponzetto and M. Strube. Exploiting Semantic Role Labeling,
WordNet and Wikipedia for Coreference Resolution. HLT-NAACL-06.

14

Semantic Features for Coreference
•

Input

•

Data sources– discourse entities and possibly referring expressions in documents
–
–
–
–

•

collection of documents annotated with coreference chains
WordNetcollection of articles from Wikipedia
category network in Wikipedia, containing edges from articles to theirparent categories, and from categories to their own parent categories

Output– coreference chains linking referring expressions and discourse entities towhich they refer

•

Steps
– besides lexical, grammatical and distance features, collect features from
output of semantic role labeler applied to documents; from WordNet; andfrom Wikipedia– exploit features in classifying pairs of possibly coreferring expressions as
being coreferent or not

Referring Expressions

But frequent visitors say that given the sheer weight ofthe country ’s totalitarian ideology and generations of massindoctrination, changing this country ’s course will be something
akin to turning a huge ship at sea. Opening North Korea up,even modestly, and exposing people to the idea that
Westerners – and South Koreans – are not devils, alone
represents an extraordinary change. [...] as his people begin to
get a clearer idea of the deprivation they have suffered,especially relative to their neighbors. This is a society thathas been focused most of all on stability, [...].

15

Coreference Chains

But frequent visitors say that given the sheer weight ofthe country ’s totalitarian ideology and generations of massindoctrination, changing this country ’s course will be something
akin to turning a huge ship at sea. Opening North Korea up,even modestly, and exposing people to the idea that
Westerners – and South Koreans – are not devils, alone
represents an extraordinary change. [...] as his people begin to
get a clearer idea of the deprivation they have suffered,especially relative to their neighbors. This is a society thathas been focused most of all on stability, [...].

Finding Coreference Chains(Courtesy S. Ponzetto)

16Evidence from Semantic Role Labeling•

Features: semantic role argument-predicate pairs of the referring
expressions

Evidence from WordNet•

Features: largest, averagesimilarity score among allpairs of WordNet synsets
to which pair of referring
expressions belong•

Based on path length:sim(car, auto) = 1
sim(car, bike) = 0.25

17

Evidence from Wikipedia•

Features from pairs of Wikipedia articles, if any, retrieved for the two
referring expressions– feature: whether first paragraph of the article of one expression contains
the other expression– feature: whether an outgoing internal link of the article of one expression isan article that contains the other referring expression– feature: whether categories of the article of one expression contain theother expression as an article– feature: ngram overlap score between first paragraphs of the articles of
the two expressions

Evidence from Wikipedia•

Relatedness among Wikipedia articles– path length, via ancestor categories,
between Wikipedia articles•

Features from Wikipedia category network– features: largest, average relatedness score18

Relative and Combined Contribution• Evaluation set of ACE news documents
Method

R

P

F1

Ap

Acn

Apn

Baseline

54.5

88.0

67.3

34.7

20.4

53.1

+SRL

56.3

88.4

68.8

35.6

28.5

49.6

+WordNet

56.7

87.1

68.6

34.8

26.0

50.5

+Wikipedia

55.8

87.5

68.1

38.9

21.6

51.7

(All)

61.0

84.2

70.7

38.9

29.9

51.2

(A=accuracy rate; p=pronouns; cn=common nouns; pn=proper nouns)

Word Sense Disambiguation•[Mih07]: R. Mihalcea. Using Wikipedia for Automatic Word Sense
Disambiguation. NAACL-HLT-07.

19

Wikipedia in Word Sense Disambiguation
•

Input

•

Data sources– ambiguous words in documents– collection of documents annotated with word senses– WordNet– collection of articles from Wikipedia•

Output•Steps– disambiguation of words into WordNet synsets– for a small set of ambiguous words, manually create mappings from
Wikipedia articles that likely capture possible senses of the words, and
WordNet synsets– based on the mappings, collect additional features to disambiguate theambiguous words as they occur in documents

Mappings from Wikipedia to WordNet•

For a given word of interest:

Titles of Wikipedia articles
pointed to from anywhere within
Wikipedia, where the anchor textof the pointing link is the word

Definition from
Wikipedia
disambiguation pageof the word

Manually selected
WordNet synset
corresponding toWikipedia article

Word
Sense

Labels in
Wikipedia

Wikipedia definition

WordNet definition

bar(counter)bar (counter)the counter from which
drinks are dispensed

a counter where you can obtainfood or drink

bar(music)bar (music),
measure music,
musical notationa period of music

musical notation for a repeating
pattern of musical beats

bar(landform)bar (landform)a type of beach behind
which lies a lagoon

a submerged (or partly
submerged) ridge in a river oralong a shore(Courtesy R. Mihalcea)

20

Word Sense Disambiguation via Wikipedia•

Set of 30 nouns with at least two WordNet senses for Wikipedia labels

Number of senses

Most frequent sense

Number of examples

Lesk corpus

Wikipedia vs. WordNet•

Comparison of Senseval word senses vs. Wikipedia word senses

Documents annotatedwith WordNet synsets

21

Entity Disambiguation and Linking•[RRD+11]: L. Ratinov, D. Roth, D. Downey and M. Anderson. Local andGlobal Algorithms for Disambiguation to Wikipedia. ACL-11.

Disambiguation to Wikipedia•

Task– given a text fragment containing mentions (substrings) to be disambiguated,“wikifi” the mentions by identifying the Wikipedia article, if any,corresponding to each mention– mapping from mentions to Wikipedia articles relies on evidence available in
the text fragment•

Scope of available evidence– local: separately available for each mention in the text fragment– global: collectively available for all mentions in the text fragment•

Goal– investigate impact of local vs. global evidence on accuracy of disambiguation22

Mapping Mentions to Wikipedia
It’s a version of Chicago – thestandard classic Macintosh menu
font, with that distinctive thickdiagonal in the “N”

Chicago was used by default for
Mac menus through MacOS 7.6,
and OS 8 was released mid-1997

Chicago VIII was one of the early70s-era Chicago albums to catchmy ear, along with Chicago II

Text fragment
Disambiguation
Wikipedia article

is-a

is-a
released

releasedused-in

Links amongarticles within
Wikipedia

successor-of(Courtesy L. Ratinov)46

Disambiguation Strategy• Two stages– ranker: compute best Wikipedia article that potentiallydisambiguates the mention– linker: determine whether the mention should be mapped to the
Wikipedia article or should not be mapped to any article

23

Ranker: Local vs. Global Disambiguation
Accuracy: fraction of mentions for which ranker identifies correct disambiguation
DatasetBaseline

ACE

Baseline+
LexicalBaseline+
GlobalUnambiguous

Baseline+
GlobalNER

Baseline+
Global, All
Mentions

94.05

94.56

96.21

96.75

MSNBC News

81.91

84.46

84.04

88.51

AQUAINT

93.19

95.40

94.04

95.91

Wikipedia Test

85.88

89.67

89.59

89.79

Previous methods

Ranker: Local vs. Global Disambiguation
Accuracy: fraction of mentions for which ranker identifies correct disambiguation
DatasetBaseline

Baseline+
LexicalBaseline+
GlobalUnambiguous

ACE

94.05

96.21

96.75

MSNBC News

81.91

85.10

88.51

AQUAINT

93.19

95.57

95.91

Wikipedia Test

85.88

93.59

89.79

Local disambiguation

Baseline+
GlobalNER

Baseline+
Global, All
Mentions

Global disambiguation

Over test set of Wikipedia
documents, local performs
better than global

24Overall: Local vs. Global Evidence
Combined precision and recall (F1 score)
DatasetBaseline

Baseline+
LexicalBaseline+
Lexical+Global

ACE

94.05

96.21

97.83

MSNBC News

81.91

85.10

87.02

AQUAINT

93.19

95.57

94.38

Wikipedia Test

85.88

93.59

94.18

(Comparing set of Wikipedia articles output by algorithm for a
document, with gold set of Wikipedia articles for the document)

Role of Wikipedia in Text Analysis
Methods for:...
• coreference resolution• word sense disambiguation• entity disambiguation and linking• information extraction...

25

Information Extraction•[TP10]: P. Talukdar and F. Pereira. Experiments in Graph-Based SemiSupervised Learning Methods for Class-Instance Acquisition. ACL-10.

Graph-Based Assignment of Class Labels
Edge weightSet of three instances(e.g., from same table
column)bob dylan

0.95

Set 1

0.87
0.82

musician 1.0

johnny cash
musician 1.0

0.73

Set 2
musician 1.0

0.75
Set of two instances(e.g., produced by IsA
patterns over text)

musician 1.0

billy joel
musician 1.0

Seed label
Predicted label(Courtesy P. Talukdar)

26

Graph-Based Assignment of Class Labels(Newly) predicted label

bob dylan

0.95

Set 1
(iter 1)

0.87

musician 0.8
0.82(iter 2)musician 1.0(iter 0)musician 1.0(iter 0)musician 1.0(iter 0)musician 1.0(iter 0)johnny cash
0.73

Set 2
(iter 0)musician 0.6

musician 1.0
0.75

billy joel

Incorporating Semantic Constraints

bob dylan

0.95

Set 1
0.82

Set 2

has-attribute:
albums0.87

johnny cash
0.73

0.75

Structured data derived
from Wikipedia

billy joel27

Extracted Class Labels• Input data = graphs derived from existing sources• Evaluate lists of class labels assigned to instances: mean
reciprocal rank of gold class labels
SourceDerived Graph
Vertices

Edges

Freebase-1

32K

957K

Freebase-2

301K

2310K

TextRunner

175K

529K

Yago

142K

777K

TextRunner+Yago

237K

1307K

(LP-ZGL, Adsorption = earlier methods)(Courtesy P. Talukdar)

Information Extraction•[PS07]: S. Ponzetto and M. Strube. Deriving a Large Scale Taxonomy
from Wikipedia. AAAI-07.

28

Hierarchy of Wikipedia Categories•

Input– category network in Wikipedia, containing edges from articles to theirparent categories, and from categories to their own parent categories• e.g., Semantic relatedness belongs to the categories Statistical distance measures
and Computational linguistics; Statistical distance measures belongs to thecategory Statistics•

Data sources– collection of text documents– collection of Wikipedia articles•

Output– hierarchy of Wikipedia categories• e.g., [Computer scientists IsA Scientists, Caffeine IsA Stimulant,...] organizedhierarchically

•

Steps
– apply various types of filters to network of categories, to identify IsA (vs.
non-IsA) relations among the pairwise category relations

Filters•

Category network cleanup•

Identification of refinement links––•

mark meta-categories (e.g., Disambiguation pages, Weather templates) as non-IsA links
identify links from category Y X (e.g., French cuisine) to category X by Z (e.g., Cuisine
by Nationality) as refinement links, and mark them as non-IsA links

Syntactic matching (head of category, modifier of category)––mark links from category Y X (e.g., British computer scientists) to category Z X (e.g.,
Computer scientists) as IsA links
mark links from category X Y (e.g., Islamic dress) to category Z X, where Z is optional(e.g., Islam) as non-IsA links•

Connectivity checking•

Lexico-syntactic matching

–
–
–
–

•

mark links from any leaf (non-category) article to a category as IsA links
identify links from category X to category Y, where Y and X occur in text documents in
one of a few PartOf patterns (e.g., Y’s X, Y with X)
identify links from category X to category Y, where Y and X occur in text documents in
one of a few IsA patterns (e.g., Y such as X)
if PartOf patterns occur less frequently than IsA patterns, then mark links fromcategory X to category Y as IsA links, otherwise as non-IsA links

Transitivity checking–

if link from category X to category Y was marked as IsA link, and link from category Y
to category Z was marked as IsA link, then mark link from category X to category Z as
IsA link

29

Filters
Category networkfrom Wikipedia
Text documents

388K links

515K links

228K non-IsA links
Syntactic(head, modifier)matching

141K IsA links

147K links

Category
networkcleanup

743K links

178K links

67K non-IsA links

127K non-IsA links
Connectivity
checking
31K IsA links

Lexico-syntactic
matching

49K IsA links

3K non-IsA links(of 31K IsA links)

Refinement link
identification

Total: 335K
IsA links
found

Transitivity
checking
28K IsA links(of 31K IsA links)

117K IsA links

Information Extraction•[PN09]: S. Ponzetto and R. Navigli. Large-Scale Taxonomy Mapping for
Restructuring and Integrating Wikipedia. IJCAI-09.

30

Hierarchy Refinement and Restructuring• Input– hierarchy of Wikipedia categories generated in [PS07]• e.g., [Computer scientists IsA Scientists, Caffeine IsA Stimulant,...]
organized hierarchically– hierarchy from WordNet• Output– restructured hierarchy of Wikipedia categories, with categories
mapped to WordNet synsets• Steps– map Wikipedia categories to WordNet synsets– use mappings to restructure hierarchy of Wikipedia categories

Hierarchy Refinement and Restructuring•

Map categories from Wikipedia hierarchy to WordNet synsets– identify sets of candidate WordNet synsets• full match, e.g., category Plants to synsets available for plant• head match, e.g., category Edible plants to synsets available for plant– select best candidate WordNet synsets• e.g., for category Plants, select second synset available for plant (a living organism
lacking the power of locomotion)• equivalent to finding most appropriate sense for Wikipedia category, from senses
available in WordNet• as an alternative to choosing the most frequent of the available WordNet senses•

Use mappings to restructure hierarchy of Wikipedia categories– identify links in Wikipedia hierarchy whose corresponding links in WordNet
hierarchy are the most inconsistent• e.g., [Fruits-->Crops-->Edible plants-->Plants] in Wikipedia hierarchy, but no [fruit->crop] or [fruit-->plant] in WordNet– identify replacements of most inconsistent links, by finding alternative
parent categories• e.g., check for possible replacements of [Fruits-->Crops]31Information Extraction•[FVP+14]: T. Flati, D. Vannella, T. Pasini and R. Navigli. Two Is Bigger(and Better) Than One: the Wikipedia Bitaxonomy Project. ACL-14.

Constructing Hierarchies from Text•

Data source– category network in Wikipedia, containing edges from articles to theirparent categories, and from categories to their own parent categories; also
edges from articles to other articles•

Output– an hierarchy containing IsA edges between Wikipedia articles, and anotherhierarchy containing IsA edges between Wikipedia categories

•

Steps
– analyze the text of each article to select a candidate hypernym phrase forthe article (e.g., character for Mickey Mouse)– disambiguate the hypernym phrase into another article corresponding to thedesired sense of the hypernym phrase (e.g., character into Character (arts))– organize pairs of an article and its disambiguated hypernym article into
hierarchy of articles– starting from the hierarchy of articles (e.g., Real Madrid IsA Football club),
exploit Wikipedia edges between articles and categories to iteratively infer
IsA edges between categories of articles (e.g., Football clubs in Madrid IsA
Football clubs), and then IsA edges between articles of categories (e.g.,
Atletico Madrid IsA Football club)– expand the hierarchy of categories to increase its coverage

32Edges in Category Network
Wikipedia categories

Wikipedia articles
is a

CartoonMickey Mouse

is a

Fictional
characters

Donald Duck

The Walt Disney
Fictional characters
Company
by medium

is a

is a
Disney comics

Disney character

Funny Animal

Comics bygenre

Superman

Disney comics
characters(Courtesy T. Flati)

Constructing Hierarchy of Articles•

Select main (first) sentence in article(Courtesy T. Flati)•

From the dependency parse of main sentence, select candidate
hypernym phrasesnsubj
nnScrooge McDuck isHypernym phrase:
Scrooge McDuck is a character[…]a character […]charactercop•

Using heuristics, disambiguate the hypernym phrase into another article
corresponding to the desired sense– heuristics rely on links among articles, common categories, context aroundlinks

Hypernym phrase: character•

Character (arts)

Retain pairs of an article and its hypernym article, as IsA edges
Scrooge McDuck
Character (arts)

33

Constructing Hierarchy of Categories
Football teamReal Madrid
F.C.

Atletico
MadridFootballteams

Football clubs(Courtesy T. Flati)

Wikipedia articles

Football clubs
in Madrid

Wikipedia
categories

Start from the hierarchy of articles

Constructing Hierarchy of Categories
Football teamReal Madrid
F.C.

Atletico
MadridWikipedia articles

Footballteams

Football clubs
Football clubs
in Madrid

Wikipedia
categories

Exploit the article to category edges to infer hypernym relations in the
category hierarchy34

Iteratively Refining the Hierarchies
Football teamReal Madrid
F.C.

Atletico
MadridWikipedia articles

Footballteams

Football clubs
Football clubs
in Madrid

Wikipedia
categories

Traverse article to category edges to infer back is-a relations in the hierarchyof articles

Iteratively Refining the Hierarchies
Football teamReal Madrid
F.C.

Atletico
MadridWikipedia articles

Footballteams

Football clubs
Football clubs
in Madrid

Wikipedia
categories

Iteratively use the relations found in previous step to infer new hypernym
edges

35

Expanding the Hierarchy of Categories•

Expand for categories with a single parent category in the category
network
Fictional charactersby medium

Animated characters

This category has
only one parent
category in the
category network

Comics characters

Animation

Animated television
characters byseriesRetain the parent
category as being a
hypernym category

Comics charactersby protagonist

Garfield characters

Expanding the Hierarchy of Categories•

Infer hypernym categories of a category, from hypernym categories
already extracted for child categories in the category network

Comics characters

Comics by company

Comics charactersby company

Marvel Comics
characters

DC Comics
characters

Comics titles
by company

Disney comics

36

Expanding the Hierarchy of Categories•

Infer hypernym categories of a category, from hypernym categories
already extracted for child categories in the category network

Comics characters

Two IsA
edges

Comics by company

Comics charactersby company

Marvel Comics
characters

DC Comics
characters

Comics titles
by company

One IsA
edge

Disney comics

Information Extraction•[WW07]: F. Wu and D. Weld. Autonomously Semantifying Wikipedia.
CIKM-07.

37

Creation and Augmentation of Infoboxes•

Motivation– Wikipedia articles may lack or have incomplete infoboxes– content from an infobox may contradict content from article– similar articles may incorrectly use different infobox templates•

Data source•

Output– collection of articles from Wikipedia– Wikipedia infoboxes extended with inferred attributes and values

Processing Infoboxes(Courtesy F. Wu)

38

Extraction from Wikipedia Articles(Courtesy F. Wu)

Extraction Components•

Preprocessor– identify relevant attributes from articles using the same infobox template– generate training data for classification and extraction•

Document classifier– determine whether an article belongs to a certain class– one classifier per class of articles•

Sentence classifier– determine whether a sentence contains the value of an attribute– one classifier per attribute per infobox template•

Extractors– given a sentence deemed to contain a value, extract the value– aggregate across sentences, return first/multiple values for single/multiplevalued attributes

39

Information Extraction•[NS08]: V. Nastase and M. Strube. Decoding Wikipedia Categories forKnowledge Acquisition. AAAI-08.

Extraction from Wikipedia Categories•

Data source•

Output– Wikipedia category network– relations among categories or instances• e.g., <kind of blue-artist-miles davis>, <deconstructing harry-directed-by-woody
allen>– ... including attributes of categories• e.g., {band, community, ethnicity, genre, instrument, language, region, ...} forMusician– filter the category network and analyze the categories– extract relations from categories, by matching category names to predefined patterns– extract attributes from categories, by matching category names to predefined patterns

40Extraction from Wikipedia Categories• Match category name with patterns identifying either a relation
and a category, or a relation and two categories• Given matches and the category network, derive relations

chancellors of Germany, members of
the European Parliament, Queen(band) members, ...
Cx, Cy = categories; P1, P2, ..., Pn = pages (articles)
villages in Brandenburg, movies
directed by Woody Allen, ...

(Courtesy V. Nastase)

Extraction of Labeled Relations

Queen (band) members

John
Roger
Deacon Taylor

Movies directed by Woody Allen

Annie Hall

The Scoop

Deconstructing Harry…

member ofFreddy Brian
Mercury May

Queen (band)

Freddy Brian
Mercury May

John
Roger
Deacon Taylor

MoviesWoody Allenisa

directed by

Annie Hall

The Scoop

Deconstructing Harry…

41

Extraction of Unlabeled Relations• Category name: mixed martial arts television programs

Information Extraction•[VMT+15]: N. Voskarides, E. Meij, M. Tsagkias, M. de Rijke and W.
Weerkamp. Learning to Explain Entity Relationships in Knowledge
Graphs. ACL-15.

42

From Relations to Explanatory Sentences•

Input– pairs of instances connected by a relation, as available in a knowledge
repository (e.g., the pair Brad Pitt, Seven (1995 movie))•

Data source– Wikipedia articles corresponding to instances from the knowledge repository•

Output– ranked list of sentences extracted from documents, which explain therelations within the pairs of instances (e.g., “Brad Pitt gave criticallyacclaimed performances in the crime thriller Seven”)

•

Steps
– extract surface forms for each instance in a pair of instances (e.g., Brad
Pitt, Brad, Pitt)– extract candidate sentences from Wikipedia articles, using both surface
forms and instances to which surface forms are disambiguated– rank candidate sentences using a variety of features

Ranking Candidate Sentences•

Textual features– length of candidate sentence– fractions of sentence tokens that are verbs vs. nouns vs. adjectives
– ...

•

Instance features– count of instances in candidate sentence– distance in tokens between last match of the two input instances in thecandidate sentence
– ...

•

Relation features– whether candidate sentence contains tokens of the input relation
– ...

•

Document features– position of candidate sentence in source document– whether the source document of the candidate sentence is the article ofone of the two input instances
– ...

43

Accuracy of Explanatory Sentences(Courtesy N. Voskarides)

Normalized
discounted
cumulative
gain

Prior document
retrieval method
developed
specifically for
sentence retrieval

Proposed ranking
method with one
combined ranking
model for all
relation types

Proposed ranking
method withseparate ranking
models for eachrelation type

At least one of theretrieved sentences
contain a sentenceof the indicatedrelevance bucket

Next Part• Part One: Wikipedia as a Knowledge Resource• Part Two: Role of Wikipedia in Text Analysis• Part Three: Role of Wikipedia in Information Retrieval

44

Role of Wikipedia in Information Retrieval
Methods for:...
• Document analysis and understanding• Query analysis and understanding• Onebox search results...

Role of Wikipedia in Information Retrieval•[Cuc07]: S. Cucerzan. Large-Scale Named Entity Disambiguation Based on Wikipedia Data.
EMNLP-07.

•[HWL+09]: J. Hu, G. Wang, F. Lochovsky, J. Sun and Z. Chen. Understanding User’s QueryIntent with Wikipedia. WWW-09.

•[PF11]: P. Pantel and A. Fuxman. Jigs and Lures: Associating Web Queries with Structured
Entities. ACL-11.

•[SMF+12]: U. Scaiella, A. Marino, P. Ferragina and M. Ciaramita. Topical Clustering of Search
Results. WSDM-12.

•[FS12]: P. Ferragina and U. Scaiella. Fast and Accurate Annotation of Short Texts with
Wikipedia Pages. IEEE Software, vol. 29, 2012.

•[HMB13]: L. Hollink, P. Mika and R. Blanco. Web Usage Mining with Semantic Analysis.
WWW-13.

–

–

–

–

–

–

disambiguate instances mentioned in a document relative to articles in Wikipedia, using evidence
available in the form of local context for each mention

model query intent domains as areas in the Wikipedia category network situated around manuallyprovided seed articles in Wikipedia, and map queries into those domains

compute mappings from queries into instances from a structured database, for the purpose ofidentifying relevant products from a product catalog and recommending them in response to queries

take advantage of mappings from instances mentioned in documents to Wikipedia articles, in order tocluster search results and their result snippets into sets associated with descriptive labels

disambiguate mentions in short text fragments to their Wikipedia articles, by scoring candidates of agiven mention higher, if they are more strongly related to candidates of other mentions

compute mappings from query fragments into instances from an existing knowledge repository, tobetter identify patterns of Web usage

45

Role of Wikipedia in Information Retrieval•[YV14]: X. Yao and B. Van Durme. Information Extraction over Structured Data: Question
Answering with Freebase. ACL-14.

•[DAD14]: J. Dalton, J. Allan and L. Dietz. Entity Query Feature Expansion using Knowledge
Base Links. SIGIR-14.

•[BMH+15]: B. Bi, H. Ma, B. Hsu, W. Chu, K. Wang and J. Cho. Learning to Recommend Related
Entities to Search Users. WSDM-15.

•[BOM15]: R. Blanco, G. Ottaviano and E. Meij. Fast and Space-Efficient Entity Linking inQueries. WSDM-15.

–

–

–

–

•

compute mappings from query fragments into instances from an existing knowledge repository, toexpand queries for better search results

given a query, compute and recommend related entries from a knowledge repositorycompute mappings from query fragments into instances from an existing knowledge repository, understrong latency constraints[CFC+16] M. Cornolti, P. Ferragina, M. Ciaramita, S. Rud and H. Schutze. A Piggyback System
for Joint Entity Mention Detection and Linking in Web Queries. WWW-16.
–•

in response to fact-seeking questions, extract answers from unstructured text from Web documents
and from relations available in a knowledge repository

link mentions within queries to corresponding Wikipedia articles by jointly exploiting evidence
available for multiple, co-occurring mentions being disambiguated[GGL+16] O. Ganea, and M. Ganea, A. Lucchi, C. Eickhoff and T. Hofmann. Probabilistic BagOf-Hyperlinks Model for Entity Linking. WWW-16.
–

link mentions within documents to corresponding Wikipedia articles by jointly exploiting evidence
available for multiple, co-occurring mentions being disambiguatedRole of Wikipedia in Information Retrieval•[RXC+16] M. Rizoiu, L. Xie, T. Caetano and M. Cebrian. Evolution of Privacy Loss in Wikipedia.
WSDM-16.
–•[SF16] A. Sil and R. Florian. One for All: Towards Language Independent Named Entity
Linking. ACL-16.
–•

recover privacy-sensitive traits of human contributors to Wikipedia, from their editing contributions
over time

based on evidence from one language edition of Wikipedia, link mentions within documents tocorresponding articles in a variety of language editions of Wikipedia[XRF16] K. Xu, S. Reddy, Y. Feng, S. Huang and D. Zhao. Question Answering on Freebase via
Relation Extraction and Textual Evidence. ACL-16.
–

in response to fact-seeking questions, extract candidate answers from relations available in aknowledge repository and filter the candidates using evidence from unstructured text within
Wikipedia

46

Document Understanding•[FS12]: P. Ferragina and U. Scaiella. Fast and Accurate Annotation of
Short Texts with Wikipedia Pages. IEEE Software 2012.

Linking in Short Text Fragments
•

Input

•

Data source•

Output– short fragment of text
– Wikipedia articles and categories, connected via the category network– disambiguation of relevant mentions in text to their corresponding Wikipedia
articles•Steps– identify candidate mentions in text fragment– score candidate Wikipedia articles of a given mention higher, if they are
more strongly related to candidate articles of other mentions– select highest-scoring Wikipedia article of a given mention, as candidate
annotation of the mention– possibly discard the candidate annotation, if the anchor text is usually notlinked within Wikipedia, or the candidate annotation is not coherent withcandidate annotations selected for other mentions

47

Disambiguating Mentions in Text
Diego Maradona won against Mexico
Mexico’s football teamex-Argentina’s football player

Linking Mentions in Text to Wikipedia
Topics: Wikipedia Articles

Entities: Anchor Texts
maradona

Diego
Maradona Jr.
Relatedness: number of common
incoming internal links
Maradona
Movie
Rel(Diego Maradona Jr.,
Diego A. Maradona) ≅ 2

diego maradonadiego armando maradona

Diego A.
Maradona

el pibe de oro
mexicoMexico national
baseball team

Mexico Nation

mexicanmexico national football team
mexican national team

Any Relatedness
between articles
in Wikipedia

Mexico national
football team(Courtesy P. Ferragina)

48

(Result) Document Understanding•[SMF+12]: U. Scaiella, A. Marino, P. Ferragina and M. Ciaramita. Topical
Clustering of Search Results. WSDM-12.

Clustering of Search Results
•

Input

•

Data source•

Output– search results and their snippets, returned in response to queries– Wikipedia articles and categories, connected via the category network– decomposition of search results into topically coherent subsets associatedwith labels derived from Wikipedia– on the fly, without analysis of full content of search results

•

Steps
–
–
–
–

annotate snippets with corresponding Wikipedia articles (“topics”)
analyze graph of snippets and topics, to determine most significant topics
partition graph around most significant topics, and cut into ~10 clusters
for each cluster, select centroid topic as label for the entire cluster

49

Annotation of Snippets with Topics(Courtesy P. Ferragina)
Snippets

Topics

Mappings fromsnippets to topics

Wikipedia articles

Relatedness amongarticles within Wikipedia

Selection of Significant Topics•••

Exploit weights assigned
during annotation tomappings from snippets to
topicsProcess topic nodes
iteratively, in order of thesum of weights ofconnecting edges
As topic nodes are marked
as significant, ignore
corresponding snippet
nodes and their outgoing
mappings in subsequent
iterations

Snippets

Topics50

Selection of Significant Topics

Partition into Clusters

Cluster of topics

51

Selection of Cluster Labels

Label selected
for entire cluster

Role of Wikipedia in Information Retrieval
Methods for:...
• Document analysis and understanding• Query analysis and understanding• Onebox search results...

52

Query Understanding•[HWL+09]: J. Hu, G. Wang, F. Lochovsky, J. Sun and Z. Chen.
Understanding User’s Query Intent with Wikipedia. WWW-09.

Modeling Query Intent with Wikipedia
•

Input

•

Data source•

Output– queries– Wikipedia articles and categories, connected via the category network– intent domains identified for queries, modeled as areas in the Wikipedia
category network situated around manually-provided seed articles in
Wikipedia•

Steps– independently from input queries, manually identify a small set of seed
queries for each domain of interest– given set of seed queries, manually identify seed Wikipedia articles that
correspond to the domain of interest– for each domain, expand seed Wikipedia articles into more Wikipedia
articles, using connections between articles (article links, category network)– map queries into intent domains, taking into consideration manually-provided
mappings from sets of seed queries

53System Architecture

Wikipedia

Query

Labeled seed articles

Query can be mapped directly tosome Wikipedia article?

Wikipedia link graph construction

Map query to Wikipedia articles

Wikipedia articles associated withscores for each intent domain

Set of Wikipedia articles
corresponding to query terms
Query intent

Modeling of Intent Domains• Construct link graph for Wikipedia articles– nodes: Wikipedia articles, Wikipedia categories– edges: links between articles, links in Wikipedia category network
between articles and categories; edges added between two nodes
only when bi-directional links exist between the two nodes– edge weights: counts of links between the two nodes• Associate Wikipedia articles with score for each intent domain– manually select seed Wikipedia articles deemed to belong to intent
domainIntent Type

Examples of Seed Queries# Seed Queries

Traveltravel, hotel, tourism, airline tickets, expedia

2389

Person Namebritney spears, david beckham, george w. bush

10000

Employment

employment, monster, career2543– iteratively propagate intent from seed articles to their neighbors
articles in the link graph, assigning gradually lower intent scores

54

Determining Query Intent• Case 1: query can be mapped directly to a Wikipedia article– retrieve intent domain whose intent score associated with the
Wikipedia article is highest• Case 2: query cannot be mapped directly to a Wikipedia article– map query into its more related Wikipedia articles, by
disambiguating (“wikifying”) mentions (substrings) from query tocorresponding Wikipedia articles– retrieve intent domain for which the combination of intent scores,
associated with the related Wikipedia articles, is highest
Query Top Articles to Which Query is Mapped
employment
vacation
tobyreviews
walkerguide tripadvisor,
employment
fear(film), briangolf
website,resort,froud,
jobconde
clearlakesearchnast
engine,(band),
traveler,annie oakley,sidestep,careerlink,
hotwire.com,
jobkhehunting,sanh (song),
victoria
eluta.ca,bobclipper
types
fass ofairlinetickets,
expediabrave archer,advancedbookingchien-ming
center,
wang,
young
list
personsoflee-feng
cheapfares
chien unemployment,
job builder railcard,
taiwanese
job searchhotwire.com,
people,engine,lists
jobserve,
travelof chinese
falcon’sagency,people,eye, list
priceline,com,
careerbuilder,of taiwanese footballers
kayak.com
eluta.ca, monster (website)

Query Intent
PersonEmployment
TravelName
PersonTravel
Name
Employment

Query Understanding•[BMH+15]: B. Bi, H. Ma, B. Hsu, W. Chu, K. Wang and J. Cho. Learning to
Recommend Related Entities to Search Users. WSDM-15.

55

Recommending Related Instances•

Input– query submitted by a user
– main structured instance, if any, returned by search engine as a side result
for the query•

Data sources– click data for search results returned in response to queries– click data for main instances, if any, returned as side results in response toqueries– collection of instances available within a structured knowledge repository(e.g., Freebase)•

Output– list of instances from knowledge repository deemed relevant to the queryand the main instance, based on click data available for the user
– similar to query suggestion, but suggestions are instances not strings, andsuggestions are for instances rather than queries

•

Steps
– exploit three types of evidence, namely edges between instances withinknowledge repository; edges between main instances in side results andclicked documents; and edges between main instances in side results andclicked related instances in side results– given a main instance, recommend a list of related entities based on theuser’s interests

Main Instance and Related Instanceslincoln movie

SearchMain instance
returned bysearch engine

Related instances(Courtesy B. Bi)

56

Evidence Towards Related Instances

Edges between instances andclicked documents

Edges between instances
within knowledge repository

Edges between instances andclicked related instances inside results

User
ID

Time

Main
entityRelatedentity

Rank

Click

32

7/9/2013
10:32:26

Pacific
Rim

Man of
Steel

1

0

32

7/9/2013
10:32:26

Pacific
Rim

The
Wolverine

2

0

32

7/9/2013
10:32:26

Pacific
Rim

The Lone
Ranger3

1

498

6/16/2013
15:16:41

Leonardo
DiCaprio

Kate
Winslet10498

6/16/2013
15:16:41

Leonardo
DiCaprioJohnnyDepp

2

1

Recommended Instances
Mean reciprocal rank of relevant instance in computed ranked list of related instances

Main instances and recommended
instances are movies

Main instances and recommended
instances are celebrities

Co-click: evidence from user clicks on both main instance and related instance
CTR-model: evidence from click-through rate for related instances being returned
TEM: all sources of evidence57Query Understanding•[HMB13]: L. Hollink, P. Mika and R. Blanco. Web Usage Mining with
Semantic Analysis. WWW-13.

Web Usage Understanding•

Data sources– query sessions including queries and clicked documents– collection of instances available within a structured knowledge repository(Freebase and DBpedia)•

Output•Steps– semantic rather than lexical patterns of Web usage mining– annotate queries, by linking query fragments to corresponding instancesfrom knowledge repository– use properties available for instances within knowledge repository to
generalize and categorize queries into patterns of usage

58

Linking Queries to Instances•

Link queries to instances– from search results returned for site-restricted queries, identify instances
corresponding to queries
moneyball site:wikipedia.org Search(Courtesy L. Hollink)
Query session

Link between
query and instance

Properties of
instance withinknowledge repository•

Generalize from linked queries to query types– using instance types from knowledge repository, generalize queries intoquery types that lead to websites

Patterns of Web Usage•

Estimate the differences in the content of two websites, by comparing
the top query types that lead to clicks on the sites

The first website
specializes in movies,
whereas the second isbroader as it covers
content related to movies,
TV and people

59Patterns of Web Usage•

Compare query patterns obtained by generalizing from queries linked to
instances that are relatively recent movies; vs. instances that are
relatively older movies

vs.

Role of Wikipedia in Information Retrieval
Methods for:...
• Document analysis and understanding• Query analysis and understanding• Onebox search results...

60Retrieval of OneBox Results•[YV14]: X. Yao and B. Van Durme. Information Extraction over
Structured Data: Question Answering with Freebase. ACL-14.

Question Answering as Binary Classification•

Input– natural-language questions (What is the name of the Justin Bieber’s
brother?)•

Data sources– knowledge repository of inter-connected topics (Freebase)– collection of Web documents•

Output•Steps– topics that answer the questions (Jaxon Bieber)– convert the question into a question graph– based on the node from the question graph corresponding to the question
topic (Justin Bieber), assemble a topic graph of inter-connected topics up toa few hops away from the question topic– using individual and combination features from question graph and topic
graph, determine whether each node from the topic graph is or is not ananswer to the question

61

Answers from Knowledge Repositories(Courtesy X. Yao)

Question: What is the name of Justin Bieber’s brother?

Answers from Knowledge Repositories

who

brother

who

who

Question: What is the name of Justin Bieber’s brother?

62

Question Answering as Classification

is answer?

is answer?

is answer!

is answer?

Question: What is the name of Justin Bieber’s brother? Answer: Jaxon Bieber

Features for Classification
Features fromknowledge repository

Features from dependency
parse trees of questions

63

Features for Classification
Features fromknowledge repository

Features from dependency
parse trees of questions

Combined features from knowledge
repository and questions

Estimated Utility of Features64

Mapping Relations to Phrases•

Align relations from knowledge repository to phrases that may express
the relations in document sentences– film/starring (Gravity, Sandra Bullock)vs.

•– Sandra then was cast in Gravity, a two actor spotlight film
– Sandra Bullock plays an astronaut hurtling through space in new
blockbuster "Gravity“– Sandra Bullock stars/acts in Gravity– Sandra Bullock conquered her fears to play the lead in Gravity
Use alignments to predict relevant relations when answering questions

65