ALGORITMI STROJNOG UČENJA ZA OTKRIVANJE ZNANJA U SLOŽENIM STRUKTURAMA PODATAKA

Projekt financira Hrvatska zaklada za znanost
broj: 9623
početak: 16. kolovoza 2014.

Rezultati aktivnosti po točkama radnog plana:


O1: Feature extraction. Feature extraction from strings (Month 1-18)

A1.1 S. Ristov and D. Gamberger: Specification of applications that can exploit string type data as the input for machine learning procedures (završeno u studenom 2014.)
Standardni sustavi strojnog učenja koriste vektore značajki dobivene transformacijom ulaznih podataka. U mnogim slučajevima te transformacije prirodno proizlaze iz podataka i omogućavaju učinkovito razdvajanje ulaznih podatka u prostoru značajki. Međutim, postoje brojni slučajevi kad se ulazni podatci ne mogu jednostavno transformirati u eksplicitne vektore značajki. Primjeri za to su slike, grafovi, i podatci u obliku znakovnih nizova (strings) poput tekst dokumenta i bioloških sekvenci. Općenite karakteristike takvih podataka su da mogu biti tretirani kao sekvenca simbola, te da za takve ulazne podatke proces izlučivanja značajki može biti vrlo složen. Uprkos tome, u mnogim primjenama je vrlo važno da postoji mogućnost obrade sekvencijalnih podataka. Čest pristup rješavanju tog problema je korištenje klasičnog "bag of words" postupka gdje se ulazni nizovi izravno transformiraju u vektore preko zastupljenosti predefiniranih "riječi". To je moguće kad se ulazni podatci daju prikladno segmentirati, kao što je to slučaj s tekstovima na prirodnim jezicima. U nekim slučajevima to nije jednostavan pristup jer se, npr. u DNA slijedu ne mogu prirodno izdvojiti "riječi", već se moraju koristiti proizvoljno određeni n-grami.

Drugi način razdvajanja ulaznih podataka u grupe, kad se radi o znakovnim nizovima, je izravno računanje udaljenosti među njima. U takvim slučajevima ključ su dvije stvari: prva je izbor učinkovite mjere udaljenosti (ili, inverzno, sličnosti) između dva znakovna niza, takve da je primjerene vrsti podataka; i druga je postojanje učinkovitog algoritma računanja, što je važno budući da ulazni podatci mogu biti i vrlo dugački nizovi.

Slijed diskretnih znakova je jedan od temeljnih prikaza podataka u računarstvu, i velik je broj primjena u strojnom učenju koje se temelje na analizi takvih podataka. To su napose: u obradi prirodnog jezika razvrstavanje i dohvat dokumenata te pretraživači i rangiranje dokumenata; analiza bioloških sekvenci nukleotida i aminokisenina (npr. pronalaženje gena, prepoznavanje mjesta prekrajanja, ili predikcija funkcije proteina); u području računalne sigurnosti anti-virusni programi, nadzor mreže, filtriranje neželjene pošte i škodljivog softvera.

A2.1 S. Ristov: Investigating the possible transformations of continuous signals to discrete sequence of symbols (završeno u veljači 2015.)
Pretvorbom kontinuiranog signala u uređen niz diskretnih znakova postiže se dvojaki učinak. S jedne strane smanjuje se dimenzionalnost i složenost ulaznih podataka čime se omogućava jednostavnija i brža obrada. S druge strane, omogućava se korištenje postupaka za reprezentaciju podataka specifičnim značajkama izlučenim iz stringa. Pretvorba vremenskih serija u znakovne nizove moguća je na dva glavna načina: agregatnom aproksimacijom i simboličkim kodiranjem promjene.

Agregatnom aproksimacijom kontinuirani se signal unutar zadanog prozora aproksimira nekom vrijednosti kojoj je unaprijed pridijeljen neki simbol. Budući da se veličina prozora i veličina alfabeta simbola mogu mijenjati, transformacijom se može postići proizvoljno velik stupanj redukcije dimenzionalnosti ulaznog signala. Pri kodiranju promjena promatra se relativan odnos uzastopnih elemenata signala. U ovisnosti o vrsti promjena konstruira se znakovni niz od simbola koji te promjene kodiraju.

Kao i kod svakog postupka diskretizacije signala važan problem je izbor granica prozora, odnosno širine uzorka koji se zamjenjuje simbolom. Stoga su za transformaciju u znakovne nizove posebno pogodni periodički signali gdje postoji prirodna granica između dva perioda. Takve se vremenske serije često javljaju kod bilježenja fizioloških vrijednosti kao što su to mjerenja EKG signala ili motoričkih aktivnosti (hod, trk).

A3.1 S. Ristov: Investigating the possible use of straightforward features extracted from strings (završeno u svibnju 2015.)
Kod razmatranja mogućih značajki koje bi se mogle izvesti iz slijeda diskretnih znakova pokazalo se da se te značajke prirodno dijele u dvije grupe. U prvoj su značajke koje se mogu nazvati izravnima (straightforward), a u drugoj one koje su dobivene složenim postupcima pretvorbe ulaznog signala. Neformalna definicija izravnih značajki bila bi da su to one koje su: 1) jednostavno dostupne iz samog niza, poput duljine niza ili alfabeta znakova od kojih se niz sastoji; 2) koje se dobivaju jednostavnim operacijama kao što je to prebrojavanje pojedinih sastavnica niza; te 3) za čije izračunavanje su dovoljne osnovne računske operacije poput izračunavanja frekvencija pojedinih sastavnica. Primjeri izravnih značajki su: duljina niza, veličina i vrsta alfabeta, broj različitih n-grama, broj ponavljanja (frekvencija) pojedinih znakova ili n-grama, omjeri frekvencija različito izabranih sastavnica (npr. najčešće, najrjeđe i prosječno zastupljene) gdje sastavnice mogu biti sami znakovi ili n-grami različitih duljina. Općenito, možemo reći da su jednostavne značajke one koje se mogu dobiti bez matematičkih transformacija. Koliko će jednostavne značajke biti korisne u primjeni ovisi o vrsti ulaznih podataka i samom problemu klasifikacije. Budući da su jednostavne, mogu se dobiti bez velikog utroška računalnih resursa i mogu se bez velikog opterećenja uključiti u ulazne podatke u postupcima strojnog učenja.

A4.1 S. Ristov and D. Gamberger: Investigating the possible complex string transformations as the means for obtaining useful features (završeno u srpnju 2015.)
Osim jednostavnim postupcima, značajke se iz znakovnih nizova mogu dobiti i složenim transformacijama za koje, u pravilu, ili nisu dovoljne osnovne matematičke operacije, ili se te operacije provode nad podatcima koji nisu izravno uočljivi u nizu. Na primjer, iz nizova se mogu izračunati složene topološke osobine poput različitih koeficijenata distribucije regija s različitim gustoćama neke sastavnice (znaka ili n-grama), te zatim distribuciju tih koeficijenata po sastavnicama. Broj načina na koje se takvi topološki koeficijenti mogu definirati je praktično beskonačan pa postoji opasnost od pretjeranog procesiranja. Broj i vrstu topoloških koeficijenta trebalo bi prilagođavati vrsti ulaznih podataka. Još jedan tipičan primjer složenih transformacija su Fourrierovi koeficijenti, u ovom slučaju diskretni. Kod njih je problem što postupci izračunavanja mogu biti dugotrajni ako se radi o dugačkim ulaznim nizovima. Posebna vrsta značajki, koje bi u većini slučajeva trebale davati dobre rezulate, su one dobivene transformacijama nizova korištenjem postupaka poznatih iz područja obrade znakovnih nizova (string algorithms). Te se značajke dobivaju ne izravno iz ulaznog niza već iz novonastalih struktura dobivenih transformacijom niza. Primjeri takvih struktura su sufiksno polje (suffix array) i stablo LCP intervala (LCP-interval tree). Konstrukcija tih struktura je u suštini kompleksna transformacija niza, kao što je to i srodna Burrows-Wheeler transformacija. Sve te transformacije za rezultat imaju strukture koje odražavaju ali i ističu kakrakteristične osobine ulaznog niza.
U našem istraživanju izdvojena vrsta transformacija je pretvorba niza u jedinstvenu bezkontekstnu gramatiku. Taj se postupak može koristiti u svrhu sažimanja niza, ali on ujedno daje i uvid u hijerarhijsku strukturu ponavljanja u nizu što može dovesti do jedinstvenih značajki. Pri transformaciji niza u gramatiku, u pravilu se teži pronaći najmanju gramatiku koja reproducira niz. Taj problem je NP-težak pa se koriste različite heurističke metode. U pravilu, što je rezultat metode bliži optimumu to je postupak složeniji i sporiji, pa se kao važan problem pojavljuje brzina algoritma. Naša istraživanja su velikim dijelom posvećena ubrzanju postupaka transformacije niza u gramatiku.

