星の本棚

サイエンス、テクノロジー、エンジニア関連のノート(忘備録)です。

カーネル法

非線形データに対する多変数解析の一種であるカーネル法の、主に数理面について勉強したことをまとめたノート(忘備録)です。

目次 [Contents]

  1. 概要
    1. 特徴写像と再生核ヒルベルト空間
    2. カーネルトリック
    3. リプレゼンター定理
    4. カーネル法を利用した各種データ解析手法に共通する手順
  2. 正定値カーネル
    1. 実数の正定値カーネル
    2. 複素数の正定値カーネル
    3. 正定値カーネルの基本的な性質
    4. 関数の内積で表現される正定値カーネル
    5. 正定値カーネルの例
      1. 線形カーネル(=通常のユークリッド空間上での内積)
      2. 指数型カーネル
      3. 動径基底関数カーネル(RBFカーネル)[radial bases function kernel]
      4. ラプラスカーネル
      5. 多項式カーネル
  3. 再生核ヒルベルト空間
    1. 再生核の性質
      1. 再生核のテンソル積
    2. 再生核ヒルベルト空間の線形汎関数を用いた特徴付けとリースの表現定理
    3. Moore-Aronszajn の定理
      1. 特徴写像とカーネルトリック(Moore - Aronszajn の定理からの帰着)
    4. 再生核ヒルベルト空間の具体的な構成
      1. 線形カーネルの再生核ヒルベルト空間
      2. 有限集合上の(エルミート行列の)再生核ヒルベルト空間
      3. 多項式カーネルの再生核ヒルベルト空間
    5. 埋め込み写像による再生核ヒルベルト空間の構成
      1. フーリエ変換の形をした埋め込み写像による再生核ヒルベルト空間の構成
      2. RBF カーネルの再生核ヒルベルト空間
      3. ラプラスカーネルの再生核ヒルベルト空間
  4. 正則化とカーネル法
    1. リプレゼンター定理
    2. 【補足(外部リンク)】正則化 [Regularization] による過学習への対応
  5. 正定値カーネルの理論
    1. 負定値カーネル
      1. 負定値カーネルの基本的な性質
      2. 負定値カーネルの基本的な例
    2. Schoenberg の定理
    3. カーネルを生成する操作
    4. Bochner の定理
    5. Mercer(マーセル、マーサー)の定理
      1. 積分作用素、積分核
      2. 積分作用素とヒルベルト=シュミット作用素
      3. 積分核のヒルベルト=シュミット展開
      4. 正値積分核(Mercer核)と Mercer の定理
      5. Mercer 核が定める再生核ヒルベルト空間の具体的な構成
      6. 【補足】ヒルベルト空間上の線形作用素のトーレス、ヒルベルト=シュミット作用素
      7. 【補足】共役作用素と正値性
  6. 各種カーネル法
    1. カーネル主成分分析(kernel PCA)
      1. 【補足(外部リンク)】主成分分析 [PCA : Principal Component Analysis])
      2. 【補足(外部リンク)】カーネル主成分分析 [kernel PCA : kernel Principal Component Analysis]
      3. カーネル主成分分析の再生核ヒルベルト空間を用いた議論
      4. カーネル主成分分析の簡単な適用列
    2. 正準相関分析
      1. 線形正準相関分析(CCA)
      2. カーネル正準相関分析(kernel CCA)
    3. サポートベクターマシン(SVM)
      1. ハードマージンSVM(マージン最大化を実現する線形識別器)
      2. ソフトマージンSVM(スラッグ変数の導入と正則化)
      3. ヒンジ損失関数を用いた正則化法としての SVM
      4. マージン最大化を実現する線形識別器のカーネル化
      5. SVM の最適化問題の最適解と KKT 条件
      6. SVM の数値解法の概要
      7. SVM の簡単な適用例
  7. 補足事項
    1. 【外部リンク】関数解析とヒルベルト空間
    2. 【外部リンク】測度論
    3. 【外部リンク】最適化問題
    4. 【外部リンク】機械学習
  8. 参考文献

■ 概要

カーネル法は、非線形データに対する多変量解析の手法の1つであるが、その特徴としては、非線形データを正定値カーネルの形に応じて定まる再生核ヒルベルト空間上の線形データに持ち込んで解析する点にある。

ここでは、以下のような観点からカーネル法全体の概要を見ている。

◎ 特徴写像と再生核ヒルベルト空間

image
左上図のように、データの分布が線形でない場合において、例えば、2クラスの識別問題などに対する有限次元のユークリッド空間上での線形なデータ解析手法はうまくいかない。
このような場合、右上図のように、データをより高次元の空間に持ち込み、その空間上で線形なデータ解析手法を適用するという解決策が考えられる。
カーネル法では、このようなデータをより高次元の空間に持ち込む写像を特徴写像として定式化し、特徴写像写像先である高次元の特徴空間を、一般的かつ汎用的な枠組みで扱えるように内積が定義された無限次元空間である再生核ヒルベルト空間として定式化する。
(※再生核ヒルベルトでは、更に、再生性の条件が成り立つが、これは、後述のカーネルトリック、及び、リプリゼンター定理を適用できるために必要な性質となっている。)

詳細は、再生核ヒルベルト空間 に記載

カーネルトリック

カーネル法では、特徴写像 Φ により、ユークリッド空間上のデータをより高次元の特徴空間へ写像するが、この際に、ユークリッド空間上の2つのデータの類似性を表すカーネル関数 k は、特徴空間内の2つの特徴ベクトルの内積、即ち、image によって定まる。
従って、特徴空間での特徴ベクトルの内積を計算したい場合(例えば、データ解析手法において共分散分散行列を計算したい場合など)において、特徴空間の次数に依存して膨大になる特徴ベクトルの内積計算ではなく、正定値カーネルで直接計算することができる。
このような計算量の大幅削減テクニックをカーネルトリックという。
尚、このカーネルトリックの元になる image 関係は、カーネル関数が正定値カーネルであることと、再生核ヒルベルト空間における再生性の条件、及び、Moore - Aronszajn の定理からの帰着から得られる。

詳細は、正定値カーネル再生核ヒルベルト空間 特徴写像とカーネルトリック(Moore - Aronszajn の定理からの帰着) に記載

◎ リプレゼンター定理

特徴写像写像先である再生核ヒルベルト空間内で、各種データ解析手法で線形解析を行う際に、再生核ヒルベルト空間が無限次元空間であるために、実際上には、計算機で計算不可能であるという問題がある。
このような問題は、リプレゼンター定理により解決できる。
即ち、この無限次元である再生核ヒルベルト空間内での最適化問題は、データの張る有限次元部分空間の中での最適化問題に帰着できる。

詳細は、リプレゼンター定理 に記載

カーネル法を利用した各種データ解析手法に共通する手順

カーネル法を利用したデータ解析手法には、サポートベクターマシンカーネル主成分分析など様々な手法が存在するが、いずれもその基本的なコンセプトに一貫した3つの共通ポイントが見られる。

  • 1つ目のポイントは、ユークリッド空間上での線形解析手法を特徴写像により再生核ヒルベルト空間に持ち込み、その再生核ヒルベルト空間上で線形解析手法を適用することで、ユークリッド空間では線形分離不可能であった問題を、線形分離可能な問題に落とし込むいう点である。
  • 2つ目のポイントは、この再生核ヒルベルト空間上での線形解析手法を適用する際に、再生核ヒルベルト空間が無限次元空間であるが故に、実際上計算機で計算不可能な問題が発生するが、リプレゼンター定理により、データより張られる有限次元部分空間上でのデータ解析手法に置き換えるという点である。
  • 3つ目のポイントは、このリプレゼンター定理により有限次元化されたデータ解析手法において、分散共分散行列などの計算で内積演算が必要になるケースが多々あるが、この再生核ヒルベルト空間上での内積演算を2つの特徴ベクトルの内積を計算することなく、カーネル関数で直接計算出来るという、カーネルトリックを用いて、計算負荷を削減する点にある。

