Karakterlánc kernel

A string kernel egy karakterláncokon definiált kernelfüggvény , azaz . véges karaktersorozatok, amelyek nem feltétlenül azonos hosszúságúak. A karakterlánc-magok intuitív módon értelmezhetők olyan függvényekként, amelyek a karakterláncpárok hasonlóságát mérik – minél jobban hasonlít az a és b karakterlánc , annál nagyobb a karakterlánc-mag K(a, b) értéke .

A karakterlánc-magok kerneltanuló algoritmusokkal , például támogató vektorgépekkel való használata lehetővé teszi, hogy az ilyen algoritmusok karakterláncokon működjenek anélkül, hogy azokat állandó hosszúságú jellemzővektorokká kellene konvertálniuk , amelyek valós elemekkel rendelkeznek [1] . A karakterlánc-magokat olyan területeken használják, ahol egy adatsorozat klaszterezett vagy osztályozott, például szöveges adatfeldolgozás és génelemzés [2] .

Informális bemutatkozás

Tegyük fel, hogy valaki automatikusan összehasonlít két szövegrészt, és meghatározza a relatív hasonlóságukat. Sok alkalmazás esetén elegendő lehet néhány teljesen egyező kulcsszót találni. Egy példa arra, amikor egy ilyen pontos egyezés nem mindig elegendő, a levélszemét -érzékelőkben [3] található . Egy másik példa a számítógépes génanalízis, amelyben a homológ gének olyan mutációkkal rendelkeznek, amelyekben a teljes szekvencia karakterei törölhetők, beilleszthetők vagy helyettesíthetők.

Háttér

Mivel néhány jól bevált módszert a klaszterezésre, az osztályozásra és az adatokból információ kinyerésére (például a támogató vektorgép) úgy terveztek, hogy vektorokkal működjenek (azaz az adatok egy vektortér elemeit képviselik), a karakterlánc-kernel használata lehetővé teszi ezeket a módszereket ki kell terjeszteni a szekvenciális adatokra.

A string kernel metódus ellentétben áll a megjelenése előtt elterjedt szövegosztályozási megközelítésekkel, ahol a jellemzővektorok csak egy szó jelenlétét vagy hiányát mutatták. Ez nemcsak a meglévő megközelítéseket javította, hanem arra is példa, hogy a kernelek egész osztálya hogyan alkalmazkodik a 21. században megjelenő adatstruktúrákhoz. Az ilyen módszerek áttekintését Gärtner [4] készítette .

A bioinformatikában a sztringmagokat biológiai szekvenciák, például fehérjék vagy DNS vektorokká történő transzformálására használják, hogy további felhasználásra kerüljenek a gépi tanulási modellekben. Az ilyen célokra szolgáló karakterlánc-kernel például a profil kernel [5] .

Definíció

A D tartomány kernelje néhány feltételt kielégítő függvény ( szimmetrikus argumentumokban, folytonos , bizonyos értelemben pozitív határozott

A Mercer-tétel kimondja, hogy K ezután kifejezhetőc függvényként, amely az argumentumokat egy pontszorzattérre képezi le .

Most már reprodukálhatjuk a karakterlánc-alszekvenciák [1] magjának definícióját az ábécé karakterláncaira . A koordináta szerinti leképezés a következőképpen definiálható:

Az indexek többindexűek , u pedig egy n hosszúságú karakterlánc - a részsorozatok lehetnek nem folytonosak, de a rések büntethetők. A többindex határozza meg az u és s karakterek egyező pozícióit . a különbség az első és az utolsó elem között , vagyis milyen messze van egy s -beli részsorozat a hozzá tartozó u -beli részsorozattól . A paraméter tetszőleges értékre állítható 0 (hézagok nem megengedettek, mivel csak a 0 0 nem 0, hanem 1) és 1 (a részsorozatok nagy távolság esetén is ugyanolyan súlyúak, mint a távolságok nélkül, azaz folytonos részsorozatok) között. óta .

Néhány fontos algoritmus esetében az algoritmus csak a jellemzővektor skaláris szorzatát használó kifejezésekben kapja meg az adatokat, ezért ezeket kernelmetódusoknak nevezzük . Ezért kívánatos, hogy ne legyen szükség a transzformáció explicit kiszámítására , hanem csak a kernelen keresztüli skaláris szorzatot lehessen kiszámítani, ami sokkal gyorsabb lehet, különösen közelítéssel [1] .

Jegyzetek

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

Irodalom