Programiranje

[Tutorial] Uvod u umjetnu inteligenciju, GA

1domagoj1 čet 24.12.2015 23:39

Ponukan (zabrinutim) komentarima na BOL vijestima vezanim uz temu umjetne inteligencije, odlucio sam napisati ovaj pomalo duzi tutorial da bacim malo svjetla na "misticnu" temu umjetne inteligencije. Tutorial je prvenstveno namijenjen programerima jer se bavi konkretnom implementacijom odredenog podrucja umjetne inteligencije, ali vrlo lako moze posluziti kao stivo i onima koji nisu u toj bransi jer ima dosta price "na suho" da se tako izrazim. Imajte na umu da je ovo samo djelic velikog i aktivnog podrucja umjetne inteligencije.

Krenimo s jednim naizgled jednostavnim, pomalo filozofskim pitanjem: sto je to svijest? Ovo pitanje na prvi pogled nema veze s racunalima i racunarstvom, no ako pogledamo malo dublje u tematiku dolazimo do potpuno suprotnog zakljucka. Naime, povecanjem racunalne moci danas imamo sve "pametnije" programe, algoritme, robote, drugim rijecima, imamo sve "pametniju" umjetnu inteligenciju. Probleme koji se danas postavljaju pred racunarsku znanost vise nije moguce rijesiti konvencionalnim metodama i algoritmima, rjesenje moramo traziti u drugim smjerovima. Raspoznavanje uzoraka na slici, raspoznavanje govora, kombinatorijalni problemi, izvlacenje znanja iz gomile podataka (big data), predvidanje trendova, klasifikacija i dr., pa u krajnjem slucaju i proucavanje ljudskog mozga na temelju umjetnih modela, sve su to problemi koje je nemoguce rijesiti uobicajenim algoritmima i tu se okrecemo tzv. umjetnoj inteligenciji.

Vratimo se malo na pocetno pitanje o tome sto je svijest. Na njega bas i ne mozemo odgovoriti (jos). Idemo se onda pitati jedno drugo pitanje. Da li npr. glista ima svijest? Opet, mozda malo zeznuto, ali mogli bi se sloziti da nema. No sto je sa psom? Psi su svjesni okruzenja, osjecaju bol, strah, ali recimo, ne prepoznaju se pred ogledalom. Tu je jos teze odgovoriti, pa bi se mogli sloziti da su psi do neke mjere svjesni. Svjesniji od gliste, ali ne kao covjek. Sto mozemo zakljuciti iz ovoga? Sto konkretno cini razliku? Pa, ocito je to velicina mozga. Sigurni smo da svijest ima veze s mozgom (kao i emocije npr.), ali ne i kako, a i ne znamo definirati.

Danas znamo da je glavni element za obradu u mozgu neuron. Pojednostavljeno, neuron se sastoji od dendrita, tijela neurona i aksona. Prosjecno, svaki je neuron povezan s jos 10^4 drugih neurona preko dendrita. Svaki neuron se moze "upaliti" i pritom salje elektricne impulse drugim neuronima preko svog izlaza, aksona. Drugi neuroni akumuliraju ulaze, obraduju ih pa pale ili ne pale i tako u krug. Neurona u ljudskom mozgu ima oko 100 milijardi koji su medusobno povezani s oko 10^15 veza. Iz svih ovih brojki jasno je da se obrada podataka u mozgu odvija masivno, ali MASIVNO paralelno. Dodatni argument ovome jest cinjenica da su neuroni jako spori, vrijeme paljenja im je cca 1 ms. S obzirom da covjek moze izrazito kompleksnu obradu podataka obraditi u vrlo kratkom roku (npr. mozemo prepoznati poznatu osobu sa slike za cca 0.1 s) ocito je da se obrada ne vrsi slijedno. Za usporedbu danas najdublju neuronsku mrezu ima Microsoft (koliko dugo, to cemo jos vidjeti) sa 152 sloja ako se ne varam (zanimljivost je da je 2012. ako se ne varam, najdublja mreza imala 8 slojeva). Cak i ako svaki sloj ima po 10000 neurona, to je i dalje puno manje od ljudskog mozga.

No, da li je svijest posljedica tih ogromih brojki? Vrlo vjerojatno ne. Ako bi napravili racunalo sa sirovom procesnom moci mozga, vrlo vjerojatno za posljedicu ne bi dobili svijest. Takoder, istrazivanja pokazuju da u mozgu nema posebnog mjesta (centra) za svijest, tako da smo u slijepoj ulici po tom pitanju. Ne znamo odgovor na njega, a mozda nikad niti necemo znati. Postoji vise hipoteza, da je svijest posljedica kompleksnih procesa u mozgu, da mozda samo imamo dojam svijesti, a ustvari smo samo zrtve uzroka i posljedice. Ustvari, cak ne mozemo niti reci da li su drugi oko nas svjesni. Sto se nas tice, moze biti da svi samo reagiraju na podrazaje. S tim na umu, ako bi i stvorili svjesnog robota, ne bi mogli ni reci da li je svjestan ili samo reagira na podrazaje pa izgleda da je svjestan. Ovo je samo povrsina ovo pitanja, koga zanima vise moze traziti po internetu.

Jos je jedna stvar kod umjetne inteligencije. Dosta cesto razlikujemo tzv. "jaku" i "slabu" (ili primjenjenu) umjetnu inteligenciju. Jaka umjetna inteligencija je ustvari opca umjetna inteligencija koja bi imala sve znacajke ljudske inteligencije. Stvaranje ovakog tipa inteligencije zahtijeva jos nepoznata i fundamentalno nepredvidiva znanstvena otkrica te duboko znanstveno poznavanje i shvacanje svijesti. A to jos nemamo i dok ti uvjeti ne budu zadovoljeni, tesko da ce se cak u ovom stoljecu nesto na ovom polju postici. Gdje smo trenutno kod opce umjetne inteligencije? U principu, jaz izmedu danasnjeg racunarstva i opce umjetne inteligencije istovjetne ljudskoj je otprilike kao i jaz izmedu danasnjeg svemirskog leta i prakticnog svemirskog leta nadsvjetlosnom brzinom. Slaba umjetna inteligencija je ono cime se ustvari danas najvise bavimo i na sto cu se ja kroz ovaj tutorial (a mozda i jos koji) osvrnuti, tocnije, osvrnut cu se samo na dijelic jer je to podrucje stvarno ogromno. Sad se postavlja pitanje cemu ovoliki uvod? Pa, kao prvo, volim puno pricati. :P Kao drugo, ovime sam se htio osvrnuti na ceste komentare u BOL vijestima o umjetnoj inteligenciji, a koji redovito glase "skynet", "we're doomed", "propali smo", "naj* smo" i sl. Ne, nismo, moramo jos puno zgancov pojesti da bismo bili u stanju nesto takvo napraviti. S druge strane, tko zna, mozda se potrefe neki od potrebnih (navedenih) uvjeta i nesto napravimo, ali kako to obicno biva, malo je vjerojatno. Einstein je prije 100 godina predstavio teoriju relativnosti, pa i dan danas jos ne putujemo kroz crvotocine ili koristimo energiju crne rupe, ili sto vec. Tako da, jos smo jako daleko od "skyneta". Ubuduce kad govorim o umjetnoj inteligenciji, mislim upravo na tu primjenjenu umjetnu inteligenciju.

Sad nakon malo poduzeg uvoda, krenimo na konkretnije stvari. Za pocetak cemo obraditi jedno od podrucja unutar umjetne inteligencije za koje smatram da ga je relativno lagano shvatiti (i prakticki nema matematike sto se ne moze reci za neka druga podrucja koja se temelje na dosta netrivijalnoj matematici) i nakon sto shvatite nacin rada vrlo lako mozete sami implementirati slicne stvari. Rijec je o tzv. evolucijskom racunarstvu, tj. evolucijskom racunanju. Sto to konkretno znaci? Pa, nije bas lagano definirati taj pojam, ali mozemo reci da je to podrucje racunarske znanosti koje proucava algoritme koji simuliraju evolucijski razvoj vrsta, ponasanje jedinke u drustvu ili pak simuliraju neke aspekte umjetnog zivota. Svi ti algoritmi su tzv. populacijski algoritmi (jer operiraju nad nekom populacijom) iako se moze dogoditi da populacija padne na samo jednu jedinku. Uz to, velik dio ovih algoritama inspiraciju vuce iz prirode i procesa u prirodi, no postoje i oni koji nemaju nikakvu motivaciju iz prirode. Razvoj ovog podrucja je zapoceo negdje sezdesetih godina proslog stoljeca. Onako kako danas znamo to podrucje, ono se dijeli na ugrubo tri dijela: evolucijske algoritme (evolucijske strategije, evolucijsko programiranje, genetsko programiranje, genetske algoritme...), algoritme rojeva (algoritam roja cestica, algoritam kolonije mrava, algoritam kolonije pcela, umjetni imunoloski sustav...) te ostale algoritme (algoritam diferencijske evolucije...). Konkretno, u ovom tutorialu obradit cemo jednog od najpoznatijih predstavnika evolucijskih algoritama, genetski algoritam.

