Microsoft PowerPoint - OsakaU_6kernelMean.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - OsakaU_6kernelMean.pptx"

なおかに
6 years ago
Views:

1 カーネル法入門 6. カーネル平均を用いたノンパラメトリック推論福水健次統計数理研究所 / 総合研究大学院大学大阪大学大学院基礎工学研究科集中講義 2014 September 1

2 カーネル法概観 : 復習 x i x j 特徴写像 Φ Φ 元の空間特徴空間 (RKHS) Φ: Ω, Φ, データ点を特徴ベクトルに写像し, データ解析手法を適用する 2

3 カーネル平均による方法 : 概観確率変数特徴写像確率ベクトル Φ 平均 Φ 元の空間 Φ 特徴空間 (RKHS) ランダムな特徴ベクトルΦ の平均 Φ 表現する, だけで 3

4 カーネル平均 X: 可測空間 Ω, に値を取る確率変数分布 P k: 上の可測な正定値カーネル, H: の定めるRKHS Def. の (における) カーネル平均 Φ,, もRKHSの元, すなわち関数. 確率によってとも書くことにする. 例 : ガウスカーネルのとき exp 2 [convolution] 厳密には, Φ, のときに平均が存在 (Bochner 積分 ). 4

5 カーネル平均の性質再生性,. 言い換えると, Φ, Φ 平均操作と内積は交換可能高次モーメントの表現例 ) Taylor 展開, 0, e.g., モーメント母関数の役割を果たす 5

6 特性的な正定値カーネル (Fukumizu et al. JMLR 2004, AoS 2009; Sriperumbudur et al. JMLR2010) 定義. 可測空間 Ω, 上の可測かつ有界な正定値カーネル k が特性的 (characteristic) であるとは { Ω, 上の確率 }, が単射であること, すなわち, ~, ~, であることをいう. 特性的なカーネルによって, カーネル平均は確率を一意に定める 6

7 特性関数の類似. 特性関数はユークリッド空間上のBorel 確率測度を一意に定める. 特性的なカーネルはユークリッド空間に限らない (Fukumizu et al. 2009). カーネルトリックにより推定量の計算が容易. 例 : Gaussian, Laplace カーネルは特性的多項式カーネルは特性的でない ( 次のモーメントまでしか表せない ) 特性的な RKHS は十分広い空間である. 定理 6.1 (Fukumizu et al 2009) 可測空間 Ω, 上の有界で可測な正定値カーネルが特性的であるための必要十分条件は,Ω, の任意の確率に対して ( 和空間 ) がで稠密なことである. ( 証明は福水. 補題 8.6) 7

8 カーネル平均を用いた統計的推論原理 : 特性的なカーネルを用いると, 確率に関する推論問題ベクトルに関する推論問題 2 標本問題? (Gretton et al. JMLR 2012) 独立性検定? ベイズ推論事後確率のカーネル平均表示. 8

9 カーネル平均の推定,, : i.i.d. 標本定義. 標本カーネル平均 1, 一致性定理 6.2., のとき,. 9

10 補題 6.3, (: independent copy of ) 証明 ),,,,,,,,,, 2,, 1,, Chebyshev の不等式により Pr,,. 10

11 共分散作用素, : Ω Ω に値を取る確率変数. (H X, k X ), (H Y, k Y ): Ω,Ω 上のRKHS. 定義. ( 中心化しない ) 共分散作用素 :, : : Φ Φ,, Φ Φ,,,,, X X (X) Y (Y) Y X X C YX Y Y H X H Y ユークリッド空間に値を取る通常の確率ベクトル, の共分散行列の自然な拡張 11

12 再生性,, 共分散作用素は, との関係を表現している共分散作用素 = 積空間でのカーネル平均線形写像とテンソル積は同一視できる ( 次ページ ) Φ Φ 共分散作用素積空間での, のカーネル平均 12

13 テンソル積と線形写像内積空間, のテンソル積は, 線形写像の空間, : は線形写像と同一視される., :, 一般には :, Hilbert 空間の場合は, の Hilbert-Schmidt 作用素全体と, 積空間が同一視される. 13

14 共分散作用素の推定量,,,,, ~, i.i.d. 標本共分散作用素 : 1,,, 1, RKHS 間の作用素, ランクは高々. 一致性を持つ ( カーネル平均とみなせばよい ) 14

