言語処理学会 第24回年次大会 発表論文集 (2018年3月)

カーネル法に基づく疎な⾔語表現のための共起尺度
横井 祥 1,2
1 東北大学小林 颯介 3

2 理化学研究所 AIP センター

{yokoi,inui}@ecei.tohoku.ac.jp
1

福水 健次 4

乾 健太郎 1,2

3 株式会社 Preferred Networks

sosk@preferred.jp

はじめに4 統計数理研究所

fukumizu@ism.ac.jp

表1: 提案尺度 Pointwise HSIC（PHSIC）の位置づけ．

ふたつの言語表現の間の共起の強さのモデル化は，自然言語処理における基本的タスクである．たとえばコロケーション獲

確率変数間の依存性の尺度

サンプル間の共起の尺度

X と Y の依存の度合い（pXY とpX pY の異なりの度合い）

ペア (x, y) の「X と Y の依存の度合い」への貢献度

相互情報量

得では，はじめにコーパスから bigram が集められ，とくに強自己相互情報量（PMI）

I(X, Y ) = KL[pXY ∥pX pY ]
p (x, y) = E  log XYx,yp(x)X pY (y) 

く共起する bigram（たとえば “New York”）を見つけることが目的となる．あるいは対話の応答文選択では，はじめに〈発話文，応答文〉ペアの集合が正例として与えられ，発話文 x にPMI(x, y; X, Y )= log

Pointwise HSIC（PHSIC）

HSIC

