DEIM Forum 2014 C4-6

カテゴリ階層の拡張を目的とした階層的トピックモデル
山本 浩平†

江口

浩二†

高須

淳宏††

† 神戸大学 大学院システム情報学研究科 〒 657-8501 神戸市灘区六甲台町 1-1†† 国立情報学研究所 〒 100–8430 東京都千代田区一ツ橋 2-1-2
E-mail: †yamamoto@cs25.scitec.kobe-u.ac.jp, eguchi@port.kobe-u.ac.jp ††takasu@nii.ac.jp
あらまし カテゴリ階層付き文書データにおいて，新たなデータの追加によって既存のカテゴリ階層が不完全になり，カテゴリ階層への新規カテゴリの挿入や既存カテゴリの分割が必要とされることがある．そのようなカテゴリ階層の拡張と文書データの再配置はしばしば困難を伴う．解決策として，カテゴリ階層を教師情報として利用する階層的ト
ピックモデルの推定を行い，カテゴリ階層を自動的に拡張することが考えられる．そこで，階層の拡張を目的とした
階層的トピックモデルである Generalized SSHLDA (G-SSHLDA) を提案する．提案モデルは，任意の既存カテゴリの子孫となる潜在トピック階層をモデル化している点で従来モデルと異なる．実験では，現実データを利用して，提案モデルが推定した拡張カテゴリ階層と，提案モデルの汎化能力・クラスタリング能力の評価を行う．
キーワード

カテゴリ階層，階層的トピックモデル，nested Chinese Restaurant Process

1. は じ め にるモデルも存在する．しかし，これらのモデルは，カテゴリ分
割問題への活用には限界がある．

近年，人手で作成されたカテゴリ階層中に文書などのデータ

そこで，本論文では，新たな階層的トピックモデルであるを配置したカテゴリ階層付きデータコレクションが存在し，利Generalized SSHLDA (G-SSHLDA) を提案する．G-SSHLDA

用者の効率的な情報の発見を補助している．

は，観測カテゴリ階層中の任意ノードを根ノードとした，根そのようなコレクションの例として，生命科学分野の学術

ノード以外は潜在ノードからなる潜在木を階層中に挿入する．

文献データベースである MEDLINE や，オンライン百科事典

次に，ある観測ノードを根とする部分木を，その上位の潜在木である Wikipedia が存在する．これらのデータに付与された中のどのノードに接ぎ木するかの選択を，確率的にモデル化す

カテゴリは階層構造化されている．このため，MEDLINE やる．以上の方法より，G-SSHLDA はカテゴリ階層を自動的に

Wikipedia はカテゴリにデータが配置されているデータコレク

拡張することが可能である．

ションと見なすことができる．また，文書に付与されたカテゴ

提案モデルを検証するために，MEDLINE, Wikipedia のサリの名前や，カテゴリ間の階層関係を利用することで，ユーザブセットをデータセットとして，実験を行う．まず，データセッは効率的に情報を発見できる．

トに対して，提案モデルを推定し，得られた拡張カテゴリ階層

いま，これらのデータコレクションにおいて，新しい概念やを例示する．また，提案・既存両モデルの未知文書に対する汎話題を含む文書を，類似する概念や上位概念を表す既存カテゴ化能力をパープレキシティによって評価する．さらに，カテゴ

リ（観測カテゴリ）に配置することを考える．すると，新しいリ階層中の内部ノードを含むレベルを一部縮約したデータセッ

概念を含む文書を観測カテゴリに配置することで，観測カテゴ

トに対して，モデル推定によるカテゴリ階層拡張を行うことでリに新たな概念が混在するため，ユーザの情報発見の効率性が縮約したレベルを復元し，復元されたレベルにおける潜在ノー

損なわれる可能性がある．

ドの文書クラスタリング能力を評価する．以上の実験により，そこで，解決策として，観測カテゴリを分割し，新規カテゴ

G-SSHLDA は既存モデルと同程度の汎化能力を持ちつつ，既リを子孫として階層構造に挿入することで，それらの文書を再存のモデルでは実現できなかった拡張カテゴリ階層の推定に配置することが考えられる．しかし，人が新規カテゴリを作成

よって，カテゴリ分割問題に対応可能であることを示す．

して，そこに新規文書を配置するかどうか判断するのは，しばしば困難になる（カテゴリ分割問題）．

2. 関 連 研 究

本論文では，先に述べたカテゴリ分割問題を解決するために，

本節では，本研究の基盤となる階層的トピックモデルについトピックモデルの一種である階層的トピックモデルに着目する．

て述べる．ここからは，表 1 に示す表記を利用する．ある変数

トピックモデルは，文書・画像・ネットワークなどの，グルーが · で置換されているときは，その変数に関する総和を表す．

プ化された離散データ（データグループ）からなるコレクショ

また，ある変数の前に − が付与されているときは，その変数ンを解析する手法である [3], [7]．特に，hLDA [1], [2] に代表さで示される要素を除くことを表す．

れる階層的トピックモデルは，データに内在する潜在トピック

2. 1 階層的トピックモデルのための確率過程の階層関係を解析することが可能であり，SSHLDA [9] のよう2. 1. 1 Nested Chinese Restaurant Processに，データコレクションに付与されたカテゴリ階層を利用でき

nested Chinese Restaurant Process (nCRP) [1], [2] は，木Beta(·)
Dir(·)GEM(·)
Mult(·)nCRP(·)
U(·)
Cu
T
To
L
Le
D
Du
K
Nd
V
mi
nd,l
nk,v
nd,>l
nd,>
=l
#[·]

表 1 本論文で利用する表記．
Beta distribution
Dirichlet distribution
GEM distribution
Multinomial distribution
nested Chinese Restaurant Process
Uniform distribution
Observed children of observed node u
Infinite tree
Observed tree
Maximum level of the tree
Maximum level of the latent tree in G-SSHLDA
Number of documents
Number of documents in observed node u
Number of topics
Number of tokens in document d
Number of types
Number of customers at node i in nCRP
Number of tokens assigned to level l in document d
Number of times when type v is assigned to topic k
Number of tokens assigned to level > l in document d= nd,l + nd,>lNumber of times when the argument is trueえる．

