Identifying Constant and Unique Relations
by using Time-Series Text
Yohei Takaku Nobuhiro Kaji Naoki Yoshinaga Masashi Toyoda
Toyo Keizai Inc. Institute of Industrial Science, University of Tokyo

Relation Extraction from the Evolving Web• Web (text) as a growing goldmine for extracting
relations between real-world entities[Pantel+ 06; Banko+ 07; Suchanek+ 07; Wu+ 08,10; Zhu+ 09; Mintz+ 09]– Processing more text leads to more relations, but– Relations in text could be obsolete / will become outdated
Apple’s CEO isete
Steve Jobslosbo2009

2010

2011

Apple’s CEO is
Tim Cook2012

How to Consistently Compile
Extracted Relations?
• <arg1, flows through, arg2>• <arg1, ‘s CEO is, arg2>• <arg1, sells, arg2>

How to Consistently Compile
Extracted Relations?
• <arg1, flows through, arg2>• <arg1, ‘s CEO is, arg2>• <arg1, sells, arg2> Accumulate all the relations, because

the relation does not evolve over time

Moselle river flows
through Germany
2009

2010

2011

Moselle river flows
through France
2012How to Consistently Compile
Extracted Relations?
• <arg1, flows through, arg2>• <arg1, ‘s CEO is, arg2>• <arg1, sells, arg2> Overwrite with new one, because

the relation can take one value of arg2

2009

Apple’s CEO isnet
Steve Jobs
itr
rweov

Apple’s CEO is
Tim Cook

Apple sells
MacBook Air

Apple sells
iPhone 4S

2010

2011

2012

Constant and Unique Relations• Given value of arg1,– Constant rel.: value of arg2 is independent of time
– Unique rel.: value of arg2 is one at any point in time

constant, unique

non-constant, unique<arg1, was born in, arg2><arg1, ’s CEO is, arg2><arg1, ‘s father of, arg2><arg1, belongs to, arg2><arg1, flows through, arg2><arg1, sells, arg2>

constant, non-unique

non-constant, non-unique

Overview• Constancy and Uniqueness of Relations• Our Approach• Features for Constancy Classification• Features for Uniqueness Classification• Experiments• Conclusion

Two Binary Classification Tasks<arg1, was born in, arg2><arg1, ’s CEO is, arg2><arg1, ’s father is, arg2><arg1, belongs to, arg2><arg1, borders on, arg2><arg1, sells, arg2>

Two Binary Classification Tasks
Task 1: constancy classification
constant

non-constant<arg1, was born in, arg2><arg1, ’s CEO is, arg2><arg1, ’s father is, arg2><arg1, belongs to, arg2><arg1, borders on, arg2><arg1, sells, arg2>

Two Binary Classification Tasks
Task 2: uniquness classification
unique<arg1, was born in, arg2><arg1, ’s CEO is, arg2><arg1, ’s father is, arg2><arg1, belongs to, arg2><arg1, borders on, arg2><arg1, sells, arg2>

non-uniqueTwo Kinds of Features forTraining Supervised Classifiers• Frequency obtained from time-series text
– Detailed later– Based on blog posts crawled from 2006 to 2011

• Linguistic cuese.g., <arg1, ’s president is, arg2>non-const.
Prefix George Bush is ex-president of USAe.g., <arg1, borders on, arg2>non-uniq.
Coordination France borders on Italy as well as Spain

Overview• Constancy and Uniqueness of Relations• Our Approach• Features for Constancy Classification• Features for Uniqueness Classification• Experiments• Conclusion

Using Time-series Textfor Constancy Classification<Keisuke Honda(=arg1), belongs to, arg2>non-const.

2008 – 2010, VVV-Venlo2010 – now, CSK Moskow

Using Time-series Textfor Constancy Classification<Keisuke Honda(=arg1), belongs to, arg2>non-const.
2010 – 20112008 – 200930

VVV Venlo25

frequency

frequency

30

20
15
1050w
lo
co Ve nso
M VVAVKCSVVV

lyItanemea
gu di u rude el saahtlee
Cch i ki S Hai bt
Du zhn an
Lu i rmaCharg2 fillers

CSKA Moscow

25
20151050OPAw
lo
co Ve nsoVMAVVKCSVVV…
lyeman l sea
Ita agu di u i rmeta haleChShiCtcikDu zhnLuarg2 fillers

