UNIVERZA V LJUBLJANI FAKULTETA ZA RAČUNALNIŠTVO IN INFORMATIKO DUŠAN BOŢIČ Avtomatsko povzemanje besedil s pomočjo semantične analize MAGISTRSKO DELO MENTOR: prof. dr. Igor Kononenko Ljubljana, 2016 Rezultati magistrskega dela so intelektualna lastnina avtorja in Fakultete za računalništvo in informatiko Univerze v Ljubljani. Za objavljanje ali izkoriščanje rezultatov magistrskega dela je potrebno pisno soglasje avtorja, Fakultete za računalništvo in informatiko ter mentorja. Zahvaljujem se mentorju prof. dr. Igorju Kononenku za strokovne napotke in usmeritve pri izdelavi magistrske naloge. Zahvaljujem se dr. Ercanu Canhasiju za nesebično pomoč pri interpretaciji njegove doktorske dizertacije in pristopa ekstraktnega povzemanja s pomočjo analize arhetipov. Zahvaljujem se doc. dr. Tomažu Erjavcu za vpeljavo v svet slavističnih virov na področju raziskovanja slovenskega jezika in za posredovanje elektronskih virov, ki so predmet obravnave magistrskega dela. Zahvaljujem se sodelavcu Srečku Mandlju za strokovno pomoč pri izdelavi lastne programske rešitve, ki je rezultati magistrske naloge. Zahvaljujem se doc. dr. Darji Fišer za pomoč pri dostopu in razlagi slovenskih digitalni viri. Zahvaljujem se staršem in prijateljem za podporo ter razumevanje tekom študija. Zahvaljujem se ženi dr. Maji Šubelj za pomoč pri lektoriranju in prevajanju magistrske naloge. Zahvaljujem se ji za vse vzpodbudne besede, ki so odločno pripomogle k dokončanju teme, kjer ne manjka multidisciplinarnih izzivov. Kazalo Seznam slik Seznam tabel Slovar pojmov Slovar kratic Povzetek Abstract 1. Uvod ....................................................................................................................................... 1 1.1 Raziskovalne teme ...................................................................................................... 2 1.2 Prispevek naloge ......................................................................................................... 3 1.3 Organizacije naloge .................................................................................................... 5 2. Raziskovanje naravnih besedil ............................................................................................... 8 2.1 Jezikovne strukture ................................................................................................... 10 2.2 Povzemanje naravnega jezika ................................................................................... 12 2.2.1 Vidik vhoda povzemanja besedila ........................................................................ 12 2.2.2 Vidik namena povzemanja besedila ...................................................................... 13 2.2.3 Vidik izhoda povzemanja besedila ....................................................................... 14 3. Računalniško povzemanje besedil ........................................................................................ 17 3.1 Ekstraktni pristop povzemanja besedil ..................................................................... 18 3.1.1 Preprosti pristop ekstraktnega povzemanja besedil .............................................. 18 3.1.2 Pristop ekstraktnega povzemanja besedil na podlagi korpusa besedil .................. 20 3.1.3 Pristop ekstraktnega povzemanja besedil na podlagi grafa .................................. 20 3.1.4 Pristop ekstraktnega povzemaja besedil z matrično faktorizacijo ........................ 20 3.1.5 Ekstraktivno povzemanje besedil z analizo arhetipov .......................................... 21 3.1.6 Pristop ekstraktnega povzemanja besedil z algebraično redukcijo ....................... 22 3.1.7 Algoritmi izbiranja stavkov v LSA ....................................................................... 25 3.2 Semantični pristop povzemanja besedil ................................................................... 28 3.2.1 Pristop semantičnega povzemanja besedil s koherenco ........................................ 29 3.2.2 Semantično povzemanje besedil s teorijo jezikovne strukture ............................. 30 3.2.3 Pristop semantičnega povzemanja besedil s kohezijo .......................................... 32 3.3 Mere za ocenjevanje metod povzemanja besedil ..................................................... 34 3.3.1 Kvaliteta besedila .................................................................................................. 35 3.3.2 Ocenjevanje kvalitete besedila z mero so-izbire ................................................... 36 3.3.3 Ocenjevanje kvalitete besedila z mero so-izbire glede na vsebino ....................... 36 3.3.4 Zunanje mere ocenjevanja kvalitete besedila ....................................................... 39 4. Opis knjiţnic in uporabljenih orodij ..................................................................................... 41 4.1 Java EE ..................................................................................................................... 41 4.2 ZK ............................................................................................................................. 41 4.3 WebLogic streţnik .................................................................................................... 42 4.4 WAMP streţnik ........................................................................................................ 43 4.5 Matlab ....................................................................................................................... 44 4.6 CoreNLP ................................................................................................................... 44 4.7 TML .......................................................................................................................... 44 4.8 Log4J ........................................................................................................................ 45 4.9 Analiza Arhetipov..................................................................................................... 45 4.10 JROUGE ................................................................................................................... 45 4.11 Digitalni viri ............................................................................................................. 46 4.12 NetBeans ................................................................................................................... 46 5. SimpleX ................................................................................................................................ 49 5.1 Zahteve za delovanje in arhitektura sistema ............................................................. 50 5.2 Uporabniški vmesnik ................................................................................................ 54 5.3 Najbolj pogoste besede ............................................................................................. 56 5.4 Zajem podatkov ........................................................................................................ 58 5.5 Predobdelava podatkov............................................................................................. 58 5.6 Analiza ...................................................................................................................... 60 5.6.1 Analiza arhetipov .................................................................................................. 60 5.6.2 Semantična analiza ................................................................................................ 61 5.7.1 Izvorni dokumenti ................................................................................................... 65 5.7.2 Analiza rezultatov .................................................................................................... 65 6. Zaključek .............................................................................................................................. 78 7. Literatura in internetni viri ................................................................................................... 81 8. Priloge ................................................................................................................................... 89 Seznam slik Slika 1: Primer analize arhetipov ............................................................................................. 22 Slika 2: Taksonomija mer ocenjevanja povzetkov in izvlečkov ............................................. 35 Slika 3: Uporabniški vmesnik aplikacije SimpleX .................................................................. 42 Slika 4: Administratorska konzola aplikacijskega streţnika WebLogic .................................. 43 Slika 5: Administratorska konzola MySQL baze ..................................................................... 43 Slika 6: Razvojno okolje NetBeans .......................................................................................... 47 Slika 7: Arhitekturni opis programa za povzemanje naravnih besedil SimpleX ...................... 50 Slika 8: Izsek podatkovnega relacijskega modela baze LBS ................................................... 51 Slika 9: Lista uporabniške maske za različna načina povzemanja ........................................... 54 Slika 10: Generiranje PDF dokumenta izvlečka....................................................................... 55 Slika 11: Prikaz trenda ocen povzemanja ................................................................................. 55 Slika 12: Uporabniška maska semantičnega povzemanja ........................................................ 56 Slika 13: Koraki semantičnega povzemanja ............................................................................. 63 Slika 14: Histogram ocen povzemanja z AA in človeškim povzemanjem (Rouge-1) ............. 67 Slika 15: Histogram ocen podobnosti LSA in človeškega povzemanja(Rouge-1) .................. 68 Slika 16: Primerjava LSA in analize arhetipov z ročnimi povzetki. ........................................ 69 Slika 17: Histogram ocen povzemanja z AA in človeškim povzemanjem (Rouge-2) ............. 71 Slika 18: Histogram ocen podobnosti LSA in človeškega povzemanja(Rouge-2) ................. 72 Slika 19: Histogram ocen povzemanja z AA in človeškim povzemanjem (Rouge-3) ............. 74 Slika 20: Histogram ocen podobnosti LSA in človeškega povzemanja(Rouge-3) .................. 75 Seznam tabel Tabela 1: Algoritmi izbiranja stavkov v okviru LSA .............................................................. 28 Tabela 2: Primeri relacij RST v besedilu ................................................................................ 31 Tabela 3: Najbolj pogoste besede v slovenskem jeziku na podlagi korpusa Gigafida ............ 57 Tabela 4: Primerjava analize arhetipov in ročnih povzetkov z uporabo Rouge-1. .................. 65 Tabela 5: Primerjava analize arhetipov in ročnih povzetkov z uporabo Rouge-2. ................... 69 Tabela 6: Primerjava analize arhetipov in ročnih povzetkov z uporabo Rouge-3 .................... 72 Tabela 7: Primerjava kvalitete povzetkov z arhetipi in ročnih povzetkov ............................... 75 Tabela 8: Primerjava kvalitete ročnih povzetkov s semantičnim povzemanjem...................... 76 Tabela 9: Primerjava kvalitete semantičnega povzemanja z povzemanjem z arhetipi. ............ 76 Slovar pojmov Prazne besede (angl. stop words) – so besede, ki predstavljajo lepilo pri vzpostavitvi stavčne oblike, ki ustreza gramatiki, vendar ne vplivajo na pomen stavka. Te besede so v fazi predprocesiranja naravnih jezikov odstranjene, ker so zelo pogoste in motijo značilke povezane s frekvenco pojavitve besed [19]. Pogoste besede (angl. common words) – seznam pogostih besed ni dokončen in je rezultat analize zelo velikega števila besedil. V primeru Oxford English besedil je bilo upoštevanih preko milijarde besed. The Reading Teacher’s Book of Lists trdi, da prvih 25 besed s seznama predstavlja eno tretjino vseh besed v vseh angleških besedilih, prvih 100 besed pa polovico vseh besed napisanega materiala [20]. Polisemija (angl. polysemy) – polisemija je asociacija z eno ali več besedami, ki imajo različen pomen. Polisem je beseda ali fraza z več pomeni. Nasprotno imenujemo natančno ujemanje besede s pomenom monosemija (angl monosemy). Monosemijo lahko najdemo v specializiranih slovarjih, ki se nanašajo na tehnične teme [22]. Izvlečki (angl. extractive summary) – izvlečki so krajši sestavki besedila, pri katerih so stavki izbrani iz izvornega besedila in kot taki tvorijo novo ter krajše besedilo, ki ohranja pomen in koncepte izvornega besedila. Povzetki (angl. abstractive summary) – povzetki so krajši sestavki besedila, pri katerih se ohranja pomen in koncepte izvornega besedila, vendar le-ti ne ustrezajo izvornim stavkom. Povezovalna beseda/fraza (angl. cue word/phrase) – beseda ali fraza, ki povezuje dele besedila in označuje določeno semantično relacijo v diskurzu besedila. Primeri takih besed so: mimogrede (angl. incidentally), na primer (angl. for example), kakorkoli (angl. whatever), vseeno (angl. anyway), mimogrede (angl. by the way), poleg tega (angl. furthermore), prvi (angl. first), drugi (angl. second), potem (angl. then), sedaj (angl. now), tako (angl. thus), poleg tega (angl. moreover), zato (angl. therefore), zato (angl. hence), nazadnje (angl. lastly), končno (angl. finally), po drugi strani (angl. on the other hand) [3]. Preprosti pristop (angl. shallow approach ali surface level approach) – najstarejši pristop, kjer se uporabljajo preprosti indikatorji, na podlagi katerih se odloča, kateri deli besedila so pomembni. Primeri takih indikatorjev so: frekvenca pojavitev besed, pojavitev pogostih besed, lokacija besed v stavku, pojavitev besed iz naslova, ipd. Anafora (angl. anaphoric expression) – je izraz, katerega interpretacija je odvisna od drugega izraza v skupnem kontekstu [35]. Neredundantnost (angl. non-redundancy) – je lastnost, da so vsi podatki informativni tj., da se informativnost podatkov niti ne ponavlja niti je odveč. Lematiziranje (angl. lemmatization) – je spreminjanje besedne vrste iz skladenjske oblike v nedoločnik na podlagi digitalnega vira. Krnjenje (angl. stemming) – je alternativa lematiziranju, ker ne uporablja digitalnih virov in je hevristični proces odstranjevanja prefiksov ali postfiksov.