Reprezentarea Cunostintei Folosind Distanta Normalizata Google (ngd)

Politehnica

Reprezentarea Cunostintei Folosind Distanta Normalizata Google (ngd)

Byadmin ianuarie 1, 2024

CUPRINS

Introducere

1. Reprezentarea cunoștinței

1.1 Scheme de reprezentare a cunoștințelor

1.2 Rețele semantice

2. Distanța normalizată Google

3. Extragerea relațiilor semantice folosind Google

4. Introducere în Word-Net

4.1 Matricea lexicală

4.2 Relații între synset-uri

5. Căutarea sinonimelor folosind Google

6. Tehnici folosite

6.1 Google Custom Search

6.2 UPGMA

6.2.1 Algoritm

7. Calcularea similarităților semantice folosind NGD – Platforma de Test

7.1 Prezentarea platformei experimentale

7.2 Funcționalități

8. Testare și verificare

8.1. Ordonarea cuvintelor în limba engleză

Test 1

Test 2

Test 3

8.2. Ordonarea cuvintelor în limba română

Test 1

Test 2

Test 3

Concluzii

Bibliografie

Introducere

Domeniul inteligenței artificiale se ocupă cu crearea sistemelor inteligente care sunt capabile să invețe fară ajutor uman cu scopul de a se îmbunătăți permanent.

Reprezentarea cunoștiinței este o subarie a inteligenței artificiale care se ocupă cu înțelegerea, design-ul si implementarea modurilor de reprezentare a informației pentru ca programele computerizate sa se comporte inteligent. Din această categorie fac parte programele de traducere automată, roboții antropomorfi, programele de jucat sah, calculatoarele care pot dialoga într-un limbaj similar celui uman, etc.

Reprezentarea cunoștințelor reprezintă un domeniu important în cadrul inteligenței artificiale. Multe dintre problemele pe care le dorim rezolvate de calculatoare necesită cunoștințe detaliate despre lume. Lucrurile pe care un sistem inteligent ar trebui sa fie capabil să le reprezinte sunt: proprietățile obiectelor, categoriile de obiecte, relațiile dintre obiecte, evenumente, cauze și efecte. O astfel de reprezentare poartă numele de ontologie.

În domeniul inteligenței artificiale există două abordări [6]:

Abordarea conexionistă se bazează pe ideea că inteligența este emergentă rețelelor neuronale deosebit de complexe.

Abordarea simbolică consideră că orice sistem inteligent este un sistem fizic de prelucrare a simbolurilor.

Una dintre definițiile inteligenței artificiale este că aceasta reprezintă studiul comportamentului inteligent. Reprezentarea cunoștinței si raționamentul reprezintă, deci, o parte a inteligenței artificiale care se concentrează pe modul în care agentul folosește ce cunoaște și decide ce să facă pe baza acestor cunoștințe. Cu alte cuvinte reprezentarea cunoștinței se referă la manipularea unor simboluri formale pentru a reprezenta o colecție de propoziții. Raționamentul, pe de altă parte este manipularea a acestor simboluri care formeaza o colecție pentru a produce noi reprezentări.

Reprezentarea cunoștinței

Cercetările în domeniul reprezentării cunoștinței a început în jurul anului 1958, când cercetătorii au investigat modalitatea în care un calculator ar putea sa reprezinte și să folosească cunoștințele “de bun simț ” pe care oamenii le folosesc. Pentru oameni ințelesul următoarei propoziții “Am văzut Statuia Libertății zburând deasupra New-York-ului!” în sensul că vorbitorul zbura și nu statuia, este instantaneu, in schimb pentru un calculator acesta este foarte greu de realizat[8].

Reprezentarea cunoașterii presupune existența unor fapte, adică adevăruri într-o anumită situație sau univers de discurs relevant și apoi reprezentarea faptelor într-un formalism ales. Mai exact, faptele sunt lucrurile pe care vrem să le reprezentăm, iar reprezentările lor sunt lucrurile pe care le vom putea manipula efectiv.

Calculatoarele și mințile umane sunt exemple de sisteme de simboluri fizice. Un simbol este un model semnificativ care poate fi manipulat. Exemple de simboluri sunt cuvinte scrise, fraze, gesturi, semne pe hârtie, sau secvențe de biți. Un sistem de simboluri crează, copiază, modifică și distruge simboluri. În esență un simbol este unul dintre modelele manipulate ca unitate de către un sistem de simboluri [8].

Un agent poate manipula sistemele simbolice fizice pentru a modela lumea. Un model al unei lumi este o reprezentare a ce este adevărat în acea lume. Mediul nu trebuie să fie modelat la nivelul cel mai detaliat. Toate modelele sunt abstracțiuni; ele reprezintă doar o parte din mediu, multe dintre detalii ne fiind luate în considerare. Un agent poate avea un model foarte simplist al lumii (mediului), sau poate avea un model foarte detaliat. Nivelul de abstractizare oferă o ordonare parțială de abstractizare. O abstractizare de nivel inferior include mai multe detalii decât o abstractizare de nivel superior. Un agent poate avea mai mutle modele, chiar contradictorii ale unei lumi. Modelele sunt evaluate nu după faptul dacă acestea sunt corecte sau nu, ci după faptul dacă aceste sunt utile [8].

Manipularea simbolurilor pentru a produce o activitate poartă numele de raționament.

Plecând de la următoarele afirmații: „Andrei este prieten cu Mihai” și “Mihai vine la petrecere”, putem face următoarea afirmație: ”Un prieten de-al lui Andrei vine la petrecere”. Acest exemplu este o formă de raționament deoarce ultima propoziție reprezintă o concluzie logică a informaților ce reies din primele două propoziții. Putem spune astfel, că raționamentul este o metodă de calcul ce folosește simboluri.

Scheme de reprezentare a cunoștințelor

Cunoașterea este informația despre un domeniu care poate fi folosită pentru a rezolva probleme din acel domeniu. Pentru a rezolva mai multe probleme este nevoie de mai multă cunoaștere, iar această cunoaștere trebuie reprezentată în calculator. Ca parte a proiectării unui program care să rezolve probleme, trebuie să definim mai întâi cum poate fi reprezentată cunoașterea. O schemă de reprezentare a cunoștințelor este folosită pentru rezolvarea problemei[8].

Programul rezultat trebuie să conțină suficente cunoștințe pentru a rezolva problemele din domeniu și trebuie să facă o inferență corectă a acestora în mod eficient. Rezultatele inferenței asupra bazei de cunoștințe ar trebui să corespundă acțiunilor sau observațiilor din lumea reală.

O schemă de reprezentare ideală ar trebui:

Să fie destul de complexă pentru a exprima cunoștințele necesare pentru a rezolva problema

Să fie compactă, să se concentreze asupra problemei.

Să aibă un set semantic bine definit

Să permită cunoștințelor noi să fie deduse din faptele deja stocate in baza de cunoștințe.

Tehnicile/schemele de reprezentare a cunoștințelor folosite în ziua de astăzi sunt:

Rețelele semantice

Frame-uri

Logica deductivă

Sisteme bazate pe reguli

În această lucrare vor fi prezentate rețele semantice, ca și tehnică de reprezentare a cunoștinței.

Rețele semantice

O rețea semantică este o tehnică a reprezentării cunoștinței. Aceasta este reprezentată sub forma unui graf orientat, ale cărui arce leagă vârfuri etichetate.

