Elektrotehnicki fakultet Univerzitet u Beogradu Doktorska disertacija SAMOORGANIZUJUCE NEURALNE MREZE ZA ANALIZU GLAVNIH KOMPONENATA Mr Marko V. Jankovic, dipl. inz. el. Beograd, 2006. Elektrotehnicki fakultet Univerziteta u Beogradu Mr Marko V. Ј ankovic, dipl. inz. el. SAMOORGANIZUJUCE NEURALNE MREZE ZA ANALIZU GLAVNIH KOMPONENATA Doktorska disertacij а Datиm иsmene odbrane: 23. 03. 2006. Komisija: Dr Branimr Reljin, red. prof. Elektrotehnickog fakиlteta и Beogradи, mentor Dr Srdan Stankovic, red. prof. Elektrotehnickog fakиlteta и Beogradи Dr Dragan Kandic, red. prof. Masinskog fakиlteta и Beogradи Dr Irini Reljin, docent Elektrotehnickog fakиlteta и Beogradи Dr Zeljko Dиrovic, van. prof. Elektrotehnickog fakиlteta и Beogradи Apstrakt - Ovaj rad ј е posvecen jednostavnim Ьioloski verovatnim algoritmima za ekstrakcijи glavnih!sporednih komponenata i/ili njihovih potprostora iz kovarijansne matrice иlaznog signala, kao i pronalazenjи generalnog metoda za transformacijи metoda za anal izи glavnih i sporednih potprostora и metode za analizи glavnih i sporednih komponenata. Proиcavane sи jednostavne, homogene neuralne mreze, bazirane na lokalnim izracunavanj ima, sto sve zajedno daje dobrи osnovи za jednostavnи implementacijи и paralelnom hardverи. Teorijski doprinos ovog rada se ogleda и sledecem: - pokazano је da direktna primena Hebovog zakona ne dovodi do divergencije sinaptickog vektora ako se taj zakon primeni na mrezi odgovarajиce strukture; - predlozena је strиktura neuralne mreze za izracиnavanje PSA, koja је и mnogo сети slicna sa strukturom dela retine kod riЬa; - prikazan је generalni metod koji transformise PSAIМSA metode и РСА!МСА metode i tako omogиcava formiranje veoma velikog broja novih РСА!МСА algoritama. Koriscenjem ove transformacije mogиce је formiranje homogenih algoritama na bazi Hebovog zakona исеnја, koji koriste samo lokalno dostиpne podatke za modifikacijи vrednosti sinapticke matrice, i koji Ьi onda mogli Ьiti smatrani za Ьioloski verovatne. Prakticna primena originalnih metoda koje sи predlozene и ovom radи se moze na6i и mogиcem modelovanjи racиnskih principa koji se koriste и realnim neuralnim mrezama i kod jednostavne realizacije PSAIМSA ili РСА/МСА algoritama и paralelnom hardveru. "Unsupervised neural networks for principal component analysis" Abstract - This thesis is devoted to the simple Ьiologically plaиsiЬle algorithms for extraction of the principal/minor components/sиbspace from inpиt signal covariance matrix, as well as discovery of а general method that transforms principal/minor sиbspace analysis methods into principal/minor component analysis methods. Analyzed neural networks are simple, their strиcture is homogeneoиs and proposed leaming rиles are based on local calcиlations. These features make proposed neural networks sиitable for implementation in parallel hardware. Theoretical contriЬиtions ofthis thesis are: - It is shown that direct implementation of the basic HebЬian scheme woиld not lead to ишealistic growth of the synaptic strengths, thanks to the adopted network structure; - Proposition of the PSA algorithm which is implemented in а neural network whose strиcture shows high degree similarity with а part ofthe fish retina wiring; - А new method which transforms PSAIМSA methods into РСА!МСА methods is proposed. Ву implementation of this method it is possiЬle to create а Ьig nиmber of new Р СА/М СА methods. Also, иsе of the proposed transformation facilitates creation of homogeneoиs algorithms based on Hebbian leaming rule, which иsе only locally available information for modification of synaptic matrix, and which coиld Ье, conseqиently, considered as а biologically plaиsiЬle. Practical implementation of the proposed methods coиld Ье foиnd in modeling of the general compиtational principles which are иsed in real neural networks, as well as in construction of simple neural networks for PSAIМSA or РСА!МСА which are sиitable for realization in parallel hardware. "Самоорганизующиеся нейроннъ1е сетьи для анализа главных :комnонентов" Zahvaljujem se mentoru prof. dr Branimiru Reljinu na dragocenim savetima koje mi је pruzio prilikom pisanja ovog rada. Zahvaljujem se prof. dr Itsuko Teruoka na pomoCi u pronalazenjн istrazivacke pozicije na Saitama Univerzitetu i Elektrotehnickoj laboratoriji u Tsukubi. Istrazivanja koja sam obavljao tamo su direktno uticala na izbor oЬlasti kojom se bavi ova disertacija. Zahvaljнjem se prof. dr Hidemitsuu Ogawi na savetima koji su pomogli da neki od mojih rezultata istrazivanja postanu razumljiviji. Takode, zahvaljujem mu se sto mi је omogucio jednomesecni boravak na Tokyo Institute ој Technology i tako mi olaksao postizanje rezultata koji sн vezani za vremenski orijentisan hijerarhijski metod. Zahvaljujem se svojim kolegama iz Centra za automatiku i regulaciju Instituta «Nikola Tesla», koji su mi profesionalnim i prijateljskim odnosom omogucili da, uz brojne redovne obaveze, pronadem dovo~no vremena i energije za pisanje ove teze. Posebno bih se zahvalio kolegama Predragu Ninkovicu, Zoranu Ciricu, Jasni Dragosavac i Vladimiru Vukicu. Zahvalio bih se i Marijanu Stojkovicu na pomoci koju mi је pruzio prilikom realizacije grafickih resenja i animacija koje su pratile moja izlaganja na konferencijama i pri odbrani teze. Zahvaljujem se svojim roditeljima na pomoci i razumevanju tokom izrade ove teze. Bez njihove pomoCi ovaj proces bi Ьiо svakako mnogo tezi i dugotrajniji. Zahvaljujem se svojoj supruzi Cije su razumevanje i podrska u svakom trenutku Ьili od velikog znacaja za zavrsetak ove teze. Njena povremena podsecanja da Ьi proces pisanja trebao da se okonca su, konacno, dovela i do zavrsetka ovog rada. Iako је ovaj rad rezultat originalnih naucnih ideja, on је u stvari samo interpretacija nekih prica u kojima me је moja nana, moj najvaznф ucitelj i najbolji prijatelj, ucila о tajnama zivota kao sto su ljubav i vreme. Ovaj rad posvecujem svojoj deci. I Vvoa I I o/estack? neura(ne mreie 2.1 Bioloski prototip 2.2 Vestacki пеиrоп 2.З Samoorgaпizиjиce пеиrаlпе mreie 2. 4 Razlike и primeпi samoorgaпizиjиCih пeиralпih mreia и оdпоsи па mreie koje исе pod пadzorom 2.5 Оsпоvпе kategorije samoorgaпizиjиCih пeuralпih mreia 2. 5.1 Samoorgaпizиjиce пeuralпe mreie baziraпe па staпdardпim statistickim Ј б 6 8 10 11 1З metodama 1З 2. 5.1.1 Hebov zakoп исепја 1З 2.5.1.20јiпzаkописепја 15 2.5.1.З Procesiraпje sigпala "па slepo "(BSP) 16 2.5.2 Samoorgaпizujuce пеиrа!пе mreie i klasterovaпje podataka 19 III ./lnaCiza gCavnifi i sporeanifi kJymponenata 22 З.l Aпaliza glavпih kompoпeпata (РСА) 22 З.1.1 Odredivaпje sopstveпih vredпosti 22 З.1.2Рrосепа kovarijaпsпe matrice 25 З.2 Potprostori sigпala i suma- automatski izbor dimeпzije РСА 27 З. З Оsпоvпе osoblпe РСА Зl З.4 Ekstrakcija glavпih kompoпeпta korisceпjem priпcipa optimalпe kompresije-rekoпstrukcije ЗЗ З.5 Osпovпefuпkcije сепе i adaptivпi algoritmi za РСА З6 З. 5.1 Rejlijev koeficijeпt- оsпоvпе osoblпe З6 З.5.2 Оsпоvпе fиnkcije сепе zasekveпcijalпo izracuпavaпje glavпih i sporedпih kompoпenata З8 З. 5. З Brzi РСА algoritam baziran па pиver metodu 4 Ј 3.5.4 Jnverzпi iterativпi pmver metod 4-1 З.5.5 Robusпa РСА 45 З.6 Adaptivпi algoritmi za sekveпcijalпu ekstrakciju sporedпih kompoпeпata 49 Io/ CI>arafe(ni a(goritmi za estimaciju gCavnifi R,slmponenata, sporeanifi R,slmponenata i njiliovifi potprostora 4.1 Funkcija cene za paralelnu ekstrakciju glavnih komponenata i njihovih potprostora 4.2 Potprostorni algoritam 4.3 Gradijentfunkcije cene J(W) 4.4 Analiza stabllnostipredloienog algoritma о/ (]3ioCosRj verovatan zaR,sln ucenja za izracunavanje aominantne gCavne R,slmponente 5.1 Jednostavan Ьioloski verovatan се() Н model neurona 5.2 Matematicka analiza се() Н algoritma 5.3 Poreilenje sa nekim poznatim algoritmima za ekstrakciju dominantne glavne komponente 5.4 Generalizacija predloienog algoritma za slucaj mreia sa vise izlaza 5.5 Analiza и slucaju kada ulazna sekvenca пета srednju vrednost nula o/I :Мoaullsani Jfeбov (:м:н) metoa- бioCosRj verovatan metoa za izracunavanje gCavnog potprostora (CFSJf.) 6.1 Matematicka analiza МН metoda 6.2 Poreilenje usvojene strukture sa delom retine kod riba 6.3 Modulisani НеЬ-Оја zakon ucenja 6.4 Matematicka analiza МНО metoda 6.5 Rezultati simulacija 6.6 Poгeilenje sa poznatim PSA algoгitmima о/Ј I o/remensRj orijentisan liijerarfiijsRj metoa (ТОЈf:М) za izracunavanje CFc;I i :Мс;I 7.1 Matematicka analiza predloienog principa 7.2 Jedan pгimer primene ТОНМ metoda za РСА 7.3 Analiza asimptotske staЫ!nosti геsепја 54 54 58 62 67 69 70 74 83 86 87 89 92 96 98 99 110 112 119 124 128 134 7.4 Primer primene ТОНМ metoda za МСА 7.5 Generalizovani ТОНМ VIII Zak.!Juca{ Literatura 139 148 149 154 AIC ART вс м BIC BMU BSE BSP BSS EOF FA FLA FLIN FP GHA GTOHM ICA ILA LA MBD МСА MCD Lista ~ti1cenili sfi.racenica Akaike Information Criterion- Akaikeov informaiconi kriterijum Adaptive Resonant Theory- teorija adaptivne rezonancije Bienestock Cooper Mumo Bayesian Information Criterion - Bajesov informacioni kriterijum Best Mathcing Unit- najpriЫiznijajedinica Blind Signal Extraction - izdvajanje signala «na slepo» Blind Signal Processing - procesiranje signala «na slepo» Blind Signal Separation- razdvajanje signala «na slepo» Empirical Orthogonal Function- empirijska ortgonalna funkcija Factor Analysis - faktor analiza Family part ofthe Leaming Algorithm - «porodicni» deo algoritma za ucenje Foldiak Latteral lnhiЬition Network- Foldiakova mreza sa bocnom inhiЬicijom Family Part - porodicni deo General Hebbian Algorithm- opsti Hebov algoritam Generalized Time Oriented Hierarchical Leaming - generalizovani vremenski orijentisan hUerarhijski metod Independent Component Analysis - analiza nezavisnih komponenata lndividual part ofthe Leaming Algorithm- individualni deo algoritma za ucenje Leaming Algorithm- algoritam za ucenje Multichannel Blind Deconvolution - visekanalna dekonvolucija naslepo Minor Component Analysis- analiza sporednih komponenata Minimum Covariance Determinant- minimalna kovarijansna determinanta МDL м н мно MIВS MIMO MSA РСА PSA REC RК SEC SLA SMCA SNR SOM SPCA тонм WTA со ОН Minimum Description Lenght- minimalna duzina zapisa Modulated HebЬian- modulisani Hebov metod Modulated НеЬЬ Ој а- modulisani НеЬ-Оја Minka Bayesian model Selection- Minka-Bajesov metod za selekciju Modela Multiple-Input Multiple-Output- vise ulaza- vise izlaza Minor Subspace Analysis- analiza sporednog podprostora Principal Component Analysis - analiza glavnih komponenata Principal Subspace Analysis- analiza glavnog podprostora Recurrent Епоr Correction- rekurentna korekcija greske Rayleigh Quotient- Rejlijev koeficijent Symmetrical Епоr Coпection- simetricna korekcija greske Subspace Leaming Algorithm- podprostomi algoritam Single Minor Component Analysis- analiza najsporednije glavne komponente Signal-Noise Ratio- odnos signal sum Self-Organized Maps - samoorganizujuce mape Single Principal Component Analysis - analiza dominantne glavne komponente Time-Oriented Hierarchical Method- vremenski orijentisan hijerarhijski metod Winner Takes All - pobedniku pripada sve со Оја НеЬ 11 IPogCav{je Uvod Razumevanje principa izracunavanja koje koristi mozak za svoje funkcionisanje је jedan od najinteresantnijih i najtezih naucnih proЫema. Iako u nekoliko poslednjih decenija postoji veliki broj otkrica koja rasvetljavaju strukturu mozga na nekoliko razliCitih nivoa, jos uvek nije moguce razumeti na koji nacin nervni sistem omogucava coveku da vidi, cuje, uci, pamti dogadaje, planira aktivnosti ili donosi odluke. Istrazivanja na polju obrade slike, robotike i ostalih grana vestacke inteligencije su pokazala da i najjednostavniji zadaci koje mozak ljudi ili zivotinja obavlja bez skoro ikakvog napora, kao sto su prepoznavanje objekata, koordinacija pokreta, ili snalazenje i kretanje u nepoznatom okruzenju, predstavljaju veoma slozene racunske proЫeme. Smatra se da је glavni razlog za dosadasnji neuspeh svih masina koje је stvorio covek da emuliraju ili se bar malo priЬlize performansama zivotinja ili coveka, lezi u Cinjenici da је za resavanje i naizgled veoma jednostavnih proЫema potrebno veoma veliko znanje о statistickim i drugim karakteristikama signala koje iz okruzenja prikupljaju senzori (nasa cula). Sposobnost mozga da na osnovu tih znanja kodira signale, uCi i pristupa znanju (memoriji) na efikasan naCin predstavlja osnovu za njegovu sposobnost da efikasno resava mnogobrojne proЫeme . Racunarska nauka о neurologiji је naucna oЫast koja proucava kako se realni signali (elektricni i hemijski) koriste u mozgu u cilju ispravne reprezentacUe i obrade prikupUenih informacija. U сЩu pronalazenja resenja, obicno se koriste pojednostavljeni racunarski modeli koji bi trebalo da na nekom nivou apstrakcije eventualno omoguce shvatanje principa rada neuralnih mreza u nervnom sistemu. Glavna prednost takvih modela lezi u njihovoj intemoj konzistentnosti kao i cinjenici da mogu biti analizirani, bilo analiticki ili koriscenjem racнnarskih simulacija. Ј Ро ГavGe V voa 2 Pojednostavljeni modeli se veoma cesto koriste и razшm granama naиke . Isto tako, koriscenje иproscenih modela nervnog sistema omogиcava analizи osnovnih proЬlema (principa) izracunavanja Cije bi razиmevanje vodilo ka razиmevanjи рrшс1ра nekih od procesa izracunavanja koji se odvijajи и mozgи. Jedan od mogиcih pristupa је da se pri modeliranjи mozga pocne od nasih saznanj a iz anatomUe i psihologye i da se postepeno razvijajи modeli koji bi иkljиCivali sve vise i vise detalja, а koji Ьi se иbacivali na osnovи pretpostavki, и slисаји da ne postoje Cinjenice koje Ьi mogle da potvrde njihovo prisиstvo и mozgи. То је takozvani inverzni inzenjerski pristиp, cija је primena veoma teska cak i slисаји kada se radi о sistemima srednje slozenosti, i to cak i и slисаји kada znamo osnovne principe na kojima se sistem bazira. То је, na primer, slиcaj и роkиsаји otkrivanja osoЬina nepoznatog integrisanog kola. Naravno, sitнacija је mnogo slozenija kada se radi о mozgи. Zato se mnogo privlacnijom Cini ideja da se pode od pokиsaja da se identifikиjи cЩevi proracuna, razmotre mogиCi mehanizmi za realizacijи tih ciljeva i da se tek onda testira stepen slicnosti predlozenog modela i stvamog sistema. Takav model se od realnog sistema moze razlikovati и mnogim aspektima, ali је svakako nemogиce razиmeti kompleksan sistem bez razиmevanja nekih osnovnih principa na kojima је on baziran. U tom slисаји se modeliranje i testiranje sistema obavljajи istovremeno. Pri kreiranjи modela potrebno је napraviti veliki broj иproscavanja iz dva razloga- jedan cesto lezi и nedostatkи adekvatnog znanja о detaljima sistema, а drиgi и ogranicenim racunarskim resursima sa aspekta potrebnog vremena za testiranje pretpostavke. Medиtim , cak i и slиcajevima kada dva gore pomenиta proЬlema ne predstavljajи ogranicenje, jednostavniji model se moze smatrati pozeljnфm иkoliko dodatni detalji ne doprinose sиstinskom poboljsanjи modela. Model sa manje parametara је neprecizniji и modelovanjи dostupnih podataka ali ima vece izglede za korektnи generalizacijи novih podataka. IstrazivaCi и oЬlasti neuralnih mreza se и sиstini bave sledeCim proЬlemom : kako mreza jednostavnih procesnih jedinica koje imajи veliki broj medиsobnih veza moze da se иpotreЬi za izvodenje kompleksnih (ili barem netrivijalnih) izracиnavanja. Tipicno, vestacka neuralna mreza se sastoji od velikog broja jedinica koje imajи odredene slicnosti sa karakteristikama realnih neurona, kao sto sи medиsobne veze koje podsecajи na aksone i dendrite kao i promenljive tezine tih veza koje podsecajи na sinapse. Same jedinice najcesce obavljajи veoma jednostavna izracиnavanja (oЬicno izracиnavajи tezinskи sиmи иlaza) i dаји skalamи vrednost na izlazи koja se dalje prosledиje ka drugim jedinicama. I pored jednostavnosti osnovnih jedinica, mreze koje te jedinice Cine mogи izvrsavati veoma razliCita izracиnavanja, иsled velikog broja specificnih medиsobnih veza. Za razlikи od veCine konvencionalnih 2 з Ј Ро (щ;Gе - V votf. algoritama, neuralne mreze poseduju inherentnu sposobnost ucenja. Ucenje se obavUa modifikacijom veza koje spajaju pojedine jedinice, а modifikacija se obavlja na osnovu razliCitih algoritama za ucenje. Primenom takvih algoritama mreza se, u stvari, оЬнсаvа za izvodenje o'dredenih kompleksnih algoritama, umesto da Ьнdе programirana za nj ihovo izvodenje. Interesantno је da takvi algoritmi veoma cesto prevazilaze performanse konvencionalnih kompjuterskih programa, posebno u proЬlemima kao sto su obrada slike i govora ili prepoznavanje oЬlika, posto је za tu vrstu proЬiema veoma tesko formalizovati resenje proЬlema, а prema tome i napisati odgovarajuci program. Druga osobina neuralnih mreza је brzina odziva - u situaciji kada је mreza dobro obucena njen odziv је veoma brz, skoro trenutan. Za razliku od konvencionalnih racunarskih algoritama koji izracнnavaju resenje, neuralne mreze su sustinski bazirane na pamcenjн podataka i interpolaciji izmedu njih. Ukoliko se zeli koriscenje neuralnih mreza za modelovanje procesa izracunavanja u mozgu, moraju se napraviti odredene pretpostavke i onda izvrsiti provera da li one mogu biti podrzane ili odbacene na osnovu poznatih anatomskih i fizioloskih otkrica. Kako је trenutno poznavanje funkcionisanja nervnog sistema jos uvek na relativno niskom nivou, to otvara prostor za postavljanje velikog broja hipoteza koje se ne mogu definitivno ni potvrditi ni odbaciti. Postoji veliki broj hipoteza о potencijalnim mogucnostima izracнnavanja pojedinacnog neurona. Jedna od najcesce koriscenih hipoteza је da neuron vrsi lineamo sumiranje svojih ulaza. Iako su postojale i drugaCije pretpostavke (о mnogo vecoj sofisticiranosti izracunavanja koje obavlja neuron) obicno sн anatomske i fizioloske analize pokazivale da је racunarska sposobnost pojedinih neurona strogo ogranicena i da је izvestan stepen sofisticiranosti od sekundamog znacaja. Takode, pretpostavka о lineranom sumiranju izgleda prihvaЩiva imajuCi u vidu rezultate koje su objavili vizuelni neurofiziolozi za odziv veceg broja celija vizuelnog korteksa [Eшoth, 1966], [Movshon, 1978]. Druga pretpostavka koja se cesto koristi је da neuron komunicara sa ostalim neuronima, sa kojima је povezan, putem signala koji odgovara frekvenciji impulsa na njegovom izlazu (aksonu). Iako postoje pretpostavke da fina vremenska struktura impulsa predstavlja specifican kod [Cattaneo, 1981 ], [Dayhoff, 1983], [Sherry, 1982] detaljnijom analizom је dokazano [Douglas, 1988] , [Douglas, 1991], [Young, 1991] da, cak i slucaju da medнsobni polozaj impulsa nosi nekakvu kolicinu informacija, te informacUe su od sekundamog znacaja. Mozda najvaznija hipoteza oko modela vestackih neuralnih mreza, kao modela nervnog sistema, odnosi se na zakone нсеnја koji su odgovomi za modifikacijн sinaptickih vrednosti. 3 I Ро Гаvбе - Vvoa 4 Jedna od glavnih hipoteza је da zakon исеnја posedиje osobinи lokalnosti, sto znaci da modifikacija pojedinacne sinapse treba sto manje da se oslanja na informacije о vrednostima drиgih sinapsi pogotovo ako sи one vezane za drиge neurone. Za оvи pretpostavkи postoji sve veCi broj dokaza koji poticи iz istrazivanja biofizickih mehanizama odgovomih za proces исеnја и nervnom sistemи (na primer [Brown, 1990]). Deo nervnog sistema о kome se danas najvise zna је onaj deo koji prikиplja i obradиje informacije sa senzora (сиlа) . Iako jos иvek nije jasno kako mozak vrsi interpretacijи i koristi podatke sa miliona senzora, interesantno је da mi, kao ziva Ьiса, pri koriscenjи сиlа ne dozivljavamo informacije koje primamo sa tih senzora kao promene и pojedinim komponentama matrica signala, vec detektиjemo promene na nivoи objekata, sitиacija ili dogadaja и okruzenjи. Poznato је da signali iz naseg okrиzenja nisи potpиno slиcajni, vec da (kao na primerи сиlа vida) signali koji poticи od istog objekta imajи visok stepen korelacije i da sи razdvojeni objekti medиsobno relativno nezavisni. Na primer, skиpovi signala koji sи jako korelisani, kao sto sи leva i desna strana lica, ne smatrajи se razdvojenim objektima. Odatle је jasno da Ьi jedan naCin za razlikovanje objekata Ьiо trazenje skиpova signala koji роkаzији visok stepen medиsobne korelacije i istovremeno sи relativno nekorelisani sa drugim skиpovima. Smatra se da delovi mozga koji slиze za prijem signala sa senzora i njihovи inicijalnи obradи, kao sto је na primer retina, imajи zadatak da smanje redиndantnost komponenata иlaznog signala, kako Ьi se mogla napraviti njegova efikasnija reprezentacija. Osnovna ideja је da retina ili drugi slicni organi, imajи zadatak da izvrse inicijalnи dekorelacijи izmedи reprezentacionih jedinica (neurona), koje Ьi se kasnije, и sledecem stepenи procesiranja, svele na statisticki nezavisne jedinice, а za koje se veruje da Ьi omogиCile najefikasnije procesiranje и visim delovima korteksa. U ovom radи се Ьiti analizirani potencijalni mehanizmi za иklanjanje korelacije medи иlazriim signalima. Jedan od naCina da se to иcini је primena analize glavnih komponenata (РСА - engleski Principal Component Analysis). Bice predlozeno vise algoritama koji Ьi se mogli smatrati Ьioloski mogиcim РСА algoritmima. Као ekstenzije РСА algoritama Ьiсе razmatrani i analiza sporednih komponenata (МСА- engleski Minor Component Analysis) kao i analiza glavnih i sporednih potprostora (PSAIМSA- engleski Principal/Мinor Sиbspace Analysis). U drugom poglavljи је dat prikaz vestackih neuralnih mreza. Poglavlje se иglavnom bavi samoorganizиjиCim neuralnim mrezama. Ти sи objasnjeni glavni pravci razvoja i иkratko prikazani najpoznatiji modeli. Takode, tu се Ьiti objasnjena osnovna ideja na kojoj se bazira исеnје и samoorganizиjиcim neuralnim mrezama, а koja se ogleda и Hebovom zakonи исеnја. 4 5 Ј Ро [a:vfie - Vvocf. Definicija, podrucje primene i nacini realizacije РСА su analizirani u trecem poglavlju. U ovom poglavlju su prikazane najvaznije osobine РСА, objasnjeni osnovni principi za izracunavanje РСА i prikazani sekvencijalni algoritmi koji se koriste za izracunavanje РСА u neuralnim mrezama. Takode, ovo poglavlje sadrzi i definiciju МСА kao i prikaz osnovnih algoritama koji se koriste za sekvencijano izracunavanje МСА u neuralnim mrezama. Najznacajniji poznati algoritmi za paralelnu ekstrakcUu РСА (kao i analizu sporednih komponenata- МСА) н samoorganizujucim neuralnim mrezama се Ьiti prikazani u cetvrtom poglavlju. Poglavlja pet, sest i sedam sadrze originalni doprinos ovog rada. Peto i sesto poglavlje sadrze rezultate istrazivanja u vez1 sa Ьioloski verovatnim strнkturama i algoritmima za implementacijн PSAIPCA u neuralnim mrezama. U petom poglavlju је prikazan algoritam соОН za ekstrakciju dominantne glavne komponente koji zahvaljujuci usvojenoj strнkturi neuralne mreze omogucava direktnu primenu Hebovog zakona ucenja, bez uvodenja Ьilo kakvih dodatnih clanova za staЬilizaciju. ImajuCi u vidu da su sva izracunavanja bazirana na lokalno dostupnim vrednostima, ovaj algoritam se moze smatrati Ьioloski verovatnim. Sesto poglavlje sadrzi algoritme za izracunavanje PSA koji su nazvani МН (modulisani Hebov) i МНО (modulisani Heb-Ojin), i koji su inspirisani delom strukture retine kod riЬa. Ovi algoritmi koriste osnovni Hebov zakon sa dodatnim modulisucim clanom. Algoritam МН predstavlja ekstenziju соОН za slucaj kada је broj neurona na izlazu veCi od jedan, pri cemu su lokalne povratne veze zamenjene globalnom povratnom vezom. Algoritmi МН i МНО predstavljaju kompromis izmedu broja globalnih izracunavanja i brzine konvergencije neuralne mreze za izracunavanje PSA. Generalni metod za transformaciju metoda za analizu glavnih i sporednih potprostora u metode za analizu glavnih i sporednih komponenata је prikazan u sedmom poglavlju. Prema saznanjima autora i na osnovu raspolozive literature, ovaj metod је prvi metod takve vrste. Pokazano је da se PSA/МSA algoritmi mogu transformisati u РСА!МСА algoritme bez uvodenja nelinearnosti ili asimetrije u neuralnu mrezu. Princip koji omogucava ovu transformaciju se bazira na vremenski orijentisanoj hijerarhijskoj strukturi - razliCiti delovi algoritma se obavljaju na razliCitim vremenskim skalama. U zakljucku је data rekapitulacija rada i ukazano је na moguce pravce daljeg razvoJ a istrazivanja. Koriscena literatura ( oko 130 referenci) је prikazana na kraju ove disertacije . 5 II (JJogfav(je Vestacke neuralne mreze Vestacke neuralne mreze Sll razviJene u veoma razlicitim konfiguracijama. Uprkos velikom broju razliCitih konfiguracija sva resenja u mnogo сети imaju mnogo slicnosti. U ovom poglavlju се biti opisano sta se u najopstijem smislu podrazumeva pod vestackim neuralnim mrezama, pri cemu се akcenat biti stavljen na samoorganizujuce neuralne mreze. 2.1 Bioloski prototip Vestacke neuralne mreze su bioloski inspirisane - istrazivaci obicno misle na organizaciju mozga kada razmatraju nove strukture mreza i algoritme koji se u njima primenjuju. I tu negde se moze i zavrsiti prica о slicnosti izmedu Ьioloskih uzora i njihovih vestackih imitacija. Razlog za to је Cinjenica da se i pored velikog napretka u proucavanju mozga i njegovih principa rada, jos uvek prilicno malo zna о tome. Stoga је tesko naci principe koji Ьi sa sigumoscu Ьili pokazatelj о uspesnosti vestacke neuralne mreze u emulaciji pojedinih ili ukupnih funkcija mozga. Iz tog razloga, istrazivaci na polju neuralnih mreza moraju da pokusavaju da pronadu strukture koje mogu realizovati korisne funkcije, а koje bi na osnovu nekih dodatnih principa mogle Ьiti smatrane za manje ili vise verovatne modele delova ljudskog mozga Ljudski nervni sistem је sagraden od nervnih celija i njegova slozenost је veoma velika. Procenjeno је da oko 10 11 - 1012 nervnih celija ucestvuje u oko 1015 meduveza preko prenosnih puteva koji mogu Ьiti i do jednog metra duzine . Sve nervne celije imaju шnogo zajednickih osoЬina sa ostalim celijama u telu, ali poseduju jedinstvenu karakteristiku da su u stanju da prime, procesiraju i prosleduju elektrohemijske signale preko neuralnih veza koje cine komunikacioni sistem mozga. 7 11 Pog&zv[ze -Vestacke neuralne mreze. Slika 2.1 prikazuje strukturu para tipicnih bioloskih neurona. Dendriti (nervni zavrseci) se prostiru od tela celije ka drugim neuronima gde primaju signale na konekcionim tackama koje se nazivaju sinapse. Sa prijemnih strana sinapsi ti ulazi se odvode do tela celije . Tu se sumiraju, pri cemu neki signali imaju tendenciju da pobude celiju dok drugi imaju tendenciju da је inhiЬiraju. Kada kumulativna eksitacija prede odredeni prag, celija poCinje da generise izlaz u vidu povorke impulsa i tako putem aksona prosleduje signale ka drugim neuronima. Ovo predstavlja osnovni princip funkcionisanja nervne celije u odnosu na koji postoje brojni izuzeci. Bez obzira na to, veCina vestackih neuralnih mreza modeluje ovakav naCin rada. dendriti а) Ь) Slika 2.1 а) Prikaz para realnih neurona; Ь) uprosceni prikaz neurona telo celije 7 П PogГavfie-Vestacke neuralne mreze 8 2.2 Vestacki neuron Vestacki neuroni imaju zadatak da imitiraju osnovne karakteristike Ьioloskih neurona. U principu ulaze za pojedinacni neuron, predstavljaju izlazi drugih neurona. Svaki ulaz se mnozi sa odgovarajucom tezinom, koja predstavlja sinapticku «snagш>, i onda se svi ti ponderisani ulazi saЬiraju kako Ьi se doЬio ukupni aktivacioni nivo neurona. Slika 2.2 prikazuje model za implementaciju ove ideje. Ulazi, koji odgovaraju signalima na sinapsama, su oznaceni vektorom х (Cije su komponente х 1 , х2 , ... , хк). Signal је pomnozen sinaptickim vektorom 'v (koji Cine tezine w1, w2, .•. , vvк) i uveden u sumator I. Svaka tezina sinaptickog vektora odgovara «snazi» pojedinacne Ьioloske sinapticke veze. Sumacioni Ыоk priЫizno odgovara funkcUi tela nervne сеЩе. Sumator saЬira ponderisane ulaze algebarski i proizvodi izlaz koji је oznacen say. U kompaktnoj notaciji to se moze predstaviti sa х у = wтх. w, ~~L , . , : : ; wк · · w - т 1----- · ... у- w х Slika 2.2 Lineami model neurona (2.1) U mnogim modelima suma wтх se dalje procesira aktivacionom funkcUom F kako Ьi se proizveo izlazni signal у (vidi sliku 2.3). Na taj nacin se uzima u obzir nelineamost pojedinacnog neurona i oЫast zasicenja koj~je neizbezno prisutna u realnom slucaju. Takode, usvajanjem odgovarajuce nelineame aktivacione funkcije (kao sto su sigmoidalna funkcija ili tanh funkcija) moze se dati odgovor na neka pitanja kao sto је, na primer, pitanje postavljeno od strane Grosberga [Grossberg, 1973], а koje se tice na primer dileme sum/zasicenje - drugim recima, kako ista mreza moze da obraduje i male i velike signale. 8 9 11 Pogtavlie -Vestacke neuralne mreze. F х W TX ~-------.J·I _гlг----+---.. у ј 1 ~ w N ј ј ! V estacki neuron w ( .... .............. ............................................................................................. . Slika 2.3 Nelineami model neurona Naravno gore predlozeni model ne uzima u obzir brojne karakteristike realnog neurona kao sto su vremenska kasnjenja, koja uticu na dinamiku sistema, ili proЬlemi sinhronizma, ili frekvencijske modulacije signala. I pored toga sto ti nedostaci predstavljaju ogranicenja u modelovanju realnog neurona, ovaj model se smatra prihvatljivim jer mreze cija је on osnovna jedinica mogu procesirati signale i proizvoditi rezultate koji podsecaju na rezultate procesiranja realnih neurona. Vise medusobno povezanih neurona koji obavljaju specificnu funkcUu se nazivaJu neuralnom mrezom. Za sve neuralne mreze koje се biti analizirane u ovom radu, kao model neurona се biti prihvacen model prikazan na Slici 2.2. Bice izostavljeno procesiranje nelineamom aktivacionom funkcij om i ј ednacina (2 .1) се predstav lj ati vezu izmedu ulaznih signala i izlaza neurona. Takav model daje mogucnost formiranja neuralnih mreza Cije prenosne funkcije podsecaju na funkcije realnih neuralnih sklopova i to pre svega onih koje se bave prvostepenom obradom signala sa senzora (cula). u principu, vestacke neuralne mreze se dele ро nacinu ucenja na mreze koje uce pod nadzorom i samoorganizujuce neuralne mreze, koje се dalje biti analizirane u ovom radu. 9 П PogCav fie- Vestacke neuralne mreze 10 2.3 Samoorganizujuce neuralne mreze Samoorganizovanje predstavlja veoma dubok koncept koji moze Ьiti analiziran sa veoma razliCitih aspekata od psiholoskih ра do in:Z:enjerskih. Cesto se takav koncept naziva i ucenje bez uCitelja. То znaci da covek, zivotinja ili vestacki sistem uce iz informacUa koje dobUaju iz svog okruzenja (uglavnom putem senzora) i na osnovu tih informacija prilagodavaju svoje ponasanje bez dodatnih uputstava о tome kako da povezu svoja zapazanja sa zeljenim ponasanjem (sto је slucaj kod ucenja pod nadzorom) i bez ikakvih ideja da li је rezultujuce ponasanje ispravno ili ne (sto је slucaj kod reinforcement ucenja). OЬicno, rezultat ucenja bez nadzora је nova interpretacija ili reprezentacija ulaznih signala koja Ьi trebalo da rezultuje poboljsanim odzivom na slicne situacije ili na donosenje boljih odluka u buducnosti . u oblasti masinskog ucenja i vestacke inteligencije reprezentacija ulaznih podataka predstavlja skup koncepata i pravila koja povezuju te koncepte, sto omogucava simbolicko objasnjenje podataka. U oblasti vestackih neuralnih mreza reprezentacija moze predstavljati grupisanje podataka, diskretno mapiranje ili kontinualno nizedimenziono projektovanje na mnogostrukost u vektorskom prostoru definisanom ulaznim podacima, Ciji је moguCi zadatak objasnjenje strukture podataka ili otkrivanje medusobnih zavisnosti. Prema dosadasnjim istrazivanjima, izgleda da је samoorganizovanje osnovni mehanizam koji se koristi u takozvanom vizuelnom putu u mozgu [Foldiak, 1991], а koji omogucava adaptaciju na senzome signale (u smislu reprezentacije i posledicnog izvodenja odgovarajuCih aktivnosti). Sa in:Z:enjerske tacke gledista, predstavlja jedan od obecavajucih i veoma mocnih pristupa za neke prakticne probleme u vezi sa procesiranjem podataka, kao sto su data mining i otkrivanje znanja u velikim bazama podataka, ili otkrivanje novih naCina interakcUe izmedu coveka i racunara, а koji omogucavaju da se softver prilagodi potrebama i navikama individualnog korisnika na osnovu pracenja njegovog ponasanja. Ovde cemo se iskljuCivo baviti samoorganizujucim mrezama koje se primenjuju u oЬlasti analize signala i podataka. Naravno, Ьiсе reci samo о glavnim principima i kategorijama samoorganizujuCih mreza. 10 11 11 Pogtav(z'e -Vestacke neuralne mreze. 2.4 Razlike и primeni samoorganizиjиCih neиralnih mreza и odnosи па neиralne mreze koje исе pod nadzorom Startnu tacku za ucenje u vestackim neuralnim mrezama predstavljaju skupovi numerickih vektora podataka za ucenj a, koji su tipicno velikih dimenzija. Mreze koje uce na bazi skupa podataka za obucavanje kao i skupa zeljenih ostvarenih vrednosti se nazivaju mreze koje uce pod nadzorom. Tipicni predstavnici te vrste mreza su viseslojni perceptron i radial basis mreze. Svrha ucenja је formiranje nelinearnog mapiranja izmedu ulaza i izlaza koriscenjem baze podataka za ucenje (i za ulaz i za izlaz). Ovakve mreze se primenjuju u oЬlastima kao sto su prepoznavanje slike, teksta ili govora, industrijska dijagnostika, monitorisanje stanja, modelovanje kompleksnih Ыасk Ьох kontrolnih sistema kao i analiza signala. Ulazi su obicno vektori koji su dobijeni odabiranjem karakteristicnih signala, dok izlazi predstavljaju ili klase signala koje su kodirane kao binarni vektori, ili neka vrsta zeljenog odziva koji se moze predstaviti numerickim vektorima. Tipicno, ucenje је kompletno bazirano na skupovima podataka za ucenje, bez ikakve dodatne informacije о tome koja је pozeljna nelinearna funkcija koja sluzi za klasifikaciju ili aproksimaciju. Вlack Ьох modelovanje је prikazano na Slici 2.4. U mnogim realnim proЬlemima kao sto su: analiza slike, data mining, istrazivacka analiza podataka ili modelovanje velikih kompleksnih sistema, dimenzije ulaza sistema su reda stotina i hiljada, i funkcya koja treba da se aproksimira је veoma nelinearna i kompleksna. U tom slucaju se od mreze zahteva da ima veliki broj parametara kako bi se omoguCila adekvatna aproksimacija ili generalizacija ulaznog domena. То dalje znaci da velicina skupa Modelovanje Ulazi ulazno/izlaznog Izlazi mapiranJa Slika 2.4 Вlack Ьох modelovanje za obucavanje mora rasti proporcionalno sa brojem slobodnih parametara. То znaCi, takode, da је, pored velike koliCine podataka za obucavanje mreze, neophodno i veoma veliko vreme za realizaciju tog obucavanja. U tom slucaju obucavanje postaje veoma skupo, а mozda i 11 Ровw:џ{је - Vestacke neuralne mreze 12 nemoguce. То ujedno i predstavlja glavni proЬlem u primeni neuralnih mreza koje uce pod nadzorom za prakticne proЬleme analize podataka. ProЬlem bi se mogao uЬlaziti ako bi na neki nacin bilo moguce smanjiti kompleksnost sistema. U svakom realnom procesu analize podataka, podaci nisu potpuno slucajni vec su generisani pomocu nekakvih fizickih procesa ili su posledice sistema koji imaju ogranicenu slozenost [Hinton, 1987], [Sejnowski, 1987]. U tom slucaju је potrebno naci manji broj latentnih promenljivih koje dobro karakterisu proces i taj zadatak se moze ostvariti upotrebom samoorganizujucih neuralnih mreza. Jos jedna velika razlika izmedu samoorganizujucih mreza i onih koje uce pod nadzorom је mogнcnost njihove primene н modelovanjн realnog nervnog sistema. Veoma је tesko zamisliti odakle dolaze signali za nadzor, na primer, pri obradi podataka signala koji dolaze sa senzora (снlа) . Takode, ako prihvatimo hipotezн daje нсеnје bazirano na modifikaciji sinapsi, proЬlem је kako lokalno implementirati zakone нсеnја koji sн karakteristicni za mreze koje нсе pod nadzorom, kao sto је metod «prostiranja unazad» (backpropagation). Prema trenнtnim fizioloskim i anatomskim saznanjima realne neuralne mreze se mogн sa mnogo vecom verovatnocom modelovati samoorganizнjнCim neuralnim mrezama. 12 13 II PogГav{je -Vestacke neuralne mreze. 2.5 Osnovne kategorije samoorganizujucill neuralnih mreza Samoorganizujuce neшalne mreze se, na osnovu algoritama za ucenje koj i se u nJima primenjuju, mogu podeliti u dve osnovne grupe: jednu grupu Cine zakoni ucenj a koj i predstavljaju ekstenzije lineamih statistickih metoda i koje u sustini predstavljaju kodiranje u potprostor nize dimenzye, dok drugu grupu Cine metode koje se bave vektorskim kodiranjem ili grupisanjem i bazirane su na kompetitivnom ucenju. 2.5.1 Samoorganizujuce neuralne mreze bazirane па standardnim statistickim metodama U ovu klasu algoritama spadaju metode koje se baziraju na standardnim statistickim metodama kao sto su analiza glavnih komponenta (РСА) i faktor analiza (F А) , koje rezultuju redukovanim podskupom lineamih kombinacija originalnih ulaznih varijaЬli . Mnoge metode za РСА su bazirane na Ojinom zakonu ucenja [Оја, 1982], koji u sustini predstavlja modifikaciju Hebovog zakona ucenja [НеЬЬ, 1949] . U ovu klasu spadaju i tehnike koje se bave otkrivanjem nezavisnih komponenata, koje maksimalno redukuju redundansu medн latentnim varijaЫama. Generalno taj nacin obrade signala је poznat kao obrada signala «na slepo» (blind signal processing - BSP). U tu vrstu spadaju analiza nezavisnih komponenata (independent component analysis - ICA) i/ili razdvajanje signala «na slepo» (Ьlind signal separation - BSS). BSS i ICA su tehnike koje omogucavaju izdvajanje nezavisnih latentnih varijaЫi iz paralelnih signala kao sto su govomi signal, elektromagnetska merenja na mozgu ili nekakve sekvence iz oЫasti finansija, pri cemu se smatra da su ulazni signali lineame kombinacije nezavisnih latentnih varijaЫi . Ovde се biti predstaljen Hebov zakon ucenja, Ojin zakon ucenja kao i osnovne ideje vezane za ICA i BSS. РСА nece biti analizirana u ovom poglavlju jer се biti predmet detaljnije analize u narednom poglavUu. 2.5.1.1 Hebov zakon ucenja Ovde cemo analizirati jednoslojnu mrezu sa jednim izlaznim neшonom, kao primer. Lineami model neшona sa К ulaznih signala se moze opisati jednaCinom (2.1 ). Као sto је vec receno neшon uCi promenom vrednosti komponenata sinaptickog vektora w. U samoorganizujuCim mrezama taj zakon ucenjaje baziran na sledecem principu kojije definisao НеЬ [НеЬЬ, 1949] : 13 П Poglд:vfie -Vestacke neuralne mreze Kada jedan akson celije А cesto ili stalno иcestvиje и eksitaciji celije В, tada se desava proces rasta ili metabolicka promena и jednoj ili оЬе celije tako da se efikasnost celije А и eksitaciji celije В иvecava. 14 Ova ideja је atraktivna iz razloga sto је veoma jednostavna (bazirana је na korelacij i иlaznog i izlaznog signala) i sto је bazirana na lokalnom principи (informacije koje sи potrebne za modifikacijи sinapticke vrednosti sи prisиtne na krajevima sinapse i nije neophodno postojanje dodatnih mehanizama koji bi ih obezbedivali). Iako је Hebov zakon исеnја 1949. godine bio samo hipoteza, do danasnjeg dana postoji veliki broj neurofizioloskih rezиltata koji idи и prilog toj tezi [Brown, 1990]. U najjednostavnijoj matematickoj interpretaciji ovaj zakon исеnја se moze pisati kao (2.2) gde дwk predstavlja modifikacijи vrednosti sinapse koja spaja k-ti иlazni signal i izlazni neuron, i gde је у faktor исеnја, а i predstavlja indeks koji oznacava diskretne trenиtke и vremenи. Zakon исеnја opisan jednacinom (2.2) је poznat kao Hebov zakon исеnја. Za jednи izlaznи jedinicи on se moze interpretirati kao rezиltat zeUe za maksimizacijom varijanse izlaznog signala. Ako иsvojimo daje иlazni signal sa srednjom vrednoscи nиla imamo Е(у2 ) = E[(w т х Ј Ј= w тсw (2.3) gde је С kovarijansna matrica иlaznog signala, а Е oznacava matematicko ocekivanje. Jednostavno је иoCiti da formiranje иzlaznog gradijentnog metoda za maksimizacijи varijanse izlaznog signala (иz иsvajanje dovoljno malih vremenskih koraka) vodi direktno do Hebovog zakona ucenja. Ako se ovakav zakon primeni direktno na linearnoj mrezi koja је prikazana na Slici 2.2, jasno је da се vrednosti sinaptickog vektora teziti beskonacnosti i imati pravac dominantnog sopstvenog vektora matrice С [Кrasиlina, 1970]. Veliki broj radova se do danas bavio stabilizacijom (ogranicavanjem vrednosti) osnovnog Hebovog zakona исеnја dodavanjem odredenih stabilizacionih clanova. Jedan od najpoznaЩih zakona је Ojin zakon исеnја [Оја, 1982], koji cemo predstaviti и sledecem paragrafи. 14 15 11 Pogllz'Vfie -Vestacke neuralne mreze. 2.5.1.2 Ojin zakon ucenja I ovde cemo se baviti jednoslojnom neuralnom mrezom koja na izlazu ima samo jedan neuron, а koja primenjuje jedan od najpoznatijih zakona ucenja koji је predlozen 1982. godine i naziva se Ojin zakon ucenja, prema autoru. Postavlja se sledece pitanje: Zasto је interesantno analizirati takvu mrezu? Prvo cemo pokusati da damo odgovor na to pitanje. Iako se korteks ljudskog mozga deli na veliki broj funkcionalno specijalizovanih oЬlasti, njegova anatomska struktшa је iznenadujuce uniformna [Hubbel, 1974] , [Rockel, 1980]. Takode, Cinjenica da se neokorteks razvija veoma brzo za vreme filogene faze razvoja ukazuje na to da se on relativno lako replicira i da dalja ekspanzija zahteva mali broj dodatnih genetickih instrukcija. Tipovi сеЩа i osnovni tipovi lokalnih veza medu njima su veoma slicni u razlicitim regionima korteksa. Razlike su mnogo cesce kvantitativne nego kvalitativne i povezane su sa tipom funkcije koju region obavya. Na primer, slojevi koji obraduju senzome signale imaju deЬlje ulazne slojeve, dok najveci broj izlaza potice od motomih oЬlasti. Korteks pokazuje uniformnost ne samo u anatomiji vec i u mnogim aspektima svog razvoja. Vestackim preusmeravanjem projekcije signala retine kod fereta (vrsta glodara), auditomi korteks moze razviti tipove celija koje su karakteristicne za video korteks, kao sto su orijentaciono i direkciono selektivne celije [Sur, 1988]. Rezultati koji su dobijeni kod hrcaka kod kojih su signali retine projektovani u somatosenzomi korteks pokazali sн da celije somatosenzomog korteksa dајн odziv koji је karakteristican za oЬlast 17 primamog vizнelnog korteksa normalne zivotinje, sa procentom celija koje razvijajн orijentacionн i direkcionн selektivnost, veoma slicnim kao н obasti 17 [Metin, 1989]. Cini se da glavna razlika izmedн pojedinih oЬlasti korteksa lezi н tome sto primajн нlaze iz, i prosledнjн izlaze н razliCite oЬlasti mozga. Postoji mnogo dokaza koji Ьi нpнcivali na to da sve сеЩе korteksa ili koriste isti algoritam pri radн [GilЬert, 1988] ili н najgorem slнcaju koriste iste radne principe. Na primer, potpuno isti mehanizmi mogu Ьiti korisceni da izazovu direkcionu selektivnost u vizuelnom i somatosenzomom korteksu. Ako sve celije korteksa rade na istom principu, koji је to princip? Posto taj princip jos uvek sa sigurnoscu nije poznat postoji prostor za pretpostavke (spekulacije) koje се Ьiti potvrdene ili odbacene kada za to bude postojalo dovoyno saznanja. ZnaCi, proucavanje osnovnog mehanizma rada jednog neurona moze potencijalno Ьiti od velikog znacaja. Ojin zakon ucenja predstavlja, u sustini, Hebov zakon ucenja koji је staЬilizovan dodatnim clanom. StaЬilizacija је obezbedena па bazi lokalno dostupnih informacija. On u sustini 15 п Pog!дv(ie-Vestacke neuralne mreze 16 predstavlja lokalnu primenu ideje normalizacije sinaptickog vektora koji је vec bio predlagan u literaturi i pre Оје [Amari, 1978; Kohonen, 1982]. Polazna tacka Ojinog zakona ucenja је sledeca formula [Amari, 1978; Kohonen, 1982; Оја, 1982]: (2.4) koja, pod pretpostavkom da је у dovoljno malo, moze biti razvijena u Tejlorov red ро у, sto daje (2 .5) gde O(;f) predstavlja kvadratni i vise clanove reda ро у. Ako usvojimo da је у dovoljno malo, dobijamo sledeCi zakon ucenja wk (i + 1) = wk (i) + r у(i)(ч (i)- y(i)wk (i) ), (2.6) koji је poznat kao Ojin zakon ucenja. Pod odredenim pretpostavkama (о ulaznim signalima, faktoru ucenja у i td.), pokazano је [Оја, 1982; Оја, 1985] da sinapticki vektor tezi dominantnom sopstvenom vektoru matrice С pod pretpostvakom da nije normalan na njega u pocetnom trenutku, sto је tacno sa verovatnocom 1. 2.5.1.3 Obrada signala «па slepo» (BSP) Obrada signla «na slepo» (Blind signal processing - BSP) је pristup analizi signala koji se generalno moze formulisati na sledeCi nacin: Pretpostavimo da prikupljamo signale sa senzora koje cemo oznaciti sa x(t) = (x1(t), х2(t), ... ,хк(t))т iz MIMO nelineamog dinamickog sistema. Cilj је pronalazenje inverznog sistema, koji cemo nazvati rekonstrukcioni sistem, neuralna mreza ili inverzni adaptivni sistem, ako on postoji i ako је stabilan, kako bi se odredili primami izvori signala s(t) = (s1 (t), s2(t), ... ,sN(t)) т _ Та estimacija se obavlja na osnovu izlaznih signala y(t) = (у 1 (t), y2(t), ... ,yN(t)) т i senzorskih signala kao i nekog prethodnog znanja о sistemu koji vrsi mesanje primamih 16 17 П Poвtav[ze -Vestacke neuralne mreze. signala. U principu, pozeljno је da inverzni sistem bude adaptivan u tom smislu da ima mogucnost pracenja nestacionamog okruzenja. Umesto estimiranja izvora signala direktno, cesto је mnogo jednostavnije prvo identifikovati dinamicki sistem za mesanje i filtriranje (pogotovu u slucajevima kada inverzni sistem ne postoji ili ako је broj opservacija manji od broja izvora signala) i onda estimirati izvore signala implicitno koriscenjem nekih а priori informacija о sistemu i primenom pogodnih optimizacionih procedura. U mnogim slucajevima, izvomi signali su istovremeno lineamo filtrirani i izmesani. Cilj BSP је procesiranje opservacija na takav nacin da adaptivni sistem ekstrahuje originalne izvore. ProЬlem estimacije i razdvajanja originalnih izvora talasnih oЬlika moze ukratko biti izrazen u vidu brojnih medusobno povezanih proЬlema kao sto su analiza nezavisnih komponenata (ICA), razdvajanje signala «na slepo» (BSS), ekstrakcija signala «na slepo» (BSE) ili visekanalna dekonvolucija signala «na slepo» (MBD) . Uprosceno govoreCi ovi proЬlemi mogu biti predstavljeni kao proЬlemi razdvajanja i estimiranja talasnih oЬlika originalnih izvora iz mreze senzora ili prijemnika, а bez poznavanja karakteristika predajnog kanala. Generalno gledano BSS i ICA se mogu definisati na sledeCi naCin: BSS slucajnog vektora x(t) = (x1(t), х2 (t), ... ,хк(t))т se dobija pronalazenjem KxN, maksimalnog ranga, lineame transformacije (matrice) W takve da izlazni signalni vektor у= (y 1(t), y2(t), ... ,yN(:t))т, definisan kao у = wтх, sadrzi komponente koje su medusobno nezavisne koliko је to vise moguce, pri cemu se nezavisnost utvrduje na osnovu informaticko- teorijskog kriterijuma kao sto је KulЬak-LajЬlerova divergencija [Deco, 1996] ili nekog drugog kriterijuma kao sto su nepopunjenost ili lineama prediktabilnost. Pri tome se smatra da izvomi signali imaju srednju vrednost nula. U principu za ICA metod postoji nekoliko vrsta definicya koje zavise od tipa proЬlema na koji se metod primenjuje. Ovde cemo navesti dve osnovne definicye (postoje i druge koje ovde nece biti prikazane- vidi [Cichocki, 2002]). Definicija Ј (Temporalna ICA) ICA slucajnog vektora x(i) Е Rк se doЬija pronalazenjem KxN separacione matrice W (N ~ К) tako da izlazni signal y(i)=(y1 (i), Y2Ci), ... , ун(i)) definisan sa y(i) = W т x(i) (2.7) 17 11 PogГavlie-Vestacke neuralne mreze 18 sadrzi estimirane izvome komponente s(i) Е RN koje su nezavisne koliko је to moguce, а sto se procenjuje na osnovu informaciono-teorijske funkcije cene kao sto је KulЬak-LajЫerova divergencija. Lako је uoCiti daje ovo definicija kojaje identicna definiciji BSS. Definicija 2 Za slucajan vektor x(i) koji sadrzi i sum, definisan sa x(i) = Hs(i) + v(i), (2.8) gde је Н (NхК) matrica za mesanje, s(i) = (s1 (i), s2(i), ... , sн(i)) vektor izvora statisticki nezavisnih signala i v(i) = ( v1 (i), v2(i), ... , vн(i)) vektor nekorelisanih clanova koji reprezentuju sum, ICA se doЬija estimiranjem matrice za mesanje Н i nezavisnih komponenata s(i) = (s 1(i), s2(i), .. . , sн(i)). Pored formalnih definicija, uoЬicajeno је da se ICA proЫem predstavlja na osnovu jedne konkretne primene tog metoda na takozvani «cocktail party» proЬlem. «Cocktail party» proЫem se moze opisati kao sposobnost fokusiranja na govor pojedinca u prisustvu kakofonije drugih konverzacija kao i prisustvu suma. Ovaj proЫem је veoma interesantan i tehnicki veoma slozen za resavanje. Moze se opisati i kao proЫem izdvajanja originalnih signala iz mesavine signala koji se detektuju matricom mikrofona (vidi Sliku 2.5). Poznato је da ljudski mozak resava ovaj proЫem veoma uspesno. Slika 2.5 «Cocktail party» proЫem- ilustracija 18 19 II О faktor ucenja (а faktor l-ТЈо faktor zaboravljanja) i koji se bira na osnovu stacionarnosti signala i tipicno iznosi 0.01 do 0.1. Altemativno, u aplikacijama u realnom vremenu, kovarijansna matrica se moze rekurzivno izracunavati na osnovu sledece formule См =-1 ± x(l)xт(l) =-1 [ Ix(l)xт(l) + x(i)xт(i)] М l = i - M + 1 М l=i - M +1 (3.7) м - 1 с 1 ( ') т ( ') =-- м-1 +-хzх 1, м м gde См oznacava estimiranu vrednost kovarijansne matrice u i-tom trenutku i gde је 1 i-1 т См-Ј =-- Ix(l)x (/). M- 1Z=i-M+J Rekurzivna formula u mnogo opstijoj formi је data sa См = аСм_1 +6С (3.8) gde је а parametar u intervalu О do 1, а 6С predstavlja simetricnu matricu Ciji је rang mnogo manji od ranga matrice См-Ј. U slucaju kada se radi о stacionamim signalima obicno se bira а= (М-1)/М i 6С=(1 /М)х(i)хт(i) Ciji је rang 1, gde је x(i) vrednost ulaznog vektora u trenutku i. Sa druge strane u nestacionamom slucaju, koristi se 6С ranga 1, pri cemu је а<< 26 27 III PogГav[fe- Analiza glavnih komponenata 1, а ~С Је x(i)xт(i). Altemativno, u nestacionamom slucaju, koristi se ~С ciji је rang 2, а а=1. 3.2 Potprostori signala i suma- automatski izbor dimenzije РСА Veoma vazan problem koji se pojavljuje u mnog1m oblastima pпmene РСА jeste odredivanje dimenzije signala kao i potprostora suma. Drugim reCima, jedan od glavnih problema kod primene РСА је izbor broja glavnih komponenata koje је potrebno zadrzati [Minka, 2001] . Da Ьismo resili taj problem oЬicno se koristi fundamentalna osoЬina РСА: РСА projektuje ulazne podatke x(i) iz njihovog originalnog K-dimenzionog prostora u N- dimenzioni izlazni potprostor y(i) (tipicno N <<К), pri cemu se redukcija dimenzije obavlja na takav nacin da se zadrzi maksimalno moguca koliCina informacija koja se sadrzi u ulaznim podacima. Drugim recima, glavne komponente Yk(i)=w/x(i) se procenjuju na taj naCin da se, i pored znacajne redukcije dimenzionalnosti, zadrzi maksimalna koliCina informacija. U tom slucaju se ulazni podaci х mogu rekonstruisati na osnovu izlaznih podataka у pomocu transformacije xp=Wy, tako da se minimizira odgovarajuca funkcija cene. Najcesce korisceni kriterijumje minimizacija srednjeg kvadratnog odstupanja llx-WWтxll2 . РСА nam omogucava da podelimo merene, senzome signale: x(i)=xs(i)+v(i) na dva potprostora: signalni potprostor koji odgovara glavnim komponentama koje odgovaraju najvecim sopstvenim vrednostima i odgovarajucim sopstvenim vektorima i potprostor suma koji odgovara sporednim komponentama koje su povezane sa najmanjim sopstvenim vrednostima. Signalni potprostor se tada moze smatrati potprostorom koji је «besuman». Jedan od problema koji se pojavljuje kod ovakvog pristupa problemu је kako korektno proceniti prag koji deli sopstvene vrednosti u dva podskupa, posebno u slucajevima kada је poznato da је nivo suma visok. Pretpostavimo da је model vektora x(i) Е 91к dat sa x(i) = Hs(i) + v(i) (3.9) gde је НЕ91(КхN) matrica za mesanje (К> N) maksimalnog ranga, s(i)E91N vektor izvora koji zadovoUavaju Gausovu raspodelu sa srednjom vrednoscu nula i Cija је kovarijansna matrica Rss=E(s(i)s т (i)) nesingulama i gde је v(i) Е 91к vektor suma koji zadovoljava Gausovu 27 III PogГav{je-Analiza glavnih komponenata 28 raspodelu sa srednjom vrednoscu nula i Cija је kovarijansna matrica data sa Rvv=cr} lњ pri сети su vektori s i v nekorelisani. Ovakav model se cesto naziva i probabilisticka РСА i obicno se koristi u kontekstu masinskog ucenja (machine learning). Takode, ovakav model se moze smatrati posebnom formom faktor analize (F А) u kojoj је sum izotropan. Razlika u odnosu na F А је u tome sto је kod F А kovarijansna matrica suma, generalno gledano, dij agonalna matrica. Za model (3 .9), pod gore navedenim uslovima, kovarijansna matrica x(i) se moze pisati kao (3.10) gde је HRssHт = VsAsV/ matrica ranga К, Vs Е m_КxN i sadrzi sopstvene vektore koji odgovaraju N dominantnih sopstvenih vrednosti, koje Cine dijagonalu matrice As=diag{A.1 2А.2 2 ... 2 А.н } u opadajucem redosledu. Slicno, matrica VN1 Е m.к~rк-N) sadrzi (K-N) sopstvenih vektora koji odgovaraju sopstvenim vrednostima suma ЛN1=diag{A.н+I 2А.н+2 2 . . . 2 А.к }=cr! lк-N . То znaCi, teorijski, da је (K-N) najmanjih sopstvenih vrednosti matrice С jednako cr !, tako da se moze odrediti dimenzija signalnog potprostora na osnovu visestrukosti sopstvene vrednosti Cija је vrednost najmanja, pod pretpostavkom da је varijansa suma relativno mala i da је moguca perfektna procena vrednosti kovarijansne matrice. Medutim, u praksi, kovarijansna matrica se procenjuje na osnovu ogranicenog broja uzoraka i naJmanJe sopstvene vrednosti su obicno razliCite, tako da odredivanje dimenzije signalnog potprostora nije jednostavan zadatak. Umesto da se prag izmedu sopstvenih vrednosti koje reprezentuju signal i onih koje reprezentuju sum postavlja na osnovu nekakve heuristicke procedure, mogu se koristiti i informacioni teoretski kriterijumi, kao sto su Akaikeov informacioni kriterijum (AIC), minimalna duzina zapisa (Minimum Description Lenght - MDL) i Bajesov informacioni kriterijum (BIC) [Karhunen, 1997; Wax, 1985; Minka, 2001] . Primena ovih kriterijuma zahteva izracunavanje verovatnoce podataka za sve moguce dimenzije . Primenom AIC kriterijuma bira se model koji minimizira sledecu funkciju cene [Liavas, 1999] 28 29 ЈП PogCav{je- Analiza glavnih komponenata AIC = -2log(p(x(l),x(2),K ,x(M)IG к))+ 2N, (3 .11) gde је p(x(l), х(2), ... , x(N))IE>к) parametrizovana funkcija gustine verovatnoce, Е>к је maksimum likelihood estimator parametarskog vektora 8, i N је broj slobodno podesivih parametara. MDL kriterijum selektuje model koji minimizira MDL = -1og(p(x(1),x(2),K ,x(M)IG к ))+_!_N1ogM. 2 (3.12) Ako usvojimo da је vektor ulaza { x(i)} i=l м u stvari vektor Cija је srednja vrednost nula i ako zadovoljava Gausovu raspodelu, moze se pokazati [Wax, 1985] da se dimenzija signalnog potprostora N Е (1 ,2, ... , К) dobija za ono N za koje је AIC(N) = -2М(К- N)logp(N) + 2N(2K- N), (3.13) MDL(N) = -М(К- N)logp(N) + 0.5N(2K- N)log(M) (3.14) minimalno. Ovde је М broj vektora podataka x(i) koji se koriste za estimiranje kovarijansne matrice С i р је dato sa (3.15) i predstavlja odnos geometr*ke i aritmeticke sredine najmanjih (K-N) sopstvenih vrednosti. Estimirana vrednost za N se moze izabrati primenom bilo AIC, Ьilo MDL kriterijuma. Nazalost, оЬа kriterijuma daju samo priЫiznu procenu dimenzije signalnog potprostora i оЬа su veoma osetljiva na odnos signal/sum (SNR) kao i na broj raspolozivih uzoraka ulaznog signala [Liavas, 1999] . Drugi proЫem koji se pojavljuje kod primene AIC ili MDL kriterijuma је taj sto se mora pretpostaviti da ulazni vektor x(i) zadovoljava Gausovu raspodelu [Wax, 1985]. То је uradeno iz razloga sto је izborom Gausove raspodele omoguceno doЬijanje izraza u zatvorenoj formi. 29 III РоgГаvГ,е - Analiza glavnih komponenata 30 Nedavno је Minka [Minka, 2001] predlozio veoma efikasan kriterijum koji se koristi za estimaciju dimenzije signalnog potprostora, а koji se bazira na Bajesovoj selekciji modela (MIВS) . Estimacija izracunava integral na Stifelovoj mnogostrukosti koji se aproksimira Laplasovom metodom. Za primenu ovog metoda potrebno је izabrati N, 1:s:; N :s:; К tako da se maksimizira izraz (3.16) gdeje PN = 2 -Nfiг(к- i + 1)тr -n kada је Лk1 = Gn. Kako Ьi se odredila stvarna dimenzija podataka Х, Ьiramo vrednost N tako se maksimizira aproksimacij а p(X]N) [Minka, 2001]. Jedna aproksimacija MIВS dovodi do Bajesovog informacionog kriterijuma (BIC) koji zanemaruje sve clanove koji ne zavise od М: м BIC(N) = (fi А; Ј-2 СЈнмск-н) / 2 м-cdN +N ) / 2 . j=l (3.17) Eksperimenti koje је obavljao Minka su pokazali da је kriterijum robusan u odnosu na distribuciju izvora i veoma konzistentan cak i u slucaju relativno malog broja ulaznih podataka. Sledeca dva uslova mogu dovesti do korektne estimacije broja izvora. Prvo, dimenzija ulaznog podatka mora Ьiti veca od broja izvora. Ako је broj izvora jednak broju senzora, svi kriterijumi bez izuzetka procenjuju da је broj izvora za jedan manji nego sto jeste. Drugi 30 31 III PogfavCie- Analiza glavnih komponenata uslov је da mora postojati barem mala kolicina suma. То, takode, garantuje da su najmanje sopstvene vrednosti koje odgovaraju sumu, razliCite od nule. 3.3 Osnovne osohine РСА Sada cemo navesti neke osoЬine glavnih komponenata yk(i)=w/x(i), bez dokaza jer se svi dokazi mogu ј ednostavno izvesti. 1. Faktor y 1 (i)=w 1 тx(i) је glavna komponenta x(i) ako је varijansay1(i) maksimalna, pod uslovom da је norma ( duzina) vektora w 1 konstantna [О ја, 1992]. Tada vektor \V 1 maksimizira sledeCi kriterijum Ј1 (w1) =Е~[)= в(w[ c,v1 ), (3.18) Pod ogranicenjem llwiii2=1. Ovaj kriterijum se moze prosiriti na N glavnih komponenata (N је Ьilo koji сео broj veCi od 1 i manji od К) kao (3.19) d •v • Т S: ро ograшcenJem wi W]uij· 2. Glavne komponente imaju srednju vrednost nula, Vi. (3.20) З. Razlicite glavne komponente su medusobno nekorelisane (i, ј= 1,2,К , N). (3 .2 1) 4. Varijansa i-te glavne komponente је jednaka i-toj sopstvenoj vrednosti kovarijansne matrice С 31 ЈП PogCavfie- Analiza glavnih komponenata 5. Osobina najbolje aproksimacije Pretpostavimo da vazi: Л!:;::: А-2 :;::: ... :;::: Лк . Za srednju kvadratnu gresku aproksimacije N N хр = LYk'vk = Iwkwrx, k=l k=l 1mamo 32 (3.22) (3.23) NО. Algoгitam (3.30) moze da~e biti нргоsсеn (3.31) јег dгugi clan na desnoj stгani jednacine (3.30) koji moze biti napisan kao xw/e1=x,v1\x- w1y1)=x(l-w1тw1)y1, tezi Ьгzо ka nнli јег w1тwi tezi 1 kako t tezi beskonacnosti i tako moze biti zanemaгen. Ova osobina moze biti potvгdena kгoz simulacije. Inteгesantno је pгimetiti da diгektna гealizacija ovog zakona ucenja w 1 (i + 1) =w 1 (i) + r 1 (i)y1 (i)[x(i)- w 1 (i)y1 (i) 1 (i = 0,1,2,К) (3.32) 34 35 ЈП PogCavfie- Analiza glavnih komponenata u stvari predstavlja poznati Ojin algoritam [Оја, 1982] . Као sto је vec pomenuto, nije bas previse poznato da је Amari [Amari, 1978] bio prvi koji је predlozio algoritam u kome је normalizovani Hebov zakon ucenja bio koriscen za izdvajanje dominantne glavne komponenete. Predlozeni zakon ucenja moze Ьiti prosiren na izracunavanje proizvoljnog broja glavnih komponenata koriscenjem principa samonadziranja i hijerarhijske neuralne mreze (vidi na primer [Sanger, 1989] ). Sada cemo predstaviti pristup za sekvencijalnu ekstrakciju glavnih komponenata koje odgovaraju realnom, slucajnom ulaznom signalu sa srednjom vrednoscu nula, bez estimacije kovarijansne matrice. Ekstrakcija се se obavUati sekvencijalno i onoliko dugo dok је poslednja izracunata glavna komponenta veca od nekog izabranog praga. Bice usvojeno da sporedne komponente odgovaraju aditivnom sumu. Zakon ucenja za izdvajanje druge glavne komponente А.2 = E(y/(i)) је slican onome koji је koriscen pri izdvajanju dominantne glavne komponente. Razlika se sastoji u tome sto se algoritam ne primenjuje direktno na ulazni vektor vec na vektor koji se formira kao Х2 (i) = Xt (i)- XPt (i) = Xt (i)- WtYI (i) (3.33) i gde је y2(i) = w 2 тх2 (i) . Odatle sledi da se k-ta glavna komponenta moze pisati u formi 'У k (i + 1) = w k (i) + Yk (i)yk (i)xk+! (i), gdeje х 1 (i) = x(i). Izlazni signali Yk(i) posle pпmene ovog algoritma се Ьiti dekorelisani sopstvenim vrednostima Ak = E(yk2(i)), (k=l ,2, ... , N). (3.34) (3.35) odgovarace 35 ЈП PogГav{je -Analiza glavnih komponenata 36 3.5 Osnovnefunkcije cene i adaptivni algoritmi za РСА 3.5.1 Rejlijev koeflcijent- osnovne osoblne VeCina adaptivnih algoritama za РСА i МСА mogu direktno ili indirektno biti definisane koriscenjem Rejlijevog koeficijenta (RК) specificne kovarijansne matrice kao funkcije cene. Rejlijev koeficijent r(,v) је definisan za w* О, kao wTCw r(w) = r(w,C) = т w w gde је С=Е(ххт) . Rejlijev koeficijent ima sledece osobine: 1. Stacionarnost i kriticne tacke: Л1 = maxr(w,C) Лк = minr(w,C) gde su Л1 i Лк najveca i najmanja sopstvena vrednost matrice С. (З . З6) (З . З7) (З.З8) Generalno govoreci, kriticne tacke funkcije r(w, С) su sopstveni vektori i sopstvene vrednosti matrice С. Pretpostavimo da za sopstvene vrednosti kovarijansne matrice vazi (З . З9) 2. Homogenost: r(rлv,fЗC)= fЗr(w,C) \fa;;f:.O, fЗ*О . (З.40) З. Invarijantnost u odnosu na translaciju r(w,C- al) = r(w,C)- а (З .41 ) З6 37 ЈП Poglдvfie- Analiza glavnih komponenata 4. Minimalni ostatak I(C- r(w,C)I~vll ~ II(C- al~vll 2 , Vw =1= О i svaki skalami koeficijent а. (3.42) 5. Ortogonalnost w 1. (с- r(w,C)I)w. (3.43) б . Hesijan Rejlijevog koeficijenta је [ a 2 r(w,C)] 2 ( { 4 тЈ Hr(w,C)= =--2 C-r(w,C)I 1---2 ww . awiaw ј llwll2 llwli2 (3.44) Za sopstvene vrednosti А- 1 , А-2 .. . , А-к i odgovarajuce sopstvene vektore с 1 , с2 , ... , ск Hesijan moze biti izrazen kao [Ciпincione, 1998] Hr(', mozemo koristiti sledecu uproscenu formulu м LY?) (i)x(i) i=l wl(l+1)= м ' I~iz)Ci)J (3.62) i=l ili opstije, za veci broj glavnih komponenata mozemo koristi deflacioni postupak м LYk1) (i)xk (i) w k (l + 1) = i=~ , (k = 1,2, .. . ,N) I ~iz)cof (3.63) i=l gde је Yk(f)(i) = w/(l)xk(i). Nakon konvergencUe vektora wk(l) ka Wk#, mozemo izvrsiti deflaciju Xk+I=xk-Wk#Yk, х1=х. Ovakav algoritam moze rigoroznije biti izveden u nesto modifikovanoj formi kao minimizacUa sledece funkcUe cene: (3.64) pri cemu је ogranicenje Jl'vЉ = 1. Gomja funkcija cene dostize ravnoteznu tacku kada је gradij ent Ј1 nula, tj. u м LY#(i)x(i) \V # = -'-i =....:.1 __ _ м LY~(i) i=l (3.65) 42 43 ЈП PogГavfie- Analiza glavnih komponenata То nam sugerise sledecu iterativnu formulu [Roweis, 1998], [Tipping, 1999] м L у(!) (i)x(i) w(l + 1) = i=l (3.66) м L y О parametar koji zavisi od vrste proЫema, nazvan parametar odsecanja (tipicna vrednost mu је 1 <Р < 3). Tipicne funkcije guЬitka robusnosti i njihove funkcije aktivacije su definisane sa (3.73) i prikazane su u literaturi [Cichocki, 2002]. Generalno govoreCi, izbor odgovarajuce funkcije guЬitka zavisi od raspodele ulaznog vektora x(t). PrimenjujuCi standardni opadajuCi gradijentni metod na energetsku funkciju (3.68) doЬijamo sledeci algoritam (predstavlja generalizacijujednacine (3.29)) (3.74) gde )-t(t) pozitivno i U matricnoj formi ovaj algoritam se moze pisati kao (3.75) gdeje 46 47 ЈП PogГav[fe- Analiza glavnih komponenata Uproscena verzija ovakvog zakona ucenja ima oblik (3.76) gde је џ. >О. Koriscenjem principa samonadziranja i kaskadnih hijerarhijskih neшalnih mreza, zakoni ucenja (3.74), (3.75) i (3.76) mogu biti prosireni za dobijanje veceg broja znacajnih glavnih komponenata. Drugim reCima, algoritam ucenja za odredivanje druge glavne komponente (komponente koja odgovara drugoj najvecoj sopstvenoj vrednosti) је veoma slican onome za odredivanje prve sopstvene vrednosti, pri cemu se proces ucenja ne primenjuje direktno na ulaznu komponentu х vec na dostupnu gresku (3 .77) (3.78) Ostale komponente se izracunavaju analogno. U tom slucaju se moze definisati sekvencijalna funkcija cene kao к Ј p('v k) = p(ek) = IPp(ekp), р=! (k = 1,2 ,К N) (3.79) gde је ek= ek-1 - \Vk)lk, Yk = w/ek-1, i gde је eo(t)= x(t). Minimizacija ove funkcije cene primenom metoda opadajuceg gradijenta dovodi do adaptivnog algoritma ucenja (3.80) za bilo koje \Vk(O) *О (k=1 ,2, ... , N) gde је 47 ЈП PogГav[je-Analiza glavnih komponenata Jik (t) >о Ч'(еk) =[Ч'! (ek!), ч-'1 (ek2),K ч-'1 (еkк )]т, Ч' (е ) = ор р (е kp) р kp o(ekp) ' ео (t) = x(t). 48 Obicno је drнgi clan na desnoj strani jednacine (3.80) relativno mali i moze biti zanemaren. Tada dobijamo нproscenн verzijн zakona нсеnја za ekstrakcijн najvecih N glavnih komponenata (3.81) ili н diskretnoj formi w k (i + 1) = w k (i) + Yk (i)yk (i)Ч'[ek (i)] (3.82) gde је wk(O) -:;t О i YkCi) >О. 48 49 ЈП PogШvfie- Analiza glavn ih komponenata 3.6 Adaptivni algoritmi za sekvencijalnu ekstrakciju sporednih komponenata Na prvi pogled izgleda logicno da se za ekstrakciju sporednih komponenata mogu koristiti algoritmi koji su slicni onima za izracunavanje glavnih komponenata, ali jednostavna promena znaka faktora ucenja kod velike vecine algoritama izaziva numericku nestaЬilnost . То dalje znaci da је potrebno uvesti dodatne staЬilizacione clanove kako Ьi se obezbedila stabilnost algoritma. Na primer, Ojin zakon ucenja za izracunavanje dominantne komponente moze Ьiti modifikovan da izracunava najmanju sporednu komponentu na sledeCi naCin w(i + 1) = w(i)- y(i)~(i)x(i)- у2 (i)w(i) + ('v т (i),v(i) -1)w(i)) (3 .83) Lako је uoCiti da zakon ucenja sadrzi dodatni kazneni clan (,v\v-1) koji obezbeduje stabilnost algoritma forsiranjem duzine sinaptickog vektora najedinicnu vrednost. Siroka klasa МСА algoritama se moze izvesti iz minimizacionog proЬlema (bez ogranicenja) minr(w)/2 )VE~K wтcw r(w) = т . W \V (3.84) PrimenjujuCi opadajuci gradijentni metod direktno, doЬijamo sistem nelineamih oЬicnih diferencij alnih ј ednacina dw = -yV ,vr(w) = -r дr(w) = -r[c,vw т w- w(w т Cw )] dt дw (,v т w Ј (3 .85) gde је r(t) > о faktor ucenja. Vazna osoЬina gomjeg zakona ucenjaje daje norma (duzina) vektora 'v konstantna и toku ucenja i jednaka jedinici. То је jednostavno dokazati na sledeci nacin, posto је (3.86) 49 ЈП PogГav{je-Analiza glavnih komponenata 50 pri cemuje neophodno da inicijalno w nije О. То znaCi daje Vt ~О. С3.87) Bez gubitka opstosti, moze se usvojiti da је norma JlwCO)II = 1. То dalje znaCi da clan w \v moze Ьiti zanemaren ili formalno apsorbovan u pozitivni fakor ucenja yCt) tako da vazi dw = -r(cw -w wтcwJ· dt WTW С3.88) Moze se pokazati da ova jednaCina moze Ьiti interpretirana i kao specyalni slucaj Broketovog dvostrukog brackettoka [Brockett, 1991а], [Brockett, 1991Ь] . Na bazi jednaCine С3.88), u literaturi је predlozeno vise modifikacija koje u generalnoj formi mogu Ьiti napisane kao d\V т ( wтcw Ј - = -rCt)gC"v w) Cw- т w dt w w С3.89) ili ekvivalentno dw = -y(t) gCwттw) [cww т w- (w т Cw )w Ј dt w w С3.90) gde gCwтw) uzima razliCite forme Cna primer Cwтw), 1, Cwтwy 1 ). U diskretnom domenu algoritam se u najjednostavnijoj formi moze pisati kao с . 1) с·) c·)[cU) с·) w т Ci)CU\v(i) с·)] wz+ =wz-yz wz- т wz, w Ci)\vCi) С3.91) а njegova online verzija 50 51 ЈП РоgГа:vГте- Analiza glavnih komponenata w(i + 1) = w(i)- y(i)g(llwU)II~ )[y(i)x(i)- ;~ (i) . w(i)], w (z)w(l) (3.92) gde је y(i) = wтx(i). Nazalost, usled numerickih aproksimacija gornji diskretni algoritam је nestabilan (algoritam divergira posle velikog broja iteracija, ukoliko se ne koristi periodicna normalizacija na jedinicnu duzinu). Da Ьi se spreCila nestaЬilnost, faktor ucenja mora eksponencijalno da tezi ka nuli ili moramo da ortonormalizujemo vektor \v(i) posle svakih nekoliko iteracija: . w(i) w(z) = llwCi)ll2 (3.93) Posle ekstrakcije prve sporedne komponente, u cilju ekstrakcije ostalih sporednih komponenata, umesto eliminacije vektora wk iz kovarijansne matrice, pokusava se ekstrakcUa dominantne glavne komponente nove kovarUansne matrice koja se definise kao сС2) =сО) +к w w т n n n' (3 .94) gde ј е с С 1 )=Е { хх т} i Кп ј е fiksna konstanta veca od А Ј. Svi gore pomenuti algoritmi za МСА su vrlo spori i njihova konvergencija veoma zavisi od izabranog faktora ucenja у (i). Nedavno, Sakai i Simizu su izvrsili modifikaciju brzog РСА RLS algoritma za МСА [Sakai, 1997] (vidi takode [Cichocki, 1993]): Yk (i) = w r (i)xk (i), wk(i+l)=wk(i) - Yk(i) [xk(i) - yk(i)'vk(i)1 77 k 1 (i) 77 k 1 (i + 1) = У77 k 1 (i) + IY k (i)l2 ' w k ~ w k - 'I\\v Ј \V ј~ ј, \V k (i) = \V k (i)(\v Ј (i)\v k (i) )-}i j=m k=m,m-1,K, (3 .95) (3 .96) (3.97) (3.98) (3 .99) 51 III PagCavГze- Analiza glavnih komponenata 52 X n (i) = x(i), (3.100) Kmje vece od tч. Glavna razlika izmedu ovog algoritma i RLS РСА algoritma lezi u promeni znaka faktora ucenja, ortonormalizaciji vektora Wk(f) U svakoj iteraciji i U tome sto se vec ekstrahovane sporedne komponente premestaju na glavne komponente. RazliCiti adaptivni algoritmi za МСА su prikazani u Tabeli 3.3 . 52 53 ЈП PogГav{je- Analiza glavnih komponenata Tabela 3.3 Adaptivni algoritmi za МСА Br. Algoritam Reference 1. д\V k (i + 1) = -y(i)~ k (i)x(i)- У~ (i)w(i) +(w r (i)w k (i) -1)\V k (i)) [Оја, 1992а] 2. дw k с;+ !Ј= -rCiJg(llw k CiJII; )[Yk CiJx(iJ у~ (i) Ј [Оја, 1992а]. т w k(i) ' [Luo, 1997] W k (i)\V k (i) g(wтw)=1, т ( т )- 1 [Ciпincione , ili wkwk ili wkwk 1998] 3. дw k (i +Ј) = -ru{Yk (i)x(i)- Yi (i) w k (i)] [Xu, 1994а; Хн, jjw k (i)jj~ 1994Ь] 4. д,v k (i + 1) = -y(i)y k (i)[JJw k (i)jj~ x(i)- у k (i)w k (i) Ј [Chen, 1998] 5. дw k (i + 1) = - r(i)y k (i)[JJw k (i)jj~ x(i)- у k (i)w k (i) Ј [Doнglas, 1999] 6. дw k (i + 1) = -r(i)~ k (i)x(i) -log~Jw k (i)jj Р р k (i) Ј [Amari, 1998] 7. д,v k и+ 1) = -ru)~k (i)x(i)- ~d - Jiw kci)JJP r k с6Ј [Zhang, 2000] gde је d > Amax 8. дw k (i + 1) = -rcnl'v k (i) - у k (i)x(i)jjw k (i)jj Р Ј [Cichocki, 2002] 9. Yk(i) =w k (i)xk(i), [Sakai, 1997] wk(i+l) = \vk(i)- Yk(i) [xk(i)-yk(i)wk(i)1 r; ;;1 (i) 77 ;;1 (i + 1) = rr;J; 1 (i) + iYk (i)j 2 , k+l( р wk+--wk-IwJwj ј' W k (i) = W k (i)(\v r (i)\V k (i) г )'i j =m Xk-1 (i) = Xk +У mYk (i)\V k (i) k=m,m-l,K, хп(i) = x(i), 53 Io/ CIJogfav[je Cl'arafe{ni a{goritmi za estimaciju g{a:rmifi R..fJmponenata, sporednifi R..fJmponenata i njiliovifi potprostora U prethodnom poglavlju su prikazani osnovni adaptivni algoritmi za sekvencijalnu ekstrakciju glavnih i sporednih komponenata. U ovom poglavlju се Ьiti prikazan jedan moguCi generalni pristup paralelnim algoritmima za ekstrakciju glavnih komponenata, sporednih komponenata ili njihovih potprostora. Prvo се Ьiti analizirana funkcija cene koja dovodi do opsteg metoda za ekstrakciju vise glavnih (РСА) ili sporednih (МСА) komponenata. Postoje slucajevi kada nije neophodno identifikovati glavne/sporedne komponente vec samo potprostore koje oni definisu. U tom slucaju cemo se baviti analizom glavnog (PSA) i sporednog potprostora (MSA). Detaljno се Ьiti opisan jedan od najpoznatijih PSA algoritama - SLA algoritam. U veCini slucajeva РСА/МСА su nastali modifikacijom nekog od PSA/МSA algoritama tako da cemo se baviti generalnim pricipima koji omogucavaju formiranje algoritama Ьilo za PSAIМSA ili РСА/МСА. Navedeno је nekoliko najpoznatijih PSA/PCA i МSА/МСА algoritama. Na kraju је pokazana analiza staЬilnosti za jednu klasu algoritama. 4.1 Funkcija cene za paralelnu ekstrakciju glavnill komponenata i njihovih potprostora Prvo cemo dati intuitivno objasnjenje ideje. Neka su {/ч, .. . , Лm} i {d1, ••• , dm} dva skupa od ро т pozitivnih brojeva, pri сети је d1 > ... > dm > О. Razmotrimo proЫem maksimizacije ( odnosno minimizacij е) sume 55 IVPog&:zvГ,e- Para\elni algoritmi za estimaciju ... т S= IA-гdi , (4.1) i=l pri cemu {Л, 1 ·, ••• , Ат·} predstavlja pregrupisan skup nastao od {AI, ... ,Ат}, gde је { 1 ', ... , т'} permutacija {1,2, . .. , т} . Jednostavno је uoCiti da је S maksimalno kada је {Ат·} uredeno u opadajucem poretku (А 1 • > ... >Ат), а minimalno kadaje А 1 • < ... <Ат·· Broket [Brockett, 1991а], [Brockett,1991Ь] је generalizovao ovu ideju za slucaj matricnog racuna. Neka је V=[v 1, ••. , vт] ortogonalna matrica Cije kolone zadovoljavaju sledecu jednaCinu т V· v. =Ь ·· l Ј lJ (4.2) Definisimo J(V) kao J(v) = tr(nv т cv )= tr(vnv т с) (4.3) gde је D=diag(d1, ••• , dm) . Ako se V sastoji od т sopstvenih vektora matrice С, tj . V=[v 1·, • •• , Vт·], tada је V Т CV = diag(A-1' ,К , ).т•) (4.4) i jednacina (4.3) se svodi na J(V)='i,d/Ai'. U opstem slucaju kada је V ortogonalna matrica vтcv nije dijagonalana matrica. Medutim, i u tom slucaju vazi sledece tvrdenje. Tvrdenje 4.1. Funkcija cene J(V) је maksimalna kadaje (4 .5) а minimimalno kadaje (4.6) 55 I'VPogfavfie- Paralelni algoritmi za estimaciju ... 56 ako sopstvene vrednosti zadovoUavaju /ч > ... > Ат. J(V) nema ш lokalnih mш1muma ш lokalnih maksimuma izuzev globalnih. Razmotrimo sada slucaj kadaje d1 > ... > dn > dn+I = ... =О. U tom slucaju о [vl ,К' v n' v n+l ,К' v т ]Т о (4.7) о tako da zadnjih т-п kolona V automatski iscezavaju. Uzmimo n proizvoUnih mec1usobno ortogonalnihjedinicnih vektora w 1, .. . , 'Vn koji su predstavljeni sledecom matricom (4.8) Tada imamo J(W) = tr(Dw т CW) = tr(WDW т С), (4.9) koja је definisana na isti naCin kao i J(V). Odmah је jasno da је J(W) maksimalno (minimalno) kada se W sastoji od sopstvenih vektora koji odgovaraju n najvecih (najmanjih) sopstvenih vrednosti, pri cemu ne postoje lokalni minimumi i maksimumi osim globalnih. Znaci, predlozena funkcija cene је primenjiva i na РСА i na МСА, а takode i na PSA i MSA. Kada је n=1, J(w) је (4.10) pri Cemuje d1 = 1 i WTW = 1. Kada su d1 = d2= ... = dn=d, J(W) је maksimalno (minimalno) kada se W sastoji od vektora koji predstavljaju lineame kombinacye sopstvenih vektora koji odgovaraju n najvecih 56 57 IVPogГav(je- Paralelni algoritmi za estimaciju ... (najmanjih) sopstvenih vrednosti. Ne postoje drugi lokalni maksimumi i minimumi. U ovom slucaju, maksimizacijom ili minimizacijom funkcije cene se moze identifikovati samo odgovarajuCi potprostor, ali se ne mogu odrediti sopstveni vektori. Takode, postoji i drugi slucajevi kada је dovoljno izvrsiti identifikaciju glavnog potprostora, а nije neophodno pronaci sopstvene vektore. U tom slucaju se primenjuju PSA algoritmi. Primer za to је potprostorni algoritam (Subspace Learning Algorithm - SLA) [Оја, 1989], koji cemo ovde prikazati detaljnije. 57 Io/PogГav{je Paralelni algoritmi za estimaciju ... 58 4.2 Potprostorni algoritam Pretpostavicemo, kao i ranije, da је х slucajni vektor sa srednjom vrednoscu nнla i da pripada Rк. Matrica С је КхК kovarijansna matrica definisana sa ( 4.11) Potprostorni kriterijum је definisan sledecom jednaCinom J~CA(w 1 , .. . ,w N) ~ Е{Е1у~} ~ E{E/w~x)2 } N = Iw~Cwn = max, (4.12) n=1 U kompaktnom zapisu imamo РСА ) Т JN (wl , ... , \V N = trace(W CW), WTW =I, (4.13) gde је w matrica cija је n-ta kolona Wn i 1 predstvalja NxN jedinicnu matricu. JednaCina (4.13) implicira da је matrica P=WWт ortogonalna projekciona matrica koja zadovoljava Р2=Р i р Т =Р. Sadajednacina (4.13) moze biti zapisana kao trace(W Т CW) = Е {11Pxll 2 } (4.14) Odavde vidimo da је originalni proЫem ekvivalentan sa proЫemom pronalazenja N- dimenzionog potprostora и Rк, tako da је ocekivanje kvadrata norme projekcije vektora х na taj potprostor maksimalno veliko. 58 59 Јо/<РоgГаvГте- Paralelni algoritmi za estimaciju .. . Ovaj proЬlem је resen u [Ogawa, 1992], i rezultat pokazuje da је resenje potprostor koji је definisan sa N sopstvenih vektora СЈ, с2, . .. , ен , koji odgovaraju N najvecih sopstvenih vrednosti matrice С. Ako uvedemo sledecu oznaku ( 4.15) ortogonalna projekciona matrica Р moze biti izrazena kao (4.16) То znaci da matrica W u kriterijumu (4.13) nije definisana najedinstven nacin. Imamo daje W= UR, (4.17) gde је R proizvoljna NxN rotaciona matrica koja zadovoljava K 1=R т. ProЬlem kompresUe u stvari predstavlja proЬlem rekonstrukcije х sa Xrec = Рх. Posto srednja kvadratna greska rekonstrukcije moze biti predstavljena sa ( 4.18) ocekivana greska se minimizira kada se E{IIPxl!2 } maksimizira. Na osnovu potprostornog kriterijuma, moze se konstruisati sledeCi algoritam (baziran na [Оја, 1989]): w k (i + 1) ~w k (i) + r{Yk (i{x(i)-~/т (i)>v т (i) Ј} Ут (i) = \V т (i) Т x(i), m,k = 1, ... ,N, ( 4.19) 59 I'V PogCav[fe - Paralelni algoritmi za estimaciju ... 60 gde i oznacava diskretne trenutke u vremenu (i=O , 1, .. . ) i У; predstavlja faktor ucenja. Ovaj algoritam је poznat kao potprostomi algoritam za ucenje (Subspace Learning Algorithm - SLA). Ovaj algoritam i njegova implementacija na potprostomoj mrezi su detaljno analizirani u literaturi [Ој а, 1989; Ој а, 1992]. Rezultat primene ovog algoritma је takav da cak i u slucaju kada se primeni usrednjavanje primenom tehnike stohasticke aproksimacije, algoritam ne rezultuje asimptotski stabilnim resenjima. Tezinski vektori teze ka nekoj ortonormalnoj bazi u N-dimenzionom potprostoru koji је definisan dominantnim sopstvenim vektorima kovarijansne matrice ulaznog signala, ali ta baza ne mora biti ona koju definisu sami sopstveni vektori. То је u potpunosti u skladu sa resenjem potprostomog kriterijuma koje је dato ujednaCini (4.17) [Ogawa, 1992]. U matricnom zapisu, sistem ( 4.19) moze biti prikazan kao dW = a(x - wwтx~тw. dt (4.20) Ako su ulazni podaci doЬijeni uzorkovanjem stacionamog signala cija је kovarijansna matrica С definisana u jednacini (4.11), tada na jednaCinu (4.20) moze Ьiti primenjena stohasticka aproksimacija, pri cemu doЬijamo: dW = a(cw-WWт CW). dt ( 4.21) OvajednaCinaje analizirana u [Оја, 1989]. U [Оја, 1989] је receno da, posto jednacina (4.21) predstavlja matricnu jednacinu treceg stepena, jednacina је teska za resavanje, iako odgovarajuca jednacina ро wwт moze biti resena u zatvorenoj formi , pod odredenim uslovima. Sada cemo pokazati da se odredeni rezultati о prirodi sistema opisanog jednacinom ( 4.21) mogu doЬiti jednostavnom analizom jednaCine, bez pokusaja resavanja iste. JednaCina ( 4.21) se moze pisati kao sistem jednacina: (4.22) 60 61 Io/PogtavГ,e - Paralelni algoritmi za estimaciju ... gde wk (k=1, ... ,N) predstavlja k-tu kolonu matrice w. u tom slucaju mozemo izvuci sledece zakljucke: а) Stacioname tacke jednacine ( 4.22) predstavljaju jednacine Cija su resenja sopstveni vektori matrice WW т_ Ь) Ocigledno је da се sistem pronaCi sopstvene vektore (CWk) koji odgovaraju sopstvenim vrednostima koje su jednake jedinici. с) Ako је rank(W)=K, tada се matrica W\-Vт imati К razliCitih sopstvenih vektora koji svi odgovaraju sopstvenim vrednostima 1. U tom slucaju је jednostavno zakljuCiti da matrica wwт predstavlja projekcionu matricu. Ovaj slucaj је, takode, analiziran u [PlumЫey, 1991]- isti rezultatje dobijen na drugaciji nacin. d) Ako је rank(W)=r АЈ > ... >"-к- Ј > О . (5 .17) Drugim reCima, prepostavicemo da Rx ima К razlicitih striktno pozitivnih sopstvenih vrednosti koje odgovaraju pojedinim ortonormalnim sopstvenim vektorima. Analiza koja sledi se moze izvesti i bez te pretpostavke ali su u tom slucaju izvodenja komplikovanija. OЬicno, u realnim situacijama (na primer kada је ulazna sekvenca rezultat odaЬiranja govomog signala kod procesiranja govora ili vektor koji sadrzi stepen osvetljenosti pojedinih piksela u prozoru kod procesiranja slike ), sopstvene vrednosti kovarijansne matrice се Ьiti razliCite i striktno pozitivne. Ako usvojimo daje m~vт, diferencijalnajednacina od interesaje rii = d m = R m - 1 mm т R m d t х 1 - (1 - m Т m) 2 х (5.18) Ako predstavimo m pomocu ortonormalnog skupa sopstvenih vektora ( ek), koj i predstvaljaju sopstvene vektore matrice Rx doЬijamo gdeje К-1 m = Iakek' k=O (5.19) 77 rr.J О. Sa druge strane imamo 1 K-i 2 Ао- 2 LAtat ( К-1 Ј /-0 1- 1- Iai - k=O (5 .30) ili (5 .31) 79 o/PogГavfie оо ОН metod 80 Posto Bk~O kada t ~оо i k >О, doЬijamo sledeCi izraz . 1 [ 1 з] а о = ло а о - ( 2 \2 а о ' 1- 1-а0 Ј (5.32) ili (5.33) Da Ьismo pokazali da gomjajednaCina konvergira, zapazimo daje (5.34) funkcija Ljapunova, posto је (5.35) V ima minimum za ао = ± 1. ZnaCi, ао ~ ± 1 kako t ~ оо. Posto Bk ~о za k > О, zakljucujemo da ak ~о za k > О. Znaci za veliko t, jedina vazna komponenta је ао, sto znaCi da се т konvergirati ka ±е0 • Sada mora Ьiti pokazano da postoji kompaktan podskup ОсD{Т} vektora w(t) takvih da w(t) Е О beskonacno cesto sa verovatnocom jedan, i da postoji slucajna promenljiva С takva da је 1 y(i) 1 < С beskonacno cesto sa verovatnocom jedan 1 za w(i) Е О. Da Ьismo to ostvarili razmotrimo sledeci algoritam: 80 81 o/PogГavfie - оо ОН metod . Ovde <р[] predstavlja inkrement и trenиtkи i; normalizacija se ostvarиj e роmоси neke ogranicavajиce funkcije ЧЈ[]. U slисаји koji nas interesиje иsvajamo lJJ[•vk (i) , ч (i + 1), y(i + 1)] =ч (i + 1) · y(i + 1) (5.38) (5 .39) y(i + 1) = (1- w(i) · w(i) Т )y(i) + w(i)x(i + 1). (5.40) Imp1ementacijom istih koraka koji sи primenjeni и Ojinom radи [Оја, 1982] doЬij amo (posle nekoliko jednostavnih transformacija) wk (i) = wk (i -1) + rlJJ[Ч (i),y(i)] -rwk(i-1) 0џr +O(r2 ) Ву r =O (5.41) = YVk (i -1) + JXk (i). y(i)- YWk (i -1)y (i) 2 + О(у 2 ) , sto predstavlja zakon исеnја koji је ovde i predlozen (DR је definisano ranije). Tada mozemo reCi da је sledeca jednaCina zadovoljena: (5 .42) Sada se jednacina (5.12) moze napisati na sledeCi naCin 81 o/PogГav(ze - оо ОН metod 82 i+l[ i+l Ј y (i+1)= I пocrf_l) · \V(j-1)·x(j) . J=l l= j+l (5 .43) Iz jednaCine (5.42) zakljucujemo da је w(k) ograniceno, i imajuci u vidu pretpostavke А2 i Аб, na osnovu (5.43) mozemo zakljuCiti da postoji slucajna promenljiva С takva da је ly(i) 1 < Cbeskonacno cesto sa verovatnocom 1 za w(i)EDR. Sada је prva pretpostavka za Teoremu 1 iz Ljungovog rada [Ljнng, 1977], zadovoljena. Sada cemo dokazati da \V(i) ={wi} posecuje skoro sigшno beskonacno cesto kompaktan podskup domena privlacenja jedne od asimptotski stabilnih tacaka, ео ili -ео, diferencUalne jednacine (5.16). Da bismo to postigli pokazacemo da postoji broj s takav da se dogadaj 1 wieo 1 :2: Е desava beskonacno cesto i skoro sigurno. Iz jednacine (5.5) imamo (5.44) Posle jednostavne transformacije dobijamo (5.45) Imajнci н .vidu jednaCinu (5.42) kao i to da pocev od nekog i, clan (1-y/yi) postaje pozitivan (imajuci u vidu da је pokazano da y(i) uzima vrednosti iz konacnog intervala), primenjнjuci potpuno iste korake kao u dokazu Leme З Ojinog i Karhunenovog rada [Оја, 1985], moze se pokazati da postoji broj Е takav da se dogadaj 1 wieo 1 :2: Е desava beskonacno cesto i skoro sigurno. Tako, mozemo zakljнciti da је нslov А8 Ljungove teoreme zadovoljen. Sad su svi нslovi Ljungove teoreme [Ljung, 1977] zadovoljeni. То znaci da је dokazano da pod datim нslovima, jednaCine (5 .3) i (5.4) uslovUavajн da \V konvergira, sa verovatnocom 1, ka transponovanom dominantnom sopstvenom vektoru matrice Rx. 82 83 o/PogГav(je -оо ОН metod. 5.3.Poredenje sa nekim poznatim algoritmima za ekstrakciju dominantne glavne komponente Као sto је vec prikazano и glavi 3, postoji brojna literatura koja se bavi proЬlemom implementacye РСА и neuralnim mrezama. Ovde cemo razmotriti slicnosti i razlike predlozenog соОН metoda sa reprezentima pojedinih klasa algoritama. А. Ojin zakon исеnја Prvo се biti izvrseno poredenje predlozenog zakona исеnја i Ojinog zakona исеnја. Poredenje sa pojedinim drиgim poznatim zakonima, kao sto је na primer SEC, necemo raditi jer је pokazano [Baldi, 1995] da sи mnogi poznati zakoni исеnја и sиstini ekvivalentni Ojinom zakonи исеnја. Na slici 5.2 је prikazan graf koji је ekvivalentan strukturi neuralne mreze koja se koristi za соОН i neke ekvivalentne transformacije koje prevode taj graf и jednostavnije forme. Sa slike 5.2 se jasno mogи иoCiti slicnosti i razlike izmedи predlozenog i Ojinog zakona исеnја. Aиtor ne zna za postojanje matematickog dokaza о ekvivalentnosti transformacija koje sи prikazane na slici, ali intиitivno, ako је promena pojacanja grana grafa veoma spora и poredenjи sa varijacijama veliCina na иlаzи grafa, rezиltati bi trebalo da Ьиdи veoma slicni sa slиcajem kada pojacanja grana grafa imajи konstantne vrednosti. Za konstantne vrednosti pojacanja grana grafa vidi [Chen, 1971]. Poredenjem соОН zakona исеnја sa Ojinim zakonom исеnја [Оја, 1982] moze se иoCiti nekoliko razlika. Ojin zakon исеnја ne primenjиje Hebov zakon исеnја direktno, dok соОН metod direktno primenjиje Hebov zakon исеnја. Drugim reCima, zahvaljиjиci иsvojenoj strиkturi mreze predlozeni metod koristi оЬа kraja sinapse simetricno, sto nije slиcaj sa Ojinim zakonom исеnја. Takode, соОН metod ne zahteva nikakva dodatna lokalna preracиnavanja- и. slисаји Ojinog zakona исеnја potrebna sи dodatna izracиnavanja (potrebno је izracиnati kvadrat postsinaptickog potencijala). Sa tehnicke tacke gledista (а Cini se i sa bioloske, takode) ovo se moze smatrati dobrom stranom predlozenog algoritma. 83 o/PogCavlie оо ОН metod 84 -w 1 а) Ь) с) VVk/(1-(1-vvvvт))= 1 /sqrt( vvvv т)*vvk/sqrt( vvvv т) Slika 5.2 Grafovska reprezentacija predlozenog zakona ucenja i njegove ekvivalentne transformacije koje dovode do struktura koje podsecaju na zakone ucenja predlozene u [Оја, 1982] i [Kohonen, 1982] (sa izuzetkom jednog dodatnog clana) (potrebno је uociti prisustvo dodatnog clana 1/sqrt(W\-Vт) - bazirano na rezultatima simulacija, ovaj dodatni clan nema znacajan uticaj na zakon ucenja koji је predlozio Ој а [Ој а, 1982]) Novi algoritam vrsi vremensku integraciju, sto nije slucaj sa Ojinim modelom. То se, takode, moze smatrati dobrom osobinom novog algoritma jer se Cini da је postojanje integracije neurotransmitera sasvim razumna pretpostavka. Kod Ojinog algoritma izlaz predstavlja lineamu komЬinaciju trenutnog stanja ulaza mreze. U ооОН metodu to nije slucaj, striktno govoreci. Medutim, iz analize predlozenog resenja se moze videti da nelineamost iscezava sa vremenom. В . Harpurova rekurentna korekcija greske (REC) REC mreza [Harpur, 1997] u slucaju mreze sa samo jednim izlaznim neuronom, ima identicnu strukturu kao i ооОН mreza kada se izabere 1-L =1 i у= 1. Takode, i zakon ucenja је identican. ооОН metod је razvijen bez ranijeg uvida u postojanje REC metoda (па REC metod је autoru skrenuta paznja tokom revizije rada [Jankovic, 2003а]). Medutim, postoji veoma bitna razlika u primeni zakona ucenja. Та razlika se ogleda u tome sto primena REC metoda podrazumeva da se ulazni signal odrzava konstantnim dovoljno dugo dok izlazni potencijal i 84 85 o/PogCavlie - oo ОН metod . proces modifikacije sinaptickih vrednosti ne dostignu stacionamo stanje. Та pretpostavka је nepotrebna za ооОН metod (sto se moze smatrati bioloski mnogo verovatnijim), i konsekventno matematicka analiza ооОН metoda se Ьitno usloznjava. U [Harpur, 1997], mreza sa samo jednim izlaznim neuronom nije Ьila posebno razmatrana. Jedan od razloga za to је i motivacija za dizajn algoritma. REC algoritam је usmeren na sto bolju rekonstrukciju ulaznog signala. Sa druge strane, kod ооОН metoda to је samo jedan od сЩеvа. Razlog za takav pristup је veoma jednostavan - ako karakteristike ulaznog signala nisu dobro lokalizovane u dominantnoj glavnoj komponenti onda ne mozemo govoriti о kvalitetnoj rekonstrukciji ulaznog signala. Medutim, u tom slucaju jos uvek mozemo postici perfektno potiskivanje ulaznog signala (sto је jedan od ciljeva ооОН metoda) - dominantna glavna komponenta се Ьiti precizno rekonstruisana dok се preostale komponente Ьiti ignorisane. ZnaCi, pored naCina primene REC i ооОН metod se razlikuju i u motivaciji koja је dovela do njihove konstrukcije. С: Pobednik-uzima-sve (Winner-Take-All, WTA) zakon ucenja "Pobednik-uzima-sve" ideja је osnova za nekoliko samoorganizujucih sistema [Grossberg, 1988]. U slucaju kada је korelaciona matrica ulaznog signala dijagonalna (sto znaci da su ulazne komponente medusobno dekorelisane) metod predlozen u ovom radu се rezultovati WTA zakonom ucenja. Drugim reCima samo се jedna sinapticka vrednost Ьiti razlicita od nule (u predlozenom slucaju се Ьiti jednaka 1). То dalje znaci da се samo jedna ulazna komponenta Ьiti predstavljena na izlazu i to ona koja odgovara dominantnom glavnom vektoru. Preostale komponente се Ьiti ignorisane. 85 o/PogG:zv fie -оо ОН metod 86 5.4. Generalizacija predlozenog algoritma za slucaj mreza sa vise izlaza Predlozeni metod se moze generalizovati za slucaj kada neuralna mreza ima vise izlaza. U slucaju GHA metoda [Sanger, 1989], generalizacija је jednostavna i u tom slucaju mreza се obavljati РСА. Takode, moguce је izvrsiti generalizaciju u smislu potprostomog kriterijuma [Оја, 1983][0ја, 1989] ili REC mreze sa vise izlaza i u tom slucaju се mreza obavljati PSA (u tom slucaju, struktura mreze је prikazana na slici 5.3). U slucaju da se izvrsi generalizacUa slicna tezinskom potprostomom metodu [Оја, 1992] mreza се obavljati РСА. Moguce је izvrsiti generalizaciju i na nesto drugaCiji naCin. Ako mreza ima vise od jednog izlaza i lokalne povratne veze u соОН algoritmu zamenimo globalnom povratnom vezom, to се rezultovati МН/МНО [Jankovic, 2001] PSA algoritmom. Тај metod се biti predmet analize н sledecem poglavlju. Slika 5.3 REC neuralna mreza 86 87 o/Pograv[je - СХЈ ОН metod. 5.5 Analiza и slucaju kada ulazna sekvenca пета srednju vrednost nula Ovde cemo ponoviti neke proracune za slucaj kada ulazna sekvenca nema nultu srednju vrednost. Bice usvojeno da za svako t, x(t) = х + xs(t) gde је х fiksni vektor i xs(t) simetricno distriЬuiran vektor sa srednjom vrednoscu nula. U tom slucaju је dominantni glavni vektor ulazne korelacione matrice Rx vektor х, i najveca sopstvena vrednost Rx је 1 +р, gde је р varijansa vektora xs(t). Sada cemo usvojiti oznake Rxs = E{xs хsт} i С= ххт. U tom slнcaju limEQ(w,x) = lim f( ft A(w)J~(w)x(j)x(k + 1) т /-'>ОО 1---'>00 J=l p=J+l r -t(Д~ О. Posle par transformacija dobijamo sledeCi izraz 87 o/Pog!дv[je-oo ОН metod ili . А-о ( з ) а ( 2 з ) а0 = а0 -а +-- а0 ---а , 2-а2 О l-a l-a2 О о з а 0 -а ao=(A-o-l) о 2-а 2 о Da bismo pokazali da gomja jednacina ima stacionamo stanje uocimo, ponovo, da је funkcija Ljapunova, posto је jednostavno proveriti daje (ako imamo u vidu daje Ло> 1) v <0. 88 ZnaCi, sada se moze izvuCi potpuno isti zakljucak kao i slucaju kada је srednja vrednost ulazne sekvenca bila nula. 88 о/Ј (]Jogfav{je :Мotfu{isani 1feбov (:мЈ!) metod- бiofoskj verovatan metod za izracunavanje (l>S.Jl МН metod predstvalja novi bioloski verovatan model koji vrsi PSA analizн. Metod је inspirisan delom strнktшe retine kod riЬa. U ovom, нvodnom, delн cemo posmatrati mrezн koja ima jednak broj нlaza i izlaza (N=К). Тај slнcaj nije od velikog prakticnog znacaja ali omogнcava jednostavno predstavljanje jednog zakona нсеnја koji се biti predstavljen н sledecem paragrafu. Bice pokazano da predlozena mreza нz predlozeni zakon нсеnја obezbed:нje da sinapticki vektori н stacionarnom stanjн predstavljajн Ьаzн potprostora koji је definisan korelacionom matricom нlazne sekvence slнcajnog stacionarnog signala. Da Ьismo predstavili novi zakon нсеnја ponovo cemo analizirati jednaCinн ( 4.18) koja је doЬijena pod pretpostavkom da је W тW=IN. Jednacina ( 4.18) moze Ьiti napisana kao N N IJ xrec - xll 2 = Ixi- LYi = min. (6.1) k=I k=I Као sto је vec pomenнto н prethodnom poglavljн objasnjeno н literatшi [Оја, 1992] ocekivana greska se minimizira kada se clan N LYi k=I maksimizira. Vec је objasnjeno kod SLA algoritma (poglavlje 4) da н slнcaju direktnog generisanja zakona нсеnја na osnovн gradijentnog metoda, postoji potreba za dodatnim о/Ј Pog(avfie-МН(О) metod 90 clanovima и zakonи исеnја koji bi obezbedili ortogonalnost sinaptickih vektora. Sada cemo pokazati nesto drиgaCiji pristиp koji се dovesti do novog zakona исеnја. Jasno је da desna strana jednaCine (6.1) (bez ikakvih dodatnih ogranicenja), takode, ne moze dovesti do stabilnog silaznog gradijentnog metoda jer је и tom slисаји minimalna vrednost -оо. Zato се sada biti razmotren novi kriterijиm (6.2) na osnovи koga se moze direktno generisati sledeCi silazni gradUentni metod: W(i + 1) = W(i) + y(i)( fx; (i)- IY; (i)Jx(i)y Т (i). k=l k=l (6.3) Nazvacemo ovaj metod Modиlisanim Hebovim (МН) algoritmom. Razlog za to је jednostavan- iz jednacine se vidi da zakon исеnја predstavlja Hebov clan koji је modulisan jednim jedinim signalom koji predstavlja razlikи energija иlaznog i izlaznog signala. Jasno se moze иociti da и ovoj jednacini ne postoje nikakva dodatna ogranicenja koja obezbedиju konvergencijи algoritma. Struktura neuralne mreze za implementacijи ovog zakona исеnја је prikazana na slici 6.1. Olaz s -.-·-------·---- Slika 6.1 Lokalno implementirana PSA neuralna mreza (s oznacava kvadratnи funkcijи) 90 91 о/Ј PogCavfie- МН(О) metod Sa slike 6.1 se uocava da predlozeni metod ima osobine lokalnosti i homogenosti sto predstavlja pozeljne karakteristike mreze koja se realizuje u paralelnom hardveru. Ovde necemo vrsiti deta~no poredenje ovog metoda sa drugim poznatim metodima, јег се to biti uradeno za slucaj МНО algoritma koji predstavlja modifikaciju ovog algoritma и slucaju kada је broj izlaznih neurona manji od broja ulaznih neurona, а sto је od mnogo veceg prakticnog interesa. Ovde cemo samo istaCi da se iz jednaCine (6.3) moze jednostavno uoCiti da modifikacija pojedinih sinaptickih tezina ne zahteva informaciju о eksplicitnoj vrednosti bilo koje druge sinapticke vrednosti. Takode, moze se uociti da је broj sumatora koji obavljaju globalne kalkulac~e uvek 2, bez obzira na broj ulaznih i izlaznih neurona. 91 о/Ј PogCav fie- МН(О) metod 92 6.1 Matematicka analiza МН metoda Sada cemo pretpostaviti da slиcajni иlazni vektor sa srednjom vtednoscи nиla, ostaje stacionaran и periodи koji је od interesa. U tom slисаји је mogиce primeniti stohastickи aproksimacijи kako је to vec radeno ranije [Ljиng, 1977] [Оја, 1985] . Usvoj icemo pretpostavkи da иlazni vektor ima medиsobno nezavisne komponente, sto znaCi da је aиtokorelaciona matrica С dijagonalna. Za implementacijи algoritma nije neophodno da komponente vektora х Ьиdи medиsobno nezavisne, ali takva pretpostavka znatno иproscava matematickи analizи koja sledi . Usrednjavanjem jednaCine (6.3) (detalji ovog postиpka se mogи videti и [Ljиng, 1977], [Оја, 1985]) i koriscenjem kompaktne notacije dobijamo s ledecи diferencijalnиjednacinн d W = diag(kшt(x))diag(I -WW т )w+ trace(c - WW т С ~W+ 2с(1 -WW т ~W, (6.4) dt gde diag(kшt(x)) predstavlja dijagonalnи matricи Ciji Sll dijagonalni elementi jednaki kшtozisн individнalnih komponenata нlaznog signala i pri сеmн је definicija kиrtozisa data sa Iz jednaCine (6.4) se moze jednostavno zakljнCiti da jedno resenje koje zadovoljava gornjн jednaCinн jeste W takvo da vazi WWт = I. Ovde necemo striktno analizirati jednacinн (6.4). Koristeti metod koji је slican onom koji sledi mogнce је pokazati da stacionarno stanje zal1teva da matrica M=WWт Ьнdе ortogonalna ako se W sastoji od N nezavisnih kolona. Ovde cemo detaljno analizirati samo jedan specijalan slнcaj jednacine (6.4) - нsvojicemo da Sll нlazni signali Gaнsovog tipa. U tom slнсајн za svakн individиalnи komponentн нlaznog signala imamo da јој је kнrtozis nнla, tako da sistem jednacina koji се biti analiziran mozemo pisati kao dWk = trace(c- WWTC~Wk +2C(I - WWT ~Wk , dt (6.5) 92 93 'III PogГavlie - МН(О) metod gde wk (k=l ,2, .. . , N) predstavUa k-tu kolonu matrice W . JednaCine dostizu stacionamo stanje u tackama u kojima vazi О = trace((I - WW т )с )cw k + 2с(1 - WW т )cw k (6.6) ili FCWk = _..!_trace(F)CW k, gde је . 2 F = 2с(1 -WW т). Iz ove jednaCine је jasno da sistem pokusava da nade sopstvene vektore matrice F i da su ti vektori predstavljeni sa CWk. Sada се Ьiti pokazano da ako matrica W ima N nezavisnih kolona (rank(W) = N) tada mora Ьiti WтW=I. Iz jednaCine (6.6) је jednostavno zakljuciti da jedno od resenja predstavlja i W takvo da је WWт=I. U tom slucaju је F=O. Sada cemo pretpostaviti da postoji drugo W takvo da је rank(W) = N i da је W resenje jednacine (6 .6) . Iz jednaCine (6.6) tada vidimo da matrica F ima N lineamo nezavisnih sopstvenih vektora koji svi imaju sopstvene vrednosti -0.5 trace(F) . Sa druge strane, poznato је da suma svih sopstvenih vrednosti matrice F mora Ьitijednaka trace(F). Tada imamo а sto је moguce jedino u slucaju N - - trace(F) = trace(F) 2 trace(F) =О. U tom slucaju matrica F ima sve sopstvene vrednosti jednake nuli i tada sledi da mora Ьiti F=O. Drugim recima, ako је rank(W) = N, tada matrica F mora biti nula i to је moguce samo u slucaju sto znaCi da vazi w т w = 1. Ako oznaCimo wwт sa М, tada na osonovu jednacine (6.4), а za slucaj ulaznog signala Gausovog tipa, doЬijamo gdeje dM - = 8СМ + 2C(I- М)СМ +М Сд+ 2MC(I- М)С, dt (6 .7) 93 о/Ј PogГav{fe- М Н (О) metod 94 8 = trace (с -WW т С). OznaCimo sada sa mk k-tu kolonu matrice M(k) = W(k)W(k)т. Sada bi bilo potrebno dokazati da mk posecuje skoro sigurno beskonacno cesto kompaktan podskup domena privlacenja asimptotski stabilnih tacaka jednaCine (6.7). Pronalazenje domena privlacenja i dokazivanje gomje osoЬine је veoma tezak zadatak. Ono sto се Ьiti receno ovde (i sto је cesto korisceno н literaturi - na primer [Ој а, 1992Ь ]) је da u svim simнlacijama u kojima је postignuto stacionamo stanje, ono koincidira sa staЬilnim resenjimajednaCine (6.7). Sada cemo dokazati da M=l predstavlja asimptotski staЬilno resenje jednacine (6 .7) . Da Ьismo to uradili primenicemo istu proceduru koja је primenjena kod dokaza teoreme 1 u [Ој а, 1992]. Као sto је to vec objasnjeno u prethodnom tekstu (poglavlje о ооОН) analiza koja sledi се Ьiti uproscena ako se pretpostavi da su sve sopstvene vrednosti matrice С razliCite i pozitivne. Da Ьismo dokazali asimptotsku staЬilnost resenja M=l, posmatracemo male perturbacije E(t)={eu} u odnosu na stacionamu tacku M=l. Tada imamo M(t) = 1 + E(t). Tada za E(t) vazi, odnosno dE - = trace(CE)c(l +Е)- 2CEC(I +Е)- trace(CEXI +Е )с- 2(1 +Е )сЕС dt = 2(trace(CE)c + 2СЕС)- trace(cEXEc +СЕ) - 2СЕСЕ- 2ЕСЕС dE = -2(trace(CE)C+ 2СЕС)+ 0(\\Е\\ 2 ), dt gde O~IE 11 2) predstavlja matricu koja se sastoji od clanova drugog reda eu matrice Е. (6.8) (6.9) Ako usvojimo da је IIEII dovoljno malo, lineami deo (ро Е) jednaCine (6 .9) odreduje asimptotsku staЬilnost. U tom slucaju, elementi matrice Е koji se nalaze van glavne dijagonale, zadovoyavaju sledeCi skup jednaCina: 94 95 о/Ј РоgШ:vГте - МН(О) metod de - 1 -u = -4с с .е . dt t Ј U (6.10) i ;:f. ј, gde ci, с1 predstavljaju i-ti i j-ti dijagonalni element matrice С, respektivno. Iz jednaCine (6.10) је jasno da eu ~О (tezi asimptotski ka nuli), kada se ima u vidu da su sve sopstvene vrednosti matrice С pozitivne. Dijagonalni elementi matrice Е zadovoljavaju sledeCi skup jednaCina: de ·· LN 2 - 11 = -2с· с ·е ·· -4с · е·· dt 1 . Ј ЈЈ 1 11' ј=1 (6.11) i = 1,2, ... ,N. Definisimo V kao N V=Ieй. (6.12) i=1 Kako је Ј!гО i dV ( N [ N 2 ]Ј -=-4 "'е ·· с·"'с · е .. +2с·е· · dt ~ 11 1 ~ Ј ЈЈ 1 11 i=1 }=1 = -4(~ е .. с · [~ с · е .. Ј+ 2~ с~ е~ Ј 11 1 Ј ЈЈ 1 11 i=1 }=1 i=1 (6.13) = -4(["' е ·· С·Ј 2 + 2~ с~ е~]< О ~111 ~ -, i=1 V predstavlja funkciju Ljapunova. Sada mozemo zakljuciti da (6.11) konvergira. Jednostavno se uocava da V konacno dostize svoj minimum V=O sto znaci da је eu = О za svako i,j. Drugim reCima, pokazali smo da, pod pretpostavkama koje su usvojene, predlozeni algoritam dovodi do toga da је matrica М ortonormalna. 95 о/Ј PogГavfie- МН(О) metod 96 6.2 Poret/enje usvojene strukture sa delom retine kod riha U literaturi postoji vise algoritama za neuralne mreze za koje se tvrdi da predstavljaju bioloski verovatne modele (videti [Foldiak, 1992], [Fyfe, 1995], [Harpur, 1997]). Neki od rezultata su bili direktno inspirisani psihofizickim rezultatima doЬijenim ispitivanjem retine (vidi [Atick, 1990; Atick, 1992; Atick, 1993], [Goodall, 1960]). U tim radovima, medutim, cilj autora nije Ьiо da formiraju strukturu neuralne mreze koja Ьi imala slicnosti sa Ьioloskim uzorom vec samo ostvarivanje slicne prenosne funkcije . Sa druge strane МН algoritam (i njegov derivat МНО) su zapravo insipirisani delom strukture retine kod riЬa. Slika 6.2 predstavlja aproksimaciju dela retine riЬe koja је prikazana u (Dowling, page 76, Fig. 3.17). Slika 6.2 Uproscen prikaz dela retine riЬe (IВ- invaginacione Ьipolame celije; Н- horizontalne celije; IP - interpleksiformne celije; А- amarkrine celije; FB - ravne Ьipolame celije; Gi - ganglione celije; R Т- krajevi stapica) 96 97 о/Ј IPogГav[ze- МН(О) metod Poredenjem sa strukturom МН mreze koja је prikazana na slici 6.1, mozemo uoCiti veoma veliki stepen slicnosti sa vezama izmedu IВ, Н, А i IP celija. Iako autor nema nikakve rezultate koji bi ukazivali i na funkcionalnu slicnost, visok stepen struktume slicnosti moze ukazivati i na postojanje odredene verovatnoce о postojanju slicnosti u funkcionalnom smislu. Ako imamo u vidu da је u referencama [Atick, 1992], [Deco, 1996] sugerisano da је cilj preprocesiranja koje se odvija u retini, u stvari transformisanje vizuelnog ulaza u sto је moguce vise dekorelisanu bazu (u model koji sadrzi manji stepen redundantnosti ili generalnije, u statisticki nezavisnu reprezentaciju u korteksu), mozemo reCi da predlozeni metod zasluzuje da bude analiziran kao bioloski moguc. U literaturi su opisana bioloski moguca resenja (na primer [Atick, 1993]) koja modeluju sveukupno procesiranje koje se obavlja u retini. Medutim, ta resenja nisu bila usmerena na imitiranje strukture retine. U referenci [ Atick, 1993] su analizirani razliCiti aspekti procesiranja koje se obavlja u retini - kao sto su lokalizacija prijemnih polja koja bi odgovarala ganglionim celijama retine, ili proЫem simetrije. Ovde ti proЬlemi nisu detaUnije analizirani ali se moze reCi da bi se proЫem simetrije mogao resiti na putu od bipolamih do ganglionih celija u nekom medusloju, ili delimicnom modifikcijom predlozenog zakona ucenja. 97 о/Ј Роg[щ;{је- МН(О) metod 98 6.3 Modulisani НеЬ-Оја zakon ucenja U slucaju kada је broj izlaznih neurona manji od broja ulaznih neurona МН metod се rezultovati ortogonalnim sinaptickim vektorima ali ti vektori vise nece Ьiti ortonormalni. Da Ьi se odrzala ortonormalnost kolona sinapticke matrice W, potrebno је izvsiti modifikaciju zakona ucenja. Jedna mogucnost је implementacija ооОН metoda. Medutim, u tom slucaju је matematicka analiza veoma komplikovana. Posto је kod analize ооОН metoda pokazano da postoji slicnost sa Ojinim zakonom ucenja, ovde се kao dodatak МН metodн па svaki pojedinacni sinapticki vektor Ьiti primenjen Ojiin stabilizacioni clan. U tom slнcaju zakon ucenja od intersa se izrazava sledecom jednaCinom: W(i + 1) = W(i) + y(i)(x(i) Т x(i) -y(i) т y(i) ). (x(i)y(i) Т-W(i)diag(y(i)y(i) т)). (6.14) Ovaj zakon нсеnја cemo nazvati Modulisanim НеЬ-Оја zakonom нсеnја (МНО). Primenjen na mrezi koja је prikazana na slici 6.1, ovaj zakon нсеnја generise sinapticku matricu W, Cije kolone pokrivajн potprostor koji definise N dominantnih sopstvenih vektora matrice С . 98 99 о/Ј Pog[av[ze - МН(О) metod _ 6.4 Matematicka analiza МНО metoda U analizi koja sledi pretpostavicemo da је ulazni signal stacionaran i da mu је srednja vrednost nula. Takode, da bi se analiza uprostila, pretpostavicemo da su komponente ulaznog vektora medusobno nezavisne (bez te pretpostvake analiza koja sledi Ьi Ьila znatno komplikovanija). Primenom stohasticke aproksimacije asimptotski staЬilna resenja jednaCine (6.14) se mogu doЬiti resavanjem sledece jednacine (koja је od jednacine (6.14) doЬijena usrednjavanjem) d W = (ctiag(kurt(x) )diag(I- WW т)+ tr(c- WW т С~+ 2с(1-WW т~ )w dt - Wdiag(wт (ctiag(kurt(x))diag(I- vvwт )+ tr(c-wwт С~+ 2с(1- wwт ~ ~V ). (6.15) U analizi koja sledi Ьiсе analizirane staЬilne tacke jednacine (6.15) kao i njihova oЬlast privlacenja. Da Ьi se dokazalo da originalni diskretni algoritam (6.14) ima iste stacioname tacke Ьilo Ьi potrebno dokazati da (6.14) posecuje skoro sigumo, beskonacno cesto kompaktan podskup domena privlacenja asimptotski staЬilnih resenja jednaCine (6.15). Mora se reCi da је takav dokaz veoma tezak i da taj deo dokaza ne postoji za veCinu poznatih algoritama. Na bazi iskustva, generalno se moze reci da ako zeljena staЬilna tacka diskretnog algoritma ne koincidira sa nekom od asimptotski staЬilnih tacaka pridruzene diferencijalne jednaCine, tada do konvergencije diskretnog algoritma nece ni doCi [Оја, 1992]. Ovde се Ьiti naglaseno da su u svim simulacijama koje su radene i u kojima је algoritam (6.14) konvergirao, staЬilne tacke algoritma koincidirale sa asimptotski staЬilnim resenjima jednaCine (6.15). Prvo се Ьiti pokazano da (6.15) obezbeduje da u stacionamim tackama vazi : т W W=Iн. (6.16) Ako usvojimo da ulazni signali zadovoljavaju Gausovu raspodelu (kurt (х) = 0), jednaCina ( 6.15) poprima sledeCi oЬlik 99 о/Ј PogCav[ie- МН(О) metod 100 dW = (tr(c- wwтc~+2c(I- wwт ~)w dt - Wdiag(wт(tr(c- wwтc~+2C(I- wwт ~)w). (6.17) Od ovog momenta cemo analizirati samo slucaj kada ulazni signal zadovoljava Gausovu raspodelu jer се to jednacine uciniti manje komplikovanim i analizu koj a sledi jednostavnijom. Analiza koja sledi se moze primeniti i bez te pretpostavke ali jednacine postaju znatno slozenije i analiza znatno komplikovanija. Iz jednacine (6.17) је jasno da sistem pokusava da pronade sopstvene vektore matrice F=(tr(C-WWтC)*2C(I-WWт)C) i da su ti sopstveni vektori predstavljeni kolonama matrice W . Moze se jednostavno zakljuCiti da ako matrica W ima N nezavisnih kolona (rank(W)=N) tada mora biti WтW=I jer је matrica F realna i simetricna. OCigledno da ista analiza moze Ьiti sprovedena i zajednaCinu (6.15). Sada се Ьiti pokazano da resenje W ima range (potprostor definisan kolonama matrice W) koji је ekvivalentan potprostoru koji је definisan sa N sopstvenih vektora matrice С koje odgovaraju najveCim sopstvenim vrednostima, pod pretpostavkom da (6.16) vazi aproksimativno (drugim recima wтw = 1). Moze se uoCiti da se jednaCina (6.14) moze predstaviti sa W(i + 1) = W(i) + y(i)~(i)(x(i)x(i) т W(i) - W(i)O(i)), ~(i) = x(i) Т x(i) - y(i) Т y(i) = tr(x(i)x(i) Т - y(i)y(i) т), (6.18) sto predstavUa PlamЬlijevu generalnu stohasticku aproksimaciju [PlumЬley, 1991] sa izuzetkom clana ~i) . Bice pokazano da Ьilo koji algoritam iz klase (6.18) dovodi do identicnih uslova za konvergenciju ortogonalne projekcije P(i) na range od W(i), bez obzira na pojedinacni izbor 8(i), pod uslovom da је rank(W) maksimalan za svako i. Bice pokazano da ta ortogonalna projekcija konvergira ka projekciji Р н koja је projekcUa na N-dimenzioni glavni potprostor matrice С. Ortogonalna projekcija na range W(i) је (pod pretpostavkom da је W(i) maksimalnog ranga za svako i) (6.19) jer је P(ii=P(i), P(i)т=P(i), i range P(i) i W(i) su isti ([PlumЬley, 1991]). 100 101 'V'I PoвГavfie- М Н( О) metod Teorema 6.1 Ako је \V(i)тW(i) invertibilna matrica i 11 W(i)тW(i)ll i II(W(i)тW(i))- 1 11 su ograniceni za svako i, algoritam (6.18) za W(i+1) rezultuje sledecim algoritmom za P(i+1) gdeje P(i + 1) = P(i) + y(i)L1P(i) + O(y(i) 2 ) , дР(i) = (I- P(i))(tr((I- W(i)W(i) т FCi) fCi) f(i) + P(i)(tr((I- W(i)W(i) т ~(i) ~(i) JI- P(i) ), C(i) = x(i)x(i) Т. (6.20) (6.21) Dokaz Dokaz се biti izveden ро slicnom postupku koji је primenjen za dokaz teoreme 3.3.1 u [PlumЬley, 1991] . Napisimo (6.20) kao W(i + 1) = W(i) + y(i)L1 W(i) + O~(i)2 ) gdeje д W(i) = ~(i)(x(i)x(i) т W(i)- \V(i)8(i) ). Sada oznacimo R(i)=W(i)тW(i), tako da sledi gdeje R(i + 1) = W(i + 1) TW(i + 1) = (w(i) + у(i)д W(i) + O~(i)2 )У (w(i) + у(i)д W(i) + O~(i) 2 )) = R(i) + y(i)дR(i) + O~(i) 2 ), Ako pretpostavimo da vazi 101 о/Ј CJ>ogCavfie- МН(О) metod za svako i, R(i+1)- 1R(i+l)=l = R(i + 1) - 1 (R(i) + y(i)дR(i) + O(y(i) 2 )) sto rezultuje sa R(i + 1)-1 = R(i)-1 - y(i)R(i)-1 (дR(i))R(i)- 1 + O(y(i) 2 ), а to dovodi do sledece jednaCine gdeje P(i + 1) = W(i + 1)(W(i + 1) т W(i + 1) )-1 W(i + 1) т = (wu) + r(i)дW(i) + o~(i)2 )~и+ 1)- 1 (wci) + r(i)дW(i) + o~(i)2 ))т = P(i) + y(i)дP (i) + O(y(i)2 ), дР(i) = (1- W(i)R(i)-1 W(i) т ~W(;)R(i)- 1 W(i) т + W(i)R(i) - 1 L1 W(i) т (1- W(i)R(i) - 1 W(i) т) = ((1- Р(i))д W(i)R(i)-1 W(i) т)+ ((1- Р(i))д W(i)R(i)-1 W(i) т )т. Sada, posto је д W(i) = ~(i)(x(i)x(i) т W(i)- W(i)G(i) ), posle nekoliko jednostavnih transformacija dobijamo дР(i) = (1- P(i)~tr((1-W(i)W(i) т ~(i) ~(i) f(i) + P(i)(tr((l- W(i)W(i) т ~(i) ~(i) Xl- P(i)). 102 102 103 о/Ј PogГavl/e - М Н (О) metod Ovim је teorema dokazana. Primenom stohasticke aproksimacije, Р u (6.20) i (6.21) moze biti pridruzena sledeca diferencyalna jednaCina dP - = (1- P)(tr((l- Р )с )с+ 2C(I- Р )с)Р dt pod pretpostavkom da vazi + P(tr((l- Р )с )с+ 2C(I- Р )cXI- Р), т WW ::::::Р. (6.22) (6.23) Pod pretpostvakama koje su analizirane na pocetku ove sekcije, Р u (6.22) i (6.23) tezi skoro sigurno ka asimptotski stabilnim resenjimajednaCine (6.22). Sada navedimo sledecu Lemu, koja се nam biti od koristi u analizi koja sledi. Lema 6.1 ([Ogawa, 1987], [Brocket, 1991а]) Ako је Х nxn Hermitova matrica Ciji је rang rang(X)=r i neka је Qk neka nxk matrica, k ::=:; r, sa k ortonormalnih kolona. Tada, za dato Х, tr(Q/XQk) se maksimizira kada је Qk=VEk gde V oznacava matricu ortogonalnih sopstvenih vektora matrice Х i Ek predstavlja matricu sa k ortonormalnih kolona koja zadovoljava EkE/=Ik (lk oznacava dijagonalnu matricu Cijih је prvih k dijagonalnih elemenata jednako 1 dok su ostali dijagonalni elementi jednaki nuli). Sada cemo analizirati ponasanje diferencyalne jednaCine (6.22). Prvo cemo pokazati da vazi sledeca teorema. Teorema 6.2 U jednacini (6.22) Р izvodi najbrze opadajuce pretrazivanje kvadrata greske u rekonstrukciji ulaznog signala, definisanog sa (6.24) Dokaz: Mozemo napisati S kao: (6.25) Znamo da vazi (1 - р? = (1 - р). 103 о/Ј РоgГдvГ,е М Н( О) metod Kako је Р= Р2, imamo d Р = ( d Р )Р +Р( d Р), dt dt dt tako (l _Р) dP = (dP)p dt dt (1-Р)- = (1-Р - Р dP {dP) dt dt Sadaje jednostavno uociti da vazi dP dP dP - = (1-Р)-Р+Р-(1-Р). dt dt dt Tada vazi -= -2tr((1-P)c)tr -С . dS (dP ) dt dt Na osnovu jednacina (6.22) i (6.24) i posle nekoliko transformacija doЬijamo d S = -4tr2 ((1- Р )c)tr((l- Р )сРс) dt - 8tr((1- Р )c)tr(C(I- Р )cPC(I- Р)) . 104 (6.26) (6.27) (6.28) Kako su СРС i (1-P)CPC(I-P) realne simetricne matrice i imajuCi u vidu Lemu 6.1 mozemo zakljuCiti da dS ~О dt (6.29) 104 105 о/Ј Pog&zv[ie- МН(О) metod pri cemu se jednakost postize samo u slucaju СР=РС (sto takode znaCi i da је dP/dt=O). Mozemo zakljuCiti da Р i С komutuju u stacionamim tackama algoritma (6.28) koje su u isto vreme i stacionarne tacke algoritma (6.22). То znaCi da Р ima iste sopstvene vektore kao i С, sto znaCi da Р mora biti ortogonalna projekcija na potprostor koji је definisan nekim od sopstvenih vektora matrice С . Koriscenjem informacionog kapaciteta sistema (u slucaju da smatramo da је sfemi Gausov sum prisutan na ulazu) i odgovarajuce funkcije Ljapunova, pokazacemo da је potprostor koji се biti pokriven u stvari potprostor koji је definisan dominantnim sopstvenim vektorima matrice С. Metod za dokaz је veoma slican metodu koji је koriscen u [Plumbley, 1991] . Informacioni kapcitet na izlazu, od interesa za nas slucaj , је definisana kao lc = lc(Y;Q) = _!_(log(det(w т CW ))-log(det(cr~ ~V т w))), 2 х (6.30) gde У predstavlja izlaz mreZe, О sfemi aditivni Gatlsov Sum na izlazu, rЈФх је varijansa ulaznog suma. Sada mozemo predstaviti sledecu teoremu: Teorema 6.3. Funkcija (maxp(lc)- lc) је funkcija Ljapunova za algoritam (6.22). Algoritam се biti stabilan u tackama u kojima је Р projekcija na neke od sopstvenih vektora matrice С. Dokaz Koriscenjem identiteta d ( dV) - et(V) = tr adj(V)- , dt dt (6.31) gde је adj(V) adjungovana matrica matrice V, dobijamo -log(det(v))= tr асђ(V)- = tr V -d 1 ( . dV) ( -1 dV) dt det(V) dt dt (6.32) pod uslovom da је V invertiЬilna matrica. Nalazenjem izvoda Ic u (6.30) rmamo (posle nekoliko jednostavnih transformacija) 105 о/Ј PogГavlie- МН(О) metod 106 d!c = tr((wтcw )- 1 wт c(I -P)d w). dt dt (6.33) Posto је PW=W dobijamo (6.34) dP W=(I-P)dW dt dt (6.35) i to daUe znaci da vazi dlc = tr((wтcw)-lwтcdP w). dt dt (6.36) Mozemo jednostavno zakljuciti da poslednja jednaCina zavisi samo od forme algoritma za matricu Р , а ne i od forme algoritma za matricu W. Zamenom (6.22) u (6.36) dobijamo d:; =t{(wтcw)-1 wтcpw }r((I - P)c) +2t{(wтcw )- 1 wтc(I- P)c(I -P)cPw} Posle par transformacija to dovodi do d:; ~ tr((r- P)c)t{ (r- r)cw(w т cw Г' w т c(r- r)) +t{ c((r -P)cw(wтcw Г' w тc(r-r))) ~о , (6.37) (6.38) pri cemu se jednakost ostvaruje samo u slucaju da vazi (1-Р)С=О (posto је (WтCW)" 1 pozitivno definitna). ZnaCi, predlozeni zakon ucenja, kada se razmatra u kontinualnom domenu, dovodi do toga da је informacioni kapacitet sistema neopadajuca funkcija u 106 107 о/Ј PogCav{je - М Н( О) metod vremenu, i dostize stacionarno stanje samo u slucaju kada је Р projekcija na neke od sopstvenih vektora matrice С. Nazalost, to nam jos uvek ne ukazuje na to koje su od stacionarnih tacaka stabilne i koj i ј е njihov domen privlacenja. То znaCi da moramo postiCi "snazniji" rezultat. Тај rezultat se bazira na cinjenici da Р nikada nece pronaci potprostor koji је definisan sa N dominantnih sopstvenih vektora matrice С ako nema komponente u pravcu svake od njih na pocetku. Drugim reCima, ako је pocetna vrednost det(WтQNW)=O, gde је QN projekcya na N- dimenzioni glavni sopstveni potprostor matrice С, predlozena klasa algoritama nece pronaci dominantni sopstveni potprostor. Ovde QN predstavlja jednu vrstu pseudo-kovarijansne matrice koja daje jedinicne tezine za N dominantnih glavnih komponenata matrice С, i tezinu nula za preostalih K-N komponenata. Primetimo da pri izvodenju (6.38), nismo koristili nikakve posebne osobine matrice С (osim daje matrica kvadratna i simetricna). Na osnovu (6.30) pravimo novu funkciju : (6.39) u kojoj wтQNW zamenjuje wтcw. Sada mozemo predstaviti sledecu teoremu Teorema 6.4. Funkcija (maxp(IQN) - lQN) predstavlja Ljapunovu funkciju za algoritam (6.22). Algoritam се biti stabilan u tackama u kojima је Р projekcija na glavni sopstveni potprostor matrice С. Dokaz. Ako је det(WтQNW};z:O imamo ddtiQн = t{(wтQNw)-JwтQн~~w) =А+ В, gde su А = tr{(I-r)c{ tr((wтQNw}1 wт QNcw )- t{(wтw}1 wтcw )Ј в= 2t{(wт QнW )- 1 wт Qн (I-P)c(I -P)cw). (6.40) 107 о/Ј PogГavlie - МН(О) metod 108 Ako imamo u vidu da је Qi=Qн i da Qн iste sopstvene vektore kao С onda vazi QнС=Qн(QнС)=QнСQн. Posto znamo da је Qн ortogonalna projekcija na potprostor definisan sa N dominantnih sopstvenih vektora matrice С, mozemo pisati Qн=qq т gde ј е q ortonormalna matrica Cije su kolone N dominantnih sopstvenih vektora matrice С. Na osnovu toga sledi W1QнW=W1qq1W gde је W1 q NxN nesingularna kvadratna matrica, i det(w т qJ = det(w т Qн W)* о. (6.41) Tadaje А= tr((I- Р )cXtr(QнC) - tr(Pc)). (6.42) Iz prethodne analize (Lema 6.1 ), znamo da је tr(PC) maksimalno kad Р pokriva N dominantnih sopstvenih vektora matrice С, ра mozemo zakljuCiti daje А~О. Takode је (imajuci u vidu (6.23)) в= 2t{(wт QнW )- 1 wт Qн(I -P)c(I -P)cw) = 2t{ w(wтQнw)-1 wтQнC(I-P)c-Pc(I -Р )с} (6.43) Definisimo ( т )-1 т Pl=WW QнW W QN. (6.44) Tada, nije tesko uociti da је Pl idempotentna matrica, posto је P1 2=Pl. ImajuCi u vidu cinjenicu daje (I-P/=(1-P), dobijamo В= 2tr((I- Р )cPl PlC(I- Р))- 2tr(w т (C(I- Р )c)w) = В1-В2 gdesu Bl = 2tr((I- Р )cPl PlC(I- Р)), в2 = 2tr(w т (c(I- P)c)w). (6.45) 108 109 'V'I PogГa.vfie - М Н (О) metod Nije tesko zakljuciti da је ВГ~О. Takode, na osnovu Leme 6.1 znamo da је В2 maksimalno kadaje W takvo da P=WWт pokriva N dimenzioni dominantni potprostor matrice С . U tom slucaju Р i С komutuju. Tada imamo da је maksimalna vrednost В2 В2 _ max = 2tr(PC(I- Р )с)= 2tr(CP(I- Р )с)= О. То znaCi daje В2 ~О. Na osnovu toga zakljucujemo daje (ako је det(WтQнW):;t:O) d -IQ ~о dt N pri cemu se jednakost ostvaruje samo za Р=Qн. Iz svega navedenog zakljucujemo daje (maxp(JQн) -IQн) nasa funkcija Ljapunova. (6.46) (6.47) Domen privlacenja је skup W takav da za sve dominantne sopstvene vektore ~i matrice С (1~ i ~ N), wт~i :;t: О. Ukratko, pod pretpostavkama koje su napravljene na pocetku ove sekcije, pokazali smo da algoritam (6.22), а posledicno i algoritam (6.17), konvergira ka W koje pokriva N-dimenzioni dominantni potprostor matrice С, pod uslovom da matrica W(i) ima maksimalni moguCi rang za svako i. 109 'f)J Pog[a:vl/e- МН(О) metod 110 6.5 Rezultati simulacija Sada cemo prikazati rezultate simulacija za mali sistem. Broj ulaza је К= 5 а broj izlaznih neurona је N = 3. Ulazni vektor sa srednjom vrednoscu nula i nekorelisanim komponentama је definisan sledeCim jednacinama: x(l, i) = .9 * sin(i/2); x(2,i) = .9 * ((rem(i,23) -11)/9).л5; х(З, i) = .9 * ((rem(i,27) -13)/9); x(4,i) = .9 * ((rand(1,1) < .5) * 2 -1) . * log(rand(1,1) + .5); х(5, i) =- .5 + rand(l, 1 ); Slika 6.3 prikazjuje kako se menja "ortogonalnost" matrice W u odnosu na broj iteracija za МНО algoritam (inicijalna vrednost matrice W је Winit = 0.1 *rand(5,3); usvojen је konstantan faktor ucenja у = 0.015). Rezultati predstavljeni na slici 6.4 prikazuju kako se menja ortonormalnost matrice W u odnosu na broj iteracija za МНО algoritam pri cemu komponente uzlaznog vektora nisu dekorelisane vec predstavljaju linearnu kombinaciju komponenata vektora xm(i) = mix*x(i) (inicijalna vrednost matrice W је Winit = 0.1 *rand(5,3); matrica koja definise lineamu kombinaciju је mix = -.15+.3*rand(5,5); usvojen је konstantan faktor ucenja у = 4.0). Ortonormalnost matrice W је definisana kao 11 1-WтW 11 F, gde F predstavlja Frobenijusovu normu. 1.8.-----.---г---т----.---т----т--....------..---т----. 1.6 1.4 о~-~--~~==~~~~~~~~~~~~-~~~~ о 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 NшnbOI" or itOI"atiOliS Slika 6.3. Mera ortonormalnosti u odnosu na broj iteracija (ulazni vektor ima dekorelisane komponente) 11 о 111 1.8 1.6 1.4 1.2 ъ = "' 1 Е "' = ,s 0.8 б 0.6 0.4 0.2 о о о/Ј Pog&:vГze- МНС О) metod 0.5 1 2 2.5 3 3.5 4 4.5 5 Nwnbe1· of ite1·atioпs х 104 Slika 6.4 Мега ortonormalnosti u odnosu na broj iteracija (komponente ulaznog vektora su medusobno korelisane) Moze se uoCiti da algoritam brze konvergira u slucaju kada su komponente ulaznog vektora dekorelisane. 111 о/Ј PogГav(ze- МН(О) metod 112 6. 6 Poretlenje sa poznatim PSA algoritmima Sada cemo izvrsiti poredenje predlozenog metoda sa nekim od poznatih metoda kao sto su SLA [Оја, 1989] i Foldiakova bocna inhiЬiciona mreza (FLIN) [Foldiak, 1991]. Sledece dve slike prikazuju PSA mreze za SLA i FLIN algoritam, respektivno. ОЬе slike sadrze "paнkova mreza" komponentu koja naglasava prisustvo modulacionaog signala u zakonu нсеnја, а koji se takode moze uoCiti i na slikama 6.1 ili 6.3. х, Х к х, Х к • • • /~~ f ј 1 ,~ ~ Slika 6.5 SLA neшalna mreza Slika 6.6 Foldiakova bocna inhiЬiciona neшalna mreza 112 113 'V'I PogШvfie - МНСО) metod Tabela 6.1 sadrzi jednaCine koje se koriste za izracunavanje vrednosti potencijala izlaznih neurona za odgovarajucu PSA rnrezu, kao i jednaCine za izracunavanje vrednosti poj edinih sinapsi na bazi predlozenog zakona ucenja za dati PSA algoritam. Individualne komponente vektora x(i) i y(i) su oznacene sa Xn (n-ta individualna kornponenta) i Уп, dok su clanovi pojedinih rnatrica oznaceni sa "1-Vk/. Faktor ucenja za SLA i FLIN је у =у (i), dok ј е za МНО slucaj у=]'(i)(хтх-уту) =y(i, х, у) . Tabela 6.1 Pregled nekih PSA algoritama Skr. Zakon ucenja Izlaz mreze Broj operacija Broj kola za globalana izracunavanja SLA !lwkl = r У{ч -±y;wki Ј у = Wтх Mnozenje: 4KN к SaЬiranje: 2KN-N I=l мно !:J.1-vkf = r(чyz - "~-vkzYT) у=Wтх xтx:;t:CQNST 2 r = r . (х т х - у т у) Mnozenje: 4KN+K+N+ 1 SaЬiranje: 2KN +К -1 xтx=CONST Mnozenje: 4KN+N+ 1 SaЬiranje: 2KN FLIN t:J.wkz = r(xkyz-wk!YT) y = Wтx+Qy Mnozenje: о t:J.q Ј р = -r У Ј У Р 4KN+ ЗN(N-1 )/2 SaЬiranje: 2KN+N(N-3) Poredenjem sa SLA algoritmom mozemo videti da МНО algoritarn ne zahteva podatak о eksplicitnoj vrednosti sinapse koja је vezana za Ьilo koji drugi neuron. Takode, broj kola za globalna izracunavanja је 2 u slucaju МНО, а К u slucaju SLA algoritrna. Jedina globalna 11 з '1/Ј c:Pog(m;{je- МН(О) metod 114 izracunavanja koja su potrebna u slucaju МНО algoritma su izracunavanja energije koja se sadrzi u ulaznom i izlaznom signalu. Sa druge strane, broj izracunavanja koje zahteva SLA algoritam је manji od broja kalkulacija koji se zahteva za realizaciju МНО algoritma. U slucaju FLIN algoritma sva izracunavanja koja su vezana za modifikaciju sinaptickih vrednosti su strogo lokalnog karaktera. Cena koja је placena za lokalnost izracunavanja је: prisustvo anti-Hebove mreze koja povezuje sve izlazne neurone kao i povecanje broja operacija koje је neophodno za izracunavanje vrednosti izlaza. Nije tesko uociti da realizacija МНО algoritma zahteva manje memorijskih lokacija nego u slucaju FLIN algoritma (FLIN algoritam zahteva dodatne memorijske elemente za cuvanje elemenata matrice Q). Takode, u mnogim slucajevima, realizacija МНО algoritma zahteva manju slozenost izracunavanja (ili hardvera) nego realizacija FLIN algoritma. То vazi za slucajeve kada ne postoji veoma znacajna razlika u broju ulaznih i izlaznih neurona (N2 >К). U slucaju da se energija ulaznog signala odrzava konstantnom na nekom odredenom nivou, uz pomoc nekakvog spoljnog kola, МНО algoritam uvek ima manju kompleksnost izracunavanja nego FLIN algoritam bez obzira na broj izlaznih neurona. То se jasno moze uoCiti iz Tabele 6.1. Interesantno је zapaziti da МНО algoritam u formi koja је predlozena, u stvari obavlja Ojin zakon ucenja na pojedinacnim sinaptickim vektorima UZ samo jednu razliku - faktor ucenja у је specificno "programiran" od strane same mreze. U ovom slucaju r ima inherentnu osoЬinu da se smanjuje kako vreme odmice (u slucaju МН algoritma faktor ucenja tezi nuli). U slucaju SLA i FLIN algoritma faktor ucenja r ne poseduje tu osoЬinu. Sada cemo izvrsiti poredenje gore pomenutih algoritama na primeru male neuralne mreze. Broj ulaza је К= 5, а broj izlaznih neurona је N = 3. Ulazni vektor sa srednjom vrednoscu nula i nekorelisanim komponentama је definisan sledeCim jednaCinama: x(l, i) = .45 * sin(i/2); х(2, i) = .45 * ((rem(i,23) -11 )/9)/'5; x(3,i) = .145 * ((rem(i,27) -13)/9); х( 4, i) = .145 * ((rand(l, 1) < .5) * 2 -1 ). * log(rand(l, 1) + .5); х(5, i) =- .5 + rand(l, 1 ). U sv1m рпmепmа koji slede inicijalna vrednost matrice W је Wini1=-.5+rand(5,3). Ortonormalnost matrice W је koriscena kao mera brzine konvergencije algoritma. Ortonormalnost matrice W је definisana sa 11 1-WтW 11 F, gde F predstavlja Frobeniusovu normu. Rezultati koji се Ьiti prikazani predstavljaju karakteristicno ponasanje algoritama. 114 115 o/I Poвfa'l![je- МН(О) metod Slika 6.7 pokazuje kako se menja ortononnalnost matrice W sa brojem iteracija, za SLA, FLIN i МНО algoritme. Izabrani faktor ucenja је Yi = 0.8/(2+i/400). U posmatranom slucaju komponente ulaznog vektora su medusobno nekorelisane. Sa slike se moze zakljнciti da је SLA algoritam najbrzi, dok МНО i FLIN algoritam konvergiraju priЬlizno istom brzinom. Na slici 6.8 нlazni vektor је xm =mix*x, gde је mix matrica za mesanje definisana sa mix -.5 +rand(5,5). Jasno, u ovom slucaju komponente ulaznog vektora su medusobno korelisane. lzabrani faktor ucenja је Yi = 0.8/(2+i/400). Sa slike jasno da је SLA algoritam najbrzi, dok је FLIN algoritam najsporiji. Slike 6.9 i 6.1 О sadrze rezultata simнlacije za slнcaj kada је xm =mix*x, mix .5+rand(5,5). Faktor ucenja је konstantna Yi = 2.3, н prvih 18000 iteracija, а nakon toga se postavlja na Yi = 0.8/(2+(i-18000)/400). Sa slika se jasno moze uociti da SLA i FLIN algoritam nece konvergirati ka stabilnom resenju sve dok је faktor ucenja konstantan. Sa druge strane, мно algoritam се konvergirati ka staЬilnom resenju cak i slucaju kada је faktor ucenja konstantan. 3.5 INШП@ 2 .5 Num Ьег of iterations Slika 6. 7 "Ortononnalnost" u zavisnosti od broja iteracija (tackasta linija - МНО algoritam; isprekidana linija - FLIN algoritam; debela puna linija - SLA algoritam). Komponente ulaznog vektora su medusobno nekorelisane. Faktor ucenja је Yi = 0.8/(2+i/400). 115 о/Ј PogГavlie -М Н (О) metod 2 . 5 о 0 .2 0 .4 0 .6 0 .8 1 . 2 Num b e r of iterations ------ -- -- -- ·- --- ---- -.-- ----- -- -------- -- --- 1. 4 1 . 6 1 . 8 116 Slika 6.8 "Ortonormalnost" u zavisnosti od broja iteracija (tackasta linija- МНО algoritam; isprekidana linija - FLIN algoritam; debela puna linija - SLA algoritam). Komponente ulaznog vektora su medusobno korelisane. Faktor ucenja је Yi = 0.8/(2+i/400) . 116 117 ~ ro Е о с: о .<:: о/Ј PogГдv[ze - МН(О) metod м но 1.5,--------,---------.--------.-------~,--------,--------~ \ '• ......... _ ....... -"'- - ...... ·---.. ~'-•,·v~,___.._"'~.,.., .... _..._ _ ,~•..-"~ .. -.<,.,.••~ .... , .._, ., _ _ ,_.. -~ •., · · ·-··· · ·· ,,•• • •• • • •• • • · ···- · ·· ··••• •• • •· •••• • Q L-------~--------~--------~------~L-------~--------~ о 0.5 1.5 Number of iterations SLA 2 2.5 1 . 5 ,--------,---------,--------.--------,~-------,--------~ 6 0.5 0.5 1.5 Number of iterations 2 2.5 Slika 6.9 "Ortonormalnost" u zavisnosti od broja iteracija Komponente ulaznog vektora su medusobno korelisane. Faktor ucenja је Yi = 2.3, za i <18000, i Yi = 0.8/(2+(i-18000)/400) za i ::::: 18000. Gornja polovina slike predstavlja ponasanje МНО algoritma. Donja polovina slike prikazuje ponasanje SLA algoritma. 117 о/Ј Pog(avГ,e - МН(О) metod м но 1.5,-----,----.--- ---,-----,------,--------, ~ 1 ~-Е 1 g \ _g 1 9 0.5 .. ·, 1 ·, <., о L__''•_ ..',J_'·•_·•#_c:','-:;:_-':_c.;...· ,=·~~н'=.,..'· ......,.;=>=:·'-.Ј=~=·'\ ";с..,•,...=•' -~=""'"-'' ·~=--<>='-'=•' ·='=··V·= . .,.·'w=• .. "л=~~=-=··=··=~ -=-""-""'=· =-· =·-=· --=·•·=··=--·~--.=-··=· "-'."-'-"" =· -=--=-_ -=--=-- ·="'-'-'-'" о ~5 1.5 2 2.5 з Number of iterations FLIN 8.------,----,-----,-----,------.------, 0.5 1.5 Number of iterations 2 2.5 118 Slika 6.10 "Ortonormalnost" и zavisnosti od broja iteracija Komponente иlaznog vektora sи medиsobno korelisane. Faktor исеnја је Yi = 2.3, za i <18000, i Yi = 0.8/(2+(i-18000)/400) za i ~ 18000. Gornja polovina slike predstavUa ponasanje МНО algoritma. Donja polovina slike prikazиje ponasanje FLIN algoritma. Na osnovи prethodne analize i simиlacionih rezиltata mozemo zakljиciti sledece: SLA algoritam је najbrzi, njegova realizacija zahteva najmanji broj operacija, ali sa drиge strane, zahteva veliki broj kola za globalna izracиnavanja i nece konvergirati ka stabilnom resenjи и slисаји kada је faktor исеnја konstantan. FLIN algoritam ne zahteva globalna izracиnavanja, ali је sporiji od the SLA i МНО algoritama, i ne konvergira ka stabilnom resenjи kadaje faktor исеnја konstantan. МНО algoritam zahteva samo 2 kola za globalna izracиnavanja, sporiji је od SLA algoritma i stabilan је cak i и slисаји kada је faktor исеnја konstantan. 118 o/II CIJogfav[je o/remensNj orijentisan fiijerarfiijsNj metoa (Ч'О:Ј{:М.) za izracunavanje Cl'C)l i :М.С)l U ovoj sekciji се biti predstavljen opsti metod koji transformise PSA/МSA algoritme u РСА/МСА algoritme. Glavna ideja, na kojoj se metod bazira, је data u sledecoj recenici: Svaki neuron radi опо sto је najbolje za njegovu "porodicu" а potom опо sto је najbolje za njega samog. Ovu ideju cemo nazvati "porodicni princip". Algoritam se sastoji od dva dela: jedan deo је odgovoran za ostvarivanje porodicnog cilja (jamily-desiraЫe feature learning), а drugi је odgovoran za ostvarivanje zelja pojedinacnih neurona (individual-neuron-desiraЫe feature learning). Drugi deo zakona ucenja se uzima sa tezinskim koeficijentom koji је ро apsolutnoj vrednosti manji od 1. То drugim reCima znaCi da se u algoritam uvodi vremenski orijentisana hijererhija kod realizacije "porodicnog" i "individualnog" dela zakona ucenja. Na slici 7.1 је prikazana gustina verovatnoce multivarijabilnog Gausovog signala. Poznato је da su u tom slucaju glavne ose hiperelipsoida paralelne sopstvenim vektorima kovarijansne matrice ulaznog signala kadaje srednja vrednost ulaznog signala nula. U slucaju kada se primenjuje PSA/МSA algoritam, sinapticki vektori, koji su na slici prikazani isprekidanim linijama, se ne poklapaju sa osama hiperelipsoida. Oni su za izvestan ugao rotirani u odnosu na njih. Vektori su medusobno ortonormalni pod uticajem "sile" PSA algoritma- ta "sila" је na slici oznacena sa F PSA· Sada se postavUa pitanje koju dodatnu "silu" treba primeniti da Ьi se sinapticki vektori dodatno rotirali do osa hiperelipsoida. Ovde се Ьiti predlozeno da se u PSA/МSA algoritam doda jos jedan clan. Тај novi clan Ьi imao zadatak da doda "diferencijalni momenat" koji је na slici oznacen "silama" F IILA i F21Lд· o/II PogfДvfie- ТОНМ metod 120 Glavna osa 2 Slika 7.1 Gustina verovatnoce multiltivarijaЬilnog Gausovog signala Za realizaciju "porodicnog principa" predlazemo sledeCi opsti metod, koji transformise PSA/МSA algoritam, oznacen sa FLApsNМsл u РСА!МСА algoritam, oznacen sa LАРсNМсл: LApcAfМCA ~ FLA PSAIМSA +а ILA max ЕЈ & ту )w ~w k ~ 1, l (7.1) l k -1,2 ... NJ gde је а konstanta takva da vazi la\<1. ILA oznacava individualni deo zakona ucenja. ILA predstavlja algoritam za maksimizaciju Е(уту) pod ogranicenjem w/wk=1 for k=1,2 , ... ,N. Drugim recima, novi РСА/МСА algoritam ucenja ima sledecu formu f..WpcAJМSA = f..WFLA +af..WILA, (7.2) gde f.. W FLA oznacava doprinos porodicnog dela zakona ucenja, dok f.. W1Lл oznacava doprinos individualnog dela zakona ucenja. Lako је uociti da ako se koristi homogeni PSA/МSA algoritam rezultujuci РСА/МСА algoritam се takode Ьiti homogen. Posto је laJ < 1, porodicni deo zakona ucenja se primenjuje brze nego individualni deo zakona ucenja. JednaCina (7.2) је uprosceno prikazana na slici 7.2. Iako је usvojeno laJ < 1, sada cemo se pozabaviti uproscenom analizom u slucaju kada је lal mnogo manje od 1. U tom slucaju, individualni deo jednaCine (7.2) skoro da nema nikakvog uticaja na porodicni deo. Tada porodicni deo obezbeduje dostizanje glavnog/sporednog potprostora. То znaci da је WтW=I i da W pokriva glavni/sporedni 120 121 о/П Pogfavfie-ТОНМ metod. potprostor. Drugim reCima, usled uvodenja dve vremenske skale mozemo pristupiti proЬlemu РСА!МСА kao optimizacionom proЫemu. U sustini, onaj deo zakona ucenja koji se odvija ILA (spor) FLA (PSA/ MSA) (brz) у Slika 7.2 Blok sema realizacije predlozenog metoda na brzoj vremenskoj skali, i koji obavlja PSA/МSA, predstavlja ogranicenje za spOПJl (individualni) deo zakona ucenja. Znaci, ako usvojimo da је PSA/МSA deo zakona ucenja dovoljno brz, mozemo reCi da on predstavlja striktno ortonormalno ogranicenje na PSAIМSA potprostoru. U tom slucaju, za individualni deo ujednaCini (7.2) mozemo pisati W(i + 1) = W(i) + y(i)(x(i)y(i) т- W(i)diag~1 (i) 2 , .. ·, yN(i) 2 )~, gde је а takvo da је јај < 1, (7.3) W т W = 1 i pokriva glavni/sporedni podprostor. Odgovarajuca diferencijalna jednaCina је [Ljung, 1977; Ој а, 1985] d w = (cw- w diag(w т cw )~, dt (7.4) gde diag(WтCW) predstavlja dijagonalnu matricu koja se dobija kada se svi elementi van glavne dijagonale matrice wтcw, anuliraju. Ako napisemo jednacinu za pojedinacne kolone (7.5) gde је Ak k-ti dijagonalni element matrice diag(WтCW). Mozemo lako zakljuciti da sн stacioname tacke ove jednaCine sopstveni vektori matrice С. Posto \Vk pokrivaju 121 о/П PogГav{fe- ТОНМ metod 122 dominantni/sporedni potprostor matrice С, onda su jedino moguca resenja dominantne/sporedne komponente . Ako wk(i) pridruzene diferencne jednaCine роsеснје beskonacno cesto skoro sigumo, kompaktan podskнp domena privlacenja resenja jednacine (7.5), tada resenje jednaCine (7.5) predstavlja resenje diskretne jednaCine (7.3 ). Naravno, veomaje tesko (ako ne i nemoguce) dokazati ovo u opstem slucajн. Usled simetЩe predlozenog algoritma, sistem ima vise od jednog resenja. То moze proнzrokovati "konflikt interesa" izmedu pojedinih neurona. Ako razmotrimo slнcaj na slici 7.1 moze se uoCiti da dok se jedan sinapticki vektor krece u pravcu pozitivnog dela dominantne ose 1, u isto vreme drugi sinapticki vektor moze da ima "nameru" da se krece ka negativnom delu dominantne ose 1. То znaCi da algoritam moze da postane osetljiv na izbor koeficijenta а. Osim toga, znacajno је proнCiti i slнcaj н kome realizacya algoritma u paralelnom hardveru dovodi do toga da koeficijent а nye perfektno jednak za sve vektore, ра se н tom slucaju postavlja pitanje stabilnosti algoritma. Sada cemo analizirati slнcaj kada је u algoritam uneta nekakva vrsta asimetrije. Drugim recima, dacemo pojedinim vektorima drugaCije sanse za dostizanje dominantnog/najsporednyeg sopstvenog vektora. U tom slucajн, predlozeni metod se moze opisati sledecom jednacinom: LA РСА!МСА = FLA PSAIМSA + JLA max ЕЈ ((ny јТ у (~w k = 1,! l Jlk - 1,2 ... N (7.6) gde је D dyagonalna matrica sa nenнltim dijagonalnim elementima dn takvim da је JdпJ< l . Unosenje asimetrije dovodi do dodatne vremenske hijerarhije н realizaciji individнalnih delova zakona нсеnја. Ako sн svi dnjednaki а, ovajednaCina se svodi na homogeni slнcaj . Ponovo cemo sprovesti uproscenн analizu za slнcaj kada је Jdпl mnogo manje od 1. U tom slнсајн, individualni deo u jednaCini (7.6) prakticno nema uticaj na porodicni deo. Tada porodicni deo obezbedнje pronalazenje glavnog/sporednog potprostora. То znaci da је WтW=I i da W pokriva glavni/sporedni potprostor. Као sto је vec ranye objasnjeno mozemo pristнpiti proЬlemu РСА/МСА kao optimizacionom proЬlemн. U stvari brzi deo zakona ucenja, koji obezbeduje izracнnavanja PSA/МSA predstavlja ogranicenje za spoПJl (individнalni) deo zakona ucenja. То znaCi da ako pretpostavimo da је PSA/МSA deo zakona нсеnја dovoljno brz mozemo reci da u tom slucajн taj deo zakona ucenja predstavlja 122 123 о/П Pogfav{ie-ТОНМ metod. ortonormalno ogranicenje na PSAIМSA potprostoru. U tom slucaju, individualni deo u jednaCini (7.6) mozemo pisati kao W(i + 1) = W(i) + y(i)(x(i)y(i) Т - W(i) diag~1 (i)2 ,. ··,у N (i) 2 )~, gde је D dijagonalna matrica sa dijagonalnim elementima d k takvim da је jd k ј < 1 i W т W= 1 i pokriva glavni(sporedni) podprostor. Odgovarajuca diferencijalnajednaCinaje [Ljung, 1977], [Оја, 1985] dW = (cw- Wdiag(wтcw)~, dt (7.7) (7 .8) gde је diag(WтCW) definisana kao i ranije. Ako napisemo jednaCinu za svaku kolonu 'vk, imamo (7.9) gde је Ak k-ti dijagonalni element matrice diag(WтCW). Nije tesko zakljuCiti da su stacioname tacke ove jednacine sopstveni vektori matrice С . Ako wk(i) pridruzenog diskretnog algoritma posecuje beskonacno cesto skoro sigumo kompaktni podskup domena privlacenja jednacine (7.9), tada resenje jednaCine (7.9) predstavlja i resenje algoritma (7.6). Ponovo cemo naglasiti, da је veoma tesko pokazati tu osobinu diskretnog algoritma u opstem slucaju. 123 о/П PogГд:vfie- ТОНМ metod 124 7.1 Matematicka analiza predlozenog principa u ovom paragrafu се biti pokazano kako predlozeni тонм metod moze biti predstavljen i kao ucenje na priЫizno Stifel/Grasmanovoj (Stiefel/Grassman) podmnogostrukosti. Bice predstavljen algoritam koji izvodi ucenje na Grasmanovoj dominantnoj/sporednoj podmnogostrukosti i kasnije се biti pokazano kako se on moze povezati sa ТОНМ metodom. Potpuno analogno moze se izvesti analiza za slucaj ucenja na Stifelovoj dominantnoj/sporednoj podmnogostrukosti. Sada cemo neformalno ponoviti definiciju Grasmanove mnogostrukosti koja је data u [Edelman, 1998], [Fiori, 2002]: Prostor matrica w Е о КтN с R КхN (N~ takvih da је wтw=I i homogena funkcija Ј: о KxN -----f R takva da је J(W)=J(WQ) za Ьilo koju NxN ortogonalnu matricu Q se nazivaju Grasmanovom mnogostrukoscu. Algoritmi ucenja koji se primenjuju u neuralnim mrezama se cesto mogu shvatiti kao algoritmi koji maksimiziraju/minimiziraju funkciju cene pod nekakvim ogranicenjem, рп сети је to ogranicenje najcesce ortonormalnost sinapticke matrice. Takvi zakoni ucenja mogu predstavljati resenje sledeceg proЫema: Nadi Weks takvu da vazi: J(Weks) = max/min J(W), w Е R KxN. Standardan naCin za doЬijanje zeljenog resenjaje definisanje Lagranzove funkc~e Jz(W) = J(W) + ltr(w т w- 1), gde је l takozvani Lagramov multiplikator, i trazenje ekstremuma funkcije J1(W), na primer upotrebom tehnike uzlaznih/silaznih gradijenata, dW -=ryVJz. dt Kako Ьi se osigurala ortonormalnost sinaptickih kolona, moze se primeniti iterativna ortogonalizacija kolona matrice W, na primer upotrebom Gram-Smit (Gram-Schmidt) metoda 124 125 'VII PogГavfie- ТОНМ metod. ortogonalizacije matrice Ciji se elementi menjaju na osnovu gradijentne optimizacije funk.cije J(W) ili pomocu projekcije na ortonormalnu grupu [Fiori, 2001] . Medutim, iterativna primena ortonormalnosti moze Ьiti proЬlematicna u praksi (see e.g. [Fiori, 2001]). То је razlog zasto su istrazivaCi poceli da proucavaju zakone ucenja koji odгZavaju ortogonalnost sinapticke matrice u svakom momentu. Takvi algoritmi su poznati kao SOC (Orthonormal Strongly- Constrained - striktno ortnormalno ograniceni) algortimi. Nekoliko algoritama iz te klase је analizirano u [Fiori, 2001]. Prvo analizirajmo sledeci algoritam: (7.10) (7 .11) gde х predstavlja ulazni vektor za jednoslojnu mrezu sa jednim izlaznim neuronom (у) i w predstavlja sinapticki vektor. Jednostavnoje uociti dajednaCinu (7.10) mozemo napisati i kao (7.12) Ako sada direktno generisemo uzlazni gradijentni algoritam u odnosu na /, pri cemu se gradijent racuna ро w, imamo: w(i + 1) = w(i) + y(i) xy~w(i) т w(i)- y2w(i) . w(i) Т w(i) (7.13) Jednostavno se uocava da zamenom w(i)тw(i)= 1 doЬijamo, direktno, poznati Ojin zakon ucenja [Ој а, 1982]. Ako generalizujemo ovaj algoritam na slucaj sa vise izlaznih neurona, 1mamo E(tr(yy т))= max 125 о/П PogГavГze- ТОНМ metod 126 gde Yk predstvalja k-ti izlazni neuron i W k predstvalja k-tu kolonu sinapticke matrice W . Zakon ucenja za modifikaciju sinaptickih vektoraje u tom slucaju ( . 1) (") ( .)XYk~wk(i)тwk(i)- Yk 2wk(i) wkz+ =wkz+yz Т · 'v k (i) w k (i) (7.14) Sada cemo definisati Grasmanovu dominantnu podmnogostrukost. Prostor matrica w Е о 16:N с R 16:N (Ng() takvih da је wтw=I i w pokriva dominantni potprostor matrice С, i funkcija Ј: О 16:N -----f R takva da је J(W)=J(WQ) za Ьilo koju NxN ortonormalnu matricu Q cemo nazvati Grasmanovom dominantnom podmnogostrukoscu. Ako sada primenimo algoritam (7.14) pod striktnim ogranicenjem za W- W је takvo da је WтW=I i W pokriva dominantni potprostor matrice С, u stvari imamo sledeCi algoritam w k (i + 1) = 'v k (i) + y(i)(xy k -у k 2w k (i) ), т Yk = w kx. FunkcUa cene u kompaktnoj notaciji је data sa E(tr(yy т)) = E(tr(W т хх т W)= tr(W т CW) = max Nije tesko uoCiti da se radi о funkciji za koju је ispunjeno J(WQ)=J(W). Drugim reCima mozemo reci algoritam (7.14) vrsi ucenje na Grasmanovoj dominantnoj podmnogostrukosti. Algoritmu (7 .14) se moze pridruziti sledeca diferencij alna ј ednaCina ( u kompaktnoj notacij i) d w = (cw- w diag(w т cw )), dt (7.15) gde је diag(WтCW) dijagonalna matrica definisana kao i ranije . Ako napisemo (7.15) za svaku kolonu Wk, imamo dw k ( ) --= Cwk -Лkwk , dt (7.16) gde је Ak k-ti element glavne dijagonale matrice diag(WтCW) . Lako је zakljuCiti da su stacioname tacke ovih jednaCina sopstveni vektori matrice С . Posto se ucenje obavlja na 126 127 о/П PoвCav[ze- ТОНМ metod. dominantnoj Grasmanovoj podmnogostrukosti rezultujuCi vektor wk се Ьiti jednak nekom od dominantnih sopstvenih vektora matrice С. Ako wk(i) pridruzenog diskretnog algoritma posecuje beskonacno cesto kompaktan podskup domena privlacenja resenjajednacine (7.16), tada su resenja jednacine (7 .16) takode resenja pridruzenog diskretnog algoritma (7 .11 ). Naravno, kao sto је vec receno, ovu osobinu algoritma (7.11) је tesko dokazati. Na slican naCin se moze definisati Grasmanova sporedna podmnogostrukost. Prostor matrica W Е О КхN с R KxN (N~К) takvih da је Wт\-V=I i W pokriva sporedni potprostor matrice С, i funkcija Ј: О КхN -ј- R takva da је J(W)=J(WQ) za bilo koju NxN ortonormalnu matricu Q се biti nazvani Grasmanovom sporednom podmnogostrukoscu. Ako se algorithm (7.14) primeni pod striktnim ogranicenjem za W, W је takvo da је WтW=I i W pokriva sporedni potprostor matrice С, i primenimo analizu kao u slucaju dominantne Grasmanove podmnogostrukosti kolone sinapticke matrice W се biti jednake sporednim sopstvenim vektorima matrice С. Potpuno analogno, mogu se definisati Stifelova dominantna i sporedna podmnogostrukost, za slucaj kada algoritam nije potpuno simetrican (vidi [Jankovic, 2005а, 2005Ь ]). 127 o/II Pogtav[ze-ТОНМ metod . 128 7.2 Jedan primer primene ТОНМ metoda za РСА U ovom pragrafu се Ьiti pokazano kako se ТОНМ metod moze primeniti za transformaciju SLA metoda [Оја, 1989] u РСА metod. U poglavlju 4 је vec objasnjeno da је SLA metod PSA metod. Primenom ТОНМ metoda na SLA Gednacina (4.19)) doЬijamo sledeCi РСА algoritam: w k (i + 1) ~w k (i)+ r (i{Yk (i)x(i) ~у k (i) };!Ут (i)w т (i) Ј + y(i)dk ~k (i)x(i) - w k (i)yi (i) ], m,k = 1, ···,N, gde su dk parametri razliCiti od nule takvi da vazi 1 dk 1 <1. U kompaktnoj notaciji imamo W(i + 1) = W(i) + y(i)(x(i)y(i) т - W(i)y(i)y(i) т) + y(i)(x(i)y(i) Т-W(i)diag(y(i)y(i) т)~, (7.17) (7.18) gde је W(i) = (wi(i) ... wN(i)), y(i) = (y1(i) .. . yN(i))т, D dijagonalan matrica sa dijagonalnim elementima dk (k=1 ,2, ... ,N), i diag(F) oznacava dyagonalnu matricu doЬijenu od matrice F u kojoj su svi elementi van dijagonale matrice F postavljeni na О. Primenom stohasticke aproksimacije ovoj diferencnoj jednaCini se moze pridruziti odgovarajuca diferencijalna jednacina: d w= cw- wwтcw +(cw- Wdiag(wтcw )~. dt (7.19) 128 129 o/II PogГavfie- ТОНМ metod. Као sto је vec ranije receno, pod uslovima koji su dati u [Ljung, 1977] [Оја, 1985] resenja stohasticke diferencne jednacine (7.18) teze asimptotski ka staЬilnim resenjima jednacine (7.19). Kljucna pretpostavka za konvergenciju је da resenje W(i) originalnog diskretnog algoritma (7.18) posecuje beskonacno cesto sa verovatnocom 1 kompaktan podskup domena privlacenja asimptotski staЬilnog resenjajednaCine (7.19). Nazalost, dokazivanje ove osoЬine је veoma tesko. Ovde mozemo reCi da је u svim simulacUama koje su izvedene staЬilno resenje jednaCine (7.19) predstav~alo i resenje jednaCine (7.18), pod uslovom da је matrica D Ьila izabrana na odgovarajuCi nacin. Sada cemo pronaci asimptotski staЬilno resenje jednacine (7.19), ako isto postoji. Prvo uvedimo sledecu oznaku U = (с 1 , ••• , ен). (7.20) Tadaje CU = UA, uтcu = А, (7.21) gdeje A=diag(A.J, ... ,A.н) i А.1 > А.2 > ··· > А.н > A.N+I 2':: A.N+2 2':: •·· 2':: А.к >О. Nije tesko uoCiti da W=U ili W koje је jednako nekoj permutaciji od U predstavlja resenje jednacine (7.19). Zaista, ako zamenimo W=U ujednaCinu (7.19), tadaje dW = cu - uuтcu +(cu - Udiag(uтcu)~ dt W= U (7.22) = UA- UA+(UA- UA)D = О. Takode, ako zamenimo W=UP u jednaCinu (7.19), gde Р oznacava permutacionu matricu, imacemo isti rezultat. 129 rrJjJ PogГavfie- ТОНМ metod 130 Sada се biti pokazano da ne postoje druga resenja. Prvo се biti pokazano da resenje ј ednacine (7 .19) pokriva N-dimenzioni glavni potprostor matrice С. Ј ednacina (7 .18) se moze napisati i na sledeci naCin: W(i + 1) = W(i) + rCi)(x(i)y(i) т Х1 + D) - y(i) W(i)(y(i)y(i) т + diag~[ (i),- ··,у~ (i) ~) , (7.23) ili W(i + 1) = W(i) + y(i) · (x(i)x(i) т W(i) JI + D)- y(i)· W(i)0i, (7.24) gde је 1 jedinicna matrica i e i matrica dimenzije NxN definisana sa 0 i = y(i)y(i) Т + diag~f (i), ·· · ,у~ (i) ~. U homogenom slucaju (kada su svi dijagonalni clanovi matrice D jednaki) mozemo pisati D =al, pri cemu је а>-1. Tada imamo W(i + 1) = W(i) + y(i)(1 + a)(x(i)x(i) т W(i) )- y(i)(1 + a)W(i)0 i /(1 +а). (7.25) Nije tesko uociti da ova jednaCina (sa izuzetkom clana 1 +а) predstavlja jednaCinu koja је analizirana od strane PlamЬlija [PlumЬley, 1991]. U [PlumЬley, 1991] је analizirana sledeca klasa zakona ucenja: W(i + 1) = W(i) + y(i)(x(i)x т (i)W(i) + W(i)0(i)) (7.26) 130 131 о/П PogГavlie- ТОНМ metod. gde је 0(i) nekakva N х N matrica koja moze Ьiti funkcija od W(i) i/ili x(i). Pod uslovima koji su definisani u [Ljung, 1977] i [Оја, 1985], resenje stohasticke diferencne jednaCine (7.26) tezi asimptotski staЬilnom resenju sledece jednacine: dW -=CW+W0. dt U [PlнmЬley, 1991] је dokazana sledeca teorema: (7.27) Teorema 7.1. Ako tezinska matrica W ima maksimalni rang za svako t, ordinarna diferencijalna jednaCina (7.27) је asimptotski stabilna na skupu gde kolone matrice W pokrivaju potprostor definisan sa N dominantnih sopstvenih vektora matrice С. OЬlast privlacenja ovog skupa је skup W takav da је za sve dominantne sopstvene vektore Сј (1 ::::;; i::::;; N) matrice С, ispunjeno Wтсј 7: О. Ukratko, u [PlumЬley, 1991] је pokazano da klasa algoritama (7.26) konvergira ka matrici W koja pokriva N-dimenzionalni dominantni potprostor matrice С, pri cemu se smatra da је matrica W(i) maksimalnog ranga. Konvergencija ne zavisi od 0(i), iako је jasno da 0(i) mora da bude izabrano tako da matrica W(i) ostaje nesingularna u toku primene algoritma [PlumЬley, 1991]. Kako је 1 +а> О Ger је usvojeno а>-1 ), clan 1 +а ne нtice na analizu koja је izvedena u [PlumЬley, 1991]. То znaCi da resenje jednaCine (7.25) prekriva N-dimenzioni glavni potprostor matrice С. Koriscenjem slicnog postupka moguce је pokazati, da i kada su dijagonalni clanovi matrice D nejednaki, resenje jednacine (7.18) pokriva glavni potprostor matrice С. То se moze pokazati analizom sledeg algoritma: W(i + 1) = W(i) + y(i)(x(i)x т (i)W(i)D1 + W(i)0(i)) (7.28) 131 о/П Pog[a:u[ze-ТОНМ metod 132 gde је 8(i) neka N х N matrica koja moze Ьiti funkcija od W(i) i/ili x(i), i D1 је dijagonalna matrica Ciji su svi dijagonalni elementi pozitivni. Opet, pod uslovima koji su ranije definisani, resenje stohasticke diferencnejednaCine (7.28) tezi asimptotski staЬilnom resenjujednaCine: dW -=CWD1 +W0. dt (7.29) Sada cemo predstaviti sledecu teoremu koja predstavlja generalizaciju Teoreme 7.1 . Teorema 7.2. Ako tezinska matrica W ima maksimalni rang za svako t, ordinarna diferencijalna jednaCina (7.29) је asimptotski staЬilna na skupu gde kolone W pokrivaju N- dimenzioni dominantni potprostor С. Domen privlacenja ovog skupa је skup W takav da za sve dominantne sopstvene vektore ci (1 ~ i ~ N) matrice С vazi Wтci i:- О . Dokaz se moze izvesti analogno dokazu Teoreme 7.1, а koji је prikazan u [PlumЫey, 1991] . Kako moguce resenje pokriva dominantni potprostor matrice С, jedino resenje koje nije matrica Cije su kolone sopstveni vektori matrice С, је matrica koja predstvalja rotaciju matrice cUe su kolone dominantni sopstveni vektori matrice С. OznaCimo sa R rotacionu matricu. OznaCimo sa Ws matricu koja se od matrice U dobUa rotacijom W5 = UR, R -l = R т . Ako zamenimo Ws ujednacinu (7.19) imamo dW _ = CW5 - W5 W5 т CW5 + (cws - W5 diag(ws т CW5 ))о dt W- W5 = CUR- URR т U т CUR + (cuR- UR diag(R т U т CUR ))о = UAA- UAA + (uлл- UR diag(R т AR ))о = u(лR- R diag(R т AR ))о . (7.30) (7.31) 132 133 o/IJ PogГavlie- ТОНМ metod. NUe tesko uociti da se stabilne tacke dobijaju kada је ЛR -Rdiag(R т ЛR) = О . Ovo је moguce samo kada је R jedinicna ili permutaciona matrica, posto је Л dUagonalna matrica, i kolone R moraju biti jednake nekim od sopstvenih vektora matrice Л. То dalje znaci da su jedina moguca resenja permutacije matrice U. 133 о/П PogCav(je-ТОНМ metod 134 7.3 Analiza asimptotske stabllnosti resenja Sada posto smo pronasli resenja jednacine (7019) pokazacemo da ta resenja predstavljaju asimptotski stabilna resenjao Da Ьismo to uradili, razmotrimo malo odstupanje д=(81 о о o8N) od staЬilne tacke U о U ј ednaCini (7 019) zamenaimo W=U+Ll o Tada imamo dil dW -=-- dt dt w= u +Ll = C(U +Ll)-(U +Ll)(U +Ll)T C(U +Li) + (ccu +Li)-(U +Li)diag(cu +Li)т ccu +Li))~ (7032) = Cil- Uil т cu -Liuтcu- uuт Cil + (cil- u diag(u т C(Li + Li) )- Lidiag(U т CU) ~+ o(IIL1II2 ) о Ako usvojimo da је llдll malo, linearni deo (ро д) jednaCine (7032) odreduje asimptotsku satЬilnosto Za n-tu kolonu 8n matrice д, linearni deo jedancine (7032) daje (7033) 134 135 '1/11 Pogfav[ze-ТОНМ metod. Sada се Ьiti analizirano sta se desava sa projekcijom 8n na razliCite sopstvene vektore сг, r=l , .. . , К. Prvo, usvojimo r > N. Tadaje, usled ortonormalnosti sopstvenih vektora { cr}, (7.34) Tako, ako је dn > -1, tada c/8n tezi asimptotski nuli kako t ~ оо, posto је ро pretpostavci Ar < Ako usvojimo r-:;N, tada је _d_(с...:....'[_о...:.:п_) = Ar (сТ Б п)- Ar (сТ Б п)- An (о; Сп)- An (сТ б n) dt + dn (Ar (с'[ Б п)- An (с'[ Б п)- б(r,n)Ап (c;on )), (7 .35) gde је (\r, n) Kronekerov delta simbol. Lako је uoCiti da su funkcije Crт8n dekuplovane u smislu da c/8n i Cnт8r zavise jedna od druge ali ne i od ostalih funkcija. Slucaj r=n је najjednostavniji i rezultuje sledecom jednaCinom _d...:....( с_:..:~=-:....:..:п"-) = А п (с; б n)- А п (с; О n)- An (с; О n)- An (с; О n) + d n (An (С; О n)- An (С; О n)- 2An (с; О n)) т = -2(l+dn)An(cп<>n) · То implicira da c/8n tezi asimptotski nuli kako t ~оо ako је dn > -1. (7.36) Konacno, usvojimo f-l:.n, i r ~ N. Sada cemo morati da analiziramo sistem dve jednacine koji opisuje ponasanje c/8n i c/8r 135 о/П Pogfa:vfie-ТОНМ metod Uvedimo sledece oznake Tada se jednacina (7.37) moze pisati kao dX =АХ. dt 136 (7.37) (7.38) (7.39) Poznato је da resenje jednacine (7.39) tezi asimptotski ka nuli ako i samo ako оЬа korena karakteristicnog polinoma imaju striktno negativne realne delove. Karakteristicni polinom se moze dobiti iz sledece jednaCine det(sl- А)= О . (7.40) U nasem slucaju, (7.41) Posle nekoliko algebarskih manipulacija dobijamo 136 137 о/11 PogCav(ie-ТОНМ metod. s 2 + s(A.r +An -(dп -drXAr -А-п )) - (А.п(l + dп ) - Ar(l + dr)XA-r - Ап)- (1 + dnX1 + dr XA-r- An ? =О . (7.42) Prvo cemo razmotriti slucaj kada su svi di j ednaki а. U tom slucaju ј е jednacina od interesa (7.43) U tom slucaju su koreni jednaCine dati sa (7.44) Nije tesko uoCiti da mora biti а<О. Uistinu, ako је а> О, jedan koren се imati pozitivan realni deo. ZnaCi, mora biti О > а> -1. Sta se moze reci о izboru d? Iz jednacine (7.44) mozemo videti da ako је а Ыisko О ili -1 imamo jedan koren karakteristicnog polinoma Ciji је realni deo veoma Ыizak nuli. То znaci da и tom slucaju, algoritam sporo konvergira. Analizom (7.44) se moze pronaCi ono а koje obezbeduje maksimalnu brzinu konvergencye. U slucaju kada su svi di razliCiti jednaCina (7.42) rezultuje sa: s 2 +s(A.r +An -(dп -dr)(Ar - Ап)) -(dп -dr)(Ar -Ап)Ап - (l+dr)dп(Ar - An? =О. (7.45) Uvedimo sledecu oznaku 137 rr)IJ PogГav[ie-ТОНМ metod 138 Koreni ј ednaCine (7 .4 5) su dati sa Ako је В<О , оЬа korena се imati negativan realan deo u slucaju (7.46) Iz ove nejednakosti se vidi da vektor d moze Ьiti izabran na mnogo nacina tako da nejednakost (7.46) bude zadovoljena, ili drugim recima da algoritam ima staЬilno resenje. Interesantno је zapaziti, ako su svi di pozitivni i razliCiti, i posto za sopstvene vrednosti matrice с vazi da је jedino resenje ono u kojem vecem di odgovara vece Лi (samo u tom slucaju је (dп-dr)(Лr- Лп) <О za svako r i svako n). 138 139 о/11 PogГav{ie - ТОНМ metod. 7.4 Primer primene ТОНМ metoda za МСА Sada cemo primeniti ТОНМ metod na MSA metod predstavljen u [Douglas, 1998]: W(i + 1) = W(i)- y(i)(x(i)y(i) TW(i) TW(i)W(i) TW(i)- W(i)y(i)y(i) Т), (7.47) gde x(i) predstavlja ulazni vektor sa srednjom vrednoscu nula, y(i)=Wт(i)x(i) predstavlja izlazni vektor i W(i) predstavlja tezinsku (sinapticku) matricu. U referenci [Douglas, 1998] је pokazano da је algoritam stabilan, tako da nije neophodno vrsiti renornmalizaciju vektora wk(i), koji predstavlja k-tu klonu matrice W(i). Nije tesko uociti da је predlozeni algoritam homogen sa aspekta pojedinacnog neurona. Ako sada primenimo ТОНМ metod na algoritam (7.47), dobijamo sledeCi zakon ucenja W(i + 1) = W(i)- y(i)(x(i)y(i) т W(i) TW(i)W(i) т W(i)- W(i)y(i)y(i) т) - ay(i)(x(i)y(i) т -W(i)diag(y(i)y(i) т)), (7.48) gde diag(A) postavlja sve clanove matrice А, koji nisu na glavnoj dijagonali, na nulu i gde је -1 <а<О. Ovaj algoritam predstavlja МСА algoritam. KoristeCi stohasticku aproksimaciju [Ljung, 1977], [Оја, 1985] znamo da algoritam (7.48) moze biti povezan sa sledecom ordinarnom diferencijalnom jednaCinom dW = -(cwwтwwтw -wwтcw)-a(cw- Wdiag(wтcw)). dt Ovajednacina moze biti koriscena za proucavanje ponasanja algoritma (7.48). Dve teoreme koje slede opisuju ponasanje algoritma (7.49) . (7.49) Teorema 7.3: Moguce је izabrati а tako da kolone W pokrivaju sporedni podprstor matrice С pod uslovom da su svi elementi matrice W ograniceni. Dokaz teoreme 7.3: Neka su Е 1 Е RКxN i Е2 Е RКx(K-NJ matrice koje sadrze N sporednih i (K-N) glavnih sopstvenih vektora matrice С, respektivno. Mozemo izraziti W(t) u (7.49) kao 139 о/П PogГavfie-ТОНМ metod 140 (7.50) gde su AI=AI(t) Е R NxN i А2= A2(t) Е R (K-N)xN_ Analiza koja sledi се biti uproscena ako usvojimo da vazi sledeca nejednakost za sopstvene vrednosti matrice С : Drugim recima, bice usvojeno da matrica С ima К razlicitih striktno pozitivnih sopstvenih vrednosti sa odgovarajuCim ortonormalnim vektorima. Analiza koja sledi moze se obaviti i bez te pretpostavke ali se onda ista usloznjava. Obicno su, u realnim sutuacijama kao sto su situacije kada ulazni vektor х predstavlja uzorke signala govora ili vektore nivoa sivog u prozorima kod procesiranja slike, sopstvene vrednosti kovarijansne matrice ulaznog signala razliCite i striktno pozitivne. Napisimo (7.49) kao d W = - (cw( W Т WW Т W+ al )- W0 N) , dt gde је 1 jedinicna matrica odgovarjucih dimenzya (NxN) i Е> н= wтcw +adiag(wтcw). Mnozenjem оЬе strane jedanCine (7.51) sa Е1 т doЬijamo gdeje А 1 = diag{J.,1,. · ·,А. н} i В= B(t) =(л[ At +AiA2J. (7.51) (7.52) (7.53) 140 141 Mnozenjem оЬе stranejednaCine (7.51) saE/ gdeje dA 2 -- = -Л2А2 (В+ al) + А20 N dt o/JI Pog(a:vfie-ТОНМ metod. (7.54) Razmotrimo matricu S(t) = A2(t)A1-1(t). Ako је А1 (0) nesingulama, tada је В(О) pozitivno definitna, i tada је, na osnovu (7.53) A1(t) nesingulama, pod pretpostavkom da је а izabrano na odgovarajuCi naCin (sto је uvek moguce imajuCi u vidu rezultate u referenci [Douglas, 1998] - dokaz је moguce izvesti kontrapozicijom) i pod pretpostavkom da su komponente matrice W ogranicene. Sada mozemo pisati dS _ dA2 л- 1 А л- 1 dA1 л-1 - - -- 1 - 2 1 -- 1 dt dt dt Zamenom (7.53) i (7 .54) u (7.55) i uproscavanjem, posle par transformacija dobijamo (7.55) (7.56) gde је M=M(t)=A1(B+ai)A1-1 Е RNxN i ло lineami operator koji deluje na S(t). Kako је B(t) kvadratna pozitivno definitna simetricna matrica, В+ al i M(t) su takode pozitivno definitne matrice ukoliko је а izabrano na odgovarajuCi nacin (nije tesko uoCiti da а mora biti ро apsolutnoj vrednosti, manje od najmanje sopstvene vrednosti matrice В). Sada cemo pokazati da је Л о negativan operator. Mozemo smatrati da S(t) predstavlja vektor i onda mozemo traziti sopstvene vrednosti Л0 • Sopstvene vrednosti ло su AkFAk-At, k Е{1 , .. . , N}, lE {K-N+1, .. . ,К}, i odgovaraju sopstvenim vektorima (vektorizovanim matricama) Skl(t) Cije su sve komponente nula izuzev elementa (k,l) koji ima jedinicnu vrednost, jer је 141 о/П Pogf'av[je-ТОНМ metod 142 (7.57) Kako је ро pretpostavci Ak-AJ <О za svaki par{ k,l} , ло је negativan operator, i sve sopstvene vrednosti [А 0 ]M(t) imaju negativne realne delove. Tada је lim S(t) =О, (~ОО i span[W] ~ span[Et]. Teorema 7.4: Ako је rank[W] = N, tada prostor lokalno asimptotski stabilnih tacaka jednaCine (7.49) zadovoljava wтw = 1 i kolone matrice W се biti jednake sopstvenim vektorima matrice С. Dokaz teoreme 7.4: Stacioname tacke jednaCine (7.49) zadovoljavaju sledecujednaCinu CWWTWWTW-WWт CW + aCW = aW diag(wтcw ). (7.58) Ako је rank[W]=N, tada iz teoreme 7.3 znamo da su potencijalne stacioname tacke (na osnovu (7.50)) date и formi W=E1A1, gde А1 Е R NxN predstavlja proizvoljnu nesingulamu matricu i Е 1 је definisano kao i ranije. Zamenom ove forme и (7.58) i posle odredenog uproscavanja dobijamo (7.59) Mnozenjem sa desne strane (7.59) sa А1т i posle grupisanja, dobUamo (7.60) Ocigledno је da desna strana jednacine (7.60) predstavlja simetricnu matricu. То znaci da i leva stranajednacine (7.60) mora predstavljati simetricnu matricu i н tom slucaju mora biti: 142 143 о/П PogГavlie -ТО НМ metod. А 1 ((л 1 А Т Ј + аА 1 А Т ) = ((л 1 А Т Ј + аА 1 А Т )л 1 . (7.61) Iz (7.61 ) nije tesko zakljuciti da je matrica (7.62) dijagonalna matrica jer је komutativna sa dijagonalanom matricom А1 . Mnozenjem sa desne strane оЬе strane jednacine (7.62) sa A1At т dob~amo (7.63) Sada imamo da је matrica na levoj strani jednacine (7 .63) simetricna sto znaCi da i matrica na desnoj strani (7.63) mora predstavljati simetricnu matricu. То znaci da vazi sto dalje znaci da је matrica А1А1т dijagonalna matrica. Ako oznaCimo А1А1т DA zamenimo u (7.59) imamo (7.65) Nije tesko uociti da jednaCina (7.65) predstavlja jednacinu za odredivanje sopstvenih vrednosti i sopstvenih vektora matrice F=A1DA2-DAA1+aA1 pri cemu kolone matrice А1 predstavljaju sopstvene vektore te matrice koja је ( oCigledno) dijagonalana matrica. То znaCi da su kolone matrice А1 u oЬliku [О .. . ak ... О( Sada cemo pokazati da щ moze imati iskljuCivo vrednosti -1 ili 1. Ako napisemo (7.65) za k-tu kolonu matrice А1 dobijamo sledecujednacinu (7.66) ili, posle odredenih transformacija 143 o/II PogГav[je- ТОНМ metod 144 4 2 ak -(1+a)ak +а= О. (7.67) Nije tesko uociti da (7.67) predstavlja bikvadratnu jednacinu Cij a su resenja а/=1 i/ili а/=а. Kako је а <0, jedino resenje је а/ =1, sto znaCi da је щ=±1. То dalje znaCi da su kolone matrice W jednake sporednim sopstvenim vektorima matrice С i posledicno wтW=I . Sada с ето analizirati stabilnost u okolini stacionamih tacaka. Prvo oznacimo ( ci=ei) U = (с1 , .. . , ен). (7.68) Tadaje (7.69) gde је Л1 =A=diag(A-J, .. . , А-н), i At је vec ranije definisano. Sada cemo pokazati da је resenje jednaCine (7.49) W=U, asimptotski stabilno resenje . Da bismo to uradili , razmotrimo malo odstupanje L1=(8 1 , • •• , 8н) od stacioname tacke U. U jednacini (7.49) stavimo W=U+A. Tada imamo dA = dW =-(CA+2CUATU +2CUUTA-AЛ- UUT А- UA Tcu) dt dt W=U+A - а(сА- АЛ- 2U diag(A т CU ))+ OCIIAII2 ) . (7.70) Ako pretpostavimo da је IIAII malo, lineami clan (ро А) jednaCine (7. 70) odreduje asimptotsku stabilnost. Za n-tu kolonu Dn matrice А, lineami deo jednaCine (7.70) daje 144 145 o/IJ PogГa.v{ie- ТОНМ metod. d(on) = -(con + ±лтст (c:on )+ ± (2Лт- лЈст (о:сЈ- Лn<>n) dt m=l m=l (7.71) -a(con -Лnon -2cnлn(c~oJ) . Sada cemo analizirati sta se desava sa projekcijama vektora 8n na razliCite sopstvene vektore cr, r=l, .. . , К. Prvo cemo analizirati slucaj r > N. Tada је, usled ortonormalnosti sopstvenih vektora { Cr}, ct(c;oJ = -(l+aXл -л )сто. dt r n r n (7.72) Posto је а> -1, tada Crт8n tezi asimptotski nuli kako t-+ со, posto је ро pretpostavci Ar > An. Sada cemo analizirati slucaj rgy. Tada је (7.73) gde је б.._r, n) Кronekerov delta simbol. Mozemo uoCiti da su funkcije c/8n razdvojene u smislu da c/8n i c/8r zavise jedna od druge ali ne i od drugih funkcija. Slucaj r = n је najjednostavniji i daje (7.74) То implicira da c/8n tezi asimptotski nuli kako t-+ со posto је а< О. Konacno, razmotricemo i slucaj kada је f-l:.n , i kada su i r i n manji od N. Sada cemo analizirati sledeCi sistem od dve diferencijalne jednaCine (7.75) 145 о/П PogГav{je- ТОНМ metod Nekaje Tadajednacinu (7.75) mozemo pisati kao dX =АХ. dt 146 (7.76) (7.77) Dobro је poznato da resenje jednaCine (7.77) tezi asimptotski ka nuli ako i samo ako sн realni delovi оЬа korena karakteristicnog polinoma striktno negativni. Karakteristicni polinom se moze doЬiti iz sledece jednaCine det(sl- А) = О . (7.78) u nasem slucaju det(sl- А)= (s + (2 +а )A-r - (1 +а )А-п) (s+(2+a)-iп -(l+a)A-r) - (2-ir -AnX2A-n -Ar)= О , (7.79) ili posle odredenih transformacija (7.80) Koreni ove jednacine sн dati sa (7 .81 ) 146 147 'f)IJ CFogГavlie - ТОНМ metod. Nije tesko uoCiti da posto је -1 < а< О оЬа korena imaju negativan realan deo sto dalje znaCi da sporedni vektori matrice С predstavljaju asimptotski stabilna resenjajednaCine (7.49). Sada cemo analizirati ponasanje algoritma na bazi simulacUe. Razmotricemo simulaciju sistema malih dimenzija cije је ponasanje prikazano na slici 7.3. Broj ulaznih neurona је К= 5 i broj izlaznih neurona је N = 3. Vektori sa srednjom vrednoscu nula i medнsobno nekorelisanim komponentama su generisani na osnovu sledecihjednacina: x(l,i) = .2*sin(i/2); x(2,i) = .2*((rem(i,23)-11)/9).л5; x(3,i) = ((rem(i,27)-13)/9); х( 4,i) = ((rand(i, 1 )<.5)*2-1 ). *log(rand(i, 1 )+.5); x(5,i) = 1 *(-.5 + rand(i,1)). U tom slucaju su tri sporedna vektora с 1 = (00001)1 , с2 = (01000)1 i с3 = (10000)1 . Inicijalna vrednost W је bila Winit = 0.3*rand(5,3), dok је faktor ucenja bio у = 1/(i/2000+6). Slicnost sinaptickih vektora i odgovarajнcih sopstvenih vektora је merena na osnovu vrednosti ll'v;1c;ll, i = 1,2,3, i prikazanaje na slici 7.3. 1.4г--------.----------,-----.----------.------, ~ ·;:: 1.2 ~ .Е ·џ; (/) ~~· о ' -~-,,.; t5 .Ј •.,;.~ .. ·У ~ о .а r··Г' '/ ф ' ; • " О) '/ !lf't> "ф 0.6 ' i: о ~ м ·~~ .5 .\ ~~~ Е 0.4 ·• L:J"/.f, t ~ . \~Ylf:,/ ~ ~-11\\ ~ 0.2 (ј) . / о~---~---~----Ј_---~-~ о 500 1 оо о 1500 2000 lteration number Slika 7.3 Slicnost sinaptickih i sopstvenih vektora и zavisnosti od broja iteracija (tackasta linija predstavlja w 11c1, debela puna linija predstavlja \ђ1с2 i tanka puna linija predstavlja w з 1сз) 147 о/11 PogГavfie- ТОНМ metod 148 7.5 Generalizovani ТОНМ Nedavno је predlozena generalizacija ТОНМ metoda [Jankovic, 2005Ь] koja је nazvana GTOHM. Generalizovani zakon ucenja za izracunavnje РСАIМСА moze biti predstavljen sledecom jednacinom: LA РСА/ = FPpsA/ + D(i)IPsPCAorSMCA (7.82) МСА MSA gde LАРсNмсл definise ~ WрсNМсл (vidi (7.2)), FP definise porodicni deo zakona ucenja (koji је PSA ili MSA zakon ucenja) ~ WPSNМSA, IPsPCAorSMCA predstavlja individualni deo zakona ucenja (РСА ili МСА algoritam za izracunavanje dominantne ili najsporednije glavne komponente) i D(i) је dijagonalna matrica Ciji dijagonalni elemnti mogu biti u funkciji od vremena. Ako porodicni deo zakona ucenja predstavlja PSA algoritam tada је rezultujuCi algoritam РСА algoritam. Ako pak FP predstavlja MSA algoritam tada је rezultujuCi algoritam МСА tipa. Interesantno је zapaziti da individualni deo moze predstavljati algoritam za izracunavanje najsporednije glavne komponente dok algoritam ukupno predstavlja РСА, kao i da individualni deo moze biti algoritam za izracunavanje dominantne glavne komponente, dok algoritam sve zajedno vrsi izracunavanje МСА. Pojednostavljena matematicka analiza u opstem slucaju i rezultati simulacija za nekoliko specificnih algoritama su prikazani u [Jankovic, 2005Ь] . Moze se uociti da predlozeni metod omogucava kreiranje veoma velikog broja РСА/МСА algoritania na bazi dostupnih SPCA/SMCA i PSAIМSA algoritama. U zavisnosti od podrucja primene moze se konstruisati РСА/МСА algoritam koji је optimalan sa aspekta jednostavnosti implementacije u paralelnom hardeveru, brzine konvergencije ili stabilnosti rada. 148 o/III CFogCavEje ZaR.fjucak. Ovaj rad је posvecen jednostavnim bioloski verovatnim algoritmima za ekstrakciju glavnih komponenata i/ili njihovih potprostora iz kovarijansne matrice ulaznog signala, kao i pronalazenju generalnog metoda za transformaciju metoda za analizu glavnih i sporednih potprostora u metode za analizu glavnih i sporednih komponenata. U radu su proucavani jednostavni modeli koji, naravno, ne mogu da daju odgovor na osnovno pitanje na koji nacin se formira reprezentacija sveta u nasem mozgu. Predlozeni modeli u mnogo cemu ignorisu poznate Cinjenice о genetski determinisanim osobinama i anatomskim ogranicenjima mozga, ali oni demonstriraju neke principe koji, mozda, leze u osnovi naseg nervnog sistema, koji је za nas jos uvek velika nepoznanica. Predlozeni modeli su jednostavni, bazirani na lokalnim izracunavanjima i omogucavaju formiranje homogenih struktura, sto sve zajedno daje dobru osnovu za jednostavnu implementaciju u paralelnom hardveru. Izracunavanje glavnih/sporednih komponenata koriscenjem neuralnih mreza је proЫem koji је ispitivan u brojnim radovima u poslednjih dvadesetak godina. OЬlast interesovanja istrazivaca је bila podeljena na nekoliko celina. Jedan od pravaca istrazivanja је bilo pronalazenje struktura mreza koje bi bile bioloski verovatne. Та vrsta mreza Ьi Ьila koriscena za ispitivanje hipoteza о mogucim racunarskim konceptima koje primenjuje mozak. Jedan od osnovnih zadataka za istrazivace koji su se bavili ovim problemom је Ьiо rad na otkrivanju Ьioloski verovatne strukture koja Ьi mogla da bude primenjena za modelovanje pojedinacnog realnog neurona. U literaturi је predlozeno nekoliko pristupa koji su prikazani u trecem poglavlju, а detaljnije analizirani u petom poglavlju. Uglavnom su se sve metode bazirale na Hebovom zakonu ucenja koji је bio primenjivan na mrezi koja је sadrzala samo direktne veze od ulaza ka izlazu. Као sto је i о/ЈП PogГavfie- Zakljucak 150 op1sano u poglavlju pet, u tom slucaju је neophodno da se izvrsi modifikacija Hebovog zakona ucenja kako bi se izvrsila njegova stabilizacija. Manji broj radova se bavio drugim mogucim nacinima stabilizacije Hebovog zakona ucenja, kao sto је izmena strukture mreze na kojoj se zakon primenjuje, ili promena nacina na koji se izracunava potencijal izlaznog neurona. U petom poglavlju је predstavljen ооОН metod, koji predstavlja lineami model pojedinacnog neurona koji vrsi ekstrakciju dominantne glavne komponente kovarijansne matrice stacionamog ulaznog signala. Primena originalnog Hebovog zakona ucenja и ооОН neuralnoj mrezi, ne dovodi do divergencije norme sinaptickog vektora zahvaljujuCi usvojenoj strukturi mreze i usvojenom naCinu izracunavanja vrednosti potenc~ala izlaznog neurona. Predlozeni metod koristi оЬа kraja sinapse simetricno, i ne zahteva nikakva dodatna lokalna preracunavanja. Sa tehnicke tacke gledista ovo se moze smatrati dobrom stranom predlozenog algoritma. Originalna ideja, koja је koriscena pri konstrukciji strukture mreze, је da neuron pokusava da neutralise (potisne) izvor promene na svom ulazu. U tom slucaju је prisustvo povratnih veza neizbezno. Druga oЬlast istrazivanja, u oЬlasti izracunavanja glavnih komponenata na bazi neuralnih mreza, је vezana za realizaciju efikasnih algoritama za izracunavanje glavnog potprostora kovarijansne matrice ulaznog signala cija је srednja vrednost nula. Pored nastojanja da se koriste Ьioloski verovatni zakoni ucenja, dva apsekta su posebno naglasavana kod realizac~e takvih mreza, а to su brzina konvergencije algoritma i broj globalnih kalkulacija koje mreza koristi. U principu је pokazano da mreze koje sadrze samo lokalna preracunavanja za modifikaciju vrednosti sinapticke matrice konvergiraju mnogo sporije ka konacnom resenju od mreza koja koriste globalna izracunavanja. U literaturi nije dostupna informacija da је neko od predlozenih resenja bazirano na imitaciji neke od struktura koja se nalazi u realnim nervnim sistemima. Takode, da Ьi se obezbedio staЬilan rad ovih mreza, uglavnom је neophodno da se faktor ucenja sa protokom vremena smanjuje i tezi nuli. Ovi algoritmi su Oplsaш u cetvrtom poglavlju. Pojedini algoritmi su detaljnije analizirani na kraju sestog poglavlja. Sesto poglavlje opiSUJe МН i МНО metod koji se mogu koristiti za analizu glavnog potprostora kovarijansne matrice ulaznog signala. Ova dva metoda su inspirisana strukturom dela retine kod riЬa. МН metod је baziran na ekstenziji ооОН metoda. «StaЬilizacija» originalnog Hebovog zakona ucenja је postignuta uvodenjem samo jednog dodatnog modulisuceg signala. Originalna ideja је Ьila da se umesto velikog broja lokalnih povratnih 150 151 о/ЈП PogГav[ze- Zakljucak veza, koristi globalna povratna veza koja vrsi staЬilizacUи zakona исеnја. Kod МНО metoda је potrebna primena i lokalnih povratnih veza kako Ьi norma sinaptickih vektora Ьila 1. U оЬа metoda zakon исеnја је baziran na lokalnim izracиnavanjima. Jedina globalna izracиnavanja koja sи potrebna и slисаји МН i МНО algoritma sи izracunavanja energije koja se sadrzi и иlaznom i izlaznom signalи. Modifikacija pojedinih sinapsi и МН i МНО algoritmи ne zahteva podatak о eksplicitnoj vrednosti sinapse koja је vezana za Ьilo koji drugi neuron. Ovo se moze smatrati dobrom osoЬinom algoritma. Cinjenica da se moze иociti velika strukturna slicnost sa delom retine kod riba ukazиje na to da ovaj algoritam zaslиzиje daljи analizи . Na krajи sestog poglavlja је pokazano, na bazi simиlacija, da sи МН i МНО algoritmi staЬilni cak i и slисаји kada је faktor исеnја konstantan и tokи vremena, sto је veoma povoljna osoЬina za eventиalnи hardverskи realizacijи algoritma. Trece vazno podrиcje koja је istrazivano и oЬlasti izracunavanja glavnihlsporednih komponenata и neuralnim mrezama је vezano za otkrivanje algoritama/mreza koji се omogиCiti paralelnи ekstrakcijи veceg broja glavnihlsporednih komponenata istovremeno. Za razlikи od velikog broja algoritama za izracиnavanje PSAIМSA broj algoritama za izracunavanje РСА!МСА је relativno mali. Uglavnom sи РСА!МСА algoritmi doЬijani modifikacijom odredenog PSAIМSA algoritma и smislи иvodenja odredene nesimetrije ili nelineamosti, pri сети је ta modifikacija иvek Ьila specificna i vezana za izabrani PSAIМSA algoritam. Uvodenje nesimetrije i nelineamosti је dalje znacilo da ti algoritmi nisи pogodni za iщplementacijи и paralelnom hardveru. Jedini poznati algortitam za formiranje homogenih strиktura za derivacijи РСА!МСА је Ьigradijentni algoritam. Тај algoritam transformise algoritme za izracиnavanje jedne glavne/sporedne komponente и algoritme za ekstrakcijи vise glavnihlsporednih komponenata иvodenjem tzv. penala, koji forsira medиsobnи ortogonalnost sinaptickih vektora koji Cine sinaptickи matricи . Medиtim, taj algoritam ро svojoj strиkturi ne moze Ьiti koriscen za modelovanje Ьioloski verovatnih mreza. Generalni metod za transformacijи PSAIМSA metoda и РСА!МСА metode је prikazan и sedmom poglavljи. Metod је baziran na originalnoj ideji о porodicnom principи koji kaze da svaki neиron pokиsava da uradi ono sto је najbolje za njegovи porodicи i zatim ono sto је najbolje za njega samog. Primena ove ideje је rezиltovala generalnim algoritmom koji је nazvan vremenski orijentisan hijerarhijski metod (ТОНМ). Primena ovog metoda omogиcava formiranje homogenih (simetricnih) struktura za realizacyи РСА/МСА и paralelnom hardveru. Uvodenje vremenske hijerarhije и realizacijи algoritma dovodi do zanimljive hipoteze о neophodnosti postojanja vise od jedne vrste neиrotransmitera, kao i hipoteze da razliCite vrste neиrotransmitera odgovarajи procesima na razliCitim vremenskim skalama. U 151 о/ЈП Pogfav{ze- Zakljucak 152 radu је prikazana uproscena matematicka analiza u opstem slucaju. Stabilnost metoda је detaljno analizirana na jednom РСА i jednom МСА metodu. Ono sto је potrebno naglasiti је da primena ovog metoda dovodi do formiranja vise stotina (ра i hiljada) novih РСА!МСА algoritama. U zavisnosti od zeljenog podrucja primene moze se formirati optimalan algoritam koriscenjem poznatih algoritama za PSAIМSA i odgovarajucih algoritama za izracunavanje pojedinacne glavne/sporedne komponente. Teorijski doprinos ovog rada se ogleda u sledecem: pokazano је da direktna primena Hebovog zakona ne dovodi do divergencije sinaptickog vektora ako se taj zakon primeni na mrezi odgovarajuce strukture; predlozena је struktura neuralne mreze koja је u mnogo cemu slicna sa strukturom dela retine kod riЬa; prikazan је generalni metod koji transformise PSAIМSA metode u РСА!МСА metode i tako omogucava formiranje veoma velikog broja novih РСА/МСА algoritama. Koriscenjem ove transformacije moguce је formiranje homogenih algoritama na bazi Hebovog zakona ucenja, koji koriste samo lokalno dostupne podatke za modifikaciju vrednosti sinapticke matrice, i koji bi onda mogli biti smatrani za bioloski verovatne. Prakticna primena originalnih metoda koje su predlozene u ovom radu је moguca pri resavanju Ьilo kog problema gde se zahteva izracunavanje glavnihlsporednih komponenata ili l!jihovih potprostora u neuralnim mrezama. Medutim, njihova glavna primena se moze naci u mogucem modelovanju racunskih principa koji se koriste u realnim neuralnim mrezama i kod jednostavne realizacije PSAIМSA ili РСА!МСА algoritama u paralelnom hardveru. Radovi koji su objavljeni u vezi sa temom ove teze su: А. Radovi vezani za ооОИ metod [1] Jankovic, М., "А new simple ооОН neuron model as а principal component analyzer", ССЕСЕ '01, Toronto, Canada, Мау 2001, рр. 981-986, (CD ROM code: f45ta207) . [2] Jankovic, М. , "А simple Ьiologically inspired principal component analyzer- ModH neuron model", NEUREL-2002, Belgrade, Yugoslavia, September 2002, рр. 23-26. [3] Jankovic, М., "А new simple ооОИ neuron model as а Ьiologically plausiЬle principal component analyzer", IEEE Trans. on Neural Networks, vol. 14, рр. 853-859, 2003. В. Radovi vezani za МИ i МИО metod [1] Jankovic, М. , "А new modulated HebЬian leaming rule- method for local computation of а principal subspace", ICONIP2001 , Shanghai, China, November 2001, Vol. 1, рр . 470-475. 152 153 о/ЈП PogГavlie- Zakljucak [2 Ј Jankovic, М and Ogawa, Н ''А пеw modulated НеЬЬ learning rule - Biologically plausiЬ!e methodfor !оса! computation ofprincipal subspace", lnt. Ј Neural Systems, Vol. 13, no.4, рр. 215-224, 2003. [3] Jaпkovic, М., Ogawa, Н., "Modulated НеЬЬ Оја learпiпg rule- а method for priпcipal subspace aпalysis" , IEEE Traпs. оп Neural Networks, vol. 17, по. 2, рр. 345- 356 ' 2006. С. Radovi vezaпi za ТОНМ metod [1] Jankovic, М. and Ogawa, Н. "Method for transformation ofprincipal subspace algorithms to principal components algorithms ", ICESТ' 04, рр. 65-68, Bitola, Macedonia, 2004. [2 Ј Jankovic, М and Ogawa, Н, "Time-oriented hierarchical method for computation ој principal components using subspace learning algorithm ", Int. Ј Neural Systems, Vo/.14, no.5, рр.313-324, 2004. [3] Jankovic, М. and Ogawa, Н. , "Time-oriented hierarchical method for computation of minor components", ICANNGA '05, рр. 38-41 , Portugal, 2005 . [4] Jankovic, М. and Reljin, В . , "Neurallearning on Grassman/Stiefel principal/minor submanifold", EUROCON 2005, рр . 249-252, Serbia and Montenegro, 2005 . (5] Jankovic, М. апd Reljiп, В., "А пеw minor соmропепt aпalysis method based оп Douglas-Kuпg-Amari miпor subspace aпalysis method", IEEE Sigпal Processiпg Letters, vol. 12, рр. 859-862, 2005. Dalja analiza moze Ьiti usmerena na sledece proЫeme : 1. Matematicka analiza соН О metoda u opstijem slucaju. 2. Matematicka analiza МНО metoda u opstijem slucaju. 3. Pokusaj daUeg smanjenja globalnih izracunavanja u МНО modelu modifikacijom srtukture neuralne mreze. 4. Dalja generalizacija ТОНМ metoda kako sa aspekta pпmenJenog individualnog zakona ucenja, tako i naCina na koji se taj zakon primenjuje. Na primer, umesto uzimanja indivudualnog clana zakona ucenja sa tezinom koja је manja od jedan, mogao Ьi se primeniti i princip drugacUeg vremena odabiranja koji Ьi se primenio na taj deo zakona ucenja (odnosno taj deo zakona ucenja Ьi se ubacivao u formulu svaki n-ti put). 5. Eventualna analiza staЬilnosti ТОНМ u opstem slucaju. 6. Analiza staЬilnosti РСА/МСА algoritama doЬijenih primenom ТОНМ metoda na PSA/МSA metode koji su bazirani na ucenju na ortogonalnim grupama ili Stifelovoj mnogostrukosti. 153 Literatura [1] К. Abed-Meraim, А. Chkief and У. Hua (2000) "Fast orthonormal PAST algorithm", IEEE Signal Processing Letters, vol. 7, no. 3, рр . 60-62. [2] S.-1. Amari (1978) "Neural theory of association and concept formation", Вiological Cybernetics, vol. 26, рр. 175-185. [З] Ј.Ј . Atick and A.N. Redlich (1990) "Towards а theory of early visual processing", Neural Computation, vol. З, рр . ЗО8-З20 . [4] Ј.Ј. Atick and A.N. Redlich (1992) "What does the retina know about natural scenes?", Neural Computation, vol. 4, рр . 196-210. [5] Ј.Ј. Atick and A.N. Redlich (199З) "Convergent algorithm for sensory receptive field development", Neural Computation, vol. 5, рр. 45-60. [6] Z. Bai, Ј . Demmel, Ј . Dongarra, А. Ruhe and Н. van der Vorst (editors), (2000) Templates jor the Solution ој Algebraic Eigenvalue ProЫems: А Practical Guide, SIAM, Philadelphia. [7] Р. Baldi and К. Homik (1995) "Leaming in linear neural networks: А survey", IEEE Trans. Neural Networks, vol. 6, рр. 837-858. [8] S. Bannour and M.R. Azimi-Sadjadi (1989) "Principal component extraction using recursive least squares leaming", IEEE Trans. оп Neural Networks, vol. 6, рр . 456-469. [9] E.L. Bienenstock, L.N. Cooper and P.W. Munro (1982) "Theory for the Development of Neuron Selectivity: Orientation Specificity and Binocular Interaction in Visual Cortex", The Journal ој Neuroscience , vol. 2, No. 1, рр . 32-48. [10] R.W. Brockett (1991) "Dynamical systems that leam subspaces", Mathematical system theory: The injluence ој R.E. Kalman, рр. 579-592, Springer, Berlin. [11] R.W. Brockett (1991) "Dynamical systems that sort lists, diagonalize matrices and solve linear programming proЬlems", Liпear Algebra Applicatioпs, vol. 146, рр. 79-91 . [12] Т.Н. Brown, Е. W. Kairiss and С . L. Keenan (1990) "Hebbian synapses: Biophysical mechanisms and algorithms", Аппи. Rev. Neurosci. , рр . 475-51 1. [13] А. Cattaneo, L. Maffei and С. Мопоnе (1981) "Pattems in the discharge of simple and complex visual cortical cells", Proc. R. Sot. Lопdоп В, vol. 21 2, рр. 279-297. [14] G.A. Carpenter and S. Grossberg (1988) "The ART of adaptive pattem recognition Ьу а self-organizing neural network", Computer, 21 , рр . 77-88 . [15] W.K. Chen (1971) Applied Graph Theory, John Willey and Sons, New York. [16] Т.-Р. Chen and S. Amari (2001) "Unified staЬilization approach to principal and minor components", Neural Networks, vol. 14, рр . 1377-1387. [17] Т.-Р. Chen, S. Amari, and Q. Lin (1998) "А unified algorithm for principal and minor components extraction", Neural Networks, vol. 11, рр. 385-390. [18] Т. Chen, У. Hua and W. Yan (1998) "Global Converegence ofOja's Subspace Algorithm for Principal Component Extraction", IEEE Traпs. Neural Networks, vol. 9, no. 1, рр.58-67 . [19] С . Chatterjee, Z. Kung and V.P. Roychowdhury (2000) "Algorithms for Accelerated Convergence of Adaptive РСА", IEEE Traпs. Neural Networks, vol. 11 , no. 2, рр. 338-355. [20] С . Chatterjee, V.P. Roychowdhury and Е.К.Р. Chong (1998) "On relative convergence properties of principal component analysis algorithms", IEEE Traпs. оп Neural Networks, vol. 9, no. 2, рр. 319-329. [21] С. Chatterjee, Z. Kung and V.P. Roychowdhury (2000) "Algorithms for accelerated convergence of adaptive РСА", IEEE Traпsactioпs оп Neural Networks, vol. 11, no. 2, рр. 338-355. [22] А. Cichocki, S.-I. Amari, (2002) Adaptive Вliпd Sigпal апd Jmage Processiпg - Learniпg Algorithms апd Applicatioпs, John Wiley and Sons, New York. [23] А. Cichocki, R.R. Gharieb, and Т. Ноуа (2001) "Efficient extraction of evoked potentials Ьу comЬination of independent component analysis and cumulant-based matched filtering", in Proc. Ј /h IEEE Sigпal Processiпg Workshop оп Statistical Sigпal Processiпg, рр. 237-240, Singapore. [24] А. Cichocki and R. Unbehauen (1993) "Robust estimation of principal components in real time", Electroпics Letters, vol. 29, no. 21 , рр . 1869-1870. 155 [25] А. Cichocki and R. Unbehauen (1994) Neural Networksfor Optimizatioп апd Sigпal Processiпg, John Wiley & Sons, New York. [26] А. Cichocki, R. Swiniarski and R.E. Bogner (1996) "Hierarchical neural networks for robust РСА of complex-valued signals", in Proc. World Coпgress оп Neural Networks, WCNN-96, USA, рр. 818-821 . [27] G. Cirrincione (1998) "А Neural Approach to the Structure from Motion ProЬlem", Ph.D. thesis, INPG GrenoЬle, France. [28] Ј. Е. Dayhoff and G. L. Gerstein (1983) "Favored patterns in spike trains. П", Application. Journal ofNeurophysiology, vol. 49, рр . 1349-1363. [29] Р. Dayan, G.E. Hinton, R.M. Neal and R.S. Zemel (1995) "The Helmholtz machine", Neural Computatioп 7(5), рр. 889-904. [30] G. Deco and D. Obradovic (1996) Ап lnformatioп-Theoretic Approach to Neural Computiпg, Springer-Verlag New У ork Inc. [З 1] K.I. Diamantaras (1996) "Robust principal component extracting neural networks", ICNN'96, Washington, D.C., USA, рр. 74-77. [32] K.I. Diamantaras and S.Y. Kung (1996) Priпcipal Сотропепt Neural Networks- Theory апd Applicatioпs, John Wiley & Sons Inc., New York. [33] R. Ј . Douglas and К. А. С . Martin (1991) "Opening the gray Ьох", Treпds iп Neuroscieпce, vol. 14, рр. 286-293. [34] R. Ј. Douglas, К. А. С. Martin and D. Whitteridge (1988) "Selective responses ofvisual cortical cells do not depend on shunting inhiЬition", Nature, vol. 332, рр . 642-644. [35] S.C. Douglas, S.Y. Kung and S. Amari (1998) "А self-stabilized minor subspace rule", IEEE Sigпal Processiпg Letters, vol. 5, no. 12, рр . 328-330. [36] S.C. Douglas, S.-У. Kung, S. Amari (1999) "On the numerical staЬilities of principal, minor and independent component analysis algorithms", in Proc. IEEE Iпternatioпal Confereпce оп Iпdepeпdeпt Сотропепt Aпalysis апd Sigпal Separatioп, France, рр. 419-425. [37] Ј. Dowling (1987) The Retiпa: Ап ApproachaЫe Part of the Braiп, The Belknap Press ofHarward University Press. [38] А. Edelman, Т.А. Arias and S.T. Smith (1998) "The geometry of algorithms with orthogonality constraints", SIAM Journal оп Matrix Aпalysis Applicatioпs, vol. 20, no. 2, рр . 303-353. [39] С . Eшoth-Cugell and J.G. Robson (1966) "The contrast sensitivity of retinal ganglion cells ofthe cat", Journal ој Physiology, 187, рр . 517-552. 156 [40] S. Fiori (2002) "А minor subspace algorithm based on neural Stiefel dynamics", International Journal ој Neural Systems, vol. 12, no. 5, рр . 339 - 350. [41] S. Fiori (2003) "А Neural Minor Component Analysis Approach to Robust Constrained Beamforming", IEE Proceedings - Vision, Image and Signal Processing, vol. 150, рр. 205-218. [ 42] S. Fiori (200 1) "А theory for learning Ьу weight flow on Stiefel-Grassman manifold", Neural Computation, vol. 13, рр. 1625-1647. [ 43] L. Fox (1962) Numerical Solution ој Ordinary and Partial Differential Equations, Pergamon Press. [44] С. Fyfe and R.J. Baddeley (1995а) "Finding compact and sparse distriЬuted representations of visual images", Network: Computation in Neural Systems vol. 6, no.3, рр. 334-344. [45] С. Fyfe and R.J. Baddeley (1995Ь) "Nonlinear data structure extraction using simple HebЬian networks", Вiological Cybernetics, vol. 72, no.6, 533-541. [46] Р. Foldiak (1992) "Models of Sensory Coding", Technical Report CUED/F- INFENG/TR 91 , Cambridge University Engineering Department, UK. [47] Р. Foldiak (1991) "Learning invariance from transformation sequence", Neural Computation, vol. 3, рр. 194-200. [48] М.С. Goodall (1960) "Performance of stochastic net", Nature 185, рр. 557- 558. [49] S. Grossberg (1973) "Contour enhancement, short-term memory, and constancies in reverberating neural networks", Studies in Applied Mathematics, vol. 52, рр. 213-257. [50] S. Grossberg (1988) "Nonlinear neural networks: principles, mechanisms, and architectures", Neural Networks, vol. 1, рр. 17-61. [51] G.F. Harpur (1997) "Low entropy coding with unsupervised neural networks", Ph.D. thesis, Cambridge University Engineering Department, UK. [52] G.F. Harpur and R.W. Prager (1994) "Experiments with simple HebЬian-based leaming rules in pattem classification tasks", Technical report CUED/F- INFENG/ТR 168, Cambridge University Engineering Department, UК. [53] D.O. НеЬЬ (1949) The Organisation ojBehaviour, New York: Wiley. 157 [54] G.E. Hinton (1987) "Learning translation invariant recognition in а massively parallel network", In G. Goos & Ј. Hartmanis (Eds.), PARLE: Parallel Architectures and Languages Europe (рр. 1-13). Berlin: Springer-Verlag. [55] Н. Hotelling (1933) "Analysis of а complex of statistical variaЫes into principal components", Journal ој Educational Psychology, vol. 24, рр . 417- 441. [56] У. Hua, У. Xiang, Т.-Р . Chen, К. Abed-Meraim and Y.Miao (1999) "А ne\v Iook at the power method for fast subspace tracking", Digital Signal Processing, vol. 9, рр. 297-314. [57] Н. Hubel and Т. N. Wiesel, (1974) "Uniformity of monkey striate cortex: А parallel between field size, scatter, and magnification factor", Ј Comu. Neurol., vol. 158, рр. 295-305. [58] N. Intrator and L.N. Cooper (1992) "Objective function formulation of the ВСМ theory of visual cortical plasticity: statistical connections, staЬility conditions", Neural Networks, vol.5, рр. 3-17. [59] М. Jankovic (2001а) "А new simple ооОН neuron model as а principal component analyzer", in Proc. ССЕСЕ 'О Ј, Toronto, Canada, рр. 981-986, (CD ROM code: f45ta207). [60] М. Jankovic (2001Ь) "А new modulated HebЬian learning rule- method for local computation of а principal subspace", in Proc. ICONIP 200 Ј, Shanghai, China, vol. 1, рр. 470-475 . [61] М. Jankovic (2002) "А simple Ьiologically inspired principal component analyzer - ModH neuron model", in Proc. NEUREL-2002, Belgrade, Yugoslavia, рр. 23-26. [62] М. Jankovic (2003а) "А new simple ооОН neuron model as а Ьiologically plausiЫe principal component analyzer", IEEE Trans. оп Neural Networks, vol. 14, рр. 853-859. [63] М. Jankovic and Н. Ogawa (2003Ь) "А new modulated НеЬЬ learning rule- Biologically plausiЫe method for local computation of principal subspace", Int. Ј Neural Systems, vol.13, no.4, рр . 215-224. [64] М. Jankovic and Н. Ogawa (2004а) "Method for transformation of principal subspace algorithms to principal components algorithms ", in Proc. ICESТ' 04, рр. 65-68, Bitola, Macedonia. [65] М. Jankovic and Н. Ogawa (2004Ь) "Time-oriented hierarchical method for computation of principal components using subspace learning algorithm", Int. Ј Neural Systems, vol.l4, no.5, рр.ЗlЗ-324. 158 [66] М. Jankovic and Н. Ogawa (2005а) "Time-oriented hierarchical method for computation of minor components", in Proc. ICANNGA '05, рр. 38-41, Portugal. [67] М. Jankovic and В . Reljin (2005Ь) "Neural learning on Grassman/Stiefel principal/minor submanifold", in Proc. EUROCON 2005, рр . 249-252, SerЬia and Montenegro. [68] М. Jankovic and В. ReUin (2005с) "А new minor component analysis method based on Douglas-Kung-Amari minor subspace analysis method", IEEE Sigпal Processiпg Letters, vol. 12, no. 12, рр . 859-862, 2005. [69] М. Jankovic and Н. Ogawa (2006) "Modulated НеЬЬ Оја leaming rule - а method for principal subspace analysis", IEEE Traпs. оп Neural Networks, vol. 17, no. 2, рр. 345-356, 2006. [70] К. Karhunen (1947) "0Ъеr lineare Methoden in der Wahrscheinlichkeitsrechnung," Апп. Acad. Sci. Feпn., Ser. A.l .: Math.-Phys., vol. 37, рр. 3-79. [71] Ј. Karhunen, А. Cichocki, W. Kasprzak, and Р. Pajunen (1997) "On neural Ьlind separation with noise suppresion and redundancy reduction", Iпt. Journal оп Neural Systems, vol. 8, no. 2, рр. 219-237. [72] R. Klemm (1987) "Adaptive airbome МТI: an auxiliary channel approach", IEE Proceediпgs, vol. 134, рр . 269-276. (73] Т. Р .Krasulina (1970) "Method of stochastic approximation in the determination of the largest eigenvalue of the mathematical expectation of random matrices," Automat. Remote Coпtr., vol. 2, рр. 215-221. [7 4] Т. Kohonen (1982) "Self-organization of Topologically Сопесt F eature Maps", Biological Cybernetics, vol. 43, рр. 59-69. [75] Т. Kohonen (1995) Self-Orgaпiziпg Maps, Springer, Berlin (3rd Edition, 2001) [76] Т. Kohonen (1982) "Self-organization of topologically сопесt feature maps", Вiological Cybernetics, vol. 43, рр. 59-69. [77] S.Y. Kung, К. Diamantaras and Ј. Taur (1991) "Neural networks for extracting pure/constrainedloriented principal components", in J.R. Vaccaro, editor, SVD апd Sigпal Processiпg, рр. 57-81, Elsevier Science, Amsterdam. [78] А.Р . Liavas, Р.А. Regalia and Ј.-Р. Delmas (1999) "Вlind channel approximation: Effective channel order determination", IEEE Traпs. Sigпal Processiпg, vol. 47, рр . 3336-3344. [79] R. Linsker (1988) "Self-organization in а perceptual network", Computer, vol. 21, рр. 105-117. 159 [80] L. Ljung (1977) "Analysis of recursive stochastic algorithms", IEEE Trans. Automat. Coпtr. , vol. 22, рр. 551-575. [81] М. Loeve (1948) "Fonctions al'eatoires du second ordre," in Processus stochastiques et mouvemeпts Browпieпs (Р . L'evy, ed.), Paris, France: Gauthier-Villars. [82] E.N. Lorenz (1956) "Empirical orthogonal functions and weather prediction", Sci. Rept. No. 1, Contract AF19(604)-1566, Dept. ofMeteorology, M.I.T., 49. [83] Н. Luo, R.-W. Liu and Y.Li (1997) "Internal structure identification for layered medium", iп Proc. IEEE ISCAS, рр. 161-164, USA. [84] G. Mathew and V. Reddy (1994) "Orthogonal eigensubspace estimation using neural networks", IEEE Traпs. оп Sigпal Processiпg, vol. 42, рр . 1803-1811 . [85] С. Metin and D. О. Frost (1989) "Visual responses of neurons in somatosensory cortex of hamsters with experimentally induced retinal projections to somatosensory thalamus", Proc. Natl. Acad. Sci. USA, 86, 357- 361. [86] Т.Р. Minka (2001) "Automatic choice of dimensionality for РСА", In NIPS 13 in Todd К. Leen, Thomas G. Dietterich and Volker Tresp, editors, Advaпces iп Neural Jпformatioп Processiпg Systems, рр. 598-604, МIТ Press. [87] Ј.А. Movshon, I.D. Thompson and D.J. Tolhurst (1978) "Spatial summation in · the receptive fields of simple cells in the cat's striate cortex", Journal ој Physiology, vol. 283, рр. 53-77. [88] Н. Ogawa (1992) "Karhunen-Loeve subspace", in Proc. Iпterпatioпal Сопfеrепсе оп Pattern Recogпitioп, Hague, The Netherlands, рр. 75-78. [89] Е. Оја (1982) "А simplified neuron model as а principal component analyzer", Ј Math. Biol., vol. 15, рр. 267-273. [90] Е. Оја (1983) Subspace Method ој Pattern Recogпitioп, Research Studies Press and Ј. Wiley, Letchworth. [91] Е. Оја and Ј. Karhunen (1985) "On stochastic approximation of the eigenvectors and eigenvalues ofthe expectation of а random matrix", Ј Math. Апаl. , Appl., 106, рр. 69-84. [92] Е. Оја (1989) "Neural networks, principal components, and subspaces", Јпt. Ј Neural Systems, 1, рр. 61-68. [93] Е. Оја (1992а) "Principal components, minor components and linear neural networks", Neural Networks, vol. 5, рр. 927-935. 160 [94] Е. Оја, Н. Ogawa and Ј. Wangviwattana (1992Ь) "Principal component analysis Ьу homogeneous neural networks, Part 1: The weighted subspace criterion", IEICE Traпs. Iпf&Syst., E75-D, 3, рр. 366-375. [95] Е. Оја, Н. Ogawa and Ј . Wangviwattana (1992с) "Principal component analysis Ьу homogeneous neural networks, Part 11: Analysis and extensions of the leaming algorithm", IEICE Traпs. Jпf&Syst. , E75-D, 3, рр. 376-382. [96] Е. Оја, Ј. Karhunen and А. Hyvarinen (1997) "From neural principal components to neural independent components", in Proc. Iпt. Сопfеrепсе оп Arrtifical Neural Networks, Lausanne, Switzerland. [97] Е. Оја, S. Kaski (Eds.) (1999) "Kohonen Maps", Elsevier, Amsterdam. [98] S. Ouyang, Z. Вао and G. Liao (2000) "Robust recursive Least Squares Leaming Algorithm for Principal Component Analysis", IEEE Traпs. Neural Networks, vol. 11, no. 1, рр . 215-221. [99] К. Pearson (1901). Оп liпes апd plaпes of closest fit to systems ofpoiпts iп space, The London, Ediпburgh апd DuЬliп Philosophical Magaziпe апd Jourпal ofScieпce, Sixth Series 2, 559-572. [100] М. PlumЬley (1991) "On information theory and unsupervised neural networks", Technical Report CUED/F-INFENG/ТR. 78, Cambridge University Engineering Department, UK. [101] У. Rao and Ј.С. Principe (2002) "Time series segmentation using novel adaptive eigendecomposition algorithm", Journal of VLSI Sigпal Processiпg, vol. 32(1/2), рр. 7-17. [102] 1. Reljin, G. Jovanovic, В. Reljin (2002а) "The use ofSOM neural network for precipitation pattem recognition in Yugoslavia", in Proc. 18th Iпt. Сопf оп Carpathiaп Meteorology, рр. 24-25, Belgrade, Oct. 7-11. [103] 1. Reljin, В . Reljin, G.Jovanovic (2002Ь) "Clustering of climate data in Yugoslavia Ьу using SOM neural network", in Proc. 2002 61h Semiпar NEUREL, рр. 203-206, Belgrade, Sept. 26-28. [ 104] Н. Ritter, Т. Martinetz, К. Schulten ( 1992) Neural Computatioп апd Self- Orgaпiziпg Maps: Ап Iпtroductioп, Addison-Wesley, Reading, МА. [105] Ј. Rockel, R. W. Homs and Т. 1. S. Powell (1980) "The basic uniformity in structure ofthe neocortex", Braiп, vol. 103, рр. 221-244. [106] Р.Ј. Rousseeyw and D.K. van Driesen (1999) "А fast algorithm for the minimum covariance determinant estimator", Techпometrics, vol. 41, рр. 212- 223. [107] S.T. Roweis (1998) "ЕМ algorithmsfor РСА and SPCA", in Proc. Advaпces iп Neural Jпformatioп processiпg Systems, NIPS-98, 10:452-456. 161 [108] Н. Sakai and К. Shimizu (1997) "Two improved algorithms for adaptive subspace filtering", in Proc. 111h IFAC Symposium System Ideпtificatioп (SYSID '97), рр. 1б89-1б94, Kitakyushu, Japan. [109] T.D. Sanger (1989) "Optimal unsupervised learning in а single-layer linear feedforward neural network", Neural Networks, vol. 2, no. б, рр . 459-47З . [ 11 О] Е . Saund (1995) "А multiple cause mixture model for unsupervised learning", Neural Computatioп, vol. 7, рр. 51-71. [ 111] R. Schmidt (198б) "Multiple emitter location and signal parameter estimation", IEEE Traпs. Оп Апtеппаs апd Propagatioп, vol. З4, рр . 27б-280 . [112] Т.Ј. Sejnowski and С . R. Rosenberg (1987) "Parallel networks that leam to pronounce English text", Complex Systems, L 145-1б8. [113] Ј. Sherry, D. L. Barrow and W. R. Klemm (1982). "Brain", Research Bulletiп, S, 1бЗ-1б9. [114] М. Sur, I. Е. Garraghty and А. W. Roe (1988) "Experimentally induced visual projections into auditory thalamus and cortex", Scieпce, vol. 242, рр . 14З7- 1441. [115] М.Е. Tipping, and С.М. Bishop (1999) "Probabilistic principal component analysis", Journal of the Royal Statistical Societe, Series В, vol. З, рр. б00- б1б. [ llб] М. Turk and А. Pentland (1991) "Eigenfaces for recognition", Journal ој Cogпitive Neuroscieпce, vol. З, рр. 71-8б . [117] М. VanНulle (2002) Faithful Represeпtatioпs апd Topographic Maps, Wiley, NewYork. [ 118] Ј. Wallace, R. Dickinson ( 1972) "Empirical orthogonal representation of time series in the frequency domain. Part I: Theoretical considerations", Journal of Applied Meteorology, vol. 11, no. б, рр. 887-892. [119] L. Wang, and Ј. Karhunen (199б) "А unified neural bigradient algorithm for robust РСА and МСА", Iпt. Ј ofNeural Systems, vol. 7, no. 1, рр. 5З-б7 . [120] М. Wax and Т. Kailath (1985) "Detection of signals Ьу information theoretic criteria", IEEE Traпs. Acoustic, Speech, Sigпal Processiпg, ЗЗ:З87-З92. [121] А Weingessels and К. Homik (2000) "Local РСА algorithms", IEEE Traпs. Neural Networks, vol. 11, no. б, рр. 1242-1250. [122] L. Wiscott (1998), "Learning invariance manifolds", in Proc. Iпternatioпal Сопfеrепсе оп Artificial Neural Networks (ICANN), рр. 555-5б0 . 1б2 [123] L. Xu (1993) "Least mean square error reconstruction principle for self- organizing neural nets", Neural Networks, vol. б, рр. 627-648, 1993. [124] L. Xu, Е. Оја, С.У. Suen (1992) "Modified HebЬian leaming for curve and surface fitting", Neural Networks, vol. 5, рр. 441-457. [125] L. Xu and А. Yuille (1993) "Self organizing rules for robust principal component analysis", in Proc. Advaпces iп Neural Jпformatioп Processiпg Systems, NIPS 5, рр. 467-474. [126] W. Yan, U. Helmke and Ј.В. Moore (1994) "Global Analysis ofOja's flovv for Neural Networks", IEEE Traпs. оп Neural Nenvorks, vol. 5, no. 5, рр . 674- 683 . [127] М.Р. Young, К. Tanaka and S. Yamane (1991) "On oscillating neuronal responses in the visual cortex of the monkey" In University Laboratory of Physiology, Oxford,manuscript. [128] A.L. Yuille, D.M. Kammen and D.S. Cohen (1989) "Quadrature and development of orientation selective cortical cells Ьу НеЬЬ rules", Biological Cybernetics, vol. 61, рр. 183-194. [129] Q. Zhang and У. Leung (2000) "А class of leaming algorithms for principal component analysis and minor component analysis", IEEE Traпs. оп Neural Networks, vol. 11, no. 2, рр. 529-533 . 163 Прилог 1. Изјава о ауторству Потписани-а Јанковић, Марко В. Изјављујем да је докторска дисертација под насловом Самоорганизујуће неуралне мреже за анализу главних компонената • резултат сопственог истраживачког рада, • да предложена дисертација у целини ни у деловима није била предложена за добијање било које дипломе према студијским програмима других високошколских установа, • да су резултати коректно наведени и • да нисам кршио/ла ауторска права и користио интелектуалну својину других лица. Потпис Прилог 2. Изјава о коришћењу Овлашћујем Универзитетску библиотеку "Светозар Марковић" да у Дигитални репозиторијум Универзитета у Београду унесе моју докторску дисертацију под насловом: Самоорганизујуће неуралне мреже за анализу главних компонената која је моје ауторска дело. Дисертацију са свим прилозима предао/ла сам у електронском формату погодном за трајно архивирање. Моју докторску дисертацију похрањену у Дигитални репозиторијум Универзитета у Београду могу да користе сви који поштују одредбе садржане у одабраном типу лиценце Креативне заједнице (Creative Commons) за коју сам се одлучио/ла. 1. Ауторство 2. Ауторство - некомерцијално ·~ [9Ауторство - некомерцијално- без прераде 4. Ауторство - некомерцијално- делити под истим условима 5. Ауторство- без прераде 6. Ауторство- делити под истим условима (Молимо да заокружите само једну од шест понуђених лиценци, кратак опис лиценци дат је на полеђини листа). Потпис У Београду, ,1 /\ . D 1- . )~ 0 1 ~ . /~~ ~~ /т---',;""----fј/'/ 1. Ауторство - Дозвољавате умножавање, дистрибуцију и јавно саопштавање дела, и прераде, ако се наведе име аутора на начин одређен од стране аутора или даваоца лиценце, чак и у комерцијалне сврхе. Ово је најслободнија од свих лиценци. 2. Ауторство - некомерцијалне. Дозвољавате умножавање, дистрибуцију и јавно саопштавање дела, и прераде, ако се наведе име аутора на начин одређен од стране аутора или даваоца лиценце. Ова лиценца не дозвољава комерцијалну употребу дела. З. Ауторство - некомерцијалне - без прераде. Дозвољавате умножавање, дистрибуцију и јавно саопштавање дела, без промена, преобликовања или употребе дела у свом делу, ако се наведе име аутора на начин одређен од стране аутора или даваоца лиценце. Ова лиценца не дозвољава комерцијалну употребу дела. У односу на све остале лиценце, овом лиценцом се ограничава највећи обим права коришћења дела. 4. Ауторство - некомерцијалне - делити под истим условима. Дозвољавате умножавање, дистрибуцију и јавно саопштавање дела, и прераде, ако се наведе име аутора на начин одређен од стране аутора или даваоца лиценце и ако се прерада дистрибуира под истом или сличном лиценцом. Ова лиценца не дозвољава комерцијалну употребу дела и прерада. 5. Ауторство - без прераде. Дозвољавате умножавање, дистрибуцију и јавно саопштавање дела, без промена, преобликовања или употребе дела у свом делу, ако се наведе име аутора на начин одређен од стране аутора или даваоца лиценце. Ова лиценца дозвољава комерцијалну употребу дела. 6. Ауторство - делити под истим условима. Дозвољавате умножавање, дистрибуцију и јавно саопштавање дела, и прераде, ако се наведе име аутора на начин одређен од стране аутора или даваоца лиценце и ако се прерада дистрибуира под истом или сличном лиценцом. Ова лиценца дозвољава комерцијалну употребу дела и прерада. Слична је софтверским лиценцама, односно лиценцама отвореног кода.