Jądro ciągu

W uczeniu maszynowym i eksploracji danych jądro łańcuchowe jest funkcją jądra , która działa na ciągach znaków , tj. skończonych sekwencjach symboli, które nie muszą mieć tej samej długości. Jądra łańcuchów można intuicyjnie rozumieć jako funkcje mierzące podobieństwo par łańcuchów: im bardziej podobne są dwa łańcuchy a i b , tym wyższa będzie wartość jądra łańcucha K ( a , b ).

Używanie jąder ciągów z algorytmami uczenia się opartymi na jądrze , takimi jak maszyny wektorów nośnych , umożliwia takim algorytmom pracę z łańcuchami bez konieczności tłumaczenia ich na wektory cech o stałej długości i wartościach rzeczywistych . Jądra łańcuchowe są używane w dziedzinach, w których dane sekwencyjne mają być grupowane lub klasyfikowane , np. w eksploracji tekstu i analizie genów .

Nieformalne wprowadzenie

Załóżmy, że chcemy automatycznie porównać niektóre fragmenty tekstu i wskazać ich względne podobieństwo. W przypadku wielu aplikacji może wystarczyć znalezienie dokładnie pasujących słów kluczowych. Przykładem sytuacji, w której dokładne dopasowanie nie zawsze wystarcza, jest wykrywanie spamu . Innym byłaby obliczeniowa analiza genów, w której geny homologiczne uległy mutacji , w wyniku czego powstały wspólne podsekwencje wraz z usuniętymi, wstawionymi lub zastąpionymi symbolami.

Motywacja

Ponieważ kilka dobrze sprawdzonych metod grupowania danych, klasyfikacji i wyszukiwania informacji (na przykład maszyny wektorów nośnych) jest zaprojektowanych do pracy na wektorach (tj. dane.

Metodę jądra łańcuchowego należy przeciwstawić wcześniejszemu podejściu do klasyfikacji tekstu, w którym wektory cech wskazywały jedynie na obecność lub brak słowa. Nie tylko usprawnia te podejścia, ale jest przykładem dla całej klasy jąder dostosowanych do struktur danych, które zaczęły pojawiać się na przełomie XIX i XX wieku. Przegląd takich metod został opracowany przez Gärtnera.

W bioinformatyce jądra strun są wykorzystywane zwłaszcza do przekształcania sekwencji biologicznych, takich jak białka czy DNA, w wektory do dalszego wykorzystania w modelach uczenia maszynowego. Przykładem jądra łańcuchowego używanego do tego celu jest jądro profilu.

Definicja

Jądro w domenie $pewne$ funkcja $.$ ( symetryczna w argumentach _ dodatni półokreślony w pewnym sensie).

$Twierdzenie$ Mercera twierdzi, że można następnie wyrazić jako $\ varphi (y)}$ z $iloczynu$ argumentów na wewnętrzną przestrzeń .

Możemy teraz odtworzyć definicję jądra podsekwencji ciągów na ciągach nad alfabetem ${\ displaystyle \ Sigma}$ . Pod względem współrzędnych mapowanie jest zdefiniowane w następujący sposób:

${\ Displaystyle \ varphi _ {u}: \ lewo \ {{\ rozpocząć {tablica} {l} \ Sigma ^ {n}\rightarrow \mathbb {R} ^{\Sigma ^{n}}\\s\mapsto \sum _{\mathbf {i} :u=s_{\mathbf {i} }}\lambda ^{l (\mathbf {i} )}\end{tablica}}\right.}$

$multiindeksy$ to i jest ciągiem o długości $karane$$podsekwencje mogą występować$ w sposób nieciągły, ale przerwy są Multiindex podaje pozycje pasujących znaków $displaystyle$ s ${$$s$ } ${\ Displaystyle l (\ mathbf {i})}$$między$ pierwszym a ostatnim wpisem w $:$ jak daleko od siebie $w$ jest . Parametr może być ustawiony na dowolną wartość pomiędzy ${\ displaystyle$$0}$ (przerwy nie są dozwolone, ponieważ tylko $\ displaystyle 0 ^ {0}}$ nie jest ${\ displaystyle 0}$ , ale ${\ displaystyle 1}$ ) i ${\ displaystyle 1}$ (nawet szeroko rozpowszechnione „zdarzenia” mają taką samą wagę jak występy jako ciągły podciąg, ponieważ ${\ Displaystyle 1 ^ {l (\ mathbf {i})} = 1}$ ).

W przypadku kilku odpowiednich algorytmów dane są wprowadzane do algorytmu tylko w wyrażeniach obejmujących iloczyn wewnętrzny wektorów cech, stąd nazwa metody jądra . Pożądaną konsekwencją tego $iloczyn$ że nie trzeba jawnie obliczać transformacji wewnętrzny przez jądro, co może być znacznie szybsze, zwłaszcza w przybliżeniu .