DEIM Forum 2013 B4-3

異種混合メンバーシップ・ブロックモデルと情報推薦への応用
石黒 七海†

江口 浩二†

横峯樹†† 神戸大学工学部 〒 657–8501 兵庫県神戸市灘区六甲台町 1–1
E-mail: †ishiguro@cs25.scitec.kobe-u.ac.jp,eguchi@port.kobe-u.ac.jp
あらましネットワークで表現されたデータの潜在構造をモデル化するアプローチとして，混合メンバーシップ・ブ

ロックモデルが知られている．本研究ではそれを拡張し，複数種類のノードまたはリンクで構成されたネットワークの潜在構造をモデル化する．また，それを用いて，ユーザのアイテム利用履歴に基づいて構成された二部グラフと社会ネットワークなどを合成することによって得られた異種ネットワークに対して適用し，上位 N 件推薦問題に応用し，評価を行う．
キーワード

混合メンバーシップ・ブロックモデル，異種ネットワーク，情報推薦

Nanami ISHIGURO† , Koji EGUCHI† , and Tatsuki YOKOMINE†† Faculty of Engineering, Kobe University
1–1 Rokkodai, Nada, Kobe, Hyogo 657–8501 Japan
E-mail: †ishiguro@cs25.scitec.kobe-u.ac.jp,eguchi@port.kobe-u.ac.jp

1. は じ め にて無限次元に拡張したモデルである．二つ目に，Airoldi らが提案した混合メンバシップ・ブロックモデル (Mixed Membership

近年，インターネットの普及に伴い，情報の量とそれを扱う

Blockmodels: MMSB) [1] がある．このモデルでは，ノードにユーザの数が爆発的に増加している．これらの多大な量の情報対する潜在的なグループを確率分布として表現し，グループ間の中から，自分の必要としている情報を選択することは容易でのリンクの生成確率を考慮している．前者は多項分布で表現さはない．また同時に，ネットワーク構造で表される情報も増加

れ，ディリクレ事前分布を仮定する．また，後者はベルヌーイ

している．その代表的な例が，Facebook や Twitter である．イ

分布で表現され，これにベータ事前分布を導入することができ

ンターネットユーザが増え続けている今，これらのネットワー

る．これにより，各ノードが複数のグループに属することを許ク構造で表される情報を有効的に使いたいという需要が高まっ容する柔軟なモデリングが可能になる．そこで本稿では MMSBている．これらの問題を解決するためには，ユーザの嗜好を分のアプローチをとる．

析し，ユーザの嗜好にあった情報を推薦するということが必要
である．

しかし，MMSB ではネットワーク上におけるノードの種類
や，リンクに付与されたラベルを直接的に考慮することができ

本稿では，ベイズ的アプローチによるネットワークモデリン

ない．そこで本稿では，複数の種類のノード，リンクが混在するグに着目する．ベイズ的アプローチによるモデリングには大き異種ネットワークを扱うよう MMSB を拡張した異種混合メン

く二つの流れがあると考えられる．一つ目は，ブロックモデルとバシップ・ブロックモデル (Heterogeneous Mixed Membership

呼ばれるモデルをベイズ的統計学的に拡張した確率論的ブロッ

Stochastic BlockModel: HMMB) を提案する．リンクの種類

クモデル (Stochastic Block Models: SB) [4] である．これはに着目するモデルと，ノードの種類に着目するモデル，リンク

ノードが単一のクラスタに割り当たるようにクラスタリングし，に付与された複数のラベルを考慮するモデルを検討し，従来手同じクラスタのノードはすべて相手クラスタにリンクを張る確法に対する優位性を示す．

率が同じであるという仮定のもとにネットワークのモデリングを行ったものである．また，上記で述べたモデルではクラスタ

2. 混合メンバシップ・ブロックモデルの数を所与のパラメータとしている．この問題を回避したモデ

まずは，本稿で用いる定義についてまとめる．グラフをルとして無限関係モデル (Infinite Relational Model: IRM) [2]G = (N, Y ) で表し，N をノード集合，Y を隣接行列とする．

がある．IRM は SB において固定的なクラスタの数だけ次元が観測されるデータについて，ノード p, q に対応する隣接行列のあったベクトルを Chinese Restaurant Process(CRP) によっ

要素を Y (p, q) ∈ {0, 1} と表す．MMSB において，ある 2 ノー

ド間のリンクはそれぞれのノードの潜在的なグループの多項分
布と，それぞれのグループ対における辺の起こりやすさを示す
ベルヌーイ分布から生成される．すなわち，各ノードはグループ上の多項分布 Mult(πp ) で特徴づけられるとし，グループ gに関する多項分布パラメータを πp,g とすると，πp,g はノード

p がグループ g に属する確率である．このように，それぞれのノードはリンクごとに異なるグループを持つことができる．ま図 1 MMSB のグラフィカルモデル

た，グループ間の関係は K × K 行列で表されたパラメータで決まるベルヌーイ分布 Bern(B) によって定義される．ここでB(g, h) はグループ g に属するノードから，グループ h に属するノードへの辺が存在する確率であり，K はグループ数である．指示ベクトル zp→q はノード p からノード q へリンクが存在するとき，ノード p に割り当てられる潜在グループを表して

