Eureka! Inferentiemechanisme voor zoekresultaten

Eureka! Inferentiemechanisme voor zoekresultaten 27-06-2008

Auteur:

Tom Aizenberg Supervisor: Bachelorstudent Bèta-gamma Major: Kunstmatige Intelligentie Universiteit van Amsterdam Dijkmanshuizenstraat 160 1024 XM Amsterdam [email protected]

Frank Nack Human computer studies Universiteit van Amsterdam Kruislaan 419 1098 VA Amsterdam [email protected]

Samenvatting Op zoek naar een manier om concepten te verklaren met behulp van verschillende media, voornamelijk beeld, kwam ik tot de conclusie dat er eerst een goed inferentiemechanisme gebouwd moet worden. De basis hiervoor heb ik gelegd door een statistisch clusteringalgoritme te ontwikkelen, dat op drie maatstaven van een woord een score voor een zoekterm opstelt. Met deze zoektermen kan vervolgens een query worden gedaan naar sites als Flickr of Google Images. Ik ben uiteindelijk tot de conclusie gekomen dat men met de juiste statistiek en een vooraf bepaald domein een goede afbakeningen van zoektermen kan genereren, door een statistische clustermethode te gebruiken.

Inhoudsopgave Inleiding .................................................................................................................................................. 3 Theoretische context................................................................................................................................ 3 Methode................................................................................................................................................... 4 Juist dit inferentiemechanisme ............................................................................................................ 4 Clusteralgoritme .................................................................................................................................. 5 Statistiek .............................................................................................................................................. 6 TF x IDF weighting ......................................................................................................................... 6 Fraselengte....................................................................................................................................... 6 Phrase independence....................................................................................................................... 7 Lineaire combinatie......................................................................................................................... 7 Internet ................................................................................................................................................ 7 Algoritme ............................................................................................................................................ 8 Resultaten ................................................................................................................................................ 8 Algoritme ............................................................................................................................................ 8 Clustering ............................................................................................................................................ 9 “Cobra”............................................................................................................................................ 9 “Paris” ............................................................................................................................................. 9 “Dichotomy” ................................................................................................................................... 9 “Congruent”................................................................................................................................... 10 “Bestand”....................................................................................................................................... 10 Conclusie............................................................................................................................................... 10 Discussie................................................................................................................................................ 11 Future work ........................................................................................................................................... 11 nGram............................................................................................................................................ 11 Dynamische parameterbepaling .................................................................................................... 12 Betere statistieken.......................................................................................................................... 12 Referenties............................................................................................................................................. 13 Bijlage A: .............................................................................................................................................. 14 Voorbeelduitvoer wrapper ............................................................................................................ 14 Uitvoer enkele inferentie ............................................................................................................... 15

Inleiding De regel is een bekende binnen de psychologie, een mooi cijfertje dat iedere eerstejaars al zal kennen, namelijk het gegeven dat maar 7% van de communicatie tussen mensen via het verbale verloopt, de overige 93% van het begrip tussen elkander halen wij uit het non-verbale (als beschreven in: Mehrabian, 1981). Zo kunnen we als wij spreken bepaalde bewegingen met ons lichaam maken om aan te duiden hoe ‘de woorden op te vatten’. Emoties geef je weer met je gezicht, je handen en de rest van je lijf, maar ook met de toon van je stem of dingen die niet bij je lichaam horen, bijvoorbeeld een plaatje of een tekening. Slaat dit gegeven ook op geschreven woorden? Bij het schrijven van een tekst zal de schrijver over het algemeen zijn uiterste best hebben gedaan om de tekst duidelijk te maken voor de lezers. Maar toch, het zal niet vaak voorkomen dat een tekst volledig begrijpelijk is voor de lezer. Een voor de hand liggende oplossing hiervoor is het toevoegen van plaatjes bij begrippen waarvan de schrijver of redacteur al vermoed dat ze verwarring op zullen leveren. Nu, iedereen zal het volgende wel herkennen: je leest een wetenschappelijke tekst, maar een bepaald concept gebruikt in de tekst begrijp je toch niet, ook uit de context is het niet te halen. Het concept dat je niet begrijpt is enkel uitgelegd in woorden. De meeste mensen zullen een woordenboek erbij pakken, even Google-en of een andere manier zoeken om te ontdekken wat een woord betekend. Maar, wat nu als we dit concept in andere media weergeven dan tekst, of in combinatie met tekst? Voor tekst zal hoogstwaarschijnlijk niet de 7%-regel gelden, aangezien het taalgebruik (spreektaal versus schrijftaal) hier heel anders is, maar toch missen we nog een zekere uitleg bij sommige concepten. De informatie die we hiervoor gebruiken moeten we ook ergens vandaan halen. Toevallig genoeg is een van de eigenschappen van het Internet, dat er heel veel gratis en open informatie op staat. Deze informatie is te gebruiken om de lezer te helpen. Het gebruik van Internet heeft natuurlijk ook wat uitdagingen. Het idee om (digitale) tekst uit te breiden met een multimediale beschrijving van onduidelijke woorden en concepten met behulp van webbronnen en hoe we dit zouden kunnen toepassen is in dit artikel beschreven. De grootste uitdagingen bij het tackelen van dit probleem liggen bij het gebruik van Internet, de informatie mag dan gratis zijn, er is geen structuur, geen meta-informatie en geen betrouwbaarheid. Een probleem dat hieruit voortvloeit is de ambiguïteit die inherent is aan natuurlijke taal. Deze ambiguïteit moet zo klein mogelijk gemaakt worden, er moet een context of afbakening worden geïdentificeerd. In dit artikel zal ik mij daarom richten op de vraag “Hoe kunnen we met behulp van informatie van het web een afbakening voor een betekenis van een woord in een bepaalde tekst maken? ”. Hiervoor heb ik getracht resultaten van online zoekmachines te clusteren, om een soort a priori contexten te definiëren, met deze mogelijke interpretaties zouden we een n-gram kunnen gebruiken om de meest waarschijnlijke interpretatie te kiezen, gegeven de tekst waar het woord uit komt. Om op gestelde vraag antwoord te geven wordt eerst een beschrijving gegeven van de theoretische context, de methode, waaronder ook de implementatie van het algoritme valt en de resultaten, om zo uiteindelijk het antwoord op de vraag te presenteren.