15 2 標本問題への応用 15

16 2 標本問題,, ~, i.i.d.,, ~, i.i.d. とは互いに独立 2 標本問題 : P = Q? 例服薬を行ったグループと行っていないグループで, 血糖値に違いがあるか? 中学校 Aと中学校 Bでテストの点数に違いがあるか? 古典的なアプローチ : X, Y の平均値の違いを見る. カーネル法によるアプローチ :? により検定を行う. 16

17 2 標本問題の従来法パラメトリックモデルを用いる ( 正規分布など ) 2 標本 t 検定 1 次元分布, 等分散 1 次元正規分布, 不等分散 (Welch s test) ノンパラメトリック検定 1 次元の場合 : よい方法が知られている Mann-Whitney U-test ( 等分散, 順序統計量に基づく ) Kolmogorov-Smirnov test ( 不等分散でもOK,c.d.f. に基づく ) Wald Wolfowitz run test ( 順序統計量の連に基づく ) 多次元の場合 : Friedman Rafsky (1979) による KS, WW test の多次元拡張. Minimum spanning tree を用いる. 17

18 MMD: maximum mean discrepancy 定義.(Gretton et al NIPS19), : 可測空間 Ω, 上に値を取る確率変数., : Ω 上の特性的な正定値カーネル MMD, サンプルによる推定量 MMD, 名前の由来 sup 平均の差が最大になる値を見る. 18

19 MMD による 2 標本検定ノンパラメトリック検定帰無仮説 H 0 : 対立仮説 H 1 : 検定統計量, 1, 1, 2,,, 19

20 あるいは, 不偏化した U- 統計量, 1 1, 2, 1 1, * 2 標本 U- 統計量カーネル, ;, を持つ2 標本 U- 統計量 1,, ;, : 1,, の要素数の部分集合 : 1,, の要素数の部分集合, ;,,,,,,, とおけばよい [Exercise: これを確かめよ ] 20

21 帰無分布 ( 退化したU- 統計量 ) 漸近分布, 1 ( ) と仮定, ,2,, 0,,... 1,2, : 次の積分作用素の非負固有値 :,,,,,,, 中心化グラム行列による固有値の推定が可能 (Gretton et al NIPS 22) 21

22 Experiments Comparison of two databases. Data size / Dim Neural I: 4000 / 63 Neural II: 1000 / 100 Health: 25 / Subtype: 25 / 2118 Data set Attr. MMD- WW KS B Neural I Same Different Neural II Same Different Gaussian kernels are used. WW: Wald-Walfovitz test KS: Kolmogorov-Smirnov test -- Classical methods (see Appendix) Health Same Different Subtype Same Different Percentage of accepting. Significance level. (Gretton et al. JMLR 2012) 22

23 23

24 24

25 依存性尺度と独立性検定 25

26 定義復習 : 独立性次元確率ベクトルと次元確率ベクトルが独立であるとは, 任意の可測集合, に対し, Pr, Pr Pr が成り立つことをいう. と書く. Fact. 1. ならば. 2., の分布が密度関数, を持つとき, との周辺分布の密度関数をそれぞれ, とすると,, 26

27 復習 : ガウス変数の独立性多変量ガウス確率変数,,, 独立性, : l 次元ガウス確率変数分散共分散行列 l l 命題 If, exp 1 2, 2 exp exp

28 独立性の特徴づけ復習 : Cov, 0 (, 可測関数 ) 依存性尺度? sup,: Cov, すべての可測関数を評価することはできない. 有限サンプルによってどう推定するか? 28

29 HSIC Hilbert-Schmidt Independence Criteria (Gretton et al 2005), : Ω Ω に値を取る任意の確率変数 (Euclid 空間とは限らない ),,, : RKHSと正定値カーネル Σ, ( 中心化した ) 共分散作用素 Σ 定義 HSIC, Σ HSIC, 29

30 共分散の 2 乗和 Σ Cov,, Note: Σ, Cov, HSICはすべての基底関数の組に関して共分散が0か調べている. MMD の特別なケース Σ, 同時分布と, 周辺分布の積を MMD で比較 30

31 積分表示を持ち, 推定が容易 HSIC(, ),, 2,,,,,. [Exercise] 上式を示せ.,: independent copy of, 推定量 HSIC,,,,,,,,,,,,,, 1 Tr : 中心化グラム行列 : Gram 行列, 1 31

