Mihai Dascălu
email: mihai.dascalu@cs.pub.ro

Philippe Dessus
email: philippe.dessus@upmf-grenoble.fr

Evaluarea şi sumarizarea automată a conversaţiilor chat

REZUMAT

Odată cu evoluţia continuă a mediilor colaborative, nevoia unei analize automate în vederea evaluării participanţilor la discuții de tip Instant Messenger (chat) a devenit din ce în ce mai acută. De asemenea, o facilitate necesară la nivelul unui sistem de notare și evaluare a replicilor și, implicit, a participanților este sumarizarea. În vederea atingerii acestor obiective, o serie de factori bazați pe procesarea limbajului natural (inclusiv analiza semantică prin intermediul Latent Semantic Analysis -LSA) şi datamining au fost luați în considerare. De asemenea, în vederea obținerii unei evaluări minuțioase și multiperspectiste a participanţilor, au fost calculați factori derivați din metodele lui Page de notare a eseurilor, diverse abordări pentru estimarea lizibilității şi metrici specifice analizei rețelelor sociale. Un standard de aur a fost utilizat pentru măsurarea corectitudinii rezultatelor obținute.

Cuvinte cheie

sumarizarea extractivă a chat-urilor, evaluarea participanților din mediul colaborativ, rețele sociale, LSA etichetat.

Clasificare ACM

H5.2. Information interfaces and presentation: Training, help, and documentation and Natural language.

INTRODUCERE

Ca urmare a evoluţiei web-ului au apărut noi instrumente de colaborare şi concomitent cu acestea s-a multiplicat dorinţa de procesare automată a unui volum cât mai mare de informaţii. În cadrul Învățământului Colaborativ Sprijinit de Calculator (Computer Supported Collaborative Learning -CSCL) [START_REF] Stahl | Group Cognition: Computer Support for Building Collaborative Knowledge[END_REF], chat-urile joacă un rol important şi au devenit din ce în ce mai utilizate. Pe de altă parte, evaluarea manuală a unui chat este un proces consumator de timp pentru profesor, necesitând pentru analiză un timp mai mare decât durata efectivă a discuției. Astfel, necesitatea de a dezvolta aplicaţii care pot ajuta procesul de evaluare a devenit esenţială. Din această perspectivă au fost vizate două direcții majore:  Un sistem automat pentru evaluarea fiecărui participant la o sesiune de chat prin utilizarea unor metode specifice prelucrării limbajului natural, analiza de suprafață și analiza rețelelor sociale;  Un sistem automat de sumarizare extractivă bazat pe rezultatele sistemului de mai sus, care poate fi utilizat pentru a reduce considerabil timpul petrecut de tutor în cazul unei evaluări manuale. Utilitatea sumarizării se răsfrânge în posibilitatea de a evalua manual un număr mult mai mare de chat-uri în aceeași unitate de timp. De asemenea, sumarizarea este utilă și unui participant care intră mai târziu în chat sau pentru a revedea ce s-a discutat.

Scenariul utilizat pentru sesiunile de chat a fost următorul: studenţii din cadrul cursurilor de Interacțiune Om-Calculator (IOC) din doi ani diferiți și de la Prelucrarea Limbajului Natural, de la facultatea de Automatică și Calculatoare au fost invitaţi să discute beneficiile instrumentelor colaborative on-line (de exemplu, la IOC wiki-uri, blog-uri, chat-uri şi forumuri), dezbătând și argumentând beneficiile și dezavantajele fiecărei tehnologii. Fiecare student era responsabil de o tehnologie și își susținea punctul de vedere relativ la beneficiile acesteia, încercând totodată să contracareze "ofertele" celorlalți participanți. În ultima parte a discuției erau analizate posibilitățile de integrare și inter-comunicare a diferitelor tehnologii. Toate interacţiunile sunt exclusiv între studenţi, fără intervenţia efectivă a unui profesor, iar limba utilizată în cadrul discuțiilor a fost engleza. Mediul utilizat a fost VMT [START_REF]Studying Virtual Math Teams pag[END_REF], iar în medie fiecare chat a avut 4 participanţi. Corpusul obţinut conţinea aproximativ 80 de chat-uri, care au fost ulterior evaluate manual de un student de la un an diferit. Astfel s-a încercat diminuarea subiectivismului în evaluare. Domeniul discuțiilor a fost IT-ul, centrat pe tehnologii web colaborative, iar participanţii au avut cunoştinţe similare, atât de bază cât și în domeniul tehnologiilor discutate, şi aceleaşi roluri în cadrul discuţiei din perspectiva responsabilităților. Această analiză poate fi extrapolată la orice tip de discuţii centrate pe un domeniu specific, cu o reprezentare corespunzătoare a cunoştinţelor (condiționat, de un proces anterior de învăţare supervizată folosind Latent Semantic Analysis (LSA)). De asemenea, se pot realiza experimente pe baza următoarelor scenarii: prezenţa efectivă a unui tutore/profesor și influența acestuia, sau interacţiunile între participanți la acelaşi nivel, precum este cazul celor prezentate anterior.