Theoretische context Verschillende wetenschappers hebben voor uiteenlopende doelen getracht gegevens te clusteren. Denk hierbij aan bijvoorbeeld het classificeren van meetresultaten of het groeperen van documenten. De gegevens die ik wil gaan clusteren betreffen resultaten van zoekqueries die zoekmachines op het Internet retourneren. De technieken om dit te doen zitten op het moment tussen een ontwikkelings- en implementatiefase in, dat wil zeggen, er zijn veel algoritmes ontwikkeld, een klein aantal minder grote zoekmachines gebruiken het al en er zijn zelfs al ‘best practises’ ontstaan. Echter, de grotere zoekmachines als Google, Yahoo! en Windows Live gebruiken de technieken nog niet in de online versies van hun site (Jacsó, 2007). In de wetenschappelijke journals is al veel geschreven over het probleem van het clusteren van gegevens. De algoritmes die hiervoor zijn ontwikkeld zijn bijvoorbeeld te gebruiken in de WEKA-toolkit. Waar ik mij echter op richt is het clusteren van zoekresultaten van het Internet, dit probleem is anders, doordat de gegevens die op het Internet gevonden worden vaak niet heel duidelijk

zijn en ook in grote getale komen (Jacsó, 2007). Uit de literatuur is duidelijk op te maken dat het clusteren van zoekresultaten een vorm van post-processing is, algoritmes werken nadat resultaten zijn verkregen (Mecca, Raunich en Pappaldardo, 2006; Zeng, He, Chen, Ma en Ma, 2004). Zo hebben Zeng et al. (2004) een algoritme ontwikkeld dat uit een bag van zoekresultaten namen destilleert die kenmerkend zijn voor de verschillende manieren van uitleg die mogelijk zijn voor een woord. Dit is precies wat ik nodig heb. Mecca et al. hebben een algoritme ontwikkeld dat niet alleen de titels of snippets van zoekresultaten gebruikt voor de clustering, maar hele pagina’s. Ze konden de tijdscomplexiteit hiervan aanvaardbaar maken, door Singular Value Decomposition te gebruiken. Vervolgens komen we op het probleem van de ‘word sense disambiguation’. We willen niet alleen de verschillende mogelijke conceptuele varianten van een woord vinden, maar ook de meest waarschijnlijke, gegeven de context. Dit kan gebeuren met behulp van een n-gram, of complexere modellen, zoals fuzzy sets (Sekiya, Kondo, Hashimoto, Takagi, 2006). Voor mijn doeleinden zal ik gebruik gaan maken van een n-gram.

Methode In dit deel van het paper zal ik de methode uiteenzetten, welk deels gebaseerd is op inzichten uit Zeng et al.2004. Het programma, zoals dat in de uiteindelijke versie zal moeten werken, bestaat uit verschillende, van elkaar te scheiden onderdelen. Dit is aan de ene kant om de verschillende problemen die komen kijken bij het schrijven van het gehele programma los aan te kunnen pakken, maar natuurlijk ook om zo vanuit een ontwikkelperspectief goed te kunnen werken. Het eerste onderdeel (1 in figuur 1) is onder een noemer te vatten als het ‘voorwerk’. Hier licht het initiatief bij de gebruiker. De gebruiker geeft aan een bepaald concept uitgelegd te willen zien, door bijvoorbeeld het woord aan te wijzen of te selecteren. Dit woord wordt vervolgens met de nodige pre-processing klaargemaakt om verwerkt te worden. Het Figuur 1: Schematische weergave programma resultaat van deze stap is dus een losse zoekterm, als er voor de eerste keer gezocht wordt, wordt ook de tekst meegegeven om een nGram te genereren. In het tweede onderdeel (2 in figuur 1), de inferentie, wordt vervolgens het woord zo bewerkt, dat het als combinatie van woorden als zoekterm voor het uit te leggen concept kan dienen. Dit is in feite wat ik heb gedaan, dus hier zal ik dadelijk verder op in gaan. Ten slotte wordt in de laatste stap (3 in de figuur) een aantal databases geselecteerd naar gelang het domein van de tekst en andere factoren waar ik nu niet verder op in zal gaan, deze worden vervolgens gequeried met de verkregen zoekterm. De resultaten hier van, plaatjes, tekst, filmpjes, geluiden en zo voorts worden tenslotte in het juiste formaat aan de gebruiker getoond. Dit kan bijvoorbeeld een e-bookreader zijn, of een tekstprogramma op een computer, zoals Adobe Reader, dat veel voor wetenschappelijke teksten gebruikt wordt.

