渋谷駅前で働くデータサイエンティストのブログ

元祖「六本木で働くデータサイエンティスト」です / 道玄坂→銀座→東京→六本木→渋谷駅前

"Online Chinese Restaurant Process" (Liu et al., KDD 2014) メモランダム

先週のうちのチームの論文輪読会でこの論文を読んだので、その時用いた資料を一部改訂して上げておきます。いつも通り炎上ラーニング大歓迎*1なので、おかしなところがあったらどんどん突っ込んで下さると有難いです。


Online chinese restaurant process - ACM Digital Library


何とビデオレクチャーということで、去年のNYCでのKDDの本番トークそのものがまんま収録されて公開されてるんですね~。ということで論文読みながら*2このトークを改めて聴くのも良いかも。

0 全体要約


読んで字の如し、混合ディリクレ過程(Dirichlet Process Mixture)をオンライン化しようという論文。大規模データであればあるほどクラスタリングする際にクラスタ数が事前に分かっているケースは少ないのでDPMが大事になってくるが、当然のように大規模になるほどバッチで回すのは難しくなってくる。そこで、核となる中華レストラン過程自体をオンライン化してしまい、クラスタ数の「増加」に対応できるようにしようというのがこの論文の主旨。


1 INTRODUCTION


めんどいので大半割愛。要するにクラスタ数不明の状況でどうやってクラスタリングするかという話のコンセプトとしてノンパラベイズがあり、その実現として最初に中華レストラン過程(Chinese restaurant process)とその実装としての混合ディリクレ過程があり、という話題から始まり、でも大規模データだとバッチでは回り切らないのでオンラインで逐次処理しながら中華レストラン過程回せれば嬉しいよねという話をしている。


2 ONLINE CHINESE RESTAURANT PROCESS


要は混合分布モデルですよね、という書き出しから始まる。


2.1 Notation


ここで中華レストラン過程(CRP)の復習。CRPは「客・テーブル・料理」のメタファーで表されるが、客 \mathbf{x}_iが個々のデータポイントに対応し、テーブルがCRPではクラスタ(online CRPではクラス)に対応する。テーブルjにおける料理はクラスjのパラメータ\theta_jとして表され、テーブルjに座る客の人数をm_jとする。客\mathbf{x}_iがテーブルjで供される料理\theta_jに示す「好み」(preference: 嗜好性とでも何とでも呼んで良いと思うが)はH(\mathbf{x}_i, \theta_j)で表され、これは\mathbf{x}_iがクラスjに属する尤度を意味する。


CRPとは異なり、online CRPでは個々の客が一度席を割り当てられた後もテーブルを移動して良いとする。この時客\mathbf{x}_iが割り当てられたテーブルをz_i、最終的に座ったテーブルをy_iとする。


Online CRPはノンパラであり、テーブルの数は無限大まで拡張し得る。この論文では利用されたテーブルの数をkとする。基本分布とその濃度パラメータはG_0\alphaである。さらにrelaxing functionとしてg (\gamma_1, \gamma_2, e_j, f_j)をonline CRPにおける事前分布を補正する関数として定める。\gamma_1, \gamma_2はregret rates、f_j, e_jはテーブルjにおける過去のi-1客の割り当て失敗を追跡するのに用いられる。最後に、\mathbf{x}_{-i}は客i以外の全ての客を表し、\mathbf{x}_{-i,c}は客i, c以外の全ての客を表す(多分PythonやRの記法と同じ)。y_{-i}, z_{-i}についても同様。


2.2 Chinese Restaurant Process


CRPについておさらい。CRPとは離散時間確率過程であり、データ分割(partition)間をまたいで単一の分布(=ディリクレ分布)を定義する。これはクラスタ構造の事前分布を形成する(クラスタ構造は多項分布に従う)。メタファーとしては上述の通り、無限に客が座れるテーブルが無限にある中華レストランを仮定し、n人の客がやってきてテーブルに座るということを考えるもの。i番目の客は既に先客のあるテーブルか、誰もまだ座っていない新しいテーブルに座ることになる。その確率を以下のように置く。


 P(z_i = j | z_{-i}, \alpha) \propto \begin{cases} \frac{m_j}{i-1+\alpha} ~ if ~ j \leq k \\ \frac{\alpha}{i-1+\alpha} ~ if ~ j = k+1 \end{cases} (1)


CRPはpartition間で単一の可換な分布を誘導する。このためデータ点が各クラスタに割り振られる順番に対して結合分布は不変である。ここで個々の客のテーブル割り当てz_i\mathbf{x}_iが最後にそのテーブルに座る客であると仮定することによって得られる。(1)式にあるように、i番目の客はある先客のあるテーブルjに先客の人数m_jに比例する確率で座るか、新しいテーブルに\alphaに比例する確率で座る。m_jは大きくなればなるほどさらに大きくなりやすい。よって、CRPは「富める者はさらに富む」現象に従ってクラスタリングすることになる。もちろん、式の都合上客が増えれば増えるほどテーブルの数も増えることになる。


ディリクレ過程(DP)混合モデルの事後期待値の正確な計算は、観測値が少ない場合には実行不能である。これは例えばMCMCなどで計算可能だが、その収束性の診断は難しい。変分推論(variational inference)が代替手段として提案されている。この場合は決定論的に尤度と事後分布の近似値を求めることになる。
CRPはその柔軟性ゆえ様々な発展形が提案されているが、ここでは割愛。

2.3 Relaxing Function


Online CRPもオリジナルのCRPから拡張したメタファーに従う。まず、最初にやってきた客はCRP同様に最初のテーブルに座る。ところが、online CRPではウェイターが個々の料理全てを追跡し、さらにウェイターが持つ料理と客の好みに関する事前情報(分布)に基づいて客をより適切なテーブルに割り当てようとする。ところが客はその料理が気に入らず、勝手に別にテーブルに移ってしまう。もちろんこれではレストランは大混乱になるので、割り当てミスの確率を減らすためにウェイターは客の移動を追跡し、さらにその次の客がテーブルにつく確率を調整し、テーブルと料理の間の情報(?)を割り当てミスが減るように調整する。


i番目の客へのテーブル割り当ては2通りに分かれる。1つはウェイターによって提案されたテーブル割り当てz_iであり、もう1つは実際に客が最終的に座ったテーブルy_i。テーブルjと客iについて、f_j, e_jは過去のi-1人の客の割り当てミスを追跡する。これを表したのが(2)式で、\mathbb{I}は指示関数(indicator function)である。


 f_j = \displaystyle \sum^{i-1}_{a=1} \mathbb{I} \{ y_a = j \land z_a \neq j \}
 e_j = \displaystyle \sum^{i-1}_{a=1} \mathbb{I} \{ z_a = j \land y_a \neq j \} (2)
 g(\gamma_1, \gamma_2, e_j, f_j) = (1 + \gamma_1)^{f_j} (1 - \gamma_2)^{e_j} (3)


テーブルjについて、f_j > 0はテーブルjへの割り当ては増えるべきであるということを示しており、客はテーブルjへと移動する傾向を持つ。逆にe_j > 0であれば客はテーブルjから離れやすくなる。Regret theory*3に触発されて、この研究ではrelaxing functionを設けている。式(3)における\gamma_1, \gamma_2はregret rateであり、f_j , e_jによってもたらされる割り当てミスに関する情報はテーブル割り当て事後分布を決定する上での事前知識とみなされる。


 P(z_i = j | z_{-i}, \mathbf{x}_i, y_i, \theta, G_0,  \alpha) \propto
 \begin{cases} g(\gamma_1, \gamma_2, e_j, f_j) \frac{m_j}{i-1+\alpha} H(\mathbf{x}_i, \theta_j) ~ if ~ j \leq k \\ \frac{\alpha}{i-1+\alpha} \int H(\mathbf{x}_i, \theta_j) d G_0(\theta_j) ~ if ~ j = k+1 \end{cases} (4)


