文字列カーネル

機械学習やデータマイニングにおいて、文字列カーネルとは、文字列（長さが必ずしも同じである必要のない、有限個の記号のシーケンス）に対して作用するカーネル関数です。文字列カーネルは、直感的には文字列のペアの類似性を測定する関数として理解できます。つまり、2つの文字列aとbが似ているほど、文字列カーネルK ( a , b )の値は高くなります。

サポートベクターマシンなどのカーネル化学習アルゴリズムで文字列カーネルを使用すると、これらのアルゴリズムは文字列を固定長の実数値特徴ベクトルに変換することなく文字列を扱うことができます。^{[ 1 ]}文字列カーネルは、テキストマイニングや遺伝子解析など、シーケンスデータをクラスタリングまたは分類するドメインで使用されます。^{[ 2 ]}

テキストのいくつかのパッセージを自動的に比較し、それらの相対的な類似性を示したいとします。多くのアプリケーションでは、完全に一致するキーワードを見つけるだけで十分かもしれません。完全一致だけでは十分でない例の 1 つはスパム検出です。^{[ 3 ]}もう 1 つは、相同遺伝子が突然変異を起こし、削除、挿入、または置換されたシンボルとともに共通のサブシーケンス が生じる計算遺伝子解析です。

データクラスタリング、分類、情報検索の手法（例えばサポートベクターマシン）の多くは ベクトル（つまりデータはベクトル空間の要素）を扱うように設計されているため、文字列カーネルを使用することで、これらの手法を拡張してシーケンスデータを処理できるようになります。

文字列カーネル法は、特徴ベクトルが単語の有無のみを示す従来のテキスト分類手法とは対照的です。この手法は、従来の手法を改良するだけでなく、21世紀初頭に登場し始めたデータ構造に適合したカーネルのクラス全体の例でもあります。このような手法の調査は、Gärtnerによってまとめられています。^{[ 4 ]}

バイオインフォマティクスでは、特にタンパク質やDNAなどの生物学的配列を、機械学習モデルでさらに使用するためのベクトルに変換するために、文字列カーネルが使用されます。その目的で使用される文字列カーネルの例として、プロファイルカーネルがあります。^{[ 5 ]}

ドメイン上のカーネル${\displaystyle D}$関数です${\displaystyle K:D\times D\rightarrow \mathbb {R} }$ いくつかの条件を満たす（引数に関して対称であること、連続であること、ある意味で正半定値であること）。

マーサーの定理は次のように主張する。${\displaystyle K}$すると次のように表現できる。${\displaystyle K(x,y)=\varphi (x)\cdot \varphi (y)}$と${\displaystyle \varphi }$引数を内積空間にマッピングする。

これで、アルファベット 上の文字列に対する文字列部分列カーネルの定義^{[ 1 ]}を再現できる。${\displaystyle \Sigma }$座標に関しては、マッピングは次のように定義されます。

${\displaystyle \varphi _{u}:\left\{{\begin{array}{l}\Sigma ^{n}\rightarrow \mathbb {R} ^{\Sigma ^{n}}\\s\mapsto \sum _{\mathbf {i} :u=s_{\mathbf {i} }}\lambda ^{l(\mathbf {i} )}\end{array}}\right.}$

の${\displaystyle \mathbf {i} }$はマルチインデックスであり、${\displaystyle u}$長さの文字列です${\displaystyle n}$部分列は非連続的に出現する可能性がありますが、ギャップはペナルティの対象となります。マルチインデックス${\displaystyle \mathbf {i} }$一致する文字の位置を示します${\displaystyle u}$で${\displaystyle s}$。${\displaystyle l(\mathbf {i} )}$は、最初のエントリと最後のエントリの差です。${\displaystyle \mathbf {i} }$つまり、${\displaystyle s}$部分列のマッチング${\displaystyle u}$パラメータは${\displaystyle \lambda }$任意の値に設定できます。${\displaystyle 0}$（ギャップは許可されていません。${\displaystyle 0^{0}}$ではない${\displaystyle 0}$しかし${\displaystyle 1}$） そして${\displaystyle 1}$ （広く分布している「出現」も、連続する部分文字列としての出現と同じ重み付けがされます。${\displaystyle 1^{l(\mathbf {i} )}=1}$)

いくつかの関連アルゴリズムでは、データは特徴ベクトルの内積を含む式でのみアルゴリズムに入力されるため、カーネル法と呼ばれます。このことの望ましい結果として、変換を明示的に計算する必要がなくなります。${\displaystyle \phi (x)}$カーネルを介した内積のみで、特に近似するとはるかに速くなる可能性があります。^{[ 1 ]}