WikiSort.ru - Лингвистика

ПОИСК ПО САЙТУ | о проекте

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

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

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

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

Предпосылки

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

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

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

Определение

Ядро области D — это функция , удовлетворяющая некоторым условиям (симметричная по аргументам, непрерывная, положительно определённая[en] в некотором смысле).

Теорема Мерсера[en] утверждает, что К может затем быть выражен как c функцией , отображающей аргументы в пространство со скалярным произведением.

Мы можем теперь воспроизвести определение ядра строковых подпоследовательностей[1] над строками из алфавита . Покоординатно отображение определяется следующим образом:

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

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

Примечания

Литература

  • Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, Chris Watkins. Text classification using string kernels // Journal of Machine Learning Research. — 2002.
  • Leslie C., Eskin E., Noble W.S. Pacific Symposium on Biocomputing Proceedings. — 2002.
  • Ola Amayri, Nizar Bouguila. Improved online support vector machines spam filtering using string kernels // Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. 14th Iberoamerican Conference on Pattern Recognition, CIARP 2009, Guadalajara, Jalisco, Mexico, November 15-18. — Springer. — Т. 5856. — (Lecture Notes in Computer Science).
  • Gärtner T. A survey of kernels for structured data // ACM SIGKDD Exploration Newsletter. — ACM, 2003. Т. 5, вып. 1.
  • Rui Kuang, Eugene Ie, Ke Wang, Kai Wang, Mahira Siddiqi, Yoav Freund, Christina Leslie. Profile-based string kernels for remote homology detection and motif extraction // Journal of Bioinformatics and Computational Biology. — 2005. — Июнь (т. 3, вып. 3). ISSN 0219-720.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии