. Rezolutia Anaforei

CUPRINS

ARGUMENT

A învăța să comunici cu calculatorul poate schimba modul în care înveți alte lucruri. (Seymour Papert)

Oamenii sunt fără nici un dubiu cele mai inteligente ființe. Relațiile dintre oameni se bazează pe comunicare, mai ales pe limbaj. Care este relația dintre inteligență și limbaj? Cum contribuie limbajul la inteligență? Dar ce este inteligența? Sunt numai câteva întrebările la care filozofii sau oamenii de știință au încercat să răspundă.

Oamenii și-au dorit din totdeauna să construiască mașini „inteligente” care să le ușureze viața și să comunice cu ele eventual prin limbaj natural.

În prezent calculatoarele (și roboții) sunt considerate cele mai „inteligente” mașini, dar ele sunt departe de a fi atât de inteligente precum și-au dorit oamenii.

În încercarea de a crea inteligență artificială informaticienii au „programat” calculatoarele să imite oamenii: le-au „dotat” cu cunoștințe dintr-un domeniu anume și cu un algoritm pentru o funcție asociată, sperând ca rezultatele calculatorului să egaleze sau depășească rezultatele oamenilor în acel domeniu. O tendință actuală în informatică este de a transforma calculatorul pentru a permite realizarea dialogului dintre om și calculator în maniera cea mai naturală – limbajul. De această problemă se ocupă Lingvistca computațională, ramură a Inteligenței artificiale.

Rezoluția anaforei este o problemă clasică de lingvisitică computațională și are un rol vital într-un număr mare de aplicații de prelucrare a limbajului natural cum ar fi traducerea automată, abstractizarea automată, extragerea de informații și răspunderea la întrebări.

INTRODUCERE

Comunicarea este esența științei. (Bachelard)

Această lucrare este despre rezoluția automată a anaforei, o problemă esențială în înțelegerea limbajului natural de către calculatoare. Anafora este un fenomen studiat atât de lingvistica computațională cât și de cea clasică ce a atras atenția multor cercetători în ultimii ani. Teorii și formalisme ca teoria centrelor, teoria structurilor retorice au inspirat noi cercetări legate de rezoluția automată a anaforei. În plus, aplicațiile orientate spre cercetare ca abstractizarea automată, extragerea de informații au identificat, independent, importanța rezoluției anaforei.

Am prezentat rezoluția anaforei pentru limba engleză deoarece pentru această limbă sunt mai multe unelte de prelucrare a limbajului (WordNet, parsere, etc.) necesare unui program de prelucrare a limbajului. Exemplele sunt de asemenea în limba engleză pentru înțelegerea problemelor specifice limbii engleze referitoare la anaforă.

În primul rând va fi explicat de ce înțegerea limbajului natural de către calculator este o problemă atât de dificilă, cum ar trebui abordată, ce presupune analiza unui text și de ce este rezoluția anaforei importantă. În Capitolul I vor fi prezentate câteva noțiuni teoretice necesare înțelegerii lucrării. În Capitolul II este explicat cum funcționează și cum se evaluează un algoritm pentru rezoluția anaforei; sunt prezentați algoritmi clasici și tendințele actuale. Capitolul III este dedicat descrierii unui sistem pentru rezoluția automată a anaforei – GenFrame. În capitolul IV este descris și evaluat modelul propus de mine pentru a rezolva problema anaforei. Ultima parte este rezervată concluziilor și sugestiilor.

De ce este atât de dificil pentru calculatoare să înțeleagă limbajul natural?

Înțelegerea limbajului natural este o sarcină dificilă pentru calculatoare. Principala dificulate rezultă din faptul că limbajul natural este ambiguu. Oamenii reușesc să înțeleagă informațiile pe care le primesc cu ajutorul „mecanismelor de inteligență” cu care sunt dotați. Complexitatea acestora îi ajută să proceseze informațiile și să facă asocierile necesare descifrării acestora. Calculatorul nu reușește să găsească sensul unei informații dintr-un set de interpretări posibile deoarece „cunoștințele” sale sunt limitate și el este incapabil să le integreze în contex.

Ambiguitatea poate apărea la nivel lexical pentru că sunt cuvinte care au mai multe sensuri (bank, file, chair), dar și la nivel sintactic când sunt posibile mai multe analize structurale (I saw the man with the telescope). Mai mult ambiguitate este și la nivelul semantic (The rabbit is ready for lunch – unde rabbit poate fi interpretat și ca agent și ca subiect) sau la nivel pragmatic (Can you open the window? – poate fi interpretată și ca intrebare dar și ca rugăminte în funcție de situație). Rezolvarea automată a ambiguității presupune existența unei cantități imense de cunoștințe lingvistice și nelingvistice precum și capacități de învățare și inferare. De aceea este o problemă care poate fi rezolvată doar pentru un domeniu restrâns.

Nivelele analizei lingvistice

Un sistem de prelucrare a limbajului natural necesită cunoștințe despre limbaj, inclusiv identificarea cuvintelor, modul de aranjare a cuvintelor în propoziții, sensul cuvintelor și modul în care sensul lor individual se combină pentru a da înțeles propoziției. La un nivel superior, trebuie să știe să identifice propoziții într-un text, să stabilească relații între ele, etc. Pentru ca un sistem de prelucrare automată a limbajului natural să fie capabil să înțeleagă limbajul ca oamenii, ar trebui să aibă cunoștințe (world and domain knowledge) cât și capacități de raționare.

Un program NLU (Natural Language Understanding) ar trebui să fie capabil să stabilească relații între diferite părți ale unei propoziții sau ale unui text.

Fie următorul text:

This book outlines the state of the art of anaphora resolution. It discusses the complexity of this NLU task.

(Această carte subliniază satutul de artă al rezolvării anaforei. Discută complexitatea acestei probleme NLU.)

Ruslan Mitkov, Anaphora Resolution

Pentru a prelucra text-ul sunt necesare următoarele etape și cunoștințe:

Analiza morfologică și lexicală pentru a identifica cuvintele, clasa lexicală (partea de vorbire) și derivările posibile; sunt necesare cunoștințe morfologice și lexicale sub forma unor reguli și dicționare (pentru acronisme de exemplu).

→ This va fi identificat ca determinant; book ca substantiv, etc.

Despărțirea în propoziții.

Analiza sintactică pentru a despărți propozițiile în componenți sintactici (grupuri nominale, grupuri verbale, etc) și aplicarea de reguli gramaticale: this book, the state of the art, anaphora resolution vor fi recunoscute ca grupuri nominale, iar outlines the state of the art of anaphora resolution ca grup verbal;

Analiza semantică va determina sensul fiecărui cuvânt și cum cuvintele se leagă unele de altele; cunoștințele necesare sunt de obicei dicționare sau ontologii: verbul outline necesită un agent, și anume o persoană sau o lucrare scrisă iar subiectul acțiunii ar trebui să fie o problemă, un eveniment, un domeniu, etc.

Pentru ca textul să fie înțeles o etapă a analizei textului ar fi determinarea legăturilor anaforice: programul ar trebui să determine că it din a doua propoziție referă this book și că this NLU task referă anaphora resolution.

Importanța rezoluției anaforei pentru alte aplicații NLP

Interpretarea anaforei este vitală pentru succesul unui sistem de traducere automată. În particular, când se traduce dintr-o limbă pentru care pronumele au forme diferite pentru fiecare gen în altă limbă care nu are forme diferite este esențială găsirea relațiilor anaforice. Doar un număr limitat de sisteme de traducere automată reușesc să traducă cu succes un discurs, nu doar propoziții izolate, pentru că nu rezolvă problema anforelor. [Wada, 1990], [Leass & Schwall, 1991], [Nakaiawa et al, 1994], [Saggion & Carvalho, 1994], [Mitkov et al., 1997], [Geldbach, 1997] sunt proiecte care au obținut rezultate încurajatoare legate de rezoluția anaforei pentru traducerea automată.

Relația de coreferință are un rol important și pentru extragerea de informații. [Al-Kofani et al., 1999] este sistem ce folosește rezoluției anaforei pentru extragerea și prelucrarea de informații.

În domeniul sumarizării textelor tehnicile de extragere a propozițiilor mai importante au rezultate mai bune dacă sunt folosite și relații anaforice. Lanțurile coreferențiale și coreferința au fost folosite pentru abstactizare. [Baldwin & Morton, 1988], [Azzam, Humphreys & Gaizauskas, 1999] descriu tehnici de sumarizare a textelor folosind lanțurile coreferențiale.

Rezoluția coreferinței dintre documente este importantă pentru sumarizarea inter-document. (de exemplu algoritmul [Bagga & Baldwin, 1998] )

Găsirea automată a răspunsurilor la întrebări este ajutată mult de găsirea coreferințelor. [Morton, 1999] găsește răspunsuri la întrebări prin stabilirea de legături coreferențiale între entitățile și evenimentele din întrebări și cele din document.

Alte aplicații folosesc rezoluția anaforei pentru obținerea unor rezultate mai bune (de la 92,6% la 97%) în învățarea automată a unor diferite structuri ([Charniak, 2001]), verificarea corectitudinii traducerii ([Canninq et al., 2000])

CAPITOLUL I – Referințe teoretice

Tot ceea ce e mai bun în lume este ceea ce produce gândul. (Hegel)

Primul capitol este o prezentare a anaforei și a conceptelor asociate. Prezintă fenomenul de coreferință și clasificarea anaforei.

Discursul

Un text nu este numai un șir de semne grafice, după cum un discurs vorbit nu e numai un șir de sunete. Pentru a urmări un text sau o cuvântare, expunere utilizăm reprezentări mentale, integrând o anumită cunoaștere despre lume pe care o aveam cu ceea ce ne este comunicat. Textul adesea referă entități din lumea reală, fie ele entități fizice, entități conceptuale, ori evenimente. Pe măsură ce discursul avansează, aceste entități se transformă, își modifică trăsăturile ori se îmbogățesc cu trăsături noi, participă în alte evenimente, uneori dispar, apar altele noi. Un text se transformă în discurs doar atunci când cineva îl citește sau ascultă. Când acest personaj începe să citească sau să asculte, în mintea lui începe un proces de asocieri și evocări, de inferențe și de construcții de entități. Un discurs nu poate fi rupt de procesul citirii sau al ascultării lui. Discursul trebuie asociat momentului interpretării lui și nu poate fi confundat cu notația lui grafică.

Coerența și coeziunea textului

Coerența unui text reprezintă acea calitate a lui de a manifesta o inter-relaționare satisfăcătoare între elementele lui cât și între ceea ce el comunică și ceea ce știe deja cititorul, informația este prezentată într-un manieră și o ordine logică, acestea toate atribuindu-i un înțeles, ce poate fi ușor desprins.

Coeziunea unui text este proprietatea ca părțile lui să fie legate într-un mod care să le dea calitatea de întreg.

Când un text nu este coerent? Ceea ce pare incoerent într-un anumit context, sau în lipsa unui context, poate căpăta înțeles atunci când un context particular îi este asociat. Nu este vorba despre lipsa de înțeles a propozițiilor (de genul celebrului exemplu al lui Chomsky Colourless green ideeas sleep furiously), ci de combinații de propoziții, care deși independent pot avea sens, să apară incoerente luate împreună.

Centrele

Un segment de discurs este o secvență de enunțuri în care se vorbește despre ceva ori cineva: lucruri, idei, evenimente, fenomene, persoane – în general entități semantice. Într-un spațiu situațional aceste entități au fiecare câte o reprezentare semantică. În teoria centrelor (CT) [Grosz, Joshi and Weinstein, 1995] acestea sunt numite centre. Ele sunt indexate în text în general prin grupuri nominale. Dar nu oricărui grup nominal îi corespunde un centru.

Ex. Polițistul părăsi în grabă postul de observație pentru a începe o urmărire ca-n filme.

Următoarelor secvențe lexicale le corespund centre: polițistul, postul de observație, o urmărire. Este dificil a spune dacă secvențelor lexicale grabă și filme le sunt de asemenea atașate centre pentru că expresia în grabă este o sintagmă cu valoare adverbială (repede, grăbit) iar ca-n filme este una cu valoare a) iar ca-n filme este una cu valoare adjectivală (aventuroasă, palpitantă). Pentru recunoașterea secvențelor cu valoare referențială putem considera ca criteriu normalitatea de referire în text a unei entități despre care s-a vorbit deja.

Din punct de vedere reprezentațional centrele sunt structuri de caracteristici. Un fapt semnificativ este că centrele pot fi interpretări parțiale care ulterior să capete caracterizări suplimentare.

Grup nominal (NP), grup verbal

Capul lexical (head-ul) unei expresii este acel cuvânt al construcției care luat singur poate împlini funcția întregii expresii. Intuiția în spatele noțiunii de head este că fiecare constituient sintactic conține un anumit cuvânt (numit cap lexical – lexical head) considerat a fi definitoriu pentru grup pentru că el determină multe dintre proprietățile sintactico-morfologice ale grupului luat ca un întreg. De exemplu head-ul grupului cel mai frumos măr este măr pentru că întregul grup preia proprietățile gen și număr de la acesta.

Grup nominal (notat NP de la noun phrase – în limba engleză) este o expresie a cărei head este un substantiv.

Grup verbal (notat VP) îndeplinește rolul unui verb simplu și este alcătuit din verb principal și elemente auxiliare (verbe auxiliare, adverbe, etc.) care formează împreună o singură unitate sintactică și semantică. Cel mai adesea un grup verbal îndeplinește funcția de predicat.

Anafora

Numim anáforă o relație de referință, în text, între două entități. Vom numi cele două elemente ale textului care participă în anaforă – expresii referențiale.

“Anafora reprezintă relația dintre un termen (numit "anafor") și un altul (numit "antecedent"), când interpretarea anaforului este într-un anumit mod determinată de interpretarea antecedentului.” (Barbara Lust, introducere la Studies in the Acquisition of Anaphora, D. Reidel, 1986)

“Termenul de relație anaforică este utilizat pentru a marca relația dintre două elemente din text care denotă același obiect” (Massimo Poesio, What is ‘coreference’?)

“În majoritatea textelor obiectul aflat în discuție este menționat de mai multe ori, iar ceea ce este nou introdus în text este legat într-un fel sau altul de ceea ce s-a discutat deja. Menționările ulterioare ale unei entități pot avea sau nu aceeași formă de suprafață. Există o întreagă clasă de expresii, numite expresii anaforice sau expresii referențiale utilizate pentru a indica elementele aflate în corelație. Ele mai sunt considerate și entități lexicale.” (S. Davies, M. Poessio, Coding Schemas for Co-reference, 2000)

Relația dintre cei doi termeni ce participă la realizarea unei anafore poate fi diversă. Cea mai comună este anafora coreferențială, în care entitatea referită în contextul universului de discurs este aceeași pentru ambii termeni. Așa cum vom vedea mai jos, dacă însă anaforul și antecedentul referă entități distincte, dar aflate, ele însele, într-o anumită relație atunci avem de-a face cu o anaforă funcțională.

Relația dintre anafor și antecedent nu trebuie confundată cu cea dintre anafor și referentul său. De obicei referentul este o entitate din lumea reală, în timp ce antecedentul este o formă lingvisitcă.

Relația anaforică trebuie înțeleasă ca fiind amorsată de cei doi termeni lexicali dar având loc într-un plan semantic, exterior textului. În nici un caz ea nu este o relație între elemente de text. La modul general o anaforă este formată dintr-o pereche de referințe text-situație, deci de realizări, în care antecedentul este entitatea textuală anterioară anaforului cea mai recentă ce realizează același centru ca și anaforul:

Fig. 1: Triada

anafor-antecedent-centru

Într-o schemă simplificatoare, ce scurt-circuitează traiectoria situațională, o relație anaforică poate fi evidențiată numai la nivelul textului. O astfel de reprezentare este doar una convențională, simplificatoare, pentru că relația anaforică este de natură semantică, nu textuală. O manieră de a nota o relație anaforică este prin indici pe text, anaforul și antecedentul purtând aceiași indici (așa cum va fi notată în exemplele din această lucrare).

Anafora se clasifică în funcție de forma anaforului și în funcție de componenta semantică a relației anaforice

Diferite tipuri de anaforă în funcție de forma anaforului

Anafora pronominală

Este cel mai întâlnit tip de anaforă. Pronumele este reprezentantul numelui în enunț [Irimia, 1997]. Cel mai adesea el dă formă anaforei coreferențiale, în care anaforul este un pronume iar antecedentul este realizat printr-un grup nominal.

Pronume personale:

Ex. 1: The most difficult for Dali1 was to tell her, between two of nervous laughter, that he1 loved her.

(Cel mai dificil lucru pentru Dali a fost să-i spună, între două râsete nervoase, că el o iubește )

Gilles Neret, Dali

Pronume posesive:

Ex. 2: But the best things about Dali1 are his2 roots and his1 antennae. (Dar cele mai bune lucruri la Dali sunt rădăcinile sale și simțurile sale)

Gilles Neret, Dali

Pronume reflexive:

Ex. 3: Dali1 once again locked himself1 in his studio… (Dali încă o dată s-a închis în studioul său…)

Gilles Neret, Dali

Pronume demonstrative:

Ex. 4: Dali, however, used photographic precision to transcribe the images of his dreams1. This1 would become one of the constraints of his work…

(Dali, în orice caz, folosea o precizie fotografică pentru a transcrie imaginile din visurile sale. Aceasta va deveni una din constrângerile operei sale…)

Gilles Neret, Dali

Spre deosebire de exemplele de până acum, aici antecedentul este o întreagă propoziție, mai corect – o reprezentare a evenimentului comunicat de propoziție.

