Recunoasterea Actelor de Vorbire Dintr Un Dialog

Recunoasterea actelor de vorbire dintr-un dialog

Capitolul 1. Introducere

Limbajul natural este un fenomen extrem de complicat. El se dezvolta incet si treptat de-a lungul unei perioade indelungate de timp, aparent pentru a optimiza comunicarea dintre oameni.

In limbajul natural, apare o mare incidenta a variatiei si incertitudinii. Cea mai mare sursa a variatiei este data de continutul mesajelor. In plus, fiecare mediu de transmisie a limbajului natural este supus la zgomote, distorsiuni si pierderi.

Datorita acestor incertitudini se naste nevoia unui model lingvistic. Cea mai importanta utilizarea a modelelor lingvistice este aplicarea in recunoasterea automata a actelor de vorbire, unde un computer este folosit pentru a pune textul intr-o forma acceptabila. Limbajul natural poate fi vazut ca un proces stohastic. Fiecare cuvant, enunt, document sau alt nivel al vorbirii este tratat ca fiind o variabila aleatoare cu o anumita probabilitate de distributie. Daca W=w1w2…wn reprezinta o secventa de n cuvinte, scopul modelului lingvistic este de a calcula probabilitatea P(W).

O metoda de a calcula aceasta probabilitate este de a considera o regula de tip lant, in care cuvintele de la un anumit moment depind de cele dinaintea lui.

In lucrarea de fata se inceaca o abordare de acest gen. Se doreste sa se ajunga la recunoasterea actelor de vorbire din texte de tip chat care au un anumit format, recunoastere bazata pe identificarea unor modele lingvistice ale textelor si pe gasirea unor cuvinte-cheie specifice fiecarui act de vorbire in parte.

Initial se incearca obtinerea unui model lingvistic prin aplicarea unor tehnici de invatare asupra unor texte adnotate manual si prin folosirea unui model Markov ascuns, iar dupa aceea se incearca recunoasterea actelor de vorbire din texte neadnotate pe baza modelului obtinut in pasul anterior si a identificarii unor cuvinte-cheie specifice pentru fiecare act de vorbire in parte.

Capitolul 2. Notiuni referitoare la dialog

Intelegerea limbajului natural din transcrierea dialogurilor ridica probleme specifice fata de textele obisnuite, deoarece dialogul are cateva caracteristici care ingreuneaza acest lucru.

Una din principalele caracteristici ale dialogului este structura sa bazata pe replici (turn-taking), fiecarui participant venindu-i randul la un moment dat sa spuna ceva.

Problema este cum isi dau seama participantii cand este randul lor sa vorbeasca. Pentru aceasta, exista o regula care sa modeleze aportul participantilor la un dialog:

daca in timpul replicii curente, cel ce vorbeste specifica faptul ca un anumit participant la dialog trebuie sa vorbeasca in continuare, atunci acela este cel ce va urma;

daca vorbitorul curent nu specifica nici o persoana ca fiind urmatorul vorbitor, atunci oricine poate sa continue;

daca nimeni nu preia rolul de vorbitor in momentul in care vorbitorul curent a terminat ceea ce avea de spus, atunci vorbitorul curent poate sa continue.

Prima parte a regulii are o importanta deosebita, deoarece subliniaza faptul ca exista anumite tipuri de replici prin care un vorbitor poate sa selecteze cine va fi urmatorul vorbitor. Cele mai frecvente replici de genul acesta sunt intrebarile la care vorbitorul selecteaza o anumita persoana sa ii raspunda. Astfel de constructii se numesc perechi de adiacenta.

Aceasta regula scoate in evidenta si un alt aspect al dialogurilor: linistea dintre doua replici consecutive. In general, timpul de latenta dintre doua replici consecutive este foarte mic si de aceea, in momentul in care se intalnesc momente de tacere mai indelungate, pot exista anumite cauze care le genereaza. In cazul perechilor de adiacenta, daca intervine o pauza intre cele doua replici componente ale acesteia, se poate trage concluzia ca a existat un anume disconfort in a raspunde la prima replica. In afara acestor perechi de adiacenta, incidenta momentelor de liniste este mai putin semnificativa.

O alta caracteristica foarte importanta a dialogurilor este aceea ca ele sunt destinate vorbirii, ceea ce duce la o serie de diferente fata de textele scrise. Aceste diferente se refera la structura replicilor: acestea tind sa fie mai scurte, de tip propozitie simpla (si nu fraza ca in textele scrise), iar subiectele replicilor sunt de cele mai multe ori pronume si nu substantive. Acest lucru duce la o crestere a greutatii de segmentare a dialogurilor, deoarece pot exista cazuri in care o replica se poate intinde pe mai multe ture, precum si cazuri in care o tura cuprinde mai multe replici. Pentru a putea segmenta un dialog, se aplica algoritmi bazati pe identificarea limitelor dintre replici, cautandu-se diferite indicii in acest sens: cuvinte-cheie (cuvinte ce tind sa apara la inceputul sau sfarsitul unei replici); modele de cuvinte N-gram (care pot fi antrenate pe un set de replici adnotate in care se specifica limitele fiecareia dintre ele, iar apoi, prin aplicarea unui decodificator, sa se gaseasca succesiunea de limite cea mai probabila pe un text neadnotat); prozodie (diferenta de intonatie, accentul, duratele unor fraze).

O alta caracteristica importanta a dialogurilor este ca intre participanti se stabileste un scop comun. Adica, cei care participa la dialog, trebuie intr-un fel sau altul sa aprobe sau sa motiveze ceea ce spune vorbitorul. Daca aceste replici aprobatoare nu apar, inseamna ca s-a intamplat ceva in intelegerea a ceea ce vorbitorul a spus.

Ultima carcateristica importanta a dialogurilor consta in modul de interpretare a replicilor. Interpretarea nu se face doar in sensul propriu al cuvintelor. Acest lucru a fost semnalat de Grice in lucrarea sa referitoare la implicaturile conversationale. El a subliniat faptul ca ascultatorii sunt indemnati sa inteleaga replica in alte sensuri decat cel propriu, daca nu sunt respectate anumite maxime:

Maxima cantitativa – fii exact atat de informativ pe cat este necesar;

Contributia ta trebuie sa fie atat de informativa pe cat este necesar;

Nu spune mai mult decat este necesar;

Maxima calitativa – incearca sa aduci o contributie adevarata;

Maxima relevantei – fii relevant;

Nu spune lucruri pe care nu le crezi adevarate;

Nu spune lucruri pe care nu poti sa le demonstrezi;

Maxima ce tine de maniera – fii perspicace;

Evita obscuritatea expresiilor;

Evita ambiguitatea;

Fii concis;

Fii ordonat;

Capitolul 3. Acte de vorbire

3.1 Adnotarea actelor de vorbire

Teoria actelor de vorbire a fost introduse de Austin. El a intuit ca o replica a unui dialog este un fel de actiune executata de catre vorbitor. Tot el a observat ca unele verbe descriu o stare de fapt, iar Austin le-a numit acte constatative, in timp ce altele au ca efect schimbarea unei stari de fapt sau efectuarea unor actiuni. El le-a numit pe acestea din urma acte performative, iar actiunile ce sunt descrise de astfel de verbe, acte de vorbire. Termenul de acte de vorbire este in general utilizat pentru a descrie acte ilocutionale.

Plecand de la ideile lui Austin, Searle a dezvoltat teoria actelor de vorbire, specificand ca acestea pot fi impartite intr-una din urmatoarele clase:

ilustrative, care reprezinta o stare de fapt: asertiuni, descrieri;

comisive, care implica vorbitorul intr-un curs viitor de actiuni: promisiuni, amenintari;

directive, ce atrag atentia asupra efectuarii unei actiuni: comenzi, cereri;

declaratii, care aduc o anumita stare de lucruri: denumire, arestare, casatorie, binecuvantare;

expresive, care indica starea psihologica sau atitudinea mentala a vorbitorului: felicitari, multumiri, scuze;

verdicative, care dau o apreciere: judecata, iertare.

O incercare recenta de a dezvolta schemele de adnotare a actelor de vorbire este arhitectura DAMSL (Dialog Act Markup in Several Layers) care codifica pe diferite nivele informatiile referitoare la replicile unui dialog. Doua dintre aceste nivele, functia de anticipare (FLF, in engleza, “forward looking function”) si functia de adaptare regresiva (BLF, in engleza, “backward looking function”) sunt extensii ale actelor de vorbire ce extrag notiuni legate de structura dialogului cum ar fi perechile de adiacenta sau notiunile de grupare.

Functia de anticipare a unei notiuni corespunzand unor acte de vorbire de genul Searle/Austin e bazata pe tipul actelor ce pot aparea intr-un dialog:

Afirmatii o afirmatie facuta de cel ce vorbeste

Cerere de informatie intrebare pusa de cel ce vorbeste

Confirmare intrebare pentru confirmarea unor informatii

Influenta asupra ascultatorului = directivele lui Searl

Optiune o sugestie slaba sau o lista de optiuni

Ordin este de fapt o comanda

Influenta asupra vorbitorului = directivele lui Austin

Oferta vorbitorul se ofera sa faca ceva si asteapta confirmarea

Executie vorbitorul face ceva

Acte Conventionale

Deschidere mesaje de intampinare

Incheiere mesaje de inchidere

Multumire multumiri si raspunsuri la multumiri

Functia de adaptare regresiva se bazeaza pe relatia dintre notiunea curenta si alte notiuni care au fost enuntate anterior de catre alte persoane. Aceasta include acceptarea/refuzarea propunerilor precum si notiuni de grupare:

Acord raspunsul vorbitorului la o propunere anterioara

Accepta acceptarea propunerii

Accepta Partial accepta o parte a propunerii

Poate nici nu accepta, dar nici nu refuza

Refuza refuzarea propunerii

Refuza Partial refuzarea partiala a propunerii

Abtinere amana/evita raspunsul

Raspuns raspunsul la o intrebare

Intelegere daca vorbitorul intelege notiunea anterioara

Semnal de neintelegere vorbitorul nu a inteles

Semnal de intelegere vorbitorul a inteles

Aprobare demonstrare prin continuare

Repetare/Reformulare demonstrare prin repetitie/reformulare

Completare demonstrare prin completare, prin colaborare

3.2 Interpretarea actelor de vorbire

Odata cu dezvoltarea teoriei actelor de vorbire, au aparut doua modele de interpretare a acestora: primul dintre ele este un model inferential, iar cel de-al doilea este bazat pe modelul idiomului.

Modelul inferential a fost propus prima data de Gordon si Lakoff, iar mai tarziu a fost sustinut si de Searle. Acest model este bazat pe inferenta unei serii de deductii logice pornind de la ceea ce vorbitorul intreaba si ceea ce interlocutorul cunoaste si tinand cont de maximele lui Grice. Modelul a fost dezvoltat de catre Allen, Cohen si Perrault in lucrari ce foloseau un model BDI (belief, desire, intention). Aceste modele necesitau o axiomatizare a actiunilor si a planificarii, cea mai simpla metoda fiind bazata pe un set de scheme de actiune similar modelului STRIPS de planificare in inteligenta artificiala. Fiecare schema de actiune avea un set de constrangeri referitoare la tipul fiecarei variabile in parte si era compusa din trei parti:

Preconditii: conditiile ce trebuiesc sa fie indeplinite inainte de executarea actiunii curente, pentru a putea duce la bun sfarsit actiunea

Efecte: conditiile ce devin adevarate ca urmare a efectuarii actiunii curente

Corp: un set de stari ordonate reprezentand scopuri partiale ce trebuiesc atinse in efectuarea actiunii curente.

Aceasta metoda de abordarea a dialogului este extrem de puternica datorita utilizarii unor structuri bogate in cunostinte si a unor tehnici de planificare extrem de eficiente, dar are si dezavantaje. Dezavantajul major al acestei metode este timpul foarte mare necesar atat din punct de vedere al programatorului – timpul pierdut cu dezvoltarea unor euristici inferentiale – cat si din punctul de vedere al timpului de executie al acestor euristici. Acest model reprezinta o problema AI-completa, ce nu poate fi cu adevarat rezolvata fara a rezolva intreaga problema a crearii unei inteligente artificiale.

Astfel, in multe aplicatii, un model mai putin sofisticat, dar mai eficient este suficient. O astfel de metoda este o varianta a modelului idiomului. O metoda de intrepretare a actelor de vorbire bazata pe modelul idiomului este Preconditii: conditiile ce trebuiesc sa fie indeplinite inainte de executarea actiunii curente, pentru a putea duce la bun sfarsit actiunea

Efecte: conditiile ce devin adevarate ca urmare a efectuarii actiunii curente

Corp: un set de stari ordonate reprezentand scopuri partiale ce trebuiesc atinse in efectuarea actiunii curente.

Aceasta metoda de abordarea a dialogului este extrem de puternica datorita utilizarii unor structuri bogate in cunostinte si a unor tehnici de planificare extrem de eficiente, dar are si dezavantaje. Dezavantajul major al acestei metode este timpul foarte mare necesar atat din punct de vedere al programatorului – timpul pierdut cu dezvoltarea unor euristici inferentiale – cat si din punctul de vedere al timpului de executie al acestor euristici. Acest model reprezinta o problema AI-completa, ce nu poate fi cu adevarat rezolvata fara a rezolva intreaga problema a crearii unei inteligente artificiale.

Astfel, in multe aplicatii, un model mai putin sofisticat, dar mai eficient este suficient. O astfel de metoda este o varianta a modelului idiomului. O metoda de intrepretare a actelor de vorbire bazata pe modelul idiomului este abordarea bazata pe cuvinte-cheie.

O caracteristica a modelului bazat pe cuvinte-cheie este faptul ca se utilizeaza diferite surse de informatii pentru identificarea actelor de vorbire (lexicale, colocutionale, sintactice, prozodice). Aceste modele utilizeaza algoritmi de invatare, antrenati pe un corpus de dialog care este adnotat de utilizator cu actele de vorbire pentru fiecare replica in parte. Multe sisteme se bazeaza pe faptul ca actele de vorbire individuale au de obicei o microgramatica a lor, adica un sistem specific lor din punct de vedere lexical, colocutional, prozodic si cu o anumita structura conversationala.

Mai multe persoane, incepand cu Nagata si Morimoto, si-au dat seama ca o mare parte a structurii acestor microgramatici poate fi simplu determinata prin antrenarea unor gramatici N-gram separat pentru fiecare act de vorbire in parte. Aceste sisteme creaza minicorpusuri separate formate din replicile care reprezinta aceleasi acte de vorbire, iar apoi antreneaza modele bazate pe gramatici N-gram pentru fiecare astfel de minicorpus in parte. Dandu-se o replica de intrare constand intr-o serie de cuvinte W, se va alege actul de vorbire d a carui gramatica N-gram asociata da cea mai mare rata de asemanare cu W:

d* = argmaxd P(d|W) = argmaxd P(d)P(W|d).

O alta metoda de determinare a microgramaticii este cea prozodica. Aceasta metoda se bazeaza pe ridicarea sau coborarea tonului, pe variatia accentului si pe corelatii acustice cum ar fi durata sau energia folosita. Un sistem bazat pe rezultatele obtinute pe aceasta cale a fost construit de catre Shrinberg. El a antrenat arbori de decizie de tip CART pe trasaturi simple de prozodie bazate pe acustica (variatia intonatiei la sfarsitul replicilor, energia medie folosita in diferite locuri din replica, variatia duratei) si a descoperit ca aceasta metoda era utila in determinarea tipurilor de acte de vorbire: afirmatii, intrebari de tipul da/nu, aprobari, intrebari de tipul cine/cum/unde/cand.

Un important indiciu pentru interpretarea actelor de vorbire este structura conversationala. O modalitate simpla de a modela structura conversationala, bazata pe idea perechilor de adiacenta este obtinerea unei secvente probabilistice a actelor de vorbire. Identificarea actelor de vorbire curente poate fi folosita in continuare la prezicerea urmatoarelor acte. In multe studii, modelul actelor de vorbire a fost dat sub forma unor gramatici N-gram de acte de vorbire, uneori chiar ca o parte a unor modele Markov ascunse pentru aceste acte.

3.3 Identificarea actelor de vorbire pe baza unui Model Markov ascuns (Hidden Markov Model – HMM)

Aceasta abordare presupune prezenta canalului comunicational de perturbatii introdus in teoria informatiei lui Shannon.

Sistemele de recunoastere a actelor de vorbire trateaza intrarile ca fiind o forma ambigua, afectata de erori a sursei.

Se considera ca avem un mesaj initial, format din acte de vorbire, ce intra in canal si textul dialogului care este iesirea din acesta. In aceste conditii, pentru a determina efectul perturbatiilor din canal, se vor calcula (pentru fiecare semnal in parte) probabilitatile de a fi un anumit semnal, iar dupa accea se va lua in considerare semnalul a carei probabilitate este maxima.

In cazul identificarii actelor de vorbire avem mai multe semnale care pornesc de la sursa si mai multe semnale care ajung la destinatie, iar in acest caz se pune intrebarea: “Care este cea mai probabila secventa ce a pornit de la sursa si care a ajuns la destinatie in forma data?”

Fie D=d1d2d3..dn secventa de semnale care porneste de la sursa si E=e1e2e3..en secventa de semnale care ajunge la destinatie. Se pune problema calcularii unei secvente D*, care maximizeaza probabilitatea ca la iesire sa se obtina secventa E conditionata de intrari:

D*=argmaxP(D|E)=argmaxP ((P(E|D)*P(D)) / P(E))

Cum iesirea este intotdeauna aceeasi, inseamna ca P(E) este constanta si cum pe noi ne intereseaza de fapt secventa maxima si nu valoarea maxima, nu vom mai tine cont de P(E). Ne intereseaza, prin urmare, maximul produsului dintre probabilitatea P(E|D)*P(D), adica:

D*=argmax(P(E|D)*P(D))

Daca expandam P(D) obtinem:

P(D)=P(d1)*P(d2|d1)*….P(dn|d1,d2…)

Aceasta probabilitate este greu de calculat si atunci ea se aproximeaza considerand ipoteza unui lant (model) Markov de ordin k, adica faptul ca fiecare semnal in parte depinde doar de k semnale anterioare, cu valori tipice k=1 (cand avem practic un automat finit cu tranzitii probabiliste, caz de multe ori denumit model Markov fara a mai preciza un ordin) sau k=2. Pentru k=1 se va calcula P(D) ca:

P(D)=P(d1)*P(d2|d1)*P(d3|d2)…*P(dn|dn-1)

unde P(di) este probabilitatea de aparitie a fiecarui tip de semnal in parte si P(di|di-1) este probabilitatea conditionata sa avem di daca am avut inainte di-1, altfel spus, sa avem bigrame. In concluzie trebuie sa se calculeze probabilitatile bigramelor. Daca se considera k=2, apare o formula similara in care intervine P(di|di-1,di-2), adica este nevoie de probabilitatile trigramelor.

Pentru P(E|D) se face o simplificare similara:

P(E|D)= P(e1|d1)*P(e2|d2)…*P(en|dn)

Pentru calculul bigramelor (P(a|b)) se procedeaza în urmatorul mod:
initial se numara toate tagurile din text si se obtine valoarea nr_total. Dupa aceea, se numara tagurile din fiecare tip (nr_act_vorbire) in parte: nr_accept, nr_reject, nr_maybe, nr_accept_part, nr_reject_part, nr_none. In continuare se calculeaza probabilitatile de aparitie ale fiecarui tip ca fiind:

prob_act_vorbire=nr_act_vorbire/nr_total

Pasul urmator este numararea succesiunilor nr_Act1_Act2, adica nr_AP_AP; nr_AP_RP; nr_AP_A; nr_AP_R; s.a.m.d., pentru ca intr-un ultim pas sa se calculeze probabilitatile :

