Fokus disertacije usmeren je na zadatak klasifikacije teksta, koji pripada jednom od zadataka oblasti obrade prirodnih jezika. U predavanju će biti prikazana četiri klasifikaciona problema u kontekstu obrade prirodnih jezika: problem validacije bilingvalnih parova višečlanih leksema, problem određivanja dobrih primera upotrebe rečeničnih odrednica, problem identifikacije autora kratkih tekstova, kao i problem analize osećanja u kratkim porukama.

Klasifikacija bilingvalnih parova leksema Primeri višečlanih leksemskih jedinica su: „predikatska logika“, „digitalne biblioteke“, „skup za obučavanje“, itd. Disertacija će se baviti problemom validacije prevoda bilingvalnih parova, tako da su klase dobar prevod i loš prevod. Na primer, neka je ulazni skup D1 = {((predikatska logika, mathematics), loš),((digitalne biblioteke, digital libraries), dobar), . . . ,((skup za obučavanje, training set), dobar)}. Atributi koji mogu biti korisni pokazatelji da je u pitanju dobar prevod su: vrste reči u obe lekseme („predikatska logika“ sadrži pridev i imenicu, dok je mathematics samo imenica), postojanje zajedničke podniske određene dužine (kod para „digitalne biblioteke“ i digital libraries to je podniska „digital“), broj reči u obe lekseme, itd.

Klasifikacija dobrih primera upotrebe rečničkih odrednica U svakom rečniku, elektronskom ili papirnom, korisno je da uz rečničku odrednicu stoji i primer kako se ona koristi u jeziku. U ovom slučaju klasifikacije, zadatak je svakom primeru dati ocenu podobnosti, odnosno automatski zaključiti da li je primer dobar ili loš. Na primer, za odrednicu „računar“, dobri primeri upotrebe su rečenice „Celodnevno sedenje uz računar može izazvati krivljenje kičme“ ili „Fon Nojman je autor arhitekture modernog računara“, ali ne i „Lenovo računar.“ jer nije dovoljno informativno. Atributi koji mogu biti korisni pokazatelji koliko dobro tekst ilustruje upotrebu rečničke odrednice su: pozicija rečničke odrednice u primeru, vrsta reči rečnike odrednice, dužina teksta, broj reči, broj cifara, broj imenica, broj prideva, broj glagola, broj pokaznih zamenica, broj ličnih zamenica, broj znakova interpunkcije, broj tehničkih oznaka i skraćenica, itd.

Klasifikacije kratkih poruka u odnosu na autora U disertaciji će se razmatrati dva slučaja klasifikacije kratkih poruka. U prvom slučaju, klase su autori poruka, a zadatak je svakoj poruci dodeliti njenog autora iz tog fiksnog skupa. Ovaj problem naziva se identifikacija autorstva. Na primer, neka je poznato da pošiljalac poruke može biti ili osoba A ili osoba B. Zadatak identifikacije autorstva, u tom slučaju, je konstrukcija matematičkog modela koji će za kratku poruku proceniti da li je šalje osoba A ili osoba B. Atributi koji mogu biti korisni diskriminatori autorstva su: dužina poruke, broj reči, broj cifara, broj imenica, broj prideva, broj glagola, broj znakova interpunkcije, upotreba emotograma, upotreba određenih skraćenica, i slično.

Klasifikacija kratkih poruka u odnosu na stav i raspoloženje Drugi problem klasifikacije nad kratkim porukama koji će se razmatrati u tezi naziva se analiza raspoloženja i stavova, odnosno analiza sentimenata. Ako se krene od pretpostavke da SMS poruka nosi u sebi pozitivan ili negativan stav o nekoj stvari, ali i da može biti isključivo informativna, klase mogu biti: pozitivan, negativan i neutralan stav. Na primer, za kratku poruku „Pada kiša.“ stav je neutralan i poruka je informativne prirode, dok bi se za poruku „Jao ne, opet kiša!!!“ moglo reći da njen autor nema pozitivan stav. Atributi koji mogu biti korisni diskriminatori sentimenata su: broj emotograma koji predstavljaju srećno, tužno, neutralno, zbunjeno ili neko drugo stanje, dužina poruke, broj prideva, broj uzvičnika, broj upitnika, broj tačaka, i slično.