SBP は以下の比喩で表現される．区間 (0, 1) を単位長の棒と見なして，Beta(α1 , α2 ) から選択した値 V1 をこの棒から折り取る．つまり，この V1 を θ1 とし，1 − θ1 を棒の残りとす
る．この棒に対して，再帰的に以上の手順を繰り返すことで，数列に確率を与える．一般的には，以下の式で折り取った棒の長さが表される．

θi = Vii−1∏(1 − Vj )

(2)

j=1

この方法で得られる {θi } は∑∞

i=1 θi = 1 を満たす [12]．

Beta(mπ, (1 − m)π) から Vi を選択して θ を構成するとき，
θ ∼ GEM(m, π) と表現し [1], [11]，この分布を GEM 分布と呼ぶ．ここで，m ∈ (0, 1) かつ π > 0 である．

2. 2 階層的トピックモデル
2. 2. 1 hLDA

構造上の確率過程である．nCRP を構成するために，フラット

Latent Dirichlet Allocation (LDA) [3] に代表されるトピッ

な整数分割上の確率過程である Chinese Restaurant Process

クモデルは，Bag-of-Words で表現した文書などの離散データ(CRP) を利用する．

グループのコレクションに対する確率的生成モデルである．ト

まず，CRP はパラメータ γ を持ち，以下の比喩で表現されピックモデルは，データグループが潜在トピックからなると仮る．可算無限個のテーブルが順序付けて並べられたレストラン

定しており，潜在トピックはデータグループを要約するものとを仮定する．また，γ は正の実数とする．今，{1, 2, . . . , } とラ見なせる．ここからは，データコレクション中のデータグルー

ベル付けできる D 人の客が，順番に店に入ってくるとする．こプの例として文書，データ点の例として単語を考える．

のとき，m 人目の客が座るテーブルを cm とすると，m 人目

hierarchical Latent Dirichlet Allocation (hLDA) [1], [2] はの客が i 番目のテーブルに座る確率は以下の分布によって決定

代表的な階層的トピックモデルである．hLDA では，フラットされる．

な潜在トピックを仮定する LDA とは異なり，潜在トピックはp(cm = i | c1:(m−1) ) =





mi
m+γ−1

(if i is existing)

γ
m+γ−1

(if i is new)

無限高さかつ無限に枝分かれする木構造の部分木を構成している．そして，木構造は nCRP によって生成され，nCRP における客が文書，テーブル（またはレストラン）がトピックを表(1)現している．

γ は客が新しいテーブルを選ぶ確率を制御する役割を果たす．

hLDA の生成過程は以下の通りである．ここからは，先行研D 人の客が以上の分布にしたがってテーブルに座ったとき，そ究 [1], [2] にならい，ディリクレ分布のハイパーパラメータはの座り方が D 個の整数分割を表現している．

全要素が同じ値であると見なし（対称ディリクレ分布），スカnCRP において，客は繰り返し CRP によるテーブルの選択

ラー値として表す．

を行い，木構造を構成する．nCRP は以下の比喩で表される．

（ 1 ） 各トピック k ∈ T に対して

街に可算無限個のレストランが存在し，各レストランは可算無（ a ） 単語上の多項分布パラメータ βk ∼ Dir(η) を選択

限個のテーブルを持つと仮定する．また，階層の根となるレス（ 2 ） 各文書 d ∈ {1, . . . , D} に対してトランが存在し，レストラン内の各テーブルは他のレストラン（ a ） パス上のノード cd,1 に T の根ノードを設定を指し示している．まず，客は根のレストランに入り，CRP に（ b ） 各レベル l ∈ {2, . . . , L} に対してしたがって，あるテーブルを選択する．次に，そのテーブルに

i. 式 (1) にしたがってノード cd,l を選択指示される別のレストランに行き，CRP にしたがって，ある（ c ） レベル上の多項分布パラメータ θd ∼ Dir(α) を選択

テーブルを選択する．これを無限に繰り返すことで，その客の（ d ） 各単語 wd,n (n ∈ {1, . . . , Nd }) に対して

木構造におけるパスを決定する．ここで，各レストランは，そi. レベル zd,n ∼ Mult(θd ) を選択

れぞれ木構造上のあるレベルに対応する．これをすべての客に

ii. 単語 wd,n ∼ Mult(βcd,zd,n ) を選択

ついて行うと，各レストランにおける客の座り方が無限に枝分かれした無限深さの木の部分木を表現するようになる．

2. 1. 2 Stick-Breaking Process

hLDA における潜在トピック木構造の高さを無限大にする
ために，レベル上の分布 θ の事前分布に GEM 分布を利用することができる [1]．本論文では，この hLDA を GEM hLDA

Stick-Braeking Process (SBP) [12] は，非負実数列 {θi }∞i=1∑に値を与える確率過程である．ここで， ∞i=1 θi = 1 である．

と呼び，θ の事前分布がディリクレ分布である hLDA を Dir

よって，この {θi }∞
i=1 は確率分布を構成するパラメータとい（ 1 ） 各トピック k ∈ T に対して

hLDA と呼ぶ．GEM hLDA の生成過程は以下の通りである．

（ a ） 単語上の多項分布パラメータ βk ∼ Dir(η) を選択（ 2 ） 各文書 d ∈ {1, . . . , D} に対して
（ a ） パス cd ∼ nCRP(γ) を選択（ b ） レベル上の多項分布パラメータ θd ∼ GEM(m, π) を選択
（ c ） 各単語 wd,n (n ∈ {1, . . . , Nd }) に対してi. レベル zd,n ∼ Mult(θd ) を選択
ii. 単語 wd,n ∼ Mult(βcd,zd,n ) を選択

図 1

潜在木高さ 1 の G-SSHLDA で拡張されるカテゴリ階層の例．

2. 2. 2 hLLDA

陰付きノードは観測ノード，無色ノードは潜在ノードを表す．各

hierarchical Labeled LDA (hLLDA) [10] は，カテゴリ階層

観測ノードは潜在木の根である．

が付与されたデータのための階層的トピックモデルである．カ
テゴリ階層は木構造であり，文書は階層における葉ノードに属