32 Hilbert-Schmidt ノルム定義. ヒルベルト空間の間の作用素 : が Hilbert-Schmidt であるとは,, の任意の正規直交基底, に対して,,, であることをいう. このとき, 左辺の値は正規直交基底の取り方に依らず,,, は Hilbert-Schmidt 作用素全体のなすベクトル空間にノルムを定める. 32

33 共分散作用素と独立性定理 Ω,,Ω, : 可測空間, : Ω Ω に値を取る任意の確率変数,,, : Ω,Ω 上のRKHSと正定値カーネル仮定 : 積カーネルは Ω Ω 上特性的 Σ. 系上の定理の仮定の下, HSIC X, Y 0. 33

34 HSIC による独立性検定独立性検定,,, ~,... H0: X と Y は独立 H1: 独立でない検定統計量 Σ 基本は MMD と同じ ( Σ, ) 棄却域の決定漸近的 ( ) な帰無分布を用いる : 2, 0,2,... 並べ替え検定 / リサンプリング 34

35 独立性検定の従来法カテゴリカル / 分割表 -test A B a b 5 32 連続値 & ノンパラメトリック Spearman s rank test 1 極限帰無分布は - 分布, : :. Power divergence 35

36 Jensen-Tsallis / Power Divergence (Read&Cressie, Ku&Fine05) 各次元を個に分割 ( 等頻度など ). ( ) : 各小領域の頻度., : を構成する各変数の領域の周辺頻度, 1 2 1, 相互情報量, -ダイバージェンス / mean square contingency における帰無分布 2, 分割による方法は, 次元が高いと困難 36

37 数値実験データ :, : 1 dim プラスノイズの次元回転角 0. 0 なら独立, で最も依存性高い方法 HSIC モーメントマッチングによるGamma 曲線近似 HSIC リサンプリング Power divergence ( 3/2) functional correlation (Dauxois and G. M. Nkiet AoS 1998) 37

38 HSIC (Gamma 近似 ) HSIC (resampling) Power divergence ( 3/2, 等確率による分割 ) functional Correlation Type II errors 38

39 文書の独立性検定 Data: Official records of Canadian Parliament in English and French. Dependent data: 5 line-long parts from English texts and their French translations. Independent data: 5 line-long parts from English texts and random 5 line-parts from French texts. Kernel: Bag-of-words and spectral kernel Results of permutations test with HS measure Topic Match BOW(N=10) Spec(N=10) BOW(N=50) Spec(N=50) Agri- Random culture Same Fishery Random Same Immig- Random ration Same Acceptance rate ( = 5%) (Gretton et al. 07) 39

40 Distance covariance Def. dcov との比較, : 確率変数 (Euclidean 空間に値を取る ) dcov, 2.,,, : independent copies of,. c.f. HSIC(, ),,,, Note: は正定値ではない. 2,, Distance covariance (distance correlation) は最近注目されている依存性尺度 (Székely, Rizzo, Bakirov, AoS 2007). 40

41 の拡張 Ω 上のsemi-metric,, [ 対称性 ], 0, 等号成立は, [ 正値性 ] ( 三角不等式は仮定しない ) semi-metric, に対し,generalized distance covariance を以下で定義. dcov,,,, 2,,,,. 41

42 定理 (Sejdinovic et al. AoS 2013). [dcovはhsicの特別な例], が負定値なsemi-metric であるとき,,,,, により定まる正定値カーネル ( 補題 4.8 参照 ) を, とおくと, HSIC,, dcov,,. 証明は略. 直接計算. 例 ) ユークリッド空間上 (02) は負定値なsemi-metric ( 定理 4.10 Remark 1),,, HSIC, dcov, 2. 42

43 数値実験, (A) (B), 1 sin l sin l independent dependent harder easier 43

44 カーネル選択 MMD/HSIC によるノンパラメトリック検定の場合カーネルは特性的なものがよい. カーネルパラメータの選択本来は,powerやefficiencyを用いるのがよい. しかし, 必ずしも理論解析できない ( 参考 :Gretton et al NIPS 2012) Heuristics median, 1, supmmd sup, を検定統計量に用いる. 今後の研究が必要. 44

参考 : MIC Maximal Information coefficient, MIC Reshef, et al. "Detecting Novel Associations in Large Data Sets". Science 6062, 2011.

