A Latent Variable Model Approach to PMI-based Word Embeddings
Sanjeev Arora+ (TACL 2016)
統計数理研究所
持橋大地

daichi@ism.ac.jp
最先端 NLP8
2016-9-11 (Sun)
Modified for ISM, 2016-9-30 (Fri)A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.1/26

概要• word2vec, GloVe, …は PMI の行列を低ランク近似していることが知られている• しかし, なぜ PMI を考えることが意味があるのかは不問• 本論文では, ランダムウォークする文脈ベクトル ct からの近さに従って単語が生まれたと仮定することで,◦ 単語ベクトルの内積が相互情報量に対応すること,◦ “意味” の方向がベクトルの差と内積で書けること− 特に, 低次元表現により, それがノイズに埋もれないことを示している.

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.2/26

注意• 以下で誤差項 ǫ を複数含む式の等式は厳密ではありませんので,厳密な導出は完全版のhttp://arxiv.org/abs/1502.03520“RAND-WALK: A Latent Variable Model Approach to WordEmbeddings” Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu
Ma, Andrej Risteski
をお読み下さい.

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.3/26

はじめに
単語ベクトル v, w について

hv, w i ≈ PMI(v, w)(1)• Levy&Goldberg (2014b) は SGNS の解が (1) 式に似た,hv, w i ≈ PMI(v, w) − β(2)を満たすことを示した◦ ただし高次元での話であり, 低次元表現が高精度であることの説明はない• Hashimoto+(2016) は p(v|w) ∝ h(|v − w|2 ) と仮定すると, (1) が導かれることを示した◦ ただし, 文脈ベクトルのような概念はなく, 単語だけで考えているので, “意味” の方向などは説明できない◦ 文脈ベクトルを考えることは, 意味が複数ある場合への拡張でも有効 (Arora+, arXiv 2016)

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.4/26

基本モデル• 時刻 t において, ランダムウォークする文脈ベクトル ct があり,それに従って単語 wt が下の式に従って発生すると仮定

exp(wtT ct )p(wt |ct ) =Z; Z=X

exp(wT ct )(3)w

◦ これは, Mnih&Hinton (2007) の Log-bilinear モデルを動的にしたもの◦ Belanger&Kakade (2015) はカルマンフィルタで単語が生成されるモデルを考えたが, 線形システムであり, 上のようなロジスティック回帰ではない• 単語には確率が非常に大きいものもあるので, それは単語ベクトル w のノルムに反映される◦ w = s · ŵ を仮定, ŵ は単位球面 C 上のベクトル, s は確率変数
A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.5/26