(4)式はonline CRPにおける事後分布推定を表す。H (\mathbf{x}_i, \theta_j)はデータ点\mathbf{x}_iがクラスjに属する尤度を示す。なお全てのjに対してf_j = 0, e_j = 0の時online CRPCRPと一致する。


オリジナルのCRPとonline CRPとはメタファーではよく似通っているが、いくつか大きく異なる点がある。まずCRPは純然たる教師なし学習であり、クラスタリングに用いられる。一方でonline CRPはオンライン学習であり、ラベルy_iは毎回\mathbf{x}_iに対する予測が行われた後でないと得られない。次に、online CRPの事前分布はCRPのそれとは異なる。最後に、データ点\mathbf{x}_iがクラスを移動すると、同時にz_i, y_iでインデックスされたクラスのパラメータも変化するため、複雑になる。



2.4 Inference and Learning


ここからは実際のモデル推定のプロセスについて。


f:id:TJO:20150417170922p:plain


Figure 1はonline CRPのグラフィカルモデルを示している。サンプリングプロセスは以下の通り。


 z_i | \alpha \sim Mult(Online CRP(\alpha))
 \theta_{z_i} | G_0 \sim G_0
 \mathbf{x}_i | \theta, z_i \sim F(\theta_{z_i}) (5)


式(5)においてz_iはクラス指示変数であり、データ点\mathbf{x}_iの予測クラスを表す。個々のデータ点\mathbf{x}_iに対して予測クラスのラベルz_iはonline CRPからサンプリングされる。クラスパラメータ\theta_{z_i}は基底分布G_0からサンプリングされ、各データ点\mathbf{x}_iはパラメータ\theta_{z_i}に関連する分布Fからサンプリングされる。今回提案しているアルゴリズムオンラインアルゴリズムであるため、正しいラベル情報y_iは予測が完了してから与えられる。このモデルはz_i, y_iをクラスパラメータ更新のために用いる。


その他の(例えば)パーセプトロンなどのオンラインアルゴリズムとは異なり、online CRPは誤判定に基づく更新は行わない。その代わり予測が正しかろうが正しくなかろうが常にパラメータの更新は行われる。


もし予測が正しくない、即ちz_i \neq y_iである場合、データ点\mathbf{x}_iがクラスz_iに属する尤度は過大評価されていることになる。これを補正するために、擬似データ点\mathbf{x'}_i = -\mathbf{b} \times \mathbf{x}_iがクラスz_iに属すると想定する。ただしb > 0は定数で擬似データ点の重みを与える。その際、モデルは\mathbf{x'}_i, \mathbf{x}_{-i,z_i}, \alpha, G_0及びテーブルz_iに関連する全ての擬似データ点のもとでの\theta_{z_i}の条件付き事後確率に基づいて新しいクラスパラメータ\theta_{z_i}をサンプリングする。


逆にデータ点\mathbf{x}_iがクラスy_iに属する尤度が過小評価されている場合、擬似データ点\mathbf{x''}_i = \mathbf{b} \times \mathbf{x}_iがクラスy_iに属すると想定する。その際、モデルは\mathbf{x''}_i, \mathbf{x}_{-i,y_i}, \alpha, G_0及びテーブルy_iに関連する全ての擬似データ点のもとでの\theta_{y_i}の条件付き事後確率に基づいて新しいクラスパラメータ\theta_{y_i}をサンプリングする。


予測が正しい(z_i = y_i)場合は前者と同様の方法でサンプリングする。


