Русская Википедия:Строковое ядро
Строковое ядро — это ядерная функция, определённая на строках, т.е. конечных последовательностях символов, которые не обязательно имеют одну и ту же длину. Строковые ядра можно интуитивно понимать как функции, измеряющие похожесть пар строк — чем больше похожи две строки a и b, тем больше значение строкового ядра K(a, b).
Использование строковых ядер с ядерных алгоритмами обучения, таких как метод опорных векторов, позволяет таким алгоритмам работать со строками без необходимости преобразовывать их к векторам признаков постоянной длины, имеющих вещественные элементыШаблон:Sfn. Строковые ядра используются в областях, где кластеризуется или классифицируется последовательность данных, например, при обработке текстовых данных и анализе геновШаблон:Sfn.
Неформальное введение
Предположим, что кто-то собирается сравнить два фрагмента текста автоматически и определить их относительную похожесть. Для многих приложений может быть достаточным найти некоторые полностью совпадающие ключевые слова. Примером, когда такое точное совпадение не всегда достаточно, можно найти в детекторах спамаШаблон:Sfn. Другим примером может служить компьютерный анализ генов, в котором гомологичные гены имеют мутации, при которых в общей последовательности символы могут быть удалены, вставлены или заменены.
Предпосылки
Поскольку некоторые хорошо себя зарекомендовавшие методы кластеризации, классификации и извлечения информации из данных (например, метод опорных векторов) разработаны для работы с векторами (т.е. данные представляют элементы векторного пространства), использование строкового ядра позволяет распространить эти методы на последовательные данные.
Метод строкового ядра контрастирует с распространёнными до его появления подходами для классификации текстов, где вектора признаков показывали только присутствие или отсутствие слова. Это не только улучшило существовавшие подходы, но и является примером, как весь класс ядер адаптируется под структуры данных, которые начали появляться в 21-м веке. Обзор таких методов сделал ГэртнерШаблон:Sfn.
В биоинформатике строковые ядра используются для преобразования биологических последовательностей, таких как протеины или ДНК, в вектора для дальнейшего использования в моделях машинного обучения. Примером строкового ядра для таких целей является профильное ядроШаблон:Sfn.
Определение
Ядро области D — это функция <math>K : D \times D \to \R</math>, удовлетворяющая некоторым условиям (симметричная по аргументам, непрерывная, Шаблон:Не переведено 5 в некотором смысле).
Шаблон:Не переведено 5 утверждает, что К может затем быть выражен как <math>K(x, y) = \varphi(x) \cdot \varphi(y)</math> c функцией <math>\varphi</math>, отображающей аргументы в пространство со скалярным произведением.
Мы можем теперь воспроизвести определение ядра строковых подпоследовательностейШаблон:Sfn над строками из алфавита <math>\Sigma</math>. Покоординатно отображение определяется следующим образом:
- <math>\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. </math>
Индексы <math>\mathbf{i}</math> являются мультииндексами, а u является строкой длины n — подпоследовательности могут оказаться разрывными, но промежутки штрафуются. Мультииндекс <math>\mathbf{i}</math> задаёт позиции соответствия символов в u и s. <math>l(\mathbf{i})</math> является разницей между первым и последним элементом в <math>\mathbf{i}</math>, то есть как далеко отстоит подпоследовательность в s от соответствующей ей подпоследовательности в u. Параметр <math>\lambda</math> может быть установлен в любое значение между 0 (промежутки не разрешены, так как только 00 равно не 0, а 1) и 1 (подпоследовательности даже с большими расстояниями весят столько же, сколько и без расстояний, то есть как непрерывные подпоследовательности), так как <math>1^{l(\mathbf{i})} = 1</math>.
Для некоторых важных алгоритмов данные получаются алгоритмом только в выражениях, использующих скалярное произведение от вектора признаков, вследствие чего они и получили название ядерные методы. Поэтому желательно, чтобы не нужно было явно вычислять преобразование <math>\varphi(x)</math>, а можно было бы вычислять только скалярное произведение через ядро, что может быть много быстрее, особенно при применении аппроксимацииШаблон:Sfn.
Примечания
Литература
Шаблон:Refend Шаблон:Машинное обучение Шаблон:Rq