Următoarea secţiune a acestui document va prezenta factorii utilizați în cadrul procesului de evaluare: de la cei mai simpli precum lizibilitatea sau metricile derivate din metodele lui Page de analiză a eseurilor [START_REF] Page | Analysis of essays by computer[END_REF], trecând la analiza reţelelor sociale şi, în final va fi utilizat Latent Semantic Analysis LSA [12], pentru o abordare semantică a procesului de notare. A treia secţiune evaluează sistemul, iar ultima secţiune, înainte de concluzii, va fi dedicată prezentării sistemului de sumarizare.

PROCESUL DE EVALUARE

Noutatea abordării constă în primul rând în procesul de evaluare atât al replicilor, cât și al participanților la nivelul căruia sunt integrate perspective multiple pentru o privire cât mai holistică. Astfel, evaluarea se realizează pe 3 nivele după cum urmează:  Analiza de suprafață structurată pe două direcții: pe de-o parte evidențierea lizibilității replicilor, iar pe de alta o serie de metrici derivate din studiile inițiale ale lui Page pentru analiza eseurilor precum fluență, corectitudine gramaticală, dicție sau structura replicilor [START_REF] Page | Analysis of essays by computer[END_REF];  Analiza morfologică (Spellchecking, Stemming, Tokenizing) și etichetarea actelor de vorbire (Part of Speech Tagging);  Analiză semantică având în spate modelul Latent Semantic Analysis (LSA) pentru evaluarea similarității dintre o replică și întreaga conversație, respectiv cu un set predefinit de cuvinte specificate de profesor drept subiecte impuse de discuție.

Adițional, analiza specifică rețelelor sociale este aplicată atât asupra grafului rezultat din numărul de mesaje interschimbate între participanți, cât și asupra grafului cu costul arcelor egal cu suma notelor replicilor aferente.

Analiza de suprafață

Analiza de suprafață se focalizează pe două categorii de factori: lizibilitate și factori obținuți prin adaptarea studiilor lui Page aplicate inițial exclusiv pentru analiza eseurilor. Ideea în sine era simplă -evaluarea automată a unui document cu performanțe similare cu ale unui evaluator uman având la bază exclusiv atribute simple statistice [START_REF] Wresch | The Imminence of Grading Essays by Computer--25 Years Later[END_REF]. Scopul sistemului presupunea facilitarea evaluării, permițând astfel asignarea mai multor teme și îmbunătățirea capabilităților studentului prin exercițiu, similare cu cele ale sistemului de față. Ideea de evaluare a avut la bază relația dintre proxes (aproximări ale interesului documentului la nivel de factori ușor de calculat automat -practic componenta computațională) și trins (variabile intrinseci utilizate de către evaluatorii umani). Concluziile studiului inițial au fost promițătoare: corelație de 71% similară cu corelația medie dintre doi evaluatori umani, demonstrând astfel viabilitatea metodei.

Pornind de la acest studiu inițial și integrând abordarea lui Slotnick [START_REF] Wresch | The Imminence of Grading Essays by Computer--25 Years Later[END_REF] pentru gruparea factorilor identificați anterior în funcție de valorile intrinseci, următorii factori au fost obținuți, fiecare cu o pondere egală la nivelul notei categoriei din care fac parte. Nota finală reprezintă media aritmetică a notele fiecărei categorii. Astfel factorii utilizați în special din perspectiva unei analize cantitative, ulterior convertiți în procente prin scalarea raportat la valoarea maximă, sunt cei din Tabelul 1 și sunt figurați conform Figurii 1 la nivelul aplicației dezvoltate.

