第10回講義資料

LSA, pLSA, LDA
• 文書・単語行列をモデル化する
• ノイズと偏りを除去する方法に諸手法あり
トピックモデル
–
–
–
–
LSA と pLSA と LDA
櫻井彰人
LSA, LSI: Latent Semantic Analysis/Indexing
pLSA: Probabilistic Latent Semantic Analysis
LDA: Latent Dirichlet Allocation
なお、tf/idf が非常に重要な概念であるが、今回は省略
• 最近は、Non‐negative matrix factorization (NMF) も注
目されている
Wikipediaより
LSA vs. PLSA/LDA
z1,…,zK
uk
文書
d1,..,dN
w1,…,wM
z1,…,zK
z1,…,zK k
0
0
文書di
PLSA/LDA in Graphical Models
z1,…,zK
単
語
wj
pLSA
d
vk
z
K
 P(d )P( z
k 1
i
k
w
| di ) P(w j | zk )  P(di , w j ) 
P( d i  w j1 w j2  w j|d | )  P( d i )l 1
|d i |
i
d1,…,dN
d1,…,dN P(di
0)
w1,…,wM
z1,…,zK
0
文書
d1,..,dN
z1,…,zK
文書di
単
語
wj
P(w |zk)
d
または

K
k 1
z
 P( z )P(d | z )P(w
k
k 1
P (w |  ,  )   P( |  )k 1
K
i
k
j

| zk )
P( z k | d i ) P ( w jl | z k )
をパラメータとする
多項分布と考える
LDA
w
K

zk
をパラメータとする
多項分布と考える

P ( z k |  ) P( wk | z k ,  ) d
をパラメータとする多
項分布と考える
をパラメータとする
多項分布と考える
P(d |zk)
目次


Latent Semantic Analysis/Indexing (LSA/LSI)
Probabilistic LSA/LSI (pLSA または pLSI)




長所・短所
作り方
 アスペクトモデル
 Tempered EM
LSA との比較
Latent Dirichlet Allocation (LDA)



長所・短所
作り方
LSA/pLSA との比較
LSA vs. LSI
• LSA と LSAI
– LSA: Latent Semantic Analysis
– LSI: Latent Semantic Indexing
• 両者の違いは？
– LSI: 情報の indexing , i.e. 情報検索に用いる.
– LSA: 解析（いろいろ）に用いる.
– 同じ技術を異なる分野に適用しただけ.
1
問題
問題例
• 例: ベクトル空間モデルで
• ベクトル空間モデルを用いたときに出てくる二
つの問題:
– cosine 類似度で考える: 大きい方がより類似
– 同義語: 同じもの・事を意味する異なる語．
• 「リコール率」が悪くなる
auto
engine
bonnet
tyres
lorry
boot
– 「オートバイ」で検索したら、「二輪」が出てこない
– i.e. 結果にあるべきものがないことが多くなる
– 多義語: 多くの単語には複数個の意味がある
• 「精度（precision）」が悪くなる
– Java （コーヒー）で検索したら Java （プログラム言語）に関する
ものが得られる
– i.e. 結果に間違ったものが入っていことが多くなる
同義語
– D={d_1, … ,d_N}
make
hidden
Markov
model
emissions
normalize
多義語
Cosine 類似度が小さい Cosine 類似度が大きいが、
が、関連している
関連せず
道具立て
• コーパス, N 個の文書の集合
car
emissions
hood
make
model
trunk
(from Lillian Lee)
LSI: Latent Semantic Indexing
• Latent – "潜在", "隠れ"
• Semantic – “意味”
• 語彙, M 個の単語の集合
– W={w_1, … ,w_M}
LSI を用いると単語の “隠れた意味”を、
単語が文書中に現れる様子から見出す
• 大きさ N * M の行列で、文書に単語が出現していることを表す
– 文書・単語行列と呼ばれる
– 0‐1行列（現れる（1）か否（０）か）、または頻度行列（出現回数）を用いる
潜在意味空間
LSI の方法
Latent Semantic Space
• LSI は、単語と文書を潜在意味空間に写像す
る
• 特異値分解: SVD (Singular Value Decomposition )
• 潜在意味空間においては、同義語（類義語）
は近くにくるべきである

A{mn 行列} = U{mr 行列} Σ{rr 行列} V*{rn 行列}

近似行列を得る: k (r)個の特異値のみ使用