カーネル法を利用した各種データ解析手法の詳細は、各種カーネル法 に記載

■ 正定値カーネル

カーネル関数は、2つのデータ image の類似度を表す関数であるが、概要のカーネルトリックの説明で見たような2つの特徴ベクトルの内積で記述できるカーネル関数 image は、カーネル関数の内、特に、対象性と正値性を兼ね備えた正定値カーネルと呼ばれるものになる。

◎ 実数の正定値カーネル

image

image

複素数の正定値カーネル

実数ではなく複素数で扱うことにより、理論を展開する上での見通しがよくなることがあるが、これは正定値カーネルに関しても同様である。(例えば、後述の Bochner の定理など)
そのため、複素数の正定値カーネルなるものを定義する。

image

ここで、複素数の正定値カーネルでは実数の正定値カーネルとは異なり、
(実数の正定値カーネルのときの)対称性の条件 image にあたるエルミート性の条件 image は不要となる。
これは、エルミート性が正定値性の帰着として導かれるためである。

そのことを以下に示す。

任意の1点 image に対する正定値性は、
image
より非負の実数である。
又、任意の2点 imagel と複素数定数 image に対する正定値性は、
image
この式の複素数部分に対して、その複素共役を取ると、
image
両式の差をとると、
image

◎ 正定値カーネルの基本的な性質

次に、この正定値カーネルに関して成り立つ基本的な性質をいくつか見てみる。

image

  • (証明略)

◎ 関数の内積で表現される正定値カーネル

以下の定理で示すように、内積空間上での関数の内積は、正定値カーネルになる。 image

  • (証明)
    正定値性を示すために、正定値性の条件
    image
    の左辺に image を代入すると、
    image
    ノルムの2乗は必ず正になるので、
    image
    の関係が成り立ち、
    image が、正定値カーネルになることがわかる。

◎ 正定値カーネルの例

m 次元ユークリッド空間 image 上で定義されるいくつかの正定値カーネルの例を見ていく。

☆ 線形カーネル(=通常のユークリッド空間上での内積

image
image
image

ここで、このカーネルが、確かに正定値カーネルになることを示す。
この線形カーネルは、先の関数の内積で表現される正定値カーネル image より、明らかに正定値カーネルであることが分かる。

☆ 指数型カーネル

image
image

ここで、このカーネルが、確かに正定値カーネルになることを示す。
この指数型カーネルを、Tayler 展開すると、
image
先の正定値カーネルの性質(カーネル線形結合、カーネルの積)より、この展開式の各項の点列
image
の和もまた正定値カーネルとなる。
更に、image は、この点列の極限となるが、
先の正定値カーネルの性質(カーネルの点列の極限)より、この指数型カーネル image は、正定値カーネルであることが分かる。

☆ 動径基底関数カーネル(RBFカーネル)[radial bases function kernel]

image
ここで、上式のパラメータ σ は、関数の広がりを制御するパラメータである。

image

ここで、この RBF カーネル関数を、例えば、SVMサポートベクターマシン)に適用した場合、このカーネル関数の制御パラメータ σ に関して、一般的に、以下のような関係が成り立つ。

  1. 制御パラメータ σ が大きい
    写像後の特徴ベクトルが離れた位置に写像される
    ⇒ 入力データ(特徴ベクトル)から離れている広範囲のサポートベクトルが識別関数に寄与する。
  2. 制御パラメータ σ が小さい
    写像後の特徴ベクトルが近い位置に写像される
    ⇒ 入力データ(特徴ベクトル)近傍のサポートベクトルが識別関数に寄与する。

image

ここで、このカーネルが、確かに正定値カーネルになることを示す。
この RBF カーネルを変形すると、
image
となるが、先の指数型カーネル image が正定値カーネルであったことを利用すると、
正定値カーネルの性質より、この RBF カーネルも正定値カーネルであることが分かる。

ラプラスカーネル

image

多項式カーネル

image
image

この関数は、例えば d=2 で、c=1 の場合、
image
上式の image のみ依存する項目を、
image
のように分離すると、多項式カーネル
image
の様な6次元の内積演算の形となる。
即ち、逆に言い換えれば、
6次元空間でのベクトルの内積演算 image が、
先の2次元ベクトルの内積スカラー
image
の計算で出来ることになる。⇒ 計算量を削減出来る。

次に、(次数が)一般の場合 d では、
多項式カーネル image を2項定理を用いて展開すると、
image
即ち、多項数カーネルの使用した時の2つのベクトル image の次元(次数)の上限は ∑ の形で求めることが出来る。

■ 再生核ヒルベルト空間

概要でみたように、カーネル法では特徴空間を再生核ヒルベルト空間で定式化する。
一見すると、特徴空間では、内積構造が備わっている完備な無限次元空間、即ち、ヒルベルト空間で定式化すれば十分であるように思えるが、カーネルトリックの元になる関係式 image 、及び、リプリゼンター定理が成り立つための要件として、再生核ヒルベルト空間における再生性の条件が必要になるので、再生核ヒルベルト空間で定式化する。
(※尚、ただの高次元空間ではなく無限次元空間で定式化するのは、一般性や汎用性を確保するため)

image

【Memo】
この定義単体だけでは、再生核ヒルベルト空間の意味は分かりにくいが、後述の 再生核ヒルベルト空間の線形汎関数を用いた特徴付けMoore-Aronszajn の定理まで飛ばして見てみれば、その幾何学的な意味を理解しやすい。

◎ 再生核の性質

image

  • (証明)
    正定値カーネルの対称性 image やエルミート性 image を利用すると、
    2つの再生核 image に対して、再生性の条件より、
    image
    の関係より、この2つの再生核は同一であるので、再生核は一意に存在することが分かる。


image

  • (証明)
    複素数の)正定値カーネルの定義の正定性は、
    任意の整数 imageimage に対して、
    image
    であったが、この左辺は、再生核 image を用いて、
    image
    従って、再生核 image は、正定値カーネルである。

☆ 再生核のテンソル

再生核のテンソル積が、また再生核になることを示すために、まず、再生核ヒルベルト空間のテンソル積なるものを定義する。

image
image


image

  • (証明)
    テンソル積の定義 image より、
    image
    内積の式は、
    image
    となり、再生性の条件が成り立つので、
    この image は再生核となる。

◎ 再生核ヒルベルト空間の線形汎関数を用いた特徴付けとリースの表現定理

image

  • (証明)
    リースの表現定理より、線形汎関数が連続(=有界)であるならば、
    ヒルベルト空間上の要素(関数)g∈H が存在して、任意のヒルベルト空間上の要素(関数)∀f∈H に対して、有界線形汎関数内積で表現出来る。即ち、
    image
    と表現できる。
    従って、この中に、L(f) が f(x) となるような image が存在し、
    image
    の関係が成り立つ。

【メモ】
再生性の条件 image と、リースの表現定理の内積表現 image が対応していることに注目。

◎ Moore-Aronszajn の定理

image

先の再生核ヒルベルト空間の線形汎関数を用いた特徴付けと、
Moore-Aronszajn の定理より、再生核ヒルベルト空間を再解釈(=特徴付け)したのが以下の図である。
正定値カーネルが、再生核ヒルベルト空間の基底になっており、それを元に再生核ヒルベルト空間が構築されていることと、再生性の条件 image が、元のベクトル空間での入力値の写像後の値に対応している点がポイントである。

image

☆ 特徴写像カーネルトリック(Moore - Aronszajn の定理からの帰着)

特徴写像 Φ は、集合 X から再生核ヒルベルト空間への写像 image である。
このとき、Moore - Aronszajn の定理より、正定値カーネルの組 image を基底として張られる空間は、再生核ヒルベルト空間になるので、再生核ヒルベルト空間上の任意の2つの要素(関数)∀f,g ∈H の内積は、
image

image

従って、
image
となり、カーネルトリックの元になる関係式が成り立っていることが分かる。
つまり、カーネルトリックは、Moore - Aronszajn の定理からの帰着で導かれる。

