Learning Co-Substructures
by Kernel Dependence Maximization
IJCAI’17

横井 祥1,2 ，持橋 大地 3 ，高橋 諒 1 ，岡崎 直観 4 ，乾 健太郎 1,2
1 東北大，2 RIKEN/AIP，3 統数研，4 東工大

ERATO 感謝祭 SeasonIV2017-08-04
1 / 31

導入：やりたいこと
1
2

獲得したい常識的知識

コーパス内の生文

余計な語がたくさん入っている“Bob had dinner with his friends〈have dinner, be full〉
at his favorite Japanese restaurant just now
and he is full.”
知識に含める語を自動で選択したい3(

haveX, )at
be full
restaurant
Xdinnerwith friends
favoriteJapanese(haveX,be fulldinnerX)

根付き部分木を教師なしで決定する問題だと思う

2 / 31

Table of Contents
解きたい問題
従属性最大化による共部分構造の教師なし学習
提案手法
目的関数：Hilbert–Schmidt Independence Criterion
探索：Metropolis–Hastings
実験
定性評価：小規模人工データからの知識獲得
定量評価：実コーパスを用いた関係予測
まとめ

3 / 31

関心：言語表現ペアの獲得・予測
関連する言語表現ペアの獲得・予測（NLP の中心課題のひとつ）• コーパスから，関連する言語表現ペアを収集（知識獲得）• 与えられた言語表現ペアに関連があるのかないのかを予測

たとえば• 単語と単語の関係：概念同士の関係• 意味は近いか，上位下位関係を持つか• 文と文の関係：命題同士の関係• 含意関係にあるか，因果関係にあるか• イベントとイベントの関係

今回例として採用• 典型的に連続して生じるイベント対を獲得・予測したい[Schank&Abelson’77]• 例： ⟨have dinner, be full⟩4 / 31

問題：獲得パターンが固定
イベントペア獲得・予測の典型的プロセス [Chambers&Jurafsky’08]

1. 文ペアの収集：共参照項を持つ文対をコーパスから収集
Tom killed nancy.
co-referent

The policearrested him immediately.

2. 予め決められた 抽象表現に変換：「述語動詞と登場人物の位置」に着目 → ⟨X kill, arrest X⟩
3. モデル化：PMI で関連の良さをモデル化
p(X kill, arrest X )PMI(X kill, arrest X ) = logp(X kill)p(arrest X )一見問題なさそう• 知識獲得：可読的な知識 ⟨X kill, arrest X⟩• 予測：自己相互情報量（PMI）によるモデル化
5 / 31

問題：獲得パターンが固定先の手法は 場合によって 問題がある [Granroth-Wilding&Clark’16]• ⟨“Tom had had absent repeatedly.”, “He was fired.”⟩→ ⟨X have, fire X⟩• ⟨“Bob has a talent for accounting work.”, “He was hired withfavorable treatment.”⟩→ ⟨X have, hire X⟩
この場合に 理想的な知識• ⟨X have absent repeatedly, fire X⟩ ， ⟨X have talent, hire X⟩
必要な情報はインスタンス毎に異なる
他，次のような語句の有無によってもイベントの意味が大きく変わり得る• 否定表現• 特定の条件を表す修飾節• etc.

6 / 31

Table of Contents
解きたい問題
従属性最大化による共部分構造の教師なし学習
提案手法
目的関数：Hilbert–Schmidt Independence Criterion
探索：Metropolis–Hastings
実験
定性評価：小規模人工データからの知識獲得
定量評価：実コーパスを用いた関係予測
まとめ

7 / 31

解きたい問題
ペアをペアたらしめている部分構造を，インスタンス毎に，教師なしで決定する（獲得する知識の “粒度” を教師なしで決定したい）

She

has

dinnerTomatfull
restaurant She
Italianeat,

is,stuffedHe

hastrouble,Heconcentrating
haveItroublefalling
asleep,heartShedinnerTom

iswith John
outdoors
Bob

very

My

Bob

extremely,

stuffedHewith John,,

He

eat

has
troubleconcentrating

filledis

Italianoutdoors

sadis

Z

at
full
restaurant She

has

have
I
with
sadnesstroublefalling
asleepisisheart,

very

My

sadis

extremely

fillediswithsadness

今回の設定：各文を依存構造木で表現（根付き部分木の大きさを調整すれば表現の抽象度を調整できる）
8 / 31

定式化：従属性最大化n
入力 文のペアの集合 D = {(si, ti )}i=1n
出力 元の文の部分構造のペアの集合 Z = {(xi, yi )}i=1
i.i.d.

目的関数 Z ∼ PXY と見て maximize D[PXY ∥PX PY ]Shehasdinner
Tomat
full
restaurant She
Italianeat,

is,stuffedHe

hastrouble,Heconcentrating
haveItroublefalling
asleep,TomheartMy

