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

Предположим, что кто-то собирается сравнить два фрагмента текста автоматически и определить их относительную похожесть. Для многих приложений может быть достаточным найти некоторые полностью совпадающие ключевые слова. Примером, когда такое точное совпадение не всегда достаточно, можно найти в детекторах спама[3]. Другим примером может служить компьютерный анализ генов, в котором гомологичные гены имеют мутации, при которых в общей последовательности символы могут быть удалены, вставлены или заменены.

Поскольку некоторые хорошо себя зарекомендовавшие методы кластеризации, классификации и извлечения информации из данных (например, метод опорных векторов) разработаны для работы с векторами (т.е. данные представляют элементы векторного пространства), использование строкового ядра позволяет распространить эти методы на последовательные данные.

Метод строкового ядра контрастирует с распространёнными до его появления подходами для классификации текстов, где вектора признаков показывали только присутствие или отсутствие слова. Это не только улучшило существовавшие подходы, но и является примером, как весь класс ядер адаптируется под структуры данных, которые начали появляться в 21-м веке. Обзор таких методов сделал Гэртнер[4].

В биоинформатике строковые ядра используются для преобразования биологических последовательностей, таких как протеины или ДНК, в вектора для дальнейшего использования в моделях обучения машин. Примером строкового ядра для таких целей является профильное ядро[5].

Ядро области D — это функция ${\displaystyle K:D\times D\to \mathbb {R} }$, удовлетворяющая некоторым условиям (симметричная по аргументам, непрерывная, положительно определённая в некотором смысле).

Теорема Мерсера утверждает, что К может затем быть выражен как ${\displaystyle K(x,y)=\varphi (x)\cdot \varphi (y)}$ c функцией ${\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} }$ являются мультииндексами, а u является строкой длины n — подпоследовательности могут оказаться разрывными, но промежутки штрафуются. Мультииндекс ${\displaystyle \mathbf {i} }$ задаёт позиции соответствия символов в u и s. ${\displaystyle l(\mathbf {i} )}$ является разницей между первым и последним элементом в ${\displaystyle \mathbf {i} }$, то есть как далеко отстоит подпоследовательность в s от соответствующей ей подпоследовательности в u. Параметр ${\displaystyle \lambda }$ может быть установлен в любое значение между 0 (промежутки не разрешены, так как только 0⁰ равно не 0, а 1) и 1 (подпоследовательности даже с большими расстояниями весят столько же, сколько и без расстояний, то есть как непрерывные подпоследовательности), так как ${\displaystyle 1^{l(\mathbf {i} )}=1}$.

Для некоторых важных алгоритмов данные получаются алгоритмом только в выражениях, использующих скалярное произведение от вектора признаков, вследствие чего они и получили название ядерные методы. Поэтому желательно, чтобы не нужно было явно вычислять преобразование ${\displaystyle \varphi (x)}$, а можно было бы вычислять только скалярное произведение через ядро, что может быть много быстрее, особенно при применении аппроксимации[1].