Ak{mn 行列} = U{mk 部分行列} Σ{kk 部分行列} V*{kn 部分行列}
単語と文書ベクトルを k次元ベクトルに変換する
2
LSA と SVD
トピック
単語
簡単な例
トピック
単語
k
Anthony Julius
and
Caesar
Cleopatra
ANTHONY
1
BRUTUS
1
CAESAR
1
CALPURNIA
0
CLEOPATRA
1
MERCY
1
WORSER
1
k
VT
A
文書
Σ
U
=
The
Tempest
1
1
1
1
0
0
0
Hamlet
0
0
0
0
0
1
1
Othello
0
1
1
0
0
1
1
Macbeth
0
0
1
0
0
1
1
1
0
1
0
0
1
0
k
mxr
mxn
uk
文書
d1,..,dN
rxr
rxn
z1,…,zK
z1,…,zK
z1,…,zK k
0
単
語
wj
z1,…,zK
0
文書di
または
w1,…,wM
Anthony and Cleopatra
Julius Caesar
The Tempest
Hamlet
Othello
Macbeth
vk
ANTHONY BRUTUS CAESAR CALPURNI CLEOPATRMERCY
1
1
1
0
1
1
1
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
1
0
0
WORSER
1
0
1
1
1
1
1
0
1
1
1
0
Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2008.
簡単な例
簡単な例：近似
> d
setwd("E:/R/")
d <- read.csv("08LSI-Shakespeare.csv", header=T, row.names=1)
ANTHONY BRUTUS CAESAR CALPURNIA CLEOPATRA MERCY WORSER
Anthony and Cleopatra
1
1
1
0
1
1
1
Julius Caesar
1
1
1
1
0
0
0
The Tempest
0
0
0
0
0
1
1
Hamlet
0
1
1
0
0
1
1
Othello
0
0
1
0
0
1
1
Macbeth
1
0
1
0
0
1
0
d.svd <- svd(d)
d - d.svd[[2]] %*% diag(d.svd[[1]]) %*% t(d.svd[[3]])
plot(d.svd[[2]][,1:2])
text(d.svd[[2]][,1:2],labels=rownames(d),pos=3)
plot(d.svd[[3]][,1:2])
text(d.svd[[3]][,1:2],labels=colnames(d),pos=3)
Anthony and Cleopatra
Julius Caesar
The Tempest
Hamlet
Othello
Macbeth
ANTHONY BRUTUS CAESAR CALPURNI CLEOPATRMERCY
1
1
1
0
1
1
1
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
1
0
0
The Temp
WORSER
MERCY
0.4
0.4
Othello
-0.4
-0.2
-0.2
Macbeth
0.0
d.svd[[3]][, 1:2][,2]
0.0
and Cleopatra
CLEOPATRA
AESAR
BRUTUS
CALPUR
-0.4
-0.6
d.svd[[2]][, 1:2][,2]
0.2
0.2
Hamlet
ANTHONY
Julius Caesar
-0.60
-0.55
-0.50
-0.45
-0.40
-0.35
-0.30
-0.5
-0.25
-0.4
-0.3
-0.2
-0.1
d.svd[[3]][, 1:2][,1]
d.svd[[2]][, 1:2][,1]
WORSER
1
0
1
1
1
1
1
0
1
1
1
0
> d.svd[[2]][,1:2] %*% diag(d.svd[[1]][1:2]) %*% t(d.svd[[3]][,1:2])
[,1]
[,2]
[,3]
[,4]
[,5]
[,6]
[,7]
[1,] 0.8327142 0.87075536 1.2819192 0.258569439 0.3538872 1.12392852 0.9036710
[2,] 1.1568480 0.92786465 1.0082634 0.665723465 0.2585694 0.06248386 -0.1700712
[3,] -0.1699857 0.03122636 0.3112280 -0.280056074 0.1005788 0.88202181 0.8725302
[4,] 0.3948208 0.52230162 0.9078465 0.003571743 0.2582987 1.11497839 0.9820280
[5,] 0.1137595 0.29134444 0.6477284 -0.152156330 0.1909063 1.07039479 0.9953852
[6,] 0.6006586 0.58576299 0.8086186 0.232555085 0.2202575 0.58555509 0.4377091
> d.svd[[2]][,1:4] %*% diag(d.svd[[1]][1:4]) %*% t(d.svd[[3]][,1:4])
[,1]
[,2]
[,3]
[,4]
[,5]
[,6]
[,7]
[1,] 1.02285340 1.02912701 0.9457880 0.009006517 0.965970538 1.0385090 0.99063266
[2,] 0.92900279 1.06869323 1.1062884 0.840727430 0.009006517 -0.0134736 -0.09274244
[3,] -0.17268628 0.03570139 0.3098034 -0.279034563 0.101727564 0.8796082 0.87498743
[4,] 0.06021168 0.84004232 0.9495523 0.218959286 0.054149957 0.9436014 1.15649897
[5,] 0.05649234 0.14951847 0.8357352 -0.041673681 -0.131215398 1.1468902 0.91750879
[6,] 1.00590863 -0.08575238 1.0223925 0.079268842 0.047876347 0.9477444 0.06898092
> d.svd[[2]][,1:6] %*% diag(d.svd[[1]][1:6]) %*% t(d.svd[[3]][,1:6])
[,1]
[,2]
[,3]
[,4]
[,5]
[,6]
[,7]
[1,] 1.000000e+00 1.000000e+00 1.000000e+00 -2.949030e-16 1.000000e+00 1.000000e+00 1.000000e+00
[2,] 1.000000e+00 1.000000e+00 1.000000e+00 1.000000e+00 -1.491862e-16 -8.222589e-16 -6.002143e-16
[3,] -1.734723e-17 -1.089406e-15 -6.591949e-16 2.151057e-16 -6.245005e-17 1.000000e+00 1.000000e+00
[4,] -3.851086e-16 1.000000e+00 1.000000e+00 -4.857226e-17 -4.857226e-16 1.000000e+00 1.000000e+00
[5,] -3.261280e-16 -8.049117e-16 1.000000e+00 1.665335e-16 -9.714451e-17 1.000000e+00 1.000000e+00
[6,] 1.000000e+00 -9.020562e-16 1.000000e+00 -5.412337e-16 -1.318390e-16 1.000000e+00 -9.228729e-16
蛇足: 固有値と特異値
K
固有値分解： N '   k u k u k
T
SVDの次元とスパース性の対応
k 1
N ': 実対称行列 , k : 固有値 , u k : 固有ベクトル
N ' u k  k u k
K
特異値分解： N    k u k v k
T
k 1
 k : 特異値 , u k : 左特異ベクトル , v k : 右特異ベクトル