Rețelele semantice au fost pentru prima dată dezvoltate de Quillian în anul 1968. Acesta a pornit de la caracterul de asociativitate al memoriei umane. Un eveniment sau un obiect poate fi modelat cu ajutorul unui graf. Astfel o rețea semantică este un graf orientat și etichetat, primitivele reprezentaționale sunt nodurile și arcele. Atât nodurile și arcele sunt etichetate. Etichetele nodurilor pot fi: concepte, instanțe, valori și proceduri. Arcele sunt etichetate cu relații ce există între noduri [7].

Arcele pot fi de două tipuri:

Arce care unesc un nod concept de un nod instanță (este un/este o)

Arce care unesc două concepte dintre care unul îl cuprinde pe celălalt (subset)

Figura 1.1 Rețea semnantică

Arcele de tipul este-un corespund relației de apartenență, iar arcele de tipul subset corespund relației de incluziune. Deasemenea un arc de tip subset ii corespunde unei relații tranzitive.

Rețeaua semnatică descrisă în figura 1.1 poate fi folosită pentru reprezentarea unor fapte ca:

Fapt 1: “persoanele sunt mamifere”

Fapt 2: “persoanele de sex feminin sunt persoane”

Fapt 3: “Jill este o persoană”

Un cuvânt reprezintă asocierea dintre un concept lexicalizat și o formă lexicală care joacă un rol sintactic. Organizarea conceptelor pe care cuvintele le pot exprima se poate face prin intermediul unei matrice lexicale care stabilește o corespondență între formele și sensurile cuvintelor.

Distanța normalizată Google

Rudi Cilibrasi și Paul Vitanyi au demonstrat că este posibil sa extragi înțelesul unui cuvânt din paginile web. Pentru a obține acest lucru, ei se bazează pe numărul de pagini web care sunt returnate de către o căutare Google a unui anumit cuvânt si asociază acest număr cu probabilitatea de apariție a acelui cuvânt într-o anumită pagină web. Astfel, în funcție de probabilitățile de apariție se poate corela un cuvânt cu sensul altui cuvânt. Mai mult de atât, ei au dezvoltat o funcție distanță care calculează cât de apropiate sunt cele două cuvinte între ele.

Rudi Cilibrasi și Paul Vitanyi: “Am găsit o metodă care să extragă în mod automat înțelesul cuvintelor si al frazelor din paginile web folosind motorul de căutare Google . Abordarea este nouă în domeniul său, prin simplitatea implementării, și evidențierea fundamentelor ontologice.”[1]

Pentru a da calculatoarelor un plus de inteligență, o idee ar fi să le facem pe acestea sa înteleagă sensul cuvintelor ; altfel spus, să stabilim o relație semantică între denumirile diferitor obiecte. În acest demers au fost realizate proiectele Cyc și WordNet.

Cyc este un proiect de inteligență artificială, care încearcă sa adune o ontologie completă și o bază de cunoștințe a cunoștințelor de zi cu zi cu sens comun, cu scopul de a permite aplicațiilor de inteligență artificială de a efectua un raționament uman [2]. WordNet este o bază de date lexicală pentru limba engleză. Grupează cuvintele din limba engleză în seturi de sinonime numite synsets, prevede definiții scurte, generale, și înregistrează diferitele relații semantice între aceste seturi de sinonime. Scopul este dublu: de a realiza un dicționar care este mult mai intuitiv de utilizat, și de a sprijini analiza automată a textului și a aplicațiilor de inteligență artificială.[3]

Progresul tehnologiei informației a făcut posibilă stocarea și accesarea cantităților mari de date. Cu toate acestea, din moment ce oamenii gândesc în moduri diferite și folosesc terminologii diferite pentru stocarea informației, devine greu accesul la toate referințele despre o anumită idee sau despre un anumit concept.

Când motorul de căutare Google este folosit pentru a căuta un anumit cuvânt x, acesta afișează numărul de pagini care conțin cuvântul căutat. Raportul dintre numărul de pagini rezultat în urma căutării cuvântului respectiv și numărul de pagini indexate de către Google reprezintă probabilitatea de apariție a cuvântului x într-o pagina web. Cilibrasi și Vitanyi au folosit aceasta probabilitate pentru a extrage înțelesul cuvintelor din paginile web. Dacă cuvântul y are o probabilitate mare de apariție condiționată de cuvântul x într-o anumită pagină, putem ajunge la concluzia că cele două cuvinte sunt legate. Mai mult, cu cât probabilitatea de apariție condiționată este mai mare cu atât relația dintre cele două cuvinte este mai apropiată. În altă ordine de idei, cuvântul x îi dă un anumit înțeles cuvântului y și viceversa.[1]

Funcția distanță Google normalizată introdusă de Cilibrasi și Vitanyi măsoară cât de apropiat este cuvântul x față de cuvântul y pe o scară de la 0 la infinit. O distanță egală cu 0 indică practic că cele două cuvinte sunt la fel din punct de vedere al înțelesului. Pentru două cuvinte independente distanța normalizată este egală cu 1. O distanță egală cu infinit se produce atunci când cele două cuvinte nu apar niciodată împreună.[1]

Cilibrasi și Vitanyi au arătat că dacă este o pagină web și este termenul căutat, atunci putem spune ca , astfel Google întoarce o pagină ca rezultat a căutării termenului . Un eveniment reprezintă un set de pagini web returnate de către Google ca urmare a căutării unui anumit termen. De asemenea dacă este termenul de căutare, autorii lucrării „Auusă de Cilibrasi și Vitanyi măsoară cât de apropiat este cuvântul x față de cuvântul y pe o scară de la 0 la infinit. O distanță egală cu 0 indică practic că cele două cuvinte sunt la fel din punct de vedere al înțelesului. Pentru două cuvinte independente distanța normalizată este egală cu 1. O distanță egală cu infinit se produce atunci când cele două cuvinte nu apar niciodată împreună.[1]

Cilibrasi și Vitanyi au arătat că dacă este o pagină web și este termenul căutat, atunci putem spune ca , astfel Google întoarce o pagină ca rezultat a căutării termenului . Un eveniment reprezintă un set de pagini web returnate de către Google ca urmare a căutării unui anumit termen. De asemenea dacă este termenul de căutare, autorii lucrării „Automatic Meaning Discovery Using Google ”, notează evenimentul generat de și definesc . Probabilitatea a evenimentului este numărul de pagini web generate de acest eveniment raportat la numărul total de pagini web indexate de către Google. Astfel spus Se definește evenimentul comun ca mulțimea paginilor web returnate de către Google în urma căutării termenilor și . Probabilitatea este numărul paginilor web care conțin atât evenimentul cât și evenimentul raportat la numărul total de pagini web returnate de către Google. Pornind de la cele enunțate mai sus, se poate defini astfel probabilitatea evenimentelor condiționate ca fiind egală cu raportul dintre și ; [1]

În acest moment se poate defini funcția distanță ca:

S-a demonstrat că această distanță nu dă rezultate bune. Un motiv ar fi că diferențele dintre probabilitățile mici de apariție au o importanță crescută cu cât valorile probabilităților respective sunt mai mici. Pe de altă parte s-a observat că două noțiuni care au probabilitățile de apariție foarte mici având o distanță sunt mai puțin similare decât două noțiuni care au probabilități de apariție mai mari și au aceiași distanță . Pentru prima problemă, R. Cilibrasi și P. M. B. Vitanyi, au logaritmat negativ cele două probabilități[1]:

Pentru a rezolva a doua problemă se normalizează funcția distanță raportând-o la maximul dintre și , obținând astfel următoarea distanță normalizată:

pentru (sau ) și pentru (sau ). Când cei doi termeni și nu apar niciodată împreună. Dacă probabilitățile și sunt egale cu 0 atunci și probabilitățile condiționate și sunt egale cu 0. Reciproca nu este întotdeauna adevărată.[1]

După cum se observă din formula , probabilitățile condiționate sunt independente de numărul total de pagini indexate de către Google. Astfel acestea pot fi înlocuite cu numărul de pagini returnate de către Google în urma căutării termenilor și . Se definește așadar frecvența ca fiind egală cu numărul paginilor web ce conțin cuvântul , iar frecvența fiind egală cu numărul de pagini web ce conțin cuvintele și ; și [1].

Realizând înlocuirile de rigoare în ecuația (1.3) se obține funcția distanței normalizate Google[1]:

Din (1.4) se poate observa că:

este nedefinită pentru ;

pentru sau și ; și

altfel

Un exemplu de calculare a distanței normalizate Google este următorul:

O căutare pe Google a cuvântului “football” a returnat 1.650.000.000 de rezultate, iar o căutare a cuvântului “player” a returnat 1.300.000.000 de rezultate. O căutare a ambelor cuvinte “football player” a returnat 669.000.000 de pagini web. Având în vedere că numărul total de pagini web indexate de către Google conform statisticilor din 2011 este de 46 de miliarde putem calcula distanța normalizată Google între cuvintele “player” și “football” după cum urmează:

Conform lucrării „Automatic Meaning Discovery Using Google ” NGD are următoarele proprietăți[1]:

Funcția NGD ia valori între 0 și ;

Dacă sau dacă dar , atunci . Altfel spus cuvintele și au același sens.

Dacă frecvența , atunci pentru fiecare termen avem , și .

Funcția NGD este întotdeauna pozitivă si pentru orice . Pentru fiecare pereche avem , altfel spus funcția NGD este simetrică. Cu toate acestea nu se satisface condiția pentru orice . NGD nu satisface nici inegalitatea triunghiului pentru oricare . De exemplu, alegem și . Atunci, și . Rezultă că și , nerespectând astfel inegalitatea triunghiului pentru .

Funcția NGD este invariantă. Este foarte important ca, în cazul în care numărul de pagini indexate de Google crește suficient de mult, numărul paginilor care conțin anumiți termeni dați să fie egal cu a o fracțiune fixată din . Astfel dacă își dublează valoarea la fel și valoarea frecvențelor se dublează. Funcția NGD trebuie să devină stabilă atunci când numărul crește pentru ca relația semantică dintre termenii de căutare să fie obiectivă.

Extragerea relațiilor semantice folosind Google

În 2011 Google indexa aproximativ 46 de miliarde de pagini web. Conform statisticilor acest număr continuă să crească pe zi ce trece. Practic probabilitatea de apariție a unui termen returnat de o căutare Google calculată ca numărul de pagini în care apare acel cuvânt raportat la numărul total de pagini indexate de către Google, este frecvența cu care acel termen este folosit în societate. Bazându-se pe această teorie, R. Cilibrasi și P. M. B. Vitanyi arată că relațiile reprezentate de distanța normalizată Google capturează aproximativ adevărata relație semantică dintre termenii căutați.

R. Cilibrasi și P. M. B. Vitanyi au introdus conceptul de distanță normalizată Google (NGD) pornind de la investigarea distanței compresiei normalizate (NCD) într-o mare varietate de domenii cum ar fi genomica, evoluția limbii, literatură, etc. În urma experimentelor s-a observat că un compresor nu aplică cunoștințe externe compresiei, în sensul că trebuie să învețe același lucru pentru fiecare fișier (sau obiect). Astfel, folosind baza de date Google a fost creat un pseudo-compresor bazat pe NCD, iar noua distanța a fost numită Normalized Google Distance sau NGD[1].

Experimentele sugerează că această distanță nouă are puncte tari și puncte slabe condiționate de oamenii care au creat milioanele de pagini web de pe internet. Distanța normalizată Google este foarte adaptabilă și aproape fără restricții în ceea ce privește domeniul, dar în același timp este imprecisă și versatilă în ceea ce privește comportamentul[1].

În urma experimentelor autorii lucrării „Automatic Meaning Discovery Using Google ” au demonstrat că NGD dă rezultate mai bune decât NCD. Astfel pornind de la fraza The quick brown fox jumps over the lazy dog, autorii au calculat distanța compresiei normalizate și distanța normalizată Google între secvența de cuvinte ”the quick brown” și fiecare cuvânt compus din trei litere ce aparține vocabularului limbii engleze pentru a vedea care dintre acestea are probabilitatea mai mare de a continua secvența de cuvinte respectivă. S-a constatat că în urma calculării distanței dintre secvența de cuvinte ”the quick brown” și fiecare cuvânt de trei litere folosind formula NCD, distanța minimă a fost egală cu 0,61 pentru cuvintele: own, row, she, the, iar folosind formula NGD cea mai mică distanță a fost de 0,53 pentru cuvântul fox [1].

Astfel se observă că NCD se bazează pe o interpretare literală a datelor în timp ce NGD interpretează datele ca denumiri a unor obiecte abstracte care dobândesc sens/înțeles din vastitatea de cunoștințe. Se poate spune că NCD ignoră sensul mesajului, în timp ce NGD se concentrează pe acesta[1].

Introducere în Word-Net

WordNet este o bază de date lexicală în limba engleză de mari dimensiuni. Substantive, verbe, adjective și adverbe sunt grupate în seturi de sinonime cognitive (synset-uri), fiecare exprimând un concept diferit. Synset-urile sunt interconectate din punct de vedere al conceptului semantic si al relațiilor lexicale.

WordNet se aseamană superficial cu un tezaur, în care cuvintele sunt grupate in funcție de semnificația lor. Cu toate acestea, există câteva distincții importante. În primul rând, interconectările din WordNet nu formează doar cuvinte – șiruri de litere – ci sensuri specifice ale cuvintelor. Altfel spus, cuvinte care se găsesc in apropiere unul de altul in rețea sunt diferite din punct de vedere semantic. În al doilea rând, WordNet etichetează relațiile semantice dintre cuvinte, acolo unde grupurile de cuvinte din tezaur nu urmeaza nici un patern explicit.

Matricea lexicală

Semantica lexicală începe cu o recunoaștere a faptului că un cuvânt este o asociație convențională între un concept lexicalizat și o declarație care joacă un rol sintactic. Această definiție a “cuvântului” ridică cel puțin trei clase de probleme pentru cercetare. În primul rând, ce fel de enunțuri intra în aceste asociații lexicale? În al doilea rând, care este natura și organizarea conceptelor lexicalizate pe care cuvintele le pot exprima? În al treilea rând, ce rol sintactic îl joacă cuvinte diferite?

În Tabelul 4.1 este prezentată matricea lexicală. Cuvintele sunt dispuse pe coloane iar sensurile cuvantului sunt dispuse pe rânduri. Intrarea dintr-o celulă a matricei implică faptul că pe coloana respectivă cuvântul poate fi folosit (într-un context adecvat) pentru a exprima sensul exprimat în acel rând. Astfel, intrarea E1, 1 implică faptul că cuvântul F1 pot fi folosit pentru a exprima sensul M1. Dacă există două intrări în aceeași coloană, cuvântul este polisemantic, în cazul în care există două intrări în același rând, cele două cuvinte sunt sinonime (relativ la un context).[12]

