カーネル法
非線形データに対する多変数解析の一種であるカーネル法の、主に数理面について勉強したことをまとめたノート(忘備録)です。
目次 [Contents]
- 概要
- 正定値カーネル
- 再生核ヒルベルト空間
- 正則化とカーネル法
- 正定値カーネルの理論
- 各種カーネル法
- 補足事項
- 参考文献
■ 概要
カーネル法は、非線形データに対する多変量解析の手法の1つであるが、その特徴としては、非線形データを正定値カーネルの形に応じて定まる再生核ヒルベルト空間上の線形データに持ち込んで解析する点にある。
ここでは、以下のような観点からカーネル法全体の概要を見ている。
◎ 特徴写像と再生核ヒルベルト空間
左上図のように、データの分布が線形でない場合において、例えば、2クラスの識別問題などに対する有限次元のユークリッド空間上での線形なデータ解析手法はうまくいかない。
このような場合、右上図のように、データをより高次元の空間に持ち込み、その空間上で線形なデータ解析手法を適用するという解決策が考えられる。
カーネル法では、このようなデータをより高次元の空間に持ち込む写像を特徴写像として定式化し、特徴写像の写像先である高次元の特徴空間を、一般的かつ汎用的な枠組みで扱えるように内積が定義された無限次元空間である再生核ヒルベルト空間として定式化する。
(※再生核ヒルベルトでは、更に、再生性の条件が成り立つが、これは、後述のカーネルトリック、及び、リプリゼンター定理を適用できるために必要な性質となっている。)
詳細は、再生核ヒルベルト空間 に記載
◎ カーネルトリック
カーネル法では、特徴写像 Φ により、ユークリッド空間上のデータをより高次元の特徴空間へ写像するが、この際に、ユークリッド空間上の2つのデータの類似性を表すカーネル関数 k は、特徴空間内の2つの特徴ベクトルの内積、即ち、 によって定まる。
従って、特徴空間での特徴ベクトルの内積を計算したい場合(例えば、データ解析手法において共分散分散行列を計算したい場合など)において、特徴空間の次数に依存して膨大になる特徴ベクトルの内積計算ではなく、正定値カーネルで直接計算することができる。
このような計算量の大幅削減テクニックをカーネルトリックという。
尚、このカーネルトリックの元になる 関係は、カーネル関数が正定値カーネルであることと、再生核ヒルベルト空間における再生性の条件、及び、Moore - Aronszajn の定理からの帰着から得られる。
詳細は、正定値カーネル、再生核ヒルベルト空間、 特徴写像とカーネルトリック(Moore - Aronszajn の定理からの帰着) に記載
◎ リプレゼンター定理
特徴写像の写像先である再生核ヒルベルト空間内で、各種データ解析手法で線形解析を行う際に、再生核ヒルベルト空間が無限次元空間であるために、実際上には、計算機で計算不可能であるという問題がある。
このような問題は、リプレゼンター定理により解決できる。
即ち、この無限次元である再生核ヒルベルト空間内での最適化問題は、データの張る有限次元部分空間の中での最適化問題に帰着できる。
詳細は、リプレゼンター定理 に記載
◎ カーネル法を利用した各種データ解析手法に共通する手順
カーネル法を利用したデータ解析手法には、サポートベクターマシン、カーネル主成分分析など様々な手法が存在するが、いずれもその基本的なコンセプトに一貫した3つの共通ポイントが見られる。
- 1つ目のポイントは、ユークリッド空間上での線形解析手法を特徴写像により再生核ヒルベルト空間に持ち込み、その再生核ヒルベルト空間上で線形解析手法を適用することで、ユークリッド空間では線形分離不可能であった問題を、線形分離可能な問題に落とし込むいう点である。
- 2つ目のポイントは、この再生核ヒルベルト空間上での線形解析手法を適用する際に、再生核ヒルベルト空間が無限次元空間であるが故に、実際上計算機で計算不可能な問題が発生するが、リプレゼンター定理により、データより張られる有限次元部分空間上でのデータ解析手法に置き換えるという点である。
- 3つ目のポイントは、このリプレゼンター定理により有限次元化されたデータ解析手法において、分散共分散行列などの計算で内積演算が必要になるケースが多々あるが、この再生核ヒルベルト空間上での内積演算を2つの特徴ベクトルの内積を計算することなく、カーネル関数で直接計算出来るという、カーネルトリックを用いて、計算負荷を削減する点にある。
■ 正定値カーネル
カーネル関数は、2つのデータ の類似度を表す関数であるが、概要のカーネルトリックの説明で見たような2つの特徴ベクトルの内積で記述できるカーネル関数 は、カーネル関数の内、特に、対象性と正値性を兼ね備えた正定値カーネルと呼ばれるものになる。
◎ 実数の正定値カーネル
◎ 複素数の正定値カーネル
実数ではなく複素数で扱うことにより、理論を展開する上での見通しがよくなることがあるが、これは正定値カーネルに関しても同様である。(例えば、後述の Bochner の定理など)
そのため、複素数の正定値カーネルなるものを定義する。
ここで、複素数の正定値カーネルでは実数の正定値カーネルとは異なり、
(実数の正定値カーネルのときの)対称性の条件 にあたるエルミート性の条件 は不要となる。
これは、エルミート性が正定値性の帰着として導かれるためである。
そのことを以下に示す。
任意の1点 に対する正定値性は、
より非負の実数である。
又、任意の2点 l と複素数定数 に対する正定値性は、
この式の複素数部分に対して、その複素共役を取ると、
両式の差をとると、
◎ 正定値カーネルの基本的な性質
次に、この正定値カーネルに関して成り立つ基本的な性質をいくつか見てみる。
- (証明略)
◎ 関数の内積で表現される正定値カーネル
以下の定理で示すように、内積空間上での関数の内積は、正定値カーネルになる。
- (証明)
正定値性を示すために、正定値性の条件
の左辺に を代入すると、
ノルムの2乗は必ず正になるので、
の関係が成り立ち、
が、正定値カーネルになることがわかる。
◎ 正定値カーネルの例
m 次元ユークリッド空間 上で定義されるいくつかの正定値カーネルの例を見ていく。
☆ 線形カーネル(=通常のユークリッド空間上での内積)
ここで、このカーネルが、確かに正定値カーネルになることを示す。
この線形カーネルは、先の関数の内積で表現される正定値カーネル より、明らかに正定値カーネルであることが分かる。
☆ 指数型カーネル
ここで、このカーネルが、確かに正定値カーネルになることを示す。
この指数型カーネルを、Tayler 展開すると、
先の正定値カーネルの性質(カーネル線形結合、カーネルの積)より、この展開式の各項の点列
の和もまた正定値カーネルとなる。
更に、 は、この点列の極限となるが、
先の正定値カーネルの性質(カーネルの点列の極限)より、この指数型カーネル は、正定値カーネルであることが分かる。
☆ 動径基底関数カーネル(RBFカーネル)[radial bases function kernel]
ここで、上式のパラメータ σ は、関数の広がりを制御するパラメータである。
ここで、この RBF カーネル関数を、例えば、SVM(サポートベクターマシン)に適用した場合、このカーネル関数の制御パラメータ σ に関して、一般的に、以下のような関係が成り立つ。
- 制御パラメータ σ が大きい
⇒ 写像後の特徴ベクトルが離れた位置に写像される
⇒ 入力データ(特徴ベクトル)から離れている広範囲のサポートベクトルが識別関数に寄与する。 - 制御パラメータ σ が小さい
⇒ 写像後の特徴ベクトルが近い位置に写像される
⇒ 入力データ(特徴ベクトル)近傍のサポートベクトルが識別関数に寄与する。
ここで、このカーネルが、確かに正定値カーネルになることを示す。
この RBF カーネルを変形すると、
となるが、先の指数型カーネル が正定値カーネルであったことを利用すると、
正定値カーネルの性質より、この RBF カーネルも正定値カーネルであることが分かる。
☆ ラプラスカーネル
☆ 多項式カーネル
この関数は、例えば d=2 で、c=1 の場合、
上式の のみ依存する項目を、
のように分離すると、多項式カーネルを
の様な6次元の内積演算の形となる。
即ち、逆に言い換えれば、
6次元空間でのベクトルの内積演算 が、
先の2次元ベクトルの内積とスカラー積
の計算で出来ることになる。⇒ 計算量を削減出来る。
次に、(次数が)一般の場合 d では、
多項式カーネル を2項定理を用いて展開すると、
即ち、多項数カーネルの使用した時の2つのベクトル の次元(次数)の上限は ∑ の形で求めることが出来る。
■ 再生核ヒルベルト空間
概要でみたように、カーネル法では特徴空間を再生核ヒルベルト空間で定式化する。
一見すると、特徴空間では、内積構造が備わっている完備な無限次元空間、即ち、ヒルベルト空間で定式化すれば十分であるように思えるが、カーネルトリックの元になる関係式 、及び、リプリゼンター定理が成り立つための要件として、再生核ヒルベルト空間における再生性の条件が必要になるので、再生核ヒルベルト空間で定式化する。
(※尚、ただの高次元空間ではなく無限次元空間で定式化するのは、一般性や汎用性を確保するため)
【Memo】
この定義単体だけでは、再生核ヒルベルト空間の意味は分かりにくいが、後述の 再生核ヒルベルト空間の線形汎関数を用いた特徴付けと Moore-Aronszajn の定理まで飛ばして見てみれば、その幾何学的な意味を理解しやすい。
- 【参考】
◎ 再生核の性質
- (証明)
正定値カーネルの対称性 やエルミート性 を利用すると、
2つの再生核 に対して、再生性の条件より、
の関係より、この2つの再生核は同一であるので、再生核は一意に存在することが分かる。
☆ 再生核のテンソル積
再生核のテンソル積が、また再生核になることを示すために、まず、再生核ヒルベルト空間のテンソル積なるものを定義する。
◎ 再生核ヒルベルト空間の線形汎関数を用いた特徴付けとリースの表現定理
- (証明)
リースの表現定理より、線形汎関数が連続(=有界)であるならば、
ヒルベルト空間上の要素(関数)g∈H が存在して、任意のヒルベルト空間上の要素(関数)∀f∈H に対して、有界線形汎関数は内積で表現出来る。即ち、
と表現できる。
従って、この中に、L(f) が f(x) となるような が存在し、
の関係が成り立つ。
【メモ】
再生性の条件 と、リースの表現定理の内積表現 が対応していることに注目。
- 【参考】
◎ Moore-Aronszajn の定理
先の再生核ヒルベルト空間の線形汎関数を用いた特徴付けと、
Moore-Aronszajn の定理より、再生核ヒルベルト空間を再解釈(=特徴付け)したのが以下の図である。
正定値カーネルが、再生核ヒルベルト空間の基底になっており、それを元に再生核ヒルベルト空間が構築されていることと、再生性の条件 が、元のベクトル空間での入力値の写像後の値に対応している点がポイントである。
☆ 特徴写像とカーネルトリック(Moore - Aronszajn の定理からの帰着)
特徴写像 Φ は、集合 X から再生核ヒルベルト空間への写像 である。
このとき、Moore - Aronszajn の定理より、正定値カーネルの組 を基底として張られる空間は、再生核ヒルベルト空間になるので、再生核ヒルベルト空間上の任意の2つの要素(関数)∀f,g ∈H の内積は、
従って、
となり、カーネルトリックの元になる関係式が成り立っていることが分かる。
つまり、カーネルトリックは、Moore - Aronszajn の定理からの帰着で導かれる。
◎ 再生核ヒルベルト空間の具体的な構成
先の Moore-Aronszanの定理より、正定値カーネルにより、再生核ヒルベルト空間の基底が定まり、再生核ヒルベルト空間が構成されることを見てきたが、ここでは、具体的に、幾何学的に表現が可能な場合の再生核ヒルベルト空間を見ていく。
☆ 線形カーネルの再生核ヒルベルト空間
- (証明)
線形カーネルは、先に示したように正定値カーネルである。
又、Moore-Aronszanの定理より、再生核ヒルベルト空間の任意の要素(関数)f∈H は、線形写像である線形カーネルを基底とする線形結合
で表現できるので、
この再生核ヒルベルト空間中の任意の要素 f もまた線形写像であることが分かる。
更に、この再生核ヒルベルト空間中の任意の2つの要素(=関数)∀f,g∈H の内積は、
となり、ユークリッド空間の内積そのものとなるので、
この線形カーネルによる再生核ヒルベルト空間は、ユークリッド空間そのものであることが分かる。
尚、カーネル PCA の手法においては、この線形カーネルを用いることにより、
主成分が非線形になるようなデータに対し、(より高次元空間の再生核ヒルベルト空間における)線形な通常の主成分分析に落とし込むことを実現している。(詳細は後述)
☆ 有限集合上の(エルミート行列の)再生核ヒルベルト空間
- (証明略)証明の方針のみ記載
内積が再生性の条件を満たすことを示せばよい。
即ち、例えば、エルミート行列 K の第 i 行である に対して、
を示せばよい。
☆ 多項式カーネルの再生核ヒルベルト空間
- (証明略)
◎ 埋め込み写像による再生核ヒルベルト空間の構成
再生核ヒルベルト空間を、他の一般的な関数空間(例えば、ヒルベルト空間)の部分空間として構成する一般的な方法に、関数空間へのヒルベルト空間の埋め込み写像(=ヒルベルト埋め込み写像)による構成方法が存在する。
ここで議論する、ヒルベルト埋め込み写像による再生核ヒルベルト空間の構成と再生核ヒルベルト空間のフーリエ変換による表示の大まかな話の流れは、以下のようになる。
- 埋め込み写像とは、数学的な構造を保ちながら、写像元より一般的で広い空間の部分空間に埋め込むような写像(例えば、2次元ユークリッド空間の3次元ユークリッド空間への埋め込み。正数の実数への埋め込みなど)であるが、
- 可測関数を基底ベクトルとするL2空間の部分空間を、より一般的な関数空間(例えば、ヒルベルト空間)の部分空間として埋め込むような埋め込み写像を考えると、この埋め込んだ部分空間は、再生核ヒルベルト空間になり、その具体的な表示が得られる。(内積は、写像元のL2空間での内積で定義。再生核は、写像元のL2空間での再生性を経由して得られる)
言い換えると、埋め込み写像により、再生核ヒルベルト空間を他の一般的な関数空間(例えば、ヒルベルト空間)の部分空間として実現できる。 - 次に、この可測関数として、 の形を採用すると、埋め込み写像がフーリエ変換の形となる。(=埋め込み写像の1つの具体的な例が、フーリエ変換となる)
そして、先の議論と同様にして、このフーリエ変換の形をした埋め込み写像により、部分空間としての再生核ヒルベルト空間の具体的表示が得られる。 - 最後に、このフーリエ変換の形をした埋め込み写像により得られる再生核ヒルベルト空間の具体的な表示を構成する確率密度関数に、各々の正定値カーネル(RBFカーネル等)の確率密度関数の式を適用すると、各々の正定値カーネル(RBFカーネル等)の再生核ヒルベルト空間のフーリエ変換による表示が得られる。
この定理の内容を、解釈図とともに簡潔にまとめると、以下のようになる。
【Memo】埋め込み写像
数学的な構造を保ちながら、写像元より一般的で広い空間の部分空間に埋め込むような写像。
例えば、以下のような埋め込みは、埋め込み写像である。
- 例1(図形):平面(2次元ユークリッド空間)は立体的空間(3次元ユークリッド空間)への埋め込み。
- 例2(図形):球面や球体の、立体的空間への埋め込み。
- 例3(数):整数の有理数への埋め込み。
- 例4(集合):集合 X の部分集合 A の、X への埋め込み。
☆ フーリエ変換の形をした埋め込み写像による再生核ヒルベルト空間の構成
次に、この埋め込み写像がフーリエ変換によって与えられることを見ていく。
この定理の内容を、簡潔にまとめると、以下のようになる。
この定理(フーリエ変換の形をした埋め込み写像による再生核ヒルベルト空間の構成)を用いれば、各々の正定値カーネル(RBFカーネル等)に対しての再生核ヒルベルトのフーリエ変換での具体的な表示を得ることが出来る。
☆ RBF カーネルの再生核ヒルベルト空間
先の定理(フーリエ変換の形をした埋め込み写像による再生核ヒルベルト空間の構成)の密度関数に対して、正定値カーネルの1つの例として、RBFカーネルの確率密度関数の式を代入するとこで、RBFカーネルの再生核ヒルベルトのフーリエ変換での具体的な表示を得ることが出来る。
RBFカーネルの確率密度関数 を以下のように定める。
これを先のフーリエ変換での再生核ヒルベルトの具体的な表示の式に代入すると、
RBFカーネルの再生核ヒルベルト空間の具体的な形は、
同様にして、内積は、
又、再生核は、
となる。
即ち、埋め込み写像により定まる再生核ヒルベルト空間は、RBFカーネルの定める再生核ヒルベルト空間に一致することが分かる。
そして、このRBFカーネルの再生核ヒルベルト空間の具体的な表示
より、このRFBカーネルの再生核ヒルベルト空間に含まれる関数(=再生核ヒルベルト空間の要素)は、周波数領域で指数関数的に減衰するものに限られることも分かる。
尚、後述の Bochner の定理からも、RBF カーネルが正定値カーネルであることを導くことが出来る。
☆ ラプラスカーネルの再生核ヒルベルト空間
同様にして、先の定理(フーリエ変換の形をした埋め込み写像による再生核ヒルベルト空間の構成)の密度関数に対して、正定値カーネルの1つの例として、ラプラスカーネルの確率密度関数の式を代入するとこで、ラプラスカーネルの再生核ヒルベルトのフーリエ変換での具体的な表示を得ることが出来る。
ラプラスカーネルの確率密度関数 を、以下のように定める。
これを先のフーリエ変換での再生核ヒルベルトの具体的な表示の式に代入すると、
ラプラスカーネルの再生核ヒルベルト空間の具体的な形は、
同様にして、内積は、
又、再生核は、
となる。
即ち、埋め込み写像により定まる再生核ヒルベルト空間は、ラプラスカーネルの定める再生核ヒルベルト空間に一致することが分かる。
そして、このラプラスカーネルの再生核ヒルベルト空間の具体的な表示
より、このラプラスカーネルの再生核ヒルベルト空間に含まれる関数(=再生核ヒルベルト空間の要素)は、先のRBFカーネルと比べて、周波数領域(=波数)でより緩やかに減衰するものに限られることも分かる。
尚、後述の Bochner の定理からも、ラプラスカーネルが正定値カーネルであることを導くことが出来る。
■ 正則化とカーネル法
機械学習における(損失関数の)正則化は、主に、汎化性能を向上させ、過学習を抑制するために行われる手法の1つであるが、カーネル法における正則化は、この汎化性能の向上の目的だけではなく、後述のリプリゼンター定理によって、無限次元である再生核ヒルベルト空間内でのモデルをカーネル関数の有限次元での線形結合のモデルに限定するという別の大きな目的がある。
☆ リプレゼンター定理
以下、この無限次元である再生核ヒルベルト空間内でのモデルをカーネル関数の有限次元での線形結合のモデルに限定するリプリゼンター定理を導く。
まず、与えられたデータ に対して、最適化問題の解を再生核ヒルベルト空間中の関数 とするような、以下のような最適化問題を考える。
ここで、L は任意の損失関数で、 は、与えられたデータ と再生核ヒルベルト空間中の関数 に依存するという意味。
又、 は、以下の図のように、最適化問題のL2正則化項となっている。(λは、正則化パラメータ)
(※図では、 で対応)
この最適化問題をより一般化して、以下のような最適化問題を考える。
このような最適化問題は、再生核ヒルベルト空間内での最適化問題なので、無限次元空間での最適化問題になっているために、現実的に計算機での計算が困難であるように思える。
しかしながら、以下のリプリゼンター定理により、このような無限次元空間である再生核ヒルベルト空間での最適化問題が、再生核ヒルベルト空間の再生性を用いることで、有限次元での最適化問題に置き換えられるので、計算可能な最適化問題となる。
- (証明)
- 級数展開の式
において、基底となる正定値カーネル の組より生成される有限次元の部分空間
とその直交補空間 を用いて、
再生核ヒルベルト空間は、
のように表現できる。
従って、最適化問題の解である再生核ヒルベルト空間の要素(=関数)に対しても、
の関係が成り立つ。 - ここで、再生核ヒルベルト空間における再生性の条件
を考えると、
従って、 を に変更しても最適化関数 L の値は変わらず、 である。 - 更に、直交性から、
となるが、Ψ は単調増加関数なので、
- 従って、この最適化問題の min の中身は、
という関係が成り立つので、この級数展開の式
で与えられる関数 は、最適化問題の最小値を達成する解であることが分かる。
- 級数展開の式
■ 正定値カーネルの理論
ここでは、正定値カーネルの理論と称して、以下のようなトピックを取り上げる。
Schoenberg の定理を用いて、正定値カーネルや負定値カーネルから、様々な正定値カーネルを系統的に生成出来ること。
ユークリッド空間上での平行移動(アフィン変換)に対して不変な正定値カーネル全体を、その正定値カーネルのフーリエ変換により特徴づけることを主張している Bochner の定理。
正定値カーネルに対する固有値分解である Mercer の定理。
より厳密には、正定値カーネルを積分作用素のスペクトル分解によって表現する Mercer の定理。
◎ 負定値カーネル
まず、先の正定値カーネルとの対比で、負定値カーネルなるものを導入する。
以下、断り書きがない限り、負定値カーネルといえば、この複素数の負定値カーネルを表すものとする。
☆ 負定値カーネルの基本的な性質
次に、この負定値カーネルに関して成り立つ基本的な性質をいくつか見てみる。
- (証明略)負定値カーネルの定義より成り立つ。
- (証明略)正定値カーネルのときと同様
☆ 負定値カーネルの基本的な例
- (例)負定値カーネルの例
集合 X から内積空間 V への写像 に対して、
以下のような定義される関数は、集合 X 上の負定値カーネルであることを示す。
この関数に対して負定値カーネルの非負性の条件を確認すると、
従って、負正値の条件が成り立つので、この関数 ψ は負定値カーネルである。
◎ Schoenberg の定理
Schoenberg の定理は、先に導入した負定値カーネルと正定値カーネルを関連付ける定理であるが、そのための前段階として、以下の補題を示す。
- (証明)
- (証明)
- 「⇐」 の方向証明
を Tayler 展開すると、
1次の項まで採用して、変形すると、
今、 は負定値カーネルであるので、この逆符号の関数をもつ上式は、正定値カーネルとなる。
- 「⇒」 の方向の証明
先の補題(正定値カーネルと負定値カーネルの同値関係)に対応した関数
を定義すると、この関数 は正定値カーネルであるが、 この関数 に対して、exp をとった は、 ラプラスカーネル の形になるので、正定値カーネルになる。
正定値カーネル を展開すると、
ここで、一般の正定値カーネル に対して、任意の関数 f ではさみうちした関数
は、正定値カーネルとなるという関係(証明略)と対比すると、
も正定値カーネルとなることが分かる。
- 「⇐」 の方向証明
◎ カーネルを生成する操作
この Schoenberg の定理を用いて、負定値カーネル から作られる関数が、負定値カーネル or 正定値カーネルであるかを示すことが出来る。
(言い換えると、負定値カーネル から、別の負定値カーネル or 正定値カーネルを生成することが出来る。)
尚、この Schoenberg の定理を用いて、負定値カーネル から別の負定値カーネル or 正定値カーネルを生成する際には、いずれも、その関数が、 の形に変形できるかがポイントとなる。
- (証明)Schoenberg の定理を用いて証明できる。
の関係を用いると、
上式の の部分は、Scohenberg の定理より、正定値カーネルである。
更に、被積分関数部分全体 は、正定値カーネル に関しての逆符号になっているので、負定値カーネルである。
そして、積分はリーマン和の極限なので、負定値カーネルの性質(カーネルの点列の極限)より、上式も負定値カーネルである。
従って、 も負定値カーネルとなることが分かる。
- (証明)Schoenberg の定理を用いて証明できる。
先の負定値カーネルの例
において、集合 X を とすると、
に対して、先の命題(負定値カーネルの階上関数)を適用すると、
も、負定値カーネルであることが分かる。
更に、この関数に exp をとった
は、Scoenberg の定理より、正定値カーネルとなる。
- (証明)Schoenberg の定理を用いて証明できる。
を積分表示すると、
の形に展開できているので、
先の命題(負定値カーネルの階上関数)の証明と同様にして、上式の右辺の積分項は、負定値カーネルであるといえ、
は、負定値カーネルであることが分かる。
そして、
と変形できるが、負定値カーネルの性質より、 は、負定値カーネルであることが分かる。
- (証明)Schoenberg の定理を用いて証明できる。
対象関数を積分表示すると、
の形に展開できているので、
先の命題(負定値カーネルの階上関数、負定値カーネルのlog関数)の証明と同様にして、
上式の右辺の積分項は、正定値カーネルであるといえ、
は正定値カーネルであることが分かる。
◎ Bochner の定理
Bochner の定理は、ユークリッド空間上での平行移動(アフィン変換)に対して不変な正定値カーネル全体を、その正定値カーネルのフーリエ変換により特徴づけることを主張している定理である。
まず、カーネル関数の平行移動不変性、及び、そこから定義される正値とはどのようなものなのかを定義する。
このように定義した平行移動不変性、及び、正値の概念に関連して、以下の Bochner の定理が成り立つ。
- (証明略)十分条件(⇐)の証明み記載する。
このフーリエ変換の式
の積分は、これら各々の に対しての の線形結合の極限和で表せる。即ち、
ここで、正値の条件 、及び の関係より、
は正値関数となるが、
これは、先の線形結合の極限和の式の基底に対応しており、正定値カーネルの性質(線形結合もまた正定値カーネル、極限も正定値カーネル)より、この線形結合の極限和である も正値であることが分かる。
◎ Mercer(マーサー、マーセル)の定理
Mercer の定理は、正定値カーネルに対する固有値分解の定理である。
より厳密に言えば、正定値カーネルを積分作用素のスペクトル分解によって表現する定理となってる。
☆ 積分作用素、積分核
まずは、この積分作用素、積分核とはどのようなものなのかを見ていく。
☆ 積分作用素とヒルベルト=シュミット作用素
以下の定理で示すように、積分作用素は、ヒルベルト=シュミット作用素でもある。
一方、自己共役なヒルベルト=シュミット作用素は、固有値分解が可能である。(後述)
そしてこれら2つの事実が、正定値カーネルを積分作用素のスペクトル分解によって表現する Mercerの定理に結びつく。
- (証明)
まず前提として、L2空間 は、ヒルベルト空間でもあるので()、この空間上のヒルベルト=シュミット作用素なるものが導入出来る。
次に、積分核 K の2乗可積分性より、
ほとんどいたるところの x∈Ω に対して、 の関係が成り立つ。
をL2空間 の完全正規直交系とすると、
の複素共役をとった もL2空間 の完全正規直交系となるので、
☆ 積分核のヒルベルト=シュミット展開
自己共役なヒルベルト=シュミット作用素は、固有値分解可能であるという事実を、ヒルベルト=シュミット作用素である積分作用素にも適用するために、自己共役な積分作用素なるものを導入する。
積分作用素は、ヒルベルトシュミット作用素であり、
又、自己共役なヒルベルトシュミット作用素は、固有値展開可能(ヒルベルトシュミットの展開定理)であることより、自己共役な積分作用素も、以下の定理のように固有値で展開表現可能となる。
- (証明略)
更に、 ではなく においては、積分核は、以下の定理のように固有値で展開表現できる。
- (証明)
積分核 K の2乗可積分性より、
ほとんどいたるところの に対して、 の関係が成り立つ。
ここで、
の関係式より、
の関係が成り立つが、更に、
となるので、測度 μ に関して、ほとんどいたるところの に対して、
というL2空間 におけるフーリエ展開の関係が成り立つ。
次に、この展開式の i=1~N までの項をとった展開式 及び の収束性について調べる。
フビニの定理より、
の関係が成り立つが、右辺の被積分関数(赤字部分)は、先のフーリエ展開の式より、ほとんどいたるところの に関して、N→∞ で0に収束する。
更に、
のように、N に依存しない被積分関数 で上限を定められるので、ルベーグの収束定理より、先のフビニの定理からの式が、N→∞ で0に収束する。
従って、青字部分の N を ∞ にした展開式
が成り立つことが分かる。
☆ 正値積分核(Mercer核)と Mercer の定理
次に、前段階として、測度の台の概念を導入する。
以下の定理は、ハウスドルフ空間上のラドン測度上のカーネル関数を元にした作用素が、正値作用素となることを述べたものであり、この定理と先の積分作用素の正値性の定義と組合わせ、更にヒルベルト=シュミット作用素が積分作用素でもある事実を利用することで、積分作用素の固有値の正値性が示せ、最終的に Mercer の定理に結びつく。
- (証明)
- 「⇒」方向の証明
は正定値カーネルであるので、
ハウスドルフ空間 Ω 上の任意の連続関数 ∀g∈Ω と、ハウスドルフ空間 Ω の分割された可測集合 を考えると、
の関係が成り立つ。
積分作用素 の正値性の条件式の積分
は、この和の極限として与えるものになっているので、非負である。即ち、
となり、積分作用素 は、正値作用素となることが分かる。
※ 尚、今の場合、ハウスドルフ空間 Ω 上の連続関数 ∀g∈Ω で考えて、 と積分作用素の正値性の条件 を対応付けたが、より厳密には、 において、任意の ε>0 に対して、 となるような連続関数 g∈Ω を考え、積分作用素の正値性の条件 を対応付ければよい。
- 「⇐」方向の証明
背理法で示す。
- 「⇒」方向の証明
この定理(カーネル関数と正値作用素)と先の定義(正値積分核)と組合わせる。
具体例には、
定義(正値積分核)において、定理(カーネル関数と正値作用素)のように、
のようになり、この積分作用素 が、必要十分条件により、正値作用素にもなる。
更に、積分作用素は、ヒルベルト=シュミット作用素でもあり、又、正値作用素がは自己共役作用素であるので、
自己共役なヒルベルトシュミット作用素の固有値が全て実数である事実と同様にして、積分作用素 は固有値展開可能であり、それらの全ての固有値は非負の実数となることが分かる。
即ち、非負の実数の固有値 が存在し、これに対応する固有ベクトル が存在する。
これらのことをまとめて、更に収束性に関する内容を加えた定理が、以下に示す Mercer の定理となる。
☆ Mercer 核が定める再生核ヒルベルト空間の具体的な構成
Mercer の定理を用いれば、再生核ヒルベルト空間とその空間上で定義される内積の具体的な表示を構成することが出来る。
- (証明略)(b) の証明のみ記載
【補足】ヒルベルト空間上の線形作用素のトーレス、ヒルベルト=シュミット作用素
- (証明)
以下の関係式より成り立つ。
- (証明)
以下の関係式より成り立つ。
- 【参考】
【補足】共役作用素と正値性
- (証明略)
■ 各種カーネル法
カーネル法を利用したデータ解析手法には、サポートベクターマシン、カーネル主成分分析など、様々な手法が存在するが、いずれもその基本的なコンセプトに一貫した3つの共通ポイントが見られる。
- 1つ目のポイントは、ユークリッド空間上での線形解析手法を、特徴写像により再生核ヒルベルト空間に持ち込み、その再生核ヒルベルト空間上で、線形解析手法を適用することで、ユークリッド空間では線形分離不可能であった問題を、線形分離可能な問題に落とし込むいう点である。
- 2つ目のポイントは、この再生核ヒルベルト空間上での線形解析手法を適用する際に、再生核ヒルベルト空間が無限次元空間であるが故に、実際上計算機で計算不可能な問題が発生するが、リプレゼンター定理により、データより張られる有限次元部分空間上でのデータ解析手法に置き換えるという点である。
- 3つ目のポイントは、このリプレゼンター定理により有限次元化されたデータ解析手法において、分散共分散行列などの計算で、内積演算が必要になるケースが多々あるが、この再生核ヒルベルト空間上での内積演算を2つの特徴ベクトルの内積を計算することなく、カーネル関数で表せるという、カーネルトリックを用いて、計算負荷を削減する点にある。
■ カーネル主成分分析(kernel PCA)
カーネル主成分分析は、カーネル法を用いて、線形分離不可能な問題を、より高次元の線形分離可能な再生核ヒルベルト空間持ち込んで、この再生核ヒルベルト空間内で主成分分析を行う手法であるが(下図参照)、ここでは、このカーネル主成分分析を、再生核ヒルベルト空間の概念で捉え直し、より一般的な視点で見ていく。
まず、このカーネル主成分分析の基本となる、通常の主成分分析(PCA)については、以下のページを参照。
次に、カーネル主成分分析の再生核ヒルベルト空間の概念を(表立って)用いない内容については、以下のページを参照
◎ カーネル主成分分析の再生核ヒルベルト空間を用いた議論
集合 X 上の与えられたデータ に対して、X×X 上の正定値カーネル を用意し、この正定値カーネル k の組を基底として張られる再生核ヒルベルト空間 において、
特徴写像 により、 という再生核ヒルベルト空間 中のデータが生成されているようなケースを考える。
カーネル主成分分析は、この再生核ヒルベルト空間内で主成分分析を行うのであるが、通常の主成分分析の際の、第1主成分の軸 へのデータの射影 の分散値
の最大化(=最適化問題)
に対応するものとして、再生核ヒルベルト空間 中の主成分軸 f に対して、
を考える。
※ は、主成分軸 f のデータの射影の意味合いとなっており、通常の主成分分析の内積演算 に対応するものである。
ここで、主成分分析は、標準化されたデータ(平均0,分散値1)で行う必要があるので、
この再生核ヒルベルト空間内でのデータを中心化した
で考える。
このとき、先のリプレゼンター定理より、この最適化問題の解(=再生核ヒルベルト空間中の関数) は、X×X 上の正定値カーネル から求まる を用いて、
と表現できる。
即ち、第 p 主成分の軸は、
の式から求めることが出来る。
更に、再生核ヒルベルト空間の再生性の条件
を用いると、先の最適化問題の式は、
という、一般化固有値問題の形に置き換えられる。(計算略)
この固有方程式において、グラム行列 の固有値を とし、対応する固有ベクトルを とし、以上の議論をまとめると、主成分 f は、以下のようにして求まる。
第 p 主成分の軸:
第 p 主成分
◎ カーネル主成分分析の簡単な適用列
ここでは、カーネル主成分分析の実際の応用例として、カーネル主成分分析による次元の削除(=特徴抽出)を、簡単な例で見てみる。
(例1)2次元の半月状データの特徴抽出
上図のような、scikit-learn のsklearn.datasets.make_moons( n_samples = 100 )
メソッドで生成した2つのクラス(0 or 1)をとりうる線形分離不可能な2次元の半月状のデータ(サンプル数:100個)に対して、主成分分析により、次元の削除(=特徴抽出)し、更に、線形分離可能なデータに変換することを考える。通常の主成分分析の適用
まずこの問題に対して、通常の主成分分析を適用する。
上図は、各主成分に対する固有値(左上図の青の棒)と寄与率(右上図の青の棒)、累積寄与率(右上図の赤線)の図である。
この図より、第1主成分の寄与率が 80% 程度の高い値になっており、固有値の値だけを見る限り、特徴抽出として適していることが分かる。
左上図は、半月状の2次元データを、主成分分析で変換した図(PC1:第1主成分軸、PC2:第2主成分軸)。
右上図は、更に、寄与率が 80% 程度である第1主成分(PC1)のみの1次元に次元削除(=特徴抽出)した図である。
(※尚、各クラス(0 or 1)の識別を見やすくするため、上下に少し移動させている。)
この図より、通常の PCA では、この半月状のデータをうまく線形分離可能なデータに変換できていないことが分かる。カーネル主成分分析の適用
次に、この問題に対して、RBFカーネル(gamma=15)をカーネル関数とするカーネル主成分分析を適用してみる。
上図は、RBFカーネル関数のカーネル行列(グラム行列)の固有値を、大きい順に 40 個表示した図。
カーネル行列の固有値は固有値分解を近似的な数値解析的手法で解いており、0 に近い値の固有値がこれに続いている。
左上図は、半月状の2次元データを、主成分分析で変換した図(PC1:第1主成分軸、PC2:第2主成分軸)。
右上図は、更に、第1主成分(PC1)のみの1次元に次元削除(=特徴抽出)した図である。
通常の主成分分析のときとは異なり、RBFカーネルをカーネル関数とするカーネル主成分分析では、この半月状のデータをうまく線形分離可能なデータに変換出来ていることが分かる。
(尚、第1主成分 PC1 のみに次元削除(特徴抽出)した図は、各クラス(0 or 1)の識別を見やすくするため、上下に少し移動させている。)
(例2)同心円状のデータ
上図のような、scikit-learn のsklearn.datasets.make_circles( n_samples = 1000 )
メソッドで生成した2つのクラス(0 or 1)をとりうる線形分離不可能な2次元の同心円状のデータ(サンプル数:1000個)に対して、主成分分析により、次元の削除(=特徴抽出)し、更に、線形分離分離可能なデータに変換することを考える。通常の主成分分析
上図は、各主成分に対する固有値(左上図の青の棒)と寄与率(右上図の青の棒)、累積寄与率(右上図の赤線)の図である。
左上図は、同心円状の2次元データを、主成分分析で変換した図(PC1:第1主成分軸、PC2:第2主成分軸)。
右上図は、更に、寄与率が 50% 程度である第1主成分(PC1)のみの1次元に次元削除(=特徴抽出)した図である。
(※尚、各クラス(0 or 1)の識別を見やすくするため、上下に少し移動させている。)
この図より、通常の PCA では、うまく線形分離可能なテータに変換できていないことが分かる。カーネル主成分分析の適用
上図は、RBFカーネル関数のカーネル行列(グラム行列)の固有値を、大きい順に 40 個表示した図。カーネル行列の固有値は固有値分解を近似的な数値解析的手法で解いており、0 に近い値の固有値がこれに続いている。
左上図は、半月状の2次元データを、主成分分析で変換した図(PC1:第1主成分軸、PC2:第2主成分軸)。
右上図は、更に、第1主成分(PC1)のみの1次元に次元削除(=特徴抽出)した図である。
通常の主成分分析のときとは異なり、RBFカーネルをカーネルとするkernelPCA では、この同心円状のデータをうまく線形分離可能な特徴空間に写像出来ていることが分かる。
(尚、第1主成分 PC1 のみに次元削除(特徴抽出)した図は、各クラス(0 or 1)の識別を見やすくするため、上下に少し移動させている。)
■ 正準相関分析
◎ 線形正準相関分析(CCA)
線形正準相関分析は、2つの多変量データを線形変換した後の、互いの相関係数が最大になるような、線形変換のパラメータを求める手法と見なすことも出来る。
今、原因と結果となる2種類の多変量データ とし、線形変換 を考える。ここで、 は、線形変換のパラメータになっており、後述の相関係数が最大になるように、正準相関分析で求めるパラメータである。
この線形変換後のデータ に対して、共分散を各々の標準偏差で割ったものが相関係数、
即ち、
であるが、更に、これの最大値を、正準相関という。
即ち、
ここで、簡単のため、
2種類の多変量データ の平均を0とすると、この正準相関は、
この式において、線形変換のパラメータ に対して、正の数を掛けても、分母と分子で打ち消しあうので、この最大化問題は、以下の最適化問題に置き換えられる。
この最適化問題を解くために、ラグランジュの未定乗数法を用いると、
従って、この最適化問題は、以下のような固有値問題に帰着される。
この固有値問題において、固有値に対応する固有ベクトルが、線形変換のパラメータ となるが、今、求めたいのは、正準相関を最大化する線形変換のパラメータ であったので、
最も大きい固有値に対応する固有ベクトルを求めれば、ここでは目的値 が得られることがわかる。
◎ カーネル正準相関分析(kernel CCA)
先の線形正準相関分析がユークリッド空間上での相関分析であったのに対し、カーネル正準相関分析は、再生核ヒルベルト空間上での正準相関分析になっている。
今、先の線形正準相関分析のときと同様にして、原因と結果となる2種類の多変量データ とする。
このとき、この2種類の多変量データに対応した正定値カーネル 及び を導入し、この正定値カーネルによって張られる再生核ヒルベルト空間をそれぞれ とする。
そして、元のユークリッド空間から再生核ヒルベルト空間への特徴写像 により、2つの再生核ヒルベルト空間 上の多変量データ へと写像されるケースを考える。
(※2種類の多変量データ は、異なる種類のデータなので、特徴抽出も別の特徴写像 で行う。)
その上で、先の線形正準相関分析のときと同様にして、この再生核ヒルベルト空間内での線形変換後のデータ に対して、後述の相関係数(=正準相関)が最大になるように、この線形変換のパラメーター を求めることを考える。
即ち、
ここで、簡単のため、この再生核ヒルベルト空間内でのデータ点を中心化(=平均0)した
で考えると、この正準相関は、以下のように書き換えられる。
より一般的には、パラメーター による線形変換に対応した再生核ヒルベルト空間の要素(関数) と再生核ヒルベルト空間中の内積を用いて表現すると、この正準相関は、以下のように書き換えられる。
ここで、リプレゼンター定理より、この最適化問題の解(=再生核ヒルベルト空間中の関数) は、
のような有限次元の級数展開の式で表現できるが、これを元の正準相関の式に代入すると、以下のように変形できる。(途中計算略)
ここで、この最適化問題の定性的な議論として、再生核ヒルベルト空間という関数の自由度が高すぎる空間での最適化、より詳細には、サンプル数に対して、パラメーター数が多すぎる最適化となっているために、過学習が発生してしまい、その結果として、相関係数が1になるような意味のないパラメーター の解が求まってしまうという問題がある。
この過学習を回避するために、目的関数に対して正則化項を付け加えることを考える。
即ち、以下のような正則化項付きの最適化問題を考える。
先と同様にして、関数 f,g をレプリゼンター定理にもとづく級数展開式、及び、グラム行列 K で書き換えると、
この最適化問題を解くために、線形正準相関分析のときと同様にして、ラグランジュの未定乗数法を用いて変形すると、最終的に、この最適化問題は、以下のような固有値問題に帰着される。
この固有方程式において、固有値 ρ が正準相関係数に対応するので、最も大きい値となる固有値 に対応する固有ベクトルが、求めるべきパラメーター となる。
■ サポートベクターマシン(SVM)
サポートベクターマシンは、カーネル法を利用したパターン認識アルゴリズムの1つであるが、主に、以下のような特徴がある。
マージン最大化を行う線形識別器:
サポートベクターマシンは、線形識別器の1種であるが、マージンと呼ばれる線形識別器(=分離超平面になる)からのノイズを取り除くための余白領域を最大化するように、線形識別器(=ハードマージンSVM)を構成する。(上図参照)
そして、このマージン最大化は、最適化問題として定式化される。カーネル法とカーネルトリック、リプレゼンター定理(カーネル化):
サポートベクターマシンでも他のカーネル法と同様にして、ユークリッド空間において線形分離不可能な問題を、より高次元の再生核ヒルベルト空間内での線形識別問題に置き換える。(上図参照)
そして、リプレゼンター定理により、再生核ヒルベルト空間という無限次元空間での最適化問題が、サンプル数に応じた有限次元空間での最適化問題に置き換えられる。
更に、カーネルトリックにより、2つの特徴ベクトルの内積演算をカーネル関数で直接計算可能とする。サポートベクトルとスパーズ性:
先のリプレゼンター定理により、無限次元である再生核ヒルベルト空間内での最適化問題は、有限次元の最適化問題に置き換えられることが出来た。
しかしながら、サンプル数が膨大な場合、依然として、計算が困難であるという問題は残る。
サポートベクターマシンでは、全サンプル数の内、サポートベクトルと呼ばれる分離超平面付近のサンプルのみを利用して識別を行うというスパーズな表現になっており、結果として、計算量やメモリの節約が出来るというメリットが存在する。
尚、このSVMによる識別関数に寄与するサンプルがサポートベクトルのみであるという事実は、KKT 条件から示せる。
【Memo】サポートベクターマシンの定式化スタイル
サポートベクターマシンの定式化は、マージン最大化を実現する線形識別器(ハードマージン)→スラッグ変数の導入しての正則化(ソフトマージン)→最適化問題への置き換え→・・・という順に議論していくスタイルが基本であるが、直接ヒンジ損失関数の正則化の議論から定式化する方法もある。
赤穂「カーネル多変量解析」の本では後者で話を展開している。ソフトマージンSVMの最適化問題が、ヒンジ損失関数の和と正則化項を目的関数とする制約条件のない最適化問題に置き換えられるので、サポートベクターマシンは、最小2乗誤差関数ではなく、ヒンジ損失関数を損失関数とするカーネル2乗推定法であるとも言え、これはつまり、ヒンジ損失関数の議論からもサポートベクターマシンを定式化出来ることを意味している。
◎ ハードマージンSVM(マージン最大化を実現する線形識別器)
前述のように、サポートベクターマシンは、マージン最大化を実現する線形識別器であり、このマージン最大化の問題は、最適化問題として定式化される。
以下このことの詳細を見ていく。
d 次元のユークリッド空間 において、以下のような教師データ付きの学習データの集合 が与えられたケースを考える。
このとき、上図のように、線形識別器の関数 のマージンを h>0 に設定すると、全ての学習データ に対して、このマージン分 h だけ離れた値の関係
が成り立つ。
両辺を h で割って、線形識別関数の係数ベクトルとバイアス項を正規化し、それらを同じ記号で表記すると、
ここで、上図のように、クラス間マージン ρ は、正負のクラスのデータを、重みの係数ベクトル (=分離超平面の法線ベクトル)の方向へ直交射影した長さの差の最小値で与えられる。
即ち、
マージン最大化を実現する最適な分離超平面の式を
とすると、この超平面は、最大クラス間マージン
を与えるので、ここでの目的であった最大化マージンは、以下のように書けることがわかる。
ここで、バイアス項 b は定数なので、マージンを最大化、即ち とする分離超平面 は、先の制約条件 のもとでの、係数ベクトル を最小化する解、即ち、以下のような2次凸最適化問題の解として定式化される。
そして、このような最適化問題による識別関数を、ハードマージンSVMという。
(※このハードマージンSVMという言葉は、後述の正則化項も考えたソフトマージンSVMとの対比から)
ここで、この最適化問題に寄与する学習データは、上図のように、
正のクラスに属する分離超平面近くにあるベクトル(=サポートベクトルという) と
負のクラスに属する分離超平面近くにあるベクトル(=サポートベクトルという) のみである。
(言い換えると、これらのサポートベクトルによって、マージン h がマージン最大化される。)
※ 正確には、このSVMによる識別関数に寄与するサンプルがサポートベクトルのみであるという事実は、後述の KKT 条件から示せる。
つまり、N 個の学習データの内、一部のサンプルしか利用していないスパーズな表現となっており、その結果として、計算量やメモリの消費の節約が行える。
◎ ソフトマージンSVM(スラッグ変数の導入と正則化)
先のハードマージンSVMの最適化問題
において、
制約条件 は、線形分離可能性の条件になっているが、線形分離不可能な系においては、この最適化問題の解が存在しないことになってしまう。
そこで、制限の緩和を考える。
具体的には、スラック変数 ξ なるものを導入することにより、線形分離不可能な系においても、最適化問題の制約条件を満たすような解が存在するようにする。
即ち、制約条件は、このスラック変数を用いて、以下のように置き換わる。
このスラック変数の導入による効果は、以下の図のようになる。
ここで、スラック変数の値はデータの分布に応じて、以下のような意味を持つ。(上図参照)
- :設定したマージンで、正と負のクラスのデータが正しく識別できている。
- :設定したマージンを超えているが、識別境界は超えておらず、正と負のクラスのデータを正しく識別できている。
- :設定したマージンを超えており、識別境界も超えているので、正と負のクラスのデータを正しく識別できていない。
このように、スラック変数は、データがうまく分類できていない度合いを表すパラメーターになっているので、損失関数の正則化項として利用することが出来る。
即ち、先の正則化なしの最適化問題を、以下のような正則化項ありの最適化問題に変更することが出来る。
ここで、正則化項の係数(パラメーター)C は、誤識別数に対するペナルティーの強さを表しており、値が大きいほど、係数ベクトルのノルム の最小値(=マージン最大化 )よりも、誤識別数を小さくする解が得られる。
このようなパラメーター C による正則化項付きの最適化問題の解による識別関数を、ソフトマージンSVM、或いは、C-SVM と呼ぶ。
※ この最適化問題の正則化パラメーターは、1つのパラメーターCのみであることに注目。
※ 最適なパラメーター C の値は、クロスバリデーションなどで問題に応じて検討する必要がある。
◎ ヒンジ損失関数を用いた正則化法としての SVM
先に導出した、ソフトマージンSVMの最適化問題
は、目的関数をヒンジ損失関数の和と正則化項とするような制約条件のない最適化問題に置き換えることが出来る。以下、そのことを見ていく。
まず、 なる関数ものを導入すると、ソフトマージンSVMの最適化問題の制約条件は、と書き換えられので、λ=1/C とおくと、最適化問題は
ここで、このスラック変数 に対する最適化問題 は、 のとき達成されるので、この最適化問題は、以下のような制約条件のない最適化問題に置き換えることが出来る。
この最適化問題における目的関数は、ヒンジ損失関数 を導入すると、
と書き換えられ、ヒンジ損失関数の和と正則化項を目的関数とする最適化問となっていることが分かる。
それ故に、サポートベクターマシンは、(カーネル2乗推定法において、)最小2乗誤差関数ではなく、ヒンジ損失関数を損失関数とするカーネル2乗推定法であるとも言える。
(※ これはつまり、ヒンジ損失関数の議論からもサポートベクターマシンを定式化出来ることを意味している。)
◎ マージン最大化を実現する線形識別器のカーネル化
ここまでのSVMは、ユークリッド空間上でマージン最大化を実現する線形識別器であったが、これをカーネル化、即ち、以下の図のように、特徴写像により、ユークリッド空間から再生核ヒルベルト空間へという、より高次元でデータを線形分離可能な空間へと写像し、この再生核ヒルベルト空間内で、線形識別を行う。
※ 一般的に、SVMというと、このカーネル化も含めてSVMという。
とする。
このとき、再生核ヒルベルト空間内での線形識別関数は、
従って、先のユークリッド空間内でのソフトマージンSVMの最適化問題
は、この再生核ヒルベルト空間内では、以下のように置き換わる。
或いは、同様の意味だがヒンジ損失関数 L を用いて、
この最適化問題は、再生核ヒルベルト空間が無限次元空間であるために、計算機で具体的に計算可能ではないという問題がある。
従って、リプレゼンター定理を適用する。
即ち、ユークリッド空間での重みベクトル に対応する再生核ヒルベルト空間中の関数 は、
と表現できるので、更に、カーネルトリック も使用すると、
となり、元の再生核ヒルベルト空間における最適化問題は、
のようなデータ数 N に応じた有限次元での最適化問題に書き換えられる。
◎ SVM の最適化問題の最適解と KKT 条件
先の最適化問題
は、不等式制約条件付き凸最適化問題になっているが、この最適化問題の最適解を求めることを考える。
ここで、一般的な議論としての、不等式制約条件付きの凸最適化問題ついては、以下のサイトを参照。
今考えている、SVMの不等式制約条件付きの凸最適化問題の場合に、ラグランジュ未定乗数法を適用すると、ラグランジュ関数は、
ここで、ラグランジュ関数の各パラメーターで偏微分したものを0とおく。
即ち、
これらの式を、元のラグランジュ関数の式に代入すると、ラグランジュ関数は、ラグランジュ乗数のみに依存する関数に書き換えれる。
即ち、
が得られるので、元の最適化問題(=主問題)は、この関数の最適な係数(=主問題のラグランジュ乗数)を求める双対問題に置き換わる。
即ち、双対問題は、
今まで見てきた、SVMの主問題における制約条件を全て合わせたものを、KKT [Karush-Kuhn-Tucker] 条件というが、この KKT 条件は、凸最適化問題の解の必要十分条件になっている。
次に、この KTT 条件を用いて、SVM による識別関数に寄与するサンプルが、サポートベクトルのみから構成されることを示す。
まず、KTT 条件 (3),(4) より、 であるが、更に、値の範囲に応じて3つに場合分けすると、以下のようなことが分かる。
のとき
KKT 条件より、 の関係が成り立つが、 のときは、 となる。
従って、KTT条件 (1) より、 の関係が成り立つ。
この関係式は、サンプル が、SVMの識別関数で十分正しく識別出来ていることを示している(上図参照)のとき
このときも、KKT条件より、 となるが、KKT 条件より定まる関係、 の関係より、
の関係が成り立つ。
この関係式は、サンプル が、SVMの識別関数上に存在していることを示している(上図参照)のとき
このとき、KKT 条件より定まる関係、 の関係より、 の関係が成り立つ。
この関係式は、サンプル が、SVMの識別関数を反対方向に飛び越えた誤識別領域に存在していることを示している(上図参照)
次に、KKT条件 (7) より、この SVM の最適化問題の最適解は、
の形で表現できるが、 のとき でバイアス項と等しくなってしまうので、SVMの解の表現に用いられるサンプル は、 や を満たすようなサンプルとなる。
先の場合分けの結果と合わせると、最適解の表現に使われるサンプル(=識別関数に寄与するサンプル)は、誤識別されるサンプル、及び、正しく識別されているがマージンを定める超平面上かその付近のみのサンプル(=サポートベクトル)のみであることが分かる。
※ のときのサポートベクトル を、自由サポートベクトルという。
※ のときのサポートベクトル を、上限値 C になっているという意味で、上限サポートベクトルという。
◎ SVM の数値解法の概要
ここまで、SVMの最適化問題における最適解が、KKT 条件で与えられることを見てきたが、膨大なデータに対して、実際にこれを解いて、具体的な最適解(=最適なパラメーター)を求めるのは、一般的に困難である。
従って、一般的な凸2次計画問題用の数値解法を用いて、SVM の最適化問題(=凸2次計画問題)の具体的な最適解を求めることが考えられるが、データが膨大な場合、これらの一般的な凸2次計画問題用の数値解法では、実用的な計算時間で最適解を求めることが困難である。
そこで実際には、SMO などの SVM の最適化問題の解法に特化した効率的な最適化手法で、SVM の具体的な最適解を求めることになる。
以下、最も一般的な SMO アルゴリズムの概要のみ記載する。
SMO [Sequential Minimal Optimization](逐次最小問題最適化法)
ある2つの変数のペアを選び、一方の変数を固定した上で、ペアの値を順次変えながら、よりよい最適値を逐次求めていく手法。
各最適化ステップにおいて、2つの変数を選ぶための基準として、KTT 条件に基づく基準を採用する。【参考サイト】
◎ SVM の簡単な適用例
ここでは、SVMの実際の応用例として、SVMによるデータの分類タスクを、簡単な例で見てみる。
- XOR データの2クラス分類
上図のような、numpy.logical_xor()
で生成した、2つのクラス(-1 or 1)をとりうる2次元のXORで分布したデータ(特徴数 2 個 × サンプル数 200 個)に対して、C-SVMを用いて識別するタスクを考える。
尚、この検証は、以下のような条件で行なっている。
<条件>
・ XORデータ(サンプル数:200個)
・ トレーニングデータ 80% 、テストデータ 20%の割合で分割
・ XORデータに対して、正規化処理実施
・ カーネル関数は、RBFカーネル
・ k-fold クロス・バディゲーション(k=10)で汎化性能を評価
① グリッドサーチによるパラメーターのチューニング
まずは、グリッドサーチを用いて、この分類タスクにおけるC-SVM の最適なパラメーター(=C値、gamma値)をチューニングする。
上図は、scikit-learn のsklearn.model_selection.GridSearchCV
モジュールを用いて、C-SVM のパラメーターをグリッドサーチし、対象のXOR データの正解率をヒートマップで図示したものである。(横軸と縦軸が、C-SVM のハイパーパラメータである RBFカーネルの gamma 値と、C-SVM の C 値)
このヒートマップ図より、推定器として、カーネル関数を RBFカーネルとする C-SVM を使用した場合、最も正解率が高くなるパラメータ(ハイパーパラメータ)は、C = 1000, gamma = 0.1 (Accuracy = 0.971) となることが分かる。
② 識別結果&汎化性能の確認
上図は、グリッドサーチで最もよいスコアとなってC-SVM のハイパーパラメータ(C=1000,gamma=0.01)での、XOR データの識別境界の図である。
ここで、○で囲んだ箇所は、テスト用データのサンプルであることを示している。
■ 参考文献
カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)
- 作者: 赤穂昭太郎
- 出版社/メーカー: 岩波書店
- 発売日: 2008/11/27
- メディア: 単行本
- 購入: 7人 クリック: 180回
- この商品を含むブログ (32件) を見る
- はじめに、カーネル法の基本的なコンセプト(特徴写像カーネルトリック、レプリゼンター定理など)を説明した上で、その後、各種カーネル法(カーネル主成分分析、カーネル判別分析、サポートベクターマシンなど)の説明がある。後半に、カーネル法の数理的な内容として、再生核ヒルベルト空間についての(関数解析用語での)理論的な説明、加えて、正定値カーネルの情報幾何的な解釈、厳密な定義でのリプレゼンター定理)などがある。各種カーネル法の説明が豊富に記載されており、おすすめです。
カーネル法入門―正定値カーネルによるデータ解析 (シリーズ 多変量データの統計科学)
- 作者: 福水健次
- 出版社/メーカー: 朝倉書店
- 発売日: 2010/11/01
- メディア: 単行本
- クリック: 19回
- この商品を含むブログ (11件) を見る
- 正定値カーネル、再生核ヒルベルト空間、リプレゼンター定理、Bochner の定理、Mercer の定理などのカーネル法の数理的な内容が豊富に記載されている。カーネル法の数理的な内容が知りたい方には、おすすめです。
- 作者: C.M.ビショップ,元田浩,栗田多喜夫,樋口知之,松本裕治,村田昇
- 出版社/メーカー: 丸善出版
- 発売日: 2012/02/29
- メディア: 単行本
- 購入: 6人 クリック: 14回
- この商品を含むブログを見る
- いわずと知れた機械学習の定番書。6章にカーネル法、7章にサポートベクターマシン、12章にカーネル主成分分析の説明がある。
- 作者: 平井有三
- 出版社/メーカー: 森北出版
- 発売日: 2012/07/31
- メディア: 単行本(ソフトカバー)
- 購入: 1人 クリック: 7回
- この商品を含むブログ (5件) を見る
- 作者: ネロクリスティアニーニ,ジョンショー‐テイラー,Nello Cristianini,John Shawe‐Taylor,大北剛
- 出版社/メーカー: 共立出版
- 発売日: 2005/03/01
- メディア: 単行本
- 購入: 8人 クリック: 135回
- この商品を含むブログ (42件) を見る
- 原書は英語の本。カーネル法の1種であるSVMのみのタイトルだが、3章のカーネル誘導特徴空間の章で、より一般的な、正定値カーネル、再生核ヒルベルト空間の理論的な説明。及び、マーセルの定理の説明。加えて、カーネルとガウス過程の話がある。更に(カーネル法の話題からは話が逸れる?が)4章の汎化理論で、PAC学習、VC理論(※これらに関しては全然知らない)の説明もある。
機械学習のエッセンス -実装しながら学ぶPython,数学,アルゴリズム- (Machine Learning)
- 作者: 加藤公一
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2018/09/21
- メディア: 単行本
- この商品を含むブログを見る
- 5-7章にカーネル法の1種であるSVMのアルゴリズムを構成するマージン最大化と最適化問題の丁寧な式変形での解説と、scikit-learn などの機械学習フレームワークを使用せず、numpyだけを使用したPythonでのスクラッチ実装コードとその丁寧なコード説明がある。
- 出版社/メーカー: 日本評論社
- 発売日: 2018/11/12
- メディア: 雑誌
- この商品を含むブログを見る
- 連載特集に機械学習の数理として、カーネル法とニューラルネットワークの関連性について書かれた記事がある。