Information Retrieval: introductie 1

Information Retrieval: introductie 1 • hoe is relevante informatie in zeer grote hoveelheden van documenten te vinden? • deze documenten moeten wel door de computer verwerkbaar zijn • vaak zijn er te veel hits: 1.530.000 Nederlandstalige pagina’s voor vezekering – soms heeft dat met ambiguiteit te maken: LSA Vereniging voor Letselschade ” Advocaten”, Landelijk Samenwerkingsverband Aandachtswijken”, Linguistic ” ” Society of America”, . . .

– soms krijg je te weinig hits door synonymie (mobbing, pesten) of inflectie (pesten, gepest)

• Information Retrieval (IR) zoekt relevante documenten voor een bepaald onderwerp in een grote hoeveelheid documenten

Markus Egg, Computercommunicatie B 2007

58

Information Retrieval: introductie 2 • zoekmachines zijn een soort van IR-systemen • twee kenmerken onderscheiden IR van het gewone zoeken in databases – vaagheid: the gebruiker kan zijn informatiebehoeften niet precies uitdrukken en formaliseren

– onzekerheid: het systeem heeft geen kennis over de inhoud van de documenten

• verschil tot Information Extraction (IE): extractie van relevante informatie voor een bepaald onderwerp uit een grote hoeveelheid documenten

• de auteurs van de documenten en hun gebruikers zijn ook meestal gescheidene groepen

• documenten zijn niet als onderdeel van een database geschreven of gestandaardiseerd Markus Egg, Computercommunicatie B 2007

59

Information Retrieval: introductie 3 • er wordt naar index-termen gezocht, niet direkt naar documenten • voorbereidende stap: indexopbouw – bepaal relevante termen en hun voorkomens in de documenten – termen zijn niet zomaar tekengroepen tussen spaties (anders zou string search voldoen)

– sla dit in een index op – beide taken zijn vrij ingewikkeld (zie presentatie volgende week) • ook zoekopdrachten worden na index-termen vertaald ¨ • ze worden aan de hand van de index geevalueerd (niet de documenten)

• een index is voor het beantwoorden van zoekopdrachten geoptimaliseerd, wat het beantwoorden heel effectief maakt Markus Egg, Computercommunicatie B 2007

60

Information Retrieval: introductie 4 • een index is statisch, hij verandert niet automatisch als documenten erbij komen/verdwijnen

• resultaten van een zoekopdracht worden m.b.t. hun relevantie gerangschikt • de zoekprocedure (geformaliseerd als een algoritme) moet de relevantie van documenten voor een zoekopdracht kunnen beoordelen

– algoritmen voor deze rangschikking kunnen worden gemisbruikt om webpagina’s na voren te schuiven ( search engine optimisation”) ” – voorbeeld: pagina’s voor verzekeringen


61

Information Retrieval: vectorruimtemodellen 1 • documenten worden met betrekking tot hun index-termen gekarakteriseerd/ ¨ geevaluateerd

• elk document krijgt krijgt als waarde een vector • de dimensies zijn de index-termen, er zijn dus heel veel dimensies • de waarde m.b.t. een index is het aantal voorkomens van de term (vaak is de waarde 0)

• een metriek voor de overeenkomst tussen twee documenten is de cosinus van de hoek tussen hun vectoren

• zoekopdrachten worden ook als vectoren ge¨ınterpreteerd


62

Information Retrieval: vectorruimtemodellen 2 • heel triviaal voorbeeld: vectorruimtemodel met maar twee index-termen Bush

<,<Bush.6>>

6 5

4 3 2 <,<Bush,1>>

1

<,<Bush,1>> 1

2

3

4

5

6

Kennedy

• Boolese zoekmethodes hebben een sterker microscopisch perspectief (van index-termen tot documenten)

• het vector-model heeft een sterker macroscopisch perspectief (er worden documenten en niet hun index-termen vergeleken) Markus Egg, Computercommunicatie B 2007

63

Information Retrieval: vectorruimtemodellen 3 • hoe vaker een term in een document voorkomt, hoe belangrijker hij is voor het document

• maar ruige gewichten voor termen (aantal voorkomens; tft,d ) suggereren dat alle termen voor de relevantie van een document evenwichtig zijn

– maar zeldsame termen zijn belangrijker ervoor – bijv. aansprakelijkheidsverzekering in tegenstelling tot verzekering – er wordt dus ook gekeken hoeveel documenten in de hele collectie van documenten D een term t inhouden (document-frequentie dft ) – daarmee wordt de inverse document-frequentie idft berekend – formule: idf = log |D| (log x = y ⇔ 10y = x) t

