Claudiu Musat
email: claudiu.musat@cs.pub.ro

Marian-Andrei Rizoiu
email: marian-andrei.rizoiu@univ-lyon2.fr

Stefan Trausan-Matu

Claudiu Muşat

Ştefan Trauşan-Matu

O metodă pentru evaluarea şi îmbunătăţirea performanţelor sistemelor de extragere a topicelor

Keywords: Modelarea Topicelor, WordNet, Ontologie, LDA, Subarbore, Evaluare, Îmbunătăţire Topic Modeling, WordNet, Ontology, LDA, Subtree, Evaluation, Improvement

HAL is

Introducere

Una din provocările zilelor noastre este informaţia, mai precis cantitatea de informaţie furnizată zilnic pe internet. Aceasta ajută utilizatorii să creeze (folosind platforme de genul blogurilor, chat-urilor etc) şi să partajeze (folosind reţele sociale) informaţie. Aceasta se găseşte, de obicei, în format nestructurat (cel mai adesea în limbaj natural), opus al formatărilor structurate: tabele, formulare. Dat fiind faptul că importanța economică a informaţiei nestructurate este din ce în ce mai mare (reclame pe reţele sociale, suite de aplicații gen Facebook etc.), unul dintre subiectele de cercetare des abordate în ultimul deceniu este Extragerea Automată de Informații din textele în Limbaj Natural.

Una dintre pistele explorate de cercetători este Extragerea de Topice. Dată fiind o colecţie de texte în limbaj natural (deseori provenite din internet, ex: bloguri, articole de ziar) se doreşte extragerea automată a subiectelor abordate în textele colecţiei (de exemplu politică, economie, sport). Această posibilitate ar fi de un enorm ajutor pentru toate domeniile unde se lucrează cu cantităţi mari de text: inventarierea articolelor, filtrarea mailurilor nedorite etc.

Subiectele care apar în textele unei colecţii sunt numite în literatura de specialitate topice. Făcând o paralelă cu conceptele, Rizoiu şi Velcin (2010) ne arată că nu există o definiție larg acceptată a topicelor. În timp ce unii cercetători consideră un topic ca fiind o simplă regrupare a unor texte ce împărtăşesc aceeaşi tematică, alţii văd topicele ca pe nişte abstractizări ale grupurilor de texte, fie materializate lingvistic (un cuvânt, o expresie, o propoziţie), fie sub forma unui set de perechi cuvânt-probabilitate. În secţiunile următoare vom considera topicul ca o distribuţie de probabilităţi, unde fiecare valoare numerică reprezintă probabilitatea ca un cuvânt să aparţină unui topic.

Dat fiind faptul că distribuţiile de probabilităţi sunt ilizibile pentru un utilizator uman, au fost propuse sisteme care asociază expresii relevante fiecărui topic pentru a-l rezuma (Rizoiu, Velcin și Chauchat, 2010;[START_REF] Geraci | Cluster generation and cluster labelling for web snippets: A fast and accurate hierarchical solution[END_REF]Osinski și Weiss, 2004).

Cu toate că literatura ne oferă multe exemple de sisteme de extragere a topicelor, unele dintre ele fiind prezentate în secțiunea următoare, problema este departe de a fi rezolvată. Rezultatele sunt deseori afectate de zgomot, proprietăţi speciale ale cuvintelor (cum ar fi polisemia), dimensiunea setului de texte etc. O altă problematică sensibilă este evaluarea calităţii topicelor.

Creşterea în popularitate a modelelor de topice a dus şi la generalizarea presupunerii că acestea conţin în mod automat informaţii utile şi purtătoare de semnificaţie. Însă, deoarece extragerea topicelor este un proces nesupervizat, a demonstra aceste afirmaţii este un proces dificil. Acest obstacol este amplificat şi de faptul că nu există un standard general acceptat cu care să fie comparate modelele studiate. Totodată, deşi s-a depus un volum considerabil de muncă în găsirea unor algoritmi din ce în ce mai performanţi şi a unor modele îmbunătăţite, comparativ foarte puţin efort a fost dedicat stabilirii unor metode obiective de evaluare a acestora.

În această lucrare propunem o medodă de evaluare complementară celor deja existente, bazată pe caracteristicile intrinseci ale modelelor de topice analizate, şi nu pe documentele din care acestea au rezultat. Folosim apoi această nouă metrică pentru a demonstra posibilitatea îmbunătăţirii acestor parametri cu ajutorul datelor dintr-o ontologie binecunoscută, WordNet (Feldbaum, 1998). Prezentăm două modalităţi de îmbunătăţire ale caracteristicilor unui model de topice -în primă instanţă acţionând asupra topicului la nivel individual şi apoi asupra întregului model.

Expunerea continuă cu descrierea cadrului şi a abordărilor relevante din domeniile conexe în secţiunea 2, acestea fiind urmate de prezentarea metodei propuse în secţiunea 3, rezultatele experimentelor şi concluziile fiind expuse în părţile 4 şi 5.

Abordări relevante

Așa cum am arătat în secțiunea anterioară, sistemele de extragere de topice au utilizări multiple. De aceea, când vine vorba de clasificarea lor, autorii folosesc criterii diferite. De exemplu, în (Rizoiu și Velcin, 2010) algoritmii sunt împărțiți în funcţie de partiţiile pe care le crează. Pornind de la observaţia că un text poate să se refere la mai multe tematici în același timp (de exemplu efectele economice ale unei decizii politice), autorii argumentează că textele trebuie să aibă posibilitatea să facă parte din mai multe grupuri în același timp.

Un alt criteriu, pe care îl vom folosi şi noi în continuare, este capacitatea algoritmilor de a lucra direct cu text (de exemplu, LDA [START_REF] Blei | Latent dirichlet allocation[END_REF]) sau dacă este nevoie de o tratare iniţială. Cei din a doua categorie sunt algoritmi de clustering, adaptaţi pentru regruparea textelor folosind Modelul Spațiului Vectorial (Salton, Wong, şi Yang, 1975).

Algoritmi bazaţi pe clustering

Clusteringul (clusterizarea), sau regruparea automată nesupervizată, este o tehnică prin care un set de indivizi este partiţionat în mulţimi, bazat pe similitudinea trăsăturilor (variabilelor) cu ajutorul cărora indivizii sunt descrişi. Deşi aceştia au fost creaţi pentru a prelucra date numerice, pot fi adaptați pentru text prin traducerea prealabilă a acestuia în Modelul Spaţiului Vectorial, introdus de Salton, Wong, şi Yang (1975). În principiu, fiecare text devine un vector într-un spaţiu n-dimensional. Fiecărui cuvânt din colecţia de texte îi corespunde o dimensiune, iar valorile numerice corespunzătoare fiecărui document pentru fiecare cuvânt sunt determinate folosind o schema de ponderare a cuvintelor (prezență/absență, frecvența cuvintelor în text, TF-IDFfrecvenţa termenilor înmulţită cu inversul frecvenţei documentelor în care apar termenii).

Rezultatul algoritmilor trecuți în revistă mai jos este de obicei un "centroid". Acesta este un vector n-dimensional, descris în același spațiu ca şi restul documentelor. El reprezintă centrul grupului de texte şi poate fi privit ca o abstractizare a acestora. Deşi centroizii nu sunt distribuţii de probabilităţi, într-o anumită măsură putem să îi considerăm similari acestora şi să aplicăm măsurile de evaluare propuse în secţiunile următoare.

KMeans [START_REF] Macqueen | Some methods of classification and analysis of multivariate observations[END_REF] este unul dintre cei mai cunoscuţi algoritmi de clustering. A fost îndelung folosit şi numeroase articole i-au demonstrat acurateţea. Algoritmul optimizează iterativ un criteriu obiectiv, de obicei o funcție de tipul erorii pătratice. În cazul clusteringului textual, distanţa bazată pe cosinus este folosită pentru a calcula similitudinea dintre texte.

Bisecting KMeans [START_REF] Steinbach | A comparison of document clustering techniques[END_REF] este o variantă ierarhică a KMeans, care s-a demonstrat a fi mai precisă pentru clusteringul textual. Este bazat pe un algoritm descendent care divide la fiecare pas documente în 2 sub-clustere. De exemplu, la primul pas întreaga colecție este divizata în două clustere. La pasul următor, unul dintre grupuri este selectat şi împărţit iarăși în două subgrupuri. Per total obținem trei clustere. Procesul se repetă până când o condiţie de oprire este îndeplinită (de exemplu un număr fixat de clustere).