Sto je genetski algoritam? GA je heuristicka metoda (vrlo vazno, sve u umjetnoj se vrti oko nekakve heuristike) slucajnog i usmjerenog pretrazivanja prostora rjesenja koja imitira prirodni evolucijski proces. GA (kao i svi algoritmi evolucijskog racunanja) sluzi za rjesavanje tezih optimizacijskih problema za koje ne postoji egzaktna matematicka metoda rjesavanja ili NP-teskih problema. Sad bude jasno zasto sam za pocetak odabrao GA. Nacin rada GA moze se sazeti prakticki u jednu recenicu: imamo pocetnu populaciju, iz nje se odabiru bolje jedinke, one sudjeluju u reprodukciji i tako ukrug dok se ne zadovolji uvjet zavrsetka procesa. Pa ovo je zaista lagano! Pa i jest, ali postoji kvaka. S obzirom da je u svojoj sustini GA ovako "lagan", ono sto je tesko jest konkretno definirati te korake. Kako prikazati populaciju? Kako generirati pocetnu populaciju? Kako evaluirati populaciju? Kako izabrati jedinke iz populacije? Kako ih krizati? Sve ovo treba definirati za svaki problem posebno i upravo taj nedostatak univerzalne i konkretne kuharice GA cini u odredenoj mjeri teskim.

Stoga, u sljedecim retcima osvrnut cemo se na sljedeci problem te na njemu objasniti konkretne korake u nadi da steknete odredeni osjecaj za GA. Problem je ovaj: imamo neku crnu kutiju koja za odredeni ulaz generira nekakav izlaz. Jedino sto znamo je priblizan oblik prijenosne funkcije. Nas ce zadatak biti dokuciti pravi oblik prijenosne funkcije, a u tome ce nam pomoci GA. No, prvo idemo definirati pseudokod genetskog algoritma. Konkretno, postoje dva tipa GA: eliminacijski i generacijski. Sto to znaci i koja je razlika izmedu njih? Kao sto smo vec rekli GA radi nad nekom populacijom iz koje se izabiru jedinke za daljnju reprodukciju. Uvjet eliminacijskog genetskog algoritma jest da se uvijek radi nad jednom populacijom, drugim rijecima, iz populacije se uzmu potencijalni roditelji te se krizaju cime se stvara novo dijete koje se ubacuje u populaciju. Medutim, da bi se dijete moglo ubaciti u populaciju, neka jedinka se mora eliminirati iz populacije (da se odrzi konstantan broj jedinki unutar populacije). Na taj nacin u populaciji postoje i roditelji i djeca. To je eliminacijski genetski algoritam. Generacijski GA iz koraka u korak iz populacije roditelja stvara novu populaciju djece (dakle, ovo je vazno, sad imamo dvije populacije u memoriji), a nakon toga stara populacija odumire i ostaje samo nova te se proces ponavlja. Iz mog iskustva, eliminacijski GA je nesto brzi i trosi manje memorije jer operira nad samo jednom populacijom, no sporije konvergira k rjesenju (u vise generacija). S druge strane generacijski je nesto sporiji i trosi vise memorije (zbog dvije populacije u isto vrijeme), ali nesto brze konvergira k rjesenju (u manje generacija). Idemo sada vidjeti konkretan pseudokod oba tipa GA.

 

Pseudokod eliminacijskog GA:

populacija = stvori_pocetnu_populaciju(velicina)
evaluiraj(populacija)
ponavljaj_dok_nije_zadovoljen_uvjet_zavrsetka:
    odaberi roditelj1 i roditelj2 iz populacija
    dijete = krizaj(roditelj1, roditelj2)
    mutiraj dijete
    evaluiraj dijete
    odaberi jedinku iz populacije -> ako losija zamijeni s djetetom
kraj

Kao sto vidimo, u principu vrlo jednostavno.

 

Generacijski GA:

populacija = stvori_pocetnu_populaciju(velicina)
evaluiraj(populacija)
ponavljaj_dok_nije_zadovoljen_uvjet_zavrsetka:
    nova_populacija = 0 // ova razlika je bitna!
    ponavljaj_dok_je velicina(nova_populacija) < populacija:
        odaberi roditelj1 i roditelj2 iz populacija
        dijete = krizaj(roditelj1, roditelj2)
        mutiraj dijete
        dodaj_u(nova_populacija, dijete)
    kraj
    populacija = nova_populacija
kraj

Mozemo vidjeti, ovdje baratamo s dvije populacije.

Postoji jos jedna vrsta generacijskog GA koja podrzava tzv. elitizam (zadrzavanje najbolje/ih jedinke/i u generaciji):

populacija = stvori_pocetnu_populaciju(velicina)
evaluiraj(populacija)
ponavljaj_dok_nije_zadovoljen_uvjet_zavrsetka:
    nova_populacija = 0
    ubaci_u_nova_populacija(dvije_najbolje_jedinke_iz_populacija) // elitizam!
    ponavljaj_dok_je velicina(nova_populacija) < populacija:
        odaberi roditelj1 i roditelj2 iz populacija
        dijete = krizaj(roditelj1, roditelj2)
        mutiraj dijete
        dodaj_u(nova_populacija, dijete)
    kraj
    populacija = nova_populacija
kraj

Ovdje dakle vidimo da imamo jedan dodatan korak koji u ovom slucaju uzima dvije najbolje jedinke i cuva njihov genetski materijal u sljedecoj generaciji. To se naziva elitizam.

Sad prakticki znamo kako napraviti GA, trebamo jos dodatno pojasniti neke pojmove koji su se do sad pojavili. Krenimo redom:
Jedinka ili kromosom - jedinka je neko konkretno rjesenje.
Populacija - populacija je (ocito) skup jedinki.
Gen - gen je dio nekog kromosoma, tj. dio nekog rjesenja, ako sad nije jasno, bude kad krenemo raditi GA

Nad navedenim pojmovima djeluju nekakvi genetski operatori koje smo sreli u pseudokodu:
Operator selekcije - ovaj operator bira jedinke iz populacije
Operator krizanja - ovaj operator kriza izabrane jedinke i stvara novu koja nosi karakteristike roditelja
Operator mutacije - ovaj operator je izrazito bitan jer mutira pojedinu jedinku te tako omogucava genetsku raznolikost, drugim rijecima, sprijecava da zapnemo u lokalnim optimumima (mi se nadamo globalnom).

Jos moramo obratiti paznju na par stvari. Prvo, prikaz rjesenja, tj. kako cemo definirati prikaz jedinke (kromosoma) i gena. Drugo, na koji nacin evaluirati jedinku, tj. kako prikazati i izracunati njezinu dobrotu (engl. fitness). Sad vec imamo osjecaj da iako je u principu GA lagan, nije bas trivijalan kad se krene u samu implementaciju.

Prikaz jedinke:
Jedinku se moze prikazati prakticki na proizvoljan nacin i to ovisi o konkretnom problemu. Ovdje cemo razmotriti samo prikaz brojevima s pomicnim zarezom, ali spomenut cemo i binarni prikaz. Dakle, prikaz rjesenja brojevima s pomicnim zarezom je u principu najjednostavniji i najprirodniji nacin prikaza rjesenja. Npr., ako trazimo minimum funkcije dviju varijabli, tocku T(x, y) za koju je iznos funkcije najmanji, tj. f(z) = (x, y) gdje f(z) moze biti bilo kakvog oblika, recimo f(z) = x^2 + y, jedna jedinka, tj. kromosom izgledao bi ovako:
jedinka = [0.4, 2.3]
Ja sam to ovdje napisao kao Python listu, ali to moze biti i obicno polje u C++-u/Javi/C#-u, svejedno. Dakle, vrlo jednostavno, jedan gen je varijabla x, a drugi gen je varijabla y.