Pronume relative:

Ex. 5: Dali1,a Catalan who1 was addicted to fame and gold, paited a lot and talked a lot.

(Dali, un catalan care era dependent de faimă și aur, a pictat mult și a vorbit mult.

Gilles Neret, Dali

În limba engleză setul de pronume anaforice este alcătuit din toate pronumle la persoana a III-a – pronume personale, posesive, reflexive, demonstrative, relative la singular și plural. Pronumele personale la persoana I și a II-a sunt folosite într-o manieră diaclitică. Pronumele it poate fi adesea neanaforic. Identificarea automată a pleonastului it în limba engleză nu este o sarcină ușoară. În următorul exemplu pronumele it nu specifică suficient pentru a fi considerat anaforic:

Ex. 6: It is dangerous to be beautiful – that is how women have learned shame.

(Ø este periculos să fii frumoasă, astfel au învățat femeile ce este rușinea.)

John Updike, Brazil

Anafora substantivală definită

Dacă anaforul este realizat printr-un grup nominal definit, avem de a face cu o anaforă substantivală definită. Deși și pronumele sunt considerate expresii definite, doar grupurile nominale au înțeles independent de antecedentul lor. Expresiile definite fac mai mult decât doar să refere, ele aduc informații adiționale.

În general, articolul hotărât atașat unui substantiv îi atribuie caracteristica semantică de identitate specifică, cunoscută deja. Cunoașterea lui se poate datora introducerii lui în text într-un moment precedent:

Ex. 7: I bought a book1. The book2 is verry interesting.

(Am cumpărat o carte. Cartea este foarte interesantă)

O expresie definită acționează deci și într-un sens și în celălalt: o situație comună este referită, iar o situație nouă primește calificativul de comună.

Invers, un substantiv articulat definit nu denotă însă întotdeauna o referință punctuală, spre o entitate bine precizată. Se poate spune:

Ex. 8: Take the bus. (Ia autobuzul)

deși pot exista mai multe autobuze care să poată fi luate. Referința este spre un obiect din clasa autobuz, fără ca acesta să fie precizat.

Anafora substantivală nedefinită

Când anaforul este un grup nominal nearticulat avem de a face cu o anaforă nedefinită. De cele mai multe ori un grup nominal nearticulat introduce o nouă entitate în discurs (exemplu 7 în care este introdusă o entitate printr-un substantiv nearticulat referit apoi printr-un substantiv articulat). Uneori însă o anumită relație anaforică, care nu e una de coreferențialitate, se poate stabili printr-un anafor nedefinit, ca de exemplu introducerea unei entități de aceeași natură ca una deja menționată:

Ex. 9: What beautifull house1! A house2 like this1 is hard to find. (Ce casă frumoasă! O casă ca asta e greu de găsit)

Prima mențiune house introduce aici o entitate. A doua mențiune house introduce o entitate din aceeași clasă semantică, însă diferită de prima. Pronumele this referă prima entitate.

Anafora vidă (elipsa)

Anaforele vide sunt anafore „invizibile” – la prima vedere nu se văd deoarece ele nu sunt reprezentate textual printr-un cuvânt sau o propoziție. Din moment ce una din proprietățile și avantajele anaforei este abilitatea de a reduce cantitatea de informație spre a fi reprezentată printr-o formă lingvistică abreviată, elipsa este poate cea mai sofistificată varietate a anaforei. Se notează cu Ø.

Există mai multe tipuri de elipse. Cea mai întâlnită este anafora vidă pronomială care are loc atunci când un pronume anaforic este omis dar este subînțeles. Acest fenomen se întâlnește în limba engleză în împrejurări foarte restrânse, dar este comun în alte limbi cum ar fi româna, spaniola, italiana, poloneza, portugheza, japoneza.

Ex. 10: Zero pronomial anaphora occurs when the anaphoric pronoun is omitted but Ø is nevertheless understood.

(Elipsa se produce când pronumele anaforic este omis, dar Ø totuși este înțeles)

Ruslan Mitkov,Anaphora Resolution

În a treia propoziție se aștepta but it is nevertheless understood.

Alt tip de elipsă este elipsa textuală (numită și anaforă funcțională):

Ex. 11: Starea acumulatorului îi este indicată utilizatorului. Înainte cu 30 minute de descărcarea completă, calculatorul semnalizează pentru 5 secunde.

Strube & Hahn, 1996

Descărcarea completă este o prescurtare pentru descărcarea completă a acumulatorului. Între [descărcarea acumulatorului] și [acumulator], entitățile referite de anafor și antecedent, respectiv, există o relație de proprietate: un acumulator are proprietatea de a se descărca, după cum are proprietatea de a se încărca.

Anafora propozițională

Anafora propozițională este anafora pentru care anaforul este o propoziție În exemplul 12 this referă o situație a cărei realizare lexicală este o întreagă propoziție, (Dali, however, used photographic precision to transcribe the images of his dreams) La nivelul situațional trebuie găsită o reprezentare a evenimentului descris de frază.

Ex. 12: Dali, however, used photographic precision to transcribe the images of his dreams1. This1 would become one of the constraints of his work…

(Dali, în orice caz, folosea o precizie fotografică pentru a transcrie imaginile din visurile sale. Aceasta va deveni una din constrângerile operei sale…)

Gilles Neret, Dali

Tipuri de anaforă în funcție de semantică

Coreferința

Cea mai simplă relație anaforică este aceea în care atât anaforul cât și antecedentul realizează direct același centru. Relația este în acest caz numită coreferință.

Fig. 2: Relația anaforică coreferențială

Ex.13: The most difficult for Dali1 was to tell her, between two of nervous laughter, that he1 loved her. (Cel mai dificil lucru pentru Dali a fost să-i spună, între două râsete nervoase, că el o iubește )

Gilles Neret, Dali

Uneori relația de coreferință se multiplică în lungul unui text, formând lanțuri coreferențiale prin care traseele unor personaje, obiecte, situații, pot fi urmărite înapoi până la prima lor apariție.

Relația de coreferință este simetrică (dacă A coreferă cu B, atunci B coreferă cu A) și tranzitivă (dacă A coreferă cu B și B coreferă cu C, atunci A coreferă cu C). Aceste proprietăți induc un set de clase de echivalență în mulțimea expresiilor referențiale.

Anafora funcțională

Anaforele funcționale sunt cunoscute de asemenea și ca anafore text ([Udo & Strube, 1986]), sau anafore ori referințe de legătură (bridging references – [Clark & Haviland, 1974]). Pentru acest tip de anaforă nu există o relație de identitate între anafor și antecedent, ci una funcțională. Relația există aici între expresia anaforică și o expresie antecedent astfel încât una dintre ele este un rol al celeilalte.

Relația funcțională partitivă

Această relație se stabilește între un anafor al cărui centru reprezintă o parte componentă a centrului corespunzător antecedentului:

Fig. 3: Relație anaforică funcțională partitivă:

a. reprezentare completă;

b. reprezentare simplificată

Ex. 3: A reserve battery pack supplies the 316LT with power for approximately 2 hours. The status of the accumulator is indicated to the user.

(Un pachet de baterii de rezervă alimentează 316LT-ul cu putere pentru aproximativ 2 ore. Starea acumulatorului este indicat utilizatorului.)

Strube&Hahn, 1996

The accumulator trebuie să fie recunoscut ca parte a lui 316LT (un calculator) menționat în propoziția precedentă.

Relația proprietar – obiect posedat

Ex. 4: I have moved in a new flat.

The owner asked me 300.000 per mounth.

Aici [the owner] (proprietarul) posedă [a new flat] (apartamentul nou).

Referințe în care intervin mulțimi

Ex. 5: Vorbind de-a lor iubire – iubire fără saț –

Ea se lăsase dulce și greu pe al lui braț

Eminescu, Strigoii

Fig 4: Relații element – mulțime.

a: reprezentare completă, b: simplificată

Catafora

Lingviștii numesc relația referențială în care elementul arătător precede elementul referit (de exemplu, pronumele precede entitatea lexicală pe care acesta o referă) – catáforă.

Ex.15: When he1 became president, George Bush1 renewed his appeal for a "kinder, gentler nation." (Când el a devenit președinte, George Bush a înnoit apelul la „națiune nobilă și prietenoasă”)

(Compton’s Interactive Encyclopedia, 1995)

Într-un limbaj care scurt-circuitează planul reprezentațional, într-o viziune tradițională, ponumele he este o cataforă la George Bush. Interpretarea incrementală a acestui text este însă una în care construim întâi o reprezentare pentru he, pentru ca mai apoi George Bush să completeze cu informații entitatea corespunzătoare. O astfel de distincție pozițională, ca cea pusă în evidență în definiția cataforei, devine inutilă într-o viziune care încearcă să reconstituie procesele cognitive ce stau la baza înțelegerii textelor, pentru a crea pe baza lor modele interpretative computaționale. Discursul este imposibil de detașat de momentul lecturii lui. Acest lucru atribuie discursului întotdeauna o unică direcționalitate, care corespunde axei timpului lecturii, și care este cea a desfășurării liniare a textului, de la stânga la dreapta (ori de la dreapta la stânga pentru limbile semitice). Relația de referențialitate trebuie deci să se proiecteze pe această axă, dinspre entități "noi" către entități "vechi", deci de la dreapta spre stânga (stânga spre dreapta în cazul limbilor semitice), mereu către înapoi pe axa timpului lecturii. Acesta este motivul pentru care referințele înspre înainte nu sunt posibile, și deci catafora nu există.

Entități variabile în timp

Entitățile din spațiul situațional nu sunt constante în lungimea discursului. Două axe temporale pot fi evidențiate, fără a fi evident pe care ar trebui să ne situăm: prima este axa timpului istorisirii, care este timpul real al istoriei relatate. În acest timp, entitățile despre care se povestește îmbătrânesc, și deci nu mai sunt aceleași. Cealaltă axă este cea a reprezentărilor create în mintea cititorului de povestea în sine, pentru că despre o entitatea la mijlocul povestirii știm mai multe decât despre aceeași entitate la începutul povestirii. Cele două ipostaze ale aceluiași personaj sunt diferite deci și pentru că unul e mai bătrân decât celălalt în viața relatată, dar și pentru că unul e mai bogat decât celălalt în reprezentările mintale pe care le avem despre el. Din aceste motive relația de coreferință este și ea numai o abstractizare, o simplificare, adoptată ori de câte ori din diferite motive pot fi lăsate la o parte amănunte temporale asupra entităților asupra cărora se operează. Atunci când, însă, modificările sunt dramatice, se folosesc în reprezentare indícii care să evidențieze măsura inconstanței entităților reprezentate.

Ex.16: Maria1 was dreaming. The girl1 had just finished high-school and was engaged to be married. She imagined her wedding night in the arms of her beloved and imagined herself as his loving and caring wife1. He would have made her a woman1, and a mother1, and they would have grown old together in peace and happiness.

(Maria visa. Fata abia terminase liceul și se logodise. Ea își imagina noaptea nunții în brațele iubitului ei și se imagina fiind o soție bună și iubitoare. El ar fi transformat-o în femeie și mamă și ei ar fi îmbătrânit împreună în pace și fericire.)

Maria este referită printr-o serie de substantive (girl, wife, woman, mother), care descriu progresul, schimbarea suferite de entitatea respectivă. Pentru a marca aceste schimbări și pentru a memora informațiile relative aduse ar putea fi utilizată o notație diferită (pe nivelul semantic) între începutul lanțului anaforic și fiecare anafor.

Fig 5: Reprezentarea entităților variabile în timp

Rezoluția anaforei

Rezoluția anaforei este procesul de determinare a antecedentului unui anafor.

Considerăm următoarele exemple:

The Queen1 is not here yet but she2 is expected to arrive in the next half on hour.

(Regina nu este încă aici, dar ea este așteptată să ajungă în următoarea jumătate de oră)

Huddleston, 1984

Pronumele she este un anafor, iar the Queen este antecedentul și ele sunt coreferențiale. Se observă că antecedentul nu este un substantiv ci un grup nominal (NP).

Stephanie balked, as did Mike. (Stephanie a ezitat, ca și Mike)

Ian MacMillan, Ligth and Power Stories

În această propoziție vebul did este anafor și este un substituient pentru antecedentul balked totuși pentru că cei doi temeni nu au un referent comun, nu este vorba despre o relație de coreferință între cei doi termeni.

CAPITOLUL II – Rezoluția automată a anaforei

Picătura găurește piatra nu prin forță, ci prin continua ei cădere.(Ovidius)

Acest capitol prezintă sursele de cunoaștere necesare pentru rezoluția automată a anaforei și explică ce unelte și resurse sunt nesecare. Este acordată o atenție specială factorilor ce stau la baza algoritmilor pentru rezoluția anaforei. În continuare sunt descrise succint cele mai semnificative proiecte legate de rezoluția anforei din perioada 1960 – 1980. Urmează principale tendințe în cercetarea actuală în domeniul rezoluției anaforei și modalitatea de evaluare a algoritmilor pentru rezoluția anaforei.

Cunoașterea necesară pentru rezoluția automată a anaforei

Rezoluția anaforei este o problemă provocatoare și necesită o cantitate mare de cunoștințe ca suport – de la informații morfologice și lexicale (la un nivel de jos) la informații semantice și reguli pragmatice (la un nivel superior).

Cunoaștere morfologică și lexicală

Informațiile morfologice și lexicale sunt necesare nu doar pentru identificarea anaforelor pronomiale, ci și pentru prelucrări sintactice ulterioare. Există anafore care sunt rezolvate doar pe baza informațiilor lexicale cum ar fi genul sau numărul. Faptul că anaforele nominale (de fapt head-ul) au același număr și gen cu antecedenții este câteodată suficient pentru a alege un singur NP candidat, ca în exemplul:

Ex1: Green1 had no letters from Catherine while în Switzerland and he1 feared the silence. (Green nu are nici o scrisoare de la Catherine din Switzerland și lui îi este frică de liniște.)

Norman Sherry, The Life of Graham Green

Conform unei reguli de potrivire în număr și gen, NP-ul Greene este selectat ca un antecedent al anaforului pronomial he, întru cât ceilalți candidați posibili (Switzerland, Catherine și letters) sunt eliminați pentru că nu se potrivesc în număr și gen.

Potrivirea în gen este un criteriu util pentru limba engleză când candidatul anaforului este un nume propriu feminin sau masculin, un substantiv ce referă oameni (man, woman, father, mother, son, etc), substantive reprezentând profesii ca nu pot fi referite prin pronumele it, etc. De asemenea acordul în număr ajută la filtrarea candidaților. Este luat în considerare numărul entității de discurs asociate fiecărui candidat și nu numărul head-ului NP-ului. Antecedenții coordonați (de exemplu John and Mary) sunt referiți prin pronume la plural, în timp ce substantivele colective (commitee, army, team) pot fi referite atât prin pronume la singular (it) cât și prin pronume la plural (they). În unele limbi pluralul pronumelor marchează și genul (exemplu în limba română: ei, ele).

Cunoaștere sintactică

Cunoașterea sintactică este mai importantă decât cea morfologică și lexicală. Astfel în exemplul 1 Greene, no letters, Switzerland și Catherine sunt indentificate ca fiind grupuri nominale.

Sintaxa este indispensabilă pentru rezoluția anaforei. Pe lângă rolul important în delimitarea propozițiilor, frazelor și a altor construcții, sintaxa are un rol în formularea unor reguli folosite în procesul de rezoluție a anforei. O regulă simplă ar fi că un pronume este coreferențial cu grupul nominal subiect al aceleiași propoziții sau fraze doar dacă este reflexiv. Această regulă, bazată pe informații sintactice despre limitele propozițiilor și frazelor și despre funcția sintactică a fiecărui cuvânt, găsește, de exemplu că John este anatecedent pentru him în exemplul:

Ex2: Jim1 is running the business for him1. (Jim își conduce singur afacerea.)

O altă constrângere sintactică interzice ca un pronume dintr-o propoziție principală să refere un grup nominal aflat într-o propoziție secundară următoare.

Ex3: Because Amanda1 had saved hard, she1 was finally able to buy the car of her dreams.

(Pentru că Amanda a economisit din greu, ea în sfârșit și-a putut cumpăra mașina visurilor ei.)

Ex4: She1 was finally able to buy the car of her dreams, because Amanda2 had saved hard.

(Ea, în sfârșit, a putut să-și cumpere mașina visurilor ei, pentru că Amanda a economisit din greu.)

În exemplul 3 Amanda și she sunt coreferențiale, dar în exemplul 4 conform constrângerii de mai sus nu.

Pentru a putea aplica această regulă, un program pentru rezoluția anforei trebuie să aibă acces la informații detaliate despre structura frazelor, tipul propozițiilor (principale sau subordonate).

Cunoaștere semantică

Oricât de importante ar fi informațiile lexicale, morfologice și sintactice, în multe cazuri, ele singure nu pot ajuta la găsirea antecedenților. Fie exemplul:

Ex5: The petrified kitten1 refused to come down from the tree. It1 gazed beseechingly at the onlookers below. (Pisicuța împietrită refuza să coboare din copac. Ø se uita implorând la spectatorii de dedesubt.)

Folosind reguli de acord nu se pot elimina nici the petrified kitten, nici the tree ca potențial antecedent, pentru că ambii au genul neutru. Ar fi necesară o restricție bazată pe faptul că verbul to gaze (a privi lung) necesită ca agent o ființă (un lucru animat). Faptul că kitten (pisicuța) este o ființă este o informație vitală. Într-un sistem de rezoluție automată a anaforei aceste informații sunt memorate într-o bază de cunoștințe, de obicei un dicționar sau o ontologie.

În multe cazuri interpretarea corectă a anaforelor depinde de abilitatea sistemului de a folosi informația semantică pentru identificarea entităților de discurs asociate cu antecedentul.

Fie exemplul:

Ex6: Mary bought several shirts1 at the shop. They1 cost £20.

(Mary a cumpărat căteva tricouri din magazin. Ele au costat 20£)

Pentru ca un sistem NLU să „înțeleagă” acest exemplu, nu este suficient ca sistemul să găsească grupul nominal several shirts ca antecedent al pronumelui they ci să identifice entitatea de discurs asociată (setul de tricouri cumpărat de Mary de la magazin). Această descriere nu poate fi obținută sintactic și ar trebui găsită automat din logica propoziției.

În acest fel rezoluția anaforei poate fi privită ca un proces de substituție: anaforul este înlocuit de o descriere semantică mult mai complexă ce permite interpretarea grupului nominal în fazele următoare de procesare semantică ([Grishman, 1986]). Această substituție ar trebui să aibă loc după analiza semantică, și nu după parsare.

Un algoritm de rezoluție a anaforei aplicat după analiza semantică a textului ar conduce la rezultate mai bune decât un algoritm aplicat după analiza sintactică a textului. Totuși, majoritatea sistemelor de rezoluție a anaforei, în special cele care lucrează cu baze de cunoștințe reduse, nu au modalități de a realiza analize semantice (sau de alt tip). Prin urmare aceste sisteme nu încearcă să determine entitățile de discurs, ci lucrează cu constituenți de suprafață (grupuri nominale) iar strategiile de determinare a anaforelor sunt bazate pe ieșirea unui parser sintactic (parțial sau complet).

Cunoașterea semantică este în mod special importantă pentru interpretarea anaforei indirecte. O strategie semantică clasică este căutarea conflictelor dintre descrierile semantice asociate anaforului și candidatului. Este conflict între cele două grupuri nominale dacă nu sunt într-o relație de sinonimie, generalizare, specializare sau o relație de tipul membru – mulțime. De asemenea este conflict dacă modificatorii celor două grupuri nominale nu sunt compatibili (de exemplu the first – primul și the second – al doilea). Această strategie am încercat să o aplic în algoritmul meu de rezoluție a anaforei.

Cunoaștere despre stuctura discursului

Deși criteriile morfologice, lexicale, sintactice și semantice pentru selecția antecedentului unui anafor sunt puternice, ele nu sunt întotdeauna suficente pentru a determina antecedentul din setul de candidați posibili. Mai mult aceste criterii sunt mai degrabă niște filtre pentru a elimina candidați nepotriviți. În cazul unei ambiguități în alegerea antecedentului, de obicei, este ales candidatul cel mai semnificativ. În lingvistica computațională el este numit focus ( focus – [Groz, 1977], [Sidner, 1979]) sau centru (center – [Groz et al, 1983],[ Joshi și Weinstein, 1981]).

În exemplul următor, nici oamenii, nici calculatorarele nu vor putea interpreta anaforul pronomial it:

Ex7: Tilly tried on the dress over her skirt and ripped it.

(Tilly a probat rochia peste cămașa ei și ea s-a rupt.)

Dacă propoziția ar face parte dintr-un segment de discurs, lucru care ar permite determinarea celui mai semnificativ element, atunci situația ar fi diferită:

Ex8: Tilly’s mother had agree to make her a new dress for the party. She worked hard on the dress for weeks and finally it was ready for Tilly to try on. Impatiet to see what it would look like, Tilly tried on the dress over her skirt and ripped it.

(Mama lui Tilly a fost de acord să-i facă o rochie pentru petrecere. Ea a lucrat din greu la rochie săptămâni întregi și în final era gata ca Tilly să o probeze. Grăbită să vadă cu îi stă, Tilly a probat rochia peste cămașa ei și ea s-a rupt)

În acest segment de discurs, the dress este entitatea cea mai semnificativă și este în centrul atenției pe parcursul segmentului. Teoria centrelor sau a focusului se bazează pe faptul intuitiv că un discurs este de obiecei structurat în jurul unui subiect central. Mai mult, de obicei, elementul central al unei propoziții sau fraze este reluat folosind un pronume. Aceste ipoteze influențează interpretarea pronumelor deoarece odată stabilit elementul central, există o probabilitate mare ca pronumele următoare să refere acest element.

Când există doi sau mai mulți candidați pentru rolul de antecedent, sarcina de a determina antecedentul poate fi redusă la găsirea centrului / focusului propoziției sau frazei.

Cunoaștere din lumea reală

Rezoluția anaforei oferă o ilustrare a complexității înțelegerii limbajului natural. Un sistem de rezoluție automată a anaforei ce are doar informații morfologice, lexicale, sintactice și semantice, probabil că nu va reuși să determine corect anafora din exemplul:

Ex9: The soldiers shot at the women1 and they1 fell.

(Soldații au împușcat femeile și ele/ei au căzut)

Găsirea corectă a antecedentului în acest exemplu este posibilă doar dacă sistemul are la dispoziție o cunoaștere suplimentară, de exemplu sub forma unor reguli:

Regula 1: Dacă X împușcă pe Y și dacă Z (Z {X, Y}) cade, atunci este mai probabil ca Z să fie Y.

Regula 2: Dacă X împușcă pe Y și dacă Z (Z {X, Y}) ratează, atunci este mai probabil ca Z să fie X.

Multe exemple de anafore din viața reală necesită cunoștințe din lumea reală pentru rezolvarea lor. Integrarea unor astfel de cunoștințe într-un sistem practic de rezoluție a anaforei este foarte dificilă și este o sarcină consumatoare de timp. Marea majoritate a sistemelor pur și simplu nu au acces la asemenea informații extra-lingvistice.

Etapele procesului automat de rezoluție a anaforei

Rezoluția automată a anaforei presupune următoarele etape:

Identificarea anaforilor;

Găsirea candidaților;

Selecția antecedentului dintr-o mulțime de candidați pe baza factorilor de rezoluție a anaforei.

Identificarea anaforilor

Primul pas în procesul de determinare automată a anaforelor este identificarea anaforilor ai căror antecedenți trebuie găsiți. Identificarea automată a acestora, cel puțin pentru limba engleză, nu este o sarcină ușoară. De exemplu aparițiile neanaforice ale pronumelui it (Ex. 1) trebuie recunoscute de program.

Ex. 1: It must be stated that Oskar behaved impeccably.(Ø ar trebui declarat că Oskar s-a comportat impecabil)

Thomas Keneallz, Schindler’s List

În acest caz pronumele it este pleonastic. Există câțiva algoritmi pentru identificarea acestui tip de pronume. Algoritmul lui Lappin și Leass consideră pronumele it pleonastic dacă apare într-o construcție de forma:

It is [Adjectiv_modal] that [S]

It is [Adjectiv_modal] (for [NP]) to [VP]

It is [verb_cognitiv]-ed that [S]

Algoritmul lui Denber’s este o variantă a algoritmului lui Lappin și Leass. Și acest algoritm este bazat pe folosirea unor șabloane simple. Cei mai detaliați algoritmi pentru identificarea pronumelor pleonastice sunt algoritmul [Paice și Husk, 1987] și algoritmul [Evans, 2000, 2001].

Găsirea grupurilor nominale anaforice este și mai dificilă. Este important pentru un program de rezoluție a anaforei să fie capabil să identifice grupurile nominale neanaforice. Algoritmul [Bean și Riloff, 1999] generază (dintr-un text) o listă de grupuri nominale neanaforice și șabloane de grupuri nominale pe care le folosește mai departe pentru a recunoaște grupurile nominale neanaforice din alte texte. Acest algoritm are un procent de recall de 77,7% și o precizie de 86,6%. Algoritmul lui Vieira și Poesio (2000b) pentru identificarea grupurilor nominale neanaforice se bazează pe lucrarea lui Hawkins (1978) care a identificat o serie de corelații între diferite tipuri de structuri sintactice și apariția unei entități noi de discurs. Are un recall de 69% și o precizie de 72%. Algoritmul lui Munoz (2001) prepune clasificarea grupurilor nominale în anaforice și neanaforice folosind rețeaua semantică generată de WordNet.

Găsirea candidaților

Majoritatea sistemelor se ocupă de anafora nominală deoarece rezoluția anaforelor a căror antecedenți sunt grupuri verbale, propoziții sau fraze este foarte dificilă. De obicei aceste sisteme consideră candidați toate grupurile nominale ce precedă anaforul într-un anumit domeniu de căutare.

Domeniul căutării candidaților diferă în funcție de modelul de procesare adoptat și în funcție de tipul anaforului. Pentru că majoritatea relațiile anaforice sunt în interiorul unui segment de discurs, domeniul de căutare este considerat segmenul de discurs ce conține anaforul ([Kennedy & Bogureav, 1996]). Sistemele de rezoluție a anaforei pronomiale care nu au instrumente de determinare a granițelor segmentelor de discurs consideră, de obicei, domeniul de căutare propoziția curentă și două – trei propoziții anterioare ([Mitkov 1998b]). Grupurile nominale definite pot referi entități aflate la distanțe mai mari în text, și de aceea domeniul de căutare pentru acest tip de anafore este mai mare ([Kamayama 1997] – 10 propoziții). Aceste abordări de căutare a candidaților sunt considerate lineare. Există și modele de căutare ierarhice cum ar fi modelul bazat pe teoria nervurilor [Cristea et al. 1998, 2000] care consideră candidați grupurile nominale din segmentul curent și din segmentul precedent ierarhic. Identificarea automată a segmentelor (necesare teoriei nervurilor) este dificilă.

Selecția candidatului

Odată identificați anaforul și candidații, programul va încerca să determine anatecedentul din setul de candidați. Algoritmul de rezoluția a anaforei utilizează reguli bazate pe diferite surse de cunoaștere. Acordul în număr și gen, restricțiile semantice, paralelismul sintactic și semantic sunt câteva din cele mai utilizate reguli. Unele reguli pot elimina diferite grupuri nominale din mulțimea de candidați posibili (constrângeri bazate pe acordul în gen sau număr) – reguli eliminatoare. Alte reguli specifică că unii candidați au mai multe șanse să fie antecedentul căutat decât alti candidați (reguli bazate pe focus, paralelism) – reguli cu scor. Mai există și reguli confirmatoare, care găsesc antecedentul.

Aceste reguli lucrează împreună pentru identificarea antecedentului. Aplicarea unei singure reguli (eliminatoare, confirmatoare sau cu scor) nu conduce la găsirea antecedentului. Regulile interacționază între ele ducând fie la îmbunătățirea fie la scăderea performanței algoritmului. Acest fenomen de dependență nu a fost încă complet investigat, dar poate juca un rol important în procesul de rezoluție a anforei. Informații despre gradul de dependență sunt în special utile modelelor probabilistice și se speră să ajute la îmbunătățirea rezultatelor.

Pentru alegerea antecedentului din setul de candidați sunt necesare diferite unelte și resurse: dicționare, analizatoare morfologice, marcatoare pentru partea de vorbire. O problemă specifică limbii engleze este identificarea genului substantivelor (unele substantive au genul masculin sau feminin sau și feminin și masculin – pot apărea erori în interpretarea anaforei). Identificarea entităților animate ar putea ajuta la depistarea genului semantic. [Denber, 1998] și [Cardie & Wagstaff 1999] folosesc în acest sens WordNet-ul. [Evans & Orasan 2000] propun folosirea unui FDG – parser gramatical superficial, WordNet-ul și un set mic de reguli pentru identificarea entităților animate în limba engleză. Lucrarea lor arată că recunoașterea entităților animate contribuie la mărirea performantelor în rezoluția anaforei.

Informațiile semnatice pot fi oferite de WordNet, o ontologie folosită mult de cercetătorii NLP. WordNet-ul oferă o serie de relații semantice (între cuvinte) cum ar fi sinonimia, antonimia, hipernimia (relație de tipul „este un/o”), hiponimie, meronimie (relație de tipul „parte – întreg”), familiaritate (rar, neobișnuit, obișnuit).

Evaluarea algoritmilor pentru rezoluția anaforei

Evaluarea este esențială pentru progresul în cercetare și pentru dezvoltare. Ea este esențială pentru oricare sistem de prelucrare a limbajului. Evaluarea oferă o modalitate de apreciere a performanței individuale a unui sistem și de comparare cu alte aplicații. Un sistem este evaluat prin supunerea sa la o probă practică, astfel ca acea probă să poată fi folosită pentru a măsura obiectiv performanțele sistemului în raport cu performanțele altui sistem. Este necesară diferențierea dintre evaluarea unui algoritm și evaluarea unui sistem pentru rezoluția anaforei. Prin sistem pentru rezoluția anaforei se înțelege un sistem implementat complet care procesează un text de intrare pe mai multe nivele: morfologic, sintactic, semantic, al discursului și alimentează cu text procesat algoritmul pentru rezoluția anaforei.

O modalitate naturală de testare a unui algoritm de rezoluție a anaforei este rularea lui într-un mediu ideal fără a ține cont de erorile sau complicațiile posibile ce pot apare la diferite nivele de pre-procesare a textului. Când este evaluat un sistem de rezoluție a anaforei, apar scăderi în performanță datorate imposibilității analizării limbajului natural cu acuratețe absolută. Un număr de sisteme pentru rezoluția anaforei lucrează cu texte de intrare controlate de oameni (textul este pre-procesat manual sau este corectată adnotarea) sau sunt simulate manual, ceea ce sugerează că evaluarea raportată este de fapt a algoritmului de rezoluție. Pe de altă parte sunt sisteme care procesează complet textul înainte de a fi prelucrat de algoritmul de rezoluție a anaforei și evaluarea lor este a întregului sistem. Este preferabil ca evaluarea algoritmului de rezoluție a anaforei să fie făcută alături de evaluarea sistemului din care face parte. Este posibil ca un sistem cu rezultate slabe să fie bazat pe un algoritm eficient de rezoluție a anaforei.

3.1. Măsuri utilizate pentru evaluarea în rezoluția anaforei

MUC (Message Understanding Conferences) a introdus pentru rezoluția coreferinței următoarele măsuri: recall și precizia. Aceste măsuri au fost adoptate de un număr mare de cercetători în evaluarea algoritmilor sau sistemelor pentru rezoluția anaforei.

Există mai multe definiții ale acestor măsuri:

[Aone & Bennett, 1995]:

[Baldwin, 1997]:

Definiția preciziei este aceeași, însă definiția lui Aone și al lui Bennett a recall-ului include doar anaforele identificate de program, și nu toate anaforele, împiedicând ca această măsură să fie un indicator bun al succesului. Programul ar putea identifica numai un număr anume de anafore care sunt ușor de rezolvat și recall-ul obținut nu ar oferi o imagine realistă a performanței. Mai mult, pentru algoritmi robuști, care propun un antecedent întotdeauna, definiția lui Aone nu ar face nici o diferență între recall și precizie pentru că numărul de anafore identificate de program ar fi egal cu numărul de anafore propuse spre rezolvare.

În definiția preciziei numărul de anafore propuse spre rezolvare face posibil ca anumiți algoritmi care lasă nerezolvate anumite pronume (de exemplu cele care nu pot fi rezolvate de programul respectiv), sistemele care rezolvă doar pronumele cu un singur candidat să obțină incorect precizie mare.

Mitkov propune pentru măsurarea performanțelor unui algoritm următoarele măsuri: rata de succes (success rate), rata de succes critic (critical success rate) și rata de succes netrivial (non-trivial success rate).

Definiția ratei de succes pentru un algoritm de rezoluție a anaforei este:

Rata de succes pune accent pe performanța algoritmului și nu a altor module de pre-procesare, va fi obținută o valoare corectă dacă textul de intrare este adnotat manual sau este corectat.

Rata de succes netrivial se aplică doar pentru anaforele care au mai mult de un candidat pentru alegerea antecedentului, eliminându-le pe acelea precedate de un singur grup nominal în domeniul de căutare al algoritmului (prin urmare având un singur candidat) pentru că rezolvarea lor ar fi trivială.

Rata de succes critic se aplică doar acelor anafore dificile care au mai mult de un candidat după filtrarea candidaților după gen și număr. Această măsură este un indicator bun care descoperă greșelile generate de o evaluare care folosește date ce conțin doar anafore ușor de rezolvat. Dacă N este mulțimea de anafore împlicate întro evaluare, S mulțimea de anafore rezolvate corect, K mulțimea de anafore care au avut un singur candidat (si care au fost rezolvate corect într-un mod trivial), M mulțimea de anafore care au fost rezolvate pe baza acordului în gen și număr și n = |N|, s = |S|, k = |K|, și m = |M|. În mod evident s ≤ n, k ≤ s, k+m ≤ s, k ≥ 0, m ≥ 0, s ≥ 0.

Are loc următoarea relație:

rata de succes ≥ rata de succes netrivial ≥ rata de succes critic

pentru că:

rata de succes = s / n,

rata de succes netrivial = (s – k) / (n – k) =>

rata de succes critic = (s – k – m) / (n – k – m)

Rata de succes critic este un criteriu important pentru evaluarea eficienței factorilor utilizați în algoritmi de rezoluție a anaforei pentru cazurile critice când acordul în gen și număr nu sunt suficiente.

3.2. Evaluare comparativă

Performanța unui algoritm poate fi evaluată prin compararea cu algoritmi și modele reprezentative, indicând locul algoritmului respectiv în evoluția rezoluție anaforei.

Sunt prezentate trei clase de evaluări comparative:

evaluare prin comparare cu modele de bază – acest tip de evaluare justifică utilitatea algoritmului dezvoltat.

Oricât de mare ar fi rata de succes, nu merită dezvoltarea algoritmului decât dacă îți demonstrează clar superioritatea față de un model de bază

evaluare prin comparare cu algoritmi care folosesc aceeași „filozofie” – ajută la descoperirea noutăților aduse de algoritm în domeniul respectiv

evaluare prin comparare cu un algoritm bine cotat / punct de referință în domeniu – algoritmul lui Hobbs și algoritmul BFP (al lui Brennan) sunt de obicei folosite pentru acest tip de evaluare de mulți cercetători.

Este totuși dificilă compararea directă între doi algoritmi de rezoluție a anforei folosind oricare din aceste trei metode. Chiar dacă evaluarea este realizată pentru același set de date, uneltele de pre-procesare utilizate de sistemele de rezoluție introduc suficientă variație sau erori ce pot afecta procesul de comparare.

3.3 Evaluarea separată a componentelor unui algoritm de rezoluție a anaforei

Evaluarea separată a performanței componentelor unui algoritm pentru rezoluția anaforei este importantă pentru îmbunătățirea ulterioară. Evaluarea fiecărui factor inclus în algoritmul de rezoluție ne oferă o idee despre importanța sau contribuția sa, permițând îmbunătățirea ulterioară a scorurilor asociate factorilor.

Puterea de decizie a unui factor (DPk) este măsura influenței fiecărui factor în luarea deciziei:

unde Sk = nr. de cazuri în care candidatul, pentru care factorul k a fost aplicat, a fost ales ca antecedent , Ak = numărul de aplicări ale factorului.

Pentru factorii folosiți pentru eliminarea candidaților puterea de decizie se calcurează astfel:

unde NonSk = nr. de cazuri în care candidatul pentru care factorul k a fost aplicat și care nu a fost ales ca antecedent , Ak = numărul de aplicări ale factorului.

Importanța relativă arată cât de importantă este prezența unui factor. Pentru un factor k ea este definită astfel:

unde SR = rata de succes a tuturor factorilor, SR-k = rata de succes a tuturor factorilor mai puțin factorul k. Această mărime exprimă contribuția relativă a unui factor, și cât de mult din performață se pierde dacă factorul este eliminat.

3.4. Evaluarea unui sistem de rezoluție a anaforei

Rata de succes pentru un sistem de rezoluție a anforei este definită similar cu rate de succes a unui algoritm de rezoluție a anforei. Ea exprimă, pe lângă rata de succes a algoritmului implementat, performanța globală a sistemului, performanță care este influențată de calitatea pre-procesării. Determinarea corectă a grupurilor nominale, care vor deveni candidați, este o parte foarte importantă a pre-procesării.

Rata de succes a unui sistem de rezoluție a anaforei se definește astfel:

unde, numărul total de anafore este numărul de anafore din textul de evaluare care ar fi identificate de oameni. Această definiție presupune că identificarea anaforilor este responsabilitatea sistemului. Cum pre-procesarea se presupune a fi realizată automat, este probabil ca sistemul să omită câțiva anafori sau candidați, fapt care duce la scăderea ratei de succes. Se recomandă și determinarea ratei de succes a algoritmului implementat de sistem prin rularea lui pe un text de intrare perfect pre-procesat, pentru a vedea limitele algoritmului.

[Mitkov, Evans & Orasan, 2001] consideră că această definire a ratei de succes nu ține cont de cazurile în care programul încearcă să rezolve incorect anafore ne-nominale. Pentru programele de rezoluție a anaforei nominale, este importantă determinarea eficienței programului în eliminarea instanțelor de anaforă ne-nominală. Această mărime, numită eticheta rezoluției (resolition etiquette) este definătă astfel:

unde A’ = numărul de anafore nominale corect rezolvate; B’ = numărul de pronume, descrieri definite sau nume proprii care sunt filtrare corect ca instanțe de anafore ne-nominale; A = numărul total de anafore nominale; B = numărul total de pronume, descrieri definite sau nume proprii. Această mărime exprimă contribuția modulelor de recunoaștere a pronumelor ne-nominale și pleonastice și a modulului de rezoluție la performanța sistemului.

Pentru un sistem de rezoluție a anaforei pot fi determinate rata de succes netrivial și rata de succes critic, însă nu sunt indicate pentru că sunt caracteristice evaluării algoritmilor.

Fiabilitatea rezultatelor evaluării

Majoritatea sitemelor pentru rezoluția anaforei raportează rezultate la teste de un singur tip. În plus calitatea evaluării depinde de dimensiunea, semnificația statisitică și de cât de reprezentativ este textul de intrare folosit. Rezultatele sunt mai semnificative dacă textele folosite pentru evaluare sunt mari conținând mii de anafore. Teoretic, rata de succes sau altă măsură de evaluare este corect determinată doar dacă testarea se face pe toate textele posibile, lucru imposibil de realizat. Această afirmație subliniază importanța evaluării automate. Evaluarea automată presupune un text mare adnotat la coreferință, în raport cu care va fi comparat textul obținut prin rularea sistemului de rezoluție a anforei.

O metodă alternativă este selectarea la întâmplare (random) a propozițiilor folosite la testare, în speranța că astfel se vor obține rezultate mai semnificative.

Cât de realiste sunt rezultatele obținute în urma evaluării depinde și de natura textelor folosite: dacă textele conțin anafore greu de rezolvat, anafore care au un număr mare de posibili candidați, anafore care au antecedenții la distanță mare în text sau texte care conțin aprope doar anafore cu un singur candidat. Sunt necesare măsuri pentru determinare mediei complexității rezoluției anaforei pentru un text. Mitkov propune ca măsuri pentru deteminarea gradului de dificultate a textului: numărul mediu de candidați ai unui anafor și distanța medie dintre un anafor și antecedentul său.

Alte propuneri pentru evaluare

[Mitkov, 2000] propune un mediu (workbench) pentru compararea algoritmilor de rezoluție a anaforei bazați pe principii asemănătoare folosind nu doar același text de intrare ci și aceleași instrumente de pre-procesare. Această dezvoltare este un proiect consumator de timp pentru că presupune reimplementarea majorității algoritmilor, dar se așteaptă să ofere o imagine mai bună a avantajelor și dezavantajelor diferiților algoritmi. Un alt avantaj este faptul că algoritmii încorporați funcționează în mod complet automat. Versiunea curentă folosește parserul FDG ([Tapanainen, 1997]) pentru determinarea relațiilor de dependență între cuvinte (folosite pentru determinarea grupurilor nominale), a informațiilor morfologice și sintactice. În viitor vor fi posibile două modele de utilizare: unul folosind un parser superficial – pentru algoritmi ce folosesc o analiză parțială și altul folosind un parser complet – pentru algoritmi ce necesită o analiză completă. Versiunile viitoare vor include și accesul la informații semantice cu ajutorul WordNet-ului pentru a putea fi incluși și algoritmi ce necesită acest tip de informații.

[Donna Byron, 2001] propune ca numărul de tipuri de informații suplimentare folosite ar trebui inclus în evaluarea algoritmilor pentru rezoluția anaforei pronomiale. Este definită o nouă măsură numită rata de rezoluție (resolution rate) astfel:

Este sugerat ca toate metodele de evaluare a algoritmilor pentru rezoluția pronumelor să ofere informații despre textul folosit pentru evaluare.

[Stuckardt, 2001] sugerează că evaluarea sistemelor pentru rezoluția anaforei ar trebui să țină cont de mai mulți factori în afară de acuratețea rezoluție (de exemplu cu cât se mărește performanța unei aplicații NLP dacă folosește sistemul respectiv).

[Bagga, 1998] propune o metodă de evaluare a sistemelor pentru rezoluția coreferinței. Coreferința este clasificată în funcție de procesarea de care este nevoie pentru rezoluție. Este propusă o evaluare separată a claselor de coreferință (apoziție, nume predicative, nume proprii, pronume).

Primele sisteme pentru rezoluția anaforei

Cele mai importante cercetări în domeniul rezoluției anaforei din perioada 1960 – 1980 sunt: [Bobrow, 1964], [Winogad et al., 1972], [Hobbs, 1976, 1978], [Carter, 1968, 1987a], [Rich & LuperFoy, 1988], [Carbonnell & Brown, 1988]. Primele lucrări se bazează pe reguli eurisitice și nu exploatează complet analiza lingvistică – sitemul STUDENT al lui Bobrow sau SHRDLU al lui Winograd. Abordările ulterioare sunt mult mai complexe și folosesc euristici mai bune. Cercetătorii s-au implicat în dezvoltarea unor sisteme ce folosesc diferite surse de cunoaștere. De exemplu algoritmul lui Hobbs (Hobbs’ naive approach) din 1976 a folosit sintaxa în primul rând, iar algoritmul LUNAR și algoritmul lui Wilks semantica. Primele lucrări orientate discurs sunt ale lui [Sider, 1979] și [Webber, 1997]; lucrările următoare mergând și mai departe folosind și informații din lumea reală [Carter, 1986], [Carbonnell & Brown, 1988], [Rich & LuperFoy, 1988].

Majoritatea lucrărilor din această perioadă nu pot fi comparate cu metodele recente de rezoluție a anaforei pentru că multe din ele nu au fost implementate sau evaluate, Cele evaluate au fost testate manual acordându-se atenție doar algoritmului: textele erau analizate sinatctic și semantic de oameni, oferind astfel algoritmului avantajul de-a lucra cu un text de intrare pre-procesat perfect.

În continuare sunt pezentate pe scurt câteva din cele mai semnificative proiecte de rezoluție a anaforei din perioada timpurie (anii 60 – 80).

STUDENT (Bobrow 1964)

Este una din primele încercări de rezolvare a anaforei de către un program de calculator, fiind un sistem de rezolvare de probleme de algebră de liceu. STUDENT încearcă să găsească anaforii și antecedenții folosind pattern-matching.

Ex : The number of soldiers the Russians have is half the number of guns they have. The number of guns is 7000. What is the number of soldiers they have? (Numărul de soldați pe care rușii îl au este jumătate din numărul armelor pe care ei le au. Numărul de arme este 7000. Care este numărul de soldații pe care ei îl au?)

Sistemul găsește ca antecedent al lui they grupul nominal the Russians prin potrivirea dintre the number of soldiers the Russians have și the number of soldiers they have.

Sistemul lui Bobrow include o regulă care specifică că grupurile nominale ce conțin cuvântul this referă grupuri nominale similare precedente.

De fapt STUDENT folosește euristici limitate și în afară de tehnicile de potrivire propozițiile nu sunt parsate și nu are loc un proces real de rezoluție a anaforei.

SHRDLU (Winograd 1972)

Winograd este primul care dezvoltă proceduri pentru rezoluția pronumelor în sistemul său SHRDLU, care întreține un dialog despre o micro-lume de forme (blocuri și piramide). Euristicile sunt mult mai complexe lăsând impresia unei abordări complexe a rezoluției anaforei. SHRDLU găsește referințe din părți anterioare ale conversației dintre utilizator și program. Algoritmul lui Winograd verifică grupurile nominale anterioare pentru a găsi antecedentul și nu consideră doar primul candidat potrivit ci examinează toate posibilitățile. Se ține cont de poziția sintactică: subiectul este favorizat complementului și ambele sunt favorizate față de un complement cu o prepoziție. Este folosit de asemenea și focusul, care este determinat din răspunsurile la întrebări și din întrebările de tipul da/nu. Dacă nici un candidat nu este găsit cu siguranță ca fiind antecedentul, utilizatorul este rugat să ajute la selectarea celui mai bun candidat.

SHRDLU folosește euristici practice care și astăzi, după 30 ani, sunt încă relevante pentru sistemele de rezoluție a pronumelor.

LUNAR (Woods, Kaplan, Nash-Webber 1972)

Acest sistem folosește un parser ATN ([Woods, 1970]) și un interpretor semantic bazat pe principiile semanticii procedurale ([Woods 1968]). Rezoluția anaforei este realizată în cadrul interpretorului semantic care distinge două clase de anafori: parțiali (care referă o parte dintr-un grup nominal precedent) și compleți (referă un grup nominal precedent). Strategia de rezolvare a anaforilor parțiali este căutarea unui antecedent ce se găsește într-o structură sintactică (semanică) paralelă cu cea a anaforului. Sistemul utilizează atât nivelul sintactic cât și cel semantic, dar suferă de aceași limitare ca și STUDENT – poate rezolva doar anaforele pentru care antecedenții au o structură similară.

Sunt folosite trei metode diferite pentru a găsi referințele în funcție de forma anaforului (pentru anafor de tipul pronume demontrativ + substantiv, pentru pronume și pentru anaforii precedați de one, too și also ). Principala limitare a sistemului LUNAR este faptul că nu găsește referințele dintre propoziții.

Algoritmul lui Hobbs

Hobbs propune două modalități de rezoluție a anaforei pronomiale: una folosind arbori sintactici și alta folosind semantica ([Hobbs 1976, 1978]). Algoritmul ce folosește sintaxa este cunoscută ca Hoobs’ naive approach și a atras atenția cercetătorilor fiind încă unul din cei mai de succes algoritmi.

Algoritmul lui Hobbs folosește arbori sintactici de parsare, care sunt parcurși într-o anumită ordine căutând un grup nominal ce are numărul și genul corect. Hoobs adoptă două constrângeri sintactice propuse de Langacker: un pronume nereflexiv și antecedentul său nu se pot afla în aceeași propoziție și antecedentul unui pronume trebuie să precede sau „comande” (relație definită de Langacker) pronumele.

Rata de succes a acestul algoritm este între 81,8% și 92%. El este un algoritm „clasic” și rămâne un punct de referință pentru evaluarea algoritmilor actuali.

Algoritmul BFP (Brennan et al, 1987; Walker 1989)

Este un algoritm pentru rezoluția anaforei pronomiale ce își are originea în modelul extins al teoriei centrelor al lui Brennan, Friedman și Pollard.

Rezoluția anaforei în prezent

Primii algoritmi pentru rezoluția anaforei s-au bazat pe exploatarea cunoștințelor lingvistice și cele despre domeniu, cunoștințe greu de reprezentat sau procesat și care presupun prelucrarea manuală a textului. Printre acești algoritmi se numără [Carbonell & Brown, 1988], [Carter, 1986, 1987a], [Rich & LuperFoy, 1988], [Sidner, 1997].

Cererile de sisteme NLP practice au încurajat cercetătorii să treacă la strategii de rezoluție care presupun puține surse de cunoaștere (knowledge-poor). Dezvoltarea algoritmilor robuști și cu puține surse de cunoaștere a fost motivată și de apariția unor unelte de prelucrare a limbajului bazate pe texte, unelte mai ieftine și mai performante, și de existența textelor adnotate și a altor resurse (ontologii, dicționare).

Existența textelor adnotate la relațiile coreferențiale a permis dezvoltarea algoritmilor de învățare și evaluare a rezoluției anaforei. Textele, în special cele adnotate, sunt resurse neprețuite nu doar pentru cercetarea empirică ci și pentru metodele de învățare automată și pentru evaluarea algoritmilor implementați.

Performanța algoritmilor depinde de calitatea și cantitatea textelor folosite ca resurse. Algoritmul lui Dagan și Itai din 1999 folosește reguli simple de învățare pe baza unor șabloane, Algoritmul lui Aone și Bennett din 1995 folosește arbori de decizie pentru învățare în scopul identificării perechilor anafor – antecedent, iar algoritmii lui Orasan din 2000 și al lui Mitkov din 2001 introduc algoritmii genetici pentru optimizarea procesului de rezoluție a anaforei.

Momente semnificative în cercetarea legată de rezoluția anaforei sunt:

Trecerea spre strategii bazate pe surse de cunoaștere puține în anii 90;

Folosirea textelor în procesul de determinare a anaforei;

Includerea rezoluție anaforei în sistemel MUC-6 și MUC-7;

Dezvoltarea de proiecte pentru rezoluția anaforei pentru alte limbi decât engleza:

pentru limba franceză: [Popescu-belis & Robba, 1997];

pentru limba germană: [Dunker &Umbach, 1993],[Fischer et al., 1996], [Leass & Scwall, 1991], [Stuckadt, 1996, 1997];

pentru limba japoneză: [Mori et al., 1997], [Murata & Nagao, 2000], [Nakaiwa & Ikehara, 1992], [Nakaiwa & Ikehara, 1995], [Nakaiwa et al., 1995, 1996], [Wakao, 1994];

pentru limba portugheză: [Abraços & Lopes, 1994];

pentru limba turcă: [Tin & Akman, 1994];

Rezoluția coreferinței și anaforei pentru mai multe limbi a câștigat mult teren în ultimii ani [Aone & McKee, 1993], [Azzam et al., 1998], [Harabagiu & Maiorano, 2000], [Mitkov, 1999], [Mitkov & Stys, 1997].

Alte tendințe în cercetare sunt:

folosirea teoriei probabilităților și tehnicilor de învățare automată ([Aone & Bennett, 1995], [Ge et al., 1998], [Kehler, 1997], [Cardie & Wagstaff, 1999]);

folosirea teoriei centrelor în forma originală sau revizuită ([Abraços & Lopes, 1994], [Hahn & Strube, 1997], [Strube & Hahn, 1996], [Tetranl, 1999]);

dezvoltarea de metodologii pentru evaluarea algoritmilor de rezoluție a anaforei ([Mitkov 1998a, 2000, 2001b], [Byron, 2001]).

În continuare sunt prezentate pe scurt câteva din cele mai importante lucrări referitoare la rezoluția anaforei din ultimii ani.

Algoritmul [Dagan & Itai, 1990, 1991] – bazat pe frecvență de apariție a șabloanelor

Este un algoritm pentru rezoluția anaforei pronomiale, pentru care anaforul este un pronume la persona a III-a.

Sunt utilizate șabloane pentru găsirea antecedentului, alternativă la implementările costisitoare ce presupuneau o selecție restrictivă completă.

Șabloanele sunt găsite automat într-un corpus (texte folosite ca sursă de cunoaștere) și sunt folosite pentru filtrarea candidaților nepotriviți. Selecția se face pornind de la ideea că antecedentul trebuie să satisfacă constrângerile impuse anaforului. În particular, dacă anaforul se găsește într-o anumită relație sintactică (este subiect sau complement al unui verb) atunci substituția anaforului cu antecedentul ar trebui să fie posibilă din moment ce antecedentul va satisface restricțiile cerute.

Anaforul este înlocuit cu fiecare candidat și candiadtul care produce cele mai multe apariții ale șablonului este preferat.

Modelul are două faze: prima în care corpus-ul este procesat și este construită baza de bate statistice și a doua fază, faza dezambiguizării, în care baza de date statistice este folosită pentru găsirea antecedenților pronumelor la persona a III-a.

Rata de succes a acestui algoritm este de 74%. Deși testat pe un set mic de date, modelul lui Dagan și Itai este o tehnică de rezolvare a anaforei utilă, mai ales dacă există multe texte care pot fi folosite pentru colectarea de date statistice.

Algoritmul RAP al lui Lappin și Lears (1994) – folosește parserul SGP pentru filtrarea candidaților din interiorul propozițiilor

Shalom Lappin și Herbert Leass în 1994 descriu un algoritm pentru rezolvarea pronumelor la persoana a III-a (incluzând și pronumele reflexive) a căror antecedenți sunt grupuri nominale. Algoritmul, numit RAP (Resolution of Anaphora Preocedure) folosește reprezentările sintactice generate de parserul lui McCord (1990, 1993). Pentru a selecta antecedentul din lista de grupuri nominale candidate sunt folosite scoruri determinate folosind structuta sintactică și modelul dinamic al stărilor atenționale. Nu folosește infomații semantice sau din lumea reală.

RAP contine mai multe componente: un filtru sintactic intrapropozițional, un filtru morfologic, o procedură pentru identificarea pronumelor pleonastice, un algoritm pentru identificarea candidaților, o procedură care asignează valori unor parametri (cum ar fi rolul sintactic, frecvența), o procedură pentru identificarea grupurilor nominale legate printr-o relație de referință, o procedură de decizie pentru selecția antecedentului din lista de candidați.

RAP are o rată de succes de 86%, 72% pentru cazurile de referință între propoziții și 89% pentru referințele în interiorul propozițiilor.

În 1995 Dagan a construit o procedură (numită RASPTAT) ce utilizează preferința lexicală, pentru a îmbunătăți performanța algoritmului RAP. RASPTAT are o rată de succes de 89%, adică cu 3% mai bun decât RAP

Algoritmul lui Lappin și Leass este una din cele mai importante contribuții la rezoluția anaforei din anii 1990: a folosit ca bază pentru dezvoltarea altor aplicații și este citat mult în literatura de specialitate.

Parserul lui Kennedy și Boguraev – versiune a algoritmului RAP.

Nu necesită parsare sintactică completă, ci funcționează pe ieșirea unui POS-tagger îmbogățită cu adnotarea la funcția gramaticală. Sistemul folosește o gramatică pentru identificarea constituienților și, similar algoritmului lui Lappin și Leass, folosește scoruri pentru candidați. Nu este o simplă adaptare cu mai puține surse de cunoaștere a algoritmului RAP, ci mai degrabă o extensie, pentru că în acest nou sistem sunt folosiți factori noi.

Pentru fiecare element din propoziție tagger-ul folosit (Lingsoft – realizat de [Voutilainen et al, 1992]) oferă un set de valori ce indică proprietățile morfologice, lexicale și gramaticale. Textul este examinat propoziție cu propoziție și referenții discursului sunt interpretați de la stânga la dreapta. Coreferința este determinată astfel: întâi sunt eliminați acei referenți pe care un anafor nu-i poate referi, apoi se alege antecedentul din rândul candidaților în funcție de scor. Scorurile utilizate sunt un supraset a celor utilizate de algoritmul lui Lappin și Leass. La evaluarea algoritmului s-a obținut o rată de succes de 75%, mai mică nu cu mult decât cea a algoritmului RAP.

CogNIAC – [Baldwin, 1997]

Este un program pentru rezoluția anaforei pronomiale.

Principala presupunere teoretică pe care se bazează strategia acestui algoritm este că există o subclasă de anafore care poate fi rezolvată cu ajutorului unei cantități limitate de cunoștințe și resurse. Ceea ce diferențiază CogNIAC de alți algoritmi este faptul că în cazul unei ambiguități pronumele nu este rezolvat. Acest lucru conduce la obținerea unei precizii mari, dar un recall nesatisfăcător.

CogNIAC utilizează cunoștințe și resurse puține. Folosește șase reguli de bază (unicitate în discurs, reflexivitate, unicitate în propoziția anterioară și în cea curentă, pronume posesive, unicitatea propoziției curente, subiect unic) și două suplimentare. Pronumele sunt procesate de la stânga la dreapta și pentru fiecare regulile sunt aplicate într-o ordine specificată. Dacă o regulă găsește un antecedent, nu mai sunt aplicate celelalte reguli. Dacă nici o regulă nu găsește nici un antecedent atunci pronumele este lăsat nerezolvat.

CogNIAC a fost evaluat în paralel cu algoritmul lui Hobbs obținându-se rezultate aprope egale: 78,8% pentru algoritmul lui Hobbs și 77,9% pentru CogNIAC. Versiunea de înaltă precizie a CogNIAC-ului are o precizie de 92% și un recall de 64%.

Proiectului lui Vieira și Poesio pentru expresii definite

S-a încercat dezvoltarea unui sistem de procesare care să lucreze cu informații structurale, informații oferite de resurse lexicale existente cum este WordNet-ul, cu informații minimale adnotate manual sau cu informații care ar putea fi obținute automat. Ca consecință sistemul nu este echipat pentru rezolvarea grupurilor nominale care necesită procesare complexă. Pentru aceste tipuri de anafore sunt dezvoltate câteva euristici.

Sistemul lui Vieira și Poesio nu doar găsește antecedentul anaforilor ci este capabil să recunoască entitățile noi de discurs. Sistemul ajunge la o precizie de 83% și de recall de 62% pentru anafora directă și o precizie de 72% și recall de 69% in cazul identificării entităților de discurs noi.

Abordări bazate pe învățare automată

Ca alternativă la sistemele bazate de surse de cunoaștere, metodele de învățare automată propun obținerea de cunoștințe / informații din texte adnotate sau nu, prin învățarea folosind un set de exemple (șabloane). Termenul de învățare automată este folosit pentru a referi în special metodele care reprezintă cunoștințele învățate într-o formă declarativă, simbolică, metode diferite de cele statistice sau care folosesc rețelele neuronale. Interesează metodele care reprezintă cunoștințele învățate sub forma unor arbori de decizie interpretabili, reguli logice și instanțe memorate. Arborii de decizie sunt de fapt funcții de clasificare reprezentate sub forma unor arbori ca au drept noduri teste asupra atributelor, drept arce valori pentru atribute iar frunzele sunt etichete pentru clase.

[Aone și Bennet, 1995] descriu un sistem pentru rezoluția anaforei pentru limba japoneză care învață din texte adnotate cu informații despre discurs – articole din ziare. Este continuarea proiectului de rezoluție a anaforei pentru mai multe limbi [Aone & McKee, 1993]. Modului de învătare automată (MLR) folosește arbori de decizie C4,5. Arborele de decizie este construit pe baza unor vectori de caracteristici pentru un anafor și antecedenții posibili. Caracteristicile de învățare sunt fie unare, fiind legate de anafor sau de candidat (număr sau gen), fie binare, reprezentând o relație dintre anafor și antecedent (distanța). Sunt folosite 66 de caracteristici (lexicale, sintactice, semantice și de poziție). Metoda de învățare lucrează cu trei parametri: lanțuri anaforice, identificator de tip de anaforă și factori de încredere. Precizia acestui algoritm se situează între 83,49% și 88,55%, iar recall-ul între 67,53% și 70,20%.

Sistemul RESOLVE al lui McCarthy și Lehnert utilizează arbori de decizie C4,5 pentru a învăța să clasifice grupuri nominale coreferențiale în domeniul întreprinderilor mixte de afaceri. Vectorii caracteristici utilizați sunt creați pe baza legăturilor coreferențiale și referențiale dintr-un text adnotat manual. La evaluarea sistemului s-a obținut o precizie de 87,6% și un recall de 80,1%.

[Soon, Ng și Lim, 1999] descriu un algoritm de învățare pentru rezoluția anaforei substantivale într-un text nelimitat. Modulul de rezoluție a coreferinței este parte a unui sistem mai mare de rezoluție. Caracteristicile utilizate pentru perechi de grupuri nominale sunt: distanța, egalitate de siruri, acord în număr, acord de clasă semantică, acord în gen, nume proprii, aliasuri, iar pentru un grup nominal individual: pronume, grup nominal definit, grup nominal demonstrativ. Acest sistemul de rezoluție a coreferinței are o precizie de 68% și un recall de 52%.

[Ge et al., 1998] – algoritm probabilistic pentru rezoluția anaforei

Este propus un cadru statistic pentru rezoluția pronumelor la persona a III-a. Sunt combinați mai mulți factori ai rezoluției anaforei într-unul singur, probabilitatea, utilizat pentru găsirea antecedentului. Programul nu folosește reguli, dar în schimb folosește Penn Wall Street Journal Treebank pentru învățare.

Un prim factor utilizat de autori este distanța (Hobbs’ distance – calculată în funcție de gen, număr și animație) dintre pronume și candidat. Cu cât distanța este mai mare cu atât probabilitatea este mai mică. Sunt folosite de asemenea șabloane pentru calcularea probabilității ca un candidat să apară cu aceeași funție sintactică ca anaforul. Ultimul factor menționat este numărul de apariții. Un grup nominal menționat mai frecvent are mai multe șanse să fie antecedentul. Aceste patru propabilități sunt înmulțite pentru fiecare candidat; este ales candidatul cu probabilitatea cea mai mare. În urma evaluării s-a obținut o rată de succes de 82,9%.

[Cardie & Wagstaff, 1999] – propun rezoluția coreferinței ca algoritm de clustering (însumare)

Fiecare grup nominal este reprezentat ca un vector de unsprezece proprietăți (constrângeri sau preferințe) și valorile lor. Algoritmul de clustering împarte mulțimea grupurilor nominale în partiții, reprezentând clase de echivalență a lanțurilor referențiale. Grupurile nominale sunt determinate folosind Empire NP finder [Cardie &Wagstaff, 1999]; pentru fiecare grup nominal sunt determinate valorile pentru cele 11 proprietăți. Gradul de „apropiere de tip coreferință” dintre fiecare două grupuri nominale este determinat pe baza „distanței metrice”. Cu cât sunt „mai apropiate”, cu atât probabilitatea ca cele două grupuri nominale să fie coreferențiale este mai mare. Algoritmul începe de la sfârșitul textului și merge înapoi comparând fiecare grup nominal cu toate grupurile nominale precedente. Dacă distanța dintre două gurpuri nominale este mai mică decât raza de însumare r, atunci clasele lor sunt unite dacă nu există nici un grup nominal incompatibil în nici una din clase.

În urma evaluărilor algoritmul are o precizie de 54,6 – 57,4 % și un recall de 52,7 – 48,8 %. Acest algoritm nu necesită surse de cunoaștere, nici adnotarea textelor folosite pentru învățare, în plus nu doar realizează rezoluția pronumelor ci și a grupurilor nominale. Limitarea este dată de algoritmul de clustering care este un algoritm greedy, a acurateței scăzute a pre-procesării, a faptului că nu rezolvă pronumele reflexive și pleonastice.

Algoritmul lui Mitkov – robust și cu puține surse de cunoaștere

Dezvoltarea acestui algoritm, pentru rezoluția pronumelor ce au ca antecedenți grupuri nominale, demonstrază că anafora poate fi rezolvată cu suficient succes fără cunoștințe lingvistice sofisticate sau chiar fără parsare. Evaluarea algoritmului arată că setul de factori utilizați poate fi folosit și pentru alte limbi decât engleza. Analiza sintactică, semantică și a discusului sunt eliminate folosindu-se în schimb o listă de preferințe – indicatorii antecedentului. Textul de intrare este adnotat la partea de vorbire. Algoritmul funcționează astfel: localizează grupurile nominale care preced anaforul într-un interval de două propoziții, verifică acordul cu anaforul în gen și număr și apoi aplică indicatorii candidaților rămași prin asignarea unui scor pozitiv sau negativ (2, 1, 0, -1). Grupul nominal cu scorul cel mai mare este propus ca antecedent. Algoritmul are o precizie de 77,9%.

CAPITOLUL III – Genframe

Nimic nu este dat, totul este construit. (Bachelard)

Genframe este un sistem pentru rezoluția anaforei realizat de Dan Cristea, Oana-Diana Postolache, Gabriela-Eugenia Dima, și Cătălina Barbu. Este prezentat în lucrările Tough anaphora resolution problems (Dan Cristea, Gabriela E. Dima, Oana-Diana Postolache, Ruslan Mitkov) și AR-Engine – a framework for unrestricted co-reference resolution (Dan Cristea, Oana-Diana Postolache, Gabriela-Eugenia Dima, Cătălina Barbu)

Genframe-ul este un motor specializat pentru rezoluția anaforei (motor-AR) care funționează pe baza unui model (model-AR) pe care îl primește la intrare:

Fig 1. motorul-AR funcționează pe baza modelelor-AR

El poate fi ușor integrat în diverse aplicații pentru prelucrare a limbajului ce necesită un modul de rezoluție a anaforei.

Cele doua principii ale GenFrame-ului:

Relațiile referențiale sunt de natură semantică nu textuală (Halliday&Hassan)

Procesarea textului este incrementală.

Cum funcționează?

Funcționarea este bazată pe modelul lui Ruslan Mitkov de rezoluție a anaforei;

Atașează fiecărui anafor o listă de atribute împreună cu valorile lor și compară aceste valori cu cele ale entităților deja existente;

Alege drept antecedent acea entitate care are cele mai multe valori identice cu ale anaforului.

Structura Genframe-ului este:

Fig 2. Motorul de rezoluție a anaforei

RE – expresii referențiale = grupuri nominale (din text )care pot referi entități de discurs

Attr – structuri care memorează informația pe nivelul proiecțiilor

DE – entități de discurs

Modelul de reprezentare a anaforei folosit în Genframe

Genframe folosește este un model de reprezentare a anaforei care ține cont de relațiile morfologice și sintactice dintre elementele constitutive ale anaforei. Un set de restricții morfologice, sintactice și semantice (specifice fiecărei limbi) este folosit pentru eliminarea candidaților, fiind introdus un nivel nou în reprezentarea anaforei: nivelul restricțiilor morfo-sintactico-semantice (feature structures)

Interpretarea anaforei este privită ca un proces în doi pași:

un prim proces de proiectare în care nivelul intermediar este populat cu informații aduse din text,

un proces de evocare, care cu ajutorul regulilor (dependente de limbă, de structură, de caracteristicile nivelului intermediar) evocă o entitate deja introdusă în discurs sau propune una nouă.

Mecanismul de evocare este bazat pe nivelul intermediar, și nu pe textul propriu-zis, și este dependent de limbă mai mult sau mai puțin în funcție de setul de reguli.

Fig. 2: Reprezentarea anaforei pe trei nivele

Introducerea nivelului intermediar este o rafinare a modelului clasic de reprezentare a anaforei pe două nivele. Acest nivel este eliminat când procesul de rezoluție este încheiat.

Rezoluția anaforei în Genframe

S-a dorit crearea unui model care să permită utilizarea tuturor ipotezelor formulate până în prezent despre rezoluția anaforei: acordul morfologic, sintactic sau semantic sub forma unor reguli dependente de limbă, variația entităților de discurs în timp, catafora, amânarea momentului rezoluție.

În cazul rezovării automate a anaforelor procentul de indecizie poate fi mare datorită lipsei capacității de rezoluție, absenței sau limitării cunoașterii. Amânarea rezoluție anaforei adaugă un nou nivel semantic la model. Acest nivel este folosit în cazul unei indecizii și permite păstrarea unor structuri importante pentru identificarea referentului în discursul anterior în orice moment al ascultării / citirii textului, simultan sau după momentul apariției expresiei referențiale.

Fig. 3: Reprezentarea pe patru nivele impusă de amânarea rezoluției

Figura 3 arată procesul de rezoluție pentru un caz care necesită amânarea rezoluției. La momentul t0 are loc citirea RE-ului c. În același timp, c proiectează structura morfo-sintactic-semantică pe nivelul restricțiilor. În același moment cititorul devine conștient de existența unei ambiguități. Pe nivelul temporal asociat, un atribut (numit candidati – reprezentat de o pereche de linii punctate) va conține lista posibilor antecedenți (în exemplul din figura 3 conține valorile centrula și centrulb). Elemetele din listă au asociate niște scoruri ce exprimă gradul de fiabilitate. Apoi într-un moment t1, când există suficientă informație are loc procesul de dezambiguizare (în figură, centrulb este ales). Criterii de alegere a antecedentului sunt: un scor aflat sub un prag stabilit precum și o diferență anume dintre primul și al doilea candidat.

Încheierea acestui proces implică transferul unei părți din datele memorate în reprezentarea de pe nivelul intermediar în reprezentarea semantică a candidatului ales, urmată de ștergerea reprezentărilor de pe nivelul intermediar. La sfârșit este păstrată doar o legătură directă între nivelul textului și nivelul semantic. În toate referințele funcționale, anaforul construiește întâi o entitate și apoi o pune într-o anumită relație semantică (partitivă, proprietar-obiect posedat) cu antecedentul.

Structura unui model-AR

Framework-ul este capabil să integreze sau să găzduiască o mare parte a algoritmilor existenți, fiind incluși în motor sub forma unui model. Deci, noțiunea principală este cea de model pentru rezoluția anaforei. Modelul reprezintă modalitatea prin care se rezolvă anaforele.

Un model este alcătuit din patru componente:

Componenta 1 este formată dintr-un set de atribute primare care completează nivelul intermediar (al proiecților) și care sunt apoi raportate nivelului semantic. Fiecare atribut contribuie la stabilirea relației dintre anafor și antecedent.

Atributele, așa cum sunt menționate în majoritatea abordărilor existente, pot fi clasificate în categoriile:

morfologice:

număr;

gen lexical;

persoană.

Toți algoritmi existenți utilizează criterii morfologice pentru filtrarea candidaților. Eliminarea unei posibile legături referențiale pe baza unei nepotriviri morfologice poate duce la apariția unor erori. Deși autorii nu sunt de acord cu părerea lui [Barlow, 1998] în această privință, și anume că morfologia ar trebui ignorată, consideră că o abordare mai puțin categorică este preferabilă.

sintactice:

descrierea sintactică completă a RE-urilor ca constituenți ai arborelui sintactic:[Lappin & Leass, 1994];

rolul sintactic al RE-urilor față de subiectului sau față de verb. Exemplu: în abordările bazate pe teoria centrelor [Grosz, Joshi & Weinstein, 1995], [Brennan, Friedman & Pollard, 1987], cele bazate pe domeniul sintactic: [Chomsky, 1981], [Reinhart, 1981], [Gordon & Hendricks, 1998], [Kennedy & Boguraev, 1996];

calitatea de a fi adjunct, inclus sau complement al unei prepoziții [Kennedy & Boguraev, 1996];

incluziunea sau nu într-o construcție [Kennedy and Boguraev, 1996];

șabloane sintactic în care este implicat RE-ul, care permit identificarea paralelismului sintactic [Kennedy & Boguraev, 1996], [Mitkov, 1997].

semantice:

poziția head-ului RE-ului într-o ierarhie conceptuală (hiponimie, hipernimie): toate modele care folosesc WordNet-ul ([Poesio, Vieira & Teufel, 1997]). Proprietăți ca animația, sexul (genul natural) sau calitatea de a fi concret sau abstract pot fi considerate atribute simplificate derivate dintr-o ierarhie conceptuală;

apartenența la o clasă de sinonimie, determinată din context;

rolul semantic ce permite verificarea legăturilor inferențiale, limitărilor pragmatice, paralelismului semantic, preferința unui obiect;

poziționale:

offsetul primului element al RE-ului (un grup nominal) în text ([Kennedy & Boguraev, 1996]);

incluziunea într-un segment, propoziție sau frază, considerate ca unități de discurs ([Azzam, Humphreys & Gaizauskas, 1998]). Această proprietate permite calcularea gradului de apropiere dintre anafor și antecedent. Gradul de apropiere poate fi intra-unitate sau inter-unitate (multe modele stabilesc un maxim număr de unități între RE-uri pentru stabilirea de accesibiliate din componenta 4).

realizare de suprafață

domeniu acestei proprietăți este: elipse, pronume clitice, complete, reflexive, posesive, demonstrative, pronumele eliptiv “it”, grupurile nominale nedefinite, definite, determinate sau nedeterminate, numerale, etc.

altele

incluziunea sau nu a RE-ului într-un câmp lexical anume, dominant în text (este numit “domain concept” în [Mitkov, 1997]);

frecvența termenului în text ([Mitkov, 1997]);

apariția termenului în titlu ([Mitkov, 1997]).

Componenta 2 include un set de surse de cunoaștere

Setul de surse de cunoaștere găsește valori pentru atribute în timpul procesării imcrementale a textului (considerând textul în ordinea în care este citit).

O sursă de cunoaștere este văzută ca un procesor virtual capabil să găsească valori pentru un singur atribut de pe nivelul proiecțiilor (restricțiilor), de exemplu număr, gen, parte de vorbire, rol sintactic. Practic, un procesor actual găsește valori pentru mai mult de un atribut. De aceea un marcator morfo-sintactic reprezintă mai multe surse de cunoaștere pentru că găsește valori pentru mai multe atribute.

Cel puțin două surse de cunoaștere sunt fundamentale pentru toate modele posibile de rezoluție a anforei: un marcator pentru partea de vorbire (POS tagger) – pentru a asocia tag-uri tuturor elemetelor din text și un parser superficial (shallow parser) capabil să recunoașcă RE-uri prin gruparea cuvintelor textului în grupuri nominale. Din moment ce există grupuri nominale care nu pot fi RE-uri (ex: the bucket în afara grupului verbal to kick the bucket), un parser ar trebui să respingă aceste grupuri nominale, prin folosirea unui set de expresii.

În afară de aceste procesoare, sisteme existente folosesc surse de cunoaștere suplimentare. De exemplu Kennedy și Boguraev (1996) introduc un marcator pentru funcția sintactică și un set de șabloane pentru recunoașterea eliptivului “it”. Azzam, Humphreys și Gaizauskas (1998) folosesc un analizator sintactic, un analizator semantic și un descoperitor de eveniment elementare. Gordon și Hendrick (1998) utilizează un identificator de realizare de suprafață și un parser sintactic, iar Hobbs (1978) are nevoie , pentru algoritmul semantic , de un analizator sintactic, un identificator de realizare de suprafață și de un set de axiome pentru determinarea rolului semantic și a relațiilor dintre elementele lexicale.

Componenta 3 – un set de euristici sau reguli

Componenta 3 conține un set de euristici sau reguli care cooperează pentru a găsi răspunsul la întrebările:

(1) Un RE introduce o nouă entitate de discurs?

(2) Dacă nu, ce entitate de discurs existență referă?

Euristicile și regulile realizază faza de evocare dintre o structură existentă ce aparține nivelului restricțiilor și entitățile de discurs de pe nivelul sematic.

În concordanță cu majoritatea autorilor, pentru realizarea acestui proces sunt folosite trei tipuri de reguli:

Reguli demolatoare (aplicate primele) care elimină un posibil candidatat. Aceste reguli se aplică într-o fază de eliminare din rândul candidaților a acelor entități de discurs care nu pot fi referite de RE-ul ce se procesează

Reguli confirmatoare confirmă dacă un candidat anume este antecedentul căutat.

Reguli cu scor care măresc sau scad un factor asociat unui atribut. Aceste reguli se aplică într-o fază ulterioară, în care este ales cel mai bun candidat (este ales din rândul candidaților rămași după aplicarea regulilor demolatoare) sau este introdusă o nouă entitate de discurs.

Multe reguli sunt bazate direct pe valorile atributelor găsite de sursele de cunoaștere. Altele sunt aplicate cu ajutorul unor relații binare, care sunt determinate pe baza atributelor primare.

De exmplu, pentru a elimina candidați [Kennedy & Boguraev, 1996] implementează reguli care împiedică un pronume să refere un grup nominal ce îl conține. (în exemplul the child of his brother, his nu referă nici child, nici brother, ci o entitate diferită). Pentru restul de candidați ei calculază un scor prin evaluarea unui set de perechi de atribute. Aceste scoruri sunt justificate lingvistic și experimental (conform lui [Keenan & Comrie, 1977], [Lappin & Leass, 1994]).

[Gordon & Hendricks, 1998] calculează scorul pentru un anafor și un antecedent cu ajutorul unei clasificări a perechilor bazate pe realizarea de suprafață: substantiv-pronume > substantiv-substantiv > pronume-substantiv. Dacă realizarea de suprafață a unui anafor este substantiv, atunci un candidat a cărui realizare de suprafață este un substantiv va avea scor mai mare decât unul a cărui realizare de suprafață este un pronume. Deși nu este specificat explicit, este probabil ca, dacă realizarea de suprafață a unui anafor este un pronume, candidatul a cărui realizare de suprafață este un substantiv să aibă un scor mai bun decât cel a cărui realizare de suprafață este un pronume.

Componenta 4 – un set de reguli care stabilesc domeniu de accesibilitate

Această componentă are două sarcini: să determine entitățile de discurs care pot fi referite și să le ordoneze potrivit unui criteriu.

Pentru ordonarea entităților pot fi adoptate diferite strategii: ordonarea liniară – așează toate entitățile de discurs găsite până în momentul respectiv descrescător momentului apariției RE-urilor din text pe care le referă. Dacă se folosește acest criteriu și există doi candiați cu același scor este ales candidatul cel mai apropiat textual de anafor. În algoritmul bazat pe teoria stărilor atenționale [Grosz și Sidner, 1986] domeniul de accesibilitate este unitatea de discurs curentă iar entitățile sunt memorate într-o stivă a focusului. Abordările bazate pe teoria centrelor cum ar fi [Sidner, 1981], [Azzam, Humphreys și Gaizauskas, 1998] folosesc regiștri pentru memorarea focusului curent și liste actualizate pentru fiecare propoziție și definesc o ordine de căutare a antecedentului. Teoria nervurilor [Cristea, Ide și Romary 1998] ordonează unitățile discursului potrivit unui domeniu extins de acesibilitate (E-DRA). In teoria nervurilor domeniul de acesibilitate efențială a unei unități de discurs este dat de structura discursului și identifică o secvență de unități de discurs, numită nervură, în care se caută antecedentul. Domeniul de acesibiliate extins (E-DRA) este domeniul de acesibilitate plus restul de unități de discurs.

Funcționarea Genframe-ului

Textul este procesat secvențial astfel:.

La nivelul textului sunt delimitate grupurile nominale prin contribuția a două surse de cunoaștere (POS tagger și shallow parser).

La început pe nivelul proiecțiilor nu se găsește nici o structură intermediară (nici un attr) și nici pe nivelul semantic nu există nici o entitate de discurs. La un moment dat se procesează un RE care aparține unui segment anume de discurs. Cum rolul nivelului proiecțiilor este doar de a meține informații despre RE-ului ce se procesează, după rezolvarea lui structura de pe acest nivel este ștearsă. Nivelul semantic conține structuri ce corespund entităților de discurs găsite (DE1, … DEm), ordonate conform criteriului dat de Componenta 4. Aceste entități de discurs definesc clase de echivalență pentru expresiile referențiale (RE) aflate pe nivelul textului astfel că expresiile coreferențiale referă același DE.

Pentru fiecare RE din text (de la stânga la dreapta) se execută:

faza de proiecție (RE-ul este transformat într-un Attr care conține setul de atribute împreună cu valorile corespunzătoare); Momentul procesării unui RE poate fi amânat dacă unele surse de cunoaștere necesită mai mult text. De exemplu unele proprietăți semantice ale RE-urilor sunt identificate doar după prelucrarea verbului de care sunt legate.

faza de propunere/evocare (Attr-ul obținut este procesat, adică se încearcă să se găsească antecedentul aplicându-se regulile). Presupunem că structura attrx de pe nivelul proiecțiilor are următoarea listă de perechi atribut-valoare: ai = vi, i{1,n} și DE1, … DEm este lista ordonată a entităților de discurs de la momentul respectiv, iar DE1 – cea mai importantă. Presupunem că atributele și valorile acestora pentru DEj sunt: aji = vji, i{1,n}. Atributul candidați al structurii attrx este un vector de lungime m ce conține perechi de valori numerice: primul număr este un indice corespunzător unui DE iar al doilea număr este un scor care exprimă probabilitatea ca DE-ul corespunzător să fie antecedentul anaforului curent. Notăm cele două valori ale unei perechi din lista candidați cu idx respectiv val. Faza de evocare se execută astfel:

1. Pentru fiecare entitate de discurs DEj execută {

2. candidați.idx(j) := j;

3. candidați.val(j) := 0;

4. pentru fiecare atribut ai al stucturii attrx execută {

5. candidați.val(j) := candidați.val(j) + regula-i(vi, vji);

}

}

6. ordonează lista candidați în ordinea descrescătoare a valorilor

val și apoi a valorilor idx ;

7. dacă candidați.val(0) < pragmin atunci copie attrx ca DEm+1 și

conectează anaforul curent REx) la el;