Juist dit inferentiemechanisme Het inferentiemechanisme heeft dus als invoer een woord en als uitvoer een cluster van woorden en eventueel - de eerste keer - een nGram van de tekst. Het inferentiemechanisme is verdeeld in twee stappen. Eerst wordt er een set van zoektermen gekozen en vervolgens wordt er uit deze set van zoektermen de beste gekozen aan de hand van het nGram. De lezer bekend met dit onderwerp zal zich afvragen waarom ik er nu precies voor heb gekozen om het op deze manier aan te pakken. Het is - en was ook voor mij - niet de meest voor de hand liggende manier om dit probleem aan te pakken. Men zou bijvoorbeeld kunnen bedenken om

éérst een zoekopdracht te doen naar verschillende databases, dit resulteert dan in een collectie van documenten, of in ieder geval zogenoemde snippets van documenten, en de nodige andere media, zoals plaatjes. Dit zijn de titels en de korte beschrijvingen, zoals men dit meestal tegenkomt bij zoekmachines. Hierna zou men uit de collectie van geretourneerde documenten de meest waarschijnlijke resultaten kunnen kiezen, gegeven de tekst. Dit klinkt erg logisch. Er zijn toch verschillende redenen om dit juist niet zo te doen, of in ieder geval, om het anders te proberen. De meest voor de hand liggende reden is dat we werken met het Internet. Dit heeft, op het moment dat ik dit schrijf, een aantal duidelijke nadelen. Als we iets zoeken, beschikken we over een haast onuitputtelijke bron van mogelijke zoekresultaten. Dit leidt er toe dat we voor iedere query, een enorme berg terug kunnen verwachten aan mogelijk correcte documenten. De documenten die we terug krijgen van de verschillende databases zijn daarbij ook nog vaak nutteloos, we beschikken dan dus zelfs bij vrij weinig gebruikte termen nog steeds over grote hoeveelheden informatie1, waarvan een groot deel kwalitatief slecht is, of gewoon redundant. Wat we dan hebben moeten we vervolgens gaan bewerken. We zitten dus met het probleem dat veel informatie subjectief en slecht is. Daarbij kost dit hele proces op het Internet tijd, afhankelijk van de kwaliteit van de Internetverbinding, aardig wat tijd. Was het nu zo dat we één database direct zouden willen aanroepen, dan is dit geen probleem, maar wanneer we Flickr, Google maps, Google, The CIA World Factbook en zo voorts allemaal los te grote queries sturen, dan wordt dit een probleem. De tijd die dit kost zal al snel vrij groot worden en met de inferentie kunnen we pas beginnen als alles binnen is. We zouden hier dus kunnen spreken van een zwakste-schakel probleem. Het eerste grote probleem komt er dus op neer dat we te veel data, te langzaam kunnen verkrijgen. Dan vloeit het tweede grote probleem hier bijna als een logisch gevolg op uit. We zitten nu dus met kaarten van Google Maps, foto’s van Flickr, woordenboekdefinities van Wordnet en ga zo maar door. Deze grote hoeveelheid moeten we gaan bewerken, dit kost veel processortijd. Nu is dit niet zo’n probleem wanneer men een computer van een paar duizend euro tot zijn beschikking heeft, maar op een simpele studentenlaptop of een personal digital assistant wordt dit, zeker voor de kleinere handheldapparatuur een heel ander verhaal. Wat dus beter lijkt, is om eerst op zoek te gaan naar een zoekterm waarvan we zeker weten dat wanneer we deze bij aan een databases geven als query, de eerste twee à drie resultaten overeenkomen met het gezochte resultaat. Dit betekend dat we met een afgebakende zoekterm op zoek kunnen gaan naar de eerste twee resultaten van de gekozen databases en deze zonder verdere grote berekeningen kunnen tonen. Er zal misschien een plaatje moeten worden vergroot of verkleind en dergelijke, maar deze tijdskosten zijn verwaarloosbaar. We hebben hiermee dus een methode bedacht die, mits het clusteren van de mogelijke zoektermen tijdskostenefficient werkt, veel sneller is dan de “obvious one”.

Clusteralgoritme Het clusteralgoritme om een goede zoekterm te vinden voor de verschillende databases heb ik gebaseerd op het werk van Zeng et al. (2004). Zij beschrijven in hun artikel - toepasselijk - genaamd “Learning to Cluster Web Search Results” een algoritme, dit algoritme is statistisch, in tegenstelling tot symbolisch. De reden om voor dit algoritme als basis te kiezen is wederom het feit dat Internet gebruikt wordt, het Internet is immers ongestructureerd en constant aan verandering onderhevig. Het is naar mijn idee beter om hier ‘behavioristische’ statistiek op toe te passen dan formele symbolische regels. Zelf beschrijven zij de aanpak die zij hebben ontwikkeld als een ‘salient phrases ranking problem’, ofwel een zoekprobleem waarbij we op zoek zijn naar de meest kenmerkende frases in documenten. In eerste instantie wordt er een query gedaan naar een online zoekmachine, die vervolgens een gesorteerde lijst met resulterende documenten terug geeft. Deze lijst, R, kan worden opgevat als R={r(di|q)}