Bobextremely,

stuffedHewith John,,

He

eat

hastrouble
concentrating

filledis

ItalianoutdoorssadisZatfull
restaurant She

hasdinneriswith John
outdoors
Bobvery

She

have
Iwith
sadnesstrouble
falling
asleepisisheart,

veryMysadisextremely

fillediswithsadness

cf. 特徴選択:入出力間の関連の良さを従属性に帰着 [Peng+’05][Song+’12]
9 / 31

従属性最大化に伴う問題
目的関数：データ・スパースネス
8 数千〜数百万オーダーの語彙 … の組合せ
→ 個々の部分構造は超低頻度
例：have dinner at my favorite Italian restrant（ナイーブな最尤推定における）各 p(x, y), p(x) は非常にスパース

I(X; Y ) = KL[PXY ∥PX PY ]∑∑p(x, y)=p(x, y) log
p(x)p(y)x y8 多様な言い換え表現（自然言語処理に常につきまとう問題）
例：get angry ↔ be offended→ 完全一致ではなく類似度に基づいて従属性を測りたい
探索：組合せ爆発各 xi 各 yi についてそれぞれ部分木の取り方を考える必要がある

10 / 31

Table of Contents
解きたい問題
従属性最大化による共部分構造の教師なし学習
提案手法
目的関数：Hilbert–Schmidt Independence Criterion
探索：Metropolis–Hastings
実験
定性評価：小規模人工データからの知識獲得
定量評価：実コーパスを用いた関係予測
まとめ

11 / 31

Table of Contents
解きたい問題
従属性最大化による共部分構造の教師なし学習
提案手法
目的関数：Hilbert–Schmidt Independence Criterion
探索：Metropolis–Hastings
実験
定性評価：小規模人工データからの知識獲得
定量評価：実コーパスを用いた関係予測
まとめ

12 / 31目的関数（従属性尺度）：HSIC
Hilbert–Schmidt Independence Criterion [Gretton+05]• カーネル法ベースの独立性，従属性尺度
HSIC(X, Y ) = MMD2 (PXY , PX PY )i.i.d.

N• 出力 Z = {(xi, yi )}i=1 ∼ PXY に対する HSIC の推定量

HSIC(Z; k, ℓ) :=11tr(KHLH)=tr(K̃L̃)N2
N2

K = (k(xi, x j )) ∈ RN×N , L = (ℓ(yi, y j )) ∈ RN×N
k : X × X → R, ℓ : Y × Y → R (正定値カーネル)K̃ := HKH, L̃ := HLH (中心化グラム行列)
H = (δi j − N −1 ) ∈ RN×N
13 / 31HSIC の推定量の気持ち
HSIC の推定量
xjyjyixi

˜ i , yj )`(yk̃(xi , xj )K̃k̃i ˜`iL̃「HSIC の推定値が大きい」＝「カーネル関数（類似度）が定める距離が入った空間に放り込むと，前件側および後件側のフレーズの相対的な位置関係がだいたい一致する」

have dinner

be full

14 / 31HSIC の推定量の気持ち
HSIC の推定値は以下の場合に大きくなる• X 側が似ていれば Y 側も似ている• X 側が似ていなければ Y 側も似ていない
Similar

Shedinner
TomZ

atfullrestaurant She

has

Italian,stuffedHewith John,
,

He

eat

outdoorsBob

hastroubleconcentrating
haveI

Unsimilar

troublefalling
asleepisisheart,SimilarveryMysadis

extremely

filledis

withsadness

Unsimilar

4 類似性に基づいた一貫した（従属性の高い）知識を期待できる
4 完全一致に基づいた数え上げではないのでデータ・スパースネスに対応できる

15 / 31

Table of Contents解きたい問題
従属性最大化による共部分構造の教師なし学習
提案手法
目的関数：Hilbert–Schmidt Independence Criterion
探索：Metropolis–Hastings
実験
定性評価：小規模人工データからの知識獲得
定量評価：実コーパスを用いた関係予測
まとめ

16 / 31

探索：Metropolis–Hastings
以下の分布上で Metropolis–Hastings (MCMC) でサンプリング（焼きなましをしてもほとんど意味なし．適当な β = const. でほぼ一直線にサチる）

p(Z; k, ℓ, β) ∝ exp(β · HSIC(Z; k, ℓ))
少しずつ枝の刈り方を変えながら確率的に山登り

q(Z 0 |Z)Z

q(Z 00|Z 0 )Z0Z 0017 / 31探索：提案分布
n1. 現在の解候補：Z = {(xi, yi )}i=1