OPA

Cosine Similarity as a Feature Value<Keisuke Honda, belongs to, arg2>non-const.
30

30

25

25

20

20

15

15

10

cosine = 0.0 105

50( 0, 27, 7, 0, 0, 0, 1, 0, 0)naVOlyewlomco Ve n VV Ita agu di u rude el se PAsao Vhtlee
CM Vch i ki S Hai bAVtKDu zhn anCSLu i rmaCh0…
… a 0,(19,SKA…0,nlo 0,1)
V 0,Ol y ch0,i ki…0,an l0,se PA
VV Ita ut nC VeVVVDzh i rm e
Lu Cha Ch<Tokyo, has river, arg2>const.

25

25

20

20

1510cosine = 0.39

5

( 4, 0,0 1, 3, 1, 21, 3, 1, 1)
rrr
r
rr
r
r
r
ive rive ri ve ri ve ri ve ri ve ri ve ri ve ri ver
i a aa a o a a om id gur As nd Ed aka ias ndanm
ST uam OS MeKainM

15
105( 4, 02, 1, 1, 1, 1, 0, 0, 0)
r r r r r r r r r
ive rive ri ve ri ve ri ve ri ve ri ve ri ve ri veri a aa a o a a om id ur As nnd Ed aka ias ndSTa um eg
am OS M
KainM

Importance of Choosing Time Windows<Keisuke Honda, belongs to, arg2>non-const.
VVV Venlo

30
2520
1510
5030
25
20151050n a Ow lo V ly e mco Ve n VV Ita agu di u rude el se PAsohle ta
M VVh ki S ai be CcAVti
H
KDu zhn an
CSu
L i rmaCh

20092010

CSKA MoscowanVOly ew lom
co Ve n VV Ita agu di u rude el se PAsotale
ChM VVh ki S ai bec
AVti
HKDu zhn an
CSu
L i rmaChX
Teamchanged2011

2012

Importance of Choosing Time Windows<Keisuke Honda, belongs to, arg2>non-const.
30
25
20
15
1050

CSKA Moscow

30
2520
15
1050anVOly ew lom
co Ve n VV Ita agu di u rude el se PAsotale
ChM VVh ki S ai bec
AVti
HKDu zhn an
CSu
L i rmaCh

2009

2010

CSKA MoscowanVOly ew lom
co Ve n VV Ita agu di u rude el se PAsotale
ChM VVh ki S ai bec
AVti
HKDu zhn an
CSu
L i rmaChX
Teamchanged

2011

2012

Using Multiple Time Windows
0.4 + 0.3 + 0.0= 0.233
340

...

200…
A… VV utc hai … A OKD CVPCS

0.4 300.3 30...

...

10-10… r…
…
KA VVV utch hai PA OSCCDT months
200910-10… r…
…
KA VVV utch hai PA OSCC
D0.02010

2011

Window size T = { 1, 3, 6, 12 (months) }Integration method = { ave., min., max. }

2012

...
time

12 (= 4 x 3) features

Overview• Constancy and Uniqueness of Relations• Our Approach• Features for Constancy Classification• Features for Uniqueness Classification• Experiments• Conclusion

Using Time-series Text
for Uniqueness Classification<Keisuke Honda, belongs to, arg2>uniq. <Google, acquires, arg2>non-uniq.

30

30

25

25

20

20

15

single entity

12 entities

10number of entity types

105500w
loco Ve nsoM VVAVKCS

15……

VVV… alyemeanIta agu di u i rm el shle Sta haChCtc ni kiuDzhLuarg2 fillersOPAr ee n eu fekd w er
Pub upo Sli d man No itt DS urne e vi n Ffl ic Jai k hLi
Ty wsu odB Wi dPu
De Sa TYo GreFearg2 fillers

Using Time-series Text
for Uniqueness Classification (Cont.)<Keisuke Honda, belongs to, arg2>uniq. <Google, acquires, arg2>non-uniq.
Frequency
ratio between the 1st and 302nd most frequent entities
30252025

1920

1/19 ≒ 0.05

151050w
loco Ve nsoM VVAVKCSVVV… alyemean
Ita agu di u i rm el sh
le Sta haChCtc ni kiuDzhLu

15
1097

7/9 = 0.77