◎ 再生核ヒルベルト空間の具体的な構成

先の Moore-Aronszanの定理より、正定値カーネルにより、再生核ヒルベルト空間の基底が定まり、再生核ヒルベルト空間が構成されることを見てきたが、ここでは、具体的に、幾何学的に表現が可能な場合の再生核ヒルベルト空間を見ていく。

☆ 線形カーネルの再生核ヒルベルト空間

image


尚、カーネル PCA の手法においては、この線形カーネルを用いることにより、
主成分が非線形になるようなデータに対し、(より高次元空間の再生核ヒルベルト空間における)線形な通常の主成分分析に落とし込むことを実現している。(詳細は後述)

☆ 有限集合上の(エルミート行列の)再生核ヒルベルト空間

image

  • (証明略)証明の方針のみ記載
    内積が再生性の条件を満たすことを示せばよい。
    即ち、例えば、エルミート行列 K の第 i 行である image に対して、
    image
    を示せばよい。

多項式カーネルの再生核ヒルベルト空間

image

  • (証明略)

◎ 埋め込み写像による再生核ヒルベルト空間の構成

再生核ヒルベルト空間を、他の一般的な関数空間(例えば、ヒルベルト空間)の部分空間として構成する一般的な方法に、関数空間へのヒルベルト空間の埋め込み写像(=ヒルベルト埋め込み写像)による構成方法が存在する。

ここで議論する、ヒルベルト埋め込み写像による再生核ヒルベルト空間の構成と再生核ヒルベルト空間のフーリエ変換による表示の大まかな話の流れは、以下のようになる。


image

この定理の内容を、解釈図とともに簡潔にまとめると、以下のようになる。

image


【Memo】埋め込み写像
数学的な構造を保ちながら、写像元より一般的で広い空間の部分空間に埋め込むような写像
例えば、以下のような埋め込みは、埋め込み写像である。
- 例1(図形):平面(2次元ユークリッド空間)は立体的空間(3次元ユークリッド空間)への埋め込み。
- 例2(図形):球面や球体の、立体的空間への埋め込み。
- 例3(数):整数の有理数への埋め込み。
- 例4(集合):集合 X の部分集合 A の、X への埋め込み。

フーリエ変換の形をした埋め込み写像による再生核ヒルベルト空間の構成

次に、この埋め込み写像フーリエ変換によって与えられることを見ていく。

image
image

この定理の内容を、簡潔にまとめると、以下のようになる。

image

この定理(フーリエ変換の形をした埋め込み写像による再生核ヒルベルト空間の構成)を用いれば、各々の正定値カーネル(RBFカーネル等)に対しての再生核ヒルベルトフーリエ変換での具体的な表示を得ることが出来る。

☆ RBF カーネルの再生核ヒルベルト空間

先の定理(フーリエ変換の形をした埋め込み写像による再生核ヒルベルト空間の構成)の密度関数に対して、正定値カーネルの1つの例として、RBFカーネル確率密度関数の式を代入するとこで、RBFカーネルの再生核ヒルベルトフーリエ変換での具体的な表示を得ることが出来る。

RBFカーネル確率密度関数 image を以下のように定める。
image
これを先のフーリエ変換での再生核ヒルベルトの具体的な表示の式に代入すると、
RBFカーネルの再生核ヒルベルト空間の具体的な形は、
image
同様にして、内積は、
image
又、再生核は、
image
となる。
即ち、埋め込み写像により定まる再生核ヒルベルト空間は、RBFカーネルの定める再生核ヒルベルト空間に一致することが分かる。

そして、このRBFカーネルの再生核ヒルベルト空間の具体的な表示
image
より、このRFBカーネルの再生核ヒルベルト空間に含まれる関数(=再生核ヒルベルト空間の要素)は、周波数領域で指数関数的に減衰するものに限られることも分かる。

尚、後述の Bochner の定理からも、RBF カーネルが正定値カーネルであることを導くことが出来る。

ラプラスカーネルの再生核ヒルベルト空間

同様にして、先の定理(フーリエ変換の形をした埋め込み写像による再生核ヒルベルト空間の構成)の密度関数に対して、正定値カーネルの1つの例として、ラプラスカーネル確率密度関数の式を代入するとこで、ラプラスカーネルの再生核ヒルベルトフーリエ変換での具体的な表示を得ることが出来る。

ラプラスカーネル確率密度関数 image を、以下のように定める。
image
これを先のフーリエ変換での再生核ヒルベルトの具体的な表示の式に代入すると、
ラプラスカーネルの再生核ヒルベルト空間の具体的な形は、
image
同様にして、内積は、
image
又、再生核は、
image
となる。
即ち、埋め込み写像により定まる再生核ヒルベルト空間は、ラプラスカーネルの定める再生核ヒルベルト空間に一致することが分かる。

そして、このラプラスカーネルの再生核ヒルベルト空間の具体的な表示
image
より、このラプラスカーネルの再生核ヒルベルト空間に含まれる関数(=再生核ヒルベルト空間の要素)は、先のRBFカーネルと比べて、周波数領域(=波数)でより緩やかに減衰するものに限られることも分かる。

尚、後述の Bochner の定理からも、ラプラスカーネルが正定値カーネルであることを導くことが出来る。

正則化カーネル法

機械学習における(損失関数の)正則化は、主に、汎化性能を向上させ、過学習を抑制するために行われる手法の1つであるが、カーネル法における正則化は、この汎化性能の向上の目的だけではなく、後述のリプリゼンター定理によって、無限次元である再生核ヒルベルト空間内でのモデルをカーネル関数の有限次元での線形結合のモデルに限定するという別の大きな目的がある。

☆ リプレゼンター定理

以下、この無限次元である再生核ヒルベルト空間内でのモデルをカーネル関数の有限次元での線形結合のモデルに限定するリプリゼンター定理を導く。

まず、与えられたデータ image に対して、最適化問題の解を再生核ヒルベルト空間中の関数 image とするような、以下のような最適化問題を考える。

image

ここで、L は任意の損失関数で、image は、与えられたデータ image と再生核ヒルベルト空間中の関数 image に依存するという意味。
又、image は、以下の図のように、最適化問題のL2正則化項となっている。(λは、正則化パラメータ)
(※図では、image で対応)

image

この最適化問題をより一般化して、以下のような最適化問題を考える。

image

このような最適化問題は、再生核ヒルベルト空間内での最適化問題なので、無限次元空間での最適化問題になっているために、現実的に計算機での計算が困難であるように思える。
しかしながら、以下のリプリゼンター定理により、このような無限次元空間である再生核ヒルベルト空間での最適化問題が、再生核ヒルベルト空間の再生性を用いることで、有限次元での最適化問題に置き換えられるので、計算可能な最適化問題となる。

image

  • (証明)
    • 級数展開の式
      image
      において、基底となる正定値カーネル image の組より生成される有限次元の部分空間
      image
      とその直交補空間 image を用いて、
      再生核ヒルベルト空間は、
      image
      のように表現できる。
      従って、最適化問題の解である再生核ヒルベルト空間の要素(=関数)に対しても、
      image
      の関係が成り立つ。
    • ここで、再生核ヒルベルト空間における再生性の条件
      image
      を考えると、
      image
      従って、imageimage に変更しても最適化関数 L の値は変わらず、image である。
    • 更に、直交性から、
      image
      となるが、Ψ は単調増加関数なので、
      image
    • 従って、この最適化問題の min の中身は、
      image
      という関係が成り立つので、この級数展開の式
      image
      で与えられる関数 image は、最適化問題の最小値を達成する解であることが分かる。

■ 正定値カーネルの理論

ここでは、正定値カーネルの理論と称して、以下のようなトピックを取り上げる。

◎ 負定値カーネル

まず、先の正定値カーネルとの対比で、負定値カーネルなるものを導入する。

image

image

以下、断り書きがない限り、負定値カーネルといえば、この複素数の負定値カーネルを表すものとする。

