For faster navigation, this Iframe is preloading the Wikiwand page for Стрічкове ядро.

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

Матеріал з Вікіпедії — вільної енциклопедії.

У машинному навчанні та добуванні даних стрічкове ядро (англ. string kernel) — це ядрова функція[en], яка діє на стрічках, тобто, скінченних послідовностях символів, які не мають бути однакової довжини. Стрічкові ядра можна інтуїтивно розуміти як функції, які вимірюють подібність пар стрічок: що подібнішими є дві стрічки a та b, то вищим буде значення стрічкового ядра K(a, b).

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

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

[ред. | ред. код]

Припустімо, що потрібно автоматично порівнювати уривки текстів та вказувати їхню відносну подібність. Для багатьох застосувань може бути достатнім знаходити деякі ключові слова, які збігаються точно. Одним із прикладів, де точної відповідності не завжди достатньо, є виявлення спаму.[3] Іншим міг би бути обчислювальний аналіз генів, у якому гомологічні гени мутували, в результаті чого спільні послідовності мають вилучені, вставлені або замінені символи.

Спонукання

[ред. | ред. код]

Оскільки деякі добре доведені методи кластерування, класифікації та добування інформації (наприклад, метод опорних векторів) розроблено для роботи з векторами (тобто, дані є елементами векторного простору), застосування стрічкових ядер уможливлює поширення цих методів на обробку даних послідовностей.

Стрічково-ядровий протиставляється ранішим підходам до класифікації текстів, де вектори ознак лише вказували на наявність або відсутність певного слова. Він не лише вдосконалює ці підходи, а й є прикладом цілого класу ядер, пристосованих до структур даних, як почали з'являтися на рубежі XXI сторіччя. Огляд цих методів було складено Гертнером.[4]

Визначення

[ред. | ред. код]

Ядром на області визначення є функція , яка задовольняє деякі умови (є симетричною за аргументами, неперервною та додатно напівозначеною[en] в певному сенсі).

Теорема Мерсера[en] стверджує, що тоді може бути виражено як , де відображує аргументи до простору з внутрішнім добутком[en].

Тепер ми можемо відтворити визначення ядра стрічкових підпослідовностей (англ. string subsequence kernel)[1] на стрічках над абеткою . Відображення визначається покоординатно наступним чином:

є мультиіндексами, а є стрічкою довжини : підпослідовності можуть траплятися не неперервними, але прогалини штрафуються. Мультиіндекс задає положення символів, які збігаються з , в . є різницею між першим та останнім елементами , тобто: наскільки розкиданою в є підпослідовність, що збігається з . Параметр може бути встановлено в будь-яке значення між (прогалини не дозволено, оскільки лише є не , а ) та (навіть широко рознесені «трапляння» зважуються однаково із присутностями як неперервний підрядок, оскільки ).


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

Примітки

[ред. | ред. код]
  1. а б в Lodhi, Huma; Saunders, Craig; Shawe-Taylor, John; Cristianini, Nello; Watkins, Chris (2002). Text classification using string kernels (PDF). Journal of Machine Learning Research: 419—444. Архів оригіналу (PDF) за 19 листопада 2016. Процитовано 23 жовтня 2016. (англ.)
  2. Leslie, C.; Eskin, E.; Noble, W.S. (2002), The spectrum kernel: A string kernel for SVM protein classification, т. 7, с. 566—575 (англ.)
  3. Amayri, O., Improved Online Support Vector Machines Spam Filtering Using String Kernels (англ.)
  4. Gärtner, T. (2003), A survey of kernels for structured data, ACM SIGKDD Explorations Newsletter, ACM, 5 (1): 58 (англ.)
{{bottomLinkPreText}} {{bottomLinkText}}
Стрічкове ядро
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?