DEIM Forum 2019 A4-5

多次元関係データに対する潜在変数モデルのための双対分解による推定
井上曜†

梅原頌平†

江口浩二††

神戸大学 〒 657–8501 神戸市灘区六甲台町 1-1
E-mail: †{ainoue,umehara}@cs25.scitec.kobe-u.ac.jp, ††eguchi@port.kobe-u.ac.jp
あらましオブジェクト間の関係を表す関係データはグラフとして表現することができ，そのときグラフにおける頂点はオブジェクト，辺は関係に対応する．また，複数種類の関係からなる多次元関係データは，複数種類の辺からなる多モードネットワークとして表現できる．ウェブ検索クエリログでのクエリ間の複雑な関係や属性付き社会ネットワークを多次元関係データあるいは多モードネットワークと見なすことができ，筆者らは, この問題を解決するために多モードブロックモデル（multi-mode blockmodel）を提案した．本論文では多モードブロックモデルを推定するため，双対分解を用いる推定手法を提案する．現実の検索クエリログと属性付き社会ネットワークのデータを用いた実験により，提案手法の有効性を示した.
キーワード 潜在変数モデル, 双対分解, 多次元関係データ, クエリクラスタリング, 社会ネットワーク分析
定されている. それに対して, 関係データにおける各オブジェ

1 序論

オブジェクト間の関係を表す関係データはグラフとして表現することができ，そのときグラフにおける頂点はオブジェクト，辺は関係に対応する．また，複数種類の関係からなる多次元関係データは，複数種類の辺からなる多モードネットワークとして表現できる．多次元関係データの例は枚挙に暇がないが，共通の趣味を持つ人間関係や共通の出身校である人間関係などからなる社会ネットワークが典型的である． ウェブ検索クエリ
ログにおいても共通のウェブページに対してクリックが行われたクエリの対や，同一の検索セッションにおいて投入されたクエリの対，部分的に共通した文字列からなるクエリの対などのような，クエリ間の複雑な関係を多次元関係データあるいは多モードネットワークと見なすことができる．
さて，種々の離散データ集合の分析手段の一つとして混合多項分布モデル（Multinomial mixture models) [1] やそれを拡張したトピックモデル（Topic models）[2] が有効であることが知られている．文書データ集合を例にとって説明すると，混合多項分布モデルは文書毎に単語の分布として表現される潜在的なトピックが背後に存在すると仮定するモデルである．ここでは文書毎に一つの潜在トピックが対応付けられるのに対しクト対について異なるトピックを仮定するスパースブロックモデル（Sparse block model: SBM）[5] がある．これらのモデルは均質な関係データやネットワークを想定したものであり，多次元関係データや多モードネットワークにおける種々の関係の不均質性を捉えることはできない．
以上の問題を解決するために，筆者らは多モード・ブロックモデル（multi-mode block model）を提案した [8]．このモデルは多モードで構成されるネットワークをモデリングするもので，各モードが共通のトピックの分布から生成されると考えるものである．ここでは, 推定手法としてギブスサンプラーが用いられた. これらの推定では各モードを逐次的に推定する事で実現している. しかし, これらの推定手法は逐次的に推定をおこなう事から, 最後に推定したモードに強く依存してしまうという問題点がある. そこで本論文では変分ベイズ推定の過程で双対分解 [7] を用いることで, 効率的かつ, 特定のモードに依存しない推定を行う. さらに本論文では現実の検索クエリログのデータと離散関係属性付き社会ネットワーク用いた実験により，提案手法の多モード・ブロックモデルの有効性を評価する．

2 関連研究て，トピックモデルは各文書を複数の潜在トピックの混合分布

ここでは提案手法に関連した研究として，混合多項分布モデとして表現するモデルである．トピックモデルの代表的なもの

ル及びバイタームトピックモデル，スパースブロックモデルにとしては潜在ディレクレ配分法（Latent Dirichlet Allocation:ついて説明する．