HEHLDA により，既存のカテゴリ階層外の文書中のトピックしている．文書は根ノードからその葉ノードまでのパス上のラをそのカテゴリ階層に統合するのに伴い，カテゴリ階層を水平

ベルのみをトピックとして利用する．

方向に拡張している．さらに，SSHLDA を併用することで，カhLLDA の生成過程は以下の通りである．

テゴリ階層を垂直方向に拡張している．一方，これらのモデル（ 1 ） 各トピック k ∈ T o に対して

は，階層への新たなレベルの挿入，内部ノードに配置する文書（ a ） 単語上の多項分布パラメータ βk ∼ Dir(η) を選択と葉ノードに配置する文書の違いの考慮ができない．よって，（ 2 ） 各文書 d ∈ {1, . . . , D} に対して

カテゴリ分割問題に適用するには限界がある．

（ a ） パス cd ∈ T o を設定

そこで，データコレクションに付与された既存のカテゴリ階（ b ） レベル上の多項分布パラメータ θd ∼ Dir(α) を選択

層の拡張を目的とした階層的トピックモデルである，Gener-（ c ） 各単語 wd,n (n ∈ {1, . . . , Nd }) に対してalized SSHLDA (G-SSHLDA) を提案する．G-SSHLDA

i. レベル zd,n ∼ Mult(θd ) を選択

では，観測カテゴリ階層の任意ノードに文書が割り当たった文ii. 単語 wd,n ∼ Mult(βcd,zd,n ) を選択

書集合を対象としている．生成過程において，文書は，根ノー2. 2. 3 SSHLDA

ドからその文書が配置された観測ノードまでのパスを観測パス

Semi-Supervised Hierarchical LDA (SSHLDA) [9] は hLDA

として選択する．さらに，文書が配置された観測ノードを根とと hLLDA を一般化したモデルである．カテゴリ階層が付与さして，nCRP を利用した潜在トピックからなる木構造（潜在れた文書集合を対象とする．SSHLDA は，hLLDA と同様に木）を生成し，潜在パスを選択する．これらの観測パスと潜在

カテゴリ階層中のラベルを 観測トピック として利用する．さパスを結合したものを，その文書のパスとする．以上の方法にらに，観測カテゴリ階層における葉ノードを根として，hLDA

より，各文書がどのノードに属しているかという情報を，観測と同様に潜在トピック階層を生成し，より粒度の細かい潜在ト

パスとして扱うことで利用できる．また，任意の観測ノードかピックを発見する．

ら潜在ノードを拡張することが可能となる．

SSHLDA の生成過程は以下の通りである．

一方，観測カテゴリ階層において，ある観測内部ノードの子（ 1 ） 各トピック k ∈ T に対してであった観測子ノードを根とする部分木を接ぎ木するための（ a ） 単語上の多項分布パラメータ βk ∼ Dir(η) を選択

ノード（接ぎ木ノード）の選択は自明ではない．ここで，以下（ 2 ） 各文書 d ∈ {1, . . . , D} に対しての仮定をおく．

（ a ） 各レベル l ∈ {1, . . . , L} に対して

i. このレベルが観測ノードのとき，そのノードを cd,l として設定•

カテゴリ階層上で多くのデータが割り当たるノードは，階層全体において重要な意味を持つため，下位のカテゴリと強い関連を持つii. そうでなければ，(1) の式にしたがって cd,l を選択

G-SSHLDA では，文書に割り当たるパスの末端ノードに，そ（ b ） レベル上の多項分布パラメータ θd ∼ Dir(α) を選択の文書が配置されていると見なし，観測内部ノードを根とする（ c ） 各単語 wd,n (n ∈ {1, . . . , Nd }) に対して

潜在木中の葉ノードに配置された文書数を重みとする分布から，

i. レベル zd,n ∼ Mult(θd ) を選択

接ぎ木ノードを選択する．この接ぎ木ノードの選択により，観ii. 単語 wd,n ∼ Mult(βcd,zd,n ) を選択

測カテゴリ階層へ新たなレベルが挿入できる．G-SSHLDA に

3. カテゴリ階層の拡張を目的とした階層的ト
ピックモデル

よって拡張されるカテゴリ階層の例を図 1 に示す．

G-SSHLDA の生成過程を以下に示す．
（ 1 ） 各トピック k ∈ T に対して

本節では，カテゴリ分割問題の解決のための階層的トピック
モデルを提案する．
観測・潜在の両トピックを利用できる階層的トピックモデルとして，SSHLDA や HEHLDA [8] が存在する．Mao らは，（ a ） 単語上の多項分布パラメータ βk ∼ Dir(η) を選択（ 2 ） 幅優先探索時の各ノード u ∈ T o に対して
（ a ） u に属する各文書 d ∈ {1, . . . , Du } に対して

i. 観測パス cod を根ノードから u までのパスとして設定
ii. 潜 在 木 の 根

ced,1を u に 設 定 し ，各 レ ベ ル l ∈{2, . . . , Le } に対してP (ced | w, c−d , z, η, γ) ∝ P (wd | ced , w−d , zd , η)P (ced | ce−d , γ)(3)
ここで，パスが与えられた下での単語の尤度である式 (3) の右A. 式 (1) にしたがって ced,l を選択
iii. レベル上の多項分布パラメータ θd ∼ Dir(α) を選択
iv. 各単語 n ∈ {1, . . . , Nd } に対して

辺第 1 項は，以下の式で表される．

P (wd | ced , w−d , zd , η)

A. レベル zd,n ∈ {1, . . . , |cd |} ∼ Mult(θd ) を選択|ced|B. 単語 wd,n ∼ Mult(βcd,zd,n ) を選択=（ b ） u が内部ノードであれば，u の各子ノード u′ ∈ Cu に∏Γ(nce−d,l ,· + V η)∏ew Γ(nc−d,l ,w + η)

l=1∏w Γ(nc−d,l ,w + ncd,l ,w + η)
e

Γ(n

ce
,·
−d,l

e

+n

ce
,·
d,l

+ V η)(4)

対して