2. 木を選択：xi または yi をひとつ選択 q(x|Z) = q(y|Z) = 21n3. 枝を選択：選択された x をわずかに変えて新しい部分構造 x′ を
n を得る
作り (q(x ′ |x))，新しい解候補 Z ′ = {. . . , (xi′, yi ), . . . }i=1q(x′ |x) = 1/|M(x)| (x′ ∈ M(x)), 0 (otherwise)
4. 確率 min(1, r) で Z ′ を受理r=p(Z ′; k, ℓ, β) q(Z|Z ′)·p(Z; k, ℓ, β) q(Z ′ |Z)= exp(β · (HSIC(Z ′; k, ℓ) − HSIC(Z; k, ℓ))) ·5. 2–4 を繰り返し

q(x|x′)
q(x′ |x)18 / 31

計算コスト• 中心化グラム行列 K̃, L̃ を構成するのは最初の 1 回だけO(N 2 )• サンプリング毎にグラム行列 K, L を 1 行だけ更新
O(N)• → K, L を（ランク κ ）不完全コレスキー分解してからHSIC(Z; k, ℓ) を計算
O(κ 2 N)

19 / 31ここまでのまとめ解きたい問題：ペアをペアたらしめている部分構造を教師なしで決定する
n
入力 文のペアの集合 D = {(si, ti )}i=1n
出力 元の文の部分構造のペアの集合 Z = {(xi, yi )}i=1i.i.d.

目的関数 Z ∼ PXY と見て max. D[PXY ∥PX PY ]（従属性最大化）

She

has

dinnerTomatfull
restaurant She
Italianeat,,

isstuffedHe

hastrouble
concentrating
haveItrouble
falling
asleep,,TomHe

heartMyBob

extremely,,stuffed
Hewith John,

He

eat

hastrouble
concentrating

filledis

Italianoutdoors

sadis

Zat
full
restaurant She

hasdinneriswith John
outdoors
Bob

very

She

have
Iwithsadness

troublefalling
asleepisisheart,

very

My

sadis

extremely

fillediswithsadness

提案手法• 目的関数：8 データ・スパースネス＆多様な言い換え → 4 HSIC
• 探索：8 組合せ爆発 → 4 MH で確率的山登り

20 / 31

Table of Contents
解きたい問題
従属性最大化による共部分構造の教師なし学習
提案手法
目的関数：Hilbert–Schmidt Independence Criterion
探索：Metropolis–Hastings
実験定性評価：小規模人工データからの知識獲得
定量評価：実コーパスを用いた関係予測
まとめ21 / 31

Table of Contents
解きたい問題
従属性最大化による共部分構造の教師なし学習
提案手法
目的関数：Hilbert–Schmidt Independence Criterion
探索：Metropolis–Hastings
実験定性評価：小規模人工データからの知識獲得
定量評価：実コーパスを用いた関係予測
まとめ

22 / 31

定性評価：小規模人工データからの知識獲得
12
入力：D = {(si, ti )}i=1si
I have had breakfast at my house .
We had special dinner .
I have had breakfast at ten .
They had breakfast at the eatery .
She had breakfast with her friends .
I had breakfast with my friends at my uncle ’s house .
They had breakfast with their friends at the cafeteria .
He had lunch with his friends at eleven .
I had trouble associating with others .
He had trouble with his homework .
I have trouble concentrating .
She had trouble reading books .

ti
I am full .
We are full .
I ’m full .
They are full now .
She felt happy .
I feel happy .
They felt happy .
He felt happy .
I cry .
He cries .
I cry .
She cries .

類似度（カーネル）：
k(xi, x j ) = cos(ave(wordvecs(xi )), ave(wordvecs(x j )))ℓ(yi, y j ) = cos(ave(wordvecs(yi )), ave(wordvecs(y j )))フレーズ間類似度の典型的な尺度．学習済み単語ベクトルを利用．
23 / 31

定性評価：小規模人工データからの知識獲得
12
出力：Z = {(xi, yi )}i=1

太字：提案アルゴリズムが残した単語
xi
I have had breakfast at my house .
We had special dinner .
I have had breakfast at ten .
They had breakfast at the eatery .
She had breakfast with her friends .
I had breakfast with my friends at my uncle ’s house .
They had breakfast with their friends at the cafeteria .
He had lunch with his friends at eleven .
I had trouble associating with others .
He had trouble with his homework .
I have trouble concentrating .
She had trouble reading books .

yi
I am full .
We are full .
I ’m full .
They are full now .
She felt happy .
I feel happy .
They felt happy .
He felt happy .
I cry .
He cries .
I cry .
She cries .

4 1 度だけ出現する単語 (dinner, lunch) が頻出語 (breakfast) との類似度に基づいて残される
4 第 2 ブロックの (with) friends が残され，左辺 → 右辺の予測を容易に
24 / 31

Table of Contents
解きたい問題
従属性最大化による共部分構造の教師なし学習
提案手法
目的関数：Hilbert–Schmidt Independence Criterion
探索：Metropolis–Hastings
実験
定性評価：小規模人工データからの知識獲得
定量評価：実コーパスを用いた関係予測
まとめ25 / 31

