Csoport-struktúrált generátorrendszerek online tanulása

Csoport-struktúrált generátorrendszerek online tanulása Szabó Zoltán

ELTE, Informatikai Kar

TÁMOP Kutatószeminárium 2011. jan. 28

Szabó Zoltán

Csoport-struktúrált generátorrendszerek online tanulása

Tartalomjegyzék

Motiváció Regressziós feladatok (generátorrendszer fix) Legkisebb négyzetes becslés Lasso feladat (ritkaság) Group-Lasso feladat (csoportok) Általános csoportok és nem-konvex regularizáció

Generátorrendszerek tanulása: ˝ Fokomponens analízis (PCA) Nem-negatív mátrix faktorizáció (NMF) Batch vs online tanulás Hiányos megfigyeltség

Szabó Zoltán


Motiváció

Ajánlórendszerek, Netflix verseny: adottak bizonyos felhasználói értékelések filmekre (X), feladat: X nem-mért értékeinek kitöltése (ajánlás), motiváció: $1M (-2009 szept), fontos tanulság: mátrix faktorizációs megoldások X ≈ DA

(1)

˝ elonyösnek mutatkoznak kitöltés szempontjából.

Dokumentumok (pl Wiki) elemzése, ˝ ˝ Pénzügyi idosorok elorejelzése: mik a kitöltéshez ’jó’ ˝ ... jellemzok,

Szabó Zoltán


Regressziós feladatok: legkisebb négyzetes becslés

Adott: x ∈ Rdx , D ∈ Rdx ×dα . Feladat: f (α) = kx − Dαk22 → min . α∈Rdα

(2)

˝ Megoldás (Moore-Penroose inverzbol): α ˆ = D+ x.

(3)

Ez optimális, abban az értelemben, hogy a kx − Dαk22 -t minimalizálók közül minimális 2-es normájú. ’Gond’: túl sok/akár ∀ D oszlopot használhat. Pl: x dokumentum, D(ictionary) oszlopai témák. ⇒ ritkaság.

Szabó Zoltán


Regressziós feladatok: ritkaság – Lasso és csoportok A ritkasági kényszer megragadható regularizációval: Lasso feladat [k·k1 –ritkaság indukáló norma]: f (α) = kx − Dαk22 + λ kαk1

(λ > 0) → min . α∈Rdα

(4)

Group-Lasso: csoportok → dokumentumokra gondolva a témák közt lehet összefüggés. f (α) = kx −

Dαk22

+

K X i=1

ahol

{Gi }Ki=1

λi αGi 2

(λi > 0, ∀i) → min , α∈Rdα

(5)

a {1, . . . , dα } halmaz egy partíciója.

Szabó Zoltán


Regressziós feladatok: átfedo˝ csoportok, nem-konvex regularizáció Group-Lasso kiterjesztések, átfedo˝ csoportok: f (α) = kx − Dαk22 +

K X i=1

λi αGi 2 → min , avagy α∈Rdα

f (α) = kx − Dαk22 + Ω(α) → min , α∈Rdα

ahol G = {Gi }Ki=1 nem feltétlenül partíció és

K

(0 < η < 1). Ω(α) = λi αGi 2 i=1 η

(6) (7)

(8)

Sikeres egyéb alkalmazás példák: génmintázatok elemzése, arckifejezés felismerés, képekhez kulcsszavak rendelése ˝ (annotálása; keresomotorok) Szabó Zoltán


Generátorrendszerek tanulása–PCA

Adott: xt ∈ Rdx , t = 1, . . . , T mintapontok. ˝ Feladat (fokomponens analízis): keressük azt a dα -dimenziós alteret (D ∈ Rdx ×dα ), i h f (D) = E kx − projD (x)k2

(9)

minimális. Megoldás: cov(x) dα db domináns sajátvektora =: D.

Szabó Zoltán


Generátorrendszerek tanulása–NMF (nem-negativitási kényszer)

Adott: xt ≥ 0 ∈ Rdx , t = 1, . . . , T mintapontok (X). Feladat (nem-negatív mátrix faktorizáció): keressük azt a D ∈ Rd+x ×dα mátrixot és hozzá tartozó A = [α1 , . . . , αT ] ≥ 0 reprezentációt, amire f (D, A) = kX − DAk2F

(10)

minimális.

Szabó Zoltán


Generátorrendszerek tanulása–NMF++ Mixture-of-topic modell (xt szógyakoriságok): D-re (=témákra)Pkényszer: di ≥ 0 oszlopok és l1 -gömbbeliek ( j dij ≤ 1), α-ra megkötés: α ≥ 0,

G: hierarchikus felépítés, Gi az i-edik nódus a gyerekeivel.

Szabó Zoltán


Generátorrendszerek tanulása–batch vs online, hiányos megfigyelések

Batch vs online D becslés: Batch: Becslés módja: X = {x1 , . . . , xT } → D. Hátrány: xt nagydimenziós lehet (pl Wiki-nél) ⇒ nem fér be a memóriába.

Online: t = 0: D0 . t = 1: D0 ,x1 → D1 . t = 2: D1 ,x2 → D2 . ...