LDA）[3] が挙げられる．混合分布モデルやトピックモデルの適用範囲は広く，その拡張形が関係データやネットワークの分析にも適用されている．
関係データまたはネットワークを扱えるトピックモデルの一つとして，短い長さのテキストデータにおける単語間の関係に着目したバイタームトピックモデル（Biterm topic model:BTM）[4] が挙げられる. バイタームトピックモデルでは関係データにおける各オブジェクト対について共通のトピックが仮

2. 1 混合多項分布モデル
混合多項分布モデル (Multinomial of mixture models) は，文書毎に単語の分布として表現される潜在的なトピックが背後に存在すると仮定するモデルである．すなわち各文書はそれぞれ 1 つのトピックで表現され，文書内の単語はそのトピックから生成される．またトピックはそれぞれ異なった単語分布として表現される．混合多項分布モデルのグラフィカルモデルを図図 1 Grephical model representation of multinomial mixture

図 2 Grephical model representation of BTM.

model.

（ 1 ） バイターム集合全体に対し，θ ∼ Dirichlet(α) を選択

1 に示す．図中の D, Nd , K はそれぞれ文書数，文書 d の単語する．

数，トピック数である．θ, ϕk はそれぞれトピックの多項分布パ（ 2 ） K 個のトピックに対し，ϕk ∼ Dirichlet(β) を選択

ラメータ，トピック k に関するデータの多項分布パラメータでする．

ある．α, β はそれぞれ上記 2 種類の多項分布に対応するディレ（ 3 ） バイターム b に対し:

クレハイパーパラメータである．混合ユニグラムモデルにおけa トピック zb ∼ M ultinomial(θ) を選択する.

る文書の生成過程を以下に示す．

b バイタームの 2 単語 wbi , wbj に対し，単語 wbi , wbj ∼M ultinomial(ϕzb ) を選択する．

（ 1 ） 文書全体に対し，θ ∼ Dirichlet(α) を選択する．
（ 2 ） K 個のトピックに対し，ϕk ∼ Dirichlet(β) を選択

2. 3 スパースブロックモデル
スパースブロックモデルは，タンパク質の相互作用や社会する．
（ 3 ） 文書 d に対し:a トピック zd ∼ M ultinomial(θ) を選択する.

ネットワークの分析などの関係データ間のリンクをモデリングするブロックモデルである．関係データにおける各オブジェク

b Nd 個の単語 wdi に対し，単語 wdi ∼ M ultinomial(ϕzd ) ト対についてそれぞれ異なるトピックを仮定していることが2.2 節の BTM との違いである．スパースブロックモデルのグを選択する．
ここで Dirichlet はディレクレ分布，M ultinomial は多項分

ラフィカルモデルを図 3 に示す．L はリンクの集合を表し，図布を表している．

中の |L| はその総数を表す．スパースブロックモデルにおける生成過程を以下に示す．

2. 2 バイタームトピックモデル
バイタームトピックモデル (Biterm Topic Model: BTM) は，（ 1 ） リンク全体に対し，θ ∼ Dirichlet(α) を選択する．

短い長さのテキストデータに対して単語共起性に着目したト（ 2 ） K 個のトピックに対し，ϕk ∼ Dirichlet(β) を選択

ピックモデルである．従来のトピックモデル (LDA や PLSA)する．

は文書単位の単語共起性を捉えるものであるため，ショートテ（ 3 ） リンク ℓ = (i, j) に対し:キストでは単語共起性が疎になるという問題を抱えている．そa トピックペア zℓ ∼ M ultinomial(θ) を選択する.

こで BTM はコーパス全体の単語共起性を捉えることでこの問b リンク ℓ の両端の 2 つのエンティティwli , wlj に対題を解決しようとしている．BTM では関係データにおける各し，オブジェクト対を「バイターム」として抽出して考える．BTM

エ ン ティティwliの特徴として，同じバイタームの 2 つのオブジェクトは同じト∼M ultinomial(ϕz1 ), wlj∼

M ultinomial(ϕz2 ) をそれぞれ選択する．

ピックに属すると仮定されている．BTM のグラフィカルモデ

