カーネルパーセプトロン

機械学習において、カーネルパーセプトロンは、カーネルマシン、つまりカーネル関数を用いて未知のサンプルと訓練サンプルの類似度を計算する非線形分類器を学習できる、一般的なパーセプトロン学習アルゴリズムの変種です。このアルゴリズムは1964年に発明され、^[1]、最初のカーネル分類学習器となりました。^[2]

準備

パーセプトロンアルゴリズム

パーセプトロンアルゴリズムは、「エラー駆動学習」と呼ばれる原理で動作するオンライン学習アルゴリズムです。モデルをトレーニングサンプルで実行し、教師信号に対して誤った分類を行ったことが判明するたびにモデルを更新することで、モデルを反復的に改善します。標準的なパーセプトロンアルゴリズムによって学習されたモデルは、線形2値分類器です。これは、重みw（およびオプションで切片項b、ここでは簡潔にするために省略）のベクトルであり、サンプルベクトルxをクラス「1」またはクラス「-1」に 分類するために使用されます

${\displaystyle {\hat {y}}=\operatorname {sgn}(\mathbf {w} ^{\top }\mathbf {x} )}$

ここで、ゼロは任意に 1 または - 1 にマッピングされます。( ŷの「ハット」は推定値を表します。)

擬似コードでは、パーセプトロン アルゴリズムは次のように表されます。

w を、予測子（特徴）の数である長さpのすべてゼロのベクトルに初期化します。

一定の反復回数、または停止基準が満たされるまで:

各トレーニング例x _iとグラウンドトゥルースラベルy _i ∈ {-1, 1 }について:

ŷ = sgn( w ^T x _i )とします。

ŷ ≠ y _{i の}場合、w ← w + y _i x _iを更新します。

カーネル法

パーセプトロンによって学習される線形モデルとは対照的に、カーネル法^{[3]は、訓練例}x _iのサブセットを格納し、それぞれに重みα _iを関連付け、新しいサンプルx'について評価することで 決定を下す分類器です

${\displaystyle \operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )}$ 。

ここで、Kはカーネル関数です。正式には、カーネル関数は非負の半正定値カーネル（Mercerの条件を参照）であり、高次元空間におけるサンプル間の内積を表します。これは、サンプルが関数Φによって拡張され、追加の特徴が含まれるようになったかのように表現されます：K ( x , x' ) = Φ( x ) · Φ( x' ) 。直感的には、これはサンプル間の類似度関数と考えることができ、カーネルマシンはトレーニングセットとの加重比較によって新しいサンプルのクラスを確立します。各関数x' ↦ K ( x _i , x' )は、分類における 基底関数として機能します。

アルゴリズム

パーセプトロンアルゴリズムのカーネル化バージョンを導出するには、まず重みベクトルwがn個の訓練サンプルの線形結合として表現できるという観察から始めて、それを双対形式で定式化する必要があります。重みベクトルの式は次のとおりです

${\displaystyle \mathbf {w} =\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}}$

ここで、α _iはx _{i が}誤分類された回数であり、 w ← w + y _i x _iという更新を強制します。この結果を用いて、デュアルパーセプトロンアルゴリズムを定式化できます。このアルゴリズムは、これまでと同様にサンプルをループ処理して予測を行いますが、重みベクトルwを保存・更新する代わりに、「誤りカウンタ」ベクトルαを更新します。また、予測式をwを取り除くために書き直す必要があります。

${\displaystyle {\begin{aligned}{\hat {y}}&=\operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} )\\&=\operatorname {sgn} \left(\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}\right)^{\mathsf {T}}\mathbf {x} \\&=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}(\mathbf {x} _{i}\cdot \mathbf {x} )\end{aligned}}}$

これら 2 つの方程式をトレーニング ループに挿入すると、デュアル パーセプトロンアルゴリズムになります。