˝ csak Hiányos megfigyelések: minden egyes xt -bol ˝ bizonyos koordináták mérhetok.

Szabó Zoltán


Generátorrendszerek tanulása: általános feladat

Felmerült természetes kényszerek: csoport ritkaság és nem-konvex regularizáció ({Gi }Ki=1 , Ω), ˝ D és α-ra: kényszerek lehetosége (pl korlátosság, nem-negativitás) online tanítás, hiányos megfigyelések.

Szabó Zoltán


Az általános feladat–teljesen megfigyelheto˝ eset

Adott: xi ∈ Rdx (i = 1, 2, . . .) megfigyelések, α dictionary kényszer (D ∈ D): D = ×di=1 Di ⊆ Rdx ×dα korlátos, konvex, zárt, reprezentáció kényszer (α ∈ A ⊆ Rdα ):

A: konvex, zárt, struktúrális kényszerek (G): ∪G∈G G = {1, . . . , dα }, dG ∈ Rdα , ≥ 0, G tartójú súlyvektorok,

Szabó Zoltán


Az általános feladat–teljesen megfigyelheto˝ eset (folyt.) Legyen fix D és x-re, az x-hez tartozó α reprezentáció: 1 2 kx − Dαk2 + κΩ(α) (κ > 0) l(x, D) = min α∈A 2

(11)

minimum helye, ahol Ω(y) = k(kdG ◦ yk2 )G∈Gkη

(η ∈ (0, 1]).

(12)

l(xi , D) → min ,

(13)

Feladat (OSDL): ft (D) = Pt

1

t ρ X i

t

ρ j=1 (j/t) i=1

D∈D

ahol ρ ≥ 0 felejtési ráta. Speciálisan (ρ = 0): t

ft (D) =

1X l(xi , D). t

(14)

i=1

Szabó Zoltán


Az általános feladat–hiányosan megfigyelt eset

˝ Az i-edik idopillanatban az Oi ⊆ {1, . . . , dx } koordinátákat ˝ x Oi . látjuk xi -bol: l(xi , D) helyett az (x, D)-hez tartozó α legyen:

1

xO − DO α 2 + κΩ(α) , l(x, D, i) = min i i 2 α∈A 2

(15)

minimum helye.

Feladat: ft (D) = Pt

1

t ρ X i

ρ j=1 (j/t) i=1

Szabó Zoltán

t

l(xi , D, i) → min . D∈D

(16)


Fontos speciális esetek

Oi = {1, . . . , dx } (∀i): teljesen megfigyelheto˝ eset. Speciális esetek G-re: |G| = dα és G = {{1}, {2}, . . . , {dα }}: αi -k közt nincs kapcsolat (klasszikus ritka dictionary). Ezen belül, ha D adott, ρ = 0, η = 1, di = ei : Lasso feladat. |G| = dα , αi egy fa nódusai, G = {gyerek1 , . . . , gyerekdα }: fa-struktúrált, hierarchikus reprezentáció |G| = dα , αi egy rácson, G = {NN1 , . . . , NNdα }, NNi i-edik pont r -sugarú környezete: rács reprezentáció. G = {P1 , . . . , PK }, {Pk }Kk=1 a {1, . . . , dα } halmaz egy partíciója: non-overlapping csoport struktúra.

Szabó Zoltán


Fontos speciális esetek (folyt.)

Speciális esetek D, A-ra: Di = L2 -gömb (∀i), A = Rdα : D oszlopaira kdi k2 ≤ 1 korlát, Di = nem-negatív L2 -gömb (∀i), A = Rd+α : struktúrált NMF, Di = nem-negatív L1 -gömb (∀i), A = Rd+α : struktúrált mixture-of-topics modell.

Speciális eset dG -re: dG = χG (∀G ∈ G), ahol χ a karakterisztikus fg: nem alkalmazunk extra súlyozást.

Szabó Zoltán


Optimalizáció

Az OSDL feladat ekvivalens a D dictionary és az {αi }ti=1 együtthatók együttes optimalizációjával: ft (D, {αi }ti=1 ) →

min

D∈D,{αi ∈A}ti=1

,

(17)

ahol t ρ X

2 i 1

x − DOi αi 2 + κΩ(αi ) . (18) ft = Pt ρ t 2 Oi j=1 (j/t) i=1 1

Szabó Zoltán


Optimalizáció (folyt.)

D online optimalizációja: Az aktuális xOt -re és Dt−1 -re αt -t az

2 1

x − (Dt−1 )Ot α 2 + κΩ(α) αt = argmin 2 Ot α∈A

(19)

feladat mo-jaként becsüljük. Az eddigi {αi }ti=1 -ket ’használva’ Dt a ˆft (Dt ) = min ft (D, {αi }t ) i=1 D∈D

(20)

kvadratikus probléma megoldásaként kapjuk.

Szabó Zoltán


α becslés Kihasználva, hogy ∀ y ∈ Rd és η ∈ (0, 2) esetén d

kykη = min

z∈Rd+

2

1 X yj 1 + kzkβ , 2 zj 2

(21)

i=1

= |yi |2−η kykη−1 kapjuk: η  