8. altfel dacă abs(candidați.val(0) – candidați.val(1)) < pragdiff

atunci menține doar candidați(0) și candidați(1) în attrx;

9. altfel alege drept antecedent al REx DE-ul dat de

candidați.idx(0), (primul candidat după ordonare) ,

unește attrx cu DE-ul găsit și

șterge attrx de pe nivelul proiecțiilor;

faza de completare (se testează dacă s-a găsit antecedent sau nu. Dacă nu s-a găsit antecedentul, attr-ul se adaugă la lista de attr-uri amânate); Pasul 7 descrie acțiunile ce se execută când este propusă o nouă entitate de discurs datorită potrivirii slabe dintre structurile proiectate și entitățile de discurs deja existente. Pasul 8 descrie acțiunile ce se execută când există o incertitudine în alegerea antecedentului (scorurile asociate primilor doi candidați sunt sub un prag stabilit) Pragurile utilizate în acești doi pași pragmin and pragdiff) sunt incluse în model printre alți parametri.

faza de reevaluare (se reia reprocesarea attr-urilor amânate) Sunt situații în care două sau mai multe structuri attr sunt menținute pe nivelul proiecțiilor. Aceste situații apar în cazul amânării rezoluției, datorită diferenței de scor prea mici între candiații cei mai probabili.

