鈴木大慈東京大学大学院情報理工学系研究科数理情報学専攻数理第六研究室Outline ●再生核ヒルベルト空間の定義●カーネル法の推定精度●再生核ヒルベルト空間における最適化線形回帰デザイン行列X = (X j ) ∈ R n×P .     Y = [ Y 1 , . . , y n ]    ∈ R n .真のベクトルβ* ∈ RP:
リッジ回帰（Tsykonov正則化）

3 / 28

デザイン行列X = (Xij) ∈ Rn×P.     Y = [y1,...,yn] T ∈ Rn.真のベクトルβ* ∈ RP:
リッジ回帰（Tsykonov正則化）
変数変換: ●正則化項のため，β ∈ Ker(X) ⊥ . つまり，β ∈ Im(X T ). ●あるâ ∈ R nが存在して， â = X T âと書ける.
※ (XX T );j = x, T x;より，観測値x;とx;の内積さえ計算できればよい.
3 / 28

リッジ回帰（変数変換版）
※ (XX T );j = x; x;はサンプルx;とx;の内積.
4 / 28

リッジ回帰（変数変換版） â ← arg min └‖XX ⸢ α − Y‖ ² + λ nα ⸢ (XX ⸢ )α. α∈R" ※ (XX T );; = x; x;はサンプルx;とx;の内積. ●カーネル法のアイディアxの間の内積を他の非線形な関数で置き換える: x;' xj   →  k(x;, xj).このk : RP × RP → Rをカーネル関数と呼ぶ. Definition (正定値カーネル) 。対称性:  k(x, x') = k(x', x). 。正値性: ∑ i=1 ∑ i=1 α ;α jk(x i ,x j) ≥ 0,  (V{x i} ≥ 1,  {α i} ≥ 1,  m ).逆にこの性質を満たす関数なら何でもカーネル法で用いて良い.
4 / 25

で予測.
5 / 28

カーネルリッジ回帰: Ｋ＝(k(x;,x;)); j=1として,
で予測.カーネル関数  ⇔  再生核ヒルベルト空間(RKHS)
H kあるφ(x) : RP → Hkが存在して, e k(x, x') = {φ(x), φ(x')} H, . ●カーネルトリック: 〈∑ i=1 α iφ(x i ), φ(x)\ H x = ∑ i=1 α i k(x i , x ). →カーネル関数の値さえ計算できれば良い.
5 / 28

