情報ボトルネック法

情報ボトルネック法は、ナフタリ・ティシュビー、フェルナンド・C・ペレイラ、ウィリアム・ビアレクによって導入された情報理論の手法である。^[1]これは、ランダム変数Xと観測された関連変数Yとの間の結合確率分布p(X,Y)が与えられた場合に、Xを要約（例えばクラスタリング）する際に、精度と複雑さ（圧縮）の間の最適なトレードオフを見つけるために設計されており、「信号処理と学習における様々な問題を議論するための驚くほど豊富なフレームワーク」を提供すると自称されている。^[1]

応用分野としては分布クラスタリングや次元削減が挙げられ、近年では深層学習の理論的基礎として提案されています。パラメトリック統計における最小十分統計量の古典的な概念を、指数分布に限らず任意の分布へと一般化しました。これは、関連変数Yとの相互情報量の一部を捉えるための十分条件を緩和することで実現されます。

情報ボトルネックは、圧縮表現TからYを予測する際の精度を、Xからの直接予測と比較して測定する歪み関数を持つ、レート歪み問題として捉えることもできます。この解釈は、情報ボトルネックのトレードオフを解決し、分布p(X,Y)から情報曲線を計算するための一般的な反復アルゴリズムを提供します。

圧縮表現を確率変数 で与えるとします。このアルゴリズムは、条件付き分布 に関して次の関数を最小化します。 ${\displaystyle T}$ ${\displaystyle p(t|x)}$

${\displaystyle \inf _{p(t|x)}\,\,{\Big (}I(X;T)-\beta I(T;Y){\Big )},}$

ここで、とはそれぞれ、 と の相互情報量、と の相互情報量であり、はラグランジュ乗数です。 ${\displaystyle I(X;T)}$ ${\displaystyle I(T;Y)}$ ${\displaystyle X}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle Y}$ ${\displaystyle \beta }$

深層学習の学習理論

情報ボトルネックの制御は、深層学習における汎化誤差を制御する一つの方法であることが数学的に証明されています。 ^[2]具体的には、汎化誤差は に比例することが証明されています。ここで、 は学習サンプル数、は深層ニューラルネットワークへの入力、は隠れ層の出力です。この汎化境界は、パラメータ数、 VC次元、ラデマッハ複雑度、安定性、または堅牢性 に比例する他の汎化境界とは異なり、情報ボトルネックの程度に比例します。${\displaystyle {\tilde {O}}\left({\sqrt {\frac {I(X,T)+1}{n}}}\right)}$ ${\displaystyle n}$ ${\displaystyle X}$ ${\displaystyle T}$

相転移

深層学習の情報理論

情報ボトルネックの理論は、最近、ディープ ニューラル ネットワーク (DNN) の研究に使用されています。^[3]とをそれぞれ DNN の入力層と出力層として 考え、をネットワークの任意の隠れ層とします。Shwartz-Ziv と Tishby は、相互情報量と のトレードオフを表現する情報ボトルネックを提案しました。この場合、とは、それぞれ隠れ層が入力と出力について保持する情報量を定量化します。彼らは、DNN のトレーニング プロセスは 2 つの別々のフェーズ、つまり 1) が増加する における初期フィッティング フェーズと、2) が減少する における後続の圧縮フェーズで構成されていると推測しました。 ^[4]で Saxe らはShwartz-Ziv と Tishby の主張に反論し、^[3] DNN におけるこの圧縮現象は包括的ではなく、特定の活性化関数に依存すると述べています。シュワルツ＝ジヴとティシュビーはこれらの主張に異議を唱え、サックスらは相互情報量の推定値が弱かったため圧縮を観測していないと主張した。一方、ゴールドフェルドらは最近、観測された圧縮は情報理論的な現象ではなく幾何学的な現象の結果であると主張した^[5]。この見解は^{[6]でも共有されている。}${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle T}$ ${\displaystyle I(X,T)}$ ${\displaystyle I(T,Y)}$ ${\displaystyle I(X,T)}$ ${\displaystyle I(T,Y)}$ ${\displaystyle I(T,Y)}$ ${\displaystyle I(X,T)}$