3. 提 案 手 法
本章では，提案手法である HMMB-L と HMMB-N，LH-

MMB について述べる．HMMB-L ではリンクの種類に着目し，HMMB-N はノードの種類に着目したモデル，LHMMB はノー

いて (該当するグループの成分が 1 であり，他が 0 であるベクドの種類とリンクに付与された複数のラベルを考慮するモデルトル)，それに対し zp←q はノード q に割り当てられる潜在グである．

ループを表している．これら二つのベクトルの集合は，それぞれ {zp→q | p, q ∈ N } = Z→ と {zp←q | p, q ∈ N } = Z← である．以上の定義から，MMSB モデルによるリンクの生成過程を以下に示す．

MMSB と同様に，用いる定義についてまとめる．グラフをついて隣接行列の要素を Y (p, q) = δ とそのリンクの種類を

ハイパーパラメータ α で特定されたディリクレ分布から

多項分布パラメータ πp を選択

Q(p, q) = t と表す．δ ∈ {0, 1} であり，リンクがあるかないかを示すパラメータとする．また，t ∈ {1, 2, . . . , T } であり，リ（ 2 ） すべてのグループの対 (g, h) に対して•MMSB を拡張したモデルである HMMB-L について述べる．
G = (N, Y, Q) と表し，観測されるデータは，ノード p, q に（ 1 ） すべてのノード p に対して•

3. 1 HMMB-L

ンクの種類を表すパラメータである．ある 2 ノード間のリンク

ハイパーパラメータ ψ = (ψ0 ，
ψ1 ) で特定されたベータ分布からベルヌーイ分布パラメータ B(g, h) を選択

は，MMSB と同様にして二種類の多項分布から生成される．すなわち，ノード p がグループ g に属する確率 πp,g と，グルー（ 3 ） すべてのノード対 (p, q) に対して

プ g に属するノードから，グループ h に属するノードへの辺•多項分布 M ult(πp ) から指示ベクトル zp→q を選択•

多項分布 M ult(πq ) から指示ベクトル zp←q を選択•

ベルヌーイ分布 Bern(z⊤p→q Bzp←q ) から Y (p, q) を生成義されたグループ対毎の多項分布によって表す．ここで K は

このとき，データ Y と潜在変数 π1:N , Z→ , Z← および B の同グループ数であり，T はネットワーク上に T 種類のリンクの

時分布 (完全同時分布) は以下のようになる．

= P (B|ψ)類のリンクの種類において，グループ g のノードからグループ

P (Y (p, q)|zp→q , zp←q , B)P (zp→q |πp )

p,q,p=q|

P (zp←q |πq )∏P (πp |α)グループ間の関係を，K × K × T の三次のテンソル M で定種類が存在することを表す．よって，M (g, h, t) は t 番目の種P (Y, π1:N , Z→ , Z← , B|α, ψ)∏が存在する確率 B(g, h) である．さらに，ある種類のリンクの(1)

h のノードへの辺が存在する確率である．また，指示ベクトルzp→q , zp←q については，ノード p, q に割り当てられる潜在グループを表している (該当するグループの成分が 1 であり，他が 0 であるベクトル)．これら二つのベクトルの集合は，それp

ぞれ {zp→q | p, q ∈ N } = Z→ と {zp←q | p, q ∈ N } = Z← で

また，完全条件付確率分布は以下のようになる．

ある．以上の定義から，HMMB-L モデルによるリンクの生成

P (zp→q = g, zp←q = h | Y, Z→ , Z← ; α, ψ)過程を以下に示す．

C(p, g) + αgC(q, h) + αh∝Σg C(p, g) + Σg αg Σh C(q, h) + Σh αh（ 1 ） すべてのノード p に対して•

C(g, h, δ) + ψδC(g, h, 0) + C(g, h, 1) + ψ0 + ψ1
= πp,g πq,h B(g, h)

ハイパーパラメータ α で特定されたディリクレ分布から

多項分布パラメータ πp を選択(2)

ここで，C(p, g) はあるノード p がグループ g に割り当てられた頻度である．C(g, h, 0), C(g, h, 1) は，観測されたネットワー
ク全体におけるノード対において，一方のグループが g であり，他方のグループが h であるときに，リンクが存在する頻度と存在しない頻度をそれぞれ示している．δ ∈ {1, 0} とし，リンクの有無を表す．MMSB のグラフィカルモデルを図 1 で示す．

（ 2 ） すべてのグループの対 (g, h) に対して•

ハイパーパラメータ ψ = (ψ0 ，
ψ1 ) で特定されたベータ分布からベルヌーイ分布パラメータ B(g, h) を選択•

リンクの種類 t ∈ {1, . . . , T } に対して

– ハイパーパラメータ ϕ で特定されたディリクレ分布から
多項分布パラメータ M (g, h, t) を選択（ 3 ） すべてのノード対 (p, q) に対して

•

多項分布 M ult(πp ) から指示ベクトル zp→q を選択

x であるとき，任意の種類のノード p がグループ g に属する確•多項分布 M ult(πq ) から指示ベクトル zp←q を選択率である．またグループ間の関係は K × K 行列で表されたパ•

ベルヌーイ分布 Bern(z⊤p→q Bzp←q ) から Y (p, q) を生成