Fuzzy KMeans [START_REF] Dunn | A fuzzy relative of the isodata process and its use in detecting compact wellseparated clusters[END_REF] este o adaptare a algoritmului KMeans folosind logica fuzzy. În clusteringul de tip fuzzy, fiecare document aparține fiecărui grup într-o anumită măsură, în loc să aparțină integral unui singur grup. De asemenea, documentele care sunt mai departe de centrul grupului aparţin acestuia într-o măsură mai mică decât cele centrale. În Fuzzy Kmeans, documentele contribuie la calculul centroidului corespunzător în funcție de gradul lor de apartenenţă la grupul respectiv.

Latent Semantic Indexing [START_REF] Berry | Using linear algebra for intelligent information retrieval[END_REF] este un algoritm statistic de extragere de topice, bazat pe descompunerea în valori singulare. Ideea principală a algoritmului este să descompună matricea cuvânt/document într-un produs de trei matrici: A = USV T . U și V sunt matrici ortogonale ce conțin valorile singulare la dreapta și la stânga, iar S este o matrice diagonala având valorile singulare ale lui A ordonate descrescător. Dacă reţinem doar primele k valori singulare și le eliminăm pe restul, împreună cu coloanele și rândurile corespunzătoare din U, respectiv V, obținem produsul A k = USV T , o k-aproximare a lui A. Coloanele din U crează o bază ortogonală pentru spaţiul documentelor, deci fiecare document poate fi scris ca o sumă ponderată:

d i = α 1 e 1 + α 2 e 2 + ... + α k e k
Astfel, elementele e l , l ∈ {1..k} ale bazei pot fi considerate ca niște centroizi, iar α i probabilitatea ca documentul d i să aparțină clusterului j.

Overlapping KMeans (OKM) [START_REF] Cleuziou | Okm : une extension des k-moyennes pour la recherche de classes recouvrantes[END_REF] este o extensie recentă a bine-cunoscutului KMeans. Funcționează într-un mod similar, încercând să minimizeze o funcţie obiectivă. Principala diferența este în OKM, un document poate fi asociat mai multor clustere. Dacă în KMeans, un individ era asociat centroidului cel mai apropiat, măsurat cu distanţa cosinusului, OKM calculează o imagine a centroidului, adăugând documente la cluster până când distanța dintre el și imagine este minimă. Această imagine este centrul de greutate documentelor din cluster.

Desigur, în afară de algoritmii prezentați mai sus, exista multi alţii. Unii dintre ei au chiar și capacitatea de a asocia o expresie pertinentă pe post de nume, de exemplu AGAPE (Velcin şi [START_REF] Steinbach | A comparison of document clustering techniques[END_REF]. Majoritatea acestora prezintă la ieşire câte un centroid pentru fiecare clasă, ceea ce dă posibilitatea de a utiliza metoda propusa în secțiunea "Sistemul propus" pentru a evalua calitatea topicelor extrase de fiecare din aceste sisteme.

Algoritmi bazați pe distribuția de probabilități

Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF] este un algoritm probabilist generativ creat special pentru a extrage topice direct din text. LDA consideră documentele ca o colecție de cuvinte şi modelează fiecare cuvânt dintr-un document ca un eşantion dintr-un amestec de modele: fiecare componentă a amestecului poate fi văzută ca un "topic". Deci, fiecare cuvânt este generat de un singur topic, dar cuvinte diferite dintr-un document sunt, în general, generate de topice diferite. Fiecare document este reprezentat ca o listă de proporții diferite pe fiecare componentă a amestecului, deci redus la o distribuție de probabilităţi pe un set fixat de topice.

