F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek Bod´ o Zal´ an
F´elig-fel¨ugyelt tanul´as kernelekkel ´es hashing m´odszerek Bod´ o Zal´an Babe¸s–Bolyai Tudom´ anyegyetem, Kolozsv´ ar Matematika ´ es Informatika Kar Magyar Matematika ´ es Informatika Int´ ezet
1/1
Tartalom
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek Bod´ o Zal´ an
2/1
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek
F´elig-fel¨ugyelt tanul´as kernelek seg´ıts´eg´evel Fel¨ ugyelt ´ es f´ elig-fel¨ ugyelt tanul´ as I
I
Bod´ o Zal´ an
fel¨ ugyelt: D = {(xx i , yi ) | x i ∈ X ⊆ Rd , yi ∈ {−1, +1}, i = 1, . . . , `}; keress¨ uk f : X → {−1, +1}-et, amely egyezik D-vel f´elig-fel¨ ugyelt: D = {(xx i , yi ) | i = 1, . . . , `} ∪ {xx j | j = ` + 1, . . . , ` + u =: N}, ` u; I
I
indukt´ıv: keress¨ uk f : X → {−1, +1}-et, amely egyezik D-vel + DU felhaszn´ al´ asa transzdukt´ıv: keress¨ uk f : DU → {−1, +1}-et felhaszn´ alva a D = DL ∪ DU adatokat
4
4
2
2
0
0
−2
−2
−4
−4 −6
−6 0
5
10
0
5
10
3/1
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek
Kernel m´ odszerek a g´ epi tanul´ asban
I
I
James Mercer (1909): minden folytonos szimmetrikus pozit´ıv definit kernel f¨ uggv´eny fel´ırhat´ o skal´arszorzatk´ent egy (nagydimenzi´ os) t´erben kernel: k(xx , z ) = hφ(xx ), φ(zz )i = φ(xx )0 φ(zz ), feature lek´epez´es: φ:X →H alkalmazhat´ o minden geometriai konstrukci´ o eset´en, ha az FEJEZET 6. KERNEL ´ 132 sz¨ ogeket, hosszokat eMÓDSZEREK s t´avols´agokat haszn´al
◦
1
1
0.8
0.8
X1X2
×
X1X2
I
Bod´ o Zal´ an
0.6
0.6
0.8
0.8 0.2
◦
(a)
(a) 1. ´abra.
×
0 0
0.2
0.4
0.6
0.6
0.2 0 0
1
1
0.4
0.4
0.4
0.4 0.2
0.6
0.8 X21
(b)
0.2
0.4 0.2
1
0
0.6
X22
0.8
1
0
X2 2
X2 1
(b)
6.1. ábra. Az XOR feladat – bal oldali ábra – és a nemlineáris vetítés, mely szeparálAz XOR (a)– input erben, (b) m´ asodfok´ u polinomi´ alis kernel hatóvá teszifeladat: az adatokat jobbra t´
´ altal gener´ alt t´ erben. tól a legtávolabb van. Ez összekapcsolható a 2.4. fejezetben említett regularizáció módszerével, ugyanis ez a hipersík a legstabilabb a lehetséges hipersíkok közül. A
4/1
Gyakran haszn´ alt kernelek: I
line´aris:
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek Bod´ o Zal´ an
k(xx , z ) = x 0z I
polynomi´alis: k(xx , z ) = (axx 0z + b)c
I
Gauss-f´ele, RBF: kxx − z k2 k(xx , z ) = exp − 2σ 2
I
szigmoid: k(xx , z ) = tanh(axx 0z + r )
5/1
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek
F´ elig-fel¨ ugyelt kernelek
Bod´ o Zal´ an
Adatf¨ ugg˝ o (data-dependent) kernelek I
hagyom´anyos kernelek: D1 6= D2 adathalmazok eset´en, x , z ∈ D1 ∩ D2 k(xx , z ) = k(xx , z )
I
adatf¨ ugg˝ o kernelek: D1 6= D2 adathalmazok eset´en, x , z ∈ D1 ∩ D2 k(xx , z ; D1 ) m k(xx , z ; D2 )
I
ahol m”-et nem felt´etlen¨ ul egyenl˝ o”-k´ent olvassuk ” ” fel¨ ugyelt tanul´as + adatf¨ ugg˝ o kernelek = f´ elig-fel¨ ugyelt tanul´ as
6/1
B
Klaszter-kernelek ] I klaszter feltev´ Σet pont es (cluster assumption): ha k´ ugyanabban a klaszterben van, nagy val´ osz´ın˝ us´eggel A B (= ua. a c´ımk´ej¨uk) ugyanabba az oszt´alyba is tartoznak I hierarchikus klaszter-kernel: → I
I
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek Bod´ o Zal´ an
haszn´ aljuk a hierarchikus klaszterez´esb˝ ol sz´ armaz´ o t´ avols´ agokat (single, complete, average linkage) hasznos tulajdons´ ag: ultrametrikusC t´ avols´ agm´ atrixot C eredm´enyez az adatokonC 3
1
2
5 3 3 A
T´etel [Fischer, 2003]
2 B
C
1 D
E
A B C D E
Adott ultrametrikus M eset´en a − 12 M c = − 21 J M J m´ atrix egy Gram-m´ atrix lesz, amely a z i , i = 1, 2, . . . , N vektorok skal´ arszorzatait tartalmazza, melyek euklideszi t´ avols´ agai az M -ben vannak (JJ = I − (1/N)1110 ). I
az algoritmus: (i) pontok hierarchikus klaszterez´ese, (ii) Mij = linkage t´ avols´ ag az ered˝ o ultrametikus f´ aban a legk¨ ozelebbi k¨ oz¨ os felmen˝ on´el, Mii = 0.
7/1
I
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek
´ats´ ulyoz´ o klaszter-kernelek: I I
kernel kombin´ aci´ ok: K 1 + K 2 , a · K , K 1 K 2 ´ ats´ ulyoz´ o klaszter-kernel: K = K rw K b , ahol I I
I
Bod´ o Zal´ an
K b = alap kernel (pl. Gauss, polinomi´ alis stb.) K rw = ´ ats´ ulyoz´ o kernel
Gauss-f´ele ´ ats´ ulyoz´ o kernel: 1 U ·xx − U ·zz k2 krw (xx , z ) = exp − 2 kU 2σ
I
skal´ arszorzat alap´ u´ ats´ ulyoz´ o kernelek: K rw = U 0U + α · 11 0 ,
α ∈ [0, 1)
K rw = β · U 0U + 11 0 ,
β ∈ (0, ∞)
ahol U a K × N m´eret˝ u klaszter hovatartoz´ asi m´ atrix (oszlopokban) I
probl´ ema: ´altal´anos´ıt´as – k¨ ozel´ıt˝ o m´ odszerek
8/1
Legk¨ozelebbi szomsz´edok gyors keres´ese Legk¨ ozelebbi szomsz´ edok keres´ ese pozit´ıv definit kernelekkel I egyenl˝ otlens´egek: p d 2 (x, z) ≥ k(x, x) + k(z, z) − 2 k(x, x)k(z, z) 1 d 2 (x, z) ≥ k(z, z) − k(x, x) 2 2 I t´ aroljuk a maxim´alis dmax t´avols´agot, ´es mindig megn´ezz¨ uk, 1 2 hogy pl. 2 k(z, z) − k(x, x) ≥ dmax I a sz´ am´ıt´asok ak´ar 50%-´at megtakar´ıthatjuk
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek Bod´ o Zal´ an
y
1
2
3
5
6
9
8
001100
1, 3, 6, . . .
110010
4, 7, 8, . . .
...
...
...
...
010100
2, 5, 9, . . .
4
x z
7
2. ´abra. Locality-sensitive hashing
9/1
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek
Hashing m´ odszerek
Bod´ o Zal´ an
1
Locality-sensitive hashing v´ eletlen hipers´ıkokkal I Hamming-t´ avols´ag hat´ekonyan kisz´am´ıthat´ o: dH (uu , v ) =
n X (uu XOR v ) i=1
I
I
a k darab hash f¨ uggv´eny¨ unk legyen 0 1, r i u ≥ 0 hi (uu ) = , i = 1, 2, . . . , k, r ∈ Rd v´eletlen vektor 0, r 0i u < 0 egy x ponthoz rendelt bin´aris hash szekvencia [h1 (xx ), h2 (xx ), . . . , hk (xx )]
I
ekkor: u r
P(hr (u) = hr (v )) = 1−
θ(uu , v ) π v
1 Hely´ erz´ ekeny
has´ıt´ as/hashel´ es
10/1
Hash kulcsok kiterjeszt´ ese c´ımk´ ezett adatok seg´ıts´ eg´ evel I felt´ etelezz¨ uk, hogy vannak c´ımk´ezett pontjaink (minden oszt´alyb´ ol) I valamilyen hashing m´ odszerrel el˝ o´all´ıtott bin´aris kulcsok + hibajav´ıt´ o k´ odok seg´ıts´eg´evel tan´ıtott f´elig-fel¨ ugyelt m´ odszerek (ECOC) I ECOC: I
1 1 M = −1 −1
I
I
Bod´ o Zal´ an
k´ odm´ atrix:
I
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek
1 −1 1 −1
1 −1 −1 1
−1 1 1 −1
−1 1 −1 1
−1 −1 1 1
M (oszt´ alyok sz´ ama ×c) minden oszlop´ ara betan´ıtunk egy f´elig-fel¨ ugyelt modellt kimenet: fi (xx ) = a FF m´ odszer kimenete, i = 1, . . . , c
kiterjesztett kulcsok: [h1 (xx ), . . . , hk (xx ), f1 (xx ), . . . , fc (xx )] {z } | kiterjeszt´es
11/1
F´ elig-fel¨ ugyelt tanul´ as kernelekkel ´ es hashing m´ odszerek Bod´ o Zal´ an
K¨ osz¨ on¨ om a figyelmet!
12/1
