DEIM Forum 2014 C4-6 カテゴリ階層の拡張を目的とした階層的トピックモデル 山本 浩平† 江口 浩二† 高須 淳宏†† † 神戸大学 大学院システム情報学研究科 〒 657-8501 神戸市灘区六甲台町 1-1 †† 国立情報学研究所 〒 100–8430 東京都千代田区一ツ橋 2-1-2 E-mail: †[email protected], [email protected] ††[email protected] あらまし カテゴリ階層付き文書データにおいて，新たなデータの追加によって既存のカテゴリ階層が不完全になり， カテゴリ階層への新規カテゴリの挿入や既存カテゴリの分割が必要とされることがある．そのようなカテゴリ階層の 拡張と文書データの再配置はしばしば困難を伴う．解決策として，カテゴリ階層を教師情報として利用する階層的ト ピックモデルの推定を行い，カテゴリ階層を自動的に拡張することが考えられる．そこで，階層の拡張を目的とした 階層的トピックモデルである 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,>l Number of times when the argument is true える． SBP は以下の比喩で表現される．区間 (0, 1) を単位長の棒 と見なして，Beta(α1 , α2 ) から選択した値 V1 をこの棒から折 り取る．つまり，この V1 を θ1 とし，1 − θ1 を棒の残りとす る．この棒に対して，再帰的に以上の手順を繰り返すことで， 数列に確率を与える．一般的には，以下の式で折り取った棒の 長さが表される． θi = Vi i−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 Stick-Braeking Process (SBP) [12] は，非負実数列 {θi }∞ i=1 ∑ に値を与える確率過程である．ここで， ∞ i=1 θi = 1 である． よって，この {θi }∞ i=1 は確率分布を構成するパラメータとい hLDA における潜在トピック木構造の高さを無限大にする ために，レベル上の分布 θ の事前分布に GEM 分布を利用す ることができる [1]．本論文では，この hLDA を GEM hLDA と呼び，θ の事前分布がディリクレ分布である hLDA を Dir hLDA と呼ぶ．GEM hLDA の生成過程は以下の通りである． （ 1 ） 各トピック k ∈ T に対して （ 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 ) を選択 |ce d| B. 単語 wd,n ∼ Mult(βcd,zd,n ) を選択 = （ b ） u が内部ノードであれば，u の各子ノード u′ ∈ Cu に ∏ Γ(nce−d,l ,· + V η) ∏ e w Γ(nc−d,l ,w + η) l=1 ∏ w Γ(nce−d,l ,w + nced,l ,w + η) Γ(nce−d,l ,· + nced,l ,· + V η) (4) 対して i. ノード gu′ ∼ U(c1,|c1 | , . . . , cDu ,|cDu | ) を選択 また，nCRP による事前分布である式 (3) の右辺第 2 項は，以 ii. gu′ を u′ の親ノードに設定 下の式で表される． ここで，上述した G-SSHLDA の生成過程において，レベル 上の分布 θ の事前分布を，第 2. 1. 2 節で紹介した GEM 分布 に変更する．これにより，G-SSHLDA でも無限深さの潜在木 |ce d| P (ced | ce−d , γ) = ∏ P (ced,l = k | ce−d , γ) l=2 を表現できる．また，各文書ごとの最大レベルをデータから推 定できるため，各観測ノードごとの潜在木の高さが決まり，文 P (ced,l = k | ce−d , γ) = 書に割り当てられるパスの末端ノードは潜在木の内部ノードに mc e mk +γ−1 (if k is existing) d,l−1 γ mc e d,l−1 +γ−1 (if k is new) もなりうる．結果として，潜在木の内部ノードへの接ぎ木を表 現可能な，より一般的なモデルとなる．レベル上の分布 θ の事 前分布に 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 に 設 定 し ，潜 在 パ ス (5) 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 ∝ nd,l −(d,n) nd,· −(d,n) +α + |cd |α · 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 π + nd,>i +Vη i=1 d, l 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 データセットの概要． Dataset Number 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 のように， より根に近いノード，または，より根から遠いノードへの接ぎ リが付与されるように，複数カテゴリが付与されている文書に ついては，取り出した部分木において最も深いレベルに存在す るもの以外を削除する．Wikipedia からは，カテゴリ階層にお 木後に，レベル割り当てのリサンプリングを行う． いま，図 2 を例として説明する．図 2 で左から右に木を変形 すると，ノード 3 を根とする部分木は，より浅いレベルのノー ドに接ぎ木される．よって，その部分木上の文書が利用できる レベルが減る．このとき，元々の割り当てがレベル 3, 4 のもの を，それぞれレベル 2, 3 に変更し，元々の割り当てが レベル 2 のものに対してはリサンプリングを行う．逆に，図 2 で右か ら左に木を変形すると，ノード 3 を根とする部分木は，より深 いレベルのノードに接ぎ木される．よって，その部分木上の文 書が利用できるレベルが増える．このとき，元々の割り当てが レベル 2, 3 のものを，それぞれレベル 3, 4 に変更し，さらに けるカテゴリ “Programming” を根ノードとする部分木に対し て同様の処理を行う．Wikipedia では，3 文書以下しか含まな いカテゴリを削除する． 両方のデータセットについて，ストップワード [4]，10 語以 下からなる文書と 5 文書未満にしか現れない語彙 [6]，数字と 記号のみからなる語彙を削除する． 以上の手順で作成した MEDLINE, Wikipedia のサブセット をそれぞれ ML, WP と呼ぶ．ML, WP の概要を表 2 に示す．表 2 から，2 種類のデータセットはそれぞれ異なった特徴を持つこ とがわかる． 5. 2 観測カテゴリ階層の拡張 一定割合のレベル割り当てに対してリサンプリングを行う． 4. 1. 4 推定アルゴリズム programming language programming code c system これまでに説明した条件付き分布を利用して，G-SSHLDA を周辺化ギブスサンプリングでモデル推定する．現在の変数の { } (t) (t) (t) 状態 c1:D , z1:D , g1:(|T o |−1) が与えられたとき，以下の推定 func!on example data value memory programming paradigms アルゴリズムにより各変数をサンプリングする． lisp object programming class func!onal application programming interface api opengl d windows graphics （ 1 ） 幅優先探索の各観測ノード u ∈ T o について （ a ） 観測ノードに属する各文書 d ∈ {1, . . . , Du } について i. 観測パス cod を T の根ノードから u までのパスとし て設定 contract literate rule eiffel answer oop paradigm structured dataflow declara!ve func!onal programming graphs random eager monads spirit e (t+1) ii. 潜在パス cd iii. パス (t+1) cd を式 (3) から選択 e (t+1) を cod と cd algol modula ajax pl oberon object-oriented programming abstract uml inversion subclasses four data tree func!on list 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 debugger purify verifica!on exploring sugges!ng detected arch lamp scm clearcase sccs version control system revision clearcase argue peer compliant 図 3 GEM G-SSHLDA によって拡張された WP のカテゴリ階層の の連結として設定 (t+1) iv. 各単語 n ∈ {1, . . . , Nd } について，レベル zd,n 一部．木全体は 310 個のノードからなる．見出しのある黒色の を 式 (7) または式 (8) から選択 ノードは観測ノード，赤色のノードは潜在ノードである．各ノー ドは単語上の分布 β の上位 5 件の語彙で表現されている． ′ （ b ） 各観測子ノード u ∈ Cu について，接ぎ木ノード (t+1) gu′ を式 (9) または式 (10) から選択 （c） (t) g u′ と (t+1) gu′ が異なるレベルに位置するとき，レベル 割り当てを補正 5. 実 WP に対して潜在木高さ 1 の GEM G-SSHLDA を推定し， 拡張カテゴリ階層を得る．Le = 1 とし，SBP は |cod | + 1 回で 打ち切る．周辺化ギブスサンプリングの繰り返し数は 500 回， 験 本節では，MEDLINE, Wikipedia という 2 種類の現実世界 の文書データに対する実験とその結果について説明する． ハイパーパラメータは η = 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 # nodes 200 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 が e 2, 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 のとき，全 体の 24% にあたる根ノードの文書（注 2）は，利用できるトピック 上の分布 θd の最頻値であるレベル l (1 < =l< = L) で示される ノードに各文書を配置する．また，Dir G-SSHLDA では，Dir が 2 個と少ない数になり，それらの文書を潜在トピックで十分 hLDA と同様の方法で各文書をノードに配置するが，レベル l o e の取りうる範囲を |cod | < =l< = |cd | + L とし，その範囲で θd を に表現できないため，hLDA より高いパープレキシティになる 最大にする l を選択する．GEM 分布に基づくモデルでは，各 と考えられる． 文書に割り当てられたパスの末端ノードにその文書を配置する． 以上のことから，Dir G-SSHLDA は，カテゴリ階層を教師 そして，生成されたクラスタから，データセットの準備の時点 情報として用いることで，汎化能力を改善することができると で削除されたノードに属していた文書以外を削除する．その結 いえる． 果のクラスタに対して，F 値と正規化相互情報量 (NMI) で評 価する． b ) GEM G-SSHLDA e = 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-score NMI 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-score NMI 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-score NMI 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-score Dir hLDA0.5 0.137 ± 0.020 Dir hLDA1.0 0.137 ± 0.008 GEM hLDA0.5 0.183 ± 0.006 GEM hLDA1.0 0.175 ± 0.014 Dir G-SSHLDA0.5 0.207 ± 0.009 Dir G-SSHLDA1.0 0.209 ± 0.007 GEM G-SSHLDA0.5 0.201 ± 0.006 GEM G-SSHLDA1.0 0.190 ± 0.003 Single linkage clustering 0.359 ± 0.154 NMI 0.754 ± 0.004 0.724 ± 0.008 0.801 ± 0.010 0.751 ± 0.014 0.871 ± 0.005 0.863 ± 0.011 0.851 ± 0.005 0.842 ± 0.002 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. Griffiths, 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. Griffiths, 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. Griffiths and M. Steyvers. Finding scientific topics. Proceedings of the National Academy of Sciences of the United 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 hierarchical model 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 of Lecture 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.
© Copyright 2024 ExpyDoc