45 参考 : MIC Maximal Information coefficient, MIC Reshef, et al. "Detecting Novel Associations in Large Data Sets". Science 6062, さまざまな分割の仕方を組み合わせて使う. A Correlation for the 21st Century by Terry Speed, Science 6062, 2011 HSICとの比較 45

46 HSIC の応用 : Kernelized Sorting (Quadrianto, Smola, Song, Tuytelaars IEEE PAMI 2010) マッチング問題 : オブジェクトの対応を取るしかし, 対応の情報 ( 辞書 ) は全く使えないとする. 46

47 各ドメイン内でオブジェクト間の類似性の情報を使う. Domain A:,,. Domain B:,, Permutation で, と (1,,) が対応するものを探す. カーネル, によるグラム行列, は計算可能と仮定. HSIC = グラム行列の類似尺度, 1 Tr Kernelized Sorting max, or max max Tr を [0, 1] 値の確率行列に緩和して解く Convex Kernelized Sorting (Djuric et al AAAI2012) 47

48 (Quadrianto et al. IEEE PAMI 2010) 48

49 条件付独立性 49

50 条件付共分散作用素,, : Ω Ω Ω に値を取る確率変数.,, :Ω,Ω,Ω 上の正定値カーネル条件付相互共分散作用素 Σ Σ Σ Σ Σ / / 分解 : Σ Σ Σ, 1(Baker 1973). / / は相関を表す. Σ Σ Σ. 50

51 条件付独立性すべてのカーネルは特性的とする. Σ は条件付独立より弱い ( 次ページ参照 ). Σ, if and only if., : 変数の組み. 積カーネルを用いる. 条件付独立性尺度 : HSCONIC, Σ,, 推定量 : HSCONIC, Tr 2. : regularization coefficient 51

52 定理 ( 福水定理 9.6) が特性的なカーネルであるとき,, Σ Cov,, c.f. Cov, 0 for any square integrable,, and a.e.. 52

53 条件付独立性検定 HSICとは違い, 漸近的な帰無分布の形は知られていない. ( 正則化の扱いが難しい ) 並べ替え検定 / リサンプリングは, が連続変数の場合, 簡単ではない. の値の離散化が必要厳密な条件付独立性とシミュレートしていない. 53

54 正規化共分散作用素による依存性尺度 54

55 共分散作用素の正規化命題 (Baker 1973) 相互共分散作用素 Σ : に対し, 作用素 : で 1, / / Σ Σ Σ かつ, 在する. Σ, Σ となるものが一意に存正規化相互共分散作用素 (Normalized Cross-Covariance Operator) NOCCO / / Σ Σ Σ 相関を表す作用素 55

56 NOCCO による依存性尺度 Characterization of independence With characteristic kernels, WYX O X Y Dependence measure Assume W XY etc. are Hilbert-Schmidt. 56

57 Kernel-free Integral Expression Theorem (Fukumizu et al. NIPS 21, 2008) Assume P XY have density p XY ( x, y) H X H Y is characteristic. W YX is Hilbert-Schmidt. Then, 2 pxy ( x, y) 2 WYX 1 p x p y dxdy HS X ( ) Y ( ) px ( x) py ( y) - Kernel-free expression, though the definitions are given by kernels! -divergence (aka mean square contingency) is expressed by kernels! - A conditional version exists. 57

58 Empirical Estimator Empirical estimation is straightforward with the empirical crosscovariance operator ˆ ( N ). YX Inversion regularization: ˆ N 1 1 ( ) XX XX I 1/ 2 1/ 2 Replace the covariances in W YX YY YX XX by the empirical ones given by the data X (X 1 ),, X (X N ) and Y (Y 1 ),, Y (Y N ) Tr (dependence measure) where 1 R G G N I X X X N N T 1 X I N 1 N 1N N K X I N N T 1 1N N K N X k( X i, X j ) i j G 1, 1 HSNIC emp gives a new kernel estimator for the -divergence. Consistency is known. 58

59 Application to Independence Test Toy example 3 = 0 = /4 = / Y Y Y X 1 independent X 2 dependent X 3 independent They are all uncorrelated, but dependent for 0 < < /2 59

