Sumarizare automat focalizat temporal - profs.info.uaic.rocorinfor/Claudiu.pdf · Universitatea...

Universitatea "Al.I. Cuza" Ias, i

Facultatea de Informatic

Sumarizare automat

focalizat temporal

Autor:

Claudiu Mih il

Coordonator:

Corina For scu

iunie 2008

Introducere

În lucrarea de fat, analiz m o metod de creare a rezumatelor multi-document în

mod automat, cu accent pe localizarea temporal a act,iunilor, exploatând propriet t

,ile

de coeziune s,i coerent

, ale textului.

Obiectivul sumariz rii automate este preluarea datelor de la sursele de informat,ie, ex-

tragerea cont,inutului s

,i prezentarea esent

,ialului într-o form condensat s

,i într-o manier

sensibil la nevoile utilizatorului sau aplicat,iei. Sistemul este capabil s observe evolut

,ia

în timp a informat,iilor prezentate în articolele de s

,tiri, s identi�ce asem n rile s

,i de-

osebirile între informat,iile oferite de surse de s

,tiri diferite. În funct

,ie de num rul de

schimb ri în timp ale punctului de vedere s,i de relat

,ia cu alte surse de informat

,ie, gradul

de încredere asociat articolelor este modi�cat, astfel încât ele pot � incluse sau nu înrezumatul produs.

Primul capitol al acestei lucr ri este destinat considerat,iilor generale asupra suma-

riz rii automate, precum s,i asupra proces rilor de text necesare. Sunt aduse în discut

,ie

atât caracteristicile parametrice, cât s,i abord rile sumariz rii, insistându-se pe pas

,ii

preg titori, componente f r de care sumarizarea nu este posibil .Corpusul utilizat s

,i metoda prin care s-a realizat sumarizarea automat ocup capi-

tolul al doilea al lucr rii. Astfel, sunt descrise colect,ia de texte utilizate s

,i analiza efec-

tuat asupra lor, modalitatea de reprezentare a informat,iei s

,i algoritmul implementat,

al turi de de�nit,iile operatorilor aplicat

,i. Partea de sfârs

,it a capitolului se refer la

generarea limbajului natural, ultima faz a sumariz rii, în care se sintetizeaz produsul�nal.

În cel de-al treilea capitol este prezentat o evaluare a rezumatelor produse de acestsistem, efectuat atât de judec tori umani, cât s

,i de o aplicat

,ie specializat . Rezultatele

obt,inute sunt satisf c toare s

,i dovedesc c sistemul este unul viabil s

,i �abil.

3

Cuprins

1 Metod general 7

1.1 Sumarizare. Sumarizare automat . . . . . . . . . . . . . . . . . . . . . . 71.1.1 Abord ri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Arhitectur abstract pentru sumarizare . . . . . . . . . . . . . . . . . . 101.3 Proces ri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3.1 Segmentare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.3.2 Analiz morfologic . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3.3 Recunoas

,terea entit t

,ilor . . . . . . . . . . . . . . . . . . . . . . . 15

1.3.4 Rezolut,ia referint

,elor anaforice . . . . . . . . . . . . . . . . . . . 17

1.3.5 Coreferint,e între documente . . . . . . . . . . . . . . . . . . . . . 18

1.3.6 Analiz sintactic . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3.7 Expresii temporale . . . . . . . . . . . . . . . . . . . . . . . . . . 191.3.8 Ordonare temporal . . . . . . . . . . . . . . . . . . . . . . . . . 211.3.9 Similaritate cosinus . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.4 Exemple de sisteme de sumarizare . . . . . . . . . . . . . . . . . . . . . . 22

2 Sumarizare aplicat pe corpusurile MUC 25

2.1 Arhitectura sistemului . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.2 Colect

,ie de documente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2.1 Tipuri de documente . . . . . . . . . . . . . . . . . . . . . . . . . 252.2.2 Corpusuri utilizate . . . . . . . . . . . . . . . . . . . . . . . . . . 262.2.3 Analiza corpusului . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3 Modele de reprezentare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.3.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.3.2 Reprezentarea informat

,iei curente . . . . . . . . . . . . . . . . . . 29

2.3.3 Reprezentarea informat,iei ontologice . . . . . . . . . . . . . . . . 31

2.4 Sumarizare multidocument . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4.2 Idee de algoritm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4.3 Operator de plani�care generic . . . . . . . . . . . . . . . . . . . 342.4.4 Taxonomia operatorilor de plani�care . . . . . . . . . . . . . . . . 34

5

Claudiu Mih il

2.4.4.1 Schimbarea perspectivei . . . . . . . . . . . . . . . . . . 342.4.4.2 Contradict

,ia . . . . . . . . . . . . . . . . . . . . . . . . 35

2.4.4.3 Elaborarea . . . . . . . . . . . . . . . . . . . . . . . . . 352.4.4.4 Ra�narea . . . . . . . . . . . . . . . . . . . . . . . . . . 362.4.4.5 Acordul . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.4.4.6 Agregarea . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.4.5 Algoritm pentru aplicarea operatorilor . . . . . . . . . . . . . . . 372.4.5.1 Intrare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.4.5.2 Combinare euristic . . . . . . . . . . . . . . . . . . . . 382.4.5.3 Ordonarea formatelor s

,i generarea lingvistic . . . . . . 38

2.5 Generarea limbajului natural . . . . . . . . . . . . . . . . . . . . . . . . . 392.5.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.5.2 Metode de generare a limbajului natural . . . . . . . . . . . . . . 392.5.3 S

,abloane de text . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3 Rezultate 43

3.1 Evaluare uman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.1.1 Organizare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.1.2 Evaluarea rezultatelor . . . . . . . . . . . . . . . . . . . . . . . . 463.1.3 Evaluarea coerent

,ei . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.2 Evaluare automat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Concluzii s,i perspective 49

6

Capitolul 1

Metod general

1.1 Sumarizare. Sumarizare automat

Obiectivul sumariz rii automate este de a prelua informat,iile de la o surs , de a

extrage cont,inutul din ele s

,i de a prezenta esent

,ialul din acest cont

,inut într-o form

condensat , într-o manier sensibil la nevoile utilizatorului, �e el uman sau o aplicat,ie

[Mani, 2001].Exemple de sumarizare exist oriunde în viat

,a cotidian contemporan . Titlurile

ziarelor sunt frecvent rezumate ale articolelor cont,inute, scrise într-un stil atr g tor.

Abstractele articolelor s,tiint

,i�ce sunt rezumate în form tradit

,ional , scrise chiar de au-

tori sau de persoane special desemnate. Tabelele care arat statistici din fotbal pentruun juc tor sau pentru o echip sunt în mare parte rezumate, precum sunt s

,i recenziile

(pentru c rt,i sau �lme), ghidurile programelor TV, programele conferint

,elor, prognozele

meteorologice, curriculum vitae, necrologurile, paginile web care listeaz resurse pentruun anumit domeniu, cuprinsurile c rt

,ilor sau revistelor, chiar s

,i cataloagele cu produse

disponibile la comerciant,i.

Un sumarizator este un sistem de prelucrare automat a unuia sau mai multor texte,cu scopul obt

,inerii unui rezumat (sumar) util unui utilizator uman [Mani, 2001].

Exist o varietate de parametri care pot in�uent,a proiectarea, dezvoltarea s

,i rezul-

tatele unui sistem de sumarizare. Aces,tia au fost discutat

,i de mult

,i autori, precum

[Mani s,i Maybury, 1999], [Mani, 2001], [Hovy, 2001] etc. s

,i sunt prezentat

,i succint în

continuare:

1. Rat de compresie. Lungimea unui rezumat poate varia, în principiu, de la put,in

mai scurt decât lungimea intr rii pân la aproape zero. Acest lucru înseamn c rata de condensare (sau rat de compresie), descris în ecuat

,ia 1.1, poate varia

de la put,in sub 100% pân la put

,in peste 0%.

wh→ h(w) = v,Rh =

length(v)

length(w)≤ 1 (1.1)

7

Claudiu Mih il

unde w, respectiv v, sunt sursa, respectiv rezumatul, iar length() reprezint funct,ia

de lungime din punctul de vedere al criteriului ales (num r de bit,i, num r de cu-

vinte, num r de propozit,ii sau chiar paragrafe). Funct

,ia h reprezint sistemul de

sumarizare.

2. Auditoriu. Rezumatul focalizat pe utilizator poate � format prin utilizareaunui limbaj speci�c unui anumit tip de utilizator, luând în considerare interesele,cunos

,tint

,ele s

,i nevoile acestuia. Pe de cealalt parte, rezumatele generice sunt

destinate unui grup larg s,i variat de cititori.

3. Relat,ie fat

, de surs . Rezumatele pot � de dou tipuri, în funct

,ie de acest

criteriu: extracte s,i abstracte. Prima categorie se refer la rezumatele formate

prin copierea integral a unor sect,iuni din surs . De exemplu, un rezumat cu rata

de condensare de 25% va cont,ine un sfert din documentul init

,ial. Aceast proport

,ie

se poate referi la num rul de cuvinte, la num rul de propozit,ii, la num rul de

paragrafe. De obicei se aplic metode statistice pentru identi�carea s,i extract

,ia

propozit,iilor cheie dintr-un articol. Spre deosebire, abstractele sunt rezumate al

c ror text nu este prezent, cel put,in part

,ial, în surse. În general, un abstract ofer

posibilitatea unui grad de condensare mai mare: un abstract mai scurt poate oferimai mult informat

,ie decât un extract de aceeas

,i lungime sau chiar mai lung.

4. Funct,ie. Din acest punct de vedere, rezumatele abstracte pot � indicative, in-

formative sau critice. Un abstract indicativ ofer referint,e pentru selectarea

documentelor, în cazul dorint,ei de aprofundare a subiectului. Un abstract infor-

mativ acoper informat,ia important din surs cu anumit grad de detaliu. Un

abstract critic evalueaz problematica articolului surs , exprimând opinia abstrac-torului despre calitatea lucrului autorului. Printre acestea se num r recenziile,care includ p reri, feedback, identi�carea sl biciunilor, recomand ri etc. Totus

,i, un

astfel de sistem este considerat peste scopul actual al sumarizatoarelor, deoarecedepinde într-o mare m sur de interpretarea cultural . Trebuie ment

,ionat îns c

aceast distinct,ie nu este una exclusiv . Rezumatele informative sunt de obicei s

,i

indicative, iar cele critice pot � indicative sau informative.

5. Coerent, . Un text incoerent este unul nelegat, în care propozit

,iile nu sunt închegate

pentru a forma un întreg. Acest defect se poate datora referint,elor anaforice sau

expresiilor temporale nerezolvate (sau rezolvate incorect), propozit,iilor care repet

aceeas,i informat

,ie (situat

,ie care se numes

,te redundant

, ), logicii incorecte, lipsei

unei organiz ri etc.

6. Acoperire. Rezumatele pot � produse dintr-un singur document sau din mai multedocumente, as

,a cum este cazul sumariz rii multi-document (MDS1). În cazul MDS,

1Multi-Document Summarization

8

Sumarizare automat focalizat temporal

Imaginea 1.1: Relat,ia dintre rezumatele indicative, informative s

,i critice

sistemul de sumarizare identi�c asem n rile s,i/sau deosebirile dintre articole s

,i,

eventual, le semnaleaz în rezumat.

7. Limb . Rezumatele pot � monolingve (se proceseaz doar o singur limb , cuies

,irea în aceeas

,i limb ), multilingve (se proceseaz mai multe limbi, cu ies

,irea

într-o limb din cele de la intrare) sau translingve (se proceseaz mai multe limbi,dar ies

,irea este într-o alt limb decât cele de intrare). De asemenea, rezumatele

pot � restrict,ionate la un limbaj particular, un vocabular specializat (în cazul în

care utilizatorul dores,te, de exemplu, un manual tehnic), sau la un limbaj adecvat

elevilor sau turis,tilor str ini, care au nevoie de un vocabular simplu, f r construct

,ii

complexe.

8. Gen. Un sistem de sumarizare poate aplica strategii speciale pentru variet t,i

diferite de texte, precum rapoartele s,tiint

,i�ce sau tehnice, articolele de s

,tiri, mesajele

e-mail, c rt,i, editoriale etc.

9. Media. Rezumatele pot cont,ine diferite tipuri media (text, audio, tabele, imagini

s,i diagrame, �lme). În sumarizarea multimedia, intrarea s

,i ies

,irea constau într-o

combinare de tipuri media distincte.

În cazul oric rei aplicat,ii, important

,a acestor parametri variaz , depinzând în prin-

cipal de domeniul în care ea va � utilizat s,i c rui tip de grup îi este adresat rezumatul

produs de ea. Este improbabil ca în dezvoltarea unui sistem s se t,in cont de tot

,i

parametrii.

1.1.1 Abord ri

Metodele de baz pentru sumarizare pot � împ rt,ite în dou categorii, în funct

,ie de

proces rile lingvistice utilizate.

1. Abord ri super�ciale2. În cazul acestora nu se merge mai departe de un nivel de

2Shallow approaches

9

Claudiu Mih il

reprezentare a sintaxei propozit,ionale. Este posibil, totus

,i, ca unele cuvinte s �e

analizate s,i semantic. Rezultatul acestor abord ri este de obicei un extract, obt

,inut

prin extract,ia de propozit

,ii. Acest fapt impune îns veri�carea incoerent

,elor care

pot ap rea din cauza extract,iei, rearanj rii textului, referint

,elor anaforice nerezol-

vate etc.

2. Abord ri aprofundate3. Acestea presupun cel put,in un nivel de reprezentare a se-

manticii propozit,ionale. De obicei, aceste sisteme produc abstracte al c ror text

este generat. De aceea obiectivul lor este crearea unui text care s �e coerent,folosind pentru aceasta diverse reguli despre modul în care segmentele de discursse leag între ele.

1.2 Arhitectur abstract pentru sumarizare

Dat �ind prezent,a din ce în ce mai numeroas a surselor de s

,tiri on-line, este de

as,teptat ca informat

,iile cele mai interesante s

,i importante s �e acoperite de majoritatea,

dac nu de toate, sursele. Dac mai multe surse prezint aceeas,i informat