Figure 1に示されたグラフィカルモデルにおいて、ランダム変数z, \thetaは潜在変数であることを示している。この場合、事後分布推定のためにGibbs samplingを使うことになる。基本的にGibbs samplingは(他のMCMC同様に)1つの変数を固定しつつもう1つの変数を得るという方法を繰り返す。これにより条件付き事後確率が得られるという仕組みである。\theta_jのサンプリング方法は既に上に述べた通り。z_iのサンプリングは以下の式に従う。


 P(z_i = j | z_{-i}, y_{-i}, \mathbf{x}_i, \theta_j, \alpha, G_0) \propto P(z_i = j | z_{-i}, y_{-i}, \alpha)P(\mathbf{x}_i|\theta_j) (6)


この研究では(6)式はそのまま(4)式と等価になる。よって以下のような擬似コードのもとでonline CRPは動く。


f:id:TJO:20150417171001p:plain


2.5 Collapsed Sampling


一般に、周辺化を行うことで分散の低下が期待できる。そこで\theta_jに関して解析的に統合し、アルゴリズムから\theta_jを消去することでサンプリングプロセスを簡潔にする。そこで各データ点\mathbf{x}_iに対して式(7)からz_iのみをサンプリングする。この式においてF(\theta_j)_{-i}\mathbf{x}_{-i,j}、テーブルjにおける擬似データ点とG_0のもとでの条件付き事後確率\theta_jである。


 P(z_i = j | z_{-i}, \mathbf{x}_i, y_i, \theta, G_0,  \alpha) \propto
 \begin{cases} g(\gamma_1, \gamma_2, e_j, f_j) \frac{m_j}{i-1+\alpha} \int H(\mathbf{x}_i, \theta_j) d F(\theta_j)_{-i} ~ if ~ j \leq k \\ \frac{\alpha}{i-1+\alpha} \int H(\mathbf{x}_i, \theta_j) d G_0(\theta_j) ~ if ~ j = k+1 \end{cases} (7)


f:id:TJO:20150417171018p:plain


以下の実験ではこのアルゴリズム2を用いた。


(ちなみにGibbs samplingまわりの詳細は例えば佐藤一誠さんの『トピックモデルによる統計的潜在意味解析 (自然言語処理シリーズ)』あたりを読むと分かりやすいと思う。LDAに絡めてディリクレ過程周りを調べるのも良さそう)


3 EXPERIMENTS, 4 DISCUSSION AND ANALYSIS, 5 CONCLUSION


面倒なので実験結果の表だけ張っておく。


f:id:TJO:20150417171223p:plain
f:id:TJO:20150417171232p:plain
f:id:TJO:20150417171239p:plain
f:id:TJO:20150417171248p:plain


(パラメータチューニング次第という気がしないでもないが、名だたるオンライン学習アルゴリズムほど速くはないがそれらよりは精度が良く、名だたるバッチ学習アルゴリズムほど精度は良くないが圧倒的に速い、という巧みなラインを突いているように見える)


ということで。ちなみにチームの輪読会で出た感想としては「理論的背景の割に擬似コードめちゃくちゃ簡単なのですぐ実装できそう」というものでした。確かに、サンプリングのところだけ工夫が要りますが後はジョークのようにシンプルだし。。。なんて言ってると「お前が実装しろ」とマサカリが飛んできそうで、お後がよろしいようで。以下参考文献。


トピックモデルによる統計的潜在意味解析 (自然言語処理シリーズ)

トピックモデルによる統計的潜在意味解析 (自然言語処理シリーズ)

オンライン機械学習 (機械学習プロフェッショナルシリーズ)

オンライン機械学習 (機械学習プロフェッショナルシリーズ)


トピックモデル本はGibbs samplingのところとか併せて読むと参考になると思います。オンライン学習本はそもそも論としてのストリームに対する学習方法についての理解を深めるというのと、さらにリグレット解析のところが参考になるかなと。

*1:ってか間違ってても自分だと全然分からない分野なので

*2:ただし今調べたらarXivには上がってない模様。。。

*3:僕は浅学にして知らなかったのですが、リグレット解析はオンライン学習文脈ではよく使われるんだそうで