u i u Tj   ij , v i v Tj   ij
Nv k   k u k , u Tk N   k v Tk
3
長所短所
• LSI を用いると、共通の単語がなくとも文書間
の関係を示すことができる。ただし、頻繁に共
起する単語（の片方）を持っている場合。
pLSA: 確率的トピックモデル
– 頻繁に共起する単語には、強い共通性がある
• 短所:
– 統計的な意味合いがない
確率的トピックモデル
生成モデル
• LSA/LAI の確率モデル版.
確率的に生成する
• 統計的機械学習の分野から
– (e.g., Hoffman, 2001; Blei, Ng, Jordan, 2003)
文書はトピックからなり、
トピックは単語からなる
• 文書集合からトピックを抽出する
トピック
• このトピックは、解釈（意味づけ）可能である。
この点がLSA/LSI と異なる
– LSA/LSI では、各特異ベクトルの意味付けができな
い
パラメータを推定する
各文書を形作るトピックを推定する
各トピックを形作る単語を推定する
確率的トピックモデル
文書の生成過程
• 各文書は、トピックの上のある確率分布
• 各トピックは、単語上のある確率分布
1.
各文書につき、トピックの、あ
る分布を定める
2.
各トピックにつき、単語の、あ
る分布を定める
トピック
...
トピック
（各文書の各単語位置で）ト
ピックをサンプルし、
単語
...
単語
3.
文書＝トピックの分布
...
4.
そのトピックから単語をサン
プルする
単語の現れる位置
4
モデルの学習
文書の生成例
?
DOCUMENT 1: money1 bank1 bank1 loan1 river2 stream2 bank1
money1 river2 bank1 money1 bank1 loan1 money1 stream2 bank1
money1 bank1 bank1 loan1 river2 stream2 bank1 money1 river2 bank1
money1 bank1 loan1 bank1 money1 stream2
.8
.2
DOCUMENT 1: money? bank? bank? loan? river? stream? bank?
money? river? bank? money? bank? loan? money? stream? bank?
money? bank? bank? loan? river? stream? bank? money? river? bank?
money? bank? loan? bank? money? stream?
TOPIC 1
TOPIC 1
?
DOCUMENT 2: river? stream? bank? stream? bank? money? loan?
river? stream? loan? bank? river? bank? bank? stream? river? loan?
bank? stream? bank? money? loan? river? stream? bank? stream?
bank? money? river? stream? loan? bank? river? bank? money? bank?
stream? river? bank? stream? bank? money?
.3
.7
DOCUMENT 2: river2 stream2 bank2 stream2 bank2 money1 loan1
river2 stream2 loan1 bank2 river2 bank2 bank1 stream2 river2 loan1
bank2 stream2 bank2 money1 loan1 river2 stream2 bank2 stream2
bank2 money1 river2 stream2 loan1 bank2 river2 bank2 money1
bank1 stream2 river2 bank2 stream2 bank2 money1
?
TOPIC 2
TOPIC 2
http://helper.ipam.ucla.edu/publications/cog2005/cog2005_5282.ppt
pLSA
Probabilistic Latent Semantic Analysis

隠れ状態（トピック）を EM 法で発見することができる

次の問題の解決が可能

多義語

同義語



• アスペクトモデル
– 文書は、基盤である（潜在的な） K 個のアスペクト
の混合である
– 個々のアスペクトは単語分布 p(w|z) で表される
Java はコーヒーを意味するがあるコンピュータ言語も意味する
• 学習には Tempered EM を使用
計算機、コンピュータ、PC はほぼ同じ意味
LSI/LSAに比し、統計的意味がある
アスペクトモデル


等価なモデル
Hofmann 1999 の提案
共起するデータに対する潜在変数モデル

個々の観測データ (w,d) にクラス変数 z  Z={z_1,…,z_K} を付随させる
– 確率 P(d) で文書を選ぶ
– 確率 P(z|d) で、潜在クラス z を選ぶ
– 確率 p(w|z) で、単語 w を選ぶ
w
d
z
w
K
P( w | d )   P( w | zk ) P( zk | d )
k 1
P(d , w) 
P(z|d)
d
z
P ( d , w)  P (d ) P ( w | d ), where
• 生成モデル
P(d)
d
P(w|z)
z
w
K
 P( z )P(d | z )P(w | z )
