表現者の定理の証明
📂機械学習 表現者の定理の証明 定理 インプット集合input set X ≠ ∅ X \ne \emptyset X = ∅ 正定値カーネル k : X × X → R k: X \times X \to \mathbb{R} k : X × X → R 学習データセット training Dataset を
D : = { ( x i , y i ) } i = 1 m ⊂ X × R
D := \left\{ \left( x_{i} , y_{i} \right) \right\}_{i=1}^{m} \subset X \times \mathbb{R}
D := { ( x i , y i ) } i = 1 m ⊂ X × R 再生カーネルヒルベルト空間 H k H_{k} H k F : = { f ∈ R X : f ( ⋅ ) = ∑ i = 1 ∞ β i k ( ⋅ , z i ) ∧ β i ∈ R ∧ z i ∈ X ∧ ∥ f ∥ < ∞ } ⊂ H k
\mathcal{F} := \left\{ f \in \mathbb{R}^{X} : f \left( \cdot \right) = \sum_{i=1}^{\infty} \beta_{i} k \left( \cdot , z_{i} \right) \land \beta_{i} \in \mathbb{R} \land z_{i} \in X \land \left\| f \right\| < \infty \right\} \subset H_{k}
F := { f ∈ R X : f ( ⋅ ) = i = 1 ∑ ∞ β i k ( ⋅ , z i ) ∧ β i ∈ R ∧ z i ∈ X ∧ ∥ f ∥ < ∞ } ⊂ H k 目的関数 c : ( D × R ) m → R ‾ c : \left( D \times \mathbb{R} \right) ^{m} \to \overline{\mathbb{R}} c : ( D × R ) m → R 単調増加関数 であるレギュライザー regulizer g : R → [ 0 , ∞ ) g : \mathbb{R} \to [0,\infty) g : R → [ 0 , ∞ ) 正則化された目的汎関数 regulized Objective Functional L : F → R ‾ L : \mathcal{F} \to \overline{\mathbb{R}} L : F → R L ( f ) : = c ( ( x 1 , y 1 , f ( x 1 ) ) , ⋯ , ( x m , y m , f ( x m ) ) ) + g ( ∥ f ∥ )
L (f) := c \left( \left( x_{1}, y_{1}, f \left( x_{1} \right) \right), \cdots , \left( x_{m}, y_{m}, f \left( x_{m} \right) \right) \right) + g \left( \left\| f \right\| \right)
L ( f ) := c ( ( x 1 , y 1 , f ( x 1 ) ) , ⋯ , ( x m , y m , f ( x m ) ) ) + g ( ∥ f ∥ ) H k H_{k} H k ノルム ∥ ⋅ ∥ \left\| \cdot \right\| ∥ ⋅ ∥ k k k positive Definiteness によって次のように与えられる。
∥ ∑ i = 1 ∞ β i k ( ⋅ , z i ) ∥ 2 : = ∑ i = 1 ∞ ∑ j = 1 ∞ β i β j k ( z i , z j ) ≥ 0
\left\| \sum_{i=1}^{\infty} \beta_{i} k \left( \cdot , z_{i} \right) \right\|^{2} := \sum_{i=1}^{\infty} \sum_{j=1}^{\infty} \beta_{i} \beta_{j} k \left( z_{i} , z_{j} \right) \ge 0
i = 1 ∑ ∞ β i k ( ⋅ , z i ) 2 := i = 1 ∑ ∞ j = 1 ∑ ∞ β i β j k ( z i , z j ) ≥ 0
R \mathbb{R} R 実数の集合 であり、R ‾ \overline{\mathbb{R}} R ∞ \infty ∞ 拡張実数 である。R X \mathbb{R}^{X} R X X X X R \mathbb{R} R 関数 を集めた関数空間 である。レギュライザー とは、データに対する過学習 を防ぐためのペナルティpenalty 関数である。汎関数 とは、ざっくり言えば関数自体をインプットとして受け取る関数のことである。ノンパラメトリックnonparametric L ( f ) L (f) L ( f ) f ∈ F f \in \mathcal{F} f ∈ F { α i } i = 1 m ⊂ R \left\{ \alpha_{i} \right\}_{i=1}^{m} \subset \mathbb{R} { α i } i = 1 m ⊂ R f ( ⋅ ) = ∑ i = 1 m α i k ( ⋅ , x i )
f (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right)
f ( ⋅ ) = i = 1 ∑ m α i k ( ⋅ , x i )
セミパラメトリックsemiparametric X X X { ψ p : X → R } p = 1 M \left\{ \psi_{p} : X \to \mathbb{R} \right\}_{p=1}^{M} { ψ p : X → R } p = 1 M 行列 ( ψ p ( x i ) ) i p \left( \psi_{p} \left( x_{i} \right) \right)_{ip} ( ψ p ( x i ) ) i p ランク が M M M f ∈ F f \in \mathcal{F} f ∈ F h ∈ span { ψ p } h \in \span \left\{ \psi_{p} \right\} h ∈ span { ψ p } c ( ( x 1 , y 1 , f ~ ( x 1 ) ) , ⋯ , ( x m , y m , f ~ ( x m ) ) ) + g ( ∥ f ∥ )
c \left( \left( x_{1}, y_{1}, \tilde{f} \left( x_{1} \right) \right) , \cdots , \left( x_{m}, y_{m}, \tilde{f} \left( x_{m} \right) \right) \right) + g \left( \left\| f \right\| \right)
c ( ( x 1 , y 1 , f ~ ( x 1 ) ) , ⋯ , ( x m , y m , f ~ ( x m ) ) ) + g ( ∥ f ∥ ) f ~ = f + h \tilde{f} = f + h f ~ = f + h { α i } i = 1 m , { β p } p = 1 M ⊂ R \left\{ \alpha_{i} \right\}_{i=1}^{m}, \left\{ \beta_{p} \right\}_{p=1}^{M} \subset \mathbb{R} { α i } i = 1 m , { β p } p = 1 M ⊂ R f ~ ( ⋅ ) = ∑ i = 1 m α i k ( ⋅ , x i ) + ∑ p = 1 M β p ψ p ( ⋅ )
\tilde{f} (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right) + \sum_{p=1}^{M} \beta_{p} \psi_{p} (\cdot)
f ~ ( ⋅ ) = i = 1 ∑ m α i k ( ⋅ , x i ) + p = 1 ∑ M β p ψ p ( ⋅ )
説明 可能であれば、以下の二つのポストを先に読むことをお勧めする:
表現者 表現者定理 representer theorem は、古典的な機械学習 、特にサポートベクターマシン の文脈で最も重要な定理の一つとして、与えられたデータに対して私たちが近似しようとしている目的関数 f f f カーネル k k k f ( ⋅ ) = ∑ i = 1 m α i k ( ⋅ , x i )
f (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right)
f ( ⋅ ) = i = 1 ∑ m α i k ( ⋅ , x i ) x i x_{i} x i k ( ⋅ , x i ) = ϕ ( x i ) ( ⋅ ) ∈ H k
k \left( \cdot , x_{i} \right) = \phi \left( x_{i} \right) (\cdot)\in H_{k}
k ( ⋅ , x i ) = ϕ ( x i ) ( ⋅ ) ∈ H k representer と呼ぶ。これにより、表現者定理は「再生カーネルヒルベルト空間 で学習データに適合したfitted 任意の関数は、表現者たちの有限な線形結合 で表すことができる」と要約することができる。特に、非線形回帰のためのサポートベクターマシンのカーネルトリックは、これに正確に合致している。
データサイエンスの文脈では、表現者 ϕ ( x i ) ( ⋅ ) \phi \left( x_{i} \right) (\cdot) ϕ ( x i ) ( ⋅ ) feature Map とも呼ばれ、任意のデータ X X X feature を知ることができるヒルベルト空間 に移し、その有限な和で私たちが求める関数を表現できるということは、これまで私たちが学んできた多くの機械学習技術がなぜ機能してきたのかを正当化する。もちろん、数学的な保証がなく
てもそれらの技術はそれ自体で有効であるが、表現者定理があることで、それらの技術が理論的な基盤を築くことになるという点で非常に重要である。
目的関数とレギュライザー 定理のステートメントでは、目的関数 c c c g g g c c c f f f 平均残差二乗 、つまり
c = 1 m ∑ i = 1 n ( y i − f ( x i ) ) 2
c = {{ 1 } \over { m }} \sum_{i=1}^{n} \left( y_{i} - f \left( x_{i} \right) \right)^{2}
c = m 1 i = 1 ∑ n ( y i − f ( x i ) ) 2 g g g セミノルム ペナルティ g ( ∥ f ∥ ) = λ ∥ f ∥ 2 g \left( \left\| f \right\| \right) = \lambda \left\| f \right\|^{2} g ( ∥ f ∥ ) = λ ∥ f ∥ 2
注意すべき点は、この式の形や単語の意味だけを見て目的関数とレギュライザーを区別してはいけないということである。表現者定理の最も代表的な応用がサポートベクターマシンであるが、ソフトマージンを許容するソフトマージンSVM で扱う最小化問題 は次のようである。
Minimize 1 2 ∥ w ∥ 2 2 + λ ∑ k = 1 n ξ k subject to ∣ f ( x k ) ∣ ≥ 1 − ξ k ξ k ≥ 0 k = 1 , ⋯ , n
\begin{matrix}
\text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} + \lambda \sum_{k=1}^{n} \xi_{k}
\\ \text{subject to} & \left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 - \xi_{k}
\\ & \xi_{k} \ge 0
\end{matrix}
\\ k = 1, \cdots , n
Minimize subject to 2 1 ∥ w ∥ 2 2 + λ ∑ k = 1 n ξ k ∣ f ( x k ) ∣ ≥ 1 − ξ k ξ k ≥ 0 k = 1 , ⋯ , n
ここで、最適化自体だけを考えた場合、目的関数は実際には
1 2 λ ∥ w ∥ 2 2 + ∑ k = 1 n ξ k
{{ 1 } \over { 2 \lambda }} \left\| \mathbf{w} \right\|_{2}^{2} + \sum_{k=1}^{n} \xi_{k}
2 λ 1 ∥ w ∥ 2 2 + k = 1 ∑ n ξ k ∑ k = 1 n ξ k \sum_{k=1}^{n} \xi_{k} ∑ k = 1 n ξ k c c c f ( x ) = w T + b f (\mathbf{x}) = \mathbf{w}^{T} + b f ( x ) = w T + b 1 2 λ ∥ w ∥ 2 2 {{ 1 } \over { 2 \lambda }} \left\| \mathbf{w} \right\|_{2}^{2} 2 λ 1 ∥ w ∥ 2 2 g g g
数学の色が強い人はSVMを「まず線形回帰 を終えてから例外を設けるもの」と見なし、∥ w ∥ 2 2 \left\| \mathbf{w} \right\|_{2}^{2} ∥ w ∥ 2 2 データサイエンスの色が強い人はSVMを「まずデータをうまく分類し、その中で最もマージンの大きな超平面 を見つけるもの」と見なし、∑ k = 1 n ξ k \sum_{k=1}^{n} \xi_{k} ∑ k = 1 n ξ k どちらの視点も十分に共感できるものであり、表現者定理の応用がSVMだけでないことを考えると、ここでは暗記術のようなものを探そうとせず、問題に応じて能動的に考え受け入れる必要がある。
証明 参考文献にあるように、ノンパラメトリック表現者定理 のみを証明する。
Part 1. f = ∑ i = 1 m α i ϕ ( x i ) + v f = \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v f = ∑ i = 1 m α i ϕ ( x i ) + v
再生カーネルの定義 : 関数 k : X × X → C k : X \times X \to \mathbb{C} k : X × X → C H H H 再生カーネル reproducing Kernel と言う。
(i): 表現者 representer : すべての x ∈ X x \in X x ∈ X k ( ⋅ , x ) ∈ H
k \left( \cdot , x \right) \in H
k ( ⋅ , x ) ∈ H (ii) 再生性質 reproducing Property : すべての x ∈ X x \in X x ∈ X f ∈ H f \in H f ∈ H < f , k ( ⋅ , x ) > = f ( x ) = δ x ( f )
\left< f , k \left( \cdot , x \right) \right> = f(x) = \delta_{x} (f)
⟨ f , k ( ⋅ , x ) ⟩ = f ( x ) = δ x ( f ) x 1 , x 2 ∈ X x_{1} , x_{2} \in X x 1 , x 2 ∈ X k ( x 1 , x 2 ) = < k ( ⋅ , x 2 ) , k ( ⋅ , x 1 ) >
k \left( x_{1} , x_{2} \right) = \left< k \left( \cdot , x_{2} \right), k \left( \cdot , x_{1} \right) \right>
k ( x 1 , x 2 ) = ⟨ k ( ⋅ , x 2 ) , k ( ⋅ , x 1 ) ⟩ 再生カーネル k : X × X → R k : X \times X \to \mathbb{R} k : X × X → R x ↦ k ( ⋅ , x ) x \mapsto k (\cdot ,x) x ↦ k ( ⋅ , x ) ϕ : X → R X \phi : X \to \mathbb{R}^{X} ϕ : X → R X k k k x ′ ∈ X x' \in X x ′ ∈ X ( ϕ ( x ) ) ( ⋅ ) \left( \phi (x) \right) (\cdot) ( ϕ ( x ) ) ( ⋅ ) x , x ′ ∈ X x, x' \in X x , x ′ ∈ X ( ϕ ( x ) ) ( x ′ ) = k ( x ′ , x ) = < ϕ ( x ′ ) , ϕ ( x ) >
\left( \phi (x) \right) (x ') = k \left( x' , x \right) = \left< \phi \left( x ' \right) , \phi (x) \right>
( ϕ ( x ) ) ( x ′ ) = k ( x ′ , x ) = ⟨ ϕ ( x ′ ) , ϕ ( x ) ⟩ < ⋅ , ⋅ > \left< \cdot , \cdot \right> ⟨ ⋅ , ⋅ ⟩ H k H_{k} H k 内積 である。与えられた { x i } i = 1 m \left\{ x_{i} \right\}_{i=1}^{m} { x i } i = 1 m f ∈ F f \in \mathcal{F} f ∈ F span { ϕ ( x i ) } i = 1 m \span \left\{ \phi \left( x_{i} \right) \right\}_{i=1}^{m} span { ϕ ( x i ) } i = 1 m 直交 するすべての j j j < v , ϕ ( x j ) > = 0
\left< v , \phi \left( x_{j} \right) \right> = 0
⟨ v , ϕ ( x j ) ⟩ = 0 v ∈ F v \in \mathcal{F} v ∈ F ( α 1 , ⋯ , α m ) ⊂ R m \left( \alpha_{1} , \cdots , \alpha_{m} \right) \subset \mathbb{R}^{m} ( α 1 , ⋯ , α m ) ⊂ R m f = ∑ i = 1 m α i ϕ ( x i ) + v
f = \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v
f = i = 1 ∑ m α i ϕ ( x i ) + v L ( f ) : = c ( ( x 1 , y 1 , f ( x 1 ) ) , ⋯ , ( x m , y m , f ( x m ) ) ) + g ( ∥ f ∥ ) = c + g
\begin{align*}
L (f) :=& c \left( \left( x_{1}, y_{1}, f \left( x_{1} \right) \right), \cdots , \left( x_{m}, y_{m}, f \left( x_{m} \right) \right) \right) + g \left( \left\| f \right\| \right)
\\ =& c + g
\end{align*}
L ( f ) := = c ( ( x 1 , y 1 , f ( x 1 ) ) , ⋯ , ( x m , y m , f ( x m ) ) ) + g ( ∥ f ∥ ) c + g c c c v v v v = 0 v = 0 v = 0 f f f L ( f ) L(f) L ( f )
Part 2. c c c v v v
関数 f = f ( ⋅ ) f = f(\cdot) f = f ( ⋅ ) k ( ⋅ , x j ) k \left( \cdot , x_{j} \right) k ( ⋅ , x j ) = < f , k ( ⋅ , x j ) > f ( x j ) = < ∑ i = 1 m α i ϕ ( x i ) + v , ϕ ( x j ) > = ∑ i = 1 m α i < ϕ ( x i ) , ϕ ( x j ) > + 0
\begin{align*}
=& \left< f , k \left( \cdot , x_{j} \right) \right>
\\ f \left( x_{j} \right) =& \left< \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v , \phi \left( x_{j} \right) \right>
\\ =& \sum_{i=1}^{m} \alpha_{i} \left< \phi \left( x_{i} \right) , \phi \left( x_{j} \right) \right> + 0
\end{align*}
= f ( x j ) = = ⟨ f , k ( ⋅ , x j ) ⟩ ⟨ i = 1 ∑ m α i ϕ ( x i ) + v , ϕ ( x j ) ⟩ i = 1 ∑ m α i ⟨ ϕ ( x i ) , ϕ ( x j ) ⟩ + 0 v v v L ( f ) = c + g L (f) = c + g L ( f ) = c + g D D D f f f c = c ( ( x 1 , y 1 , f ( x 1 ) ) , ⋯ , ( x m , y m , f ( x m ) ) )
c = c \left( \left( x_{1}, y_{1}, f \left( x_{1} \right) \right), \cdots , \left( x_{m}, y_{m}, f \left( x_{m} \right) \right) \right)
c = c ( ( x 1 , y 1 , f ( x 1 ) ) , ⋯ , ( x m , y m , f ( x m ) ) ) v v v
Part 3. g g g v = 0 v = 0 v = 0
(1): v v v ∑ i = 1 m α i ϕ ( x i ) \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) ∑ i = 1 m α i ϕ ( x i ) (2): g g g 単調関数 であると仮定したため、 g ( ∥ f ∥ ) = g ( ∥ ∑ i = 1 m α i ϕ ( x i ) + v ∥ ) = g ( ∥ ∑ i = 1 m α i ϕ ( x i ) + v ∥ 2 + ∥ v ∥ 2 ) ∵ ( 1 ) ≥ g ( ∥ ∑ i = 1 m α i ϕ ( x i ) ∥ ) ∵ ( 2 )
\begin{align*}
& g \left( \left\| f \right\| \right)
\\ =& g \left( \left\| \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v \right\| \right)
\\ =& g \left( \sqrt{\left\| \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v \right\|^{2} + \left\| v \right\|^{2}} \right) & \because (1)
\\ \ge& g \left( \left\| \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) \right\| \right) & \because (2)
\end{align*}
= = ≥ g ( ∥ f ∥ ) g ( i = 1 ∑ m α i ϕ ( x i ) + v ) g i = 1 ∑ m α i ϕ ( x i ) + v 2 + ∥ v ∥ 2 g ( i = 1 ∑ m α i ϕ ( x i ) ) ∵ ( 1 ) ∵ ( 2 ) v = 0 v = 0 v = 0 g g g v = 0 v=0 v = 0 v v v c c c v = 0 v = 0 v = 0 L = c + g L = c + g L = c + g 関数 f f f f ( ⋅ ) = ∑ i = 1 m α i k ( ⋅ , x i )
f (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right)
f ( ⋅ ) = i = 1 ∑ m α i k ( ⋅ , x i )
■
