Background

Automatic Extraction of
Attribute Relations
from Text

Efficient Information Access tovast amounts of text data on theWeb and in encyclopedias andnewspapers
Newspaper

Computational Linguistics Lab.
Tetsuro TAKAHASHIThe Internet

When isHalloween?
Encyclopedia

2004/11/25

COE technical presentation

12

Background

Motivation

Online strategy vs. Offline strategy
Newspaper

Offline QA strategy[Fleischman et al.03, Lin and Katz03]
Types of users’ questions quantitatively obey
Zipf's Law.

The Internet
Online QAsystem

A small fraction of question types accounts for asignificant portion of all question instances.

Encyclopedia

frequency

ft×f =CName
Object 1
Object 2

CreateDate
1/1/1
1/1/1

Mod.
Date
2/2/2
2/2/2

Object 3

1/1/1

2/2/2

Object 4

1/1/1

2/2/2

Object 5

1/1/1

2/2/2

Object 6

1/1/1

2/2/2

Object 7

1/1/1

2/2/2

Summary

Offline QA
systemTest Object
Test Object
Test Object
Test Object
Test Object
Test Object
Test Object

Object 8

1/1/1

2/2/2

Test Object

Object 9
Object 10
Object 11

1/1/1
1/1/1
1/1/1

2/2/2
2/2/2
2/2/2

Test Object
Test Object
Test Objectt3Motivation

type of queries

4

Attribute Relations
Objectives

Offline QA strategy

Extract attribute relation triplets(Object, Attribute, Value) from text

Analysis of questions in QAC2
40% (79/200) of questions asked about
Attribute Relations

Newspaper

石ノ森章太郎さんの出身地はどこですか？

Ishinomori Shotaro

birthplace

5(Object，Attribute，Value)(Torino，population，2.2 million)(Akashi-Kaikyo-Bridge，length，3910m)(Japan subway，parent company，suntory)：6

Related Work

Related Work

Pattern + Bootstrapping

Pattern + Bootstrapping

Extracts domain specific words andpatterns (Brin98, Riloff99)known answer

perpetrator: Akudamantarget:power tower
:
:

top 5

Extracts domain specific words andpatterns (Brin98, Riloff99)

known answer

domain specificdictionary

perpetrator: Akudamantarget:power tower::

YattaKing

ZendaLion

corpus:corpusdomain specificdictionary
YattaKing

ZendaLion

corpus:This approach cannot
extract“... Doronbo bomb
against YattaKing ...”
arbitrary relation type“... Doronbo bomb
against YattaKing ...”

corpuspatternbomb against <target>:“... they bomb against
power tower ...”top 5

patternbomb against <target>:“... they bomb against
power tower ...”
78Related WorkApproach

Machine Learning

Proposed approach

extracts answer candidates using
patterns
Predicts answer by supervisedmachine learning