LDA este asemănător cu "probabilistic Latent Semantic Analysis" (pLSA), cu excepția faptului că în LDA distribuția de topice se presupune a fi o distribuție Dirichlet. Acest fapt este foarte important din cauză că permite rezolvarea principalelor limitări ale pLSA: supra-specializarea şi imposibilitatea de a face inferențe adevărate pe documente noi [START_REF] Blei | Latent dirichlet allocation[END_REF]. Mai precis, LDA este bazat pe un proces ierarhic și generativ. Hiperparametrii α și β sunt bazele celor 2 distribuţii Dirichlet. Prima distribuţie Dirichlet controlează modelul de amestecuri pentru fiecare din cele |D| documente. A doua distribuție controlează generarea amestecului de cuvinte pentru fiecare dintre cele K topice. Deci, fiecare topic este o distribuție a celor W cuvinte din vocabular.

Procesul generativ este următorul: pentru fiecare cuvânt w d,i din vocabular, generează un topic z dependent de amestecul θ asociat documentului d și apoi generează un cuvânt din topicul z. Demn de notat este faptul că acele cuvinte care nu au o relevanță specială (articole, prepoziții) vor avea aproximativ aceeași probabilitate pentru fiecare clasă sau pot fi puse într-o clasa aparte. Determinarea parametrilor θ și z, iar uneori a hiper-parametrilor α și β, se poate dovedi dificilă pentru că posteriorul p(θ, z/D, α, β, K) nu poate fi calculat cu precizie din cauza sumei infinite de la numitor. De aceea sunt folosiți diferiţi algoritmi de aproximare, cum ar fi EM, Monte-Carlo, procese Markov etc.

O abordare probabilistică ca aceasta prezintă o serie de avantaje și dezavantaje :

Fundamentul teoretic este bine cunoscut în statistica bayesiana şi a fost îndelung folosit. Este creată pentru a crea inferenţe pe documente noi, dar apar probleme: care sunt topicele asociate şi în ce proporţii? Care parte a documentului este asociată cu ce topic? În funcție de probabilitatea p(d/Θ), poate un document nou să fie descris de amestecul original de topice sau de un topic nou, care nu a mai fost văzut înainte?

LDA nu prezintă la ieşire un centru pentru fiecare cluster, ci o distribuţie a documentelor în funcție de topice. Acest fapt prezintă o serie de dificultăţi în asocierea unui nume lizibil (detalii în Introducere). Lucrări recente încearcă să găsească metode de a asocia nume topicelor găsite de LDA folosind n-grame (Wang, McCallum şi Wei, 2007);

Ca şi celelalte modele prezentate, această metoda probabilistică nu rezolvă problema clasică a găsirii optimului global și a găsirii numărului K de topice. Pentru a doua problemă au fost propuse metode inspirate din selecția de modele (Rodriguez, 2005).

Algoritmul LDA doar a deschis calea, multe alte modele fiind propuse ulterior pentru a corecta diferite hibe ale modelului inițial: extragerea de arbori de topice (hLDA) [START_REF] Blei | Hierarchical topic models and the nested Chinese restaurant process[END_REF], inducerea unei structuri de corelație între topice (Lafferty şi Blei, 2005), modelarea topicelor dinamice în timp (Blei şi Lafferty, 2006), folosirea de n-grame în loc de cuvinte simple pentru a descrie topicele (Wang, McCallum şi Wei, 2007) etc.

WordNet

Între sistemele de gestionare şi stocare de cunoştinţe, ontologiile ocupă un loc important, între acestea una dintre cele mai cunoscute fiind WordNet (Fellbaum, 1998). Creată la Princeton, această ontologie grupează conceptele limbii engleze, reprezentate atât prin cuvinte cât şi prin grupuri de cuvinte, în mulţimi de sinonime, synsets. Fiecare astfel de mulţime defineşte un concept lexical, şi poate fi reprezentat prin o colecţie de substantive, adjective, adverbe sau verbe. Trebuie menţionat faptul că unui cuvânt din vocabular îi pot corespunde mai multe sensuri, acestea fiind omonime între ele.

Între conceptele astfel definite există unul sau mai multe tipuri de relaţii, între care se evidenţiază cele de hiper şi hiponimie, antonimie sau holonimie. Un caz particular este reprezentat de relaţiile de hiper şi hiponimie, care, aplicate substantivelor crează un arbore cu rădăcina în cel mai general concept -entity.