k 1
k
k
k
5
文書クラスタリングとの比較
Tempered EM を用いたモデル学習
• 文書は、クラスタ（アスペクト）一つだけに関連
付けられるものではない
• アスペクトモデルに従い、対数尤度を記述す
ることができる。それを最大化すればよい
– 文書ごと P(z|d) はアスペクトのある混合を定める
– より柔軟性が高く、より有効なモデルができよう
ただ, P(z), P(z|d), P(w|z) を計算しないといけない. あるのは文書(d) と単語(w)のみなのに.
L
  n(d , w) log P(d , w)
dD wW
• EM (Expectation Maximization) 法が使える
– 過学習を避けるため tempered EM を用いる
EM のステップ
• E‐ステップ
– 現在のパラメータ値に従って、対数尤度関数の
期待値（潜在変数に関する期待値）を求める
E ステップ
• 潜在変数 z の分布は、文書 d 中に単語 w が
現れることを z が説明する確率である
– 今回は例によって、その途中で求める、潜在変数
の分布を求める
P( z | d , w) 
• M‐ステップ
P( z) P(d | z) P(w | z)
K
 P( z )P(d | z )P(w | z )
k
k 1
k
k
– 上記「対数尤度関数の期待値」を最大化するよう
パラメータを定める
pLSI 更新式まとめ
M ステップ
• 下記のパラメータは、E ステップで求めた
p(z|d,w) を用いて表現できる
 n(d , w)P( z | d , w)
P(w | z ) 
 n(d , w)P( z | d , w)
 n(d , w)P( z | d , w)
P(d | z) 
 n(d , w)P( z | d , w)
 n(d , w)P( z | d , w)
P( z ) 
 n(d , w)
d
d , w
• pLSI の対数尤度
L
  n(d , w) log P(d , w)
dD wW
- E - Step
P( z | d , w) 
• 尤度関数の局所最大値に収束する

P( z) P(d | z) P(w | z)
P( z) P(d | z) P(w | z)
zZ
- M- Step
P(w | z) 
 n(d , w)P( z | d , w)
 n(d , w)P( z | d , w)
d
d , w
d ,w
d ,w
zZ
• EM アルゴリズム
w
d , w
P(d , w)   P( z) P(d | z) P(w | z)
P(d | z) 


w
n(d , w)P( z | d , w)
d , w
n(d , w) P( z | d , w)
P( z) 

d ,w
n(d , w) P( z | d , w)

d ,w
n(d , w)
6
過学習
• ところが、pLSA ではパラメータ数が多いため、
過学習（学習データはよく説明するが、未知
データ上での性能は悪い）が起こってしまう
• E ステップを少し修正する
• フィットしすぎないようにする
Simulated Annealing
• 焼きなまし（annealing）: 金属を加工するにあたって、
加工硬化による内部のひずみを取り除き、組織を軟
化させ、展延性を向上させるため、一定温度に熱した
のち、ゆっくりと冷却する方法 – 初期状態よりさらに内
部エネルギーが低い状態にもっていく
• 疑似焼きなまし: 最小値解の候補解を繰り返し求める
にあたり、パラメータ β が大きければ大きく動き、小さ
ければ小さく動くようにし、繰り返すに従って、徐々に
β を小さくしていく方法。 β が温度の働きをする。
例: Perplexity の比較
• Perplexity – Log‐averaged inverse probability （対未知データ）
• 確率が高ければ（よく予測できていれば） perplexity は下がる
TEM (Tempered EM)
• 学習量を制御するパラメータ β を導入する
P( z)P(d | z) P(w | z)

z P( z)P(d | z)P(w | z)

P ( z | d , w) 
• β (> 0)は１から開始し、次第に減少していく
β の選び方
• 適切な β はどう選べばよいか?
• β は学習不足と学習過多を分ける
• Validation データセットを用いる簡便な方法は
– 学習データを対象とした学習を β =1 から開始する
– Validation dataset を用いて学習モデルをテストする
– 前回より改善しているなら、同じ β で継続する
– 改善がなければ、 β <‐ β where <1
例: トピック分解
• 1568 文書のアブストラクト
• 128 潜在クラスに分解
• "power" と名付けたいトピック
に属する単語の語幹, i.e.,
p(w|z) が大きい語幹
Power1 – 宇宙関連
Power2 ‐ 電気関連
Figure 6. Perplexity results as a function of the latent space dimensionality for (a) the MED data (rank 1033) and
(b) the LOB data (rank 1674). Plotted results are for LSA (dashed-dotted curve) and PLSA (trained by TEM =
solid curve, trained by early stopping EM = dotted curve). The upper baseline is the unigram model corresponding
to marginal independence. The star at the right end of the PLSA denotes the perplexity of the largest trained aspect
models (K = 2048).
(Hofmann 2001)
Thomas Hofmann. Probabilistic Latent Semantic Analysis. In Proceedings
of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI'99)
7
例: 多義語
• 二つの異なる文脈（一文書一文脈）に出現す
る “segment” を検出している
Latent Dirichlet Allocation
Thomas Hofmann. Probabilistic Latent Semantic Analysis. In Proceedings
of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI'99)
pLSI の欠点
• pLSI においては, 観測可能変数 d はある学習
データで用いる索引番号である。従って、未
知文書を扱う自然な方法がない.
• pLSI のパラメータ数は、学習データ中の文書
数に比例する. 過学習する（そこで、T‐EM を
用いている）
• トピック混合にもベイズ的にできないか.
Unigramの混合
Zi
wi1
w2i
w3i
w4i
Unigrams 混合モデル (単に Naïve Bayes)
M 個の文書それぞれにつき,
 トピック z （一個）を選ぶ.
 N 単語を選ぶ。各単語を独立に、z を条件とするある多項分布から生成さ