Implementarea sistemului Genframe

Genframe este implementat în limbajul Java. Este un modul care poate fi inclus în alte aplicații de prelucrare a limbajului.

La intrare: primește un text, în format XML, adnotat la POS (partea de vorbire) și la NP (grupuri nominale) și un model ce reprezintă tocmai modalitatea prin care se rezolvă anaforele (clase derivate din clasele GenFrame-ului scrise în Java);

La ieșire: un text adnotat cu lanțurile coreferențiale existente în text;

Clase importante:

Clasa RE – clasă folosită pentru memorarea unui RE (grup nominal ce poate referi o entitate de discurs);

Clasa DE – clasă folosită pentru memorarea unui DE (entități de discurs); conține o listă cu RE-urile ce au contribuit la entitatea respectivă; fiecare DE are asociat un vector cu atributele și valorile lor date de toate RE-urile care referă entitatea respectivă;

Clasa Attr – clasă folosită pentru memorarea unei structurii Attr, pe nivelul proiecțiilor. Fiecare Attr memorează RE-ul căruia îi corespunde, un vector cu atributele și valorile corespunzătoare, DE-ul la care pointează și un vector cu candidații valizi;

Clasa Candidate – clasă folosită pentru memorarea unui candidat; are asociat un DE, un scor și o poziție;