☆ 負定値カーネルの基本的な性質

次に、この負定値カーネルに関して成り立つ基本的な性質をいくつか見てみる。

image

  • (証明略)負定値カーネルの定義より成り立つ。


image

☆ 負定値カーネルの基本的な例

  • (例)負定値カーネルの例
    集合 X から内積空間 V への写像 image に対して、
    以下のような定義される関数は、集合 X 上の負定値カーネルであることを示す。
    image

    この関数に対して負定値カーネルの非負性の条件を確認すると、
    image
    従って、負正値の条件が成り立つので、この関数 ψ は負定値カーネルである。

◎ Schoenberg の定理

Schoenberg の定理は、先に導入した負定値カーネルと正定値カーネルを関連付ける定理であるが、そのための前段階として、以下の補題を示す。

image

  • (証明)
    • 「⇐」 方向の証明
      作られた関数 image は、正定値カーネルなので、
      正定性の条件より、
      image
      ここで、関数 image のエルミート性 image より、
      image
      となるので、
      image
      となり、関数 image は負定値カーネルであることが分かる。

    • 「⇒」 方向の証明
      元の関数 image は、負定値カーネルなので、
      image
      従って、作られた関数 image は正定値カーネルである。


image

  • (証明)
    • 「⇐」 の方向証明
      image を Tayler 展開すると、
      image
      1次の項まで採用して、変形すると、
      image
      今、image は負定値カーネルであるので、この逆符号の関数をもつ上式は、正定値カーネルとなる。

    • 「⇒」 の方向の証明
      先の補題(正定値カーネルと負定値カーネルの同値関係)に対応した関数
      image
      を定義すると、この関数 image は正定値カーネルであるが、 この関数 image に対して、exp をとった image は、 ラプラスカーネル image の形になるので、正定値カーネルになる。

      正定値カーネル image を展開すると、
      image
      ここで、一般の正定値カーネル image に対して、任意の関数 f ではさみうちした関数
      image
      は、正定値カーネルとなるという関係(証明略)と対比すると、
      image も正定値カーネルとなることが分かる。

カーネルを生成する操作

この Schoenberg の定理を用いて、負定値カーネル image から作られる関数が、負定値カーネル or 正定値カーネルであるかを示すことが出来る。
(言い換えると、負定値カーネル image から、別の負定値カーネル or 正定値カーネルを生成することが出来る。)
尚、この Schoenberg の定理を用いて、負定値カーネル image から別の負定値カーネル or 正定値カーネルを生成する際には、いずれも、その関数が、image の形に変形できるかがポイントとなる。

image

  • (証明)Schoenberg の定理を用いて証明できる。
    image
    の関係を用いると、
    image
    上式の image の部分は、Scohenberg の定理より、正定値カーネルである。
    更に、被積分関数部分全体 image は、正定値カーネル image に関しての逆符号になっているので、負定値カーネルである。
    そして、積分はリーマン和の極限なので、負定値カーネルの性質(カーネルの点列の極限)より、上式も負定値カーネルである。
    従って、image も負定値カーネルとなることが分かる。


image

  • (証明)Schoenberg の定理を用いて証明できる。
    先の負定値カーネルの例
    image
    において、集合 X を image とすると、
    image
    に対して、先の命題(負定値カーネルの階上関数)を適用すると、
    image
    も、負定値カーネルであることが分かる。

    更に、この関数に exp をとった
    image
    は、Scoenberg の定理より、正定値カーネルとなる。


image

  • (証明)Schoenberg の定理を用いて証明できる。
    image積分表示すると、
    image
    image の形に展開できているので、
    先の命題(負定値カーネルの階上関数)の証明と同様にして、上式の右辺の積分項は、負定値カーネルであるといえ、
    image は、負定値カーネルであることが分かる。
    そして、
    image
    と変形できるが、負定値カーネルの性質より、image は、負定値カーネルであることが分かる。


image

  • (証明)Schoenberg の定理を用いて証明できる。
    対象関数を積分表示すると、
    image
    image の形に展開できているので、
    先の命題(負定値カーネルの階上関数、負定値カーネルのlog関数)の証明と同様にして、
    上式の右辺の積分項は、正定値カーネルであるといえ、
    image
    は正定値カーネルであることが分かる。

◎ Bochner の定理

Bochner の定理は、ユークリッド空間上での平行移動(アフィン変換)に対して不変な正定値カーネル全体を、その正定値カーネルフーリエ変換により特徴づけることを主張している定理である。

まず、カーネル関数の平行移動不変性、及び、そこから定義される正値とはどのようなものなのかを定義する。

image

このように定義した平行移動不変性、及び、正値の概念に関連して、以下の Bochner の定理が成り立つ。

image
image

  • (証明略)十分条件(⇐)の証明み記載する。
    このフーリエ変換の式
    image
    積分は、これら各々の image に対しての image の線形結合の極限和で表せる。即ち、
    image

    ここで、正値の条件 image、及び imageの関係より、
    image は正値関数となるが、
    これは、先の線形結合の極限和の式の基底に対応しており、正定値カーネルの性質(線形結合もまた正定値カーネル、極限も正定値カーネル)より、この線形結合の極限和である image も正値であることが分かる。

◎ Mercer(マーサー、マーセル)の定理

Mercer の定理は、正定値カーネルに対する固有値分解の定理である。 より厳密に言えば、正定値カーネル積分作用素のスペクトル分解によって表現する定理となってる。

積分作用素積分

まずは、この積分作用素積分核とはどのようなものなのかを見ていく。

image

積分作用素ヒルベルト=シュミット作用素

以下の定理で示すように、積分作用素は、ヒルベルト=シュミット作用素でもある。
一方、自己共役なヒルベルト=シュミット作用素は、固有値分解が可能である。(後述)
そしてこれら2つの事実が、正定値カーネル積分作用素のスペクトル分解によって表現する Mercerの定理に結びつく。

image

  • (証明)
    まず前提として、L2空間 image は、ヒルベルト空間でもあるので(image)、この空間上のヒルベルト=シュミット作用素なるものが導入出来る。

    次に、積分核 K の2乗可積分性より、
    ほとんどいたるところの x∈Ω に対して、image の関係が成り立つ。

    image をL2空間 image の完全正規直交系とすると、
    image
    image複素共役をとった image もL2空間 image の完全正規直交系となるので、
    image

積分核のヒルベルト=シュミット展開

自己共役なヒルベルト=シュミット作用素は、固有値分解可能であるという事実を、ヒルベルト=シュミット作用素である積分作用素にも適用するために、自己共役な積分作用素なるものを導入する。

image

  • (証明)
    積分image がエルミート性の条件 image を満たす場合、
    積分作用素 image とある関数 image内積演算に関して、
    image
    の関係が成り立つので、この積分作用素は自己共役作用素となっていることが分かる。


積分作用素は、ヒルベルトシュミット作用素であり、
又、自己共役なヒルベルトシュミット作用素は、固有値展開可能(ヒルベルトシュミットの展開定理)であることより、自己共役な積分作用素も、以下の定理のように固有値で展開表現可能となる。

image

  • (証明略)


更に、image ではなく image においては、積分核は、以下の定理のように固有値で展開表現できる。

image

  • (証明)
    積分核 K の2乗可積分性より、
    ほとんどいたるところの image に対して、image の関係が成り立つ。

    ここで、
    image
    の関係式より、
    image
    の関係が成り立つが、更に、
    image
    となるので、測度 μ に関して、ほとんどいたるところの image に対して、
    image
    というL2空間 image におけるフーリエ展開の関係が成り立つ。

    次に、この展開式の i=1~N までの項をとった展開式 image 及び image の収束性について調べる。
    フビニの定理より、
    image
    の関係が成り立つが、右辺の被積分関数(赤字部分)は、先のフーリエ展開の式より、ほとんどいたるところの image に関して、N→∞ で0に収束する。
    更に、
    image
    のように、N に依存しない被積分関数 image で上限を定められるので、ルベーグの収束定理より、先のフビニの定理からの式が、N→∞ で0に収束する。
    image
    従って、青字部分の N を ∞ にした展開式
    image
    が成り立つことが分かる。