60 N = 200. Permutation test is used for independence test except contingency table. indep. more dependent Angle HSIC (Median) HSIC (Asymp. Var.) HSNIC (= 10 4, Median) HSNIC (= 10 6, Median) HSNIC (= 10 8, Median) HSNIC (Asymp. Var.) MI (#NN = 1) MI (#NN = 3) MI (#NN = 5) Power Diverg. (#Bins=3) Power Diverg. (#Bins=4) Power Diverg. (#Bins=5) # acceptance of independence out of 100 tests (significance level = 5%) 60

61 まとめカーネル平均による分布の表現カーネル平均埋め込み : 特徴ベクトルの平均により分布を一意に表現することが可能である特性的なカーネル. 密度関数の推定などの従来の方法と異なる, ノンパラメトリック推論の方法が構築できる. 再生性により, 推定量の計算が容易である. 共分散作用素 2つの確率変数の関係は,RKHS 上の共分散作用素により表現できる. 特性的なカーネルを用いると, 共分散作用素 =0により独立性を特徴づけられる. 独立性尺度 : HSIC= 共分散作用素のHSノルム 2 独立性検定の新しい統計量として HSIC が有効である. 61

62 条件付独立性条件付共分散作用素により, 条件付き独立性を特徴づけることが可能である. 多次元連続変数の場合の条件付独立性検定は, 困難を伴う. 正規化された相互共分散作用素 HS ノルムが -divergence( カーネルに依存しない量 ) を表す. 62

63 References Gretton, A., K.M. Borgwardt, M.J. Rasch, B. Schölkopf, A. Smola; A Kernel Two-Sample Test. Journal of Machine Learning Research 13(Mar): , Gretton, A., Bousquet, O., Smola, A., and Schoelkopf, B., Measuring Statistical Dependence with Hilbert-Schmidt Norms, Proc. 16th International Conference on Algorithmic Learning Theory: Springer- Verlag, Gretton, A., K. Fukumizu, C.-H. Teo, L. Song, B. Scholkopf, A. Smola. A Kernel Statistical Test of Independence. Advances in Neural Information Processing Systems 20, , MIT Press (2008). Fukumizu, K., L. Song, A. Gretton (2014) Kernel Bayes' Rule: Bayesian Inference with Positive Definite Kernels. Journal of Machine Learning Research. 14: Gretton, A., K. Fukumizu, C.-H. Teo, L. Song, B. Schölkopf, A. Smola. A Kernel Statistical Test of Independence. Advances in Neural Information Processing Systems 20, , MIT Press (2008). Gretton, A., Z. Harchaoui, K. Fukumizu, B. Sriperumbudur. A Fast, Consistent Kernel Two-Sample Test. Advances in Neural Information Processing Systems 22, , MIT Press (2010) 63

64 A. Gretton, B. Sriperumbudur, D. Sejdinovic, H. Strathmann, S. Balakrishnan, M. Pontil, K. Fukumizu (2012) Optimal kernel choice for large-scale two-sample tests. Advances in Neural Information Processing Systems 25 (NIPS2012), pp Székely, G. J. Rizzo, M. L. and Bakirov, N. K. (2007). Measuring and testing independence by correlation of distances, Annals of Statistics, 35/6, Sejdinovic, D., Sriperumbudur, B., Gretton, A. and Fukumizu, K. (2013) Equivalence of distance-based and RKHS-based statistics in hypothesis testing. Annals of Statistics 41, 5, Reshef, D. N.; Reshef, Y. A.; Finucane, H. K.; Grossman, S. R.; McVean, G.; Turnbaugh, P. J.; Lander, E. S.; Mitzenmacher, M.; Sabeti, P. C. (2011). "Detecting Novel Associations in Large Data Sets". Science 334 (6062): Fukumizu, K., A. Gretton, X. Sun, and B. Scholkopf: Kernel Measures of Conditional Dependence. Advances in Neural Information Processing Systems 20, , MIT Press (2008). 64

Microsoft PowerPoint - IBIS2012_open.pptx

Microsoft PowerPoint - IBIS2012_open.pptx カーネル法の新展開ーその理論と応用ー福水健次統計数理研究所 / 総合研究大学院大学第 15 回情報論的学習理論ワークショップ (IBIS2012) 2012.11.7 9. @ 筑波大学東京キャンパス 1 Outline 1. イントロダクション : カーネル法の概要 2. 確率分布の表現としてのカーネル法 3. 条件付確率の表現と推定精度 4. カーネル推論則 5. おわりに 2 データの高次元性,