定理 (0)• 以下の計算で, 正規化定数 Z(c) =T c) は c にかかわらexp(wwPずほぼ 1 (!)◦ Self-normalizing log-linear model (Andreas & Klein 2014)hi(4)pc∼C (1 − ǫ)Z ≤ Z(c) ≤ (1 + ǫ)Z ≥ 1 − δ√
ここで ǫ = Õ(1/ n), δ = exp(−Ω(log2 n)) (n: 単語種数)

Percentage

401008080406060204020402020000.5

11.5

Partition function value(a) SN

200.5

11.5

Partition function value(b) GloVe

200.5

11.5

20.5

11.5

Partition function value

Partition function value(c) CBOW(d) skip-gram

2Figure 1: The partition function Zc . The figure shows the histogram of Zc for 1000 random vectors c of appropriatenorm, as defined in the text. The x-axis is normalized by the mean of the values. The values Zc for different c
concentrate around the mean, mostly in [0.9, 1.1]. This concentration phenomenon is predicted by our analysis.
A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.6/26

定理 (1)• 先の生成モデルと窓幅 2 の下で,これから,|v+w|2log p(v, w) =− 2 log Z ± ǫ
2d|w|2log p(w) =− log Z ± ǫ2dp(v, w)
PMI (v, w) = log
p(v)p(w)vT w± O(ǫ) .
=d(5)
(6)

(7)

(8)

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.7/26

補題 (2) q• 窓幅が q 単語の場合は, 単語ペアの数がその中で通りある
2
ので,|v+w|2log pq (v, w) =− 2 log Z + γ ± ǫ
2dp(v, w)
PMIq (v, w) = log
p(v)p(w)vT w=+ γ ± O(ǫ)
d(9)
(10)

(11)

q(q − 1).
2
◦ Levy&Goldberg(2014) のただし, γ = logの β を説明

h v, w i ≈ PMI(v, w) − β(12)A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.8/26

証明の概略• 文脈 c ∼ C と続く文脈 c′ ∼ p(c′ |c) について,p(v, w) = Ec,c′ [p(v, w|c, c′ )]を示せばよい.

= Ec,c′ [p(v|c)p(w|c′ )]TT′exp(v c) exp(v c )= Ec,c′ZcZc′(13)(14)(15)• ここで最初の定理から, Zc と Zc′ が高い確率で (1 ± ǫ)Z である

ことを用いると, それが成り立つ場合 (T1) と成り立たない場合(T2) に分けて上の確率を評価できる◦ T2 の場合は, 確率は以下で negligible|T2 | = exp(−Ω(log1.8 n))(16)

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.9/26

証明の概略 (2)• T1 の場合は,


1 ± O(ǫ) 
TT ′
T1 =
Ec exp(v c)Ec′ |c [exp(w c )]Z2

1 ± O(ǫ) TEc exp(v c) A(c)=2Z
1 ± O(ǫ) T=
Ec exp(v c) (1 ± O(ǫz )) exp(hw, ci)2Z
1 ± O(ǫ)
Ec [exp(hv + w, ci)]
≃2Z

(17)
(18)
(19)
(20)

• さらにEc∼C [exp(hv + w, ci)] = (1 ± ǫ) exp

2|v + w|2d(21)から, 定理が得られる. A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.10/26

基本モデルに基づく単語ベクトルの学習• Xvw で窓の中で単語 v, w が共起した回数を表すと, 提案モデル

では, X の確率

L = log

Yp(v, w)Xvw(22)

Xvw log p(v, w)

(23)

v,w

=X
v,wを最大化するような単語埋め込みベクトル w を探せばよい.

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.11/26

基本モデルに基づく単語ベクトルの学習 (2)• 準備 1: 総観測数 N =P

v,w Xvw について

N p(v, w)∆vw = log
Xvwとおけば,N p(v, w)
Xvw ∆vw =Xvw log
Xvw
v,w
v,w
X=Xvw (log N + log p(v, w) − log Xvw )XX(24)

(25)

(26)

v,w

=X
v,w

よって,L=Xv,w

Xvw log p(v, w) − c

(27)

X

(28)

Xvw log p(v, w) =Xvw ∆vw + c .

v,w

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.12/26

基本モデルに基づく単語ベクトルの学習 (3)• 準備 2: ここで,X

Xvw =v,w

X

N p(v, w)

(29)

v,w

N p(v, w)
Xvw exp log=Xv,wv,w

2X
X
∆vw
∆vw
Xvw 1 + ∆vw +Xvw e
≃
=2v,w
v,w
X

• これから,1X
Xvw ∆vw ≃ −Xvw ∆2vw .
2 v,w
v,w

X

(30)

(31)

(32)

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.13/26

基本モデルに基づく単語ベクトルの学習 (4)• よって,

L=X

Xv,w ∆vw + c

(33)

v,w

1X
≃−Xvw ∆2vw + c2 v,w2X
1N p(v, w)=−Xvw log+c2 v,w
Xvw

(34)

(35)

1X
Xvw (log p(v, w) + log N − log Xvw )2 + c(36)=−2 v,w
22X
1|v+w|=−Xvw− 2 log Z ± ǫ + log N − log Xvw
2 v,w2d(37)A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.14/26

基本モデルに基づく単語ベクトルの学習 (5)• ゆえに, L の最大化は以下の最小化と同値.

minw,CXv,w

Xvw

|v+w|22d− log Xvw − C2(38)A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.15/26

他モデルとの関係• GloVe (Pennington+ 2014) の目的関数:

Xv,wf (Xv,w )(log Xvw − vT w − sv − sw − C)2(39)(with f (X) = min(X 3/4 , 100)) において, バイアス項 sv , sw の意
味が明解に: sw = |w|2 .

• Word2vec (CBOW) の予測確率はp(wt+1 |{wk }Ki=1 ) ∝ exp
◦

1KK
X

wk は ct の最尤推定量D

1wt+1 ,KK
X
k=1wk

E!

(40)

k=1

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.16/26

意味方向ベクトルの学習• Pennington+(2014) の議論によれば,man : woman = king : queenが成り立つのは, 確率で以下の関係が成り立つから.
p(x|king)
p(x|man)≈p(x|queen)p(x|woman)(41)◦ この式が説明できればよい• ある関係 R について上の式が成り立っていたとすると, R を満たすすべての単語ペア (a, b) についてp(x|a)= νR (x) · ζa,b,R (x)p(x|b)(42)であることが期待できる. 右辺第 2 項はノイズ項.
A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.17/26

意味方向ベクトルの学習 (2)• ここで定理 1 から, p(v|w) =p(v, w)
はp(w)|w|2|v+w|2− 2 log Z ± ǫ −+ log Z ± ǫlog p(v|w) =2d2d1=(|v|2 + 2vT w) − log Z ± ǫ2d• これより,p(v|w)′log=logp(v|w)−logp(v|w)′p(v|w )1(2vT (w − w′ )) ± ǫ=2d
1= hv, w − w′ i ± ǫ .
d(43)

(44)
(45)
(46)

◦ 「v と w−w′ がどれだけ同じ方向を向いているか」が得られた!

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.18/26

意味方向ベクトルの学習 (3)∴1hv, w − w′ i + ǫ = log νR (v) + ζa,b,R (v)dhv, w − w′ i = d log νR (v) + d(ζa,b,R (v) − ǫ)(47)(48)とおいてみる• これが関係 R を満たす任意の単語 v について成り立つから, V をそれらの m 個の単語ベクトルを並べた m × d の行列, νR , ζR をm 次元のベクトルにとれば, 行列表記で′V (w − w′ ) = d log νR + ζa,b,R(49)′(v) = d(ζa,b,R (v) − ǫ)
(ただし, ζa,b,Rと書くことができる.
◦ これは m × d 次元の線形回帰モデル!
◦ V の擬似逆行列 V † を左からかければ, 回帰が解ける.
A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.19/26

低次元化とノイズ′• (49) 式は有用だが, ノイズ ζa,b,Rが大きい◦ 次元 d が高次元の場合に, d log νR を上回るほどのノイズ• d ≪ n で低次元の場合に, ノイズが少なくなる!
• これが次の定理

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.20/26

定理:3• 次の条件が成り立っているとする.

(1) V の最大固有値が, 固有値の幾何平均より c1 倍以上大きい′とほぼ無相関(2) V の左特異ベクトルは, ζa,b,R√′(内積が高々 c2 |ζa,b,R |/ n)√(3) V の列のノルムの最大値は O( d)• このとき, d 次元に削減した場合のノイズ ζ̄a,b,R は′|2|ζ̄a,b,R |2 . |ζa,b,R

√d.
2(50)

◦ 証明は少し面倒, 論文の Appendix A.10-A.12 参照

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.21/26

実験• 観測された共起カウント行列 Xvw を max(Xvw , 100) で置き換えた観測値に対して提案法を適用したものを, SN (Squared Norm)と呼ぶ◦ Word2vec, GloVe 等と比べ, ほとんどヒューリスティックなパラメータがない• GloVe, CBOW, skip-gram と比較 (それぞれデフォルトパラメータ設定)

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.22/26

実験 (2)• 単語アナロジータスクの精度◦ Google(G): 7874 個の意味的ペア, MSR(M): 10167 個の文法的ペア◦ 提案法は単語の順序を使っていないので, 後者では不利なはず◦ 生成モデルでも充分に高い精度

GMRelations
semantic
syntactic
total
adjectivenounverb
totalSN
0.84
0.61
0.71
0.50
0.69
0.48
0.53

GloVe
0.85
0.65
0.73
0.56
0.70
0.53
0.57

CBOW
0.79
0.71
0.74
0.58
0.56
0.64
0.62

skip-gram
0.73
0.68
0.70
0.58
0.58
0.56
0.57

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.23/26

実験 (3)• “意味方向” の存在を示す• 回帰行列の第 1 固有ベクトルを使った場合 (1st) と, 第 2 固有ベク

トルを使った場合 (2nd)relation
1st
2nd

cap-com
0.65 ± 0.07
0.02 ± 0.28

cap-wor
0.61 ± 0.09
0.00 ± 0.23

adj-adv
0.35 ± 0.170.07 ± 0.24

opp
0.42 ± 0.16
0.01 ± 0.25

◦ 第 1 主成分のみが強い相関, 第 2 主成分はほとんどノイズ◦ 「意味方向」の存在!

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.24/26

実験 (4)• 「意味方向」が存在することが分かったので, たとえば “男性–女性” の方向を得るのに “king–queen” だけでなく, “boy–girl” なども使えばよりロバストに• k 個の同義ペアを使った実験 (RD: relation direction)◦ ペアは多数の質問から, v−w を K 平均クラスタリングして獲得

w/o RD
RD(k = 20)
RD(k = 30)
RD(k = 40)

SN
0.71
0.74
0.79
0.76

GloVe
0.73
0.77
0.80
0.80CBOW
0.740.79
0.82
0.80

skip-gram
0.70
0.75
0.800.77

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.25/26

まとめ• ランダムウォークする文脈から単語が生まれる生成モデルを考えることで, 単語の同時確率が計算できる→◦ 単語の相互情報量が単語ベクトルの内積になることが説明できる◦ 「意味方向」が単語ベクトルの内積で計算できることが説明できる• これまでの理論的研究は高次元の設定に限られ, なぜ低次元の埋め込みが必要なのか理解されていなかった◦ 低次元に埋め込むことで, 単語ベクトルが空間上一様に分布することになり, 真の値へのノイズが高次元の場合より減る→ノイズに埋もれない• 「意味方向」の存在を回帰モデルの固有ベクトルから示し, 多数の単語ペアから求める実験で効果を実証

A Latent Variable Model Approach to PMI-based Word Embeddings, TACL 2016 – p.26/26