☆ 正値積分核(Mercer核)と Mercer の定理

まず、積分核と積分作用素の正値性の関連を示す。

image


次に、前段階として、測度の台の概念を導入する。

image

image


以下の定理は、ハウスドルフ空間上のラドン測度上のカーネル関数を元にした作用素が、正値作用素となることを述べたものであり、この定理と先の積分作用素の正値性の定義と組合わせ、更にヒルベルト=シュミット作用素積分作用素でもある事実を利用することで、積分作用素固有値の正値性が示せ、最終的に Mercer の定理に結びつく。

image

  • (証明)
    • 「⇒」方向の証明
      image は正定値カーネルであるので、
      ハウスドルフ空間 Ω 上の任意の連続関数 ∀g∈Ω と、ハウスドルフ空間 Ω の分割された可測集合 image を考えると、
      image
      の関係が成り立つ。
      積分作用素 image の正値性の条件式の積分
      image
      は、この和の極限として与えるものになっているので、非負である。即ち、
      image
      となり、積分作用素 image は、正値作用素となることが分かる。

      ※ 尚、今の場合、ハウスドルフ空間 Ω 上の連続関数 ∀g∈Ω で考えて、image積分作用素の正値性の条件 image を対応付けたが、より厳密には、image において、任意の ε>0 に対して、image となるような連続関数 g∈Ω を考え、積分作用素の正値性の条件 image を対応付ければよい。

    • 「⇐」方向の証明
      背理法で示す。
      • まず、非正定値カーネルの条件として、ある image に対して、
        image
        が成り立つと仮定する。
      • カーネル関数 image の連続性と、ハウスドルフ空間 Ω のハウスドルフ性(=空間中の異なる点がそれらの近傍によって分離可能)より、各点 image の開近傍 image が存在して、
        image
        の関係が成り立つ。
      • ここで、image の条件より、image の関係が成り立つ。
        (=このハウスドルフ空間 Ω は、測度 μ が非ゼロな集合から構成されているので、このハウスドルフ空間 Ω の近傍 image に対しても、測度は非ゼロで、image となる。)
      • 関数 image において、
        image
        とおくと、
        積分作用素 image の正値性の条件式の積分 image は、
        image
        となり、仮定(正値作用素)に矛盾するので、命題は成り立つ。


この定理(カーネル関数と正値作用素)と先の定義(正値積分核)と組合わせる。
具体例には、
定義(正値積分核)において、定理(カーネル関数と正値作用素)のように、

と置き換えると、定理(カーネル関数と正値作用素)において、

のようになり、この積分作用素 image が、必要十分条件により、正値作用素にもなる。

更に、積分作用素は、ヒルベルト=シュミット作用素でもあり、又、正値作用素がは自己共役作用素であるので、 自己共役なヒルベルトシュミット作用素固有値が全て実数である事実と同様にして、積分作用素 image固有値展開可能であり、それらの全ての固有値は非負の実数となることが分かる。
即ち、非負の実数の固有値 image が存在し、これに対応する固有ベクトル image が存在する。

これらのことをまとめて、更に収束性に関する内容を加えた定理が、以下に示す Mercer の定理となる。

image

  • (証明略)収束性に関する主張の証明は略
    前半の内容はこれまでの議論(積分核のヒルベルト=シュミット展開~定理(カーネル関数と正値作用素)まで)より、成り立つことが分かる。

☆ Mercer 核が定める再生核ヒルベルト空間の具体的な構成

Mercer の定理を用いれば、再生核ヒルベルト空間とその空間上で定義される内積の具体的な表示を構成することが出来る。

image
image

  • (証明略)(b) の証明のみ記載
    • (a) ヒルベルト空間の証明
      この空間の完備性を示せばよい。

    • (b) 再生核ヒルベルト空間の証明
      積分核 K は、Mercer の定理より、
      image
      と書けるが、
      image
      であるので、この積分核 K が、ヒルベルト空間中の要素(関数)であり、image である。
      従って、ヒルベルト空間中の要素(関数)image との内積 image が定義でき、
      image
      のように再生性の条件を満たすので、
      積分核 K は再生核であり、この部分空間 H が、再生核ヒルベルト空間となることが分かる。

【補足】ヒルベルト空間上の線形作用素トーレスヒルベルト=シュミット作用素

image

image

  • (証明)
    以下の関係式より成り立つ。
    image


image

image

  • (証明)
    以下の関係式より成り立つ。
    image

image

  • (証明)
    ヒルベルト=シュミットノルムは、image で定義されるが、
    パーシバルの等式より、
    image
    の関係が成り立つので、ヒルベルト=シュミットノルムに対して、
    image
    の関係が成り立つ。


【補足】共役作用素と正値性

image

image

  • (証明略)

■ 各種カーネル法

カーネル法を利用したデータ解析手法には、サポートベクターマシンカーネル主成分分析など、様々な手法が存在するが、いずれもその基本的なコンセプトに一貫した3つの共通ポイントが見られる。

  1. 1つ目のポイントは、ユークリッド空間上での線形解析手法を、特徴写像により再生核ヒルベルト空間に持ち込み、その再生核ヒルベルト空間上で、線形解析手法を適用することで、ユークリッド空間では線形分離不可能であった問題を、線形分離可能な問題に落とし込むいう点である。
  2. 2つ目のポイントは、この再生核ヒルベルト空間上での線形解析手法を適用する際に、再生核ヒルベルト空間が無限次元空間であるが故に、実際上計算機で計算不可能な問題が発生するが、リプレゼンター定理により、データより張られる有限次元部分空間上でのデータ解析手法に置き換えるという点である。
  3. 3つ目のポイントは、このリプレゼンター定理により有限次元化されたデータ解析手法において、分散共分散行列などの計算で、内積演算が必要になるケースが多々あるが、この再生核ヒルベルト空間上での内積演算を2つの特徴ベクトルの内積を計算することなく、カーネル関数で表せるという、カーネルトリックを用いて、計算負荷を削減する点にある。

カーネル主成分分析(kernel PCA)

カーネル主成分分析は、カーネル法を用いて、線形分離不可能な問題を、より高次元の線形分離可能な再生核ヒルベルト空間持ち込んで、この再生核ヒルベルト空間内で主成分分析を行う手法であるが(下図参照)、ここでは、このカーネル主成分分析を、再生核ヒルベルト空間の概念で捉え直し、より一般的な視点で見ていく。

image

まず、このカーネル主成分分析の基本となる、通常の主成分分析(PCA)については、以下のページを参照。

次に、カーネル主成分分析の再生核ヒルベルト空間の概念を(表立って)用いない内容については、以下のページを参照

カーネル主成分分析の再生核ヒルベルト空間を用いた議論

集合 X 上の与えられたデータ image に対して、X×X 上の正定値カーネル image を用意し、この正定値カーネル k の組を基底として張られる再生核ヒルベルト空間 image において、

特徴写像 image により、image という再生核ヒルベルト空間 image 中のデータが生成されているようなケースを考える。