ここで zℓ = (z1 , z2 ) であり，単一のトピックではなくトピックルを図 2 に示す．B はバイタームの集合を表し，図中の |B| はの対を指しており，それぞれのトピックからエンティティが選その総数を表す．BTM における文書の生成過程を以下に示す．

択される．また，z = {z}ℓ である．

図 5 multi-mode network.

図 3 Grephical model representation of Sparse Block Model.

しかし，2.2 節のバイタームトピックモデルや 2.3 節のスパー
スブロックモデルは通常のネットワークのような均質なリンクに対して提案されており，そのまま適用するのは困難である．

3 提案手法筆者らは多モードネットワークに関する上記の問題を解決する

3. 1 多モード・ブロックモデルために，スパースブロックモデルを拡張した多モード・ブロッ
クモデルを提案した [8]．バイタームトピックモデルではなくスネットワークにおいて辺が二種類の集合に分かれるようなパースブロックモデルを拡張したのは，リンクの両端の 2 つのネットワークを 2 モードネットワーク集合と呼ぶ．この 2 モーエンティティが常に同じトピックに属するというバイタームトドネットワークを一般化し，均質でない辺からなるネットワー

ピックモデルの仮定は, 現実の社会ネットワークなどにおいてクを多モードネットワークとする．図 5 は 2 モードネットワーは考えにくいからである．このモデルは多モードネットワーククの例を示し，図 6 は多モードネットワークの例を示す．2 モーの各辺が T 種類に分けられるとき，各種類のリンクが共通のトドネットワークでは 2 種類の辺に分かれており，多モードネッピックの分布から生成されると考える．図 6 は T = 3 のとき

トワークでは複数種類 (図中では 3 種類) に分けられている．この多モード・ブロックモデルのグラフィカルモデルを示していのような多モードネットワークの例として，共通の趣味を持つる．多モード・ブロックモデルの生成過程を以下に示す:

人間関係や共通の出身校である人間関係などからなる社会ネッ（ 1 ） タイプ t のリンク全体に対し，θt ∼ Dirichlet(αt ) をトワークや検索クエリログにおける検索クエリ間の多様な関係選択する．

がある．

（ 2 ） K 個のトピックに対し，ϕk ∼ Dirichlet(β) を選択する．
（ 3 ） タイプ t のリンク lt = (i, j) に対し:a トピック対 zlt ∼ M ultinomial(θt ) を選択する.
b バ イ タ ー ム の 2 単 語 wlt i , wlt j に 対 し ，単 語 wli ∼M ultinomial(ϕz1 ), wlj ∼ M ultinomial(ϕz2 ) をそれぞれ選択する．

3. 2 モデルの推定
3. 2. 1 変分ベイズ推定によるモデルの推定
多モード・ブロックモデルの変分ベイズ推定は N 種類のリンクを順に推定する事で行う. それぞれの種類のリンクは独立なトピック対分布から生成されるので変分下限の式は以下の通りである.

図 4 2-mode network.