Enorman rast količine podataka koji potiču iz bioloških istraživanja, koji se svakodnevno pronalaze i čuvaju u raznim bazama podataka, kao i specifičnost i kompleksnost samih bioloških podataka, dovela je do potrebe razvoja sofisticiranih računarskih metoda pomoću kojih bi se ti podaci struktuirali, pohranjivali, analizirali i tumačili. Stoga je u naučnoj oblasti bioinformatike posljednjih godina fokus stavljen na razvoj matematičkih i računarskih modela i metoda kojim bi se zadaci obrade bioloških podataka rješavali na što efikasniji način.

Potreba za sistematskim pristupom izučavanja određenih bioloških struktura (kao što su proteini ili metaboliti), kao i veza između njih, dovela je do formiranja bioloških mreža, koje se dalje analiziraju u cilju dobijanja korisnih bioloških informacija. Predstavljanje bioloških procesa u vidu mreže omogućava jasnije sagledavanje kompletnog procesa i konteksta u kojem se dešava, a omogućava lakše izvođenje novih saznanja i zaključaka. Biološke mreže su apstraktan prikaz bioloških sistema, koji sadrži većinu važnih karakteristika. Čvorovima u mreži odgovaraju komponente biološkog sistema, a grane između čvorova predstavljaju veze ili zavisnosti između komponenti.

Predmet istraživanja ove doktorske disertacije biće particionisanje velikih bioloških mreža na manje podmreže, kao i grupisanje čvorova mreže u određene kategorije. Particionisanje mreže se vrši po različitim kriterijumima koji osiguravaju da podmreže imaju određena topološka svojstva, dok se grupisanjem pronalaze biološkim elementi sa sličnim funkcijama. Podmreže dobijene kao rezultat particionisanja će dalje biti analizirane sa biološkog aspekta i predstavljaće osnov za: prepoznavanje značajnih grupa čvorova (proteina/metabolita) u mreži, kao i razvoj novih ili unapređenje postojećih alata za biološku, funkcionalnu i molekulsku anotaciju proteina. U okviru disertacije razmatraće se četiri problema. Problem particionisanja rijetkih bioloških mreža na međusobno povezane podmreže, tzv. k-plex podmreže koje se formalno definišu na sljedeći način. Neka je dat graf G=(V,E). Podgraf od n čvorova grafa G je k-plex ako je svaki čvor susjedan sa bar (n-k) čvorova u tom grafu. Problem k-plex maksimalnog težinskog particionisanja po granama (engl. maximum edge-weight k-plex partitioning problem -- Max-EkPP) je problem koji podrazumijeva pronalaženje k-plex particionisanja ulaznog težinskog grafa takvog da je suma težina svih grana u dobijenim indukovanim k-plex podgrafovima maksimalna.

Nad listom metaboličkih reakcija posmatra se problem predikcije uloge metabolita u metaboličkim reakcijama. Motivacija za rješavanje problema predikcije je u tome što dobijena saznanja mogu doprinijeti boljem razumijevanju metaboličkih putanja (engl. metabolic pathways). Identifikacija uloge metabolita u reakciji se koristi za dobijanje novih saznanja o vezi između metabolita na osnovu njihovog učešća u zajedničkoj reakciji.

Klasterovanjem velikih mreža dimenzija strukture se smanjuje, a funkcionalnosti se očuvaju u gusto povezanim komponentama. Jedan od poznatih problema u ovoj oblasti je particionisanje velike mreže na manje visoko povezane (engl. highly connected) podmreže uklanjanjem što je moguće manje grana. Za podmrežu sa n čvorova kažemo da je visoko povezana ako je stepen svakog čvora bar n/2. Dobijene podmreže predstavljaju grupe bioloških elemenata sa sličnim funkcijama.

Problem dodavanja što je moguće manje grana u graf da bi se određeni skupovi čvorova povezali formalno se definiše na sljedeći način. Dat je neusmjeren graf G=(V,E), gdje je V skup čvorova, a E skup grana i kolekcija C podskupova skupa V. Potrebno je naći skup dodatnih grana E’ minimalne kardinalnosti takav da je svaki podgraf grafa G=(V,E∪ E’) koji je indukovan čvorovima iz podskupa Ci. Dobijene grane za određenu biološku mrežu predstavljaju osnov za dalju identifikaciju značajnih grupa bioloških elemenata.