定量評価：実コーパスを用いた関係予測
raw data

abstract representation
1. abstraction

training

2. training

Z={(xi , yi )}i
1. abstractionmodel

2. scoring

test

学習（知識獲得）n
1. コーパスから共参照項を持つ文対を収集：D = {(si, ti )}i=1
例： ⟨“Tom killed Nancy.”, “The police arrested him immediately.”⟩n
2. 抽象表現に変換して保存：Z = {(xi, yi )}i=1
例： ⟨X kill, arrest X⟩

予測
1. 文対 (s, t) を抽象表現 (x, y) に変換
2. 集めた Z を用い (x, y) の関連の良さをスコアリング：g(x, y; Z)
評価尺度：AUC-ROC26 / 31

定量評価：関連の強さの尺度
Poitwise Mutual Information [C&J’08]
N · c(x, y)
PMI(x, y; Z) = logc(x)c(y)Pointwise HSIC：中心化したカーネル密度推定
1 ∑˜ yi )k̃(x, xi )ℓ(y,PHSIC(x, y; Z) :=N i=1
N

N で中心化したカーネルk̃(·, ·) は既知のデータ点 {xi }i=1

1 ∑k̃(x, x ) := k(x, x ) −k(x, x j )N j=1′′

N

N NN
1 ∑
1 ∑∑′k(xi, x j )−k(xi, x ) + 2
N i=1
N i=1 j=1

X に和が定義されていれば k̃(x, x′) = k(x − x̄i, x′ − x̄i )27 / 31

PMI:MI ≈ PHSIC:HSIC
PHSIC は類似度でスムージングした PMI に見える

PMI で測る (x, y) の関連の良さ• x = xi ∧ y = yi なる (xi, yi ) が存在 → PMI が上昇• x = xi ⊻ y = yi なる (xi, yi ) が存在 → PMI が低下

PHSIC で測る (x, y) の関連の良さ
˜ yi ) > 0 なる (xi, yi ) が存在 → PHSIC が上昇• k̃(x, xi )ℓ(y,“x ≈ xi ∧ y ≈ yi ” のとき上昇
˜ yi ) < 0 なる (xi, yi ) が存在 → PHSIC が低下• k̃(x, xi )ℓ(y,PMI:MI ≈ PHSIC:HSIC

1 ∑PMI(xi, yi ; Z)
N i
1 ∑HSIC(X, Y ; Z) =PHSIC(xi, yi ; Z)
N i
MI(X, Y ; Z) =28 / 31

定量評価：実コーパスを用いた関係予測
1.0

1.0

0.8

0.8

0.6

0.6

0.4

C&J'08Jans et al.'12
C&J'08+PHSIC
Proposed

0.2
0.0
0.0

0.2

0.4

(a) Gigaword
Method[C&J’08][Jans+’12][C&J’08] + PHSIC
Proposed

0.6

0.8

1.0

N = 16,748
Abstraction
Fixed (C&J)
Fixed (C&J)
Fixed (C&J)
Dynamic

0.4

C&J'08Jans et al.'12
C&J'08+PHSIC
Proposed

0.2
0.00.00.20.4(b) Fairy Tale
ModelPMI
Conditional
PHSIC
PHSIC

Gigaword
0.553
0.556
0.518
0.633

0.6

0.8

1.0

N = 1,673
Fairy Tale
0.596
0.576
0.518
0.646

4 「インスタンス毎に注目すべき場所を決める」アプローチは予測精度にも寄与
4 PHSIC という予測モデルでスコアが向上しているわけではない
29 / 31

Table of Contents
解きたい問題
従属性最大化による共部分構造の教師なし学習
提案手法
目的関数：Hilbert–Schmidt Independence Criterion
探索：Metropolis–Hastings
実験
定性評価：小規模人工データからの知識獲得
定量評価：実コーパスを用いた関係予測
まとめ

30 / 31

まとめ
問題：「ペアをペアたらしめている部分構造を探す」問題を提案
n
入力 文のペアの集合 D = {(si, ti )}i=1n
出力 元の文の部分構造のペアの集合 Z = {(xi, yi )}i=1i.i.d.

目的関数 Z ∼ PXY と見て max. D[PXY ∥PX PY ]（従属性最大化）

提案手法• 目的関数：8 データ・スパースネス＆多様な言い換え → 4 HSIC
• 探索：8 組合せ爆発 → 4 MH で確率的山登り

実験：イベントペアの獲得・予測• 定量評価：提案手法が知識獲得の観点で理想的に動く• 定量評価：インスタンス毎の抽象化が予測精度に貢献

今後の取り組み• 高速化：現状数万オーダー → 数百万オーダー• より精緻な類似度関数の導入：構造カーネル• 他タスクへの適用
31 / 31