Extract triplet using abstracted
patterns
Filter out noise using a statisticalmeasure(Zelenko02, Fleischman03）

Training data is required foreach type of attribute relation

Birthday： X is born on Y
Author： author of X is Y

X is Z on Y
Z of X is Y

Score(O,A,V) = Score(Mt.Fuji，height，3776m)
910ApproachOverview

Score(O, A, V ) = SOA (O, A) × SV A (V, A)

Estimation of an attribute relation
Pattern set

Score(Mt.Fuji，height，3776m)= SOA(Mt.Fuji，height) SVA(3776m，height)

A of O is V
A of O (V)O (A=V):

SOA(Mt.Fuji, height): Mt.Fuji has an attribute height
SVA(3776m, height): 3776m is a value of height(Mt.Fuji, height, 3776m)?
CORPUS

Score(Mt.Fuji, X , 3776m)

Weighted Mutual Information for both SOA and SVA

p(x, y)weighted M I = p(x, y) × log2p(x)p(y)Extracts arbitrary relations
Training data is not required

The height of Mt.Fuji is3776m. On the other hand,Mt.Haruna is 1449m high.

11

1: Score(Mt.Fuji, height, 3776m) = 0.48
Top N 2: Score(Mt.Fuji, population, 3776m) = 0.32
3: Score(Mt.Fuji, principal food, 3776m) = 0.07
4: Score(Mt.Fuji, prime minister, 3776m) = 0.02:

Attribute List
staple foodprime ministerheightpopulation:

12

Overview

Overview

Estimation of an attribute relation
Pattern set
A of O is V
A of O (V)O (A=V):The height of Mt.Fuji is3776m. On the other hand,Mt.Haruna is 1449m high.

acquiredautomaticaly

CORPUS

Estimation of an attribute relation
Pattern set
A of O is V
A of O (V)O (A=V):(Mt.Fuji, height, 3776m)?

(Mt.Fuji, height, 3776m)?
CORPUS

Score(Mt.Fuji, X , 3776m)
Attribute List
staple foodprime ministerheightpopulation:

1: Score(Mt.Fuji, height, 3776m) = 0.48
Top N 2: Score(Mt.Fuji, population, 3776m) = 0.32
3: Score(Mt.Fuji, principal food, 3776m) = 0.07
4: Score(Mt.Fuji, prime minister, 3776m) = 0.02:

13

Score(Mt.Fuji, X , 3776m)
Mainichi newspaper
Attribute Liststaple food(6 =months)
1: Score(Mt.Fuji, height, 3776m)
0.48
prime ministerheightpopulation:Top N 2: Score(Mt.Fuji, population, 3776m) = 0.32
3: Score(Mt.Fuji, principal food, 3776m) = 0.07
4: Score(Mt.Fuji, prime minister, 3776m) = 0.02
:Overview

14

Overview

Estimation of an attribute relation
Pattern set
A of O is V
A of O (V)O (A=V):The height of Mt.Fuji is3776m. On the other hand,Mt.Haruna is 1449m high.

Estimation of an attribute relation
Pattern set
A of O is V
A of O (V)O (A=V):The height of Mt.Fuji is3776m. On the other hand,Mt.Haruna is 1449m high.

The height of Mt.Fuji is3776m. On the other hand,Mt.Haruna is 1449m high.

(Mt.Fuji, height, 3776m)?
CORPUS(Mt.Fuji, height, 3776m)?
CORPUS

Object is limited tonamed entities:

Score(Mt.Fuji, X , 3776m)
Attribute List
staple foodprime ministerheightpopulation:

1: Score(Mt.Fuji, height, 3776m) = 0.48
ARTIFACT, LOCATION,Top N 2: Score(Mt.Fuji, population, 3776m) = 0.32
3: Score(Mt.Fuji,principal food, 3776m) = 0.07
ORGANIZATION,
4: Score(Mt.Fuji, prime minister, 3776m) = 0.02
PERSON:15

Overview

A of O is V
A of O (V)O (A=V):Score(Mt.Fuji, X , 3776m)

1: Score(Mt.Fuji, height, 3776m) = 0.48
Top N 2: Score(Mt.Fuji, population, 3776m) = 0.32
3: Score(Mt.Fuji, principal food, 3776m) = 0.07
4: Score(Mt.Fuji, prime minister, 3776m) = 0.02:

Attribute List
staple foodprime ministerheightpopulation:

16

Evaluation

Estimation of an attribute relation
Pattern set

Attribute list consistsof 1038 words

comparison

without filtering(only pattern matching)

The height of Mt.Fuji is3776m. On the other hand,Mt.Haruna is 1449m high.

(Mt.Fuji, height, 3776m)?

with filtering

CORPUS

Score(Mt.Fuji, X , 3776m)
Top 3
1: Score(Mt.Fuji, height, 3776m) = 0.48
Top N 2: Score(Mt.Fuji, population, 3776m) = 0.32
3: Score(Mt.Fuji, principal food, 3776m) = 0.07
4: Score(Mt.Fuji, prime minister, 3776m) = 0.02:

Attribute Liststaple foodprime ministerheightpopulation:

Evaluation Measure
Precision
RecallF-measure1718

Evaluation Results

Evaluation Results

Candidates: 19,620

Examples of Attribute estimation

Analysis of 500 samples「米朝は朝鮮労働党の金容淳書記が一月訪米，米．．」Attribute relations：216

Precision

216/500 (0.43)

210/417 (0.50)

Recall216/216 (1.00)

210/216 (0.97)

F-measure

0.60

0.66

Evaluation Results72

総書記

2.79e-10

8

代表団

1.06e-10

7
1

92-

1

委員長
主席

2.49e-10
1.73e-10

910

問題
会議
部長

1.25e-10

objectattributevalue

6.53e-11
3.09e-11

1
2
3
4
5

問題
会議
国家外相
大使

2.74e-10
1.34e-10
8.39e-11
4.30e-11
3.93e-11

6
7
8
910

大統領
長官
代表
首相
政策

3.58e-11
1.86e-11
1.06e-11
9.48e-129.29e-1220

cooccurrence within a sentence→ cooccurrence in patterns ordependency pairs.

Correct attributesʼ ranks

39

3

7

Strict cooccurrence measure

to be in the top 10 attributecandidates.
The score has high recall.

#cand. 164

1.62e-10

2.89e-10

Future work

Almost all candidates are estimated

4担当

団長

「ソ連の在外資産・に関する協定．．」

19

365

Improvement of 6% in F-measure2

2.89e-08

4w/ Filtering

1書記

2w/o Filtering

rank

1

Smoothing in scoringSum

Introduce a word class based

216

cooccurrence measure into thecalculation of the statistical measure.
21

Summary
Set a task of extracting triplets of(object, attribute, value)
Proposed an approach which
combines patterns with a statisticalmeasure.
Improved performance with a 6%
increase in the F-measure.

2322