Clasa CandidateComparator – clasă folosită pentru compararea candidaților în vederea ordonării lor;

Clasa TagAttrNames – clasă folosită pentru memorarea tag-uri folosite in adnotarea textului și a altor constante folosite ce depind de adnotare și de limba pentru care se face rezoluția anaforei;

Clasa Rule – clasă abstractă ce trebuie derivată; este folosită pentru a descrie o regulă; o regulă are asociată un nume, o prioritate, un tip, un scor și o pondere. Regulile pot fi de două tipuri:

certificatoare / demolatoare

regulile certificatoare returnează –1 în cazul în care s-a găsit cu DE-ul la care referă attr-ul, altfel returnează 0;

regulile demolatoare returnează –2 în cazul în care DE-ul curent nu este cu siguranță antecedentul attr-ului și 0 altfel;

cu scor

regulile cu scor returnează un anumit scor care se adună la scorul candidatului (DE-ului) curent;

Metoda abstractă a acestei clase este:

public abstract int run(DE de, Attr attr);

Clasa Model – clasă abstractă ce trebuie derivată și metodele ei abstracte implementate.

Metodele abstracte sunt:

public abstract void setFeatures(Attr attr);

– stabilește care sunt atributele care interesează din punctul de vedere al modelului și de asemenea atașează valorile corespunzătoare fiecărui atribut în parte pentru attr-ul curent. Pentru găsirea valorilor corespunzătoare se pot folosi sursele externe, fie care sunt deja exsistente, fie altele nou create special pentru acest scop. Pentru adăugarea de noi atribute se folosește metoda public void addFeature(String f, Object v) din clasa Attr.

