6 UČENJE I STROJNO UČENJE
180
6 UČENJE I STROJNO UČENJE
Prva asocijacija na riječ učenje kod većine je ljudi ! školsko učenje. Školsko učenje ili edukacija
bavi se pomaganjem prihvata znanja, vještina, ponašanja, vrijednosti!U učenju razlikujemo dvije uloge
učenika ili entitet koji prihvaća znanje i učitelja koji pomaže u postupku učenja. Ipak, pojmom
učenje možemo obuhvatiti puno širi spektar značenja, od nesvjesnog učenja jedinki životinjskog svijeta
koje je bitno za preživljavanja do!cjeloživotnog učenje ljudi kao stila života. U svim tim slučajevima učenje
je prihvat novih znanja ili vještina.
Učenje se može odvijati svjesno i nesvjesno. Svjesno učenje događa se kada imamo namjeru
usvojiti neko novo znanje ili vještinu, te svjesno i aktivno!prikupljamo informacije koje vode prema tom
cilju. Ovaj proces može biti potpomognut prisustvom učitelja koji upravlja cijelim ovim postupkom.
Nesvjesno učenje događa se kroz interakciju s okolinom bez voljnog prikupljana i oblikovanja
informacija. Nesvjesno učenje je prisutno i kod primitivnih jedinki.
Teoriju učenja u početku su izučavali filozofi. Platon (427. 347. g. pr. n. e.) se prvi zapitao kako
ljudi uče. Ovaj je filozof dao odgovor u vidu teorije rekolekcije ili Platonove epistemologije. Prema
njegovoj teoriji sve naučene informacije su zapravo prisjećanje prijašnjeg iskustva.
Britanski filozof John Locke (1632. 1704.) ponudio je teoriju praznog stanja. On tvrdi!kako se
sva živa bića rađaju kao prazna ploča (tabula rasa), bez ikakvog znanja, koju onda popunjavaju
iskustvima.
6.1 Edukativna psihologija
Osim filozofije, učenjem se bavi i psihologija. Edukativna psihologija zaživjela je početkom 20.
stoljeća, te predložila nekoliko! teorija učenja.
6.1.1 Biheviorizam
Bihevioristički pristup učenju (engl. Behaviorism) utemeljio je John B. Watson (1878.-1958.).
Njegove smjernice prate B. F. Skinner, Ivan Pavlov i drugi. Bihevioristička teorija učenja! jedna je od
prvih teorija edukativne psihologije. Prema ovoj teoriji nova ponašanja ili promjene u ponašanju postižu
Strojno učenje danas je sigurno jedno od područja nebiološke inteligencije koje se
najbrže razvija, posebno u odnosu na rješavanja brojnih kompleksnih zadataka koji se
nisu mogli riješiti, bar ne na zadovoljavajući način. Sigurno je tome pridonio i razvoj
računala koja su sve brža, sposobna napraviti brojne numeričke operacije na kojima se
strojno učenje i zasniva. Nakon kratkog uvoda o učenju u ovom poglavlju dajemo pregled
osnovnih postupaka strojnog učenja.
6 UČENJE I STROJNO UČENJE
181
se formiranjem veza između stimulacija i odgovora. Učenik se promatra kao pasivan sudionik te se ne
analiziraju njegovi! interni procesi, već samo reakcije na podražaje. Učenje se postiže pozitivnim i
negativnim potkrepljivanjem, tj. kaznama i nagradama kojima se forsiraju željene reakcije na podražaje.
Glavna zamjerka biheviorizmu je ta da je učenik pasivan, a okolina aktivna.!Također, kazna i nagrada
nisu jedine motivacije učenja, već ljudi njeguju kompleksniji sustav vrijednosti koje ova teorija ne uzima
u obzir.
6.1.2 Kognitivizam
Kognitivna teorija učenja (engl. Cognitivism) zaživjela je 50-ih godina 20. stoljeća, kao reakcija
na biheviorizam koji ne promatra interne procese kod učenja. Ova teorija stavlja učenika u aktivnu ulogu
i kaže kako je učenje zapravo obrada informacija koja vodi k razumijevanju i zadržavanju naučenog.
Kognitivni konstruktivizam smatra da se nove kognitivne strukture!aktivno kreiraju i nadograđuju na
postojeće kognitivne strukture. Ovakvo objašnjenje procesa učenja vodi prema mogućnosti računalne
implementacije modela učenja u obliku umjetne inteligencije koja uči. Zamjerke ovoj teoriji su što
zanemaruje utjecaj okruženja (fizičkog, socijalnog, kulturnog). Također, učenje nije samo obrada
informacija već konstruiranje sadržaja.
6.1.3 Konstruktivizam
Konstruktivizam (engl. Constructivism) se javlja 80-ih godina 20. stolčjeća, a temelji se na
činjenici da učenje nije samo uspostava asocijativnih veza, kako tvrdi bihevioristička teorija, ili obrada
informacija, kako tvrdi kognitivna teorija,! već konstruiranje značenja i smisla. Ne naučimo samo ono što
pročitamo i čujemo već najvećim dijelom ono što iskusimo. Učenje je proaktivan proces gdje učenik nove
informacije interpretira i primjenjuje u vlastitu realnost.
6.1.4 Konektivizam
Konektivističku teoriju (engl. Connectivism) zovu još i teorija učenja za digitalno doba. Javlja
se u 21. stoljeću i objašnjava kako Internet, te velika i jednostavna dostupnost informacija oblikuju nove
paradigme učenja.
6.1.5 Računalna teorija učenja
Psihološke teorije učenje pokušavaju objasniti kroz ljudsko učenje. Od samih početaka
računarskih znanosti znanstvenici pokušavaju stvoriti računalnu tvorevinu koja će imati približne
mogućnosti kao i ljudske jedinke. Proces učenja pri tome nije iznimka. Računalna teorija učenja koja nam
je ovdje i zanimljiva razvila se kao posebno područje umjetne inteligencije koje se bavi analizom i
dizajnom algoritama strojnog učenja.
6.2 Strojno učenje
Strojno učenje (engl. Machine Learning) jedan je od pravaca umjetne inteligencije, te je ujedno
i najzastupljeniji u posljednje vrijeme, kako u znanosti tako i u svakodnevnom korištenju. Ideja strojnog
učenja jest postići da računala uče. Odavno znamo da su računala naprave koje lako pamte podatke.
Razvojem tehnologije medija pohrane i distribuirane pohrane omogućili smo računalima da pamte
podatke bez ograničenja količine, no pohrana velike količine podataka ne znači i usvajanje znanja ili
vještine. U okviru strojnog učenja želja nam je da računala koriste te podatke za nova znanja i nova
ponašanja. Strojno učenje bavi se idejom da računala sama stvaraju algoritme. U praksi, to se svodi na
uočavanja zakonitosti iz podataka. Strojno učenje producira algoritme koji na temelju pohranjenih,
dostupnih podataka generiraju hipoteze koristeći algoritme predviđanja. Postupak učenja iz podataka
zove se treniranje algoritma strojnog učenja.
Strojno učenje sadrži različite algoritme posuđene iz statistike, informacijske teorije,
matematičke optimizacije, teorije automatskog vođenja, teorije grafova, fizike, kognitivne znanosti,
6 UČENJE I STROJNO UČENJE
182
psihologije, objedinjene pod zajedničkim nazivom strojno učenje. Naziv je skovao Arthur Samuel (1901.
1990.), jedan od pionira računalnih igara i umjetne inteligencije. On je 1959. godine dao i prvu definiciju:
Strojno učenje je područje istraživanja u kojemu se računalu daje mogućnost učenja bez eksplicitnog
programiranja. Arthur Samuel bavio se izradom programa za igru Dame (engl. Checkers) u kojoj
program uči u interakciji s igračem.
Tom M. Mitchell (1951. ), američki znanstvenik, autor je knjige Machine Learningizdane
1998. godine. Njegova definicija strojnog učenja kaže: Kaže se da se računalni program uči iz iskustva E
u odnosu na neki zadatak T s nekom mjerom uspješnosti P, ako se njegov učinak na T, mjereno s P,
poboljšava s iskustvom E.
Algoritmi strojnog učenja imaju sposobnost uočavanja pravila (npr. algoritama i funkcija) iz
skupa podataka kao što prikazuje Slika 6-1. Algoritam strojnog učenja za ulazne podatke uzima skup
podataka za treniranje, a rezultat primjene algoritma strojnog učenja na ove podataka jest hipoteza.
Hipoteza je uočena zakonitost koja daje metodu kako na temelju novih podataka odrediti odgovor. Cilj
algoritma strojnog učenja je dati hipotezu koja se najbolje uklapa u skup podataka za treniranje. Što je
više podataka za treniranje, to je i ishod učenja bolji. Andrew Ng, profesor sa Stanforda koji predaje
strojno učenje, je kazao: Ponekad ne pobjeđuje onaj koji ima najbolji algoritam, već onaj koji ima najviše
podataka.
Slika 6-1. Ilustracija postupka strojnog učenja
Primjer skupa podataka za treniranje mogao bi biti popis različitih bolesti i njihovih simptoma.
Na taj bi se skup podataka mogao primijeniti neki od algoritama strojnog učenja da bi se dobila hipoteza.
Hipotezi se tada može proslijediti skup novih simptoma i kao odgovor dobila bi se bolest koja ih uzrokuje.
Razlog zašto se znanstvenici u zadnje vrijeme intenzivno bave razvojem algoritama strojnog
učenja razumljiv je. Velike količine podataka dostupne su na internetu, od generiranog sadržaja
društvenih mreža, podataka dobivenih sa senzora Interneta stvari (engl. IoT Internet of Things) i
satelitskih informacija, do zapisa rada računanih sustava (engl. Logs), zapisa aplikacija, dnevnika
rada itd. Svi ti podaci u sebi nose zanimljive informacije i znanja koje je potrebno otkriti, a ručno
pregledavanje je zamorno i skupo.
Algoritme strojnog učenja dijelimo na vrste prema nekoliko različitih podjela. Prema načinu
pripreme skupa podataka za obradu, algoritmi strojnog učenja najčešće se dijele na:
6 UČENJE I STROJNO UČENJE
183
nadzirano učenje (engl. Supervised Learning) i
nenadzirano učenje (engl. Unsupervised Learning).
Osnovna razlika između ova dva pristupa je u načinu pripreme skupa podataka za treniranje
algoritma. Kod nadziranog učenja, algoritam radi s označenim podacima. Daje mu se skup značajki (npr.
simptoma) i zaključaka (npr. bolesti koje uzrokuju te simptome). Na temelju tih zaključaka koje najčešće
zovemo oznake (engl. Labels), algoritam nauči kako označiti nove značajke, a da se ta oznaka najbolje
uklapa u uočene zakonitosti značajki ulaznog skupa. Kod nenadziranog učenja, podaci nad kojima se radi
učenje su neoznačeni. Ulaz u algoritam je skup neoznačenih značajki, a zadatak algoritma je pronaći
strukturu u tim podacima i donijeti vlastite zaključke. Iz ovog objašnjenja jasno je da je nenadzirano
učenje mnogo kompleksniji problem od nadziranog.
Slika 6-2. Ilustracija razlike ulaznih podataka za nadzirano i nenadzirano učenje
Naravno da algoritmi nadziranog učenja imaju lakši posao, ali je u posljednje vrijeme dosta veći
zahtjev za boljim i preciznijim algoritmima nenadziranog učenja. Lako dostupni podaci su uglavnom
neoznačeni. Skup podataka senzora ili zapisa aplikacije lako je dobaviti, ali označavanje podataka je skup
i zahtjevan posao. Kažemo da su podaci jeftini, ali su oznake skupe”.
Uz nadzirano i nenadzirano učenje, postoje još i hibridne tehnike polunadziranog učenja,
poput:
pojačano učenje (engl. Reinforcement Learning) kod kojeg se učenje temelji na nagradi i
kazni, te
davanje preporuka (engl. Recommender Systems) kod kojega sustav istovremeno uči na
primjer o proizvodima i kupcima te preporučuje kupcima proizvode koje preferiraju kupci
slični njima.
6.3 Nadzirano učenje
Kod nadziranog strojnog učenja algoritmu učenja trebamo na početku pripremiti skup
označenih podataka koji služi za treniranje algoritma. Označeni podaci koje zovemo oznake trebali bi
sadržavati pouzdane parove ulazno-izlaznih informacija za koje znamo da su istinite. Na primjer, kod
sustava medicinske dijagnostike to bi trebali biti parovi (simptomi, bolesti) na temelju kojih bismo
istrenirali algoritam kako bi tijekom rada mogao zaključiti koja bi bolest mogla biti vezana uz pojavu
određenih simptoma. Što je veći skup ulaznih podataka, to je algoritam bolje istreniran.
Postupcima nadziranog strojnog učenja možemo rješavati različite zadatke koje najčešće dijelimo
u dvije grupe na temelju toga hoće li izlazna vrijednost koja se predviđa biti kontinuirana ili diskretna.
Nazivamo ih zadacima:
6 UČENJE I STROJNO UČENJE
184
regresije (engl. Regression) koji predviđaju kontinuirane izlazne vrijednosti i
klasifikacije (engl. Classification) koji predviđaju diskretne izlazne vrijednosti.
Kod regresije hipoteza daje postupak izračuna kontinuirane izlazne vrijednosti za neki novi
ulazni podatak koji se najbolje uklapa u poznati skup podataka za treniranje. Kod klasifikacije hipoteza
daje postupak izračuna kojoj je grupi iz podataka za treniranje najsličniji novi ulazni podatak.
Nadzirano strojno učenje primjenu nalazi u brojnim područjima, na primjer u već spomenutoj
medicinskoj dijagnostici, predviđanju cijena proizvoda, predviđanju događanja, filtriranju neželjene
elektroničke pošte, prepoznavanju znakova (engl. Optical Character Recognition OCR) itd.
U nastavku ćemo prikazati nekoliko tipova regresije i klasifikacije, te načine njihovog rješavanja
značajnim postupkom strojnog učenja koji se zove spust gradijenta. Spust gradijenta je iterativni
optimizacijski algoritam prvog reda kojim se traži minimum funkcije koja će se u našem slučaju nazivati
funkcija cijene. Predložio ga je još 1847. godine francuski matematičar Augustin-Louis
Cauchy! (1789. 1857.), ali je značajnu primjenu dobio tek pojavom strojnog učenja koje se uvodi 60-ih
godina 20. stoljeća.
Posebno mjesto u nadziranom učenju imaju umjetne neuronske mreže koje u posljednje vrijeme
doživljavaju veliki značaj u rješavanju brojnih zadataka, posebno klasifikacije.
6.3.1 Linearna regresija s jednom varijablom
Linearna regresija s jednom varijablom je zadatak predviđanja kontinuirane vrijednosti na
temelju linearne funkcije uz promatranje samo jedne varijable. Pogledajmo najprije primjer s kojim ćemo
je ilustrirati.
Zadatak 6. Primjer linearne regresije
Linearna regresija između težine vozila i potrošnje goriva
88
. Ulazni podaci su 100 podataka
prikazanih na slici 6-3 koji povezuju težinu vozila u tonama i potrošnju goriva u l/100 km.
Slika 6.3 Potrošnja goriva u ovisnosti o težini vozila
88
Primjer i kod korišten kod ilustracije linearne regresije su prilagođeni podaci i kod prema
https://github.com/adeveloperdiary/MachineLearning/tree/master/LinearRegression/Univariate_using_Octave
6 UČENJE I STROJNO UČENJE
185
Na slici je moguće vrlo lako vizualno primijetiti trend potrošnje što je automobil teži, to više troši.
Osim rasipanja podataka pri kraju, mogli bismo i pretpostaviti da je ova ovisnost linearna. Cilj nam
je odrediti tu ovisnost, kako bismo, ako nam je poznata težina vozila, lako procijenili kolika bi mu
bila potrošnja.
Postupak je sljedeći: s x ćemo označiti varijablu o kojoj ovisi predviđanje (težina), a s y varijablu
koju predviđamo (potrošnja). Funkciju predviđanja kojom izražavamo ovisnost cijene o godini proizvodnje
zvat ćemo hipoteza. Hipoteza je algoritam kojeg kao rezultat daje postupak strojnog učenja. Budući
da je ideja napraviti linearno predviđanje, naša funkcija hipoteze imat će sljedeću formu:
!
!
"
#
$
%&
"
'&
#
#
(6-1)
Linearnu regresiju s jednom varijablom grafički možemo prikazati slikom 6-4.
Slika 6-4. Grafički prikaz linearne regresije s jednom varijablom
U formuli (6-1) θ
0
i θ
1
su parametri hipoteze. Cilj nam je parametre hipoteze podesiti tako da se
funkcija hipoteze najbolje uklapa u podatke koje imamo. Nastojimo da za godinu proizvodnje automobila
iz oglasa hipoteza predviđa vrijednosti cijene što bliže stvarnim cijenama iz oglasa. Zbog toga uvodimo
funkciju cijene (engl. Cost Function). Funkcija cijene je funkcija parametara hipoteze (θ
0
i θ
1
) i govori
nam koliko je hipoteza kojoj damo određenu vrijednost parametara udaljena od stvarnih vrijednosti u
skupu podataka. Vrijednost funkcije cijene za vrijednost parametara θ
0
i θ
1
možemo računati prema
formuli (6-2):
(
"
&
"
)&
#
$
%
#
$%
*
"!
!
+
#
&'(
,
-.
&'(
$
$
%
' )#
(6-2)
Ova formula kaže da je vrijednost funkcije cijene za fiksne parametre jednaka sumi kvadrata
udaljenosti vrijednosti hipoteze h
0
(x) i stvarnog podatka y iz skupa podataka, a m je broj podataka u
skupu podataka. Cilj nam je pronaći takvu kombinaciju parametara θ
0
i θ
1
za koje će funkcija cijene biti
minimalna. U našem primjeru, temeljem skupa podataka za treniranje, pronaći ćemo linearnu ovisnost
godine proizvodnje automobila i cijene, takvu da za podatke iz skupa za treniranje ukupna udaljenost
hipoteze i cijene bude minimalna.
Formalno napisano cilj postupka se iskazuje formulom (6-3):
&
"
)&
#
/012
*
!
+*
"
(
"
&
"
)&
#
$
3
(6-3)
Ograničimo se sada (ilustracije radi) na samo jedan parametar θ
1
, te zanemarimo θ
0
. Pogledajmo
kako se promjenom parametra θ
1
mijenja vrijednost funkcije cilja. Radi lakšeg praćenja koristit ćemo
hipotetske podatke prikazane tablicom 6.1, a našem primjeru vratit ćemo se kasnije.
6 UČENJE I STROJNO UČENJE
186
Tablica 6-1. Hipotetski podaci za ilustraciju traženja parametara linearne regresije
x
1
2
3
y
1
2
3
Tražimo hipotezu h(x) = θ
1
.
x. Ako pretpostavimo da je θ
1
= 0, hipoteza postaje: h(x) = 0.
Tablica 6-2. Izlazna varijabla i hipoteza za θ
1
= 0
x
1
2
3
y
1
2
3
h(X) za θ
1
=0
0
0
0
Vrijednost funkcije cijene za θ
1
= 0 je:
(
"
4
$
%
5
678
""
5-4
$
$
'
"
6-4
$
$
'
"
8-4
$
$
$
%
59
:
%6)88
Ako pretpostavimo da je θ
1
= 1, hipoteza postaje: h(x) = 1
.
x, a vrijednost funkcije cijene je J(1) =
0. Za θ
1
= 2 hipoteza je h(x)= 2
.
x, a vrijednost funkcije cijene je J(2) = 2,33. Prikažemo li grafički funkciju
cijene u ovisnosti o parametru θ
1
, dobit ćemo sliku 6-5.
Slika 6-5. Grafički prikaz funkcije cijene u ovisnosti o parametru θ
1
Slika 6-5 pokazuje da funkcija cijene ima minimum u vrijednosti θ
1
= 1 i upravo je taj parametar
najbolji kandidat za funkciju hipoteze u ovom jednostavnom primjeru.
Vratimo li se na hipotezu linearne funkcije s dva parametra, prikaz funkcije cilja u ovisnosti o
dva parametra (θ
0
i θ
1
) mogao bi izgledati kao na slici 6-6:
Slika 6-6. Funkcija cijene za dva parametra linearne hipoteze kod ujednačenih podataka
6 UČENJE I STROJNO UČENJE
187
Najbolji kandidat za hipotezu jest kombinacija parametara na dnupovršine ovakvog prikaza.
Problem je što vrijednost funkcije cijene neće uvijek biti ovako pravilna. Češće će prikaz funkcije cijene
izgledati puno složenije, s većim brojem minimuma i maksimuma, kao na primjer na slici 6-7.
Slika 6-7. Primjer prikaza funkcije cijene za dva parametra hipoteze
I u ovom slučaju bilo bi potrebno odabrati točku s kombinacijom parametara gdje je vrijednost
funkcije cijene minimalna (najniža). Osim globalnog minimuma, ovakva funkcija ima i nekoliko lokalnih
minimuma pa je pronalazak minimuma još više otežan.
Kod jednostavnog oblika funkcije cijene sa slike 6-6 zadatak linearne regresije možemo riješiti i
analitički, na primjer metodom najmanjeg kvadratnog odstupanja (engl. OLS Ordinary Least
Squares). Kod funkcije cijene prikazane slikom 6-7, teško je analitički odrediti minimum vrijednosti
funkcije, pa se zbog toga koriste iterativni postupci od kojih je posebno važan spust gradijenta.
6.3.2 Spust gradijenta
Spust gradijenta (engl. Gradient Descent) je postupak pronalaska lokalnog minimuma funkcije
kroz iterativni postupak kojim se kreće” po funkciji u smjeru najvećeg pada. Smjer pada funkcije
matematički se pronalazi pomoću derivacije funkcije. Postupak se sastoji od toga da se slučajno odabiru
početne vrijednosti parametara θ
0
i θ
1
te se zatim iterativno mijenjaju u smjeru pada funkcije cijene.
Formalno, spust gradijenta možemo opisati formulom 6-4:
ponovi do konvergencije {
33333333&
,
3%&
,
-;
-
-*
#
3("&
"
)&
#
$
(6-4)
}
gdje je α parametar brzine učenja (engl. Learning Componet Rate), a derivacijski član
J/
θ
j
je gradijentna komponenta (engl. Gradient Component).
Kod linearne regresije s jednom varijablom koja ima dva parametra θ
0
i θ
1
algoritam spusta
gradijenta može se opisati formulom 6-5:
ponovi do konvergencije {
&
"
3%&
"
-
.
%
3
*
"!
*
+
#
&
'
(
-.
&
'
(
,
%
' )#
&
#
3%&
#
-
.
%
3
*
"!
*
"#
&
'
(
-.
&
'
(
$<3#
&
'
(
%
' )#
(6-5)
}
6 UČENJE I STROJNO UČENJE
188
Za parametre θ
0
i θ
1
odaberu se proizvoljne početne vrijednosti, koje se zatim iterativnim
postupkom mijenjaju. Vrijednost parametra se u svakoj iteraciji ažurira u smjeru pada vrijednosti
funkcije cijene. Izbor parametra brzine učenja α je posebno kritičan. Premala vrijednost parametra α
usporit će konvergenciju jer će se u svakom koraku iteracije napraviti mali korak. S druge pak strane,
prevelika vrijednost parametra α može rezultirati prevelikim koracima te se optimalna vrijednost
parametara θ
0
i θ
1
može preskočiti. Parametar m u nazivniku formule 6-5 predstavlja ukupan broj
podataka skupa za treniranje.
Suma se računa tako da se za svaki podatak iz skupa za treniranje izračuna razlika hipoteze za
trenutne parametre θ
0
i θ
1
, oduzme se stvarna vrijednost podatka te se sumiraju svi podaci. Pseudokod
ovog postupka bio bi sljedeći:
Algoritam 6-1. Pseudokod postupka za spust gradijenta
// inicijalizacija na početne vrijednosti
theta0 = 0;
theta1 = 0;
// iteracija
for (numiter) {
// inicijalizacija sume na nulu
delta0 = 0; //suma za ažuriranje parametra theta0
delta1 = 0; //suma za ažuriranje parametra theta1
// za svaki podatak iz skupa za treniranje
for (i = 1 to m){
delta0 += (theta0 + theta1*x[i] y[i]);
delta1 += (theta0 + theta1*x[i] y[i])*x[i]
}
// update parametara na nove vrijednosti
theta0 = theta0 - alpha * (1/m) * delta0;
theta1 = theta1 - alpha * (1/m) * delta1
}
Tablični zapis podataka za treniranje pogodan je i za matrični prikaz. Uvodimo vektore x i y.
Vektor x sadržavat će težine automobila, a vektor y potrošnju goriva.
Zbog elegantnijeg matričnog zapisa, vektoru x ćemo dodati još jedan stupac na početku u kojemu
će biti samo jedinice. Ovako dobivenu matricu označit ćemo s X.
3=%
>
5 #
#
5 #
$
? ?
5 #
%
@
Tražene parametre također ćemo predstaviti pomoću vektora θ:
A%
B
&
"
&
#
C
Sada hipotezu možemo u matričnom obliku pisati:
D
*
"
#
$
%=<A
(6-6)
Matričnim množenjem matrica X i θ dobijemo matricu vrijednosti hipoteze za svaki redak skupa
za treniranje. Oduzimanjem matrice y dobit ćemo vrijednosti cijene svakog podatka skupa za treniranje
za trenutne vrijednosti parametara θ
0
i θ
1
. Kada vektor transponiramo u matricu jednog retka i m stupaca
6 UČENJE I STROJNO UČENJE
189
i pomnožimo je s vektorom x, dobit ćemo vektor s vrijednostima derivacija za parametre θ
0
i θ
1
, te novi
vektor θ postupkom spusta gradijenta u matričnoj formi računamo jednadžbom 6-7:
A%A-"EFG$<"
"
3=<A-H
$
/
<I$
(6-7)
Vratimo se sada na naš primjer i sliku 6-3 i primijenimo algoritam spusta gradijenta. Krećemo
od nultih početnih vrijednosti θ
0
= θ
1
=0. Tablica 6-3 prikazuje nekoliko prvih koraka za parametar brzine
učenja α = 0,1 koristeći Octave
89
:
Tablica 6-3. Nekoliko prvih koraka traženja parametara linearne regresije metodom spusta gradijenta za
podatke sa slike 6-3 za parametar brzine učenja α=0,1.
Korak
θ
0
θ
1
J(θ
0
, θ
1
)
1
1,400816
2,283847
106,752304
2
2,316807
3,792360
47,219340
3
2,913491
4,790153
21,387389
10
3,904009
6,674050
1,616149
100
2,630459
7,612992
1,274125
1000
0,600699
8,882528
1,110289
Analitička metoda najmanjeg kvadratnog odstupanja
90
daje točno analitičko rješenje θ
0-ANALITICKI
= 0,587421 i θ
1-ANALITICKI
=8,890934 pa vidimo da se nakon 1000 iteracija spust gradijenta dosta približio
analitičkom rješenju. Slika 6-8 prikazuje točnu jednadžbu linearne regresije (crno) i najbolju hipotezu
(crveno) nakon 100 iteracija i nakon 1000 iteracija, te ovisnost funkcije cijene o broju iteracija.
89
Octave je program za matematičke proračune https://www.gnu.org/software/octave/ .
90
Korišten je online kalkulator https://planetcalc.com/5992/
6 UČENJE I STROJNO UČENJE
190
Slika 6-8. Linearna regresija kod predviđanja potrošnje goriva za točno (analitičko) rješenje (crno) i
rješenje dobiveno spustom gradijenta nakon 100 iteracija (gore) i 1000 iteracija (sredina) i ovisnost
funkcije cijene o broju iteracija (dolje) za prvih 100 iteracija.
U ovom primjeru funkcija cijene u prvom dijelu brzo konvergira, ali zato u drugom dijelu
konvergira sporo, pa veći broj iteracija i nema smisla. Na slici su ucrtane i tri zelene točke za predviđanje
potrošnje goriva ako je težina vozila 0,59 tona, 1,63 tona i 2,49 tona.
Spust gradijenta opisan u ovom poglavlju je temeljni postupak. Razvojem strojnog učenja
predložene su i njegove brojne modifikacije koje su u nekim elementima bolje, primjerice algoritmi
Momentum (1964.), AdaGrad (2011.), RMSprop (2102.), AdaDelta (2012.), Nesterov (2013.), Adam (2014.),
6 UČENJE I STROJNO UČENJE
191
AdaMax (2015.), Nadam (2015.), AMSGrad (2018.)
91
. Modifikacije se od osnovnog algoritma razlikuju
uglavnom po modifikaciji parametra brzine učenja i/ili modifikaciji gradijentne komponente.
6.3.3 Linearna regresija s više varijabli
Svi znamo da cijene rabljenih automobila ne ovise samo i jedino o godini proizvodnje. Osim godine
proizvodnje, cijeli je niz faktora koji utječu na konačnu cijenu automobila, poput proizvođača i modela,
snage motora, broja prijeđenih kilometara itd. Faktore koji utječu na konačnu cijenu nazvat ćemo
značajke (engl. Features). Broj značajki koje ćemo uzeti u obzir označit ćemo s n. Kod linearne regresije
s jednom varijablom broj značajki koji je uzet u obzir bio je n = 1.
Ako predviđamo kontinuirane vrijednosti linearnom hipotezom temeljem više vrijednosti, radimo
linearnu regresiju s više varijabli (engl. MVLR Multi Variable Linear Regresson ili samo Multiple
Linear Regression) kod koje hipoteza glasi:
!
!
"
#
#
)#
$
)?)#
0
$
%&
"
'&
#
#
#
'&
$
#
$
'
3
<<<
3
'&
0
#
0
(6-8)
Zadatak 7. Primjer linearne regresije s više varijabli
Linearna regresija s više varijabli kod predviđanja cijene rabljenih automobila. Za potrebe primjera
prikupljeni su podaci o cijenama rabljenih automobila s mrežne stranice za oglašavanje
www.njuskalo.hr. Uzeti su oglasi u kojima su oglašavane prodaje rabljenih automobila te u kojima
su navedene cijene i dodatne informacije o kojima će u nastavku biti više govora. Dio prikupljenih
podataka za treniranje prikazan je u tablici 6-6. Imamo ukupno 6 različitih značajki (n = 6).
Tablične podatke također možemo prikazati matrično. Umjesto vektora x koji je sadržavao samo
jednu varijablu sada imamo matricu s n stupaca, pa matrica X koja se kod linearne regresije s
jednom varijablom sastojala od dva stupca stupca jedinica i stupca s vrijednostima značajki, kod
linearne regresije s više varijabli postaje matrica s n+1 stupcem stupac jedinica i po jedan stupac
za svaku od n značajki.
Neke značajke koje su nam bitne kod određivanja cijene nemaju numeričke vrijednosti, poput
marke automobila ili boje. Kako se algoritam oslanja na numeričke proračune, potrebno ih je na
neki način predstaviti (kodirati) brojevnim vrijednostima kako bi ih se moglo uzeti u obzir u
proračunu. Tako ćemo npr. bijelu boju označiti brojem 1, sivu brojem 2, crnu brojem 3 itd. Sada
nam boja kao značajka može biti navedena u matrici značajki X.
Drugi način tretiranja nenumeričkih podataka s konačnim brojem nominalnih vrijednosti je one-
hot encodingpostupak. Za svaku vrijednost koju podatak može poprimiti uvodi se novi stupac kao
nova značajka. Za svaki uzorak vrijednost samo jedne od grupe značajki je 1, i to za onu značajku
koja odgovara vrijednosti, dok je za ostale vrijednost 0. Primjer ovakvog načina kodiranja za boju
automobila za neke od automobila iz tablice 6-6 prikazan je u tablici 6-7.
Postupak proračuna parametara θ
0
, θ
1
, ... , θ
n
ostaje isti prema jednadžbi 6-4, odnosno u matričnoj
formi jednadžbi 6-7. U našem primjeru pogledat ćemo što će linearna regresija dati ako nas zanima
ovisnost cijene o godini (x
1
), prijeđenim kilometrima (x
2
) i broju vrata (x
3
). Rezultat je
92
:
!
!
"
#
#
)#
$
)?)#
0
$
%-558J:444'K:JJ<#
#
-4)49L:K<3#
$
':6KK<3#
1
Zanimljivo je pogledati koje bi cijene automobila, za podatke koje smo koristili, dala ova jednadžba
linearne regresije. Najveće odstupanje je naravno za podatke koji su najudaljeniji od pravca
linearne regresije. Na primjer, za Mercedes E-klase 350 4MATIC cijena u oglasu je bila 144986 kn.
Jednadžba linearne regresije s jednom varijablom daje 56032 kn, a jednadžba linearne regresije s
91
Više detalja o ovim algoritmima može se pronaći npr. na
https://towardsdatascience.com/10-gradient-descent-optimisation-algorithms-86989510b5e9
92
Korišten je on-line kalkulator https://home.ubalt.edu/ntsbarsh/Business-stat/otherapplets/MultRgression.htm
6 UČENJE I STROJNO UČENJE
192
više varijabli daje 62840 kn. Taj je automobil imao mali broj prijeđenih kilometara, pa je cijena
zbog toga i viša.
Tablica 6-6. Primjer podataka prodaje polovnih vozila
Tablica 6-7. Primjer kodiranja boje automobila metodom one-hot encoding
U oba ova slučaja pretpostavili smo linearnu ovisnost značajki, ali to u praksi nije uvijek slučaj.
Ako sve značajke nisu linearno ovisne jedna o drugoj, treba primijeniti druge načine regresije, na primjer
polinomalnu regresiju.
6.3.4 Polinomalna regresija
Polinomalna regresija (engl. Polynomial Regression) daje hipotezu u formi polinoma višeg
stupnja (npr. 2., 3., 4. stupnja). Što je polinom većeg stupnja, to je funkcija hipoteze kompleksnija i moguće
6 UČENJE I STROJNO UČENJE
193
je bolje približavanje funkcije hipoteze podacima iz skupa za treniranje. Na slici 6-9 prikazani su različiti
skupovi podataka i njihova aproksimacija funkcijom linearne regresije.
Lako se vizualno može zaključiti da se za x
1
, y
1
i x
3
, y
3
može pretpostaviti da su linearno ovisne
jedna o drugoj, ali za x
2
, y
2
, iako možemo temeljem podataka izračunati parametre linearne regresije, ta
hipoteza nikad neće dobro raditi na novim podacima. Bilo bi bolje pretpostaviti neku polinomalnu
hipotezu koja u pojedinim značajkama ovisi o zakonitostima koje su kompleksnije od linearnih. Dobro je
što se prethodno opisani algoritam linearne regresije može lako prilagoditi i polinomalnoj regresiji
jednostavnim proširenjem broja značajki i to za koliko smo pretpostavili da će biti stupanj polinoma.
Ako imamo skup značajki x
1
i x
2
, i želimo donijeti hipotezu u formi polinoma drugog stupnja, tada
ta proširena hipoteza glasi:
A
(
#
2+
#
3
)
= &
4
'&
2
#
2
'&
3
#
2
3
'&
5
#
3
'&
6
#
3
3
(6-9)
Slika 6-9. Različiti skupovi podataka i njihova aproksimacija funkcijom linearne regresije
Matematički jednostavno proširujemo skup značajki na x1, x12, x2 i x22, pa nam matrica X sada
ima stupac jedinica i još četiri stupca značajki, a vektor θ ima 5 redova. Daljnji postupak treniranja
hipoteze i optimizacije parametara funkcije hipoteze postupkom spusta gradijenta ostaje identičan.
6.3.5 Pretreniranje i regularizacija
Što je stupanj polinoma veći, to je oblik funkcije hipoteze lakše uklopiti u dostupne podatke.
Drugim riječima, kompleksnijom funkcijom hipoteze dobit ćemo hipotezu s manjom vrijednošću funkcije
cijene. No ovisnosti su nekada jednostavnije nego što izgledaju, pa se može dogoditi da se korištenjem
kompleksnije funkcije samo pretjerano zamaramo funkcijom cijene, dok bi jednostavnije hipoteze bolje
opisale model pojave koju podaci opisuju.
Pretjerana pažnja na funkciju cijene izračunate na skupu podataka za treniranje može dovesti do
tzv. pretreniranja (engl. Overfitting). Pretreniranje je pretjerano namještanje funkcije hipoteze da se
što bolje uklopi u skup podataka za treniranje. Je li došlo do pretreniranja, možemo provjeriti na način
da testiramo kako radi hipoteza za neke nove podatke koji se nisu nalazili u skupu podataka za treniranje.
Kako nemamo uvijek dostupne nove podatke, u praksi se skup dostupnih podataka obično podijeli na
podskup podataka za treniranje i podskup za testiranje, obično u omjeru 80:20. Hipoteza se trenira na
6 UČENJE I STROJNO UČENJE
194
skupu za treniranje, te se provjeri vrijednost funkcije cijene na skupu podataka za testiranje. Ako
hipoteza daje malu funkciju cijene za podatke za treniranje, a lošu (veliku) cijenu na skupu za testiranje,
došlo je do pretreniranja. U tom slučaju potrebno je izabrati jednostavniju formu funkcije hipoteze,
dovoljno jednostavnu da nema pretreniranja, a opet dovoljno složenu da dobro opisuje dani skup
podataka. Princip Occamove britve
93
(engl. Occam's Razor) kaže Ako dva rješenja daju iste rezultate,
uvijek treba izabrati ono jednostavnije. Konkretna primjena Occamove britve kod regresije naziva se
regularizacija. Regularizacija je uvođenje dodatnog izraza u funkciju cijene kojim se dodatno penalizira
korištenje presložene forme funkcije hipoteze. Funkcija cijene dobiva sada oblik prikazan formulom 6-10:
(
"
A
$
%
#
$%
M
*
"!
!
+
#
&'(
,
-.
&'(
$
$
%
' )#
'N<
*
&
,
$
0
,)#
O (6-10)
Osim sume kvadrata udaljenosti hipoteze i stvarne vrijednosti, cijena se uvećava i za sumu
kvadrata parametara hipoteze čime se postiže uvećanje cijene za veće vrijednosti parametra hipoteze.
Dva su načina minimizacije ovakve funkcije cijene:
smanjenjem udaljenosti vrijednosti hipoteze za dane podatke od stvarnih vrijednosti
podešavanjem vrijednosti parametara na podatke iz skupa za treniranje, i
smanjenjem ukupne sume kvadrata parametara hipoteze korištenjem jednostavnije funkcije
hipoteze.
Minimizacija ovakve funkcije cijene postiže se balansiranjem između ova dva dijela odabirom
takvih parametara da je hipoteza dovoljno bliska podacima iz skupa za treniranje, a istovremeno i
dovoljno jednostavna.
6.3.6 Klasifikacija logističkom regresijom
Logistička regresija (engl. Logistic Regression) je postupak klasifikacije korištenjem ideja
linearne regresije. Problem klasifikacije se javlja kada imamo diskretne vrijednosti uzoraka koje
smještamo u neku od klasa. Klasifikacija je predviđanje kojoj klasi uzorak pripada. Primjena ima puno,
na primjer u klasifikaciji je li neka elektronička pošta smeće (engl. Spam) (y=1) ili nije (y=0), je li student
na temelju rješavanja m broja zadataka prošao ispit (y=1) ili nije (y=0), je li neki tumor na temelju
provedenih testova maligan (y=1) ili nije (y=0) itd.
Zadatak 8. Primjer linearne regresije s više varijabli
Za primjer ćemo uzeti predviđanje je li student prošao ispit na temelju rezultata dvaju testova (Test
1 i Test 2). Na slici 6-10 prikazani su prikupljeni podaci skupa za treniranje
94
.
Svaki podatak predstavlja jednu točku određenu s koordinatama rezultata Testa 1 i Testa 2, a oblik
oznake označava je li student prošao ispit (križić) ili nije (kružić).
93
Princip Occamove britve pripisuje se fratru Williamu Occamu (1287. 1347.) i koristi se kao princip kod
rješavanja problema. Ako više postupaka daje isti rezultat, onda uvijek treba uzeti najjednostavniji od njih.
94
Primjer je dorađen prema ideji s
http://openclassroom.stanford.edu/MainFolder/DocumentPage.php?course=MachineLearning&doc=exercises/ex4/ex
4.html
6 UČENJE I STROJNO UČENJE
195
Slika 6-10. Ulazni podaci logističke regresije na osima je postotak postignut na dva testa (Test 1 i
Test 2), a oblik oznake kaže je li student prošao ispit ili nije
U ovom primjeru imamo dvije značajke, a u općem slučaju može ih biti m. Konačna odluka je
binarna i nju donosi klasifikator na temelju ulaznih podataka. Kod logističke regresije hipoteza nije
linearna kombinaciju značajki, već nelinearna funkcija linearne kombinacije značajki
!
!
"
I
$
%P"A
7
I$
, a
kao funkcija najčešće se koristi Sigmoidna funkcija definirana jednadžbom (6-11) i prikazana slikom 6-
11:
Slika 6-11. Sigmoidna funkcija
"
(
1
)
=
#
#$%
8!
7
9
(6-11)
gdje je
A
7
I
linearna kombinacija značajki:
A
7
I%&
"
'&
#
#
#
'&
$
#
$
'3<<<'&
%
#
%
%&
"
'
*
&
,
#
,
%
,)#
(6-12)
Sigmoidna funkcija daje vrijednosti od 0,5 do 1 za ulazne vrijednosti veće od 0, a vrijednosti
između 0 i 0,5 za ulazne vrijednosti manje od 0. Važno je naglasiti da za velike ulazne vrijednosti
sigmoidna funkcija ne daje znatno povećane izlazne vrijednosti kao linearna funkcija, već se izlazne
vrijednosti asimptotski približavaju vrijednosti 1. Ako linearna kombinacija ulaznih značajki
A
7
I
rezultira vrijednostima većima od 0, sigmoidna funkcija daje vrijednost h
θ
(x) veću od 0,5, a za ulazne
6 UČENJE I STROJNO UČENJE
196
vrijednosti za koje je
A
7
I
negativan (manji od 0) sigmoidna funkcija daje vrijednost manju od 0,5. Nama
na izlazu treba binarna odluka pripadanja (1) ili nepripadanja (0), pa iza sigmoidne funkcije trebamo
staviti klasifikator koji za
!
!
"#$Q4)K
daje 1 (pripadanje klasi 1), a za vrijednosti
!
!
"
#
$
R4)K
daje 0
(pripadanje klasi 0).Grafički prikaz logističke regresije u dvije klase na temelju dviju značajki prikazuje
slika 6-12.
Slika 6-12. Grafički prikaz logističke regresije u dvije klase
Kako interpretirati ovako definiranu funkciju hipoteze? Uvodimo novi pojam koji se zove granica
odluke (engl. Decision Boundary).
Granica odluke
Pogledajmo na primjer podatke s dvije značajke na temelju kojih ulazne podatke klasificiramo u
dvije klase (slika 6-10). Pitanje je možemo li postaviti jasnu granicu između skupa uzoraka prošaoi
nije prošao. Ako bismo granicu mogli predstaviti formulom jednadžbe pravca, tada bi nju definirao izraz
A
7
I%4
, odnosno u slučaju kod kojeg imamo dvije značajke
&
"
'&
#
<#
#
'&
$
<#
$
%4
. Kod sigmoidne
funkcije kombinacije značajki x
1
i x
2
za koje je ova linearna kombinacija veća od 0 u koordinatnom sustavu
prikazuju se točkama iznad pravca. Za takve vrijednosti hipoteza će predvidjeti pripadnost klasi 1.
Kombinacije za koje linearna kombinacija ima vrijednosti manje od 0 nalaze se ispod pravca i hipoteza
predviđa pripadanje klasi 0. Zbog toga se linija predstavljena izrazom
A
7
I%4
naziva granica odluke
za logističku regresiju. Na Slici 6-13 prikazana je granica odluke za primjer prolaznosti ispita sa Slike 6-
10 dobivena programskom bibliotekom Octave.
Slika 6-13. Granica odluke za ulazne podatke prolaznosti na temelju rezultata dvaju testova.
6 UČENJE I STROJNO UČENJE
197
Pitanje je kako smo došli do ove jednadžbe pravca. Osnovni je problem, kao i u prethodnim
slučajevima, odrediti vektor težina θ. Na svu sreću to je ovdje moguće napraviti algoritmom spusta
gradijenta uz određene modifikacije funkcije cijene.
Funkcija cijene
Funkcija cijene hipoteze logističke regresije mora biti izražena drugačije nego kod linearne
regresije. Greška predviđanja pojedinog podatka je 0 ili 1, ovisno o tome je li ispravno ili neispravno
hipotezom predviđeno pripadanje klasi 1 i klasi 0.
Za jedan podatak matematički izraz za funkciju cijene logističke regresije koju smo označili
funkcijom Cost() je:
STUV
"
!
!
"
#
$
).
$
%
W
-XTP
+
!
*
"
#
$
,
)
-XTP
+
5-!
*
"
#
$
,
3YZ3.%5
)YZ3.%4
333
(6-13)
Kada sumiramo po svim podacima, dobije se funkcija cijene hipoteze za određenu kombinaciju
parametara θ:
3(
"
A
$
%3
5
0
[M
.
&
'
(
<STUV
#
+
!
!
+
#
&
'
(
,
).
&
'
(
,
'
+
5-.
&
'
(
,
<3STUV
#
+
!
!
+
#
&
'
(
,
).
&
'
(
,O
%
' )#
%
3
%3-
#
%
M
*
".
&
'
(
XTP!
!
+
#
&
'
(
,
'"5-.
&
'
(
$XTP3"5-!
!
"#
&
'
(
$$
%
' )#
3
O (6-14)
Ovo možemo interpretirati na način da želimo maksimizirati vjerojatnost da se slučajno odabrani
uzorak pravilno klasificira, što se uobičajeno naziva maksimalna procjena vjerojatnosti (engl.
Maximum Likelihood Estimation). Na ovu funkciju cijene možemo primijeniti i regularizaciju (poglavlje
6.3.5).
Spust gradijenta za logističku regresiju
Algoritam za spust gradijenta kod ovako postavljene funkcije cijene ostaje isti kao i za linearnu
regresiju. Tražimo min
θ
J(θ) na način da se u svakoj iteraciji parametri mijenjaju u smjeru pada funkcije
cijene:
ponovi do konvergencije {
333333333333333333333333333333333&
,
3%&
,
-
.
%
3
*
"!
*
"#
&
'
(
-.
&
'
(
$<3#
&
'
(
%
' )#
(6-15)
}
što je u biti ista jednadžba kao kod spusta gradijenta linearne regresije.
U našem primjeru sa slike 6-12 konačne vrijednosti vektora težina θ su θ
0
=-44,26458, θ
1
=0,45777,
i θ
2
=0,38577.
Logistička regresija u više klasa
Opisani algoritam logističke regresije koristan je za tzv. binarnu klasifikaciju kod koje radimo
klasifikaciju u dvije klase, pa izlaz hipoteze uzima vrijednosti iz dvočlanog! skupa {0,1}. Ako podatke
trebamo smjestiti u više klasa, algoritam se treba tome prilagoditi. Jedan od načina prilagodbe je metoda
jedan protiv svih(engl. One vs. All ili One vs. Rest) koju prikazuje slika 6-13. Ova se metoda temelji
na treniranju više klasifikatora, po jedan za svaku klasu.
Npr. ako imamo 3 klase, postupak logističke regresije provest ćemo 3 puta:
u prvom prolasku, podaci klase 1 imat će vrijednost 1, a klase 2 i 3 vrijednost 0, pa dobijemo
granicu odluke između klase 1 i ostalih dviju
6 UČENJE I STROJNO UČENJE
198
u drugom prolasku, podaci klase 2 imat će vrijednost 1, a klase 1 i 3 vrijednost 0, pa dobijemo
granicu odluke između klase 2 i ostalih dviju
u trećem prolasku podaci klase 3 imat će vrijednost 1, a klase 1 i 2 vrijednost 0, pa dobijemo
granicu odluke između klase 3 i ostalih dviju.
Rezultat su tri funkcije hipoteze koje daju vrijednost sigmoidne funkcije između 0 i 1. U ovom
slučaju nema smisla određivati binarni izlaz kao kod klasifikacije u dvije klase koristeći granicu na
vrijednosti 0,5. Izlazna vrijednost sigmoidne funkcije h(x) u ovoj situaciji može imati smisao vjerojatnosti
da podatak pripada klasi za koju je hipoteza istrenirana.
Slika 6-14. Ilustracija algoritma jedan protiv svih
Za slučaj m klasa to možemo iskazati izrazom:
!
!
&
'
(
"
I
$
%\
"
3.%1
]
I3^3A
$
3YZ31%5)6)?)0
(6-16)
Odluka se donosi na temelju ove vjerojatnosti, odabirom one klase čija odgovarajuća hipoteza ima
najveću vrijednost. To znači da kod logističke regresije u više klasa na izlazu nemamo binarni
kvantifikator, već komparator.
Pogledajmo primjer za situaciju sa slike 6-14. Pretpostavimo da smo za jedan konkretni uzorak x
=(x
1
, x
2
) dobili u tri prolaska sljedeće:
!
!
&
#
(
"
I
$
%\
"
3.%5
]
I3^3A
$
%4):
!
!
&
$
(
"
I
$
%\
"
3.%6
]
I3^3A
$
%4)93
!
!
&
1
(
"
I
$
%\
"
3.%8
]
I3^3A
$
%4)83
Zaključujemo da ćemo taj uzorak pridijeliti klasi 1 zato što u prvom prolasku hipoteza ima najveću
vrijednost 0,6.
6 UČENJE I STROJNO UČENJE
199
6.3.7 Stroj s potpornim vektorima
Stroj s potpornim vektorima (engl. SVM Support Vector Machine) je sličan logističkoj
regresiji i također se koristi kod klasifikacije u linearno odvojive klase binarnom klasifikacijom. Ideja je
pronaći takvu granicu odluke koja ima najveću udaljenost od najbližih uzoraka koji pripadaju pojedinim
klasama. Razliku između standardne granice odluka i stroja s potpornim vektorima u slučaju dviju
značajki x
1
i x
2
prikazuje slika 6-15.
Slika 6-15. Razlika između standardnih linearnih granica odluke (lijevo) i granica odluke stroja s
potpornim vektorima (desno). Kod logističke regresije traži se pravac koji maksimizira vjerojatnost da se
slučajno odabrani uzorak pravilno klasificira, a kod stroja s potpornim vektorima pravac koji ima
najveću marginu razdvajanja
Kod stroja s potpornim vektorima traži se takva granica odluke koja ima najveću marginu
razdvajanja. Uzorci koji se nalaze najbliže margini razdvajanja zovu se potporni vektori.
Kod logističke regresije nastoji se maksimizirati vjerojatnost da se slučajno odabrani uzorak
pravilno klasificira. Što je uzorak dalje od granice odluke, to je funkcija cijene bolja, a na granicu odluke
utječu svi uzorci. Kod stroja s potpornim vektorima nastoji se maksimizirati margina razdvajanja, pa su
važni jedino uzorci najbliži margini razdvajanja (potporni vektori). Svaki od ova dva postupka
klasifikacije ima svoje prednosti i nedostatke. Stroj s potpornim vektorima je nešto manje osjetljiv na
uzorke koji upadaju u suprotne klase (tzv. outliers), a iskustva kažu da daje i bolje rezultate ako imamo
malo značajki (n), a velik broj uzoraka za treniranje (m).
Ako se uzorci mogu idealno klasificirati (klase su linearno odvojive), moguće je povući pravce
paralelne s granicom odluke na kojima će ležati potporni vektori. U tom linearnom slučaju funkcija cijene
stroja s potpornim vektorima definira se izrazom:
STUV
"
!
!
"
#
$
).
$
%
W
0Z#
+
4)5-!
*
"
#
$
,
)YZ3.%5
0Z#
+
4)5'!
*
"
#
$
,
)YZ3.%4
333
(6-17)
Kada sumiramo po svim podacima, dobije se funkcija cijene hipoteze za određenu kombinaciju
parametara θ:
3(
"
A
$
%3
5
0
[
_
.
&
'
(
<STUV
#
+
!
!
+
#
&
'
(
,
).
&
'
(
,
'
+
5-.
&
'
(
,
<3STUV
#
+
!
!
+
#
&
'
(
,
).
&
'
(
,
`
%
' )#
%
3
%-
#
%
a
*
b
.
&
'
(
<0Z#
_
4)5-!
!
+
#
&
'
(
,
`
'"5-.
&
'
(
$<0Z#
_
4)5'!
!
+
#
&
'
(
,
`
c
%
' )#
3
d (6-18)
6 UČENJE I STROJNO UČENJE
200
Lako je uočiti da postoji velika sličnost s funkcijom cijene logističke regresije opisane
jednadžbama (6-13) i (6-14), s tim da kod stroja s potpornim vektorima maksimiziramo marginu
razdvajanja. Kao i kod logističke regresije na ovu funkciju cijene možemo primijeniti i regularizaciju
(poglavlje 6.3.5).
Ostaje nam još za pronaći takvu kombinaciju parametara θ koji minimiziraju ovu funkciju cijene
min
θ
J(θ). Jedan od postupaka je svakako i spust gradijenta s tim da se obično koristi stohastički spust
gradijenta (engl. Stohastic Gradient Descent) ili stohastički spust sub-gradijenta (engl. Stohastic
Sub-Gradient Descent). Za više detalja čitatelje upućujemo na dodatnu literaturu.
Osim linearnog stroja s potpornim vektorima postoji i nelinearni koji se koristi u slučajevima
kada se ne postoji linearna odvojivost klasa. Od linearnog se razlikuje po tome što se uvodi tzv. funkcija
kernela (engl. Kernel Function).
6.3.8 Umjetne neuronske mreže i duboko učenje
Duboko učenje (engl. Deep Learning) u posljednje vrijeme budi interes javnosti i pokazuje
izvrsne rezultate u područjima poput računalnog vida, obrade prirodnog jezika, prepoznavanja govora,
igranja igara i sl. Duboko učenje oslanja se na ideju umjetnih neuronskih mreža (engl. ANN
Artificial Neural Networks) koje oponašaju rad biološkog neuronskog (živčanog) sustava. Umjetne
neuronske mreže uveli su 1943. godine neuroznanstvenik Warren S. McCulloch i logičar Walter Pitts
95
,
a popularnost im raste nakon što je 1949. godine Donald Hebb postavio temeljni zakon učenja neurona
poznat kao Hebbovo pravilo koje se kratko opisuje rečenicom: Neuroni koji se zajedno aktiviraju se i
povezuju. Prava primjena umjetnih neuronskih mrež omogućena je tek razvojem računala, dostupnošću
velikih količina podataka i novih topologija mreža koje su omogućile stvaranje kompleksnijih mrežnih
struktura.
Umjetni neuron (perceptron)
Istraživanjem neuronskog sustava bioloških organizama bave se neuroznanstvenici koji su otkrili
da se neuronski sustav sastoji od međusobno povezanih neurona (živčanih stanica). Neuroni (slika 6-16)
se sastoje od tijela (soma), ulaznih niti (dendrita) i izlaznih niti (aksona). Dendriti primaju električne
impulse iz okoliša ili drugih stanica, tijelo ih promijeni u drugi oblik (obradi), te se onda aksonima provode
sljedećoj razini neurona. Na taj način živčani sustav bioloških organizama prenosi informacije koje
prikupljaju biološka osjetila i upravlja radom cjelokupnog organizma. Umjetni neuroni su matematičke
funkcije koje oponašaju rad bioloških neurona. Dendrite predstavljaju ulazni podaci, a aksone izlazni
podaci. Tijelo neurona provodi funkciju sumiranja ulaznih vrijednosti.
Slika 6-16. Biološki neuroni su inspiracija za računalnu tvorevinu umjetni neuron
95
Inicijalni rad McCullocka i Pittsa objavljen je u članku A logical calculus of the ideas immanent in nervous activity
u Bulletin of Mathematical Biophysics 5:115-133, 1943. g.
6 UČENJE I STROJNO UČENJE
201
Perceptron je računalna implementacija umjetnog neurona. On je samostalna računalna
jedinica koja ulazne vrijednosti množi težinama, zbraja ih i računa ukupnu vrijednost sume na koju zatim
djeluje aktivacijskom funkcijom koja uspoređuje vrijednost sume s graničnom vrijednosti koju nazivamo
prag (engl. Threshold), te na temelju te usporedbe određuje vrijednost izlaznog signala. Slika 6-17
prikazuje grafičku interpretaciju perceptrona.
Slika 6-17. Računalna interpretacija perceptrona (umjetnog neurona)
Usporedimo li ga s grafičkim prikazom algoritama linearne i logističke regresije (Slike 6-4 i 6-13),
lako je uočljiva sličnost. Perceptron je u biti algoritam linearne regresije kojem je na izlazu dodana
aktivacijska funkcija (engl. Activation Function), odnosno logistička regresija koja nema blok sa
sigmoidnom funkcijom. Aktivacijska funkcija je funkcija jediničnog skoka koja za ulaznu vrijednost veću
od 0 daje 1, a za ulaznu vrijednost manju od 0 daje -1. Ovdje je važno uočiti da su izlazi 1 i -1 iako se radi
o binarnoj klasifikaciji kod koje se kao izlazne vrijednosti uobičajeno koriste 0 i 1. Razlog je algoritam
učenja perceptrona koji opisujemo u nastavku.
Ulazna vrijednost računa se na isti način kao i hipoteza linearne regresije, s tim da je kod
neuronskih mreža uobičajeno koristiti druge oznake:
3!
:
"
#
$
%e
"
'e
#
#
#
'e
$
#
$
(6-19)
Težina w
0
ima poseban značaj. Ona određuje prag iznad kojeg suma
"e
#
#
#
'e
$
#
$
$
na izlazu daje
1, pa se zato i naziva faktor korekcije (engl. Bias) i često označava s b. Na primjer, za w
0
= -2 perceptron
će na izlazu imati 1 ako je
"e
#
#
#
'e
$
#
$
$f6
.
Kao i u prethodnim slučajevima projektirati perceptron znači odrediti težine w
0
, w
1
i w
2
. Postupak
koji se koristi je vrlo sličan spustu gradijenta koji se koristio kod linearne i logističke regresije, ali ne
potpuno isti. Početnu ideju je 1957. godine predložio američki psiholog Frank Rosenblatt (1928. 1971.)
i nazvao ju perceptronsko pravilo (engl. Percepton Rule). Sastoji se od toga da se krene od nekih malih,
proizvoljno odabranih vrijednosti težina. Za svaki ulazni podatak (x
1
,x
2
) težina se korigira već
poznatom jednadžbom iz spusta gradijenta:
e
,
g%e
,
-he
;
&
'
(
%e
,
-3;<"!
<
&
'
(
"
I
$
-.
&'(
$<#
;
&
'
(
(6-20)
Osnovna razlika između spusta gradijenta i perceptronskog pravila je u riječima za svaki ulazni
podatak. Kod spusta gradijenta težine se korigiraju nakon cijele sekvence podataka za treniranje. Kod
proračuna novih vrijednosti težina, razlika između dobivenog izlaza i željenog izlaza
"!
<
&
'
(
"
I
$
-.
&'(
$<#
;
&
'
(
se najprije sumira za sve ulazne podatke (i = 1, ... , m), pa tek onda množi s parametrom brzine učenje α
i oduzima od postojeće vrijednosti težina. Kod perceptrona se korekcija težina radi za svaki ulazni
podatak. Zbog toga se ponekad algoritam perceptronskog pravila naziva inkrementalni spust
gradijenta (engl. Incremental Gradient Descent).
6 UČENJE I STROJNO UČENJE
202
Pogledajmo primjer. Kod perceptrona hipoteza i željeni izlaz mogu imati samo vrijednosti 1 ili -1.
U slučaju da perceptron pogodi izlaz nema korekcije težina:
e
,
ie
,
-3;<
"
5-5
$
<#
;
&
'
(
%e
,
-4
e
,
g%e
,
-3;<
"
-5-"-5$
$
<#
;
&
'
(
%e
,
-4
U slučaju da perceptron ne pogodi izlaz, za negativne vrijednosti stvarnog izlaza korekcija će biti
negativna, a za pozitivne pozitivna:
e
,
ie
,
-3;<
"
5-"-5$
$
<#
;
&
'
(
%e
,
-;<6<#
;
&
'
(
e
,
g%e
,
-3;<
"
-5-5
$
<#
;
&
'
(
%e
,
';<6<#
;
&
'
(
Veličina promjene ovisi o parametru brzine učenja i ulaznoj vrijednosti. Postupak je vrlo
jednostavan i može se koristiti za jednostavnu binarnu klasifikaciju metodom nadziranog učenja.
Ograničenje mu je konvergencija. Namještanje težina konvergira samo ako su klase linearno odvojive.
Ako se klase ne mogu razdvojiti linearnom granicom odluke, promjena parametara neće konvergirati.
Parametri će oscilirati pa je nužno ograničiti maksimalan broj prolazaka kroz podatkovni skup za učenje
i/ili postaviti prag za broj toleriranih pogrešnih klasifikacija. Problem linearne odvojivosti može se riješiti
i unapređenjem arhitekture perceptrona na način da se uzme drugačija aktivacijska krivulja koja na
izlazu ne daje binarne podatke -1 ili 1, već vrijednost iz intervala [-1, 1]. Tipičan primjer je funkcija slična
sigmoidnoj funkciji iz logističke regresije, samo što je spuštena tako da daje izlazne vrijednosti u intervalu
[-1, 1], a kreira se na primjer pomoću hiperbolnog tangesa:
j
"
#
$
%VZ2!
"
#
$
%
=
$
>=
%$
=
$
?=
%$
(6-21)
Umjetni neuron s ovakvom kontinuiranom aktivacijskom funkcijom uobičajeno se zove
sigmoidni neuron (engl. Sigmoid Neuron).
Osim aktivacijske funkcije hiperbolnog tangensa, u umjetnim neuronskim mrežama koriste se i
druge aktivacijske funkcije, pa i originalna sigmoidna funkcija (koja se ponekad naziva i logistička
aktivacijska funkcija). Ona daje izlaznu vrijednost u intervalu [0 , 1], što ponekad stvara problem u
procesu učenja. U dubokom učenju posebno je popularna pojednostavljena verzija logističke funkcije koja
se naziva ispravljena linearna funkcija (engl. ReLU Rectified Linear Unit):
j
"
#
$
%
k
4)
#)
3YZ3#l4
3YZ3#f4
(6-22)
koja daje izlaznu vrijednost u intervalu [0 , ¥]. Kako za sve negativne vrijednosti na izlazu daje
0, i ona ponekad ima probleme u procesu učenja, pa se primjenjuje i njena modificirana verzija
parametarska ReLU (engl. Parametric ReLU):
j
"
#
$
%
k
;#)
#)
3YZ3#l4
3YZ3#f4
(6-23)
Ako je a = 0,01 naziva se propustljiva ReLU (engl. Leaky ReLU).
Spajanjem više perceptrona na način da izlazni signali neurona početnog sloja budu ulazni signali
neurona sljedećeg sloja dobije se višeslojni perceptron (engl. Multi Layered Perceptron) koji sada već
spada u umjetne neuronske mreže.
Umjetna neuronska mreža
Umjetne neuronske mreže (engl. ANN Artificial Neural Network) su mreže umjetnih neurona.
Umjetna neuronska mreža spada u nadzirane ili polunadzirane metode strojnog učenja. Mreža se sastoji
od umjetnih neurona, najčešće poredanih u slojeve, tako da razlikujemo:
ulazni sloj neurona koji preuzimaju ulazne signale
6 UČENJE I STROJNO UČENJE
203
skrivene slojeve koji prenose signale i
izlazni sloj koji daje izlazne zaključke.
Struktura prikazana na slici 6-18 obično se naziva unaprijedna neuronska mreža (engl.
Feedforward Neural Network).
Slika 6-18. Unaprijedna umjetna neuronska mreža s jednim skrivenim slojem
Svaki neuron ima svoje težinske faktore s kojima se množe njegovi ulazni signali, sumator i
aktivacijsku funkciju kojom se računa njegov izlazni signal. Projektirati umjetnu neuronsku mrežu znači:
odabrati njenu arhitekturu (broj umjetnih neurona, oblik aktivacijske krivulje, broj
slojeva, način međusobnog povezivanja umjetnih neurona) i
trenirati (naučiti) umjetnu neuronsku mrežu na način da se odrede vrijednosti svih težina
tako da mreža za ulaze iz skupa podataka za treniranje daje izlaze što sličnije rezultatima iz
skupa za treniranje.
Kod treniranja umjetne neuronske mreže najčešće se koristi postupak propagacije pogreške
unatrag (engl. Backpropagation). To je iterativni postupak kojim se optimiziraju vrijednosti težinskih
faktora neurona kako bi na izlazu dobili vrijednosti iz skupa za treniranje. Pri tome se najčešće koriste
različite inačice postupka spusta gradijenta koji smo detaljno upoznali.
Neuronske mreže u početku su se sastojale samo od jednog skrivenog sloja. Dugotrajan i složen
postupak treniranja mreže ograničavao je praktičnu primjenu većeg broja slojeva i kompleksnijih
struktura. Današnje računalne arhitekture, najviše zahvaljujući paralelnoj obradi podataka, omogućile
su realizaciju neuronske mreže s više skrivenih slojeva koje se nazivaju duboke neuronske mreže.
Duboke neuronske mreže i duboko učenje
Duboke neuronske mreže (engl. Deep Neural Networks) sastoje se od više skrivenih slojeva, ali
i koriste naprednije strukture od višeslojnog perceptrona. Jednu duboku unaprijednu neuronsku mrežu
s pet skrivenih slojeva prikazuje slika 6-19.
Osim unaprijedne arhitekture, danas se koriste i rekurentne neuronske mreže (engl. Reccurent
Neural Networks) kod kojih protok informacija među neuronima ide u svim smjerovima. Ovakve mreže
su pokazale dobre rezultate u obradi prirodnog jezika. Tu su i konvolucijske neuronske mreže (engl.
Convolutional Neural Networks) koje koriste trodimenzionalnu strukturu pogodnu za obradu i analizu
digitalnih slike i daju odlične rezultate na području kognitivnog računalnog vida, posebno u
prepoznavanja objekata na slici i odnosa među njima (prepoznavanje scene). Ilustraciju duboke
neuronske mreže za prepoznavanje lica već smo prikazali na slici 1-11.
Danas duboke neuronske mreže nalaze brojne praktične primjene, a projektiraju se obično
korištenjem posebnih programskih okvira (engl. Frameworka) kao što su TensorFlow, Keras i
PyTorch.
6 UČENJE I STROJNO UČENJE
204
Slika 6-19. Duboka unaprijedna neuronska mreža s pet skrivenih slojeva
Projektirati duboku neuronsku mrežu znači definirati hiperparametre koji predstavljaju
vanjske parametre mreže. Hiperparametri se dijele u dvije grupe:
hiperparametri vezani za strukturu mreže:
o broj skrivenih slojeva duboko učenje obično koristi 3 10 skrivenih slojeva
o odumiranje koliki će broj neurona slučajnim odabirom odumrijeti kako bi se spriječilo
pretreniranje
o aktivacijska funkcija koju će aktivacijsku funkciju neuroni koristiti (linearnu,
sigmoidnu, tanh, softmax, ReLU itd.)
o inicijalne težine za prvu iteraciju treniranja tipično se postavljaju na 0 ili slučajnim
odabirom, ali nekada se može koristiti heuristika npr. kod tanh aktivacijske funkcije
može se koristi tzv. Xavierova inicijalizacija
96
.
hiperparametri vezani za algoritam učenja:
o brzina učenja korak učenja kod spusta gradijenta
o broj epoha učenja, iteracija i veličina serije jedne iteracije backpropagation učenja
o algoritam optimizacije temeljni algoritam koji se koristi je stohastički spust gradijenta,
no tipično se još koriste
97
i miniserija spusta gradijenta (engl. Mini-batch Gradient
Descent), momentum algoritam (koji čeka da se težina osvježi te je ažurira drugi put
koristeći delta vrijednost što se pokazalo da ubrzava učenje), RMS Prop (engl. Root-
Mean-Square Propagation), AdaM (engl. Adaptive Momentum), AdaGrad, AdaDelta,
Nesterov ubrzani gradijent.
Programski okviri (engl. Frameworka), kao što su prije spominjani TensorFlow, Keras i
PyTorch, omogućavaju relativno jednostavno podešavanje ovih hiperparametara, te pokretanje
algoritma treniranja na skupu podataka za treniranje. Programerski okvir inicijalizira mrežu željene
96
Za detalje pogledati na primjer https://prateekvjoshi.com/2016/03/29/understanding-xavier-initialization-in-deep-
neural-networks/
97
Za detalje pogledati na primjer https://d2l.ai/chapter_optimization/index.html
6 UČENJE I STROJNO UČENJE
205
strukture te pokreće algoritam treniranja. Po završetku treniranja, dobijemo model s istreniranim
parametrima za svrhu određenu podacima za treniranje.
Praktične primjene također često koriste i prijenosno učenje (engl. Transfer Learning).
Prijenosno učenje odnosi se na korištenje već stečenog znanja i njegovog nadograđivanja. Naime, nekada
se za inicijalne težine koriste podaci već istrenirane duboke neuronske mreže te se optimiziraju manjim
skupom podataka za treniranje. Druga mogućnost je koristiti već istreniranu neuronsku mrežu za
generičke namjene, a trenirati samo dodatne slojeve za specifičnu namjenu.
Korištenje biblioteka i programerskih okvira olakšalo je!implementaciju projekata za industrijsku
primjenu dubokog učenja. To je rezultiralo time da danas mnogi praktičari duboko učenje svode na model
crne kutije (engl. Black Box) bez razumijevanja načina rada internih procesa. To i nije baš pravi put,
zato što se zadovoljavajući rezultati mogu dobiti samo uz dobro razumijevanje domenskog znanja,
mehanizma treniranja i zaključivanja dubokih neuronskih mreža.!
6.4 Nenadzirano učenje
Nadzirano učenje ima za cilj pronaći hipotezu koja se na najbolji način uklapa u ulazne označene
podatke, dok nenadzirano učenje ima za cilj pronalaženja strukture u neoznačenim podacima.
Nenadziranog učenja je posebno značajno u današnje vrijeme, zato što su neoznačeni podaci lako dostupni
i jeftini (otvoreni web, podaci sa senzora, IoT). Skupo ih je označavati, pa su postupci koji ne zahtijevaju
označene podatke vrlo važni. Nenadzirano učenje se može podijeliti po različitim kriterijima, a mi ćemo
ovdje navesti podjelu po ciljevima, pa razlikujemo:
klasteriranje (postupak grupiranja podataka po sličnim značajkama)
smanjenje dimenzionalnosti (postupak kojim se matematičkim postupcima identificiraju
najbitnije značajke podataka te se smanjuje njihova dimenzionalnost) i
detekcija anomalija (koristi se za prepoznavanje podataka koji se ne uklapaju u očekivane
podatke).
6.4.1 Klasteriranje
Klasteriranja (engl. Clustering) ima za cilj grupirati podatke u grupe ili klastere prema sličnosti
određenih značajki. Slični podaci svrstavaju se u iste grupe. Ovakav postupak koristan je u mnogim
segmentima industrijske primjene strojnog učenja, a neki od njih su:
segmentacija tržišta (grupe kupaca koje imaju slične afinitete)
analiza društvenih mreža (Facebook, Twitter itd. imaju velike količine pohranjenih podataka
o korisnicima, pa se klasteriranje koristi za prepoznavanje sličnih korisnika)
klasteri servera (alokacija resursa za distribuirano računanje prema sličnim karakteristikama
i blizini)
astronomski podaci (razumijevanje formiranja galaksija) itd.
Najpoznatiji algoritam za klasteriranje je algoritam k-sredina.
Algoritam k-sredina
Algoritam k-sredina (engl. k-means Algorithm) je algoritam za automatsko grupiranje
podataka u koherentne grupe. Najpoznatiji algoritam za klasteriranje, a popularnost može zahvaliti tome
što je intuitivan i jednostavan za implementaciju. Da bismo ga primijenili, potrebno je poznavati značajke
podataka koje želimo razdvojiti u grupe i broj grupa (K) na koji ćemo podatke razdvojiti. Nakon
provođenja postupka dobijemo informacije o formiranju K klastera, a svaki od njih je opisan sa svojim
prosječnim vrijednostima značajki. Postupak je sljedeći:
Na početku ili svjesnim vlastitim odabirom ili slučajnim odabirom postavimo K početnih
centara klastera µ
k
, k=1,...,K.
6 UČENJE I STROJNO UČENJE
206
Za svaki podatak x
i
provjerimo njegovu udaljenost od centara svih K klastera te primjenom
operacije argmin f(.) koja vraća element skupa za koji je funkcija f(.) minimalna taj podatak
x
i
pridružimo klasteru kojem je najbliži. Pri tome se obično koristi Euklidska udaljenost.
Prolaskom kroz sve podatke, dobit ćemo prvu verziju razdiobe podataka na klastere.
Sada je potrebno izračunati nove centre klastera, na način da se izračuna srednja vrijednost
svih podataka koji su tom klasteru pridruženi.
Nakon što su se centri pomakli, postupak se ponavlja. Ponovno se prolazi kroz sve podatke
te se pojedinačni podaci pridjeljuju najbližem centru te se izračunavaju novi centri klastera
sve dok ne dobijemo stacionarno stanje što znači da se centri klastera više ne mijenjaju.
Primjer klasteriranja postupkom k-sredina u tri klase na temelju dviju značajki prikazuje slika
6-20. Prikazana je početna situacija i podjela u klase nakon 14 iteracija.
Slika 6-20. K-means klasteriranje u tri klase na temelju dviju značajki na početku i nakon 14 iteracija
98
Pseudokod algoritma k-sredina daje algoritam 6-2.
Algoritam 6-2. Pseudokod algoritma za klasteriranje u K klastera
//Definirati broj klastera K
K
//Inicijalizirati slučajnim odabirom početne centre K klastera (k = 1 , K)
µ
1
, ... , µ
K
Repeat
//Za svih m ulaznih podataka izračunaj pripadanje g
ij
jednom od klastera na temelju
Euklidske udaljenosti
for (i = 1 to m) {
g
ik
= {1 if k=argmin
k
||x
i
- µ
k
||
2
else 0} }
98
Slika je s https://commons.wikimedia.org/wiki/File:K-means_convergence.gif uz GNU Free Documentation
License.
6 UČENJE I STROJNO UČENJE
207
//Izračun novih centara klastera
for (k = 1 to K) {
n
k
= SUM
(i=1 to m)
(g
ik
) //# podataka klastera k
µ
k
= (1/n
k
)SUM
(i=1 to n)
( g
ik
x
i
) } //novi centri klastera
until Covergence
Nedostaci algoritma k-sredina
Pet je temeljnih nedostatka algoritma k-sredina:
1. Iako je intuitivan, i daje dobre rezultate za većinu praktičnih primjena, kritičari algoritma
k-sredina zamjeraju mu nedostatak matematičke osnove. Naime, algoritam k-sredina nije
nastao temeljem matematičkog izvoda, već intuitivnog postupka.
2. Rezultat algoritma klasteri, ovise o odabranim početnim točkama centara klastera. Ako
ponovimo postupak s drugačije odabranim početnim centrima klastera, rezultati se mogu
razlikovati. To znači da je moguće da algoritam pronađe lokalni optimum, a ne globalni
optimum najbolji izbor centara klastera. Šanse za pronalazak lokanog optimuma mogu se
umanjiti tako da se cijeli postupak algoritma ponovi više puta, ali s različitim izborom
početnih točaka centara klastera. Većim brojem ponavljanja uočit će se postojanje globalnog
optimuma kod više rezultata, dok će se lokalni optimum pojaviti samo kod pojedinih izbora
početnih točaka. Postavlja se pitanje kako ocijeniti koja je najbolja razdioba klastera.
Intuitivno rješenje je da je bolja razdioba ona u kojoj su podaci najbolje grupirani oko svog
centra. To možemo kvantitativno izraziti mjerom srednje kvadratne udaljenosti podatka od
centra njegovog klastera. Dakle, nakon iterativnog provođenja k-sredina klasteriranja s
različito odabranim početnim centrima odaberemo rezultat s najmanjom vrijednošću ove
mjere.
Slika 6-21. Klasteriranje podataka u klastere ovise o odabiru početnih centroida. Na objema
slikama isti su podaci odnosa visine i težine koji su na lijevoj slici klasterirani u tri klastera
veličine majica (S, M i L), a na desnoj slici u pet klastera veličina (XS, S, M, L, XL)
99
3. Nerazdvojivi klasteri u slučaju da su podaci takvi da nema jasne granice razdvajanja među
grupama (podaci su kontinuirani), rezultati algoritma k-sredina ovisit će o odabiru početnih
točaka. U ovom slučaju ni intuitivno ne možemo razdvojiti podatke na klastere ovakvim
postupkom.
4. Poznavanje broja klastera algoritmu k-sredina kao ulazni podatak potreban je broj
očekivanih klastera. Nekada imamo samo podatke, ali ne znamo koliko različitih skupina
99
Slika je s OpenCV Python Tutoriala