Стрічкове ядро

Припустімо, що потрібно автоматично порівнювати уривки текстів та вказувати їхню відносну подібність. Для багатьох застосувань може бути достатнім знаходити деякі ключові слова, які збігаються точно. Одним із прикладів, де точної відповідності не завжди достатньо, є виявлення спаму.[3] Іншим міг би бути обчислювальний аналіз генів, у якому гомологічні гени мутували, в результаті чого спільні послідовності мають вилучені, вставлені або замінені символи.

Оскільки деякі добре доведені методи кластерування, класифікації та добування інформації (наприклад, метод опорних векторів) розроблено для роботи з векторами (тобто, дані є елементами векторного простору), застосування стрічкових ядер уможливлює поширення цих методів на обробку даних послідовностей.

Стрічково-ядровий протиставляється ранішим підходам до класифікації текстів, де вектори ознак лише вказували на наявність або відсутність певного слова. Він не лише вдосконалює ці підходи, а й є прикладом цілого класу ядер, пристосованих до структур даних, як почали з'являтися на рубежі XXI сторіччя. Огляд цих методів було складено Гертнером.[4]

Ядром на області визначення ${\displaystyle D}$ є функція ${\displaystyle K:D\times D\rightarrow \mathbb {R} }$, яка задовольняє деякі умови (є симетричною за аргументами, неперервною та додатно напівозначеною в певному сенсі).

Теорема Мерсера стверджує, що тоді ${\displaystyle K}$ може бути виражено як ${\displaystyle K(x,y)=\varphi (x)\cdot \varphi (y)}$, де ${\displaystyle \varphi }$ відображує аргументи до простору з внутрішнім добутком.

Тепер ми можемо відтворити визначення ядра стрічкових підпослідовностей (англ. string subsequence kernel)[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]