Tabelul 4.1

Mapările între cuvinte și sensuri sunt many to many – unele cuvinte pot avea mai multe sensuri diferite, iar unele sensuri poate fi exprimata prin mai multe cuvinte diferite. Două probleme dificile de lexicografie, polisemia și sinonimie, pot fi privite ca aspecte complementare ale acestei cartografieri.

Pentru a simula o matrice lexicală este necesar să avem un mod de a reprezenta atât cuvintele cât și sensurile într-un calculator. Inscripționarea poate oferi o solutie satisfacatoare pentru cuvinte, dar cum și sensul ar trebui să fie reprezentat se pune o întrebare esențială pentru orice teorie a semanticii lexicale. Lipsind o teorie psihologică adecvată, metodele dezvoltate de lexicografi poate oferi o soluție temporară: definițiile pot juca acelasi rol intr-o simulare cum sensurile cuvintelor joacă în mintea unui utilizator uman.

Cum ar trebui să fie reprezentate conceptele lexicalizate prin definiții într-o teorie a semanticii lexicale depinde de faptul dacă teoria este destinată pentru a fi constructivă sau pur și simplu diferențială. Într-o teorie constructivă, reprezentarea trebuie să conțină informații suficiente pentru a susține o construcție exactă a conceptului (fie o persoană sau o mașină). Cerințele unei teorii constructive nu sunt ușor de îndeplinit. Într-o teorie diferențială, pe de altă parte, semnificațiile pot fi reprezentate de orice simboluri care permit un teoretician să facă distincție între ele. Cerințele pentru o teorie diferențială sunt mai modeste, dar suficiente pentru construirea mapărilor dorite.[12]

Relații între synset-uri

Relația principala între cuvintele din WordNet este sinonimia, ca cea care se găseste între cuvintele “shut” și “close” sau între cuvintele “car” și “automobile”. Fiecare synset din WordNet este legat cu alte synset-uri printr-un număr mic de relații conceptuale. În conformitate cu o definiție, două expresii sunt sinonime dacă substituirea unul pentru celălalt nu se schimbă niciodată valoarea de adevăr a unei propoziții în care se face înlocuirea. Prin această definiție, sinonime adevărate sunt rare, în cazul în care acestea există, la toate.[13]

Cea mai frecventă relație între synset-uri este relația de subordonare / supraordonare (numită și hipernomie, hiponomie sau relație este-un). Această relație leagă synset-urile generale ca {mobilier, piesă de mobilier} la cele mai specifice ca {pat} și {pat supraetajat}. Astfel WordNet afirmă că gruparea mobilier include pat , care la rândul său include pat supra-etajat; inversa fiind reciprocă, conceptele pat și pat supra-etajat alcătuind categoria mobilier. Relația de hiponomie este tranzitivă în cazul în care un fotoliu este un fel de scaun, și dacă un scaun este un fel de mobilier, atunci un fotoliu este un fel de mobilier. WordNet distinge între tipuri (substantive comune) și cazuri (persoane specifice, țări și entități geografice). Astfel, fotoliu este un tip de scaun, Barack Obama este un exemplu de un președinte. Cazurile sunt întotdeauna noduri frunză (terminale) în ierarhiile lor.[13]

Figura 4.2. Relații de tipul este-un