ラメータで決まるベルヌーイ分布 Bern(B x1 ,x2 ) によって定義– Y (p, q) = 1 のとき，多項分布 M ult(z⊤p→q M zp←q ) からされる．ここで B x1 ,x2 (g, h) はグループ g に属する種類 x1 のQ(p, q) を生成

ノードから，グループ h に属する種類 x2 のノードへの辺が存

このとき，データ Y, Q と潜在変数 π1:N , Z→ , Z← および M, B

在する確率であり，K はグループ数である．また，指示ベクトの同時分布 (完全同時分布) は以下のようになる．

ル zp→q , zp←q については，ノード p, q に割り当てられる潜在グループを表している (該当するグループの成分が 1 であり，P (Y, Q, Z→ , Z← , πp , πq , B, M |α, ψ, ϕ)=∏

P (zp→q |πp )P (πp |α)

p

∏∏
g

∏

他が 0 であるベクトル)．これら二つのベクトルの集合は，そP (zp←q |πq )P (πq |α)

れぞれ {zp→q | p, q ∈ N } = Z→ と {zp←q | p, q ∈ N } = Z←qである．以上の定義から，HMMB-N モデルによるリンクの生

P (Y (p, q)|zp→q , zp←q , B)P (B|ψ)

成過程を以下に示す．

h

P (Q(p, q)|zp→q , zp←q , M )P (M |ϕ)(3)

また，完全条件付確率分布は以下のようになる．

P (zp→q = g, zp←q = h | Y, Q, Z→ , Z← ; α, ψ, ϕ)∝（ 1 ） 隣接するノードの種類が U であるすべてのノード p に対して•ハイパーパラメータ α で特定されたディリクレ分布から

多項分布パラメータ πpU を選択（ 2 ） 隣接するノードの種類が I であるすべてのノード q にC(q, h) + αhC(p, g) + αg
Σg C(p, g) + Σg αg Σh C(q, h) + Σh αh

対して

C(g, h, δ) + ψδC(g, h, t) + ϕt
(4)C(g, h, 1) + C(g, h, 0) + Σδ ψδ Σt C(g, h, t) + Σt ϕt

多項分布パラメータ πqI を選択

ここで，C(p, g) はあるノード p がグループ g に割り当てられた頻度である．C(g, h, δ) は，観測されたネットワーク全体におけるノード対において，一方のグループが g であり，他方のグループが h である回数であり，δ はリンクがあるかないかを表す．同様に C(g, h, t) はあるノードがグループ g であり，相手のノードがグループ h である回数で，t はリンクの種類を表す．HMMB-L のグラフィカルモデルを図 2 で示す．

•

ハイパーパラメータ α で特定されたディリクレ分布から（ 3 ） ノードの種類 (U, I) のすべてのグループの対 (g, h) に対して•

ハイパーパラメータ ψ U I = (ψ0U I ，
ψ1U I ) で特定されたベータ分布からベルヌーイ分布パラメータ B U I (g, h) を選択（ 4 ） ノードの種類 (I, U ) のすべてのグループの対 (g, h) に対して•

ハイパーパラメータ ψ IU = (ψ0IU ，
ψ1IU ) で特定されたベータ分布からベルヌーイ分布パラメータ B IU (g, h) を選択（ 5 ） ノードの種類 (U, U ) のすべてのグループの対 (g, h) に対して•

ハイパーパラメータ ψ U U = (ψ0U U ，
ψ1U U ) で特定されたベータ分布からベルヌーイ分布パラメータ B U U (g, h) を選択（ 6 ） ノードの種類 (I, I) のすべてのグループの対 (g, h) に対して•
図 2 HMMB-L のグラフィカルモデル

ハイパーパラメータ ψ II = (ψ0II ，
ψ1II ) で特定されたベータ分布からベルヌーイ分布パラメータ B II (g, h) を選択（ 7 ） ノードの種類 (U, I) のすべてのノード対 (u, i) に対

3. 2 HMMB-N

して続いて，HMMB-N について述べる．用いる定義についてま•

多項分布 M ult(πuI ) から指示ベクトル zu→i を選択

とめる．グラフを G = (N, Y, L) と表し，観測されるデータ•

多項分布 M ult(πiU ) から指示ベクトル zu←i を選択

は，ノード p, q について隣接行列の要素を Y (p, q) = δ とその•UI
ベルヌーイ分布 Bern(z⊤u→i Bgh zu←i ) から Y (u, i) ∈ノードの種類を L(p) = x と表す．δ ∈ {0, 1} であり，リンク{0, 1} を生成があるかないかを示す．ここでは簡単のため，x ∈ {U, I} であ（ 8 ） ノードの種類 (I, U ) のすべてのノード対 (i, u) に対り，それぞれ，ユーザ・ノード，アイテム・ノードを示すとす

してる．ある 2 ノード間のリンクはそれぞれのノードの潜在的な•多項分布 M ult(πiU ) から指示ベクトル zi→u を選択

グループの多項分布と，それぞれのグループ対における辺の•多項分布 M ult(πuI ) から指示ベクトル zi←u を選択

起こりやすさを表すベルヌーイ分布から生成される．すなわ•

