Originalne prosojnice (str. 90–94)
Druga polovica predmeta. Pojmovni aparat (okolje, področje uporabe, vzorec, razred), zapisi vzorcev, rojenje, razvrščanje in preizkušanje. Daje izpitne naloge 19, 20 in 21.
Disciplina »razpoznavanje vzorcev«:
| Pojem | Definicija |
|---|---|
| Okolje $O$ | Množica predmetov, pojavov in bitij (objektov) v prostoru in času, ki jih razpoznavamo. Razpoznavalni sistem, ki bi se zavedal celotnega okolja, je danes še neizvedljiv. |
| Področje uporabe $PU$ | Vsebuje samo tiste objekte in njihove medsebojne zveze, ki jih razpoznavamo, torej $PU \subset O$. Primer: razpoznavanje števk 0–9 in črk; registrskih tablic; kontrola kvalitete zamrznjenega sadja… |
| Razred objektov | Podmnožica objektov iz $PU$, na katere se nanaša oznaka (simbol, ime razreda). Število razredov $M \geq 2$ je določeno z nalogo. Razredi so tuji in neprazni, njihova unija je enaka $PU$. |
| Vzorec | Vsebina čutil — odčitek merilnih naprav, ki daje organizmu (stroju) podatke o objektu ali objektih in njihovih medsebojnih zvezah. |
| Razred vzorcev | Slika razreda objektov. Sestavljajo ga vzorci, ki so slike objektov iz razreda objektov. V posameznem razredu vzorcev so najbolj podobni si vzorci. |
Pri tem sta 1 in 2 začetni opis vzorca, 3 do 5 pa izpeljani zapis vzorca. Ločimo tudi preprost in zapleten vzorec.
| Pojem | Definicija |
|---|---|
| Spoznavanje področja uporabe | Predpogoj za razpoznavanje objektov. Je preslikava, ki preslika množico vzorcev objektov razpoznavanja v učno množico vzorcev $UM$. |
| Učna množica $UM$ | Končna množica vzorcev z danega $PU$, iz katere se stroj (samodejno) nauči zvez med oznakami razredov in objekti. $UM = (S_N, \Omega)$, kjer je $S_N$ množica vzorcev (velikosti $N$), $\Omega$ pa množica oznak razredov. Vzorce iz $S_N$ je označil učitelj. $UM$ mora zajemati vzorce iz vseh možnih razredov. |
| Učenje | Proces, v katerem se vzpostavijo zveze med vzorci iz $S_N$ in oznakami razredov $\Omega$. Pogosto učimo z nepopolno indukcijo: pravila, ki veljajo v $UM$, posplošimo na celotno $PU$. |
| Razvrščanje (klasifikacija) | Proces razporejanja vzorcev v razrede, sestavljene iz že prej razvrščenih, medsebojno podobnih si vzorcev. Razvrščamo s prileganjem, odločanjem, stavčno analizo ali z logičnim sklepanjem. Temelji na merjenju razdalje med vzorci. |
| Razpoznavanje vzorcev | Zadnja faza procesa zaznavanja, v kateri se določi istovetnost ali velika podobnost nove vsebine čutil z vsebino, ki je že bila spoznana in zapomnjena. |
Predavanja jo pokažejo z zgledom stavka. Razvrščanje je: vsako besedo posebej uvrstim v kategorijo. Razpoznavanje je: razumem, kaj stavek pomeni.
| Beseda v stavku | Pomen |
|---|---|
| Z | Skupaj s kom |
| Lučko | osebo ženskega spola |
| tečeva | hitiva ali se nama mudi |
| na kavo | na pijačo |
| v As. | v kavarno ali gostilno |
Model velja za vzorce, zapisane v obliki nestrukturirane množice vrednosti značilnic. Sistem ima dve fazi, ki ju preklaplja »stikalo«:
Pot signala: sistem za zajemanje vzorcev → določitev vrednosti značilk → množica značilk $\{x_1, \dots, x_n\}$ → (1) učenje ali (2) razvrščanje → vzorec pripada razredu $C_i$.
Vzorec je zapisan kot množica meritev, ki so rezultat merjenja ene ali več količin (lastnosti), ki zaznamujejo objekte razpoznavanja. Vzorec je predstavljen kot eno- ali večdimenzionalna matrika meritev (označimo ga z $m$). Primer začetnega zapisa vzorca za slivo:
| Tip | Podtip | Primer | Aritmetika? |
|---|---|---|---|
| Kvalitativni | nominalni — jih ni moč urejati | seznam imen barv | NI dovoljena |
| ordinalni — jih lahko urejamo | majhen, srednji, velik | ||
| Kvantitativni | absolutni | masa v kg (0 kg je najmanjša možna masa) | je dovoljena |
| relativni | temperatura v °C |
Pri zapisu vzorca v obliki množice vrednosti značilnic od meritev obdržimo ali izpeljemo le najpomembnejše lastnosti objekta glede na nalogo, ki jo rešujemo. Bistvene lastnosti objektov so tiste, ki poudarjajo posebnosti posameznih razredov vzorcev. Takšno lastnost imenujemo značilnica.
Pristopa za določanje značilnic:
Cilj: poiskati le tisto informacijo iz množice meritev $m$, ki je pomembna za razvrščanje vzorcev.
Najboljša (optimalna) množica značilnic je tista, ki v novem, manj razsežnem prostoru ne poveča verjetnosti napačnega razvrščanja vzorcev s teoretično najboljšim razvrščevalnikom (tj. Bayesov razvrščevalnik).
Iz množice meritev izločimo spremenljivke, ki ne prispevajo k natančnosti razpoznavanja oz. ne prispevajo k boljši ločljivosti razredov v prostoru $\mathbb{R}^n$.
Izbrane značilnice ohranijo pomen in enoto izbranih meritev.
Primer: $x_1 = m_2$, $x_2 = m_4$.
Preslikava $r$-dimenzionalnega prostora meritev v $n$-razsežni prostor značilnic, pri čemer je $n < r$. V novem prostoru se mora ohraniti (ali zgolj minimalno zmanjšati) stopnja ločljivosti razredov.
Izpeljane značilnice ne ohranijo niti pomena niti enot meritev.
Primer: $[x_1, x_2] = A(m_1, \dots, m_5)$.
Poznani postopki izpeljave značilnic: analiza glavnih komponent (PCA) oz. dekompozicija na singularne vrednosti (SVD) oz. Karhunen-Loèvejeva transformacija, analiza neodvisnih komponent itd.
Temelji na samodejnem razvrščanju (rojenju) vzorcev iz končne množice vzorcev $S_N$ ter na označevanju rojev vzorcev z oznakami razredov. Je preslikava, ki preslika množico $S_N$ v učno množico $UM$ — preslikava ni avtomatična, saj označevanje vzorcev opravi učitelj.
1. Ali kakšni značilnici vzorca manjka vrednost?
Rešitev: a) vzorec izločimo iz $S_N$, ali b) manjkajočo vrednost nadomestimo s povprečno vrednostjo
te značilnice, izračunane iz preostalih vzorcev.
2. Ali vrednost značilnice pri posameznem vzorcu zelo odstopa od povprečja?
Rešitev: a) vzorec izločimo iz $S_N$, ali b) uporabimo drugačno razdaljo med vzorci, ki ne poudarja
razlike vrednosti značilnic.
Izračunamo tri pomožne izraze za vsako značilnico $j$:
Vrednost značilnice »zelo« odstopa od povprečja, če je izraz $\dfrac{|x_j - \mu_j|}{\sigma_j}$:
V tem predmetu je $\sigma_j^2 = \frac{1}{N}\sum(x_{i,j} - \mu_j)^2$ — torej populacijska varianca (delimo z $N$, ne z $N-1$). Če uporabiš vzorčno varianco, dobiš pri nalogi 19 številko, ki ni med ponujenimi.
Postopek je potreben, če želimo, da imajo vse značilnice enak doprinos pri računanju mere podobnosti. Sicer bi značilnica z veliko številsko vrednostjo (npr. masa v gramih) povsem prevladala nad drugo (npr. dolžina v metrih).
a) Simetrična porazdelitev okoli $\mu_j$ ($|\Upsilon_j| \approx 0$) → linearna transformacija:
Skaliranje/linearizacija — če želimo značilnice na intervalu $[0, 1]$ ali $[-1, 1]$:
kjer sta $x_j^{\min}$ in $x_j^{\max}$ minimalna in maksimalna vrednost $j$-te značilnice, $s_{\min}$ pa je 0 za interval $[0, 1]$ oz. −1 za interval $[-1, 1]$.
b) Asimetrična porazdelitev okoli $\mu_j$ ($|\Upsilon_j| \neq 0$) → nelinearna transformacija v DVEH korakih:
4. Ali se vzorci v prostoru značilnic porazdeljujejo naključno oz. po določenih zakonitostih?
Naključna porazdeljenost oz. porazdeljenost po določeni zakonitosti kaže na neprimerno določitev
značilnic — če se vzorci ne zberejo v roje, izbrane značilnice razredov ne ločujejo.
Cilj: v fazi samodejnega razvrščanja dobimo na vhod razpoznavalnika neznan vzorec $x$, ki ga moramo razvrstiti v enega izmed razredov vzorcev $C_i$.
Razvrščevalnik vzorcev vključuje znanje o posameznem razredu bodisi:
Tipični predstavnik razreda običajno določimo kot povprečje vseh vzorcev razreda:
Razvrščamo na osnovi prileganja oz. merjenja podobnosti med neznanim vzorcem $x$ in vzorci iz $UM$. Ideja: v učni množici poiščemo vzorec, ki je najbližji vzorcu $x$, in $x$ razvrstimo v razred, iz katerega prihaja ta najbližji vzorec.
Izpeljanke osnovnega pravila: »k najbližjih sosedov« in »(k, l) najbližjih sosedov«.
Poglej $k$ najbližjih sosedov neznanega vzorca. Vzorec razvrsti v razred le, če vsaj $l$ od teh $k$ sosedov pripada temu razredu. Če noben razred ne doseže praga $l$, vzorca ni možno razvrstiti — in to je pri nalogi 20 pogosto eden od ponujenih odgovorov. Pri (3, 2) torej: pogledaš 3 najbližje in zahtevaš, da sta vsaj 2 iz istega razreda.
Takšno razvrščanje razdeli prostor značilnic $\mathbb{R}^n$ v $M$ neprekrivajočih se področij ($M$ je enako številu razredov). Odločitvena funkcija je v splošnem funkcija $n$ spremenljivk. Za vsak razred $C_i$ uvedemo svojo odločitveno funkcijo $\varphi_i$, pri čemer velja:
Neznan vzorec $x$ razvrstimo v tisti razred $C_i$, za katerega vrne odločitvena funkcija največjo vrednost. Ločilno mejo med razredoma $C_i$ in $C_j$ zapišemo kot:
Razvrščevalnik moramo naučiti $\binom{M}{2} = \dfrac{M(M-1)}{2}$ ločilnih mej!
$w = [w_1, \dots, w_n]$ je vektor koeficientov (uteži), $w_0$ pa prag. Ločilna meja:
Ločilne meje so v prostoru značilnic $\mathbb{R}^n$ dejansko $(n-1)$-razsežne hiperravnine:
Zgled za dvodimenzionalni prostor: iz $Ax_1 + Bx_2 = C$ dobimo $x_2 = -\frac{A}{B}x_1 + \frac{C}{B}$.
Učinkovitost naučenega razvrščevalnika ugotavljamo na osnovi vzorcev iz preizkusne (testne) množice $TM$, ki ima sorodne lastnosti kot učna množica. Učinkovitost ocenjujemo na osnovi števila napačno razvrščenih vzorcev.
Stopnja napačnega razvrščanja $P(x \in C_i, C_j)$ je verjetnost, da vzorec $x$ iz razreda $C_i$ napačno razvrstimo v razred $C_j$. Ne moremo je natančno izračunati, ampak jo iz $TM$ zgolj ocenimo:
kjer je $N_i^T$ število vseh vzorcev iz $C_i$ v $TM$, $n_i$ pa napačno razvrščeni vzorci iz $C_i$.
Postopek: iz celotne množice vzorcev izpustimo en vzorec za preizkušanje, vse preostale vzorce pa uporabimo za učenje razvrščevalnika.
Celotno učno množico najprej uporabimo za učenje, nato pa še za preizkus razvrščevalnika. (Optimistična ocena — razvrščevalnik je videl vse.)
Povprečje $N$ napak, kjer vsako napako izračunamo tako, da izpustimo en vzorec $x_i$ za preizkušanje, preostale pa za učenje.
kjer je $\hat{P}_e^{(x_i)} = 1$, če smo vzorec $x_i$ napačno razvrstili z razvrščevalnikom (naučenim brez vzorca $x_i$), sicer pa 0.
Prava vrednost napake leži med spodnjo in zgornjo mejo; z večanjem števila vzorcev v $UM$ se meji približujeta.
Ko izpustiš vzorec, se spremeni tipični predstavnik njegovega razreda — izračunati ga moraš znova, brez izpuščenega vzorca. Pri razredu z dvema vzorcema je novi predstavnik kar drugi vzorec. Če tega ne narediš, je rezultat vedno 0 % napake, kar je eden od napačnih odgovorov.
Korak 1: $z = \dfrac{1 - 10{,}43}{1 \cdot 5{,}68} = -1{,}66$.
Korak 2: $x = \dfrac{1}{1 + e^{-z}} = \dfrac{1}{1 + e^{1{,}66}} = \dfrac{1}{6{,}26} = \mathbf{0{,}160}$.
Odgovor a) je past za tiste, ki se ustavijo po prvem koraku. Odgovor b) je past za napačen predznak v eksponentu — pozor, $e^{-z}$ pri negativnem $z$ da $e^{+1{,}66}$.
Pravilo (k, l) = (3, 2): pogledamo $k = 3$ najbližje sosede in zahtevamo, da jih vsaj $l = 2$ pripada istemu razredu. Tu ima A dva, B enega → razvrstimo v A.
Odgovor a) bi bil pravilen, če bi bilo razmerje npr. 1 : 1 : 1 pri treh razredih ali če prag $l$ ne bi bil dosežen — zato vedno preštej.
Preizkusimo vse štiri izpuste (predstavnik razreda se vsakič preračuna brez izpuščenega vzorca):
$\hat{P}_e = 1/4 = \mathbf{25\ \%}$. Odgovor a) dobiš, če predstavnika po izpustu ne preračunaš.