多項式カーネル

機械学習において、多項式カーネルは、サポートベクターマシン（SVM）やその他のカーネル化モデルで一般的に使用されるカーネル関数であり、元の変数の多項式上の特徴空間におけるベクトル（訓練サンプル）の類似性を表し、非線形モデルの学習を可能にします。

直感的に言えば、多項式カーネルは入力サンプルの与えられた特徴だけでなく、それらの組み合わせも考慮して類似性を判断します。回帰分析の文脈では、このような組み合わせは相互作用特徴として知られています。多項式カーネルの（暗黙的な）特徴空間は多項式回帰のそれと同等ですが、学習するパラメータ数の組み合わせ爆発はありません。入力特徴がバイナリ値（ブール値）の場合、特徴は入力特徴の論理積に対応します。^{[ 1 ]}

次数d の多項式の場合、多項式カーネルは次のように定義されます^{[ 2 ]}

${\displaystyle K(\mathbf {x} ,\mathbf {y} )=(\mathbf {x} ^{\mathsf {T}}\mathbf {y} +c)^{d}}$

ここで、xとyは入力空間におけるサイズnのベクトル、すなわちトレーニングまたはテスト サンプルから計算された特徴のベクトルであり、c ≥ 0は多項式の高次項と低次項の影響をトレードオフする自由パラメータです。c = 0 の場合、カーネルは均質であると呼ばれます。^{[ 3 ]} (さらに一般化された多項式カーネルは、x ^T y をユーザー指定のスカラー パラメータaで割ります。^{[ 4 ]} )

カーネルとして、K はあるマッピングφに基づく特徴空間における内積に対応する。

${\displaystyle K(\mathbf {x} ,\mathbf {y} )=\langle \varphi (\mathbf {x} ),\varphi (\mathbf {y} )\rangle }$

φの性質は例から見ることができます。d = 2 とすると、二次カーネルの特殊なケースが得られます。多項定理(2 回 - 最も外側の適用は二項定理) を使用し、再編成すると、

${\displaystyle K(\mathbf {x} ,\mathbf {y} )=\left(\sum _{i=1}^{n}x_{i}y_{i}+c\right)^{2}=\sum _{i=1}^{n}\left(x_{i}^{2}\right)\left(y_{i}^{2}\right)+\sum _{i=2}^{n}\sum _{j=1}^{i-1}\left({\sqrt {2}}x_{i}x_{j}\right)\left({\sqrt {2}}y_{i}y_{j}\right)+\sum _{i=1}^{n}\left({\sqrt {2c}}x_{i}\right)\left({\sqrt {2c}}y_{i}\right)+c^{2}}$

このことから、特徴マップは次のように与えられることがわかる。

${\displaystyle \varphi (x)=\left(x_{n}^{2},\ldots ,x_{1}^{2},{\sqrt {2}}x_{n}x_{n-1},\ldots ,{\sqrt {2}}x_{n}x_{1},{\sqrt {2}}x_{n-1}x_{n-2},\ldots ,{\sqrt {2}}x_{n-1}x_{1},\ldots ,{\sqrt {2}}x_{2}x_{1},{\sqrt {2c}}x_{n},\ldots ,{\sqrt {2c}}x_{1},c\right)}$

一般化する${\displaystyle \left(\mathbf {x} ^{T}\mathbf {y} +c\right)^{d}}$、 どこ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$、${\displaystyle \mathbf {y} \in \mathbb {R} ^{n}}$そして多項定理を適用すると：

${\displaystyle {\begin{alignedat}{2}\left(\mathbf {x} ^{T}\mathbf {y} +c\right)^{d}&=\sum _{j_{1}+j_{2}+\dots +j_{n+1}=d}{\frac {\sqrt {d!}}{\sqrt {j_{1}!\cdots j_{n}!j_{n+1}!}}}x_{1}^{j_{1}}\cdots x_{n}^{j_{n}}{\sqrt {c}}^{j_{n+1}}{\frac {\sqrt {d!}}{\sqrt {j_{1}!\cdots j_{n}!j_{n+1}!}}}y_{1}^{j_{1}}\cdots y_{n}^{j_{n}}{\sqrt {c}}^{j_{n+1}}\\&=\varphi (\mathbf {x} )^{T}\varphi (\mathbf {y} )\end{alignedat}}}$

最後の総和は${\displaystyle l_{d}={\tbinom {n+d}{d}}}$要素によって、次のようになります。

${\displaystyle \varphi (\mathbf {x} )=\left(a_{1},\dots ,a_{l},\dots ,a_{l_{d}}\right)}$

どこ${\displaystyle l=(j_{1},j_{2},...,j_{n},j_{n+1})}$そして

${\displaystyle a_{l}={\frac {\sqrt {d!}}{\sqrt {j_{1}!\cdots j_{n}!j_{n+1}!}}}x_{1}^{j_{1}}\cdots x_{n}^{j_{n}}{\sqrt {c}}^{j_{n+1}}\quad |\quad j_{1}+j_{2}+\dots +j_{n}+j_{n+1}=d}$

RBFカーネルはSVM分類では多項式カーネルよりも人気がありますが、後者は自然言語処理（NLP）では非常に人気があります。^{[ 1 ] [ 5 ]} 最も一般的な次数はd = 2 （二次）です。次数が大きいとNLP問題で過学習する傾向があるためです。

多項式カーネルを計算するさまざまな方法（正確な方法と近似的な方法の両方）が、通常の非線形SVMトレーニングアルゴリズムの代替として考案されており、以下のようなものがある。

• 線形SVMによるトレーニング/テストの前にカーネルを完全に展開する^{[ 5 ]} 、つまり多項式回帰のようにマッピングφを完全に計算する。
• バスケットマイニング（アソシエーションアルゴリズムの変種を使用）により、トレーニングセット内で最も頻繁に出現する特徴の組み合わせを抽出し、近似的な展開を生成する。^{[ 6 ]}
• サポートベクターの逆インデックス付け。^{[ 6 ] [ 1 ]}

多項式カーネルの問題点の1つは、数値的不安定性に悩まされる可能性があることです。x T y + c < 1 の場合、^K ( x , y ) = ( x T y + ^c ) dはd^の増加とともにゼロに近づきますが、 x ^T y + c > 1の場合、K ( x , y ) は無限大に近づきます。^{[ 4 ]}

^{[ 7 ]}