(1.1)

waar r een onbekende sorteerfunctie is, di een document en q de query die is gedaan. R is dus de lijst van geretourneerde documenten, geordend op een ranking met als kansmaat de kans op het huidige

1

incommensurability levert bijvoorbeeld ongeveer 241.000 resultaten bij Google

document gegeven de zoekterm. Een standaard clustering algoritme zou nu een set clusters C proberen te vinden, waarbij ieder cluster Ci bestaat uit een set resultaten. Dit komt dus neer op C = {Rj}, waar Rj={r(di|q,Rj)}.

(1.2)

Zeng et al. herformaliseren dit probleem als een probleem waarbij we niet op zoek zijn naar de beste zoekresultaten Rj, maar een probleem waarbij we op zoek zijn naar de meest waarschijnlijke (op volgorde gesorteerde) clusters C’. Dit betekent dus dat we C’ = { r’(ck,Rk|q)}, waar Rk={r(dk|q,ck)}

(1.3)

krijgen. Hier is r’ een rankingfunctie voor de clusternamen. Deze r’ is dus eigenlijk waar we in geïnteresseerd zijn. Deze rankingfunctie hebben zij opgebouwd door een aantal statistische factoren te berekenen, die ik zo vanuit mijn eigen perspectief zal toelichten. Deze waardes kunnen voor iedere frases van 1 tot n, berekend worden en uiteindelijke tot een lineaire combinatie worden gesmeed. Deze lineaire combinatie resulteert in een score voor iedere frase:

Σ

Scorei = a + bixi

(1.4)

Hier is de score voor iedere term i de som van alle factoren x vermenigvuldigd met een constante b, dit geheel wordt bij een constante a opgeteld. Zeng et al. hebben de beste waardes voor de vermenigvuldigingsfactoren bepaald door het te beschouwen als een supervised learning probleem en dit te trainen met data van menselijke evalueerders van de uitgevoerde frases.

Statistiek Zoals gezegd wordt de score van iedere frase bepaald door een lineaire combinatie van vermenigvuldigingsfactoren en statistische eigenschappen van een term. Deze zal ik hier toelichten. TF x IDF weighting Een vrij logische statistische factor voor de kans dat een woord ‘belangrijk’ is, is het aantal keer dat het woord voorkomt in een set documenten. We zouden kunnen stellen dat de frequentie, hier TF (term frequency), van een woord in een document een goede voorspelling kan zijn waar het document over gaat. Een hoge frequentie van een woord kan betekenen dat de tekst als onderwerp dat woord heeft. Dit lijkt een goede maat voor de betekenis van een tekst. We komen hier echter een probleem tegen. Woorden als ‘de’, ‘het’ en ‘een’ komen belachelijk vaak voor, maar voegen vrij weinig aan semantische informatie toe, in ieder geval niet voor een computer. Eigenlijk zijn we dus niet alleen op zoek naar woorden die vaak voorkomen, maar op de een of andere manier ook discrimineren van andere documenten. Hiervoor is er een maat voor de verspreiding van een term over een gehele set van documenten, ofwel de verhouding tussen het aantal documenten N en het aantal documenten di die term w bevatten, in de gehele set van documenten D (Jurafsky & Martin, 2000). De formule die ik hiervoor heb gebruikt wordt ook wel TF x IDF weighting genoemd:

TFIDFi = f(wi )log(

N ) ni

(2.1)

Er wordt hier een logaritmische schaal gebruikt, om ervoor te zorgen dat er bij grote waardes voor N/ni nog bruikbare resultaten uitkomen. Fraselengte Deze eigenschap van een potentiële zoekterm is voor verschillende dingen van nut. In het huidige geval is het van belang om een juiste lengte van een frase te vinden, welke tussen 1 en n kan liggen, omdat we hiermee gaan zoeken op verschillende databases. Een te korte frase levert te veel, ambigue resultaten, terwijl een te lange frase misschien wel te weinig resultaten levert. Nu is het zo dat we liever een te lange frase hebben, we willen de bovenste x (x~2 of iets in die richting) zoekresultaten gebruiken. Als we drie resultaten krijgen is dat in principe niet zo erg.

Phrase independence Volgens Zeng et al.(2000) kunnen we van een frase de onafhankelijkheid van zijn context meten, door een maat hiervoor te introduceren, welke door hen ‘phrase independence’, of IND, wordt genoemd. Deze maat bepaald de onafhankelijkheid van een woord van zijn directe context. Deze maatstaf lijkt een beetje op de TFIDF, maar is in die zin anders dat we niet kijken naar documenten, dus de globale context, maar naar naburige woorden, dus lokale context. Om de IND te berekenen, moeten we zowel voor de rechtercontext als de linkercontext de onafhankelijkheid meten. Dit doen we door voor iedere frase wi uit W, de volgende berekening uit te voeren:

INDlinks = −∑ D

f ( wi −1 )  f ( wi −1 )   log f ( wi ) f ( w ) i  

(3.1)

Hetzelfde doen we voor de directe context aan de rechterkant:

INDrechts = −∑ D

f ( wi +1 )  f ( wi +1 )   log f ( wi )  f ( wi ) 

(3.2)

Deze twee waardes kunnen we nu combineren om de waarde voor INDi te verkrijgen, door het gemiddelde te nemen van de twee IND-waardes:

INDi =