IU
ベルヌーイ分布 Bern(z⊤i→u Bgh zi←u ) から Y (i, u) ∈ち，各ノードはグループ上の多項分布 Mult(πpx ) で特徴づけら{0, 1} を生成れるとし，x は隣接ノードの種類である．グループ g に関する（ 9 ） ノードの種類 (U, U ) のすべてのノード対 (u, u′ ) に対x
多項分布パラメータを πp,gとすると，これはノードの種類がして•

多項分布 M ult(πuU ) から指示ベクトル zu→u′ を選択表す．t の各成分は ts ∈ {1, . . . , T }(s = 1, . . . , S(p, q)) であり，•多項分布 M ult(πuU′ ) から指示ベクトル zu←u′ を選択
UU′
ベルヌーイ分布 Bern(z⊤u→u′ Bgh zu←u′ ) から Y (u, u ) ∈ラベルの種類を示す．ある 2 ノード間のリンクは HMMB-N•{0, 1} を生成と同様にして，2 種類の多項分布から生成される．すなわち，ノードの種類が x であるとき，任意の種類のノード p がグルー′

（ 10 ） ノードの種類 (I, I) のすべてのノード対 (i, i ) に対x
プ g に属する確率 πp,gと，グループ g に属する種類 x1 のノーしてドから，グループ h に属する種類 x2 のノードへの辺が存在す•

多項分布 M ult(πiI ) から指示ベクトル zi→i′ を選択•

多項分布 M ult(πiI′ ) から指示ベクトル zi←i′ を選択

けられたリンクのグループ間の関係を K × K × T の三次のテ•′II
ベルヌーイ分布 Bern(z⊤i→i′ Bgh zi←i′ ) から Y (i, i ) ∈ンソル M x1 ,x2 で表されたパラメータによって決まる多項分布

る確率 B x1 ,x2 (g, h) である．さらに，ある種類のラベルをつ{0, 1} を生成によって定義する．ここで K はグループ数であり，T はネッ

このとき，データ Y と潜在変数 π1:N , Z→ , Z← および B の同

トワーク上に T 種類のラベルが存在することを表す．よって，

時分布 (完全同時分布) は以下のようになる．

M x1 ,x2 (g, h, t) は t 番目の種類のラベルが付けられたノード対において，グループ g に属する種類 x1 のノードからグループ h

P (Y, L, Z→ , Z← , πp , πq , B|α, ψ)=∏P (zp→q |πpx1 )P (πpx1 |α)

p,x1

∏

に属する x2 のノードへの辺が存在する確率である．また，指示P (zp←q |πqx2 )P (πqx2 |α)

q,x2

∏

ベクトル zp→q , zp←q については，ノード p, q に割り当てられる潜在グループを表している (該当するグループの成分が 1 でP (Y (p, q)|zp→q , zp←q , B x1 ,x2 )P (B x1 ,x2 |ψ x1 ,x2 )

g,h,x1 ,x2あり，他が 0 であるベクトル)．これら二つのベクトルの集合は，それぞれ {zp→q | p, q ∈ N } = Z→ と {zp←q | p, q ∈ N } = Z←

また，種類 U のノードと種類 I のノード間のリンクに関するである．以上の定義から，LHMMB モデルによるリンクの生

完全条件付確率分布は以下のようになる (他の種類のリンクに成過程を以下に示す．

関しても同様である)．

（ 1 ） 隣接するノードの種類が U であるすべてのノード p に対して

P (zp→q = g, zp←q = h | Y, L, Z→ , Z← ; α, ψ)∝•C I (p, g) + αg
C U (q, h) + αhIΣg C (p, g) + Σg αg Σh C U (q, h) + Σh αh

多項分布パラメータ πpU を選択（ 2 ） 隣接するノードの種類が I であるすべてのノード q に

C U I (g, h, δ) + ψδU I
UI
C (g, h, 1) + C U I (g, h, 0) + Σδ ψδU I(5)

ここで，C I (p, g) はノード p の隣接のノードの種類が I の時にグループ g に割り当てられた頻度である．C

ハイパーパラメータ α で特定されたディリクレ分布から

UI(g, h, δ) は，観測されたネットワーク全体において，ノードの種類が U である方のグループが g であり，他方の種類が I のノードのグループが h である回数であり，δ はリンクがあるかないかを表す．

HMMB-N のグラフィカルモデルを図 3 で示す．

対して•ハイパーパラメータ α で特定されたディリクレ分布から

多項分布パラメータ πqI を選択（ 3 ） ノードの種類 (U, I) のすべてのグループの対 (g, h) に対して•

ハイパーパラメータ ψ U I = (ψ0U I ，
ψ1U I ) で特定されたベータ分布からベルヌーイ分布パラメータ B U I (g, h) を選択•

ラベルの種類 t ∈ {1, . . . , T } に対して

– ハイパーパラメータ ϕ で特定されたディリクレ分布から
多項分布パラメータ M (g, h, t) を選択（ 4 ） ノードの種類 (I, U ) のすべてのグループの対 (g, h) に対して•

ハイパーパラメータ ψ IU = (ψ0IU ，
ψ1IU ) で特定されたベータ分布からベルヌーイ分布パラメータ B IU (g, h) を選択
図 3 HMMB-N のグラフィカルモデル•

ラベルの種類 t ∈ {1, . . . , T } に対して

