基於信息瓶頸的空間聚類(一)

03-31

最近在讀Tishby提出的信息瓶頸理論，本人實現了 Susanne Still的基於信息瓶頸進行空間聚類的演算法，在此想展示一下這一演算法的實現過程。歡迎各位道友提出寶貴意見

信息瓶頸的motivation

讓我們先考慮聚類問題，在空間中給出一堆的data points ${m x_i,y_i}_{i=1}^N$ ，我們想把它們分成若干類 ${1,2,dots,N_c}$ (cluster indices)，每一類對應著一個cluster centroid $m X_c^{(i)}$ 。從資訊理論的角度來看，聚類的過程實質上是把這些data points的信息壓縮成若干個cluster，同時又要儘可能確保聚類的質量僅可能地好。

首先我們來定義「聚類的質量」。為了使我們聚類的效果（準確度）儘可能的好，我們需要儘可能保留這些data points的位置關於cluster indices的信息。我們定義 $m X$ 為data points的location的random variable, $m C$ 為cluster indices的random variable。故我們要儘可能maximize $[ mathcal{I}(m C;m X) ]$ ，這裡 $mathcal{I}$ 表示mutual information。
其次，我們來定義data points的壓縮。聚類其實是把data points的indices一對一映射到cluster indices上。我們定義 $m I$ 為data points的indices的random variable。故我們要儘可能minimize $mathcal{I}(m I;m C)$ 。

如果我們使得 $mathcal{I}(m C;m X)$ 儘可能大，那麼 $mathcal{I}(m I;m C)$ 隨之也會變大，這就會跟我們的目的衝突了。所以我們打算設置 $mathcal{I}(m C;m X)$ 的lower bound為 $D$ ，同時儘可能minimize $mathcal{I}(m I;m C)$ ，即

$qquadqquadqquadqquadqquadqquadqquadmin_{p(c|i): mathcal{I}(m C;m X)ge D}mathcal{I}(m I;m C) qquadqquadqquad(1)$

這裡 $p(c|i)$ 是我們的controller，它代表當data point的index為 $i$ 時，它被歸為第 $c$ 類的概率。為了解決(1)，我們引入參數Lagrange multiplier $eta$ ,這樣我們只需要解決一個unconstrained optimization

$qquadqquadqquadqquadqquadqquadqquadmin_{p(c|i)}mathcal{I}(m I;m C)-eta I(m C;m X) qquadqquadqquad(2)$

迭代演算法求解最優化問題

這裡Tishby給出了求解(2)的迭代演算法：

Input: $p(m I,m X)$ , $eta$ , $m X$ ，容限 $epsilon$ , $m X_c^{(0)}$
Output: $p(m C|m I)$ , $p(m X|m C)$ , $p(m C)$ ,cluster centroids的位置 $m X_c$ .
Initialization: $p^0(m C)$ , $p^0(m X|m C)$ , m=0.
While True:
$p^{m+1}(c|i)leftarrow frac{p^{m}(c)}{Z_t(i,eta)}exp[-eta * D_{KL}(p(m X|i)||p^m(m X|c))]$

$p^{m+1}(m x|c)leftarrowfrac{1}{p^m(c)}sum_{i}p(i)p(m x|i)p^m(c|i)$
$p^{m+1}(c)leftarrow sum_{i}p(i)p^m(c|i)$
$m x_c^{(m+1)} leftarrow sum_{m x}m x p^m(m x|c)$
$mleftarrow m+1$
$mathcal{L}^{m} leftarrow mathcal{I}^m(m I;m C)-etamathcal{I}^m(m C;m X) = D_{ ext{KL}}(p^m(i,c)||p(i)p^m(c)) - D_{ ext{KL}}(p^m(c,x)||p^m(c)p(x))$

If we have $|mathcal{L}^{m+1}-mathcal{L}^m|leepsilon$ ,break.

這裡的關鍵在於如何恰當地選取 $p(m I,m C)$ 和起始點 $p^0(m C)$ 與 $p^0(m X|m C)$ .由直覺地，我們選擇

$p^0(c)=frac{1}{N_c}$ , $cin{1,2,dots,N_c}$
$p^0(m x|c)=frac{1}{Z^0(c,eta)}exp[-d(m x,m x_c^{(0)})]$
$p(i) = frac{1}{N},forall i; qquad p(m x|i) = delta_{m x,m x_i}=left{egin{align}0, m x e m x_i \1, m x=m x_i end{align} ight.$

其中出現的 $Z_0(c,eta)$ 和 $Z_t(i,eta)$ 都是normalization term，它們是為了使得 $sum_{m x}p^{m}(m x|c)=1$ .

我們隨機選取起始的cluster centroid $m x_c^{(0)}$ ,然而如果你直接就這樣實現這個演算法，那麼你的程序將永遠不會收斂，這是因為我們設置的 $p(m I,m X)$ 有問題，這一原因被詳細介紹在（Strouse, 2017）的paper裡面。由直覺地，這樣設置的 $p(m I;m X)$ 將會使兩個不同的data points之間的距離成為泛函：

$qquadqquadqquadqquadqquad d(m x_i,m x_j) := D_{ ext{KL}} (p(m x|i) || p(m x|j)) = left{ egin{align} 0, m x_i=m x_j\ +infty, m x_i e m x_j end{align} ight.$

由直覺性的，這樣做會使得任意兩個不同位置的data points都會被分到不同的cluster裡面。（可以參考論文里的詳細證明）

同時，論文提出了新的設置 $p(m I;m X)$ 的方法：

$p(i) = frac{1}{N},forall i; qquad p(m x|i)=frac{1}{Z(s,m x)}expleft[-frac{1}{2s^2}||m x-m x_i||_2^2 ight]$

其中 $s$ 是一個新的參數， $Z(s,m x)$ 是normalization term.

實驗結果

為了驗證這一演算法的有效性，我們隨機選取空間中的2500個data points並試圖使用以上演算法聚類：

我們generate四組呈Gaussian distribution的data points,每一組625個點，它們的分布為： $mathcal{N}left(egin{bmatrix}-1\1end{bmatrix},egin{bmatrix}.3&0 \0&.3end{bmatrix} ight);qquad mathcal{N}left(egin{bmatrix}1\1end{bmatrix},egin{bmatrix}.3&0 \0&.3end{bmatrix} ight);qquad mathcal{N}left(egin{bmatrix}1\-1end{bmatrix},egin{bmatrix}.3&0 \0&.3end{bmatrix} ight);qquad mathcal{N}left(egin{bmatrix}-1\-1end{bmatrix},egin{bmatrix}.3&0 \0&.3end{bmatrix} ight)$
使用以上聚類演算法以後，我們得到了聚類效果圖：

聚類的error probability 為6.1%，貌似效果還不錯，可以在GitHub上查看我的源代碼。

Future Work

接下來我打算探索這一演算法的優缺點和內在原理，以及使用該演算法實現圖像分割的過程

Reference

N. Tishby, F. C. Pereira, and W. Bialek, 「The information bottleneck method,」
arXiv preprint physics/0004057, 2000. [Online]. Available: https://arxiv.org/
pdf/physics/0004057.pdf.
D. Strouse, and D. Schwab, " The information bottleneck and geometric clustering", arXiv:1712.09657. [online]. Available: https://papers.nips.cc/paper/2361-geometric-clustering-using-the-information-bottleneck-method.pdf
S. Still, W. Bialek, and L.Bottou, "Geometric Clustering using the Information Bottleneck method",[online] Available: https://www.princeton.edu/~wbialek/our_papers/still+al_04.pdf