「21世紀の相関」HSICの原論文"Measuring Statistical Dependence with Hilbert-Schmidt Norms" (Gretton et al., Algorithmic Learning Theory, 2005)メモランダム

相変わらずうちのチームでは論文輪読会をやってまして、先日僕が担当したのが「21世紀の相関の本命」HSIC (Hilbert-Schmidt Independence Criteria)の原論文たるこいつ↓でした。

Measuring Statistical Dependence with Hilbert-Schmidt Norms (Gretton et al., Algorithmic Learning Theory, 2005)

HSICと言えば@motivic_氏の手による一昨年夏のTokyoRでの発表が一番ナイスな解説だと思います。

21世紀の手法対決 (MIC vs HSIC)

追記

HSIC関連だと鈴木先生のこれもお勧め(昔紹介したかも Bayes Independence Test - HSIC と性能を比較する- http://t.co/IMWUpB5qEu
— motivic (@motivic_) 2015, 1月 15

だそうです。

ということではっきり言ってそっちを読んだ方が早いです＆ここで公開するのは前回同様メモ形式の資料どころか逐次訳みたいな駄文ということで。。。"Understanding Dropout"論文の時と同様に本文を読みながら併せて参照するメモとしてご利用ください。

概要

問題意識として「非線形な関係の相関を見る」のは難しいというものがある。例えば、 $y=x^2$ という放物線を考えた時に $x$ と $y$ の関係性を、普通にピアソンの積率相関係数で計算すると（当たり前だが）途方もなく低い値になる。だがそもそもの式を考えれば、 $x$ と $y$ との間には非常に密接な関係があるはずで、これを検出出来たら（それこそモデルとなる式やらその次数やらも考える必要すらなくて）素晴らしい話ではある。

それを実現するために、この論文ではデータを再生核ヒルベルト空間(RKHSs)に飛ばし、そこでの関係性を見ることで非線形でも関係性を見出す（≒独立性の検定を行う）という手法を提案している。なお、author listを見れば分かるようにSmolaも名前を連ねている。

1 Introduction

これまでの取り組みのおさらい。非線形相関の取り組みは色々あったが、ここではi)Renyiの独立性検定に属するものと、ii)カーネル法に基づくものを主にfeatureしている。そのii)の親玉としてここでは自らが提案するHSICを推しており、その理由として以下のように述べている。

empirical estimateは単純で良い：グラム行列の積のtraceで済む。しかも追加で正則化などする必要もない

サンプルサイズmに対して $\frac{1}{\sqrt{m}}$ の学習係数という収束の速さ

有限サンプルバイアスは $O(m^{-1})$ と低い

そしてICAよりも「独立性」の検出という点では優れている

とりあえず詳細はこの後の2～3章で見ていきましょうということで。

2 Cross-Covariance Operators

ここからHSICの肝となる、RKHSs同士のcross-covarianceを与える作用素の話。以下参考資料など。

ヒルベルト空間（そもそも論として）

ヒルベルト＝シュミット作用素

正定値カーネルなどなど

フロベニウスノルム、ヒルベルト＝シュミットノルム

2.1 RKHS Theory

まずはカーネル法のおさらい（例えばSVMでのカーネル化を思い出そう*1）。

ここでは $\cal{X}$ から $\mathbb{R}$ への関数から成るヒルベルト空間 $\cal{F}$ を考える。定義としては各々の $x \in \cal{X}$ に対して、Dirac evaluation operator（←これ何だか分からない：ディラックのデルタ関数？） $\delta_x : \cal{X} \rightarrow \mathbb{R}$ が $f \in \cal{F}$ から $f(x) \in \mathbb{R}$ への写像となる場合に、 $\cal{F}$ は有界関数的(bounded linear functional)であると呼ばれる。

$x \in \cal{X}$ の個々の要素に対して、 $k : \cal{X} \times \cal{X} \rightarrow \mathbb{R}$ が一意な正定値カーネルである時、 $\langle \phi(x), \phi(x') \rangle_{\cal{F}} = k(x,x')$ なる要素 $\phi(x) \in \cal{F}$ に対応する。

なお、今後の議論のため特に $\cal{F}$ は可分(separable)であることを要件とする（完全な正規直交系を持っていなければならない）。

文献[12]の定理7で指摘されているように、可分な $\cal{X}$ におけるいかなる連続なカーネルも可分なRKHSを導く。

ここでは $\cal{F}$ とは異なる別のRKHSとして可分空間 $\cal{Y}$ へのRKHS $\cal{G}$ （カーネル $l(\cdot,\cdot)$ 、特徴写像 $\psi$ から成る）を仮定する。

その次は具体的なHilbert-Schmidt (HS)各指標の定義。

(1)式がHSノルムの定義で、内積の二乗和で表される。 $C : \cal{F} \rightarrow \cal{G}$ を線形作用素として、 $\|C\|^2_{HS} := \displaystyle \sum_{i,j} \langle C v_i, u_i \rangle^2_{\cal{F}}$ ただし $v_i, u_i$ は $\cal{F, G}$ の正規直交基底。