れる.
この Unigrams 混合モデルでは, 一文書に一トピック
ところで： pLSI モデルは
d
zd1
wd1
zd2
wd2
zd3
wd3
確率潜在意味解析 (pLSI)
モデル
zd4
wd4
学習データの文書 d 中の各単語に
つき,
 文書（のインデックス） d を条件と
するある多項分布に従い、トピッ
ク z を選ぶ.
 トピック z を条件とするある多項
分布に従い、単語を生成する.
pLSI では, 一文書が複数個のトピッ
クをもってもよいことになる.
Dirichlet 分布
p( |  ) 

 i 1 i
k

k
i 1


 
k
  1  i 1 i 1
i 1 i
i
k
i
i
• 有用な性質:
– この分布は (k‐1)‐単体の上で定義される. すなわち, k 個の非負の引
数を持ち、その総和は1であるという制約がある. 従って、これはタコ
分布に対して用いるのに極めて自然な分布である.
– 事実, Dirichlet 分布は多項分布の双対分布である (これは、用いる尤
度が、 Dirichlet 分布を事前分布とする多項分布であれば、事後分布
もDirichlet 分布となることを意味する)
– Dirichlet 分布のパラメータ i は、i 番目のクラスの「事前」発現回数と
考えることができる.
8
Dirichlet 分布
多項分布
多項分布では、各試行の結果は固定したある有限個（k個）の値をとり、それぞれの値
であり、例えば、n 回の独立した試行を行った時、確率変数は n
をとる確率は
回の試行で i という数が出る回数を示す。この時
,…,
は n と p をパ
ラメータとする多項分布に従うという。.

公平な賽
i
1
2
3
4
5

i
2
3
4
5
1
2
6
z ~ Multinomia l6 ( )
i  1
 0.2 
 
1
   0.5 
 0.3 
 
i
6
不公平な賽
1
k 次元単体上の各点は、一つの多項分布に対応する:
1
0
i
1
1
1
1
2
3
1
2
3
i
1
 
i  1
  0
0
 
3
i
多項分布の一個のサンプルは一個の整数である
e.g. 5, 2, 3, 2, 6 …
Thanks to Nigel Crook
Thanks to Nigel Crook
Dirichlet 分布
Dirichlet 分布
各 Dirichlet 分布は、当該単体中の、多項分布
ある。
2
0
1 1
0
1
  (1  k )  i  0
i  {1 k}
1
Dirichlet 分布からのサンプルは次のように書かれる:
1
1
1
1
1
3
Dirichlet 分布は、集中度パラメータと呼ぶ、k-単体上で定義される
,…,
をパラメータとする
2
2
11
1
上の分布で
3
 ~ Dirichlet k ( )
1
ただし  は k 個の結果の上の多項分布である.
3
Thanks to Nigel Crook
Thanks to Nigel Crook
Dirichlet 分布
グラフィカルモデル
Bayesian Network の表現方法
3-単体上の Dirichlet 分布からのサンプル:
2
0
3
2
1
0
3
2
A
Dirichlet(5,5,5)

1
p(A,B) = p(B|A)p(A)
B
Dirichlet(0.2, 5, 0.2)
1
Plate記法
Dirichlet(0.5,0.5,0.5)
A
A

1
3
B1
Bi
Thanks to Nigel Crook
B2

Bn
n
9

パラメータ: Θ = (, ) = (1
潜在変数: z = (z1 … zn)
観測変数: x = (x1 … xn)
z
zi
z
k
k
n
z 1
i 1
(Blei, Ng, & Jordan, 2001; 2003)
… k,
1 … k )

n
文書毎のトピック上の分布
Dirichlet 事前分布
p ( ,  , z , x)  p( ) p( z ) p ( xi |  zi ) p( zi |  i )
xi
i
Latent Dirichlet Allocation
ベイズ混合モデル


 (d)  Dirichlet()
 (d)

トピック毎の単語の分布
 ~Dirichletk(, …, )
要素 z (z  (1 … k)) は基底分布 G0 からのサンプル
z ~ G0
(例. Dirichletv( , …, ))
各データ点（文書）に対し、一要素 z をサンプルする:
zi ~ Multinomial()
そしてデータ点をある分布 F() からサンプルする
xi ~ F(zi )
(例. Multinomial(z ))
単語毎のトピック割当て
 (j)  Dirichlet()