O1: Feature extraction. Feature extraction from continuous signals (Month 1-18)

A10.1 I. Michieli: Design of the general framework for feature extraction using discrete wavelet transform of input signals (završeno u studenom 2014.)
Odabrano je više velikih skupova podataka dobivenih mjerenjem na kontinuiranim signalima fizioloških sustava čovjeka (i psa) raspoloživih na web-u (Intracranial EEG (iEEG) data clips - American Epilepsy Society Seizure Prediction Challenge -https://www.kaggle.com/c/seizure-prediction/data ) kao i skupovi podataka dobiveni akcelerometrijskim metodama mjerenja kretanja žvačnog sustava čovjeka u tri okomite ravnine (podaci sa Stomatološkog fakulteta u Zagrebu). Ovi skupovi podataka predstavljaju velike složene višekanalne podatkovne strukture primjerene za razvoj i testiranje općeg okvira za izlučivanje značajki signala upotrebom diskretne wavelet transformacije (DWT)! Prilagodba formata podataka provedena je tako da omogući uvoz u programske pakete "Mathematica" i "MathLab". Izvedeno je testiranje kapaciteta obrade i brzine wavelet transformacije podataka unutar programskih paketa na radnoj stanici Z-230 s 16 GB RAM (i-7 quad procesor) kao i provjera mogućnosti ekstrakcije i manipulacije s koeficijentima transformacije. Nakon podrobne analize odabran je programski paket "Mathematica" zbog veće fleksibilnosti u odabiru i manipulaciji s željenim parametrima! Razvijena je procedura interaktivnog unosa podataka, ispitivanja i prilagodbe veličine skupa podataka te iterativnog biranja tipa transformacije (odabir tipskih wavelet funkcija) za izlučivanje koeficijenata transformacije! DWT je primjenjena nad skupovima podataka različite dužine sve do 3 000 000 točaka signala! Testirani algoritmi su interaktivnog tipa ali ih je moguće posve automatizirati za specifičnu aplikaciju na odabranom skupu ili skupovima podataka!!

A11.1 I. Michieli: Transformation of data through specifically chosen signal related wavelet packets (završeno u prosincu 2014.)
Wavelet Packet Transform (WPT) je poopćenje diskretne wavelet transformacije kojom se postiže veća koncentracija energije signala te na taj način i bolja reprezentacija određenih karakteristika signala kroz dobivene koeficijente transformacije! Kombiniranjem DWT-a i WPT-a u različitim fazama dekompozicije signala moguće je dobiti specifičan skup koeficijenata koji najbolje opisuje određena svojstva signala. Isproban je algoritam iterativne dekompozicije signala tako da izlazni skup koeficijenata transformacije uključuje sve moguće kombinacije po svim nivoima dekompozicije signala! Na taj način se broj izlučenih značajki signala kroz koeficijente DWT i WPT transformacije maksimizira s ciljem obuhvaćanja svih mogućih skrivenih svojstava signala.

A12.1 I. Michieli: Development of iterative procedures for embedding pseudo-phase spaces (završeno u veljači 2015.)
Istraživanje metoda izlučivanja značajki iz kontinuiranih signala nastavljeno je razvojem procedura za primjenu modificirane analize glavnih komponenti sustava (Principal component analysis). Analiza glavnih komponenti pretpostavlja ugradnju vremenske serije (signala) u višedimenzionalni pseudo-fazni prostor gdje se formira strukturni atraktor sustava koji ocrtava njegova osnovna dinamička svojstva! Ovisno o načinu ugradnje mogu se naglasiti različita svojstva sustava i na taj način, primjenom jedne od metoda linearne algebre (PCA, SVD, LDA...), izlučiti one značajke za koje mislimo da će najbolje opisati specifična svojstva signala. Načini ugradnje vremenske serije u pseudo fazni prostor razlikuju se prema odabranoj širini prozora ugradnje („window width“) kao i prema izboru koraka između susjednih točaka signala. Cilj je dobiti maksimalno rašireni prostorni atraktor koji najbolje prezentira dinamičke karakteristike sustava pri čemu se istovremeno filtrira šum koji ih maskira! Razvijeni su algoritmi ugradnje s varijabilnim korakom i širinom prozora. Primjenjeni algoritmi omogućuju, nakon ugradnje, odabir povoljne težinske funkcije kojom se rotiraju glavne osi atraktora u smjeru naglašavanja funkcijskih značajki sustava. Na taj je način pripremna faza ugradnje signala završena i moguće je izlučiti čitav set novih značajki kao što su dimenzionalnost sustava, principalne vrijednosti („singular spectrum“), nelinearne invarijante sustava (fraktalna dimenzija , Korelaciona dimenzija , entropija sustava) i sl. Za verifikaciju metode korišteni su artificijelno generirane serije poznatih 3D fractalnih atraktora (Lorentz, Rösller,...) kao i odabrani podaci intervala hoda iz baze podataka „PhysioBank gait database“ i podaci srčanog ritma iz „PhysioBank interbeat (RR) interval database”.

A13.1 I. Michieli: Extraction of features in the form of singular spectrum and modified principal components. (završeno u lipnju 2015.)
Metoda rastava višedimenzionalnih podataka nekog dinamičkog sustava na glavne funkcionalne komponente (principal component analyses - PCA) se direktno nastavlja na metode ugradnje vremenskih serija u n-dimenzionalni fazni prostor. Rastavom na glavne komponente (svojstvene vrijednosti kovarijantne matrice podataka) podaci se dekoreliraju i prikazuju u projekciji u kojoj su dinamičke karakteristike najviše izražene (maksimalna varijanca podataka)! Na taj je način moguće smanjiti dimenzionalnost matrice podataka zanemarujući projekcije s malom ukupnom varijancom ispod nekog zadanog praga! više ...

A14.1 I. Michieli: Approximate entropy spectrum calculation in selected principal vector spaces of various dimensionalities and associated signal dynamical parameters. (završeno u srpnju 2015.)
Metoda karakterizacije signala pod nazivom „Approximate entropy- (ApEn)“ kao i njena modifikacija pod nazivom „Sample entropy- (SampEn)“ nastala je kao aproksimacija poznate „Kolmogorov“ entropije koja mjeri stupanj kaotičnosti signala nelinearnih dinamičkih sustava (Pincus, 1994; Moody, Peng et. al. 1997; Richman and Randall, 2000.). Metoda omogućuje upotrebu sličnog koncepta na realnim konačnim signalima a posebno na šumnim vremenskim serijama iz fizioloških sustava. Može se reči da ApEn predstavlja statistiku pravilnosti koja procjenjuje stupanj predviđanja fluktuacija u signalu ili drugačije rečeno ona je mjera rasipanja informacije u signalu. Metoda se može direktno primjeniti na atraktore nastale ugradnjom vremenske serije (signala) u pseudo-fazni prostor („delay-time embedding“). Za razliku od Kolmogorovljeve entropije, ApEn definira čitav spektar vrijednosti ApEn(N,m,r), ovisno o odabiru dimenzionalnosti pseudo faznog prostora „m“ i ovisno o veličini okoliša „r“ u nizu oko pojedinih pseudo vektora za koje se ApEn statistika određuje.
U okviru ovog istraživanja ApEn metoda je prilagođena tako da se može primjeniti na pseudo-vektore u koordinatnom sustavu glavnih osi (singular vectors' projection axes). Na ovaj način moguće je, u ovisnosti o iznosu singularnih vrijednosti, procjeniti dominantnu dimenzionalnost dinamičkog sustava te izračunati ApEn spektar u okolišu procjenjene dimenzije „m“ sustava! Za pretpostaviti je da če ovako izračunati ApEn spektar odražavati glavne značajke dinamike signala. Modifikacija ApEn i SampEn proračuna izvedena je u programskom paketu „Mathematica“. Razvijeni algoritam omogućuje ugradnju vremenske serije u pseudo fazni prostor, određivanje singularnih vektora i singularnih vrijednosti te proračun ApEn i SampEn spektra u sustavu glavnih osi projekcije uz slobodan odabir intervala vrijednosti parametara „m“ i „r“ . Proračun je primjenjen na vremensku seriju stiska šake („grip force time series“) dobivenu mjerenjem na pacijentima oboljelim od Reumatoidnog artritisa kao i na kontrolnom uzorku zdravih osoba. Podaci su dobiveni u suradnji s odjelom za reumatske bolesti poliklinike „Dr. Drago Čop“ u Zagrebu! Rezultati proračuna pokazali su visoku koreliranost dobivenih vrijednosti ApEn i SampEn spektra sa stupnjem oboljenja ispitanika!

O1: Feature extraction. Combinations of events in multi-channel sets of synchronized sequences (Month 13-18)

A16.1 I. Michieli: Functional merging of related signal vector variables from different synchronized signal levels. (završeno u prosincu 2015.) Višekanalne podatkovne strukture predstavljaju najčešći oblik signala iz realnog svijeta proizvedene složenim mjernim tehnologijama čije je zajedničko obilježje vremenski sinhronizirano prikupljanje podataka na jednoj ili više karakterističnih funkcionalnih točaka složenog sustava. U to smislu može se govoriti o prostorno sinhroniziranim ili prostorno distribuiranim višekanalnim podacima. Isto tako mjerni podaci mogu predstavljati iste ili različite skalarne ili vektorske veličine. Višekanalne sekvence signala sadrže kvaliteniju podatkovnu bazu za analizu sustava koji se istražuje uz prisutnost određenog stupnja redundancije dinamičkih svojstava pogotovo ako se mjere iste fizikalne veličine. Izlučivanje značajki sustava za ovako široku lepezu višekanalnih podataka obuhvača niz posve različitih matematičkih metoda i postupaka.
Za ovo istraživanje odabrani su podaci dobiveni akcelerometrijskom metodom mjerenja kretnji žvačnog sustava čovjeka. Ove podatke možemo opisati kao višekanalne sekvence istih fizikalnih vektorskih veličina sinhronizirane u vremenu i prostoru jer opisuju ubrzanje kretanja čeljusti u tri okomite ravnine u jednoj mjernoj točci (vrh brade) i to za tri različita položaja glave. Mjerenje je obuhvatilo 20 ciklusa otvaranja i zatvaranja usta za svaki od tri položaja glave na 78 zdravih ispitanika. Dio ove podatkovne baze ustupljen nam je sa Stomatološkog fakulteta u Zagrebu.
Kod ovakvih podataka broj kanala ujedno predstavlja i broj stupnjeva slobode ili dimenzionalnost sustava. Za istraživanje su slučajnim odabirom preuzeti podaci 10 ispitanika. U programskom paketu „Mathematica“ kreiran je vektorski parametarski prikaz atraktora sustava za sva tri položaja glave u realnom faznom prostoru višekanalnih varijabli. Primjena ranije adaptiranih algoritama za izlučivanja glavnih komponenti sustava (PCA) kao i za proračun približnog entropijskog spektra (APN) na ovako pripremljene podatke je izravna! Pored gore opisanog pristupa provedena je i višedimenzionalna analiza spajanja signala odabranim vektorskim kombiniranjem dijelova ili cijelih sinhroniziranih sekvenci pojedinih kanala signala. Razvidno je da se različitim odabirom višekanalnih komponenti mogu istaknuti posve određene značajke signala kao temelj za efikasnije izlučivanje željenih funkcionalnih parametara.

A17.1 I. Michieli: Construction of characteristic time dependent joined signal patterns suitable for further feature extraction analyses. (završeno u siječnju 2016.)
Nastavak analize obuhvatio je izbor odgovarajućeg kompozitnog vremenskog signala nastalog vektorskom kombinacijom njegovih višekanalnih komponenti za koji se pretpostavilo da će najbolje istaknuti tražene značajke sustava. Kriterij za odabir određen je preko diskretne wavelet analize (DWT) kroz novo razvijeni iteracijski algoritam! Na odabranom uzorku izabranih signala provedena je DWT analiza za pojedine kanale kao i za module svih kombinacija vektorskih suma komponenti signala i odabrana je ona kombinacija za koju je sadržaj energije koeficijenata transformacije trenda signala u odnosu na ukupnu energiju signala največi.
Analiza je provedena upotrebom više wavelet filtera (Haar, Daubechies, Coiflets). Ovdje treba istaknuti da je Coiflet familija filtera posebno dizajnirana da što vjernije preslikava vrijednosti signala na vrijednosti trenda wavelet transformacije. Rezultati su pokazali da „Daub4“ i „Coif6“ filteri najbolje kompaktiraju energiju signala što naravno ovisi o frekvenciji uzorkovanja kao i o frekvencijskom sadržaju signala.

A18.1 I. Michieli: Implementation of developed feature extraction algorithms on selected multi-channel event patterns. (završeno u veljači 2016.)
U završnoj fazi istraživanja provedena je obrada odabranih višekanalnih signala ranije razvijenim ili modificiranim metodama izlučivanja značajki. Singularni spektar razvijenog atraktora u realnom faznom prostoru kao i približni entropijski spektar pokazali su donekle primjetne razlike u formi spektra za sva tri tipa signala (tri različita položaja glave ispitanika). Ove razlike moguće je kvantificirati standardnim statističkim metodama.
Primjenom diskretne wavelet analize izlučene su značajke na kombiniranim višekanalnim signalima. Kao kriterij izbora slaganja komponenti signala izabran je stupanj kompresije energije prvog nivoa wavelet transformacije. Na ovaj način osigurava se odabir kvalitetnog seta značajki sa stanovišta razlučivanja vrste signala. Jednostavnom algebarskom manipulacijom wavelet koeficijenata prva 2 nivoa transformacije (suma kvadrata) pokazane su izrazite razlike između signala različitih položaja glave. Detaljna kvantifikacija razlika može se verificirati upotrebom standardnih statističkih metoda kao što su linearna regresije ili diskriminantna analiza na odabranim kombinacijama izlučenih wavelet koeficijenata prvih nekoliko nivoa transformacije.

O1: Feature extraction. Feature extraction from network data (Month 18-23)

A19.1 D. Gamberger: Construction of features for inference on networks. (završeno u travnju 2016.)
Bez obzira kako izgleda originalni problem, za primjenu tehnika strojnog učenja potrebno je originalni problem transformirati u skup primjera koji su opisani skupom atributa (značajki). Porastom značaja sociajalnih mreža, porastao je i interes za analizom podataka koji su strukturirani kao mreže. Bitna karakteristika socijalnih mreža su veličina i relativno slaba povezanost. Zbog toga se takove mreže tipično rješavaju postupcima otkrivanja centralnosti pojedinih čvorova odnosno otkrivanjem izoliranih podgrupa. Osim socijalnih mreža postoje mrežno strukturirani podaci i u drugim područima. Primjeri su mreža banaka koje su povezane i s obzirom na vlasničku strukturu i međusobne pozajmice odnosno garancije, mreža trgovačkih društava, ekonomsko-političko-geografska mreža država i mreža regulacije gena u organizmu. Tip podataka i tip veza u spomenutim područjima je vrlo različit. Zajedničko im je samo to da postoje podaci o čvorovima i podaci o vezama među njima iz čega proizlazi potreba da se ti podaci transformiraju u oblik koji mogu prihvatiti postupci strojnog učenja. Primjenom tih postupaka moguće je otkrivanje izuzetaka, grupa sličnih čvorova i otkrivanje značajnih veza. Cilj rada je definiranje i izgradnja okvira analize mreža koji će biti univerzalan bez obzira na domenu u kojoj je mreža definirana.

A20.1 D. Gamberger: Testing and interpretation of network features. (završeno u srpnju 2016.)
U postupku razvoja ustanovljeno je postojanje četiri osnovnih tipova mreža (nepovezane, slabo povezan, jako povezane, potpuno povezane) te četiri vrste vrijednosti veza (A-D) koje imaju bitan utjecaja na način konstrukcije značajki. Iako su tipovi mreža i veza definirani općenito, tek korištenje sustava treba pokazati eventualno potrebu za uvođenjem i dodatnih relevantnih podskupina. U procesu razvoja ukazala se mogućnost za većom i manjom detaljnosti pri konstrukciji značajki. U ovoj fazi istraživanja nije moguće definirati univerzalno primjenjiv pristup koji će biti prihvatljiv za sve primjene. Zbog toga je postupak realiziran modularno sa mogućnošću utjecaja korisnika na konačni rezultat te sa mogućnošću nadogradnje sustava. Posebna pažnja je posvećena izgradnji modula koji konstruiraju značajke za osnovne slučajeve a koji se onda mogu iterativno i u kombinacijama koristiti i za složenije tipove veza. više ... .

O2: Ensembles of rules. Evaluation of existing algorithms for outlier detection and clustering (Month 1)

A1.2 D. Gamberger: Evaluation of existing algorithms (završeno u rujnu 2014.)
Postupci strojnog učenja vrlo su osjetljivi na šum u skupu podataka. Šuu uključuje greške i izuzetke. Posebna pažnja pri konstrukciji prediktivnih modela posvećuje se izbjegavanju preprilagodjenja podacima koji uključuju šum. Za postupke otkrivanja znanja bitno je eksplicitno detektiranje šumnih primjera. Oni predstavljaju sam po sebi važan rezultat bilo radi otkrivanja uzroka grešaka bilo radi razumijevanja karakteristika izuzetaka.

Suvremeni postupci detekcije koriste glasanje više modela za donošenje odluke o postojanju šuma. Vidi Ensemble-based noise detection: noise ranking and visual performance evaluation. U ovom projektu primijeni ćemo postupak glasanja velikog broja modela (više tisuča pravila). Kao šumni primjeri bit će izdvojeni oni primjeri za koje je modelima predvidjena klasa bitno drugačija od one koja im je trenutno pridružena.

Klasteriranje primjera je najvažnija tehnika strojnog učenja za neklasificirane primjere. Poznati postupci su zasnovani na primjenama tehnike mjerenja udaljenosti medju primjerima. Osnovni problem je odabir prikladne mjere udaljenosti. Vidi Data Clustering: Theory, Algorithms, and Applications. Dodatno je problem odabir broja klastera u koji će se primjeri grupirati. Trenutno se taj broj najčešče odredjuje na osnovi iskustva ili očekivanja korisnika rezultata.

Suvremeni postupci klasteriranja koriste informacije iz više nezavisnih skupova atributa za postizanje pouzdanijih rezultata grupiranja. Vidi A survey of multi-view machine learning i From black and white to full color:extending redescription mining outside the Boolean world. U ovom projektu realizirati i evaluirati ćemo potpuno nov pristup zasnovan na sličnosti primjera koja je odredjena brojem modela (pravila) koja istovremeno pokrivaju par primjera. Za generiranje modela koristiti ćemo postupak klasificiranja primjera preko velikog skupa pravila. Klasifikacijski problem će se stvoriti tako da će pozitivnu klasu tvoriti raspoloživi neklasificirani primjeri a negativnu klasu će tvoriti ti isti primjeri ali sa slučajno izmjenjenim vrijednostima atributa.

O2: Ensembles of rules. Development and implementation of an algorithm for construction of ensembles of rules (Month 2-12)

A2.2 D. Gamberger: Prototype development (završeno u studenom 2014.)
Razvijen je novi algoritam za konstrukciju potencijalno velikog skupa pravila za razlikovanje primjera u različitim klasama. Centralni dio iterativno gradi jedno po jedno pravilo i to dotle dok svaki od primjera nije pokriven sa barem P pravila, P je konstanta koja je unaprijed odredjena ili je odredjena tijekom izvodjenja na osnovi procijenjene prediktivne točnosti.

Pojedino pravilo se gradi tako da se pronadje primjer koji je do tada pokriven najmanji broj puta. Klasa kojoj pripada odabrani primjer je pozitivna klasa a sve ostale klase su negativne. S ciljem dizerfikacije pravila, kvaliteta pravila se odredjuje na slučajnom podskupu svih primjera a mogu se koristiti samo neki od raspoloživih atributa. Konstrurano pravilo mora pokrivati odabrani primjer, te čim veći broj drugih primjera pozitivne klase, a niti jedan od primjera negativne klase.

Pojedino pravilo se gradi tako da se iterativno dodaju uvjeti koji eliminiraju pokrivanje negativnih primjera. Uvjet se konstruira tako da se pronadje jedan pokriveni negativni primjer te atribut koji može razlikovati odabrani pozitivni primjer od tog negativnog primjera. Taj atribut se koristi za konstrukciju uvjeta. U svakoj iteraciji se konstruiraju barem dva uvjeta a za uvrštavanje u pravilo odabire onaj koji ima najbolje pokrivanje pozitivnih primjera i najbolju eliminaciju negativnih primjera. Proces dodavanja uvjeta završava kada pravilo ne pokriva niti jedan negativni primjer.

Realizirani sustav prihvaća skupove podataka sa do 1000 primjera klasificiranih u do 10 klasa. Primjeri mogu biti opisani sa do 100 atributa koji mogu biti numerički i nominalni.


A3.2 D. Gamberger: First useful version (završeno u veljači 2015.)
Napravljen je program za generiranje skupa slučajnih pravila pod nazivom RandomRules (RR). Program je namijenjen rješavanju klasifikacijskih problema sa više klasa u kojem su primjeri opisani sa numeričkim i kategoričkim atributima koji mogu uključivati i nepoznate vrijednosti. Na osnovi generiranih pravila program može predvidjeti klasu neklasificiranih primjera. Realizirani program uključuje sve osnovne dijelove za generiranje pravila i predviđanje klase. Razvoj je napravljen sa ciljem postizanja visoke prediktivne točnosti. Pojedina pravila se međusobno moraju što više razlikovati da bi se u konačnici pristupom većinskog glasanja dobila dobra točnost. Zbog toga svako pravilo zasebno ne treba i ne može imati dobru prediktivnu točnost već samo točnost koja je sistematski bolja od slučajne točnosti. Za svaku realnu primjenu generira se od tisuću do milion pravila. Pravila nije potrebno pamtiti jer se klasifikacija radi istovremeno sa generiranjem pravila.

Činjenica da svako zasebno pravilo ne treba imati visoku točnost ni veliko pokrivanje primjera, omogućuje da se koriste postupci generiranja koji su vrlo jednostavni. A to omogućuje da se odaberu oni postupci koji se mogu izvoditi brzo pod uvjetom da osiguravaju raznolikost generiranih pravila. U razvoju je testirano nekoliko mogućih pristupa a u prvoj realiziranoj verziji je odabrano rješenje koje se činilo najbolje s obzirom na prediktivnu točnost postignutu na nekoliko testnih zadataka. U realizirani program uključen je cijeli niz parametara s ciljem da se kroz sistematsku evaluaciju omogući otkrivanje optimalne strukture programa i vrijednost nekih konstanti. Osnovne dileme su broj uvjeta koji se testiraju u svakoj iteraciji izgradnje pravila te kako se mjeri kvaliteta pokrivenosti primjera skupa za učenje, odnosno kako se odlučuje koji će se primjer odabrati kao polazna točka za slijedeće pravilo.

A4.2 D. Gamberger: Tests and iterative improvement of the algorithm for construction of ensembles of rules (završeno u travnju 2015.)
Cilj testiranja je bio postizanje da postupak bude primjenjiv na vrlo različitim skupovima podataka. Testiranja su rađena na nuričkim i kategoričkim skupovima, te na njihovim kombinacijama. Korišten je javno dostupni skup podataka sa UCI repositorija i to domene: glass, car i tic-tac-toe. U procesu testirnja otkriven je cijeli niz problema posebno vezano na format podataka te na prisustvo ekstremno malih vrijednosti. Ti su problemi odmah djelomično ili u potpunosti riješeni. Idetificiran je i problem hrvatskih slova u imenima atributa i kategoričkih vrijednosti ali je odlučeno da će realizacija biti do daljnjega ograničena na engleski alfabet.

Rezultat testiranja je da je prva verzija znatno poboljšana prvenstveno u smislu prihvaćanja ulaznih podataka. Trenutna verzija je spremna za prva testiranja prediktivne točnosti.

A5.2 M. Piškorec: Evaluation on synthetic data (završeno u svibnju 2015.)
Napravljen je program za genererianje skupova podataka u kojima se može birati izmedju nekoliko tipova ovisnosti ciljne varijable i aributa. Program omogućuje generiranje skupova podataka sa različim brojem primjera i brojem atributa. Uz pomoć ovog programa generirana su tri skupa testnih podataka, u prvom (F1) je ovisnost ciljne varaijable relativno jednostavna, u drugom je vrlo složena (F2) a u tećem je potpuno slučajna (R1). Za svaki od tih tipova generirano je po 16 skupova primjera različite veličine, broj primjera je variran izmedju 350 i 10000 a broj atributa izmedju 35 i 1000. Na generiranim podacima mjerena je prediktivna točnost i brzi izvodjenja za dvije verzije implementiranog sustava za generiranje pravila (sa automatskim odredjivanjem brojem pravila i fiksnim brojem pravila) te sa PARF implementaciom Random Forest algoritma. Rezultati su prikazani u cjelovitom izvješću. Analizom rezultata je ustanovljena zadovoljavajuća stabilnosost i ponašanje realiziranog postupka ali su ustanovljeni i neki bitni problemi vezani na verziju sa automatskim odredjivanjem broja generiranih pravila. U daljem radu će se pažnja morati posvetiti otklanjanju uočenih problema.

A6.2 M. Piškorec: Evaluation on publicly available data (završeno u lipnju 2015.)
Testiranje primjenjivosti razvijenog postupka na realnim skupovima podataka napravljeno je uz pomoć OpenML (http://www.openml.org/) web platforme koja je razvijena na Sveučilištu Leiden, Nizozemska. Ova platforma uključuje velik broj realnih skupova podataka te omogućuje direktnu usporedbu rezultata dobivenih raznim postupcima strojnog učenja. Za potrebe evaluacije, na platformu je poslana prva stabilna verzija RendomRules postupka i to njena osnovna ("default") verzija čije izvodjenje ne zahtijeva podešavanje niti jednog parametra (broj generiranih pravila se odredjuje automatski). Na http://www.openml.org/f/707 su prediktivni rezultati postignuti na otprilike 50 skupova podataka. Odlaskom na odgovarajući skup podataka i klasifikacijski zadatak moguće je dobiti uvid u komparativne rezultate sa drugim već testiranim postupcima.

Iz rezultata je vidljivo a) da je nezavisno testiranje pokazalo stabilnost razvijenog postupka (uspješno je napravljen klasifikacijski postupak na svim testiranim skupovima podataka), b) postugnuta je zadovoljavajuća prediktivna točnost koja je tipično bolja nego što se postiže nekim standardnim postupcima (JRip, J48, REPTree), c) demonstrirana je zavidna brzina izvodjenja (koja nije dokumentirana zbog trenutnih ograničenja platforme).
Complete report (pripremio Jan van Rijn, Leiden University, Nizozemska).