15OPAr ere n eu fekd w
Pub upo Sli d man No itte DS urne e vi n Ffl ic Jai k hLiTy w
su odB Wi dPu
De Sa TYo GreFe0values of arg2data can be noisy

values of arg2

Setting Appropriate Time Windows
is also Important<Keisuke Honda, belongs to, arg2>uniq.
VVV Venlo CSKA Moscow
30
25
20
15
1050yow e nl o VVV Ital gue i um de n l sea PA Ocdeua
Vosle Sta be r Ch
M VVhiic
Vti k HaKA
Du zhn anCSLu i rmaCh

2009

2010

X
Team
changed

2011

2012

Overview• Constancy and Uniqueness of Relations• Our Approach• Features for Constancy Classification• Features for Uniqueness Classification• Experiments• Conclusion

Experiments• Evaluate our method with relations extracted fromtime-series text
– Classifier: Passive-aggressive algorithm w/ proposed features– Time-series text: 6-year’s worth of Japanese blog posts(2.3-billion sentences)• Conduct experiments to:– Evaluate the constancy classification– Evaluate the uniqueness classification– Investigate the impact of multiple window sizes

Data and Settings• Parse time-series text to extract dependency paths
connecting two named entities as relation instances• Annotate 1000 relations (majority vote, 3 humans)
Kappa [Fleiss 1971]

Constancy

Uniqueness0.346 (fair)

0.428 (moderate)– Major reason for disagreement: type ambiguity
Ex. <arg1human, is seen in, arg2>non-const.
<arg1mountain, is seen in, arg2>const.

• Use the labeled relations for training & testing– Evaluation metric: Precision & Recall (5-fold cross validation)

Classification Result: Constancy• Varying the threshold to classifier’s output (margin)
to plot recall-precision curve– Baseline: cosine similarity between distributions over arg2
in the first and last month
ProposedBaseline

Recovered most of the constantrelations while keeping precision

Suffered from data sparsenessClassification Result: Uniqueness• Varying the threshold to classifier’s output (margin)
to plot recall-precision curve– Baseline: re-implementation of [Lin+ 10](based on gross distributions over arg2)

ProposedTime-series distributions over arg2
greatly improved the precision

Baseline

Confused non-constant, uniquerels. with non-unique rels.

Impact of using Multiple Time Windows, T• Compare our method (multiple time windows) withmethods using a single time window

ConstancyUniqueness– Combining features computed from multiple time windowsgreatly improved the precision of uniqueness classification

Error Analysis• Investigate 200 misclassified relations
Error Type
Paraphrases

Const. Uniq. Total
165268

ex.
<Obama,Topicalbiasis president of, {USA, the0 United
56States}>
56uniq.
ex.
<Will Smith, ’s sonis, {Jaden Smith/TreySmith}>47
non-uniq.
Short/long-term
evolution
20
27
co-starred in a filmth, 2012
ex.
<RealMadrid,beats,Valencia>
Apr.
7
Obsolete/Speculative facts uniq.
10
1929st, 2012
<Real
Madrid,beats,Barcelona>
Apr.
21
uniq.
ex. <Japan, ‘s capital city is, {Tokyo, Kyoto}>(outdated fact)
uniq.

<Sun, is bought out by, {Oracle, IBM}>const.

(speculation)

Related Work• TempEval temporal relation identification[Verhagen+ 2007, 2010]– Associate event (relation instance) with timeex. <Charles Chaplin, was born in, London> OVERLAP 1889
– Do not address constancy of relation• Functional relation identification [Ritter+ 10]– Use distributions over arg2 to identify uniqueness [Lin+ 10]– Time dimension should be considered to identify uniquenessex. <Naoki Yoshinaga, lives in, {Kyoto (-’96),
Tokyo (‘96-’05,’08-)}>uniq.

Overview• Constancy and Uniqueness of Relations• Our Approach• Features for Constancy Classification• Features for Uniqueness Classification• Experiments• Conclusion

2019/11/7

EMNLP-CoNLL201231

Conclusion• A novel notion of constancy of relations• A method of identifying constant and unique relations– Use massive time-series text to induce features– Timer-series distributions over arg2 computed with multiple
time windows were quite effective• Future work
– Apply our method to relations with typed arguments [Lin+ 10]
Ex. <arg1mountain, is seen in, arg2>const.
– Use constancy/uniqueness to compile extracted relations