変分ボトルネック

ガウスボトルネック

ガウスボトルネック^[7]、すなわち情報ボトルネックアプローチをガウス変数に適用することで、正準相関分析に関連する解が導き出される。共分散を持つ多変量ゼロ平均正規ベクトルを共存させ、を圧縮したものであり、相互情報量の所定の値を維持するものとする。最適値は、行列が直交する行を持つ、の要素の線形結合からなる正規ベクトルであることが示される。 ${\displaystyle X,Y\,}$ ${\displaystyle \Sigma _{XX},\,\,\Sigma _{YY}}$ ${\displaystyle T\,}$ ${\displaystyle X\,}$ ${\displaystyle Y\,}$ ${\displaystyle T\,}$ ${\displaystyle X,\,\,T=AX\,}$ ${\displaystyle A\,}$

射影行列は実際には行列の 特異値分解の重み付き左固有ベクトルから選択された行を含む（一般に非対称）${\displaystyle A\,}$ ${\displaystyle M\,}$

${\displaystyle \Omega =\Sigma _{X|Y}\Sigma _{XX}^{-1}=I-\Sigma _{XY}\Sigma _{YY}^{-1}\Sigma _{XY}^{T}\Sigma _{XX}^{-1}.\,}$

特異値分解を定義する

${\displaystyle \Omega =U\Lambda V^{T}{\text{ with }}\Lambda =\operatorname {Diag} {\big (}\lambda _{1}\leq \lambda _{2}\cdots \lambda _{N}{\big )}\,}$

そして臨界値

${\displaystyle \beta _{i}^{C}{\underset {\lambda _{i}<1}{=}}(1-\lambda _{i})^{-1}.\,}$

投影における有効な固有ベクトルの 数、つまり近似の次数は次のように与えられる。${\displaystyle M\,}$

${\displaystyle \beta _{M-1}^{C}<\beta \leq \beta _{M}^{C}}$

そしてついに

${\displaystyle A=[w_{1}U_{1},\dots ,w_{M}U_{M}]^{T}}$

ここで重みは次のように与えられる。

${\displaystyle w_{i}={\sqrt {\left(\beta (1-\lambda _{i})-1\right)/\lambda _{i}r_{i}}}}$

どこ${\displaystyle r_{i}=U_{i}^{T}\Sigma _{XX}U_{i}.\,}$

ガウス情報ボトルネックを時系列（プロセス）に適用すると、最適予測符号化に関連する解が得られます。この手順は、線形スローフィーチャ分析と形式的には同等です。^[8]

線形動的システムにおける最適な時間構造は、いわゆる過去未来情報ボトルネック、つまり非ガウス分布のサンプルデータへのボトルネック法の適用によって明らかになる。^[9]クロイツィヒ、ティシュビーらが扱うこの概念は、2つの独立した段階から成り立つため、複雑性を伴う。第一に、データサンプルが抽出される未知の親確率密度の推定、第二に、ボトルネックの情報理論的枠組みにおけるこれらの密度の利用である。

密度推定

ボトルネック法は統計的ではなく確率論的な観点から構築されているため、サンプル点における基礎的な確率密度を推定する必要がある。これはSilverman ^[10]によって記述された複数の解を持つよく知られた問題である。本手法では、マルコフ遷移行列法を用いて結合サンプル確率を求めており、これはボトルネック法自体と数学的に相乗効果を持つ。 ${\displaystyle X={x_{i}}\,}$