A7.2 D. Gamberger and M. Piškorec: Implementaion of a public service (završeno u kolovozu 2015.)
Random Rules.

O2: Ensembles of rules. Implementation of an outlier detection algorithm based on ensembles of rules (Month 13-18)

A8.2 D. Gamberger: Implementation of the outlier detection procedure (završeno u listopadu 2015.)
Otkrivanje izuzetaka je postupak eksplicitne identifikacije onih primjera koji ne slijede logiku većine primjera u skupu za učenje. Po svojem rezultatu je komplementaran postupku otkrivanja grupa primjera jer nema za cilj otkrivanje općih značajki koje karakteriziraju (velike) grupe već predstavlja selekciju (malog) skupa primjera koji bitno razlikuju od ostalih primjera. Zadatak otkrivanja izuzetaka može se definirati u kontekstu klasificiranih i neklasificiranih primjera. U klasificiranoj domeni je izuzetak definiran kao bitno odstupanje od općenite logike povezanosti vrijednosti atributa i klase pridružene tom primjeru a u neklasificiranoj domeni kao neuklapanje u niti jednu homogenu grupu primjera.
Postojanje izuzetaka u podacima može imati dva osnovna uzroka. Prvi je postojanje pogrešaka bilo koje vrste, napr. pri sakupljanju podataka, transformaciji podataka ili pripremi za primjenu strojnog učenja. Drugi uzrok je da su to primjera koji su točni primjeri koji ne slijede logiku većine primjera. Izuzetne vrijednosti u podacima mogu biti u vrijednostima pojedinih atributa i u klasifikaciji primjera. Prvi tip je manje opasan jer može imati utjecaja na klasifikaciju primjera samo kada se koristi upravo određeni atribut čija vrijednost je ili pogrešna ili izuzetna. Izuzetak u klasifikaciji je opasan jer takav primjer pri svim odlukama o izgradnji pravila u kojima sudjeluje sugerira pogrešnu odluku o klasifikaciji. Kada se govori o detekciji i eliminaciji izuzetak u podacima onda se prvenstveno misli na izuzetke u klasifikaciji.
Cilj postupaka za otkrivanje izuzetaka je da se eksplicitno navedu primjeri za koje se smatra da su izuzeci. Zadatak korisnika je da analizom tih primjera zaključi da li se radi o greškama ili stvarnim izuzetcima.
Algoritam je implementiran tako da se za vrijeme izgradnje velikog skupa pravila za svako generirano pravilo zapamte njegove predikcije na primjerima koji nisu korišteni u odlukama o izgradnji konkretnog pravila ("out-of-bag" examples). Nakon završetka izgradnje svih pravila, za svaki primjer se radi predikcija na osnovi glasanja svih pravila na principu nadglasavanja. Ovakva procjena klase primjera se smatra pouzdanom jer je svaki glas dobiven na skupu primjera koji je nezavisan od skupa za učenje i jer je dobiven nadglasavanjem velikog broja nezavisnih pravila. Ova procjena se u postupku učenja skupa praavila koristi za izračunavanje prediktivne točnosti skupa generiranih pravila te se u automtaskom režimu rada dalji proces konstrukcije pravila zaustavlja kada se njegova vrijednost stabilizira.
Kao izuzetci se smatraju oni primjeri za koje je odluka glasanjem drugačija od originalne klasifikacije tog primjera. Za svaki pojedini primjer može se usporediti broj glasova koje je dobila pojedina klasa. Što je razlika između broja glasova za "krivu" klasu i originalnu klasu primjera veća, smatra se i da je veća vjerojatnost da je taj primjer i stvarno "izuzetan". Svi izuzeci se sortiraju po iznosu te razlike te se sortirana lista prikazuje korisniku. Za svaki takav primjer moguće je korisniku i sugerirati klasu u kojoj bi se takav primjer stvarno trebao nalazati: to je klasa koja je dobila najveći broj glasova.

