Statistical learning theory
コンピュータサイエンス においては 、 統計学習理論 において、 表現定理とは、 再生カーネルヒルベルト空間 上で定義された正規化された 経験的リスク関数 の 最小化が、 トレーニングセットデータの入力ポイントで評価されたカーネル積の有限線形結合として表現できることを示す、いくつかの関連する結果のいずれかです。 f ∗ {\displaystyle f^{*}}
以下の代表者定理とその証明は、 Schölkopf 、Herbrich、Smolaによるものである。 [1]
定理： 空でない集合上の 正定値実数値核 と、それに対応する再生核ヒルベルト空間を考える 。 k : X × X → R {\displaystyle k:{\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} } X {\displaystyle {\mathcal {X}}} H k {\displaystyle H_{k}}
トレーニングサンプル 、 ( x 1 , y 1 ) , … , ( x n , y n ) ∈ X × R {\displaystyle (x_{1},y_{1}),\dotsc ,(x_{n},y_{n})\in {\mathcal {X}}\times \mathbb {R} } 厳密に増加する実数値関数 、および g : [ 0 , ∞ ) → R {\displaystyle g\colon [0,\infty )\to \mathbb {R} } 任意の誤差関数 、 E : ( X × R 2 ) n → R ∪ { ∞ } {\displaystyle E\colon ({\mathcal {X}}\times \mathbb {R} ^{2})^{n}\to \mathbb {R} \cup \lbrace \infty \rbrace } これらを合わせると、 上の次の正規化された経験的リスク関数が定義されます 。 H k {\displaystyle H_{k}}
f ↦ E ( ( x 1 , y 1 , f ( x 1 ) ) , … , ( x n , y n , f ( x n ) ) ) + g ( ‖ f ‖ ) . {\displaystyle f\mapsto E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+g\left(\lVert f\rVert \right).} そして、経験的リスクを最小化する
f ∗ = argmin f ∈ H k { E ( ( x 1 , y 1 , f ( x 1 ) ) , … , ( x n , y n , f ( x n ) ) ) + g ( ‖ f ‖ ) } , ( ∗ ) {\displaystyle f^{*}={\underset {f\in H_{k}}{\operatorname {argmin} }}\left\lbrace E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+g\left(\lVert f\rVert \right)\right\rbrace ,\quad (*)} 次のような形式の表現が可能です。
f ∗ ( ⋅ ) = ∑ i = 1 n α i k ( ⋅ , x i ) , {\displaystyle f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i}),} すべての 場合において 。 α i ∈ R {\displaystyle \alpha _{i}\in \mathbb {R} } 1 ≤ i ≤ n {\displaystyle 1\leq i\leq n}
証明: マッピングを定義する
φ : X → H k φ ( x ) = k ( ⋅ , x ) {\displaystyle {\begin{aligned}\varphi \colon {\mathcal {X}}&\to H_{k}\\\varphi (x)&=k(\cdot ,x)\end{aligned}}} （したがって、それ 自体は写像である ）。 は再生核なので、 φ ( x ) = k ( ⋅ , x ) {\displaystyle \varphi (x)=k(\cdot ,x)} X → R {\displaystyle {\mathcal {X}}\to \mathbb {R} } k {\displaystyle k}
φ ( x ) ( x ′ ) = k ( x ′ , x ) = ⟨ φ ( x ′ ) , φ ( x ) ⟩ , {\displaystyle \varphi (x)(x')=k(x',x)=\langle \varphi (x'),\varphi (x)\rangle ,} の内積は どこにありますか 。 ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } H k {\displaystyle H_{k}}
任意の について、直交射影を使用して、任意の を 1 つは にあり、 もう 1 つは 直交補関数 にある 2 つの関数の和に 分解できます 。 x 1 , … , x n {\displaystyle x_{1},\ldots ,x_{n}} f ∈ H k {\displaystyle f\in H_{k}} span { φ ( x 1 ) , … , φ ( x n ) } {\displaystyle \operatorname {span} \left\lbrace \varphi (x_{1}),\ldots ,\varphi (x_{n})\right\rbrace }
f = ∑ i = 1 n α i φ ( x i ) + v , {\displaystyle f=\sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v,} すべての 場合において 。 ⟨ v , φ ( x i ) ⟩ = 0 {\displaystyle \langle v,\varphi (x_{i})\rangle =0} i {\displaystyle i}
上記の直交分解と 再生特性 を組み合わせると、 任意のトレーニングポイントに適用すると 、 f {\displaystyle f} x j {\displaystyle x_{j}}
f ( x j ) = ⟨ ∑ i = 1 n α i φ ( x i ) + v , φ ( x j ) ⟩ = ∑ i = 1 n α i ⟨ φ ( x i ) , φ ( x j ) ⟩ , {\displaystyle f(x_{j})=\left\langle \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v,\varphi (x_{j})\right\rangle =\sum _{i=1}^{n}\alpha _{i}\langle \varphi (x_{i}),\varphi (x_{j})\rangle ,} これは に依存しないことがわかります。したがって、 (*) における 誤差関数の値も同様に に依存しません。2番目の項（正規化項）については、 は に直交し 、 は厳密に単調である ため、 v {\displaystyle v} E {\displaystyle E} v {\displaystyle v} v {\displaystyle v} ∑ i = 1 n α i φ ( x i ) {\displaystyle \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})} g {\displaystyle g}
g ( ‖ f ‖ ) = g ( ‖ ∑ i = 1 n α i φ ( x i ) + v ‖ ) = g ( ‖ ∑ i = 1 n α i φ ( x i ) ‖ 2 + ‖ v ‖ 2 ) ≥ g ( ‖ ∑ i = 1 n α i φ ( x i ) ‖ ) . {\displaystyle {\begin{aligned}g\left(\lVert f\rVert \right)&=g\left(\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v\rVert \right)\\&=g\left({\sqrt {\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})\rVert ^{2}+\lVert v\rVert ^{2}}}\right)\\&\geq g\left(\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})\rVert \right).\end{aligned}}} したがって、設定は (*)の第一項には影響を与えないが、第二項を厳密に減少させる。したがって、 (*)における任意の最小化項は必ず 、すなわち、 の形をとる。 v = 0 {\displaystyle v=0} f ∗ {\displaystyle f^{*}} v = 0 {\displaystyle v=0}
f ∗ ( ⋅ ) = ∑ i = 1 n α i φ ( x i ) = ∑ i = 1 n α i k ( ⋅ , x i ) , {\displaystyle f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i}),} これが望ましい結果です。
一般化 上記の定理は、総称して「代表定理」と呼ばれる一連の結果の特定の例です。ここでは、そのような定理をいくつか説明します。
代表者定理の最初の定理は、キメルドルフとワバによって、次のような特別なケースに対して示された。
E ( ( x 1 , y 1 , f ( x 1 ) ) , … , ( x n , y n , f ( x n ) ) ) = 1 n ∑ i = 1 n ( f ( x i ) − y i ) 2 , g ( ‖ f ‖ ) = λ ‖ f ‖ 2 {\displaystyle {\begin{aligned}E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)&={\frac {1}{n}}\sum _{i=1}^{n}(f(x_{i})-y_{i})^{2},\\g(\lVert f\rVert )&=\lambda \lVert f\rVert ^{2}\end{aligned}}} Schölkopf、Herbrich、およびSmolaは 、損失コストの二乗の仮定を緩和し、正規化子を ヒルベルト空間ノルムの
厳密に単調増加な関数にすることで、この結果を一般化しました。 λ > 0 {\displaystyle \lambda >0} g ( ⋅ ) {\displaystyle g(\cdot )}
正規化された経験的リスク関数にペナルティのないオフセット項を追加することで、さらに一般化することが可能になる。例えば、Schölkopf、Herbrich、Smolaは、最小化についても考察している。
f ~ ∗ = argmin { E ( ( x 1 , y 1 , f ~ ( x 1 ) ) , … , ( x n , y n , f ~ ( x n ) ) ) + g ( ‖ f ‖ ) ∣ f ~ = f + h ∈ H k ⊕ span { ψ p ∣ 1 ≤ p ≤ M } } , ( † ) {\displaystyle {\tilde {f}}^{*}=\operatorname {argmin} \left\lbrace E\left((x_{1},y_{1},{\tilde {f}}(x_{1})),\ldots ,(x_{n},y_{n},{\tilde {f}}(x_{n}))\right)+g\left(\lVert f\rVert \right)\mid {\tilde {f}}=f+h\in H_{k}\oplus \operatorname {span} \lbrace \psi _{p}\mid 1\leq p\leq M\rbrace \right\rbrace ,\quad (\dagger )} すなわち、 の形の関数を考える。 ここで 、 は 有限の実数値関数の集合の範囲内にあるペナルティなしの関数である。 行列の 階数が である という仮定のもとで、 の最小化関数 は の形の表現を許すこと を示す。 f ~ = f + h {\displaystyle {\tilde {f}}=f+h} f ∈ H k {\displaystyle f\in H_{k}} h {\displaystyle h} { ψ p : X → R ∣ 1 ≤ p ≤ M } {\displaystyle \lbrace \psi _{p}\colon {\mathcal {X}}\to \mathbb {R} \mid 1\leq p\leq M\rbrace } n × M {\displaystyle n\times M} ( ψ p ( x i ) ) i p {\displaystyle \left(\psi _{p}(x_{i})\right)_{ip}} M {\displaystyle M} f ~ ∗ {\displaystyle {\tilde {f}}^{*}} ( † ) {\displaystyle (\dagger )}
f ~ ∗ ( ⋅ ) = ∑ i = 1 n α i k ( ⋅ , x i ) + ∑ p = 1 M β p ψ p ( ⋅ ) {\displaystyle {\tilde {f}}^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i})+\sum _{p=1}^{M}\beta _{p}\psi _{p}(\cdot )} ここで 、 と はすべて一意に決定されます。 α i , β p ∈ R {\displaystyle \alpha _{i},\beta _{p}\in \mathbb {R} } β p {\displaystyle \beta _{p}}
代表者定理が存在する条件は、Argyriou、Micchelli、Pontil によって調査され、次のことが証明されました。
定理： を空でない集合とし、 上 の正定値実数値核 で、対応する再生核ヒルベルト空間 をもち 、 を 微分可能な正則化関数とする。訓練サンプル と任意の誤差関数が与えられたとき 、最小化関数は X {\displaystyle {\mathcal {X}}} k {\displaystyle k} X × X {\displaystyle {\mathcal {X}}\times {\mathcal {X}}} H k {\displaystyle H_{k}} R : H k → R {\displaystyle R\colon H_{k}\to \mathbb {R} } ( x 1 , y 1 ) , … , ( x n , y n ) ∈ X × R {\displaystyle (x_{1},y_{1}),\ldots ,(x_{n},y_{n})\in {\mathcal {X}}\times \mathbb {R} } E : ( X × R 2 ) m → R ∪ { ∞ } {\displaystyle E\colon ({\mathcal {X}}\times \mathbb {R} ^{2})^{m}\to \mathbb {R} \cup \lbrace \infty \rbrace }
f ∗ = argmin f ∈ H k { E ( ( x 1 , y 1 , f ( x 1 ) ) , … , ( x n , y n , f ( x n ) ) ) + R ( f ) } ( ‡ ) {\displaystyle f^{*}={\underset {f\in H_{k}}{\operatorname {argmin} }}\left\lbrace E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+R(f)\right\rbrace \quad (\ddagger )} 正規化された経験的リスクは、次のような表現をとることができる。
f ∗ ( ⋅ ) = ∑ i = 1 n α i k ( ⋅ , x i ) , {\displaystyle f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i}),} ここで 、 すべての に対して、 次 の非減少関数が存在する 場合のみ、 α i ∈ R {\displaystyle \alpha _{i}\in \mathbb {R} } 1 ≤ i ≤ n {\displaystyle 1\leq i\leq n} h : [ 0 , ∞ ) → R {\displaystyle h\colon [0,\infty )\to \mathbb {R} }
R ( f ) = h ( ‖ f ‖ ) . {\displaystyle R(f)=h(\lVert f\rVert ).} 実質的に、この結果は、対応する正規化経験的リスク最小化が代表定理を持つための、 微分可能正則化に関する必要十分条件を提供する 。特に、これは、（キメルドルフとワバが当初考えていたものよりもはるかに広範な）正規化リスク最小化の広範なクラスが代表定理を持つことを示す。 R ( ⋅ ) {\displaystyle R(\cdot )} ( ‡ ) {\displaystyle (\ddagger )}
アプリケーション 表現子定理は、正規化された 経験的リスク最小化 問題 を大幅に単純化するため、実用的な観点から有用である 。最も興味深い応用では、最小化の探索領域 は の無限次元部分空間となる ため、探索（記述されているとおり）は有限メモリおよび有限精度のコンピュータでは実装できない。対照的に、表現子定理によって提供される の表現は、元の（無限次元）最小化問題を最適な 次元係数ベクトル の 探索に簡約し 、 その後、任意の標準的な関数最小化アルゴリズムを適用して を得ることができる。したがって、表現子定理は、一般的な機械学習問題を実際にコンピュータで実装できるアルゴリズムに簡約するための理論的基礎を提供する。 ( ‡ ) {\displaystyle (\ddagger )} H k {\displaystyle H_{k}} L 2 ( X ) {\displaystyle L^{2}({\mathcal {X}})} f ∗ ( ⋅ ) {\displaystyle f^{*}(\cdot )} n {\displaystyle n} α = ( α 1 , … , α n ) ∈ R n {\displaystyle \alpha =(\alpha _{1},\ldots ,\alpha _{n})\in \mathbb {R} ^{n}} α {\displaystyle \alpha }
以下は、代表者定理によって存在が保証されている最小解を求める方法の例です。この方法は任意の正定値カーネルに適用でき 、複雑な（場合によっては無限次元の）最適化問題を数値的に解ける単純な線形システムに変換することができます。 K {\displaystyle K}
最小二乗誤差関数を使用していると仮定する
E [ ( x 1 , y 1 , f ( x 1 ) ) , … , ( x n , y n , f ( x n ) ) ] := ∑ i = 1 n ( y i − f ( x i ) ) 2 {\displaystyle E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{n},f(x_{n}))]:=\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}} と、何らかの 正規化関数が存在する 。代表者定理により、最小化関数 g ( x ) = λ x 2 {\displaystyle g(x)=\lambda x^{2}} λ > 0 {\displaystyle \lambda >0}
f ∗ = argmin f ∈ H { E [ ( x 1 , y 1 , f ( x 1 ) ) , … , ( x n , y n , f ( x n ) ) ] + g ( ‖ f ‖ H ) } = argmin f ∈ H { ∑ i = 1 n ( y i − f ( x i ) ) 2 + λ ‖ f ‖ H 2 } {\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}{\Big \{}E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{n},f(x_{n}))]+g(\|f\|_{\mathcal {H}}){\Big \}}={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}\left\{\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda \|f\|_{\mathcal {H}}^{2}\right\}} フォームは
f ∗ ( x ) = ∑ i = 1 n α i ∗ k ( x , x i ) {\displaystyle f^{*}(x)=\sum _{i=1}^{n}\alpha _{i}^{*}k(x,x_{i})} 一部の人にとっては 。 α ∗ = ( α 1 ∗ , … , α n ∗ ) ∈ R n {\displaystyle \alpha ^{*}=(\alpha _{1}^{*},\dots ,\alpha _{n}^{*})\in \mathbb {R} ^{n}}
‖ f ‖ H 2 = ⟨ ∑ i = 1 n α i ∗ k ( ⋅ , x i ) , ∑ j = 1 n α j ∗ k ( ⋅ , x j ) ⟩ H = ∑ i = 1 n ∑ j = 1 n α i ∗ α j ∗ ⟨ k ( ⋅ , x i ) , k ( ⋅ , x j ) ⟩ H = ∑ i = 1 n ∑ j = 1 n α i ∗ α j ∗ k ( x i , x j ) , {\displaystyle \|f\|_{\mathcal {H}}^{2}={\Big \langle }\sum _{i=1}^{n}\alpha _{i}^{*}k(\cdot ,x_{i}),\sum _{j=1}^{n}\alpha _{j}^{*}k(\cdot ,x_{j}){\Big \rangle }_{\mathcal {H}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\alpha _{i}^{*}\alpha _{j}^{*}{\big \langle }k(\cdot ,x_{i}),k(\cdot ,x_{j}){\big \rangle }_{\mathcal {H}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\alpha _{i}^{*}\alpha _{j}^{*}k(x_{i},x_{j}),} 次のような形をしている ことがわかります α ∗ {\displaystyle \alpha ^{*}}
α ∗ = argmin α ∈ R n { ∑ i = 1 n ( y i − ∑ j = 1 n α j k ( x i , x j ) ) 2 + λ ‖ f ‖ H 2 } = argmin α ∈ R n { ‖ y − A α ‖ 2 + λ α ⊺ A α } . {\displaystyle \alpha ^{*}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatorname {argmin} }}\left\{\sum _{i=1}^{n}\left(y_{i}-\sum _{j=1}^{n}\alpha _{j}k(x_{i},x_{j})\right)^{2}+\lambda \|f\|_{\mathcal {H}}^{2}\right\}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatorname {argmin} }}\left\{\|y-A\alpha \|^{2}+\lambda \alpha ^{\intercal }A\alpha \right\}.} ここで 、 と である 。これは因数分解して次のように簡略化できる。 A i j = k ( x i , x j ) {\displaystyle A_{ij}=k(x_{i},x_{j})} y = ( y 1 , … , y n ) {\displaystyle y=(y_{1},\dots ,y_{n})}
α ∗ = argmin α ∈ R n { α ⊺ ( A ⊺ A + λ A ) α − 2 α ⊺ A ⊺ y } . {\displaystyle \alpha ^{*}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatorname {argmin} }}\left\{\alpha ^{\intercal }(A^{\intercal }A+\lambda A)\alpha -2\alpha ^{\intercal }A^{\intercal }y\right\}.} は正定値行列なので 、この式には確かに単一の大域的最小値が存在する。 とし、 が凸である ことに注意する 。すると 、大域的最小値である は と置くことで解ける 。すべての正定値行列は逆行列であることを思い出すと、 A ⊺ A + λ A {\displaystyle A^{\intercal }A+\lambda A} F ( α ) = α ⊺ ( A ⊺ A + λ A ) α − 2 α ⊺ A ⊺ y {\displaystyle F(\alpha )=\alpha ^{\intercal }(A^{\intercal }A+\lambda A)\alpha -2\alpha ^{\intercal }A^{\intercal }y} F {\displaystyle F} α ∗ {\displaystyle \alpha ^{*}} ∇ α F = 0 {\displaystyle \nabla _{\alpha }F=0}
∇ α F = 2 ( A ⊺ A + λ A ) α ∗ − 2 A ⊺ y = 0 ⟹ α ∗ = ( A ⊺ A + λ A ) − 1 A ⊺ y , {\displaystyle \nabla _{\alpha }F=2(A^{\intercal }A+\lambda A)\alpha ^{*}-2A^{\intercal }y=0\Longrightarrow \alpha ^{*}=(A^{\intercal }A+\lambda A)^{-1}A^{\intercal }y,} したがって、最小値は線形解によって見つけることができます。
参照
参考文献 ^ Schölkopf, Bernhard; Herbrich, Ralf; Smola, Alex J. (2001). 「一般化表現定理」. Helmbold, David; Williamson, Bob (編). 計算学習理論 . コンピュータサイエンス講義ノート. 第2111巻. ベルリン、ハイデルベルク: Springer. pp. 416– 426. doi :10.1007/3-540-44581-1_27. ISBN 978-3-540-44581-4 。 Argyriou, Andreas; Micchelli, Charles A.; Pontil, Massimiliano (2009). 「代表子定理はいつ成立するのか？ ベクトル正規化子と行列正規化子の比較」. Journal of Machine Learning Research . 10 (12月): 2507–2529 . クッカー, フェリペ; スメール, スティーブ (2002). 「学習の数学的基礎について」. アメリカ数学会報 . 39 (1): 1– 49. doi : 10.1090/S0273-0979-01-00923-5 . MR 1864085. Kimeldorf, George S.; Wahba, Grace (1970). 「確率過程におけるベイズ推定とスプラインによる平滑化との対応」. 数理統計年報 . 41 (2): 495– 502. doi : 10.1214/aoms/1177697089 . Schölkopf, Bernhard; Herbrich, Ralf; Smola, Alex J. (2001). 「一般化表現定理」. 計算学習理論 . コンピュータサイエンス講義ノート. 第2111巻. pp. 416– 426. CiteSeerX 10.1.1.42.8617 . doi :10.1007/3-540-44581-1_27. ISBN 978-3-540-42343-0 。 
![{\displaystyle E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{n},f(x_{n}))]:=\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d354601f2920a8bb29f0439e039dd59400a16c87)
![{\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}{\Big \{}E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{n},f(x_{n}))]+g(\|f\|_{\mathcal {H}}){\Big \}}={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}\left\{\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda \|f\|_{\mathcal {H}}^{2}\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0dec0b274ce39a169bcf01c4e1da6fcb12513568)