public abstract void sortDeList(Vector deList);

– sortează lista de DE-uri;

public abstract void applyHeuristics(Attr attr);

– Este posibil ca unui attr să nu i se poată stabili antecedentul. Acest lucru se întâmplă atunci când doi (sau mai mulți) candidați au acealași scor sau diferența scorurilor este foarte mică. În acest caz acești candidați sunt memorați (clasa Attr are un membru validCandidați în care sunt stocați). Atunci când lista de RE-uri a fost parcursă în toatalitate dar un attr sau mai mulți nu au putut fi rezolvați se aplică această funcție care trebuie să aleagă un candidat din lista de candidați valizi (care se poate obține folosind metoda getValidCandidați() din clasa Attr) folosindu-se de niște euristici.

public abstract void createRules()- modelul, pe lângă atribute, poate stabili și niște reguli care ajută la determinarea antecedentului;

– în această metodă sunt adăugate regulile cu ajutorul metodei public void addRule(Rule r);

Clasa Engine – este clasa cea mai importantă; implementează algoritmul de rezoluție a anforei ce funcționează pe baza unui model (o clasă derivată din clasa Model) prin metodele run, process și processAttr(); conține modelul, lista de RE-uri, de DE-uri și de Attr-uri, pragul sub care se construiesc noi DE-uri, pragul sub care este amanata decizia, multimea de tag-uri folosite in adnotarea textului (clasă derivată din TagAttr).

