UNIVERZA V LJUBLJANI
FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika – 1. stopnja
Jakob Zmrzlikar Jedrne metode
Delo diplomskega seminarja
Mentor: doc. dr. Matija Pretnar
Ljubljana, 2021
Kazalo
1. Uvod 4
2. Motivacijski problem 4
2.1. Binarna klasifikacija 4
2.2. Linearna ločljivost podatkov 5
2.3. Coverjev izrek 6
3. Jedrne funkcije 7
3.1. Osnovne definicije 7
3.2. Hilbertovi prostori z reproducirajočim jedrom 8
3.3. Reprezentacijski izrek 13
3.4. Primeri jedrnih funkcij 16
4. Jedrne metode 18
4.1. Metoda podpornih vektorjev 18
4.2. Analiza glavnih komponent 21
4.3. Gaussovi procesi 24
Slovar strokovnih izrazov 27
Literatura 27
Jedrne metode
Povzetek
V diplomskem delu predstavimo jedrne funkcije in njihovo uporabo v jedrnih meto- dah. Predstavimo splošen problem binarne klasifikacije in njegovo rešitev v primeru homogene linearne ločljivosti podatkov. Preko Coverjevega izreka spoznamo po- trebo po jedrnih funkcijah. Ogledamo si Hilbertove prostore z reproducirajočim jedrom ter dokažemo Moore–Aronszajnov in reprezentacijski izrek. Navedemo ne- kaj primerov jedrnih funkcij in pravila za sestavljanje novih. Podrobneje spoznamo tri pomembne jedrne metode: metodo podpornih vektorjev, analizo glavnih kom- ponent in Gaussove procese. Spoznamo tudi povezavo med Gaussovimi procesi in drugimi metodami strojnega učenja.
Kernel methods
Abstract
In this work we present kernel functions and their use in kernel methods. We state the general problem of binary classification and its solution in case of homogene- ously linearly separable dataset. Through Cover’s theorem we recognize the need for kernel functions. We present reproducing kernel Hilbert spaces and prove the Moore–Aronszajn and representer theorems. We take a look at a few examples of kernel functions and the rules for constructing new ones. We cover three important kernel methods in depth: support vector machines, principal component analysis and Gaussian processes. We also present the link between Gaussian processes and other machine learning methods.
Math. Subj. Class. (2020): 46E22
Ključne besede: jedrne funkcije, Hilbertovi prostori z reproducirajočim jedrom Keywords: kernel functions, reproducing kernel Hilbert spaces
1. Uvod
Metode strojnega učenja se v sedanjem času uporabljajo na nešteto različnih po- dročjih. Te metode so pogosto zelo dobro raziskane v linearnih primerih, tj. ob določenih predpostavkah o linearnosti nabora podatkov, iz katerega se učijo. Iz- kaže se, da lahko veliko izmed teh metod s pomočjo t. i. jedrnih funkcij izboljšamo in posplošimo tudi na nelinearne nabore podatkov. Metodam strojnega učenja, ki uporabljajo jedrne funkcije, pravimo jedrne metode.
V razdelku 2 si ogledamo motivacijski problem ter teoretično ozadje, preko kate- rega spoznamo potrebo po uporabi jedrnih funkcij v strojnem učenju. V razdelku 3 si ogledamo teorijo jedrnih funkcij in njihovo uporabnost pri reševanju motivacij- skega problema, v razdelku 4 pa si podrobneje ogledamo nekaj izmed najbolj znanih jedrnih metod. V razdelku 2 se primarno držimo vira [4], v razdelku 3 povzemamo po [7, 16, 17], v razdelku 4 pa se držimo virov [17, 8, 15, 13].
2. Motivacijski problem
V tem razdelku si bomo ogledali določeno vrsto problemov s področja strojnega učenja ter njihovo teoretično ozadje. Ti nam bodo motivirali uvedbo jedrnih funkcij in njihovo uporabo.
2.1. Binarna klasifikacija. Naj boX neprazna množica inY ={−1,1}. Denimo, da imamo dan nabor podatkovS ={(x1, y1),(x2, y2), . . . ,(xn, yn)} ⊆X×Y. Iščemo tisto preslikavo f :X → {−1,1}, ki se bo najbolje prilegala naboru podatkov. Bolj natančno, stremimo k temu, da je
(1) f(xi) = yi za i = 1, . . . , n.
Poleg tega želimo še, da naša preslikava dobro posplošuje tudi za tiste x ∈ X, ki niso del nabora podatkov. Naš končni cilj je namreč, da za vsak nov x ∈ X čim bolje napovemo pripadajočo vrednosty∈Y. Napoved je dobra, če, ohlapno rečeno, za podobne vrednosti xnapove podobne vrednosti y. To »mero podobnosti« bomo matematično formalizirali v poglavju 3.
Preslikavo f :X → {−1,1} v tem kontekstu navadno imenujemo binarni klasifi- kator. V nadaljevanju bomo pogosto pisali samo klasifikator.
Zgoraj definiran problem imenujemo problem binarne klasifikacije. Ta vrsta pro- blemov je izjemno pogosta na področju strojnega učenja, saj lahko veliko različnih vprašanj s področja analize podatkov matematično predstavimo na ta način. Iska- nje optimalnega binarnega klasifikatorja si lahko predstavljamo kot učenje iz danega nabora podatkov.
Za lažjo predstavo si oglejmo problem iz vsakdanjega življenja, ki ga lahko pre- vedemo na problem binarne klasifikacije. Denimo, da imamo zdravniški register podatkov n testiranih ljudi, ki so kazali znake okužbe z virusom COVID-19. Za vsakega pacienta poznamo njegovo starost, spol ter prisotnost nekaterih začetnih simptomov okužbe, hkrati pa poznamo tudi rezultat njegovega testa. Na podlagi teh podatkov želimo sestaviti napovedni model, ki bo iz podatkov o novem pacientu, ki kaže znake okužbe, znal čim bolj natančno napovedati rezultat njegovega testa.
Problem iskanja optimalnega napovednega modela lahko matematično zastavimo kot problem binarne klasifikacije. Elementi nabora podatkov so informacije o pre- teklih testiranjih, zakodirane kot vektorji xi, ter informacije o rezultatu njegovega testayi, ki so enake 1, če je bil test pozitiven, ter−1, če je bil negativen. Napovedni model bo preprosto optimalni binarni klasifikator.
To ni zgolj ilustrativen primer uporabe binarne klasifikacije, temveč tudi dejanski pristop, ki ga je ekipa znanstvenikov uporabila v praksi [21].
2.2. Linearna ločljivost podatkov. Preden se lotimo reševanja splošnega pro- blema binarne klasifikacije, moramo najprej spoznati nekaj osnovnih pojmov, ki nam bodo pomagali opisati strukturo problema.
Definicija 2.1. Naj bo V vektorski prostor nad R. Skalarni produkt na V je bili- nearna forma V ×V →R, definirana s predpisom
(x, y)↦→ ⟨x, y⟩V,
za katero za vse vektorje x, y, z ∈V in vsaka α, β ∈Rveljajo naslednje lastnosti:
• simetričnost: ⟨x, y⟩V =⟨y, x⟩V,
• linearnost v prvem faktorju: ⟨αx+βy, z⟩V =α⟨x, z⟩V +β⟨y, z⟩V,
• neizrojenost: ⟨x, y⟩V = 0 za vsak y∈V ⇒x= 0.
Naša definicija se razlikuje od klasične definicije skalarnega produkta. Zadnjo lastnost navadno nadomeščata dve drugi lastnosti:
• pozitivna semidefinitnost: ⟨x, x⟩V ≥0 za vsak x∈V,
• definitnost: ⟨x, x⟩V = 0 ⇒x= 0.
Ti lastnosti pogosto združimo v eno ekvivalentno lastnost, ki ji rečemo pozitivna definitnost:
⟨x, x⟩>0 za vsak x̸= 0.
Našo definicijo lahko torej gledamo kot posplošitev, saj dovoljujemo tudi skalarne produkte, ki niso pozitivno definitni. Razlog za tako definicijo bomo spoznali ka- sneje, ko bomo govorili o jedrnih funkcijah.
Definicija 2.2. Hiperploskev v Rd je d−1 razsežna podmnogoteorst.
Definicija 2.3. Hiperravnina v Rd je d−1 razsežna ravnina.
Hiperravnina je enolično določena z normalnim vektorjem w ter poljubnim ska- larjem b ∈R. Hiperravnina je ravno množica rešitev enačbe ⟨w, x⟩ −b = 0, kjer je
⟨·,·⟩ standardni skalarni produkt v Rd. Če hiperravnina poteka skozi koordinatno izhodišče, je b= 0 in jo imenujemo homogena hiperravnina.
Definicija 2.4. Naj bowvektor v evklidskem prostoruE inb realno število. Funk- ciji
fw,b(x) =
⎧
⎪⎪
⎨
⎪⎪
⎩
1, ⟨w, x⟩> b 0, ⟨w, x⟩=b
−1, ⟨w, x⟩< b
rečemo linearna funkcija praga. Če je b = 0, ji rečemo homogena linearna funkcija praga in namesto fw,b pišemo le fw.
Za vsakawinb linearna funkcija praga naravno razdeli evklidski prostor tako, da dobimo množici vektorjev E+ in E−, za kateri velja
fw,b(x) = 1, x∈E+, fw,b(x) = −1, x∈E−.
Množici ločuje hiperravnina {x ∈E |fw,b(x) = 0}. Vidimo, da je evklidski prostor E unija treh disjunktnih množic. V nadaljevanju bomo pogosto govorili le o uniji
dveh množic, ter hiperravnino izpuščali. To sledi iz dejstva, da ima hiperravnina mero 0 in je zato zanemarljiva.
Na funkcijo fw,b(x) lahko sedaj gledamo malo drugače, kot na predznak projekcije vektorja x na normalo hiperravnine. Funkcijo lahko torej enostavneje zapišemo kot
fw,b(x) = sign(⟨w, x⟩ −b).
Definicija 2.5. Naj bo X ⊆E. Par (X+, X−) podmnožic množice X je homogeno linearno ločljiv natanko tedaj, ko obstaja tak vektorw∈E, da velja
fw(x) = 1 za vsak x∈X+, fw(x) =−1 za vsak x∈X−.
Homogeno hiperravnino {x ∈ E | fw(x) = 0} v tem primeru imenujemo ločitvena hiperravnina.
V luči novih definicij si lahko ponovno ogledamo naš motivacijski problem. Če je množica X iz motivacijskega problema podmnožica nekega evklidskega prostora, lahko govorimo o linearni ločljivosti danega nabora podatkov S.
Definicija 2.6. Naj bo X neprazna podmnožica nekega evklidskega prostora in Y = {−1,1}. Naj bo dan nabor podatkov S = {(x1, y1),(x2, y2), . . . ,(xn, yn)} ⊆ X×Y. Definiramo množiciX+ ={xi ∈X |yi = 1} in X− ={xi ∈ X |yi =−1}.
Nabor podatkov S je homogeno linearno ločljiv, če je homogeno linearno ločljiv par (X+, X−).
V tem primeru tudi obstaja pripadajoča homogena linearna funkcija praga fw(x), ki po definiciji homogene linearne ločljivosti ustreza pogoju (1) iz motivacijskega problema.
V primeru, da je X podmnožica nekega evklidskega prostora ter je nabor po- datkov S homogeno linearno ločljiv, smo torej motivacijski problem prevedli na problem iskanja vektorja w. Ta problem je lažji, saj ga lahko rešimo s klasičnimi optimizacijskimi metodami. Več o tem bomo spoznali v razdelku 4.1.
2.3. Coverjev izrek. Kaj pa, če nabor podatkov ni linearno ločljiv? Ta problem se izkaže za težjega, vendar nam bo pri obravnavi v pomoč Coverjev izrek. Tho- mas M. Cover je leta 1965 v svojem članku [4, izrek 1] med drugim predstavil naslednji izrek, ki ga je sicer pred njim dokazalo že več ljudi.
Izrek 2.7. Naj bo X ⊆ Ed množica n točk v splošni legi. Število vseh homogeno linearno ločljivih parov (X+, X−) je enako
C(n, d) = 2
d−1
∑
k=0
(n−1 k
)
.
Zanimivo je, da se samo ime »Coverjev izrek« v sodobni literaturi ne nanaša na ta izrek, temveč na spodnjega, ki ga Thomas M. Cover nikoli ni zapisal. Izrek v tej obliki je bil prvič omenjen šele v devetdesetih letih v delu [6, str. 280] in je sčasoma postal znan pod imenom Coverjev izrek, saj njegova ideja sloni na izreku 2.7.
Izrek 2.8 (Coverjev izrek). Naj bo X ⊆ Ed množica moči n. Če X nelinearno vložimo v neki evklidski prostor razsežnosti m(m > d), je verjetnost, da je naključno izbran par (X+, X−) homogeno linearno ločljiv v prostoru Em, večja kot verjetnost, da je homogeno linearno ločljiv v prostoru Ed.
Coverjev izrek nas sam po sebi ne pripelje do rešitve motivacijskega problema, vendar nam da dobro intuicijo, kako se problema lotiti.
Definicija 2.9. Naj bo X neprazna množica, F vektorski prostor in ϕ:X →F
vložitev, ki X vloži v F. Preslikavo ϕ imenujemo preslikava značilk, prostor F pa prostor značilk.
V primeru, da je X podmnožica nekega evklidskega prostora in F evklidski pro- stor višje razsežnosti, nam Coverjev izrek pove, da bo vložitev nabora podatkov v prostoru značilk homogeno linearno ločljiva z večjo verjetnostjo. V primeru, da je prostor značilk neskončno razsežen, bo ta verjetnost enaka 1. To dejstvo bomo s pridom uporabili v naslednjem poglavju.
Do zdaj smo se podrobneje ukvarjali s primeri, ko je bila X podmnožica nekega evklidskega prostora, čeprav v motivacijskem problemu o množici X nismo pred- postavili nobene posebne strukture. Izkaže se, da se naša intuicija iz evklidskih prostorov dobro prenese tudi na splošnejše primere, ko je X podmnožica nekega poljubnega vektorskega prostora razsežnosti dinF neki prostor višje razsežnosti. V nadaljevanju si bomo podrobneje ogledali posebno vrsto teh prostorov, za katere se bo izkazalo, da imajo uporabne lastnosti za reševanje motivacijskega problema.
3. Jedrne funkcije
V tem poglavju bomo spoznali definicijo in lastnosti jedrnih funkcij ter teorijo funkcijskih prostorov, povezanih z njimi. Na koncu si bomo ogledali še nekaj kon- kretnih primerov.
3.1. Osnovne definicije. Če je vektorski prostorF, v katerega slikamo s preslikavo ϕ, opremljen s skalarnim produktom, lahko definiramo t. i. jedrno funkcijona X.
Definicija 3.1. Naj bo ϕ : X → F preslikava značilk in F prostor, opremljen s skalarnim produktom ⟨·,·⟩F. Funkciji K :X×X →R, definirani s predpisom
K(xi, xj) =⟨ϕ(xi), ϕ(xj)⟩F, rečemo jedrna funkcija na X, porojena s preslikavo ϕ.
Jedrna funkcija je skalarni produkt slik dveh vektorjev iz X v prostoru F. Inter- pretiramo jo lahko kot »mero podobnosti« med dvema vektorjema iz X, ki smo jo omenjali že v motivacijskem problemu. Namesto izraza jedrna funkcija včasih upo- rabljamo samo izraz jedro. Ime prihaja iz integralskih jeder, ki so bila zgodovinsko prvo področje študija jedrnih funkcij.
Z naslednjimi tremi definicijami bomo spoznali zanimivo podmnožico jedrnih funkcij, ki jo bomo kasneje pogosto uporabljali.
Definicija 3.2. Naj bo K jedrna funkcija in x1, x2, . . . , xn ∈ X. Matriki velikosti n×n, definirani z G= [K(xi, xj)]ij, pravimo Gramova matrika.
Definicija 3.3. Naj bo n ∈ N poljubno naravno število in A ∈ Rn×n kvadratna matrika. Matrika A je simetrična pozitivno semidefinitna, če velja A = A⊺ in za vsak vektor v ∈Rn velja
v⊺Av ≥0.
Definicija 3.4. Naj bo X neprazna množica. Funkcija K, definirana na X ×X, je simetrična pozitivno semidefinitna jedrna funkcija natanko tedaj, ko za vsak n∈ N in vse x1, x2, . . . , xn ∈ X porodi simetrično pozitivno semidefinitno Gramovo matriko G.
Neenačaj v zadnjih dveh definicijah lahko tudi obrnemo. Tako dobimo definicijo simetrične negativno semidefinitne matrike in funkcije.
V tuji literaturi jedrno funkcijo iz definicije 3.4 pogosto imenujejo kar pozitivno definitna jedrna funkcija, kljub temu da je njena Gramova matrika zgolj pozitivno semidefinitna. Razlog za tako poimenovanje je, da vsaka taka jedrna funkcija na naraven način porodi pozitivno definiten skalarni produkt. Več o tem bomo spoznali v dokazu izreka 3.13.
Ker je vsak skalarni produkt po definiciji simetričen, je simetrična tudi vsaka jedrna funkcija in posledično njena Gramova matrika. Že imena pojmov iz zgornjih definicij pa namigujejo, da verjetno podobna povezava med skalarnim produktom in jedrno funkcijo obstaja tudi za pozitivno semidefinitnost. Del tega dejstva je zajet v naslednji trditvi.
Trditev 3.5. Naj bo K jedrna funkcija, porojena s pozitivno semidefinitnim skalar- nim produktom. Potem je K simetrična pozitivno semidefinitna jedrna funkcija.
Dokaz. Naj bo G Gramova matrika za K, porojena z naborom x1, x2, . . . , xn ∈ X in α∈Rn poljuben realen vektor. Potem velja
α⊺Gα=
n
∑
i,j=1
αiαjK(xi, xj)
=K
⎛
⎝
n
∑
i=1
αixi,
n
∑
j=1
αjxj
⎞
⎠
=
⟨
ϕ
( n
∑
i=1
αixi
)
, ϕ
⎛
⎝
n
∑
j=1
αjxj
⎞
⎠
⟩
≥0. □
Spomnimo se, da po naši definiciji skalarni produkt ni nujno pozitivno semidefi- niten. Torej tudi vsaka jedrna funkcija ni nujno pozitivno semidefinitna. Jedrnim funkcijam, ki niso niti pozitivno semidefinitne niti negativno semidefinitne, pravimo nedefinitna jedra. Več o njih lahko preberemo v [11].
V nadaljevanju se bomo ukvarjali izključno s simetričnimi pozitivno semidefini- tnimi jedrnimi funkcijami. Namesto tega dolgega pojma bomo zato pogosto pisali le jedrna funkcija ali kar jedro. Če bomo kdaj mislili na druge vrste jedernih funkcij, bomo to izrecno poudarili.
Videli bomo, da jedrne funkcije močno poenostavijo reševanje motivacijskega pro- blema, tudi v primeru, ko nabor podatkov ni homogeno linearno ločljiv. Preden pa pridemo do tega, si oglejmo, kako se jedrne funkcije naravno pojavijo v določenih Hilbertovih prostorih.
3.2. Hilbertovi prostori z reproducirajočim jedrom. Najprej se spomnimo definicije Hilbertovih prostorov.
Definicija 3.6. Vektorski prostor H, opremljen s pozitivno definitnim skalarnim produktom⟨·,·⟩, jeHilbertov prostor, če je poln metričen prostor glede na kanonično normo ||x||=√⟨x, x⟩.
Pozitivna definitnost skalarnega produkta je potreben pogoj za to, da je prostor Hilbertov, saj drugače norma ni dobro definirana. Pozitivno semidefinitni skalarni produkti po drugi strani porodijo t. i. seminormo in pripadajočsemi-Hilbertov pro- stor, ki ima vse lastnosti navadnega Hilbertovega prostora, razen definitnosti norme.
Za obstoj jedrnih funkcij očitno zadostuje, da je prostor značilk Hilbertov ali vsaj semi-Hilbertov prostor. Spomnimo se, da so primeri Hilbertovih prostorov tudi določeni prostori realnih funkcij, opremljeni s primerno definiranim skalarnim produktom. V nadaljevanju si bomo podrobneje ogledali podmnožico teh prostorov.
Definicija 3.7. Naj bo X neprazna množica, H Hilbertov prostor realnih funkcij f :X →R in x poljuben element množice X. Funkcionalu Lx :f ↦→f(x) pravimo evalvacijski funkcional.
Definicija 3.8. Naj bo X neprazna množica in H Hilbertov prostor realnih funkcij f : X → R. Če je evalvacijski funkcional Lx zvezen na H za vsak x ∈ X, potem pravimo, da je H Hilbertov prostor z reproducirajočim jedrom.
V literaturi se za Hilbertove prostore z reproducirajočim jedrom pogosto uporablja zgolj kratica RKHS, po angleškem prevodureproducing kernel Hilbert space.
Na tej točki se je smiselno vprašati, če poznamo kakšne znane primere Hilberto- vih prostorov z reproducirajočim jedrom. Očiten kandidat za to je prostor L2. Ta prostor je sicer Hilbertov, vendar njegovi elementi v resnici niso funkcije, temveč njihovi ekvivalenčni razredi. Tako nima smisla govoriti o tem, ali ima prostor repro- ducirajoče jedro. Kot bomo videli kasneje, so najenostavnješi primeri Hilbertovih prostorov z reproducirajočim jedrom dualni prostori evklidskih prostorov, opremljeni s primerno definiranim skalarnim produktom. Izkaže se, da je druge primere težko najti eksplicitno. Z izrekom 3.13 bomo spoznali, da nas prostori sami pogosto sploh ne zanimajo, saj so implicitno določeni s simetričnimi pozitivno semidefinitnimi je- drnimi funkcijami.
Definicija 3.8 se morda na prvi pogled zdi nenavadna, vendar bomo videli, da prav prostori s to lastnostjo na naraven način porodijo jedrne funkcije. Najprej se spomnimo na Rieszov reprezentacijski izrek [19, str. 116, izrek 213].
Izrek 3.9 (Rieszov reprezentacijski izrek). Naj bo H Hilbertov prostor in L:H → R zvezen linearen funkcional. Potem obstaja natanko en vektor u ∈ H, da velja L(v) = ⟨v, u⟩ za vsak v ∈H.
Ta izrek bo bistven pri dokazu naslednje trditve, ki govori o pomembni lastnosti Hilbertovih prostorov z reproducirajočim jedrom. Tej lastnosti pravimo reproduci- rajoča lastnost.
Trditev 3.10 (Reproducirajoča lastnost). Naj bo H Hilbertov prostor z reproduci- rajočim jedrom. Potem za vsak x∈X obstaja natanko ena funkcija Kx ∈H, da za vsak f ∈H velja f(x) = ⟨f, Kx⟩.
Dokaz. Po definiciji evalvacijskega funkcionala velja f(x) = Lx(f) za vsak x ∈ X.
Ker je funkcional Lx zvezen, po 3.9 obstaja natanko en Kx ∈ H, da velja Lx(f) =
⟨f, Kx⟩za vsak f ∈H. Iz tega sledi f(x) = Lx(f) = ⟨f, Kx⟩. □ Funkciji Kx pravimo predstavnik zax. Trditev nam pove, da je enolično določena za vsak x∈X.
Na Hilbertov prostor z reproducirajočim jedrom lahko gledamo kot na prostor značilk za X. Ker za vsak x obstaja enolično določen predstavnik Kx, lahko na- ravno definiramo (injektivno) preslikavo značilk kot ϕ : x ↦→ Kx. Tako definirana preslikava značilk porodi jedrno funkcijo K(xi, xj) = ⟨Kxi, Kxj⟩.
Definicija 3.11. Naj bo H Hilbertov prostor z reproducirajočim jedrom. Jedrni funkciji K(xi, xj) = ⟨Kxi, Kxj⟩, porojeni s preslikavo značilk ϕ : x ↦→ Kx, pravimo reproducirajoče jedro prostora H.
Reproducirajoče jedro je očitno pozitivno semidefinitna jedrna funkcija, saj je skalarni produkt v Hilbertovem prostoru nujno pozitivno semidefiniten.
Kot namiguje že notacija, obstaja povezava med reproducirajočim jedrom K in predstavniki Kx. To povezavo nam podaja naslednja trditev.
Trditev 3.12. Naj bo H Hilbertov prostor z reproducirajočim jedrom K in ϕ : X → H pripadajoča preslikava značilk. Potem za vsaka xi, x∈ X velja ϕ(xi)(x) = K(xi, x).
Dokaz. Po definiciji je ϕ(xi) = Kxi. Za vsak Kxi ∈ H velja Kxi(x) = ⟨Kxi, Kx⟩ =
⟨ϕ(xi), ϕ(x)⟩=K(xi, x). □
Zaradi lažje berljivosti namesto K(xi, x) pogosto pišemo kar K(xi,·). S tem po- udarimo, da je K(xi, x) funkcija ene spremenljivkex, xi pa zgolj parameter. Bistvo trditve, zapisano na lepši način, je: ϕ(x) =K(x,·). To je zelo pomembna ugotovitev, saj med drugim podaja ekspliciten predpis za preslikavo značilk.
Kot smo omenili že prej, nas eksplicitni primeri Hilbertovih prostorov z repro- ducirajočim jedrom pogosto sploh ne bodo zanimali. Naslednji izrek nam pove, da implicitni primeri teh prostorov obstajajo za vsako jedrno funkcijo.
Izrek 3.13(Moore–Aronszajn).Naj bo K simetrična pozitivno semidefinitna jedrna funkcija na X. Potem obstaja do izomorfizma natančno določen Hilbertov prostor funkcij H, da je K reproducirajoče jedro za H.
Dokaz. Za vsak x∈ X definiramo njegovega predstavnika Kx(·) = K(x,·). Naj bo H0 linearna ogrinjača vseh predstavnikov
H0 = Lin{Kx |x∈X}.
Ta vektorski prostor želimo opremiti s takim skalarnim produktom, da bo veljalo
(2) ⟨Kx, Ky⟩=K(x, y).
Naj bosta f ing poljubni funkciji iz H0. Lahko ju razvijemo v vrsti f =
n
∑
i=1
αiKxi ing =
n
∑
j=1
βjKxj
za neke vrednosti αi, βj ∈R. S pomočjo tega lahko definiramo formo
⟨·,·⟩H0 :H0×H0 →R,
⟨f, g⟩H0 =
⟨ n
∑
i=1
αiKxi,
n
∑
j=1
βjKxj
⟩
H0
:=
n
∑
i=1 n
∑
j=1
αiβjK(xi, xj).
Najprej moramo pokazati, da ta forma res zadostuje pogojem skalarnega produkta.
Iz definicije je razvidno, da je forma simetrična. Naj boh∈H0 poljubna funkcija iz
tega prostora in λ, µ∈Rpoljubni realni števili. Funkcijo hlahko razvijemo v vrsto h=
n
∑
i=1
γiKxi.
Po definiciji forme velja
⟨λf +µh, g⟩H0 =
⟨
λ
n
∑
i=1
αiKxi+µ
n
∑
i=1
γiKxi,
n
∑
j=1
βjKxj
⟩
H0
=
⟨ n
∑
i=1
(λαi+µγi)Kxi,
n
∑
j=1
βjKxj
⟩
H0
=
n
∑
i=1 n
∑
j=1
(λαi+µγi)βjK(xi, xj)
=λ
n
∑
i=1 n
∑
j=1
αiβjK(xi, xj) +µ
n
∑
i=1 n
∑
j=1
γiβjK(xi, xj)
=λ⟨f, g⟩H0 +µ⟨h, g⟩H0.
Gre torej za simetrično bilinearno formo. Da bi se prepričali, da gre res tudi za skalarni produkt, bi morali dokazati še neizrojenost. To bomo zaenkrat izpustili, saj bomo kmalu dokazali še nekaj več, da je ta bilinearna forma pravzaprav tudi pozitivno definitna in s tem res v vseh pogledih tudi skalarni produkt.
Najprej si oglejmo kanonično normo, porojeno s tem skalarnim produktom. Iz pozitivne semidefinitnosti jedrne funkcije sledi, da je za vsak element tega prostora f =∑iαiKxi kvadrat kanonične norme nenegativen. Zapisano drugače
||f||2H
0 =∑
i,j
αiαjK(xi, xj)≥0.
Naj bosta f, g ∈H0 poljubni funkciji iz prostora H0 in naj velja
(3) ⟨g, g⟩= 0.
Ker gre za vektorski prostor, sledi, da je za poljubno nenegativno realno število t ∈Rtudi funkcija f−t⟨f, g⟩g element tega prostora. Torej velja
||f−t⟨f, g⟩g||2 ≥0.
Če to neenakost razpišemo s skalarnim produktom in upoštevamo (3), dobimo 0≤ ||f−t⟨f, g⟩g||2
=⟨f−t⟨f, g⟩g, f−t⟨f, g⟩g⟩
=⟨f, f⟩ −2t⟨f, g⟩⟨f, g⟩+t2⟨f, g⟩⟨g, g⟩
=⟨f, f⟩ −2t⟨f, g⟩2, oziroma zapisano drugače
⟨f, f⟩ ≥2t⟨f, g⟩2.
Ker ta neenakost velja za poljubno velikt, sledi, da je⟨f, g⟩= 0, saj bi v nasprotnem primeru moral biti ⟨f, f⟩poljubno velik. Za naš skalarni produkt torej velja
(4) ⟨g, g⟩= 0⇒ ⟨f, g⟩= 0
za vsako funkcijo f ∈ H0. Zdaj lahko pokažemo, da v prostoru H0 velja Cauchy- Schwarzova neenakost:
|⟨f, g⟩| ≤ ||f|| ||g||.
Dovolj je dokazati, da za vsaki funkciji f, g ∈H0 velja
⟨f, g⟩2 ≤ ||f||2 ||g||2.
V primeru, da je ||g||2 = ⟨g, g⟩ = 0, upoštevamo lastnost (4) in enačba velja. V primeru, da ||g||2 = ⟨g, g⟩ ̸= 0, pa si lahko ogledamo funkcijo f − ⟨f,g⟩||g||2g. Ker je ta vsebovana v prostoru H0, velja
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
f −⟨f, g⟩
||g||2 g
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
2
≥0.
Če to razpišemo s skalarnim produktom, dobimo
⟨f, f⟩ −2⟨f, g⟩2
||g||2 +⟨f, g⟩2
||g||2 =⟨f, f⟩ − ⟨f, g⟩2
||g||2 ≥0.
Iz tega vidimo, da Cauchy-Schwartzova neenakost v prostoru H0 res velja.
Posledica Cauchy-Schwartzove neenakosti je, da za vsak x∈X velja
|f(x)|=|⟨f, Kx⟩H0|
≤ ||f||H0 ||Kx||H0
=||f||H0 √⟨Kx, Kx⟩H0
=||f||H0 √K(x, x).
Zapisano krajše:
(5) |f(x)| ≤ ||f||H0 √K(x, x) za vsak x∈X.
Iz tega sledi, da velja
||f||H0 = 0 ⇒ |f(x)| ≤0⇒f(x) = 0
za vsak x. Norma je torej pozitivno definitna in s tem dobro definirana. Posledica tega je, da je tudi pripadajoča bilinearna forma pozitivno definitna in potemtakem res skalarni produkt.
Posledica neenakosti (5) je med drugim tudi, da je za vsak x ∈ X in za vsak f ∈H0 evalvacijski funkcional Lx(f) =f(x) omejen. Ker je evalvacijski funkcional linearen operator, potem zanj velja
|Lx(f1 −f2)| ≤ ||Lx|| ||f1−f2||H0.
To pomeni, da je Lx Lipschitzovo zvezen s konstanto ||Lx||, torej je tudi zvezen.
Prostor H0 ima torej vse lastnosti Hilbertovega prostora z reproducirajočim je- drom, razen polnosti. Konstruirati moramo torej še napolnitev prostora H0.
Naj bo (fn)n∈Npoljubno Cauchyjevo zaporedje vH0. Ker jeH0 vektorski prostor, je za vsaka m, n ∈ N tudi fm−fn vsebovana v H0. Če to vstavimo v enačbo (5), dobimo, da za vsak x∈X ter vsaka m, n∈N velja
|fm(x)−fn(x)| ≤ ||fm−fn||H0 √K(x, x).
Torej je za vsakx∈X tudi zaporedje (fn(x))n∈N Cauchyjevo vRin ima zato limito, saj je Rpoln metričen prostor.
Naj bo zdaj H ⊂ RX prostor tistih funkcij f : X → R, ki so točkovne limite Cauchyjevih zaporedij (fn)n∈N ∈H0. Z drugimi besedami, H je množica funkcij
f(x) = lim
n→∞fn(x).
Zanima nas, če je ta prostor poln. Vzemimo torej poljubno limito Cauchyjevega zaporedja iz tega prostora: f = limn→∞fn, fn ∈ H. Za vsak n ∈ N izberemo tak gn∈H0, da velja||gn−fn|| ≤ n1. To lahko vedno naredimo, saj je množicaH0 gosta v H. Iz tega za vsak x∈X sledi:
|gn(x)−f(x)| ≤ |gn(x)−fn(x)|+|fn(x)−f(x)|
≤ |Lx(gn−fn)|+|fn(x)−f(x)|, kjer je Lx evalvacijski funcional. Ker je ta omejen, sledi
|gn(x)−f(x)| ≤ ||Lx|| ||gn−fn||H0 +|fn(x)−f(x)|
Ker desna stran konvergira proti 0, pomeni, da tudi gnkonvergira proti f. Oglejmo si še, kako blizu so si členi zaporedja gn.
||gm−gn||H0 =||gm−gn||H
≤ ||gm−fm||H +||fm−fn||H +||fn−gn||H
≤ 1 m + 1
n +||fm−fn||H.
Vidimo, da je zaporedje gn Cauchyjevo, torej je njegova limita po konstrukciji vse- bovana v H. Prostor H je torej poln in s tem napolnitev H0. Skalarni produkt na njem definiramo kot
⟨f, g⟩H = lim
n→∞⟨fn, gn⟩H0.
Ta skalarni produkt je dobro definiran, ni odvisen od Cauchyjevih zaporedij, temveč le od njihovih limit [3, lema 4]. Od svojega predhodnika v H0 podeduje tudi vse pomembne lastnosti, vključno z lastnostjo (2). Torej je H res Hilbertov prostor z
reproducirajočim jedrom za jedro K. □
Posledica tega izreka in trditve 3.5 je med drugim tudi, da so reproducirajoča jedra natanko simetrične pozitivno semidefinitne jedrne funkcije. S tem smo tudi dokazali, da je vsaka simetrična pozitivno semidefinitna jedrna funkcija res skalarni produkt v nekem Hilbertovem prostoru z reproducirajočim jedrom.
Izkaže se, da obstajajo analogije Hilbertovim prostorom z reproducirajočim je- drom, ki veljajo tudi za nedefinitne jedrne funkcije. Ti prostori seveda niso Hil- bertovi, saj so njihovi skalarni produkti nedefinitni. Imenujejo se Kre˘ınovi prostori z reproducirajočim jedrom (angl. reproducing kernel Kre˘ın spaces, krajše RKKS).
Zanimiva lastnost teh prostorov je, da je nedefinitna jedrna funkcija lahko reprodu- cirajoče jedro več različnim Kre˘ınovim prostorom [2]. Več o njih lahko izvemo v [10]
ter [11].
3.3. Reprezentacijski izrek. Vrnimo se k motivacijskemu problemu. Ukvarjali smo se z naborom podatkov S = {(x1, y1),(x2, y2), . . . ,(xn, yn)} ⊆ X × {−1,1}.
Spomnimo se, da smo v primeru homogene linearne ločljivosti nabora podatkov problem lahko prevedli na iskanje optimalnega vektorjaw. To bi zdaj radi posplošili na vse primere, tudi tiste, pri katerih množicaX ni podmnožica evklidskega prostora ali pa nabor ni homogeno linearno ločljiv. Vemo, da lahko ob izbiri reproducirajočega jedra vsako množicoX s preslikavo značilk vložimo v pripadajoč Hilbertov prostor z reproducirajočim jedrom. Če izberemo jedro, ki porodi neskončno razsežen prostor, bo po Coverjevem izreku slika nabora podatkov tam homogeno linearno ločljiva z verjetnostjo 1. To pomeni, da bo skoraj gotovo obstajal analog optimalnega vektorja w, le da bo ta zdaj element Hilbertovega prostora z reproducirajočim jedrom, torej funkcija.
Do zdaj še vedno nismo popolnoma matematično formalizirali pojma »optimal- nega« vektorja w ali pripadajočega optimalnega binarnega klasifikatorja. To bomo naredili sedaj s formulacijo naslednjega problema.
3.3.1. Minimizacija empirične napake. Naj bo H Hilbertov prostor z reproducira- jočim jedrom in naj bodo dani:
• nabor podatkov S ={(x1, y1),(x2, y2), . . . ,(xn, yn)} ⊆X× {−1,1},
• strogo naraščajoča realna funkcija g : [0,∞)→R,
• nenegativna funkcija napake E : ({−1,1} ×R)n →R. Funkcionalu
f ↦→E((y1, f(x1)),(y2, f(x2)), . . . ,(yn, f(xn))) +g(||f||H)
pravimo funkcional regularizirane napake. Iščemo tisto preslikavo f∗ ∈ H, ki bo minimizirala ta funkcional.
Celoten problem se imenujeminimizacija empirične napake. Zelo je podoben pro- blemu binarne klasifikacije, vendar obstaja pomembna razlika. Optimalna funkcija f∗, ki minimizira funkcional regularizirane napake, namreč ni binarni klasifikator.
Pripadajoč optimalen klasifikator je oblike h(x) = sign(f∗(x)).
Čeprav je problem na prvi pogled formuliran zelo abstraktno, ima enostavno raz- lago. Funkcija napakeEmeri odstopanjef od želenih vrednosti. Navadno je izbrana tako, da je njena vrednost za funkcijo, ki porodi klasifikator, ki ustreza pogojem (1), enaka 0. Členug(||f||) pravimoregularizacijski člen. Intuitivno si njegovo prisotnost lahko razlagamo kot dajanje prednosti nekaterim »lepšim« in enostavnejšim klasi- fikatorjem. Njegova pomembnost prihaja iz področja regularizacije, ki žal presega obseg tega dela. Bolj podrobno razlago najdemo v [17, str. 87–122].
Zdaj, ko smo problem definirali, se lahko posvetimo njegovemu reševanju. Nasle- dnji izrek nam da t. i. reprezentacijo optimalne funkcije f∗.
Izrek 3.14 (Reprezentacijski izrek). Naj bo H Hilbertov prostor z reproducirajo- čim jedrom in K njegovo reproducirajoče jedro. Naj bo f∗ ∈ H tista funkcija, ki minimizira izraz
(6) E((y1, f(x1)),(y2, f(x2)), . . . ,(yn, f(xn))) +g(||f||H).
Potem obstajajo taki realni koeficienti α1, α2, . . . , αn, da velja:
f∗(·) =
n
∑
i=1
αiK(xi,·).
Ta izrek je posebej pomemben, saj prevede iskanje optimalne funkcije f∗ iz ne- skončno razsežnega prostora funkcij na iskanje končnega števila realnih koeficientov, kar je v veliko pogledih lažji problem, saj ga lahko rešimo s klasičnimi optimizacij- skimi metodami. Uporabnost tega izreka bomo spoznali tudi v poglavju 4, ko si bomo ogledali nekaj primerov metod strojnega učenja, ki uporabljajo jedrne funk- cije.
Dokaz izreka 3.14. Spomnimo se, da so slike preslikave značilk ϕ(xi) ∈ H pravza- prav realne funkcije in velja ϕ(xi) =K(xi,·) =⟨ϕ(xi), ϕ(·)⟩.
Naj bo W podprostor H, definiran kot W = Lin{ϕ(x1), ϕ(x2), . . . , ϕ(xn)} inW⊥ njegov ortogonalni komplement. Vsako funkcijo f ∈ H lahko zapišemo kot vsoto
dveh komponent, kjer prva leži v W in druga vW⊥. Velja torej
(7) f =∑
i
αiϕ(xi) +h
za neke αi ∈R in neko funkcijoh ∈W⊥. Za vsak xi torej velja
(8) ⟨h, ϕ(xi)⟩= 0
Oglejmo si, kaj karakterizacija (7) pomeni za uporabo funkcije f na poljubnem xi. f(xj) =⟨f, ϕ(xj)⟩
=
⟨
∑
i
αiϕ(xi) +h, ϕ(xj)
⟩
=∑
i
αi⟨ϕ(xi), ϕ(xj)⟩+⟨h, ϕ(xj)⟩
=∑
i
αiK(xi, xj)
Uporaba funkcije f na poljubnem xi je torej neodvisna od funkcije h, od tod pa sledi, da je tudi izraz
(9) E((y1, f(x1)),(y2, f(x2)), . . . ,((yn, f(xn)))
neodvisen od h. Oglejmo si še, kako karakterizacija (7) vpliva na drugi člen mini- mizacijskega izraza (6).
g(||f||) =g
(⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
∑
i
αiϕ(xi) +h
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐ )
=g
⎛
⎝
√
⟨
∑
i
αiϕ(xi) +h,∑
i
αiϕ(xi) +h
⟩⎞
⎠
Tu z upoštevanjem lastnosti (8) in linearnostjo skalarnega produkta dobimo
=g
⎛
⎝
√
⟨
∑
i
αiϕ(xi),∑
i
αiϕ(xi)
⟩
+⟨h, h⟩
⎞
⎠
=g
⎛
⎝
√
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
∑
i
αiϕ(xi)
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
2
+||h||2
⎞
⎠
≥g
(⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
∑
i
αiϕ(xi)
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐
⏐ )
Zadnja neenakost velja, ker je funkcija g strogo naraščajoča.
Vidimo, da funkcije f, za katere velja h = 0, minimizirajo izraz g(||f||). Ker je izraz (9) povsem neodvisen od h, sklepamo, da mora tudi za iskano funkcijo, ki minimizira izraz (6), veljati h = 0. V luči tega odkritja lahko karakterizacijo (7) zapišemo v nekoliko drugačni obliki
f(·) =∑
i
αiϕ(xi) = ∑
i
αiK(xi,·). □
3.4. Primeri jedrnih funkcij.
3.4.1. Linearno jedro. Najbolj enostaven primer jedrne funkcije je standardni ska- larni produkt v nekem evklidskem prostoru E. V jeziku jedrnih funkcij mu pogosto rečemo linearno jedro. Naravno se je vprašati, kaj je Hilbertov prostor z reproduci- rajočim jedrom, ki ga porodi linearno jedro. Izrek 3.13 nam pove, da je pripadajoč Hilbertov prostor z reproducirajočim jedrom napolnitev prostora, ki ga napenjajo funkcije oblike K(xi,·). V primeru linearnega jedra je ta prostor funkcij ravno {⟨x,·⟩E |x ∈E}, torej dualen prostor. Ker je dual evklidskega prostora že sam po sebi poln metričen prostor, mu napolnitev ne doda nobenih novih funkcij, kar po- meni, da je že sam Hilbertov prostor z reproducirajočim jedrom. To je tudi primer končno razsežnega Hilbertovega prostora z reproducirajočim jedrom, saj je izomor- fen evklidskemu prostoru, ki je končno razsežen. Preslikava značilk je kar kanonični izomorfizem med evklidskim prostorom in dualom.
Seveda pa nas zanimajo tudi drugi primeri jedrnih funkcij. Načeloma lahko po- ljubno simetrično bilinearno formo preverimo za pozitivno semidefinitnost, vendar je tak način iskanja novih jedrnih funkcij zelo mučen. Delo nam močno olajša naslednja trditev, s pomočjo katere lahko iz že znanih jedrnih funkcij sestavimo nove.
Trditev 3.15. Naj bostaK1 inK2 pozitivno semidefinitni jedrni funkciji na neprazni množici X in α >0 poljubno pozitivno realno število. Potem so tudi:
(1) αK1 (2) K1+K2 (3) K1K2
pozitivno semidefinitne jedrne funkcije na X.
Dokaz. Naj bo x1, x2, . . . , xn ∈X poljuben nabor elementov iz X in β ∈ Rn polju- ben realen vektor. Pokazati moramo, da so Gramove matrike G vseh treh funkcij pozitivno semidefinitne.
(1)
β⊺Gβ =
n
∑
i,j=1
βiβjαK1(xi, xj)
=α
⎛
⎝
n
∑
i,j=1
βiβjK1(xi, xj)
⎞
⎠≥0.
(2)
β⊺Gβ =
n
∑
i,j=1
βiβj(K1(xi, xj) +K2(xi, xj))
=
n
∑
i,j=1
βiβjK1(xi, xj) +
n
∑
i,j=1
βiβjK2(xi, xj)≥0.
(3) Naj bo G1 Gramova matrika funkcije K1 in G2 Gramova matrika funkcije K2. Gramova matrika funkcije K1K2 je oblike [K1(xi, xj)K2(xi, xj)]i,j. Vidimo, da veljaG=G1◦G2, kjer je◦ Hadamardov (v nekaterih virih imenovan tudi Schurov) produkt matrik. Ker sta K1 in K2 pozitivno semidefinitni jedrni funkciji, sta tudi njuni Gramovi matriki pozitivno semidefinitni. Zdaj lahko uporabimo Schurov izrek o produktu, ki pove, da je Hadamardov produkt pozitivno semidefinitnih matrik tudi pozitivno semidefinitna matrika [9, izrek 3.4]. Trditev je tako dokazana. □
3.4.2. Polinomsko jedro. Posledica trditve 3.15 je dejstvo, da je za vsak standardni skalarni produkt ⟨·,·⟩ iz evklidskega prostora in poljubno naravno število d tudi K(·,·) = ⟨·,·⟩d jedrna funkcija. Tej funkciji rečemo homogeno polinomsko jedro.
Obstajajo tudi t. i. nehomogena polinomska jedra, ki so oblike (⟨·,·⟩+c)d za neko pozitivno realno število c, ter so prav tako jedrne funkcije.
Izkaže se, da polinomsko jedro porodi končno razsežen Hilbertov prostor z repro- ducirajočim jedrom. Če je n razsežnost prvotnega evklidskega prostora ind stopnja nehomogenega polinomskega jedra, bo pripadajoč Hilbertov prostor z reproducira- jočim jedrom razsežnosti (n+dd ). V primeru, da gre za homogeno polinomsko jedro, pa bo razsežnost (n+d−1d ). Dokaz lahko najdemo v [18, str. 293].
3.4.3. Gaussovo jedro. S pomočjo polinomskih jeder lahko sestavimo tudi druge zanimive jedrne funkcije. Spomnimo se, da lahko eksponentno funkcijo z razvojem v Taylorjevo vrsto zapišemo kot linearno kombinacijo potenčnih funkcij. Oglejmo si funkcijo, definirano kot
(10) K(x, y) = exp
(
−||x−y||2 2σ2
)
za neko neničelno realno število σ. Ta funkcija je limita linearne kombinacije poli- nomskih jeder s pozitivnimi koeficienti. Iz trditve 3.15 sledi, da je končna linearna kombinacija jeder s pozitivnimi koeficienti tudi jedro. Velja tudi, da je pozitivna se- midefinitnost zaprta za limite po točkah [18, str. 77]. Ker je funkcija (10) limita neke linearne kombinacije jedrnih funkcij s pozitivnimi koeficienti, je torej res tudi sama jedrna funkcija. Imenuje se Gaussovo jedro, v nekaterih virih pa tudi radialno je- dro. Je ena izmed najbolj priljubljenih nelinearnih jedrnih funkcij, med drugim tudi zato, ker porodi neskončno razsežen Hilbertov prostor z reproducirajočim jedrom, kar pomeni, da so slike nabora podatkov tam skoraj gotovo linearno ločljive.
Gaussovo jedro je odvisno le od evklidske razdalje med vektorjemax iny. Zaradi tega je invariantno za premike: očitno velja, da je
K(x+c, y+c) =K(x, y)
za vse vektorjec. Invariantno je tudi za rotacije: za vsako unitarno matrikoAočitno velja
K(Ax, Ay) = K(x, y).
Te lastnosti naredijo Gaussovo jedro posebej primerno za nabore podatkov, ki so prav tako invariantni za premike ali rotacije.
3.4.4. Jedra za splošne množice. Vsi dozdajšnji primeri jedrnih funkcij so delovali za množiceX, ki so podmnožice nekega evklidskega prostora. Spomnimo se, da tako pri formulaciji motivacijskega problema kot pri dokazu reprezentacijskega izreka nismo predpostavili ničesar o strukturi množice X. Res, jedrne funkcije lahko definiramo tudi za druge, neevklidske množice. Pametna definicija le-teh je sicer zelo odvisna od primera, vendar nas vedno vodi glavna ideja, da mora biti jedrna funkcija »mera podobnosti« na množici X. Na množici nizov lahko na primer definiramo jedrno funkcijo kot število skupnih podnizov. Jedrno funkcijo med dvema besediloma lahko definiramo kot mero preseka množic besed iz teh dveh besedil. Jedrno funkcijo med dvema drevesoma lahko definiramo kot število skupnih poddreves. Ena izmed glav- nih prednosti pristopa z jedri je ravno to, da v začetni množici X morda niti ni
smiselno govoriti o linearni ločljivosti, z vložitvijo v Hilbertov prostor z reproduci- rajočim jedrom pa se temu problemu izognemo. Več primerov jedrnih funkcij lahko najdemo v [17, 18, 13].
4. Jedrne metode
V tem poglavju si bomo ogledali nekaj pomembnih algoritmov za strojno učenje, ki jih pogosto lahko dodatno izboljšamo z uporabo nelinearnih jedrnih funkcij. V razdelku 4.1 bomo primarno sledili viru [17], v razdelku 4.2 viroma [8] in [15], v razdelku 4.3 pa viru [13].
4.1. Metoda podpornih vektorjev. Naj bo dan nabor podatkov S ={(x1, y1),(x2, y2), . . . ,(xn, yn)} ⊆Rd× {−1,1}.
Podatke si lahko predstavljamo kot nabor točk, ki so razdeljene v dva razreda: xi
predstavlja krajevni vektor oziroma koordinato točke v prostoruRd,yipa, kateremu izmed dveh razredov točka pripada.
Prostor Rd bi sedaj s hiperploskvijo radi razdelili na dva dela tako, da bo en del prostora vseboval vse točke razreda 1, drug pa vse točke razreda −1. Hkrati želimo med vsemi primernimi hiperploskvami izbrati tisto, ki je hkrati čim bolj oddaljena tako od točk razreda 1, kot tudi od točk razreda −1.
Zgoraj opisan problem lahko rešujemo z algoritmom, znanim pod imenom me- toda podpornih vektorjev (angl. support vector machine, krajšeSVM). Ta metoda je močno povezana s teorijo linearne ločljivosti, ki smo jo spoznali v razdelku 2.2. Kla- sična metoda podpornih vektorjev iskanje ločitvene hiperploskve omeji na iskanje hiperravnine z dodatnim pogojem, da mora biti minimalna razdalja med hiperrav- nino in točko razreda 1 enaka minimalni razdalji med hiperravnino in točko razreda
−1 ter da je ta razdalja maksimalna možna. Ta dodatni pogoj nam na nek način zagotovi, da bomo med vsemi ločitvenimi hiperravninami izbrali tisto, ki se najbolje prilega, torej tisto, ki je »ravno na sredi« med obema razredoma podatkov.
Če je nabor podatkovS homogeno linearno ločljiv, bo klasična metoda podpornih vektorjev zagotovo rešila problem, saj obstaja homogena linearna funkcija praga ter njena pripadajoča ločitvena hiperravnina. Za začetek se bomo omejili na ta primer.
Glavni pogoj za iskano hiperravnino je, da vse točke razreda 1 ležijo na eni strani hiperravnine, vse točke razreda −1 pa na drugi. To lahko matematično zapišemo kot
(11) yi(⟨w, xi⟩ −b)>0 za i = 1, . . . , n, kjer je ⟨·,·⟩ standardni skalarni produkt v Rd.
Zaradi predpostavke o homogeni linearni ločljivosti je člen b enak 0 in ga lahko izpustimo. Kot smo ugotovili že v razdelku 2.2, je ta problem ekvivalenten iskanju normalnega vektorjaw. Iskanje tega lahko s pomočjo karakterizacije (11) zapišemo tudi v obliki optimizacijskega problema. Obstaja več ekvivalentnih pristopov, eden najbolj pogostih pa je oblike
min
w∈Rd n
∑
i=1
max(0,1−yi⟨w, xi⟩).
Dodatni pogoj prav tako lahko zapišemo v obliki optimizacijskega problema min
w∈Rd
1 2||w||2.