prob_Act1_Act2=nr_Act1_Act2/nr_Act1

In momentul in care se obtin aceste probabilitati, se construieste un tablou (k+1)-dimensional, in care se trec probabilitatile obtinute. Pe baza acestui tablou (k+1)-dimensional aplicandu-se mai departe un algoritm de decodificare, se pot recunoaste actele de vorbire din texte neadnotate.

In situatia in care k=1, tabloul bidimensional, este de fapt o matrice. Pe baza acestei matrice se poate construi un automat finit, in care trecerile dintr-o stare in alta sa se faca probabilistic, fiecare tranzitie din automat avand ca probabilitate asignata probabilitatea din matricea obtinuta anterior. Un astfel de automat este un model Markov ascuns (Hidden Markov Model), iar matricea este matricea asociata acestui model. Iata in continuare un exemplu de HMM:

Se observa ca suma arcelor ce pleaca dintr-un nod este 1, deoarece suma probabilitatilor unui act de vorbire trebuie sa fie 100%.

3.4 Recunoasterea actelor de vorbire folosind algoritmul Viterbi

Un avantaj major al automatelor finite este ca exista algoritmi eficienti de generare a probabilitatilor ce sunt necesare in implementarea metodei lui Bayse de recunoastere corecta a cuvintelor. Acesti algoritmi se pot aplica in particular si asupra modelelor Markov ascunse.

Un algoritm foarte simplu de calcul al probabilitatilor de asemanare intre cuvinte si sunete este algoritmul anticipativ (forward algorithm), care este un algoritm de programare dinamica. Acest algoritm este util in special cand sunt mai multe cai in automat pe care se poate merge de la intrare. El este punctul de plecare pentru definirea algoritmului Viterbi si a fost derivat din algoritmul distantei minime (minimum edit distance). Rolul unui astfel de algoritm este de a identifica cuvintele ce ar fi putut produce la iesire o anumita secventa de observare. Acest lucru se numeste decodificarea problemei. Pentru a realiza decodificarea, algoritmul se aplica asupra fiecarui cuvant in parte pentru a-i determina probabilitatea, iar apoi se alege cuvantul cu probabilitatea maxima.

Pentru a putea gasi calea optima in problema decodificarii, algoritmul isi construieste o tabela de rezultate intermediare pe masura ce se calculeaza probabilitatea secventei de observare.

Dar acest algoritm are si limitari, acestea provenind mai ales din faptul ca se fac prea multe calcule. Daca la un moment dat nu poate sa existe decat o cale pe care se poate merge mai departe, nu e nevoie sa se foloseasca o tabela bidimensionala pentru a retine toate combinatiile posibile. De asemenea, faptul ca acest algoritm trebuie sa fie aplicat asupra fiecarui cuvant in parte il face foarte inficient.

Aceste neajunsuri sunt eliminate printr-o usoara modificare a algoritmului anticipativ, astfel obtinandu-se algoritmul Viterbi. Acest algoritm ne permite sa consideram toate cuvintele simultan si sa calculam cea mai probabila cale. Algoritmul Viterbi este foarte folosit in recunoasterea sunetelor si a cuvintelor, dar ca si algoritmul anticipativ, este o aplicatie standard de programare dinamica, semanand cu algoritmul distantei minime. Algoritmul Viterbi a fost aplicat prima data de catre Vintsyuk.

Acest algoritm se foloseste foarte des in decodificarea problemei modelate prin automate finite probabilistice sau modele Markov ascunse. El are ca rezultat gasirea celei mai probabile cai printr-o retea compusa din mai multe cuvinte simple, pentru aceasta alegand de fiecare data cuvantul cu cea mai mare probabilitate de a genera o anumita observatie (secventa de observatii).

Verisunea algoritmului Viterbi care ne intereseaza primeste la intrare un automat finit probabilistic si o serie de sunete observate o=(o1o2o3…on) si returneaza cea mai probabila secventa de stari q=(q1q2q3…qn), impreuna cu probabilitatea cu care aceasta secventa a fost determinata.

Ca si algoritmul anticipativ, algoritmul Viterbi isi creeaza o matrice de probabilitati, avand pe coloane fiecare moment de timp, iar pe linii, fiecare stare posibila. Tot ca algoritmul anticipativ, fiecare coloana are cate o celula pentru fiecare stare in parte. De fapt, algoritmul Viterbi este identic cu algoritmul anticipativ, cu exceptia a doua modificari. In primul rand, algoritmul anticipativ plaseaza in fiecare celula in parte suma tuturor cailor anterioare, in timp ce algoritmul Viterbi va pune probabilitatea maxima gasita in caile anterioare in celula curenta.

Algoritmul creaza mai intai N+2 coloane, unde N reprezinta numarul total de unitati de timp. Prim coloana este o pseudo-observatie initiala, a doua corespunde primului moment de timp, a treia celui de-al doilea moment de timp s.a.m.d. Algoritmul incepe din prima linie si prima coloana, setand probabilitatea starii de start ca fiind 1, iar restul ca fiind 0.

Apoi se trece in starea urmatoare (la fel cum se face la algoritmul anticipativ) astfel: pentru fiecare stare din coloana 0 se calculeaza valorile probabilitatilor de a trece intr-una din starile din coloana 1. Apoi se calculeaza valorile probabilitatilor din coloana a doua pe baza celor din prima coloana si operatiunea se repeta pana la utlima coloana. Valoarea viterbi[t,j] unde t este momentul de timp, iar j este starea asociata, se calculeaza considerand maximul din toate extensiile cailor anterioare ce pot ajunge in pasul curent. O extensie a unei cai de la o stare i in care se afla la momentul t-1, la o alta stare se calculeaza prin inmultirea acelorasi factori ca la algoritmul anticipativ:

Probabilitatea caii anterioare din celula anterioara viterbi[t-1,j]

Probabilitatea tranzitiei aij din starea anterioara i in starea curenta j

Probabilitatea asemanarii bij dintre starea curenta j si simbolul observatiei la momentul t. Pentru automatele finite probabilistice, se poate considera ca bij poate lua valoarea 1 daca simbolul observatiei corespunde starii considerate, iar 0 daca nu corespunde.

La sfarsit se cauta valoarea maxima din ultima coloana, iar aceea este probabilitatea cu care s-a gasit calea optima. Pornind de la starea in care s-a gasit valoarea maxima, se reconstruieste calea pe care s-a mers pentru a ajunge in acel punct, iar dupa aceea se returneaza calea gasita.

Capitolul 4. Netezirea matricei HMM folosind metoda lui Katz

In urma identificarii modelului lingvistic, se obtin tablouri cu probabilitatile succesiunilor dintre actele de vorbire. De cele mai multe ori, aceste tablouri nu sunt uniforme, putand aparea situatii in care sa avem de-a face cu tablouri rare. Aceasta situatie apare mai ales din faptul ca modelul lingvistic se obtine in urma antrenarii unor algoritmi de invatare pe anumite corpusuri, iar aceasta antrenare nu se poate face pe corpusuri mari. Aceasta duce la subestimarea probabilitatilor unor acte de vorbire, ceea ce face ca in tablou, anumite probabilitati sa apara ca fiind 0, desi in realitate ele nu ar trebui sa fie nule. Pentru a evita aceasta situatie, se aplica algoritmi de netezire a tablourilor, care elimina valorile nule din acestea. Exista mai multe modalitati de netezire. Cea mai simpla dintre ele, dar si cu rezultatele cele mai slabe, este metoda adaugarii unei unitati (add-one smoothing). Datorita rezultatelor slabe, aceasta metoda nu este folosita. O alta metoda de netezire se numeste Written-Bell deoarece a fost introdusa de cei doi autori. Ea se bazeaza pe o intuitie simpla dar in acelasi timp ingenua referitoare la probabilitatile ce au valoarea 0. O metoda mai folosita decat Written-Bell este cea descoperita de Good , dar care mentioneaza ca Turing a fost autorul ei. Din aceasta cauza metoda se numeste Good-Turing. Aceasta metoda este mult mai complexa decat cea anterioara si se bazeaza pe reevaluarea probabilitatilor nule din tablou prin considerarea ordinelor imediat superioare. Adica, daca avem o probabilitate nula, ne vom uita la valoarea pe care o reprezinta acea probabilitate, iar dupa aceea vom considera probabilitatea valorii imediat superioare. Prin combinarea acestei metode cu metoda interpolarii si cu metoda revenirii, se obtine o metoda de netezire mult mai eficienta, numita metoda Katz. In continuare se va prezenta modul de calcul al metodei Katz pentru bigrame, adica pentru un model Markov ascuns de ordinul 1. Valoare finala netezita este data de formula:

Pk(w2|w1) =P~(w2|w1) + Θ(P~(w2|w1)) * α(w1) * P(w2)

In aceasta formula Θ(x) ia valoarea 0 in cazul in care x este nenul, sau 1 in cazul in care x este nul. Acest factor este folosit pentru a netezi doar valorile care sunt nule.

α este constanta de normalizare si se calculeaza in felul urmator:

α(w1)= ( 1- ΣC(w1,w2)>0(P~(w2|w1)) ) / ( 1- ΣC(w1,w2)>0(P(w2)) )

P~(w2|w1) se calculeaza conform formulei

P~(w2|w1)= dC(w1|w2) * C(w1|w2) / C(w1)

unde dC este un coeficient de discount.

In continuare se va prezenta modul de calcul al lui dC:

dC=( c*/c – (k-1) * nk+1 / n1 ) / ( 1 – (k-1) * nk+1 / n1 )

unde k este limita peste care nu se mai calculeaza netezirea, iar nj este numarul de bigrame ce apar in text de exact j ori. Katz recomanda ca valoarea lui k sa fie 5. In formula de mai sus mai intervine o variabila c*. Aceasta se calculeaza in felul urmator:

c*=(c+1) * nc+1 / nc

In felul acesta se face netezirea matricei de bigrame. Similar se face si pentru trigrame. Dupa aplicarea acestei metode, matricea ce reprezinta modelul Markov ascuns nu va mai contine nici o valoarea nula si va putea fi folosita in continuare la recunoasterea actelor de vorbire.

Capitolul 5. Prezentarea aplicatiei

Aplicatia urmareste identificarea actelor de vorbire din fisiere .html sau .txt avand un anumit format. Pentru a permite acest lucru, aplicatia lucreaza in mai multi pasi:

In primul pas se face transformarea din fisier .html/.txt in fisiere .xml, care sunt mai usor de prelucrat si in care se poate adauga informatie suplimentara (care mai tarziu va fi utilizata)

In al doilea pas se va realiza adnotarea manuala (adnotare star) a unor documente .xml care au fost obtinute la pasul anterior si care vor fi folosite in continuare pe post de baza de cunostiinte pe care se va aplica algoritmul de invatare

In al treilea pas se va aplica algoritmul de invatare asupra fisierelor adnotate in pasul al doilea si se vor genera anumite structuri probabile ale fisierelor

In al patrulea pas se vor aplica rezultatele obtinute in pasul anterior pe fisiere neadnotate manual, iar acestea vor fi adnotate automat pe baza modelelor rezultate in urma invatarii

In ultimul pas al aplicatiei se face o comparatie intre rezultatele obtinute prin adnotare automata si rezultatele obtinute prin adnotare manuala, pentru a vedea cat de eficienta este aceasta metoda de lucru

Capitolul 6. Schema bloc a aplicatiei

In continuare se va prezenta in detaliu fiecare pas al aplicatiei in parte.

Capitolul 7. Prezentarea detaliata a fiecarui pas in parte

Implementarea programelor s-a facut folosind mediul de programare JAVA pentru a putea fi rulate in orice sitem de operare care are o masina virtuala Java instalata (atat Windows cat si Linux).

7.1 Pasul 1 – Adnotare

Pseudocodul

Adnotare (numar, fisier_intrare,fisier_lucru,fisier_iesire)

Daca (numarul=0) prelucrare (fisier_intrare, fisier_iesire,fisier_intrare)

Altfel

citire (fisier_intrare,fisier_lucru)

prelucrare (fisier_lucru, fisier_iesire,fisier_intrare)

Citire (fisier_intrare,fisier_iesire)

Deschide cele 2 fisiere

Cat timp fisier_intrare nu e gol

Citeste din fisier_intrare

Daca (s-a gasit caracterul ‘<’)

Atunci am intrat in comentariu

Daca (nu sunt in comentariu)

Atunci scrie in fisier_iesire ce am citit

Altfel

Daca (se gaseste caracterul ‘>’)

Atunci se iese din comentariu

Inchide cele 2 fisiere

Prelucrare (fisier_1,fisier_2,fisier_3)

Deschide fisierele fisier_1 si fisier_2

In fisier_2 scrie inceputul de fisier .xml al carui Id este fisier_3

Cat timp fisier_1 nu este gol

Citeste cate o linie din fisier_1

