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

バイナリ CP 分解モデルのビット反転学習法† 林 克彦 a,∗

岸本 広輝 b,∗
新保 仁 ca 東京大学 大学院情報理工学系研究科
b 大阪大学 産業科学研究所
c 千葉工業大学 ステアラボ† khayashi0201@gmail.com

1

はじめに

表 1: KGE モデルの比較: 表現力は任意の三次隣接テ

知識グラフ埋め込み (KGE) は知識獲得，推薦，質ンソル X ∈ {0, 1}Ne ×Ne ×Nr を再現可能な次元数．

問応答などを応用先とし，NLP や AI 分野で盛んに研モデル

計算量スコア関数

表現力究されている．KGE では一般にエンティティと関係といった大規模な知識グラフには数百万から数十億単TransE 等
RESCALDistMult
CP

O(D) − O(KD)O(D2 )O(D)O(D)−||p(ai ) + bk − p(a j )||aTi Ba j⟨ai , a j , bk ⟩⟨ai , b j , ck ⟩7Ne
7Ne Nr位のエンティティが含まれるため，埋め込みモデルのB-CPO(D)−h(ai , XNOR(b j , ck ))8Ne Nrを実数ベクトルとして表現するが，YAGO や Freebase

軽量化が重要な課題となる．

• 実装が容易 (著者の github に公開予定)

岸本ら [5] は KGE に対する CP テンソル分解モデ
ルのパラメータを全てバイナリ化するバイナリ CP 分解モデル (B-CP) を提案し，タスク性能を保ったまま，従来の KGE モデルより数十倍コンパクトな埋め込みを実現した．さらに，彼らは B-CP が知識グラフをモデル化するのに十分な表現力を持つことも理論的に証明している [4]．表 1 に B-CP モデルの概要，及び，他の KGE モデルとの比較をまとめる．

B-CP の学習は Hinton 法 (HSTE) [1] に基づいており，勾配学習の中で量子化関数によって強制的に実数ベクトルを離散化してバイナリベクトルを構築する．
そのため，学習では数百から千数百次元の実数ベクトルを保持することになり，学習時のメモリ効率は悪い．
また，実数ベクトルを強制的に離散化するため，学習収束の観点からも効率的な学習法とは言えない．
本稿では B-CP の学習に使う目的関数 (ここではロジスティック損失関数) をバイナリベクトルのまま直接最適化する新しい学習法を提案する (ビット反転学習法)．提案法ではバイナリベクトルのある次元パラメータ (ビット) を反転した場合の目的関数の変化を計算し，1 ビットずつ目的関数が改善するように山登り法で学習を行う．提案法は単純であり，• ハイパーパラメータが少ないという利点を持つ．さらに，ベンチマークデータセッ
トを用いた実験から，良好な結果が得られたのでここに報告する．
知識グラフ以外にも，単語やネットワークの埋め込みをバイナリ化する手法は研究されているが [6]，提案法はそれらへの応用も十分に期待される．

2準備
ベクトル，行列，テンソルをそれぞれ太字かつ小文

字 (a)，太字かつ大文字 (A)，カリグラフィック体 (X )で表す．行列 A の i 番目の行ベクトルを ai: ， j 番目の列ベクトルを a: j または a j と表す．ベクトル，行列，テンソルの各要素を ai , ai j , xi jk と表す．
記号 ◦ はアダマール積，⊗ は外積を表す．3 つの (行または列) ベクトル a, b, c ∈ RD が与えられたとき，三重内積を ⟨a, b, c⟩ = ∑d∈[D] ad bd cd として定義する．[D]は 1, 2, · · · D の自然数の集合を表す．
三次テンソル X ∈ RI1 ×I2 ×I3 が 3 つのベクトルの外積 X = a ⊗ b ⊗ c で表せるとき，これをランク 1 テン

∗ これらの著者は本稿に等しく貢献した．

ソルと呼ぶ．

― 704 ―

Copyright(C) 2020 The Association for Natural Language Processing.
All Rights Reserved.

3 バイナリ CP 分解モデル (B-CP)

Algorithm 1 Greedy Bit-flip Training Algorithm

知識グラフは主語・目的語のエンティティei , e j ，及び，それらの間の関係 rk から成る事実 (ei , e j , rk ) の集合である．集合に存在する事実を 1，存在しない事実を 0 として，知識グラフは三次隣接テンソル X ∈ {0, 1}Ne ×Ne ×Nrで表せる．ここで Ne はエンティティ数，Nr は関係数を表す．

