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

У машинному навчанні та добуванні даних стрічкове ядро (англ. string kernel) — це ядрова функція, яка діє на стрічках, тобто, скінченних послідовностях символів, які не мають бути однакової довжини. Стрічкові ядра можна інтуїтивно розуміти як функції, які вимірюють подібність пар стрічок: що подібнішими є дві стрічки a та b, то вищим буде значення стрічкового ядра K(a, b).

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

Неформальне введення

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

Спонукання

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

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

Визначення

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

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

Тепер ми можемо відтворити визначення ядра стрічкових підпослідовностей (англ. string subsequence kernel) на стрічках над абеткою $\Sigma$. Відображення визначається покоординатно наступним чином:

$\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.$

$\mathbf {i}$ є мультиіндексами, а $u$ є стрічкою довжини $n$: підпослідовності можуть траплятися не неперервними, але прогалини штрафуються. Мультиіндекс $\mathbf {i}$ задає положення символів, які збігаються з $u$, в $s$. $l(\mathbf {i} )$ є різницею між першим та останнім елементами $\mathbf {i}$, тобто: наскільки розкиданою в $s$ є підпослідовність, що збігається з $u$. Параметр $\lambda$ може бути встановлено в будь-яке значення між $0$ (прогалини не дозволено, оскільки лише $0^{0}$ є не $0$, а $1$) та $1$ (навіть широко рознесені «трапляння» зважуються однаково із присутностями як неперервний підрядок, оскільки $1^{l(\mathbf {i} )}=1$).

Для декількох відповідних алгоритмів дані надходять до алгоритму лише у виразах, що включають внутрішній добуток векторів ознак, звідси й назва ядрові методи. Бажаним наслідком цього є відсутність потреби в явному обчисленні перетворення $\phi (x)$, а лише внутрішніх добутків через ядро, яке може бути набагато швидшим, особливо якщо воно наближене.