すべてのサンプルペアと距離行列の間の任意に増加する距離計量は です。次に、いくつかのサンプルペア間の遷移確率を計算する必要があります。サンプルを状態と扱い、 の正規化されたバージョンをマルコフ状態遷移確率行列として扱うと、初期状態 を条件とするステップ後の「状態」の確率ベクトルは です。平衡確率ベクトルは、通常どおり、初期ベクトル に依存しない行列の支配的な固有ベクトルによって与えられます。このマルコフ遷移法は、サンプルポイントにおける確率を確立し、これはそこにおける確率の密度に比例すると主張されています。 ${\displaystyle f\,}$ ${\displaystyle d_{i,j}=f{\Big (}{\Big |}x_{i}-x_{j}{\Big |}{\Big )}}$ ${\displaystyle P_{i,j}=\exp(-\lambda d_{i,j})\,}$ ${\displaystyle \lambda >0\,}$ ${\displaystyle P\,}$ ${\displaystyle t\,}$ ${\displaystyle p(0)\,}$ ${\displaystyle p(t)=P^{t}p(0)\,}$ ${\displaystyle p(\infty )\,}$ ${\displaystyle P\,}$ ${\displaystyle p(0)\,}$

距離行列の固有値の使用に関する他の解釈については、シルバーマンの「統計とデータ分析のための密度推定」^[10]で議論されています。${\displaystyle d\,}$

クラスター

以下のソフトクラスタリングの例では、参照ベクトルにサンプルカテゴリが含まれており、結合確率は既知であると仮定しています。ソフトクラスターは、データサンプル全体にわたる確率分布によって定義されます。Tishbyらは、クラスターを決定するための以下の反復方程式を提示しました^{[1]。これは、}レート歪み理論で開発されたBlahut-Arimotoアルゴリズムの一般化です。この種のアルゴリズムをニューラルネットワークに適用する試みは、決定論的アニーリングにおけるギブス分布の適用から生じるエントロピーに関する議論に端を発していると考えられます^{[11] [12] 。}${\displaystyle Y\,}$ ${\displaystyle p(X,Y)\,}$ ${\displaystyle c_{k}\,}$ ${\displaystyle x_{i}:\,\,\,p(c_{k}|x_{i})}$

${\displaystyle {\begin{cases}p(c|x)=Kp(c)\exp {\Big (}-\beta \,D^{KL}{\Big [}p(y|x)\,||\,p(y|c){\Big ]}{\Big )}\\p(y|c)=\textstyle \sum _{x}p(y|x)p(c|x)p(x){\big /}p(c)\\p(c)=\textstyle \sum _{x}p(c|x)p(x)\\\end{cases}}}$

反復の各行の機能は次のように展開される。

1行目:これは条件付き確率の行列値集合である

${\displaystyle A_{i,j}=p(c_{i}|x_{j})=Kp(c_{i})\exp {\Big (}-\beta \,D^{KL}{\Big [}p(y|x_{j})\,||\,p(y|c_{i}){\Big ]}{\Big )}}$

サンプルデータによって生成されたベクトルとその縮小情報プロキシによって生成されたベクトル間のカルバック・ライブラーダイバージェンス は、基本的なボトルネック方程式に従って、圧縮ベクトルの参照（またはカテゴリ）データに対する忠実度を評価するために適用される。分布間のカルバック・ライブラーダイバージェンスは${\displaystyle D^{KL}\,}$ ${\displaystyle Y\,}$ ${\displaystyle x\,}$ ${\displaystyle c\,}$ ${\displaystyle Y\,}$ ${\displaystyle D^{KL}(a||b)\,}$ ${\displaystyle a,b\,}$

${\displaystyle D^{KL}(a||b)=\sum _{i}p(a_{i})\log {\Big (}{\frac {p(a_{i})}{p(b_{i})}}{\Big )}}$

これはスカラー正規化です。距離の負の指数による重み付けは、Kullback-Leibler 距離が大きい場合、1 行目でクラスターの事前確率の重み付けが下げられることを意味し、成功したクラスターの確率は増加し、失敗したクラスターの確率は減少します。 ${\displaystyle K\,}$

2行目: 条件付き確率の2番目の行列値集合。定義により