Binarni prikaz je takoder jednostavan za razumijeti, ali zahtjeva dodatno kodiranje/dekodiranje kromosoma. Tu opet imamo proizvoljan nacin kodiranja/dekodiranja pojedinih gena. Npr., neka pojedini gen moze poprimiti vrijednost od 0 do 15 i neka jedinka ima istu strukturu kao i ova maloprije. Jedno moguce rjesenje neka bude 3 i 10. Tada ce jedinka izgledati ovako:
jedinka = 00111010
Ovdje sam pretpostavio da smo brojeve 0 do 15 kodirali direktno u njihove ekvivalente u binarnom sustavu tako da je 3 = 0011, a 10 = 1010. Rjesenja smo mogli kodirati i Grayevim kodom. Ili na vec neki drugi nacin, samo je bitno da je konzistentan i da znamo dekodirati vrijednosti. Sto je bolje od ovoga dvoje? Grayev kod ili prirodni binarni kod? Opet, ovisi o konkretnom problemu, implementaciji operatora, parametrima, prakticki o svemu. Tu lezi ta tezina implementacije GA. Imate nevjerojatno puno varijacija i izbora, a sve je meduovisno i nema najboljeg.

 

Kako bi u prethodnom primjeru kodirali rjesenje koje je prikazano brojevima s pomicnim zarezom u rjesenje koje je prikazano binarno? Tu postoje neke formule koje rade pretvorbu, tj. linearnu interpolaciju (odnosno uniformno uzorkovanje intervala). Necu ih izvoditi vec cu samo dati gotove formule. Zelimo preciznost na odredenu decimalu i trebamo izracunati koliko nam je potrebno bitova za prikaz nekog broja tom preciznoscu. To se racuna sljedecom formulom:
M = ld(((x_max - x_min) / preciznost) + 1)
gdje je ld dualni logaritam (logaritam po bazi 2), x_max i x_min je raspon intervala, a preciznost je zeljena preciznost. Npr., zelimo preciznost 10^-1 iz intervala [-50, 50]. Po formuli slijedi:
M = ld(((50 - (-50)) / 0.1) + 1) = ld(10^3 + 1) ~ 9.967
sto znaci da nam je za prikaz jednog broja iz intervala [-50, 50] treba 10 bitova. Iz toga slijedi da bi jedinka sa zadanom preciznoscu imala ukupno 20 bitova (jer se sastoji od dva broja s pomicnim zarezom).

 

Kako izracunati te brojeve? To nam kaze sljedeca formula:
x = (m / (2^M - 1)) * (x_max - x_min) + x_min
gdje je m = {0, 1, ..., 2^M - 1}. Drugim rijecima nulti x je upravo x_min jer cijeli umnozak s nulom postaje nula i ostaje jedino x_min, a (2^M - 1)-i x je upravo x_max jer se prva zagrada krati i ostaje x_max - x_min + x_min sto je x_max. Evo primjer: pretpostavimo da brojeve kodiramo s 4 bita, to je jako mala preciznost. To znaci da na raspolaganju imamo samo 16 brojeva uniformno rasporedenih po cijelom intervalu [-50, 50]. Dva otpadaju na granice i jos 14 ih je uniformno rasporedeno izmedu. Neka nam je jedinka sljedeca:
jedinka = 00111010
Znamo da je jedan gen kodiran s 4 bita (M = 4), dakle m1 = 0011, m2 = 1010:
x1 = (m1 / (2^M - 1)) * (x_max - x_min) + x_min = (3 / 15) * (50 - (-50)) + (-50) = -30
x2 = (m1 / (2^M - 1)) * (x_max - x_min) + x_min = (10 / 15) * (50 - (-50)) + (-50) = 16.667
Drugim rijecima, jedinka nam je jednaka [-30, 16.667] kad ju dekodiramo.

Eto, sad smo vidjeli dva od mnogo mogucih nacina prikaza rjesenja. Ostaje jos pitanje kako izracunati dobrotu pojedinog rjesenja, odnosno jedinke. Eh, to je opet jedna od onih stvari kod GA koje ovise o konkretnom problemu. U ovom konkretnom slucaju koji cemo mi raditi, koristit cemo srednju kvadratnu pogresku kao funkciju lošoće ili funkciju kazne (u kodu sam ju nazvao badness). Dakle, jos jedna od stvari koje se u GA mogu proizvoljno definirati. Opcenito se gleda da jedinke imaju cim vecu dobrotu, no u nasem slucaju mi cemo gledati obrnuto, cim jedinke imaju manju lošoću tim su bolje.

Jos nam ostaje pogledati operatore. Operatore cu objasniti za brojeve s pomicnim zarezom, kod binarnog prikaza se ne razlikuju puno.

 

Operatori:
Prvo cu objasniti operator krizanja. Najjednostavniji operator krizanja radi na sljedeci nacin: uzme dvije jedinke, odabere neku poziciju gdje ce "rezati" kromosom te napravi trecu jedinku koja je kombinacija prve i druge od razrezanih dijelova. Evo primjer:
roditelj1 = [1, 3, 4, 10, 2, 7, 9]
roditelj2 = [3, 7, 2, 1, 5, 6, 11]
Recimo da smo slucajno odabrali prekid kod treceg gena, dijete izgleda ovako:
dijete = [1, 3, 4, 1, 5, 6, 11] -> vidimo da je dijete kombinacija dvaju roditelja.