Definition (再生核ヒルベルト空間(RKHS))集合メ上の（実数値）関数からなるヒルペルト空間死が再生核ヒルペルト空間であるとは，∀ x ∈ Xに対してk ∈ Hが存在して再生性：   (f, kx)H = f(x)   (∀f ∈ H)が成り立つこととする.特に,  k(x,y) = ⟨kx, ky⟩ xは正定値カーネルであり，Hに付随した再生核(Reproducing kernel)とよぶ. Theorem (Moore-Aronszajn (Aronszajn, 1950)) k : X × X → Rは正定値カーネル. ⇒ kを再生核とする再生核ヒルベルト空間が一意的に存在する.
●入力データの分布：Px ●対応するL 2空間：L 2 (Px) = {f | Ex~Px [f(X) 2 ] < ∞} (可分とする). ( k(x,x)dPx(x) < ∞なら，カーネル関数は以下のように分解できる(Steinwart and Scovel, 2012): 9
i=1 ¤ (e;)ñ1はL2(Px)内の正規直交基底:  ||e;||L2(Px) = 1,  (e;, e;r)L2(Px) = 0 (j ≠ j'). o μ; ≥ 0. Theorem (再生核ヒルベルト空間(¥¸)の表現) o (f,g)H, := ∑j=1 µjajβj for f = ∑j=1 ajej, g = ∑j=1 βjej ∈ L2(Px). ● ||f||x, := \/(f,f)H, ● H k := {f ∈ L 2 (P x ) | ||f || H , < ∞} equipped with 〈 , 〉 H , .再生性: f ∈ H kに対してf(x)は内積の形で「再生」される: (f, k(x, ·))H, = ∑j=1 µ,αjµjej(x) = ∑j=1 αjej(x) = f(x). 7 / 28
カーネル関数に対応する積分作用素 T k : L 2 (P x ) → L 2 (P x ):
●先のカーネル関数の分解はT kのスペクトル分解に対応. ●再生核ヒルベルト空間Hkは以下のようにも書ける:

8/28

カーネル関数に対応する積分作用素 T k : L 2 (P x ) → L 2 (P x ):
●先のカーネル関数の分解はT tのスペクトル分解に対応. ●再生核ヒルベルト空間Hkは以下のようにも書ける:
● (e j ) jはL 2内の正規直交基底, ( √ je j ) jはRKHS内の完全正規直交基底. ● φκ(x) = k(x, ·) ∈ Hkは特徴写像とみなせ，Hkの完全正規直交基底に関する係数で表現すると

8/28

。カーネルリッジ回帰の再定式化= ∑(y; − f(x;))² + C||f||¥, Theorem (表現定理)最適解f ∈ H kはn個のカーネルの和で表現できる: ∃α; ∈ R    s.t.     f(x) = (Proof) f(x;) = {f,k(x;, )}H,より,  fはspan{k(x;, -) (i ∈ [n])} = ¥上にいる.実際, f = f + f 1 (f ∈ H, f 1 ∈ H − )と分解すると，∥ f ∥霧, ＝ ∥ f ∥霧, + ∥ f ∥霧,かつ{f,k(xi, ·)},, = {f,k(xi, ·)},なので, f, = 0とした方が目的関数を小さくできる。口||f||¾, = ∑'',j=1 α;α;k(x;,x;) = α T Kαに注意すると,さきほど天下り的に与えたカーネルリッジ回帰の定式化と一致. 0 / 28
。非線形な推論を再生核ヒルベルト空間への非線形写像るを用いて行う. 。再生核ヒルベルト空間では線形な処理をする。 。カーネル法は第一層を固定し第二層目のパラメータを学習する横幅無限大の2層ニューラルネットワークともみなせる. ( “浅い”学習手法の代表例)
ただし，φj(×) = √μjej(×).
11 / 28

るガウシアンカーネル
。 Matérn-kernel

12 / 28
Outline ●再生核ヒルベルト空間の定義●カーネル法の推定精度●再生核ヒルベルト空間における最適化
Polynomial regression   (15th-order polynomial)

14 / 28

Polynomial regression   (15th-order polynomial)
Horizontal axis: regularization parameter λ (log-scale). Vertical axis: generalization error (blue), training error (red).
15 / 28

●積分作用素としての表現:
in L2(P(X) × P(X)). Definition再生核ヒルベルト空間の自由度(degrees of freedom):
Nk(入)はRKHSの「複雑さ」を計る. 16 / 28
モデル:
カーネルリッジ回帰:
Proposition (Caponnetto and de Vito (2007)) f° ∈ Hであるなら.
が高い確率で成り立つ(バイアス-バリアンスのトレードオフ). ●基本的に쓰( λ = λを満たすλを選べば良い.
Minimax-optimalであることが知られている. 17 / 28 Rough sketch of N k ( λ ). N k (入) ● Estimation error in Nk(λ) dimensional space: n ●  Bias (residual):  λ Outline ●再生核ヒルベルト空間の定義●カーネル法の推定精度●再生核ヒルベルト空間における最適化
問題設定: y; = f°(x;) + ξ;. (×;, y;);期待損失の変形: E[(f(X) − Y)²] = E[(f(X) − f°(X) − ξ)²] = E[(f(X) − f°(X))²] + σ² → minfeh, E[(f(X) – Y)²]を解けばf°が求まる.期待損失のFrechet微分: K x = k(x, ·) ∈ H kとする.  f(x) = ⟨ f, K x⟩ x,に気を付けるとL(f) = E[(f(X) − Y)²] = E[((Kx, f)H, − Y)²]のRKHS内でのFrechet微分は以下の通り: ∇L(f) = 2E[Kx(\Kx,f)H, = Y)] = 2(E[KxK¥] f − E[KxY]) =:L = 2(∑ƒ – E[KxY]).
20 / 28

L(f) = E[(f(X) − Y)²]のRKHS内でのFrechet微分:
。期待損失の勾配法:
。経験損失の勾配法(ñ[.]は標本平均):
●確率的勾配による更新:

21 / 28

関数値の更新式:
積分作用素Tkは高周波成分を抑制する作用がある. ● RKHS内の勾配はL 2内の関数勾配をT kによって平滑化したものになっている．(実際はTkのサンプルからの推定値を使う) ●高周波成分が出てくる前に止めれば過学習を防げる. → Early stopping ●迂闊にNewton法などを使うと危険.
22 / 28

Early stoppingによる正則化バイアス-バリアンス分解訓練誤差最小化元に達する前に止める(early stopping)ことで正則化が働く無限次元モデル(RKHS)は過学習しやすいので気を付ける必要がある.
通常、以下の条件を考える. (統計理論でも同様の仮定を課す定番の仮定) (Caponnetto and de Vito, 2007, Dieuleveut et al., 2016, Pillaud-Vivien et al., 2018) o μ; = 0(i-α) for α > 1. αはRKHSH,の複雑さを特徴づける. (小さいα:複雑,大きいα:単純) 。 f° ∈ T ξ (L 2 (P x))  for r > 0. f°がRKHSからどれだけ“はみ出ているか”を特徴づけ. r = 1/2はf° ∈ H kに対応.  (r < 1/2:はみ出てる. r > 1/2:含まれる) • ||f||L_(ex) < ||f||l_(ex)||f||", (Vf E Hk) for µ E (0, 1]. H kに含まれている関数の滑らかさを特徴づけ. (小さいμ:滑らか) ※最後の条件について:  f ∈ W™([0, 1] a ) (Sobolev空間)かつP xの台が[0, 1] aで密度関数を持ち、その密度が下からある定数ｃ＞０で抑えられていれば、 μ = d/(2m)でなりたつ.
24 / 28

バイアス-バリアンスの分解:
(a)勾配法の解のデータに関する期待値と真の関数とのズレ(Bias). (b) 勾配法の解の分散(Variance). (c)確率的勾配を用いることによる変動.更新数tを大きくするとBiasは減るがVarianceが増える. これらをバランスする必要がある(Early stopping). Theorem (Multi-pass SGDの収束レート(Pillaud-Vivien et al., 2018)) η = 1/(4 sup, k(x, x)²)とする. ● μα < 2rα + 1 < αの時，t = Θ( nα/(2rα+1))とすれば、
םμα ≥ 2rα + 1の時, t = Θ(n≠ (log n)≠ )とすれば, E[L(g;)] = L(f°) = Θ(n≠ 2r/n )
Natural gradient (自然勾配法): ft = ft-1 - η(Σ + λΙ)-1 (Σ ft-1 - Ê[Kx Y]). (unlabeled dataが沢山ありΣは良く推定できる設定; GDの解析(Murata and Suzuki, 2021)) Theorem (Natural gradientの収束 (Amari et al., 2021))
特に，入＝ n− säñī , t = Θ(log( n ))でE[‖ ˆ ı − f°‖ z ( ρχ )] = Θ( n− zäñī log( n ) 4 ). ※バイアスは急速に収束するが、バリアンスも速く増大する. → Preconditioningのため高周波成分が早めに出現する．より早めに止めないと過学習する.
26 / 28

。 Σ = E x [K x K x ]:  Σ f =  [ k( , x ) f(x)dP x (x) ｡ Ê = ± ∑ ï=1 K x K x :  Ê f = ± ∑ ï=1 k( ·, x ; ) f(x ; ) Σ λ := Σ + λΙ,   Σ∞(λ) := sup x Κ x ∑ ζ 1 K xとする. 以下のような評価が必要:
with prob. 1 − δ.ただし，β = log( 4 Tr [ ξ →経験分布と真の分布のずれをバウンド. Theorem (自己共役作用素のBernsteinの不等式 (Minsker, 2017)) (X;)) σ² ≥ || ∑ ′ ⇒ 1 E [ X ′ ]||, ∪ ≥ ||X;||とする．r(A) = Tr[A]/||A||として,
X; = Σ ঙ 1 K x K x Σ ঙ 1とする.   (Tropp (2012)も参照)
28 / 28
S. Amari, J. Ba, R. B. Grosse, X. Li, A. Nitanda, T. Suzuki, D. Wu, and J. Xu. When does preconditioning help or hurt generalization?  In International Conference on Learning Representations, 2021. N. Aronszajn.  Theory of reproducing kernels.  Transactions of the American Mathematical Society, 68:337–404, 1950. A. Caponnetto and E. de Vito. Optimal rates for regularized least-squares algorithm.  Foundations of Computational Mathematics, 7(3):331–368, 2007. A. Dieuleveut, F. Bach, et al. Nonparametric stochastic approximation with large step-sizes.  The Annals of Statistics, 44(4):1363–1399, 2016. S. Minsker. On some extensions of Bernstein's inequality for self-adjoint operators.  Statistics &  Probability Letters,  127:111–119,  2017. T. Murata and T. Suzuki. Gradient descent in rkhs with importance labeling. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1981–1989. PMLR, 2021. L. Pillaud-Vivien, A. Rudi, and F. Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems, pages 8114–8124, 2018. I. Steinwart and C. Scovel. Mercer ' s theorem on general domains: on the interaction between measures, kernels, and RKHSs.  Constructive Approximation, 35(3):363–417, 2012. J. A. Tropp. User-friendly tools for random matrices: An introduction. Technical report, 2012.