2
HSIC(X, Y ; k, ℓ) = ∥mXY − mX m⊤
Y ∥HS
]
[
′
′
e
e
= E
E [k(x, x )ℓ(y, y )]対する最も適当な応答文 y—発話文 x との共起の強さがもっとも大きくなるような応答文 y—を候補集合から選択することがPHSIC(x, y; X, Y , k, ℓ)=(x,y) (x′ ,y ′ )[目的となる．いずれの場合も，はじめに言語表現のペアの集合

= E

(x,y)

D = {(xi , yi )}ni=1 が与えられ，新しいペア (x, y) の共起の強さを(ϕ(x) − mX )⊤ CXY (ψ(y) − mY )⊤計算・推定することになる．

p(x, y)p(x)p(y)]ℓ(y, y ′ )]E [ek(x, x′ )e(x′ ,y ′ )= (ϕ(x) − mX )⊤ CXY (ψ(y) − mY )⊤表2: 本稿で用いる記号．

自然言語処理では言語表現のペアの共起の強さをしばしば⾃k : X ×X → Rℓ : Y ×Y → R
ϕ(x) := k(x, ·)ψ(y) := ℓ(y, ·)⼰相互情報量（PMI）でモデル化する [2]．すなわち，与えられたペアの集合を適当な同時分布 pXY からのサンプル

D = {(xi , yi )}ni=1 ∼ pXY(1)

i.i.d.

ek: X ×X → R
確率分布 X で中心化したカーネル k （eℓ も同様）ek(x, x′ ) := k(x, x′ ) − Ex′ [(x, x′ )] − Ex [(x, x′ )] + Ex,x′ [(x, x′ )]だと考えて，ペア (x, y) の共起の強さをPMI(x, y; X, Y ) = log

pXY (x, y)
pX (x)pY (y)(2)

で測る．与えられたデータ D から PMI を推定する方法をふたつ述べる．ひとつめは頻度による推定である：

d MLE (x, y; D) = log ∑PMIn · c(x, y)∑.
′′y ′ c(x, y ) x′ c(x , y)

X 上の正定値カーネル（直感的には類似度関数）
Y 上の正定値カーネル
k が定める特徴空間における x ∈ X の特徴ベクトルℓ が定める特徴空間における y ∈ Y の特徴ベクトル

本稿では，句や文などの疎な言語表現に適用でき，しかも計算コストの小さい新しい共起尺度を提案する．2 節で提案尺度である Pointwise HSIC（PHSIC）の形式的な定義を与える．

(3)

ここで c(x, y) はペア (x, y) の D 内の頻度を表す．(3)は計算が容易であり，コロケーション獲得*1 など，特に単語同士の共起を測る際にしばしば用いられるが [2]，各 x や y が疎である場合（たとえば句や文である場合）は適用できない．PMI のふた
つめの推定法は RNN を用いるものである．Li ら [9] は対話の応答文生成（各 x や y が文であり非常に疎な場合）に PMI を適用するため*2 ，p(y) を RNN 言語モデル [12] で，p(y|x) を条
件付き RNN 言語モデル [13] でモデル化し，PMI を推定した：b
pCondRNN (y|x).
(4)
bpRNN (y)bpCondRNN (y|x) を学習するコストは大きいが，
pRNN (y) および b(4)の推定法は文や句などの疎な言語表現に対しても適用でき
る．以上のように，頻度による PMI の推定(3)と RNN による
PMI の推定(4)には計算コストと疎性への頑健性というトレー
d RNN (x, y; D) = log
PMI

ドオフがある．我々が知る限り，疎な表現に適用できかつ高速

PMI が「ペア (x, y) の相互情報量への貢献度」であることに対応させ，PHSIC は「ペア (x, y) のカーネル法に基づく依存性尺度 HSIC への貢献度」として定義する (表 1)．3 節で PHSIC が疎性に頑健であることの直感的な説明を与える．PMI は新しいペアとすでに観測されたペアを完全一致で照合するが，PHSIC
はカーネル関数でこれを平滑化した量と見ることができる．4
節で PHSIC の効率的な推定法を示す．5 節で対話の応答文選択の実験をおこない，PHSIC が既存尺度に比べ学習速度が約50 倍高速（2 時間 30 分 7→3 分）で，かつデータ数が少ないときにも予測精度の劣化の程度が小さいことを示す．

X, Y をそれぞれ X , Y に値をとる確率変数とする．本稿では，入力として言語表現のペアの集合 D ={(xi , yi )}ni=1 ∼ pXY を受け取り，与えられたペア (x, y) ∈ X ×Y
問題設定・記号i.i.d.

の “共起の強さ” を測るタスクを扱う．たとえば対話の応答選択タスクがこれに該当する．また提案手法はカーネル法に基づくため，カーネル法に関連する記号をいくつか用意する (表 2)．

に計算可能な共起の尺度は存在しない．
*1 コロケーション獲得において単純に頻度 c(x, y) の高い bigram を探すと，“of the” など高頻度な機能語のペアが上位に上がってきてしまい，連語を探す目的に合わない．
*2 対話の応答文生成において単純に条件付き確率 bp(y|x) の高い y を探すと，“Idon’t know.” など，発話文 x の内容に関わらず用いることのできるありきたり回答（dull responses）が上位に上がってきてしまう．

2

Pointwise HSICPMI は「ペア (x, y) の相互情報量への貢献度」と捉えることができる．これに対応させ，提案尺度 PHSIC は「ペア (x, y) の

HSIC への貢献度」として定義する (表 1)．

― 1268 ―Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

加点どの程度依存しているかは，なんらかの観点で「pXY と pX pY( x , y )確率変数 X と Y の相互情報量は次で定義される [4] ：I(X, Y ) = KL[pXY ∥pX pY ].

(5){. . . , ( xi , yi ), . . . ,( xi , yi ), . . . }

=

,

=

( x , y ),=( x , y ){. . . , ( xi , yi ), . . . ,( xi , yi ), . . . }( x , y )( x , y )≈PHSIC

( x , y )0

相互情報量と⾃⼰相互情報量

02.2

D = {. . . , ( xi , yi ), . . . }≈このようにして定められた確率変数間の依存性の尺度である．

減点( x , y )≈PMIがどの程度異なるか」を測れば良い．相互情報量や HSIC は，=布の積 pX pY が等しいことを言う．ふたつの確率変数 X, Y が0

確率変数 X と Y が独立であるとは，同時分布 pXY と周辺分

表3: PMI と PHSIC の「与えられた (x, y) と観測済みの (xi , yi ) ∈ D たちとの照合の仕方」という観点での比較．

≈

確率変数間の依存性の尺度

02.1{. . . , ( xi , yi ), . . . ,( xi , yi ), . . . }ず PMI の最尤推定量(3)は次のように書き換えられる：

すなわち相互情報量は pXY と pX pY の違いを KL ダイバージn·d MLE (x, y) = log ∑nPMI∑ni=1 I[x = xi ∧ y = yi ]∑.
I[x= xi ] ni=1 I[y = yi ]i=1

ェンスの観点で測った依存性尺度である．

(14)

相互情報量は，同時分布 pXY による期待値の形，つまりペア(x, y) ∈ X × Y 全体での総和の形でも表現することができる：[]
p (x,y)I(X, Y ) = E log p XY.
(6)(x)p (y)ここで I[cond] は指示関数を表し，条件 cond が満たされると網掛け部がまさに⾃⼰相互情報量（PMI）

くは y 側のどちらか一方のみが一致する場合は減点」を繰り返(x,y)

PMI(x, y; X, Y ) =X

Yp(x,y)
log p(x)p(y)(7)

きは 1 を，そうでないときは 0 を返す．(14)によれば，PMI の推定量は「与えられた (x, y) を観測済みの (xi , yi ) ∈ D たちと順に照合し，(x, y) と (xi , yi ) が完全に一致すれば加点，x 側もしした量である (表 3，上側)．
一方，PHSIC(12)の最尤推定量は次の通り：

であることに注意すると，PMI(x, y) は「ペア (x, y) の，相互情bee[ kernel (x, y) = 1 ∑n b
PHSIC
n i=1 k(x, xi )ℓ(y, yi ).

報量 I(X, Y ) への貢献度」と見ることができる．

2.3 HSIC と PHSICHSIC[6] はカーネル法に基づく確率変数間の依存性尺度で，次で定義される：
2
HSIC(X, Y ; k, ℓ) = ∥mXY − mX m⊤
Y ∥HS .

(8)

b

(15)

b

関数 e
k(·, ·)，eℓ(·, ·) はデータで中心化した類似度関数である．

(15)によれば，PHSIC の推定量は「与えられた (x, y) を観測済
みの (xi , yi ) ∈ D たちと順に照合し，x 側と y 側がともに平均bbより似ている場合（ek(x, xi ) > 0 かつ eℓ(y, yi ) > 0 の場合）に加

ここで mX := E[ϕ(x)] は，確率変数 X の特徴空間における期待点*4 ，x 側と y 側のどちらか一方が似ていてもう一方が似てい値で，X のカーネル平均埋め込みと呼ばれる．すなわち HSIC

ない場合は減点」を繰り返した量である (表 3，下側)．

は同時分布 pXY と周辺分布の積 pX pY の違いをカーネル平均

以上のように，PMI と PHSIC の最尤推定量を「与えられた(x, y) と観測済みの (xi , yi ) ∈ D たちとの照合の仕方」という観点で比較すると，PMI は完全一致で照合する一方，PHSIC はx

埋め込みの観点で測った量である．

HSIC も，相互情報量と同様に，同時分布 pXY による期待値の形で表現することができる：[

HSIC(X, Y ; k, ℓ) = E
[
= E

(x,y)

E [e
k(x, x′ )eℓ(y, y ′ )]](x,y) (x′ ,y ′ )](ϕ(x) − mX )⊤ CXY (ψ(y) − mY )⊤ .

(9)ことが分かる．PHSIC がデータの疎性に頑健であることがこ

(10)

3.1

の点からも期待できる．

x

(x,y)

y

沢に存在する．PHSIC はこれらの資産をそのまま活用できる．

(11)• 単語ベクトルの和（加法構成性 [11]）や⽂の分散表現 [8] など，分布仮説に基づく文や句の分散表現が多数提案されてお(9)はデータ空間での表現であり，(10)は特徴空間での表現である*3 ．Pointwise HSIC（PHSIC）を(9)および(10)の網掛け部

り，学習済みのモデルも種々配布されている．これら同士のコサインが簡便で高精度な類似尺度として利用できる．

により定義する：E [ek(x, x′ )eℓ(y, y ′ )](12)

= (ϕ(x) − mX )⊤ CXY (ψ(y) − mY )⊤ .

(13)

PHSIC(x, y; X, Y , k, ℓ) :=(x′ ,y ′ )すなわち PHSIC(x, y) は「ペア (x, y) の，HSIC(X, Y ) への貢献度」である．本節の内容をまとめると表 1の通り．

3• SVM 時代に考案された構造カーネル [3] が多数存在する．
• 正定値カーネルの和や積も正定値カーネルであるため，これ
らの類似度関数を自在に組合せることができる．

PHSIC の推定法と計算量4特徴空間での推定：線形カーネルの場合

PMI と PHSIC の違い：カーネルによる平滑化
PHSIC がデータの疎性に頑健な理由として，
PHSIC は「PMIをカーネルで平滑化した量」だと捉えられることを述べる．ま*3 一般にカーネル法では，データ空間におけるカーネル k(x, x′ ) で特徴空間における内積 ϕ(x)⊤ ϕ(x′ ) を計算できることを用いて，データ空間側で統計処理をおこなう．

既存の類似度関数の活⽤

また自然言語処理には正定値カーネルの形の類似度関数が潤

CXY は X と Y の特徴空間での相互共分散を表す：
CXY := E [(ϕ(x) − E′ [ϕ(x′ )])(ψ(y) − E′ [ψ(y ′ )])⊤ ].

これをカーネル（類似度関数）を用いてスムージングしている

一般に，カーネルk(·, ·) が定める特徴ベクトル ϕ(·) は未知ないし超高次元であり特徴空間での推定は難しい（これをデータ空間で代替するのがカーネル法の特徴のひとつであった）．ところが，昨今の自然言語処理で利用される句や文の類似度は，コサインを用いた線形e*4 x 側と y 側がともに平均より似ていない場合，すなわち bk(x, xi ) < 0 かつbeℓ(y, yi ) < 0 の場合も PHSIC の推定値が増加する．

― 1269 ―Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

カーネルで与えられるケースが多々ある (3.1 節)．コサインとともに用いられる文 x のベクトル表現を x ∈ Rd とすれば，これは特徴空間での表現 ϕ(x) = x/∥x∥2 が陽に与えられているこ

表4: 各モデルの学習時間，単位は秒．各行はモデル，各列は訓練データサイズ
n．RNN の各モデルに付記されているのは次元数および単語埋め込みの初期化法．PHSIC の計算時間は，内数として特徴関数の計算時間 (feat map) と行列計算時間 (mat calc) を付記した．

とに等しい（k(x, x′ ) = ϕ(x)⊤ ϕ(x′ ) = cos(x, x′ )）．このような場

Models合，PHSIC を特徴空間側で推定することが可能である．

PHSIC の特徴空間での表現(13) の最尤推定量は次の通り：
b (ψ(y) − ψ(y))[ RKHS (x, y) = (ϕ(x) − ϕ(x))⊤ C
PHSIC
XY
∑
⊤
1 n
⊤
b
CXY := n i=1 ϕ(xi )ψ(yi ) − ϕ(x) ψ(y) .
ただし ϕ(x) = n1

(16)

∑n

PHSIC

定する必要がある．行列分解を介する簡単な工夫で，データ空間でも(16)と同等の計算量で推定が可能である．詳細は付録 A．

5

実験
PHSIC が疎なデータに適用でき (3 節) しかも計算量が小さ

い (4 節) ことを，対話の応答文選択タスクを通して大規模実データで検証する．提案尺度は RNN を用いた PMI の推定に比べ 50 倍程度高速に学習でき，また訓練データ数が少ない場合も予測精度の劣化が少ないことがわかった．
タスク 対話の応答文選択タスクをおこなう．訓練データとして〈発話文，応答文〉のペアの集合 D = {(xi , yi )}ni=1 が与えられ，評価データの発話文 x 毎に応答文 y を選択肢から選ぶ．
データ インターネットリレーチャットにおける対話ペアを抽出したコーパスを用いる [10]*5 ．訓練データの正例ペア数 n は
約 50 万．検証・評価データの正例ペア数はそれぞれ約 2 万で，各発話文 x に対してコーパス全体から乱択で選択された負例

y ′ が 9 件ずつ割り当てられている（10 択問題となる）．
訓練データサイズの違いが学習時間・予測精度へ与える影響を確かめるため，訓練データ全体を用いる実験のほか，乱択した {102 , 103 , 104 } ペアを訓練データとした実験もおこなう．
計算機環境

CPU：Xeon E5-1650-v3 (3.5GHz, 6 Cores)，
GPU：GTX 1080 (8GB)．
5.1 提案尺度：PHSIC
PHSIC は任意の正定値カーネルを用いることができる．今
回は，もっとも簡単な類似尺度のひとつである「文を構成する
単語ベクトルの和同士のコサイン」∑∑
k(x, x′ ) = cos( wordvecs(x), wordvecs(x′ ))5.2

5 × 105

66.6
112.2

3131.25172.4300

fastTextbp(y)bp(y|x)

2.6
5.7

6.4
12.4

40.1
75.6

2386.84192.3

1200

randombp(y)bp(y|x)

5.4
12.4

19.1
29.0

88.9
142.4

5733.412511.5

1200

fastTextbp(y)bp(y|x)

4.5
19.1

12.0
29.4

67.5
145.6

5672.79414.1

4.4E−2
3.6E−2
8.1E−3

3.7E−1
3.6E−1
1.1E−23.8
3.8
5.0E−2

187.0
184.4
2.6

fastText

量も小さい．学習時はベクトル ϕ(x), ψ(y) ∈ Rd の計算，行列b ∈ Rd×d の計算が必要であり，時間計算量は O(nd 2 )，空間C
XY
計算量は O(nd)．予測時は ϕ(x), ψ(y) ∈ Rd の構成および(16)の計算に O(d 2 ) の時間計算量を要する．
データ空間での推定：⾮線形カーネルの場合 木カーネル [3]等の非線形カーネルを用いる場合は PHSIC をデータ空間で推

104

11.2
24.5

randomi=1 ϕ(xi ) は特徴空間での標本平均．ψ(y) も同様．(16)の計算は行列計算に帰着されており，しかも計算

103

4.1
8.0

300

RNN

(17)

102
b
p(y)
b
p(y|x)

total(feat map)
(mat calc)

ベースライン尺度：RNN ⾔語モデル

訓練データで RNN 言語モデル [12] および条件付き RNN 言語モデル [13] を，
1 層 LSTM[7]，フレームワークは Chainer[14]を用いて学習し，(1) 応答文の尤度 bp(y)，(2) 応答文の条件付き確率 bp(y|x)，および (3)PMI（bp(y|x)/bp(y)）をベースライン
尺度として用いる．隠れ層の次元，および単語埋め込み層の初期化については，以下の設定の組合せで学習する：• 隠れ層の次元：300，1200，• 初期化：[−0.1, 0.1] の一様ランダム，fastText．
ほか設定は以下の通り：• 語彙：頻度 10（n = 5 × 105 ），頻度 2（ほか）以上の語を利用，• ドロップアウト率：0.1（300 次元），0.3（1200 次元），• バッチサイズ：16（n = 102 ），64（n = {103 , 104 , 5 × 105 }），*8 ．
• 最大エポック：30（n = {102 , 103 , 104 }），5（n = 5 × 105 ）5.3 予測精度の評価
PHSIC やベースライン尺度は，各ペア (x, y) に対してなんらかの共起スコア score(x, y) を与える．共起スコアの良さを，Recall@{1,2,5}，すなわち発話文 x に対する 10 個の応答文
候補 yi たちを score(x, yi ) の順に並べたときにトップ {1, 2, 5}個までに正解が含まれる確率で評価する．

5.4

実験結果：計算時間

計算時間に関する実験結果は表 4の通り．約 50 万の訓練データの学習に，既存尺度は，検証セットパープレキシティが最適となるモデル（1200 次元，fastText）で約 2 時間 30 分，

PHSIC と条件を揃えた場合（300 次元，fastText）でも約 1
時間 10 分を要したのに対し，PHSIC の学習は約 3 分で完了した．なお，PHSIC の学習時間のほとんど全ては特徴ベクトルの計算（カーネルの計算）であり，行列計算に帰着させたパラメータ行列・ベクトルの計算は約 2.5 秒で完了している．

5.5

実験結果：予測精度

予測精度に関する実験結果は表 5の通り．約 50 万件の学習(18)を用いる．ℓ(·, ·) も同様．単語ベクトルは，文字 n-gram を活用した単語ベクトル学習アルゴリズムである fastText[1] によりウェブクロールデータ*6 から学習済みの公開資源*7 を利用

データをすべて使ったとき，PHSIC は，RNN を用いた PMIの推定量 4 種の大凡中間の値（既存手法とほぼ同等の予測精度）を示した．
一方，訓練データの数を減らしていくと，既存尺度の予測精する．ベクトルは 300 次元，語彙サイズは 200 万．

*8 最大エポック終了時まで，0.5 エポック（n = 5 × 105 ）または 1 エポック

*5 https://github.com/rkadlec/ubuntu-ranking-dataset-creator*6 http://commoncrawl.org/（ほか）毎に検証セットパープレキシティを計測し，検証セットパープレキ
シティが最良のモデルでの予測精度，および（最大エポックまでに要した時間ではなく）当該モデルを獲得するまでの学習時間を報告する．

*7 https://fasttext.cc/docs/en/english-vectors.html― 1270 ―Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

表5: 各モデルの予測精度（Recall@{1,2,5}）．
5 × 105[7].10, .20, .50 .10, .20, .50 .10, .20, .50 .10, .20, .50

[8]

102

ModelsChance Level

[6]

103

104

b
pRNN (y)1200 fastText .09, .20, .51 .10, .20, .51 .10, .20, .51 .10, .20, .51bpRNN (y|x)

1200 fastText .10, .20, .51 .10, .21, .51 .11, .22, .52 .11, .22, .53
300

random .10, .20, .50 .10, .21, .50 .10, .20, .50 .11, .22, .54
fastText .10, .20, .50 .10, .21, .51 .14, .27, .58 .27, .46, .78

1200

random .10, .20, .50 .10, .20, .51 .11, .22, .53 .15, .30, .65
fastText .10, .20, .51 11, .21, .52 .12, .24, .55 .26, .44, .76

d RNN (x, y)
PMI

PHSIC

fastText.16, .30, .61 .23, .39, .69 .26, .42, .72 .26, .42, .72

度は大幅に劣化するのに対し，PHSIC の予測精度の劣化スピ
ードははるかに緩慢である．すなわち，訓練データや教師デー

Gretton, A. et al. “Measuring Statistical Dependence with HilbertSchmidt Norms”. In: ALT. 2005, pp. 63–77.
Hochreiter, S. and Schmidhuber, J. “Long Short-Term Memory”. In:
Neural Computation 9.8 (1997), pp. 1735–1780.
Kiros, R. et al. “Skip-Thought Vectors”. In: NIPS. 2015, pp. 3294–
3302.
Li, J. et al. “A Diversity-Promoting Objective Function for Neural
Conversation Models”. In: NAACL-HLT. 2016, pp. 110–119.
Lowe, R. et al. “The Ubuntu Dialogue Corpus: A Large Dataset for
Research in Unstructured Multi-Turn Dialogue Systems”. In: SIGDIAL. 2015, pp. 285–294.
Mikolov, T. et al. “Distributed Representations of Words and Phrases
and their Compositionality”. In: NIPS. 2013, pp. 3111–3119.
Mikolov, T. et al. “Recurrent neural network based language model”.
In: Interspeech. 2010, pp. 1045–1048.
Sutskever, I., Vinyals, O., and Le, Q. V. “Sequence to Sequence
Learning with Neural Networks”. In: NIPS. 2014, pp. 3104–3112.
Tokui, S. et al. “Chainer: a Next-Generation Open Source Frameworkfor Deep Learning”. In: LearningSys. 2015.

[9]
[10]
[11]
[12]
[13]
[14]

タの少ないタスクに対して，PHSIC は予測精度の意味でも有付録 A用であることが期待できる．

最尤推定

なお，これらの性質は，評価尺度を ROC-AUC および MRR（平均逆順位）にした場合でも全く同様の傾向が見られた．

自然言語処理でデファクトとなっている共起尺度である

PMI は疎なデータに適用しようとすると大きな学習時間が必要であった (1 節)．我々は Pointwise HSIC（PHSIC）というカーネル法に基づく新しい共起尺度を提案した (2 節)．PHSIC
は，疎なデータに適用でき (3 節)，さらに行列計算に基づく効率的な推定が可能である (4 節)．対話の応答選択の実験の結果，PHSIC は既存尺度の約 50 倍高速に学習が完了し，しかも同等の予測精度を示した．さらに，データ数が少ない場合の予測精度の劣化の程度も小さいことが分かった (5 節)．
今後の研究方針を述べる．(1)(16)式を用いると，与えられた
ϕ(x) に対するもっとも適切な ψ(y) を（定数倍の不定性を除いて一意に）⽣成することができる．深層学習ベースの文のデコーダを用いれば ψ(y)（特徴ベクトル）から y（文）を復元できることが期待できるため，「強い共起を持つ文の高速生成」が実現する可能性がある．(2) 文の埋め込み手法の性能は，それを深層学習器の入力に用いてさらに学習をおこなった予測器を介して，外部タスクの精度で計られることが多い．すなわち予測器の性能と分散表現の性能が混ざった状態でしか評価をおこなうことができない．一方提案手法はノンパラメトリックなカーネル法であるため，予測器の性能を除いた状態で分散表現の性能を評価できる可能性がある．(3)PHSIC は幅広い類似度尺度を用いることができる (3.1 節)．今回はもっとも簡単な類似度尺度を用いたが，様々なタスクに対してタスクに見合った多様なカーネルを用いた実験も魅力的な今後の研究課題である．
謝辞

東京大学の胡緯華氏からの有益な助言に感謝します．本

研究の一部は文部科学省科研費 15H01702 の支援を受けた．

[2]
[3]
[4]
[5]

ここで k := (k(x, x1 ), . . . , k(x, xn ))⊤ ∈ Rn ，ℓ も同様．しかしこ
よび L1 ∈ Rn の計算が必要で，時間計算量は O(n2 )，空間計算量は O(n)．予測時はベクトル k, ℓ ∈ Rn の構成および H を掛け合わせる計算に O(n) の時間計算量を要する．
不完全コレスキー分解を介した推定

推定量(19)の計算コストが大きかったのは，グラム行列 K, L の構成が必要だったからであった．カーネル法ではグラム行列を陽に構成せずにその近似を低コストで計算する方法がいくつか提案されており，不完全コレスキー分解 [5] もそのひとつである．不完全コレスキー分解
により，{x1 , . . . , xn } ⊆ X および正定値カーネル k : X × X → R
から，行列 A = (a1 , . . . , an )⊤ ∈ Rn×d (d ≪ n) を時間計算量

O(nd 2 ) で得ることができる．これにより，グラム行列 K 全体を構成することなく，ai ∈ Rd たちによってカーネルを近似的⊤．
に計算できるようになる（a⊤i aj ≈ k(xi , xj )，AA ≈ K ）HSIC にも不完全コレスキー分解を介した推定法が提案されている [6]：[ ICD (X, Y ) = 12 ∥(HA)⊤ B∥F
HSIC
(20)
n

ただし A = (a1 , . . . , an )⊤ ∈ Rn×d は不完全コレスキー分解により計算した AA⊤ ≈ K なる行列であり，B も同様（BB⊤ ≈ L）．

(20)はデータによる平均の形でも表現することができる：[]⊤Cb (bi − b) . (21)[ ICD (X, Y ) = 1 ∑n
HSIC
(a
−
a)
i
ICD
n i=1
1
n
⊤
b
ただし C
ICD := n (HA) B．また a は {ai }i=1 の平均，b も同様：

a := n1 A⊤ 1 = n1∑ni=1 ai .

(22)

PHSIC(x, y) はペア (x, y) の HSIC(X, Y ) への貢献度であったので，PHSIC は(21)の網掛け部により推定できる：

b (b − b) .
[ ICD (x, y) = (a − a)⊤ C
PHSIC
ICD

(23)

ここで新しい x ∈ X に対応するベクトル a ∈ Rd は，不完全コ

参考⽂献
[1]

PHSIC のデータ空間での表現(12)の最尤推定量は，[ kernel (x, y) = (k − 1 K1)⊤ ( 1 H)(ℓ − 1 L1).
PHSIC
(19)
n
n
n

の推定方法は計算コストが大きい．学習時は縦ベクトル K1 お

おわりに

6

データ空間での PHSIC の推定

レスキー分解のアルゴリズムを「途中から行う」ことで計算でBojanowski, P. et al. “Enriching Word Vectors with Subword Information”. In: TACL 5 (2017), pp. 135–146.
Church, K. W. and Hanks, P. “Word Association Norms, Mutual
Information, and Lexicography”. In: ACL. 1989, pp. 76–83.
Collins, M. and Duffy, N. “Convolution Kernels for Natural Language”. In: NIPS. 2002, pp. 625–632.
Cover, T. M. and Thomas, J. A. Elements of Information Theory.
John Wiley & Sons, 2006.
Fine, S. and Scheinberg, K. “Efficient SVM Training Using Low-Rank
Kernel Representations”. In: JMLR 2.Dec (2001), pp. 243–264.

きる．分解中に採用された支配的な xi たちを順に x(1) , . . . , x(d)とすると，a の第 j 成分 a(j) は以下で計算できる（b も同様）．

a(j) = [k(x, x(j) ) −∑j−1

m=1 a(m)Ajm ] / Ajj .

(24)

不完全コレスキー分解を介した PHSIC の推定(23)はナイーブ
な推定(19)に比べて極めて効率的であり，計算量は線形カーネ
ルを用いた特徴空間での推定(16)と同等．

― 1271 ―Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.