zi  Discrete( (d) )
zi
 (j)
割当てられたトピックから生
成された単語
K
wi
i
wi  Discrete( (zi) )
Nd M
2003の論文で、smoothed LDAとして導入

LDA モデル（２種類）

z
i

j
i
i
z ではなく、を用いて
z
記述することが多い
z
K
wi,j
zi,j
N
i

i
M
j
smoothed LDA
z
zi,j
wi,j
N
wi,j
M
LDA
• 各文書につき   Dirichlet()
• 各トピックにつき   Dirichlet()
• 全N 単語 wn のそれぞれにつき:
– トピック zn ~ Multinomial()
– 単語 wn ~ p(wn|zn,), ただし、
p は多項分布, i.e., ~
.
• 各文書につき,   Dirichlet()
• N 単語 wn のそれぞれにつき:
– トピック zn ~ Multinomial()
– 単語 wn ~ p(wn|zn,), ただし、
p は多項分布, i.e., ~
.
i
j
N
M
z
K
z1
z2
z3
z4
z5
z6
z7
z8
z9
z10
z11
z12
w1
w2
w3
w4
w5
w6
w7
w8
w9
w10
w11
w12



d
• 生成 wn ~ Mult(  | zn)
M
 p(w ,..., w
1
d 1
w
M
N
M
 
d 1
d
M

 
d 1
d
Nd
• 生成 zn ~ Mult(  | d)
トピック分布
• 生成 wn ~ Mult(  | zn)
z
|,  )
 Nd 

p ( d |  )   p ( z n  k |  d ) p ( wn |  k ) d d
k

1
n



 Nd 


p ( d |  )    dk  kwn d d

 n 1  k
.
• For 文書内位置 n = 1,, Nd

d
• 生成 zn ~ Mult(  | d)
z
~
• 文書（トピック分布）選択 d ~ Mult()
• 生成 d ~ Dir(  | )
• For （文書中）位置 n = 1,, Nd

pLSA モデル（比較のために）
• For 文書 d = 1,,M


• 各文書につき   Dirichlet()

• 各トピックにつき   Dirichlet()
• 全N 単語 wn のそれぞれにつき:
– トピック zn ~ Multinomial()
– 単語 wn ~ p(wn|zn,), ただし、p は多項分布, i.e., LDA モデル（繰り返しですが）


z
zi,j
K
LDA モデル（plateを展開して）

M
 p(w ,..., w
d 1
w
N
M

1
Nd
,d |, )
M
 Nd 

  p (d )   p ( z n  k | d ,  d ) p( wn |  k ) 
k
d 1
n

1



M
 Nd 

   d     dk  kwn 
k
d 1
n

1



10
pLSA の特徴
LDAの特徴
• Latent Dirichlet Allocation
• Probabilistic Latent Semantic Analysis – PLSA の問題を解決
– (Tempered) EM を用いた学習
– 完全な生成モデルとはいえない
• （生成モデルとして）任意のランダム文書が生成できる
• 新規文書に対応できる
• 学習用の文書集合上の分布  がある: 新規の文書に
適用できない
– パラメータ学習:
• 変分 EM （Variational EM）
– それにも関わらず, 混合モデルより現実的
• Gibbs サンプリング
• 例えば、各文書中に複数のトピックがあってよい
– 統計的なシミュレーション
– 解にバイアスはない
– 統計的な収束
導出ポイントだけ
Gibbsサンプリング
N
p ,  , z, w |  ,    p |   p |   p z n |   pwn | z n ,  
• Gibbs サンプリング
– 結合分布の評価は難しいが、条件付き確率なら容易な時
– マルコフ連鎖を生成するようなサンプルの列を作る
– この連鎖の定常分布が、求める結合分布になる
1.
2.
•
サンプルする:
~
|
•
サンプルする:
~
|
,
~
サンプルする:
|
  p ;  pz
j
j

 i 1 i
M
 
j 1
M

j 1
t 1
,…,
,
K
i 1 ( i )
K
j



K
i 1
j ,i
θ
,…,
,…,
N
j 1
j 1
K
i 1
K
i
M
i

i 1
 i )
K
i
j , ( )
 i )
i 1
j 1 t 1

d j  
i
j , ( )
N
 r 1  r
K
i 1
  ( n
( )   (n
K

 i 1 n ij ,(  )
i 1
 i 1 i
|
i 1
K
V

r 1 ( r )
V
i


t 1


j

i 1
K
(n
i
j ,( )
  )
i
(n ij ,()   i )
i 1
K

i 1
 i 1 n ij ,(  )
j ,i
d j  1
 p ;   pw
K
M
i 1

N
i

j ,t
|  z j ,t dφ


j 1 t 1
r 1
 r 1 n(i  ),r
i ,r
t 1
V
r 1
V
r 1

i 1
i

 i 1 i
d i
 r )

i
M
i 1
K
 (n
  (n
i 1
dx  1
i
m ,()
i
m ,()
V

r
r 1
i 1
i 1
r 1
r
r
r 1
i
j ,()
i
i
j , ( )
i
r 1
V
r 1
i
(), r
 r )
i
(), r
 r )

K
V
i 1
K
i 1
K
j 1, j  m
i
V
V
V
i 1
i
K
M
i
 V (  ) 
r 
 r 1
K
i 1
j 1 t 1
K
i
i
j ,(  )
i 1
K

i
j ,( )
i 1
K
i
i 1
i 1
i
(), r
K
K
K
j 1
 r )