INDl + INDr 2

(3.3)

Voor iedere frase hebben we nu dus bovenstaande berekeningen uitgevoerd. Lineaire combinatie Men zou de waardes van de vermenigvuldigingsconstanten voor de lineaire combinatie kunnen proberen te leren met lineaire regressie. Een probleem is dat we daarvoor dan wel veel tijd en proefpersonen nodig hebben. Ik heb daarom een wrapper geschreven voor mijn ontwikkelde algoritme, deze roept het programma telkens aan met nieuwe willekeurige waardes voor de constanten. Zie voor een voorbeelduitvoer in bijlage A. De verkregen resultaten en waardes worden uitgevoerd naar een bestand. Uit deze resultaten heb ik van de naar mijn idee beste resultaten en hiervan een gemiddelde genomen. Er zijn natuurlijk, afhankelijk van bijvoorbeeld het domein, de te querien databases en dergelijke heel veel mogelijkheden, maar ik heb hieronder één combinatie weergegeven die het goed deed.

 INDi    S i = (0.4 0.01 0.2) ⋅  lengthi   TFIDF  i  

(4.1)

Hier is de score Si gelijk aan de lineaire combinatie van factoren en statistische gegegevens. Zie ook de vergelijking 1.4, ik heb hier de a weggelaten, omdat deze geen bijdrage levert aan de relatieve uitkomst, maar is enkel een absolute verschuiving op de y-as.

Internet Er zijn verschillende zoekmachines die een application programming interface, of API hebben. Ik heb een afweging gemaakt tussen Google en Yahoo!. Veel mensen denken nog dat Google het beste is op zoekmachinegebied, wat eigenlijk niet helemaal waar is. Verschillen in resultaten en snelheid zijn minimaal. De verschillen maar wat de API betreft biedt Yahoo! echter een voordeel, deze werkt namelijk erg gemakkelijk en intuïtief, voor een programmeur. Het programma doet een request via een URL met GET variabelen en Yahoo! retourneert een XML bestand met alle resultaten. Zo’n query bevat de zoekterm, de taal waarin gezocht moet worden,

de hoeveelheid resultaten en andere, niet-relevante data. Het mag duidelijk zijn, dat de resultaten kwalitatief ook enigszins afhankelijk zijn van de taal waarin we zoeken en de hoeveelheid zoekresultaten die we opvragen. Het opvragen en ontvangen van de zoekresultaten duurde gemiddeld niet langer dan één seconde op een standaard ADSL-verbinding.

Algoritme De samenvoeging van de eerder beschreven formules en dergelijke heeft uiteindelijk geleid tot het volgende algoritme, beschreven in pseudocode (5.1): 1. results[] = queryYahoo(c); 2.distinctPhrases[] = getDistinctPhrases(results[]); 3. foreach(distinctPhrases as phrase) statistics[][] = calculateStatistics(phrase); 4. list = getTopTen(results,statistics); Er worden dus eerst zoekresultaten opgehaald en in een bruikbare vorm gegoten. Dit betekend dat Yahoo! een query wordt gegeven en het programma de resultaten, titels en snippets per document samenvoegt. Van deze resultaten wordt een lijst gecreëerd waarin alle frases met lengte 1 tot en met 3 worden gezet. Vervolgens wordt voor iedere frase de benodigde statistiek berekend, dus de IND, de lengte van de frase (wat triviaal is) en de TFIDF. Dit is de meest tijdrovende taak en neemt exponentieel toe naarmate de zoekresultaten toenemen. Het is nog best lastig de juiste verhouding te vinden tussen kwaliteit van de clusterresultaten en de hoeveelheid zoekresultaten.

Resultaten Algoritme

10 0

80

60

40

20

1

t in ms

Het is, zoals gezegd, lastig een goede verhouding te vinden tussen het aantal 25000 opgevraagde zoekresultaten en de kwaliteit van de clusters. Veel resultaten 20000 opvragen kost meer tijd om te verwerken, 15000 maar leveren wel bredere resultaten. In 10000 grafiek 1 heb ik een overzicht gezet van de tijd in milliseconden die het kost om de 5000 resultaten te verwerken, dus de statistieken 0 te berekenen, en het aantal resultaten. Ik heb er bewust voor gekozen om hier geen maatstaf voor de kwaliteit van de clusters N te geven, aangezien deze zo subjectief is, dat het eigenlijk alleen gebruikt is om een goed aantal te vinden, puur op intuïtie. Grafiek 1: aantal zoekresultaten tegen inferentietijd Nu blijkt dat bij een n van 20, we al prima resultaten krijgen. Bij een n van 100 krijgen we misschien één cluster meer, maar dit is dan nog wel een overbodig cluster. Waar het dus zo zou zijn dat we een concept willen verklaren dat tien of meer mogelijke desambigueringen heeft, dan zou het nuttig zijn, dit komt echter niet zo veel voor. Ik heb er uiteindelijk voor gekozen om een n van 20 te kiezen. Voorbeelden van de resultaten die dit opleverde heb ik hieronder uiteengezet.

Clustering Hieronder heb ik voor een aantal zoektermen een clustering geprobeerd te maken, hiervan heb ik de top-5 genomen. Deze heb ik uiteengezet in tabellen samen met de score van ieder cluster en de gebruikte parameters. De verschillende zoektermen heb ik gekozen op mogelijke ambiguïteit, vaagheid en voorkomendheid. Zo komt een woord als ‘dichotomy’ niet zo vaak voor en een woord als ‘Paris’ kan op Internet duidelijk minstens twee verschillende dingen betekenen. “Cobra”