Ideea de a folosi ierarhia de concepte în modelarea topicelor a mai fost abordată de [START_REF] Graber | A Topic Model for Word Sense Disambiguation[END_REF] care împreună cu inventatorul LDA, Blei, au creat o versiune modificată a acestui algoritm, versiune care are la bază ideea de drum în WordNet. Potrivit acestei teorii, cuvintele ce corespund unor concepte apropiate din ierarhia din WordNet au şanse mai mari să apară împreună intr-un text. Folosind componenţa topicelor la finalul rulării, s-a putut realiza discriminarea între diferitele sensuri ale cuvintelor din experiment.

Evaluarea modelelor de topice

Conform rezultatelor prezentate atât în [START_REF] Blei | Latent dirichlet allocation[END_REF] cît şi în (Laffery şi [START_REF] Lafferty | Correlated topic models[END_REF], LDA este, alături de CTM, printre cei mai precişi algoritmi generatori de modele probabilistice. Totodată un avantaj important al LDA din punct de vedere al combinării metodei cu date din WordNet este faptul că majoritatea conceptelor din ontologie sunt unigrame. Astfel putem folosi direct relaţiile dintre cuvintele prezente în topice şi conceptele lor omonime.

Cele mai multe metrici folosite frecvent în literatura de specialitate sunt metrici predictive. Acestea descriu capacitatea unui model de a procesa un corpus nou de documente de test după ce au fost antrenate în prealabil. Completarea documentelor [START_REF] Rosen-Zvi | The author-topic model for authors and documents[END_REF] este una dintre cele mai cunoscute metode de evaluare a performanţelor unui model de topice. Se bazează pe faptul că, dat fiind un model şi o primă jumătate a unui document, probabilitatea ca acesta să fie urmat de cea de-a doua jumătate din textul original trebuie să fie mare. Această probabilitate stă la baza funcţiei de evaluare a modelului. [START_REF] Wallach | Evaluation Methods for Topic Models[END_REF] a demonstrat că metodele folosite în prealabil pentru evaluarea topicelor, inclusiv media armonică sau completarea documentelor dau rezultate necorespunzătoare majoritatea timpului. Totodata a fost prima care a realizat un studiu dedicat acestor metode şi a realizat una proprie, extensibilă la modelele mai complexe.

O metodă originală este cea descrisa de [START_REF] Chang | Reading Tea Leaves: How Humans Interpret Topic Models[END_REF], în care aceştia folosesc adnotarea umană pentru a evalua modelele şi totodată pentru a detecta trăsături noi ale acestora. Aceştia injectează printre cele mai importante cuvinte dintr-un topic unele diferite şi prezintă mulţimea rezultată unui evaluator uman. Apoi demonstrează că, dacă topicul iniţial era unul coerent, evaluatorul reuşeşte să diferenţieze cuvintele adăugate de cele iniţiale. Folosind rata de succes a evaluatorului, aceştia determină calitatea topicelor, iar rezultatele sunt similare cu cele obţinute în (Laffery şi [START_REF] Lafferty | Correlated topic models[END_REF].

Cu toate acestea, nici Wallach, nici Chang nu folosesc în metodele lor caracteristicile intrinseci ale distribuţiilor, ci tratează fiecare model în parte ca o unitate distinctă. În unele aplicaţii însă, cum este adnotarea topicelor, este necesară o viziune mai aprofundată, fiecare topic în parte fiind purtător de informaţie relevantă.

Un corolar al faptului că modelele de topice au fost pană acum considerate elemente unitare şi indivizibile este faptul că, din câte ştim, aceasta este prima încercare de a îmbunătăţi calităţile modelelor modificându-le componenţa.

Sistemul propus

Aşa cum s-a observat şi în [START_REF] Chang | Reading Tea Leaves: How Humans Interpret Topic Models[END_REF], caracteristicile cele mai importante ale unui topic pot fi sumarizate de cele mai importante cuvinte ale acestuia, în cazul LDA acestea fiind cele a căror probabilitate dat fiind topicul este cea mai mare. Astfel fiecare topic poate fi descris ca o mulţime de cuvinte care îl reprezintă. Notăm cu mulţimea cuvintelor relevante pentru topicul i, unde , fiind numărul de topice al modelului.

Acoperire şi redundanţă

Fie N numarul de cuvinte diferite prezente în corpusul iniţial de texte din care, folosind LDA, sunt extrase topicele. Definim acoperirea modelului ca procentul de cuvinte din total care se regăsesc în reuniunea mulţimilor cuvintelor relevante ale tuturor topicelor.

Un model în care toate cuvintele din vocabular se regăsesc în modelul final nu este însă neapărat unul reuşit. Este necesară contrabalansarea acoperirii cu specificitatea, astfel încat fiecărui topic să îi corespundă cuvinte pe cât posibil diferite de ale celorlalte topice. Definim astfel redundanţa topicelor ca numărul de cuvinte care se găsesc în două sau mai multe topice Reunind cele două concepte, ambele normalizate cu numărul de cuvinte din dicţionar N, obţinem o funcţie care relevă caracteristicile topicului dat Menţionăm că atât redundanţa cât şi acoperirea topicelor sunt concepte care în contextul evaluării topicelor nu au mai fost utilizate în prealabil.

Îmbunătăţirea topicelor

După definirea metricii de calitate a sistemului dorim să aducem îmbunătăţiri modelelor studiate, care apoi să fie analizate conform metricii anterioare. Îmbunătăţirile sunt realizate în două moduri -prin îndepărtarea cuvintelor conceptual diferite sau a topicelor redundante. Eliminarea de topice poate avea loc atât bazându-ne pe toate sensurile asociate cuvintelor conţinute, cat şi doar pe un subset reprezentativ al acestora.

Subarbori WordNet asociaţi topicelor

Sarcina de a găsi cuvintele neînrudite nu este uşor rezolvată folosind o simplă distanţă peste WordNet deoarece fiecare cuvânt dintr-un topic poate corespunde mai multor sensuri din WordNetuneori de ordinul zecilor. Această complicaţie exclude posibilitatea folosirii unor simpli algoritmi de clustering cum ar fi kMeans.

Pentru a găsi cuvintele neînrudite cu majoritatea celor dintr-un topic, vom defini o structură peste arborele creat de synset-urile substantive cu relaţia de hipernimie sau hiponimie din WordNet. Aceasta structură va fi un subarbore al arborelui ce conţine toate synset-urile cu proprietatea că acesta conţine toate synset-urile asociate cuvintelor din un topic dat.

Generarea acestui subarbore este incrementală -pornind de la mulţimea de concepte direct asociate cuvintelor din topice adăugam acesteia toate conceptele părinte, pana la rădăcina arborelui, entity. Mulţimea finală rezultată, împreună cu relaţiile de tip "e un" (is a) dintre concepte va reprezenta subarborele ce acoperă în întregime topicul, S(t i ). Fiecare nod c din acest arbore poate fi însă considerat rădăcina unui subarbore S c (t i ), inclus în S(t i ).

Evaluarea subarborilor

Fiecare subarbore este evaluat în funcţie de specificitatea şi acoperirea sa, cu referire la topicul dat. Definim acoperirea unui subarbore cu rădăcina într-un nod dat ca numărul de cuvinte din topic care au cel puţin un sens asociat care face parte din structură. Într-un exemplu din lumea animală, dacă un topic ar conţine numai trei cuvinte relevante (cat, dog, idea) atunci conceptele cat#n#1şi dog#n#1 ar fi ambele radăcinile unui arbore de acoperire 1, pe când părintele lor comunanimal#n#1ar avea o acoperire de 2 iar rădăcina celui mai extins arbore ar avea o acoperire maximă, de 3 (egală cu numărul total de cuvinte din topic).

O metodă pentru evaluarea şi îmbunătăţirea performanţelor sistemelor de extragere a topicelor 11 Este evident că acele concepte foarte generale, aflate aproape de rădăcina arborelui cel mai cuprinzător vor avea o acoperire mare în comparaţie cu cele aflate mai jos în ierarhie. De aceea este necesară şi introducerea unui factor care să măsoare specificitatea fiecărui subarbore în parte. Cu cât un nod este mai aproape de rădăcină, cu atat mai mică este specificitatea sa.

Definim înălţimea unui nod ca distanţa sa până la rădăcina arborelui iar adâncimea nodului ca distanţa maximă dintre el şi conceptele direct asociate cuvintelor din topic. Distanţa în acest caz este măsurată în numărul de tranziţii necesare pentru a ajunge parcurgând ramurile arborelui de la un nod la celălalt. Ajungem astfel la o valoare pentru funcţia de evaluare a fiecărui nod unde d,h,c sunt în ordine adâncimea, înălţimea şi acoperirea sa, iar ponderile corespunzătoare, stabilite a priori.

Eliminarea cuvintelor neînrudite

După faza de construcţie a subarborelui corespunzător unui topic şi evaluarea individuală a fiecarui nod, cuvintele neînrudite pot fi definite ca acele cuvinte aparţinând topicului care au toate sensurile pe ramuri ale subarborelui cu o valoare mică a funcţiei de evaluare.

Un exemplu ar fi cel al topicului ipotetic anterior (cat, dog, idea), în care cel mai depărtat cuvinte de celelalte este idea. Cum este valoarea maximă a funcţiei iar conceptele corespunzătoare cuvântului idea nu aparţin subarborelui lui animal#n#1, acesta va fi considerat cel mai îndepărtat din model.

Eliminarea şi contopirea topicelor redundante

Pentru o pereche de topice t i , t j determinăm similaritatea acestora pornind de la valoarea funcţiei de evaluare pentru toate nodurile comune ale subarborilor asociaţi, reţinând minimul dintre cele două valori şi însumând Două topice care au similaritatea mai mare decât un prag prestabilit pot fi considerate redundante. Pentru grupurile de topice redundante prezentăm două opţiunisuprimarea topicelor iniţiale redundante şi menţinerea unui singur reprezentant bazandu-ne pe toate sensurile cuvintelor din topice sau doar pe cele asociate nodurilor din subarbore care au acoperire minim 2.

Rezultate experimentale

În oricare dintre cele trei metode prezentate, rezultatele au fost evaluate folosind variaţia acoperirii şi redundanţei modelului rezultat faţă de cel iniţial. În toate testele atât acoperirea cât şi redundanţa au variat în acelaşi sens, dar cu viteze diferite, ceeea ce a condus la o diferenţă care este exact valoarea căutată. Dacă redundanţa scade cu o viteză semnificativ mai mare decât acoperirea modelul final poate fi considerat superior.

Corpusul folosit cuprinde 21106 articole publicate între 2007 şi 2010 în secţiunea Finance a cotidianului The Daily Telegraph, iar vocabularul cuprinde 44484 cuvinte distincte. Suita Mallet (http://mallet.cs.umass.edu), dezvoltată de Universitatea Massachusetts a fost folosită pentru determinarea topicelor cu algoritmul LDA cu 100 topice, din fiecare reţinând cele mai importante 50 cuvinte cheie.

Tabelele 1, 2 şi 3 prezintă câştigurile de performanţă obţinute în cele trei experimente, iar cazul în care este obţinut câştigul maximal este prezentat cu font mărit şi îngroşat.

În primul experiment fiecare topic este tratat separat de celelalte iar cuvintele sale cele mai puţin înrudite cu celelalte eliminate. Pentru a distinge între nodurile subarborelui asociat care au o funcţie de evaluare suficient de mare şi cele care trebuie eliminate am folosit un prag variabil, ca în tabelul 1, prezentat mai jos. Cu preţul pierderii a 35% din acoperirea modelului, redundanţa acestuia scade cu peste 60%.

Concluzii

În această lucrare am prezentat o metodă de evaluare a calităţilor unui model de topice complementar celor deja existente. Folosind această metrică am propus trei modalităţi de a îmbunătăţi trăsăturile modelelor analizate. Rezultatele obţinutecu ameliorarea de peste o treime a trasăturilor iniţiale ne îndreptăţesc să sperăm că aceste metode vor putea fi folosite ca postprocesare pentru algoritmii de extragere de topice în viitor. Important este faptul că ameliorarea se poate face la nivel de topic individual, fapt care poate permite o mai bună etichetare a topicului în cauză, ceea ce lărgeşte semnificativ aria de aplicabilitate a modelului în sine.

Mulţumiri

Adresăm mulţumiri prof. Julien Velcin, Université Lumière Lyon2, pentru ajutorul şi implicarea sa în realizarea acestei metode.

  Metoda de mai sus poate fi îmbunătăţită prin includerea în formula similarităţii între topice numai a nodurilor care nu sunt direct asociate unor cuvinte din topice. Limităm astfel riscul ca, dacă două topice conţin aceleaşi cuvinte, dar care au alte sensuri, să fie considerate pe nedrept redundante. Luăm astfel în considerare numai acele noduri care au o acoperire egală sau mai mare ca doi. Astfel fiecare cuvânt din topic va fi reprezentat numai de sensurile sale cele mai probabile. Rezultele sunt prezentate în tabelul 3 unde se observă o creştere a caştigului de peste 2.5% faţă de metoda precedentă. Câştigul obţinut prin eliminarea topicelor redundante bazat doar pe noduri semnificative

	O metodă pentru evaluarea şi îmbunătăţirea performanţelor sistemelor de	13
						extragere a topicelor
		0.6	1066	1508		30.37	53.43	23.06
		0.7	993	1244		35.14	61.58	26.44
		0.8	916	1086		40.17	66.46	26.29
		0.9	847	981		44.68 Variaţia	69.70 Variaţia	25.03
			1	814 Topice	917		46.83 acoperirii	71.68 redundanţei	24.85 Câştig
	µ			Tabel 1 -Câştigul obţinut prin eliminarea cuvintelor neînrudite sterse Acoperire Redundanţă (%) (%)	(%)
			2			1531		3238		0	0	0
	Un al doilea test conţine câştigul obţinut prin ştergerea topicelor redundante 1.9 0 1531 3238 0 0 0 din model.Un topic este considerat redundant dat fiind alt topic procesat anterior dacă similaritatea lor depăşeşte cu un factor µ similaritatea medie a 1.8 0 1531 3238 0 0 0
	modelului. Rezultatele sunt semnificativ mai bune decât în primul 1.7 0 1531 3238 0 0 0
	experiment, o scădere de aproape 60% a redundanţei fiind atinsă cu o 1.6 0 1531 3238 0 0 0
	pierdere de numai 26% a acoperirii. 1.5 2 1523	3151		0.52	2.69	2.16
		1.4		11	1458		2778		4.77	14.21	9.44
									Variaţia	Variaţia
		1.3	Topice	22	1372		2334	acoperirii 10.39	redundanţei 27.92	Câştig 17.53
	µ	1.2	sterse	50	Acoperire Redundanţă 1111 1250	(%) 27.43	(%)	61.40	(%) 33.96
		2 1.1		79	1531 614		3238 371		0.00 59.90	0.00 88.54	0.00 28.65
			1.9 1		0 92	1531 287		3238 93		0.00 81.25	0.00 97.13	0.00 15.87
	Tabel 3 -	1.8		5	1497		3033		2.22	6.33	4.11
			1.7		11	1453		2786		5.09	13.96	8.86
			1.6		23	1363		2300		10.97	28.97	18.00
			1.5		36	1252		1797		18.22	44.50	26.28
		1.4		48	1119		1356	26.91	58.12	31.21
			1.3		72	760	Variaţia 573		Variaţia 50.36	82.30	31.94
			1.2		87	421	acoperirii 195		redundanţei 72.50	Câştig 93.98	21.48
		Prag	1.1	Acoperire Redundanţă 94 225	(%)	62		(%) 85.30	98.09	(%)	12.78
			0 1	1531 98	3238 39		10	0.00	97.45	0.00 99.69	0.00 2.24
		0.1	1496 Tabel 2 -Câştigul obţinut prin eliminarea topicelor redundante 3127 2.29 3.43	1.14
		0.2	1473	3018			3.79	6.79	3.01
		0.3	1410	2785			7.90	13.99	6.09
		0.4	1311	2403		14.37	25.79	11.42
		0.5	1179	1921		22.99	40.67	17.68

  Rezultatele prezentate în acest articol au fost obţinute cu sprijinul Ministerului Muncii, Familiei şi Protecţiei Sociale prin Programul Operaţional Sectorial Dezvoltarea Resurselor Umane 2007-2013, Contract nr. POSDRU/6/1.5/S/19.

Claudiu Muşat, Marian-Andrei Rizoiu, Ştefan Trauşan-Matu