X dG ◦ α 2 2  2Ω(α) = min + kzkβ  G |G| z G z=[(z )G∈G ]∈R+ G∈G h i = min αT diag(ζ)α + kzkβ , (22)

ahol β =

η 2−η ,

és minhely

zi∗

|G|

z∈R+

ahol ζ = ζ(z) ∈ Rdα , és ζj =

X

G∈G,G∋j Szabó Zoltán

djG

2

zG

.

(23)


α becslés (folyt.) ˝ o˝ alakot az optimalizációs feladat: Beírva az eloz J(α, z) →

min

|G|

,

(24)

α∈A,z∈R+

ahol

1

xO − (Dt−1 )O α 2 + κ 1 αT diag(ζ)α + kzk . β t t 2 2 2 (25) Optimalizáció iterálva: J(α, z) =

Fix z-re: A = Rdα -re (A = Rd+α -re) least squares (nem-negatív). Ált. esetben is: kvadratikus költség, konvex felt-el–standard megoldók. Fix α-ra: G η−1 z G = kdG ◦ αk2−η 2 k(kd ◦ αk2 )G∈Gkη , G ∈ G. Szabó Zoltán

(26)


D becslés

BCD optimalizációval (dj -re, a többi di (i 6= j)-t addig fixálva). ˆft kvadratikus dj -ben, így ∂ˆft (uj ) = 0 ∂dj

(27)

megoldását vetítjük a feltételi Dj halmazra: dj ← ΠDj (uj ). Belátható: uj eleget tesz az Cj,t uj = bj,t − ej,t + Cj,t dj ,

(28)

diag-os ehómtx-ú lineáris egyenletrendszernek, ahol

Szabó Zoltán


D becslés (folyt.)

Cj,t

=

t ρ X i

∆i α2i,j ∈ Rdx ×dx , (j = 1, . . . , dα )

=

t ρ X i

∆i xi αTi = [b1,t , . . . , bdα ,t ] ∈ Rdx ×dα , (30)

i=1

Bt

ej,t

=

i=1 t X i=1

t

t i t

ρ

∆i Dαi αi,j ∈ Rdα , (j = 1, . . . , dα ),

(29)

(31)

ahol ∆i = ’mtx-os formában Oi ’. Itt mind Cj,t -k, mind Bt t ρ X i i=1

t

Ni

(32)

típusú mtx sorozatok. Szabó Zoltán


D becslés (folyt.)

Felejtést leíró rekurziók (teljes indukcióval belátható): Nt ∈ RL1 ×L2 (t = 1, 2, . . .) adott mtxsorozat. Legyen Mt M′t

= γt Mt−1 + Nt ∈ RL1 ×L2 t ρ X i Ni ∈ RL1 ×L2 = t

(t = 1, 2, . . .),

(33)

(t = 1, 2, . . .).

(34)

i=1

Ekkor ρ = 0-ra: Mt = M0 + M′t (∀t ≥ 1), ρ > 0-ra: Mt = M′t (∀t ≥ 1).

Szabó Zoltán


D becslés (folyt.) ˝ a Emiatt a Cj,t , Bt statisztikák online frissíthetok Cj,t = γt Cj,t−1 + ∆t α2tj , Bt = γt Bt−1 + ∆t xt αTt ,

(35) (36)

˝ módon (i) ρ = 0-ra: Cj,0 = 0, B0 = 0, (ii) ρ > 0 tetszoleges ρ indítással, ahol γt = 1 − 1t . ej,t =

t ρ X i i=1

t

∆i Dαi αi,j

(37)

˝ általános esetben (∆i 6= I) nem emelheto˝ ki D, de ej,t -re -bol egy numerikusan jó online közelítése ej,t = γt ej,t−1 + ∆t Dt αt αt,j

(38)

az aktuálisan becsült Dt -vel. Szabó Zoltán


OSDL: alkalmazás kitöltésre

D optimalizáció: xO1 , . . . , xOT → D.

(39)

új, kitöltendo˝ mintapont: xO , α optimalizáció: (xO , DO ) → α.

(40)

Kitöltés:

x becslés: ˆ = Dα. x

Szabó Zoltán

(41)


Illusztráció: természetes képek kitöltése

Hiányosan megfigyelt képrészleteken tanult D, teljes képkitöltési feladaton, Tesztkép (eddig semmilyen formában nem látott):

PSNR (peak signal-to-noise ratio): nagy a jó, wireless kommunikációban (kép-, videó tömörítésben) elfogadható 20 − 25 dB (30 dB).

Szabó Zoltán


Illusztráció - folyt. val = 0.3 ptr = 0.5, ptest

Szabó Zoltán


Illusztráció - folyt. val = 0.3 (PSNR = 36 dB): ptr = 0.5, ptest

Szabó Zoltán


Illusztráció - folyt. val = 0.7 ptr = 0.5, ptest

Szabó Zoltán


Illusztráció - folyt. val = 0.7 (PSNR = 29 dB): ptr = 0.5, ptest

Szabó Zoltán


Köszönöm a figyelmet!

Szabó Zoltán


Csoport-struktúrált generátorrendszerek online tanulása

Recommend Documents