Spre deosebire de sinonimie si antonimie, care sunt relațiile lexicale între cuvinte, hiponimia / hipernomia este o relație semantică între sensurile cuvantului: de exemplu, { arțar } este un fel de { copac }, iar { copac }este un fel de {plantă}. Un concept reprezentat de synset-ul {x, x’, …} este declarat a fi o hiponom al conceptului reprezentat de synset-ul {y, y ', …} dacă sunt acceptate construirea unor propoziții de genul ca x este un (fel de) y. Această relație poate fi reprezentată prin includerea în {x, x ', …} a unui pointer spre superordonata sa și includerea în {y, y', …} pointeri către hiponimul sau.[13]

Hiponimia este tranzitiva si asimetrică, și deoarece în mod normal există o singură subordonată, se generează o structură semantică ierarhică, în care un hyponym este poziționat sub superordonatul său. Astfel de reprezentații ierarhice sunt utilizate pe scară largă în construcția sistemelor de recuperare de informații, fiind numite sisteme de moștenire (Touretzky, 1986): un hiponim moștenește toate caracteristicile celui mai generic concept la care se adaugă cel puțin o caracteristică ce îl deosebește de superordonat si de toți ceilalți hiponimi ce fac parte din acel subordonat. De exemplu, arțar moștenește caracteristicile superordonatului său, copac, dar se distinge de alți arbori prin duritatea lemnului său, forma frunzelor sale, sau prin utilizarea sevei pentru sirop, etc. Această convenție prevede principiul central de organizare pentru substantivele din WordNet.[13]

O altă relație ce se găsește între synset-uri este cea de antonimie, care se dovedește a fi surprinzător de dificil de definit.Antonimul unui cuvânt x este uneori x-negat, dar nu întotdeauna. De exemplu, cuvintele bogați și săraci sunt antonime, dar pentru a spune că cineva nu este bogat nu înseamnă că acestea trebuie să fie săraci, mulți oameni se consideră nici bogați, nici săraci. Antonimia, care pare a fi o simplă relație simetrică, este de fapt destul de complexă.[13]

Antonimia este o relație lexicală între cuvinte, nu o relație semantică între sensurile cuvintelor. De exemplu, sensuri {rise, ascend} și {fall, descend} pot fi opuse conceptual, dar ele nu sunt antonime; cuvintele [rise/fall] sunt antonime la fel și cuvintele [ascend/descend]. Antonimia oferă un principiu central de organizare pentru adjective și adverbe în WordNet.[13]

Meronimia este un tip de relație parte-întreg și se află între synset-uri ca {chair} și {back, backseat} , {seat} și {leg}. Părțile sunt moștenite de la nodurile superioare: dacă un scaun are picioare, atunci și un fotoliu are picioare deasemenea. [13]

Un concept reprezentat de synset-ul {x, x ', …} este în relație de meronimie cu un concept reprezentat de synset-ul {y, y', …} sunt acceptate construirea unor propoziții de genul ca y este compus din x sau x face parte din y. Relația de meronimie este tranzitivă și asimetrică (Cruse, 1986). Se va presupune că noțiunea de parte a unui întreg poate fi o parte a unui concept de ansamblu.[13]

În figura de mai jos, Figura 4.3, sunt reprezentate relațiile care se stabiliesc între diferite synset-uri.

Figura 4.3 Reprezentarea relațiilor între synset-uri

Căutarea sinonimelor folosind Google

Internetul conține o mare cantitate de informații, care sunt diverse în ceea ce priveste conținutul si natura. Cu cantitatea imensă de informații care este disponibilă utilizatorilor prin intermediul sistemelor informatice, tehnici eficiente pentru localizarea de informații devin esențiale. Pentru a accelera procesul de căutare și recuperare a informațiilor relevante, este o practică comuna crearea unui index a informației căutate care este disponibilă de la diverse surse. De exemplu, dacă se caută o anumită informație într-un set de documente, documentele sunt mai întâi examinate pentru a identifica termeii de interes și in index este creat care asociază fiecare termen cu documentul în care apare. Ulterior, când un utilizator inițiază o cerere de căutare, termenii din cerere sunt comparați cu intrările din index, în scopul de a localiza documentele care conțin termenii solicitați.

Metodele convenționale de căutare nu pot găsi toate informațiile necesare din baza de date care conțin termenul căutat, deoarece termenul corespunzător poate fi scris greșit în unele dintre documente.

De aceea, metodele de ”căutare a similarităților” au fost dezvoltate recent în scopul de a ameliora această problemă. De exemplu, o tehnică cunoscută sub numele de ”stemming” implică reducerea cuvintelor pâna la rădacina acestora. Căutarea folosind această tehnică este îmbunățită, deoarece o căutare care folosește o formă a unui cuvânt localizează documentele care conțin toate formele acelui cuvânt. Această tehnică este aplicată tuturor cuvintelor care pot avea forme diferite. Cu toate acestea, regulile care sunt folosite pentru a reduce fiecare cuvânt la rădăcina sa gramaticală se aplică de obicei la o singură limbă. Prin urmare tehnica nu poate fi folosită în legătură cu documente care conțin cuvântul în alte limbi. Mai mult de atât, căutările returnate nu sunt limitate doar la documentele care conțin derivate ale rădăcinii cuvântului, ci includ și alte documente nedorite care conțin cuvinte care se potrivesc în mod aleatoriu cu rădăcina cuvântului căutat[15].

Atunci când căutam in motorul de căutare Google pentru cuvântul ”automobil”, motorul de căutare poate extinde căutarea pentru a include rezultate pentru cuvântul mașină, asta pentru că masină este un sinonim al cuvântului automobil. De asemenea atunci când scriem gresit un cuvânt in bara de căutare, de exemplu ”automobl”, Google poate sa corecteze automat eroarea de ortografie si să caute pentru pentru cuvântul ”automobil”.

În continuare dacă facem o căutare după cuvântul ”șofat” motorul de căutare Google poate extinde interogarea cu ajutorul procesului numit stemming care se uită la rădăcina cuvântului (șof-) și îi adaugă terminații comune, astfel, sunt incluse in căutare si cuvinte cum ar fi ”șofer”.[15]

Acest tip de extindere a căutării are scopul de a oferi rezultate de căutare mai bune. Însă această metodă de extindere a interogării s-ar putea să nu se întâmple în toate căutările.

Abordări specifice pentru extinderea interogării[15]:

Stemming

Corectarea erorilor de ortografie

Returnarea paginilor care includ rezultate ce conțin sinonime ale cuvântului căutat

Există câteva moduri diferite de a exitinde o interogare în Google folosind sinonime[14]:

Sinonimele unui cuvânt ar putea fi găsite într-un tezaur în care aceste sinonime au fost identificate de către experti, sau de o ontologie lexicală (vocabular organizat de cuvinte).

Sinonimele ar putea fi identificate de la alte intreogări de căutare, care sunt din punct de vedere sintatic similare cu interogarea originală.

O provocare pentru aceste metode este atunci când un cuvânt are mai multe sinonime, cu sensuri diferite. De exemplu, în interogarea ”Câti lei reprezintă 2 euro”, cuvântul ”lei” poate avea sensuri lexicale diferite (leu – animal, leu – moneda). În cazul în care interogarea se extinde pentru sensul leu= animal, se vor furniza rezultate irelevate pentru căutător. Un exemplu concret este evidențiat in imaginea de mai jos (Figura 5.1), unde căutarea cuvântului ”Pluto” poate întoarce pagini web în care termenul căutat are înțelesuri diferite[14].

Figura 5.1 – Exemplu de căutare

Tehnici folosite

În această secțiune vor fi descrise tehnologiile folosite în realizarea aplicației:

Google Custom Search

UPGMA

Google Custom Search

Google Custom Search[16], sau motorul de căutare personalizată, permite crearea unui motor de căutare pe bloguri sau site-uri web. Motorul poate fi configurat pentru a căuta atât pagini web cât și imagini. De asemenea se poate personaliza aspectul rezultatelor de căutare.

Există două cazuri principale de utilizare pentru Google Custom Search: se poate crea un motor de căutare care caută doar conținutul unui site web, sau se poate crea unul care se focusează pe un anumit subiect de pe mai multe site-uri.

Ce poate face Google Custom Search[16]:

Creează motoare de căutare personalizate care caută pe o anumită colecție de site-uri sau pagini;

Permite căutarea de imagini

Personalizează aspectul rezultatelor de căutare, inclusiv completările automate.

Pentru aplicația din această lucrare s-a creat un motor personalizat care va efectua căutarile pe paginile web ca Wikipedia ( www.wikipedia.com) și WordNet (http://wordnetweb.princeton.edu/perl/webwn ).

Mai jos este afișată interfața motorului de căutare personalizat (fig 6.1):

Figura 6.1 – Motorul de căutare personalizată

Mai jos (fig 6.2) este un print screen al rezultatelor căutării cuvântului “easy”. După cum se observă, în rezultatele returnate mai jos se gasesc si sinonimele cuvântului căutat.

Figura 6.2 – Rezultatele căutarii cuvântului ”easy”

UPGMA

UPGMA (Unweighted Pair-Group using Arithmetic Averages) este o metodă de reconstruire a arborilor filogenetici bazată pe distanță. Această metodă este adesea atribuită autorilor Sokal și Michener (1958), dar metoda folosită de aceștia este diferită de versiunea curentă a metodei UPGMA. Prima versiune a algoritmului a apărut în cartea autorilor Sneath și Sokal în 1973. Un arbore construit pe baza acestei metode este denumit fenogramă, deoarece inițial a fost folosit la reprezentarea gradului de similaritate fenotipică pentru un grup de specii, în cadrul taxonomiei numerice. Oricum, poate fi folosit în filogenia moleculară atunci când rata de substituție a genelor este mai mult sau mai puțin constantă. În special în cazul în care frecvența genelor este folosită în reconstrucția filogenetică, acest model produce arbori destul de buni, comparativ cu alte metode bazate pe distanță (Nei, 1983; Takezaki și Nei, 1996)[9].

În acest caz, o măsură a distanței care prezintă un coeficient mai mic de variație, pare să ducă la construirea de arbori cu o mai mare precizie, comparativ cu alte metode de determinare a distanței, chiar dacă nu respectă exact numărul de substituții genice (Takezaki și Nei, 1996). Prin UPGMA se pot construi arbori pentru evoluția în cadrul speciilor, cu toate că erori de topologie apar adesea când rata substituției genelor nu este constantă sau când numărul de gene sau nucleotide este mic.[9]

Algoritm

Algoritmul UPGMA[10] de reconstituire a arborilor construiește direcțiile filogenetice pe baza unei matrice de distanțe dată.

Tabel 6.3 Matricea de distanțe folosită în acest exemplu [10]

UPGMA este o metodă bazată pe distanță deci are nevoie de o matrice de distanță. Toate nodurile terminale se găsesc la distanță egală de rădăcină, UPGMA fiind o metodă ”ultrametrică”.

Pornind de la tabelul 3.1 putem parcurge algoritmul de reconstrucție a arborilor filogenetici. Algoritmul UPGMA constă într-o serie de pași :

Primul pas îl constă în determinarea celei mai mici distanțe din tabelul 3.1. Totodată se identifică secvențele ce urmează a fi grupate (aici BF).

Figura 6.4 a Determinarea minimului din matricea distanță

Figura 6.4 b Gruparea secvențelor B și F

Secvențele cu distanța cea mai mică între ele vor fi grupate ca în figura 6.4 b. Acestea vor pleca dintr-un ram comun.

Perechile trebuie să fie legate la o adâncime care este egală cu jumătatea distanței minime, (fig 6.4 b): .

Distanța dintre elementele unite este egală cu distanța minimă,

Se calculează distanțele medii dintre grupul identificat și celelalte secvențe

Figura 6.4 c Identificarea distanțelor dintre grupul BF și celelalte secvențe

În cazul de față se fac următoarele calcule:

Secvențele B și F sunt șterse din matricea originală și sunt înlocuite cu grupul BF. Rezultă următoarea matrice în care sunt introduse distanțele medii dintre grupul BF și celelalte secvențe, așa cum sunt calculate mai sus (figura 6.4d):

Figura 6.4 d Matricea rezultată în urma calculării distanțelor medii

Se reiau pașii 1-5: Se identifică distanța minimă din noua tabelă (figura 6.4d), , se grupează secvențele într-un ram comun și se calculează adâncimea noii ramuri (figura 6.5b). .

Figura 6.5 a Identificarea distanței minime

Figura 6.5 b Gruparea secvențelor în ram

Figura 6.5 c Identificarea distanțelor dintre grupul AD și celelalte secvențe

Pasul 5: se obține matricea din figura 6.5 d în urma calculării distanței medii dintre AD și celelalte secvențe:

Exemplu:

Figura 6.5 d Matricea rezultată în urma calculării distanțelor medii dintre grupul AD și celelalte secvențe

Se parcurg din nou primii 5 pași observând ca distanța minimă este cea dintre grupul BF și secvența G, adică 12.50.

Figura 6.6 a Identificarea distanței minime

Figura 6.6 b

Gruparea secvențelor în ram

Figura 6.6 c Identificarea distanțelor dintre grupul BFG și celelalte secvențe

Se calculează distanțele medii dintre noul grup, BFG și celelalte secvențe, obținând-se următoarea tabelă (pasul 5):

Pasul 5:

Figura 6.6 d Matricea rezultată în urma calculării distanței medii dintre grupul BFG și celelalte secvențe

Din noua tabelă (fig 6.6 d) se extrage distanța minimă: ;

Figura 6.7 a Determinarea distanței minime

Figura 6.7 b

Încadrarea într-un ram comun a grupurilor BFG și AD

Figura 6.7 c Identificarea distanțelor dintre grupul ADBFG și celelalte secvențe

Figura 6.7 d Matricea rezultată în urma calculării distanței medii dintre grupul ADBFG și celelalte secvențe

Din nou extragem valoarea minima (figura 6.8a) din tabel și parcurgem pașii algoritmului obținându-se următoarele rezultate:

Figura 6.8 a Identificarea distanței minime

Figura 6.8 b

Ramul comun al grupurilor BFG și AD

Figura 6.8 c Identificarea distanțelor dintre grupul ADBFGC și secvența E

Figura 6.8 d Distanța medie dintre grupul ADBFGC și secvența E

Odată ce ultima asociere a fost realizată, arborele UPGMA este complet (fig 6.9).

Figura 6.9 Arborele UPGMA complet

Calcularea similarităților semantice folosind NGD – Platforma de Test

Această lucrare are ca scop cercetarea și verificarea experimentală a aplicabilității distanței normalizate Google în domeniul web-ului semantic folosind principiile prezentate în lucrarea „Automatic Meaning Discovery Using Google ” de către autorii R. Cilibrasi și P. M. B. Vitanyi.

Pentru a avea rezultate cat mai reale a fost creat un motor de căutare personalizată folosind Custom Search Engine de la Google. S-a folosit următoarea colecție de site-uri pentru realizarea căutarilor astfel încat rezultatele returnate sa fie relevante pentru scopul dorit al aplicației, acela de a capta adevarata relație dintre termenii căutați:

http://www.synonym.com/

http://www.merriam-webster.com/

http://www.wordwebonline.com/

www.wikipedia.com

http://wordnetweb.princeton.edu/perl/webwn

http://www.dictionardesinonime.ro

http://www.dexonline.ro

http://www.webdex.ro/

www.wikipedia.ro

http://dex.dictoo.eu/

Prezentarea platformei experimentale

Platforma din cadrul acestei lucrări a fost realizată cu scopul de a verifica si testa similaritatea cuvintelor sau clasificarea acestora folosind metoda NGD. Sensul cuvintelor se va stabili folosind Distanța Normalizată Google. Aceasta este folosită pentru a extrage înțelesul cuvintelor în funcție de valoarea distanței dintre acestea precum și pentru a formarea relațiilor semantice.

Scopul final al platformei de test este acela de a asigura un sistem și o metodă pentru căutarea similitudinilor bazată pe grupuri de sinonime.

În cadrul platformei de test sunt implementate două funcționalităti cheie pentru realizarea testelor propuse:

Calcularea distanței între două cuvinte pentru a afla gradul de similaritate dintre acestea folosind NGD si Custom Search Engine;

Aflarea sinonimelor unui cuvânt dat.

Fig 7.1

Pentru a putea căuta sinonimele unui anumit cuvânt dat este necesară realizarea unei “baze de date” care să conțină aceste sinonime.

Pentru crearea acestei baze de date s-a pornit de la un set de cuvinte care sunt salvate intr-un fișier de tip .txt BasicWord.txt. Folosind motorul de căutare personalizată se face o primă căutare pe Google pentru fiecare cuvânt în parte și se va salva numărul de rezultate returnate într-un fisier .txt. A doua căutare se va face după toate perechile unice posiblie formate din cuvintele din fisiserul BasicWords. La fel ca și după prima căutare, se vor salva numărul de rezultate returnate într-un fișier .txt.

În cadrul platformei experimentale s-a construit o interfață grafică (fig 7.2). în care sunt implementate funcții necesare calculării matricei de similaritate cât și al arborelui filogenetic. Aceste funcții sunt prezentate în continuare.

Fig. 7.2 – Calcularea similarității dintre cuvinte

Funcționalități

Build Data Base – S-au construit următoarele funcții:

Prima funcție este realizată pentru a interacționa cu Custom Search Engine:

public int totalNumberOfResults(String word) throws IOException{

String qry=word;

String key="AIzaSyDU1zD4kbh-mjpig2nmfsefFPhGbWrIIQ4";

String cx="012219541226541165843:khnx2bmim24";

String queryArguments = "key="+key+ "&cx="+cx+ "&q="+ qry +"&num=10"+"&totalResults"+"&alt=json";

URL url = new URL("https://www.googleapis.com/customsearch/v1?"+queryArguments); HttpURLConnection conn = (HttpURLConnection)

url.openConnection();

conn.setRequestMethod("GET");

conn.setRequestProperty("Accept", "application/json");

BufferedReader br = new BufferedReader(new InputStreamReader((conn.getInputStream())));

String output;

String str=null;

int numberOfResults=0;

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

if(output.contains("\"totalResults\": \"")){

str=output.substring(output.indexOf("\"totalResults\": \"")+("\"totalResults\": \"").length(), output.indexOf("\","));

numberOfResults=Integer.parseInt(str);

}

conn.disconnect();

return numberOfResults;}

A doua funcție f(x), face o căutare pentru fiecare cuvânt din fișierul BasicWords si salvează intr-un alt fișier numărul rezultatelor returnate; acesta reprezintă numărul de pagini indexate de Google care conțin cuvântul x.

public float[] oneWord(){

try{

float [] index =new float [nrOfWords];

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

index[i]=totalNumberOfResults(words[i]);

}

return index;

}catch(Exception e){ System.err.println("Error: "+e.getMessage());}

return null;

}

Următoarea funcție f(x,y), execută căutari succesive pentru grupuri de câte două cuvinte. Numărul rezultatelor căutate se vor salva într-un fișier. Acest numșăr reprezintă numărul de pagini indexate de Google care conțin cuvintele x și y.

public float [][] pairWords() {

try{

float [][] index = new float [nrOfWords][nrOfWords];

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

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

index[i][j]=totalNumberOfResults(words[i]+"+"+words[j]);

}

return index;

}catch(Exception e){ System.err.println("Error: "+e.getMessage());}

return null;

}

