Pointwise HSIC: A Linear-Time Kernelized Co-occurrence Normfor Sparse Linguistic Expressions [EMNLP2018]
Sho Yokoi (Tohoku U./RIKEN AIP)*, Sosuke Kobayashi (PFN), Kenji Fukumizu (ISM), Jun Suzuki *, Kentaro Inui *yokoi@ecei.tohoku.ac.jp

1809.00800

https://bit.ly/2SfpZmv

pip install phsic-cli

github.com/cl-tohoku/phsic

Computing Co-occurrence Strength in NLPGeneral Settings

…

!$!%

Task:

[Lowe+,’15]

word bigrams from corpora

input-response message pairs from SNS#"

Haveyou

I'm hungry!

Let’s have lunch

#$you

ever

Will it rain today?

It’s about to rain

#%

York?

I love this manga

compute co-occurrence strength of a pair (!, #)which pairs are collocation?

#!

[Manning&Schütze,’99]…

!"

Dialogue Response Selection…

~

paired data * = { !- , #- }Observed:&'(Collocation Extraction?

which response is the best?

NewYork

I've lost my wallet

I saw it at the …

intheI've lost my wallet

I’m so sleepy

I've lost my wallet

I don’t know

input by users

response candidates

De facto Measure: Pointwise Mutual Information
Mutual Information

Pointwise Mutual Information
PMI(𝑥, 𝑦; 𝑋, 𝑌)

MI(𝑋, 𝑌) = KL[𝐏 ‖𝐏 𝐏 ]𝐏 (𝑥, 𝑦)= log
𝐏 (𝑥)𝐏 (𝑦)𝐏 (𝑥, 𝑦)log
𝐏 (𝑥)𝐏 (𝑦)

= E

( , )

co-occurrence
actualI don’t know

PMI(𝑥, 𝑦)

PMI

just counting𝑛 ⋅ #(𝑥, 𝑦)= log#(𝑥, ⋅)#(⋅, 𝑦)(𝑥, 𝑦)= log

using RNNs

𝐏

(𝑦|𝑥)

𝐏(𝑦)

[Li+,’16]<latexit sha1_base64="(null)">(null)</latexit><latexit sha1_base64="(null)">(null)</latexit><latexit sha1_base64="(null)">(null)</latexit><latexit sha1_base64="(null)">(null)</latexit>

co-occurrenceby chance

Proposed Measure : Pointwise HSIC
HSIC [Gretton+,’05]

Kernels
4: 6 × 6 → ℝℓ: ; × ; → ℝ

Pointwise HSIC
PHSIC(𝑥, 𝑦; 𝑋, 𝑌, 𝑘 , ℓ )= 𝐄= (𝜙(𝑥) − 𝑚 ) 𝐶 (𝜓(𝑦) − 𝑚 )

( , )

= 𝐄

( , ) (𝐄 [𝑘(𝑥, 𝑥 )ℓ(𝑦, 𝑦 )],=)(when using cosine similarity

PHSIC→ can estimate in RKHS directly

𝐄 [𝑘(𝑥, 𝑥 )ℓ(𝑦, 𝑦 )],Requires Very Short Learning Timeestimators are reduced to a simple matrix calculation

HSIC(𝑋, 𝑌; 𝑘 , ℓ ) = MMD ,ℓ [𝐏 , 𝐏 𝐏 ](𝜙(𝑥) − 𝑚 ) 𝐶 (𝜓(𝑦) − 𝑚 )tough to learn
applicable to sparse expressions

easy to learn
inapplicable to sparse expressions(𝑥, 𝑦; 𝑘 , ℓ )= (𝜙(𝑥)−𝜙(𝑥)) 𝐶 (𝜓(𝑦)−𝜓(𝑦)))<latexit sha1_base64="(null)">(null)</latexit><latexit sha1_base64="(null)">(null)</latexit><latexit sha1_base64="(null)">(null)</latexit>

𝜙(𝑥) ∶= 𝑘(𝑥, ⋅), 𝜓(𝑦) ∶= ℓ(𝑦, ⋅)Kernels centered on data𝑚 ∶= E[𝜙(𝑥)], 𝑚 ∶= E[𝜓(𝑦)]𝑘(𝑥, 𝑥’) ∶= 𝑘(𝑥, 𝑥’) − E[(𝑥, 𝑥’)]’− E[(𝑥, 𝑥’)] + E [(𝑥, 𝑥’)]<latexit sha1_base64="(null)">(null)</latexit>𝐶∶= E( , )𝜙(𝑥) − 𝑚

𝜓(𝑦) − 𝑚, ’<latexit sha1_base64="(null)">(null)</latexit>

when using non-linear kernels→ use incomplete Cholesky decomposition

PHSIC(𝑥, 𝑦; 𝑘 , ℓ )= (𝒂−𝒂) 𝐶(𝒃−𝒃)<latexit sha1_base64="(null)">(null)</latexit>

Kernels are Available<latexit sha1_base64="(null)">(null)</latexit>

Dependence of (2, 3)

Co-occurrence of (!, #)the difference between &'( and &' &(the contribution of !, #to the dependence of (2, 3)● Cosine Similarity between Sentence Vectors
o Sentence vectors[Kiros+,’15; Dai&Le,’15; Iyyer+,’15; Hill+,’16; Cer+,’18]

o Sum of word vectors[Mikolov+,’13; Pennington+,’14; Bojanowski+,’17]

o Many pre-trained models are off-the-shelf!

Applicable to Sparse Expressions
PHSIC smooths the matching using kernels● Structure Kernelso [Collins&Duffy,’02; Bunescu&Mooney,’06; Moschitti,’06]

exact match● Combinations

Kernels in Experiments● Cosine Similarity between Sum of Word Vectors
smooths
the matchingby kernels

Experiments𝑘 ( 𝑥 , 𝑥 ) = cos ∑ ∈ 𝑥 𝒗(𝑤), ∑∈ 𝑥𝒗(𝑤)● Gaussian Kernel between Sum of Word Vectors<latexit sha1_base64="(null)">(null)</latexit>𝑘 ( 𝑥 , 𝑥 ) = exp − ∑ ∈ 𝑥 𝒗(𝑤) − ∑∈ 𝑥𝒗(𝑤)

fastText[Bojanowski+,’17;Grave+,‘18]/2𝜎● Cosine Similarity between Sentence Vectors<latexit sha1_base64="(null)">(null)</latexit>1. Dialogue Response Selection [Lowe+,’15]< = 5×10@•Learning Time [s]PMI (w/RNN)PHSIC (cos of USE)

•Predictive Performance [R@2]

PMI (w/RNN)•Learning Time [s]49.0

PHSIC (cos of USE) 0.0<latexit sha1_base64="(null)">(null)</latexit>

2. Parallel Corpus Filtering

0.57

1.8
thousands of times faster!

< = 10A

0.5213054.9𝑘 ( 𝑥 , 𝑥 ) = cos 𝒗( 𝑥 ), 𝒗( 𝑥 )while outperforming PMI•Predictive Performance [R@2]
0.21

Universal Sentence Encoder[Cer+’18] w/Deep Averaging
Network [Iyyer+,’15]BLEU score after filtering (3M ⟼ 1M)
randomfast_alignbaseline using
word alignment[Dyer+,’13]

39.82 (-1.20)
40.56 (-0.46)
40.95 (-0.07)

PHSIC (RBF kernel of fastText)

0.56
much more robust to data sparsity

using all (3M) training data

41.02

PHSIC reduces # of training data to 1/3, almost without sacriﬁcing BLEU