${\displaystyle {\begin{aligned}p(y_{i}|c_{k})&=\sum _{j}p(y_{i}|x_{j})p(x_{j}|c_{k})\\&=\sum _{j}p(y_{i}|x_{j})p(x_{j},c_{k}){\big /}p(c_{k})\\&=\sum _{j}p(y_{i}|x_{j})p(c_{k}|x_{j})p(x_{j}){\big /}p(c_{k})\\\end{aligned}}}$

ここではベイズ恒等式が使われます。 ${\displaystyle p(a,b)=p(a|b)p(b)=p(b|a)p(a)\,}$

3行目:この行はクラスターの周辺分布を求めます${\displaystyle c\,}$

${\displaystyle {\begin{aligned}p(c_{i})&=\sum _{j}p(c_{i},x_{j})&=\sum _{j}p(c_{i}|x_{j})p(x_{j})\end{aligned}}}$

これは標準的な結果です。

アルゴリズムへの更なる入力は、支配的な固有ベクトルと行列値のカルバック・ライブラーダイバージェンス関数 によって既に決定されている周辺標本分布である。${\displaystyle p(x)\,}$ ${\displaystyle P\,}$

${\displaystyle D_{i,j}^{KL}=D^{KL}{\Big [}p(y|x_{j})\,||\,p(y|c_{i}){\Big ]}{\Big )}}$

サンプル間隔と遷移確率から導出されます。

行列はランダムに初期化することも、妥当な推測値で初期化することもできますが、行列には​​事前値は必要ありません。アルゴリズムは収束しますが、複数の最小値が存在する可能性があり、それらを解決する必要があります。^[13]${\displaystyle p(y_{i}|c_{j})\,}$ ${\displaystyle p(c_{i}|x_{j})\,}$

意思決定の輪郭を定義する

トレーニングセット 外の新しいサンプルを分類するために、前出の距離指標はと 内のすべてのサンプル間の遷移確率を正規化を用いて求めます。次に、3行アルゴリズムの最後の2行を適用して、クラスター確率と条件付きカテゴリ確率を取得します。 ${\displaystyle x'\,}$ ${\displaystyle X\,}$ ${\displaystyle x'\,}$ ${\displaystyle X:\,\,}$ ${\displaystyle {\tilde {p}}(x_{i})=p(x_{i}|x')=\mathrm {K} \exp {\Big (}-\lambda f{\big (}{\Big |}x_{i}-x'{\Big |}{\big )}{\Big )}}$ ${\displaystyle \mathrm {K} \,}$

${\displaystyle {\begin{aligned}&{\tilde {p}}(c_{i})=p(c_{i}|x')=\sum _{j}p(c_{i}|x_{j})p(x_{j}|x')=\sum _{j}p(c_{i}|x_{j}){\tilde {p}}(x_{j})\\&p(y_{i}|c_{j})=\sum _{k}p(y_{i}|x_{k})p(c_{j}|x_{k})p(x_{k}|x')/p(c_{j}|x')=\sum _{k}p(y_{i}|x_{k})p(c_{j}|x_{k}){\tilde {p}}(x_{k})/{\tilde {p}}(c_{j})\\\end{aligned}}}$

ついに

${\displaystyle p(y_{i}|x')=\sum _{j}p(y_{i}|c_{j})p(c_{j}|x'))=\sum _{j}p(y_{i}|c_{j}){\tilde {p}}(c_{j})\,}$

パラメータは、ゼロから増加すると、カテゴリ確率空間内の特徴の数が増加し、特定の重要なしきい値に焦点が合うようになるため、厳重に監視する必要があります。 ${\displaystyle \beta \,}$

例

以下のケースでは、ランダム入力と2つのカテゴリの出力（、 によって生成される）を持つ4象限乗算器におけるクラスタリングを検証します。この関数は、カテゴリごとに空間的に分離された2つのクラスターを持ち、この手法がそのような分布を処理できることを示しています。 ${\displaystyle u,v\,}$ ${\displaystyle \pm 1\,}$ ${\displaystyle y=\operatorname {sign} (uv)\,}$

