2013年1月11日金曜日

LDAについて


トピックモデル(今回はLDA: 潜在的ディリクレ配分法)について、今後自分で実装したり研究に生かしたりしたいと思ったので、
すごく簡単な例で考えてみました。(肝心なD(ディリクレ分布)についてはスルーしている・・・汗)
何か間違いとか指摘とかあれば教えて頂けると嬉しいです。

トピック
同じ文書内で使われる確率が高いような、似た意味を持つ単語の集まり。
例えば政治のトピックなら、「選挙」「国会」「内閣」が出やすい。
トピックモデルでは、文書のトピック(文書で、どのトピックがどのくらい出やすいか)と、
トピックの単語(トピックで、どの単語がどのくらい出やすいか)を求める。
参考URL: http://sucrose.hatenablog.com/entry/20120322/p1

以下、具体例を用いて具体的に流れを追ってみる。
参考URL: http://blog.echen.me/2011/08/22/introduction-to-latent-dirichlet-allocation/

・最初に観測されるのは、この文書群だけ。
(1) I like to eat broccoli and bananas.
(2) I ate a banana and spinach smoothie for breakfast.
(3) Chinchillas and kittens are cute.
(4) My sister adopted a kitten yesterday.
(5) Look at this cute hamster munching on a piece of broccoli.

自然言語処理(例:aとかtheとか意味なさそうなの(stop words)は除く。全て原形にしてカウント。)の後、文書群はこんな感じに。
(1) like eat broccoli banana.
(2) eat banana spinach smoothie breakfast.
(3) chinchilla kitten cute.
(4) sister adopt kitten yesterday.
(5) look cute hamster munch piece broccoli.

・トピックの数K=2にする、と事前に決める。topic1とtopic2。

・(参考)処理後の文書群に含まれる単語(とその頻度)。
これが、topic1やtopic2を単語の多項分布で表現する時の次元になる。
like
eat              2
broccoli     2
banana     2
spinach
smoothie
breakfast
chinchilla
kitten          2
cute          2
sister
adopt
yesterday
look
hamster
munch
piece

・各文書内の各単語に、トピックのうちの1つをランダムにassignする。(今回は手で適当に決めました)
(1) like(topic2) eat(topic1) broccoli(topic1) bananas(topic2).(4単語)
(2) eat(topic1) banana(topic2) spinach(topic1) smoothie(topic2) breakfast(topic1).(5単語)
(3) chinchilla(topic1) kitten(topic2) cute(topic2).(3単語)
(4) sister(topic2) adopt(topic1) kitten(topic2) yesterday(topic1).(4単語)
(5) look(topic1) cute(topic2) hamster(topic1) munch(topic1) piece(topic2) broccoli(topic1).(6単語)

【文書をトピック(の多項分布)で表現する】(初期値)
          topic1               topic2
(1)     2/4= 50%          2/4= 50%
(2)     3/5= 60%          2/5= 40%
(3)     1/3= 33.3%       2/3= 66.7%
(4)     2/4= 50%          2/4= 50%
(5)     4/6= 66.7%       2/6= 33.3%

【トピックを単語(の多項分布)で表現する】(初期値)
               like               eat               broccoli          ...          piece
topic1     0%               2/12= 16.7%  2/12= 16.7%                 0%                (topic1の出現回数、12回)
topic2     1/10= 10%      0%               0%                             1/10= 10%     (topic2の出現回数、10回)

・初期値を改善するため...
for each document d:
     for each word w:
          (ex) 2回目のループは、d=(1)、w = "eat" (topic1).

          for each topic t:
               * 対象の単語w以外へのトピックの割り当ては全て正しいという仮定の下、それら(対象の単語w以外の全ての単語)を用いて以下を計算する(Gibbsサンプリング)。
               (a) compute p(topic t | doc d) (文書dの中で、現在トピックtに割り当てられている単語の割合。)
               (b) compute p(word w | topic t) (全文書中で、トピックtに割り当てられた単語のうち、それがwである割合。)
               (c) (a)*(b)の値を計算。(文書からトピックが選ばれる確率)*(トピックから単語が選ばれる確率)
          wに、(c)の値が最大だったトピックtを(新たに)割り当てる。

          (ex) w = "eat" (topic1)の場合。
          (a)
          [topic1] p(topic1 | doc (1)) = 1/3
          [topic2] p(topic2 | doc (1)) = 2/3
          (b)
          [topic1] p(word "eat" | topic1) = 1/11(文書(2)のeatがカウントされる。)
          [topic2] p(word "eat" | topic2) = 0/10
          (c)
          [topic1] (1/3)*(1/11) = 1/33
          [topic2] (2/3)*(0/10) = 0
          topic1 の方が大きいので、wはtopic1 に割り当てる。(この場合は割り当てが変わらない。)

・これを繰り返すと、安定な状態に収束する。

みたい。

・「(b)の分子がゼロになってしまう。」という問題が。
全体的に単語の出現回数が低い例だったので、eatという単語も文書群中で2回しか現れなかったし、
1回しか現れない単語等は、自分自身を除けば他にどこにも現れないので、分子がゼロになる問題が生じる。
補正項入れるんだったかな。
(a)や(b)の計算には、実際にはディリクレ分布を使うはずなので、ひとまずここでアップロードして、
また勉強して分かったら記事書きたいと思います。