CP 分解はテンソルを D 個のランク 1 テンソルの線形和によって分解する．知識グラフを表した三次隣接テンソル X に対する CP 分解はInitialize
A, B ∈ {−1, +1}Ne ×DN×DrC ∈ {−1, +1}2: DL = {1, . . . , D}
3: for iter ∈ {1, . . . , I} do
4:
Negative Sampling // 負例を生成
5:
Update(C, Nr , DL) // 関係の因子行列の更新
6:
Update(A, Ne , DL) // 主語の因子行列の更新
7:
Update(B, Ne , DL) // 目的語の因子行列の更新
8:
Flush Negative Samples // 負例をクリア
9:Convergence Check // 収束判定
10: end for
1: RandomandAlgorithm 2 Update(M, N, DL)

X ≈ ∑ ad ⊗ bd ⊗ cdd∈[D]として表せる．B-CP では普通の CP 分解とは異なり，ad ∈ {−1, +1}Ne , bd ∈ {−1, +1}Ne , cd ∈ {−1, +1}Nr として，実数ベクトルの代わりにバイナリベクトルを用いる．行列 A = [a1 a2 · · · aD ] は因子行列とし，B, C も同様に定義する．X の要素 xi jk は ⟨ai: , b j: , ck: ⟩ で近似される．ai: , b j: , ck: はそれぞれ主語，目的語，関係に対する D ビットのバイナリベクトルである．

1: Random Shuffle DL
2: // N に対して非同期な並列処理が可能
3: for i ∈ {1, . . . , N} do
4:for j ∈ DL do
5:
if ∆(mi j ) < 0 then6:
mi j = −mi j7:
end if
8:
end for
9: end for

4

B-CP のビット反転学習法

本稿では知識グラフに対する B-CP の学習を二値分提案法では B-CP の因子行列 A, B, C における 1 つ類問題として考え，ロジスティック回帰による定式化の要素 (ビット) を反転させたとき，目的関数が向上を行う．まず，各 xi jk が因子行列 A, B, C から独立にすれば，それを反転させるという作業を繰り返して学生起すると仮定し，習を進める．アルゴリズム全体の流れは Algorithm 1，p(X |A, B, C) = ∏及び，2 に記述した通りである．