Daca (linia nu contine ‘(‘)

Atunci se copiaza in fisierul de iesire

Altfel

Daca (primul caracter e’(‘)

Atunci se copiaza linia la iesire (este linie de comentariu)

Altfel

Daca (nu gasesc ‘(‘)

Atunci copiez linia la iesire (era comentariu)

pune tagurile corespunzatoare la iesire

completeaza taguri cu atributele corespunzatoare

Inchide ultimele taguri

Inchide cele 2 fisiere deschise

Modalitatea de executie

Compilare: javac Adnotare/*.java

Executie efectiva: java Adnotare.Adnotare nr fisier_1 fisier_2 fisier_3

Semnificatia parametrilor dati la executie este:

Nr – specifica daca se face si parsarea fisierului de intrare (fisier_1) sau numai transformarea lui in fisier de tip .xml. Poate lua valoarea 0 sau 1. Daca valoarea este 0, atunci nu se mai face parsarea – se foloseste daca la intrare am fisiere de tip .txt. Daca valoarea este 1, se face mai intai parsarea, rezultatul parsarii fiind afisat in fisierul fisier_2 (care este un fisier de lucru intermediar), iar abia dupa aceea se va face transformarea in .xml, rezultatul fiind afisat in fisierul fisier_3. Valoarea 1 se foloseste cand la intrare avem fisiere de tipul .html.

Fisier_1 – fisierul care se doreste a fi transformat in .xml. Poate fi de tip .html sau .txt dar cu un format fix (format care va fi prezentat mai jos).

Fisier_2 – fisierul de lucru. Este folosit doar in cazul in care avem la intrare un fisier .html si se face mai intai transformarea in fisier .txt. In acest fisier se salveaza forma intermediara ce urmeaza a fi transformata in fisier .xml. Acest fisier se creeaza pentru a ajuta la debugging (daca este necesar).

Fisier_3 – fisierul rezultat. Acesta va fi fisierul .xml ce se doreste a fi obtinut.

Prezentarea principalelor functii si variabile din program

Variabile

Comentariu – specifica daca sunt intr-un comentariu sau nu. Nu se foloseste decat daca se face parsarea fisierului de intrare (.html). Este folosit pentru a elimina tagurile specifice formatului .html. Daca are valoarea 0 inseamna ca nu sunt intr-un tag specific formatului .html, iar informatia trebuie copiata la iesire. Daca valoarea este 1, inseamna ca sunt intr-un tag .html si trebuie sa caut momentul inchiderii lui. Pana atunci nu se va afisa nimic la iesire.

Nr_turn – se initializeaza la 0 si se incrementeaza inaintea fiecarei noi ture. Este utilizat pentru a contoriza numarul turelor din program si pentru a asigura un Id unic fiecareia in parte.

Nr_utt – este folosit in acelasi scop ca Nr_turn. Singura diferenta este ca se initializeaza la 1 si se incrementeaza dupa fiecare replica in parte.

First – este folosit pentru a specifica daca sunt la prima tura/replica sau nu. Este folosit pentru ca inainte de prima tura/replica sa nu inchid nici un alt tag.

Functii

citire(fisier_1, fisier_2)

Prezentare: Functia preia la intrare un fisier .html si va intoarce un fisier .txt care va reprezenta doar textul din fisierul .html, eliminand tagurile specifice formatului .html.

Functionare: Se citeste din fisierul de intrare (fisier_1) cate un caracter, iar daca se gaseste caracterul ‘<’ se intra automat in modul comentariu. Cat timp nu sunt in modul comentariu, ceea ce citesc se tipareste la iesire (fisier_2). Dupa ce am intrat in modul comentariu, se citeste in continuare cate un caracter din fisier pana cand se intalneste caracterul ‘>’, dar nu se mai tiparesc la iesire. Cand s-a intalnit caracterul ‘>’ se iese din modul comentariu.

prelucrare(fisier_1, fisier_2, fisier_3)

Prezentare: Functia primeste un fisier de intrare de tip .txt cu un anumit format si il transforma in fisier de tip .xml adaugand taguri specifice si anumite atribute:

<Turn Id="" Speaker="" time="">

<Utt Id="" Info-level="" Conventional="" Time="" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">

</Utt>

</Turn>

Functionare: La intrare se primeste un fisier .txt (fisier_1) cu un anumit format, pe care il voi prezenta in continuare printr-un mic exemplu care sa exemplifice situatiile ce pot sa apara:

(10:01:39 AM) You have just entered room "powwow1."

(10:01:49 AM) klasher321 has entered the room.

klasher321 (10:01:59 AM): hi Gerry

(10:02:00 AM) stevriz has entered the room.

klasher321 (10:02:07 AM): Hi Riz

stevriz (10:02:14 AM): Hi all

gerrystahl (10:02:40 AM): welcome Riz and Kristina

klasher321 (10:02:48 AM): Or should I say, who is this stevriz person?

stevriz (10:02:51 AM): I'm entering this experience with new optimism now that I

have this slick computer.

gerrystahl (10:03:15 AM): Shall we do some math together?

stevriz (10:03:20 AM): Well, I had already used 'steveriz' years ago and

couldn't remember the password.

gerrystahl (10:04:05 AM): do you know the powwow rules?

klasher321 (10:04:24 AM): maybe I better read them again.

stevriz (10:04:25 AM): I read the blurb on the geopow site – does that cover it?

gerrystahl (10:04:26 AM): we need a list of these rules – where are they?

gerrystahl (10:04:52 AM): suppose you have a square of side n.

gerrystahl (10:05:04 AM): The area is n^2

klasher321 (10:05:15 AM): http://mathforum.org/pow/vmt/2004021 2.info.html

gerrystahl (10:05:27 AM): How would you construct a square of area 2n^2?

stevriz (10:06:41 AM): And if the original squares are n by n, how long would

the diagonal be?

gerrystahl (10:06:43 AM): how would you "construct" that

klasher321 (10:06:47 AM): I would have written it n rt2. I don't know the proper

computer way.

gerrystahl (10:07:36 AM): share how you came up with your ideas

klasher321 (10:07:36 AM): the original diagonal is also n rt2

stevriz (10:07:46 AM): So if we took two of the original squares and cut them

along a diagonal, then put the four diamonds together to form a new square we're

all set, right? …

Initial se scrie in fisierul de iesire (fisier_2) inceputul de tag pentru intregul dialog, al carui ID va fi reprezentat de numele dat ca al treilea parametru al functiei (fisier_3). Dupa aceea se citeste cate o linie din fisierul de intrare si se cauta caracterul ‘(‘. Daca acest caracter nu a fost gasit, inseamna ca avem o linie neimportanta si o copiem la iesire. Daca s-a gasit caracterul pe prima pozitie, inseamna ca avem de-a face cu o directiva de site (se specifica daca o persoana a intrat sau a iesit de pe acea pagina) si iar se copiaza la iesire. Daca s-a gasit pe alta pozitie, incepe parsarea propriu zisa. Se retine pozitia pe care a fost gasita ‘(‘, se incrementeaza numarul turei si se incepe cautarea caracterului ’)’. Daca nu s-a gasit, inseamna ca iar am avut de-a face cu o linie neimportanta si se copiaza la iesire. Daca am gasit si acest caracter, se retine pozitia si incep sa fac tagul pentru iesire: se inchid tagurile anterioare (daca sunt la primul tag nu mai inchid nimic), se deschide noul tag si se scrie la ID numarul curent al tagului, apoi se pune speakerul si momentul de timp prin copiere din sirul initial si pana la pozitiile caracterelor ‘(‘, respectiv ’)’. Apoi se deschide tagul pentru replica (<Utterance>) si se scriu atributele corespunzatoare, completand doar valoarea atributului “Time” cu valoarea anterior determinata pentru tagul <Turn>. Dupa aceea se copiaza la iesire ceea ce a ramas pentru ca reprezinta textul efectiv. Dupa ce se termina de citit din fisier, se scriu la iesire si inchiderile ultimele taguri, inclusiv cel de dialog si apoi se inchid fisierele cu care s-a lucrat.

7.2 Pasul 2 – Adnotare manuala (Adnotare star)

Acest pas nu contine nici un fel de program, el facandu-se de catre utilizator. Se presupune ca adnotarea este facuta de catre o persoana care este experta in domeniu, ceea ce conduce la o adnotare mai buna decat orice alta adnotare facuta de catre un program automat. Din aceasta cauza, ea se mai numeste si adnotare star. Adnotarea se face dupa un model similar DAMSL-ului. Fiecare tag cotine urmatoarele atribute: Id; Info-level; Conventional; Influence-on-listener; Influence-on-speaker; Agreement; Answer.

<Utt Id="" Info-level="" Conventional="" Time="" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer=""></Utt>

Atributul Id este folosit pentru ca fiecare tag in parte sa poata fi unic identificabil, deoarece mai tarziu va fi nevoie ca fiecare tag sa poata fi identificat.

Atributul Info-level este folosit pentru a specifica tipul textului ce urmeaza. El poate lua valoarea “Task” sau “Communication-management”. Daca valoarea este “Task”, inseamna ca urmeaza o sarcina pe care cel care vorbeste o da altora (in unele cazuri, sarcina il priveste si pe el alaturi de cei cu care vorbeste). Daca valoarea este “Communication-management”, atunci textul ce va urma constituie o replica normala de dialog.

Atributul Conventional este folosit pentru a spune ca textul ce urmeaza constituie o forma speciala de dialog. El poate lua valorile: “Opening”, “Closing” sau “Thanking” reprezentand formule standard de deschidere a unei discutii, de incheiere a ei, respectiv de multumire si de raspuns la multumiri.

Atributul Time ne spune la ce moment de timp a fost trimis mesajul respectiv. El este extras din textul ce trebuie adnotat.

Atributul Influence-on-listener poate lua valorile “Info-request-directive” sau “Check” . Daca valoarea este “Info-request-directive” atunci inseamna ca vorbitorul pune o intrebare interlocutorilor. Daca valoarea este “Check” inseamna ca vorbitorul vrea sa se asigure de un anumit lucru si le cere interlocutorilor sa ii confirme ceea ce spune.

Atributul Influence-on-speaker specifica faptul ca vorbitorul se ofera sa faca ceva. Acest atribut nu a fost folosit, dar a fost introdus pentru o eventuala dezvoltare a aplicatiei in care ar putea fi si el folosit.

Atributul Agreement specifica tipul de raspuns al vorbitorului la niste replici anterioare. El poate lua urmatoarele valori: “Accept”, “Reject”, “Maybe”, “Accept Part”, “Reject Part”, “None”. Daca valoarea este ”Accept”, atunci inseamna ca vorbitorul este de acord cu una din replicile anterioare. Daca valoarea este “Reject”, atunci vorbitorul nu este de acord cu una din replicile anterioare. Daca valoarea este “Maybe”, inseamna ca vorbitorul nici nu accepta dar nici nu respinge ceea ce s-a spus inainte. De asemenea poate insemna si ca vorbitorul refuza sa isi spuna parerea clar, dand un raspuns evaziv. Daca valoarea este ”Accept Part”, inseamna ca autorul este de acord cu ceea ce s-a spus inainte, dar nu in totalitate. El accepta doar o parte din ceea ce s-a spus inainte, asupra restului avand unele dubii. Daca valoarea este “Reject Part”, insemna ca autorul respinge ceea ce s-a enuntat inainte, dar ca sunt si parti cu care este de acord. In fine, daca valoarea este “None”, inseamna ca textul ce urmeaza nu se inscrie in nici unul din tiparele de mai sus si ca este o simpla replica.

Acest atribut este atributul cel mai util in aplicatia de fata, in functie de valorile acestui atribut stabilindu-se tipologia intregului dialog. Valorile acestui atribut sunt folosite in continuare in partea de invatare si tot acest atribut va fi cel care va trebui sa fie identificat automat in partea de recunoastere a aplicatiei. Statisticile din ultimul pas al aplicatiei se vor face tot pe baza valorilor acestui atribut.

Atributul Answer specifica la care dintre replicile anterioare se refera/raspunde replica curenta. Acest atribut va avea ca valori id-urile tagurilor la care raspunde acesta replica. Din aceasta cauza, atributul Id trebuie sa fie unic.

Exemplu

In continuare voi da un mic exemplu de adnotare. Voi lua ca text de adnotat o parte din textul prezentat mai sus (pentru a arata formatul fisierelor de intrare in pasul intai).

(10:01:39 AM) You have just entered room "powwow1." (10:01:49 AM) klasher321 has entered the room.

<Turn Id="T1" Speaker="klasher321" time="10:01:59 AM">

<Utt Id="Utt1" Info-level="" Conventional="Opening" Time="10:01:59 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">hi Gerry (10:02:00 AM) stevriz has entered the room.</Utt>

</Turn>

<Turn Id="T2" Speaker="klasher321" time="10:02:07 AM">

<Utt Id="Utt2" Info-level="" Conventional="Opening" Time="10:02:07 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">Hi Riz</Utt>

</Turn>

<Turn Id="T3" Speaker="stevriz" time="10:02:14 AM">

<Utt Id="Utt3" Info-level="" Conventional="Opening" Time="10:02:14 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">Hi all</Utt>

</Turn>

<Turn Id="T4" Speaker="gerrystahl" time="10:02:40 AM">

<Utt Id="Utt4" Info-level="" Conventional="Opening" Time="10:02:40 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">welcome Riz and Kristina</Utt>

</Turn>

<Turn Id="T5" Speaker="klasher321" time="10:02:48 AM">

<Utt Id="Utt5" Info-level="Communication-management" Conventional="" Time="10:02:48 AM" Influence-on-listener="Info-request-directive" Influence-on-speaker="" Agreement="None" Answer="">Or should I say, who is this stevriz person?</Utt>

</Turn>

<Turn Id="T6" Speaker="stevriz" time="10:02:51 AM">

<Utt Id="Utt6" Info-level="Communication-management" Conventional="" Time="10:02:51 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">I'm entering this experience with new optimism now that I have this slick computer.</Utt>

</Turn>

<Turn Id="T7" Speaker="gerrystahl" time="10:03:15 AM">

<Utt Id="Utt7" Info-level="Task" Conventional="" Time="10:03:15 AM" Influence-on-listener="Info-request-directive" Influence-on-speaker="" Agreement="None" Answer="">Shall we do some math together?</Utt>

</Turn>

<Turn Id="T8" Speaker="stevriz" time="10:03:20 AM">

<Utt Id="Utt8" Info-level="Communication-management" Conventional="" Time="10:03:20 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="Utt5">Well, I had already used 'steveriz' years ago and couldn't remember the password.</Utt>

</Turn>

<Turn Id="T9" Speaker="stevriz" time="10:03:29 AM">

<Utt Id="Utt9" Info-level="Task" Conventional="" Time="10:03:29 AM" Influence-on-listener="Action-directive" Influence-on-speaker="" Agreement="Accept" Answer="Utt7">let's do some geometry!</Utt>

</Turn>

<Turn Id="T10" Speaker="klasher321" time="10:03:41 AM">

<Utt Id="Utt10" Info-level="Communication-management" Conventional="" Time="10:03:41 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="Accept" Answer="Utt9">ok!</Utt>

</Turn>

<Turn Id="T11" Speaker="gerrystahl" time="10:04:05 AM">

<Utt Id="Utt11" Info-level="Communication-management" Conventional="" Time="10:04:05 AM" Influence-on-listener="Info-request-directive" Influence-on-speaker="" Agreement="None" Answer="">do you know the powwow rules?</Utt>

</Turn>

<Turn Id="T12" Speaker="klasher321" time="10:04:24 AM">

<Utt Id="Utt12" Info-level="Communication-management" Conventional="" Time="10:04:24 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="Maybe" Answer="Utt11">maybe I better read them again.</Utt>

</Turn>

<Turn Id="T13" Speaker="stevriz" time="10:04:25 AM">

<Utt Id="Utt13" Info-level="Communication-management" Conventional="" Time="10:04:25 AM" Influence-on-listener="Info-request-directive" Influence-on-speaker="" Agreement="None" Answer="Utt9">I read the blurb on the geopow site – does that cover it?</Utt>

</Turn>

<Turn Id="T14" Speaker="gerrystahl" time="10:04:26 AM">

<Utt Id="Utt14" Info-level="Task" Conventional="" Time="10:04:26 AM" Influence-on-listener="Info-request-directive" Influence-on-speaker="" Agreement="None" Answer="Utt11">we need a list of these rules – where are they?</Utt>

</Turn>

7.3 Pasul 3 – Invatare

Pseudocodul

Invatare(numar, fisier_1, fisier_2, fisier_3, fisier_4)

Deschide cele 4 fisiere

Pentru i cuprins intre 0 si numar executa

count(i)

Calculeaza procentele din fiecare tip in parte

Calculeaza precedentele de cate 2 tipuri (matricea HMM)

Calculeaza precedentele de cate 3 tipuri

Netezeste matricea de precedente de 2 tipuri rezultata (HMM)

Scrie rezultatele in fisiere:

Scrie procentele in fisier_1

Scrie matricea de precedenta de 2 tipuri in fisier_2

Scrie matricea de precedenta de 3 tipuri in fisier_3

Scrie matricea netezita in fisier_4

Inchide cele 4 fisiere

count(i)

Creaza numele fisierului numarul i

Deschide fisierul cu numele creat

Pentru fiecare tag deschis executa

startElement(nume, locatie, tip, atribute)

startElement(nume, locatie, tip, atribute)

In functie de valoarea atributului incrementeaza numarul atributelor de acel tip

Adauga atributul in vectorul de atribute

calculProcente()

Pentru fiecare tip de atribut executa

calculeaza procentul acelui atribut din numarul total de atribute

calculPrecedente()

Determina tipul primului atribut

Realizeaza atribuirea atribut_anterior=tipul primului atribut

Construieste matricea de precedente initializata la 0

Pentru fiecare atribut de la atributul 1 pana la ultimul

Determina tipul atributului curent

Incrementeaza valoarea matricei de pe linia corespunzatoare atributului anterior si coloana corespunzatoare atributului curent

Realizeaza atribuirea atribut_anterior=atribut_curent

calculPrecedente2()

Determina tipul primului atribut

Determina tipul celui de-al doilea atribut

Realizeaza atribuirea atribut_anterior=tipul primului atribut

Realizeaza atribuirea atribut_last=tipul celui de-al doilea atribut

Construieste tabloul de precedente tridimensional initializat la 0

Pentru fiecare atribut de la atributul 1 pana la ultimul

Determina tipul atributului curent

Incrementeaza valoarea tabloului cu indicii corespunzatori atributelor anterior, last si curent

Realizeaza atribuirea atribut_anterior=atribut_last

Realizeaza atribuirea atribut_last=atribut_curent

Smooth()

Initializeaza limita pana la care se face netezirea

Se construiesc vectorii de valori din matricea de precedente (diferite de 0) si de frecvente ale acestor valori si se initializeaza la 0

Se construiesc vectorii intermediari rstar si dr

Se construieste vectorul de factori alfa

Se construieste matricea rezultat p_tilda

Initializeaza limita pana la care se face netezirea

Pentru fiecare valoare din matricea de precedente diferita de 0

Daca valoarea exista deja in vectorul de valori

Atunci incrementeaza valoarea corespunzatoare din vectorul de frecvente

Altfel

adauga valoarea in vectorul de valori

pe pozitia pe care a fost adaugata valoare in vectorul de valori, pune valoarea 1 in vectorul de frecvente

Pentru fiecare valoare din matricea de precedente diferita de 0

Daca valoarea este mai mare ca limita

Atunci rstar[i]=valoare[i]

Altfel

Cautam in vectorul de frecvente valoarea (1+valoare[i]) si salvam pozitia daca aceasta valoare a fost gasita

Daca valoarea nu a fost gasita

Atunci rstar[i]=0

Altfel se calculeaza rstar[i]

Se calculeaza constanta ce intervine in formula astfel:

Daca valoarea (limita+1) exista in vectorul de valori

Atunci se retine indexul si se calculeaza valoarea constantei

Altfel se initializeaza constanta cu 0

Se calculeaza valorile vectorului dr[i] astfel:

Daca valoarea 1 exista in vectorul de valori

Atunci se retine indexul si se actualizeaza valoarea constantei si se calculeaza valoarea dr[i]

Altfel se initializeaza valoarea dr[i] cu 1

Se calculeaza valorile matricei p_tilda:

Daca valoarea din matricea de precedente (mat[i][j])e mai mare ca limita

Atunci se actualizeaza valoarea matricei p_tilda[i][j] cu valoarea frecventei valorii din matricea de precedente

Altfel se initializeaza valoarea matricei p_tilda[i][j] cu valoarea frecventei valorii din matricea de precedente * vectorul dr[i]

Se calculeaza valorile vectorului alfa

Se actualizeaza valorile matricei p_tilda astfel:

Daca p_tilda[i][j]=0

Atunci p_tilda[i][j]=alfa[j] * frecventa atributului i

Modalitatea de executie

Compilare: javac Invatare/*.java

Executie efectiva: java Invatare.Invatare nr fisier_1 fisier_2 fisier_3 fisier_4

Semnificatia parametrilor dati la executie este:

Nr – reprezinta cate fisiere vor fi folosite la partea de invatare. In aceasta parte, vor fi deschise fisierele cu nume “Adnotat_.xml” unde _ reprezinta toate numerele de la 1 pana la nr inclusiv si se va aplica algoritmul de invatare pe ele.

Fisier_1 – este fisierul in care vor fi intoarse rezultatele partiale, continand statistici mai putin folositoare in continuare, dar care ne dau o anumita imagine asupra fisierelor.

Fisier_2 – este fisierul in care se va afisa matricea HMM. El contine procentul fiecaror bigrame intalnite in fisierele de invatare.

Fisier_3 – este fisierul in care se afiseaza tabloul de procente ale trigramelor intalnite in fisierele de invatare.

Fisier_4 – este fisierul in care se va afisa matricea HMM dupa ce a fost netezita folosind algoritmul Katz.

Prezentarea principalelor functii si variabile din program

a) Fisierul Parsare.java

– acest fisier extinde interfata AbstractXMLParser ce contine functii specifice parsarii de fisiere .xml, functii puse la dispozitie in pachetul SAX

Variabile

Agreement – vectorul in care retin valorile atributelor fiecarui tag in parte (codificate prin numele lor) din fisierele pe care se aplica invatarea;

Acc/rej/maybe/accpart/rejpart/none – numarul de taguri ce au ca valoare a atributului “Agreement” Accept/Reject/Maybe/Accept Part/Reject Part/None;

M – matricea HMM. Este matricea de precedente in care voi retine probabilitatile de aparitie a fiecaror bigrame posibile. Valorile atributelor sunt codificate numeric pentru a putea fi retinute in matrice astfel: Accept Part=0; Reject Part=1; Accept=2; Reject=3; Maybe=4; None=5.

Tablou – tabloul in care retin probabilitatile de aparitie a fiecaror trigrame posibile. Valorile atributelor sunt codificate la fel ca la matricea HMM.

Pa/pr/pm/papart/prpart/pn – procentele de aparitie a valorilor atributelor;

Functii

count(int nr_fis)

Prezentare: Aceasta functie va prelua fisierele de intrare si pentru fiecare tag in parte din fisierele de intrare, va apela o alta functie specifica SAXParser.

Functionare: Se formeaza numele fisierului din care se va citi astfel: adnotat+nr_fis+.xml. Apoi se deschide acest fisier si se lanseaza un parser pentru el. Acest parser va lansa functia specifica deschiderii unui tag.

startElement(namespace, localname, type, attributes) throws SAXException

Prezentare: Functia numara tagurile ce au o anumita valoare a atributului Agreement si apoi pune valorile intalnite intr-un vector pentru a putea fi prelucrate.

Functionare: Aceasta functie va fi apelata ori de cate ori se va deschide un tag in fisierul .xml pe care se face invatarea. Ea are rolul de a numara valorile de fiecare tip ale atributului Agreement, precum si salvarea lor in vectorul Agreement. Pentru aceasta, mai intai se verifica daca tagul deschis este cel de utterance (deoarece atributul Agreement nu se gaseste decat in taguri de tipul utterance), iar apoi se compara pe rand valoarea gasita cu “Accept Part”/”Reject Part”/ “Accept”/”Reject”/”Maybe”/”None” , incrementadu-se numarul valorii cu care coincide. Totodata, aceasta valoare ce a fost gasita va fi introdusa in vectorul de Agreement pentru a putea fi utilizata ulterior.

calculProcente()

Prezentare: Functia calculeaza procentele de aparitie a fiecarei valori in parte a atributului Agreement.

Functionare: Functia imparte numarul de atribute din fiecare tip in parte la numarul total de atribute, calculand astfel procentul de aparitie al fiecarui atribut in parte.

calcPrecedente()

Prezentare: Functia genereaza matricea HMM nenormalizata (calculeaza numarul de bigrame de fiecare tip gasite in text).

Functionare: Initial se determina tipul primei valori a atributului Agreement din text, dupa care, pentru fiecare tag in parte, se determina tipul valorii atributului si se incrementeaza valoarea matricei de precedente (m) pe linia corespunzatoare valorii anterioare si coloana corespunzatoare valorii curente a atributului Agreement.

calcPrecedente2()

Prezentare: Functia calculeaza numarul de trigrame de fiecare tip identificate in text.

Functionare: Functia este similara functiei calcPrecedente(). Initial se determina tipul primelor 2 valori ale atributului Agreement din text, dupa care, pentru fiecare tag in parte, se determina tipul valorii atributului si se incrementeaza valoarea tabloului de precedente (tablou) la indicii corespunzatori penultimei valori, ultimei valori si valorii curente a atributului Agreement.

printMatrix(out)/printTablou(out) throws IOException

Prezentare: Functiile scriu in fisierul de iesire primit ca parametru matricea/tabloul de precedente.

b) Fisierul Smooth.java

Variabile

Limita –valoarea dincolo de care nu se mai calculeaza netezirea;

Val – reprezinta valoarea maxima la care s-a ajuns in vectorii valori si nr_val;

Total – numarul total de taguri;

Agreement – vectorul in care retin de cate ori s-a intalnit fiecare valoare a atributului Agreement in parte;

Mat – matricea in care retin matricea HMM primita la intrare si pe care trebuie sa o netezesc;

Valori – vector in care retin toate valorile intalnite in matricea HMM;

Nr_val – vector in care retin frecventa cu care au fost gasite valorile ce au fost retinute in vectorul valori;

Rstar – vector in care retin procentele r* din formule;

Dr – vectorul de coeficienti dr din formule;

P_tilda – matricea HMM netezita;

Alfa – vectorul in care retin coeficietnii alfa(w1) din formule;

Functii

Smooth()

Prezentare: Functia realizeaza netezirea matricei HMM prin algoritmul lui Katz.

Functionare: Netezirea matricei HMM are mai multe etape.

In primul etapa, se cauta in matricea HMM valorile nenule si se adauga in vectorul valori, in acelasi timp actualizandu-se in vectorul nr_val de cate ori a fost gasita fiecare valoare. Cei doi vectori sunt neordonati, primul reprezentand un fel de pointer pentru al doilea.

In cea de-a doua etapa se calculeaza rstar astfel: pentru fiecare valoare din vectorul de valori, daca valoarea este mai mare ca limita impusa, atunci valoarea va fi copiata in vectorul de valori. Altfel, se cauta in vectorul de valori valoarea imediat urmatoare celei curente si se determina indexul acesteia. Pe baza indexului se determina frecventa acelei valori (din vectorul nr_val), iar pe baza acesteia se calculeaza valoarea corespunzatoare a vectorului rstar. Daca valoarea cautata nu se gaseste in vectorul de valori, atunci rstar va lua valoarea 0.

In continuare trebuie calculat dr. Pentru aceasta se calculeaza constanta ce intervine in calculul lui dr ( (limita-1)*n(limita+1)/n1 ) astfel: se cauta in vectorul de valori valoarea (limita+1). Daca nu este gasita aceasta valoare, atunci constanta va fi egala cu 0. In cazul in care aceasta valoare este gasita, se procedeaza ca la calculul lui rstar. Se retine indicele in vectorul valori si pe baza acestuia, se determina frecventa valorii (limita +1) din vectorul nr_val. In continuare se cauta in vectorul de valori valoarea 1. Daca ea nu este gasita, atunci vectorul dr va lua tot timpul valoarea 1. Daca e gasita, atunci se determina pe ce pozitie avem aceasta valoare si pe baza pozitiei, determinam frecventa ei din vectorul nr_val. In acest moment avem toate datele necesare pentru a calcula constanta. Dupa calculul acesteia, se calculeaza valorile vectorului dr pentru fiecare valoare din vectorul valori.

In continuare se calculeaza prima forma a matricei netezite p_tilda astfel: daca valoarea din matricea HMM este mai mare decat limita impusa, atunci p_tilda pentru indicii corespunzatori va lua valoarea din matricea HMM normalizata. Daca nu, atunci valoarea normalizata din matricea HMM se inmulteste si cu valoarea vectorului dr corespunzatoare.

In continuare se calculeaza vectorul de coeficienti alfa, necesari in ultima faza a algoritmului. Pentru aceasta, se ia fiecare valoare V1 a atributului Agreement in parte si, pentru fiecare valoare V2 a aceluiasi atribut, se calculeaza sumele de procente s1=sum( p(V2) ) respectiv s2=sum( p_tilda(V2,V1) ) pentru care HMM(V1,V2) > 0. Dupa ce s-au calculat aceste sume, se pot calcula valorile vectorului alfa ca fiind (1-s2)/(1-s1).

In sfarsit, ultimul pas al algoritmului este reprezentat de eliminarea zerourilor din matricea netezita. Aceasta se face astfel: daca se gaseste 0 in matricea netezita (p_tilda), atunci se actualizeaza aceasta valoare cu produsul dintre valoarea din vectorul alfa care ii corespunde coloanei si procentul de aparitie al valorii corespunzatoare liniei pe care a fost gasita valoarea 0 in matricea p_tilda.

printSmooth(out) throws IOException

Prezentare: Functia scrie matricea HMM netezita in fisierul de iesire, tinand cont si de formatul matricei HMM, pentru ca cele doua fisiere sa se potriveasca si sa poata folosi oricare dintre ele mai departe (la partea de recunoastere).

Exemplu

In continuare voi da un mic exemplu pentru a arata cum lucreaza algoritmul de netezire Katz

Pe o matrice ce necesita netezire. Fie matricea de 4*4 prezentata mai jos si limita dincolo de care nu mai calculez netezirea 3 (k=3):

1 0 3 2 agreement[0]=6

2 4 0 0 agreement[1]=6

1 2 0 3 agreement[2]=6

0 0 2 0 agreemet[3]=2

total=agreement[0]+agreement[1]+ agreement[2]+ agreement[3]=20

Algoritmul Katz lucreaza in mai multi pasi:

Se identifica valorile gasite in matrice si se consturiesc vectorii valori si nr_val

Initial cei 2 vectori sunt vizi

Incep parcurgerea matricei si de cate ori gasesc valori nenule incerc sa le aduag in vector, iar daca sunt, le incrementez numarul de aparitii:

Gasesc 1 valori [0]=1, nr_val[0]=1

Gasesc 0 nu se executa nimic

Gasesc 3 valori[1]=3, nr_val[1]=1

Gasesc 2 valori[2]=2, nr_val[2]=1

Gasesc 2 valori[2]=2, nr_val[2]=2

Gasesc 4 valori[3]=4, nr_val[3]=1

Gasesc 0 nu se executa nimic

Gasesc 0 nu se executa nimic

Gasesc 1 valori[0]=1, nr_val[0]=2

Gasesc 2 valori[2]=2, nr_val[2]=3

Gasesc 0 nu se executa nimic

Gasesc 3 valori[1]=3, nr_val[1]=2

Gasesc 0 nu se executa nimic

Gasesc 0 nu se executa nimic

Gasesc 2 valori[2]=2, nr_val[2]=4

Gasesc 0 nu se executa nimic

In acest moment avem valori[0]=1; valori[1]=3; valori[2]=2; valori[3]=4;

nr_val[0]=2; nr_val[1]=2; nr_val[2]=4; nr_val[3]=1.

Calculez r*

Pentru fiecare i de la 0 la 3

i=0

valori [0]<3

temp=1

valori[2]=temp+1=2

index=2

rstar[0]=2*4/2=4

i=1

valori [1]=3

temp=3

valori[3]=temp+1=4

index=3

rstar[1]=3*1/2=1.5

i=2

valori [2]<3

temp=2

valori[1]=temp+1=3

index=1

rstar[2]=3*2/4=1.5

i=3

valori [3]>3

rstar[3]=valori[3]=4

Am calculat r*: rstar[0]=4; rstar[1]=1.5; rstar[2]=1.5; rstar[3]=4.

Calculez constanta: (lim-1)*n[lim+1]/n[1] 2*valori[4] /nr_val[0]=0 const=0

Calculez dr: dr[0]=rstar[0]/valori[0]=4; dr[1]=0.5; dr[2]=0.75; dr[3]=1

Calculez p_tilda[i][j] cu i=0,3 si j=0,3

i=0

j=0

mat[0][0]=1<3

p_tilda[0][0]=mat[0][0]*dr[valori[1]]/agreement[0]=1/6

j=1

mat[0][1]=0<3

p_tilda[0][1]=mat[0][1]*dr[valori[0]]/agreement[0]=0

j=2

mat[0][2]=3=3

p_tilda[0][2]=mat[0][2]*dr[valori[3]]/agreement[0]=3/6=0.5

j=3

mat[0][3]=2<3

p_tilda[0][3]=mat[0][3]*dr[valori[2]]/agreement[0]=2*0.75/6

p_tilda[0][3]=0.25

i=1

j=0

mat[1][0]=2<3

p_tilda[1][0]=mat[1][0]*dr[valori[2]]/agreement[1]=2*0.75/6

p_tilda[1][0]=0.25

j=1

mat[1][1]=4>3

p_tilda[1][1]=mat[1][1]/agreement[1]=4/6=0.67

j=2

mat[1][2]=0<3

p_tilda[1][2]=mat[1][2]*dr[valori[3]]/agreement[1]=0

j=3

mat[1][3]=0<3

p_tilda[1][3]=mat[1][3]*dr[valori[2]]/agreement[1]=0

i=2

j=0

mat[2][0]=1<3

p_tilda[2][0]=mat[2][0]*dr[valori[1]]/agreement[2]=1/6

j=1

mat[2][1]=2<3

p_tilda[2][1]=mat[2][1]*dr[valori[2]]/agreement[2]=2*0.75/6

p_tilda[2][1]=0.25

j=2

mat[2][2]=0<3

p_tilda[2][2]=mat[2][2]*dr[valori[3]]/agreement[2]=0

j=3

mat[2][3]=3=3

p_tilda[2][3]=mat[2][3]*dr[valori[3]]/agreement[2]=3/6=0.5

i=3

j=0

mat[3][0]=0<3

p_tilda[3][0]=mat[3][0]*dr[valori[1]]/agreement[3]=0

j=1

mat[3][1]=0<3

p_tilda[3][1]=mat[3][1]*dr[valori[0]]/agreement[3]=0

j=2

mat[3][2]=2<3

p_tilda[3][2]=mat[3][2]*dr[valori[2]]/agreement[3]=2*0.75/2

p_tilda[3][2]=0.75

j=3

mat[3][3]=0<3

p_tilda[3][3]=mat[3][3]*dr[valori[2]]/agreement[3]=0

Calculez alfa[i][j] cu i=0,3 si j=0,3

i=0

j=0

mat[0][0]=1>0

s1+=agreement[0]/total=6/20

s2+=p_tilda[0][0]=1/6

j=1

mat[0][1]=0

j=2

mat[0][2]=3>0

s1+=agreement[2]/total=6/20+6/20=12/20

s2+=p_tilda[2][0]=1/6+1/6=1/3

j=3

mat[0][3]=2>0

s1+=agreement[3]/total=14/20=0.7

s2+=p_tilda[3][0]=1/3

alfa[0]=(1-s2)/(1-s1)=2/3/0.3=2.22

i=1

j=0

mat[1][0]=2>0

s1=agreement[0]/total=6/20

s2=p_tilda[1][1]=0.67

j=1

mat[1][1]=4>0

s1+=agreement[1]/total=6/20+6/20=12/20=0.6

s2+=p_tilda[2][1]=0.67+0.25=0.92

j=2

mat[1][2]=0

j=3

mat[1][3]=0

alfa[1]=(1-s2)/(1-s1)=0.08/0.4=0.2

i=2

j=0

mat[2][0]=1>0

s1+=agreement[0]/total=6/20

s2+=p_tilda[0][2]=0.5

j=1

mat[2][1]=2>0

s1+=agreement[2]/total=6/20+6/20=12/20

s2+=p_tilda[1][2]=0.5+0=0.5

j=2

mat[2][2]=0

j=3

mat[2][3]=3>0

s1+=agreement[3]/total=14/20=0.7

s2+=p_tilda[3][2]=0.5+0.75=1.25

alfa[2]=(1-s2)/(1-s1)=-0.25/0.3=-0.83

i=3

j=0

mat[3][0]= 0

j=1

mat[3][1]=0

j=2

mat[3][2]=2>0

s1=agreement[2]/total=6/20=0.3

s2=p_tilda[2][3]=0.5

j=3

mat[3][3]=0

alfa[3]=(1-s2)/(1-s1)=0.5/0.7=0.71

Calculez forma finala a lui p~. Caut valorile nule din matricea p~

i=0 j=1

p_tilda[0][1]=alfa[1]*agreement[0]/total=0.2*6/20=0.06

i=1 j=2

p_tilda[1][2]=alfa[2]*agreement[1]/total=0.83*6/20=0.249

i=1 j=3

p_tilda[1][3]=alfa[3]*agreement[1]/total=0.71*6/20=0.213

i=2 j=2

p_tilda[2][2]=alfa[2]*agreement[2]/total=0.83*6/20=0.249

i=3 j=0

p_tilda[3][0]=alfa[0]*agreement[3]/total=2.22*2/20=0.222

i=3 j=1

p_tilda[0][1]=alfa[1]*agreement[3]/total=0.2*2/20=0.02

i=3 j=3

p_tilda[0][1]=alfa[3]*agreement[3]/total=0.71*2/20=0.071

Si astfel matricea netezita va arata in felul urmator:

0.166 0.06 0.5 0.25

0.25 0.67 0.249 0.213

0.166 0.25 0.249 0.5

0.222 0.02 0.75 0.071

7.4 Pasul 4 – Recunoastere

Pseudocodul

Recunoastere(fisier_1, fisier_2, fisier_3, fisier_4)

citire(fisier_1,fisier_2,fisier_3)

Se salveaza numarul de taguri(nr)

Se salveaza vectorul de taguri (tags)

Se salveaza matricea de tranzitii (tr)

Se aplica algoritmul Viterbi(nr, tags,6,tr)

Se determina probabilitatea cu care s-a facut adnotarea

Se afiseaza rezultatele

citire(fisier_1,fisier_2,fisier_3)

Se deschid cele 3 fisiere

Din primul fisier se citesc cuvintele-cheie ce vor fi cautate in textul neadnotat si care dau probabilitatea ca un enunt sa aiba un atribut de un anumit tip astfel:

Se citeste cate o linie din fisier

Daca s-a gasit caracterul ‘/’

Atunci s-a terminat un cuvant-cheie si se adauga in vectorul de cuvinte-cheie corespunzator atributului respectiv

Din al doilea fisier se citeste matricea de precedente (HMM)

Din al treilea fisier se citeste textul neadnotat

Pentru fiecare tag in parte

Pentru fiecare atribut in parte

Pentru fiecare cuvant-cheie din vectorul atributului corespunzator

Cauta in text cuvantul respectiv

Daca e gasit cuvantul-cheie

Atunci se cauta cuvantul “not”

Daca se gaseste cuvantul not

Atunci marcheaza tagul ca fiind de tipul atribut negat

Altfel marcheaza tagul ca fiind de tipul atribut

Daca nu s-a marcat tagul inca

Atunci marcheaza tagul ca fiind “none”

Copiaza ultimul tag ca sa mearga algoritmul Viterbi

Inchide fisierele deschise

Viterbi(numar_taguri, tag, numar_stari, matricea de tranzitii) returneaza calea_optima

Creeaza matricea viterbi[nr_stari+2][nr_tranzitii+2]

Creeaza matricea de trace back[nr_stari+2][nr_tranzitii+2]

Creeaza vectorul rezultat

Initializeaza viterbi[0][0]=1

Pentru fiecare tag t in parte

Pentru fiecare stare s in parte

Pentru fiecare tranzitie s->s’ in parte

Daca tagul corespunde cu s’

Atunci calculeaza scor

Altfel scor=0

Daca (viterbi[s’][tag+1]==0 || scor>viterbi[s’][tag+1]==0)

Atunci

viterbi[s’][tag+1]=scor

back[s’][tag+1]=s

Determina valoarea viterbi[stare][numar_taguri] care este maxima si retine starea in index_max si valoarea viterbi[stare][numar_taguri] in probabilitate_max

Scrie in vectorul rezultat: rezultat[numar_taguri-1]=index_max

Pentru fiecare tag in parte luate in ordine inversa

rezultat[tag-2]=back[index_max][tag]

Intoarce rezultat

Scriere(tags, fisier_1, fisier_2)

Se deschid cele 2 fisiere

Se citeste din fisierul fisier_1 cate o linie

Pentru fiecare tag ce se deschide

Se initializeaza valoarea atributului “Agreement” cu valoarea corespunzatoare din vectorul de taguri (tags)

Se scrie in fisierul fisier_2 ceea ce s-a citit din fisierul fisier_1 (cu modificarea facuta anterior asupra valorii atributului “Agreement”)

Se inchid fisierele deschise

Modalitatea de executie

Compilare: javac Recunoastere/*.java

Executie efectiva: java Recunoastere.Recunoastere fisier_1 fisier_2 fisier_3 fisier_4

Semnificatia parametrilor dati la executie este:

Fisier_1 – e fisierul din care se vor citi cuvintele-cheie ce vor fi cautate in textul neadnotat.

Fisier_2 – este fisierul in care se va gasi matricea HMM (in forma normala sau in forma netezita).

Fisier_3 – este fisierul .xml neadnotat si care va fi adnotat automat.

Fisier_4 – este fisierul .xml adnotat automat.

Prezentarea principalelor functii si variabile din program

Fisierul Citire.java

Variabile

Nr_tag – variabila in care retin numarul tagului curent;

Checked – variabila in care retin daca s-a stabilit sau nu valoarea probabila a atributului Agreement pentru tagul curent. Daca este 0 inseamna ca nu s-a stabilit valoarea probabila, iar daca e 1, inseamna ca s-a stabilit valoarea probabila a atributului tagului respectiv;

Tag – vector in care retin probabilitatile tagurilor de a avea valoarea atributului Agreement Accept Part/Reject Part/Accept/Reject/Maybe/None;

Tranzitii – matricea HMM citita din fisier (poate fi matricea HMM normala sau netezita);

Acc – vectorul de cuvinte-cheie pentru valoarea Accept a atributului Agreement;

Rej – vectorul de cuvinte-cheie pentru valoarea Reject a atributului Agreement;

Maybe – vectorul de cuvinte-cheie pentru valoarea Maybe a atributului Agreement;

Functii

Citire(fisier_1, fisier_2, fisier_3) throws IOException

Prezentare: Functia realizeaza citirile din fisierele de intrare. Se vor citi cuvintele-cheie din primul fisier, matricea HMM (normala sau netezita) din cel de-al doilea fisier, iar din cel de-al treilea fisier se va citi textul neadnotat si care va fi adnotat automat de program.

Functionare: Functia are 3 parti.

In prima parte, se citesc cuvintele-cheie din programul primit la intrare (fisier_1). Acest fisier trebuie sa aiba un format specific: cuvintele-cheie pentru fiecare valoare a atributului Agreement in parte vor fi separate intre ele prin ‘/’ si vor fi scrise pe un singur rand. Cuvintele ce corespund la 2 valori diferite sunt despartite intre ele prin caracterul “\n”. In continuare voi prezenta fisierul “cue1.txt” pentru o mai buna intelegere:

ok/ok,/ok./ok / ok/ye!/ye./yeap/yes/yup/right/yeah/ya/okay/true/exactly/alright/probably/agree/sure

no/nope/nop/no /don't want/disagree/don't think/nah/no,/not

maybe/don't know/guess/whatever

Citirea se face in felul urmator: se citeste cate o linie din fisierul de intrare si apoi se parseaza acea linie. In momentul in care s-a gasit caracterul ‘/’ inseamna ca am terminat de citit un cuvant-cheie si in acest caz il adaug in vectorul de cuvinte-cheie corespunzator. Pentru a ne da seama care este vectorul in care trebuie sa adaug cuvintele-cheie, folosesc un contor al liniilor citite care se incrementeaza dupa fiecare linie. In functie de acest contor, stabilesc in ce vector adaug cuvintele-cheie.

In cea de-a doua parte, se citeste matricea HMM normala sau netezita din fisierul fisier_2.

In cea de-a treia parte, se citeste textul neadnotat si se incearca stabilirea valorii atributului Agreement pe baza cuvintelor-cheie citite din fisierul fisier_1. Pentru aceasta, se citeste continutul fiecarui tag, iar apoi in textul citit se incepe cautarea cuvintelor-cheie astfel: mai intai caut cuvintele-cheie din vectorul Maybe. Daca a fost identificat vre-un cuvant-cheie, se continua parsarea cu cautarea cuvantului “not” pentru a ne da seama daca avem cumva o respingere partiala. Daca nu s-a gasit acest cuvant, se stabileste valoarea atributului ca fiind Maybe. Daca s-a gasit cuvantul “not”, valoarea tagului va fi Reject Part. Daca nu s-a identificat nici un cuvant-cheie din acest vector, se trece la cautarea cuvintelor-cheie din vectorul Acc, iar apoi la cele din vectorul Rej. Daca se identifica vre-un cuvant-cheie in text, se continua parsarea cu cautarea cuvantului “but” pentru a ne da seama daca avem o acceptare/respingere totala sau doar partiala. Daca nu se gaseste cuvantul, se stabileste valoarea atributului la Accept/Reject in functie de vectorul din care face parte cuvantul-cheie ce a fost gasit. Daca s-a gasit cuvantul “but”, se va stabili valoarea Accept Part/Reject Part pe aceleasi principii ca mai sus. Daca nu s-a gasit nici un cuvant-cheie din nici un vector, atunci tagul va fi etichetat ca avand valoarea None.

Dupa ce s-a stabilit valoarea fiecarui tag in parte, aceste valori se trec in vectorul tag la indicele nr_tag si apoi se incrementeaza acest indice. La sfarsit, ultima valoare se mai copiaza o data pentru ca in continuare sa se poata aplica algoritmul Viterbi.

Fisierul Viterbi.java

Variabile

Prob_finala – in aceasta variabila se retine probabilitatea cu care s-a realizat adnotarea automata a fisierului de intrare

Functii

Viterbi(nr_tag, tag, nr_stari, tranzitii) returns cale

Prezentare: Functia primeste la intrare insiruirea probabila a valorilor atributului Agreement si matricea HMM (normala sau netezita) si va returna insiruirea tagurilor conform relatiilor de precedenta retinute in matricea HMM si determinate pe baza algoritmului de programare dinamica Viterbi.

Functionare: Functia are mai multi pasi.

Initial se construiesc matricele viterbi si back si vectorul rezultat. In matricea viterbi vom avea pe coloane probabilitatea fiecarei replici de a avea oricare dintre cele 6 valori posibile. Totdeauna probabilitatile replicii curente de a avea una din valori vor fi stabilite in functie de probabilitatile replicii anterioare. In matricea back vom avea pointerii catre tipul replicii anterioare celei curente pentru a putea face legatura intre tagul curent si cel anterior, deoarece rezultatele algoritmului Viterbi vor fi obtinute pe cale inversa, incepand cu ultimul tag.

Apoi se initializeaza valoarea matricei viterbi[0][0] cu valoarea 1 si se porneste algoritmul. Pentru fiecare tag in parte, pentru fiecare valoare posibila a atributului Agreement, pentru fiecare tranzitie posibila de la valoarea respectiva, se calculeaza un scor (adica o probabilitate ca tagul curent sa aiba valoarea data de tranzitia respectiva pornind de la starea anterioara). Daca scorul astfel calculat este mai mare ca cel anterior, sau daca cel anterior calculat a fost 0, atunci se actualizeaza matricele viterbi si back.

Dupa ce s-au terminat de completat cele doua matrice, se cauta in matricea viterbi, pe ultima coloana, valoarea maxima si apoi se incepe completarea rezultatului. Pe ultima pozitie a rezultatului se va pune valoarea atributului care a maximizat valoarea de pe ultima coloana a matricei viterbi. In continuare, vectorul rezultat se va completa pe baza matricei back (in care sunt salvate valorile atributelor pentru fiecare tag in parte) tot in ordine inversa.

Dupa ce s-a terminat de initializat vectorul rezultat, acesta este intors la iesire.

Fisierul Scriere.java

Functii

Scriere(vect, fisier_1, fisier_2)

Prezentare: Functia citeste textul din fisierul de intrare neadnotat (fisier_1) si il scrie in fisierul de iesire (fisier_2) completand totodata valoarea atributului Agreement pe baza valorilor citite din vectorul vect.

Functionare: Functia citeste cate o linie din fisierul de intrare si cauta sa vada daca este linia care deschide tagul utterance (deoarece numai in acel tag se gaseste atributul Agreement). Daca nu, atunci linia este scrisa la iesire asa cum este ea, deoarece nu are nevoie de nici o schimbare. Daca linia citita este cea care contine tagul de deschidere pentru utterance, atunci se cauta locul in care se deschide atributul Agreement si acolo se introduce valoarea citita din vectorul vect, dar decodificata. Aceasta inseamna ca daca in vector se gaseste valoarea 0, in fisier se scrie Accept Part, daca se gaseste valoarea 1, se scrie Reject Part, daca se gaseste valoarea 2, se scrie Accept, daca se gaseste valoarea 3, se scrie Reject, daca se gaseste valoarea 4, se scrie Maybe, iar daca se gaseste valoarea 5, in fisier se va scrie None. Dupa ce a fost scrisa valoarea atributului Agreement al tagului respectiv, se va scrie in fisier continuarea tagului asa cum era ea in fisierul initial.

Exemplu

In continuare voi da un mic exemplu pentru a arata cum lucreaza algoritmul viterbi.

Sa presupunem ca avem un text cu 4 taguri (nr_tag=4). Dupa ce s-au cautat cuvintele-cheie, sa presupunem ca vectorul de taguri e de forma : T1-None; T2-None; T3-Accept; T4- -None. Conform codificarii impuse, vom avea: b[0]=5, b[1]=5, b[2]=2, b[3]=5. Numarul de stari este 6 (Accept Part, Reject Part, Accept, Reject, Maybe, None). Sa presupunem ca matricea de tranzitii (HMM) arata in felul urmator si se va numi matricea a:

AcceptPart RejectPart Accept Reject Maybe None

AcceptPart 0.0 0.0 0.25 0.0 0.0 0.75

RejectPart 0.0 0.0 0.0 0.0 0.0 1.0

Accept 0.007 0.0 0.255 0.012 0.0127 0.710

Reject 0.0 0.0 0.211 0.154 0.0 0.633

Maybe 0.0 0.0 0.222 0.037 0.037 0.703

None 0.002 5.75E-4 0.154 0.031 0.012 0.798

In acest moment avem toate elementele pentru a putea aplica algoritmul Viterbi:

Creez matricea vit[8+2][6+2] vit[10][8]

vit[0][0]=1

Incep buclele: tag=0,3; s=0,5; s’=0,5

tag=0

s=0

s’=0

b[0]=5 b’[0]=0

scor=vit[0][0]*a[0][0]*b’[0]=0

vit[0][1]=0 vit[0][1]=scor=0

back[0][1]=s=0

Similar s’=1, s’=2, s’=3, s’=4

vit[s’][1]=scor=0

back[s’][1]=s=0

s’=5

b[0]=5 b’[5]=1

scor=vit[0][0]*a[0][5]*b’[5]=1*0.75*1=0.75

vit[5][1]=0 vit[5][1]=scor=0.75

back[5][1]=s=0

s=1

s’=0

b[0]=5 b’[0]=0

scor=vit[1][0]*a[1][0]*b’[0]=0

vit[0][1]=0 vit[0][1]=scor=0

back[0][1]=s=1

Similar s’=1, s’=2, s’=3, s’=4

vit[s’][1]=scor=0

back[s’][1]=s=1

s’=5

b[0]=5 b’[5]=1

scor=vit[1][0]*a[1][5]*b’[5]=0

vit[5][1]!=0 && vit[5][1]>scor nu se executa nimic

Similar pentru s=2, s=3, s=4 si s=5. Voi prezenta doar ultima forma:

s=5

s’=0

b[0]=5 b’[0]=0

scor=vit[5][0]*a[5][0]*b’[0]=0

vit[0][1]=0 vit[0][1]=scor=0

back[0][1]=s=5

Similar s’=1, s’=2, s’=3, s’=4

vit[s’][1]=scor=0

back[s’][1]=s=5

s’=5

b[0]=5 b’[5]=1

scor=vit[5][0]*a[5][5]*b’[5]=0

vit[5][1]!=0 && vit[5][1]>scor nu se executa nimic

tag=1

s=0

s’=0

b[0]=5 b’[0]=0

scor=vit[0][1]*a[0][0]*b’[0]=0

vit[0][2]=0 vit[0][2]=scor=0

back[0][2]=s=0

Similar pentru s’=1, s’=2, s’=3, s’=4, s’=5

vit[s’][2]=scor=0

back[s’][2]=s=0

Similar pentru s=1, s=2, s=3, s=4 si pentru s’=0, s’=1, s’=2, s’=3, s’=4, s’=5

vit[s’][2]=scor=0

back[s’][2]=s

s=5

s’=0

b[0]=5 b’[0]=0

scor=vit[5][1]*a[5][0]*b’[0]=0

vit[0][2]=0 vit[0][2]=scor=0

back[0][2]=s=5

Similar pentru s’=1, s’=2, s’=3, s’=4

vit[s’][2]=scor=0

back[s’][2]=s=5

s’=5

b[0]=5 b’[5]=1

scor=vit[5][1]*a[5][5]*b’[5]=0.75*0.79=0.59

vit[5][2]=0 vit[5][2]=0.59

back[5][2]=5

tag=2

s=0

s’=0

b[0]=2 b’[0]=0

scor=vit[0][2]*a[0][0]*b’[0]=0

vit[0][3]=0 vit[0][3]=scor=0

back[0][3]=s=0

Similar pentru s’=1, s’=2, s’=3, s’=4’s’=5

vit[s’][3]=scor=0

back[s’][3]=s=0

Similar pentru s=1, s=2, s=3, s=4 si pentru s’=0, s’=1, s’=2, s’=3, s’=4, s’=5

vit[s’][3]=scor=0

back[s’][3]=s

s=5

s’=0

b[0]=2 b’[0]=0

scor=vit[5][2]*a[5][0]*b’[0]=0

vit[0][3]=0 vit[0][3]=scor=0

back[0][3]=s=5

Similar pentru s’=1

vit[1][3]=scor=0

back[1][3]=s=5

s’=2

b[0]=2 b’[2]=1

scor=vit[5][2]*a[5][2]*b’[2]=0.59*0.15*1=0.08

vit[2][3]=0 vit[2][3]=scor=0.08

back[2][3]=s=5

s’=3

b[0]=2 b’[3]=0

scor=vit[5][2]*a[5][3]*b’[3]=0

vit[3][3]=0 vit[3][3]=0

back[3][3]=s=5

Similar pentru s’=4, s’=5

vit[s’][3]=scor=0

back[s’][3]=s=5

tag=3

s=0

s’=0

b[0]=5 b’[0]=0

scor=vit[0][3]*a[0][0]*b’[0]=0

vit[0][4]=0 vit[0][4]=scor=0

back[0][4]=s=0

Similar pentru s’=1, s’=2, s’=3, s’=4, s’=5

vit[s’][4]=scor=0

back[s’][4]=s=0

Similar pentru s=1 pentru s’=0, s’=1, s’=2, s’=3, s’=4, s’=5

vit[s’][2]=scor=0

back[s’][2]=1

s=2

s’=0

b[0]=5 b’[0]=0

scor=vit[2][3]*a[2][0]*b’[0]=0

vit[0][4]=0 vit[0][4]=scor=0

back[0][4]=s=2

Similar pentru s’=1, s’=2, s’=3, s’=4

vit[s’][4]=scor=0

back[s’][4]=s=2

s’=5

b[0]=5 b’[5]=1

scor=vit[2][3]*a[2][5]*b’[5]=0.08*0.71=0.056

vit[5][4]=0 vit[5][4]=0.056

back[5][4]=2

s=3

s’=0

b[0]=5 b’[0]=0

scor=vit[3][3]*a[3][0]*b’[0]=0

vit[0][4]=0 vit[0][4]=scor=0

back[0][4]=s=3

Similar pentru s’=1, s’=2, s’=3, s’=4

vit[s’][4]=scor=0

back[s’][4]=s=3

s’=5

b[0]=5 b’[5]=1

scor=vit[3][3]*a[3][5]*b’[5]=0

vit[5][4]>scor=0 nu se executa nimic

Similar pentru s=4 si s=5 si pentru s’=0, s’=1, s’=2, s’=3, s’=4

vit[s’][4]=scor=0

back[s’][4]=s

s’=5

b[0]=5 b’[5]=1

scor=vit[s][3]*a[s][5]*b’[5]=0

vit[5][4]>scor=0 nu se executa nimic

In acest moment s-a terminat algoritmul si trebuie sa vedem care este calea cea mai buna si care este probabilitatea cu care s-a facut recunoasterea. Pentru aceasta, ne uitam pe ultima coloana din matricea viterbi pentru a determina valoarea maxima. In matricea vit avem: vit[0][4]=0, vit[1][4]=0, vit[2][4]=0, vit[3][4]=0, vit[4][4]=0, vit[5][4]=0.056. Se observa ca valoarea maxima de pe aceasta linie este 0.056. Aceasta este probabilitatea cu care s-a facut recunoasterea. Uitandu-ne pe ce linie a fost gasita valoarea maxima, se obtine valoarea ultimului tag. Deci, ultimul tag va avea valoarea “None” pentru ca e pe linia a 6-a. In continuare ne uitam in matricea back la indicii corespunzatori valorii maxime de pe ultima coloana a matricei viterbi. Deci back[5][4]=2, insemna ca tipul tagului penultim (adica al 3-lea) este “Accept” pentru ca e pe linia a 3-a. In continuare ne uitam pe coloana imediat inferioara (penultima din matricea back) si pe linia a 3-a (data de back[5][4]). Aici se gaseste valoarea 5, deci tagul al 2-lea are valoarea “None”. In continuare ne uitam pe coloana anterioara acestei coloane si pe linia a 5-a si gasim iarasi valoarea 5. In concluzie, am determinat si primul tag ca fiind de tip “None”. In acest moment s-a terminat recunoasterea tagurilor. Deci s-a termiant si algoritmul, calea optima fiind: “None”, “None”, “Accept”, “None” si a fost recunoscuta cu probabilitatea 0.056.

7.5 Pasul 5 – Statistica

Pseudocodul

Statistica(fisier_1, fisier_2, fisier_3)

Se deschid cele 3 fisiere

Se citeste din primele doua fisiere informatia (fisier_1 si fisier_2)

Se face compararea rezultatelor

Se afiseaza rezultatele in fisierul fisier_3

Se inchid cele 3 fisiere

Citire(fisier)

Pentru fiecare tag deschis executa

startElement(nume, locatie, tip, atribute)

startElement(nume, locatie, tip, atribute)

In functie de valoarea atributului incrementeaza numarul atributelor de acel tip

Adauga atributul in vectorul de atribute

Comp()

Preia vectorii de atribute al celor doua fisiere ce se compara

Pentru fiecare element din cei 2 vectori executa

Compara elementele aflate in cei 2 vectori pe aceeasi pozitie

Daca cele doua elemente coincid

Atunci

Incrementeaza numarul valorilor atributelor identificate corect

In functie de valoarea atributului identificat incrementeaza numarul valorilor atributelor de acel tip identificate corect

Calculeaza procentul de valori ale atributelor identificate corect din numarul total de valori ale atributelor

Calculeaza procentul de valori ale atributelor din fiecare tip in parte identificate corect din numarul total de valori ale atributelor identificate corect

Modalitatea de executie

Compilare: javac Statistica/*.java

Executie efectiva: java Statistica.Statistica fisier_1 fisier_2 fisier_3

Semnificatia parametrilor dati la executie este:

Fisier_1 – este fisierul adnotat manual;

Fisier_2 – este fisierul adnotat automat;

Fisier_3 – este fisierul rezultat in care se vor afisa rezultatele comparatiei dintre celelalte doua fisiere primite ca parametri. In acest fisier vor fi rezultatele finale ce dau eficienta aplicatiei.

Prezentarea principalelor functii si variabile din program

Fisierul Citire.java

Variabile

Agreement – vectorul in care retin valorile atributelor fiecarui tag in parte (codificate prin numele lor) din fisierele pe care se aplica invatarea;

Acc/rej/maybe/accpart/rejpart/none – numarul de taguri ce au ca valoare a atributului “Agreement” Accept/Reject/Maybe/Accept Part/Reject Part/None;

Functii

count(fisier)

Prezentare: Aceasta functie va prelua fisierul de intrare (care are un format .xml) si pentru fiecare tag in parte din fisier, va apela o alta functie specifica SAXParser.

Functionare: Se deschide fisierul si se lanseaza un parser pentru el. Acest parser va lansa functia specifica deschiderii unui tag.

startElement(namespace, localname, type, attributes) throws SAXException

Prezentare: Functia numara tagurile ce au o anumita valoare a atributului Agreement si apoi pune valorile intalnite intr-un vector pentru a putea fi prelucrate.

Functionare: Aceasta functie va fi apelata ori de cate ori se va deschide un tag in fisierul .xml de la intrare. Ea are rolul de a numara valorile de fiecare tip ale atributului Agreement, precum si salvarea lor in vectorul Agreement. Pentru aceasta, mai intai se verifica daca tagul deschis este cel de utterance (deoarece atributul Agreement nu se gaseste decat in taguri de tipul utterance), iar apoi se compara pe rand valoarea gasita cu Accept Part/Reject Part/ Accept/Reject/Maybe/None , incrementadu-se numarul valorii cu care coincide. Totodata, aceasta valoare ce a fost gasita va fi introdusa in vectorul de Agreement pentru a putea fi utilizata ulterior.

Fisierul Comparare.java

Variabile

V1 – vectorul de valori ale atributului Agreement din fisierul adnotat manual;

V2 – vectorul de valori ale atributului Agreement din fisierul adnotat automat;

Lung – lungimea celor doi vectori;

Corect – numarul de taguri ce au fost identificate corect;

Acc/rej/maybe/accpart/rejpart/none – numarul de taguri ce sunt identificate corect corespunzatoare fiecarei valori a atributului “Agreement” in parte (Accept/Reject/Maybe/Accept Part/Reject Part/None);

Pcorecte – procentul tagurilor identificate corect din numarul total de taguri;

pa/pr/pm/papart/parpart/pn – procentele cu care au fost identificate corect valorile atributului Agreement (Accept/Reject/Maybe/Accept Part/Reject Part/None) din numarul total de taguri identificate corect;

Functii

comp()

Prezentare: Aceasta functie ia cei doi vectori de valori ale atributului Agreement corespunzatori celor doua fisiere adnotate si ii compara, calculand procentele cu care au fost identificate corect valorile tagurilor.

Functionare: Pentru fiecare indice in parte de la 0 si pana la lung, se compara valorile aflate la indicele respectiv in cei doi vectori si, daca coincid, atunci se incrementeaza numarul de taguri corect identificate. Totodata, se determina valoarea atributului ce a fost identificata corect si se incrementeaza contorul corespunzator. La sfarsit se calculeaza procentele de taguri corect identificate prin impartirea numarului de taguri identificate corect la numarul de taguri total (lung). Apoi se calculeaza procentele de taguri corect identificate din fiecare tip in parte prin impartirea numarului de taguri corect identificate din acel tip la numarul total de taguri identificate corect si se salveaza rezultatele obtinute in variabilele globale.

Capitolul 8. Rularea aplicatiei

8.1 Linux

Exista un fisier numit makefile in care sunt date toate comenzile necesare. Initial trebuie facuta compilarea surselor, iar dupa aceea, rularea lor intr-o anumita ordine. In continuare voi prezenta fisierul makefile:

compile:

javac Adnotare/*.java

javac Invatare/*.java

javac Recunoastere/*.java

javac Statistica/*.java

run-adnotare:

java Adnotare.Adnotare 1 powwow1.htm temp.txt powow1.xml

java Adnotare.Adnotare 1 powwow2.htm temp.txt powow2.xml

java Adnotare.Adnotare 1 powwow3.htm temp.txt powow3.xml

java Adnotare.Adnotare 1 powwow4.htm temp.txt powow4.xml

java Adnotare.Adnotare 1 powwow5.htm temp.txt powow5.xml

java Adnotare.Adnotare 1 powwow6.htm temp.txt powow6.xml

java Adnotare.Adnotare 1 powwow7.txt temp.txt powow7.xml

java Adnotare.Adnotare 1 powwow8.htm temp.txt powow8.xml

java Adnotare.Adnotare 1 powwow9.htm temp.txt powow9.xml

java Adnotare.Adnotare 1 neadnotat.htm temp.txt neadnotat.xml

run-invatare:

java Invatare.Invatare 9 partial.txt bigrama.txt trigrama.txt smooth.txt

run-recunoastere:

java Recunoastere.Recunoastere cue1.txt smooth.txt neadnotat.xml fixed.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow1.xml fixed1.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow2.xml fixed2.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow3.xml fixed3.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow4.xml fixed4.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow5.xml fixed5.xml

run-statistica:

java Statistica.Statistica adnotat.xml fixed.xml rezultat.txt

java Statistica.Statistica adnotat1.xml fixed1.xml rezultat1.txt

java Statistica.Statistica adnotat2.xml fixed2.xml rezultat2.txt

java Statistica.Statistica adnotat3.xml fixed3.xml rezultat3.txt

java Statistica.Statistica adnotat4.xml fixed4.xml rezultat4.txt

java Statistica.Statistica adnotat5.xml fixed5.xml rezultat5.txt

Rularea se face in felul urmator. La consola se vor da urmatoarele comenzi:

make compile se va face compilarea tuturor surselor

make run-adnotare se va face trecerea din fisiere .htm/.txt in fisiere .xml

make run-invatare se va face invatarea pe baza textelor adnotate manual

make run-recunoastere se va face recunoasterea tiparelor pe fisierele neadnotate

make run-statistica se vor face statistici referitoare la eficienta adnotarii automate

8.2 Windows

Sunt necesare mai multe fisiere in care sunt date comenzile necesare. In continuare voi prezenta fisierele necesare rularii aplicatiei, in ordinea rularii lor:

Compilare.bat – realizeaza compilarea surselor

javac Adnotare/*.java

javac Invatare/*.java

javac Recunoastere/*.java

javac Statistica/*.java

Adnotare.bat – transforma fisierele .txt/.html in fisiere .xml

java Adnotare.Adnotare 1 powwow1.htm temp.txt powow1.xml

java Adnotare.Adnotare 1 powwow2.htm temp.txt powow2.xml

java Adnotare.Adnotare 1 powwow3.htm temp.txt powow3.xml

java Adnotare.Adnotare 1 powwow4.htm temp.txt powow4.xml

java Adnotare.Adnotare 1 powwow5.htm temp.txt powow5.xml

java Adnotare.Adnotare 1 powwow6.htm temp.txt powow6.xml

java Adnotare.Adnotare 1 powwow7.txt temp.txt powow7.xml

java Adnotare.Adnotare 1 powwow8.htm temp.txt powow8.xml

java Adnotare.Adnotare 1 powwow9.htm temp.txt powow9.xml

java Adnotare.Adnotare 1 neadnotat.htm temp.txt neadnotat.xml

Invatare.bat – realizeaza invatarea din fisierele adnotate manual

java Invatare.Invatare 9 partial.txt bigrama.txt trigrama.txt smooth.txt

Recunoastere.bat – realizeaza recunoasterea de tipare pe fisierele neadnotate

java Recunoastere.Recunoastere cue1.txt smooth.txt neadnotat.xml fixed.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow1.xml fixed1.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow2.xml fixed2.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow3.xml fixed3.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow4.xml fixed4.xml

java Recunoastere.Recunoastere cue1.txt smooth.txt powow5.xml fixed5.xml

Statistica.bat – realizeaza statistici referitoare la eficienta adnotarii automate

java Statistica.Statistica adnotat.xml fixed.xml rezultat.txt

java Statistica.Statistica adnotat1.xml fixed1.xml rezultat1.txt

java Statistica.Statistica adnotat2.xml fixed2.xml rezultat2.txt

java Statistica.Statistica adnotat3.xml fixed3.xml rezultat3.txt

java Statistica.Statistica adnotat4.xml fixed4.xml rezultat4.txt

java Statistica.Statistica adnotat5.xml fixed5.xml rezultat5.txt

Capitolul 9. Calculul de complexitate

Pasul 1 – Adnotare

Complexitatea primului pas este O(n), deoarece nu se fac decat citiri si scrieri. Ceea ce se citeste dintr-un fisier, se parseaza si apoi se scrie in alt fisier. Este o singura bucla, deci complexitatea este O(n)

Pasul 2 – Adnotare manuala

Complexitatea celui de al doilea pas e O(0), deoarece nu avem nici un fel de program, tot ce se executa, se executa manual.

Pasul 3 – Invatare

Complexitatea celui de-al treilea pas este data de complexitatea parsarii fisierelor de intrare, care este O(n) – la fel ca mai sus, de complexitatea calcului matricei HMM, care este tot O(n) – parsarea unui vector, de complexitatea calculului celorlalte procente, care este O(1) si de complexitatea netezirii matricei HMM. Complexitatea netezirii matricei HMM este: O(n3) deoarece O(n2) provine de la parcurgerea matricei, iar inca un O(n) provine de la cautarea valorilor din matrice intr-un alt vector. In total este O(n3). Celelalte operatii care urmeaza dupa gasirea valorilor in vector/inserarea lor in vector au complexitatea de maxim O(n2). De aceea, complexitatea totala a netezirii matricei HMM este O(n3).

Deci, complexitatea totala a celui de-al treilea pas este O(n3).

Pasul 4 – Recunoastere

Complexitatea celui de-al patrulea pas este data de complexitatea citirii din fisiere care este
O(n), complexitatea scrierii in fisier, care este tot O(n) si de complexitatea algoritmului Viterbi, care este O(n3), deoarece avem un ciclu pentru taguri, unul pentru starea curenta si altul pentru starea urmatoare.

Deci, complexitatea pasului al patrulea este O(n3).

Pasul 5 – Statistica

Complexitatea acestui pas este O(n). Ea este data de citirile din fisiere, care este O(n) si de compararea efectiva, care este tot O(n) – fiind data de parcurgerea simultana a doi vectori si efectuarea unor calcule.

Deci, complexitatea intregii aplicatii este O(n3).

Capitolul 10. Prezentarea rezultatelor

In urma primului pas (Adnotare) se vor obtine fisierele de tip .xml, neadnotate. In continuare voi prezenta un mic fragment dintr-un fisier .xml obtinut in urma primului pas (powow1.xml):

(10:01:39 AM) You have just entered room "powwow1."(10:01:49 AM) klasher321 has entered the room.

– <Turn Id="T1" Speaker="klasher321" time="10:01:59 AM">

<Utt Id="Utt1" Info-level="" Conventional="" Time="10:01:59 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">hi Gerry(10:02:00 AM) stevriz has entered the room.</Utt>

  </Turn>

– <Turn Id="T2" Speaker="klasher321" time="10:02:07 AM">

<Utt Id="Utt2" Info-level="" Conventional="" Time="10:02:07 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">Hi Riz</Utt>

  </Turn>

– <Turn Id="T3" Speaker="stevriz" time="10:02:14 AM">

<Utt Id="Utt3" Info-level="" Conventional="" Time="10:02:14 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">Hi all</Utt>

  </Turn>

– <Turn Id="T4" Speaker="gerrystahl" time="10:02:40 AM">

<Utt Id="Utt4" Info-level="" Conventional="" Time="10:02:40 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">welcome Riz and Kristina</Utt>

  </Turn>

– <Turn Id="T5" Speaker="klasher321" time="10:02:48 AM">

<Utt Id="Utt5" Info-level="" Conventional="" Time="10:02:48 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">Or should I say, who is this stevriz person?</Utt>

  </Turn>

– <Turn Id="T6" Speaker="stevriz" time="10:02:51 AM">

<Utt Id="Utt6" Info-level="" Conventional="" Time="10:02:51 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">I'm entering this experience with new optimism now that I have this slick computer.</Utt>

  </Turn>

– <Turn Id="T7" Speaker="gerrystahl" time="10:03:15 AM">

<Utt Id="Utt7" Info-level="" Conventional="" Time="10:03:15 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">Shall we do some math together?</Utt>

  </Turn>

– <Turn Id="T8" Speaker="stevriz" time="10:03:20 AM">

<Utt Id="Utt8" Info-level="" Conventional="" Time="10:03:20 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">Well, I had already used 'steveriz' years ago and couldn't remember the password.</Utt>

  </Turn>

– <Turn Id="T9" Speaker="stevriz" time="10:03:29 AM">

<Utt Id="Utt9" Info-level="" Conventional="" Time="10:03:29 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">let's do some geometry!</Utt>

  </Turn>

– <Turn Id="T10" Speaker="klasher321" time="10:03:41 AM">

<Utt Id="Utt10" Info-level="" Conventional="" Time="10:03:41 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">ok!</Utt>

  </Turn>

– <Turn Id="T11" Speaker="gerrystahl" time="10:04:05 AM">

<Utt Id="Utt11" Info-level="" Conventional="" Time="10:04:05 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">do you know the powwow rules?</Utt>

  </Turn>

– <Turn Id="T12" Speaker="klasher321" time="10:04:24 AM">

<Utt Id="Utt12" Info-level="" Conventional="" Time="10:04:24 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="" Answer="">maybe I better read them again.</Utt>

  </Turn>

In urma celui de-al doilea pas (Adnotare manuala) se vor obtine fisierele adnotate manual ce vor fi utilizate mai departe in pasul al treilea (invatare). Un astfel de exemplu este dat la sfarsitul prezentarii pasului al doilea (adnotarea manuala) – pagina 23 – si de aceea nu se va mai relua.

In urma celui de-al treilea pas (Invatare) se vor obtine patru fisiere in care vor fi descrise rezultatele invatarii. Aceste fisiere sunt “partial.txt”, “bigrama.txt”, “trigrama.txt” si “smooth.txt”. In continuare voi prezenta fiecare fisier in parte:

partial.txt – realizeaza statistici partiale (si mai putin relevante) referitoare la invatare. Se specifica numarul total de taguri pe care a fost realizata invatarea, precum si numarul si procentul din fiecare tip de tag in parte.

Numarul total de taguri:=2235

Accept:=391

Reject:=71

Maybe:=27

Accept part:=8

Reject part:=1

No response:=1737

Procent Accept:=0.17494407

Procent Reject:=0.03176734

Procent Maybe:=0.012080537

Procent Accept part:=0.0035794184

Procent Reject part:=4.474273E-4

Procent No response:=0.7771812

trigrama.txt – fisierul ce contine tabloul tridimensional rezultat in urma invatarii. Este similar cu fisierul bigrama.txt (prezentat in continuare), doar ca se refera la grupe de cate 3 tipuri de tag (in loc de 2 ca la bigrama). Acest fisier nu va mai fi prezentat deoarece este similar celui de mai jos!

bigrama.txt – fisierul ce contine matricea HMM obtinuta in urma invatarii:

AcceptPart RejectPart Accept Reject Maybe None

AcceptPart 0.0 0.0 0.25 0.0 0.0 0.75

RejectPart 0.0 0.0 0.0 0.0 0.0 1.0

Accept 0.0076726344 0.0 0.25575447 0.012787724 0.012787724 0.71099746

Reject 0.0 0.0 0.2112676 0.15492958 0.0 0.63380283

Maybe 0.0 0.0 0.22222222 0.037037037 0.037037037 0.7037037

None 0.0028785262 5.7570526E-4 0.154289 0.031088082 0.01208981 0.79850316

smooth.txt – fisierul care contine matricea HMM netezita:

0.0035196804729035604 0.0035773576546257978 0.25

0.002867810705497953 0.0033578001938631787 0.75

4.3996005911294504E-4 4.471697068282247E-4 -4.184935462607891E-5 3.5847633818724415E-4 4.1972502423289734E-4 1.0

0.013810741687979541 0.17484335536983586 0.2557544757033248 0.01278772378516624 0.01278772378516624 0.710997442455243

0.0312371641970191 0.03174904918480396 0.2112676056338028

0.15492957746478872 0.02980047672053571 0.6338028169014085

0.011878921596049516 0.012073582084362069 0.2222222222222222 0.037037037037037035 0.037037037037037035 0.7037037037037037

0.0028785261945883708 5.757052389176742E-4 0.15428900402993667 0.031088082901554404 0.012089810017271158 0.798503166378814

In urma celui de-al patrulea pas (Recunoastere) se obtin fisierele adnotate automat. Iata echivalentul fragmentului adnotat manual de mai sus (de la sfarsitul pasului al doilea), dar adnotat automat de aceasta data:

(10:01:39 AM) You have just entered room "powwow1."(10:01:49 AM) klasher321 has entered the room.

– <Turn Id="T1" Speaker="klasher321" time="10:01:59 AM">

<Utt Id="Utt1" Info-level="" Conventional="" Time="10:01:59 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">hi Gerry(10:02:00 AM) stevriz has entered the room.</Utt>

  </Turn>

– <Turn Id="T2" Speaker="klasher321" time="10:02:07 AM">

<Utt Id="Utt2" Info-level="" Conventional="" Time="10:02:07 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">Hi Riz</Utt>

  </Turn>

– <Turn Id="T3" Speaker="stevriz" time="10:02:14 AM">

<Utt Id="Utt3" Info-level="" Conventional="" Time="10:02:14 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">Hi all</Utt>

  </Turn>

– <Turn Id="T4" Speaker="gerrystahl" time="10:02:40 AM">

<Utt Id="Utt4" Info-level="" Conventional="" Time="10:02:40 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">welcome Riz and Kristina</Utt>

  </Turn>

– <Turn Id="T5" Speaker="klasher321" time="10:02:48 AM">

<Utt Id="Utt5" Info-level="" Conventional="" Time="10:02:48 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">Or should I say, who is this stevriz person?</Utt>

  </Turn>

– <Turn Id="T6" Speaker="stevriz" time="10:02:51 AM">

<Utt Id="Utt6" Info-level="" Conventional="" Time="10:02:51 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">I'm entering this experience with new optimism now that I have this slick computer.</Utt>

  </Turn>

– <Turn Id="T7" Speaker="gerrystahl" time="10:03:15 AM">

<Utt Id="Utt7" Info-level="" Conventional="" Time="10:03:15 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">Shall we do some math together?</Utt>

  </Turn>

– <Turn Id="T8" Speaker="stevriz" time="10:03:20 AM">

<Utt Id="Utt8" Info-level="" Conventional="" Time="10:03:20 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">Well, I had already used 'steveriz' years ago and couldn't remember the password.</Utt>

  </Turn>

– <Turn Id="T9" Speaker="stevriz" time="10:03:29 AM">

<Utt Id="Utt9" Info-level="" Conventional="" Time="10:03:29 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">let's do some geometry!</Utt>

  </Turn>

– <Turn Id="T10" Speaker="klasher321" time="10:03:41 AM">

<Utt Id="Utt10" Info-level="" Conventional="" Time="10:03:41 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">ok!</Utt>

  </Turn>

– <Turn Id="T11" Speaker="gerrystahl" time="10:04:05 AM">

<Utt Id="Utt11" Info-level="" Conventional="" Time="10:04:05 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">do you know the powwow rules?</Utt>

  </Turn>

– <Turn Id="T12" Speaker="klasher321" time="10:04:24 AM">

<Utt Id="Utt12" Info-level="" Conventional="" Time="10:04:24 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="Maybe" Answer="">maybe I better read them again.</Utt>

  </Turn>

– <Turn Id="T13" Speaker="stevriz" time="10:04:25 AM">

<Utt Id="Utt13" Info-level="" Conventional="" Time="10:04:25 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">I read the blurb on the geopow site – does that cover it?</Utt>

  </Turn>

– <Turn Id="T14" Speaker="gerrystahl" time="10:04:26 AM">

<Utt Id="Utt14" Info-level="" Conventional="" Time="10:04:26 AM" Influence-on-listener="" Influence-on-speaker="" Agreement="None" Answer="">we need a list of these rules – where are they?</Utt>

  </Turn>

In urma ultimului pas (Statistica) se obtin fisierele rezultat, in care se fac statistici referitoare la eficienta adnotarii automate. In aceste fisiere sunt date rezultatele compararii intre fisierele adnotate manual si cele adnotate automat. In continuare se vor prezenta cateva din aceste fisere:

in primul rand, rezultatul adnotarii pe fisierul ce nu a fost utilizat la invatare:

Fisierul adnotat automat "adnotat.xml" contine: 300 taguri, dintre care:

Accept 65

Reject 11

Maybe 3

None 221

Fisierul adnotat de catre program "fixed.xml" contine: 300 taguri, dintre care:

Accept 18

Reject 1

None 281

In total au fost adnotate corect: 230.0 taguri, reprezentand 0.76666665 din numarul total de taguri

Dintre acestea,au fost recunoscute corect:

13 taguri Accept; reprezentand 0.05652174

1 tag Reject; reprezentand 0.004347826

216 taguri None; reprezentand 0.9391304

in al doilea rand voi prezenta rezultatul adnotarii pe cel mai mare fisier folosit la invatare:

Fisierul adnotat automat "adnotat2.xml" contine: 715 taguri, dintre care:

Accept 120

Reject 27

Accept Part 1

Reject Part 1

Maybe 3

None 563

Fisierul adnotat de catre program "fixed2.xml" contine: 715 taguri, dintre care:

Accept 95

Reject 29

Accept Part 1

Reject Part 2

Maybe 2

None 586

In total au fost adnotate corect: 577.0 taguri, reprezentand 0.806993 din numarul total de taguri

Dintre acestea,au fost recunoscute corect:

60 taguri Accept; reprezentand 0.10398614

8 taguri Reject; reprezentand 0.013864818

1 taguri Maybe; reprezentand 0.0017331023

508 taguri None; reprezentand 0.8804159

in ultimul rand voi prezenta rezultatul adnotarii pe cel mai mic fisier folosit la invatare:

Fisierul adnotat automat "adnotat4.xml" contine: 69 taguri, dintre care:

Accept 11

Reject 2

Accept Part 1

Maybe 1

None 54

Fisierul adnotat de catre program "fixed4.xml" contine: 69 taguri, dintre care:

Accept 4

None 65

In total au fost adnotate corect: 56.0 taguri, reprezentand 0.8115942 din numarul total de taguri

Dintre acestea,au fost recunoscute corect:

3 taguri Accept; reprezentand 0.05357143

53 taguri None; reprezentand 0.9464286

Capitolul 11. Concluzii

Aceasta metoda de determinare a tipului fiecarui enunt dintr-un dialog la care participa mai multe persoane are o complexitate buna, e rapida, usor de aplicat, si, dupa cum s-a putut vedea, cu rezultate destul de bune.

Procentul de recunoasterea a tipului enunturilor prin aceasta metoda este cuprins intre 75% si 90%. Rezultatele obtinute depind de cativa factori, cei mai importanti fiind fisierele pe care se face invatarea, cuvintele-cheie care sunt cautate in textul neadnotat, modelul ales pentru recunoastere si algoritmul aplicat in acest sens.

Aceasta aplicatie este o tema de cercetare, care poate fi imbunatatita prin cresterea aportului factorilor de care depind rezultatele.

Propuneri de imbunatatire:

marirea numarului de fisiere pe care se face invatarea va conduce la un model mai precis al fisierelor care trebuiesc adnotate, iar in acest fel recunoasterea va fi mai fidela;

marirea numarului de cuvinte-cheie cautate in textul neadnotat va asigura o recunoastere mai fidela;

modificarea algoritmului Viterbi ar putea determina calea optima cu o probabilitate mai mare. Astfel, in loc sa consideram ca un cuvant-cheie poate fi intalnit intr-un singur tip de enunt cu probabilitatea de 100%, iar in restul cu probabilitatea 0%, ar trebui sa luam in considerare faptul ca acel cuvant-cheie ar putea sa apara in mai multe tipuri de enunt. Cu alte cuvinte, ar trebui impartita acea probabilitate de 100% intre diferitele tipuri de enunturi in care poate fi intalnit cuvantul-cheie;

cresterea numarului enunturilor anterioare de care se tine cont. Acest lucru a fost incercat si in lucrarea de fata (in momentul in care s-au calculat procentele trigramelor din textele adnotate manual), dar aceasta directie a fost abandonata datorita cresterii mari a complexitatii si duratei de executie, precum si a raritatii tabloului obtinut in urma determinarii procentelor trigramelor, care ar fi condus la rezultate destul de slabe.

ANEXA 2. PREZENTAREA SURSELOR

Pachetul Adnotare

Adnotare.java

package Adnotare;

import java.awt.*;

import java.io.*;

import java.awt.event.*;

class Adnotare extends Frame

{

public Adnotare() {

addWindowListener(new WindowAdapter() {

public void windowClosing(WindowEvent e) {

dispose();

System.exit(0);

}

});

}

public static void main(String args[]) throws IOException

{

int param=Integer.parseInt(args[0]);

String f1=args[1];

String f2=args[2];

String f3=args[3];

Citire c=new Citire();

if (param==0) c.prelucrare(f1,f3,f1);

else{

c.citire(f1,f2);

c.prelucrare(f2,f3,f1);

}

}

}

Citire.java

package Adnotare;

import java.util.*;

import java.io.*;

public class Citire

{

private int comentariu=0;

private int nr_turn=0;

private int nr_utt=1;

private int first=0;//la primul tag se face 1

public Citire(){}

final public void citire(String fis1,String fis2) throws IOException{

FileReader in = new FileReader(fis1);

FileWriter out = new FileWriter(fis2);

int c;

while ((c=in.read())!=-1) {

if(c=='<') comentariu=1; //marchez inceput tag html

if(comentariu!=1) out.write(c); //scriu doar daca nu sunt intr-un tag html

else if(c=='>') comentariu=0; //marchez sfarsit tag html

}//while

in.close();

out.close();

}

public void prelucrare(String fis1,String fis2,String fis3) throws IOException{

String s=new String();

String s1=new String();

String sir=new String();

int i=0,j=0,paranteza=0,sf_nume,sf_data;

FileReader in = new FileReader(fis1);

FileWriter out = new FileWriter(fis2);

out.write("<Dialog Id=\""+fis3+"\" Date=\"\">\n");

try {

BufferedReader br = new BufferedReader(in);

while ((sir = br.readLine()) != null) {

paranteza=0;

if(sir.indexOf("(")==-1) out.write(sir);//nu e linie importanta

else if(sir.startsWith("(")) out.write(sir);//directiva de site

else {

if(paranteza==0){

paranteza++;//incrementez nrul parantezelor gasite

sf_nume=sir.indexOf("(");

if(paranteza==1 && (sir.indexOf(")")!=-1)){

paranteza++;//incrementez nrul parantezelor gasite

nr_turn++;//incrementez numarul turnului

sf_data=sir.indexOf(")");//unde se termina data

if(first==0) first=1;//nu inchid un tag inainte sa il deschid

else out.write("</Utt>\n</Turn>\n");//inchid tag

out.write("\n<Turn Id=\"T"+nr_turn);//pun tagul

s=sir.substring(0,sf_nume-1);

out.write("\" Speaker=\""+s);//pun userul

s=sir.substring(sf_nume+1,sf_data);

out.write("\" time=\""+s+"\">");//pun data

int text=sir.lastIndexOf("): ");

s1=sir.substring(text+3,sir.length());

int aux=sf_data+1;

if(sir.indexOf("(",aux)!=-1 || sir.indexOf(")",aux)!=-1){

paranteza++;

if (sir.indexOf("(",aux)!=-1)

aux=sir.indexOf("(",aux);

else aux=sir.indexOf("(",aux);

}

}

}

if(paranteza==1) out.write(s);//tot randul a fost de text

else{//fac tagurile de xml

out.write("\n<Utt Id=\"Utt"+nr_utt+"\" Info-level=\"\" ");

nr_utt++; //incrementez numarul utteranceului

out.write("Conventional=\"\" Time=\""+s+"\" Influenc");

out.write("e-on-listener=\"\" Influence-on-speaker=\"\"");

out.write(" Agreement=\"\" Answer=\"\">\n"+s1);

//pun restul

}

}

} //am terminat de citit

out.write("</Utt>\n</Turn>\n</Dialog>");//pentru ultimul turn & utt

in.close();

out.close();

}catch (IOException e){}

}

}

Pachetul Invatare

Invatare.java

package Invatare;

import java.awt.*;

import java.io.*;

import java.awt.event.*;

class Invatare extends Frame {

public Invatare() {

addWindowListener(new WindowAdapter() {

public void windowClosing(WindowEvent e) {

dispose();

System.exit(0);

}

});

}

public static void main(String args[]) throws IOException {

int fis;

int param=Integer.parseInt(args[0]);

String fis1=args[1];

String fis2=args[2];

String fis3=args[3];

String fis4=args[4];

File outputFile = new File(fis1);

File outputFile2 = new File(fis2);

File outputFile3 = new File(fis3);

File outputFile4 = new File(fis4);

FileWriter out = new FileWriter(outputFile);

FileWriter out2 = new FileWriter(outputFile2);

FileWriter out3 = new FileWriter(outputFile3);

FileWriter out4 = new FileWriter(outputFile4);

Parsare p=new Parsare();

for(fis=1;fis<=param;fis++)p.count(fis);

p.CalculProcente();

p.calcPrecedente();

p.calcPrecedente2();

Smooth s=new Smooth (p.getMatrix(), p.getAccPart(), p.getRejPart(), p.getAcc(), p.getRej(), p.getMaybe(), p.getNone());

s.Smooth();

out.write("Numarul total de taguri:="+p.getSize()+"\n");

out.write("Accept:="+p.getAcc()+"\n");

out.write("Reject:="+p.getRej()+"\n");

out.write("Maybe:="+p.getMaybe()+"\n");

out.write("Accept part:="+p.getAccPart()+"\n");

out.write("Reject part:="+p.getRejPart()+"\n");

out.write("No response:="+p.getNone()+"\n\n");

out.write("Procent Accept:="+p.getPA()+"\n");

out.write("Procent Reject:="+p.getPR()+"\n");

out.write("Procent Maybe:="+p.getPM()+"\n");

out.write("Procent Accept part:="+p.getPAPart()+"\n");

out.write("Procent Reject part:="+p.getPRPart()+"\n");

out.write("Procent No response:="+p.getPN()+"\n\n");

p.printMatrix(out2);

p.printTablou(out3);

s.printSmooth(out4);

//p.afisMatrix(); debugging

out.close();

out2.close();

out3.close();

out4.close();

}

}

Parsare.java

package Invatare;

import java.util.*;

import java.io.*;

import org.xml.sax.*;

import org.xml.sax.helpers.*;

public class Parsare extends AbstractXMLParser{

private Vector agreement=new Vector();//vectorul in care voi salva atributele

private int acc=0,rej=0,maybe=0,accpart=0,rejpart=0,none=0;

//numarul de atribute de tipul Accept/Reject/Maybe…

private int[][] m=new int[6][6];//matricea de precedente

private int[][][] tablou=new int[6][6][6];//cubul de precerente pt trigrama

private float pa=0,pr=0,pm=0,papart=0,prpart=0,pn=0;//procentele atributelor

public Parsare(){

super();

for(int i=0;i<6;i++)

for(int j=0;j<6;j++) m[i][j]=0;//init matrice

}

public void count(int nr_fis){

String fileName="adnotat"+nr_fis+".xml";

try{

parser.parse(new InputSource(new FileReader(fileName)));

}catch (Exception e) {e.printStackTrace();}

return;

}

final public void startElement(final String namespace,final String localname,final String type,final Attributes attributes) throws SAXException {

if (type.compareTo("Utt")==0){

String name=attributes.getValue("Agreement");

agreement.addElement(name);

if (name.compareTo("Accept Part")==0) accpart++;

if (name.compareTo("Reject Part")==0) rejpart++;

if (name.compareTo("Accept")==0) acc++;

if (name.compareTo("Reject")==0) rej++;

if (name.compareTo("Maybe")==0) maybe++;

if (name.compareTo("None")==0) none++;

}

}

public void CalculProcente(){

pa=(float)acc/agreement.size();

pr=(float)rej/agreement.size();

pm=(float)maybe/agreement.size();

pn=(float)none/agreement.size();

papart=(float)accpart/agreement.size();

prpart=(float)rejpart/agreement.size();

}

public void calcPrecedente(){

int curr=-1;

int last=-1;

if (agreement.elementAt(0).toString().compareTo("Accept Part")==0) last=0;

if (agreement.elementAt(0).toString().compareTo("Reject Part")==0) last=1;

if (agreement.elementAt(0).toString().compareTo("Accept")==0) last=2;

if (agreement.elementAt(0).toString().compareTo("Reject")==0) last=3;

if (agreement.elementAt(0).toString().compareTo("Maybe")==0) last=4;

if (agreement.elementAt(0).toString().compareTo("None")==0) last=5;

for (int i=1;i<agreement.size();i++){

if (agreement.elementAt(i).toString().compareTo("Accept Part")==0) curr=0;

if (agreement.elementAt(i).toString().compareTo("Reject Part")==0) curr=1;

if (agreement.elementAt(i).toString().compareTo("Accept")==0) curr=2;

if (agreement.elementAt(i).toString().compareTo("Reject")==0) curr=3;

if (agreement.elementAt(i).toString().compareTo("Maybe")==0) curr=4;

if (agreement.elementAt(i).toString().compareTo("None")==0) curr=5;

m[last][curr]++;

last=curr;

}

}

public void calcPrecedente2(){

int curr=-1;

int last=-1;

int ant=-1;

if (agreement.elementAt(0).toString().compareTo("Accept Part")==0) ant=0;

if (agreement.elementAt(0).toString().compareTo("Reject Part")==0) ant=1;

if (agreement.elementAt(0).toString().compareTo("Accept")==0) ant=2;

if (agreement.elementAt(0).toString().compareTo("Reject")==0) ant=3;

if (agreement.elementAt(0).toString().compareTo("Maybe")==0) ant=4;

if (agreement.elementAt(0).toString().compareTo("None")==0) ant=5;

if (agreement.elementAt(1).toString().compareTo("Accept Part")==0) last=0;

if (agreement.elementAt(1).toString().compareTo("Reject Part")==0) last=1;

if (agreement.elementAt(1).toString().compareTo("Accept")==0) last=2;

if (agreement.elementAt(1).toString().compareTo("Reject")==0) last=3;

if (agreement.elementAt(1).toString().compareTo("Maybe")==0) last=4;

if (agreement.elementAt(1).toString().compareTo("None")==0) last=5;

for (int i=2;i<agreement.size();i++){

if (agreement.elementAt(i).toString().compareTo("Accept Part")==0) curr=0;

if (agreement.elementAt(i).toString().compareTo("Reject Part")==0) curr=1;

if (agreement.elementAt(i).toString().compareTo("Accept")==0) curr=2;

if (agreement.elementAt(i).toString().compareTo("Reject")==0) curr=3;

if (agreement.elementAt(i).toString().compareTo("Maybe")==0) curr=4;

if (agreement.elementAt(i).toString().compareTo("None")==0) curr=5;

tablou[ant][last][curr]++;

ant=last;

last=curr;

}

}

public int getSize(){return agreement.size();}

public int getAcc(){return acc;}

public int getRej(){return rej;}

public int getMaybe(){return maybe;}

public int getAccPart(){return accpart;}

public int getRejPart(){return rejpart;}

public int getNone(){return none;}

public float getPA(){return pa;}

public float getPR(){return pr;}

public float getPM(){return pm;}

public float getPAPart(){return papart;}

public float getPRPart(){return prpart;}

public float getPN(){return pn;}

public int[][] getMatrix(){return m;}

public void printVector(){

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

System.out.println(agreement.elementAt(i));

}

public void printMatrix(FileWriter out) throws IOException{

out.write("\t\tAcceptPart\tRejectPart\tAccept");

out.write("\tReject\tMaybe\tNone\n"); //capul de tabel

for(int i=0;i<6;i++){

if (i==0) out.write("AcceptPart");

if (i==1) out.write("RejectPart");

if (i==2) out.write("Accept");

if (i==3) out.write("Reject");

if (i==4) out.write("Maybe\t");

if (i==5) out.write("None\t");

for(int j=0;j<6;j++) {

if (i==0) if(accpart!=0) out.write("\t"+(float)m[i][j]/accpart);

else out.write("\t"+0);

if (i==1) if(rejpart!=0) out.write("\t"+(float)m[i][j]/rejpart);

else out.write("\t"+0);

if (i==2) if(acc!=0) out.write("\t"+(float)m[i][j]/acc);

else out.write("\t"+0);

if (i==3) if(rej!=0) out.write("\t"+(float)m[i][j]/rej);

else out.write("\t"+0);

if (i==4) if(maybe!=0) out.write("\t"+(float)m[i][j]/maybe);

else out.write("\t"+0);

if (i==5) if(none!=0) out.write("\t"+(float)m[i][j]/none);

else out.write("\t"+0);

}

out.write("\n");

}

}

public void printTablou(FileWriter out) throws IOException{

out.write("\tAP\tRP\tA\tR\tM\tN\n");

for(int i=0;i<6;i++){

if (i==0) out.write("AP");

if (i==1) out.write("RP");

if (i==2) out.write("A");

if (i==3) out.write("R");

if (i==4) out.write("M");

if (i==5) out.write("N");

for(int j=0;j<6;j++) {

for (int k=0;k<6;k++)

if (m[j][k]!=0) out.write("\t"+(float)tablou[i][j][k]/m[j][k]);

else out.write("\t"+0);

out.write("\n");

}

}

}

/* Debugging

public void afisMatrix() throws IOException {

File output = new File("numar.txt");

FileWriter out = new FileWriter(output);

for(int i=0;i<6;i++){

for(int j=0;j<6;j++) out.write(" "+m[i][j]+" ");

out.write("\n");

}

out.close();

}

*/

}

AbstractXMLParser

package Invatare;

import java.io.*;

import org.xml.sax.*;

import org.xml.sax.helpers.*;

import javax.xml.parsers.*;

public class AbstractXMLParser implements ContentHandler,DTDHandler,EntityResolver

{

protected XMLReader parser;

public AbstractXMLParser()

{

try

{

SAXParserFactory saxParserFactory=SAXParserFactory.newInstance();

SAXParser saxParser=saxParserFactory.newSAXParser();

parser=saxParser.getXMLReader();

parser.setContentHandler(this);

parser.setDTDHandler(this);

parser.setEntityResolver(this);

}catch (Exception e)

{

e.printStackTrace();

}

}

public void startElement(final String namespace,final String localname,final String type,final Attributes attributes) throws SAXException {}

public void endElement(final String namespace,final String localname,final String type) throws SAXException {}

public void characters( final char[] ch, final int start, final int len ) {}

public void endDocument() throws SAXException {}

public void endPrefixMapping(final String prefix) throws SAXException {}

public void ignorableWhitespace(final char[] ch, final int start,final int length) throws SAXException {}

public void processingInstruction ( final String target, final String data ) throws SAXException {}

public void setDocumentLocator( final org.xml.sax.Locator locator ) {}

public void skippedEntity( final String name ) throws SAXException {}

public void startDocument() throws SAXException {}

public void startPrefixMapping( final String prefix, final String uri ) throws SAXException {}

public void notationDecl(String name, String publicId, String systemId) {}

public void unparsedEntityDecl(String name, String publicId, String systemId, String notationName) {}

public InputSource resolveEntity(String publicId, String systemId) {

return new InputSource(new StringReader(""));

}

}

Smooth.java

package Invatare;

import java.util.*;

import java.io.*;

public class Smooth{

private int limita=4;//limita dupa care nu mai calculez noile valori

private int val=0;//limita la care s-a ajuns in vectorii valori si nr_valori

private int total=0;//suma tuturor

private int [] agreement=new int[6];//in el retin valorile acc/acc part/…

private int [][] mat=new int [6][6]; //matricea pe care o am

//necesare pt calculul lui p~(w2,w1)

private int [] valori=new int [36];//aici retin valorile gasite in mat

private int [] nr_val=new int [36];//aici retin cu ce rata gasesc valorile

private double []rstar=new double [36];//noile procente r*

private double []dr=new double [36];//vectorul de coeficienti Dr

private double [][]p_tilda=new double [6][6];//matricea P~(w2,w1), care in final va deveni matricea netezita

private double []alfa=new double[6];//aici calculez coeficietii alfa(w1)

public Smooth(int [][]matrice,int accpart,int rejpart,int acc,int rej,int maybe,int none ){

mat=matrice;

agreement[0]=accpart;

agreement[1]=rejpart;

agreement[2]=acc;

agreement[3]=rej;

agreement[4]=maybe;

agreement[5]=none;

for(int i=0;i<6;i++)total+=agreement[i];

for(int i=0;i<36;i++)valori[i]=-1;

}

public void Smooth(){

int gata=0;

int gata2=0;

int gata3=0;

int gata4=0;

int index=0;

double constanta=0;

//calculez Nc in nr_valori iar vectorul valori reprezinta c-ul

for (int i=0;i<6;i++)//numarare – Nc

for(int j=0;j<6;j++){

gata=0;

if(mat[i][j]!=0){

for(int k=0;k<val;k++)

if(gata==0) if(mat[i][j]==valori[k]) {

nr_val[k]++;

gata=1;

}

if (gata==0){

valori[val]=mat[i][j];

nr_val[val]=1;

val++;

}

}

}

//s-a termiant numararea…am Nc pt c-urile din matrice

//calculez r*

for(int i=0;i<val;i++){

if(valori[i]>limita) rstar[i]=valori[i];

else {

int temp=valori[i];

for (int j=0;j<val;j++)

if(gata2==0)

if(valori[j]==temp+1){

index=j;

gata2=1;

}

if(gata2==0) rstar[i]=0;

else {

gata2=0;

rstar[i]=(double)((temp+1)*nr_val[index])/nr_val[i];

}

}//else

}

//s-a terminat si calculul lui r*

//calculez constanta (k-1)*n(k+1)/n1 k==limita … iar apoi dr

for (int j=0;j<val;j++)

if(gata3==0)

if(valori[j]==limita+1){

index=j;

gata3=1;

}

if (gata3==0)constanta=0;

else constanta=(double)(limita-1)*nr_val[index]; //trebuie sa o mai impart la n1

for (int j=0;j<val;j++)

if(gata4==0)

if(valori[j]==1){ //daca nu il gaseste inseamna ca nr_val e 0 si sa evit impartirea la 0

index=j;

gata4=1;

}

if(gata4!=0) {

constanta/=nr_val[index];//am impartit-o si la ce trebuia si am obtinut valoare finala

for(int i=0;i<val;i++) dr[i]=(double)(rstar[i]/valori[i]-constanta)/(1-constanta);

}

else for (int i=0;i<val;i++) dr[i]=1;

//s-a terminat si calculul lui dr

//calculez P~(w2,w1)

for(int i=0;i<6;i++)

for(int j=0;j<6;j++)

if(mat[i][j]>limita)p_tilda[i][j]=(double)(mat[i][j])/agreement[i];

else p_tilda[i][j]=(double)(mat[i][j]*dr[valori[mat[i][j]]])/agreement[i];

//gata calcul p~(w2,w1)

//calculez alfa

for(int i=0;i<6;i++){

double s1=0;

double s2=0;

for(int j=0;j<6;j++)

if(mat[i][j]>0){

s1+=agreement[j]/total;//aici calculez S(P~(w2)).consider ca p~(w2)=p(w2)

s2+=p_tilda[j][i];//aici calculez S(P~(w2,w1))

}

alfa[i]=(double)(1-s2)/(1-s1);

}

//gata calculul lui alfa

//calculez pk(w2,w1)

for(int i=0;i<6;i++)

for(int j=0;j<6;j++)

if(p_tilda[i][j]==0) p_tilda[i][j]=(double)alfa[j]*agreement[i]/total;

//gata calcul pk…finish

}

public void printSmooth(FileWriter out) throws IOException{

out.write("Aceasta este matricea modificata prin metoda Katz\n");

for(int i=0;i<6;i++){

for(int j=0;j<6;j++)

out.write("\t"+Double.toString(p_tilda[i][j]));

out.write("\n");

}

}

/* DEBUGGING

public void printMatrix(FileWriter out) throws IOException{

out.write(total+"\n");

for(int i=0;i<6;i++){

for(int j=0;j<6;j++)

out.write(" "+mat[i][j]);

out.write("\n");

}

out.write("\n");

for(int i=0;i<val;i++) out.write(valori[i]+ " " );

out.write("\n");

for(int i=0;i<val;i++) out.write(nr_val[i]+ " ");

out.write("\n");

for(int i=0;i<val;i++) out.write(Double.toString(rstar[i])+ " ");

out.write("\n");

for(int i=0;i<val;i++) out.write(Double.toString(dr[i])+ " ");

out.write("\n");

for(int i=0;i<6;i++){

for(int j=0;j<6;j++)

out.write(" "+Double.toString(p_tilda[i][j]));

out.write("\n");

}

}*/

}

Pachetul Recunoastere

Recunoastere.java

package Recunoastere;

import java.awt.*;

import java.io.*;

import java.awt.event.*;

public class Recunoastere extends Frame{

public Recunoastere(){

addWindowListener(new WindowAdapter() {

public void windowClosing(WindowEvent e) {

dispose();

System.exit(0);

}

});

}

public static void main(String[] args) throws IOException{

String fis1=args[0];

String fis2=args[1];

String fis3=args[2];

String fis4=args[3];

Citire c=new Citire();

c.citire(fis1,fis2,fis3);

int nr=c.getNr_tag();

int tags[]=c.getTag();

float tr[][]=c.getMat();

Viterbi v=new Viterbi();

int []rez=v.Viterbi(nr,tags,6,tr);

double prob=v.getProbability();

Double pr=new Double(prob);

System.out.println("Probabilitatea recunoasterii este:"+pr.toString());

Scriere s=new Scriere();

s.scriere(rez,fis3,fis4);

}

}

Citire.java

package Recunoastere;

import java.util.*;

import java.io.*;

public class Citire

{

private int nr_tag=0;//cu ea pastrez indicele in mat

private int checked=0;//stabilesc daca am modificat valoarea unui tag sau nu

private int [] tag=new int[1000]; //in vectorul asta o sa tin probabilitatile

//de a fi accept part-0/reject part-1/accept-2/reject-3/maybe-4/none-5

private float [][] tranzitii=new float[6][6]; //matricea HMM o citesc din fisier

private Vector Acc=new Vector(); //vectorii de cuvinte-cheie

private Vector Rej=new Vector();

private Vector Maybe=new Vector();

public Citire(){

for(int i=0;i<1000;i++) tag[i]=-1;

}

final public void citire(String fis1,String fis2,String fis3) throws IOException

{

FileReader in1 = new FileReader(fis1);

FileReader in2 = new FileReader(fis2);

FileReader in3 = new FileReader(fis3);

String sir=new String();//in asta citesc fiecare linie din fisier

String s=new String();//in asta formez continutul unui tag – xml

int poz=0,pozitie=0; //poz e de unde pleaca, pozitie e unde gaseste /

int stare=0;//stiu in care vector voi pune textele – citire cue words

int linie=0;//ca sa stiu pe ce linie sunt –citire matrice HMM

int i=0;//iterator

try { //citesc lista de cuvinte-cheie din fisierul cue1

BufferedReader br = new BufferedReader(in1);

while ((sir = br.readLine()) != null) {

pozitie=0;

poz=0;

while(pozitie!=-1){

pozitie=sir.indexOf('/',poz);

if(pozitie!=-1){

switch(stare){

case 0:Acc.addElement(sir.substring(poz,pozitie));break;

case 1:Rej.addElement(sir.substring(poz,pozitie));break;

default:Maybe.addElement(sir.substring(poz,pozitie)); }

poz=pozitie+1;

}//if

}//while

switch(stare){

case 0:Acc.addElement(sir.substring(poz,sir.length()));break;

case 1:Rej.addElement(sir.substring(poz,sir.length()));break;

default:Maybe.addElement(sir.substring(poz,sir.length()));break; }

stare++;

}//while

} catch (IOException e) {}

pozitie=0; //incep cel de-al 2-lea fisier

poz=0;

stare=0;

try { //citesc matricea HMM din fisierul bigrame

BufferedReader br = new BufferedReader(in2);

while ((sir = br.readLine()) != null) {

poz=sir.length();

if(stare!=0) {

for(i=5;i>=0;i–){

pozitie=sir.lastIndexOf("\t",poz-1);

Float numar=new Float(sir.substring(pozitie,poz));

tranzitii[linie][i]=numar.floatValue();

poz=pozitie;

}

linie++; //trec la a linia urmatoare

}

else stare=1;

}//while

} catch (IOException e) {}

try { //citesc testul neadnotat

BufferedReader br = new BufferedReader(in3);

while ((sir = br.readLine()) != null) {

if(sir.indexOf("<Utt")!=-1){

s=new String ();

while ( ((sir = br.readLine()) != null) && (s.indexOf("</Utt>")==-1)){

s=s.concat(sir);

}

int gata=s.indexOf("<");//elimin tagul de la sfarsit

s=s.substring(0,gata);

s=s.toLowerCase();

nr_tag++;

for(i=0;i<Maybe.size();i++){

if (s.indexOf((Maybe.elementAt(i)).toString())!=-1){

if(s.indexOf("not")!=-1) tag[nr_tag]=1;

else tag[nr_tag]=4;

checked=1;

break;

}

}

if(checked==0){

if (s.compareTo((Acc.elementAt(0)).toString())==0){ tag[nr_tag]=2;

checked=1;

}

}

if(checked==0){

for(i=1;i<Acc.size();i++){

if (s.indexOf((Acc.elementAt(i)).toString())!=-1){

if(s.indexOf("but")!=-1) tag[nr_tag]=0;

else tag[nr_tag]=2;

checked=1;

break;

}

}

}

if(checked==0){

if (s.compareTo((Rej.elementAt(0)).toString())==0){ tag[nr_tag]=3;

checked=1;

}

}

if(checked==0){

for(i=1;i<Rej.size();i++){

if (s.indexOf((Rej.elementAt(i)).toString())!=-1){

if(s.indexOf("but")!=-1) tag[nr_tag]=1;

else tag[nr_tag]=3;

checked=1;

break;

}

}

}

if(checked==0) tag[nr_tag]=5;

else checked=0;

}//if mare

}//while

for(i=1;i<=nr_tag;i++) tag[i-1]=tag[i];// pun tagurile incepand cu val 0

tag[nr_tag]=5;//iar ultima o las pe post de end!

//nr_tag–;//pun capatul corect

} catch (IOException e) {}

in1.close();

in2.close();

in3.close();

}

public int getNr_tag(){return nr_tag;}

public int[] getTag(){return tag;}

public float[][] getMat(){return tranzitii;}

}

Viterbi.java

package Recunoastere;

import java.util.*;

import java.io.*;

public class Viterbi

{

private double prob_finala;

public Viterbi(){}

public int[] Viterbi(int nr_tag,int []tag,int nr_stari,float[][]tranzitii)throws IOException{

double scor=0;

int val_tag;//ca sa stiu cu cat inmultesc…1 sau 0..adik probab ca

// propozitia sa fie de tipul s'

double max=0;//prob max…de a obtine rezultatul

int index_max=0;//imi trebuie ca sa retin tipul ultimei propozitii

int i,j,k;//iteratori

double [][] viterbi=new double[nr_stari+2][nr_tag+2];//mat viterbi

int [][]back=new int[nr_stari+2][nr_tag+2];//trace-ul

int []rezultat=new int[nr_tag+2];

viterbi[0][0]=1.0;//initializare algoritm

for(i=0;i<nr_tag;i++)

for (j=0;j<nr_stari;j++)

for(k=0;k<nr_stari;k++){

if(tag[i]==k) val_tag=1;

else val_tag=0;

scor=viterbi[j][i]*tranzitii[j][k]*val_tag;

if((viterbi[k][i+1]==0) || (scor>viterbi[k][i+1])){

viterbi[k][i+1]=scor;

back[k][i+1]=j;

}

}

for(i=0;i<nr_stari;i++)

if(max<viterbi[i][nr_tag]){

max=viterbi[i][nr_tag];

index_max=i;

}

rezultat[nr_tag-1]=index_max;

prob_finala=max;

for(i=nr_tag;i>1;i–){

rezultat[i-2]=back[index_max][i];

}

/*

FileWriter out=new FileWriter("test.txt");

for(i=0;i<nr_stari;i++){

for(j=0;j<nr_tag+1;j++) {

Double nr=new Double(viterbi[i][j]);

out.write(nr.toString()+"\t\t");

}

out.write("\n");

}

for(i=0;i<nr_stari;i++){

for(j=0;j<nr_tag+1;j++) {

out.write(back[i][j]+" ");

}

out.write("\n");

}

for(i=0;i<nr_tag;i++) out.write(rezultat[i]+" ");

out.write("\n\n");

for(i=0;i<nr_tag;i++) out.write(tag[i]+" ");

out.close();

*/

return rezultat;

}

public double getProbability(){return prob_finala;}

}

Scriere.java

package Recunoastere;

import java.util.*;

import java.io.*;

public class Scriere

{

public Scriere(){}

final public void scriere(int [] v,String fis1,String fis2) throws IOException

{

FileReader in = new FileReader(fis1);

FileWriter out = new FileWriter(fis2);

int nr_tag=0;

String sir=new String();

try { //citesc testul neadnotat

BufferedReader br = new BufferedReader(in);

while ((sir = br.readLine()) != null) {

if(sir.indexOf("<Utt")!=-1){

int tag=sir.indexOf("\" Answer");

int fin=sir.length();

String s1=sir.substring(0,tag);

String s2=sir.substring(tag,fin);

switch(v[nr_tag]){

case 0:s1=s1.concat("Accept Part");break;

case 1:s1=s1.concat("Reject Part");break;

case 2:s1=s1.concat("Accept");break;

case 3:s1=s1.concat("Reject");break;

case 4:s1=s1.concat("Maybe");break;

default:s1=s1.concat("None");

}

s1=s1.concat(s2);

out.write(s1);

nr_tag++;

}

else out.write(sir);

}

in.close();

out.close();

}catch (IOException e){}

}

}

Pachetul Statistica

Statistica.java

package Statistica;

import java.awt.*;

import java.io.*;

import java.awt.event.*;

class Statistica extends Frame

{

public Statistica() {

addWindowListener(new WindowAdapter() {

public void windowClosing(WindowEvent e) {

dispose();

System.exit(0);

}

});

}

public static void main(String args[]) throws IOException

{

String fis1=args[0];

String fis2=args[1];

String fis3=args[2];

FileWriter out=new FileWriter(fis3);

FileReader in1=new FileReader(fis1);

FileReader in2=new FileReader(fis2);

Citire c1=new Citire();

Citire c2=new Citire();

c1.count(in1);

c2.count(in2);

int l1=c1.getSize();

int l2=c2.getSize();

if(l1!=l2) {

System.out.println("Eroare…nu s-a folosit acelasi fisier");

System.exit(1);

}

Comparare comp=new Comparare(c1.getVector(),c2.getVector(),l1);

comp.comp();

out.write("Fisierul adnotat automat \""+fis1+"\" contine: "+l1+" taguri, dintre care:\n");

if(c1.getAcc()!=0) out.write("Accept "+c1.getAcc()+"\n");

if(c1.getRej()!=0) out.write("Reject "+c1.getRej()+"\n");

if(c1.getAccPart()!=0) out.write("Accept Part "+c1.getAccPart()+"\n");

if(c1.getRejPart()!=0) out.write("Reject Part "+c1.getRejPart()+"\n");

if(c1.getMaybe()!=0) out.write("Maybe "+c1.getMaybe()+"\n");

if(c1.getNone()!=0) out.write("None "+c1.getNone()+"\n\n\n");

out.write("Fisierul adnotat de catre program \""+fis2+"\" contine: "+l2+" taguri, dintre care:\n");

if(c2.getAcc()!=0) out.write("Accept "+c2.getAcc()+"\n");

if(c2.getRej()!=0) out.write("Reject "+c2.getRej()+"\n");

if(c2.getAccPart()!=0) out.write("Accept Part "+c2.getAccPart()+"\n");

if(c2.getRejPart()!=0) out.write("Reject Part "+c2.getRejPart()+"\n");

if(c2.getMaybe()!=0) out.write("Maybe "+c2.getMaybe()+"\n");

if(c2.getNone()!=0) out.write("None "+c2.getNone()+"\n\n\n");

out.write("In total au fost adnotate corect: "+comp.getCorect()+" taguri, reprezentand ");

out.write(comp.getPCorect()+" din numarul total de taguri\n");

out.write("Dintre acestea,au fost recunoscute corect:\n");

if(comp.getAcc()!=0) out.write(comp.getAcc()+" taguri Accept; reprezentand "+comp.getPA()+"\n");

if(comp.getRej()!=0) out.write(comp.getRej()+" taguri Reject; reprezentand "+comp.getPR()+"\n");

if(comp.getAccPart()!=0) out.write(comp.getAccPart()+" taguri Accept Part; reprezentand "+comp.getPAPart()+"\n");

if(comp.getRejPart()!=0) out.write(comp.getRejPart()+" taguri Reject Part; reprezentand "+comp.getPRPart()+"\n");

if(comp.getMaybe()!=0) out.write(comp.getMaybe()+" taguri Maybe; reprezentand "+comp.getPM()+"\n");

if(comp.getNone()!=0) out.write(comp.getNone()+" taguri None; reprezentand "+comp.getPN()+"\n\n\n");

in1.close();

in2.close();

out.close();

}

}

Citire.java

package Statistica;

import java.util.*;

import java.io.*;

import org.xml.sax.*;

import org.xml.sax.helpers.*;

public class Citire extends AbstractXMLParser

{

private Vector agreement=new Vector();//vectorul in care voi salva atributele

private int acc=0,rej=0,maybe=0,accpart=0,rejpart=0,none=0;

//numarul de atribute de tipul Accept/Reject/Maybe…

public Citire(){

super();

}

public void count(FileReader fis){

try

{

parser.parse(new InputSource(fis));

}catch (Exception e)

{

e.printStackTrace();

}

return;

}

final public void startElement(final String namespace,final String localname,final String type,final Attributes attributes) throws SAXException {

if (type.compareTo("Utt")==0) {

String name=attributes.getValue("Agreement");

agreement.addElement(name);

if (name.compareTo("Accept Part")==0) accpart++;

if (name.compareTo("Reject Part")==0) rejpart++;

if (name.compareTo("Accept")==0) acc++;

if (name.compareTo("Reject")==0) rej++;

if (name.compareTo("Maybe")==0) maybe++;

if (name.compareTo("None")==0) none++;

}

}

public Vector getVector(){return agreement;}

public int getSize(){return agreement.size();}

public int getAcc(){return acc;}

public int getRej(){return rej;}

public int getMaybe(){return maybe;}

public int getAccPart(){return accpart;}

public int getRejPart(){return rejpart;}

public int getNone(){return none;}

}

AbstractXMLParser

package Invatare;

import java.io.*;

import org.xml.sax.*;

import org.xml.sax.helpers.*;

import javax.xml.parsers.*;

public class AbstractXMLParser implements ContentHandler,DTDHandler,EntityResolver

{

protected XMLReader parser;

public AbstractXMLParser()

{

try

{

SAXParserFactory saxParserFactory=SAXParserFactory.newInstance();

SAXParser saxParser=saxParserFactory.newSAXParser();

parser=saxParser.getXMLReader();

parser.setContentHandler(this);

parser.setDTDHandler(this);

parser.setEntityResolver(this);

}catch (Exception e)

{

e.printStackTrace();

}

}

public void startElement(final String namespace,final String localname,final String type,final Attributes attributes) throws SAXException {}

public void endElement(final String namespace,final String localname,final String type) throws SAXException {}

public void characters( final char[] ch, final int start, final int len ) {}

public void endDocument() throws SAXException {}

public void endPrefixMapping(final String prefix) throws SAXException {}

public void ignorableWhitespace(final char[] ch, final int start,final int length) throws SAXException {}

public void processingInstruction ( final String target, final String data ) throws SAXException {}

public void setDocumentLocator( final org.xml.sax.Locator locator ) {}

public void skippedEntity( final String name ) throws SAXException {}

public void startDocument() throws SAXException {}

public void startPrefixMapping( final String prefix, final String uri ) throws SAXException {}

public void notationDecl(String name, String publicId, String systemId) {}

public void unparsedEntityDecl(String name, String publicId, String systemId, String notationName) {}

public InputSource resolveEntity(String publicId, String systemId) {

return new InputSource(new StringReader(""));

}

}

Comparare.java

package Statistica;

import java.util.*;

import java.io.*;

import org.xml.sax.*;

import org.xml.sax.helpers.*;

public class Comparare extends AbstractXMLParser

{

private Vector v1=new Vector();//vectorul din fis adnotat manual

private Vector v2=new Vector();//vectorul din fis adnotat prin program

private int lung;//lungimea vectorilor

private int corect=0;//cate sunt puse corect

private int acc=0,rej=0,maybe=0,accpart=0,rejpart=0,none=0;//taguri corecte

private float pcorecte=0,pa=0,pr=0,pm=0,papart=0,prpart=0,pn=0;//procentele atributelor

public Comparare(Vector vect1,Vector vect2,int lungime){

v1=vect1;

v2=vect2;

lung=lungime;

}

public void comp(){

for(int i=0;i<lung;i++)

if(v1.elementAt(i).toString().compareTo(v2.elementAt(i).toString())==0){

corect++;

if ((v1.elementAt(i).toString()).compareTo("Accept Part")==0) accpart++;

if ((v1.elementAt(i).toString()).compareTo("Reject Part")==0) rejpart++;

if ((v1.elementAt(i).toString()).compareTo("Accept")==0) acc++;

if ((v1.elementAt(i).toString()).compareTo("Reject")==0) rej++;

if ((v1.elementAt(i).toString()).compareTo("Maybe")==0) maybe++;

if ((v1.elementAt(i).toString()).compareTo("None")==0) none++;

}

pcorecte=(float)corect/lung;

pa=(float)acc/corect;

pr=(float)rej/corect;

pm=(float)maybe/corect;

pn=(float)none/corect;

papart=(float)accpart/corect;

prpart=(float)rejpart/corect;

}

public float getCorect(){return corect;}

public float getPCorect(){return pcorecte;}

public int getAcc(){return acc;}

public int getRej(){return rej;}

public int getMaybe(){return maybe;}

public int getAccPart(){return accpart;}

public int getRejPart(){return rejpart;}

public int getNone(){return none;}

public float getPA(){return pa;}

public float getPR(){return pr;}

public float getPM(){return pm;}

public float getPN(){return pn;}

public float getPAPart(){return papart;}

public float getPRPart(){return prpart;}

}