dft

– het gewicht van een term in een document wordt dan door de TF-IDF-formule berekend: tf-idft,d =tft,d ×idft Markus Egg, Computercommunicatie B 2007

64

Information Retrieval: evaluatie 1 • succes van IR heeft twee onderdelen – precisie (precision): hoeveel van de gevonden documenten zijn relevant? – formule: P =

|gevonden ∩ relevant| |gevonden|

– vangst (recall): hoeveel van de relevante documenten zijn gevonden? – formule: R =

|gevonden ∩ relevant| |relevant|

– fall-out: hoeveel van de irrelevante documenten zijn gevonden? – formule: F =

|gevonden ∩ irrelevant| |irrelevant|

• er is een inverse samenhang (of een trade-off ) tussen precisie en vangst • het hangt van de zoekopdracht af wat belangrijker is (bijv. van een gewone surfer in tegenstelling tot een jurist) Markus Egg, Computercommunicatie B 2007

65

Information Retrieval: evaluatie 2 • voorbeeld: 20 gevonden documenten, 18 ervan relevant, drie verdere relevante documenten zijn niet gevonden, 27 verdere irrelevante ook niet

– precisie: 18/20 = 90% – recall: recall 18/21 = 85,7% – fall-out: 2/29 = 6,9% • eerste poging voor een metriek die precisie en vangst samenbrengt: accuraatheid ´ – hoeveel documenten zijn correct geclassificeerd (relevant en gevonden/irrelevant en niet gevonden)

– in ons voorbeeld: (18+27)/50 = 90% – maar gezien de overgrote meerderheid van niet gevonden irrelevante documenten (in echte systemen boven de 99%) levert accuraatheid geen goede evaluatie op Markus Egg, Computercommunicatie B 2007

66

Information Retrieval: evaluatie 3 • tweede poging: F-waarde – als precisie en de vangst evenwichtig zijn: de gewogen gemiddelde ertussen 2PR – formule: F = P+R 18 2× 18 × – in ons voorbeeld: F = 1820 1821 = 0,87% 20 + 21

– dat is maar een vereenvoudigde versie van de formule met parameters voor de gewichten van F en R • een andere metriek kijkt naar de volgorde van de gevonden documenten: worden belangrijkere documenten eerst genoemd?


67

Information Extraction • vind en verzamel relevante informatie in documenten (en negeer de rest) • relevantie wordt vaak in vorm van sjablonen (templates) gedefineerd • formeel zijn dat (soms recursieve) paren van eigenschappen en nog niet ingevulde waarden

• zulke sjablonen kunnen met name als database-item worden gebruikt • IE betekent dat de sjablonen worden ingevuld op basis van informatie in documenten

• dus, IE is geen vorm van diepgaande tekstanalyse (laat staan begrijpen van teksten)


68

Information Extraction: voorbeeld 1 • de tekst Na de teleurstellende verkiezingen van 1972, waarbij D66 vijf zetels moest inleveren en de beoogde linkse meerderheid niet werd gehaald, trad Van Mierlo in de herfst van 1972 terug als fractievoorzitter. Hij werd gisteren opgevolgd door J.C. Terlouw.

• de sjabloon: aflossing” ”



OLD P ERSON



  NEW P ERSON      POSITION      ORGANISATION     TIME O UT    TIME I N


69

Information Extraction: voorbeeld 2 • resultaat 

OLD P ERSON

Van Mierlo

 NEW P ERSON   POSITION   ORGANISATION   TIME O UT 



 J.C. Terlouw    fractievoorzitter    D66    herfst 1972 

TIME I N

10-09-72

• recursieve structuren zijn mogelijk 

  OLD P ERSON    

NEW P ERSON



NAME

 SURNAME 

VOORZETSELS

...

 Mierlo      Van  


70

Information Extraction: uitdagingen • coreferenties: Van Mierlo refereert op dezelfde persoon als hij • tijd- en datums-uitdrukkingen zoals gisteren moeten naar een gestandardiseerd formaat vertaald worden

• als er geen informatie over een slot beschikbaar is moet dit leeg blijven (sjabloon niet helemaal ingevuld)

• negeer irrelevante informatie (verkiezingen) • eenvoudige linguistische analyse nodig voor passief: wie volgt nu op? • lexicalisch weten nodig: terugtreden van A en opvolgen van B is een aflossing van A door B


71

Information Retrieval: introductie 1

Recommend Documents