A9.2 D. Gamberger: Tests and iterative improvement of the algorithm (završeno u veljači 2016.)
Postupak je testiran i pobolšavan koristeći javno dostupne skupove podataka na UCI Machine Learning Repository: Data Sets.

A10.2 M. Piškorec: Evaluation of the outlier detection algorithm based on ensembles of rules (završeno u veljači 2016.)
Evaluaciju implementiranog postupka smo izvršili na dva načina. U prvom smo testirali sposobnost detekcije krive klase primjera i to tako da smo određenom broju primjera namjerno promijenili pridruženu klasu. U drugom smo testirali sposobnost detekcije slučajno generiranih primjera tako da smo generirali određeni broj novih primjera slučajnim odabirom i vrijednosti atributa i vrijednosti klase koristeći vrijednosti koje se pojavljuju u stvarnim primjerima.
Testiranje je izvršeno na pet javno dostupnih domena na OpenML platformi (www.openml.org). Odabrani su skupovi podataka sa velikim brojem atributa (do preko 22.000 atributa) i različitim brojem primjera (96-3468). Prva domena (D1) je prepoznavanje rukom pisanih znamenki a preostalih četiri (D2-D5) su skupovi podataka ekspresije gena. više ...

A11.2 D. Gamberger and M. Piškorec: Public web service of the outlier detection algorithm based on ensembles of rules (završeno u ožujku 2016.)
Random Rules.