i
K
i 1
N
  (n   )     (n

 ( )  (n   )  ( )  (n
     
 ( n   )



  
(

)

 (n   ) 



    

(n   )


i
(), r
  
 x
 ( )
K
M
i
i 1
K
  ( n
(  )  (n
r
K
 p ( z ( m , n )  k , z  ( m , n ) , w;  ,  )
r 1
V
V
N
j
M
V
 r 1  r
 
φ
K
K

p ( z ( m , n )  k | z  ( m , n ) , w;  ,  )
: i-th トピック中の（辞書中） r-th 単語が j-th 文書に現れた回数
,

N
t 1
   p  j ;   p z j ,t |  j d j   pi ;   p w j ,t |  z j ,t di
K
j ,t
j 1
   p j ;   pz j ,t |  j dθ 
|  j d j   pi ;   p w j ,t |  z j ,t di
N
j 1
~
サンプルする:
M
i 1
θ φ
,…,
M
•
M
   pφ, θ, z , w;  ,  dφdθ
,…,
,
M
•
K
pz, w;  ,  
の初期化
0to
1
:
for n 1
pφ, θ, z , w;  ,     pi ;   p  j ;   pz j ,t |  j  p w j ,t |  z j ,t
i
( ), r
r
i 1 r 1, r  v
 i )
(n(i),v   v )
K

  )   
i 1
i
K
K
i 1
i 1
  (nmi ,()   i )

V
r 1
(n(i),r   r )
(n(i),v   v )
 r 1 (n(i),r   r )
V


11
Collapsed Gibbs サンプリング
p ( z ( m , n )  k | z  ( m , n ) , w;  ,  )
K
  ( n
i
m ,( )
i 1
K
  i )

 r 1 (n(i),r   r )
i 1
K
(n(i),v   v )
V
K
  ( nmi , ,(()m ,n )   i )
i 1
i 1
k ,  ( m,n )
m ,()
 (n
k )
 (nmk ,,(()m,n )   k )

• Dirichlet 分布と多項分布の双対性を用い, 連続値パラメー
タを積分消去する
( n(i,),v( m ,n )   v )

 r 1 (n
V
i ,  ( m,n )
(),r
 r )


r 1
k ,  ( m,n )
( ), r
(n
k ,  ( m ,n )
( ),v
n

K

k 1
 r )
k
( nk( d )   )
w
 (nw( k )   )
 ( )T
d 1
P ( w | z )   P ( w | z ,  ) p (  ) d  
n(k),, v( m,n )   v
V
M

 P(z | ) p()d
P(z ) 
(  )W
 (T )
( nk( d )   )
k
(W )
( nw( k )   )
w
P( w | z ) P (z )
P(z | w ) 
 P (w | z ) P( z )
 v
r 1 (n(k),, r( m,n)   r )
V
は文書 d 中のトピック k の出現回数
は単語wのトピック k としての出現回数
は文書数
は異なり単語数
はトピック数
z
 P (w | z ) P (z )
• zの更新式をこれから求める

Collapsed Gibbs サンプリング
• 各 zi を、次の z-i で条件づけた分布でサンプルする
P ( zi | w , z i ) 
nz(id i )  
nw( zi i )  
n( di )  K n( zi )  W
 (nz(idi )   )


z2
z3
z4
z1
z2
z3
z4
z1
z2
z3
z4
w1
w2
w3
w4
w1
w2
w3
w4
w1
w2
w3
w4
nw( zi i )  
は文書 d 中のトピック k の出現回数
• 容易に実行可能:
は文書数
は異なり単語数
はトピック数
z
z
z
z
w
w
w
w
– メモリ: 数え上げは、2個の疎行列で行える
– 最適化: 特殊な関数はいらない, 単純な算術
– z と w が与えられれば  と  の分布は求めることができる
ˆj( w) 
n (jd )  
(d )

n
 K
nw( j )  
n( j )  W
は文書 d 中のトピック j
の出現回数
は単語wのトピック j とし
ての出現回数
は異なり単語数
はトピック数
ˆ j ,k 
ˆ k ,i 
n kj,()  
n (j,)()  K
, : i-th トピック中の（辞
書中） r-th 単語が j-th 文
書に現れた回数
nw( zi i )  
nz(idi )  
n( zi )  W n( di )  T
i
z
w
N
M

iteration
1


n(k),i  
n(k),()  W
P ( zi | w , z  i ) 
LDA における Gibbs サンプリング
パラメータ推定
ˆ (j d ) 


n( zi )  W
は単語wのトピック k としての出現回数
は文書中の i-th 単語が属する文書のID
は文書中の i-th 単語の単語ID
は文書中の i-th 単語のトピックID

z1

1
2
3
4
5
6
7
8
9
10
11
12
.
.
.
50
wi
MATHEMATICS
KNOWLEDGE
RESEARCH
WORK
MATHEMATICS
RESEARCH
WORK
SCIENTIFIC
MATHEMATICS
WORK
SCIENTIFIC
KNOWLEDGE
.
.
.
JOY
di
1
1
1
1
1
1
1
1
1
1
2
2
.
.
.
5
zi
2
2
1
2
1
2
2
1
2
1
1
1
.
.
.
2
12
LDA における Gibbs サンプリング
LDA における Gibbs サンプリング
iteration
1
2
i
1
2
3
4
5
6
7
8
9
10
11
12
.
.
.
50
wi
MATHEMATICS
KNOWLEDGE
RESEARCH
WORK
MATHEMATICS
RESEARCH
WORK
SCIENTIFIC
MATHEMATICS
WORK
SCIENTIFIC
KNOWLEDGE
.
.
.
JOY
di
1
1
1
1
1
1
1
1
1
1
2
2
.
.
.
5
zi
2
2
1
2
1
2
2
1
2
1
1
1
.
.
.
2
iteration
1
2
zi
i
?
1
2
3
4
5
6
7
8
9
10
11
12
.
.
.
50
wi
MATHEMATICS
KNOWLEDGE
RESEARCH
WORK
MATHEMATICS
RESEARCH
WORK
SCIENTIFIC
MATHEMATICS
WORK
SCIENTIFIC
KNOWLEDGE
.
.
.
JOY
di
zi
2
2
1
2
1
2
2
1
2
1
1
1
.
.
.
2
1
1
1
1
1
1
1
1
1
1
2
2
.
.
.
5
zi
?
P ( zi  j | w , z i ) 
Kunpeng Zhang の資料より
LDA における Gibbs サンプリング
i
wi
MATHEMATICS
KNOWLEDGE
RESEARCH
WORK
MATHEMATICS
RESEARCH
WORK
SCIENTIFIC
MATHEMATICS
WORK
SCIENTIFIC
KNOWLEDGE
.
.
.
JOY
di
1
1
1
1
1
1
1
1
1
1
2
2
.
.
.
5
zi
2
2
1
2
1
2
2
1
2
1
1
1
.
.
.
2
( di )
i , 
n
n( wi ,i j)  
 K n(i), j  W
結果の例
• pLSA等の比較
iteration
1
2
1
2
3
4
5
6
7
8
9
10
11
12
.
.
.
50
n( di ,i j)  
…
1000
zi
zi
2
1
1
2
2
2
2
1
2
2
1
2
.
.
.
1
2
2
2
1
2
2
2
1
2
2
2
2
.
.
.
1
…
P ( zi  j | w , z i ) 
Kunpeng Zhang の資料より
n( di ,i j)  
( di )
i , 
n
Unigram
小さい方がよい
LDA
n( wi ,i j)  
 K n
( )
i , j
 W
結果の例
• 過学習をしないという意味において、LDAの方がすぐれているとい
う実験結果が多い。
76 / 57
Blei et al. 2003
パラメータ数による比較
手法
パラメータ数
効率的な解法
LSA
(KV+KN)
SVD (Lanczos法)
PLSA
KV+KN
EM
Nが入っているので
overfitしやすい
LDA
KV+K
変分ベイズ
問題のNを消した
(KV+KN)
Gibbs sampler
事前分布による正
則化
K: topicの数
V: 語彙数
N: 文書数
http://chasen.org/~daiti-m/paper/topic2006.pdf
http://www.r.dl.itc.u-tokyo.ac.jp/study_ml/pukiwiki/index.php?openfile=PLSV.pptx&plugin=attach&refer=schedule%2F2008-11-06
13
参考: 他のモデル
参考: NBのplate表現
• Multinomial Naïve Bayes

• For
• 生成 Cd ~ Mult(  | )
C
C
• For 文書位置 n = 1,, Nd
C
• 生成 wn ~ Mult(  |,Cd)
W1
W2
W3


文書 d = 1,, M
…..
W1
WN
W2
W3
WN
M
M
M
 p( w ,..., w

…..
Nd
1
d 1
, Cd |  ,  )
Nd
Nd
M


 M 
   p (Cd |  )  p ( wn |  , Cd )     Cd   Cd ,wn 
d 1 
n 1
n 1

 d 1 
W
N

M

他のモデル: 混合モデル
• 混合モデル: 教師なし naïve Bayes モデル
• 単語とクラスの結合確率分布:

M
 p(w ,..., w
1
d 1
C
Z
Nd
Nd
M


, z d |  ,  )    zd   zd , wn 
d 1 
n 1

• しかし、クラスは見えない:
M
 p(w ,..., w
W
N
M
d 1
1
Nd
Nd
M  K

 
|  ,  )      k   k , wn 

1
k

1
d 1 
n




14

Download Report