Frase Event Snake and an The U.S. Spouses and dependent Room interviews with Parameters:

Score 0.487 0.477 0.420 0.420 0.420 n = 20; lang=”en”; f={0.4;0.01,0.3}

Frase Stallone Brigitte Nielsen Stallone Brigitte Brigitte Nielsen Nielsen Plan admin Parameters:

Score 1.829 1.820 1.387 1.371 1.032 n = 100; lang=”en”; f={0.4;0.01,0.3}

“Paris”

Frase Filmography and Dining and more Hotel deals and Bycicle bus and Shopping dining and Parameters:

Score 0.810 0.441 0.423 0.420 0.420 n = 20; lang=”en”; f={0.4;0.01,0.3}

Frase Travel guide Hilton Visitors Funk Filmography and Parameters:

Score 1.200 1.039 0.930 0.9013 0.807 n = 100; lang=”en”; f={0.4;0.01,0.3}

“Dichotomy”

Frase It was a Dictionary of the Was a Two groups typically Dicha apart and

Score 0.630 0.630 0.620 0.420 0.420

Parameters:

n = 20; lang=”en”; f={0.4;0.01,0.3}

Frase Was a Classical ambient Videos lyrics and Age classical Songs albums Parameters:

Score 1.230 1.220 1.220 1.220 1.220 n = 100; lang=”en”; f={0.4;0.01,0.3}

“Congruent”

Frase Morons Morons like The free encyclopedia Geometry The free Parameters:

Score 0.941 0.583 0.496 0.320 0.300 n = 20; lang=”en”; f={0.4;0.01,0.3}

Frase Phrase Like Triangles Geometry Math Pronunciations thesaurus Parameters:

Score 1.708 1.707 1.308 1.171 1.171 n = 100; lang=”en”; f={0.4;0.01,0.3}

“Bestand”

Frase Portal Software Holland Bevat bitsnelheid of File is een Waarvan de naam Parameters:

Score 0.610 0.420 0.380 0.380 0.310 n = 20; lang=”nl”; f={0.4;0.01,0.3}

Frase Buitenland Of image file PDF Converter PDF Het selecteren van Parameters:

Score 1.592 1.320 1.064 1.030 0.957 n = 100; lang=”nl”; f={0.4;0.01,0.3}

Conclusie Ik ben uiteindelijk tot de conclusie gekomen dat men met de juiste statistiek en een vooraf bepaald domein een goede afbakeningen van zoektermen kan genereren, door een statistische clustermethode te gebruiken. Mijn doel was om een afbakening, ofwel een groepje woorden of en frase, te genereren

die, wanneer gebruikt als zoekterm bij een database voor bijvoorbeeld foto’s, een eenduidig resultaat in de eerste paar zoekopdrachten kan leveren. We zien dit bijvoorbeeld bij het resultaat van de term “congruent” bij n = 100. Hier is het duidelijk dat er congruentie in de geometrie kan zijn of in de taalkunde. Bij “Paris” met n = 20 werkt het ook aardig, we krijgen een Paris Hilton en een Paris ‘de stad’, dit is natuurlijk het resultaat dat we willen zien. Echter bij andere resultaten is het verschil in synoniemen niet zo duidelijk, zoals bij “Cobra” met n = 100, hier verwijst het enkel nog naar de film Cobra. Er kan dus ook geconcludeerd worden, dat de parameters die we gebruiken erg belangrijk zijn. Deze parameters zijn dan voornamelijk afhankelijk van het domein en het woord zelf. Wanneer we dit programma toepassen in een domein als fun, dan is het niet zo erg als er alleen maar fun-resultaten getoond worden, dat is zelfs de bedoeling. In een wetenschappelijke context zit dat echter anders. Verder lijkt het er ook op dat wanneer wij op een woord zoeken dat meer een fun betekenis heeft, er ook gelijk veel meer resultaten komen van deze uitleg van het woord, zoals bij “Cobra” het geval is. Men kan dit clusteralgoritme dus implementeren in een werkend systeem, maar moet het dan wel tweaken naar het domein en de toepassing.

Discussie Wat me tijdens dit project erg is opgevallen, is toch wel het feit dat er op het Internet heel veel vage, slechte en rare informatie is. Dit is op zich niet zo verschrikkelijk voor een mens, als mens weet je wanneer je ergens op moet klikken, een sterk punt van de mens is natuurlijk ook dat we er goed in zijn om bepaalde informatie te negeren en bepaalde informatie te filteren en te sorteren. Veel van onze cognitieve processen verlopen blijkbaar toch erg onbewust. De meeste mensen zullen niet één voor één ieder zoekresultaat van Google gaan lezen en analyseren, maar doen even een ‘quick scan’ over de informatie. Voor computers is het echter wél een probleem dat informatie niet geannoteerd, of in íeder geval gestructureerd is. Computers kunnen niet niet-formeel redeneren. Een computer kan, op dit moment, niet even een snel met zijn ogen over een tekstje glijden en een juist document zoeken. Het kan alleen heel belachelijk snel rekenen, ongelooflijk veel sneller dan mensen. Persoonlijk ligt mijn smaak niet bij het volledig annoteren van informatie, het is te stug en te star, vandaar ook dat het mij logischer lijkt om, in navolging van de mens, een algoritme als dit op een statistische wijze moeten aanpakken. Echter, of dit met statistiek alleen wel gaat lukken is de vraag. Als mens gebruiken wij toch ook iets van noun/verb parses of andere expliciete informatie, om te bepalen wat een goed woord is om de zoektocht mee verder te voeren. Ik had gehoopt dat ik met dit project een soort generiek, op Internet toepasbaar inferentiemechanisme had kunnen maken. Dat is tegengevallen, in de zin dat het niet generiek is. Het mechanisme werkt best prima, maar de parameters aan het algoritme moeten toch per domein bepaald worden.