O2: Ensembles of rules. Implementation of a clustering algorithm based on ensembles of rules (Month 19-24)

A12.2 D. Gamberger: Implementation of a clustering algorithm based on ensembles of rules (završeno u svibnju 2016.)
Primjena nadziranog učenja velikog broja klasifikatora može pomoći u klasteriranju neklasificiranih primjera tako da se objektivno i univerzalno procijeni sličnost primjera. To je pokazano već na primjeru korištenja Random Forest postupka. Ideja je da se problem nenadziranog učenja pretvori u umjetno pripremljeni klasifikacijski problem na kojem se može izvesti standardni postupak indukcije a njegov rezultat se iskoristi za otkrivanje sličnosti primjera. Da bi procjena sličnosti primjera bila kvalitetna potreban je sustav efikasne konstrukcije velikog broja različitih klasifikatora. Za to je postupak indukcije pravila vrlo pogodan jer je tipično potrebno generirati 10.000 do 100.000 pravila za domene koje mogu u realnim slučajevima imati i tisuće primjera i tisuće atributa.
Umjetni klasifikacijski problem se tvori tako da se svi primjeri koje treba klasterirati proglase primjerima pozitivne klase a da se negativna klasa generira slučajno. Rezultat je klasifikacijski problem sa 2*N primjera (N je broj primjera koji se klasteriraju) koji je karakterističan po tome da za svaki atribut vrijedi da su vrijednosti u pozitivnim primjerima identične onima u negativnim primjerima te da je čak i distribucija tih vrijednosti identična. Jedina razlika između pozitivnih i negativnih primjera je da je u negativnim primjerima randomizirana logička povezanost između vrijednosti raznih atributa.
U slučaju primjene indukcije pravila na umjetno konstruiranom klasifikacijskom problemu to znači da pokrivenost pozitivnih primjera istim pravilom sugerira i sličnost originalnih primjera koje treba klasterirati. Statistikom pokrivenosti primjera vrlo velikim brojem vrlo različitih pravila dobiva se procjena sličnosti koja se može iskoristiti za klasteriranje. Rezultat određivanja sličnosti primjera korištenjem indukcije na umjetno generiranom klasifikacijskom problemu je matrica sličnosti. To je N x N matrica sa vrijednostima 0.0 - 1.0. Veća vrijednost označava veću sličnost para primjera koji odgovaraju retku odnosno stupcu matrice. Matrica je simetrična. Na dijagonali je relativna vrijednost pokrivenosti odgovarajućeg primjera sa ukupnim brojem pravila.
Matrica sličnosti je početna točka novog postupka klasteriranja. Grupiranje se vrši tako se smanjuje varijabilnost sličnosti unutar i izvan grupe. Svako spajanje primjera mora smanjiti ukupnu varijabilnost te kada to nije moguće, grupiranje prestaje. Za tu namjenu uvodi se numerička veličina CRV (Clustering Related Variability) koja se računa za svaki primjer posebno na osnovi vrijednosti iz tablice sličnosti. Iako su vrijednosti u tablici konstante, CRV je promjenjiva veličina čija vrijednost ovisi o primjerima sa kojima je određeni primjer grupiran. CRVi za primjer i se računa kao suma varijabilnosti u grupi (CRVi,in) i izvan grupe (CRVi,out).