i. ノード gu′ ∼ U(c1,|c1 | , . . . , cDu ,|cDu | ) を選択

また，nCRP による事前分布である式 (3) の右辺第 2 項は，以ii. gu′ を u′ の親ノードに設定

下の式で表される．

ここで，上述した G-SSHLDA の生成過程において，レベル上の分布 θ の事前分布を，第 2. 1. 2 節で紹介した GEM 分布に変更する．これにより，G-SSHLDA でも無限深さの潜在木|ced|P (ced | ce−d , γ) =∏P (ced,l = k | ce−d , γ)l=2を表現できる．また，各文書ごとの最大レベルをデータから推定できるため，各観測ノードごとの潜在木の高さが決まり，文P (ced,l = k | ce−d , γ) =書に割り当てられるパスの末端ノードは潜在木の内部ノードに

(5)


m

 mce k+γ−1(if k is existing)(if k is new)

d,l−1

γ
mc e

d,l−1

+γ−1

もなりうる．結果として，潜在木の内部ノードへの接ぎ木を表現可能な，より一般的なモデルとなる．レベル上の分布 θ の事
前分布に GEM 分布を利用した G-SSHLDA は以下の生成過程で表される．レベル上の分布 θ の事前分布に GEM 分布を利用した G-SSHLDA は以下の生成過程で表される．

(6)
サンプリングにおいて，各文書に割り当てる潜在パスを選択する際に，式 (3) を用いる．

4. 1. 1 レベル割り当てのサンプリング
各文書中の各単語に割り当てるレベルのサンプリングを行う（ 1 ） 各トピック k ∈ T に対してために必要な，レベルの完全条件付き分布は以下の通りである．

（ a ） 単語上の多項分布パラメータ βk ∼ Dir(η) を選択（ 2 ） 幅優先探索時の各観測ノード u ∈ T o に対してP (zd,n = l | c, w, z−(d,n) , α, η)（ a ） u に属する各文書 d ∈ {1, . . . , Du } に対して−(d,n)

i. 観測パス cod を根ノードから u までのパスとして設定
ii. 潜 在 木 の 根

ced,1を u に 設 定 し ，潜 在 パ ス

ced∼nCRP(γ) を選択
iii. レベル上の多項分布パラメータ θd ∼ GEM(m, π) を選択

iv. 各単語 n ∈ {1, . . . , Nd } に対して
A. レベル zd,n ∼ Mult(θd ) を選択
B. 単語 wd,n ∼ Mult(βcd,zd,n ) を選択（ b ） u が内部ノードであれば，u の各観測子ノード u′ ∈ Cu∝−(d,n)nd,l+α−(d,n)+ |cd |αnd,··ncd,l ,w + η(7)−(d,n)

ncd,l ,· + V η

また，GEM 分布に基づいたモデルにおける，レベルの完全条
件付き分布は以下の通りである．

P (zd,n = l | c, w, z−(d,n) , m, π, η) nc−(d,n)
 mπ + n−(d,n) l−1∏ (1 − m)π + n−(d,n)
d,zd,n ,w + η
d,l
d,>i
∝
−(d,n)−(d,n)−(d,n)
 π+n >
 nc
π+n >,· + V η
d,=l

i=1

d,=i

d,zd,n(8)に対してi. ノード gu′ ∼ U(c1,max(z1 ) , . . . , cDu ,max(zDu ) ) を選択
ii. gu′ を u′ の親ノードに設定
本論文では，θ の事前分布にディリクレ分布，GEM 分布を用いたものを，それぞれ Dir G-SSHLDA, GEM G-SSHLDAと呼ぶ．実験では，これら 2 種類のモデルについて評価する．

4. 1. 2 接ぎ木ノードのサンプリング
観測ノード u 中の各文書のパス cd と各単語のレベル割り当て zd,n が与えられたとき，u を根とする潜在木における葉ノー
ド kl を接ぎ木ノードとして選択し，観測子ノード u′ を根とす
る部分木を接ぎ木する．このときの，u を根とする潜在木における葉ノード ℓ を接ぎ木ノードとして選択する条件付き分布は

4. モデル推定
本節では，G-SSHLDA を推定するための方法について説明する．本論文では，各モデルの推定に周辺化ギブスサンプリン
グを利用する．

4. 1 潜在パスのサンプリング
各文書に割り当てられる潜在パスの条件付き分布は，以下の通りに変形できる．

以下の通りである．

P (gu′ = ℓ | ce ) =

mℓ
mu

(9)

また，GEM 分布に基づいたモデルにおける，接ぎ木ノードを選択する条件付き分布は以下の通りである．

P (gu′ = k | ce , z) =#[ced,max(zd ) = k]
mu

(10)

図2

レベル割り当てのリサンプリングが必要な接ぎ木による木の変形．

表 2 データセットの概要．
DatasetNumber of labels
Max height of the obseved tree
Avg. path length per document (approx.)
Number of documents
Avg. number of documents per label (approx.)
Number of types
Number of tokens

ML
WP
12
88
3
6
0.94
2.09
56,227
2,086
4,686
24
27,876
6,447
5,129,694 453,479

4. 1. 3 レベル割り当てのリサンプリング
GEM G-SSHLDA のモデル推定において，Fig. 2 のように，より根に近いノード，または，より根から遠いノードへの接ぎ
木後に，レベル割り当てのリサンプリングを行う．
いま，図 2 を例として説明する．図 2 で左から右に木を変形すると，ノード 3 を根とする部分木は，より浅いレベルのノードに接ぎ木される．よって，その部分木上の文書が利用できるレベルが減る．このとき，元々の割り当てがレベル 3, 4 のものを，それぞれレベル 2, 3 に変更し，元々の割り当てが レベル

2 のものに対してはリサンプリングを行う．逆に，図 2 で右から左に木を変形すると，ノード 3 を根とする部分木は，より深いレベルのノードに接ぎ木される．よって，その部分木上の文書が利用できるレベルが増える．このとき，元々の割り当てがレベル 2, 3 のものを，それぞれレベル 3, 4 に変更し，さらに一定割合のレベル割り当てに対してリサンプリングを行う．