– ハイパーパラメータ ϕ で特定されたディリクレ分布から
3. 3 LHMMB
次に，LHMMB について述べる．用いる定義についてまとめ

多項分布パラメータ M (g, h, t) を選択（ 5 ） ノードの種類 (U, U ) のすべてのグループの対 (g, h) にる．グラフを G = (N, Y, L, R) と表し，観測されるデータは，対してノード p, q について隣接行列の要素を Y (p, q) = δ とそのノー•ドの種類を L(p) = x，任意のリンクに付けられる１つまたは複ハイパーパラメータ ψ U U = (ψ0U U ，
ψ1U U ) で特定されたベータ分布からベルヌーイ分布パラメータ B U U (g, h) を選択

数のラベルを R(p, q) = t とする．δ ∈ {0, 1} であり，リンクが•あるかないかを示す．ここでは簡単のため，x ∈ {U, I} であり，

– ハイパーパラメータ ϕ で特定されたディリクレ分布から

ラベルの種類 t ∈ {1, . . . , T } に対して

それぞれ，ユーザ・ノード，アイテム・ノードを示すとする．ま

多項分布パラメータ M (g, h, t) を選択

た，ノード p, q 間のリンクにつけられたラベルの数を S(p, q) で

（ 6 ） ノードの種類 (I, I) のすべてのグループの対 (g, h) にP (zp→q = g, zp←q = h | Y, L, R, Z→ , Z← ; α, ψ, ϕ)

対して•ハイパーパラメータ ψII= (ψ0II ，
ψ1II ) で特定されたベー
II

タ分布からベルヌーイ分布パラメータ B (g, h) を選択•

ラベルの種類 t ∈ {1, . . . , T } に対して

– ハイパーパラメータ ϕ で特定されたディリクレ分布から
多項分布パラメータ M (g, h, t) を選択（ 7 ） ノードの種類 (U, I) のすべてのノード対 (u, i) に対して•多項分布 M ult(πuI ) から指示ベクトル zu→i を選択•

多項分布 M ult(πiU ) から指示ベクトル zu←i を選択•

UI
ベルヌーイ分布 Bern(z⊤u→i Bgh zu←i ) から Y (u, i) ∈{0, 1} を生成– Y (u, i) = 1 のとき，S(u, i) のそれぞれについて多項分⊤
布 M ult(⃗zu→iM⃗zu←i ) から R(u, i) を生成（ 8 ） ノードの種類 (I, U ) のすべてのノード対 (i, u) に対して•多項分布 M ult(πiU ) から指示ベクトル zi→u を選択•

多項分布 M ult(πuI ) から指示ベクトル zi←u を選択•

IU
ベルヌーイ分布 Bern(z⊤i→u Bgh zi←u ) から Y (i, u) ∈{0, 1} を生成∝

C I (p, g) + αg
C U (q, h) + αhIΣg C (p, g) + Σg αg Σh C U (q, h) + Σh αh
C U I (g, h, δ) + ψδU I
UI
C (g, h, 1) + C U I (g, h, 0) + Σδ ψδU I∏

s∈S(p,q)I
C U I (g, h, ts ) + ϕU
ts
IU
IΣt C (g, h, t) + Σt ϕU
t(6)

ここで，C I (p, g) はノード p の隣接のノードの種類が I の時にグループ g に割り当てられた頻度である．C U I (g, h, δ) は，観測されたネットワーク全体において，ノードの種類が U である方のグループが g であり，他方の種類が I のノードのグループが h である回数であり，δ はリンクがあるかないかを表す．同様に C U I (g, h, t) はある種類 U のノードがグループ g であり，相手のノードが種類 I のグループ g である回数で，t はラベルの種類を表す．また，ts (s = 1, . . . , S(p, q)) は p, q 間のリンクに付けられたラベルのそれぞれの種類を表している．LHMMBのグラフィカルモデルを図 4 で示す．ただし，ユーザノードとアイテムノードの間のリンクにのみラベルが与えられると仮定している．

– Y (i, u) = 1 のとき，S(i, u) のそれぞれについて多項分⊤
布 M ult(⃗zi→uM⃗zi←u ) から R(i, u) を生成（ 9 ） ノードの種類 (U, U ) のすべてのノード対 (u, u′ ) に対して•多項分布 M ult(πuU ) から指示ベクトル zu→u′ を選択•

多項分布 M ult(πuU′ ) から指示ベクトル zu←u′ を選択•