A doua categorie de factori reprezentativi la nivelul de suprafață reflectă lizibilitatea textului înțeleasă drept ușurința cu care pot fi parcurse replicile unui participant, oferind o imagine concludentă asupra stilului propriu de scriere. Aceasta are un impact major asupra înțelegerii, retenției, vitezei de citire, precum și asupra persistenței textului citit.

Analiza rețelelor sociale

În scopul obținerii unei perspective cât mai profunde, factorii sociali sunt luați în considerare pentru reliefarea interacțiunii dintre participanți. Astfel, un graf este generat pe baza transcriptului chat-ului analizat: nodurile reprezintă participanții, iar arcele sunt generate pe baza legăturilor explicite prin posibilitățile de referențiere directă între replici din mediul chat.

Din punctul de vedere al rețelelor sociale, diverse metrici sunt calculate pentru a determina cel mai implicat participant la nivelul discuției: gradul (indegree și outdegree), centralitate (closeness, graph centrality, eigen centrality) și ranking-ul utilizatorilor, similar cu binecunoscutul algoritm Google Page Rank. Aceste metrici sunt aplicate asupra unor matrice la nivelul cărora arcele reprezintă:  Numărul efectiv de replici interschimbate între participanți, cu accent preponderent pe o abordarea cantitativă;  Suma notelor fiecărei replici bazate pe evaluarea semantică a fiecărei replici; procesul de evaluare propriu-zisă a unei replici va fi descris într-o secțiune ulterioară, iar această abordare fundamentează evaluarea calitativă a chat-ului.

Astfel, din aplicarea metodelor specifice de analiză a rețelelor sociale, atât asupra numărului de replici, cât și asupra sumei notelor aferente, se accentuează dualitatea abordării din următoarele perspective:  Evaluare cantitativă vs. Evaluare calitativă cu substrat semantic;  Implicarea în discuție (gregariousness) vs.

cunoștințele prezentate/dobândite și aportul cognitiv, evaluate semantic folosind LSA.

Toate metricile folosite în cadrul analizei rețelelor sociale reprezintă valori relative în sensul în care pot oferi scoruri relevante numai în comparație cu implicarea celorlalți participanți ai aceluiași chat. Acesta este principalul motiv pentru care toți factorii sunt scalați între participanți, oferind fiecăruia un procent ponderat raportat la performanța globală.

Un rol important în analiza rețelelor sociale îl are componenta de vizualizare, care permite modelarea atât prin intermediul unui model fizic, cât și prin intermediul unui model radial al interacțiunii dintre participanți [START_REF] Dascalu | A Program for Chat Modeling and Assessment[END_REF]. Procesul de învățare supervizată folosește corpusul de chat-uri. Primul pas în procesul de învăţare, după verificarea ortografiei, este de a elimina cuvintele cu aport semantic redus -stop-words (foarte frecvente şi lipsite ca importanță globală "the", "a", "an", "to", etc.) din fiecare replică. Următorul pas este etichetarea actelor de vorbire -Part of Speech Tagging -iar, în cazul verbelor, acestea sunt reduse la rădăcină prin stemming pentru limitarea formelor identificate, toate exprimând același concept. Toate celelalte cuvinte sunt lăsate în formele lor identificate, singura îmbunătățire existând prin adăugarea de etichete corespunzătoare actelor de vorbire. Se consideră că două cuvinte, identice ca rădăcină și formă, dar cu acte de vorbe diferite se regăsesc în contexte diferite, prin urmare învecinându-se cu alte noduri din perspectivă semantică [START_REF] Wiemer-Hastings | Rules for syntax, vectors for semantics[END_REF].

După popularea matricei termen-document se aplică term frequency -inverse document frequency -TF-IDF (dependență directă relativ la frecvenţa termenilor și inversă raportat la numărul de documente [START_REF] Manning | Foundations of statistical Natural Language Processing[END_REF]). Etapele finale ale procesului de antrenare sunt descompunerea în valori singulare (SVD) şi proiecţia matricelor obținute cu scopul de a reduce dimensiunile acestora. În conformitate cu [START_REF] Lemaire | Limites de la lemmatisation pour l'extraction de significations[END_REF], valoarea optimă empirică pentru k este 300, o valoare utilizată frecvent în experimente curente și asupra căreia mai multe surse sunt de acord.