リが付与されるように，複数カテゴリが付与されている文書については，取り出した部分木において最も深いレベルに存在す
るもの以外を削除する．Wikipedia からは，カテゴリ階層におけるカテゴリ “Programming” を根ノードとする部分木に対して同様の処理を行う．Wikipedia では，3 文書以下しか含まないカテゴリを削除する．
両方のデータセットについて，ストップワード [4]，10 語以下からなる文書と 5 文書未満にしか現れない語彙 [6]，数字と記号のみからなる語彙を削除する．
以上の手順で作成した MEDLINE, Wikipedia のサブセット
をそれぞれ ML, WP と呼ぶ．ML, WP の概要を表 2 に示す．表 2から，2 種類のデータセットはそれぞれ異なった特徴を持つことがわかる．

5. 2 観測カテゴリ階層の拡張

4. 1. 4 推定アルゴリズム

programming
language programmingcode c system

これまでに説明した条件付き分布を利用して，G-SSHLDA
を周辺化ギブスサンプリングでモデル推定する．現在の変数の
{
}
(t)
(t)
(t)
状態 c1:D , z1:D , g1:(|T o |−1) が与えられたとき，以下の推定

programming paradigms

アルゴリズムにより各変数をサンプリングする．

lisp object programmingclass func!onal

func!on example
data value memory

application programming
interface

api opengl d windows
graphics（ 1 ） 幅優先探索の各観測ノード u ∈ T o について（ a ） 観測ノードに属する各文書 d ∈ {1, . . . , Du } について

i. 観測パス cod を T の根ノードから u までのパスとして設定
e (t+1)iv.

oop paradigm structured
dataﬂow declara!ve

func!onal programming
graphs random eager
monads spirit

ii. 潜在パス cd
iii.

contract literate rule
eiﬀel answer

を式 (3) から選択

(t+1)
e (t+1)
パス cd
を cod と cdの連結として設定(t+1)
各単語 n ∈ {1, . . . , Nd } について，レベル zd,n を

式 (7) または式 (8) から選択

algol modula
ajax pl oberon

object-oriented programming
abstract uml inversion
subclasses four

data tree func!onlist value

programming languages
logic memory bit
design circuit

sql rela!onal
database query rows

computer programming tools
text word editor editors
kde

debugger cygwin
build yacc xcode

debuggerpurify veriﬁca!on exploringsugges!ng detectedarch lamp scm
clearcase sccs

version control systemrevision clearcase
argue peer compliant

図 3 GEM G-SSHLDA によって拡張された WP のカテゴリ階層の一部．木全体は 310 個のノードからなる．見出しのある黒色のノードは観測ノード，赤色のノードは潜在ノードである．各ノードは単語上の分布 β の上位 5 件の語彙で表現されている．

′（ b ） 各観測子ノード u ∈ Cu について，接ぎ木ノード
(t+1)
gu′
を式 (9) または式 (10) から選択
(t)
(t+1)
が異なるレベルに位置するとき，レベル（ c ） gu′ と gu′

拡張カテゴリ階層を得る．Le = 1 とし，SBP は |cod | + 1 回で割り当てを補正打ち切る．周辺化ギブスサンプリングの繰り返し数は 500 回，

5. 実

験

本節では，MEDLINE, Wikipedia という 2 種類の現実世界の文書データに対する実験とその結果について説明する．

WP に対して潜在木高さ 1 の GEM G-SSHLDA を推定し，ハイパーパラメータは η = 1.0, γ = 1.0, m = 0.5, π = 100 とする．得られた拡張カテゴリ階層を図 3 に示す．
図 3 において，階層の根である観測ノード programming における潜在木に着目すると，プログラミングに関する文書で5. 1 データセット

は一般的な programming, language, code といった語で構成

実験では，MEDLINE の 2009 年のデータ，Wikipedia のされており，その潜在子ノードは data, memory, tree, func-

データ [5] について，そのサブセットを利用する．MEDLINE

tion といった，プログラミングにおける個別の概念を表す語からサブセットを抽出するために，各データに付与されたカテで表現されている．また，下位の観測ノードについても，例

ゴリがなす木構造から，“Face” を根ノードとする部分木を取りえば programming paradigms における潜在木に着目すると，出す．次に，その部分木中のカテゴリが付与された文書をデー

structured, oop, contract, declarative といった語で表現されタコレクションから取り出す．そして，各文書に 1 個のカテゴるノードがあることから，プログラミングパラダイムについて

の文書の内容を視覚的に把握することができる．これは，他のML についても観測カテゴリ階層の拡張を行い，同様の結果が得られた．以上のことから，G-SSHLDA によって，観測ノー

1900

2000

1800

1900

1700

Perplexityのノードに接ぎ木されており，階層は木構造を保持する．

Perplexity

潜在木についても同様である．さらに，各潜在木は上位潜在木

1600
1500

G-SSHLDA m=0.25
hLDA m=0.25
G-SSHLDA m=0.5
hLDA m=0.5

1400
1300
0

500

ドと潜在ノードが統合された拡張カテゴリ階層を自動的に得ら

1000

1500

1800
1700

G-SSHLDA m=0.25
hLDA m=0.25
G-SSHLDA m=0.5
hLDA m=0.5

1600
1500
2000

0

# nodes200 400 600 800 1000 1200 1400 1600
# nodes

れることがわかる．潜在ノードを新たなカテゴリと見なすことで，カテゴリ分割問題に対する一つの解決策になるといえる．

5. 3 汎化能力の評価(a) η = 0.5(b) η = 1.0

図 7 WP に対する GEM G-SSHLDA, GEM hLDA のパープレキシ
ティ．

3400

Perplexity

Perplexity

3200
3000
2800
G-SSHLDA η=0.5
hLDA η=0.5
hLLDA η=0.5
SSHLDA η=0.5

2600
2400
0

200

400

600

800

1000

1200

3600
3500
3400
3300
3200
3100
3000
2900
2800
2700

1400

が高いことを表す．未知のテストデータ wtest に対するパープ
レキシティは以下の式で求められる．

G-SSHLDA η=1
hLDA η=1
hLLDA η=1
SSHLDA η=1
0

200

400

600

# nodes

800

1000