CAPITOLUL IV – Aplicația mea

Lucrurile nu sunt grele de făcut, ceea ce este greu este să fim în stare să le facem. (C-tin Brâncuși)

Mi-am propus (dezvoltarea unui model pentru) rezolvarea unor tipuri de anaforă:

anafora funcțională și coreferința;

anafora substantivală

cazuri dificile de anaforă:

subiect – nume predicativ;

subiect – apoziție;

grupuri nominale cu același număr lexical dar leme diferite;

grupuri nominale cu numar lexical diferit si leme diferite.

Din punct de vedere computațional cea mai multă atenție a primit anafora pronomială existând multe lucări și mulți algoritmi pentru rezolvarea acestui tip de anaforă. Există semnificativ mai puține lucrări despre anafora nominală, și mai puține despre anafora funcțională. WordNet-ul este de obicei folosit pentru a rezolva anafora nominală și pe cea funcțională, dar ar fi nevoie de o dezambiguizare a sensurilor cuvintelor pentru a obține rezultate bune. De aceea am folosit în aplicația mea și web-ul pentru rezolvarea acestor tipuri de anafore.

Aplicația mea este de fapt un model folosit ca intrare pentru GenFrame – sistem pentru rezoluția anaforei (prezentat în capitolul III). Modelul reprezintă de fapt modul de rezolvare a anaforelor.

Modele existente – trasături și așteptări:

Base-model – modelul de bază:

Setul de atribute:

POS = partea de vorbire, LNUM = număr lexical, LGEN = genul lexical, NAME = nume, LEM = lema

Surse de cunoaștere:

POS-tagger, lematizator;

Reguli de potrivire:

Regulă confirmatoare: match-NAME (potrivire de nume);

Reguli cu scor: match-LNUM, match-LGEN, match-LEM (potrivire de număr, gen sau lemă);

Domeniu de accesibilitate: liniar; ordonare după poziție

Acest model rezolvă coreferințele pentru care anaforul este un pronume și antecedentul pronume sau substantiv propriu.

WordNet-model = Base-model plus…(foloseste ierarhia WordNet)

Setul de atribute:

POS = partea de vorbire, LNUM = număr lexical, LGEN = genul lexical, NAME = nume, LEM = lema

Genul natural : SHE, HE, IT; hipernime (HYPER) și sinonime (SYNO)

Surse de cunoaștere:

POS-tagger, lematizator;

WordNet-ul;

Reguli de potrivire:

Regulă confirmatoare: match-NAME (potrivire de nume);

Reguli cu scor: match-LNUM, match-LGEN, match-LEM (potrivire de număr, gen sau lemă), match-NGEN, match-HYPER, match-SYNO;

Domeniu de accesibilitate: liniar; ordonare după poziție

Față de modelul de bază acest model găsește și unele referințe pentru care anaforul este un grup nominal, însă încă rămân anafore nominale nerezolvate pentru că relațiile de hipernimie și sinonimie nu sunt suficiente și nici nu sunt complet implementate de către WordNet.

Centering-model = WordNet-model plus…(foloseste Teoria Centrelor)

Setul de atribute:

POS = partea de vorbire, LNUM = număr lexical, LGEN = genul lexical, NAME = nume, LEM = lema, Genul natural : SHE, HE, IT; hipernime (HYPER) și sinonime (SYNO)

SEG = ID-ul propoziției din care face parte RE-ul; SYN = funcția sintactică;

Surse de cunoaștere:

POS-tagger, lematizator; WordNet,

Segmentator de unități de discurs; FDG – un parser gramatical;

Reguli de potrivire:

Regulă confirmatoare: match-NAME (potrivire de nume);

Reguli cu scor: match-LNUM, match-LGEN, match-LEM (potrivire de număr, gen sau lemă); match-NGEN, match-HYPER, match-SYNO;

Euristici de potrivire: CT-preference, C-command;

Domeniu de accesibilitate: liniar; ordonare după poziție;

Centuring Model are performanțe mai bune decât modelul bazat pe WordNet, însă mai rămân cazuri mai complicate de anaforă nerezolvate cum ar fi: subiect – nume predicativ, coreferințe dintre grupuri nominale cu același număr lexical diferit, coreferințe dintre un substantiv comun și unul propriu, coreferințe pronume – antecedent splitat, coreferințe substantiv plural – antecedent splitat.

VT-model = Centering-model plus… (foloseste Teoria Nervurilor)

Setul de atribute:

Surse de cunoaștere: ca la Centering Model

Reguli de potrivire:

Domeniu de accesibilitate: ierarhic conform teoriei nervurilor

Modelul bazat pe teoria nervurilor nu aduce îmbunătățiri modelului ce folosește teoria centrelor decât în cazul unui text de dimensiuni mari.

Caracterizarea modelului meu:

Setul de atribute:

POS = partea de vorbire;

LNUM = număr lexical;

LGEN = gen lexical;

NGEN = genul natural;

PERS = persona unui pronume;

NAME = nume propriu;

LEM = lema;

SYNO = sinonimele;

HYPER = hipernimele;

MERO = meronimele (de fapt sunt de trei tipuri: part-of, substance-of și member-of);

HOLO = holonime;

DEF = definiția,

DET = “determinanții” (cuvintele dintr-un grup nominal exceptând head-ul)

ANIMACY = calitatea de a fi animat;

APP = apoziție

INCLUDE = gupul nominal în care este inclus

Sursele de cunoastere:

POS-tagger, lematizator, WordNet-ul, Internetul, bază de date (fisier) pentru nume proprii;

Reguli:

Reguli destructoare: match-DET, match-ANIMACY, IncludingRule,

Reguli confirmatoare: match-NAME, match-APP, match-HOLO, match-MERO;

Reguli cu scor: WebRule, LemmaRule, NumberRule, GenderRule, NaturalGenderRule, match-DEF;

Domeniu de accesibilitate:

liniar

Noutăți aduse de acest model:

rezolvă RE-urile "încuibărite" (se folosește WordNet-ul și Web-ul pentru a seta un atribut de tipul PART-OF, SUBSTANCE-OF, MEMBER-OF) – adică anafora funcțională.

Ex: a tree of the forest (tree = MEMBER-OF forest)

rezolvă apozițiile: (se seteaza un atribut APPOSITION-OF)

Ex: Maria, my friend, … (my friend = SAME-AS Maria)

găsește coreferințele subiect-nume predicativ: (se setează un atribut SAME-AS)

Ex: Dana is my sister. (Dana = SAME-AS my sister)

găsește coreferințe dintre grupuri nominale cu același număr lexical dar leme diferite (se folosește WordNet-ul)

Ex: The queen … the woman.

găsește coreferințe dintre NP-uri cu numere lexicale și leme diferite (se folosesc relațiile de meronimie, holonimie și hipernimie din WordNet și interogări web cu ajutorul motorului de căutare Google):

Ex: The patrol …. the soldiers

găsește coreferințe dintre un substantiv comun și unul propriu (se foloseste o baza de cunostinte – de fapt o baza de date)

Ex: Maria … the girl

găsește coreferintele pronume – antecedent splitat: (se foloseste un atribut GROUP OF)

Ex: John meet Mary. They went to a movie. => they = GROUP-OF (Jhon & Mary);

găsește coreferințele substantiv plural – antecedent splitat: (se foloseste un atribut GROUP-OF)

Ex: Dan, Chriss and Anne … the kids => the kids= GROUP-OF (Dan, Chriss & Anne);

Implementarea aplicației:

Aplicația este un model ce este intrare pentru motorul GenFrame-ului (prezentat în capitolul III). Prin urmare este scrisă în limbajul Java și constă în clase derivate din clasele GenFrame-ului (lucru necesar), clase adăugate de mine, necesare pentru a rezolva cazurile mai dificile de anaforă și clase folosite pentru accesul la WordNet (nu sunt scrise de mine, doar folosite și eventual modificate).

Precizez că am modificat și clasele GenFrame-ului deoarece am descoperit niște erori de funcționare. Este vorba de metoda public static boolean process(Attr attr) a clasei Engine. De exemplu în urma aplicării unei reguli destructoare când era eliminat un candidat, datorită modului în care era realizată o iterație, era sărit candidatul următor, adică pentru acesta nu erau aplicate regulile, prin urmare nu era luat în calcul la determinarea antecedentului. Am modificat modul de iterare și eliminare a candidaților. Pentru a putea salva în fisierul de ieșire și anafora funcțională a trebui să modific și funcția de salvare. De asemenea am modificat modul de memorare a atributelor și valorilor asociate unui DE pentru a permite găsirea tuturor atributelor și a valorilor corespunzătoare unui RE ce referă DE-ul respectiv. De exemplu pentru regulile HolomynRule, MeronymRule aveam nevoie să de numărul lexical corespunzător unei leme a DE-ului candidat. Clasa DE prin modul de memorare a atributelor nu permitea acest lucru.

Clase extinse:

Modelul : public class ModelLic extends Model – clasa care stabilește cum se face rezoluția anaforei: ce atribute se folosesc, ce reguli sau euristici se aplică;

Pragul minim (lowerBound) este 0.54f, iar pragul de diferențiere (epsilon) este 0.01f;

Metodele abstracte suprascrise sunt:

public void setFeatures(Attr attr) – stabilește care sunt atributele care interesează din punctul de vedere al modelului și de asemenea atașează valorile corespunzătoare fiecărui atribut în parte pentru attr-ul curent:

public void setFeatures(Attr attr)

{

String headID = attr.getRE().getHeadID();

String npID = attr.getRE().getNpID();

// extragere valori pentru atribute si le ataseaza attr-ulu

// extragem partea de vorbire

String pos = POSExtractor.extractPOS(headID, textFile, tags);

if (!pos.equals(""))

attr.addFeature(tags.POS, pos);

//extragem genul gramatical

String gen = GenderExtractor.extractGender(headID,textFile,tags);

if (!gen.equals(""))

attr.addFeature(tags.GENDER,gen);

//extragem lemma

String lemma = LemmaExtractor.extractLemma(headID,textFile,tags);

if (!lemma.equals(""))

attr.addFeature(tags.LEMMA,lemma);

// extragem numarul gramatical

String number = NumberExtractor.extractNumber(headID, textFile, tags);

if (!number.equals(""))

attr.addFeature(tags.NUMBER,number);

//pentru pronume extragem si persoana

String pers="";

if (pos.equals(tags.PRON))

{

pers = PersonExtractor.extractPerson(headID, textFile, tags);

if (!pers.equals(""))

attr.addFeature(tags.PERSON, pers);

}

// extragem tipul – comun, propriu

String type = TypeExtractor.extractType(headID,textFile,tags);

if (!type.equals(""))

{

attr.addFeature(tags.TYPE, type);

if (type.equals(tags.PROPER))

{

StringTokenizer tok = new StringTokenizer(lemma,",");

//instantiem clasa ce mem numele proprii

ProperNames pn = new ProperNames();

// incarcam fis cu nume proprii

pn.load();

while (tok.hasMoreTokens())

{

String token = tok.nextToken();

if (pn.isMale(token))

{

gen = tags.M;

attr.addFeature(tags.GENDER, tags.M);

break;

}

if (pn.isFemale(lemma))

{

gen = tags.F;

attr.addFeature(tags.GENDER, tags.F);

break;

}

}

}

}

/* determinam genul semantic – este de fapt dat de trei valori

reale – procente ce exprima probabilitatea de a avea genul masculin, feminin si respectiv neutru

*/

if (lemma != null)

{

float f = HeSheIt.percentHe(lemma, pos, gen, pers, tags);

attr.addFeature(tags.HE, new Float(f));

f = HeSheIt.percentShe(lemma, pos, gen, pers, tags);

attr.addFeature(tags.SHE, new Float(f));

f = HeSheIt.percentIt(lemma, pos, gen, pers, tags);

attr.addFeature(tags.IT, new Float(f));

}

//extragem apozitiile

String app = AppositionExtractor.extractApposition("" + npID, textFile, tags);

if (app != null)

attr.addFeature(tags.APPOSITION, app);

//extragem "determinantii"

ArrayList det = DetExtractor.extractDet("" + npID, textFile, tags);

if (det != null && det.size() > 0)

attr.addFeature(tags.DET, det);

// extragem id-urile NP-urilor incluse in NP/ul curent

Vector included = IncludedNP.extractIncluded(npID, textFile, tags);

if (included.size() > 0)

attr.addFeature(tags.INCLUDED, included);

// conectare la wordnet ptr. a lua synonume,meronime,….

DictionaryDatabase dictionary = new FileBackedDictionary();

if (!lemma.equals("") && pos.equals(tags.N))

{

ArrayList mp = new ArrayList(); //meronime PART OF

ArrayList mm = new ArrayList(); //meronime MEMBER OF

ArrayList ms = new ArrayList(); //meronime SUBSTANCE OF

ArrayList hp = new ArrayList(); //holonime PART OF

ArrayList hm = new ArrayList(); //holonime MEMBER OF

ArrayList hs = new ArrayList(); //holonime SUBSTANCE OF

ArrayList senses = dictionary.getAllSenses((String)attr.getFeature(tags.LEMMA));

Vector vect = new Vector() ;

for (int i = 0; i < senses.size(); i++)

{

Synset sense = (Synset)senses.get(i);

vect.add(sense.getDescription());

if (sense.getPartHolonyms().size() > 0)

mp.addAll(sense.getPartHolonyms());

if (sense.getMHolonyms().size() > 0)

mm.addAll(sense.getMHolonyms());

if (sense.getSHolonyms().size() > 0)

ms.addAll(sense.getSHolonyms());

if (sense.getPartMeronyms().size() > 0)

hp.addAll(sense.getPartMeronyms());

if (sense.getMMeronyms().size() > 0)

hm.addAll(sense.getMMeronyms());

if (sense.getSMeronyms().size() > 0)

hs.addAll(sense.getSMeronyms());

}

if (hp != null && hp.isEmpty() != true)

attr.addFeature(tags.HOLOP, hp);

if (hm != null && hm.isEmpty() != true)

attr.addFeature(tags.HOLOM, hm);

if (hs != null && hs.isEmpty() != true)

attr.addFeature(tags.HOLOP, hs);

if (mp != null && mp.isEmpty() != true)

attr.addFeature(tags.MEROP, mp);

if (mm != null && mm.isEmpty() != true)

attr.addFeature(tags.MEROM, mm);

if (ms != null && ms.isEmpty() != true)

attr.addFeature(tags.MEROS, ms);

vect = (Vector) dictionary.getSynonymSenses(lemma);

if (vect != null && vect.size() > 0)

attr.addFeature(tags.SYNO, vect);

}

}

public void sortDeList(Vector deList) – sortează lista de DE-uri în ordinea apariției în text (ultimile DE-uri referite sunt cele mai recente) aparținând ultimelor trei propoziții;

public void applyHeuristics(Attr attr) – modelul meu nu aplică nici o euristică;

public void createRules()- stabilește regulile care ajută la determinarea antecedentului, tipul lor, scorul și prioritarea asociată:

addRule(new IncludingRule(true, 15, 0));

addRule(new ProperNameRule(true, 14, 0));

addRule(new DetRule(true, 13, 0));

addRule(new AnimateRule(true, 12, 0));

addRule(new AppositionRule(true, 11, 0));

addRule(new GroupRule(true, 10, 0));

addRule(new RoleRule(true, 9, 0));

addRule(new HolonymRule(true, 8, 0));

addRule(new MeronymRule(true, 7, 0));

addRule(new LemmaRule(false, 6, 2));

addRule(new NumberRule(false, 5, 4));

addRule(new GenderRule(false, 4, 1));

addRule(new NaturalGenderRule(false, 3, 3));

addRule(new DefSRule(false, 2, 2));

addRule(new webRule(false, 1, 2));

addRule(new SynonymRule(false, 1, 1));

addRule(new HypernymRule(false, 1, 1));

addRule(new PosRule(false, 1, 1));

Regulile:

public class AnimateRule extends Rule – regulă destructoare. Sunt eliminați candidații care nu sunt la fel de “animați” ca antecedentul. Pentru fiecare candidat (de fapt un DE) și pentru attr sunt determinate (folosind WordNet-ul) procente de probabilitate ca entitatea corespunzătoare să fie “animată”. Dacă diferența dintre procentul candidatului și procentul attr-ului este mai mare ca un prag atunci candidatul este considerat nepotrivit.

public class AppositionRule extends Rule – regulă confirmatoare pentru rezolvarea referințelor de tipul substantiv – apoziție. Daca attr-ul are setat un atribut APPOSITION-OF și valoarea lui este ID-ul unui grup nominal ce referă entitatea descrisă de candidatul respectiv atunci candidatul căutat a fost găsit.