20個のサンプルが正方形 上に均一に分布して採取されます。カテゴリ数（この場合は2つ）を超えるクラスター数はパフォーマンスにほとんど影響を与えないため、パラメータ を用いた2つのクラスターの結果を示します。 ${\displaystyle [-1,1]^{2}\,}$ ${\displaystyle \lambda =3,\,\beta =2.5}$

距離関数は、条件付き分布が2×20行列で あるのに対し、${\displaystyle d_{i,j}={\Big |}x_{i}-x_{j}{\Big |}^{2}}$ ${\displaystyle x_{i}=(u_{i},v_{i})^{T}\,}$ ${\displaystyle p(y|x)\,}$

${\displaystyle {\begin{aligned}&Pr(y_{i}=1)=1{\text{ if }}\operatorname {sign} (u_{i}v_{i})=1\,\\&Pr(y_{i}=-1)=1{\text{ if }}\operatorname {sign} (u_{i}v_{i})=-1\,\end{aligned}}}$

その他の場所ではゼロになります。

2行目の和は、訓練値+1または-1を表す2つの値のみを組み込んでいますが、それでもうまく機能します。図は20個のサンプルの位置を示しており、'0'はY = 1、'x'はY = -1を表しています。尤度比1の等高線は次のように示されています。

${\displaystyle L={\frac {\Pr(1)}{\Pr(-1)}}=1}$

