読者です 読者をやめる 読者になる 読者になる

六本木で働くデータサイエンティストのブログ

元祖「銀座で働くデータサイエンティスト」です / 道玄坂→銀座→東京→六本木

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

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


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

追記


だそうです。


ということではっきり言ってそっちを読んだ方が早いです&ここで公開するのは前回同様メモ形式の資料どころか逐次訳みたいな駄文ということで。。。"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


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


これまで同様、どこか間違っていたら突っ込んでいただけると助かります。。。ということでお後がよろしいようで。

*1:カーネル化は「カーネル関数で個々の要素ごとに集合内の全ての他の要素同士のカーネル内積を計算してその総和を取る」ことで変換値を得る、という流れなわけでした

*2:そもそもVC理論なんかと同じで妥当性の話であって実装にはあまり関係ないところ

*3:というか普通のよくあるデータという意味ではということだと思う

*4:ググった範囲ではこのやり方は割とよく用いられているっぽい

*5:魂の限界まで前処理し続けて今も死にかけている