log P (D|α, β)∑∑∑∑∑>
qlk1 k2 (Ψ(αk1k2 ) − Ψ(αk1 k2 ))=lk1k2k1k2+ log Γ(αK ) − K log(Γ(α)∑∑∑∑+ (α − 1)(Ψ(αk1 k2 ) − Ψ())
2+(2∑∑∑lk1k1′k1k2′k2∑
qlk1 k2 (δl1v (Ψ(βk1 l1 ) − Ψ(βk1 v ))k2∑
+ δl2v (Ψ(βk2 l2 ) − Ψ(βk2 v )))vv+ K log(βV ) − KV log Γ(β)∑∑∑+ (β − 1)(Ψ(βkv ) − Ψ(βkv′ ))+∑∑∑nlkv′v

qdnk log qdnkk∑∑∑∑+ logΓ(αk1 k2 ) −log Γ(αk1 k2 )k1k2k1k2k1k2∑∑∑∑+(αk1 k2 − 1)(Ψ(αk1 k2 ) − Ψ(αk1′ k2′ )∑∑∑+(log Γ(βkv ) −log Γ(βkv )kv′k1k′ 2v∑∑+(βkv − 1)(Ψ(βkv ) − Ψ(βkv′ )))v

(1)v

ここで αk1 k2 はトピック対分布に関するディリクレ事前分布パラメータ,βvk は単語分布のディリクレパラメータを表す. そして, この式の右辺に与えられている下界を最大化するような βと α を推定する.α と β と辺の両端の頂点に割り当たるトピッ
クの対が k1 ,k2 である確率 qlk1k2 の更新式は以下のようになる.

αk1 K2 = α + qlk1 k2
βkv = β +(2)∑∑(ql1 kk′ + ql2 k′ k )δlvk′(3)l図 6 Graphical model representation of Multi-mode block model.

qlk1 k2 = exp(Ψ(αk1 k2 ) − Ψ(∑∑k1∑+ Ψ(βk1 v ) − Ψ(βk1 v )αk1 k2 )k2v∑+ Ψ(βk2 v ) − Ψ(βk2 v ))(4)v

3. 2. 2 双対分解を用いた変分ベイズ推定によるモデルの推定
前節までの推定手法では逐次的に推定をおこなう事から, 最後に推定したモードに強く依存してしまうという問題点がある.
そこで, 双対分解を用いることで効率的かつ特定のモードに依存しない推定を行う. N 種類のリンクの各最適化問題を統合する事によって, 以下のような最適化問題を定義する事が出来る.

argmax f1 (β) + f2 (β) + . . . + fN (β)β

ここで各 f (β) は変分下限の式, すなわち(5)ここで, µ はステップ幅であり, 本研究では Step Decay を用いf (β)∑∑∑∑∑>
qlk1 k2 (Ψ(αk1k2 ) − Ψ(αk1 k2 ))=lk1k2k1ている.

k2+ log Γ(αK ) − K log(Γ(α)∑∑∑∑+ (α − 1)(Ψ(αk1 k2 ) − Ψ())
2+(2∑∑∑
lk1

k1

′
k1k2

lr = lr0 × dropf loor(epoch/epochs drop)′k2∑
qlk1 k2 (δl1v (Ψ(βk1 l1 ) − Ψ(βk1 v ))k2+ δl2v (Ψ(βk2 l2 ) − Ψ(∑

リンクの種類ごとに β1 , . . . , βN の推定を行った後, この更新をβk2 v )))繰り返す事で下限 L(U ) の最大化を行う. そして β1 = . . . = βN+ K log(βV ) − KV log Γ(β)∑∑∑+ (β − 1)(Ψ(βkv ) − Ψ(βkv′ ))+nlkのときが, 主問題と双対問題の値が一致したときなので, 最適解∗に到達した事が保証される. これにより得られた β1∗ , . . . , βNはv′v

原理的に同一であるが，収束条件によっては互いにほぼ同一であるがやや異なる (これは双対ギャップと呼ばれる).

qdnk log qdnkk∑∑∑∑+ logΓ(αk1 k2 ) −log Γ(αk1 k2 )k1+k2k14 実∑∑∑∑(αk1 k2 − 1)(Ψ(αk1 k2 ) − Ψ(αk1′ k2′ )
k1k2v

験k2

∑∑
∑
+(log Γ(βkv ) −log Γ(βkv )kepoch が双対分解の繰り返し数,lr0 は学習率の初期値の定数,drop は減衰率の定数,epochs drop は減衰が起こる周期を示す定数である。

vv∑∑∑(13)′
k1k′ 2

4. 1 関連クエリ予測用のデータセット
関連クエリ予測の実験で用いるデータセットは「Yahoo! 検v∑∑+(βkv − 1)(Ψ(βkv ) − Ψ(βkv′ )))v

2 つの多モードネットワークを用いて, 性能を比較する.

(6)v

索」の 3 種類の検索関連クエリデータ 1 である．それぞれ共クリッククエリ，共トピッククエリ，共クリッククエリと呼ばれ，共トピッククエリと共セッションクエリは 2009 年 7 月から

双対分解を用いると, 最適化問題は2013 年 6 月，共クリッククエリは 2009 年 7 月から 2010 年 12argmax (f1 (β1 ) + f2 (β2 ) + f3 (β3 ) . . . + fN (βN ))(7)

β1 ,β2 ,...,βN

月の Yahoo!JAPAN 検索から抽出されている．それぞれのデー
タにはクエリ，関連クエリ，関連性の強さの値が含まれる．発

ラグランジュ緩和を用いると,生頻度の少ないクエリはプライバシーの問題のためデータからL(u, β1 , β2 , . . . , βN )削除されており，そのカットオフ閾値は開示されていない．各= f1 (β1 ) + f2 (β2 ) + . . . + fN (βN )クエリ対について最大 10,000 の関連するクエリ記録が各種類に+N−1∑

N∑

ついて含まれている．各クエリの正確な発生頻度は明らかでな

uij (βi − βj )(8)i=1 j=i+1

ここで uij = −uji である. 次に, L(u, β1 , β2 , . . . , βN ) を最大化する β1 , β2 , . . . , βN を考える.

いので，各データセットで定義される共起確率 PCC , PCT , PCS
を 1000 倍し，小数第一位を四捨五入した頻度だけ共起したと仮定した．また，共起頻度が 0 回となるものについては除外した．クエリ，関連クエリには複数語や文からなるものが多く含L(u)まれていることから，データのスパース性を緩和する為に関連= max(f1 (β1 ) + (u12 + u13 + . . . + u1N )β1 )クエリを形態素解析し，意味のある単語ごとに分割し，それぞβ1

れがクエリと関連するように分解を行った．前処理後のデータ+ max(f2 (β2 ) + (u21 + u23 + . . . + u2N )β2 )セットの統計を表 1 に示す．3 種類の検索クエリデータセット

β2の 3 つから 20%ずつランダムに取り出し, それらを合わせたも..
.のをテストセットとし, 残りを訓練セットとした. 3 種類の検+ max(fN (βN ) + (uN 1 + uN 2 + . . . + uN N −1 )βN )βN

双 対 定 理 よ り L∗ = minu L(u) が 成 り 立 つ.

(9)

よって L(u)の劣微分の 1 つである du12 , . . . , du1N , . . . , duN N −1 , および∗β1∗ , β2∗ , . . . , βN, ラグランジュ乗数 u12 , . . . , u1N , . . . , u1N −1 は以下のようになる.

索クエリを区別せず 1 つにまとめたスパースブロックモデルと3 モードの多モードブロックモデルを変分ベイズを用いて推定した.

4. 2 変分ベイズ推定による関連クエリ予測
各モデルを用いてクエリが与えられたときに関連クエリを候duij = βi∗ − βj∗(10)

補の中から予測する．各トピック数は 50 とし, 繰り返し数 200βi∗ = argmax fi (βi ) + (ui1 + . . . + uiN )βi(11)で変分ベイズ推定を行う. 多モードブロックモデルは推定の初(12)1：http://research.nii.ac.jp/ntcir/news-20150717-ja.html

βiuij ← uij − µ(βi∗ − βj∗ )表 4 Mean average precision(MAP) results.

表 1 Statistics of the Yahoo dataset used.

Query Type

Number of rerated queries

Co-Click Query

5671768

Sparse block model 0.409

Co-Topic Query3309638

Multi block model

Co-Session Query573485

MAPある t 検定を行った結果, 有意差が認められた (p < 0.01). ベー

表 2 Mean average precision(MAP) results.

スラインとなるスパースブロックモデルと比べると提案手法でMAPある多モード・ブロックモデルの方が優れた結果となった．

Sparse block model 0.0127
Multi block model0.565

0.02905 結論

表 3 Statistics of the Facebook Egonets dataset used.
辺の数

頂点数

モード数

本論文では, スパースブロックモデルを拡張し, 多モードネッ

ハイパーパラメータ設定用ネットワーク 119482

746

41

トワークに利用可能な多モードブロックモデルに着目し, 変分1032

43

ベイズ推定の過程で双対分解を行う推定手法を提案した, また,評価用ネットワーク

113991

その性能をスパースブロックモデルと比較した. 関連クエリ予期段階であるため,20 回目以降に開始する. 今回の実験データ

測と離散関係属性付き社会ネットワークの実験を通して多モーに対し双対分解の繰り返し数は 20 回以下で収束するため 20 回

ド・ブロックモデルの有効性を示した. また, 今回の実験では,とした.

リンクがつながっているかの予測のみであったが, どのモード候補はテストセットの全ての関連クエリとし，クエリ毎に尤度かの推定を行って評価し, その有用性を確認する必要がある.のランキングを作成し，その Mean Average Precision(MAP)を計算する．MAP は表 2 で示される．ベースラインとなるス
パースブロックモデルと比べると提案手法である多モード・ブロックモデルの方が優れた結果となった．

謝

辞本研究の一部は科学研究費補助金基盤研究 (B) (15H02703)の援助による．

4. 3 リンク予測用のデータセット
この実験には,Facebook のエゴネットワークデータセット 2を用いる. エゴネットワークとは, ある与えられたノードとそれに隣接しているノードおよびそれらの間のリンクのみによって構成される元のネットワークの誘導部分グラフである. アカウ
ントを頂点, アカウント間の関係を辺とし, アカウントを持つ属性のうち, アカウント間で共通の属性を関係属性として辺に付与する. 関係属性は通っている学校や専攻, 性別, そして住んでいる場所などが挙げられる. このデータセットは全頂点数が4039, 全リンク数が 88234 のデータセットであるが, エゴネットワークとして,10 個のデータセットに分割されている. そのうちのひとつをトピック数やディレクレ事前分布のパラメタの定数などを決める用に使い, 別の 1 つを評価用に用いた. リンク数が120 以下のものだけをまとめて,1 つのモードとして用いたデータ・セットに含まれる超点数, 辺の数, 関係属性の種類の詳細を
表 3 に示す. また, このデータセットのグラフの構造は無向グラフである.

4. 4 変分ベイズ推定によるリンク予測
各パラメータを 5 分割交差検定によりトピック数 20,α,β を0.1 とした. モード数が多い場合, 双対分解の時に疎な部分による性能劣化が大きいため, 最初の 20 回はスパースブロックモデ
ルで β を推定した. テストケースの各頂点ごとにリンク予測を行い, その結果を MAP で評価した. 結果を表 4 に示す. また,各頂点ごとに MAP を求め, その MAP の系列に対して, 対応の2：http://snap.stanford.edu/data/egonets-Facebook.html

文献[1] Kamal Nigam, Andrew Kachites Mccallum, SebastianThrun, Tom Mitchell ”Text Classification from Labeled andUnlabeled Documents using EM”, Machine Learning - Special issue on information retrieval,Vol.39,pp.103-134(2000)[2] Papadimitriou Christos, Raghavan Prabhakar, TamakiHisao, Vempala Santosh, ”Latent Semantic Indexing: Aprobabilistic analysis”, PODS ’98 Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium onPrinciples of database systems,pp.159-168(1998)[3] Blei,D.M.,Ng,A.Y., ”Latent Dirichlet allocation”, Journalof Machine Learning Research,Vol.3,pp.993-1022(2003)[4] Xiaohui Yan, Jiafeng Guo, Yanyan Lan, Xueqi Cheng, ”ABiterm Topic Model for Short Texts”, WWW ’13 Proceedings of the 22nd international conference on World WideWeb,pp.1445-1456(2013)[5] Juuso Parkkinen, Adam Gyenge,Janne Sinkkonen, SamuelKaski, ”A block model suitable for sparse graphs”, Proceedings of the 7th International Workshop on Mining andLearning with Graphs,(2009)[6] Ramnath Balasubramanyan, William W. Cohen, ”BlockLDA: Jointly modeling entity-annotated text and entityentity links”, Chapman and Hall/CRC 2014,Vol.3,pp.255273(2014)[7] Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin,”Network Flows: Theory, Algorithms, and Applications”,
citeulike.org,(1993)[8] 梅原 頌平, 江口 浩二潜在変数モデリングによる利用者の情報行動に関する予測 DEIM2017 (2017)