カーネル法

Class of algorithms for pattern analysis

機械学習において、カーネルマシンはパターン分析アルゴリズムの一種であり、最もよく知られているのはサポートベクターマシン(SVM) です。これらの手法では、線形分類器を使用して非線形問題を解決します。^[1]パターン分析の一般的なタスクは、データセット内の一般的な種類の関係 (クラスター、ランキング、主成分、相関、分類など)を見つけて調査することです。これらのタスクを解決する多くのアルゴリズムでは、生の表現のデータは、ユーザー指定の特徴マップを介して特徴ベクトル表現に明示的に変換する必要があります。対照的に、カーネル法では、ユーザー指定のカーネル、つまり、内積を使用して計算されたすべてのデータポイントのペアにわたる類似度関数のみが必要です。カーネルマシンの特徴マップは無限次元ですが、表現定理に従って、ユーザー入力から有限次元の行列のみが必要です。カーネルマシンは、並列処理を行わないと、数千の例よりも大きいデータセットの計算が遅くなります。

カーネル法は、カーネル関数を用いることからその名が付けられています。カーネル関数を用いることで、高次元の暗黙的な 特徴空間において、その空間内のデータの座標を計算することなく、特徴空間内のすべてのデータペアの画像間の内積を計算するだけで演算処理を行うことができます。この演算は、座標を明示的に計算するよりも計算コストが安価になることが多いため、「カーネルトリック」と呼ばれています。^{[2]カーネル関数は、シーケンスデータ、}グラフ、テキスト、画像、そしてベクターにも導入されています。

カーネルを操作できるアルゴリズムには、カーネル パーセプトロン、サポート ベクター マシン (SVM)、ガウス過程、主成分分析(PCA)、正準相関分析、リッジ回帰、スペクトル クラスタリング、線形適応フィルタなどがあります。

ほとんどのカーネルアルゴリズムは凸最適化または固有値問題に基づいており、統計的に十分に根拠づけられています。通常、その統計的特性は統計学習理論（例えば、ラデマッハ複雑度）を用いて分析されます。

動機と非公式な説明

カーネル法はインスタンスベースの学習器と考えることができます。入力の特徴に対応する固定のパラメータセットを学習するのではなく、番目の訓練例を「記憶」し、それに対応する重みを学習します。ラベルなし入力、つまり訓練セットに含まれていない入力の予測は、ラベルなし入力と各訓練入力との間のカーネルと呼ばれる類似度関数を適用することで処理されます。例えば、カーネル化された2値分類器は通常、類似度の加重和を計算します 。ここで ${\displaystyle i}$ ${\displaystyle (\mathbf {x} _{i},y_{i})}$ ${\displaystyle w_{i}}$ ${\displaystyle k}$ ${\displaystyle \mathbf {x'} }$ ${\displaystyle \mathbf {x} _{i}}$ $${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k(\mathbf {x} _{i},\mathbf {x'} ),}$$