Future work Op zich is dit een prima opzet. Er moet echter nog wel het een en ander gebeuren om een goed werkend programma te krijgen. nGram Mijn initiële idee, om ook een nGram te gebruiken om het meest relevante cluster te kiezen aan de hand van de globale context van een tekst, is uiteindelijk niet meer afgekomen. Op zich zouden de resultaten hiervan nog best wel een aardig kunnen zijn. Veel software werkt namelijk aan de hand van lokale context en niet de globale context. Het gebruiken van globale context kan problemen met zich meebrengen, maar zou voor wetenschappelijke teksten erg goed kunnen werken, doordat deze teksten vaak over één onderwerp gaan. Om dit uit te voeren kan er aan het algoritme 5.1 het volgende, vrij triviale deel te worden toegevoegd (6.1): 5. nGram = generateNGram(text); 6. searchTerm = selectBestCluster(list,nGram);

Dynamische parameterbepaling Zoals gezegd is een groot probleem bij dit algoritme de bepaling van de parameters. Voor verschillende domeinen, maar ook voor verschillende woorden blijken de settings bij verschillende waardes verschillende kwaliteiten te bezitten. Wat we hiervoor zouden kunnen implementeren is een algoritme dat een maatstaf voor de verschillende kwaliteiten van de clusterresultaten geeft. Vervolgens zouden we aan de hand van deze maatstaven de parameters kunnen laten veranderen, zo lang tot dat de kwaliteit van de clusters boven een bepaalde drempelwaarde is gekomen. Betere statistieken Ten slotte zou een verbetering aan het algoritme zelf zijn een verbetering van of toevoeging aan de statistische technieken die worden gebruikt. Dit is natuurlijk wat triviaal, maar er moeten wetenschappers zijn als computerlinguïsten en dergelijke die hier nog goede statistische methodes voor weten. Uiteindelijk moeten deze dan ook worden gecombineerd in een op het domein geleerd lineair model, of dynamisch worden aangepast zoals geopperd.

Referenties Chien, L. F., PAT-Tree-Based Adaptive Keyphrase Extraction for Intelligent Chinese Information Retrieval. In Proceedings of the 20th Annual International ACM/SIGIR Conference on Research and Development in Information Retrieval (SIGIR ‘97), 50-58, Philadelphia, 1997. Jacsó, P. Clustering Web Search Results. Part I: Web-Wide Search Engines, Online Information Review, 31 (1), 2007, 85-91. Jurafsky, D., Martin, J. H., Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition. Prentice Hall, NJ: Boulder (2000). Mecca, G., Raunich, S., Pappaldaro, A. A New Algorithm for Clustering Web Search Results, Data & Knowledge Engineering, 62, 2007, 504-522. Mehrabian, A., Silent messages: Implicit communication of emotions and attitudes. Belmont, CA: Wadsworth, (1981) Sekiya, H., Kondo, T., Hashimoto, M., Takagi, T. Context Representation Using Word Sequences Extracted From a News Corpus, International Journal of Approximate Reasoning, 45, 2007, 424-438. Yahoo! Websearch API, http://developer.yahoo.com/search/web/V1/webSearch.html, (juni 2008). Zeng, H., He, Q., Chen, Z., Ma, W., Ma, J. Learning to Cluster Web Search Results, Microsoft External Communication, 2004.

Bijlage A: Voorbeelduitvoer wrapper -> Start test 1... -> Start... -> Retrieving results... -> Q: http://search.yahooapis.com/WebSearchServic e/V1/webSearch?appid=boMKm8HV34Go5_BB70glwV HEQtFiQeuYVJ_T2OefaODJ8xen37iqGiWxoCu40zg06 lFqQg-&query=paris&results=100&format=html&langua ge=en&start=1 -> Retrieved results 1 to 101... -> time: 2234 -> Start timing... -> Top-10 results: Hotels City Guide 3.727985711147838 Travel Guide 4.007686977280613 of the Louvre 3.6785750220286584 the latest gossip 3.769728283531591 news photos and 3.8191389726507703 19th century 2.409337548836406 interactive maps and 3.4546156912582515 filmography and more. 3.4546156912582515 geography culture and 3.4546156912582515 culture and education. 3.4546156912582515 -> Sizes: 5893 5893 5893 5893 5893 5893 100 100 -> f[TFIDF]:0.29061751667169244 -> f[LEN]:0.9577935526382888 -> f[IND]:0.15140229016360296 -> Finished clustering... -> Time:26500 milliseconds -> End test 1. -> Start test 2... -> Start... -> Retrieving results... -> Q: http://search.yahooapis.com/WebSearchServic e/V1/webSearch?appid=boMKm8HV34Go5_BB70glwV HEQtFiQeuYVJ_T2OefaODJ8xen37iqGiWxoCu40zg06 lFqQg-&query=paris&results=100&format=html&langua ge=en&start=1 -> Retrieved results 1 to 101... -> time: 2281 -> Start timing... -> Top-10 results: Travel Guide 4.069966402892472 19th century 2.377082709181705 hotels and show 3.3614295133094942 shopping dining and 3.3614295133094942 dining and more. 3.3614295133094942