その下の式がHS作用素。HSノルムが存在する場合、 $C : \cal{F} \rightarrow \cal{G}$ はHS作用素と呼ばれる。HS作用素の集合 $HS(\cal{G}, \cal{F}) : \cal{G} \rightarrow \cal{F}$ は可分なヒルベルト空間で、以下の内積を伴う。 $\langle C, D \rangle_{HS} := \displaystyle \sum_{i,j} \langle C v_i, u_i \rangle_{\cal{F}} \langle D v_i, u_i \rangle_{\cal{F}}$

(2)式はHSテンソル積。 $f \in \cal{F}$ および $g \in \cal{G}$ とすると、テンソル積作用素 $f \otimes g : \cal{G} \rightarrow \cal{F}$ は全ての $h \in \cal{G}$ に対して $(f \otimes g)h := f\langle g, h \rangle_{\cal{G}}$

(3)式は(2)式をさらにHSノルムで書き換えたもの。 $\| f \otimes g \|^2_{HS} = \langle f \otimes g, f \otimes g \rangle_{HS} = \langle f, (f \otimes g) g \rangle_{\cal{F}}$
$= \langle f, f \rangle_{\cal{F}} \langle g, g \rangle_{\cal{G}} = \| f \|^2_{\cal{F}} \| g \|^2_{\cal{G}}$

2.2 The Cross-Covariance Operator

平均の定義。

ここで $(\cal{X}, \Gamma)$ と $(\cal{Y}, \Lambda)$ をそれぞれ確率測度 $p_x, p_y$ によって与えられる集合とする（ $\Gamma)$ は $\cal{X}$ 上の、 $\Lambda$ は $\cal{Y}$ 上のボレル集合）。それぞれの平均を定義すると、以下の(4)式のようになる。

$\langle \mu_x, f \rangle_{\cal{F}} := \mathbf{E}_x [ \langle \phi(x), f \rangle_{\cal{F}} ] = \mathbf{E}_x [ f(x) ],$
$\langle \mu_y, f \rangle_{\cal{G}} := \mathbf{E}_y [ \langle \psi(y), g \rangle_{\cal{G}} ] = \mathbf{E}_y [ g(y) ]$ (4)

ただし $\phi$ は $\cal{X}$ からRKHS $\cal{F}$ への、 $\psi$ は $\cal{Y}$ からRKHS $\cal{G}$ への写像である。以上を2回適用すれば、

$\| \mu_x \|^2_{\cal{F}} = \mathbf{E}_{x, x'} [ \langle \phi(x), \phi(x') \rangle_{\cal{F}} ] = \mathbf{E}_{x, x'} [ k(x, x') ]$ (5)

この後の説明で平均の存在条件がRKHSが有界かつカーネルが有界の場合云々ということを言っている。

相互共分散の定義。

$C_{xy} := \mathbf{E}_{x,y}[ (\phi(x) - \mu_x) \otimes ( \psi(y) - \mu_y ) ] = \mathbf{E}_{x,y} [ \phi(x) \otimes \psi(y) ] - \mu_x \otimes \mu_y$ (6)
(6)式右辺の第1項を $\tilde{C}_{xy}$ 、第2項を $M_{xy}$ とする。

2.3 Hilbert-Schmidt Independence Criterion

ここで可分なRKHSs $\cal{F}, \cal{G}$ および $( \cal{X} \times \cal{Y} , \Gamma \times \Lambda )$ に対する結合確率測度 $p_{xy}$ のもとで、associated cross-covariance operator $C_{xy}$ の平方HSノルムとしてHSICを以下のように定義する。

$HSIC ( p_{xy}, \cal{F}, \cal{G} ) := \| C_{xy} \|^2_{HS}$ (7)

ただしこれを計算するにはカーネル関数で表現する必要がある。これは以下の補題で示される。

Lemma 1 (HSIC in terms of kernels)

$HSIC (p_{xy}, \cal{F}, \cal{G} ) = \mathbf{E}_{x, x', y, y'} [ k(x, x') l(y, y') ]$
$+ \mathbf{E}_{x, x'} [ k(x,x') ] \mathbf{E}_{y, y'} [ l(y, y') ] - 2\mathbf{E}_{x, y} [ \mathbf{E}_{x'} [ k(x, x') ] \mathbf{E}_{y'} [ l(y, y') ] ]$ (8)

詳細はAppendix Aを参照のこと。

3 Empirical Criterion

HSICで独立性検定を実施するにはもう3ステップ必要。ここではその3ステップについて説明する。

まず、 $HSIC (p_{xy}, \cal{F}, \cal{G} )$ を有限なサンプルに対して近似させる必要がある。次に、この近似が正しくHSICに有効に収束することを示す必要がある。最後に、HSICの一致性について示す必要がある。3節では1つ目のステップについて論じ、2・3つ目は4節で論じる（以下の如く省略）。

3.1 Estimator of HSIC

Definition 2 (Empirical HSIC)