新しいサンプルが正方形上でスキャンされるにつれて、等高線は との座標と一致するはずですが、サンプル数が少ないため、サンプル点の誤ったクラスタリングに従っています。 ${\displaystyle x'\,}$ ${\displaystyle u=0\,}$ ${\displaystyle v=0\,}$

決定輪郭

ニューラルネットワークとファジー論理の類似点

このアルゴリズムは、単一の隠れ層を持つニューラルネットワークに類似しています。内部ノードはクラスターで表され、ネットワークの重みの第1層と第2層はそれぞれ条件付き確率とです。ただし、標準的なニューラルネットワークとは異なり、このアルゴリズムはサンプル値そのものではなく、入力として完全に確率に依存し、内部値と出力値はすべて条件付き確率密度分布です。非線形関数は、シグモイド関数ではなく、距離計量（または影響関数/ラジアル基底関数）と遷移確率にカプセル化されています。 ${\displaystyle c_{j}\,}$ ${\displaystyle p(c_{j}|x_{i})\,}$ ${\displaystyle p(y_{k}|c_{j})\,}$ ${\displaystyle f(.)\,}$

Blahut-Arimoto の 3 行アルゴリズムは、多くの場合数十回の反復で急速に収束し、、およびクラスターのカーディナリティを変更することで、さまざまなレベルの特徴への焦点を実現できます。 ${\displaystyle \beta \,}$ ${\displaystyle \lambda \,}$ ${\displaystyle f\,}$

統計的ソフト クラスタリング定義は、ファジー ロジックの言語的ファジー メンバーシップ概念と一部重複しています。 ${\displaystyle p(c_{i}|x_{j})\,}$

拡張機能

興味深い拡張として、サイド情報を伴う情報ボトルネックのケースがある。^[14]ここでは、ある目標変数に関する情報が最大化され、別の目標変数に関する情報が最小化され、データの選択された側面に関する情報表現が学習される。

${\displaystyle \min _{p(t|x)}\,\,I(X;T)-\beta ^{+}I(T;Y^{+})+\beta ^{-}I(T;Y^{-})}$

参考文献

• ワイス、Y. (1999)、「固有ベクトルを用いたセグメンテーション：統一的な視点」、IEEE国際コンピュータビジョン会議論文集(PDF)、pp.  975– 982
• P. HarremoësとN. Tishby「情報ボトルネックの再考、あるいは適切な歪み尺度の選び方」。国際情報理論シンポジウム（ISIT）2007の議事録より

参考文献

1. Tishby, Naftali ; Pereira, Fernando C. ; Bialek, William (1999年9月). 情報ボトルネック法(PDF) . 第37回Allerton通信・制御・コンピューティング会議. pp.  368– 377.
2. 川口健司、鄧俊、徐季、黄杰。「情報ボトルネックはディープラーニングにどのように役立つのか？」第40回国際機械学習会議論文集、PMLR 202:16049-16096、2023年。
3. Shwartz-Ziv, Ravid; Tishby, Naftali (2017). 「情報によるディープニューラルネットワークのブラックボックスの解明」arXiv : 1703.00810 [cs.LG].
4. Andrew M, Saxe; et al. (2018). 「深層学習の情報ボトルネック理論について」. ICLR 2018 カンファレンス ブラインドサブミッション. 2019 (12): 124020. Bibcode :2019JSMTE..12.4020S. doi :10.1088/1742-5468/ab3985. S2CID  49584497.
5. Goldfeld, Ziv; et al. (2019). 「ディープニューラルネットワークにおける情報フローの推定」Icml 2019 : 2299–2308 . arXiv : 1810.05728 .
6. Geiger, Bernhard C. (2022). 「ニューラルネットワーク分類器の情報平面解析について—レビュー」. IEEE Transactions on Neural Networks and Learning Systems . 33 (12): 7039– 7051. arXiv : 2003.09671 . Bibcode :2022ITNNL..33.7039G. doi :10.1109/TNNLS.2021.3089037. PMID :  34191733. S2CID  : 214611728.
7. Chechik, Gal; Globerson, Amir; Tishby, Naftali; Weiss, Yair (2005年1月1日). Dayan, Peter (編). 「ガウス変数の情報ボトルネック」(PDF) . Journal of Machine Learning Research (6) (2005年5月1日発行): 165–188 .
8. Creutzig, Felix ; Sprekeler, Henning (2007-12-17). 「予測符号化と遅行性原理：情報理論的アプローチ」. Neural Computation . 20 (4): 1026– 1041. CiteSeerX 10.1.1.169.6917 . doi :10.1162/neco.2008.01-07-455. ISSN  0899-7667. PMID  18085988. S2CID  2138951. 
9. クロイツィヒ, フェリックス; グロバーソン, アミール; ティシュビー, ナフタリ (2009-04-27). 「力学系における過去・未来情報ボトルネック」. Physical Review E. 79 ( 4) 041925. Bibcode :2009PhRvE..79d1925C. doi :10.1103/PhysRevE.79.041925. PMID  19518274.
10. シルバーマン、バーニー(1986).統計とデータ分析のための密度推定. 統計と応用確率に関するモノグラフ. チャップマン＆ホール.書誌コード:1986desd.book.....S. ISBN 978-0-412-24620-3。
11. Slonim, Noam; Tishby, Naftali (2000-01-01). 「情報ボトルネック法による単語クラスタを用いた文書クラスタリング」.第23回国際ACM SIGIR会議「情報検索における研究開発」議事録. SIGIR '00. ニューヨーク、ニューヨーク州、米国: ACM. pp.  208– 215. CiteSeerX 10.1.1.21.3062 . doi :10.1145/345508.345578. ISBN  978-1-58113-226-7. S2CID  1373541。
12. DJ Miller, AV Rao, K. Rose, A. Gersho: 「ニューラルネットワーク分類のための情報理論的学習アルゴリズム」 NIPS 1995: pp. 591–597
13. Tishby, Naftali ; Slonim, N. マルコフ緩和法と情報ボトルネック法によるデータクラスタリング(PDF) . Neural Information Processing Systems (NIPS) 2000. pp.  640– 646.
14. Chechik, Gal; Tishby, Naftali (2002). 「サイド情報を用いた関連構造の抽出」(PDF) . 『ニューラル情報処理システムの進歩』 : 857–864 .