潜在的ディリクレ配分法の単語列への拡張 Extension to word phrase

DEIM Forum 2010
潜在的ディリクレ配分法の単語列への拡張
鈴木
康広†
上村
卓史†
喜田
拓也†
有村 博紀†
† 北海道大学 大学院情報科学研究科 〒 060–0814 札幌市北区北 14 条西 9 丁目
E-mail: †{yasuhiro-suzu,tue,kida,arim}@ist.hokudai.ac.jp
あらまし 潜在的ディリクレ配分法 (Latent Dirichlet Allocation, LDA) は文書クラスタリング手法の一種であり，文
書を単語の集合（bag of words）と考えて，各単語を生成したトピックを推定する．これにより，各トピックが表す
単語の生成確率分布は，文書の意味的な表現となる．本稿では，接尾辞木を用いた単語列上の確率モデルを用い，ト
ピックの割り当てを単語列上に拡張する．この拡張により，より明確なトピック表現が可能になると期待される．
キーワード
潜在的ディリクレ配分法, クラスタリング，テキストマイニング
Extension to word phrase on latent dirichlet allocation
Yasuhiro SUZUKI† , Takashi UEMURA† , Takuya KIDA† , and Hiroki ARIMURA†
† Graduate School of Information Science and Technology, Hokkaido University Kita 14, Nishi 9, Kita-ku,
Sapporo, Hokkaido, 060-0814, Japan
E-mail: †{yasuhiro-suzu,tue,kida,arim}@ist.hokudai.ac.jp
Abstract Latent Dirichlet Allocation (LDA) is one of the document clustering methods. The method regards a
document as a bag of words, and presumes a topic of each word. The probability distribution of the words for each
topic is considered to be a representation of semantics of the document. In this paper, we discuss an extension of
LDA to be able to assign a topic to each phrase rather than each word used probability distribution utilized suffix
tree on each phrase. In this extension, more precise topic representation can be expected.
Key words Latent Dirichlet Allocation, Clustering, Text Mining
1. は じ め に
現在，記録媒体の発達によって，膨大な量のテキストデータ
トピックが割り当てられていると考えられる．そのため，１つ
の文書に複数の分野の情報をもつデータであっても，１つのト
ピックが割り当てられるという問題がある．
を扱う機会が増えている．そのため，情報処理の様々な状況に
そこで，本稿では，文書単位と単語単位の中間として，フ
おいて，それらのデータの中から有用なデータを発見するテキ
レーズ（ここでは可変長の単語列）を単位として，LDA を適
ストマイニングの重要性が高まっている．近年，テキストマイ
用することを考える．接尾辞木を用いた文脈を考慮したフレー
ニング手法として，潜在的ディリクレ配分法が注目されている．
ズ抽出 [?] を前処理としてフレーズを抽出し，LDA モデルを適
潜在的ディリクレ配分法は，最近提案されたテキストマイニ
用する．フレーズの列へのトピック割り当てに拡張することで，
ング手法の一種である．これは，文書を単語の集合と考えて，
より柔軟なトピック割り当てができると考える．各トピック割
単語単位にトピックを割り当て，各単語の生成したトピックを
り当ての手法を図??に示す．
推定する手法である [?]．
推論方法には，Griffiths らのギブスサンプリング [?] を用い
一方で，文書単位でトピック（クラスタ）を割り当てる手法
る．この手法では，各単語のトピックとその他の単語のトピッ
として，混合分布を用いた K-Means クラスタリングが広く使
クとの関係を，ギブスサンプリングで推定することで，各ト
われている [?]．この手法と比べると，潜在的ディリクレ配分法
ピックの出現確率を推定される．
は，文書単位のクラスタリングではなく単語単位のクラスタリ
最後に，実際の文献情報を用いた計算機実験を行った．
ングをしていると考えられる．
潜在的ディリクレ配分法は，単語にトピックを割り当てる．
そのため，出現頻度の高い語は，多くのトピックに単語が割り
当てるため，単語の分類が困難になるという問題がある．一
方で，K-Means クラスタリングは，1 つの文書の単語に同じ
—1—
タイプ 割り当て手法 割り当て 区切り 統計
単位
方
モデル
I
II
III
混合多項分布 文書
を用いたクラ
スタリング（確
率K-MEANS）
フレーズ単位
のトピック割り
当て手法
LDAP
(提案手法)
単語単位の
トピック割り当
て手法LDAW
(従来のLDA)
固定
推論
手法
混合多項 EM法 [1]
分布モデル
文献
[1]
であるという条件を満たすものである．ここに，添字 i は，
<j=
< E(i) の範囲をと
1<
=i<
= N の範囲をとり，添字 j は，1 =
>
る．ここに，E(i) = 0 は，si 中のフレーズの個数である．以下
では，P h {p1 , . . . , pL ⊂
=P h で，DP h 中に出現することなるフ
レーズのなす集合を表わす．L = |P h| である．
フレーズ 固定
（部分
単語列）
LDAモデル ギブスサンプ 本論
リング [5]
文
与えられた文書集合 DW に対して，そのフレーズ分解 DP h
は一意ではなく，一般に指数個存在する．与えられた DW から
定められた基準に基づいてフレーズ分解 DP h を計算する問題
は，文書や系列の分節化問題，理論言語学分野や統計学習分野
単語
LDAモデル 変分EM法 [2] [2],
ギブスサンプ [5]
リング [5]
固定
で様々な手法が研究されている [6]．
本研究では，4 節で DW から DP h を計算する経験的アルゴ
リズムを与える．
2. 3 トピック割り当て
図 1 各トピック割り当ての手法
トピック割り当て (topic assignment) は，文書集合に対す
るテキストマイニング問題の一種である．以下では，正整数
整数 M >
= 1 に対して，W = {w1 , . . . , wM } を単語(word) の全
体集合とする．
各 t ∈ T は，トピック (主題，topic) と呼ばれ，文書や単語
2. 1 文 書 集 合
W 上の文書集合 (document set in words) または，単語単
の種類数の情報を表わす．トピックの具体的な意味は，5 節で
述べるトピック割り当ての統計モデルを与えることで定める．
位の文書集合とは，2 次元配列
初めに，単語単位のトピック割り当てについて説明する．
DW = (di ) = (wij ) (1 <
=i<
= N, 1 <
=j <
= L(i), wij ∈ W ) を
，W 上の単語単位の文書集合とする．
DW = (di )
= (wij )
である．ここに，添字 i は，1 <
=i<
= N の範囲をとり，添字 j
は，1 <
=j<
= L(i) の範囲をとる．ここで，各 1 <
=i<
= N に対
して，第 i 行 di = (wi1 , . . . , wiL(i) ) ∈ W ∗ を第 i 番目の文書と
いう．L(i) >
= 0 を di の長さという．各 1 <
=j<
= L(i) に対して，
第 j の要素 wij ∈ W を文書 di の第 j 番目の単語という．
文書集合 DW = (wij ) に対して，そのサイズを DW が含む
単語の総出現数 ||DW || =
K >
= 1 に対して，トピックの全体集合を T = {t1 , . . . , tK } と
する．
∑N
i=1
L(i) と定義する．
2. 2 文書集合のフレーズ分解
W 上のフレーズ (phrase) または単語列 (word sequence)
とは，W の要素の空でない有限列 p = (w1 , . . . , wl ) ∈ W +
+
(l >
= 0) である．W 上のフレーズの全体集合を P hW = W で
表わす．
文書 d = (wj ) = (w1 , . . . , wL(i) ) ∈ W ∗ に対して，d のフ
レーズ分解 (phrase factoring) または分節化 (segmentation)
とは，W 上のフレーズの有限列 S = (p1 , . . . , pE(i) ) ∈ (P hW )∗
(0 <
= L(i)) で，そのフレーズを連結すると元の文書 d
= E(i) <
になるもの，すなわち，条件 d = p1 . . . pE(i) を満たすもので
ある．
DW = (di )N
i=1 = (wij ) を W 上の文書集合とする．正整数を
<
N
とおく．
DW のフレーズ分解または分節化とは，2
i
1<
= =
次元配列
Dph = (si )
= (pij )
で ，各 1 <
= i <
= N に 対 し て ，DP h の 第 i 行 si =
(Pi1 , . . . , PiE(i) ) ∈ P hW ∗ は，DW の第 i 行のフレーズ分解
DW に対する単語単位のトピック割り当てまたは単にトピッ
ク割り当て (topic assignment) とは 2 次元配列
Z = (zij )
である．ここに，任意の 1 <
=i<
=N と1<
=j<
= L(i) に対して，
zij ∈ T は，任意のトピックである．この zij を，位置 (i, j) の
単語 wij に割り当てられたトピックと呼ぶ．
次に，フレーズ単位のトピック割り当てについて説明する．
DP h = (si ) = (pij ) (1 <
=i<
= N, 1 <
=j <
= E(i), pij ∈ P hW )
を，文書集合 DW = (di ) = (wij ) のフレーズ分解とする．DP h
にたいするフレーズ単位のトピック割り当てまたは単にトピッ
ク割り当て (topic assignment) とは，2 次元配列
Z = (zij )
である．ここに，任意の 1 <
=i<
=N と1<
=j<
= E(i) に対して，
zij ∈ T は，任意のトピックである．この zij を，位置 (i, j) の
フレーズ pij に割り当てられたトピックと呼ぶ．
図 2 に文書集合とフレーズ分解の例を示す．
3. 接 尾 辞 木
本節では，単語集合をフレーズの列に拡張して表現するため
に接尾辞木を示す．接尾辞木(Suffix Tree) [4] は，与えられた文
字列のすべての接尾辞を表すトライ(trie) である．トライとは，
可変長文字列集合を格納する効率の良いデータ構造である．
文字列 T ∈ Σ∗ の接 尾辞 木 ST (T ) は ，(V, root, E) の 3
つ 組 で 表 さ れ る ．V は ，ノ ー ド の 集 合 で あ る ．頂 点 root
2
は ，接 尾 辞 木 ST (T ) の 根 で あ る ．E は ，辺 の 集 合 E ⊂
=V
—2—
Dw 1
d1
w11
…
j
・・・
w1j
・・・
di
wi1
・・・
・・・
L(1)
単語列 s のすべての後続語 x について fD (sx) < γ · fD (s) であ
・・・
w1L(1)
るならば，s はフレーズである．ここに，δ は 0 以上の整数で
・・・
あり，0 < γ <
= 1 である．より直観的には，フレーズとは，複
数の用例が存在する単語列である．すべての単語はフレーズで
・・・
wiji
・・・
・・・
dN wN1
…
wi L(i)
・・・
wNj
・・・
・・・
ある．
wN L(N)
文書集合 D の接尾辞木上においては，単語列とその後続
語はノードの親子関係で表される．すなわち，ノード u ∈ V
Dph
s1
p11
si
pi1 ・・・
sN
pN1
p1j
・・・
・・・
p1E(1)
・・・
図2
・・・
pij
・・・
pNj
・・・
di = wi1 , . . . , wiL(i) をフレーズの列 si = pi1 , . . . , piE(i) に分
pi E(i)
・・・
・・・
と u の子 v ∈ V ，単語 x について child (u, x) = v であるな
らば，v は u の x で終わる後続語を表すノードである．文書
pN E(N)
文書集合 DW とそのフレーズ分解 DP h
で あ る ．任 意 の 辺 e ∈ E に は ，T の 空 で な い 部 分 文 字 列
T [j . . . k], (1 <
= j <
= k <
= |T |) がラベル付けされる．|T | は
文字列 T の文字数である．
任意のノード s ∈ V について，ノード s が表す文字列とは，
root から s へのパス上の辺にラベル付けされた文字列を連結し
て得られる T の部分文字列である．
例として，図 3 に文字列 ABABC$ の接尾辞木を示す．ノー
ドの中の数字は，そのノードが表す文字列の出現頻度を表す．
本稿では，単語もしくはフレーズを単位として文書を扱うこと
から，文書中のそれらの語をそれぞれ 1 つの文字とみなして接
尾辞木を構築する．すなわち，図 3 において A と, B, C は，そ
れぞれ文書内の単語もしくはフレーズである．
割する手順は以下の通りである:
（ 1 ） j = 0 とする．
（ 2 ） 文書 di = wi1 , . . . , wiL(i) に対して，di の単語長が
L(i) 以下である間，以下を繰り返す:
（ a ） 文書 wi1 , . . . , wiL(i) の接頭辞である最長のフレーズ
pij = wi1 , . . . , wik を計算する．
（ b ） pij を出力する．
（ c ） j = j + 1 とする．
（ d ） di = wi(k+1) , . . . , wiL(i) とする．
5. フレーズに拡張した潜在的ディリクレ配分法
5. 1 統計モデル
本節では，フレーズ単位のトピック割り当てのためのモデ
ル (生成モデル) を与える．このとき，潜在的ディリクレ配分
法 [2], [5] のための統計モデルは次のとおりである．
θ | α ∼ Dir(α)
(1)
ϕ | β ∼ Dir(β)
(2)
Z | θ ∼ M ulti(θ)
(3)
DP h | Z, ϕ ∼ M ulti(ϕ)
(4)
式 (1) について，θ は，文書集合のフレーズ分解 DP h 内のフ
レーズについての，トピックの割り当て確率分布の集合である．
θ = (θ1 , . . . , θN ) で表わす．θi は，フレーズの列 si に対しての
トピックの生成確率分布であり，超パラメータ α > 0 のディリ
クレ分布で生成される．θi = (θi1 , . . . , θiK ) で表す．任意のフ
レーズの列 si について，
図 3 文字列 T =ABABC$に対する接尾辞木．ノードの中の数字はそ
のノードが表す文字列の出現頻度を表す．
∑K
k=1
θik = 1 である．
式 (2) について，ϕ = (ϕ1 , . . . , ϕK ) は，各トピック 1 <
=K
=k<
毎のフレーズの生成確率分布 ϕk の集合である．ϕk は，超パラ
メータ β > 0 のディリクレ分布で生成される．任意のトピック
文書集合 D = {d1 , . . . , dN } が与えられたとき，D の全要素
∑
に対する接尾辞木は，これらを連結した列 T = d1 $1 · · · dN $N
M
1<
= K について， j=1 ϕkj = 1 である．
=k<
式 (3) は，式 (1) のパラメータ θ のディリクレ分布 Dir(α) に
の接尾辞木として表すことができる．$i (i = 1, . . . N ) は終端
対する，各文書のトピック割り当て多項分布 M ult(θ) である．
記号である．
4. 接尾辞木を用いたフレーズの抽出
文書集合 D 中のある文書 di 中に現れる単語列を s とし，x
を di 中のある単語とする．このとき，sx が D 中のいずれかの
文書 e に現れるならば，x は s の後続語であるという．fD (s)
をフレーズ s の出現頻度としたとき，fD (s) > δ であり，かつ
式 (4) は，式 (2) の多項分布 ϕ と式 (3) のトピック割り当て
Z が条件として与えられたときの DP h の生成確率である．
このとき，DP h と，トピック割り当て集合 Z ，パラメータ
ϕ, θ の同時確率分布を次に示す．
P (DP h , Z, ϕ, θ | α, β)
= P (DP h | Z, ϕ)P (ϕ | β)P (Z | θ)P (θ | α)
(5)
(6)
—3—
•
Algorithm Gibbs:
LDAW: 潜在的ディリクレ配分法によるトピック割り当
てを単語列に行うアルゴリズム．
input: DW のフレーズ分解 DP h と, 繰り返し回数 R, トピッ
•
LDAP: 潜在的ディリクレ配分法によるトピック割り当
ク割り当て Z, P hW の種類数 |P hW |;
てを接尾辞木を用いて変換した，フレーズの列に行うアルゴリ
output: 再計算された割り当て Z = (Zij );
ズム．
論文情報のタイトルから，空白で区切られたアルファベ
1: for r = 1, . . . R do
2:
for i = 1, . . . , N do
for j = 1, . . . , E(i) do
t = Zij ;
3:
4:
6:
p = Pij ;
N Ppt = N Ppt − 1;
7:
N Dit = N Dit − 1;
8:
N P SU Mt = N P SU Mt − 1;
N DSU Mi = N DSU Mi − 1;
5:
9:
for (k = 1, . . . , K) do
nume = ((N Dik + α) ∗ (N Pjk + β));
10:
11:
deno = (N DSU Mi + α · K) ∗ (N P SU Mk +
β · |P hW |)
12:
P Rk =
13:
nume
deno
ット の 列 を 単 語 w ∈ W と し ，各 著 者 の 論 文 情 報 を 文 書
di ∈ DW , si ∈ DP h とした．単語集合から接尾辞木を構築
し，単語をフレーズに拡張した．特に指定がない限り，接尾辞
木の閾値 δ = 1 とした．ディリクレ分布のパラメータ α, β は
それぞれ α = 50/K, β = 0.1 である．
6. 3 実 験 結 果
実験では，フレーズ列への潜在的ディリクレ配分法を行うた
めに，アルゴリズムは LDAP に対して，実験を行った．
実験データは，MICHAEL と UKKONEN を用いた．繰り返
し回数を 3000 回で行った．フレーズ閾値を γ = 0.9 とし，ト
ピック数を 2 とした．
LDAW との LDAP の比較を行う．実験データは LDAP と
14:
end for
15:
多項分布 P Rt に従い，トピック t を確率的に選ぶ;
16:
N Ppt = N Ppt + 1;
果を表 1 に示す．
17:
N Dit = N Dit + 1;
N P SU Mt = N P SU Mt + 1;
うな単語は，出現頻度が高いため両方のトピックに出現しやす
18:
N DSU Mi = N DSU Mi + 1;
Zij = t
19:
20:
21:
22:
end for
end for
同じデータである．トピック数は 2 とする．LDAW の実験結
LDAW は，表 1 の上から 6 番目の単語”approximate”のよ
い．これはランダムサンプリングでトピックを割り当てられて
いると考えられる．LDAP の実験結果を表 2 に示す．(M n) は，
実験データ MICHAEL に出現するフレーズであり，(U n) は，
23: end for
実験データ UKKONEN に現れる．フレーズである．実験結果
24: return Z;
から，トピック 0 には MICHAEL に現れるフレーズが多くな
り，トピック 1 には，UKKONEN に現れるフレーズが多く著
図 4 ギブスサンプリングの手続き
者ごとの分類が行われていると考える．
単語単位では出現頻度が高い語も，フレーズにすることで，
5. 2 推論手続き
両方のトピックに出現しにくくなる．
図 4 は，DP h から Z, θ, ϕ を計算するギブズサンプリングの
アルゴリズムである．これは，現在のトピック割り当て集合 Z
7. お わ り に
から，各場所 ij に対して，その場所以外のすべてのトピック割
り当てから，フレーズ pij に対するトピック zij の出現確率を
求めて，zij を再度割り当てる．
このプロセスを任意の繰り返し回数を行い，各フレーズ DP h
に割り当てられるトピック Z を求める．
本稿では，単語への潜在的ディリクレ配分法を，フレーズへ
の潜在的ディリクレ配分法に拡張し考察した．
実験結果から，2 単語以上が連結した，有用なフレーズを発
見した．フレーズの列への拡張を行う事で，意味的に分かりや
すいトピック割り当てが可能になる．
6. 実
験
6. 1 実験データ
実験データとして，コンピュータサイエンス分野の論文デー
タベースである DBLP の文献情報から，論文情報を用いた．実
験データは以下の通りである．
•
MICHAEL: 著者名が”Michael I. Jordan”である論文情
報を全て集めたデータ (177 件)
•
UKKONEN: 著者名が”Esko Ukkonen”である論文情報
を全て集めたデータ (135 件)
6. 2 方
法
下記の 2 種類のアルゴリズムを C++言語で実装した．
実験では，フレーズを区切る際の閾値，および潜在的ディリ
クレ配分法の超パラメータを固定して行っている．今後の課題
として，超パラメータ α と β ，フレーズを区切るための閾値 γ
に対して，様々な値を取ることによる変化を検証を行いたい．
文
献
[1] Christopher M. Bishop, Pattern Recognition and Machine
Learning, Springer, 2006.
[2] David M. Blei, Andrew Y. Ng, Michael I. Jordan, Latent
Dirichlet Allocation, Journal of Machine Learning Research,
3:993–1022, 2003.
[3] Kumiko T. Ishii, H. Nakagawa, A Multilingual Usage Consultation Tool based on Internet Searching —More than
search engine, Less than QA, Proc. the 14th International
World Wide Web Conference (WWW2005), 363–371, 2005.
—4—
表 1 MICHAEL と UKKONEN のデータからの潜在的ディリクレ配
分法の適用結果 (出現頻度上位 50 単語)
topic 0
f
topic 1
f
1 matching
21 1 learning
44
2 kernel
11 2 string
25
3 pattern
11 3 data
17
3 models
10 4 approximate 16
4 approach
10 5 matching
14
5 approximate 10 6 markov
13
5 detection
10 6 trees
13
5 dimensional
10 6 inference
13
6 model
9
6 algorithms
13
6 time
9
6 models
13
表 2 MICHAEL と UKKONEN のデータからの潜在的ディリクレ配
分法の適用結果 (出現頻度上位 50 単語)
topic 0
f
topic 1
f
1 approximate string matching(U 8) 5 1 suffix trees(U 4)
4
2 graphical models(M 5)
4 2 string matching(U 14)
3
3 feature selection(M4 U 1)
3 2 reinforcement learning(M 4)
3
3 hidden markov(M 6 U1)
3 3 exponential families(U 3)
2
4 decentralized detection(M 2)
2 3 lower bound(U 2)
2
4 spectarl clustering(M 6)
2 3 finding approximate(U 2)
2
4 em approach(M2)
2 3 pattern matching(U 8)
2
4 lalr k testing(U 2)
2 3 machine learning(M 2)
2
4 variational methods(M 2)
2 3 cryo electron microscopy(U 3) 2
4 mixtures experts(M 3)
2 3 combinatorial patternmatching(U 2)
2
[4] P. Weiner, Linear Pattern Matching Algorithms, Proc. of
the 14th IEEE Symp. on Switching and Automata Theory,
1–11, 1973.
[5] Thomas L. Griffiths, M. Steyvers, Finding Scientific Topics,
PNAS, 101:5228–5235, 2004.
[6] S. Goldwater, Thomas L. Griffiths, M. Johnson, Contextual
Dependencies in Unsupervised Word Segmentation, Proc.
ACL 2006, 2006.
—5—