$Z := \{ (x_1, y_1), \cdots, (x_m, y_m) \} \subseteq \cal{X} \times \cal{Y}$ が確率測度 $p_{xy}$ から得られる独立の観測サンプルであるとする。この時HSICの推定値、 $HSIC ( Z, \cal{F}, \cal{G})$ は以下のように与えられる。

$HSIC ( Z, \cal{F}, \cal{G}) := (m-1)^{-2} \mathbf{\mathrm{tr}}\mathit{KHLH}$

ただし $H, K, L \in \mathbb{R}^{m \times m}, K_{ij} := k(x_i, x_j), L_{ij} := l(y_i, y_j), H_{ij} := \delta_{ij} - m^{-1}$

$HSIC ( Z, \cal{F}, \cal{G})$ の利点は、計算時間が $O(m^2)$ であるところ（他のカーネル法だと $O(m^3)$ かかる）。

Theorem 1 ([tex: O(m^{-1}) Bias of Estimator)

$\mathbf{E}_z$ を確率測度 $p_{xy}$ から得られた独立なコピー $(x_i, y_i)$ の期待値であるとすると、

$HSIC (p_{xy}, \cal{F}, \cal{G} ) = \mathbf{E}_z [ \mathit{HSIC} ( Z, \cal{F}, \cal{G}) ] + O(m^{-1})$

これは $HSIC ( Z, \cal{F}, \cal{G})$ の分散が $O(m^{-1})$ より大きい場合は、 $HSIC ( Z, \cal{F}, \cal{G})$ の定義より生じるバイアスは無視できるということを意味している。証明はAppendix Aを参照のこと。

4 Large Deviation Bounds

4節は力尽きたので省略。。。*2

5 Independent Tests Using HSIC

ここからいよいよHSICに基づく独立性検定のお話。

Theorem 4 ( $C_{xy})$ and Independence)

$\cal{F}, \cal{G}$ RKHSs（対応するカーネルやドメインは従前通り）を置く。一般性を失うことなく、 $\|f\|_{\infty} \leq 1$ かつ $\|g\|_{\infty} \leq 1$ が全ての $f \in \cal{F}, g \in \cal{G}$ について成り立つと仮定する。この時、 $x$ と $y$ が独立であれば $\|C_{xy}\|_{HS} = 0$ である。
証明：Gretton et al. [11]を読まれたし。

5.1 Independence Tests

これでHSICを独立性検定に用いる準備が整った。

確率分布 $p_{x,y}$ の集合 $\cal{P}$ を考える。一般に*3、 $\cal{P}$ は2つの部分集合に分けられる。 $\cal{P}_i$ は確率分布群 $p^{( i )}_{x,y}$ を含み、 $x, y$ は互いに独立である。一方 $\cal{P}_d$ は確率分布群 $p^{( d )}_{x,y}$ を含み、 $x, y$ は互いに従属関係にある。

次に、検定 $\Delta(Z)$ を導入する。これはデータ集合 $Z \sim p_{Z}$ を取り、 $p_Z$ は $p_{x,y}$ から $m$ 個ランダムに抽出してきた分布に対応する。この時、

$\begin{eqnarray} \Delta(Z) = \left\{ \begin{array} & 1 & if & Z \sim p^{( d )}_Z \\ 0 & if & Z \sim p^{( i )}_Z \end{array} \right. \end{eqnarray}$

を返す。ただし有限な標本しか見ていないため、これだけではどちらの確率分布からデータが抽出されたかを完全に決定することはできない。そこで検定を導入する。 $\Delta$ は $\alpha$ 検定と呼ばれ、

$\displaystyle \sup_{p^{( i )}_{x,y} \in \cal{P}_i} \mathbf{E}_{Z \sim p^{( i )}_Z} [ \Delta(Z) = 1 ] \leq \alpha$

となる。上限 $\alpha$ は第一種の過誤の確率である。第二種の過誤の確率については（ここでは省略されている4節の）Theorem 3の説明を参照のこと。

5.2 Efficient Computation

計算負荷の問題は別に重要である。[3] (http://www.di.ens.fr/~fbach/bach_jordan_csi.pdf)で提案されているように、この論文では不完全コレスキー分解によるグラム行列のlow-rank decompositionを用いている。これはカーネル関数がfast decaying spectrum*4を伴う限りは正確なHSICの近似を与える。これは以下に示すような計算コスト削減につながっている。

Lemma 2 (Efficient approximation to HSIC)

$K \approx AA^{\top}$ かつ $L \approx BB^{\top}$ 、ただし $A \in \mathbb{R}^{m \times d_f}$ , $B \in \mathbb{R}^{m \times d_g}$ とする。この時 $\mathbf{\mathrm{tr}} \mathrm{HKHL}$ は $O(m(d^2_f + d^2_g))$ の時間スケールで近似できる。

6 Experimental Results

完全に力尽きたので*5省略。比較手法はICA (FastICA, RADICAL, CFICA)。評価指標がAmari divergenceだって！

Appendix A, B

論文本文読んでも定理しか載ってないので、導出過程は付録の方をどうぞ。ぶっちゃけ付録の方を読んでる方が個人的には楽しいかも。