1200

# nodes(a) η = 0.5(b) η = 1.0

図 4 ML に対する Dir G-SSHLDA, Dir hLDA, hLLDA, SSHLDA

perplexity(wtest )( ∑D ∑N
)
train
test
d
, M)
d=1
n=1 log P (wd,n | w= exp −
∑D
d=1 Nd(11)

ここで，wtrain は訓練データ，M は評価するモデルを表す．
本実験では，G-SSHLDA, hLDA, hLLDA, SSHLDA を評価のパープレキシティ．

の対象とする．ML, WP に対して，各文書を構成する単語集合
をランダムに 5 分割し [13] ，5 分割交差検定で評価する．各1420

G-SSHLDA η=1
hLDA η=1
hLLDA η=1
SSHLDA η=1

1580
Perplexity

Perplexity

1380

モデルにおいて，周辺化ギブスサンプリングによる繰り返し

1600

G-SSHLDA η=0.5
hLDA η=0.5
hLLDA η=0.5
SSHLDA η=0.5

1400

1360
1340

1560

数は 500 回，ハイパーパラメータは α = 0.1, η ∈ {0.5, 1.0},

γ = 1.0, m ∈ {0.25, 0.5, 0.6, 0.7}, π = 100 とする（注 1）．

1540

各モデルにおける周辺化ギブスサンプリングの繰り返し数

1520

1320

1500
0

1000

2000

3000

4000

5000

0

1000

2000

# nodes

3000

4000

400 回目から 500 回目の間に，10 回につき 1 回，テストデー

5000# of nodes

タに対するパープレキシティを計算する．その結果として得た(a) η = 0.5

10 個のパープレキシティの値を平均したものを，そのテスト(b) η = 1.0

データに対する最終的なパープレキシティとする．
図 5 WP に対する Dir G-SSHLDA, Dir hLDA, hLLDA, SSHLDAのパープレキシティ．

G-SSHLDA では，Le ∈ {1, 2, 3} として，既存モデルとパー
プレキシティを比較する．ML では，各文書の平均観測パス距離が 0.94 ≈ 1 である．よって，G-SSHLDA において Le を 1, 2,

4200

3800

4000

3600

3800

3400

Perplexity

Perplexity

3 とすると，各文書の平均パス距離はそれぞれ 2, 3, 4 となる．
4000

3200
3000

G-SSHLDA m=0.25
hLDA m=0.25
G-SSHLDA m=0.5
hLDA m=0.5

2800
2600
2400
0

100

200

300

400

# of nodes

500

これより，hLDA では L ∈ {2, 3, 4} として比較する．また，

SSHLDA における木は，モデルの仮定から観測木の高さより

3600
G-SSHLDA m=0.25
hLDA m=0.25
G-SSHLDA m=0.5
hLDA m=0.5

3200
3000
2800
600

高くする必要がある．そのため，SSHLDA では L ∈ {4, 5, 6}

3400

0

100

200

300

400

500

とする．同様に，WP では，hLDA を L ∈ {3, 4, 5} ，SSHLDA
600# of nodes

を L ∈ {7, 8, 9} とする．

hLLDA と SSHLDA では，内部ノードに属する文書をラン(a) η = 0.5(b) η = 1.0

図 6 ML に対する GEM G-SSHLDA, GEM hLDA のパープレキシ
ティ．

ダムに子孫の葉ノードに配置し直したデータを用いる．本実験
では，SSHLDA における観測パスの選択は，観測木の根ノードから文書が属する葉ノードまでのパスを固定して用いるものとする．また，GEM 分布に基づく hLDA と G-SSHLDA に

本節では，提案モデルの未知データに対する汎化能力を検証する．あるトピックモデルが，訓練データだけでなく，未知デー
タに対しても高い生成確率を持つとき，モデルの汎化能力は高く，未知データに対して，より正確にトピックを推定できる．
本論文では，汎化能力の評価尺度として，パープレキシティを利用する．パープレキシティが低いほど，モデルの汎化能力

おいて，上記の高さの木に基づいて SBP を打ち切る．

5. 3. 1 実験結果と考察
各モデルのパープレキシティの比較を 図 4 から 図 7 に示す．
（注 1）：GEM G-SSHLDA については，m ∈ {0.6, 0.7} も調査したが，m ∈{0.25, 0.5} より結果は改善しなかった．よって，本論文では，m ∈ {0.25, 0.5}についてのみ報告する．

各グラフにおいて，横軸は階層におけるノード数，縦軸はパー
プレキシティを表す．エラーバーは標準偏差を表す．

観測カテゴリ階層において，1 個のカテゴリ内に多様な内容の文書が混在している場合に，カテゴリ分割問題が発生する．

図 4 では，左から右の各プロットが，Dir hLDA の L がe2, 3, 4, Dir SSHLDA の L が 4, 5, 6, G-SSHLDA の L が

本節では，提案モデルのカテゴリ分割問題への対応力を検証するために，クラスタリング能力の評価を行う．

1, 2, 3 のときに対応する．図 5 では，左から右の各プロット

今回の実験では，観測カテゴリ階層の根を 0 レベルとして，が，Dir hLDA の L が 3, 4, 5, Dir SSHLDA の L が 7, 8, 9,

WP の階層の 1, 2 レベル，1, 2, 3 レベル, 2, 3 レベル，3 レ

G-SSHLDA の Le が 1, 2, 3 のときに対応する．hLLDA は観

ベルを縮約したものをそれぞれ作成する．縮約されたレベル上測木のみをモデル推定に利用するため，常にノード数は一定でのノードに配置されていた文書は，その先祖のうち一番葉ノーある．そのため，ノード数の軸に水平な直線で表現している．

ドに近いノードに再配置する．この階層が付与されたデータを

図 6 では，左から右の各プロットが，GEM hLDA の L が 2,それぞれ D1,2 , D1,2,3 , D2,3 , D3 と呼ぶ．文書の平均パス長は3, 4, GEM G-SSHLDA の Le が 1, 2, 3 のときに対応する．

D1,2 が約 0.45, D1,2,3 が約 0.13, D2,3 が約 1.08, D3 が約 1.78

図 7 では，左から右の各プロットが，GEM hLDA の L が 3,

である．

e

4, 5, GEM G-SSHLDA の L が 1, 2, 3 のときに対応する．

この実験は，内部ノードを含むレベルを復元するため，従来a ) Dir G-SSHLDAの教師あり階層的トピックモデルとの直接的な比較はできない．