最後に、双対パーセプトロンのドット積を任意のカーネル関数に置き換えることで、 Φ( x )を明示的に計算することなく、特徴マップΦの効果を得ることができます。これにより、カーネルパーセプトロンアルゴリズムが得られます。^[4]

α を、トレーニング サンプルの数である長さnの全ゼロ ベクトルに初期化します。

一定の反復回数、または停止基準が満たされるまで:

各トレーニング例x _j、y _jについて:

とします${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})}$

ŷ ≠ y _jの場合、ミスカウンターを増分して更新を実行します

α _j ← α _j + 1

バリエーションと拡張

上で示したように、カーネルパーセプトロンの1つの問題は、スパースカーネルマシンを学習しないことです。最初はすべてのα _iがゼロなので、 ŷを得るための決定関数の評価にはカーネル評価はまったく必要ありませんが、更新ごとにα _{i が}1つずつ増加するため、評価コストはますます高くなります。さらに、カーネルパーセプトロンをオンライン設定で使用する場合、ゼロ以外のα _iの数、つまり評価コストは、アルゴリズムに提示される例の数に比例して増加します

この問題に対処するために、カーネルパーセプトロンの派生型である忘却トロンが提案されました。忘却トロンは、 α _iが非ゼロのアクティブセットを維持し、α i があらかじめ定められたバジェットを超えた場合にアクティブセットからサンプルを削除（「忘却」）し、新しいサンプルがα _iが非ゼロに昇格するにつれて古いサンプルを「縮小」（重みを下げる）します。^[5]

カーネルパーセプトロンのもう一つの問題は、正規化を行わないため、過剰適合に脆弱であることです。NORMAオンラインカーネル学習アルゴリズムは、正規化を加えたカーネルパーセプトロンアルゴリズムの一般化と見なすことができます。^[6]サポートベクターマシンの学習に使用される逐次最小最適化（SMO）アルゴリズムも、カーネルパーセプトロンの一般化と見なすことができます。^[6]

FreundとSchapireの投票パーセプトロンアルゴリズムもカーネル化されたケースに拡張され、^[7]カーネルSVMに匹敵する一般化境界を与える。^[2]

参考文献

1. , LI (1964). 「パターン認識学習におけるポテンシャル関数法の理論的基礎」. Automation and Remote Control . 25 : 821–837Guyon, Isabelle; Boser, B.; Vapnik, Vladimir (1993). 「非常に大きなVC次元分類器の自動容量調整」 . 「ニューラル情報処理システムの進歩」. CiteSeerX 10.1.1.17.7215に引用. 
2. Bordes, Antoine; Ertekin, Seyda; Weston, Jason; Bottou, Léon (2005). 「オンラインおよびアクティブ学習による高速カーネル分類器」JMLR . 6 : 1579–1619 .
3. Schölkopf, Bernhard; Smola, Alexander J.; Learning with Kernels、MIT Press、ケンブリッジ、MA、2002年。ISBN 0-262-19475-9
4. ショー＝テイラー、ジョン、クリスティアーニ、ネロ (2004).パターン分析のためのカーネル法. ケンブリッジ大学出版局. pp.  241– 242
5. Dekel, Ofer; Shalev-Shwartz, Shai; Singer, Yoram (2008). 「The Forgetron: A kernel-based perceptron on a budget」(PDF) . SIAM Journal on Computing . 37 (5): 1342– 1372. CiteSeerX 10.1.1.115.568 . doi :10.1137/060666998. 
6. Kivinen, Jyrki; Smola, Alexander J.; Williamson, Robert C. (2004). 「カーネルを用いたオンライン学習」. IEEE Transactions on Signal Processing . 52 (8): 2165– 2176. Bibcode :2004ITSP...52.2165K. CiteSeerX 10.1.1.578.5680 . doi :10.1109/TSP.2004.830991. 
7. Freund, Y. ; Schapire, RE (1999). 「パーセプトロンアルゴリズムを用いた大マージン分類」(PDF) .機械学習. 37 (3): 277– 296. doi : 10.1023/A:1007662407062 .