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

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

Использование строковых ядер с кернеризованными алгоритмами обучения, такими как машины опорных векторов, позволяет таким алгоритмам работать со строками без необходимости преобразовывать их в векторы признаков фиксированной длины с действительными значениями . ^[1] Строковые ядра используются в областях, где данные о последовательностях должны быть кластеризованы или классифицированы , например, при интеллектуальном анализе текста и анализе генов . ^[2]

Неофициальное знакомство

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

Мотивация

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

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

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

Определение

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

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

Теперь мы можем воспроизвести определение ядра строковой подпоследовательности. ^[1]на струнах над алфавитом $\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.

The $\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)$ , только внутренний продукт через ядро, что может быть намного быстрее, особенно при аппроксимации . ^[1]

Ссылки

^ Jump up to: ^а ^б ^с Лодхи, Хума; Сондерс, Крейг; Шоу-Тейлор, Джон; Кристианини, Нелло; Уоткинс, Крис (2002). «Классификация текста с использованием строковых ядер». Журнал исследований машинного обучения : 419–444.
^ Лесли, К.; Эскин, Э.; Ноубл, WS (2002), «Ядро спектра: строковое ядро для классификации белков SVM», Proceedings of the Pacific Symposium on Biocomputing , vol. 7, стр. 566–575, PMID 11928508.
^ Амайри, О. (2009), «Улучшенная онлайн-фильтрация спама векторными машинами поддержки с использованием строковых ядер», Прогресс в распознавании образов, анализе изображений, компьютерном зрении и приложениях , Конспекты лекций по информатике, том. 5856, с. 621, Bibcode : 2009LNCS.5856..621A , doi : 10.1007/978-3-642-10268-4_73 , ISBN 978-3-642-10267-7
^ Гертнер, Т. (2003), «Обзор ядер для структурированных данных», Информационный бюллетень ACM SIGKDD Explorations , 5 (1), ACM : 58, doi : 10.1145/959242.959248 , S2CID 4471326
^ Куанг, Руи; То есть, Евгений; Ван, Кэ; Ван, Кай; Сиддики, Махира; Фройнд, Йоав; Лесли, Кристина (1 июня 2005 г.). «Строковые ядра на основе профилей для удаленного обнаружения гомологии и извлечения мотивов». Журнал биоинформатики и вычислительной биологии . 3 (3): 527–550. дои : 10.1142/s021972000500120x . ISSN 0219-7200 . ПМИД 16108083 . S2CID 14032548 .

[Lodhi-1] Jump up to: ^а ^б ^с Лодхи, Хума; Сондерс, Крейг; Шоу-Тейлор, Джон; Кристианини, Нелло; Уоткинс, Крис (2002). «Классификация текста с использованием строковых ядер». Журнал исследований машинного обучения : 419–444.

[2] Лесли, К.; Эскин, Э.; Ноубл, WS (2002), «Ядро спектра: строковое ядро для классификации белков SVM», Proceedings of the Pacific Symposium on Biocomputing , vol. 7, стр. 566–575, PMID 11928508.

[3] Амайри, О. (2009), «Улучшенная онлайн-фильтрация спама векторными машинами поддержки с использованием строковых ядер», Прогресс в распознавании образов, анализе изображений, компьютерном зрении и приложениях , Конспекты лекций по информатике, том. 5856, с. 621, Bibcode : 2009LNCS.5856..621A , doi : 10.1007/978-3-642-10268-4_73 , ISBN 978-3-642-10267-7

[4] Гертнер, Т. (2003), «Обзор ядер для структурированных данных», Информационный бюллетень ACM SIGKDD Explorations , 5 (1), ACM : 58, doi : 10.1145/959242.959248 , S2CID 4471326

[5] Куанг, Руи; То есть, Евгений; Ван, Кэ; Ван, Кай; Сиддики, Махира; Фройнд, Йоав; Лесли, Кристина (1 июня 2005 г.). «Строковые ядра на основе профилей для удаленного обнаружения гомологии и извлечения мотивов». Журнал биоинформатики и вычислительной биологии . 3 (3): 527–550. дои : 10.1142/s021972000500120x . ISSN 0219-7200 . ПМИД 16108083 . S2CID 14032548 .

[1]

[2]

[3]

[4]

[5]