Ovo je bio samo primjer, postoji mnostvo operatora krizanja, svaki prikladan za drugaciji prikaz rjesenja. Cak stovise, za jedan nacin prikaza rjesenja postoji vise razlicitih operatora krizanja. Npr., za binarni prikaz rjesenja postoji krizanje s jednom tockom prekida (to je u principu ovaj primjer), krizanje s vise tocaka prekida gdje se malo uzme od jednog roditelja, malo od drugog, pa opet od prvog i tako redom koliko god tocaka prekida imamo. Takoder postoji i uniformno krizanje gdje svaki bit (gen) ima vjerojatnost 50% da ce biti nasljeden od prvog, odnosno od drugog roditelja. Kod prikaza brojevima s pomicnim zarezom imamo diskretnu (uniformnu) rekombinaciju sto je ekvivalentno uniformnom krizanju kod binarnog prikaza, svaki realni broj (gen) ima 50% vjerojatnost da ce biti nasljeden od prvog, odnosnog drugog roditelja. Imamo jednostavnu aritmeticku rekombinaciju gdje se odredi jedna tocka prekida, te se djetetu do te tocke daju geni jednog roditelja, a od te tocke nadalje uzima se aritmeticka sredina gena. Postoji i jednostruka aritmeticka rekombinacija kod koje se uzima aritmeticka sredina samo jednog gena. Postoji potpuna aritmeticka rekombinacija gdje se dijete stvara na nacin da se napravi aritmeticka sredina svih gena oba roditelja. Zatim, umjesto aritmeticke sredine moze se raditi zbrajanje/oduzimanje s vrijednoscu koju da normalna razdioba. Ima nevjerojatno puno izbora i kombinacija i niti jedno nije najbolje u opcem slucaju, tek za konkretne slucajeve su neke varijante bolje od drugih. Mi cemo u nasem primjeru raditi jednostavnu aritmeticku rekombinaciju i to umjesto jednog djeteta stvorit cemo odmah dva (eto, vec neka varijacija) tako da cu sad pokazati primjer toga:
roditelj1 = [0.1, 0.5, 0.3, 0.7, 0.2]
roditelj2 = [0.9, 0.9, 0.1, 0.5, 0.3]
Recimo da je tocka prekida kod drugog gena. Prvo dijete ce uzeti gene prvog roditelja, drugo dijete ce uzeti aritmeticku sredinu tih gena:
dijete1 = [0.1, 0.5 ...
dijete2 = [0.5, 0.7 ... -> jer (0.1 + 0.9) / 2 = 0.5 i (0.5 + 0.9) / 2 = 0.7
Sad ce prvo dijete dobiti aritmeticku sredinu ostalih gena, (0.3 + 0.1) / 2 = 0.2, (0.7 + 0.5) / 2 = 0.6, (0.2 + 0.3) / 2 = 0.25, a drugo ce dobiti gene drugog roditelja:
dijete1 = [0.1, 0.5, 0.2, 0.6, 0.25]
dijete2 = [0.5, 0.7, 0.1, 0.5, 0.3]
Jasno je da ovdje moze biti jos svakakvih varijacija na temu.

Sljedeci operator koji nam treba je operator mutacije. Operator mutacije djeluje nad jednom jedinkom i mutira ju. Opet, za razlicite prikaze postoje razliciti operatori mutacije. Tako za binarni imamo npr., jednostavnu mutaciju koja izabere neki nasumicni bit (gen) i okrene ga iz 0 u 1 ili iz 1 u 0. Postoji i potpuna mijesajuca mutacija kod koje broj jedinica i nula ostaje isti, ali im se redoslijed izmjeni. Kod prikaza brojevima s pomicnim zarezom imamo takoder jednostavnu mutaciju koja izabere nasumican broj (gen) i zamijeni ga nekim drugim nasumicnim brojem. Moguca je i varijacija gdje se izabere nasumican gen pa se zbroji/oduzme s brojem koji vucemo iz normalne (Gaussove) razdiobe. Mutacija je u principu najjednostavniji operator.

Sad kad imamo operator krizanja i operator mutacije, fali nam jos operator selekcije. Njega sam ostavio za kraj jer je on najkompliciraniji i najbitniji za optimalan rad GA. Selekcije se dijele na generacijske gdje se direktno biraju bolje jedinke ciji genetski materijal ulazi u sljedecu generaciju te eliminacijske gdje se biraju lose jedinke za eliminaciju, dok bolje prezivljavaju postupak selekcije (postoje i neke druge podjele). Selekcija ima mnogo, no ja cu ovdje spomenuti samo dvije: k-turnirsku selekciju te proporcionalnu selekciju.

Proporcionalna selekcija poznata je i pod nazivom engl. roulette-wheel selection. Kod ove selekcije vjerojatnost odabira i-te jedinke definirana je izrazom:
p_i = f_i / suma_od_1_do_n(f_j)
Dakle, vjerojatnost odabira i-te jedinke je njezina dobrota podjeljena sa sumom dobrota svih jedinki. Zove se roulette-wheel selekcija jer si ovu selekciju mozemo zamisliti na sljedeci nacin. Svaka jedinka dobije krisku odredene velicine na nekom kolu. Tada zavrtimo to kolo i jedinke s vecim kriskama imaju vecu vjerojatnost da budu izabrane, tj. da ce prenijeti svoj genetski materijal u sljedecu generaciju od jedinki s manjom kriskom. To je bitna stvar! Ne biramo eksplicitno jedinke s vecom dobrotom, nego upravo suprotno, biramo ih slucajno, ali one s boljom dobrotom imaju bolju sansu da budu izabrane. Na ovaj nacin smo osigurali da i one slabije jedinke imaju ipak nekakvu vjerojatnost da ih se odabere te smo tako smanjili mogucnost da algoritam zaglavi u lokalnom optimumu. Ova selekcija nije najsretnije rjesenje (inace, kad su GA prvi put predlozeni, ova selekcija je orignalno bila predlozena za operator) iz dva razloga. Prvo, sve dobrote moraju biti nenegativne (znaci vece ili jednake nuli) dok srednja vrijednost mora biti strogo veca od nule (jer se nulom ne moze dijeliti). Drugo, podlozna je problemu skaliranja. Sto to znaci? Zamislimo dvije populacije od po tri jedinke. U prvoj populaciji dobrote su redom 1, 2 i 3, a u drugoj 100001, 100002, 100003. Vjerojatnost odabira trece jedinke u prvoj populaciji je: 3/(1 + 2 + 3) = 0.5. Vj. odabira trece jedinke u drugoj populaciji je: 100003 / (100001 + 100002 + 100003) = 0.333336667. U obje populacije trece jedinke su najbolje, no u drugoj populaciji vjerojatnost odabira najbolje jedinke je gotovo pa ista vjerojatnosti odabira najgore koja iznosi 0.33333 (uvjerite se sami). No, u nasem primjeru ovakva ce selekcija biti relativno dobra.

Druga selekcija koju sam spomenuo je k-turnirska selekcija. Vrlo je jednostavna i najcesce se koristi kod eliminacijskih GA, ali nije nuzno, moze se koristiti i kod generacijskih (sto cemo i koristiti). Kod k-turnirske selekcije iz populacije se izvlaci nasumicno k jedinki i zatim se odabire najbolja jedinka. Postoje dvije varijante: jedna s ponavljanjima gdje je moguce istu jedinku izvuci vise puta iz populacije i druga bez ponavljanja gdje se jednom izvucena jedinka vise ne moze izvuci. Konkretna turnirska selekcija koju cemo mi implementirati biti ce 3-turnirska selekcija i koristit cemo ju kod eliminacijskog GA na sljedeci nacin: izabrat cemo nasumicno tri jedinke, dvije bolje ce biti roditelji, a nastalo dijete ce u populaciji zamijeniti trecu, najlosiju jedinku. Kod generacijskog GA k-turnirskom selekcijom uzet cemo samo najbolju jedinku iz turnira za roditelja.

Jos jedna stvar koja je ostala, a koju sam vec spomenuo, ali usputno su parametri. Koji su to parametri? Velicina populacije, vjerojatnost krizanja, vjerojatnost mutacije, velicina turnira (ukoliko se koristi k-turnirska selekcija), elitizam, itd. Svi su parametri medusobno ovisni, no u principu tri najbitnija su velicina populacije, vj. krizanja i vj. mutacije i oni najvise odreduju hoce li GA naci optimalna rjesenja ili ce negdje zaglaviti te koliko brzo ce ih pronaci. Fino podesavanje parametara je pak umjetnost za sebe.

Eto, to je vise manje to sto se tice potrebnih znanja za uspjesnu implementaciju GA. Sada cemo konacno malo zaprljati ruke i implementirati konkretan GA.

1domagoj1 pet 25.12.2015 00:02

Za pocetak, koji problem rjesavamo? Dakle, imamo nekakav sustav koji je za nas crna kutija. Taj sustav ima nekakvu prijenosnu funkciju za koju znamo samo kako djelomicno izgleda. Ona je sljedeceg oblika:
f(x) = a1 * x^4 - a2 * x^3 - a3 * x^2 + a4 * x - a5
Nas zadatak je pronaci koeficijente a1 do a5. S razlicitim koeficijentima ova funkcija moze poprimiti veoma razlicite oblike, a mi trazimo samo jedan. Dalje, na sustavu su napravljena odredena mjerenja, tocnije njih 250 na nacin da smo u sustav ubacili neku vrijednost i mjernim instrumentom izmjerili izlaz. Medutim, mjerni instrument nije savrsen (ali je i dalje dosta precizan) pa je u mjerenja unio odredeni šum. Informativno (ovo nije bitno za rjesavanje), šum se ravna po Gaussovoj razdiobi (to je dosta cest slucaj u praksi). U ovom slucaju mozemo pretpostaviti da se koeficijenti koje trazimo nalaze u intervalu [-3, 3].

Napomena: sav kod pisem u Pythonu iz ocitih razloga. Osim sto mi je najomiljeniji, to je jednostavni, cisti, visoki jezik kojeg je lako citati cak i ljudima koji nisu upoznati njime.

Krenimo redom, prvo cemo definirati arhitekturu naseg programa. S obzirom da su GA pomalo nezahvalni sto se tice objektnog oblikovanja definirat cemo sljedece klase: Chromosome, GeneticAlgorithm te Function. Iz imena samih klasa ocito je sto koja predstavlja. Chromosome je ocito kromosom, tj. jedinka koja nam predstavlja jedno rjesenje, GeneticAlgorithm je klasa koja implementira cijeli GA, a Function klasa predstavlja nasu prijenosnu funkciju sustava.

 

Definirajmo prvo kako ce nam pojedino rjesenje, tj. kromosom izgledati. S obzirom da cemo za prikaz koristiti brojeve s pomicnim zarezom, sasvim je logicno da nam se kromosom sastoji od pet gena, svaki za jedan koeficijent. Uz to, kod generacijskog GA trebat ce nam i prazna populacija tako da ce nam konstruktor Chromosome klase izgledati ovako:

def __init__(self, empty=False):
    if empty is False:
        self.values = [uniform(-3, 3) for i in range(5)]
        self.badness = 0
    else:
        self.values = [0, 0, 0, 0, 0]
        self.badness = 0

Ukoliko stvaramo "prazan" kromosom, vrijednosti gena postavljamo sve na nulu. U suprotnom, stvaramo listu od pet realnih brojeva uniformno nasumicno izabranih iz intervala [-3, 3] (ovakva lijepa, sazeta for petlja unutar liste naziva se "list comprehension" i karakteristicna je za Python).

S kromosomom smo zapravo gotovi. U kodu postoji jos i overrideanje metoda za usporedbu kromosoma, ali to je za ovu pricu manje bitno. Sljedece, definirajmo kako izgleda Function klasa:

class Function(object):
    def calculate(self, x, betas):
        return (betas[0] * x**4 - betas[1] * x**3 -
                betas[2] * x**2 + betas[3] * x - betas[4])

Ova klasa je takoder veoma jednostavna, sve sto radi je da pomocu metode calculate() izracuna vrijednost funkcije za zadani x i zadane koeficijente. Pomocu te metode racunat cemo srednju kvadratnu pogresku koja ce nam biti mjera kvalitete, tj. nekvalitete pojedinog rjesenja.

Sad ide ono glavno, GeneticAlgorithm klasa. Za pocetak cemo napraviti samo generacijski GA, a on je i nesto kompliciraniji od eliminacijskog po kolicini koda. Definirajmo prvo operatore. Vec smo prije naveli neke koje mozemo koristiti pa ih idemo sada i implementirati. Uzmimo prvo operator krizanja. Ova metoda primat ce vjerojatnost krizanja te dva roditelja. Implementirat cemo ju na nacin da stvori dva djeteta:

def simple_arithmetic_recombination(self, x_prob, parent1, parent2):

    child1 = Chromosome(empty=True)
    child2 = Chromosome(empty=True)

    if random() <= x_prob:
        x_point = randint(1, len(parent1.values) - 1)

        for i in range(x_point):
            child1.values[i] = parent1.values[i]
            child2.values[i] = (parent2.values[i] + parent1.values[i]) / 2

        for i in range(x_point, len(parent1.values)):
            child1.values[i] = (parent1.values[i] + parent2.values[i]) / 2
            child2.values[i] = parent2.values[i]
    else:
        for i in range(len(parent1.values)):
            child1.values[i] = parent1.values[i]
            child2.values[i] = parent2.values[i]

    return child1, child2

Dakle, stvorimo dva "prazna" kromosoma i ukoliko random() metoda vrati broj manji ili jednak vj. krizanja odredujemo tocku prekida izmedu prvog i predzadnjeg gena (nema smisla prekidati kromosom ispred prvog gena, tj. na nultom genu ili poslije zadnjeg gena). Zatim radimo vec opisani postupak, do tocke prekida prvom djetetu pridjeljujemo gene prvog roditelja, a drugom pridjeljujemo aritmeticku sredinu vrijednosti gena oba roditelja. Od tocke prekida do kraja radimo obrnuto. Ukoliko do krizanja ne dode dobit cemo kopije roditelja.

Sljedeci operator koji cemo implementirati je operator mutacije:

def simple_mutation(self, mu_prob, child):
    for i in range(len(child.values)):
        if random() <= mu_prob:
            child.values[i] = uniform(-3, 3)

Valjda najjednostavnija metoda xD. Prolazimo kroz kromosom i za svaki gen provjeravamo hocemo li ga mutirati ili ne. Ukoliko da, zamjenjujemo ga s nekom nasumicno uniformno odabranom vrijednoscu. Ovakva implementacija operatora mutacije nije najsretnija, ali posluzit ce za ovaj nas zadatak. Puno bolja implementacija bi bila npr., zbrojiti/oduzeti vrijednost iz normalne razdiobe.

Za operator selekcije koristit cemo k-turnirsku selekciju:

def choose_parent_ktournament(self, population, k):
    possible_parents = [choice(population) for i in range(k)]
    possible_parents.sort()

    return possible_parents[0]

Iako operator selekcije moze biti kompliciran, k-turnirska selekcija u svom najprostijem obliku je poprilicno jednostavna. Primamo populaciju i velicinu turnira k te na temelju toga iz populacije izvlacimo k jedinki metodom choice(). Sortiramo turnir te vratimo najbolju jedinku da bude roditelj. U kodu cete naci i implementaciju proporcionalne selekcije.

Jos jedna bitna metoda je metoda koja racuna dobrotu (u nasem slucaju lošoću) jedinke. Za nju smo rekli da cemo ju definirati kao srednju kvadratnu pogresku:

def evaluate_individual(self, chromosome, function):
    error_sum = 0
    for datum in self.data:
        error_sum += (function.calculate(
            datum[0], chromosome.values) - datum[1]) ** 2

    chromosome.badness = error_sum / self.data_size

Prilicno jednostavno i standardno. Prolazimo kroz sva mjerenja koja smo dobili (njih 250) i racunamo razliku izmedu onoga sto daje nase trenutno rjesenje i onoga sto je zapravo izmjereno te tako dobivenu razliku kvadriramo. Na ovaj nacin svaka pogreska bit ce nam pozitivna (zbog kvadrata), ali dobili smo jos jednu pogodnost. Malu razliku, tj. malu gresku kvadrat malo kaznjava, a vecu razliku, tj. vecu gresku kvadrat vise kaznjava. Drugim rijecima, nije isto kvadriramo li broj 0.5 (koji je mali i njegov kvadrat iznosi 0.25) ili broj 5 (koji je veliki te njegov kvadrat iznosi 25). Tako dobivene pogreske za svako mjerenje pozbrajamo i sve skupa podijelimo s brojem mjerenja. Ta velicina nam je mjera koliko je pojedino rjesenje lose. Cim manja lošoća tim bolje.

Ostale metode su pomocne metode za ucitavanje podataka mjerenja, za stvaranje inicijalne populacije, evaluaciju populacije, itd., naci cete ih sve u cijelom kodu. Ostao nam je jos glavni algoritam.

 

Prvo stvaramo dvije populacije, jednu populaciju s inicijalnim rjesenjima, drugu praznu te evaluiramo populaciju s rjesenjima:

population = self.create_population(self.population_size)
new_generation = self.create_population(self.population_size,
                                        is_empty=True)
self.evaluate_population(population, function)

 

Zatim u while petlji pokrecemo evolucijski proces:

while True:
    population.sort()
   
    if self.elite is True:
        self.copy_individual(population[0], new_generation[0])
        self.copy_individual(population[1], new_generation[1])

Sortiramo populaciju da lakse odredimo najbolje jedinke (sortiranje populacije inace nije potrebno) te ukoliko je elitizam ukljucen, u novu generaciju kopiramo dvije najbolje jedinke iz populacije.
Zatim punimo ostatak nove generacije djecom najboljih roditelja:

    for i in range(start_from, self.population_size // 2):
        parent1 = self.choose_parent_ktournament(population, 3)
        parent2 = self.choose_parent_ktournament(population, 3)
        child1, child2 = self.simple_arithmetic_recombination(
            self.crossover_prob, parent1, parent2)
        self.simple_mutation(self.mutation_prob, child1)
        self.simple_mutation(self.mutation_prob, child2)
        new_generation[2 * i] = child1
        new_generation[2 * i + 1] = child2

Dakle, prvo biramo dva roditelja k-turnirskom selekcijom, zatim od tih roditelja stvaramo dva djeteta koja potom obavezno mutiramo (ovo je bitno, u suprotnom GA ima tendenciju zaglavljivanja u lokalnom optimumu, a mi trazimo globalni). Nakon toga oba djeteta spremamo u novu populaciju.
Zatim mijenjamo mjesta staroj i novoj populaciji (ovo je svojevrsna optimizacija, na ovaj nacin samo na pocetku stvaramo dodatnu populaciju, svaki sljedeci put ju takoreci recikliramo) te evaluiramo novu populaciju:

    tmp_population = population
    population = new_generation
    new_generation = tmp_population

    self.evaluate_population(population, function)

Napomena: ovu zamjenu u Pythonu mozemo napisati i u jednoj liniji:

    population, new_generation = new_generation, population

Odabiremo najbolji kromosom, tj. najbolje rjesenje i ispisujemo ga (ispis sam ovdje ispustio):

    best_chromosome = population[0]
    for individual in population:
        if best_chromosome.badness > individual.badness:
            best_chromosome = individual

Ukoliko je zadovoljen uvjet prekida evolucijskog procesa, prekidamo ga:

    if best_chromosome.badness <= 1e-2 or generation == 10000:
        break

U ovom slucaju to su dva uvjeta: ili ako greska padne ispod 10^-2 (sto ce se tesko dogoditi kod ove f-je, ali greska se moze proizvoljno postaviti, ovisi kolika nas zadovoljava) ili ako odradimo 10000 generacija.

Trebamo imati na umu nesto sto sam ranije naveo: ovaj postupak je heuristicki postupak i sva rjesenja koja dobijemo su priblizna rjesenja. Dakle, ovdje se vise ne bavimo egzaktnim rjesavanjem, vec pribliznim. Kad zavrtite ovaj algoritam na svojem racunalu, lako je moguce da cete dobiti losije rezultate od mene. Ili bolje. Ili tu negdje. Zato je kod GA cesto potrebno vise uzastopnih pokretanja. Takoder, za rjesenja koja dobijemo ne mozemo nikako biti sigurni da li je to uopce globalni optimum. Ne mozemo biti sigurni da li je to uopce dobro rjesenje. No, iskustvo i praksa su pokazali da u vecini slucajeva GA ipak daju prilicno zadovoljavajuce rezultate.

 

Preporucam vam da se igrate i s parametrima, da mijenjate velicinu populacije, vjerojatnosti krizanja, mutacije, velicinu turnira i dr., te da vidite kako koji parametar utjece na kvalitetu rjesenja i brzinu pronalaska rjesenja. Kompletan kod s (relativno sturim) komentarima mozete naci ovdje kao i pripadajucu datoteku s mjerenjima (prvi stupac su ulazi, drugi stupac izlazi sustava).


Da vidimo konkretne rezultate generacijskog GA na ovom problemu koje sam ja dobio nakon par uzastopnih pokretanja:

----------

Current generation is: 10000

Solution badness is: 0.013574913401069845
Solution is: [1.0748090243876265, 1.0577070623418612, 2.2135841339807207, 1.0856079028850614, 0.9170838344073768]

----------


Nakon 10000 generacija greska se smanjila na gotovo pa manju od 10^-2 (sto smo postavili kao prvi uvjet) sto je odlicno. Kao rjesenja dobili smo:
a1 = 1.0748090243876265
a2 = 1.0577070623418612
a3 = 2.2135841339807207
a4 = 1.0856079028850614
a5 = 0.9170838344073768

Stvarni koeficijenti a1 do a5 (na temelju kojih sam sve generirao) su redom: 1, 1, 2, 1, 1.
Vidimo da je nas algoritam nasao poprilicno dobre aproksimacije. Kako to izgleda u odnosu na stvarnu f-ju:
 
Pa, nije lose! Gotovo pa pogodeno.

Htio bih staviti jos jednu zanimljivu vizualizaciju, šum kod mjerenja:
 
Ove tockice su ustvari vrijednosti koje je nas (nesavrseni) mjerni instrument izmjerio. Ako koga zanima, za generiranje mjernih podataka (sa šumom) i ovih grafova koristio sam numpy i matplotlib biblioteke za Python.

Eto, to bi bilo to zasad sto se tice GA (jos cu napraviti i eliminacijski GA), sad imate dosta dobru podlogu za daljnje ucenje i kratak uvid u jedan dio umjetne inteligencije. Slobodno komentirajte, diskutirajte, pitajte. Takoder, sad kad znate koeficijente f-je za vjezbu mozete probati preinaciti GA da trazi (globalni) minimum ove f-je: ovako odokativno sa slike, minimum se nalazi oko tocke T(1.4, -2.4).

Friday sub 26.12.2015 13:11

Nisam sve još pročitao (djeca me ubiše), ali imam jedno pitanje...

 

Dosta dugo sam radio za firmu u kojoj smo radili skoring kartice za banke i prateći softver. Da li je moguće primjeniti ovako nešto u tom slučaju. Konkretno, imaš npr 15 "svojstava" određenog broja ljudi koji su do sada tražili kredit i njihov dobar/loš "rezultat" odnosno podatak da li su uredno izvršavali svoje obveze. Pod svojstva mislim na podatke tipa dob, županija, plaća (u razredima), ima li npr amex karticu, koliko ima uzdržavanih članova obitelji, radi li supružnik, spol, itd...

 

Potrebno je iz svih tih podataka izračunati vjerojatnost defaulta odnosno napraviti nekakvu skoring šemu u kojoj će svatko dobiti određeni broj bodova od npr 100 do 300 s time da npr oni od 250-300 imaju izuzetno nizak probability of default (npr 2%) pa prema nekom većem postotku kako se skor snižava.

Moja bivša šefica koja je te modele radila je doktorirala na tome i bavi se time već dugo. Ali ono što ona radi je bitno drugačije od ovoga. Ne znam da li sam bio jasan, ali vjerujem da si me shvatio

1domagoj1 sub 26.12.2015 14:12
Friday kaže...

Nisam sve još pročitao (djeca me ubiše), ali imam jedno pitanje...

 

Dosta dugo sam radio za firmu u kojoj smo radili skoring kartice za banke i prateći softver. Da li je moguće primjeniti ovako nešto u tom slučaju. Konkretno, imaš npr 15 "svojstava" određenog broja ljudi koji su do sada tražili kredit i njihov dobar/loš "rezultat" odnosno podatak da li su uredno izvršavali svoje obveze. Pod svojstva mislim na podatke tipa dob, županija, plaća (u razredima), ima li npr amex karticu, koliko ima uzdržavanih članova obitelji, radi li supružnik, spol, itd...

 

Potrebno je iz svih tih podataka izračunati vjerojatnost defaulta odnosno napraviti nekakvu skoring šemu u kojoj će svatko dobiti određeni broj bodova od npr 100 do 300 s time da npr oni od 250-300 imaju izuzetno nizak probability of default (npr 2%) pa prema nekom većem postotku kako se skor snižava.

Moja bivša šefica koja je te modele radila je doktorirala na tome i bavi se time već dugo. Ali ono što ona radi je bitno drugačije od ovoga. Ne znam da li sam bio jasan, ali vjerujem da si me shvatio

Da, to se radi iako ne bas pomocu GA (mislim, moguce je no po mom iskustvu ne toliko cesto u praksi).

Ovo sto ti opisujes spada pod jednu drugu granu ovog polja koja se naziva strojno ucenje (engl. machine learning), tocnije radi se o algoritmima (nadziranog) ucenja koji se bave klasifikacijom. Nahranis ih hrpom podataka te na temelju toga oni izvuku neko znanje koje ti je korisno, odnosno kod klasifikacije grupiraju podatke u razlicite klase na temelju njihovih znacajki. Postoje razni algoritmi za tu namjenu (logisticka regresija, SVM...), a cesto se znaju koristiti i umjetne neuronske mreze.

 

Ako sam te dobro shvatio, a po svemu kako si opisao situaciju, to mi lici na to.

anndrej sub 26.12.2015 14:19
Friday kaže...

Nisam sve još pročitao (djeca me ubiše), ali imam jedno pitanje...

 

Dosta dugo sam radio za firmu u kojoj smo radili skoring kartice za banke i prateći softver. Da li je moguće primjeniti ovako nešto u tom slučaju. Konkretno, imaš npr 15 "svojstava" određenog broja ljudi koji su do sada tražili kredit i njihov dobar/loš "rezultat" odnosno podatak da li su uredno izvršavali svoje obveze. Pod svojstva mislim na podatke tipa dob, županija, plaća (u razredima), ima li npr amex karticu, koliko ima uzdržavanih članova obitelji, radi li supružnik, spol, itd...

 

Potrebno je iz svih tih podataka izračunati vjerojatnost defaulta odnosno napraviti nekakvu skoring šemu u kojoj će svatko dobiti određeni broj bodova od npr 100 do 300 s time da npr oni od 250-300 imaju izuzetno nizak probability of default (npr 2%) pa prema nekom većem postotku kako se skor snižava.

Moja bivša šefica koja je te modele radila je doktorirala na tome i bavi se time već dugo. Ali ono što ona radi je bitno drugačije od ovoga. Ne znam da li sam bio jasan, ali vjerujem da si me shvatio

 Ako sam dobro sve shvatio Domagoja, naravno da je moguće, već je to opisao.

Ovaku u grubo, prvo počinješ od svoje bivše šefice i preuzmeš model po kojem je to radila, izrešetaš je pitanjima do zadnjeg atoma.

Napraviš matematički model evaluiranja, uzmeš iz arhive sve podatke o strankama(ulaz) i bodovima(izlaz) koje je napravila bivša šefica i sa tim podacima (ulaz) testiraš rad programa (izlaz) koliko se poklapa sa skorovima koje je napravila bivša šefica i fino naštimavaš parametre koje ćeš koristiti u genetskom algoritmu.

Sa vremenom i ti dobijaš "filing" u tom "twekanju".

Skoro pa možeš koristiti ovaj isti program koji je Domagoj dao, jedino je različit broj gena (15"svojstva") i drugačija funkcija mjere kvalitete (najzaguljeniji dio - glumi bivšu šeficu).

Lako moguće, možda sam  sve fulao 

bed sub 26.12.2015 14:46

Ti si jedan od rijetkih čije postove pročitam do kraja, ma kako dugi bili. Moj naklon..

Nemam pojima o tematici, ali mi se kao laiku čini da za simulaciju evolucije/selekcije u tom GA nedostaju vanjski faktori. Barataš njihovim osobinama, vjerojatnostima odabira i sl., dok u stvarnosti i okruženje djeluje na odabir. Recimo, jedinka ima najbolje osobine i vjerojatnost odabira, ali nađe se na krivom mjestu u krivo vrijeme i popapa ju tigar. Možda brijem, ali čini mi se da u ovoj evaluaciji/odabiru populacije nedostaju neki vanjski utjecaji..

 

1domagoj1 sub 26.12.2015 14:59
bed kaže...

Ti si jedan od rijetkih čije postove pročitam do kraja, ma kako dugi bili. Moj naklon..

Nemam pojima o tematici, ali mi se kao laiku čini da za simulaciju evolucije/selekcije u tom GA nedostaju vanjski faktori. Barataš njihovim osobinama, vjerojatnostima odabira i sl., dok u stvarnosti i okruženje djeluje na odabir. Recimo, jedinka ima najbolje osobine i vjerojatnost odabira, ali nađe se na krivom mjestu u krivo vrijeme i popapa ju tigar. Možda brijem, ali čini mi se da u ovoj evaluaciji/odabiru populacije nedostaju neki vanjski utjecaji..

Ovo naravno nije apsolutna imitacija evolucijskog procesa, vec je inspiracija izvucena iz tog procesa. U ovom slucaju, "vanjski faktori" su operator selekcije (koji stvara odredeni selekcijski pritisak - odnos vjerojatnosti prezivljavanja dobrih i losih jedinki, drugim rijecima, sposobnost prezivljavanja jedinki) i funkcija dobrote.

Ajar sub 26.12.2015 15:44

prvo, hvala domagoju na trudu i pohvala na znanju i načinu kako ga prenijeti papku (za te stvari) poput mene. sedmo, ja još tragam za prirodnom inteligencijom pa je umjetna daleko iza obzorja. osamdesettreće, a propos pravopisa i krivopisa, nalazim uputnijim prepisati njegov tekst s ispravljenim pogreškama (za osjetljive duše i kra[lje]fne na makovu zrnu) te takav objaviti u svojem postu (uz pripadajuću napomenu - give credit where the credit is due) nego mu davati jedinicu i roditelji u školu i pada na polugodištu pa neće dobiti bicikl. bljedoliki je zborio. 

1domagoj1 sub 26.12.2015 17:35

Evo, ovako, s obzirom da nisam nista dobio na pp - da se citiram: "No, dobro iako je ovo forum, a ne tiskano izdanje bilo kakve knjige/casopisa/negec treceg, prihvacam svaku sugestiju, samo posalji na pp sto smatras da treba ispraviti pa cemo ispraviti." - smatram svaku daljnju raspravu o gramatici irelevantnom, ali i dalje sam otvoren po tom pitanju no iskljucivo na pp (naravno da zelim da mi tekstovi budu cim kvalitetnije napisani) osim po pitanju dijakritickih znakova. Kao sto sam vec rekao, raspored tipaka mi je EN zbog programiranja i to mijenjam samo u slucaju pisanja "sluzbenih" dokumenata/tekstova.

Iz tog razloga zamolio sam Dannya da pocisti temu od svih offtopic postova, a ako se nastavi tim tonom da po potrebi i kartonira.

Friday sub 26.12.2015 18:07
bed kaže...

Ti si jedan od rijetkih čije postove pročitam do kraja, ma kako dugi bili.

 

 

Moja novogodišnja odluka je da čitam postove od ihush-a do kraja. Nisam siguran koliko ću izdržati...

 

EDIT:

Domagoj - šefica koristi upravo logističku regresiju u modeliranju. Vidim da znaš svakog qurca

gumifufna sub 23.1.2021 02:12

Sentimentalna analiza IMDB filmskih kritika koristeći RNN (Rekurentnu neuronsku mrežu) sa više slojeva

 

Primjena strojnog učenja za analizu sentimenta bavi se analizom izraženog mišljenja rečenice ili tekstualnog dokumenta. Ovde ćemo  implementirati višeslojni RNN za analizu sentimenta koristeći arhitekturu više-prema-jedan.

U sljedećem ćemo odjeljku implementirati RNN  za aplikaciju modeliranje jezika. Modeliranje jezika ima širok spektar zanimljivih aplikacija poput izgradnje chatbota - dajući računalima mogućnost izravnog razgovora i mogu da komuniciraju s čovjekom.

 

  1. Priprema podataka

Ovde ćemo koristiti “čisti” dataset : ‘movie_data.csv’, koji ćemo pomoću biblioteke Pandas pretvoriti u DataFrame za lakšu manipulaciju.

 

import pyprind import pandas as pd

from string import punctuation

import re import numpy a snp

df=pd.read_csv('movie_data.csv',encoding='utf-8')

print(df.head(3))

 

Ovaj DataFrame ima 2 kolumne: “review” i “sentiment”, gdje review sadrži tekst same kritike filma, a sentiment ima 2 labela: 0 i 1.

Na osnovu toga želimo napraviti RNN model da procesira riječi iz svake sekvence, te na kraju ih klasificira u 0 ili 1 klasu.

 

 

Da bi pripremili podatke za ulaz u Neuronsku mrežu,  moramo ih kodirati u numeričke vrijednosti. Da bismo to uradili, moramo naći unikatne riječi u cijelom datasetu, što možemo odraditi sa set-ovima, ali je puno lakše to uraditi sa Counter paketom.

U kodu što ćemo slijedi, definirat ćemo  objekat iz klase Counts koja skuplja broj pojavljivanja svake unikatne riječi u tekstu.

Zatim ćemo mapirati u formu “dictionary-ja” koji mapira svaku našu unikatnu riječ u naš Dataset, u unikatni integer broj.

 

from collections importCounter

counts=Counter()

pbar=pyprind.ProgBar(len(df['review']),

   title='Counting words occurences')

fori,reviewinenumerate(df['review']):

   text=''.join([cifcnotinpunctuationelse' '+c+' ' \

     forcinreview]).lower()

   df.loc[i,'review']=text

   pbar.update()

   counts.update(text.split())

 

word_counts =sorted(counts,key=counts.get,reverse=True)

print(word_counts[:5])

word_to_int={word:iiforii,wordinenumerate(word_counts,1)}

 

mapped_reviews=[]

pbar=pyprind.ProgBar(len(df['review']),title='Map reviews to ints')

forreviewindf['review']:

   mapped_reviews.append([word_to_int[word]forwordinreview.split()])

   pbar.update()

 

 

Zasad smo pretvorili sekvencu riječi u sekvencu integera(cijelih brojeva).

Problem je što sekvence imaju različite dužine, radi ulaznih podataka u RNN mrežu. Zato smo manualno podesili parametar sequence_length na 200. Stoga će sekvence duže od 200 riječi biti setovane na defoltnih 200.

Preprocesiranje ćemo podijeliti u 2 koraka:

- Kreiranje matrice sa nulama, čiji svaki red odgovara veličini sekvence od 200.

- Napuniti index riječi u svakoj sekvenci od desne strane matrice, tako ako sekvenca ima 150 riječi, prvih 50 ostaju nule.

 

Možemo primjetiti da parametar sequence_length , možemo tunirati radi bolje preciznosti i performansi modela.

 

Nakon što je Dataset preprocesirana, naš model možemo podijeliti u train i test dio:

 

sequence_length=200## sequence length (or T in our formulas)

sequences=np.zeros((len(mapped_reviews),sequence_length),dtype=int)

fori,rowinenumerate(mapped_reviews):

   review_arr=np.array(row)

   sequences[i,-len(row):]=review_arr[-sequence_length:]

X_train=sequences[:25000,:]

y_train=df.loc[:25000,'sentiment'].values

X_test=sequences[25000:,:]

y_test=df.loc[25000:,'sentiment'].values

 

np.random.seed(123)# for reproducibility

 

## Function to generate minibatches:

defcreate_batch_generator(x,y=None,batch_size=64):

   n_batches=len(x)//batch_size

   x=x[:n_batches*batch_size]

   ifyisnotNone:

     y=y[:n_batches*batch_size]

   foriiinrange(0,len(x),batch_size):

    ifyisnotNone:

      yieldx[ii:ii+batch_size],

      y[ii:ii+batch_size]

    else:

      yieldx[ii:ii+batch_size]

 

  1. Embedding(tehnika učenja feature-a)

Tijekom preprocesiranja, generirali smo sekvence iste dužine.

Elementi ovih sekvenci su cijeli brojevi koji korespondiraju kao indeksi unikatnih riječi.

Indeksi riječi mogu biti pretvoreni u ulazne feature-a na više načina.

Jedan od načina je One-hot encoding koji pretvara indekse u vektore jedinica i nula.

Elegantniji način u ovom slučaju je da mapiramo svaku riječ u vektor fiksne veličine sa realnim vrijednostima elemenata.

Tako možemo iskoristiti te vektore da reprezentiraju beskonačan broj realnih brojeva.

 

To je ideja iza takozvanog Embeddinga što je tehnika učenja featura, koje možemo upotrijebiti ovdje automatski za učenje feature-a da predstavljaju riječi u našem Datasetu.

Embedding smanjuje dimenzionalnost prostora feature-a.

 

Tensorflow implementira efikasnu funkciju (tf.nn.embedding_lookup), koja mapira svaki cijeli broj u odgovarajuću unikatnu riječ, u red ove trenirane matrice.

 

  1. Pravljenje RNN modela

 

Sada ćemo implementirati SentimentRNN klasu:

- Build metoda deklarira 3 placeholdera za ulazne podatke, ulazne labele, i keep-probability za konfiguraciju hidden (skrivenih) slojeva.

- Train metoda kreira Tensorflow Sesiju za pokretanje grafa izračunavanja , ponavlja se kroz mini-batch podatke i pokreće za postavljen broj epocha.

- Predikcijska metoda kreira novu Sesiju, nalazi zadnju sačuvanu točku iz procesa treniranja i donosi predikcije za testne podatke.

 

import tensorflow as tf

classSentimentRNN(object):

   def__init__(self,n_words,seq_len=200,lstm_size=256,num_layers=1,batch_size=64,learning_rate=0.0001,embed_size=200):

     self.n_words=n_words

     self.seq_len=seq_len

     self.lstm_size=lstm_size

     ## number of hidden units

     self.num_layers=num_layers

     self.batch_size=batch_size

     self.learning_rate=learning_rate

     self.embed_size=embed_size

     self.g=tf.Graph()

     withself.g.as_default():

      tf.set_random_seed(123)

      self.build()

      self.saver=tf.train.Saver()

      self.init_op=tf.global_variables_initializer()

   defbuild(self):

     ## Define the placeholders

     tf_x=tf.placeholder(tf.int32,shape=(self.batch_size,self.seq_len),name='tf_x')  

     tf_y=tf.placeholder(tf.float32,shape=(self.batch_size),name='tf_y')

     tf_keepprob=tf.placeholder(tf.float32,name='tf_keepprob')

## Create the embedding layer

     embedding=tf.Variable(tf.random_uniform((self.n_words,self.embed_size),minval=-1,maxval=1),name='embedding')

     embed_x=tf.nn.embedding_lookup(embedding,tf_x,name='embeded_x')

## Define LSTM cell and stack them together

     cells=tf.contrib.rnn.MultiRNNCell(

      [tf.contrib.rnn.DropoutWrapper(

         tf.contrib.rnn.BasicLSTMCell(self.lstm_size),

      output_keep_prob=tf_keepprob)

      foriinrange(self.num_layers)])

## Define the initial state:

   self.initial_state=cells.zero_state(self.batch_size,tf.float32)  

   print(' << initial state >> ',self.initial_state)

   lstm_outputs,self.final_state=tf.nn.dynamic_rnn(cells,embed_x,initial_state=self.initial_state)

## Note: lstm_outputs shape:

## [batch_size, max_time, cells.output_size]

print('\n << lstm_output >> ',lstm_outputs)

print('\n << final state >> ',self.final_state)

## Apply a FC layer after on top of RNN output:

logits=tf.layers.dense(inputs=lstm_outputs[:,-1],units=1,activation=None,name='logits')

logits=tf.squeeze(logits,name='logits_squeezed')

print('\n << logits >> ',logits)

y_proba=tf.nn.sigmoid(logits,name='probabilities')

predictions={'probabilities':y_proba,'labels':tf.cast(tf.round(y_proba),tf.int32,name='labels')}

print('\n << predictions >> ',predictions)

## Define the cost function

cost=tf.reduce_mean(tf.nn.sigmoid_cross_entropy_with_logits(labels=tf_y,logits=logits),name='cost')

## Define the optimizer

optimizer=tf.train.AdamOptimizer(self.learning_rate)

train_op=optimizer.minimize(cost,name='train_op')

deftrain(self,X_train,y_train,num_epochs):

   withtf.Session(graph=self.g)assess:

     sess.run(self.init_op)

     iteration=1

     forepochinrange(num_epochs):

       state=sess.run(self.initial_state)

 

    forbatch_x,batch_yincreate_batch_generator(X_train,y_train,self.batch_size):

      feed={'tf_x:0':batch_x,'tf_y:0':batch_y,'tf_keepprob:0':0.5,self.initial_state:state}

      loss,_,state=sess.run(['cost:0','train_op',self.final_state],feed_dict=feed)

    ifiteration%20==0:

      print("Epoch: %d/%d Iteration: %d ""| Train loss: %.5f"%(epoch+1,num_epochs,iteration,loss))

      iteration+=1

    if(epoch+1)%10==0:

       self.saver.save(sess,"model/sentiment-%d.ckpt"%epoch)

defpredict(self,X_data,return_proba=False):

   preds=[]

      withtf.Session(graph=self.g)assess:

        self.saver.restore(sess,tf.train.latest_checkpoint('model/'))

        test_state=sess.run(self.initial_state)

        forii,batch_xinenumerate(

           create_batch_generator(X_data,None,batch_size=self.batch_size),1):

           feed={'tf_x:0':batch_x,'tf_keepprob:0':1.0,self.initial_state:test_state}

        ifreturn_proba:

           pred,test_state=sess.run(['probabilities:0',self.final_state],feed_dict=feed)

        else:

           pred,test_state=sess.run(['labels:0',self.final_state],feed_dict=feed)

        preds.append(pred)

   returnnp.concatenate(preds)

 

Train metoda:

 

n_words=max(list(word_to_int.values()))+1

 

rnn=SentimentRNN(

    n_words=n_words,

    seq_len=sequence_length,

    embed_size=256,

    lstm_size=128,

    num_layers=1,

    batch_size=100,

    learning_rate=0.001)

 

rnn.train(X_train,y_train,num_epochs=40)

 

 

Test

 

## Test:

preds=rnn.predict(X_test)

y_true=y_test[:len(preds)]

print('Test Acc.: %.3f'%(np.sum(preds==y_true)/len(y_true)))

 

 

Rezultat preciznosti predikcije je: 86%, što na uzeti mali dataset je zadovoljavajući rezultat.

Možemo dodatno optimizirati rezultat, tunirajući hiperparametre (lstm_size, seq_len, embed_size, ...) da bi ostvarili još bolju preciznost predikcije.