A13.2 D. Gamberger: Comparative evaluation with other clustering algorithms (završeno u kolovozu 2016.)
Osnovni karakteristika klasteriranja je nepostojanje jedinstvenog rješenja. U skupovima podataka sa mnogo atributa lako je zamisliti da se isti primjeri mogu grupirati na više načina ovisno koji atributi se koriste kao osnova grupiranja. Na primjer, u medicinskoj domeni korisnik zainteresiran za podvrste leukemije očekuje da se podaci o pacijentima sa kojima raspolaže grupiraju ovisno o ALL i AML dijagnozi (akutna limfoblastična ili akutna mijeloidna leukemija). Ali moguće je da će postupak klasteriranja identificirati grupe pacijenata ovisno o spolu (muški i ženski), odnosno o stupnju uznapredovalosti bolesti (početni stadij, ponovna pojava, kronična limfocitna leukemija). Sa stanovišta analize podataka sva ova različita rješenja su korektna a način sakupljanja i pripreme podataka može presuditi koje će rješenje postupak klasteriranja odabrati kao optimalno. A to „optimalno“ rješenje ne mora biti ono koje u biti zanima korisnika analize podataka.
Za praktičnu primjenu klasteriranja je zbog toga važno omogućiti korisniku odabir rješenja koja odgovara njegovim očekivanjima, odnosno rješenje koje ima dobru ekspertnu potporu ili je predmet njegova interesa. Sa tim ciljem razvijen je postupak istraživačkog klasteriranja koji dostupan kao javni web servis. Taj servis omogućuje usporedbu dobivenih rješenja sa nekom poznatom klasifikacijom primjera te omogućuje da korisnik sam odluči o optimalnom broju klastera odnosno da od postupka zatraži novo klasteriranje koje neće u obzir uzeti najznačniji atribut u prethodnom rješenju. Korištenjem tog servisa rezultat klasteriranja je uspoređen sa više poznatih klasifikacija primjera a rezulatati su iskorišteni za iterativno poboljšanje samog postupka klasteriranja.

A14.4 D. Gamberger and M. Piškorec: Public web service of the outlier detection algorithm based on ensembles of rules (završeno u kolovozu 2016.)
Exploratory Clustering.

O3: Hardware implementation. Implementation of interface between FPGA and software realization of machine learning algorithms (Month 1-7)

A1.3 P. Škoda and D. Gamberger: Procedural analysis of machine learning procedures (završeno u studenom 2014.)
Cilj provedene analize postupaka strojnog učenja je skupiti saznanja o značajkama koje će pomoći u odabiru najboljih kandidata za njihovu realizaciju u sklopovlju. U tu svrhu analizirana su tri algoritma koja spadaju među najvažnije algoritme u strojnom učenju/dubinskoj analizi podataka:

Svaki algoritam obrađen je teoretski, te je pregledana po jedna programska implementacija algoritma. Posebna pozornost posvećena je ponašanju algoritma i njegove implementacije pri obradi velikih skupova podataka. Razlog tome je da zbog troškova komunikacije između programa i FPGA sklopovlja, što je već dokazano u dosadašnjim istraživanjima, za male skupove nema dobitka u vremenu izvođenja programa/algoritma. Iz provedene analize navedeni su zaključci o računarsko/vremenski najintenzivnijim procesima u navedenim algoritmima, te sličnostima i razlikama tih procesa. više ...

A2.3 B. Medved Rogina: Procurement of software tools (Xiling Vivado System Edition) (završeno u siječnju 2015.)
Maxeler Vectis, te ostali razmatrani akceleratori temeljeni su na Xilinx FPGA sklopovlju, iz tog je razloga je za njihovo korištenje nužno nabaviti i Xilinx razvojne alate. Xilinx razvojni alati namijeni su prevođenju definicije sklopovlja napisanoj u VHDL-u ili Verilogu u binarnu datoteku za programiranje FPGA sklopa. Alati te vrste dostupni su samo od proizvođača FPGA sklopovlja i ne postoje open source ili besplatna rješenja.

Za korištenje Maxeler razvojnih alata potreban je Xilinx ISE, verzija 13.3. Sam program moguće je "skinuti" izravno s Xilinxove web stranice (uz prethodnu registraciju), no potrebno je kupiti licencu koja omogućuje njegovo korištenje. Nije potrebno kupiti licencu za specifičnu verziju. Vremensko trajanje licence je neogranićeno, no postoji ograničenje s obzirom na (najnoviju) verziju koja se može koristiti. više ...

A3.3 P. Škoda and D. Gamberger: Specification of the routines that are potential candidates for implementation in hardware (završeno u siječnju 2015.)
Ranije provedena analiza algoritama iz strojnog učenja pokazala je da ima malo preklapanja u osnovnim rutinama između različitih algoritama. Stoga su za ovu fazu projekta specificirane rutine ciljano za algoritam za učenje pravila koji se razvija u sklopu ovog projekta. Rutine koje će se probno paralelizirati, te ocijeniti pogodnost za izvedbu u FPGA sklopovlju su: 1. Construct feature – rutina za konstrukciju značajke (feature). Za odabrani pozitivni primjer i odabrani negativni primjer koji još nije eliminairan ispituje se kvaliteta pojedinog atributa kao podloge za izgradnju značajke koja zadovljava pozitivni a eliminira negativni primjer. Moguće je ispitivanje više atributa istovremeno. 2. Count coverage – rutina za ocjenu kvantitete pojedine značajke pos svim primjerima u skupu za učenje. Moguće je provoditi ocjenu za više značajki istovremeno. 3. Compute confusion matrix – rutina za ocjenu kvalitete naučenog pravila u smislu ispravnosti klasifikacije. Tu je moguće ispitati bar dva pristupa paralelizaciji: više različitih pravila istovremeno, te više značajki istog pravila istovremeno. 4. Update oob matrix – rutina za ažuriranje out-of-bag matrice te istovremenu klasifikaciju testnih primjera.

A4.3 P. Škoda: Evaluation of usefulness and correctness of the selected routines in software (završeno u ožujku 2015.)
Analizirane su rutine koje su u prijašnjim aktivnostima projekta identificirane kao kandidati za izvedbu u FPGA sklopovlju. Tri rutine (Construct feature, Count coverage i Update oob matrix) paralelizirane su pomoću OpenMP, te je provedeno ispitivanje utjecaja paralelizacije na vrijeme izvršavanja algoritma za učenje pravila (rule learning). Preostala rutina (Compute confusion matrix) nije dalje analizirana zbog premalog udjela u vremenu izvršavanja algoritma. Najizgledniji kandidat za izvedbu u FPGA sklopovlju je rutina Construct feature, čija je paralelizacija polučila dobar rezultat (ubrzanje konstrukcije jednog pravila do 4,146× na 6 dretvi). više ...