UU′
ベルヌーイ分布 Bern(z⊤u→u′ Bgh zu←u′ ) から Y (u, u ) ∈{0, 1} を生成– Y (u, u′ ) = 1 のとき，S(u, u′ ) のそれぞれについて多項
図 4 LHMMB のグラフィカルモデル⊤
zu←u′ ) から R(u, u′ ) を生成
分布 M ult(⃗
zu→u
′ M⃗
′

（ 10 ） ノードの種類 (I, I) のすべてのノード対 (i, i ) に対
して

4. 実

•

多項分布 M ult(πiI ) から指示ベクトル zi→i′ を選択•

多項分布 M ult(πiI′ ) から指示ベクトル zi←i′ を選択•II′
ベルヌーイ分布 Bern(z⊤i→i′ Bgh zi←i′ ) から Y (i, i ) ∈験

提案モデルである HMMB の優位性を示すため，既存手法との比較実験を行った．

4. 1 データセット{0, 1} を生成– Y (i, i′ ) = 1 のとき，S(i, i′ ) のそれぞれについて多項分

本章では，２つのデータセットを用いて比較実験を行った．
一つ目は，映画のレビューサイトである Movie Lenz のデー⊤
布 M ult(⃗zi→izi←i′ ) から R(i, i′ ) を生成′ M⃗

このとき，データ Y, R と潜在変数 π1:N , Z→ , Z← および B のタ（注 1）である．MovieLenz のユーザと，ユーザが評価した映画

同時分布 (完全同時分布) は以下のようになる．

(アイテム) をノードの種類とする．ユーザ数 943, アイテム数
1682 で，リンク数は 121694 である．ユーザ・アイテム間にP (Y, L, R, Z→ , Z← , πp , πq , B|α, ψ, ϕ)=∏

P (zp→q |πpx1 )P (πpx1 |α)は，ユーザとそのユーザの評価値の平均値以上に評価している

P (zp←q |πqx2 )P (πqx2 |α)P (Y (p, q)|zp→q , zp←q , B

アイテムにリンクが存在し，アイテム間には，同じ監督である
か，同じ俳優が出演している場合にリンクが存在すると仮定し，

q,x2

p,x1

∏

∏

x1 ,x2)P (Bx1 ,x2|ψ)

ユーザ間にはリンクが存在しないと仮定した．このデータには

g,h,x1 ,x2

ラベルが存在しないので，HMMB-L，HMMB-N について比P (R(p, q)|zp→q , zp←q , M x1 ,x2 )P (M x1 ,x2 |ϕ)較実験を行った．HMMB-L では，ノード対毎にノードの種類

また，種類 U のノードと種類 I のノード間のリンクに関するの対すなわち {U U, U I, IU, II} をリンクの種類とみなした．

完全条件付確率分布は以下のようになる (他の種類のリンクに関しても同様である)．

（注 1）：http://www.grouplens.org/node/73

二つ目は，ユーザーの音楽的指向を反映する SNS である（注 2）

Last.fm のデータである．Last.fm のユーザと，ユーザが視聴したアーティスト (アイテム) をノードの種類とする．ユー
ザ数 1101，アイテム数 524，リンク数 76088 である．ユーザ・
アイテム間にはユーザとそのユーザが視聴したアイテムにリ

LHMMB の場合，種類 U のノード p と種類 I のノード q 間のリンクに関する尤度は，以下の式で求められる (他の種類のリンクに関しても同様)．

P (Y | Z→ , Z← , πp , πq , B, M, R; α, ψ, ϕ)

ンクが存在し，ユーザ間には Last.fm 上で繋がりがあるもの=にユーザ間リンク存在すると仮定する。ユーザ間には音楽的∏上でユーザはアイテムに複数のラベルを付けることが可能である．このラベルは存在するユーザ・アイテム間リンク上にた．HMMB-L では，ノード対毎にノードの種類の対すなわち{U U, U I, IU, II} をリンクの種類とみなした．

C I (p, g) + αg
C U (q, h) + αhIΣg C (p, g) + Σg αg Σh C U (q, h) + Σh αh

C U I (g, h, δ) + ψδU I
UI
C (g, h, 1) + C U I (g, h, 0) + Σδ ψδU I

イテム間にはリンクが存在しないと仮定した．また，Last.fm

ある．HMMB-L,HMMB-N,LHMMB について比較実験を行っ(1 − ρU I )p,q g,h

嗜好が似た者同士にリンクが生まれやすいと考えられる．アあると仮定し，ラベルの種類は 250，ラベル数は 32148 個で(∏∑s∈R(p,q)I
C U I (g, h, ts ) + ϕU
ts
IU
IΣt C (g, h, t) + Σt ϕU
t

)

(13)

ρU I は式 (11)，(12) に従う．
4. 3 パラメータ
HMMB-L については，ハイパーパラメータは α は対称ディ
リクレを仮定し，その成分を α = 0.1 とし，ψ については，非

4. 2 評 価 方 法
ユーザごとにユーザ・アイテム間のリンクを尤度の高いもの

対称ベータを仮定し，Minka の不動点反復法 [3] に従い，次式で更新する．

から順にランキングする上位 N 件推薦問題を想定する．前節のデータを 5 分割し，5-fold cross validation によって評価を

new
ψδ
=ψδ

行う．

∑

HMMB-L の場合，リンクとその種類に関する尤度は，以下

g,h

∑
g,h

Ψ((1−ρ)C(g,h,δ)+ψδ )−Ψ(ψδ )Ψ(C(g,h,1)+(1−ρ)C(g,h,0)+∑δの式で求められる．

if
new
ψδ
=ψδ

P (Y | Z→ , Z← , πp , πq , B, M, Q; α, ψ, ϕ)=∏∑
p,q g,h∑ψδ )−Ψ((∑C(p, g) + αgC(q, h) + αh
(1 − ρ)Σg C(p, g) + Σg αg Σh C(q, h) + Σh αh

g,h

∑
g,h

Ψ(C(g,h,δ)+ψδ )−Ψ(ψδ )Ψ(C(g,h,1)+(1−ρ)C(g,h,0)+

∑

δ

δ

δ=0

∑

ψδ )−Ψ(

)

if

ψδ )

δ

(14)

ψδ )

δ=1

(15)

C(g, h, δ) + ψδC(g, h, t) + ϕt
(7)
C(g, h, 1) + C(g, h, 0) + Σδ ψδ Σt C(g, h, t) + Σt ϕt

HMMB-N，LHMMB については，ハイパーパラメータ α は

ここで，ρ はスパース性のモデリングのためのパラメータ [1]対称ディリクレを仮定し，その成分を α = 0.1 とし，ψ U I に
ついては，非対称ベータを仮定し，Minka の不動点反復法に従であり，ここでは以下のように定義する．

ρ = 1−d
d =

∑

(8)

Y (p, q)/(N × N )い，次式で更新する．
ψ

(9)

p,q

U I,new
UI
=ψδ
δ

∑

HMMB-N の場合，種類 U のノード p と種類 I のノード q

g,h

∑

g,h

Ψ((1−ρU I )C U I (g,h,δ)+ψ U I )−Ψ(ψ U I )δδ間のリンクに関する尤度は，以下の式で求められる (他の種類のリンクに関しても同様)．

(

U I,new
UI
ψ
=ψδ
δ

∏∑

P (Y | Z→ , Z← , πp , πq , B, L; α, ψ) =d =Y (p, q)/(U ∗ × I ∗ )p,qU ∗ , I ∗ はそれぞれの種類のノード数である．
（注 2）：http://www.grouplens.org/node/462

if

δ=0

∑

∑

δ=1

∑
δ

ψU I )
δ

(16)

∑
δ

ψU I )
δ(17)

