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

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

15.12.2020


Строковое ядро — это ядерная функция, определённая на строках, т.е. конечных последовательностях символов, которые не обязательно имеют одну и ту же длину. Строковые ядра можно интуитивно понимать как функции, измеряющие похожесть пар строк — чем больше похожи две строки a и b, тем больше значение строкового ядра K(a, b).

Использование строковых ядер с ядерных алгоритмами обучения, таких как метод опорных векторов, позволяет таким алгоритмам работать со строками без необходимости преобразовывать их к векторам признаков постоянной длины, имеющих вещественные элементы. Строковые ядра используются в областях, где кластеризуется или классифицируется последовательность данных, например, при обработке текстовых данных и анализе генов.

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

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

Предпосылки

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

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

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

Определение

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

Теорема Мерсера утверждает, что К может затем быть выражен как K ( x , y ) = φ ( x ) ⋅ φ ( y ) {displaystyle K(x,y)=varphi (x)cdot varphi (y)} c функцией φ {displaystyle varphi } , отображающей аргументы в пространство со скалярным произведением.

Мы можем теперь воспроизвести определение ядра строковых подпоследовательностей над строками из алфавита Σ {displaystyle Sigma } . Покоординатно отображение определяется следующим образом:

φ u : { Σ n → R Σ n s ↦ ∑ i : u = s i λ l ( i ) {displaystyle varphi _{u}:left{{egin{array}{l}Sigma ^{n} ightarrow mathbb {R} ^{Sigma ^{n}}smapsto sum _{mathbf {i} :u=s_{mathbf {i} }}lambda ^{l(mathbf {i} )}end{array}} ight.}

Индексы i {displaystyle mathbf {i} } являются мультииндексами, а u является строкой длины n — подпоследовательности могут оказаться разрывными, но промежутки штрафуются. Мультииндекс i {displaystyle mathbf {i} } задаёт позиции соответствия символов в u и s. l ( i ) {displaystyle l(mathbf {i} )} является разницей между первым и последним элементом в i {displaystyle mathbf {i} } , то есть как далеко отстоит подпоследовательность в s от соответствующей ей подпоследовательности в u. Параметр λ {displaystyle lambda } может быть установлен в любое значение между 0 (промежутки не разрешены, так как только 00 равно не 0, а 1) и 1 (подпоследовательности даже с большими расстояниями весят столько же, сколько и без расстояний, то есть как непрерывные подпоследовательности), так как 1 l ( i ) = 1 {displaystyle 1^{l(mathbf {i} )}=1} .

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