O3: Hardware implementation. Implementation of basic rule learning procedures in hardware (Month 8-15)

A5.3 P. Škoda and D. Gamberger: Selection of the set of procedures for implementation in hardware (završeno u lipnju 2015.)
Analizirana je rutina Construct feature, i njena podrutina Count coverage, koja je probnom paralelizacijom u softveru identificirana kao najizgledniji kandidat za izvedbu u sklopovlju. Uz nju u analizu su uključene i tri dodatne rutine – Eliminate covered, Update total coverage i Update OOB matrix – koje bi kao ulaz (i izlaz) imale podatke pohranjene u memoriji spojenoj na FPGA. Iz ulaznih i izlaznih parametara rutina, te operacija koje se izvršavaju nad podacima, specificirane su tri procedure koje će se implementirati u sklopovlju prema modelu podatkovnog toka: Count conditional, Increment conditional i Logic simple. Navedene procedure zajedno pokrivaju sve operacije koje se vrše nad podacima u analiziranim rutinama (prebrojavanje, uvećavanje za 1, logička funkcija, usporedba, itd.), te će se njihovim povezivanjem u sklopovlju replicirati rad svake analizirane rutine. više ...

A6.3 P. Škoda and B. Medved Rogina: Implementation in hardware (završeno u rujnu 2015.)
Tri jezgre (engl. kernel) specificirane u A5.3 implementirane su u sklopovlju. Specifikacije jezgara nadopunjene su detaljima koji pokrivaju konkretne primjene.
Sve opisane jezgre izvedene su pomoću MaxJ API-ja. Glavne funkcionalnosti jezgara izvedene su na način koji omogućuje njihovo kasnije kombiniranje u kompozitne jezgre. Za svaku jezgru implementirana je softverska referenca. Jezgre su preliminarno ispitane na ispravnost ne uzimajući u obzir rubne slučajeve. više ...

A7.3 P. Škoda: Evaluation of performance, comparison with pure SW implementations (završeno u studenom 2015.)
Za svaku jezgru, implementirana je softverska referenca koja se izvršava na CPU. Referentna implementacija služi za ispitivanje ispravnosti rezultata, te za usporedbu brzine izvršavanja.
Definirana su i izvedena dva ispitna programa (eng. test-bench): Functional test-bench izvodi izvršavanje softverske reference, izvršavanje jezgre na predefiniranim sintetskim skupovima, te usporedbu njihovih rezultata. Sintetski skupovi pokrivaju rubne slučajeve (engl. corner cases) relevantne za pojedine primjene jezgri, te slučajno generirane ulaze kojima se ispituje opći rad jezgri. U ovom ispitnom programu bitna je samo ispravnost rezultata dobivenih iz jezgri.
Performance test-bench izvodi mjerenje vremena pri izvršavanju softverske reference, te pri izvršavanju jezgri. Ispravnost rezultata ne provjerava se, već se podrazumijeva. Ispitni skupovi za jezgre u sklopovlju nalaze se u memoriji spojenoj na FPGA, te se također rezultati upisuju u istu memoriju. Model korištenja jezgre predviđa da se skup za učenje učitava u memoriju FPGA samo jednom, na početku programa. Stoga se vrijeme potrebno za prijenos skupova iz glavne memorije računala u memoriju FPGA isključuje iz usporedbe. Vrijeme prijenosa mjeri se i iskazuje posebno.
Veličine ispitnih skupova (broj elemenata) su u nizu od 2.000 do 100.000.000. Za ispitivanje se koriste slučajno generirani skupovi, generirani na početku izvršavanja programa. više ...

O3: Hardware implementation. Development of heterogeneous framework system (Month 13-15)

A8.3 B. Medved Rogina: Procurement of workstation and FPGA board (Maxeler Vectis) (završeno u studenom 2015.)
U fazi pripreme i predlaganja projekta u okviru druge godine trajanja projekta planirana je nabavka jedne radne stanice (12.000 kn), odgovarajućeg medija za pohranu podataka (engl. datastorage) (6.000 kn) i Maxeler Vectis-Lite FPGA kartice (24.000 kn). U skladu s time u financijskom planu projekta iskazani i planirani troškovi za nabavku i konfiguriranje tzv. heterogenog računalnog sustava temeljenog na Maxeler Vectis-Lite FPGA-u (engl. Field Programmable Gate Array).
Kao optimalnu konfiguraciju za radnu stanicu predlažemo radnu stanicu prema ponudi dobavljača S&T Hrvatska AG16-0108v2, no detaljan odabir definirat ćemo nakon kupnje Maxeler FPGA kartice. Planirana sredstva dostatna su za nabavku optimalnog rješenja s obzirom na zahtjeve i složenost rada na projektu. više ...

A9.3 P. Škoda, B. Medved Rogina: Installation (HW and SW tools), testing and deployment of the system (završeno u studenom 2015.)
Radna stanica i FPGA kartica:
Na HP Z440 radnu stanicu instaliran je CentOS 6.8 Linux operativni sustav. U računalo je ugrađena FPGA kartica, te je instaliran MaxelerOS 2015.2 (driveri i alati za upravljanje karticom). Provedeno je ispitivanje ispravnosti, te je utvrđeno da su računalo i FPGA kartica u ispravnom radnom stanju. Radna stanica je postavljena za korištenje preko mreže, te je dostupna za više-korisnički rad.
Programski alati (softver)
Na radnu stanicu instalirani su potrebi alati za razvoj programa, te FPGA hardvera. Specifični alati instalirani za rad s FPGA karticom su: Altera Quartus II 13.1, te Maxeler MaxCompiler 2015.2. Za Altera Quartus i Maxeler MaxCompiler instalirane su i nužne licence. Instalacije i konfiguracija programa provjerene su kompiliranjem referentnih programa i FPGA konfiguracija, te je utvrđeno da su ispravno postavljeni i spremni za rad.

O3: Hardware implementation. Implementation of heterogeneous rule learning using FPGA hardware (Month 16-30)

A10.3 P. Škoda, D. Gamberger: System specification, division of algorithm to hardware parts (kernels) and software parts (završeno u siječnju 2016.)
U programu su identificirane ključne petlje koje će biti nadomještene pozivima funkcija koje rade s FPGA sklopovljem. Kao model funkcionalnosti izvedenih u FPGA sklopovlju koriste se jezgre već razvijene u ranijim fazama projekta, te je za svaku petlju određeno koje ju jezgre nadomješćuju. Prema ovoj specifikaciji jezgre će se u narednim fazama projekta doraditi i implementirati tako da se bolje integriraju u program. više ...

A11.3 P. Škoda, B. Medved Rogina: Specification and implementation of individual kernels in hardware (završeno u travnju 2016.)
Prema podijeli programa na CPU/FPGA dio, napravljen u prethodnoj fazi projekta, detaljno su specificirane jezgre kojima se ključne petlje implementiraju u FPGA sklopovlju. Specificirane su unaprijeđene verzije jezgri Count conditional, Increment conditional i Logic simple. Unaprjeđenja omogućuju njihovu bolju integraciju u program. Navedene jezgre su implementirane pomoću Maxeler MaxCompiler 2015.2 razvojnog sustava i API ja, te postavljene da rade na Maxeler Galava kartici. više ...

O4: Insightful analysis. Public and third party data transformation and integration (Month 13-15)

A1.4 D. Korenčić: Scientific journal paper corpus acquisition, prepocessing and preliminary analysis (završeno u studenom 2015.)
Razvijena je aplikacija za sakupljanje novinskih članaka sa weba. Aplikacija prati news feed kanale zadane od strane korisnika, ekstrahira tekstove i naslove članaka te sprema podatke u bazu. Prema našem znanju ne postoji sličan alat koji je besplatno dostupan, dostupni su samo gotovi korpusi te web servisi za pristup predefiniranim bazama članaka. Stoga je aplikacija potencijalno koristan istraživački alat za sakupljanje novinskih korpusa koji precizno odgovaraju ciljevima istraživača i planu je njeno objavljivanje pod nekom od licenca otvorenog koda.

Pomoću opisane aplikacije pokrenuto je sakupljanje dvaju korpusa novinskih članaka, korpusa koji se sastoji od 25 najvećih američkih web izvora vijesti, te korpusa koji se sastoji od 18 najvećih hrvatskih web izvora. Oba korpusa koristiti će se za razvoj alata za automatsko mjerenje medijske agende. Mjerenje agende je problem blisko povezan sa istraživanjem postavljanja agende (engl. agenda setting).

