UČENÍ BEZ UČITELE Václav Hlaváč Fakulta elektrotechnická ČVUT v Praze katedra kybernetiky, Centrum strojového vnímání
[email protected], http://cmp.felk.cvut.cz/~hlavac
OBSAH PŘEDNÁŠKY
1/22
ÚVOD
Učení bez učitele se používá pro analýzu pozorování (nebo dat), když není k dispozici informace od učitele, tj. trénovací multimnožina.
2/22
Pozorovaná data se mají vysvětlit pomocí matematického modelu. • Statistický přístup – učení statistického modelu z dat.
Neformálně: data patřící jedné třídě jsou si navzájem podobnější než data z různých tříd.
• Deterministický přístup – podle jiných měr podobnosti dat, např. podle vzdálenosti.
Jiný název: shluková analýza.
MOTIVAČNÍ OBRÁZEK 3/22
SHLUKOVÁ ANALÝZA, 2 PŘÍSTUPY 4/22
1. Hierarchické – další shluky se hledají na základě předchozích shluků, a to metodou shora dolů nebo zdola nahoru.
Metoda k-průměrů (angl. k-means).
2. Rozdělující – najdou shluky najednou (těm se budeme v této přednášce především věnovat).
EM algoritmus.
STATISTICKÝ PŘÍSTUP
Pozorování se obvykle chápou jako náhodné veličiny.
Výsledkem učení je statistický model dovolující přiřadit pozorování x ∈ X ke třídě (skrytému stavu) k ∈ K, a to podle modelované sdružené hustoty pravděpodobnosti p(x, k ).
Ze statistického modelu p(x, k ) se odvozují podmíněné pravděpodobnosti tříd p(x|k ) a mohou se použít pro (bayesovské) rozhodování (jako v případě učení s učitelem).
5/22
Další důležitou aplikací statistického učení bez učitele je komprese dat.
POUŽÍVANÉ VELIČINY
x ∈ X - pozorování.
k ∈ K - skrytý stav (výsledek rozpoznávání).
q : X → K - rozhodovací strategie (klasifikátor).
x = (x1, x2, . . . , xn) - posloupnost pozorování (z trénovací multimnožiny).
k = (k1, k2, . . . , kn) - posloupnost výsledků rozpoznávání (informace učitele z trénovací multimnožiny).
6/22
Θ
- parametr, na němž závisí rozhodovací strategie.
KLASIFIKÁTOR S PROMĚNNÝMI PARAMETRY Dosud jsme se soustředili na návrh klasifikátoru, jehož rozhodovací funkce q závisela na parametru Θ.
x
q(x,Θ) Θ k = q (x, Θ)
k
7/22
UČENÍ S UČITELEM 8/22
x
q(x,Θ)
k
Θ x’ k’
uèení
Θ=
učení(x, k )
trénovací data
Rozhodovací pravidlo se naučí na základě trénovací multimnožiny.
UČENÍ BEZ UČITELE 9/22
x
q(x,Θ)
k
Θ uèení bez uèitele
Θ=
učení(x, k )
Pro (samo)učení se používá místo trénovací množiny výstup z klasifikátoru.
ALGORITMUS UČENÍ BEZ UČITELE 10/22
Inicializace, tj. počáteční volba parametru Θt=0.
Rozpoznávání k = q (x, Θt)
Cyklus
Učení Θt+1 = učení(x, k )
Důležitou otázkou je konvergence algoritmu.
PROČ JE UČENÍ BEZ UČITELE DŮLEŽITÉ?
Klasifikace dat není předem známá. Příklad: dolování v datech (angl. data mining).
Klasifikace dat člověkem může být příliš drahá. Příklad: rozpoznávání řeči. Složitý skrytý markovský model posloupnost. Vyžaduje spoustu trénovacích dat.
Rozsáhlé datové soubory je možné komprimovat tím, že se nahradí několika málo významnými reprezentanty.
11/22
Lze použít jako metodu aproximující složitou hustotu pravděpodobnosti pomocí směsi (např. gaussovských) rozdělení.
PŘÍKLAD UČENÍ BEZ UČITELE ALGORITMUS n-PRŮMĚRŮ
12/22
Předpokládejme statistický model pk (1) = pk (2) = . . . = pk
|K|
p(x|kj , µj ) jsou gaussovská rozdělení s jednotkovou kovarianční maticí. Parametry Θ = µ1, . . . , µ|K|. Rozpoznávání podle bayesovské strategie k = argmax p(k 0|x) = argmin kx − µk0 k k0
k0
odpovídá rozpoznávání podle nejbližšího souseda.
PŘÍKLAD UČENÍ BEZ UČITELE ALGORITMUS n-PRŮMĚRŮ (2)
13/22
Učení – maximálně věrohodný (ML) odhad parametrů Θt+1 = argmax
n X
Θ
=
argmax
i=1 n X
µ1,...,µ|K|
=
argmin µ1,...,µ|K|
= argmin 1
log pxk (xi, ki)
i=1 n X
1 −1 log √ exp (x − µki )T (x − µki ) 2 ( 2π) n
(x − µki )T (x − µki )
i=1
X
(x − µki )T (x − µki ), . . . , argmin k
i∈I1
1 X xi , ⇒ µj = |Ij | i∈Ij
j = 1, . . . |K|
X i∈Ik
(x − µki )T (x − µki )
VZTAH K ÚLOZE ODHADU HUSTOT PRAVDĚPODOBNOSTI
14/22
Parametrické odhady ⇒ maximálně věrohodný (ML) odhad.
Již známe:
Neparametrické odhady ⇒ metoda Parzenova okna (nebo metoda n-nejbližších sousedů).
Alternativní metoda: modelování hustoty pomocí směsi gaussovských rozdělení.
EM ALGORITMUS, NEFORMÁLNĚ 15/22
je iterativní postup z rodiny maximálních věrohodných odhadů (MLE) pro případy, kde MLE řešení neexistuje nebo je velmi složité;
se typicky používá při chybějících datech nebo informaci od učitele pro vytvoření trénovací množiny;
převádí rozkládá jednu složitou MLE optimalizační úlohu na několik jednodušších optimalizačních úloh tím, že zavede “chybějící parametr”.
EM algoritmus
používá gradientní optimalizaci (nejstrmější vzestup) pro nalezení MLE optima. Proto trpí neduhem uvíznutí v lokálních extrémech.
EM, STATISTICKÝ MODEL 16/22
Předpokládáme libovolný statistický model p(x, k ; Θ) = p(k ; Θ) p(x|k ; Θ) = p(k ) p(x|k ; Θk ) Θ = (p(k ), Θk ), k = 1, . . . , |K|
EM, OPAKOVÁNÍ DVOU KROKŮ 17/22
E krok (rozpoznávání), Bayesovský odhad stavu k, tj. p(k) p(x; Θk ) α(i, k) = p(x|k) = P p(k) p(x; Θk ) k
Pozn. u k-means α(i, k) ∈ {0, 1}. Zde je odpovědí rozdělení pro stav k, tj. p(k|xi). M krok, (učení), maximálně věrohodný odhad z daného pozorování x a odhadnutých stavů k Θt+1 = argmax Ep(k|x) (Lx,k (Θ)) Θ
Očekávaná věrohodnostní funkce Lx,k (Θ) =
n X i=1
log p(k) p(x; Θk )
EM ALGORITMUS 18/22
Inicializace Θ0 = p
0
(k), Θ0k
,
k = 1, . . . , n .
Cyklus Rozpoznávání
t t p (k) p(x ; Θ ) i t k α (i, k) = P t p (k) p(xi; Θtk )
k
Učení n X αt(i, k) t+1 p (k) = n i=1
Θkt+1 = argmax Θk
n X i=1
αt(i, k) log p(xi, Θi)
VLASTNOSTI EM ALGORITMU (1)
19/22
Maximalizuje věrohodnostní funkci L(Θ) =
n X
log p(xi; Θ) =
i=1
n X
log
i=1
X |k
p(k) p(xi, Θ) {z
p(xi;Θ)
}
Obecně platí L(Θ0) ≤ L(Θ1) ≤ . . . ≤ L(Θt). Posloupnost L(Θt) konverguje pro t → ∞ k L∗ (L je shora omezená), které je buď • lokálním minimem, • sedlovým bodem nebo • globálním minimem.
VLASTNOSTI EM ALGORITMU (2)
20/22
Pokud je funkce Θt+1 = f (Θt) = L x, R(x, Θt) spojitá, pak posloupnost Θ0, Θ1, . . . , Θt pro t → ∞ konverguje k Θ∗. Pro speciální statistické modely, např. model podmíněné nezávislosti a dva stavy, konverguje EM algoritmus ke globálnímu maximu. Hypotéza: platí i pro více stavů.
ML ODHAD POMOCÍ EM
EM je pro ML odhady vhodný.
Věrohodnostní funkce L(Θ) = p(x; Θ).
21/22
Pokud lze rozložit pravděpodobnostní model p(x; Θ) =
X
p(x, k; Θ) ,
k = 1, . . . , |K|,
k
potom lze EM algoritmus použít pro ML odhad parametrů směsi.
Příklad: odhad parametrů pro odhad konečných směsí, často gaussovských. ML odhad parametrů Θ∗ = argmax L(Θ).
Θ
Pro jednoduché statistické modely je analytické řešení,
∂L(Θ) ∂Θ
= 0.
EM MINIMALIZUJE DOLNÍ MEZ L
EM začíná z nějakého odhadu Θ0.
22/22
Potom se v cyklu opakuje: E-krok: odhadne dolní mez funkce L(Θ) v bodě Θt. M-krok: nalézá novou hodnotu parametru Θt+1, která maximalizuje odhadnutou dolní mez. Ta se lépe optimalizuje.
L(Θ) new estimate
lower bound
Θ
t+1
t
Θ
Θ