• ${\displaystyle {\hat {y}}\in \{-1,+1\}}$隠された真のラベルが関心のあるラベルなし入力に対するカーネル化されたバイナリ分類器の予測ラベルです。 ${\displaystyle \mathbf {x'} }$ ${\displaystyle y}$
• ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$任意の入力ペア間の類似性を測定するカーネル関数です。 ${\displaystyle \mathbf {x} ,\mathbf {x'} \in {\mathcal {X}}}$
• 合計は分類器のトレーニング セット内のn個のラベル付き例にわたっており、 ; ${\displaystyle \{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n}}$ ${\displaystyle y_{i}\in \{-1,+1\}}$
• これらは学習アルゴリズムによって決定されるトレーニング例の重みです。 ${\displaystyle w_{i}\in \mathbb {R} }$
• 符号関数は 、予測された分類が正になるか負になるかを決定します。 ${\displaystyle \operatorname {sgn} }$ ${\displaystyle {\hat {y}}}$

カーネル分類器は、カーネルパーセプトロンの発明とともに、1960年代初頭にすでに説明されていました。^{[3] 1990年代に}サポートベクターマシン（SVM）が普及し、手書き認識などのタスクにおいてニューラルネットワークと競合できることがわかったため、カーネル分類器は大きな注目を集めました。

数学：カーネルトリック

特徴マップは で与えられ、カーネル関数は で与えられるSVM 。トレーニングポイントは、分離超平面を容易に見つけることができる3次元空間にマッピングされます。 ${\displaystyle \varphi ((a,b))=(a,b,a^{2}+b^{2})}$ ${\displaystyle k(\mathbf {x} ,\mathbf {y} )=\mathbf {x} \cdot \mathbf {y} +\left\|\mathbf {x} \right\|^{2}\left\|\mathbf {y} \right\|^{2}}$

カーネルトリックは、線形学習アルゴリズムで非線形関数や決定境界を学習するために必要な明示的なマッピングを回避します。入力空間におけるすべてのおよびに対して、特定の関数は別の空間における内積として表現できます。この関数はしばしばカーネルまたはカーネル関数と呼ばれます。「カーネル」という言葉は、数学において重み付き和または積分の重み関数を表すために使用されます。 ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x'} }$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle k(\mathbf {x} ,\mathbf {x'} )}$ ${\displaystyle {\mathcal {V}}}$ ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$

機械学習における特定の問題は、任意の重み関数 よりも構造化されています。カーネルを を満たす 「特徴マップ」の形式で記述できれば、計算ははるかに簡単になります。重要な制約は、 が適切な内積でなければならないことです。一方、が内積空間である限り、 の明示的な表現は不要です。別の表現はマーサーの定理から得られます。つまり、空間に適切な測度を備え、関数がマーサーの条件を満たすことが保証される場合には、暗黙的に定義された関数が存在するということです。 ${\displaystyle k}$ ${\displaystyle \varphi \colon {\mathcal {X}}\to {\mathcal {V}}}$ $${\displaystyle k(\mathbf {x} ,\mathbf {x'} )=\langle \varphi (\mathbf {x} ),\varphi (\mathbf {x'} )\rangle _{\mathcal {V}}.}$$ ${\displaystyle \langle \cdot ,\cdot \rangle _{\mathcal {V}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {V}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle k}$

マーサーの定理は、任意の正定値行列 に内積を関連付ける線型代数の結果を一般化したものに近い。実際、マーサーの条件はこのより単純なケースに簡約できる。内のすべての に対する計数測度 （集合 内の点の数を数える）を測度として選択すると、マーサーの定理の積分は和 に簡約される。この和が内のすべての有限点列とすべての実数値係数の選択（正定値核を参照）に対して成り立つ場合、関数 はマーサーの条件を満たす。 ${\displaystyle \mu (T)=|T|}$ ${\displaystyle T\subset X}$ ${\displaystyle T}$ $${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}k(\mathbf {x} _{i},\mathbf {x} _{j})c_{i}c_{j}\geq 0.}$$ ${\displaystyle (\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle n}$ ${\displaystyle (c_{1},\dots ,c_{n})}$ ${\displaystyle k}$

ネイティブ空間における任意の関係性に依存するアルゴリズムの中には、実際には異なる設定、すなわち の値域空間においては線形解釈を持つものがあります。線形解釈はアルゴリズムに関する洞察を与えてくれます。さらに、サポートベクターマシンの場合のように、計算中に直接計算する必要がないことも少なくありません。この実行時間の短縮を主な利点として挙げる人もいます。研究者たちは、既存のアルゴリズムの意味や特性を正当化するためにもこれを利用しています。 ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$

理論的には、グラム行列 （「カーネル行列」^[4]とも呼ばれる） ）は、半正定値行列（PSD）でなければなりません。^[5]経験的には、機械学習のヒューリスティックでは、マーサーの条件を満たさない関数を選択しても、少なくとも が直感的な類似性の考え方に近似している場合は、適切に機能する可能性があります。^[6]がマーサーカーネルであるかどうかに関係なく、は依然として「カーネル」と呼ばれることがあります。 ${\displaystyle \mathbf {K} \in \mathbb {R} ^{n\times n}}$ ${\displaystyle \{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\}}$ ${\displaystyle K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

カーネル関数がガウス過程で使用される共分散関数でもある場合、グラム行列は共分散行列とも呼ばれます。^[7] ${\displaystyle k}$ ${\displaystyle \mathbf {K} }$

アプリケーション

カーネル法の応用分野は多岐にわたり、地統計学、^[8] クリギング、逆距離加重、3D再構成、バイオインフォマティクス、ケモインフォマティクス、情報抽出、手書き認識などが含まれます。

人気のカーネル

• フィッシャーカーネル
• グラフカーネル
• カーネルスムージング
• 多項式カーネル
• ラジアル基底関数カーネル（RBF）
• ストリングカーネル
• ニューラル接線カーネル
• ニューラルネットワークガウス過程（NNGP）カーネル

参照

• ベクトル出力のためのカーネル法
• カーネル密度推定
• 代表者定理
• 類似性学習
• カバーの定理

参考文献

1. 「カーネル法」Engati . 2023年4月4日閲覧。
2. Theodoridis, Sergios (2008).パターン認識. Elsevier BV p. 203. ISBN 9780080949123。
3. Aizerman, MA; Braverman, Emmanuel M.; Rozonoer, LI (1964). 「パターン認識学習におけるポテンシャル関数法の理論的基礎」. Automation and Remote Control . 25 : 821–837 .Guyon, Isabelle; Boser, B.; Vapnik, Vladimir (1993). 「非常に大きなVC次元分類器の自動容量調整」 . 「ニューラル情報処理システムの進歩」. CiteSeerX 10.1.1.17.7215に引用. 
4. Hofmann, Thomas; Schölkopf, Bernhard; Smola, Alexander J. (2008). 「機械学習におけるカーネル法」. The Annals of Statistics . 36 (3). arXiv : math/0701907 . doi : 10.1214/009053607000000677 . S2CID  88516979.
5. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). 『機械学習の基礎』 米国マサチューセッツ州：MIT Press. ISBN 9780262018258。
6. Sewell, Martin. 「サポートベクターマシン：マーサーの条件」. サポートベクターマシン. 2018年10月15日時点のオリジナルよりアーカイブ。 2014年5月30日閲覧。
7. ラスムッセン、カール・エドワード、ウィリアムズ、クリストファー・KI (2006).機械学習のためのガウス過程. MIT Press. ISBN 0-262-18253-X。 ^{[ページが必要]}
8. Honarkhah, M.; Caers, J. (2010). 「距離ベースパターンモデリングを用いたパターンの確率的シミュレーション」. Mathematical Geosciences . 42 (5): 487– 517. Bibcode :2010MaGeo..42..487H. doi :10.1007/s11004-010-9276-7. S2CID  73657847.

さらに読む

• Shawe-Taylor, J. ; Cristianini, N. (2004).パターン分析のためのカーネル法. Cambridge University Press. ISBN 9780511809682。
• Liu, W.; Principe, J.; Haykin, S. (2010). カーネル適応フィルタリング：包括的入門. Wiley. ISBN 9781118211212。
• Schölkopf, B. ; Smola, AJ; Bach, F. (2018). 『カーネルによる学習：サポートベクターマシン、正則化、最適化、そしてその先へ』MIT Press. ISBN 978-0-262-53657-8。

外部リンク

• onlineprediction.net カーネル法の記事

Retrieved from "https://en.wikipedia.org/w/index.php?title=Kernel_method&oldid=1323912764"