Show Distance Matrix – îndeplinește două funcții:

Calculează distanța normalizată Google între două cuvinte x și y folosind rezultatele salvate în cele două fișiere descrise mai sus, după urmatoarea formulă:

Rezultatul se va salva într-un fișier .txt.

Afișează într-o matrice inferior triunghiulare – matrice distanță, distanțele între perechiile de cuvinte calculate cu formula NGD (Fig. 7.3).

public float [][]NGD(){

try{

float NGD[][]=new float [nrOfWords][nrOfWords];

fx=fy=getWordOccurence();

fxy=get2WordsOccurence();

for(i=0;i<nrOfWords;i++){

for(j=0;j<=i;j++){

NGD[i][j]= (float)((Math.max(log2(fx[i]), log2(fy[j]))-log2(fxy[i][j]))/(log2(n)-Math.min(log2(fx[i]), log2(fy[j]))));

}

return NGD;

}catch(Exception e){ System.err.println("Error: "+e.getMessage());}

return null;

}

Fig 7.3 – Matrice distanță

Show Tree – funcție care ordonează si clasifică cuvintele în funcție de caracteristica lor dominantă. Ordonarea este realizată cu ajutorul unui algoritm de construcție al arborilor filogenetici. În această lucrare se folosește algoritmul UPGMA pentru construcția acestor arbori care are ca input matricea distanță prezentată mai sus. În figura 7.4 este prezentat arborele filogenetic ce reiese din matricea distanță din figura 7.2.

Fig. 7.4

Al doilea scop al platformei expermientale este acela de a oferi o interfață care să returneze sinonimele unui cuvânt căutat (Fig 7.5 – Search for synonyms).

Fig 7.5 – Search for synonyms

Dacă cuvântul căutat se află în fișierul BasicWords, căutarea va returna cuvintele ale căror distanță NGD față de cuvântul căutat este cea mică.

În cazul în care cuvântul căutat nu se gasește în fișierul BasicWords, pe ecran va aparea un mesaj care ne atenționează că trebuie sa introducem cuvântul în baza de date.

Pentru a realiza acest lucru ne intoarcem în secțiunea Compute Similarity a platformei unde cu ajutorul butonului Insert New Word va trebui să introducem cuvântul respectiv in fișierul BasicWords. Pe langă introducerea cuvântului în fișierul BasicWords, în spatele butonului este implementată o funcție care calculează distanța normalizată Google între noul cuvânt si toate celelalte cuvinte existente în fișier.

Fig 7.6 – Insert new word

După realizarea acestor operații ne putem intoarce în secțiunea Search Synonyms pentru a putea găsi sinonimele noului cuvânt.

Testare și verificare

Cea mai importantă funcție a distanței normalizate Google este aceea de a stabili relații semantice între diferite concepte, obiecte sau cuvinte. În continuare voi prezenta câteva exemple în care va observa clasificarea cuvintelor din fișierul BasicWords în funcție ințelesul acestora.

Pentru obținerea rezultatelor testelor de mai jos s-a rulat algoritmul de construcție ai arborilor filogenetici, UPGMA.

Ordonarea cuvintelor în limba engleză

Pentru ordonarea cuvintelor din limba engleză s-a inclus în motorul Custom Search Engine următoarea colecție de site-uri pe care se vor efectua căutarile:

http://www.synonym.com/

http://www.merriam-webster.com/

http://www.wordwebonline.com/

www.wikipedia.com

http://wordnetweb.princeton.edu/perl/webwn

Test 1

În primul exemplu cuvintele ce urmează a fi grupate, sunt termeni ce definesc anumite stări sau însușiri ale unor obiecte sau ființe. Programul va aranja în mod automat cuvintele-cheie în funcție de sensul acestora. Termenii folosiți in acest exemplu sunt: happy, holiday, free, strong, delicate, glad, great, good, liberate, robust, powerful, fragile, sick, ill.

În figura de mai jos (figura 8.1) este afișată matricea ce conține distanțele normalizate Google dintre fiecare termeni cheie.

Figura 8.1. Matricea distanță ce conține distanțele normalizate Google pentru termenii prezentați anterior

Din figura 8.1 se observă cum distanța normalizată Google dintre cuvintele cheie ce au același sens (înțeles) este mică. De exemplu . În schimb distanța dintre două cuvinte ce fac parte din domenii diferite este mai mare sau chiar infinită.

Exemple:

Odată rulat algoritmul generează un arbore UPGMA în care cuvintele-cheie sunt aranjate automat în funcție de înțelesul acestora (figura 8.2).

Figura 8.2 – Ordonarea cuvintelor din primul set

Se observă cum algoritmul de generarea a arborelui grupează cuvintele în funcție de sensul acestora. Astfel distanțele calculate cu formula NGD sunt utilizate pentru a forma această distribuție spațială a cuvintelor cheie. Cuvintele sunt dispuse într-un ram comun în funcție de distanța dintre ele. De asemenea se observă că lungimile ramurilor a două cuvinte care provin dintr-un ram comun sunt egale.

Dar așa cum este de așteptat, distanța normalizată Google nu dă întotdeauna rezultate bune. Un astfel de exemplu se poate observa și în figura de mai sus (figura 8.1.1), unde cuvântul robust este grupat impreună cu sinonimele fragile și delicate.

Exemple de relații de sinonimie:

ill=sick

powerful=strong

fragile=delicate

liberate=free

Test 2

În cel de al doilea exemplu, termenii folosiți sunt: alluring, appealing, attractive, captivating, charismatic, charming, late, behind, overdue, tardy, slow, postponed.

Figura 8.3. Matricea distanță ce conține distanțele normalizate Google pentru termenii din cel de al doilea set

Figura 8.4 – Ordonarea cuvintelor din cel de al doilea set

Din cel de al doilea test se remarcă următoarele seturi de sinonime:

postponed = tardy

Test 3

În cel de al treilea exemplu, termenii folosiți sunt: big, tal, dangerous, false, hard, huge, intelligent, mad, large, clever, difficult, untrue, high.

Figura 8.5. Matricea distanță ce conține distanțele normalizate Google pentru termenii din cel de al treilea set

Figura 8.6 – Ordonarea cuvintelor din cel de al treilea set

Analizând imaginea de mai sus (figura 8.6) putem spune că această metodă dă rezultate destul de satisfăcătoare. S-au format următoarele seturi de sinonime:

difficult = hard

large = big

clever = intelligent

untrue = false

Ca și în exemplele prezentate până acum, se observă că există elemente ce nu sunt grupate corespunzător. Exemplu:

dangerous huge

Pe baza celor trei exemple prezentate anterior se poate observa că folosind distanța normalizată Google putem extrage înțelesul cuvintelor iar cu ajutorul metodei de construcție a arborilor filogenetici putem vizualiza relațiile dintre acestea.

Ordonarea cuvintelor în limba română

Pentru ordonarea cuvintelor din limba română s-a inclus în motorul Custom Search Engine următoarea colecție de site-uri pe care se vor efectua căutarile:

http://www.dictionardesinonime.ro

http://www.dexonline.ro

http://www.webdex.ro/

www.wikipedia.ro

http://dex.dictoo.eu/

Test 1

În primul test s-au folosit următoarele cuvinte din limba română cu scopul de a le grupa în seturi de sinonime: trist, supărat, fericit, vesel, integru, cinstit, ipocrit, fățarnic, prefăcut, sincer adevarăt, simplu, primitiv, nebun.

Figura 8.7. Matricea distanță ce conține distanțele normalizate Google pentru termenii din primul set

Se observă atât în matricea distanță (fig 8.7) cât și în reprezentarea UPGMA (fig. 8.8) gruparea unor anumiți termeni în seturi de sinonime:

fățarnic = prefăcut = ipocrit

sincer = cinstit

Deasemenea se observă că există grupări de cuvinte care nu fac parte dintr-un set de sinonime, ci mai degrabă fac parte dintr-un set care conțin atât antonime cât și sinonime.

Exemplu: fericit, vesel, supărat

fericit = vesel

supărat fericit, vesel

Figura 8.8 – Ordonarea cuvintelor din primul set

Test 2

În cel de al doilea s-au folosit următoarele cuvinte din limba română cu scopul de a le grupa în seturi de sinonime: cuvânt, vorbă, promisiune, angajament, obligație, sarcină, instrument, sculă, ustensilă, fotografie, poză, ilustrație, reproducere, aparat.

Pentru a observa influența diacriticelor asupra rezultatelor testului, în prima parte s-a rulat algorimul NGD asupra cuvintelor din setul de mai sus fără diacritice, urmând ca apoi să se folosească varianta cu diacritice.

În figura de mai jos (figura 8.9) este afișată matricea ce conține distanțele normalizate Google dintre cuvintele fără diacritice.

Figura 8.9. Matricea distanță ce conține distanțele normalizate Google pentru termenii din cel de al doilea set fără diacritice

Figura 8.10 – Ordonarea cuvintelor din al doilea set fără diacritice

Din

Figura 8.12 – Ordonarea cuvintelor din cel de al doilea set cu diacritice

În cazul rularii testului folosind cuvintele cu diacritice se observă din reprezentarea de mai sus (fig 8.12) că s-au format următoarele seturi de sinonime:

angajament=promisiune

aparat = instrument

fotografie = poză, reproducere

sarcină = vorbă, obligație

Deasemenea se mai observă că algoritmul de construcție ai arborilor filogenetici a grupat cuvintele în două categorii

Test 3

Figura 8.7 – Ordonarea cuvintelor din primul set

Concluzii

S-a dovedit ca se poate extrage sensul cuvintelor folosind distanta normalizata google. Astfel sunt realizate relatii semantice intre evenimente, obiecte sau activitati, precum si o clasificare a acestora in functie de o caracteristica dominanta.

Pe parcursul acestei lucrări am arătat că distanța normalizată Google poate fi folosită pentru a extrage înțelesul cuvintelor și pentru a forma relații semantice între acestea. Cu ajutorul algoritmului UPGMA de construcție a arborilor putem face o clasificare a acestor cuvinte pe baza relațiilor dintre ele. Așa cum am observat, clasificarea cuvintelor în funcție de caracteristica dominantă folosind NGD nu este realizată întotdeauna într-un mod corect. Acest lucru poate reprezenta o problemă atunci când rezultatul acestei clasificări este folosit ca dată de intrare pentru o altă aplicație.

Distanța normalizată Google poate fi folosită pentru a extrage înțelesul cuvintelor în funcție de valoarea distanței dintre acesteae precum și pentru a forma relații semantice între acestea. Astfel se pot construi rețele semantice care pot fi folosite apoi ca metode de reprezentare a cunoștinței.

În această lucrare a fost abordată o metodă pentru masurarea gradului de similaritate între cuvinte. Folosind această metodă pentru a găsi cuvinte similare (cu același înțeles), se dorește să se creeze o bază de date lexicală în care adjectivele, atributele, etc. , vor fi grupate în seturi de sinonime.

Pornind de la această bază de date se poate construi o aplicație care în funcție de relațiile ce se stabilesc între cuvinte să se poată determina sinonimele sau antonimele unui anumit cuvânt.

Alte exemple de aplicații ce se pot realiza utilizând distanța normalizată Google pot fi:

Aplicații inteligente de recunoaștere a sunetului

Aplicații de predicție comportamentală

Aplicații de tip translator

Bibliografie

[1] R. Cilibrasi and P. M. B. Vitanyi. Automatic Meaning Discovery Using Google; 2004

[2] Sursă electronică. What is Cyc?. Disponibil pe : http://cyc.com/cyc/technology/whatiscyc la data de 12.06.2012.

[3] Sursă electronică. What is WordNet?. Disponibil pe : http://wordnet.princeton.edu/ la data de 12.06.2012.

[4] Stuart C Shapiro. Knowldege Representation. State University of New York, University of Buffalo, USA.

[5] Ronald J. Brachman, Hector J. Levesque. Knowledge Representation And Reasoning. 2003

[6] Ștefan Trăușan-Matu, Inteligență artificială. Disponibil pe: http://www.racai.ro/~trausan/ia.pdf la data de 05.12.2012

[7] Sisteme bazate pe cunoștințe. Disponibil pe: http://www.ac.tuiasi.ro/ro/library/SBCHTML/ curs/Cap3.3.pdf la data de 27.01.2013

[8] Sursă electronică. Artificial Inteligence. Fondation of computational agents. Disponibil pe: http://artint.info/html/ArtInt_10.html la data de 27.01.2013

[9] Dragoș Lucian Gorgan. Introducere în studiul filogeniei și filogeografiei moleculare. Capitolul 2,pag. 38-39, Editura Bioflux, Cluj-Napoca 2008

[10] Sursă electronică. UPGMA. Disponibil pe: http://www.southampton.ac.uk/~re1u06/teaching /upgma/ la data de 16.06.2012

[11] Christophe Lalanne, An introduction to knowledge engineering. 2008

[12] Sursă electronică. Five papers on WordNet. Disponibil pe: http://wordnetcode.princeton.edu/5papers.pdf la data 10.12.2013.

[13] Sursă elecronică. WordNet. Disponibil pe: http://www.cs.princeton.edu/courses/archive/spr07/cos226/assignments/wordnet.html la data 10.12.2013.

[14] Jan Nemrava, Using WordNet glosses to reﬁne Google queries.

[15] Sursă elecronică. Search Engine word stemming and synonym expansion. Disponibil pe: http://www.dba-oracle.com/t_search_engine_word_stemming_synonyms.htm la data 05.06.4014

[16] Sursă elecronică. Google Custom Search. Disponibil pe: https://www.google.com/cse/all la data 15.06.4014