Un alt aspect important în procesul de învăţare LSA este segmentarea care presupune împărțirea unui chat luând în considerare unităţi semnificative. În implementarea actuală chat-ul este împărţit între participanţi, din cauza unităţii şi coeziunii între replicile aceleiaşi persoane. Aceste documente sunt ulterior împărţite în segmente folosind ferestre disjuncte, fixe ca dimensiune.

Scopul final al utilizării LSA este de a evalua proximitatea/similaritatea dintre doi termeni sau cuvinte utilizând drept măsură cosinusul dintre vectorii aferenți:

        k i i k i i k i i i cuv cuv cuv cuv cuv cuv Sim 1 2 , 2 1 2 , 1 1 , 2 , 1 2 1 , ) , (
Similaritatea dintre replici şi similaritatea dintre replici și întregul document sunt utilizate pentru a evalua importanţa fiecărei replici în parte, comparativ cu întreaga discuție sau cu un set predefinit de cuvinte cheie menţionate ca un nou document:

    1 ) ( * )) ( _ log( 1 ( ) ( i i i cuv vector cuv aparitii nr repl Vector          ) ( ), ( ) , (

Mecanismul de notare al replicilor, respectiv al participanților

Primul aspect care trebuie luat în considerare îl reprezintă construirea grafului bazat pe legături explicite pentru marcarea relațiilor existente. Procesul de evaluare al fiecărei replici se bazează pe textul prelucrat și obținut în urma analizei morfologice şi a POS Tagging-ului și presupune următoarele etape:

1. Evaluarea fiecărei replici individual, luând în considerare următoarele caracteristici:  lungimea efectivă a replicii iniţiale;  lista de cuvinte rămase după eliminarea cuvinte de tip stop-words, verificate în prealabil ortografic; de asemenea se memorează şi numărul lor de apariții;  nivelul pe care se află replica actuală într-un fir al discuției;  factorul de ramificare egal cu numărul de replici care au legături explicite către replica curentă;  similaritatea cu întreaga discuție pentru a evidenția importanța replicii raportat la întreaga conversație;  similaritatea cu un set predefinit de subiecte de discuţie asignate de profesor pentru a verifica acoperirea temei date pentru discuție.

Aspectul surprins în cadrul abordării este exact dualitatea perspectivei: pe de-o parte avem abordarea cantitativă (lungimea replicii exprimată în caractere scrise, pornind de la premisa că informaţia ar trebui să fie mai valoroasă dacă este transmisă în mai multe mesaje, legate împreună, și o lungime mai mare nu este datorată dorinței de a impresiona, ci pentru îmbogățirea contextului), iar de cealaltă parte abordarea calitativă care presupune utilizarea LSA şi a cuvintelor cheie predefinite.

Formule utilizate pentru evaluarea fiecărei replici sunt:

                  )) _ log( 1 ( * ) ( ) ( aparitii nr radacina lungime cuv scor   ) _ _ , ( ) , ( ) _ log( 1 ( )) log( 1
       

Augmentarea scorului

Fiecare fir de discuție are un maxim global relativ la scorurile calculate anterior în jurul căruia toate replicile au importanța augmentată corespunzător cu o distribuţie Gaussiană:

2 2 2 ) ( 2 1 ) (        x e x p , unde: 2 ) _ _ min( ) _ _ max( fir repl id fir repl id    , im scor cu replica id max _ _ _ _  
Astfel scorul fiecărei replici este amplificat cu un factor de 1 + p(replica_curenta).

Determinarea scorului final de-a lungul firului de discuție

Pe baza scorului empiric, scorul final este obţinut după următoarea formulă:

empiric final final scor coef precedenta repl scor scor    ) _ ( ,
unde coeficientul este determinat de tipul actelor de vorbire din replica curentă și din cea de care aceasta este legată printr-o legătură explicită; astfel, sunt inspectate verbele, semnele de punctuaţie şi anumite cuvinte cheie. Pornind de la un set de tipuri de acte de vorbire, coeficienţii sunt obţinuți dintr-o matrice predefinită; valorile au fost determinate după estimarea impactului replicii curente luând în considerare numai nivelul anterior de replici din cadrul aceluiași fir de discuție (similar unui proces Markov). Scorul final al replicilor din cadrul unui fir de discuţie poate fi ridicat sau coborât de fiecare replică. Prin urmare, în funcţie de tipul replicii şi al actelor de vorbire identificate, nota finală poate avea o valoare atât pozitivă cât și negativă.

Notarea participanților combină metricile de la nivelul analizei de suprafață cu factorii specifici analizei rețelelor sociale aplicați asupra celor 2 matrice definite anterior. Fiecare dintre factorii de analiza este convertit la un procent (valoare curentă / suma tuturor valorilor, pentru fiecare factor, cu excepţia cazului de eigen-centrality când conversia se face automat prin înmulţirea cu 100 a valorii proprii în modul). Scorul final al participanților ia în considerare toţi aceşti factori şi ponderile corespunzătoare: Corelaţia Pearson pentru fiecare factor este determinată în raport cu notele oferite de evaluatori umani, permițând astfel evaluarea importanţei şi a relevanţei fiecăruia relativ la notele date de un evaluator uman luate drept standard de referinţă.

   k i k k i

EVALUAREA SISTEMULUI

Ponderile asociate static fiecărui factor sunt următoarele: 10% pentru metricile derivate din metoda lui Page de evaluare a eseurilor și lizibilitate, 5% pentru factorii de analiză a reţelelor sociale aplicați pe numărul de replici interschimbate şi 10% pentru factorii semantici din analiza reţelei sociale construită pe baza scorurilor fiecărei replici.

Rezultatele globale obţinute cu aceste ponderi pentru corpusul analizat sunt:  corectitudinea relativă: 77.44%  corectitudine absolută: 70.07%  corelația Pearson: 51,4% Corectitudinea relativă şi corectitudinea absolută reprezintă distanțe absolute/relative dintre valorile obținute automat și cele din urma evaluării umane. Rezultatele finale (ca media aritmetică pentru fiecare din cei 3 factori determinați individual per chat) sunt afişate la nivelul interfeței grafice proiectate:

SUMARIZARE EXTRACTIVĂ

Cel mai important aspect relativ la generarea extractivă a unui rezumat este legătura strânsă dintre sumarizare şi evaluarea propriu-zisă a chat-ul. Prin urmare, pentru a obţine un rezumat extractiv cât mai corect, fiecare replică trebuie evaluată -în cazul nostru, procesul de notare a fost descris anterior şi oferă baza pentru identificarea replicilor cheie. Aceasta abordare combină metoda de sumarizare automată bazată pe LSA [START_REF] Fernandez | Les systèmes de résumé automatique sont-ils vraiment des mauvais élèves?[END_REF], cu beneficiile de a introduce toţi ceilalţi factori prezentați în secțiunile precedente, cu impact mare în procesul de evaluare.

Pentru a răspunde cât mai bine cerințelor utilizatorului, un set de procente predefinite (procente incrementale cu 10%) a fost prevăzut, permiţând utilizatorului să selecteze nivelul de interes și de filtrare al replicilor. Astfel se poate determina numărul de replici care urmează să fie selectate și care vor face parte din rezumatul oferit de către sistem. Ulterior, replicile sunt extrase în ordinea descrescătoare a importanţei / scorului. Pentru a augmenta rolul replicilor direct legate de replica curentă (implicit corelate și din perspectiva discursului) se acordă o bonificație tuturor replicilor de pe următorul nivel din cadrul arborelui de replici definit pe baza legăturilor explicite. Astfel se asigură posibilitatea selectării comentariilor și impresiilor referitoare la o anumită replică, chiar dacă scorul inițial al acestora este relativ mic. Într-o sumarizare a chat-urilor este esențială integrarea acestor replici datorită aportului cognitiv și importanței globale relativ la impresiile împărtășite.

Scopul final al sistemului este de a reduce drastic timpul petrecut de un evaluator uman pentru a nota un chat, prin urmare, să permită relocarea timpului înspre sarcini mai creative, fără a elimina componenta umană în evaluare.

Impactul real în urma utilizării sistemului automat de rezumare este reducerea cu mai mult de 30% a timpului petrecut pentru evaluarea unui singur chat. Acest lucru permite analiza mai multor chat-uri, prin urmare oferind un corpus adnotat mai mare, util în procesul de învăţare automată. Astfel, rezultatele pot fi îmbunătăţite prin ajustarea fină a ponderilor pentru fiecare dintre factorii luaţi în considerare în procesul de notare.

Acest rezumat este, de asemenea, foarte util din perspectiva studentului, făcând posibilă o scurtă descriere a fiecărei discuţii, evidențierea enunţurilor cu un interes mai mare şi bogate în informaţii.

CONCLUZII

Rezultatele obţinute ne permit să concluzionăm că evaluarea contribuţiei participanților într-un mediu colaborativ poate fi realizată automat, iar impactul la nivelul tutorelui se reflectă într-o scădere cu peste 30% a timpului petrecut pentru evaluarea unui chat. De asemenea, împreună cu o ajustare mai bună a parametrilor și a ponderilor aferente fiecărui factor, împreună cu un proces îmbunătățit de învățare supervizată utilizând LSA, precum și prin creșterea numărului de factori specifici analizei reţelelor sociale (inclusiv cei aplicați la nivelul întregii reţele) credem că performanţa şi fiabilitatea rezultatelor obţinute va crește. Mai mult, factorul subiectiv în evaluarea manuală este întotdeauna prezent şi influenţează corectitudinea per ansamblu a sistemului.

Pornind de la direcțiile descrise anterior, următoarele îmbunătăţiri vor fi luate în considerare pentru îmbunătățirea rezultatelor:  experimente sociale cu evaluarea impactului aferent; realizarea de scenarii diferite (cu sau fără prezenţa efectivă a unui profesor) corelate cu impactul efectiv al prezenței acestuia;  identificarea de artefacte, voci şi perspective multiple ale aceluiași concept folosind LSA, în concordanță cu filosofia lui Bakhtin [START_REF] Bakhtin | Problems of Dostoevsky's poetics[END_REF] pentru o înţelegere mai profundă a discuției din punct de vedere dialogistic;  includerea de texte comune (de exemplu, articole de ziar), pentru o perspectivă de ansamblu asupra tuturor cuvintelor întâlnite dintr-un text (nu numai asupra celor specifice unui anumit domeniu) și pentru a îmbunătăţi procesul de învăţare LSA;  integrarea tuturor chat-urilor și generarea unei reţele sociale globale, rezultând astfel posibilitatea unei evaluări de ansamblu asupra întregului corpus şi posibilitatea de a căuta un participant pe baza competenţelor sale evaluate raportat la un subiect predefinit.

MULŢUMIRI

Ne dorim să mulţumim tuturor studenţilor din cadrul Facultății de Automatică și Calculatoare, Universitatea "Politehnica" din Bucureşti, care au participat la experimentele noastre şi care au format baza pentru corpusul utilizat pentru evaluarea sistemului. Activitățile de cercetare prezentate în această lucrare au fost parţial efectuate în cadrul proiectului PC7 LTfLL (Language Technologies for Lifelong Learning).

FKRA

  = Flesch-Kincaid Reading Age Notarea participanților din cadrul unui chat se face în funcție de abaterea față de valorile considerate optime, iar vizualizarea se realizează conform următoarei figuri.

Figura

  Figura 2. Lizibilitatea

Figura 3 .

 3 Figura 3. Modelarea rețelelor sociale Analiza semantică -LSA Analiza Semantică Latentă este o tehnică ce se bazează pe un model al spațiului de vectori care este folosit in analiza similarității dintre un set de documente și termenii conținuți. LSA pornește de la o matrice termen-document bi-dimensională care descrie numărul de apariții ale fiecărui termen în documentul corespunzător. LSA transformă matricea inițială într-o relație dintre termeni și concepte, respectiv o relație între aceste concepte şi

  un factor al participantului cu rangul i.

Figura 4 .

 4 Figura 4. Rezultatele obținute

Figura 5 .

 5 Figura 5. Sumarizare automată

  (

	augmentare	nivel		factor	ram
	Sim	replica	e conversati
	Sim	replica	set	subiecte	discutie