図 4 において，η ∈ {0.5, 1.0}, Le ∈ {2, 3} のときに，Dir

よって，今回は，hLDA と階層的クラスタリングの一手法であG-SSHLDA は Dir hLDA と同程度か，もしくは改善したパー

る単連結法 (single linkage method) をベースラインとして利プレキシティを示している．図 5 においても，η ∈ {0.5, 1.0}

用する．

の両方で，Dir G-SSHLDA は全ての潜在木高さについて，他

まず，各データセットに対して各モデルを推定する．このとモデルと同程度か，もしくは改善したパープレキシティを示し

き，各データにおける文書の平均パス長にしたがって，各モデている．これは，Dir G-SSHLDA が他のモデルと比較して，同ルの木の高さを 表 3 に示す値とする．Dir hLDA では，モデ程度もしくは良い汎化能力を持つことを示す．

ル推定によって各文書に割り当てられたパスについて，レベル

また，ML において，Le = 1 のときは，Dir hLDA の方が良eいパープレキシティを示している．これは，L = 1 のとき，全（注 2）

体の 24% にあたる根ノードの文書

は，利用できるトピック

上の分布 θd の最頻値であるレベル l (1 <=l<= L) で示されるノードに各文書を配置する．また，Dir G-SSHLDA では，Dir

が 2 個と少ない数になり，それらの文書を潜在トピックで十分

hLDA と同様の方法で各文書をノードに配置するが，レベル loeの取りうる範囲を |cod | <=l<= |cd | + L とし，その範囲で θd をに表現できないため，hLDA より高いパープレキシティになる最大にする l を選択する．GEM 分布に基づくモデルでは，各と考えられる．

文書に割り当てられたパスの末端ノードにその文書を配置する．

以上のことから，Dir G-SSHLDA は，カテゴリ階層を教師

そして，生成されたクラスタから，データセットの準備の時点

情報として用いることで，汎化能力を改善することができるとで削除されたノードに属していた文書以外を削除する．その結いえる．

果のクラスタに対して，F 値と正規化相互情報量 (NMI) で評価する．

b ) GEM G-SSHLDAe= 1 の GEM G-

各モデルについて，周辺化ギブスサンプリングによる繰り返

SSHLDA は，それぞれの図の m = 0.25 かつ L = 4 または

図 6, 7 において，m = 0.25 かつ L

し数は 500 回，ハイパーパラメータは α = 0.1, η ∈ {0.5, 1.0},

L = 5 の GEM hLDA と同程度のパープレキシティを示してい

γ = 1.0, m = 0.5, π = 100 とする．第 5. 3 節で利用した 5 分

る．一方，その他の場合では，GEM hLDA が良いパープレキ

割したデータに対して，4 個のデータをクラスタリングの対象

シティを示している．これは，GEM hLDA と比較して，GEM

として，G-SSHLDA, hLDA のモデル推定とクラスタへの文書

G-SSHLDA の汎化能力にあまり改善が見られないことを示す．

の割り当て処理によるクラスタリングを行う．この要領で，4

GEM G-SSHLDA のパープレキシティが大きくなる原因と個のデータの組み合わせを替えつつ，実験を 5 回繰り返す．

して，GEM 分布のパラメータ m が適切でないことや，接ぎ単連結法の実験には，クラスタリングのためのソフトウェア

木ノードの推定をレベル割り当て頻度のみに基づいて行っていパッケージである CLUTO （注 3） を用いる．また，単連結法でることが考えられる．

は，縮約されたレベルに含まれるノードに属している文書のみ

5. 4 クラスタリング能力の評価
表 3 各データセットに対する木の高さ．
Dataset Le of G-SSHLDA L of hLDA
D1,2
2
2
D1,2,3
3
3
D2,3
2
3
D3
1
3

を対象とし，削除されたノードの数だけクラスタを生成する．

5. 4. 1 実験結果と考察
それぞれの手法によるクラスタリングの評価値の平均と標準偏差を 表 4 から 表 7 に示す．それぞれの尺度について，平均が最も良い結果を太字で示している．表 4 から 表 6 では，どの場合においても，G-SSHLDA がベースラインを上回る結果を示している．一方，表 7 の場合は，NMI では η = 0.5 の Dir（注 2）：一方，WP では，根ノードに属する文書の数は，総文書数の約 5% である．

（注 3）：http://glaros.dtc.umn.edu/gkhome/cluto/cluto/overview

表 4 D1,2 における結果．
Model
F-scoreNMI
Dir hLDA0.5
0.428 ± 0.043
0.491 ± 0.011
Dir hLDA1.0
0.386 ± 0.026
0.428 ± 0.008
GEM hLDA0.5
0.478 ± 0.031
0.549 ± 0.005
GEM hLDA1.0
0.411 ± 0.026
0.485 ± 0.014
Dir G-SSHLDA0.5
0.444 ± 0.029
0.496 ± 0.008
Dir G-SSHLDA1.0
0.403 ± 0.032
0.439 ± 0.008
GEM G-SSHLDA0.5
0.509 ± 0.026 0.566 ± 0.006
GEM G-SSHLDA1.0
0.490 ± 0.019
0.527 ± 0.010
Single linkage clustering 0.273 ± 0.014
0.064 ± 0.001

いえる．

表 5 D1,2,3 における結果．
Model
F-scoreNMI
Dir hLDA0.5
0.524 ± 0.040
0.457 ± 0.006
Dir hLDA1.0
0.488 ± 0.033
0.393 ± 0.005
GEM hLDA0.5
0.544 ± 0.027
0.519 ± 0.011
GEM hLDA1.0
0.460 ± 0.052
0.453 ± 0.006
Dir G-SSHLDA0.5
0.577 ± 0.053
0.461 ± 0.006
Dir G-SSHLDA1.0
0.548 ± 0.048
0.395 ± 0.005
GEM G-SSHLDA0.5
0.620 ± 0.025 0.573 ± 0.010
GEM G-SSHLDA1.0
0.539 ± 0.014
0.511 ± 0.013
Single linkage clustering 0.433 ± 0.070
0.082 ± 0.004