U svrhu upoznavanja sa problemom i podacima, provedeno je predistraživanje mjerenja agende. Osim strukture korpusa, istraživan je i potencijal alata za automatsko mjerenje agende temeljenih na tematskim modelima (engl. topic models), te su dobiveni obećavajući rezultati. Istraživanje je objavljeno u članku "Getting the Agenda Right: Measuring Media Agenda using Topic Models".

Započeta je obrada korpusa sudskih presuda, koje su u suradnji sa pravnicima označene ključnim frazama te će se koristiti za usporedbu i razvoj alata za automatsku ekstrakciju ključnih fraza iz teksta.

A2.4 T.Šmuc: Data acquisition (World Bank, IMF-trading data), cleaning and transformation, exploratory analysis (završeno u studenom 2015.)
Eksperimente provodimo na podacima iz dva izvora: baze World bank i baze UNCTAD. Podaci sa 105 različitih indikatora iz baze World Bank opisuju 225 različitih zemalja svijeta. Malo promijenjena verzija python skript je korištena za skidanje i spremanje podataka u traženom formatu. Skripta koristi World Bank API da bi omogućila pristup i skidanje podataka. Za svaku zemlju stvorimo jedan redak u podacima pri čemu vrijednosti odabranih World Bank indikatora čine atribute odabranih zemalja. Atributi su realne vrijednosti, međutim značajni postotak u podacima čine nedostajuće vrijednosti. UNCTAD baza je korištena kao izvor podataka koji opisuju mrežu trgovine između zemalja na bazi 106 različitih trgovačkih indikatora da bi opisali isti skup od 225 zemalja. Podaci su skinuti pomoću programa Selenium u .csv formatu, parsirani s java aplikacijom razvijenom za tu svrhu i spremljeni u sqlite bazu podataka. Redci među podacima označavaju zemlje koje su opisane s 106 atributa koji opisuju izvoz i 106 atributa koji opisuju uvoz proizvoda iz drugih zemalja. Podaci su normalizirani prema ukupnom uvozu/izvozu svih proizvoda i skalirani u interval [0; 100]. Određeni postotak nedostajućih vrijednosti (daleko manji nego u World bank podacima) je prisutan i u ovom skupu.

O4: Insightful analysis. Analysis of networks of country level data (Month 12-18)

A3.4 T.Šmuc: Modeling using ensembles of rules and benchmarking against other data mining approaches (završeno u studenom 2015.)
Razvijen je novi algoritam CLUS_RM, iz tzv. redescription mining familije. Redescription mining paradigma relativno je nova i predstavlja ekstenziju tzv. asocijativnih pravila, na način da se atributi izdvajaju na dva ili više odovojenih podskupova, a pravila dobivena iz svakog podskupa se povezuju u tzv. redescription-e ukoliko postoji značajno preklapanje primjera koje pokrivaju CLUS-RM algoritam je baziran na slučajnoj šumi prediktivnih grupirajućih stabala i ima sposobnost generiranja velikog broja različitih redescriptiona što omogućava:
1) Selekciju veoma točnih redescriptiona po pitanju koeficijenta sličnosti Jaccard uz veliku razinu statističke značajnosti.
2) Otkrivanje opisa velikog postotka elemenata koristeći raznovrsne atribute.
3) Korištenje velikog skupa redescriptiona za poboljšavanje i generiranje novih redescriptiona.

Evaluacija metoda s drugim algoritmima je pokazala da naš algoritam proizvede višestruko puta više redescriptiona što mu omogućava pronalazak i optimizaciju kvalitetnijeg, manjeg, skupa redescriptiona u odnosu na druge algoritme iz polja. Skup redescriptiona je točniji po pitanju koeficijenta sličnosti Jaccard, i na većini testiranih skupova podatak sadrži statistički značajnije redescriptione. Za razliku od drugih postojeći algoritama u polju, naš algoritam uglavnom generira pravila koja sadrže logički operator konjunkcije. To je bitno zato što omogućava lakšu interpretaciju pravila i stjecanje znanja od strane korisnika.

O4: Insightful analysis. Modelling and inference on dynamical processes in complex networks (Month 12-24)

A6.4 T.Šmuc: Modelling and learning dynamics of information spreading on networks (ožujku 2016.)
Razvijen je model širenja informacija na mrežama koji uzima u obzir dva odvojena utjecaja: (i) utjecaj koji ovisi o povezanosti čvorova u mreži i (ii) vanjski utjecaj koji je neovisan o povezanosti. Predložena je metoda estimacije ova dva utjecaja iz podataka koristeći maximum likelihood metodu. Kao glavni primjer uzete su online društvene mreže gdje čvorovi odgovaraju korisnicima neke društvene mreže a poveznice njihovim online prijateljstvima. Za korisnike koji su u određenom trenutku preuzeli neki informaciju kažemo da su "aktivirani". Ključna pretpostavka našeg modela je da utjecaj prijatelja ovisi o broju aktiviranih prijatelja u mreži dok vanjski utjecaj, recimo od online medija, djeluje neovisno o broju već aktiviranih prijatelja. Istraživanja su provedena na simuliranim podacima uz pretpostavku eksponencijalnog opadanja utjecaja prijatelja, iako metoda omogućuje i drugačije parametrizacije, primjerice konstantni utjecaj koji odgovara često korištenom susceptible-infected (SI) modelu. Također, model je testiran i na stvarnim podacima korisnika Facebook društvene mreže prikupljenima pomoću dvije odvojene Facebook aplikacije koje zajedno sadrže preko 16000 korisnika. Trenutni napredak je prezentiran na dvije međunarodne konferencije u obliku prezentacije i postera.

O4: Insightful analysis. Text mining and scientific journal paper collection (Month 16-36)

A15.4 D. Korenčić: Problem analysis, research of existing applicable supervised and unsupervised methods (završeno u veljači 2016.)
Započet je rad na razvoju algoritama za ekstrakciju ključnih fraza iz pravnog korpusa. Istražene su najuspješnije već razvijene metode i započeta je prilagodba metode temeljene na PageRank algoritmu za ekstrakciju istaknutih riječi koje odgovaraju čvorovima u mreži riječi. Prilagođavanje će se vršiti ubacivanjem u PageRank model podataka dobivenih statističkom analizom tekstnog korpusa.

O4: Insightful analysis. Text mining and scientific journal paper collection (Month 16-36)

A16.4 D. Korenčić: Developement of semantic resources based on ontologies and large corpuses. (završeno u svibnju 2016.)
Nastavljen je rad na algoritmima za maksimizaciju tematske pokrivenosti. Takvi algoritmi nalaze primjenu u eksplorativnoj analizi zbirki tekstova, na primjer u analizi medijskog sadržaja. Cilj algoritama je detektirati što veći broj tema iz zbirke tekstova. Razvijani algoritmi temelje se na upotrebi grafičkih tematskih modela (engl. topic models) u kombinaciji sa algoritmima grupiranja (engl. clustering) na način da umjesto učenja jednog tematskog modela nauče nekoliko desetaka modela, filtriraju teme niske kvalitete, i grupiraju preostale teme po sličnosti. Princip rada temelji se na opažanju da samo jedan tematski model ne može pokriti sve teme koje se javljaju u većoj količini tekstova.

O4: Insightful analysis. Text mining and scientific journal paper collection (Month 16-36)

A17.4 D. Korenčić: Supervised experiments for text mining (feature extraction and selection, model selection) Interpretation of results and paper preparation. (završeno u kolovozu 2016.)
Tijekom istraživanja proučavane su mjere sličnosti i kvalitete tema, te pogodni algoritmi grupiranja, odabrana je mjera koherentnosti (engl. topic coherence), Započeta je implementacija samih algoritama za maksimizaciju pokrivenosti te rad na evaluaciji algoritama, kako na automatskoj evaluaciji koja bi korištenjem metrika sličnosti dvaju tema ocijenila međusobnu (relativnu) pokrivenost algoritama, tako i na evaluaciji algoritama putem od ljudi konstruiranog skupa podataka. Takav skup bi sadržavo referentne "koncepte" (teme konstruirane od strane ljudi i karakterizirane skupom riječi i vezanih tekstova) te skup parova tema označenih mjerom sličnosti. Na temelju označenog skupa parova bi se metodama strojnog učenja konstruirala funkcija koja može ocjenjivati parove tema po sličnosti.