Strunové jádro

Řetězcové jádro je funkce jádra definovaná na řetězcích , tzn. konečné sekvence znaků, které nemusí mít nutně stejnou délku. Řetězcová jádra lze intuitivně chápat jako funkce, které měří podobnost párů řetězců – čím jsou si dva řetězce a a b podobnější , tím větší je hodnota jádra řetězce K(a, b) .

Použití řetězcových jader s algoritmy učení jádra , jako jsou podpůrné vektorové stroje , umožňuje takovým algoritmům pracovat s řetězci, aniž by je bylo nutné převádět na vektory znaků konstantní délky, které mají skutečné prvky [1] . Řetězcová jádra se používají v oblastech, kde je sekvence dat seskupena nebo klasifikována, jako je zpracování textových dat a genová analýza [2] .

Neformální úvod

Předpokládejme, že někdo automaticky porovná dva kusy textu a určí jejich relativní podobnost. Pro mnoho aplikací může stačit najít zcela odpovídající klíčová slova. Příklad, kdy taková přesná shoda není vždy dostatečná, lze nalézt v detektorech spamu [3] . Dalším příkladem je počítačová genová analýza, ve které mají homologní geny mutace , ve kterých mohou být znaky v celkové sekvenci odstraněny, vloženy nebo nahrazeny.

Pozadí

Vzhledem k tomu, že některé dobře zavedené metody shlukování, klasifikace a extrahování informací z dat (například podpůrný vektorový stroj) jsou navrženy pro práci s vektory (tj. data představují prvky vektorového prostoru), umožňuje použití řetězcového jádra tyto metody rozšířit na sekvenční data.

Metoda string kernel kontrastuje s přístupy klasifikace textu běžnými před jeho objevením, kde příznakové vektory ukazovaly pouze přítomnost nebo nepřítomnost slova. To nejen zlepšilo stávající přístupy, ale je to také příklad toho, jak se celá třída jader přizpůsobuje datovým strukturám, které se začaly objevovat v 21. století. Přehled takových metod provedl Gärtner [4] .

V bioinformatice se jádra řetězce používají k transformaci biologických sekvencí, jako jsou proteiny nebo DNA, na vektory pro další použití v modelech strojového učení. Příkladem řetězcového jádra pro takové účely je jádro profilu [5] .

Definice

Jádro domény D je funkce , která splňuje některé podmínky ( symetrická v argumentech, spojitá , v určitém smyslu kladně definitní

Mercerův teorém říká, že K lze potom vyjádřit jakoc funkcemapující argumenty do prostoru tečkového součinu .

Nyní můžeme reprodukovat definici jádra řetězcových podsekvencí [1] přes řetězce z abecedy . Souřadnicové mapování je definováno takto:

Indexy jsou multiindexy a u je řetězec délky n – podsekvence mohou být nespojité, ale mezery jsou penalizovány. Multi-index určuje odpovídající pozice znaků v u a s . je rozdíl mezi prvním a posledním prvkem v , to znamená, jak daleko je dílčí posloupnost v s od odpovídající dílčí posloupnosti v u . Parametr lze nastavit na libovolnou hodnotu mezi 0 (mezery nejsou povoleny, protože pouze 0 0 není 0, ale 1) a 1 (podsekvence i s velkými vzdálenostmi váží stejně jako bez vzdáleností, tedy jako spojité podsekvence), od .

U některých důležitých algoritmů jsou data získávána algoritmem pouze ve výrazech využívajících skalární součin příznakového vektoru, proto se nazývají metody jádra . Proto je žádoucí, aby nebylo nutné explicitně počítat transformaci , ale bylo možné vypočítat pouze skalární součin přes jádro, což může být mnohem rychlejší, zvláště při použití aproximace [1] .

Poznámky

  1. ↑ 1 2 3 Lodhi, Saunders, Shawe-Taylor, Cristianini, Watkins, 2002 , str. 419-444.
  2. ↑ Leslie, Eskin, Noble, 2002 , str. 566-575.
  3. ↑ Amayri, Bouguila .
  4. ↑ Gartner, 2003 .
  5. ↑ Kuang, Ie, Wang a kol., 2005 , str. 527-550.

Literatura