た．今後の課題として，画像・映像などのデータを対象とした

6. お わ り に
本論文では，カテゴリ階層が付与されたデータコレクショ
ンにおけるカテゴリ分割問題を解決するために，カテゴリ階層の自動的な拡張を目的とした階層的トピックモデルである

Generalized SSHLDA (G-SSHLDA) を提案した．実験により，
G-SSHLDA はカテゴリ分割問題に対応可能であることを示しモデルへの拡張，モデリングの洗練，モデルのオンライン推定などが挙げられる．

謝辞本研究の一部は，科学研究費補助金基盤研究 (B) (23300039)の援助，および国立情報学研究所の公募型共同研究による．
文

表 6 D2,3 における結果．
Model
F-scoreNMI
Dir hLDA0.5
0.417 ± 0.058
0.539 ± 0.006
Dir hLDA1.0
0.372 ± 0.020
0.486 ± 0.005
GEM hLDA0.5
0.487 ± 0.036
0.617 ± 0.014
GEM hLDA1.0
0.430 ± 0.033
0.562 ± 0.007
Dir G-SSHLDA0.5
0.548 ± 0.023 0.687 ± 0.008
Dir G-SSHLDA1.0
0.494 ± 0.040
0.610 ± 0.028
GEM G-SSHLDA0.5
0.442 ± 0.013
0.573 ± 0.021
GEM G-SSHLDA1.0
0.344 ± 0.029
0.495 ± 0.008
Single linkage clustering 0.518 ± 0.132
0.109 ± 0.008
表 7 D3 における結果．
Model
F-scoreNMI
Dir hLDA0.5
0.137 ± 0.020
0.754 ± 0.004
Dir hLDA1.0
0.137 ± 0.008
0.724 ± 0.008
GEM hLDA0.5
0.183 ± 0.006
0.801 ± 0.010
GEM hLDA1.0
0.175 ± 0.014
0.751 ± 0.014
Dir G-SSHLDA0.5
0.207 ± 0.009 0.871 ± 0.005
Dir G-SSHLDA1.0
0.209 ± 0.007
0.863 ± 0.011
GEM G-SSHLDA0.5
0.201 ± 0.006
0.851 ± 0.005
GEM G-SSHLDA1.0
0.190 ± 0.003
0.842 ± 0.002
Single linkage clustering 0.359 ± 0.154 0.119 ± 0.011

G-SSHLDA が最も良い結果だが，F 値では単連結法が最も良い結果である．これは，単連結法はちょうど削除されたノードの数だけクラスタを生成するのに対して（この場合 28 個），

Dir G-SSHLDA はクラスタをより多く生成している（この場
合，平均 39 個）ことに起因すると考えられる．
また，どの場合でも，より深いレベルを復元するときに，NMIが良くなる傾向が見られる．これは，G-SSHLDA が，より浅いレベルの階層を利用することで，より精度の高いな木の拡張を行えるためだと考えられる．さらに，GEM G-SSHLDA は，浅いレベルを復元するときに Dir G-SSHLDA より精度が改善する傾向が見られる．このことから，Dir G-SSHLDA と比較
して，GEM G-SSHLDA は，復元するレベルの上位レベルについての情報が少ないときにも，うまく働くことが考えられる．
以上の結果から，ほとんどの場合で，G-SSHLDA はより適切に各潜在ノードへ文書を配置できている．また，木の内部のレベルのみを復元できる点は G-SSHLDA 特有のものであり，G-SSHLDA はカテゴリ分割問題を解決できる力があると献[1] D. M. Blei, T. L. Griﬃths, and M. I. Jordan. The nested
chinese restaurant process and bayesian nonparametric inference of topic hierarchies. Journal of the ACM, 57(2):7,
2010.
[2] D. M. Blei, T. Griﬃths, M. Jordan, and J. Tenenbaum. Hierarchical topic models and the nested chinese restaurant
process. Advances in Neural Information Processing Systems, 16:106–114, 2003.
[3] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent dirichlet allocation. The Journal of Machine Learning Research,
3:993–1022, 2003.
[4] J. P. Callan, W. B. Croft, and S. M. Harding. The inquery
retrieval system. In Database and Expert Systems Applications, pp. 78–83, 1992.
[5] L. Denoyer and P. Gallinari. The Wikipedia XML Corpus.
SIGIR Forum, 2006.
[6] T. L. Griﬃths and M. Steyvers. Finding scientific topics.
Proceedings of the National Academy of Sciences of theUnited States of America, 101(Suppl 1):5228–5235, 2004.
[7] T. Hofmann. Probabilistic latent semantic indexing. In
Proceedings of the 22nd Annual International ACM SIGIR
Conference on Research and Development in Information
Retrieval, pp. 50–57, 1999.
[8] X.-L. Mao, J. He, H. Yan, and X. Li. Hierarchical topic
integration through semi-supervised hierarchical topic modeling. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp.
1612–1616, 2012.
[9] X.-L. Mao, Z.-Y. Ming, T.-S. Chua, S. Li, H. Yan, and
X. Li. Sshlda: a semi-supervised hierarchical topic model.
In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 800–809, 2012.
[10] Y. Petinot, K. McKeown, and K. Thadani. A hierarchicalmodel of web summaries. In Proceedings of the 49th Annual
Meeting of the Association for Computational Linguistics,
pp. 670–675, 2011.
[11] J. Pitman. Combinatorial stochastic processes, Vol. 1875 ofLecture Notes in Mathematics. Springer-Verlag, 2006.
[12] J. Sethuraman. A constructive definition of dirichlet priors.
Statistica Sinica, 4:639–650, 1994.
[13] Y. W. Teh, D. Newman, and M. Welling. A collapsed variational bayesian inference algorithm for latent dirichlet allocation. In Advances in Neural Information Processing
Systems, Vol. 19, pp. 1353–1360, 2006.