U ovom izlaganju za navedene probleme particionisanja i grupisanja u biološkim mrežama biće prikazani postojeći i neki unaprijeđeni i novorazvijeni modeli, koji bi omogućili primjenu različitih statističkih i optimizacionih tehnika za njihovo rješavanje.

Šef studijskog programa matematika i informatika Prirodno-matematičkog fakulteta u Banjaluci prof. dr Dragan Matić i Milana Grbić, viši asistent su 4. jula ove godine posetili Matematički fakultet u Beogradu. Milana Grbić je na Seminaru Katedre za računarstvo predstavila temu i sadržaj svoje doktorske disertacije, pod nazivom “Računarske metode particionisanja i grupisanja u biološkim mrežama”. Seminaru su prisustvovali i Šef Katedre za računarstvo Matematičkog fakulteta prof. dr Nenad Mitić, prof. dr Gordana Pavlović Lažetić, prof. dr Miodrag Živković, prof. dr Vladimir Filipović i doc. dr Aleksandar Kartelj sa Matematičkog fakulteta u Beogradu, kao i prof. dr Đura Paunić, profesor sa Prirodno-matematičkog fakulteta u Novom Sadu.

Očuvanje nacionalnog kulturnog nasleđa je od izuzetnog značaja za razumevanje identiteta grupe ili pojedinca. Konvencija UNESCO iz 2003. godine prepoznaje različite domene u kojima se nematerijalno kulturno nasleđe može manifestovati. To su tradicije govora i izražavanja, izvođenje umetničkih dela, društvena dešavanja, rituali, praznični događaji, znanje i njegova primena u vezi prirode i svega oko nas, kao i razvoj i primena zanatskih veština. Srpsko kulturno nasleđe je specifičan spoj više različitih tradicija i naracija: slovenske, vizantijske, starobalkanske, herojske, nacional-romantičarske, prosvećeno-evropske. Primenom informacionih tehnologija i digitalizacije kao rezultat u domenu kulturnog nasleđa je stvaranje digitalnih baza podataka o nematerijalnoj kulturnoj baštini. S druge strane, kako je postalo jednostavnije proizvođenje digitalnih multimedijalnih dokumenata, to je takvih dokumenata sve više, i često je nemoguće upravljati njima, efikasno pretraživati i dobavljati relevantne podatake ili cele dokumenate bez uspostavljanja odgovarajuće organizacije. Pod organizacijom se smatra smeštanje dokumenata u multimedijalnu bazu podataka, uz definisanje odgovarajuće strukture za opis metapodataka i označavanje dokumenata po relevantnim metapodacima.

Predmet istraživanja ove doktorske disertacije biće razvoj adekvatnog dizajna i implementacije multimedijalne baze podataka nematerijalnog kulturnog nasleđa dela Balkana kao i automatska anotacija sadržaja ove multimedijalne baze kao osnova za uspešnu tematsku pretragu i pretragu po metapodacima. Doktorska disertacija će se baviti i povezivanjem sadržaja baze sa geolokacijskim informacijama na mapi, kao i prostorno-vremenskom pretragom. Istraživanje je motivisano multimedijalnom kolekcijom koja predstavlja rezultat petnaestogodišnjeg terenskog istraživanja koje su izveli istraživači Balkanološkog instituta SANU. Istraživači su intervujisali lokalno stanovništvo na različitim lokacijama u području Balkana. Kolekcija se sastoji od audio i video materijala, fotografija, rukopisa i tekstualnih protokola. Protokoli su dokumenti u vidu nestruktuiranog ili polustruktuiranog teksta koji imaju za cilj da opišu određeni audio ili video materijal.