,ie, este evident

c utilizatorul are nevoie de numai una din ele. Dar deoarece aceste informat,ii sunt

modi�cate de un num r mare de ori, într-o perioad scurt de timp, datorit schimb rilorde situat

,ie de dup s

,tirea init

,ial , acest lucru nu este posibil. Scopul unui sistem de

sumarizare inteligent este de a prelua o cantitate cât mai mare de informat,ii de la diverse

surse s,i de a le prezenta concis utilizatorului. De exemplu, dac dou surse distincte

prezint �ecare câte un num r (diferit de cel lalt) de victime ale unui incident, sistemulnu trebuie s aleag între cele dou surse, ci s prezinte contradict

,ia dintre ele, atribuind

�ec rui num r sursa sa.Majoritatea sumarizatoarelor multidocument reus

,esc s extrag propozit

,ii care apar

în mai multe documente (datorit cres,terii semni�cative a gradului de important

, asociat

�ec reia), dar nu reus,esc s identi�ce motivele pentru care propozit

,iile alese sunt similare.

De asemenea, aceste sisteme de sumarizare nu sunt capabile s identi�ce nici diferent,ele

majore. Spre deosebire de acestea, sistemul prezentat în continuare se bazeaz pe iden-ti�carea asem n rilor s

,i contradict

,iilor dintre diferite surse s

,i redarea lor utilizatorului

într-o form concis .În imaginea 1.2, pagina 11, am reprezentat o arhitectur de nivel înalt a unui suma-

rizator. Acesta t,ine cont de unul din parametrii descris

,i în sect

,iunea 1.1, pagina 7, rata

de condensare. Aceasta variaz de obicei între 5% s,i 30%, des

,i au fost folosite s

,i rate de

compresie mai mari sau mai mici.Tot din imaginea 1.2 se observ c procesul de sumarizare este împ rt

,it în trei faze

principale. Aceast idee apare deseori în literatur , precum în [Mani s,i Maybury, 1999],

[Hovy, 2001]:

3Deeper approaches

10


Imaginea 1.2: Arhitectura de nivel înalt a unui sistem de sumarizare

1. Analiz . În aceast faz se analizeaz documentele de la intrare s,i se construies

,te

o reprezentare intern a acestora. Aces,ti doi subpas

,i sunt descris

,i în sect

,iunile 2.2,

pagina 25, respectiv 2.3, pagina 28.

2. Transformare. În aceast faz , numit uneori s,i ra�nare, sunt transformate re-

prezent rile interne ale documentelor originale în reprezentarea intern a rezuma-tului. Faza de transformare este aplicabil de cele mai multe ori sistemelor careproduc abstracte sau care execut compact ri ori rezumate multi-document. Sis-temele care produc extracte dintr-un singur document tind s sar peste aceast faz , direct de la Analiz la ies

,ire. Aceast etap este detaliat în sect

,iunea 1.3,

pagina 12.

3. Sintez . Reprezentarea intern a rezumatului este prelucrat s,i readus în limbaj

natural. Metoda folosit în cazul acestei lucr ri este analizat în sect,iunea 2.5,

pagina 39.

Trebuie notat, totus,i, c granit

,ele dintre aceste trei faze nu sunt bine de�nite. De

exemplu, în [Pinto Molina, 1995] sunt propus,i patru pas

,i succesivi care trebuie îndepli-

nit,i de abstractorii profesionis

,ti: interpretare (care implic citire s

,i înt

,elegere), select

,ia

informat,iei pertinente, necesar utilizatorului, reinterpretarea informat

,iei pertinente s

,i

sinteza rezumatului. Se poate considera, îns , c pasul de reinterpretare face parte dincel de transformare.

Pentru faza de transformare exist în literatur trei operatori de condensare de baz ,pe care un sumarizator trebuie s îi includ . Conform lucr rilor [Mani s

,i Maybury, 1999],

[Mani, 2001], aces,tia sunt:

1. select,ia � �ltrarea elementelor.

11

Claudiu Mih il

2. agregarea � unirea elementelor.

3. generalizarea � înlocuirea elementelor cu unele mai generale/abstracte.

Alt,i operatori, mai complecs

,i, precum parafrazarea sau simpli�carea, pot � exprimat

,i

utilizând operatorii de baz . Operat,iile sunt efectuate pe diverse elemente, precum cu-

vinte, grupuri de cuvinte, propozit,ii sau chiar pe întregul discurs.

1.3 Proces ri

Exist un num r de pas,i care trebuie îndeplinit

,i pentru a putea ajunge la crearea

rezumatului propriu-zis.

1.3.1 Segmentare

Segmentarea textului reprezint procesul de împ rt,ire a textului surs în paragrafe

s,i propozit

,ii. Vom numi un document procesat în aceste fel Docsent (not

,iune preluat

de la [Radev et al., 2004], provenit din cuvintele englezes,ti document s

,i sentence). Un

exemplu de obiect docsent apare în exemplul 1.1, pagina 12.�<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE DOCSENT SYSTEM "docsent.dtd">

<docsent did="41" lang="eng">

<body>

<headline>

<s par="1" rsnt="1" sno="1">Egyptians Su f f e r Second Air Tragedy in a

Year</s>

</headline>

<text>

<s par="2" rsnt="1" sno="2">CAIRO, Egypt −− The crash o f a Gulf Air f l i g h t

that k i l l e d 143 people in Bahrain i s a d i s tu rb ing de ja vu f o r

Egypt ians : I t i s the second plane crash with in a year to devastate t h i s

Arab country .</s>

<s par="2" rsnt="2" sno="3">Sixty−three Egyptians were on board the Airbus

A320 , which crashed in to sha l low Pers ian Gulf waters Wednesday night

a f t e r c i r c l i n g and t ry ing to land in Bahrain .</s>

<s par="2" rsnt="3" sno="4">On Oct . 31 , 1999 , a plane ca r ry ing 217 mostly

Egyptian pas senge r s crashed in to the At l an t i c Ocean o f f

Massachusetts .</s>

<s par="2" rsnt="4" sno="5">The cause has not been determined , prov id ing

no c l o s u r e to the f am i l i e s , whose g r i e f was reopened t h i s month with

the r e l e a s e o f a f a c t u a l r epor t by the Nat iona l Transportat ion Sa fe ty

Board .</s>

</text>

</body>

12


</docsent>� �Exemplul 1.1: Un exemplu de obiect Docsent segmentat la nivel de propozit

,ii.

Aceast împ rt,ire în paragrafe s

,i propozit

,ii este realizat printr-o parcurgere secvent

,i-

al a textului, când se încearc detectarea semnelor de punctuat,ie care pot ar ta sfârs

,itul

unei propozit,ii. Acestea pot � semne simple, precum punctul (.), semnele întreb rii (?)

s,i exclam rii (!), sau semne compuse, precum elipsa (...) sau combinat

,ii de semne ale

întreb rii s,i exclam rii (?!, !?).

O problem care poate ap rea la acest nivel o reprezint abrevierile, care de obiceise termin cu punct. În cazul în care algoritmul nu este preg tit pentru aceast situat

,ie,

el va considera c propozit,ia se sfârs

,es

,te dup abreviere (Mr.) sau chiar în interiorul ei

(U.S.A.). Pentru a dep s,i acest inconvenient, am folosit un corpus de abrevieri disponibil

on-line4, care a servit la veri�carea existent,ei acestora în text. Astfel, ele vor � substituite

astfel încât s nu existe confuzii cu privire la sfârs,itul real al propozit

,iilor. Dup efectuarea

împ rt,irii în propozit

,ii, abrevierile înlocuite anterior vor � readuse la forma init

,ial , textul

�ind p strat în acest fel nealterat.Textul care rezult dup împ rt

,irea în propozit

,ii va � stocat într-un �s

,ier XML.

Etichetele folosite pentru marcare, exempli�cate în exemplul 1.1, pagina 12, au urm -toarele semni�cat

,ii:

• docsent - un document marcat în propozit,ii, care are identitatea did s

,i este scris

în limba lang;

• body - cont,inutul documentului;

• headline - titlul documentului;

• text - cont,inutul propriu-zis al documentului;

• s - o propozit,ie, care apart

,ine paragrafului par s

,i este a rsnt-a propozit

,ie în cadrul

paragrafului s u s,i a sno-a propozit

,ie din textul întreg.

Dup cum se observ din exemplu, consider m c s,i titlul este o propozit

,ie, a�at

într-un paragraf separat, deoarece ofer ideea general a textului, �ind astfel un rezumatde câteva cuvinte al informat

,iilor care urmeaz .

În cadrul dezvolt rii aplicat,iei, am creat o expresie regulat prin care s-a realizat

segmentarea textului în propozit,ii. Cea folosit în acest caz este urm toarea:

