基於確定性信息瓶頸的空間聚類（二）

04-01

在上一篇文章中我們對 Susanne Still的演算法進行了一點小小的改動並成功實現了空間聚類，本篇本章將討論Strouse提出的確定性信息瓶頸並將它運用到空間聚類中。

確定性信息瓶頸的motivation

在上一篇文章中我們使用 $mathcal{I}(m I;m C)$ 來作為a measure of compression (Still, 2003)，Strouse 認為，在某些情況下，採用 $mathcal{H}(m C)$ 作為compression的measure似乎更為合理(Strouse, 2016)。這裡 $mathcal{H}(m C)$ 表示 $m C$ 的entropy，即壓縮以後的對象所包含的信息。因此，原先的cost function

$qquadqquadqquadqquadqquad L_{ ext{IB}}=min_{p(c|i)}mathcal{I}(m I;m C) - eta I(m C;m X)qquadqquad(1)$

就被修改為：

$qquadqquadqquadqquadqquad L_{ ext{DIB}} = min_{p(c|i)}mathcal{H}(m C) - eta I(m C;m X)qquadqquadqquad(2)$

$(1)式-(2) 式$ ，我們發現

$qquadqquadqquadqquadqquadqquad L_{ ext{IB}}-L_{ ext{DIB}}=-mathcal{H}(m C|m I)$

這裡 $mathcal{H}(m C|m I)$ 代表給定 $m I$ 的情況下，壓縮以後的變數 $m C$ 的不確定度。我們用一副圖來描述壓縮的過程：

對於IB(信息瓶頸)來說，它允許了更多的random noise，所以才導致了它包含了 $mathcal{H}(m C|m I)$ ;然而DIB(確定性信息瓶頸)來說，它儘可能地minimize這種不確定度，即 $m Csubset m I$ .

同時，我們可以權衡容忍這種不確定度的程度，形成generalized information bottleneck：

$qquadqquadqquadqquadqquad L_{ ext{GIB}}=min_{p(c|i)}mathcal{I}(m I;m C) -alpha mathcal{H}(m C|m I)- eta I(m C;m X)qquadqquad(3)$

我們將會在將來討論這種方法。

迭代演算法的討論

幸運的是，Strouse給出了求解(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: $d^m(i,c)leftarrow D_{ ext{KL}}[p(m x|i)||p^{m}(m x|c)]$
$l^m(i,c)leftarrow log p^m(c)-eta d^m(i,c)$ $mleftarrow m+1$ $c^m(i)leftarrow argmax_{c}l^{m-1}(i,c)$ $p^m(c|i)=delta(c-c^m(i))$ $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)$ $mathcal{L}^{m} leftarrow mathcal{H}^m(m C)-etamathcal{I}^m(m C;m X) = mathcal{H}^m(m C) - D_{ ext{KL}}(p^m(c,x)||p^m(c)p(x))$
If we have $frac{|mathcal{L}^{m}-mathcal{L}^{m-1}|}{|mathcal{L}^{m-1}|}leepsilon$ ,break.

其中起始點的設置與上一篇paper討論的相同，這裡不再贅述。

這裡比較有趣的是 $p(c|i)$ 的設置結果，它是一個indicator probability:

$qquadqquadqquadqquadqquad p^m(c|i)=left{egin{align} &1, ext{if }c = c^{m}(i)\ &0, ext{otherwise} end{align} ight.$

這是一個hard clustering。比如，如果第 $i$ 個點被歸為第 $c$ 類，那麼 $p(c|m I=i)=1,$ $p(c|m I e i)=0.$ 而在第一篇文章中討論的演算法是一個soft clustering，即 $p(c|m I=i)>>p(c|m I e i)ge0.$

實驗結果

實際上，確定性信息瓶頸與上一篇文章里的演算法運行的效果差不多，但是比上一篇演算法的速度快了一到兩個數量級，可以在GitHub上查看我的源代碼。

總結

實際上IB採用的cost function是源自於資訊理論裡面的channel coding with relevance，可以看作是generalized rate distortion theory (Raymond, 頁183)；而作者聲稱DIB採用的是source coding with relevance，雖然我還沒有太懂，但是可以查看資訊理論的教材深入了解一下(Raymond，頁101)。

Reference

D. Strouse, and D. Schwab, " The information bottleneck and geometric clustering", 2017. arXiv:1712.09657. [online]. Available: https://papers.nips.cc/paper/2361-geometric-clustering-using-the-information-bottleneck-method.pdf
D. Strouse, and D. Schwab, " The deterministic information bottleneck", 2016. arXiv:1604.00268 . [online]. Available: https://arxiv.org/pdf/1604.00268.pdf
Raymond W. Yeung. "Information Theory and Network Coding", Springer, 2008
S. Still, W. Bialek, and L.Bottou, "Geometric Clustering using the Information Bottleneck method", 2003. [online] Available: https://www.princeton.edu/~wbialek/our_papers/still+al_04.pdf