この記事は古川研究室 [Advent_calendar][link-0] 10日目の記事です。
[link-0]:https://qiita.com/advent-calendar/2019/flab
本記事は古川研究室の学生が学習の一環として書いたものです。内容が曖昧であったり表現が多少異なったりする場合があります。
はじめに
文書をクラスタリングする有名な手法として非負値行列因子分解(NMF)や確率的潜在意味解析(pLSA)があります.
２つの手法は実は等価であるらしいので参考論文を読んでメモ書き程度に自分なりにまとめてみました.
詳しくは参考資料をみてください.
与えられるデータについて
各文書を単語の出現頻度で表現するBag of Wordsの形で文書を表現します.
$F_{ij}$は$\sum_{i}^{I} \sum_{j}^{J} F_{ij}=1$を満たし、単語$w_i$が文書$d_j$での出現する確率を$p(w_i,d_j)$を表しています.
- $M$: 単語数
- $N$: 文書数
- データ行列: $F=(F_{ij}) \in \mathbb{R}^{M \times N}$
非負値行列因子分解(NMF)
データ行列$F$が与えられた時にNMFは$F$を以下のように分解します.
$K$個のクラスタに分ける場合、$C: M\times K$行列、$H: N\times K$行列となります.
F=CH^{T}
NMFはデータとの誤差をユークリッド距離で測るのか、一般化KLダイバージェンスで測るのかとか色々あります.
一般化KLダイバージェンス基準のNMFの目的関数$J_{\mathrm{NMF}}$は以下のようになります.
J_{\mathrm{NMF}}=\sum_{i=1}^{m} \sum_{j=1}^{n} F_{i j} \log \frac{F_{i j}}{\left(C H^{\mathrm{T}}\right)_{i j}}-F_{i j}+\left(C H^{\mathrm{T}}\right)_{i j}
NMFで解くタスクとしては$J_{\mathrm{NMF}}$を最小化するような行列$\hat{C}$と$\hat{H}$を推定することです.
確率的潜在意味解析(pLSA)
pLSAでは尤度を表す目的関数$J_{\mathrm{PLSI}}$最大にするようなパラメータを推定します.
J_{\mathrm{PLSA}}=\sum_{i=1}^{m} -\sum_{j=1}^{n} F_{i j} \log P\left(w_{i}, d_{j}\right)
$P\left(w_{i}, d_{j}\right)$を以下のようにモデル化します.
\begin{aligned} P\left(w_{i}, d_{j}\right) &=\sum_{k} p\left(w_{i}, d_{j} | z_{k}\right) p\left(z_{k}\right) \\ &=\sum_{k} p\left(w_{i} | z_{k}\right) p\left(d_{j} | z_{k}\right) p\left(z_{k}\right) \end{aligned}
ただし
\sum_{i=1}^{m} p\left(w_{i} | z_{k}\right)=1, \quad \sum_{j=1}^{n} p\left(d_{j} | z_{k}\right)=1, \quad \sum_{k=1}^{K} p\left(z_{k}\right)=1
を満たします.
pLSAで解くタスクとしては$J_{\mathrm{pLSA}}$を最大化するような$p\left(w_{i} | z_{k}\right)$,$p\left(z_{k}\right)$,$p\left(d_{j} | z_{k}\right)$を推定することです.
示したいこと
一般化KLダイバージェンス基準のNMFとpLSIは等価であるというのを以下の2つを示すことで示します.
- $J_{\mathrm{NMF}}$最小化と$J_{\mathrm{pLSA}}$最大化は等価
- $P(d, w)$=$(CH^{T})_{ij}$となること
1.を示してみる
PLSAの目的関数は
J_{\mathrm{PLSA}}=-\sum_{i=1}^{m} \sum_{j=1}^{n} F_{i j} \log P\left(w_{i}, d_{j}\right)
でした.ここで$J_{\mathrm{PLSA}}$に$\sum_{i=1}^{m} \sum_{j=1}^{n} F_{i j} \log F_{i j}$を足したものを$J^{\prime}_{\mathrm{PLSI}}$とします.
\begin{align}
J^{\prime}_{\mathrm{PLSI}} &= \sum_{i=1}^{m} \sum_{j=1}^{n} F_{i j} \log F_{i j}-\sum_{i=1}^{m} \sum_{j=1}^{n} F_{i j} \log P\left(w_{i}, d_{j}\right)\\
&=\sum_{i=1}^{m} \sum_{j=1}^{n} F_{i j} \log \frac{F_{i j}}{P\left(w_{i}, d_{j}\right)}
\end{align}
定数を加えただけなので、$J_{\mathrm{PLSI}}$を最大化することと$J^{\prime}_{\mathrm{PLSI}}$を最小化することは等価です.
次に、次のように変形します.
\begin{align}
J^{\prime}_{\mathrm{PLSI}} &=\sum_{i=1}^{m} \sum_{j=1}^{n} F_{i j} \log \frac{F_{i j}}{P\left(w_{i}, d_{j}\right)}-1+1\\
&= \sum_{i=1}^{m} \sum_{j=1}^{n} F_{i j} \log \frac{F_{i j}}{P\left(w_{i}, d_{j}\right)}-\sum_{i^{\prime}=1}^{m} \sum_{j^{\prime}=1}^{n} F_{i j}+\sum_{i^{\prime \prime}=1}^{m} \sum_{j^{\prime \prime}=1}^{n} P\left(w_{i}, d_{j}\right)\\
&= \sum_{i=1}^{m} \sum_{j=1}^{n} F_{i j} \log \frac{F_{i j}}{P\left(w_{i}, d_{j}\right)}- F_{i j}+ P\left(w_{i}, d_{j}\right)
\end{align}
NMFの目的関数と比較してみると$P\left(w_{i}, d_{j}\right)=\left(C H^{\mathrm{T}}\right)_{i j}$となれば示せそうですね.
2.を示す
では、次に$P\left(w_{i}, d_{j}\right)=\left(C H^{\mathrm{T}}\right)_{i j}$となることを示します.
まず、次のような$\tilde{C}$,$\tilde{H}$,$D_{C}$,$D_{H}$を定義します.
$\tilde{C}$,$\tilde{H}$は$C$,$H$を列方向に総和が1になるように正規化した行列で、$D_{C}$,$D_{H}$は対角行列で対角成分以外は0です.
\tilde{C}=\left[\boldsymbol{\tilde{c}}_{1}, \ldots, \boldsymbol{\tilde{c}}_{K}\right] \in \mathbb{R}^{M \times K}\\
\tilde{H}=\left[\boldsymbol{\tilde{h}}_{1}, \ldots, \boldsymbol{\tilde{h}}_{K}\right] \in \mathbb{R}^{N \times K}\\
D_{C}=(\sum_{i=1}^{M} c_{ik}) \in \mathbb{R}^{K \times K}\\
D_{H}=(\sum_{j=1}^{N} h_{jk}) \in \mathbb{R}^{K \times K}\\
\tilde{c}_{ik}=\frac{c_{ik}}{\sum_{i=1}^{M} c_{ik}} 、\tilde{h}_{jk}=\frac{h_{jk}}{\sum_{j=1}^{N} h_{jk}}
とします.$\tilde{C}$,$\tilde{H}$,$D_{C}$,$D_{H}$を使って以下のように書くことができます.
(CH^{T})_{ij}=(CD_{C}^{-1}D_{C}D_{H}(HD_{H}^{-1})^{T})_{ij}\\
\tilde{C}=CD_{C}^{-1},\tilde{H}=CD_{H}^{-1},S=D_{C}D_{H}とすると
(CH^{T})_{ij}=(\tilde{C}S\tilde{H}^{T})_{ij}\\
となる.
\sum_{i=1}^{M} \tilde{c}_{ik}=1, \quad \sum_{k=1}^{K} s_{kk}=1,\sum_{j=1}^{N} \tilde{h}_{jk}=1
を満たします.
\mathbf{U}=\left(P\left(w_{i} | z_{k}\right)\right)_{i, k}、\mathbf{\Sigma}=\operatorname{diag}\left(P\left(z_{k}\right)\right)_{k}
、\mathbf{V}=\left(P\left(d_{j} | z_{k}\right)\right)_{j, k}
とすると
\tilde{C}=U,S=\mathbf{\Sigma},\tilde{H}=\mathbf{V}
\tilde{c}_{ik} = p\left(w_{i} | z_{k}\right)、s_{kk}=p(z_{k}),\tilde{h}_{jk} = p\left(d_{j} | z_{k}\right)
となる.
##さいごに
2つの手法の関係性を示すのはとても面白いなと思いました.
自分もこんなかっこいいことを示してみたいです.
参考資料
- [On the equivalence between Non-negative Matrix Factorization and
Probabilistic Latent Semantic Indexing][link-1]
[link-1]:https://www.sciencedirect.com/science/article/pii/S0167947308000145 - [Relation between PLSA and NMF and implications
][link-2]
[link-2]: https://dl.acm.org/citation.cfm?id=1076148 - 亀岡 弘和 "非負値行列因子分解とその音響信号処理への応用"