U disertaciji će biti primenjene metodologije razvoja objektno-orijentisane (PostgreSQL) baze podataka za upravljanje metapodacima o multimedijalnim materijalima i XML baze podataka koja će omogućiti pretraživanje protokola i informacija ekstrahovanih iz njih. Za rad sa geolokacijskim podacima koristiće se metodologije prostorne baze podataka (PostGIS). Za obradu protokola koristiće se metoda obrade prirodnih jezika zasnovana na konačnim transduktorima. Biće razvijena biblioteka konačnih transduktora za ekstrakciju i anotaciju metapodataka i sadržaja koji se odnosi na neke od tema karakterističnih za nematerijalno kulturno nasleđe. Ova metoda koristi jezičke resurse poput jezičkih rečnika reči u osnovnom i izvedenim oblicima. Formirano znanje u fazi analize protokola primenićemo u izgradnji konačnih transduktora. Za klasifikaciju multimedijalnog materijala prema sadržaju protokola primeniće se metoda mašinskog učenja zasnovana na različitim tipovima n-grama nad odgovarajućom vrećom reči. Biće razvijen i sistem za anotaciju i organizovanje samih multimedijalnih dokumenata u pretraživu formu kao i za njihov prikaz. Multimedijalna baza kulturnog nasleđa biće primenjena na pretraživanje po metapodacima kao i po sadržaju, uz razvoj interaktivne -vremenske mape.

Teorija kompleksnih mreža bavi se proučavanjem strukture kompleksnih sistema sastavljenih od velikog broja elemenata između kojih postoje izrazito jake nelinearne interakcije. Matematičku osnovu za proučavanje strukture kompleksnih sistema predstavlja teorija grafova, dok za analiziranje dinamičkih procesa važnu primenu imaju metode statističke fizike. Struktura kompleksnog sistema predstavlja se mrežom tako da se elementi sistema preslikavaju na čvorove u mreži, a interakcije između elemenata su predstavljene kao grane između čvorova. U odnosu na jednostavne ili slučajno generisane mreže, kompleksne mreže ispoljavaju veliku nehomogenost pri distribuciji grana. Karakteristično je da se javlja visoka koncentracija grana u okviru pojedinih grupa čvorova i istovremeno niska koncentracija grana između čvorova u različitim grupama. Ovakve grupe čvorova se nazivaju klasteri (moduli, zajednice) i vrlo često imaju zajedničke osobine i uloge u kompleksnom sistemu. Problem pronalaženja ovakvih grupa u kompleksnim mrežama naziva se problem klasterovanja na kompleksnim mrežama. Razvijanje metoda za rešavanje ovog problema i njihova primena su od velikog značaja za razumevanje dinamike i evolucije kompleksnih sistema. Osim toga, mogu omogućiti bolju vizualizaciju i pružiti neophodne informacije o pojedinačnim čvorovima i njihovim ulogama u mreži. Na primer, pojedini čvorovi u klasteru mogu imati ulogu u povezivanju klastera sa ostatkom mreže, dok drugi čvorovi mogu imati ulogu kontrolisanja i stabilizacije klastera.

Najzastupljeniji pristup za klasterovanje na kompleksnim mrežama se ogleda u definisanju funkcije, koja meri kvalitet particionisanja mreže, i konstruisanju metoda za pronalaženje particije za koju se dostiže maksimalna vrednost definisane funkcije. Ovakvim pristupom problem klasterovanja se svodi na problem kombinatorne optimizacije i u tom slučaju na raspolaganju je širok spektar postojećih metoda optimizacije. Od definisanih mera kvaliteta, najpopularnija je modularnost (engl. modularity) koju su 2004. godine definisali Mark Njuman i Mišel Girvan. Modularnost klastera predstavlja razliku između stvarnog broja grana unutar klastera i očekivanog broja grana unutar klastera u mreži sa čvorovima istog stepena, a slučajno postavljenim granama. Modularnost mreže predstavlja zbir modularnosti svih klastera. Kako je traženje particije mreže sa najvećom vrednošću modularnosti NP-težak problem i broj mogućih particija raste eksponencijalno u odnosu na broj čvorova za rešavanje problema razvijaju se heurističke metode.

U okviru izlaganja biće predstavljena ADVNDS metoda (engl. Ascent-Descent Variable Neighborhood Decomposition Search) koja je razvijena za maksimizaciju modularnosti mreže. U cilju efikasne primene za klasterovanje na kompleksnim mrežama velikih dimenzija metoda ima dodatni mehanizam za dekompoziciju problema na manje potprobleme i unapređeni mehanizam za prevazilaženje lokalnih maksimuma modularnosti korišćenjem kriterijuma za povremeno prihvatanje lošijeg rešenja od trenutno razmatranog. Pored toga biće predstavljena funkcija za merenje kvaliteta particionisanja mreže, koja bi trebalo da prevaziđe nedostatke uočene detaljnom analizom modularnosti.