∏ ∏ p(xi jk |θi jk )Algorithm 1 ではある因子行列を更新する際，残りi∈[Ne ] j∈[Ne ] k∈[Nr ]を考える．ある事実 (ei , e j , rk ) に対するスコアは θi jk =⟨ai: , b j: , ck: ⟩ として定義される．また，確率変数 xi jk がxi jk ∼ Bernoulli(σ (θi jk )) と仮定すると，事後確率は以下のように定義される．
{σ (θi jk )p(xi jk |θi jk ) =1 − σ (θi jk )関係の数 Nr はエンティティの数 Ne よりかなり少ない
ため，1 つの関係に対するパラメータの更新が目的関数に与える影響は大きい．よって，ここでは関係の因子行列 C を先に更新することで収束を早めるように

if xi jk = 1,
if xi jk = 0

工夫している．

.

Algorithm 2 では因子行列の更新を実際に行う．注
意として，因子行列の行要素 (関係やエンティティ) はシグモイド関数 σ (x) = 1/(1 + exp(−x)) とする．

独立に処理できるため，Algorithm 2 は行要素に対してここでは最大事後確率の負の対数尤度{}
argmin E(A, B, C) = ∑ ∑ ∑ Ei jk .
A,B,Cの 2 つの因子行列は固定する．知識グラフにおいて，非同期な並列処理が可能である．一方で，列要素 (次元数) に対しては更新順序が他の列要素の更新に影響を与えるため，次元の集合 DL をシャッフルすること

i∈[Ne ] j∈[Ne ] k∈[Nr ]でその影響を軽減する．

Algorithm 2 の更新では，因子行列の 1 つの要素をEi jk = xi jk log(σ (θi jk )) + (xi jk − 1) log(1 − σ (θi jk ))反転させたときの目的関数の変化を計算する必要があを目的関数とし，それを最小化することで学習を行う．

る．例えば，因子行列 A の要素 ai j を −ai j に反転した
ときの因子行列を A′ とし，そのときの目的関数の差分 ∆(ai j ) = E(A′ , B, C) − E(A, B, C) を考える．∆(ai j )― 705 ―

Copyright(C) 2020 The Association for Natural Language Processing.
All Rights Reserved.

は以下の等式で表される．
((∆(ai j ) = ∑ ∑ xiyz log

表 2: 知識グラフ補完精度の評価用データセット．

)
σ (θiyz )σ (θiyz − 2ai j by j cz j )y∈[Ne ] z∈[Nr ]())
1 − σ (θiyz ).
+ (1 − xiyz ) log
1 − σ (θiyz − 2ai j by j cz j )WN18RR

FB15k-237

40,5591186,835
3,034
3,134

14,505237
272,115
17,535
20,466NeNr
訓練サンプル数
開発サンプル数
テストサンプル数

この変化が目的関数を向上させる場合，ai j = −ai j としてビット反転して更新を行う1 ．因子行列 B, C についても同様である．提案法では目的関数は必ず向上す

WN18RR依存するため，局所解に陥る可能性がある．学習は目

402030的関数の向上が見られなくなるか，事前に定めれたエ20

ポック回数が終わると終了する．

FB15k-237

30Filt.MRR

50Filt.MRR

るように更新が行われるが，パラメータの更新順序に

D=200
D=400
D=600
HSTE

1010以下では，学習を高速化するための実装上の主要な0工夫について説明する．

51015Train Epochs

200

51015Train Epochs20

図 1: WN18RR，及び，FB15k-237 でのエポック数 vs

4.1 ビット演算によるスコア計算の高速化

モデル精度: MRR は開発データ上で計測した．

Algorithm 2 ではスコア θi jk の計算が繰り返し行われる．学習を高速に行うには，スコア計算の高速化が(ei , e j , rk ) に対して，ランダムサンプリングしたエン必須である．対処法の 1 つとして，全ての事実のスコアをキャッシュしておく事も考えられるが，事実の数は非常に多いため，メモリ効率の観点から，ここではビット演算によるスコア計算の高速化を考える．
実際，B-CP のスコア計算はビット演算を使って計

ティティe によって，負例 (ei , e, rk ) を生成する．また，逆関係を持つ正例 (e j , ei , rk−1 ) には，ランダムサンプリングしたエンティティe によって，負例 (e, ei , rk−1 ) を生成する．1 つの正例当たり，これらを事前に定められた負例サンプル数分だけ行う．

算することができる．

5 実験

θi jk = D − 2h(ai: , XNOR(b j: , ck: )).
ここで h(·, ·) はハミング距離，XNOR(·, ·) は排他的論

5.1 データセット・評価方法・実験設定

理和の否定を表す．文献 [5] でも報告されているように，D が数百次元の場合，ビット演算によるスコア計KGE モデルの精度を評価するため，標準の知識グ算は実数ベクトルの三重内積よりも約 50 倍高速に計

ラフ補完データセット WN18RR，及び，FB15k-237 を算できるため，スコア計算のコストはほとんど無視で用いた (表 2)．これらは他のデータセットよりも補完きるものとなる．

が難しいことで知られている．
テストデータ中の事実 (ei , e j , rk ) における ei (またはe j ) を eℓ (ℓ ∈ [Ne ]) に置き換え，スコアで降順にソート

4.2 負例サンプリング

して，元の事実の順位を平均逆順位 (MRR) と Hits@1,目的関数の計算において，全ての負例を考慮することは現実的ではない．そこで従来法の慣習に従い，負3, 10 で評価した．複数の正解事実が存在する場合，対象としている事実以外を除いた (Filterd 設定)．

例サンプリングによって目的関数を近似する．文献 [3]実験では次元数 D ∈ {200, 400, 600} を調べ，MRR

で提案されたように，B-CP の訓練では正例となる事を開発データ上で最大化するハイパーパラメータを求実 (ei , e j , rk ) が存在するとき，逆関係の事実 (e j , ei , rk−1 )めた．A, B, C は標準正規分布に従う bool 型の擬似乱も正例として追加する．ここで負例サンプリングは，数によって初期化し，負例サンプルは 1 つの正例当た

1 更新に関連する事実へのアクセスは単純な Trie 構造を利用しり，WN18RR で 5 個，FB15k-237 で 20 個生成した．

たが，より効率の良いデータ構造を考えることもできる．

― 706 ―

Copyright(C) 2020 The Association for Natural Language Processing.
All Rights Reserved.

表 3: WN18RR，及び，FB15k-237 での知識グラフ補完精度の比較: *の結果は文献 [2] から抜粋.
WN18RR

Models1310の形式の質問文を 553,774 文取り出した．そして，x

Hits@

MRR

ングしたいことはよくある．ここでは FB15k-237 のテ
ストデータから目的語が共通する事実 2 つを選び，上FB15k-237

Hits@

MRR

に対して，変数 x に当てはまるエンティティをランキ

1310に対する最良の目的語を探索した際の探索時間を計算した．

DistMult*

43.0

39.0

44.0

49.0

24.1

15.5

26.3

41.9

ComplEx*

44.0

41.0

46.0

51.0

24.7

15.8

27.5

42.8

R-GCN*

––––

24.8

15.3

25.8

41.7

ConvE*

43.0

40.0

44.0

52.0

32.5

23.7

35.6

50.1

HSTE

46.0

44.0

47.0

52.0

29.5

21.0

32.448.3

B-CP (400)

47.7

44.7

48.9

53.3

27.6

19.5

30.1

43.7±0.2±0.3±0.2±0.1±0.0±0.1±0.1±0.1

B-CP (400 × 2)

48.8

45.7

50.0

54.5

28.7

20.5

31.4

45.1

B-CP (400 × 3)

49.0

46.0

50.1

54.7

29.0

20.7

32.045.6

結果は 800 次元のバイナリベクトルで総時間 141 秒となった (1 クエリ当たり 0.0002 秒)．実数ベクトルではそのおよそ 200 倍となった．また，目的語をそれぞれの事実単独で予測した際の Filtered なしの MRR 精
度の平均は 81.1 であったのに対し，同時に予測した

B-CP (400 × 4)

49.1

46.1

50.3

54.9

29.3

21.0

32.1

45.9際の精度は 84.6 で向上が見られた (表 3 よりも精度

B-CP (400 × 5)

49.1

46.0

50.2

55.0

29.5

21.2

32.3

46.0

が高いのは，一般に目的語の方が当てやすいからである．)．これらの結果より B-CP は確率データベース検

最大エポック数は 20 とした．時間の計測は 2.7GHz

索でも有効に活用できる可能性があると言える．

Intel Core i7 の CPU を積んだラップトップ PC で行った．WN18RR に対する 400 次元のモデルは 8 並列処理で 20 エポックを約 7 分で終了した．

6 まとめ

5.2 主な実験結果

ラメータのまま学習する新たな手法を提案し，実験を

本稿では KGE に対する B-CP モデルをバイナリパ

図 1 には訓練のエポック毎の MRR 精度を示した．
提案法は訓練の早い段階で学習が収束しているが，これはパラメータの冗長性が少ないためだと考えられる．

通して，その有効性を示した．
現在，提案法の拡張を進めるべく，単語バイナリ埋め込みモデル Word2Bits [6] への拡張を検討している．

また，両データにおいて，次元数 400 で最良の結果が得られたので，テストデータ上での評価には 400 次元のモデルを用いた．
表 3 ではテストデータ上でのモデル精度を比較した．
提案法の初期値依存性を調べるため，パラメータ初期化に用いるランダムシードを変えて，モデルを 5 つ構築した．結果はそれらの精度の平均値と標準偏差を示しており，提案法は初期値に大きく依存することなく，従来法と遜色ない精度が得られた．注意として，提案法はバイナリベクトルのため，従来モデルと同次元数であれば，大まかに 1/32 のメモリ使用量となる．
提案法が軽量かつスコア計算が高速である利点を活かし，5 つのモデルをアンサンブルした．表 3 の結果
より，複数のモデルを用いることでモデル性能が向上することを確認した．

5.3 クエリ検索速度
KGE の応用先の 1 つに確率データベース検索がある．例えば，次のような質問文

参考文献[1] Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville.
Estimating or propagating gradients through stochastic neurons for conditional computation. CoRR, Vol.
abs/1308.3432, , 2013.
[2] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, andSebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proc. of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pp. 1811–1818, 2018.
[3] Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Proc. ofthe 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 4289–4300, 2018.
[4] Koki Kishimoto, Katsuhiko Hayashi, Genki Akai, andMasashi Shimbo. Binarized canonical polyadic decomposition for knowledge graph completion. arXiv preprint
arXiv:1912.02686, 2019.
[5] Koki Kishimoto, Katsuhiko Hayashi, Genki Akai, Masashi
Shimbo, and Kazunori Komatani. Binarized knowledge
graph embeddings. In European Conference on Information Retrieval (ECIR), pp. 181–196. Springer, 2019.
[6] Maximilian Lam. Word2bits - quantized word vectors.
CoRR, Vol. abs/1803.05651, , 2018.

Q(x) : ∃x.(ei1 , x, rk1 ) ∧ (ei2 , x, rk2 )― 707 ―

Copyright(C) 2020 The Association for Natural Language Processing.
All Rights Reserved.