(.+?[\.\!\?\n][\"\)]?)(?=(?:\s+[\"\(]?[A-Z]|\s*$))

Expresia permite identi�carea s,abloanelor de text care încep cu majuscul s

,i se ter-

min cu semnele punct, întreb rii, exclam rii sau linie nou . Spat,iile suplimentare de la

începutul sau sfârs,itul propozit

,iilor sunt ignorate. În cadrul propozit

,iilor sunt acceptate

s,i citate (în ghilimele sau apostrofuri � "", �) sau explicat

,ii în paranteze (()).

4http://www.abbreviations.com/

13

Claudiu Mih il

1.3.2 Analiz morfologic

Analizorul morfologic (la nivel de cuvânt) este un modul care marcheaz pentru �ecarecuvânt din text clasa morfologic a acestuia, bazându-se atât pe de�nit

,ia cuvântului, cât s

,i

pe contextul în care apare � în sensul de relat,ia cu alte cuvinte, adiacente, din propozit

,ie,

fraz sau paragraf. Unele analizoare marcheaz s,i apartenent

,a la grupuri sintactice (sub-

stantivale, verbale, adjectivale etc.). Vom numi un document astfel procesat Docpos(not

,iune preluat de la [Radev et al., 2004], provenit din cuvântul document s

,i acron-

imul POS � Part Of Speech). Un exemplu de obiect docpos este inclus în exemplul 1.2,pagina 14.�<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE DOCPOS SYSTEM "docpos.dtd" >

<docpos did="D-19970701_001.e" lang="eng">

<body>

<headline>

<s par="1" rsnt="1" sno="1"> <w c="jj">Solemn</w> <w c="nn">ceremony</w>

<w c="vbz">marks</w> <w c="nnp">Handover</w> </s>

</headline>

<text>

<s par="2" rsnt="1" sno="2"><w c="dt">A</w> <w c="jj">solemn</w><w

c=",">,</w> <w c="jj">h i s t o r i c</w> <w c="nn">ceremony</w> <w

c="vbz">has</w> <w c="vbn">marked</w> <w c="dt">the</w> <w

c="nn">resumption</w> <w c="in">of</w> <w c=="dt">the</w> <w

c="nn">ex e r c i s e</w> <w c="in">of</w> <w c="nn">sove r e i gn ty</w> <w

c="in">over</w> <w c="nnp">Hong</w> <w c="nnp">Kong</w> <w

c="in">by</w> <w c="dt">the</w> <w c="nns">People</w><w c="pos">` s</w>

<w c="nnp">Republ ic</w> <w c="in">of</w> <w c="nnp">China</w><w

c=".">.</w></s>

<s par="3" rsnt="1" sno="3"><w c="prp$">His</w> <w c="nnp">Royal</w> <w

c="nnp">Highness</w> <w c="nnp">The</w> <w c="nnp">Prince</w> <w

c="in">of</w> <w c="nnp">Wales</w> <w c="cc">and</w> <w c="dt">the</w>

<w c="nnp">Pres ident</w> <w c="in">of</w> <w c="dt">the</w> <w

c="nns">People</w><w c="pos">` s</w> <w c="nnp">Republ ic</w> <w

c="in">of</w> <w c="nnp">China</w> <w c="(">(</w><w c="nnp">PRC</w><w

c=")">)</w> <w c="nnp">HE</w> <w c="nnp">Mr</w> <w c="nnp">Jiang</w> <w

c="nnp">Zemin</w> <w c="dt">both</w> <w c="nn">spoke</w> <w

c="in">at</w> <w c="dt">the</w> <w c="nn">ceremony</w><w c=",">,</w> <w

c="wdt">which</w> <w c="vbd">st radd l ed</w> <w c="nn">midnight</w> <w

c="in">of</w> <w c="nnp">June</w> <w c="cd">30</w> <w c="cc">and</w> <w

c="nnp">July</w> <w c="cd">1</w><w c=".">.</w></s>

<s par="4" rsnt="1" sno="4"><w c="dt">The</w> <w c="nn">ceremony</w> <w

c="vbd">was</w> <w c="vbn">t e l e c a s t</w> <w c="jj">l i v e</w> <w

c="in">around</w> <w c="dt">the</w> <w c="nn">world</w><w

c=".">.</w></s>

</text>

</body>

14


</docpos>� �Exemplul 1.2: Un exemplu de obiect Docpos.

Textul care rezult dup atribuirea p rt,ilor de vorbire va � stocat într-un �s

,ier XML.

Etichetele folosite pentru marcarea, exempli�cate în exemplul 1.2, pagina 14, au urm -toarele semni�cat

,ii:

• docpos - un document marcat cu p rt,i de vorbire, care are identitatea did s

,i este

scris în limba lang;

• body - cont,inutul documentului;

• headline - titlul documentului;

• text - cont,inutul propriu-zis al documentului;

• s - o propozit,ie, care apart

,ine paragrafului par s

,i este a rsnt-a propozit

,ie în cadrul

paragrafului s u s,i a sno-a propozit

,ie din textul întreg;

• w - un cuvânt, care apart,ine clasei de p rt

,i de vorbire c;

• c - clasa (partea de vorbire) c reia apart,ine cuvântul; câteva exemple sunt prezen-

tate în tabelul din �gura 1.1, de la pagina 15.

Clas Semni�cat,ie

nn substantivnnp substantiv propriunns substantiv pluraljj adjectivdt articolin prepozit

,ie

cc conjunct,ie

vbn verb modul participiuvbz verb persoana a III-a singularvbd verb timpul trecut

Figura 1.1: Clase de p rt,i de vorbire

Dup cum se observ din exemplu, s,i cuvintele din titlu sunt marcate, ele putând oferi

informat,ii relevante.

1.3.3 Recunoas,terea entit t

,ilor

Recunoas,terea entit t

,ilor (cunoscut s

,i ca identi�carea entit t

,ilor) este o cerint

, a

extract,iei de informat

,ie care încearc s localizeze s

,i s clasi�ce elemente atomice din text

15

Claudiu Mih il

în categorii prede�nite, precum nume de persoane, organizat,ii, locuri, expresii temporale,

cantit t,i, procentaje etc.

Cel put,in dou ierarhii de entit t

,i au fost propuse în literatur . Categoriile BBN5,

propuse în 2002, sunt folosite pentru sistemele de întrebare-r spuns s,i sunt formate din 29

de tipuri s,i 64 de subtipuri. Ierarhia extins a lui Sekine, propus în 2002 ([Sekine, 2003]),

este format din 200 de subtipuri.

Un exemplu de identi�care a entit t,ilor, realizat de un sistem care produce marcarea

în format Message Understanding Conferences, este inclus în exemplul 1.3, pagina 16.�Jim bought 300 share s o f Acme Corp . in 2006 .

<ENAMEXTYPE="PERSON">Jim</ENAMEX> bought <NUMEX

TYPE="QUANTITY">300</NUMEX> share s o f <ENAMEXTYPE="ORGANIZATION">Acme

Corp .</ENAMEX> in <TIMEX TYPE="DATE">2006</TIMEX>.� �Exemplul 1.3: Exemplu de identi�care a entit t

,ilor

Etichetele folosite la marcarea entit t,ilor din exemplul 1.3, pagina 16, precum s

,i valo-

rile atributului type pe care acestea le au, sunt explicate în tabelul din �gura 1.2, pagina16.

Clas Semni�cat,ie

ENAMEX nume de lucruri sau �int,e, concrete sau abstracte

PERSON nume de persoane, reale, legendare sau �ctive, in-clusiv porecle

ORGANIZATION nume de organizat,ii compuse din mai mult de o

persoan NUMEX termeni care exprim valori numericeQUANTITY termeni care exprim cantit t

,i

TIMEX termeni care exprim un punct sau un interval peaxa temporal

DATE termeni care exprim o dat

Figura 1.2: Clase de entit t,i

Sistemele NER6 pot � dezvoltate astfel încât s poat folosi tehnici bazate pe gramaticisau modele statistice. Sistemele bazate pe gramatici dezvoltate manual obt

,in rezultate

mai bune, dar presupun un cost mai mare cel put,in din punct de vedere al timpului

necesar lingvis,tilor experimentat

,i. Sistemele NER statistice au nevoie de o cantitate

foarte mare de date adnotate manual pentru antrenare.

5BBN Technologies (originar Bolt Beranek and Newman)6Named-Entity Recognition

16


1.3.4 Rezolut,ia referint

,elor anaforice

Conform [Mitkov, 2002], o referint, anaforic reprezint o secvent

, lexical (numit s

,i

anafor ), în general realizat printr-un grup nominal, care poate avea diferite interpret ri,în funct

,ie de contextul în care apare. Secvent

,a lexical care determin interpretarea

anaforei, de cele mai multe ori precedându-l pe acesta în text, se numes,te antecedent.

Relat,ia dintre anafor s

,i antecedent poart numele de relat

,ie anaforic . În general, pen-

tru g sirea acestei relat,ii trebuie luate în considerare o gam divers de propriet t

,i mor-

fologice, sintactice s,i semantice ale cuvintelor, în contextul lor de utilizare.

Exist , îns , unele teorii, precum cea din [Halliday s,i Hasan, 1976], în care de�nit

,ia

strict a anaforei include doar referint,ele la entit t

,i anterioare. Continuând sub aceast

de�nit,ie, referint

,ele la entit t

,i ulterioare se numesc catafore, iar situat

,ia în general se

numes,te endofor . De asemenea, este de�nit termenul de exofor , care denumes

,te situa-

t,iile când referint

,a nu se a� în textul în care apare secvent

,a problematic , ci în lumea

real .Urmeaz câteva exemple simple de referint

,e anaforice, în care evident

,iem cazurile

enunt,ate anterior.

The monkey took the banana and ate it.Figura 1.3: Exemplu de referint

, endoforic

Cuvântul it este o referint, anaforic în sensul strict al de�nit

,iei. El se refer la

banan .

What is this?Figura 1.4: Exemplu de referint

, exoforic

Spre deosebire, în exemplul din �gura 1.4 cuvântul this este o referint, anaforic

care poate � considerat exofor , dac nici înainte, nici dup aceast secvent, textul

nu cont,ine elemente care s permit identi�carea cu exactitate a entit t

,ii din spatele

pronumelui this. Pronumele se poate referi la un obiect din preajma vorbitorului sau lao situat

,ie la care el ia parte.

Rezolut,ia acestor referint

,e anaforice reprezint încercarea de a trata aceste situat

,ii care

apar în mod colocvial, adic g sirea elementului la care anafora face referire. Aceastaeste necesar în cazul în care unele propozit

,ii care cont

,in anafore sunt scoase din context.

The Prime Minister of New Zealand visited us yesterday. The visit was the �rst time shehad come to New York since 1998.

Figura 1.5: Exemplu de referint, anaforic

Dac cea de-a doua propozit,ie din exemplul din �gura 1.5 este scoas din context, ea

nu va � înt,eleas pe deplin, în sensul c cititorul nu va s

,ti c she se refer la The Prime

Minister of New Zealand. În urma rezolut,iei, propozit

,ia ar deveni:

17

Claudiu Mih il

The visit was the �rst time the Prime Minister of New Zealand had come to New Yorksince 1998.

Figura 1.6: Exemplu de referint, anaforic rezolvat

Totus,i, exist situat

,ii când, chiar având la dispozit

,ie contextul, complexitatea rezolu-

t,iei cres

,te semni�cativ.

The army was marching towards Golan Heights.The soldiers wanted to get there faster.

Figura 1.7: Exemplu de referint, anaforic complex

În acest caz este mult mai greu s rezolv m referint,ele anaforice. Pe de o parte, este

necesar o înt,elegere semantic a faptului c o armat este format din mai mult

,i soldat

,i.

Pe de alt parte, trebuie cunoscut c un nume de loc poate � la plural.

1.3.5 Coreferint,e între documente

În vederea aplic rii sumariz rii automate asupra unei colect,ii de mai multe documente,

este necesar existent,a unui grad de apropiere în ceea ce prives

,te informat

,ia cont

,inut .

În mod evident, cu cât documentele din colect,ie sunt mai apropiate ca subiecte abordate,

cu atât cres,te probabilitatea ca sistemul s descopere asem n rile.

Rezolvarea acestei situat,ii presupune stabilirea faptului dac dou referint

,e, posibil

�ecare dintr-o surs de informat,ie diferit , trebuie s �e conectate sau nu.

The earthquake was centered on the industrial city of Izmit.Today's quake was centered on Izmit.

Figura 1.8: Exemplu de coreferint,

Trebuie cunoscut faptul c quake este sinonim cu earthquake, c earthquake s,i today's

quake se refer la acelas,i eveniment (fapt foarte important, deoarece cutremurele majore

au replici semni�cative).Între informat

,iile cuprinse în mai multe documente pot exista mai multe tipuri de

relat,ii. Acestea sunt prezentate schematic în �gura 1.9, pagina 19, conform [Radev, 2000],

[Mani, 2001].Situat

,ia diferent

,elor dintre sursele de informat

,ie ridic problema calit t

,ii informat

,iei

� nu toate sursele sunt la fel de credibile. O surs complet plauzibil este greu de g sit,dar cu sigurant

, exist multe surse care sunt neverosimile.

1.3.6 Analiz sintactic

Din cauza ambiguit t,ii substant

,iale care apare în limbajul uman, analizatoarelor sin-

tactice nu le este us,or s parseze propozit

,ii din limbaj natural. Pentru a reus

,i în rezolvarea

acestei probleme este necesar stabilirea gramaticii care va � utilizat .

18


Tipul relat,iei Descriere

identitate Acelas,i text apare în mai multe locat

,ii.

echivalent, Dou unit t

,i de text au acelas

,i cont

,inut de

informat,ie.

traducere Acelas,i cont

,inut informativ în limbi diferite.

incluziune O propozit,ie cont

,ine mai mult informat

,ie decât o

alta.contradict

,ie Informat

,iile sunt con�ictuale.

cadru istoric Informat,ie care pune informat

,ia curent în con-

text.coreferint

, Aceeas

,i referint

, este ment

,ionat în mai multe

locat,ii.

citare O propozit,ie citeaz un alt document.

atribuire O propozit,ie repet informat

,ia dintr-o alta,

ad ugând o atribuire.rezumat O unitate de text sumarizeaz o alta.continuare Informat

,ie adit

,ional , care cont

,ine fapte care au

avut loc dup ultima descriere.elaborare Informat

,ie care nu fusese inclus în ultima de-

scriere.vorbire indirect Schimbarea vorbirii directe în indirect s

,i invers.

ra�nare Informat,ie care este mai speci�c decât cea inclus

anterior.acord O surs exprim acordul cu o alta.îndeplinire O predict

,ie care s-a adeverit.

descriere Introducerea unei descrieri.contrast Contrastarea a dou fapte.paralel Compararea a dou fapte.generalizare Vedere de ansamblu.schimbarea perspectivei Aceeas

,i surs prezint faptele dintr-un alt punct

de vedere.

Figura 1.9: Tipuri de relat,ii între documente

Majoritatea parserelor moderne sunt m car part,ial statistice; cu alte cuvinte, ele se

bazeaz pe un corpus de antrenament, care a fost în prealabil adnotat manual. Aceast metod permite sistemului s creeze statistici privitoare la probabilitatea de aparit

,ie a

anumitor construct,ii lexicale în diferite contexte. Printre metodele care sunt folosite se

num r gramaticile independente de context probabiliste, ret,elele neuronale, entropia

maxim .

1.3.7 Expresii temporale

O expresie temporal este o combinat,ie de evenimente s

,i operatori temporali care de-

scrie un comportament. O expresie temporal exprim relat,ii temporale între evenimente,

19

Claudiu Mih il

valori, variabile sau alt,i itemi.

Conform [Mani et al., 2005], [For scu s,i Ion, 2006], informat

,ia temporal este repre-

zentat în limbajul natural prin:

• expresii temporale exprimate prin grupuri nominale, prepozit,ionale sau adverbiale

� ore (timp al zilei), date, durate: acum s,apte ore, septembrie 1986, anii 90, 29

februarie 2008 etc.; aceste expresii temporale refer timpul ca:

� punct (moment): Am luat cina la ora nou sprezece.

� interval: Maria a lucrat ieri.

• expresii ce denot evenimente exprimate în principal, pe lâng adjective, clauzepredicative sau grupuri frazale prepozit

,ionale, prin:

� propozit,ii, mai exact prin centrul (eng. head) sintactic, anume verbul princi-

pal: George a plecat la mare.

� grupuri nominale: Greva va continua s,i în zilele urm toare.

Expresiile ce denot timpul pot avea:

• referint,e explicite (speci�cate), care refer la o intrare într-un sistem calendaristic

/ orar: amiaz , 11.10.2007 (midday, 11.10.2007 );

• referint,e implicite (sub-speci�cate) - pot � evaluate doar prin intermediul unui timp

indexat: anul viitor, s pt mâna trecut , acum dou ore: În 2007, lunile februaries,i martie au fost foarte ploioase.

• referint,e vagi (nespeci�cate, neancorate), care nu pot � corelate cu un punct sau

interval exact de timp: dup -amiaz , în câteva s pt mâni, acum câteva zile.

Evenimentele exprimate prin verbe pot � temporal ancorate:

• indirect, prin categoria morfologic a timpului s,i

• direct, prin modi�catori adverbiali (adverbe de timp s,i frecvent

, , grupuri nominale

s,i prepozit

,ionale s

,i clauze subordonate).

Pentru a codi�ca toate tipurile de expresii temporale, evenimente s,i relat

,ii între aces-

tea, a fost creat standardul TimeML [Pustejovsky et al., 2006], ale c rui fundamente s-aupus înc din 2002. Standardul reunes

,te multe dintre eforturile anterioare de adnotare

temporal , diferind de acestea prin separarea reprezent rii evenimentelor s,i a expresiilor

temporale de leg turile de ancorare, ordonare sau dependent, ce apar în texte.

Standardul TimeML de�nes,te 7 etichete: EVENT, MAKEINSTANCE (pentru eve-

nimente s,i instant

,e ale acestora � doar instant

,ele vor participa în leg turi temporale),

TIMEX3 (pentru expresii temporale de tip DATE, TIME, DURATION, SET, complet

20


speci�cate, sub- s,i non-speci�cate), SIGNAL (pentru elemente lexicale de leg tur ) s

,i

TLINK, ALINK, SLINK (pentru leg turi temporale, aspectuale s,i respectiv de subor-

donare între expresii s,i evenimente).

1.3.8 Ordonare temporal

Ordonarea temporal a informat,iei este important : dac utilizatorul dores

,te doar

ultimele s,tiri, nu are sens s se rezumeze articole anterioare celor curente, cu except

,ia

cazului în care este nevoie de crearea de context. Totus,i, dac utilizatorul dores

,te o

cronologie de evenimente, atunci informat,iile esent

,iale trebuie prezentate într-o ordine

cronologic , eventual cu suport gra�c de reprezentare a informat,iei de-a lungul unei axe

temporale.

1.3.9 Similaritate cosinus

Conform [Mani, 2001], [Spärck Jones, 2004], unui cuvânt dintr-un document i se poateasocia o pondere tf · idf , o m sur statistic pentru evaluarea important

,ei unui cuvânt

într-un document dintr-un corpus. Important,a cres

,te o dat cu frecvent

,a sa în document,

dar este redus de frecvent,a sa în corpus.

Frevent,a termenului, tf 7, reprezint num rul de aparit

,ii ale termenului în document,

de obicei normalizat la num rul de cuvinte din document, pentru a preveni dezechilibrulcare poate ap rea între documente mai scurte sau mai lungi.

tfi,j =ni,j∑k nk,j

(1.2)

În ecuat,ia 1.2, tfi,j reprezint important

,a termenului i în documentul j, ni,j reprezint

frecvent,a termenului i în documentul j, iar numitorul reprezint num rul total de cuvinte

din documentul j.Frecvent

,a inversat a documentului, idf 8, reprezint important

,a general a termenu-

lui, obt,inut prin logaritmarea, în baza e, a câtului împ rt

,irii num rului total de docu-

mente la num rul de documente care cont,in termenul.

idfi = log|D|

|{dj : ti ∈ dj}|(1.3)

În ecuat,ia 1.3, |D| reprezint num rul total de documente din corpus, iar |{dj : ti ∈

dj}| reprezint num rul total de documente din corpus care cont,in termenul (deci pentru

care nk,j 6= 0).As

,adar, pentru un termen dintr-un document, ponderea tf ·idf a sa ia valori mari dac

termenul are frecvent,a mare în acel document s

,i mic în corpus; în acest fel, cuvintele

7term frequency8inverse document frequency

21

Claudiu Mih il

comune, de leg tur , au ponderile aproape nule.

Utilizând ponderea tf · idf descris mai sus, se obt,ine o metric , numit similaritate

cosinus. Aceasta determin gradul de similaritate dintre dou documente, bazându-sepe formula unghiului dintre doi vectori în plan.

sim(x, y) = N1 +

∑N2

i=1 xiyi∑N2

i=1 x2i

∑N2

i=1 y2i

(1.4)

În ecuat,ia 1.4, xi reprezint ponderea tf ·idf a cuvântului i în propozit

,ia x, yi ponderea

cuvântului i în propozit,ia y, N1 este cardinalul interesect, iei între cuvintele lui x s

,i ale lui

y, iar N2 este num rul total de cuvinte din x s,i y.

1.4 Exemple de sisteme de sumarizare

Pân în prezent au fost create mai multe sisteme de sumarizare, �ecare bazat pe oalt concept

,ie s

,i orientat spre alte nevoi de utilizare.

MEAD, descris în [Radev et al., 2000], este un sistem de sumarizare extractiv, bazatpe centre de greutate (sau centroizi). Acesta atribuie ponderi propozit

,iilor în funct

,ie

de tr s turile s,i relat

,iile lor cu celelalte propozit

,ii, ponderi care denot calitatea lor ca

propozit,ii rezumat. Ulterior alege propozit

,iile cu ponderile cele mai mari s

,i le include în

rezumat. Sistemul MEAD poate rula atât pe documente scrise în limba englez , cât s,i

pe documente în limba chinez .

Sistemul Websumm [Mani s,i Bloedorn, 1999] foloses

,te un model bazat pe grafuri s

,i

opereaz presupunând c nodurile care au gradul cel mai mare cont,in, cu o probabilitate

ridicat , informat,ie care este relevant .

În [Hovy s,i Lin, 1999] este prezentat sistemul Summarist, un sumarizator extractiv

sau abstractiv. Acesta identi�c într-un document ideile principale, le interpreteaz s,i

produce rezumatul documentului.

În lucrarea [Radev et al., 2003] a fost efectuat o evaluare a câtorva sisteme de suma-rizare. Printre acestea se num r MEAD,Websumm s

,i Summarist, descrise succint în

paragrafele anterioare. A fost evaluat corelat,ia relevant

,ei (RC9) rezumatelor obt

,inute

utilizând sistemele ment,ionate fat

, de textul original. Tabelul 1.1, pagina 22, cont

,ine

datele din lucrarea amintit . În mod evident, la compararea documentelor întregi (FD10),valoarea RC este 1,0.

As,a cum se as

,tepta, pe m sur ce lungimea rezumatului cres

,te, el cont

,ine din ce

în ce mai mult informat,ie relevant . Mai mult, performant

,a relativ a diferitelor sis-

teme de sumarizare r mâne aproximativ aceeas,i, pe m sur ce lungimea rezumatului este

modi�cat .

9relevance correlation10full document

22


5% 10% 20% 30% 40%FD 1,000 1,000 1,000 1,000 1,000

MEAD 0,724 0,834 0,916 0,946 0,962WEBS 0,730 0,804 0,876 0,912 0,936SUMM 0,622 0,710 0,820 0,848 0,862

Tabela 1.1: Corelat,ia relevant

,ei în funct

,ie de lungimea rezumatului s

,i sumarizator

Un alt sistem de sumarizare este prezentat în lucrarea [Or ³an s,i Chiorean, 2008].

Acest sistem este unul multilingv, care poate � folosit de vorbitorii de limba englez pentru a accesa s

,tiri din limba român . Sumarizatorul genereaz rezumatele în limba

român , iar acestea sunt traduse ulterior în limba englez folosind un serviciu de tra-ducere automat româno-englez disponibil public. Sistemul se bazeaz pe extract

,ia de

propozit,ii relevante din surs . Evaluând sistemul cu ajutorul judec torilor umani pe baza

rezumatelor în limba englez , autorii au concluzionat c apare o descres,tere a procenta-

jului de întreb ri la care se r spunde corect fat, de procentajul de întreb ri la care se

r spunde corect pe baza rezumatelor în limba român . Acest lucru se datoreaz faptuluic , des

,i rezumatele în limba român cont

,in informat

,ia important , acestea au o structur

complex a frazei, care nu poate � tradus coerent de c tre traduc torul automat utilizat.Solut

,iile imaginate de autori cuprind crearea unui traduc tor mai bun s

,i, în leg tur cu

aceasta, limitarea extract,iei la construct

,ii mai simple, care pot � traduse mai us

,or, deci

mai corect. Din p cate, o aplicare acestor metode va duce la pierderea de informat,ii

importante din rezumat. Totus,i, aceast idee de sumarizare multilingv poate � aplicat

oric ror perechi de limbi, atât timp cât se poate face o traducere dintr-o limb în cealalt .Unul dintre cele mai populare motoare de traducere automat , Google Translate

(http://translate.google.com), permite, în prezent, traduceri pentru 24 de limbi,ceea ce face posibil traducerea între 276 de perechi posibile de limbi.

23

Capitolul 2

Sumarizare aplicat pe corpusurile

MUC

2.1 Arhitectura sistemului

Sistemul dezvoltat are arhitectura descris în imaginea 2.1, pagina 26. Sursele deinformat

,ie ofer articole de s

,tiri, din care, prin prelucrarea oferit de modulul Message

Understanding Conference (MUC), se extrag s,abloanele MUC. Aceste s

,abloane sunt de-

scrise în sect,iunea 2.3, pagina 28. Ulterior, asupra acestor s

,abloane sunt aplicat

,i divers

,i

operatori, care le modi�c sau creeaz s,abloane noi din cele vechi. Modalitatea de aplicare

a operatorilor s,i caracterizarea acestora sunt incluse în secs

,iunea 2.4, pagina 33. Dup

ce nu se mai poate aplica nici un operator, lista de s,abloane este trimis componentei

lingvistice, pe baza c rora se va genera text în limbaj natural, prin metodele explicate însect

,iunea 2.5, pagina 39.

2.2 Colect, ie de documente

2.2.1 Tipuri de documente

Sistemul prezentat în aceast lucrare va avea ca intrare articole de s,tiri. Acest tip

de document a fost ales datorit num rului relativ mare de referint,e temporale pe care

le cuprinde. În plus, informat,iile cont

,inute în aceste articole se modi�c de obicei de

mai multe ori în aceeas,i zi, în cazul celor de actualitate, acest lucru evident

,iind mai bine

capacitatea sistemului de a se focaliza temporal.

Pentru a produce rezumate plauzibile s,i inteligibile, am utilizat corpusuri disponibile

on-line1 drept model. Din analiza corpusului MUC au rezultat unele construct,ii s

,ablon

sau fraze care au fost considerate potrivite pentru a � incluse în tipul de rezumat pe care

1http://www.itl.nist.gov/iaui/894.02/related_projects/muc/index.html

25

Claudiu Mih il

Imaginea 2.1: Arhitectura sistemului

dorim s îl gener m. Cele mai frecvente dintre aceste fraze sunt incluse în �gura 2.2,pagina 28.

Deoarece, prin natura lor, extrasele trebuie s �e concise, scopul sistemului este con-struirea unor rezumate scurte, de un paragraf, care s descrie evolut

,ia unui eveniment în

timp, sau a unor evenimente strâns legate între ele într-un num r mic de propozit,ii. De

un ajutor important este corpusul CSTI2, disponibil la www.berkshirepublishing.com/assets/pdf/pogt/Part4_Chronology.pdf.

2.2.2 Corpusuri utilizate

Aceast sect,iune explic modul în care ne-au ajutat la construct

,ia sistemului cor-

pusurile pe care le-am analizat. Am utilizat articole în special din corpusul MUC 4.Cronologia Incidentelor Teroriste Semni�cante (CSTI) este de asemenea un corpus de-osebit de relevant. Acesta cont

,ine descrieri succinte ale actelor teroriste care au avut loc

între anii 1961 s,i 2005. Am utilizat doar rezumatele evenimentelor din ultimii cât

,iva ani

(2004 � 640 evenimente, 2005 � 114 evenimente pân la 17 august). Fiecare evenimenteste descris printr-un rezumat de numai un paragraf, care, la rândul lui, nu cont

,ine mai

mult de zece propozit,ii. Câteva exemple extrase din CSTI apar în �gura 2.1, pagina 27. În

sect,iunea urm toare vom detalia o parte dintre aceste paragrafe, pentru a ar ta structura

lor.

2Chronology of Signi�cant Terrorist Incidents

26


6 January 2001, Greece. In Athens, press reported an incendiary bomb placed underthe vehicle of a Turkish commercial attache exploded, resulting in no injuries but caus-ing major damage to the car. A group calling themselves the "Crazy Gas Cannisters"claimed responsibility.16 February 2001, Bangladesh. In Rangamati, armed tribesmen at a roadblock, kid-napped two British citizens and two Danes working for a Danish consulting �rm engagedin road work, according to press reports. The driver of the vehicle and one British citizenwere later released to deliver a ransom note to the authorities.1 November 2004, Israel. At the Carmel Market in Tel Aviv, Israel, a suicide bomberdetonated an explosive device, killing three civilians and injuring 30 others. The PopularFront for Liberation of Palestine (PFLP) claimed responsibility.13 December 2004, Gaza Strip. In Ganei Tal, Gaza Strip, unknown attackers �redseveral mortar rounds at an Israeli settlement, seriously wounding a Thai worker andslightly wounding two others. No group claimed responsibility.3 January 2005, Pakistan. In Pakistan, opposition politician Manzoor Hussain Shah,his driver and two bodyguards were shot dead in an ambush, possibly politically moti-vated, on January 3.3 February 2005, India. In India, suspected Maoist rebels are blamed for electionviolence in the Indian states of Jharkhand, Bihar and Haryana. At least 20 people werekilled in several incidents.

Figura 2.1: Exemple de rezumate din corpusul CSTI

2.2.3 Analiza corpusului

Rezumatele din �gura 2.1, pagina 27, urmeaz nis,te tipare bine de�nite. De exemplu,

primul rezumat cont,ine informat

,ii despre un eveniment: un atac adresat unui atas

,at turc,

terminat prin explozia mas,inii s

,i r nirea nici unei persoane, revendicat de un grup terorist.

Dintr-un punct de vedere al discursului, cele dou fraze apart,in unor tipuri diferite. Prima

fraz este cea mai complex . Începe cu o construct,ie care prezint raportorul (presa),

iar ulterior prezint faptul (atacul). Fraza se sfârs,es

,te cu elaborarea atacului (urm rile

acestuia). A doua parte a rezumatului atribuie atacul unui grup.

Cel de-al doilea rezumat cont,ine informat

,ii despre dou evenimente strâns legate între

ele: r pirea a patru persoane s,i eliberarea ulterioar a dou dintre ele. În prima fraz , se

speci�c evenimentul produs s,i se asigneaz responsabilitatea pentru acesta unor oameni

armat,i. De asemenea, se descrie locul de munc al persoanelor r pite s

,i se ofer sursa

informat,iilor. În partea a doua este prezentat un eveniment ulterior, în leg tur cu

primul, eliberarea a dou persoane, s,i se elaboreaz asupra motivului eliber rii (biletul

de r scump rare).

Se observ c propozit,iile care formeaz rezumatele sunt oarecum stereotipice, de

aceea a fost posibil clasi�carea lor în nou categorii, în funct,ie de relat

,iile retorice,

în lucrarea [Radev, 1999]. Aceste categorii sunt exempli�cate în �gura 2.2, pagina 28.Majoritatea propozit

,iilor din rezumatele CSTI se încadreaz în aceste categorii.

27

Claudiu Mih il

Tipul mesajului Exemplu

fapt Three civilians were killed in Baghdad, Iraq onThursday.

asignare responsabilitate BBC reported that a couple of armed men wereresponsible for the death of two civilians.

revendicare responsabilitate Al Qaeda claimed the kidnapping of two Americansoldiers.

raport Reuters reported that the terrorists kidnappedColindra in Guatemala.

total A total of �ve trains were hijacked in Spain inFebruary.

negare responsabilitate Al Qaeda denied responsibility for the kidnapping.nici o responsabilitate No organization claimed responsability for the

bombings.elaborare Three people were killed and �ve were injured in

the incident.descriere Sinn Fein is the political arm of IRA.

Figura 2.2: Exemple de tipuri de mesaje obt,inute din corpus

În urma analizei poves,tilor reale din spatele rezumatelor din �gura 2.1, pagina 27,

am realizat c informat,iile din rezumate provin din una, dou sau mai multe surse.

Explicat,ia acestui fapt este simpl . Atunci când un eveniment terorist are loc, de obicei

primele rapoarte redau locul s,i tipul atacului, însot

,ite de foarte put

,ine (sau chiar deloc)

alte informat,ii, precum rezultatul sau autorii act

,iunii. Astfel de informat

,ii apar mai

târziu, în relu ri ale subiectului. Uneori o surs anunt, c ceea ce s-a difuzat anterior

nu era corect s,i îs

,i actualizeaz datele cu informat

,ii mai noi. De multe ori, surse de s

,tiri

diferite prezint informat,ii complementare (sau chiar contradictorii).

2.3 Modele de reprezentare

2.3.1 Introducere

Problema sumariz rii din mai multe documente impune ca sistemul folosit s �e ca-pabil s fac diferent

,ierea între sursele de informat

,ie curent (central ) s

,i sursele de

informat,ie ontologic .

Sursele de informat,ie curent includ textul ce urmeaz a � sumarizat. Sunt mereu

în form textual (eventual cu unele marcaje HTML, care trebuie îndep rtate în timpulpreproces rii). Aceste informat

,ii curente reprezint fundamentul gener rii rezumatului

de baz . Aceste surse sunt detaliate în sect,iunea 2.3.2, pagina 29.

Sursele de informat,ie ontologic reprezint cunos

,tint

,ele de baz ale sistemului.

Un exemplu bun de astfel de surs este ontologia prezentat în speci�cat,iile s

,abloanelor

28


MUC 43 � aceste ontologii acoper toate valorile posibile ale majorit t,ii câmpurilor

din s,abloanele MUC. De exemplu, valoarea câmpului instrument_type este preluat

dintr-o list ierarhizat prede�nit de arme posibile. Aceste surse sunt detaliate însect

,iunea 2.3.3, pagina 31.

2.3.2 Reprezentarea informat,iei curente

Am folosit o schem de reprezentare a articolelor de s,tiri bazat pe s

,abloanele folosite

în sistemele MUC. Aceasta este exempli�cat în �gura 2.4, pagina 31. Toate dateleextrase din articolele de s

,tiri sunt p strate într-o baz de date de cunos

,tint

,e, marcat

XML. Pentru a putea controla cont,inutul �s

,ierelor XML, am dezvoltat o de�nit

,ie a tipului

de document (DTD)4 s,i am asociat-o �s

,ierelor XML care cont

,in articolele. Aceasta este

descris în �gura 2.3, pagina 30.

S,abloanele MUC clasi�c informat

,ia semnatic extras din articole în cinci mari

grupuri semantice: message, incident, perp, phys_tgt s,i hum_tgt. Din aceleas

,i motive

invocate în lucrarea [Radev, 1999], la acestea cinci ad ug m înc trei grupuri, prim_src,sec_src s

,i now. Procedând în acest fel, �ecare s

,tire este reprezentat sub forma unei

ierarhii, as,a cum este evident

,iat în �gurile 2.5 � 2.8, pagina 32. Drept exemplu, s

,ablonul

prezentat în �gura 2.5, pagina 32, cont,ine cele opt grupuri semantice, unde �ecare

înseamn :

• message � meta-informat,ii despre s

,ablon, precum numele sistemului MUC care

l-a produs.

• incident � informat,iile principale despre eveniment (locat

,ie, tip, dat etc.).

• perp � informat,ii despre r uf c tori (individul infractor sau organizat

,ia infrac-

toare).

• phys_tgt � informat,ii despre t

,intele �zice ale atacului (dac se poate aplica),

precum tipul sau locat,ia lor.

• hum_tgt � informat,ii despre victimele omenes

,ti (dac exist ) � nume, tip,

num r etc.

• prim_src � sursa primar a articolului.

• sec_src � sursa secundar a articolului.

• now � data s,i timpul curente.

3Message Understanding Conferece4Document Type De�nition

29

Claudiu Mih il

<!ELEMENT templates (template+)>

<!ELEMENT template (message, incident, perp, phys-tgt, hum-tgt, prim-src, sec-src)>

<!ELEMENT message (id, number, salience)>

<!ELEMENT incident (date, time, location, type, stage-of-execution, instrument-id+,

instrument-type+)>

<!ELEMENT perp (incident-category, individual-id+, organization-id+,

organization-confidence+)>

<!ELEMENT phys-tgt (id+, type+, number+, foreign-nation, effect-of-incident+,

total-number)>

<!ELEMENT hum-tgt (name+, description+, type+, number+, foreign-nation+,

effect-of-incident+, total-number)>

<!ELEMENT prim-src (source, report, time, date)>

<!ELEMENT sec-src (source, report, time, date)>

<!ELEMENT date (#PCDATA)>

<!ELEMENT location (#PCDATA)>

<!ELEMENT type (#PCDATA)>

<!ELEMENT stage-of-execution (#PCDATA)>

<!ELEMENT instrument-id (#PCDATA)>

<!ELEMENT instrument-type (#PCDATA)>

<!ELEMENT incident-category (#PCDATA)>

<!ELEMENT individual-id (#PCDATA)>

<!ELEMENT organization-id (#PCDATA)>

<!ELEMENT organization-confidence (#PCDATA)>

<!ELEMENT id (#PCDATA)>

<!ELEMENT number (#PCDATA)>

<!ELEMENT foreign-nation (#PCDATA)>

<!ELEMENT effect-of-incident (#PCDATA)>

<!ELEMENT total-number (#PCDATA)>

<!ELEMENT name (#PCDATA)>

<!ELEMENT description (#PCDATA)>

<!ELEMENT source (#PCDATA)>

<!ELEMENT report (#PCDATA)>

<!ELEMENT time (#PCDATA)>

<!ELEMENT salience (#PCDATA)>

Figura 2.3: De�nit,ia tipului de document

Ultimele trei grupuri semantice nu fac parte din s,abloanele MUC originale, ci sunt

ad ugate în cadrul aplicat,iei dezvoltate pentru completare.

Toate valorile posibile pentru toate aceste câmpuri sunt descrise în instruct,iunile

MUC [MUC, 1997]. Deoarece au mai fost ad ugate alte trei grupuri, legate de sursele deinformat

,ie (prim_src s

,i sec_src) s

,i de data s

,i timpul curente (now), potent

,ialele valori

au fost stabilite de noi.

Cele dou noi grupuri care prezint informat,ii legate de sursele de informat

,ie sunt e-

sent,iale pentru descoperirea s

,i raportarea contradict

,iilor, deoarece nu de put

,ine ori exist

con�icte de s,tiri. Pe de alt parte, informat

,iile despre surs redau s

,i nivelul de încredere

în raport, mai ales când unul se schimb pe durata unui timp. De exemplu, dac maimulte surse secundare raporteaz aceleas

,i fapte despre acelas

,i eveniment, citând mai

multe surse primare, este mai probabil ca act,iunea s se � întâmplat în modul raportat.

30


0. MESSAGE: ID (char)

1. MESSAGE: TEMPLATE (int)

2. INCIDENT: DATE (int)

3. INCIDENT: LOCATION (char)

4. INCIDENT: TYPE (char)

5. INCIDENT: STAGE OF EXECUTION (char)

6. INCIDENT: INSTRUMENT ID (char)

7. INCIDENT: INSTRUMENT TYPE (char)

8. PERP: INCIDENT CATEGORY (char)

9. PERP: INDIVIDUAL ID (char)

10. PERP: ORGANIZATION ID (char)

11. PERP: ORGANIZATION CONFIDENCE (char)

12. PHYS TGT: ID (char)

13. PHYS TGT: TYPE (char)

14. PHYS TGT: NUMBER (int)

15. PHYS TGT: FOREIGN NATION (char)

16. PHYS TGT: EFFECT OF INCIDENT (char)

17. PHYS TGT: TOTAL NUMBER (int)

18. HUM TGT: NAME (char)

19. HUM TGT: DESCRIPTION (char)

20. HUM TGT: TYPE (char)

21. HUM TGT: NUMBER (int)

22. HUM TGT: FOREIGN NATION (char)

23. HUM TGT: EFFECT OF INCIDENT (char)

24. HUM TGT: TOTAL NUMBER (int)

25. PRIM SRC: SOURCE (char)

26. PRIM SRC: REPORT (char)

27. PRIM SRC: TIME (char)

28. PRIM SRC: DATE (int)

29. PRIM SRC: DAY (char)

30. PRIM SRC: MONTH (char)

31. PRIM SRC: YEAR (int)

32. SEC SRC: SOURCE (char)

33. SEC SRC: REPORT (char)

34. SEC SRC: TIME (char)

35. SEC SRC: DATE (int)

36. SEC SRC: DAY (char)

37. SEC SRC: MONTH (char)

38. SEC SRC: YEAR (int)

39. INCIDENT: TIME (char)

40. INCIDENT: DAY (char)

41. INCIDENT: MONTH (char)

42. INCIDENT: YEAR (int)

43. NOW: TIME (char)

44. NOW: DATE (int)

45. NOW: DAY (char)

46. NOW: MONTH (char)

47. NOW: YEAR (int)

Figura 2.4: S,ablon MUC 4 gol, extins pentru a include s

,i informat

,ii despre data s

,i

timpul curente, preluat din [Radev, 1999]

Dac în schimb exist multe contradict,ii între rapoarte, este posibil c adev rul s nu �e

înc total cunoscut.

31

Claudiu Mih il

message messageincident incidentperp perpphys_tgt phys_tgthum_tgt hum_tgtprim_src prim_srcsec_src sec_srcnow now

Figura 2.5: Entitate de nivel maxim, incluzând toate cele opt sub-formate. Fiecare s

,tire

este reprezentat în acest mod.

date

day 13month ”December”year 2004

location ”GazaStrip”type ”attack”stage_of_execution ”accomplished”instrument_id ””instrument_type ””

Figura 2.6: Entitate corespunzând sub-formatului incident.

incident_category ”terrorist act”individual_id ”urban guerillas”organization_id ”Nationalist Republican Alliance”organization_confidence ”suspected or accused : Nationalist Republican Alliance”

Figura 2.7: Entitate corespunzând sub-formatului perp.

id ”vehicle”type ”other : vehicle”number 1foreing_nation ””effect_of_incident ”destroyed : vehicle”total_number 1

Figura 2.8: Entitate corespunzând sub-formatului phys_tgt.

2.3.3 Reprezentarea informat,iei ontologice

Informat,ia ontologic din domeniul terorismului internat

,ional este reprezentat folo-

sind limbajele XML. Am utilizat relat,ii de tipul ISA pentru a descrie not

,iuni precum este

isa(gun, weapon). Exemplul 2.1, pagina 32 cont,ine un fragment de ontologie pentru

câmpul instrument-type al s,ablonului. Ontologiile ISA sunt utilizate pentru operatorul

32


de generalizare (sect,iunea 2.4).�

<define name="weapon" elements="gun, explosive"/>

<define name="gun" elements="mortar, machine gun"/>

<define name="explosive" elements="bomb, grenade"/>

<define name="bomb" elements="mine, vehicle bomb"/>� �Exemplul 2.1: Ontologia corespunz toare câmpului instrument-type.

2.4 Sumarizare multidocument

2.4.1 Introducere

Punctul central al sumariz rii multidocument este not,iunea de operator de plani�-

care. Un astfel de operator de plani�care are dou roluri: identi�c relat,iile logice între

formatele din mult,imea pe care lucreaz s

,i asigur c textul generat este corect din punct

de vedere gramatical s,i c acesta cont

,ine doar informat

,iile relevante. Astfel, operatorii

de plani�care lucreaz atât la nivel conceptual, cât s,i la nivel lexical.

2.4.2 Idee de algoritm

Un operatorO este o pereche ordonat (I,A), unde I reprezint condit,ia init

,ial , iarA

reprezint o act,iune. El este aplicat unei liste de formate L. Atunci când condit

,ia init

,ial

I(L) este satisf cut , se creeaz o nou versiune a listei, L', construit prin executareainstruct

,iunilor cont

,inute de act

,iunea A peste L. Altfel, în cazul în care condit

,ia nu este

îndeplinit , L r mâne neschimbat.

L'←

{A(L), dac I(L) satisf cut L, altfel

(2.1)

Datorit construct,iei modalit t

,ii de aplicare a operatorilor, sumarizarea multidocu-

ment poate � v zut ca un pipeline de operatori aplicat,i asupra unei liste init

,iale de

formate. Ies,irea din acest pipeline reprezint rezultatul L'.

L' = Ok(...O2(O1(L))) (2.2)

Distingem dou tipuri de operatori: minimali s,i universali. Un operator minimal

este aplicat numai unei singure perechi de formate (x, y) din lista L pentru care condit,ia

I este satisf cut . De obicei, perechea aleas este cea care are x minim (iar dac exist mai multe perechi cu acelas

,i x minim, alegerea se face în funct

,ie de y). Spre deosebire

de acesta, un operator universal este aplicat tuturor perechilor de formate (x, y) dinlista L pentru care condit

,ia I este satisf cut .

33

Claudiu Mih il

Exemple reale de utilizare a operatorilor identi�cat,i sunt incluse în sect

,iunile care

urmeaz .

2.4.3 Operator de plani�care generic

S consider m un exemplu simplu de operator. Fie L o list compus din dou formateMUC, numerotate 1 s

,i 2. Dorim s compar m valorile câmpurilor template incident-day

din cele dou formate. Dac ziua din cel de-al doilea format este urm toarea dup ziuadin primul format, vrem s fort

, m utilizarea expresiei the next day sau a uneia echivalente

în cel de-al doilea format.

Pentru aceasta, impunem condit,ia de intrare I (prev {template incident-day} {tem-

plate incident-day}). Aceasta este evident satisf cut dac zilele în care au loc incidentelesunt consecutive.

În cazul în care condit,ia init

,ial I este îndeplinit , atunci act

,iunea A asociat acesteia

este efectuat . Pentru acest exemplu, act,iunea ce trebuie executat este introducerea în

cel de-al doilea format a unei noi valori: câmpul {meta incident-day} primes,te valoarea

"on the next day".

Deoarece gramatica de generare a propozit,iilor consider câmpurile "meta" ca având

o prioritate mai mare decât cele "template" omoloage, va genera "on the next day" înlocul zilei care ap rea la început în format.

2.4.4 Taxonomia operatorilor de plani�care

Pentru sumarizarea din mai multe documente, trebuie s identi�c m diferent,ele de la

un articol de s,tiri la urm torul, pentru a evident

,ia cum se schimb datele.

Init,ial avem o list de formate L, asupra c reia aplic m consecutiv un num r de o-

peratori O1, O2, ..., On, pân în momentul în care nu mai poate � aplicat nici un operator(sect

,iunea 2.4.5, pagina 37). La �ecare pas, pe baza similarit t

,ilor dintre formatele din

baza de date se alege un operator de sumarizare. Acesta este ulterior aplicat pe for-matele alese, rezultând un nou format care sintetizeaz informat

,ia din cele vechi. Fiecare

operator este independent de cel lalt s,i mai mult

,i operatori pot � aplicat

,i succesiv pe

formatele de la intrare. Fiecare din cei s,ase operatori de baz sunt divizat

,i pentru a

acoperi multitudinea de modi�c ri posibile.

Un operator de sumarizare stabiles,te leg turi între informat

,iile cont

,inute de dou for-

mate diferite. Uneori, se poate forma o generalizare a dou evenimente diferite. Alteori,sunt marcate deosebirile dintre dou formate, ar tând evolut

,ia evenimentului.

În continuarea acestei sect,iuni descriem clasele de operatori care vor lucra pe formatele

de la intrare. Astfel, oferim o scurt caracterizare a operatorului s,i un exemplu de rezumat

pentru �ecare.

34


2.4.4.1 Schimbarea perspectivei

Când s,tirea init

,ial cont

,ine o informat

,ie gres

,it sau aceasta nu este oferit sub nici o

form , schimbarea este inclus în rezumat. Pentru ca operatorul de schimbare a perspec-

tivei s poat � aplicat, câmpurile source ale formatelor trebuie s aib aceeas,i valoare,

în timp ce valorile unui alt câmp sunt diferite. De exemplu, dac num rul de victimescade fat

, de primul raport, consider m c acela cont

,inea informat

,ii incorecte. Dar dac

acest num r cres,te, spunem c primul raport cont

,inea informat

,ii incomplete.

În exemplul de mai jos, estimarea init,ial de cel put

,in 10 persoane decedate în explozie

devine cel put,in 12 persoane. Prin aceeas

,i modalitate se schimb s

,i num rul de persoane

r nite.

description ”people”type civilian : ”people”number killed: 10

wounded: 30effect_of_incident death: 10

injury: 30sec_src_source "Reuters"

→

description ”people”type civilian : ”people”number killed: 12

wounded: 105effect_of_incident death: 12

injury: 105sec_src_source "Reuters"

Figura 2.9: Schimbarea sub-formatului hum_tgt datorat operatorului de schimbare aperspectivei.

March 4th, Reuters reported that a bomb in Tel Aviv killed at least 10 people andwounded 30. Later the same day, Reuters reported that exactly 12 people were actuallykilled and 105 wounded.

Figura 2.10: Exemplu de schimbare a perspectivei

2.4.4.2 Contradict,ia

Când dou surse distincte raporteaz s,tiri care cont

,in informat

,ii în con�ict (de exem-

plu un num r diferit de victime sau un terorist diferit) apare o contradict,ie. În absent

,a

oric rui indicator de grad de încredere în surse, sistemul nu poate presupune care dinsurse prezint adev rul, as

,a c indic faptul c evenimentele înc nu sunt clare.

Un rezumat provenit de la o surs prezint num rul de persoane decedate ca �ind 20,în timp ce o alt surs a�rm c num rul de persoane decedate este 10. Diferent

,a fat

,

de operatorul anterior, schimbarea perspectivei, o reprezint sursa. Dac anterior aceeas,i

surs îs,i corecteaz rezumatul init

,ial, în acest caz dou surse diferite prezint o variant

proprie, �ecare ne�ind neap rat mai corect decât cealalt . Putem astfel concluziona c ne confrunt m cu o contradict

,ie.

35

Claudiu Mih il

description ”people”type civilian : ”people”number killed: 6-effect_of_incident death: 6-sec_src_source "Reuters"

↔

description ”people”type civilian : ”people”number killed: 5effect_of_incident death: 5sec_src_source "Associated Press"

Figura 2.11: Contradict

,ia dintre câmpurile number.

The afternoon of February 26, 1993, Reuters reported that a suspected bomb killed atleast six people in the World Trade Center. However, Associated Press annouced thatexactly �ve people were killed in the blast.

Figura 2.12: Exemplu de contradict,ie

2.4.4.3 Elaborarea

Când un raport ulterior relateaz aparit,ia unor informat

,ii noi (precum identitatea

atacatorilor sau num rul de victime), aceste informat,ii sut incluse în rezumat printr-o

elaborare asupra rezumatului vechi. Rezultatele adit,ionale pot avea loc dup primul

raport sau pot � cunoscute atunci. Operatorul determin acest caz prin felul în care seschimb valorile formatelor. Dac în cazul primului rezumat câmpul care se refer laidentitatea atacatorilor era necompletat, iar în cel de-al doilea se speci�c cine a comisatacul, se poate aplica operatorul de elaborare.

On Monday, a bomb in Tel Aviv killed at least 10 people and wounded 30 according toIsrael Radio. Later the same day, Reuters reported that the radical Muslim group Hamashas claimed responsibility for the act.

Figura 2.13: Exemplu de elaborare

2.4.4.4 Ra�narea

Nu de put,ine ori informat

,ia prezentat init

,ial este ra�nat în rapoartele ulterioare.

Dac un atac este prezentat mai întâi ca având loc în Atena, ulterior se poate deter-mina cartierul în care s-a întâmplat evenimentul. Dac se cunoas

,te în prim faz doar

nat,ionalitatea atacatorului, mai târziu poate � identi�cat individul prin a�area numelui.Acest operator difer de operatorul de elaborare prin faptul c în formatul init

,ial este

prezent o informat,ie, iar în formatul posterior aceasta este înlocuit cu o informat

,ie mai

exact , mai speci�c .

On Monday, Reuters announced that a suicide bomber killed at least 10 people in TelAviv. Later the same day, Reuters reported that Hamas claimed responsibility for theact.

Figura 2.14: Exemplu de ra�nare

36


2.4.4.5 Acordul

Dac dou surse diferite ofer aceeas,i valoare pentru un câmp, acest fapt va cres

,te

gradul de încredere a utilizatorului în veridicitatea acestuia, s,i de aceea sistemul observ

aceste cazuri s,i le red în rezumat.

The morning of March 1st 1994, UPI reported that a man was kidnapped in Bronx.Later, this was con�rmed by Reuters.

Figura 2.15: Exemplu de acord

2.4.4.6 Agregarea

Dac acelas,i eveniment este raportat de mai multe surse, �ecare cu informat

,ii incom-

plete, este posibil combinarea informat,iei existente cu scopul de a produce un rezumat

cât mai complet. Acest operator este folosit s,i pentru agregarea mai multor evenimente,

dup cum se observ din exemplu.

Reuters reported that 18 people were killed in a Jerusalem bombing Sunday. The nextday, a bomb in Tel Aviv killed at least 10 people and wounded 30 according to IsraelRadio. A total of at least 28 people were killed in the two terrorist acts in Israel over thelast two days.

Figura 2.16: Exemplu de agregare

2.4.5 Algoritm pentru aplicarea operatorilor

În sect,iunea anterioar am prezentat operatorii implementat

,i, iar în sect

,iunea 2.4.2 am

ment,ionat c , pentru a produce un rezumat, aces

,ti operatori trebuie aplicat

,i pe intrare.

Am ales un algoritm greedy pentru aceast parte, descris în algoritmul 2.1, pagina 37.Acesta este adaptat, urmând linia general din lucrarea [Radev, 1999].

Algoritmul 2.1 Aplicarea operatorilor de plani�care

sorteaz lista L în ordine cronologic

repeat

caut în lista de operatori unul care se potrives,te cu elementele curente din L

if ∃ O operator then

aplic act,iunea A a operatorului O lui L pentru a produce L'

endif

until nu mai pot fi aplicat,i operatori

trimite L' componentei lingvistice

Algoritmul utilizat poate � descris dup cum urmeaz .

37

Claudiu Mih il

2.4.5.1 Intrare

În acest pas, sistemul primes,te o list de formate Message Understanding Confer-

ences, apart,inând unui anumit domeniu. Toate formatele sunt reprezentate ca liste de

perechi atribut�valoare. Aceste perechi sunt descrise în instruct,iunile MUC-4 s

,i au fost

exempli�cate anterior, în �gurile 2.4�2.8, de la paginile 31�32.

2.4.5.2 Combinare euristic

Baza de date creat din formatele primite la pasul anterior este scanat pentru iden-ti�carea relat

,iilor relevante dintre valorile diferitelor atribute. Astfel de relat

,ii conduc

la reordonarea formatelor s,i la modi�carea gradului de important

, asociat �ec ruia. De

asemenea, în urma aplic rii unei variat t,i de operatori, pot � create formate noi, având ca

fundament o pereche de formate existent în baza de date. Drept exemplu, dac asupraunei perechi de formate se aplic operatorul de ra�nare, formatul nou obt

,inut va avea

gradul de important, mai mare decât suma gradelor de important

, ale formatelor vechi.

În acelas,i timp, gradele de important

, ale formatelor de baz sunt decrementate cu o

anumit valoare (ment,inând îns un grad de important

, mai mare pentru cel de-al doilea

format, având în vedere c este considerat �mai corect� decât primul).Valoarea gradului de important

, a mesajului determin pozit

,ia pe care acesta o va

avea în paragraful rezumat. Astfel, un mesaj cu gradul de important, mai mare va �

generat printre primele, iar unul cu gradul de important, mai mic va � generat printre

ultimele mesaje.Fiecare nou format cont

,ine informat

,ii care indic utilitatea ulterioare a formatelor

sale constituente. Aceste pot deveni învechite s,i nu vor mai � folosite. De asemenea,

vectorul de acoperire (strucur de date care ret,ine care formate au fost deja combinate s

,i

care mai sunt înc disponibile pentru aplicarea operatorilor) este actualizat, astfel încâtacesta s refere mesajele înc active s

,i care pot � combinate în continuare. În acest fel,

se ofer o s,ans �ec rui format de a participa la crearea rezumatului.

2.4.5.3 Ordonarea formatelor s,i generarea lingvistic

Pentru ca textul �nal s �e produs, sistemul realizeaz urm torii pas,i:

• Formatele sunt ordonate descresc tor dup gradul de important, asociat �ec ruia.

Numai primele formate din lista creat vor � prelucrate s,i se vor reg si, în limbaj

natural, în rezumat. Mesajele cu un grad de important, mai mare apar prioritar

într-un rezumat în cazul unei restrict,ii de lungime a rezumatului.

• Luate în ordine temporal cresc toare, se decide ce fel de propozit,ie va � contruit

pe baza formatului curent. Astfel, în funct,ie de relat

,ia cu propozit

,i anterioar , în

ceea ce prives,te sursa s

,i câmpurile care cont

,in informat

,ii despre incident, infractori,

38


t,inte, se stabiles

,te tipul propozit

,iei. În tabelul din �gura 2.17, pagina 41, sunt

descrise tipurile de propozit,ii utilizate.

2.5 Generarea limbajului natural

2.5.1 Introducere

Conform [Bateman, 1997], generarea de propozit,ii este procesul computat

,ional prin

care se produc automat propozit,ii într-un limbaj uman pe baza unei speci�cat

,ii sau

intent,ii de comunicare. O component de generare a propozit

,iilor primes

,te ca intrare o

speci�cat,ie a ceea ce trebuie s comunice s

,i produce la ies

,ire o expresie în limbaj natural

corespunz toare.

Generarea de limbaj natural este un subiect foarte amplu s,i un domeniu extrem de

discutat. Utilizând generarea de limbaj natural a fost posibil crearea unei variet t,i de

diferite aplicat,ii practice, precum prognoze meteorologice, rapoarte ale bursei de act

,iuni,

reclame multilingve, rapoarte statistice etc.

Primul pas spre generarea limbajului natural este stabilirea unui scop comunicativ s,i

a unei reprezent ri structurate a informat,iei care se dores

,te a � comunicat în limbaj na-

tural. Datele pot exista sub form de tabele, s,abloane, concepte într-o baz de cunos

,tint

,e

sau expresii logice care exprim astfel de concepte.

În cele ce urmeaz vom prezenta succint câteva metode de generare de limbaj natural,în sect

,iunea 2.5.2, pagina 39. Apoi vom descrie metoda aleas pentru actualul sistem de

sumarizare, în sect,iunea 2.5.3, pagina 41.

2.5.2 Metode de generare a limbajului natural

În literatur au fost propuse numeroase c i de realizare a limbajului natural având doarcâteva date ca intrare. În continuare sunt descrise succint trei dintre cele mai frecventemetode. Cea de-a patra metod a fost aleas pentru generarea limbajului natural pentrusistemul prezentat în aceast lucrare s

,i este detaliat în sect

,iunea 2.5.3, pagina 41.

Graph uni�cation tools

FUF5[FUF, 2000] este un interpretor scris în CommonLisp, pentru un limbaj bazatpe uni�care funct

,ional , dezvoltat special pentru aplicat

,ii de generare de text. SURGE6

este o gramatic de generare de text în limba englez , scris în FUF. FUF a fost dezvoltatde c tre Michael Elhadad, iar SURGE a fost dezvoltat de Michael Elhadad, împreun cuJacques Robin.

5Functional Uni�cation Formalism6Syntactic Realization Grammar for Text Generation

39

Claudiu Mih il

Unitatea de baz a FUF este descrierea funct,ional (FD7), care este utilizat la de-

scrierea atât a intr rii, cât s,i ies

,irii unei gramatici. O FD este de�nit ca o îns

,iruire

de perechi atribut-valoare, unde valoarea poate � un atom (o valoare lingvistic ), o cale(o leg tur c tre o alt sect

,iune a gramaticii) sau o alt descriere funct

,ional . Dup

ce se creeaz o list de astfel de descrieri, se adaug constrângeri (de exemplu, pen-tru propozit

,iile secundare) s

,i sunt completate rolurile lexicale ale elementelor. Ulterior,

folosind gramatica SURGE, este generat textul în limbaj natural.

Exist mai multe sisteme bazate pe combinat,ia FUF/SURGE, precum Summons

[Radev, 1999].

Gramatici sistemice funct,ionale

Gramaticile sistemice funct,ionale reprezint un model de gramatici dezvoltate de

Michael Halliday înc din anii 1960. Termenul "sistemic" se refer la vizualizarea uneilimbi ca o ret

,ea de sisteme, sau mult

,imi interrelat

,ionate de opt

,iuni pentru a crea un

înt,eles. Termenul "funct

,ional" este folosit pentru a se indica faptul c aceast metod

este interesat de înt,eles.

Gramaticile sistemice funct,ionale se preocup în principal cu alegerile care sunt dispo-

nibile vorbitorilor unei limbi de sistemele lor gramaticale. Înt,elesurile într-o gramatic

sistemic funct,ional se împart în trei categorii, numite metafunct

,ii: ideat

,ional (gra-

matic pentru reprezentarea lumii), interpersonal (gramatic pentru descrierea relat,iilor

sociale) s,i textual (gramatic pentru legarea elementelor lingvistice în texte, prin pronu-

minalizare, topic , tem etc.).

Metoda gramaticilor sistemice funct,ionale a fost folosit înc din 1965 pentru gene-

rarea limbajului natural. Înc de atunci s-au descris s,i construit numeroase sisteme de

sumarizare, pentru domenii foarte diferite, de la articole de s,tiri, pân la statistici pentru

jocuri de X s,i 0. Unul dintre cele mai utilizate sisteme este KPML, descris în lucrarea

[Bateman, 1996].

Generator statistic

O alternativ la generatoarele bazate pe gramatici o reprezint generatoarele statistice,precum Nitrogren [Langkilde s

,i Knight, 1998]. Acest sistem utilizeaz un num r de

reguli, al turi de lexicon, pentru a mapa reprezentarea semantic a intr rii pe o mult,ime

de secvent,e posibile de cuvinte. Aceast mult

,ime este reprezentat ca o latice, o diagram

cu tranzit,ii de st ri. Un generator de propozit

,ii bazat pe corpus va prelua laticea de

cuvinte s,i va genera propozit

,ia care are scorul cel mai bun, în funct

,ie de statisticile

corpusului. Atractiv datorit faptului c nu necesit dezvoltarea unei gramatici, pentruaceast metod este nevoie de antrenament pe un corpus. Totus

,i, acest tip de sistem

7Functional Description

40


permite generarea de propozit,ii chiar s

,i atunci când o parte din informat

,ia pentru intrare

lipses,te.

S,abloane de text

Pentru aceast metod se creeaz o mult,ime de s

,abloane de propozit

,ii, parametrilor

s,abloanelor �indu-le atribuit valoarea prin instant

,ierea intr rii. Aceast metod este

discutat în am nunt în sect,iunea 2.5.3, pagina 41.

2.5.3 S,abloane de text

În �gura 2.17, pagina 41, sunt incluse câteva din s,abloanele propozit

,iilor utilizate

pentru generarea rezumatului. Acestea au fost construite folosind categoriile de propozi-t,ii identi�cate în rezumatele corpusului CSTI8, prezentate anterior, în �gura 2.2, pagina28.

Tipul propozit,iei S

,ablon

fapt On <date>, <source> reported that, in <location>,<perpetrator>, pertaining to <organization>,<stage-of-execution> <type-of-incident> tar-geting <physical-target>, where <human-target>

were found. This <incident-category> resulted in<effect-of-incident>.

elaborare On <date>, <source> speci�ed that ...contradict

,ie However, <source> informed that ...

acord <source> con�rmes these facts.

Figura 2.17: S,abloane de propozit

,ii

Pentru o mai mare diversitate, cuvintele �xate (care nu depind de sursele de infor-mat

,ie) sunt alese aleatoriu dintr-o list de sinonime prede�nit . Astfel, am utilizat o

ontologie, descris sub forma unui �s,ier marcat XML, în care speci�c m cuvintele sino-

nime. O parte a acestei ontologii este exempli�cat în �gura 2.18, pagina 41.

Categorie Sinonime

change-view however, on the other handsame-day later, later the same day, later on, a few hours laternext-day the next day, one day after, the second dayreport reported, announced, speci�ed, informed, mentioned,

saidagree agrees with the fact, con�rmes

Figura 2.18: Tipuri de sinonime

8Chronology of Signi�cant Terrorist Incidents

41

Claudiu Mih il

Deoarece s,abloanele sunt bazate pe existent

,a câtorva ontologii, sistemul poate � cu

us,urint

, adaptat pentru orice limb .

42

Capitolul 3

Rezultate

3.1 Evaluare uman

Scopul acestui sistem este de a vedea dac sumarizarea multidocument focalizat temporal poate facilita într-adev r accesul mai rapid la o informat

,ie corect . As

,adar,

este necesar s determin m performant,a metodei de sumarizare implementate. În aceast

sect,iune evalu m metoda folosit pentru producerea rezumatelor.

3.1.1 Organizare

Pentru a putea evalua sistemul de sumarizare prezentat pân acum, am ales dincorpusul utilizat un num r de cinci subiecte. Aceste subiecte se refer la incidente teroristeimportante care au avut loc în lume s

,i care au fost mediatizate intens de agent

,iile de s

,tiri.

În �gurile 3.1�3.5, de la paginile 43�44, sunt incluse rezumatele care au fost selectatepentru evaluare.

On February 2, Reuters reported that in Guatemala, Santo Tomas (farm), Guerilla Co-lumn, pertaining to Guatemalan National Revoluationary Unity, accomplished an attacktargeting Presidential Farm, where President Cerezo, and Civilian were found. Thisterrorist act resulted in the death of more Civilian.However, France-Press mentioned that this terrorist act resulted in the death of 10 Civi-lian, injury of Cerezo.The next day, Reuters reinformed that this terrorist act resulted in the death of 3 Civilian.

Figura 3.1: Rezumatul 1

On November 20, Reuters reported that, in El Salvador, unknown perpetrators, accom-plished an attack targeting Jesuits. This act resulted in death of more Jesuits.


43

Claudiu Mih il

On February 17, Reuters reported that, in El Salvador, San Salvador (city) , Members ofthe Farabundo Marti National Liberation Front, pertaining to Farabundo Marti NationalLiberation Front, accomplished an attack targeting Electric Power Substation, whereSoldier were found. This terrorist act resulted in injury of Soldier.


On August 29, Reuters reported that, in Colombia, Antioquia (department), Man, andWoman, attempted a bombing targeting Antioquia Liqueur Plant, where People werefound. This terrorist act resulted in no human victims or they are not mentioned.


On December 20, Reuters reported that, in Bolivia, La Paz (city), Unidenti�ed person,pertaining to Zarate Willka Armed Forces Of Liberation, accomplished a bombing tar-geting Embassy, Book store, People's Peruvian Bank, State Bank, Mariscal BallivianBuilding, and Shops. This terrorist act resulted in no human victims or they are notmentioned.


Pentru a putea decide dac sumarizarea multidocument focalizat temporal produs de sistemul prezentat în aceast lucrare faciliteaz într-adev r accesul mai rapid la oinformat

,ie corect , am supus comparat

,iei un es

,antion format din cinci rezumate unor

judec tori umani. Am ales pentru aceasta dou rezumate care au fost corect generate,unul de calitate medie s

,i dou slabe din punct de vedere al informat

,iei selectate, al

coerent,ei s

,i coeziunii textului.

Evaluarea rezumatelor este o problem care este în continu dezbatere s,i cercetare în

domeniul sumariz rii automate. Judecata uman nu este precis în aceea ce prives,te un

rezumat bun, s,i de ceea evaluarea lor nu poate � automatizat complet. Aceast evaluare

este un proces foarte di�cil, datorit faptului c nu exist numai un rezumat "perfect",ci o multitudine de rezumate la fel de acceptabile, din care sistemul trebuie s produc unul. Totus

,i, des

,i oamenii nu pot c dea de acord asupra rezumatului care este mai bun,

este destul de probabil ca ei s cad de acord în ceea ce prives,te un rezumat care nu

este corect. Incoerent,a, gres

,elile gramaticale (sintactice s

,i semantice) s

,i redundant

,a sunt

identi�cate us,or de oameni, iar aceasta duce la o notare mai slab a acestor rezumate.

Evaluarea manual este o opt,iune viabil , care este înc des utilizat , cu toate c aceast

metod este consumatoare de timp s,i munc , deoarece este necesar ca oamenii s citeasc

nu numai rezultatul sumariz rii, dar s,i documentele surs .

Dintre metodele de sumarizare disponibile, am ales s utiliz m o evaluare bazat pecerint

,e, în care judec torii umani au fost nevoit

,i s r spund unor întreb ri cu r spuns

multiplu, pe baza textelor care le-au fost puse la dispozit,ie. La o parte dintre aceste

întreb ri se putea alege un r spuns de forma Da/Nu, în timp ce altele aveau mai multer spunsuri posibile. Pentru ambele tipuri de întreb ri a fost introdus s

,i o variant de

r spuns suplimentar , Nu s,tiu, pentru cazurile în care judec torii umani nu puteau decide

44


care este r spunsul corect pe baza rezumatului. Un exemplu de întrebare Da/Nu estecel din �gura 3.6, pagina 45, iar unul pentru întreb rile cu r spuns multiplu este cel din�gura 3.7, pagina 45.

Was president Cereso killed in the attack at the predisential farm in Santo Tomas,Guatemala?

• Yes

• No

• I don't know

Figura 3.6: Întrebare cu r spuns Da/Nu

What organization were the attackers who tried to kill Cerezo in Santo Tomas, Guatemalapart of?

• Al-Qaeda

• URNG

• IRA

• FMNLF

• I don't know

Figura 3.7: Întrebare cu r spuns multiplu

Calitatea rezumatelor a fost m surat prin raportarea num rului de întreb ri la cares-a r spuns corect la num rul total de întreb ri adresate judec torilor.

Qi =qi,c

qi,a

(3.1)

unde Qi reprezint calitatea rezumatului i, qi,c reprezint num rul de întreb ri la care s-ar spuns corect pentru rezumatul i, iar qi,a num rul total de întreb ri asociate rezumatuluii.

Pe lâng aceste cinci rezumate, au mai fost evaluate s,i rezumate realizate de oa-

meni s,i rezumate de referint

, . Pentru metoda rezumatelor de referint

, am extras prima

propozit,ie din articolele surs pân când a fost atins lungimea dorit . Am luat decizia

de a include s,i rezumate realizate prin aceast modalitate bazându-ne pe faptul c , de

obicei, prima propozit,ie a articolelor de s

,tiri este cea care reprezint un rezumat su�cient

de bun al textului.Rezumatele produse de oameni au fost create cu scopul de a stabili o limit superioar

a metodei de sumarizare descrise în aceast lucrare. Din cauza lipsei de timp, în realizarea

45

Claudiu Mih il

rezumatelor a fost utilizat o manier extractiv (propozit,iile au fost extrase din text s

,i

concatenate, f r a � alterate sau conectate în vreun fel de rezumatori). De asemenea,trebuie ment

,ionat c rezumatele s

,i întreb rile pentru evaluare au fost produse de dou

persoane diferite.

3.1.2 Evaluarea rezultatelor

Pentru evaluare, �ecarui din cei cinci judec tori i s-au oferit rezumatele s,i �ecare a

fost rugat s r spund întreb rilor pe baza lor. Mai mult, judec torii au fost rugat,i s

r spund întreb rilor numai pe baza rezumatelor s,i nu pe baza cunos

,tint

,elor anterioare

despre evenimentele în cauz . Rezultatele r spunsurilor sunt incluse în tabelul 3.1, pagina46.

Dup cum se as,tepta, procentajele cele mai mari sunt cele pentru cazul rezumatelor

create de oameni, iar cele mai mici pentru cazul rezumatelor de baz . Spre surprindereanoastr , au existat cazuri în care rezumatele scrise de oameni au avut mai put

,ine r spun-

suri corecte decât cele create automat. Acest lucru se datoreaz faptului c persoanacare a creat rezumatul a considerat ca importante alte idei decât persoana care a creatîntreb rile.

Uman Baz AutomatR1 80% 46% 64%R2 60% 30% 60%R3 56% 30% 66%R4 48% 22% 52%R5 64% 26% 34%

Media 62% 30% 55%

Tabela 3.1: Evaluarea rezumatelor de c tre judec tori umani

3.1.3 Evaluarea coerent,ei

Pe lâng sarcina de a r spunde la întreb rile despre subiectele din sursele de infor-mat

,ie, �ecare din cei cinci judec tori a fost rugat s acorde câte o not pe o scar de

la 1 la 5 (1 însemnând foarte slab, iar 5 foarte bun) �ec rui din cele cinci rezumate.Rezultatele, precum s

,i mediile notelor pentru �ecare rezumat, sunt prezentate în tabelul

3.2, pagina 47.Dup cum se observ din tabel, rezumatele create de oameni obt

,in procentajul cel mai

ridicat, des,i persoana care le-a creat nu a produs rezumate coerente în mod deliberat.

Explicat,ia pentru acest fapt este c rezumatorul uman a ales o anumit mult

,ime de

evenimente importante din grup s,i a selectat propozit

,iile legate de acel eveniment. În

acest fel, propozit,iile se leag mult mai bine decât cele din cazul sumariz rii automate.

46


Uman Baz AutomatR1 4 2 3,8R2 3,8 1,8 3,6R3 3,6 2,2 3,4R4 3,2 2 3R5 3,6 2 3,6

Media 3,64 2 3,48

Tabela 3.2: Evaluarea coerent,ei rezumatelor de c tre judec tori umani

Rezumatele de baz au obt,inut din nou punctajul cel mai mic. Aceste rezultate sunt

similare celor din tabelul 3.1, pagina 46, as,a cum este ilustrat gra�c în imaginea 3.1,

pagina 47.

Imaginea 3.1: Corelat,ia evalu rilor

3.2 Evaluare automat

ROUGE1, diponibil gratuit on-line2, este un pachet creat pentru evaluarea rezu-matelor s

,i a evalu rilor lor. Include mai multe metode care m soar similaritatea dintre

rezumate:

• ROUGE-N � bazat pe funct,ia recall pe n-grame

• ROUGE-L � bazat pe subsecvent,a comun maximal

• ROUGE-W � extensie a ROUGE-L, în care subsecvent,ele primesc ponderi

1Recall-Oriented Understudy for Gisting Evaluation2http://berouge.com/

47

Claudiu Mih il

• ROUGE-S � statistici de coocurent,e ale bigramelor neadiacente

Am utilizat pentru evaluare metoda ROUGE-N, care este funct,ia recall n-gram dintre

rezumatul candidat s,i o mult

,ime de rezumate de referint

, . Conform [Lin, 2004], formula

de calcul a acestei m suri este

ROUGE −N =

∑S∈{ReferenceSummaries}

∑gramn∈S Countmatch(gramn)∑

S∈{ReferenceSummaries}∑

gramn∈S Count(gramn)(3.2)

unde n este lungimea n-gramei, gramn, iar Countmatch(gramn) este num rul maxim den-grame care apar atât în rezumatul candidat, cât s

,i în cele de referint

, .

Trebuie observat c num rul de n-grame de la numitorul formulei 3.2 cres,te pe m -

sur ce sunt ad ugate noi rezumate de referint, . Acest lucru este intuitiv s

,i rezonabil,

deoarece pot exista mai multe rezumate bune. De �ecare dat când este ad ugat o nou referint

, în mult

,ime, se extinde spat

,iul de rezumate alternative. Prin controlarea tipului

de rezumate care sunt incluse în mult,imea de referint

, , se pot obt

,ine diferite evalu ri fo-

calizate pe aspecte distincte ale sumariz rii. De asemenea, num r torul însumeaz pestetoate rezumatele de referint

, . Acest lucru ofer mai mult greutate n-gramelor care apar

în mai multe rezumate de referint, . As

,adar, un rezumat candidat care cont

,ine cuvinte

care sunt reg site în mai multe rezumate de referint, este favorizat de m sura ROUGE-N.

Din nou, s,i acest lucru este intuitiv deoarece în general se prefer un rezumat care este

cât mai similar cu toate cele de referint, .

În tabelul 3.3, pagina 48, sunt prezentate scorurile obt,inute folosind m sura ROUGE-

2 pentru cele cinci rezumate. Au fost comparate rezumatul obt,inut din sistemul actual

s,i rezumatul uman.

ROUGE-2R1 0,18R2 0,14R3 0,12R4 0,1R5 0,14

Media 0,136

Tabela 3.3: Scoruri ROUGE-2

48

Capitolul 4

Concluzii s, i perspective

În aceast lucrare am prezentat un sistem de sumarizare automat multi-document,care este focalizat pe modi�c rile suferite în timp de articolele de s

,tiri, pentru limba

englez . Acesta foloses,te abstract

,ia ca metod de sumarizare, extr gând cuvintele sau

grupurile de cuvinte importante s,i reformulând, într-un mod foarte concis, ideea textului

init,ial.

Pentru a se putea ajunge la partea de sumarizare propriu-zis , este necesar exe-cutarea unor operat

,iuni pe corpusul pe care se va lucra. Astfel, în texte trebuie marcate

propozit,iile s

,i p rt

,ile de vorbire ale cuvintelor sau grupurilor de cuvinte, trebuie rezolvate

construct,iile ambigue, produc toare de confuzie, precum referint

,ele anaforice, referint

,ele

inter-documente, expresiile temporale.

Folosind baza de date s,i metoda de adnotare a articolelor de s

,tiri ment

,ionat în

speci�cat,iile Message Understanding Conference, sistemul poate produce rezumate prin

aplicarea de operatori precum schimbarea perspectivei, acordul sau generalizarea. Aces,ti

operatori modi�c gradele de important, asociate s

,abloanelor MUC, iar în acest fel se

stabiles,te o ierarhie a informat

,iilor care prezint interes.

Generarea textului în limbaj natural a fost efectuat prin utilizarea s,abloanelor de

text. Aceast metod este avantajoas prin gradul de coerent, crescut caracteristic

viitorului rezumat. Utilizarea ontologiilor de sinonime permite crearea de construct,ii

diverse, care scad stereotipia sumarelor.

Sistemul a fost evaluat cu ajutorul not rii a cinci rezumate de c tre cinci judec toriumani din punct de vedere al informat

,iei cont

,inute s

,i al coerent

,ei textelor obt

,inute.

Notele acordate de aces,tia arat faptul c sistemul produce sumare foarte similare celor

umane, selectând informat,ia interesant s

,i formulând aproape corect gramatical propozi-

t,iile. De asemenea, utilizând sistemul de evaluare automat a rezumatelor, ROUGE, aufost con�rmate concluziile evalu rii umane.

Urm torul pas în dezvoltarea sistemului prezentat poate � crearea de ontologii înlimba român , astfel încât s poat � extrase rezumate s

,i din articole de s

,tiri românes

,ti.

În mod evident, o expansiune a sistemului prin ad ugarea de ontologii în orice alte limbi

49

Claudiu Mih il

este la fel de interesant .O alt direct

,ie este cea a dezvolt rii unui sumarizator translingv. Datorit gradului

de coerent, ridicat al rezumatelor produse de acest sistem s

,i, de asemenea, complexit t

,ii

reduse a sintaxei frazelor utilizate, textele pot � traduse în alte limbi cu o acuratet,e mare,

dac se foloses,te un sistem de traducere automat performant.

Mai mult, se poate continua cu dezvoltarea de s,abloane corespunz toare altor domenii

decât cel al articolelor de s,tiri dedicate atacurilor teroriste. Sunt enumerate mai jos câteva

dintre posibilit t,ile de abordare viitoare:

• Domeniul legislativ � se pot crea rezumate în limbaj natural, în care s se prezintelegile noi, legile abrogate sau modi�c rile aduse legilor existente.

• Domeniul sportiv � în rezumate se poate descrie evolut,ia unei echipe într-o anumit

perioad de timp, sau se pot descrie evenimentele desf s,urate pe parcursul unei

competit,ii.

• Domeniul �nanciar � cursul valutar sau tranzact,iile efectuate la bursa de va-

lori prezint un interes major în prezent, as,adar un sumarizator poate furniza pe

scurt variat,iile suferite de anumite entit t

,i (moned , act

,iuni, obligat

,iuni, dobând ,

in�at,ie etc.).

• Domeniul medical � istoricul medical al unui pacient este de o foarte mare utilitatemedicilor în diagnosticarea s

,i tratarea bolilor în mod corect.

50

Mult,umiri

Mult,umim colegilor student

,i care au creat rezumate s

,i seturi de întreb ri, care au

acordat note celor cinci rezumate s,i celor care au r spuns chestionarului, ajutând astfel

la evaluarea �nal a sistemului.De asemenea, suntem recunosc tori autorului sistemului de evaluare ROUGE, Chin-

Yew Lin, pentru permisiunea de a-i utiliza programul.[Cristea et al., 2005] [Marcu s

,i Gerber, 2001] [Marcu, 1997]

51

Bibliogra�e

[Bateman, 1996] John Bateman. KPML Development Environment: multilingual linguis-tic resource development and sentence generation. Raport tehnic, German NationalCenter for Information Technology (GMD), Institute for integrated publication andinformation systems (IPSI), Darmstadt, Germania, 1996.

[Bateman, 1997] John Bateman. Sentence generation and systemic grammar: an intro-duction, 1997.

[Cristea et al., 2005] Dan Cristea, Oana Postolache s,i Ionuµ Pistol. Summarisation

through Discourse Structure. În Alexander Gelbukh, editor, Computational Linguis-tics and Intelligent Text Processing, 6th International Conference CICLing, Mexic,februarie 2005.

[For scu s,i Ion, 2006] Corina For scu s

,i Radu Ion. TIMEBANK 1.2: O versiune adnotat

în limba român . În Corina For scu, Dan Tu�³ s,i Dan Cristea, editori, Lucr rile

atelierului Resurse lingvistice ³i instrumente pentru prelucrarea limbii române, Ia³i,3 noiembrie 2006.

[FUF, 2000] Functional Uni�cation Formalism Interpreter, 2000,http://www.cs.bgu.ac.il/fuf/index.html vizitat la 10 iunie 2008.

[Halliday s,i Hasan, 1976] Michael Alexander Kirkwood Halliday s

,i Ruqaiya Hasan. Co-

hesion in English. Longman, Londra, 1976.

[Hovy s,i Lin, 1999] Eduard Hovy s

,i Chin-Yew Lin. Automated Text Summarization in

SUMMARIST. În Inderjeet Mani s,i Mike Maybury, editori, Advances in Automatic

Text Summarization, paginile 81�94. The MIT Press, 1999.

[Hovy, 2001] Eduard Hovy. Automated text summarisation. În Ruslan Mitkov, editor,Handbook of Computational Linguistics, Oxford, 2001.

[Langkilde s,i Knight, 1998] Irene Langkilde s

,i Kevin Knight. Generation that Exploits

Corpus-Based Statistical Knowledge. În Proceedings of the 36th Annual Meeting ofthe Association of Computational Linguistics and the 17th International Conferenceon Computational Linguistics (COLING-ACL'98), New Brunswick, New Jersey, 1998.Association of Computational Linguistics.

53

Claudiu Mih il

[Lin, 2004] Chin-Yew Lin. ROUGE: A Package for Automatic Evaluation of Summaries.În Proceedings of Workshop on Text Summarization Branches Out, Post-ConferenceWorkshop of ACL 2004, Barcelona, Spania, 2004. Association of Computational Lin-guistics.

[Mani s,i Bloedorn, 1999] Inderjeet Mani s

,i Eric Bloedorn. Summarizing Similarities and

Di�erences Among Related Documents. Information Retrieval, 1(1-2):35�67, aprilie1999.

[Mani s,i Maybury, 1999] Inderjeet Mani s

,i Mark Maybury. Advances in Automatic Text

Summarization. MIT Press, Cambridge, Massachusetts, 1999.

[Mani et al., 2005] Inderjeet Mani, James Pustejovsky s,i Robert Gaizauskas. The Lan-

guage of Time: A Reader. Oxford University Press, mai 2005.

[Mani, 2001] Inderjeet Mani. Automatic Summarization. John Benjamins PublishingCompany, Amsterdam/Philadelphia, 2001.

[Marcu s,i Gerber, 2001] Daniel Marcu s

,i Laurie Gerber. An Inquiry into the Nature of

Multidocument Abstracts, Extracts and Their Evaluation. În Jade Goldstein s,i Chin-

Yew Lin, editori, Proceedings of the ANLP '01/NAACL '01 Workshop on AutomaticSummarization, Pittsburgh, Pennsylvania, SUA, iunie 2001. Association for Computa-tional Linguistics.

[Marcu, 1997] Daniel Marcu. From Discourse Structures to Text Summaries. În Proceed-ings of the ACL'97/EACL'97 Workshop on Intelligent Scalable Text Summarization,Madrid, 1997. Association for Computational Linguistics.

[Mitkov, 2002] Ruslan Mitkov. Anaphora Resolution. Longman, 2002.

[MUC, 1997] MUC 4. În Proceedings of the fourth Message Understanding Conference(MUC 4). DARPA Software and Intelligent Systems Technology, 1997.

[Or ³an s,i Chiorean, 2008] Constantin Or ³an s

,i Oana Andreea Chiorean. Evaluation

of a Cross-lingual Romanian-English Multi-document Summariser. În Proceedings ofthe 6th International Language Resources and Evaluation Conference 2008, Marrakech,Maroc, 26 mai � 1 iunie 2008. European Language Resources Association.

[Pinto Molina, 1995] María Pinto Molina. Documentary abstracting: Toward a method-ological model. Journal of the American Society for Information Science, 46(3):226�232, 1995.

[Pustejovsky et al., 2006] James Pustejovsky, Marc Verhagen, Roser Sauri, JessicaLittman, Robert Gaizauskas, Graham Katz, Inderjeet Mani, Robert Knippen s

,i Andrea

Setzer. TimeBank 1.2. Linguistic Data Consortium, Philadelphia, 2006.

54


[Radev et al., 2000] Dragomir Radev, Hongyan Jing s,i Malgorzata Budzikowska.

Centroid-Based Summarization of Multiple Documents: Sentence Extraction, Utility-Based Evaluation, and User Studies. În Proceedings of the Workshop on AutomaticSummarization at the 6th Applied Natural Language Processing Conference and the1st Conference of the North American Chapter of the Association for ComputationalLinguistics, Seattle, S.U.A., aprilie 2000.

[Radev et al., 2003] Dragomir Radev, Simone Teufel, Horacio Saggion, Wai Lam, JohnBlitzer, Hong Qi, Arda Çelebi, Danyu Liu s

,i Elliott Drabek. Evaluation challenges

in large-scale document summarization. Annual Meeting � Association for Computa-tional Linguistics, 41(1):375�382, aprilie 2003.

[Radev et al., 2004] Dragomir Radev, Timothy Allison, Sasha Blair-Goldensohn, JohnBlitzer, Arda Çelebi, Stanko Dimitrov, Elliott Drabek, Ali Hakim, Wai Lam, DanyuLiu, Jahna Otterbacher, Hong Qi, Horacio Saggion, Simone Teufel, Michael Topper,Adam Winkel s

,i Zhu Zhang. MEAD - a platform for multidocument multilingual text

summarization. În Language Resources and Evaluation Conference 2004, Lisabona,Portugalia, mai 2004.

[Radev, 1999] Dragomir Radev. Generating Natural Language Summaries from MultipleOn-Line Sources: Language Reuse and Regeneration. Tez de doctorat, ColumbiaUniversity, 1999.

[Radev, 2000] Dragomir Radev. A common theory of information fusion from multipletext sources, step one: Cross-document structure. În Proceedings 1st ACL SIGDIALWorkshop on Discourse and Dialogue, New Jersey, 2000. Association for ComputationalLinguistics.

[Sekine, 2003] Satoshi Sekine. Sekine's Extended Named Entity Hierarchy, 27 februarie2003, http://nlp.cs.nyu.edu/ene/ vizitat la 10 iunie 2008.

[Spärck Jones, 2004] Karen Spärck Jones. A statistical interpretation of term speci�cityand its application in retrieval. Journal of Documentation, 60(5):493�502, 2004.

55

Date post:	02-Sep-2019
Category:	Documents
Upload:	others
View:	6 times
Download:	0 times