Sztring- és n -gramm-kernelek

Az SVM esetén az 5. fejezetben láttuk, hogy nemlineáris dimenziónövelő transzformációkkal bizonyos osztályozási feladatok lineárisan szeparálhatóvá válnak.

A szövegosztályozás során van két kifogásolható lépés: a szózsákmodellel elvesztünk információkat a szövegből, amelynek következtében az esetleg nem lesz lineárisan szeparálható, majd nemlineáris transzformációkkal megpróbáljuk újra azzá tenni. Kézenfekvő lenne egy olyan reprezentáció, amely e két lépés kihagyásával több információt őriz meg a szövegből.

A skaláris szorzat, illetve ennek általánosabb változata a kernelfüggvény tulajdonképpen két dokumentum hasonlóságát mondja meg. A kapott modell pedig lényegében azt mondja, hogy a tesztdokumentumhoz hasonlóbb dokumentumok kategoriáját nagyobb súllyal vegyük figyelembe a tesztdokumentum kategóriájának meghatározásakor.

Egy jó reprezentációtól az alábbi három tulajdonságot várjuk el:

A sztring- és n -gramm kernelek megfelelnek ezeknek a követelményeknek.

Az n -gramm kernelek (NGK) esetén a szöveg minden n darab szomszédos karakteréből (a szóközt is beleértve) külön jellemzőt képezünk, ahol n egy rögzített konstans. Pl. a bányászat szó trigrammjai: bán, ány, nyá, yás, ász, sza, zat. Az n -gramm kernelek elsősorban akkor hasznosak, ha a szövegben hibák vannak — pl. elírások vagy egy optikai karakterfelismerő hibái. Természetesen a szomszédos betűk helyett tekinthetünk szomszédos szavakat is, ami a szózsákmodellhez képest több információt őriz meg a szövegből.

A sztringkerneleket (string subsequence kernel; SSK) Lodhi és társai javasolták dokumentum osztályozási feladatokra (Lodhi et al, 2002). A sztringkernelek lényegesen bonyolultabbak, mint az n -gramm kernelek. Két szabad paraméterük van: n és λ . Az előbbi a karakterek számát szabályozza, az utóbbi a súlyértéket adja meg.

A szavak (dokumentumok) minden n darab karaktert tartalmazó nem feltétlenül egybefüggő részszavából (dokumentumszegmensből) jellemző lesz: pl. n= 2  esetén a x = „oldal”  szóból először az alábbi listát állítjuk elő:

[ ol_ _ _: λ2  ,  _ ld_ _: λ2  ,  _ _ da_: λ2  ,  _ _ _ al: λ2  ,  o_ d_ _: λ3  ,  _ l_ a_: λ3  ,  _ _ d_ l: λ2  ,  o_ _ a_: λ4  ,  _ l_ _ l: λ4  ,  o_ _ _ l: λ5  ].

n= 3  esetén az alábbi listát állítjuk elő ugyanebből a szóból:

[ old_ _λ3  ,  _ lda_λ3  ,  _ _ dalλ3  ,  ol_ a_λ4  ,  _ ld_ lλ4  ,  o_ da_λ4  ,  _l_ alλ4  ,  ol_ _ lλ5  ,  o_ _ al       λ5  ,  o_ d_ l                    λ5  ].

Vagyis n= 2  esetén az összes lehetséges módon megtartunk 2 karaktert, n = 3  esetén az összes lehetséges módon megtartunk 3 karaktert. Mivel az „oldal” szó 5 hosszú, ezért Γ5Δ
 2 = 10  illetve Γ5Δ
3  = 10  eleműek a listáink.

A továbbiakban csak az n=  2  esetet vizsgáljuk. A kapott lista elemiből töröljük az _ karaktert, és az ismétlődő elemekhez rendelt súlyokat összeadjuk (ismétlődést most csak az ol és az o_ _ _ l okoz):

[ alλ2  ,   daλ2  ,   dlλ2  ,   laλ3  ,   ldλ2  ,   llλ4  ,   oaλ4  ,   odλ3  ,   olλ2+ λ5  ].

Ezt a listát tekinthetjük úgy, mint egy dokumentumot, amelyben az al sztring súlya λ2  , a da sztring súlya  2
λ  , . . . , az ol sztring súlya   2   5
λ  + λ  . Minden szóhoz hozzárendeljük a vektortér egy koordinátáját, a koordináta súlya pedig a listában megadott súly lesz, így adódik φ(x)  .

A sztringkernelek használata során először rögzítjük a két paramétert, n -et és λ -t. Ezután két dokumentum, d
 1  és d
 2  hasonlóságának kiszámításához kiszámítjuk mindkettőnek a sztringkerneleknek megfelelő reprezentációját, φ(d1)  -et és φ(d2)  -t, majd ezeket a vektorokat skalárisan összeszorozzuk. A d dokumentum (hosszát jelöle ∣d∣ ) reprezentációja kiszámításának menete általános esetben:

Az itt leírt módszer meglehetősen lassú,   Γ∣d∣Δ
O(  n )  futási idejű, azonban dinamikus programozással a kernelfüggvény értéke (a skalárszorzat) kiszámítható O(n ⋅∣d1∣⋅∣d2∣)  időben is (Lodhi et al, 2002).

A hivatkozott cikkben leírt kisérletek során az n -gramm kernelek mindig jobbnak bizonyultak a hagyományos tf-idf modellnél a Reuters-21578 korpuszon, n = 5  mellett. A sztringkernel tekinthető az n -gramm kernel általánosításának: nagyon kis λ esetén a nem összefüggő részszavak sokkal kisebb súlyt kapnak, mint az összefüggőek, így λ → 0  esetén a sztringkernelek és az n -gramm kernelek egyre hasonlóbb eredményt adnak. Így aztán nem is csoda, hogy a sztringkernelek jobbnak bizonyultak, mint az n -gramm kernelek. A meglepő az, hogy az SSK az NGK-hoz képest a vizsgált 4 kategória (earn, acq, crude, corn) közül mindössze 1 esetben volt lényegesen jobb, és 1 esetben kicsit jobb.

Forrás:

H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, and C. Watkins. Text classification using string kernels. J. of Machine Learning Research, 2:419–444, 2002.