カーネル主成分分析は、この再生核ヒルベルト空間内で主成分分析を行うのであるが、通常の主成分分析の際の、第1主成分の軸 image へのデータの射影 image の分散値
image
の最大化(=最適化問題
image
に対応するものとして、再生核ヒルベルト空間 image 中の主成分軸 f に対して、
image
を考える。
image は、主成分軸 f のデータの射影の意味合いとなっており、通常の主成分分析の内積演算 image に対応するものである。

ここで、主成分分析は、標準化されたデータ(平均0,分散値1)で行う必要があるので、
この再生核ヒルベルト空間内でのデータを中心化した
image
で考える。

このとき、先のリプレゼンター定理より、この最適化問題の解(=再生核ヒルベルト空間中の関数)image は、X×X 上の正定値カーネル image から求まる image を用いて、
image
と表現できる。
即ち、第 p 主成分の軸は、
image
の式から求めることが出来る。

更に、再生核ヒルベルト空間の再生性の条件
image
を用いると、先の最適化問題の式は、
image
という、一般化固有値問題の形に置き換えられる。(計算略)

この固有方程式において、グラム行列 image固有値image とし、対応する固有ベクトルimage とし、以上の議論をまとめると、主成分 f は、以下のようにして求まる。

  • 第 p 主成分の軸:
    image

  • 第 p 主成分
    image

カーネル主成分分析の簡単な適用列

ここでは、カーネル主成分分析の実際の応用例として、カーネル主成分分析による次元の削除(=特徴抽出)を、簡単な例で見てみる。

  • (例1)2次元の半月状データの特徴抽出
    image
    上図のような、scikit-learn の sklearn.datasets.make_moons( n_samples = 100 ) メソッドで生成した2つのクラス(0 or 1)をとりうる線形分離不可能な2次元の半月状のデータ(サンプル数:100個)に対して、主成分分析により、次元の削除(=特徴抽出)し、更に、線形分離可能なデータに変換することを考える。

    1. 通常の主成分分析の適用
      まずこの問題に対して、通常の主成分分析を適用する。
      image
      上図は、各主成分に対する固有値(左上図の青の棒)と寄与率(右上図の青の棒)、累積寄与率(右上図の赤線)の図である。
      この図より、第1主成分の寄与率が 80% 程度の高い値になっており、固有値の値だけを見る限り、特徴抽出として適していることが分かる。
      image
      左上図は、半月状の2次元データを、主成分分析で変換した図(PC1:第1主成分軸、PC2:第2主成分軸)。
      右上図は、更に、寄与率が 80% 程度である第1主成分(PC1)のみの1次元に次元削除(=特徴抽出)した図である。
      (※尚、各クラス(0 or 1)の識別を見やすくするため、上下に少し移動させている。)
      この図より、通常の PCA では、この半月状のデータをうまく線形分離可能なデータに変換できていないことが分かる。

    2. カーネル主成分分析の適用
      次に、この問題に対して、RBFカーネル(gamma=15)をカーネル関数とするカーネル主成分分析を適用してみる。
      image
      上図は、RBFカーネル関数のカーネル行列(グラム行列)の固有値を、大きい順に 40 個表示した図。
      カーネル行列の固有値固有値分解を近似的な数値解析的手法で解いており、0 に近い値の固有値がこれに続いている。
      image
      左上図は、半月状の2次元データを、主成分分析で変換した図(PC1:第1主成分軸、PC2:第2主成分軸)。
      右上図は、更に、第1主成分(PC1)のみの1次元に次元削除(=特徴抽出)した図である。
      通常の主成分分析のときとは異なり、RBFカーネルカーネル関数とするカーネル主成分分析では、この半月状のデータをうまく線形分離可能なデータに変換出来ていることが分かる。
      (尚、第1主成分 PC1 のみに次元削除(特徴抽出)した図は、各クラス(0 or 1)の識別を見やすくするため、上下に少し移動させている。)


  • (例2)同心円状のデータ
    image
    上図のような、scikit-learn の sklearn.datasets.make_circles( n_samples = 1000 ) メソッドで生成した2つのクラス(0 or 1)をとりうる線形分離不可能な2次元の同心円状のデータ(サンプル数:1000個)に対して、主成分分析により、次元の削除(=特徴抽出)し、更に、線形分離分離可能なデータに変換することを考える。

    1. 通常の主成分分析 image
      上図は、各主成分に対する固有値(左上図の青の棒)と寄与率(右上図の青の棒)、累積寄与率(右上図の赤線)の図である。
      image
      左上図は、同心円状の2次元データを、主成分分析で変換した図(PC1:第1主成分軸、PC2:第2主成分軸)。
      右上図は、更に、寄与率が 50% 程度である第1主成分(PC1)のみの1次元に次元削除(=特徴抽出)した図である。
      (※尚、各クラス(0 or 1)の識別を見やすくするため、上下に少し移動させている。)
      この図より、通常の PCA では、うまく線形分離可能なテータに変換できていないことが分かる。

    2. カーネル主成分分析の適用
      image
      上図は、RBFカーネル関数のカーネル行列(グラム行列)の固有値を、大きい順に 40 個表示した図。カーネル行列の固有値固有値分解を近似的な数値解析的手法で解いており、0 に近い値の固有値がこれに続いている。
      image
      左上図は、半月状の2次元データを、主成分分析で変換した図(PC1:第1主成分軸、PC2:第2主成分軸)。
      右上図は、更に、第1主成分(PC1)のみの1次元に次元削除(=特徴抽出)した図である。
      通常の主成分分析のときとは異なり、RBFカーネルカーネルとするkernelPCA では、この同心円状のデータをうまく線形分離可能な特徴空間に写像出来ていることが分かる。
      (尚、第1主成分 PC1 のみに次元削除(特徴抽出)した図は、各クラス(0 or 1)の識別を見やすくするため、上下に少し移動させている。)

■ 正準相関分析

◎ 線形正準相関分析(CCA)

線形正準相関分析は、2つの多変量データを線形変換した後の、互いの相関係数が最大になるような、線形変換のパラメータを求める手法と見なすことも出来る。

今、原因と結果となる2種類の多変量データ image とし、線形変換 image を考える。ここで、image は、線形変換のパラメータになっており、後述の相関係数が最大になるように、正準相関分析で求めるパラメータである。

この線形変換後のデータ image に対して、共分散を各々の標準偏差で割ったものが相関係数
即ち、
image
であるが、更に、これの最大値を、正準相関という。
即ち、
image

ここで、簡単のため、
2種類の多変量データ image の平均を0とすると、この正準相関は、
image
この式において、線形変換のパラメータ image に対して、正の数を掛けても、分母と分子で打ち消しあうので、この最大化問題は、以下の最適化問題に置き換えられる。
image

この最適化問題を解くために、ラグランジュの未定乗数法を用いると、
image

image

従って、この最適化問題は、以下のような固有値問題に帰着される。
image

この固有値問題において、固有値に対応する固有ベクトルが、線形変換のパラメータ image となるが、今、求めたいのは、正準相関を最大化する線形変換のパラメータ image であったので、 最も大きい固有値に対応する固有ベクトルを求めれば、ここでは目的値 image が得られることがわかる。

カーネル正準相関分析(kernel CCA)

先の線形正準相関分析がユークリッド空間上での相関分析であったのに対し、カーネル正準相関分析は、再生核ヒルベルト空間上での正準相関分析になっている。

今、先の線形正準相関分析のときと同様にして、原因と結果となる2種類の多変量データ image とする。
このとき、この2種類の多変量データに対応した正定値カーネル image 及び image を導入し、この正定値カーネルによって張られる再生核ヒルベルト空間をそれぞれ image とする。
そして、元のユークリッド空間から再生核ヒルベルト空間への特徴写像 image により、2つの再生核ヒルベルト空間 image 上の多変量データ image へと写像されるケースを考える。
(※2種類の多変量データ image は、異なる種類のデータなので、特徴抽出も別の特徴写像 image で行う。)

その上で、先の線形正準相関分析のときと同様にして、この再生核ヒルベルト空間内での線形変換後のデータ image に対して、後述の相関係数(=正準相関)が最大になるように、この線形変換のパラメーター image を求めることを考える。
即ち、
image

ここで、簡単のため、この再生核ヒルベルト空間内でのデータ点を中心化(=平均0)した
image
で考えると、この正準相関は、以下のように書き換えられる。
image

より一般的には、パラメーター image による線形変換に対応した再生核ヒルベルト空間の要素(関数) image と再生核ヒルベルト空間中の内積を用いて表現すると、この正準相関は、以下のように書き換えられる。
image

ここで、リプレゼンター定理より、この最適化問題の解(=再生核ヒルベルト空間中の関数)image は、
image
のような有限次元の級数展開の式で表現できるが、これを元の正準相関の式に代入すると、以下のように変形できる。(途中計算略)
image

ここで、この最適化問題の定性的な議論として、再生核ヒルベルト空間という関数の自由度が高すぎる空間での最適化、より詳細には、サンプル数に対して、パラメーター数が多すぎる最適化となっているために、過学習が発生してしまい、その結果として、相関係数が1になるような意味のないパラメーター image の解が求まってしまうという問題がある。

この過学習を回避するために、目的関数に対して正則化項を付け加えることを考える。
即ち、以下のような正則化項付きの最適化問題を考える。
image

先と同様にして、関数 f,g をレプリゼンター定理にもとづく級数展開式、及び、グラム行列 K で書き換えると、
image

この最適化問題を解くために、線形正準相関分析のときと同様にして、ラグランジュの未定乗数法を用いて変形すると、最終的に、この最適化問題は、以下のような固有値問題に帰着される。
image

この固有方程式において、固有値 ρ が正準相関係数に対応するので、最も大きい値となる固有値 image に対応する固有ベクトルが、求めるべきパラメーター image となる。

サポートベクターマシンSVM

サポートベクターマシンは、カーネル法を利用したパターン認識アルゴリズムの1つであるが、主に、以下のような特徴がある。

  • マージン最大化を行う線形識別器:
    image
    サポートベクターマシンは、線形識別器の1種であるが、マージンと呼ばれる線形識別器(=分離超平面になる)からのノイズを取り除くための余白領域を最大化するように、線形識別器(=ハードマージンSVM)を構成する。(上図参照)
    そして、このマージン最大化は、最適化問題として定式化される。

  • カーネル法カーネルトリック、リプレゼンター定理(カーネル化):
    image
    サポートベクターマシンでも他のカーネル法と同様にして、ユークリッド空間において線形分離不可能な問題を、より高次元の再生核ヒルベルト空間内での線形識別問題に置き換える。(上図参照)
    そして、リプレゼンター定理により、再生核ヒルベルト空間という無限次元空間での最適化問題が、サンプル数に応じた有限次元空間での最適化問題に置き換えられる。
    更に、カーネルトリックにより、2つの特徴ベクトルの内積演算をカーネル関数で直接計算可能とする。

  • サポートベクトルとスパーズ性:
    image
    先のリプレゼンター定理により、無限次元である再生核ヒルベルト空間内での最適化問題は、有限次元の最適化問題に置き換えられることが出来た。
    しかしながら、サンプル数が膨大な場合、依然として、計算が困難であるという問題は残る。
    サポートベクターマシンでは、全サンプル数の内、サポートベクトルと呼ばれる分離超平面付近のサンプルのみを利用して識別を行うというスパーズな表現になっており、結果として、計算量やメモリの節約が出来るというメリットが存在する。
    尚、このSVMによる識別関数に寄与するサンプルがサポートベクトルのみであるという事実は、KKT 条件から示せる。


【Memo】サポートベクターマシンの定式化スタイル
サポートベクターマシンの定式化は、マージン最大化を実現する線形識別器(ハードマージン)→スラッグ変数の導入しての正則化(ソフトマージン)→最適化問題への置き換え→・・・という順に議論していくスタイルが基本であるが、直接ヒンジ損失関数の正則化の議論から定式化する方法もある。
赤穂「カーネル多変量解析」の本では後者で話を展開している。

ソフトマージンSVM最適化問題が、ヒンジ損失関数の和と正則化項を目的関数とする制約条件のない最適化問題に置き換えられるので、サポートベクターマシンは、最小2乗誤差関数ではなく、ヒンジ損失関数を損失関数とするカーネル2乗推定法であるとも言え、これはつまり、ヒンジ損失関数の議論からもサポートベクターマシンを定式化出来ることを意味している。

◎ ハードマージンSVM(マージン最大化を実現する線形識別器)

前述のように、サポートベクターマシンは、マージン最大化を実現する線形識別器であり、このマージン最大化の問題は、最適化問題として定式化される。
以下このことの詳細を見ていく。

d 次元のユークリッド空間 image において、以下のような教師データ付きの学習データの集合 image が与えられたケースを考える。
image

image

このとき、上図のように、線形識別器の関数 image のマージンを h>0 に設定すると、全ての学習データ image に対して、このマージン分 h だけ離れた値の関係
image
が成り立つ。
両辺を h で割って、線形識別関数の係数ベクトルとバイアス項を正規化し、それらを同じ記号で表記すると、
image

ここで、上図のように、クラス間マージン ρ は、正負のクラスのデータを、重みの係数ベクトル image(=分離超平面の法線ベクトル)の方向へ直交射影した長さの差の最小値で与えられる。
即ち、
image

マージン最大化を実現する最適な分離超平面の式を
image
とすると、この超平面は、最大クラス間マージン
image
を与えるので、ここでの目的であった最大化マージンは、以下のように書けることがわかる。
image

ここで、バイアス項 b は定数なので、マージンを最大化、即ち image とする分離超平面 image は、先の制約条件 image のもとでの、係数ベクトル image を最小化する解、即ち、以下のような2次凸最適化問題の解として定式化される。
image

そして、このような最適化問題による識別関数を、ハードマージンSVMという。
(※このハードマージンSVMという言葉は、後述の正則化項も考えたソフトマージンSVMとの対比から)

ここで、この最適化問題に寄与する学習データは、上図のように、
正のクラスに属する分離超平面近くにあるベクトル(=サポートベクトルという)image と 負のクラスに属する分離超平面近くにあるベクトル(=サポートベクトルという)image のみである。
(言い換えると、これらのサポートベクトルによって、マージン h がマージン最大化される。)
※ 正確には、このSVMによる識別関数に寄与するサンプルがサポートベクトルのみであるという事実は、後述の KKT 条件から示せる。

つまり、N 個の学習データの内、一部のサンプルしか利用していないスパーズな表現となっており、その結果として、計算量やメモリの消費の節約が行える。

◎ ソフトマージンSVM(スラッグ変数の導入と正則化

先のハードマージンSVM最適化問題
image
において、
制約条件 image は、線形分離可能性の条件になっているが、線形分離不可能な系においては、この最適化問題の解が存在しないことになってしまう。

そこで、制限の緩和を考える。
具体的には、スラック変数 ξ なるものを導入することにより、線形分離不可能な系においても、最適化問題の制約条件を満たすような解が存在するようにする。
即ち、制約条件は、このスラック変数を用いて、以下のように置き換わる。
image

このスラック変数の導入による効果は、以下の図のようになる。
image

ここで、スラック変数の値はデータの分布に応じて、以下のような意味を持つ。(上図参照)

  • image:設定したマージンで、正と負のクラスのデータが正しく識別できている。
  • image:設定したマージンを超えているが、識別境界は超えておらず、正と負のクラスのデータを正しく識別できている。
  • image:設定したマージンを超えており、識別境界も超えているので、正と負のクラスのデータを正しく識別できていない。

このように、スラック変数は、データがうまく分類できていない度合いを表すパラメーターになっているので、損失関数の正則化項として利用することが出来る。
即ち、先の正則化なしの最適化問題を、以下のような正則化項ありの最適化問題に変更することが出来る。

image

ここで、正則化項の係数(パラメーター)C は、誤識別数に対するペナルティーの強さを表しており、値が大きいほど、係数ベクトルのノルム image の最小値(=マージン最大化 image )よりも、誤識別数を小さくする解が得られる。

このようなパラメーター C による正則化項付きの最適化問題の解による識別関数を、ソフトマージンSVM、或いは、C-SVM と呼ぶ。
※ この最適化問題正則化パラメーターは、1つのパラメーターCのみであることに注目。
※ 最適なパラメーター C の値は、クロスバリデーションなどで問題に応じて検討する必要がある。

◎ ヒンジ損失関数を用いた正則化法としての SVM

先に導出した、ソフトマージンSVM最適化問題
image
は、目的関数をヒンジ損失関数の和と正則化項とするような制約条件のない最適化問題に置き換えることが出来る。以下、そのことを見ていく。

まず、image なる関数ものを導入すると、ソフトマージンSVM最適化問題の制約条件は、imageと書き換えられので、λ=1/C とおくと、最適化問題
image

ここで、このスラック変数 image に対する最適化問題 image は、image のとき達成されるので、この最適化問題は、以下のような制約条件のない最適化問題に置き換えることが出来る。
image

この最適化問題における目的関数は、ヒンジ損失関数 image を導入すると、
image
と書き換えられ、ヒンジ損失関数の和と正則化項を目的関数とする最適化問となっていることが分かる。

それ故に、サポートベクターマシンは、(カーネル2乗推定法において、)最小2乗誤差関数ではなく、ヒンジ損失関数を損失関数とするカーネル2乗推定法であるとも言える。
(※ これはつまり、ヒンジ損失関数の議論からもサポートベクターマシンを定式化出来ることを意味している。)

◎ マージン最大化を実現する線形識別器のカーネル

ここまでのSVMは、ユークリッド空間上でマージン最大化を実現する線形識別器であったが、これをカーネル化、即ち、以下の図のように、特徴写像により、ユークリッド空間から再生核ヒルベルト空間へという、より高次元でデータを線形分離可能な空間へと写像し、この再生核ヒルベルト空間内で、線形識別を行う。
※ 一般的に、SVMというと、このカーネル化も含めてSVMという。
image

とする。
このとき、再生核ヒルベルト空間内での線形識別関数は、
image
従って、先のユークリッド空間内でのソフトマージンSVM最適化問題
image
は、この再生核ヒルベルト空間内では、以下のように置き換わる。
image

或いは、同様の意味だがヒンジ損失関数 L を用いて、
image

この最適化問題は、再生核ヒルベルト空間が無限次元空間であるために、計算機で具体的に計算可能ではないという問題がある。
従って、リプレゼンター定理を適用する。
即ち、ユークリッド空間での重みベクトル image に対応する再生核ヒルベルト空間中の関数 image は、
image
と表現できるので、更に、カーネルトリック image も使用すると、
image
となり、元の再生核ヒルベルト空間における最適化問題は、
image
のようなデータ数 N に応じた有限次元での最適化問題に書き換えられる。

SVM最適化問題の最適解と KKT 条件

先の最適化問題
image
は、不等式制約条件付き凸最適化問題になっているが、この最適化問題の最適解を求めることを考える。

ここで、一般的な議論としての、不等式制約条件付きの凸最適化問題ついては、以下のサイトを参照。

今考えている、SVMの不等式制約条件付きの凸最適化問題の場合に、ラグランジュ未定乗数法を適用すると、ラグランジュ関数は、
image
ここで、ラグランジュ関数の各パラメーターで偏微分したものを0とおく。
即ち、
image
これらの式を、元のラグランジュ関数の式に代入すると、ラグランジュ関数は、ラグランジュ乗数のみに依存する関数に書き換えれる。
即ち、
image
が得られるので、元の最適化問題(=主問題)は、この関数の最適な係数(=主問題のラグランジュ乗数)を求める双対問題に置き換わる。
即ち、双対問題は、
image
今まで見てきた、SVMの主問題における制約条件を全て合わせたものを、KKT [Karush-Kuhn-Tucker] 条件というが、この KKT 条件は、凸最適化問題の解の必要十分条件になっている。

image
image


次に、この KTT 条件を用いて、SVM による識別関数に寄与するサンプルが、サポートベクトルのみから構成されることを示す。

image

まず、KTT 条件 (3),(4) より、image であるが、更に、値の範囲に応じて3つに場合分けすると、以下のようなことが分かる。

  • image のとき
    KKT 条件より、image の関係が成り立つが、image のときは、image となる。
    従って、KTT条件 (1) より、image の関係が成り立つ。
    この関係式は、サンプル image が、SVMの識別関数で十分正しく識別出来ていることを示している(上図参照)

  • image のとき
    このときも、KKT条件より、image となるが、KKT 条件より定まる関係、image の関係より、
    image の関係が成り立つ。
    この関係式は、サンプル image が、SVMの識別関数上に存在していることを示している(上図参照)

  • image のとき
    このとき、KKT 条件より定まる関係、image の関係より、image の関係が成り立つ。
    この関係式は、サンプル image が、SVMの識別関数を反対方向に飛び越えた誤識別領域に存在していることを示している(上図参照)

次に、KKT条件 (7) より、この SVM最適化問題の最適解は、
image
の形で表現できるが、image のとき image でバイアス項と等しくなってしまうので、SVMの解の表現に用いられるサンプル image は、imageimage を満たすようなサンプルとなる。
先の場合分けの結果と合わせると、最適解の表現に使われるサンプル(=識別関数に寄与するサンプル)は、誤識別されるサンプル、及び、正しく識別されているがマージンを定める超平面上かその付近のみのサンプル(=サポートベクトル)のみであることが分かる。
image のときのサポートベクトル image を、自由サポートベクトルという。
image のときのサポートベクトル image を、上限値 C になっているという意味で、上限サポートベクトルという。

SVM の数値解法の概要

ここまで、SVM最適化問題における最適解が、KKT 条件で与えられることを見てきたが、膨大なデータに対して、実際にこれを解いて、具体的な最適解(=最適なパラメーター)を求めるのは、一般的に困難である。
従って、一般的な凸2次計画問題用の数値解法を用いて、SVM最適化問題(=凸2次計画問題)の具体的な最適解を求めることが考えられるが、データが膨大な場合、これらの一般的な凸2次計画問題用の数値解法では、実用的な計算時間で最適解を求めることが困難である。
そこで実際には、SMO などの SVM最適化問題の解法に特化した効率的な最適化手法で、SVM の具体的な最適解を求めることになる。

以下、最も一般的な SMO アルゴリズムの概要のみ記載する。

  • SMO [Sequential Minimal Optimization](逐次最小問題最適化法)
    ある2つの変数のペアを選び、一方の変数を固定した上で、ペアの値を順次変えながら、よりよい最適値を逐次求めていく手法。
    各最適化ステップにおいて、2つの変数を選ぶための基準として、KTT 条件に基づく基準を採用する。

  • 【参考サイト】

SVM の簡単な適用例

ここでは、SVMの実際の応用例として、SVMによるデータの分類タスクを、簡単な例で見てみる。

  • XOR データの2クラス分類
    image
    上図のような、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値)をチューニングする。
    image
    上図は、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) となることが分かる。

    image

    ② 識別結果&汎化性能の確認
    image
    上図は、グリッドサーチで最もよいスコアとなってC-SVM のハイパーパラメータ(C=1000,gamma=0.01)での、XOR データの識別境界の図である。
    ここで、○で囲んだ箇所は、テスト用データのサンプルであることを示している。

    image

■ 参考文献

カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)

カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)


カーネル法入門―正定値カーネルによるデータ解析 (シリーズ 多変量データの統計科学)

カーネル法入門―正定値カーネルによるデータ解析 (シリーズ 多変量データの統計科学)

  • 正定値カーネル、再生核ヒルベルト空間、リプレゼンター定理、Bochner の定理、Mercer の定理などのカーネル法の数理的な内容が豊富に記載されている。カーネル法の数理的な内容が知りたい方には、おすすめです。


パターン認識と機械学習 下 (ベイズ理論による統計的予測)

パターン認識と機械学習 下 (ベイズ理論による統計的予測)


はじめてのパターン認識

はじめてのパターン認識


サポートベクターマシン入門

サポートベクターマシン入門

  • 原書は英語の本。カーネル法の1種であるSVMのみのタイトルだが、3章のカーネル誘導特徴空間の章で、より一般的な、正定値カーネル、再生核ヒルベルト空間の理論的な説明。及び、マーセルの定理の説明。加えて、カーネルガウス過程の話がある。更に(カーネル法の話題からは話が逸れる?が)4章の汎化理論で、PAC学習、VC理論(※これらに関しては全然知らない)の説明もある。