他の種類の ψ についても同様である．また，グループ数 K = 10

)

(10)

として，実験を行った．LHMMB について，ハイパーパラメー
タ ϕ は対称ディリクレを仮定し，その成分を ϕ = 0.1 とした．

ここで，ρU I は以下のように定義する．

∑

ψ U I )−Ψ(δif

C I (p, g) + αg
C U (q, h) + αhIΣg C (p, g) + Σg αg Σh C U (q, h) + Σh αh

ρU I = 1 − dδΨ(C U I (g,h,δ)+ψ U I )−Ψ(ψ U I )
δ
δ
g,h
U
I
Ψ(C
(g,h,1)+(1−ρU I )C U I (g,h,0)+ψ U I )−Ψ(
g,h
δ δ

∑

(1 − ρU I )p,q g,hC U I (g, h, δ) + ψδU I
UI
C (g, h, 1) + C U I (g, h, 0) + Σδ ψδU I∑

Ψ(C U I (g,h,1)+(1−ρU I )C U I (g,h,0)+

4. 4 結
(11)
(12)

果

本実験では，アイテム推薦のシュミレーションを行うため，訓練データによって推定したモデルによって，ユーザごとにテストデータに含まれる全アイテムをランキングし，以下の 4 つの方法を用いて予測性能を測定した．

•

上位 10 件に含まれる正解アイテムの割合の平均をとる”top-10 precision”

•

最上位に出現する正解アイテムの順位の逆数の平均をとる”mean reciprocal rank”•

上位 10 件に少なくとも 1 つの正解アイテムが見つかったユーザの割合である”success rate at 10”•

正解アイテムが見つかった順位における precision を計算し平均をとる”mean average precision”

signed rank test [5] を用いて，MMSB を基準とした有意差の検定を行った．その結果を表 1 に示す．本検定において，提案手法である HMMB-N と MMSB との比較をしている。
表 1 Wilcoxon signed rank test
推薦方法

比較手法

p値

top-10 precision

HMMB-N

0.1708

HMMB-N(noUU)

0.1014

HMMB-N

2.376 × 10−5

MovieLenz のデータを用いた結果を図 5，図 6，図 7，図 8に示す．この実験において，MovieLenz のデータにユーザ間リ

mean reciprocal rank

HMMB-N(noUU) 6.511 × 10−14

ンクがないことから，”ユーザ間にグループ割り当てをしない”という設定でも実験を行った．これを実験結果上では”HMMB-

mean average precision

HMMB-N

2.200 × 10−16

HMMB-N(noUU) 2.200 × 10−16

N(noUU)”と表す．これに対し，HMMB-N はユーザ間リンクが無くてもユーザ間にグループ割り当てを行う．

表 1 から，mean reciprocal rank，mean average precisionにおいては，HMMB-N，HMMB-N(noUU) は p < 0.01 であるため，MMSB に対して有意に差があることを示した．

Last.fm のデータを用いた結果を図 9，図 10，図 11，図 12に示す．この実験において，Last.fm のデータにアイテム間リン
クがないことから，”アイテム間にグループ割り当てをしない”
図 5 top-10 precision for MovieLenzという設定でも実験を行った．これを実験結果上では”HMMB-

N(noII)”と表す．これに対し，HMMB-N はアイテム間リンクが無くてもアイテム間にグループ割り当てを行う．

図 6 mean reciprocal rank for MovieLenz

図 9 top-10 precision for Last.fm

図 7 successrate at 10 for MovieLenz

図 10 mean reciprocal rank for Last.fm

図 8 mean average precision for MovieLenz

図 11 successrate at 10 for Last.fm

図 5，図 6，図 8 においては，今回の提案手法である HMMB-

また，上位 10 件までに出てくる正解アイテムの順位の逆数

N は MMSB や HMMB-L よりも値が上回っており，モデルのの平均をとる mean reciprocal rank at 10 も行った．その結果精度が改善されているといえる．また，これらの MMSB に対すを図 13 に示す．

る改善が認められた結果に関して有意性を示すため，Wilcoxon

これらの実験全てにおいて，アイテム間にグループを割り当

at 10，mean reciprocal rank at 10 に見られることから，LHMMB は高順位に正解アイテムを推薦するという状況に強いのではないかと考えられる．
一方で，もうひとつの提案手法である HMMB-L の性能はMMSB に及ばないことが多かった．特に，MovieLenz のデータを用いた実験では，5-fold cross varidation を行った際，一図 12 mean average precision for Last.fm

部の fold の結果が不安定になってしまい，平均を引き下げていることが原因である．この不安定さについては，HMMB-N や

LHMMB に対して，HMMB-L の隣接行列のスパースさが原因であることが考えられる．
様々な評価方法を用いて提案手法を評価したが，提案手法の精度の良さは評価方法によって変化している．これは，各手法がそれぞれの特徴を持っている為であると考えられる．しかし，
図 13 mean reciprocal rank at 10 for Last.fm

一部を除き，どの提案手法も概ね MMSB よりも良い精度を示した．

てない LHMMB が MMSB よりも値を上回っている．また，図10，図 12，図 13 においては，今回の提案手法すべてが MMSB
を上回っている．また，これらの MMSB に対する改善が認められた結果に関して有意性を示すため，Wilcoxon signed rank

test [5] を用いて MMSB を基準とした有意差の検定を行った．
その結果の一部の例を表 2 に示す．

5. お わ り に
本論文では，異種ネットワークのための混合メンバシップブ
ロックモデルとして，リンクの種類に着目したモデル HMMB-Lと，ノードの種類に着目したモデル HMMB-N，ノードの種類とリンクに対して付与された複数のラベルを考慮したモデル

LHMMB を提案し，MovieLenz と Last.fm の 2 つのデータを

表 2 Wilcoxon signed rank test for Last.fm

用いて精度の確認を行った．上位 N 件推薦タスクによる評価

推薦方法

比較手法

p値

の結果，HMMB-N は従来の MMSB よりも有効であることを

top-10 precision

HMMB-N

0.08375

確認した．LHMMB は従来の MMSB よりも概ね有効であった

LHMMB(noII) 0.02157
mean reciprocal rank

HMMB-N

0.1789

LHMMB(noII) 0.005447
mean average precision

mean reciprocal rank at 10

HMMB-N

2.200 × 10−16

LHMMB

3.163 × 10−11

HMMB-N

0.0003202

LHMMB(noII) 4.956 × 10−6

表 2 では，mean average precision，mean reciprocal rank

at 10 においては，比較したどちらの手法でも p < 0.05 であるため，MMSB に対する有意性を確認できた．また，LH-

MMB，LHMMB(noII) ではすべての評価方法で p < 0.05 であり，MMSB に対する有意性を確認できた．

4. 5 考察

MovieLenz，Last.fm のどちらデータを用いても，今回の提案手法である HMMB-N が既存手法である MMSB よりも精度の高い推定ができていることがわかる．これは，同一ネット
ワーク上に異種ノードが存在するとき，ノードの種類を考慮することが有効であるということを示している．表 1，表 2 において，p < 0.05 である為，MMSB との差は有意であることも示した．ここで，top-10 precision において有意性が見られな
いのは，top-10 precision にゼロ値が多いという性質上，有意性が現れづらいことが原因であると考えられる．
また，LHMMB(noII) では，一部において HMMB-N よりも高い精度を示した．この現象が top-10 precision，successrateが，さらに一部において HMMB-N よりも高い精度を確認した．
一方で，HMMB-L は従来の MMSB の性能に及ばないという状況が多く見られた．より詳細な評価が今後の課題である．
文

献[1] E.M. Airoldi, D.M. Blei, S.E. Fienberg, and E.P. Xing.
Mixed membership stochastic blockmodels. The Journal of
Machine Learning Research, Vol. 9, pp. 1981–2014, 2008.
[2] C. Kemp, J.B. Tenenbaum, T.L. Griﬃths, T. Yamada, andN. Ueda. Learning systems of concepts with an inﬁnite relational model. In Proceedings of the national conference
on artificial intelligence, Vol. 21, p. 381. Menlo Park, CA;
Cambridge, MA; London; AAAI Press; MIT Press; 1999,
2006.
[3] T. Minka. Estimating a dirichlet distribution, 2000.
[4] K. Nowicki and T.A.B. Snijders. Estimation and prediction
for stochastic blockstructures. Journal of the American Statistical Association, Vol. 96, No. 455, pp. 1077–1087, 2001.
[5] F. Wilcoxon, S.K. Katti, R.A. Wilcox, Florida State University. Dept. of Statistics, and American Cyanamid Company.
Critical values and probability levels for the Wilcoxon rank
sum test and the Wilcoxon signed rank test. Lederle Laboratories Division, American Cyanamid, 1963.