filmography and more. 3.3614295133094942 interactive maps and 3.3614295133094942 geography culture and 3.3614295133094942 culture and education. 3.3614295133094942 Hilton Fashion Pictures 3.3614295133094942 -> Sizes: 5893 5893 5893 5893 5893 5893 100 100 -> f[TFIDF]:0.3723086635030348 -> f[LEN]:0.8722707287678082 -> f[IND]:0.88052309048757 -> Finished clustering... -> Time:26766 milliseconds -> End test 2. -> Start test 3... -> Start... -> Retrieving results... -> Q: http://search.yahooapis.com/WebSearchServic e/V1/webSearch?appid=boMKm8HV34Go5_BB70glwV HEQtFiQeuYVJ_T2OefaODJ8xen37iqGiWxoCu40zg06 lFqQg-&query=paris&results=100&format=html&langua ge=en&start=1 -> Retrieved results 1 to 101... -> time: 1703 -> Start timing... -> Top-10 results: m. -1.564597014586503 No -1.4463800749815956 we -1.1976193446027146 nos -1.8547710739819487 le -0.9703022226196608 P -0.8367043303269692 O -0.9085267910179444 ground -1.6967749252501365 are -1.383067851292365 hot -1.0982277154954447 -> Sizes: 5893 5893 5893 5893 5893 5893 100 100 -> f[TFIDF]:-0.7264727026304758 -> f[LEN]:-0.6898367164950916 -> f[IND]:0.20521354181153417 -> Finished clustering... -> Time:26531 milliseconds -> End test 3. -> Start test 4... -> Start... -> Retrieving results...

-> Q: http://search.yahooapis.com/WebSearchServic e/V1/webSearch?appid=boMKm8HV34Go5_BB70glwV HEQtFiQeuYVJ_T2OefaODJ8xen37iqGiWxoCu40zg06 lFqQg-&query=paris&results=100&format=html&langua ge=en&start=1 -> Retrieved results 1 to 101... -> time: 2063 -> Start timing... -> Top-10 results: m. -1.1608566123984496 No -1.0481016730948527 hot -0.7107832384116979 we -0.8108344832256875 to -0.9836268904869437 are -0.9877146764164293 P -0.4541089735606495 le -0.5887683120162172 O -0.535098929238977 nos -1.4323718766540647 -> Sizes: 5893 5893 5893 5893 5893 5893 100 100 -> f[TFIDF]:-0.6929073427596923 -> f[LEN]:-0.32651303485248606 -> f[IND]:0.1782858304829782 -> Finished clustering... -> Time:26625 milliseconds -> End test 4.

-> Start... -> Retrieving results... -> Q: http://search.yahooapis.com/WebSearchServic e/V1/webSearch?appid=boMKm8HV34Go5_BB70glwV HEQtFiQeuYVJ_T2OefaODJ8xen37iqGiWxoCu40zg06 lFqQg-&query=paris&results=100&format=html&langua ge=en&start=1 -> Retrieved results 1 to 101... -> time: 2375 -> Start timing... -> Top-10 results: Hilton 3.2895658633477076 and visitors 3.301062017962906 of a 3.301062017962906 Travel Guide 4.1694834987106955 filmography and 3.695490696929899 Guide 3.195981311708855 Rock 3.8766297501939833 the latest gossip 3.3379445731867405 news photos and 3.042826173269656 19th century 2.188012647356641 -> Sizes: 5893 5893 5893 5893 5893 5893 100 100 -> f[TFIDF]:0.6551318550448808 -> f[LEN]:0.5374816383751879 -> f[IND]:0.831477079297668 -> Finished clustering... -> Time:26844 milliseconds -> End test 5.

-> Start test 5...

Uitvoer enkele inferentie -> Start... -> Retrieving results... -> Q: http://search.yahooapis.com/WebSearchServic e/V1/webSearch?appid=boMKm8HV34Go5_BB70glwV HEQtFiQeuYVJ_T2OefaODJ8xen37iqGiWxoCu40zg06 lFqQg-&query=paris&results=100&format=html&langua ge=en&start=1 -> Retrieved results 1 to 101... -> time: 2344 -> Start timing... -> Top-10 results: Hilton 1.0341176480171081 and visitors 1.0393820026016112 of a 1.0393820026016112 Geographic 1.0293820026016112 19th century 0.5296910013008056 Rock 1.5390730039024167 Funk 1.0293820026016112 Guide 0.9912631214428623 filmography and 1.22

Travel Guide 1.200926996097583 -> Sizes: 5893 5893 5893 5893 5893 5893 100 100 -> f[TFIDF]:0.3 -> f[LEN]:0.01 -> f[IND]:0.4 -> Finished clustering... -> Time:29187 milliseconds -> opening file C:\test.txt -> Finished creating n-Gram... -> Time:30187 milliseconds