"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 CRPはCRPと一致する。

オリジナルの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

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

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は動く。

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)

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

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

3 EXPERIMENTS, 4 DISCUSSION AND ANALYSIS, 5 CONCLUSION

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

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

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