public class DefSRule extends Rule – regulă cu scor ce folosește definițiile cuvintelor oferite de WordNet. Am adăugat această regulă deoarece relațiile de hipernimie, sinonimie, meronimie și holonimie nu sunt suficiente pentru rezolvarea anaforelor nominale. Întâi se testează dacă există un ancestor comun (în ontologia oferită de WordNet) între lema attr-ului și lemele grupurilor nominale ce au contribuit la crearea entității de discurs aflată pe post de candidat. Dacă ancestorul există și este ori lema attr-ului ori una din lemele candidatului atunci avem o relație de coreferință. Dacă ancestorul există și este nu este unul “general” (adică “life form”, “something”, “organism”, etc) atunci este testat dacă definițiile date de WordNet pentru lemele asociate candidatului conțin lema attr-ului și dacă definițiile date de WordNet pentru lema attr-ului conțin una din lemele candidatului. Daca este îndeplinită una din aceste condiții atunci este considerat că există șanse să fie coreferință între attr și candidat.

public class DetRule extends Rule – regulă demolatoare referitoare la “determinații” unui grup nominal. Eu spun “determinanți” cuvintelor dintr-un grup nominal ce nu sunt substantive. Folosind acești “determinați” se testează dacă un substantiv este articulat sau nu. Dacă nu este articulat atunci el introduce o entitate nouă de discurs, prin urmare nici un candidat nu este bun ca antecedent al său. În plus mai sunt adăugate alte restricții, de exemplu dacă doar attr (sau doar candidatul) are “determinantul” some atunci nu poate exista o relație de coreferință.

public class GenderRule extends Rule – regulă cu scor. Dacă attr-ul are același gen ca un RE ce contribuie la definirea candidatului atunci candidatul are mai multe șanse să fie antecedentul căutat.

public class GroupRule extends Rule – regulă destructoare. Dacă candidatul face parte dintr-un grup (grupurile sunt determinate folosind un extractor și sunt memorate folosind o clasă Group) ce are același “tip” cu attr-ul și attr-ul poate fi considerat un grup (adică ori este la plural ori este un substantiv colectiv) atunci avem o relație de coreferință între attr și grup, iar între candidat – membru al grupului și attr nu putem avea coreferință, ci referință funcțională (de apartenență).

public class HolonymRule extends Rule – regulă confirmatoare ce folosește relația de holonimie definită de WordNet. Dacă attr este holonim al candidatului (lucru verificat cu ajutorul atributelor HOLOP, HOLOM, HOLOS și a WordNet-ului) atunci în unui testului asupra numărului attr-ului și candidatului se stabilește dacă este relație de coreferință sau de referință funcțională. Analog pentru cazul când candidatul este holonim al attr-ului.

public class IncludingRule extends Rule – regulă demolatoare ce nu permite ca între un RE inclus în alt RE să existe o relație de coreferință.

public class LemaRule extends Rule – regulă cu scor. Dacă attr-ul are același lema ca un RE ce contribuie la definirea DE-ului candidat atunci DE-ul are mai multe șanse să fie antecedentul căutat.

public class MeroniymRule extends Rule – regulă confirmatoare asemănătoare cu HolonymRule diferența fiind faptul că folosește relația de meronimie și nu cea de holonimie.

public class ProperNameRule extends Rule – regulă certificatoare. Dacă și attr-ul și DE-ul candidat sunt substantive proprii și au aceeași lema atunci ele sunt coreferențiale.

public class RoleRule extends Rule – regulă destructoare. Dacă attr-ul are pentru atributul ROLE valaorea nume predicativ și DE-ul are un pentru un atribut ROLE valoarea subiect și sunt din aceeași propoziție atunci este setat un atribut SAME-AS;

public class SemanticNumberRule extends Rule – regulă cu scor ce folosește atributele SHE, HE, IT – probabilități ca entitățile respective să fie de genul feminin, masculin sau neutru.

public class webRule extends Rule – regulă cu scor pentru anafora nominală ce folosește interogari web pentru determinarea unei probabilități de existență a unei relații de referință între candidat și attr. Este trimisă o interogare unui motor de căutare (Google) printr-un socket, folosind protocolul HTTP și comanda GET. Interogarea este construită pe baza lemelor atrr-ului și DE-ului candidat și ținând cont de numărul lexical. Pagina primită drept rezultat este prelucrată pentru a determina numărul de pagini (ce conțin șirul de interogare) găsite de motorul de căutare. Este cosiderat rezultatul căutării semnificativ, dacă se obțin mai mult de 50 de pagini.

Clase adăugate:

Extractorii – clase care extrag din adnotare sau găsesc (pe baza adnotării și a altor surse de cunoștere) valori pentru un atribut al unui Atrr:

public class AppositionExtractor extends DefaultHandler – parsează textul de intrare (fișier XML) și pentru un NP (este trimis ca paramentru ID-ul său) găsește apozițiile;

public class DetExtractor extends DefaultHandler – parseaza xml-ul și extrage informații (partea de vorbire, lema, număr) despre “determinații” unui grup nominal pe care le memorează folosind clasa DET;

public class GenderExtractor extends DefaultHandler – parsează xml-ul (trimis ca parametru) și pentru un NP (este trimis ca paramentru ID-ul său) extrage genul lexical (este de fapt un atribut al tagului folosit pentru memorarea unui cuvânt);

public class GroupParser extends DefaultHandler – parsează xml-ul și determină grupurile posibile din care un grup nominal ar putea face parte. Pentru un cuvânt din propoziție este determinat tipul său (person, being, object, concept, action) și numărul “propoziției” (Am considerat propoziție toate cuvintele la început până la primul punct sau toate cuvintele dintre două puncte). Numărul propoziției este determinat practic numărând semnele de puctuație “.” din textul ce precede grupul nominal respectiv. Grupurile sunt determinate ținând cont de aceste informații. La început sunt construite grupuri formate dintr-un singur element, apoi sunt unite grupurile care au același tip și fac parte din aceeași propoziți. Sunt păstrate doar grupurile cu mai mult de un membru, din care face parte și grupul nominal primit ca parametru.

public class LemmaExtractor extends DefaultHandler – parsează textul de intrare (trimis ca parametru) și pentru un NP (este trimis ca paramentru ID-ul său) extrage lema (este de fapt un atribut al tagului folosit pentru memorarea unui cuvânt);

public class NumberExtractor extends DefaultHandler – parsează textul de intrare (trimis ca parametru) și pentru un NP (este trimis ca paramentru ID-ul său) extrage numărul lexical (este de fapt un atribut al tagului folosit pentru memorarea unui cuvânt);

public class PersonExtractor extends DefaultHandler – parsează textul de intrare (trimis ca parametru) și pentru un pronume (este trimis ca paramentru ID-ul său) extrage persona – categorie gramaticală folosită mai departe pentru determinarea genului;

public class POSExtractor extends DefaultHandler – parsează textul de intrare (trimis ca parametru) și pentru un NP (este trimis ca paramentru ID-ul său) extrage partea de vorbire (substantiv, pronume, determinant, semn de punctuație, etc.);

public class RoleExtractor extends DefaultHandler – parsează textul de intrare (trimis ca parametru) și pentru un NP (trimis prin ID-ul său) extrage funcția sintactică ;

public class TypeExtractor extends DefaultHandler – parsează textul de intrare (trimis ca parametru) și pentru un substantiv extrage tipul – propriu sau comun (este de fapt un atribut al tagului folosit pentru memorarea unui cuvânt);

public class ProperNames – clasă folosită pentru gestionarea numelor proprii (citite și salvate într-un fișier serializate). Pentru fiecare nume propriu este instanțiat un obiect NP (ce memorează lema, genul și tipul – pesoană, companie) ce este serializat și salvat într-un fișier. Pot fi adăugate, șterse, modificate numele proprii. Pot fi salvate în alt fisier sau poate fi încărcat un alt fișier cu nume proprii.

Alte clase folosite:

public class DET – clasă folosită pentru memorarea unui “determinant”;

public class elem– clasă folosită pentru memorarea unui membru al unui grup;

public class Group– clasă folosită pentru memorarea unui group; pentru un grup se memorează tipul, numărul propoziției și membrii săi (într-un vector).

public class PN implements Serializable – clasă folosită pentru memorarea unui nume propriu.

Evaluarea aplicației

Am testat aplicația pe un set de 35 de texte și am observat că anafora pronomială nu este rezolvată cu o precizie foarte mare, în schimb pentru anafora nominală și cea funcțională rezultate destul de bune. În Anexa 1 sunt listate o parte din textele XML adnotate folosite pentru testare și textele cu rezultatele obținute.

Nu am putut testa modelul meu pe același text pe care au fost testate celelalte modele implementate și incluse în GenFrame datorită modului de acces la WordNet folosit. Pentru accesul la WordNet am folosit niște clase scrise în limbajul Java de Oliver Steele ([anonimizat]) speciale pentru acest lucru. Însă nu permit multe accese la WordNet, așa cum necesită modelul meu în cazul unui text mai mare.

Rezulatele evaluării sunt:

Pentru toate anaforele:

precizia = 85 / 98 = 86,73%;

recall = 85 / 97 = 97,70%

Pentru coreferința nominală :

precizia = 38 / 42 = 90,47%;

recall = 38 / 48 = 79,16%

Pentru anafora funcțională :

precizia = 24 / 25 = 96%;

recall = 24 / 26 = 92,30%

Pentru coreferința pronominală :

precizia = 23 / 31 = 74,19%;

recall = 23 / 23 = 100%

Aplicația mea găsește și anafore care nu există în realitate în textul respectiv (găsește referițe între elemente din text între care nu există nici o legătură referențială). Ca o consecință a acestui lucru recall-ul obținut este mai mare decât precizia.

Folosirea interogărilor web îmbunătățește rata de suces în cazul anaforei nominale și funcționale pentru că există anafore care nu pot fi rezolvate folosind doar WordNet-ul.

Modelul propus de mine are rezultate mai bune în cazul rezolvării unor cazuri dificile de anaforă, și în cazul anaforei funcționale. Anafora pronomială nu este rezolvată cu o precizie foarte mare. Există mulți algoritmi specializați pentru rezoluția anaforei pronomiale cu rată de succes mai bună.

Pentru mărirea performanței ar trebui dezvoltate regulile pentru rezolvarea anaforelor pronomiale pentru care antecedentul este un grup nominal. De asemenea ar trebui modificate regulile ce folosesc WordNet-ul, pentru a nu mai găsi anafore ce nu există de fapt. De exemplu regula cu scor ce folosește definițiile cuvintelor oferite de WordNet ar trebui să fie mai restrictivă.

Rezultatele obținute în urma evaluării arată că algoritmul propus este eficient.

CAPITOLUL V – Concluzii

Din greutăți se ivesc minunile. (La Bruyere)

Rezoluția anaforei are un rol vital în multe aplicații de prelucrare a limbajului natural cum ar fi traducerea automată, abstractizarea automată, rezumarea automată.

Rezoluția automată a anaforei este o sarcină complexă care necesită diferite surse de cunoaștere și care poate fi privită ca un proces în trei etape: identificarea anforilor, găsirea candidaților și selecția antecedentului cu ajutorul unui algoritm de rezoluție (bazat pe reguli).

Primii algoritmi de rezoluție a anaforei folosesc euristici simple cum ar fi potrivirea ([Bobrow, 1964]), sau euristici mai complexe ([Winograd, 1972]) obținând rezultate remarcabile pentru timpul respectiv. Algoritmii de mai târziu au evoluat pe măsură ce mai multe elemente teoretice despre diferite tipuri de anaforă au fost stabilite. Sunt folosite in mod extensiv informațile lingvistice și ne-ligvistice ([Carter, 1986], [Carbonnell & Brown, 1988], [Rich & LuperFoy, 1988], [Sider, 1979], [Wilks, 1973]), și din această cauză lucrările au o valoare practică mai mică, implementările fiind limitate sau inexistente. Ca urmare, evaluarea (în condiții actuale) este dificilă. Oricum, proiectele despre rezoluția anforei din anii ‘60, ‘70 și ’80 sunt remarcabile pentru că prezintă câteva probleme fundamentale și modele sofisticate. Unele abordări dezvoltate (de exemplu [Hobbs 1976, 1978], [Brennan et al., 1987]) sunt puncte de referință și sunt citate în literatura de specialitate acctuală.

Cele mai recente cercetări în rezoluția anaforei sunt orientate spre soluții robuste și bazate pe puține surse de cunoaștere ce oferă suport pentru aplicații practice cum ar fi extragerea de informații și rezumarea textelor. În plus, acum dezvoltatorii beneficiază de existența unui corpus și sunt conștienți de necesitatea evaluării pentru a vedea unde se situează o anume abordare. Dacă cercetătorii din anii 1970 sau 1980 abia își punea problema evaluării, astăzi nici un proiect nu va fi luat în serios dacă nu sunt reportate rezultatele evaluării. Oricum compararea diferitelor abordări într-un mod corect și consistent rămâne dificilă pentru că, de obicei, evaluarea se face pe texte (date de intrare) diferite deoarece fiecare abordare necesită un alt grad de pre-procesare a textului.

Textele adnotate cu legăturile anaforice și coreferențiale sunt importante pentru cercetarea în domeniu rezoluției anaforei. Ele constituie o sursă valoroasă de a obține date și reguli empirice pentru realizarea unor noi algoritmi de rezoluție a anaforei, pentru învățare, optimizare și evaluare a algoritmilor existenți.

Evaluarea algoritmilor pentru rezoluția anaforei și a sistemelor de rezoluție a anaforei ar trebui făcute separat. Există o serie de mărimi de evaluare. Compararea corectă a metodelor presupune nu doar ca evaluarea să se realizeze pentru aceleași date, dar și pentru aceleași unelte de pre-procesare.

Genframe este un model incremental pentru rezoluția relațiilor anaforice complexe. Acest model suportă diferite tipuri de amânare a rezoluției.Este posibilă o rafinare mai mare a algoritmului. Mecanismul actual de identificare a antecedentului nu este suficient detaliat. Autorii cred că abordarea corectă este o combinație între procesarea incrementală și alte criterii de identificare a antecedentului.

GenFrame permite:

definirea și rafinarea modelelor ușor;

comparare ușoară între modele:

posibilitatea de a integra diferite abordări;

amânarea rezoluției în caz de incertitudine;

Modelul propus și implementat tratează:

anafora nominală cu ajutorul interogărilor web și a WordNet-ului

RE-urile "încuibărite" prin folosirea atributul belongs-to;

apoziția dacă o sursă externă oferă acestă informație;

referințe de tipul subiect – nume predicativ prin folosirea unui atribut same-as;

anaforele pentru care anaforul și antecedentul au leme diferite, număr lexical diferit, dar același număr semantic folosind relațiile definite de WordNet și interogări web cu ajutorul unui motor de căutare;

anaforele cu antecedenți splitați prin găsirea grupurilor posibile clasificând RE-urile în clase (persoană, obiect, acțiune, etc) cu ajutorul WordNetului.

Modelul propus și implementat nu găsește anaforele pronomiale pentru care antecedentul este un grup nominal.

Algoritmul de rezoluție a anaforei descris de modelul meu a obținut în urma evaluării pe 35 de texte o precizie de 86,73% și un recall de 97,70%. Pentru anafora nominală și pentru cea funcțională se obține o precizie mai mare de 90,47%, respectiv de 96%. Precizia pentru anafora nominală este mai mică din cauza folosirii WordNet-ului. Anafora pronomială nu este suficient tratată de model.

Algoritmul meu este indicat pentru anafora nominală și cea funcțională.

Ce ar mai trebui facut?

rezolvarea anaforelor pronomiale mai eficient;

îmbunătățirea modului de acces la WordNet și folosirea pentru testare a unui text mai mare;

rafinarea interogărilor Web folosite pentru rezolvarea anaforei nominale;

includerea unui modului de învățare pentru rafinarea scorurilor regulilor și pragurilor;

folosirea informațiilor aduse de adjective și prepoziții.

Bibliografie

Bunescu, Răzvan – Associative anaphora Resolution: A Web-Based Approach, University of Texas at Austin;

Cristea, Dan – Lingvisitcă computațională – curs, Universitatea “A. I. Cuza”, Facultatea de Informatică, Iași, 2003;

Cristea, Dan; Dima Gabriela – An Integrating Framework for Anaphora Resolution, Universitatea “Al. I. Cuza”;

Cristea, Dan; Postolache, Oana-Diana; Dima, Gabriela-Eugenia; Barbu,Catalina – AR-Engine – a framework for unrestricted co-reference resolution, Universitatea “Al. I. Cuza , 2002;

Davies, S.; Poessio, M. – Coding Schemas for Co-reference, 2000

Dennett, Daniel C. – The Role of Language in Intelligence, Cambridge Univ. Press, 1994;

Fogel, David B. – Blondie24, Playing at the Edge of AI, Morgan Kaufmann Publishers, 2002;

Grosz, Barbara J; Joshi, Aravind K. & Weinstein, Scott, Centering: A framework for modelling the local coherence of discourse, Computational Linguistics, 1995.

Kennedy, C., Boguraev, B. 1996. Anaphora for Everyone: Pronominal Anaphora Resolution without a Parser, 16th International Conference on Computational Linguistics, vol. 1;

Lust, Barbara – Introducere la Studies in the Acquisition of Anaphora, D. Reidel, 1986

Markert, Katja; Nissi, Malvina; Modjeska, Natalia N. – Using the Web for Nominal Anaphora Resolution, University of Edinburgh;

Meyer, Josef; Dale, Robert – Using the WordNet Hierarchy for Associative Anaphora Resolution, Centre for Language Technology Macqarie University Sydney;

Mitkov, Ruslan – Anaphora Resolution, Longman, 2002

Mitkov, Ruslan – Evaluation in anafora resolution, University of Wolverhampton, 2001;

Poesio, Massimo – What is ‘coreference’?