Ontdekken van Impressionisten m.b.v. afstanden tot bekende Impressionisten

Ontdekken van Impressionisten m.b.v. afstanden tot bekende Impressionisten Afstudeerproject Bachelor AI 2004/2005 1 juli 2005 Michiel Nieuwenhuijsen Universiteit van Amsterdam E-mail: [email protected] Roeland Weve Universiteit van Amsterdam E-mail: [email protected] Supervisors: Maarten van Someren Victor de Boer

Samenvatting In dit document beschrijven we onze methode voor het zoeken in documenten naar nog onbekende Impressionisten. Deze Impressionisten worden gevonden door te kijken naar de afstand tot bekende Impressionisten. We beschrijven de verschillende modules waaruit onze methode is opgebouwd. Enkele modules zijn: het zoeken naar personen in documenten, vergelijken of twee persoonsnamen bij dezelfde persoon horen, en het berekenen van een score om een bepaalde zekerheid te krijgen of een naam wel of niet tot het domein hoort. Ook kijken we hoe deze methode zich verhoudt tot andere IEmethodes. Om de werking van onze methode te evalueren, zullen we een aantal tests uitvoeren op het domein van Impressionisme. Omdat het onderzoek geïnspireerd is op het werk van Victor de Boer, zullen we kijken in hoeverre onze methode vergelijkbaar is met die van hem. Tevens zullen we kort bekijken of deze methode ook op andere domeinen toepasbaar is. Te denken valt aan andere kunststromingen, personen uit een bepaald sportteam proberen te halen of mensen die eenzelfde soort beroep uitoefenen bij elkaar proberen te vinden. Tot slot bespreken we nog op welke punten de methode fouten maakt, en hoe deze fouten beperkt zouden kunnen worden.

Afstudeerproject Bachelor AI 2004/2005

2

Inhoudsopgave 1. Inleiding .............................................................................................................................................. 4 2. Information Extraction ........................................................................................................................ 5 2.1 Relation Instantiation .................................................................................................................... 5 2.2 Afstandsmeting ............................................................................................................................. 5 3. Methode............................................................................................................................................... 7 3.1. Module 1: Google zoeken ............................................................................................................ 7 3.1.1. Problemen/nadelen bij gebruik van zoekmachines............................................................... 7 3.2. Module 2: HTML verwijderen..................................................................................................... 8 3.3. Module 3: Named Entity Taggers: NE en NER........................................................................... 9 3.4. Module 4: NiWeDistance........................................................................................................... 10 3.4.1. Problemen NiWeDistance .................................................................................................. 11 3.5. Module 5: Afstandsmeting......................................................................................................... 12 3.6. Module 6: Samenvoegen van namen en lijsten.......................................................................... 13 3.7. Berekening van de score ............................................................................................................ 14 4. Uitslagen experimenten..................................................................................................................... 16 4.1. Threshold: wat is de beste threshold .......................................................................................... 16 4.2. NE met en zonder leren en NER ................................................................................................ 17 4.2.1. Werking NE en NER .......................................................................................................... 17 4.2.2. Testen NE en NER.............................................................................................................. 18 4.2.3. De test met de afstandsmethode op 10 HTML documenten............................................... 20 4.2.4. De test met de afstandsmethode op 200 HTML documenten via Google .......................... 20 4.2.5. Conclusie ............................................................................................................................ 21 4.3. Vergelijking met Relation Instantiation ..................................................................................... 22 4.4. Is het zinvol om te bootstrappen ................................................................................................ 26 5. Verschillende domeinen .................................................................................................................... 29 5.1. Expressionisme .......................................................................................................................... 29 5.2. Voetballers in het team van het WK onder 20 in 2005 .............................................................. 29 5.4. Conclusie.................................................................................................................................... 30 6. Conclusie en toekomstig onderzoek.................................................................................................. 31 7. Literatuurlijst ..................................................................................................................................... 32 8. Gebruikte figuren .............................................................................................................................. 33 9. Gebruikte tabellen ............................................................................................................................. 33 10. Bijlage: werkverdeling .................................................................................................................... 34


3

1. Inleiding Het World Wide Web is een grote brei van websites bij elkaar. Om informatie hieruit te halen, zijn er vele zoekmachines die al deze websites geïndexeerd hebben en een gebruiker kan dan aan de hand van één of meerdere woorden op zoek gaan naar informatie. Er zijn verschillende mogelijkheden [BrightPlanet, 2004] om het zoeken effectiever te maken, maar tegenwoordig is dat niet meer genoeg. Mensen willen vragen kunnen stellen aan zoekmachines, als bijvoorbeeld: ‘Welk team won de WorldCup in 1989?’, ‘Wie was de president van Amerika in 1990?’ en ‘Welke planeten staan het dichtst bij de zon?’. Om deze vragen te beantwoorden kan men alle pagina’s met de hand uitlezen, categoriseren en relevante informatie gestructureerd opslaan. Dit is echter zeer tijdrovend, dus een automatische oplossing zou uitkomst bieden. Een methode hiervoor is informatie extractie (IE), dat automatisch bepaalde (semi-) gestructureerde informatie uit ongestructureerde informatiebronnen kan halen. IE is niet alleen geschikt voor internet websites, maar ook voor andere documenten, zoals email en nieuwsgroepberichten, Word documenten, Adobe Portable Document Format(PDF) documenten en Rich Text Format (RTF) documenten. Het is niet alleen mogelijk IE te gebruiken op digitale informatie, maar ook voor bijvoorbeeld op analoge televisie en radio fragmenten. Op dit moment zijn er al een aantal IE systemen, onder andere Annie [Annie, 2005] dat bestaat uit een aantal componenten, die ervoor zorgen dat het systeem voor allerlei doeleinden gebruikt kan worden. Annie is onder andere gebruikt om samenvattingen van bedrijfsverslagen te maken over gezond- en veiligheidsonderwerpen én het analyseren van football gerelateerd informatie als commentaar, nieuwsartikelen en websites, om video’s over football wedstrijden te voorzien van semantisch commentaar en deze conceptueel te indexeren. Een ander IE systeem is ArtEquAKT [Artequakt]. De aanpak van het ArtEquAKT-project is technieken van analyse en kennisverzameling te gebruiken om informatie te halen uit webpagina's, gegeven een bepaald domein, en om daarvan een knowledge base te bouwen met een bovenliggende ontologie. Het doel van Artequakt is om automatisch biografieën te laten maken aan de hand van een knowledge base die automatisch is opgebouwd door tekst fragmenten uit webdocumenten te annoteren [Kim, et al. 2003]. De genoemde systemen kunnen niet gebruikt worden voor ons doeleinde, omdat deze hiervoor niet gemaakt zijn. Wel geven ze een goed idee over wat erop dit moment voor IE systemen wordt gebruikt. Onze informatie extractie afstandsmethode houdt in om (onbekende) instanties te zoeken met behulp van (woord-)afstanden tot bekende instanties. Op deze manier kun je aan de hand van bekende gegevens, bijvoorbeeld 2 personen van een bepaalde kunststroming, de resterende personen proberen te vinden voor die kunststroming om de set compleet te maken. We zullen ons idee uitwerken aan de hand van Impressionisten: Is het ontdekken van Impressionisten mogelijk met behulp van afstanden tot bekende Impressionisten? Het idee is geïnspireerd op het idee van Victor de Boer om bepaalde relaties in een concrete vorm te brengen; ‘Relation Instantiation’. Hier zijn verschillende methodes voor, die allemaal tot doel hebben om relaties te vinden tussen instanties en concepten. Voorbeelden hiervan zijn om relaties te vinden tussen de instanties van een concept ‘stad’ en een ander concept ‘land’, of de relatie zoeken tussen instanties in de klasse ‘ArtStyle’ en instanties in de klasse ‘Artist’ in een ontologie die het kunst domein beschrijft [de Boer, 2005]. De opzet van het verslag is als volgt. In hoofdstuk 2 zullen we onze methode en die van Victor de Boer nader omschrijven: hoe ze werken en wat de verschillen en overeenkomsten zijn. In hoofdstuk 3 gaan we dieper in op de gebruikte modules. We vertellen hoe alles werkt, welke problemen we zijn tegengekomen, en wat er nog niet goed genoeg werkt. In het vierde hoofdstuk behandelen we een aantal experimenten die wij gedaan hebben. Daarna de uiteindelijke conclusies, hoe goed werkt de methode, waarom werkt het wel of niet en de uitslag van de vergelijking met Victor de Boer’s ‘Relation Instantiation’. Tot slot zullen we vermelden op welke manieren de methode volgens ons verbeterd kan worden.


4

2. Information Extraction Hier zullen we de methode van Victor de Boer introduceren, waarop onze methode is geïnspireerd. Tevens zullen we kort omschrijven wat onze methode precies inhoudt, en hoe deze staat in relatie tot de methode van Victor de Boer. 2.1 Relation Instantiation Relation instantiation [de Boer, 2005]: Dit onderzoek betreft een methode voor het automatisch vinden van instanties van een in een ontologie gedefinieerde relatie. Deze methode gaat er vanuit dat alle instanties van te voren al bekend zijn, en zijn verzameld in een knowledge base. Er moet alleen nog gevonden worden voor welke instanties een bepaalde relatie geldt of niet. Elke instantie krijgt een score (IS), die gebaseerd is op de score van de documenten waarin die instantie is gevonden (DS). De DS geeft aan hoe goed een bepaalde relatie wordt gerepresenteerd door het document, en hoe waarschijnlijk het is dat een in dat document gevonden instantie kan worden toegevoegd aan de knowledge base. De DS is gebaseerd op het aantal bekende instanties die in dat betreffende document zijn gevonden. 2.2 Afstandsmeting Op het internet komen vaak opsommingen voor van personen in verschillende vormen. Soms worden in een enkele zin meerdere personen achterelkaar genoemd, vaak staan er rijtjes van personen onder elkaar en meestal staan personen die iets met elkaar gemeen vaak vlak bij elkaar in documenten. Dit is interessant voor informatie-extractie: is het mogelijk om de resterende personen eruit te halen als je iemand uit zo een rijtje weet? Op die manier kun je proberen bepaalde vragen te beantwoorden als: • wie komen er allemaal uit de muziekband X, als je maar een beperkt aantal personen weet uit die band? • wie spelen er allemaal in de film Y, mocht je een aantal (hoofdrol-)spelers weten? • wie zijn naast Claude Monet, Pierre Auguste Renoir en Alfred Sisley nog meer Impressionistische schilders? Onze informatie extractie afstandsmethode houdt in om (onbekende) instanties te zoeken met behulp van (woord-)afstanden tot bekende instanties. Deze methode van afstandmeten is geïnspireerd door het project van Victor de Boer. Hij is bezig een methode te ontwikkelen om instanties van een bepaalde relatie te vinden uit een aantal documenten. Hij is dit aan het testen op het domein van Impressionisten en Expressionisten, vandaar dat wij hebben besloten om ons voornamelijk op het domein van Impressionisten te richten. Op deze manier kunnen we de verschillende methodes met elkaar vergelijken. Onze methode werkt als volgt: 1. Bepaal een domein D, bijvoorbeeld Impressionisten en zorg ervoor dat er genoeg documenten zijn over dit domein. 2. Bepaal ook een seed-list met een aantal seeds die over het domein D gaan. In het geval van domein D kun je als seeds bijvoorbeeld ‘Claude Monet’, ‘Berthe Morisot’ en ‘Edgar Degas’ nemen. Deze drie namen vormen samen de seed-list. Meer of minder personen is ook mogelijk. 3. In elk van de documenten uit D moeten de persoonsnamen die er in staan gemarkeerd worden en de namen uit de seed-list moeten ook gemarkeerd worden. 4. Bepaal vervolgens per document de afstand van elke naam tot aan de dichtstbijzijnde seed uit de seed-list. Hoe kleiner de afstand, hoe beter de score. 5. Voeg alle zelfde namen bij elkaar en bereken een bepaalde score aan de hand van hoeveel keer de naam is gevonden, uit welke document de naam komt, uit hoeveel verschillende documenten, etc. 6. Sorteer de uiteindelijke lijst op score. Hoe beter de score, des te waarschijnlijker het is dat het een persoon is die ook tot domein D behoort.


5

Er is een aantal overeenkomsten en verschillen tussen onze methode, en de methode van Victor de Boer. De grootste overeenkomst is dat allebei de methodes voor een bepaald domein een aantal onbekende instanties te vinden, aan de hand van enkele bekende instanties. Victor de Boer probeert die instanties te vinden door een bepaalde relatie te vinden, die de onbekende met de bekende instanties verbindt. Die relatie hoopt hij te bewijzen door elk document een bepaalde score te geven, zodat die score iets zegt over de overige namen die in dat document staan. Onze methode probeert dat bewijs echter te vinden door te kijken naar de afstand in woorden van de onbekende instanties, tot de bekende instanties. Het uitgangspunt van Victor de Boer is dus dat de instanties van een bepaald domein in dezelfde documenten zullen staan, en ons uitgangspunt is dat de instanties van een bepaald domein binnen die documenten dicht bij elkaar zullen staan. Onze methode lijkt ook aan te sluiten op Google Sets [Google, 2002] Helaas is er weinig informatie over hoe dat precies werkt. Deze applicatie zoekt aan de hand van een aantal opgegeven woorden de woorden die erbij horen. Als je bijvoorbeeld de kleuren Blue, Yellow en Red opgeeft, dan krijg je als resultaat onder andere Green, Black, White, Orange en Purple terug. De geruchten [Questsin, 2005] op internet gaan dat Google alle pagina’s in zijn database afgaat en dan tabellen en/of lijsten opzoekt en de inhoud hiervan opslaat. Maar omdat het algoritme niet bekend is, kunnen we ook niet zeggen hoe de werking van Google Sets zich verhoudt tot onze methode. We kunnen alleen afgaan op de geruchten en als we daar naar kijken, dan werkt onze methode wel anders. Google Sets maakt namelijk geen gebruik van afstanden tussen de gevonden namen. Alle namen in tabellen en rijtjes tellen even zwaar.


6

3. Methode Het programma is opgebouwd uit verschillende modules. De output van de ene module is de input van de andere module. In dit hoofdstuk zullen we elke module bespreken en vertellen wat de beperkingen zijn, wat we er van verwachten, wat de problemen waren die we tegen kwamen en hoe we die hebben opgelost. 3.1. Module 1: Google zoeken Om personen te zoeken zijn er documenten nodig die over het domein gaan waar op gezocht wordt. Voor het domein Impressionisme en Expressionisme zijn er documenten beschikbaar, maar voor andere domeinen zijn deze er niet. Mede omdat het ons interessant leek om ons programma op andere domeinen te testen, besloten we het zoeken naar documenten te automatiseren. Het enige wat dan nodig is, is het opgeven van een zoekterm en de hoeveelheid te downloaden documenten. Bijvoorbeeld de zoekterm ‘Impressionism OR Impressionists’ en maximaal 20 documenten. Op die manier hopen we 20 documenten te vinden die gaan over Impressionisme. Om specifieker te zoeken kan ook een zoekterm als ‘Impressionism OR Impressionists -neo -post -american’ opgegeven worden. In de hoop om dan enkel pagina’s terug te krijgen die alleen over Impressionisme gaan en niet over NeoImpressionisme, Post-Impressionisme en American-Impressionisme. Na het zoeken op een zoekterm, geeft Google een resultatenlijst terug met links, beschrijvingen en titels. Het handige van Google is dat de gevonden website-links tussen en tags staan, dus met een simpele reguliere expressie kunnen de links uit de resultatenlijst gefilterd worden. Al deze links worden één voor één geopend en de inhoud wordt daarna opgeslagen in tekstbestanden. Mocht je 100 links terug willen krijgen en er zijn maar 50 links gevonden, dan werkt de code verder op de 50 links die gevonden zijn. Verder worden alleen de pagina’s opgeslagen die uit HTML code bestaan, dat wil dus zeggen dat de PDF, PS, DOC, XLS, PPT en RTF documenten niet worden ingelezen en opgeslagen, simpelweg omdat deze documenten lastig zijn om te zetten naar tekstformaat. Het komt ook regelmatig voor dat een website down is. Als dat het geval is, zal de desbetreffende pagina niet worden opgeslagen. De code is natuurlijk aan te passen voor andere zoekmachines, zoals bijvoorbeeld Altavista, Teoma, Yahoo, etc. Daarvoor moet de reguliere expressie aangepast worden om de links uit de resultatenpagina te filteren en de zoek-URL moet worden aangepast. 3.1.1. Problemen/nadelen bij gebruik van zoekmachines Het gebruik van een zoekmachine om documenten te verzamelen werkt niet zonder nadelen. We zullen kijken in hoeverre de verkregen zoekresultaten afwijken van de verwachtte resultaten. Een interessant domein om te testen, is bijvoorbeeld het domein van ‘presidenten’. In Google zouden we dan als zoekterm bijvoorbeeld ‘president OR presidents’ opgeven, en als seed-list kunnen we dan [‘Bush’, ‘Clinton’] gebruiken. Wat meteen opvalt, is de grote diversiteit aan verschillende talen. Bij de eerste twintig resultaten staan een aantal Amerikaanse sites, een Franse, Duitse, Estse, Mexicaanse en Italiaanse site. Bij al de niet-Amerikaanse sites is de kans groot dat er geen enkele seed zal worden gevonden, waardoor die site ook geen namen op zal leveren die uiteindelijk in de output komen te staan. De reden voor deze verschillende resultaten is dat ‘President’ een woord is dat in enorm veel talen gebruikt wordt, en het zal ook gebruikt worden in merknamen (brie). De zoekterm ‘president USA’ geeft al veel meer geschikte resultaten, alleen gaan een aantal van de sites over de band ‘The Presidents of the USA’. Doordat de namen van de seed-list niet in die sites voorkomen, zal dit niet direct een negatief effect hebben op de resultaten. Een ander domein is ‘voetballers’. In Engeland is voetbal ‘football’, dus als zoekterm gebruiken we ‘football players’. Hier valt meteen op dat er meer resultaten komen over ‘American Football’, dan over ‘voetbal’. Om die resultaten zoveel mogelijk uit te sluiten, veranderen we de zoekterm in ‘football players –nfl –american’. De beste resultaten worden echter verkregen door ‘soccer’ toe te voegen aan de zoektermen.


7

Uiteraard is het ook een optie om de namen uit de seed-list toe te voegen aan de zoekterm. Het gevaar is dan echter dat er een groot aantal resultaten komen die specifiek over een bepaalde persoon gaan, bijvoorbeeld George Bush, en niet zozeer over presidenten in het algemeen. Door als zoekterm ‘president Bush’ te gebruiken, beperken we het domein eigenlijk ook tot George Bush. De kans is groot dat we dan in de resultaten geen andere (Amerikaanse) presidenten krijgen, maar eerder mensen uit de omgeving van Bush; bijvoorbeeld ministers, of Laura Bush, de vrouw van. Een ander verhaal betreft het domein van Impressionisten. Bij zoeken naar ‘Impressionism OR Impressionist’ komen er veel resultaten waarin ook neo-, post-, en American-Impressionists staan. Dit hoeft niet direct een ongewenst resultaat te zijn, maar hier moet wel rekening mee worden gehouden. ‘Vincent van Gogh’ wordt bijvoorbeeld meestal als neo-Impressionist aangeduid, terwijl de meeste bronnen hem niet als ‘echte’ Impressionist zien. Omdat hij dus wel regelmatig op dezelfde sites wordt genoemd als ‘echte’ Impressionisten, zal hij door ons programma ook als Impressionist bestempeld kunnen worden, terwijl de gebruiker misschien alleen geïnteresseerd is in ‘echte’ Impressionisten. Om alleen sites te krijgen met ‘echte’ Impressionisten, kan ‘-neo –American –post’ worden toegevoegd aan de zoekterm, zodat er geen site wordt teruggeven die een van deze woorden bevat. Een andere ongewenste bijkomstigheid van Google is dat er af en toe resultaten komen, waarin die zoekterm helemaal niet voorkomt. Een extreem voorbeeld is de zoekterm ‘raar kapsel’, het eerste resultaat daarmee is de site van minister-president Jan Peter Balkenende. Dit komt omdat er een groot aantal sites een link naar die betreffende site hebben, onder de woorden ‘raar kapsel’. Een ander voorbeeld is ‘miserable failure’, dat levert een link naar de biografie van George Bush. Een eenduidige oplossing voor dit probleem lijkt niet voorhanden. Sommige domeinen, of zoektermen, zijn op meerdere manieren te interpreteren, waardoor er ook verschillende resultaten naar voren komen. Het is een optie om het domein te specificeren door een term uit de seed-list toe te voegen aan de zoekterm, maar het gevaar is dat het domein zich dan beperkt tot alleen die persoon. De beste resultaten zullen worden verkregen door domeinen te kiezen die maar op één manier is te interpreteren, bijvoorbeeld Impressionisten of Formule 1-coureurs. 3.2. Module 2: HTML verwijderen Het zoeken naar persoonsnamen uit HTML documenten kan alleen als alle HTML code weg is en pure tekst overblijft. Ten eerste omdat sommige Named Entity Taggers alleen al vast lopen op de HTML code en ten tweede, mocht de tagger de HTML documenten kunnen inlezen, dan geeft deze alleen maar rare namen terug. De HTML parser1 van Python leek ons het makkelijkste te gebruiken, maar liep in praktijk veel vast op incorrecte HTML code. Het grootste probleem waren niet de tags die niet werden afgesloten, zoals bijvoorbeeld zonder een , maar juist niet-bestaande HTML code en verkeerde commentaar tags waren voor de HTML parser funest. Voordat HTML documenten geparsed konden worden door Python, hebben we een boel reguliere expressies en aanpassingen moeten programmeren. Een opsomming van de meest voorkomende problemen die zijn opgelost: • links werden wel weggehaald, maar in plaats daarvan kwam een nummer tussen blokhaken te staan, bijvoorbeeld [12], met een verwijzing naar de link. Waarom dit standaard het geval is, is onbekend. Het was mooier geweest om hier een optie van te maken. Om het weg te krijgen was het nodig om de HTML parser klasse opnieuw te schrijven. • De parser printte de tekst alleen op het scherm. Een oplossing leidde ertoe dat de tekst wel werd opgeslagen in een bestand, maar met maximaal 75 tekens breedte. Op die manier werden namen ook opgesplitst met een voornaam als laatste woord en achternaam als begin van de zin op de nieuwe regel. • Commentaar wordt vaak als of als geschreven, in plaats van . Een aantal reguliere expressies waren hiervoor nodig om het commentaar te verwijderen voordat het werd geparsed. • Commentaar in commentaar, zoals hier: 1

met ‘parsen’ wordt het verwijderen van iets bedoelt, in dit geval de HTML code..


8

• •

Horizontale lijnen in de HTML code,
, werden door de parser omgezet naar ‘----‘ streepjes. Dit leidde tot bizarre namen die werden gevonden door de Named Entity Taggers. <script> en <noscript> tags moesten ook met reguliere expressies worden verwijderd, aangezien in elk HTML document een andere versie van die tags stond.

Omdat een aantal Named Entity Taggers na al deze aanpassingen nog problemen hadden met punten en bepaalde karakters in de namen, worden na het parsen nog twee dingen gedaan, namelijk: • Verwijder een punt die volgt na de combinatie spatie-hoofdletter. Namen als ‘George W. Edwards’, worden dan niet gezien als twee namen ‘George W’ en ‘Edwards’, maar als één naam . • Vervang de karakters die worden getokeniseerd door Named Entity Taggers, namelijk: ‘çéëèêáäàâóöòôøúüùûíïìîÉËÈÊÁÄÀÂÓÖÒÔÚÜÙÛÍÏÌÎ’ door respectievelijk ‘ceeeeaaaaooooouuuuiiiiEEEEAAAAOOOOUUUUIIII’. Dit zorgt ervoor dat ‘Cézánne’ hetzelfde is als ‘Cezanne’ en ‘Cézanne’ en dat ‘Cézanne’ niet getokeniseerd wordt als ‘C é zanne’, wat helaas door een Named Entity Tagger gedaan wordt. Al het verwijderen van HTML had tot gevolg dat namen in onder andere opsommingen en lijsten achterelkaar zonder punten en/of komma’s werden neer gezet. Namen als deze: 'Claude Monet Edgar Degas Alfred Sisley Auguste Renoir Frederic Bazille Mary Cassatt’ werden vervolgens gevonden door Named Entity Taggers. Om dat op te lossen worden alle ,
en vervangen door komma’s. Deze aanpassing zorgde er echter voor dat de Named Entity Tagger NER nu namen vond als ‘Web Search, , , , ,\n(enter) , , , , , Books’ en ‘George , . , . , .’. Dit laatste voorbeeld is opgelost door met een reguliere expressie alle punten, spaties en komma’s te verwijderen aan het einde van een naam. De gevonden ‘namen’, waar punten en komma’s veelvuldig voorkwamen tussen twee woorden in, konden we oplossen door ‘|^@*’ neer te zetten aan het einde van elke regel. Sommige taggers kijken alvast op de volgende regel of de naam daar doorloopt. Op HTML pagina’s gebeurt dit zelden tot nooit, dus konden wij daar een scheidingsteken neerzet. Dit teken zorgde ervoor dat de tagger wist waar in ieder geval de namen eindigde. 3.3. Module 3: Named Entity Taggers: NE en NER Om namen te ontdekken in stukken tekst, is er een (persoons-)naam tagger nodig, oftewel een ‘Named Entity Tagger’. Deze programma’s markeren meestal niet alleen de persoonsnamen, maar ook organisaties, datum/tijd, hoeveelheden, geld bedragen, percentages en andere entiteiten in documenten [Wei Li, et al 2003]. Een voorbeeld van een stuk tekst waarbij de persoonsnamen gemarkeerd zijn: The core of the earliest Impressionist group was made up of [PER Claude Monet ], [PER Pierre-Auguste Renoir ], and [PER Alfred Sisley ]. Alle personen die hier gemarkeerd worden, zijn potentiële Impressionisten en aan de hand van de afstandsmethode willen we de personen die we in deze module taggen een bepaalde score geven. Aangezien we geen tijd hadden om er zelf één te maken, moesten we opzoek naar een aantal bestaande versies. De eerste tagger die we onderzochten was Annie, een programma met een grafische user interface (GUI) waarbij je handig kan zien wat er getagged wordt. Aan dit programma kleefde echter wat nadelen: - Ten eerste een zeer slechte score op het domein van Impressionisten. We moesten Annie dan eerst gaan trainen. - Ten tweede moesten we alle documenten met de hand één voor één importeren en exporteren. Dit was niet handig, aangezien we een zo dynamisch en automatisch mogelijk programma wilden maken2.

2

Later bleek er voor Annie wel een automatische optie te zijn: Annie Named Entity Tagger Version 1.0: http://www.media-style.com/index.jsp?folderPK=754 Helaas kwamen we hier te laat achter, om die nog te implementeren en testen.


9

De andere Named Entity Taggers die we hadden gevonden via het internet staan in tabel 1. naam NET NE ANNIE MINIPAR NER

taal / OS Onbekend / Internet Perl en C++ / Linux Java / Alle C++ / Alle Java / Alle

link naar het web http://sds.colorado.edu/NET/ http://l2r.cs.uiuc.edu/~cogcomp/asoftware.php?skey=NE http://gate.ac.uk/ie/annie.html http://www.cs.ualberta.ca/~lindek/minipar.htm http://ciir.cs.umass.edu/~weili/research.html

Tabel 1. De verschillende Named Entity Taggers

Na het één en ander te hebben uitgeprobeerd, besloten we om met 2 verschillende taggers door te gaan, namelijk NE en NER. Dat zijn de enige 2 taggers waarvan wij wisten dat we deze konden automatiseren. De andere taggers werkte óf alleen via internet (NET) of moesten eerst nog getraind worden (MiniPar). En dan was het nog de vraag of ze goed werkte op het Impressionisten domein. Verderop in het verslag zal er getest worden welke het beste werkt: NE of NER 3.4. Module 4: NiWeDistance Deze module is nodig om te bepalen of twee persoonsnamen wel of niet behoren bij dezelfde persoon. Deze methode hebben we NiWeDistance gernoemd, naar de eerste letters van onze achternamen. De input bestaat uit twee namen en een threshold, en de output is een 1, in het geval de namen volgens de code bij dezelfde persoon horen, en anders een 0. De code bestaat uit een aantal if-statements, waarbij we de namen op verschillende manieren met elkaar vergelijken. Als een bepaald statement geldt, kunnen we zorgen dat er een bepaalde output wordt gegeven. Wanneer de verschillende delen van de namen op geen enkele manier met elkaar overeenkomen, worden de namen nog vergeleken aan de hand van de Levenshtein-distance. Dit algoritme geeft het aantal letters dat verschillend is tussen de twee namen. Voordat we de delen van de namen met elkaar gaan vergelijken, worden de namen eerst nog bewerkt. Om de verschillende woorden van de naam te onderscheiden, gebruiken we een white-space-tokenizer, zodat elke cluster van letters, gescheiden door spaties, wordt gezien als een woord. Verder willen we dat ‘Vincent van Gogh’, en ‘van Gogh, Vincent’ door de code als precies dezelfde naam worden gezien. Daarvoor worden alle woorden die voor de komma staan verwijderd, en achteraan de naam gezet. ‘van Gogh, Vincent’ wordt dan ‘Vincent van Gogh’. Omdat we uitgaan van persoonsnamen, richten we ons vooral op het laatste woord van de naam, waarbij we er vanuit gaan dat dit de achternaam is. Tot slot worden alle letters nog eens omgezet naar lowercase, zodat ‘van Gogh’ en ‘Van Gogh’ ook als gelijken worden gezien. Omdat we ons hebben gericht op het domein van Impressionisten, hebben we de code ook proberen te optimaliseren voor namen die veel in dit domein voorkomen. Een voorbeeld van een naam die veel voorkomt, is die van ‘Bazille’. Deze wordt onder andere geschreven als ‘Frederic Jean Bazille’, en ‘Frederic Bazille’. Hiervoor hebben we besloten dat als het eerste en het laatste woord van twee namen overeenkomt, eventuele woorden die er tussenin staan er niet meer toe doen. Als een naam uit één woord bestaat, en de andere naam uit meerdere woorden, kijken we of dat ene woord overeenkomt met het laatste woord van de tweede naam. Dus: ‘Bazille’ en ‘Frederic Bazille’ horen bij elkaar. In namen krijgen we ook te maken met afkortingen. Bijvoorbeeld ‘Vincent v Gogh’. Om dit op te vangen, zoeken we de woorden die uit 1 letter bestaan op, en kijken of deze letter overeenkomt met de beginletter van een woord uit de andere naam. Het kan ook voorkomen dat de namen die met elkaar worden vergeleken, een verschillend aantal woorden hebben. In dit geval vergelijken we alle woorden van de kortste naam, met alle woorden van de langste naam. Als elk woord uit de kortste naam overeenkomt met een van de woorden uit de


10

andere naam, dan worden deze namen als gelijk gezien. Hiervoor hebben we wel als extra restrictie gegeven dat het laatste woord uit de langste naam, moet voorkomen in de kortste naam. Bijvoorbeeld: 'Pierre Auguste Renoir' en 'Renoir, Auguste' matchen wel, terwijl 'Georges' en 'Georges Saurat' niet mogen matchen. Als al van de bovenstaande regels niet gelden, dan wordt er als laatste nog gekeken naar de Levenshtein-, of edit-distance. Dit hebben we toegevoegd omdat namen vaak op verschillende manieren met elkaar worden vergeleken. Bijvoorbeeld, ‘Pissarro’ / ‘Pissaro’, en ‘Degas’ / ‘Dega’. Deze Levenshtein-distance geeft het aantal letters dat verschillend is, tussen twee namen. De afstand tussen ‘Monet’ en ‘Manet’ is 1. De afstand wordt gedeeld door de lengte, in aantal letters, van de langste naam. Op deze manier ligt de Levenshtein-distance altijd tussen 0 en 1, zodat we een bepaalde threshold kunnen opgeven. De formule voor deze distance is: wordDistance = 1 - ( distance(w1, w2) / longestString )

Hoe hoger deze distance, hoe meer letters er, procentueel gezien, overeen komen. 3.4.1. Problemen NiWeDistance Omdat de NiWeDistance met een threshold werkt, is het eerste probleem al een goede threshold te vinden. Bij het hoofdstuk ‘experimenten’ zal er gezocht worden naar een goede threshold. Een ander probleem is het feit dat een aantal mensen dezelfde achternaam hebben, bij sommige artikelen zal dit minder vaak voorkomen en bij andere artikelen wat vaker. Voor Impressionisten komt dit een aantal keer voor: ‘Theodore Rousseau en Henri Rousseau’, en ‘Jacob Maris en Matthijs Maris’ zijn bekende voorbeelden. Dit is eigenlijk het grootste probleem voor NiWeDistance, want als de Named Entity Tagger alleen ‘Maris’ vindt als naam, dan zal dit matchen met zowel ‘Jacob Maris’ als ‘Matthijs Maris’. Meestal is het de fout van de Named Entity Tagger, want die pakt vaak alleen de achternaam van een persoon, in plaats van de gehele naam. Dus een betere Named Entity Tagger zou het probleem al gedeeltelijk kunnen oplossen. Echter zullen sommige auteurs nog steeds alleen de achternaam gebruiken: But applying the paint in tiny strokes allowed Monet, Renoir, or Cassatt to display color sensations openly, to keep the colors unmixed and intense, and to let the viewer's eye mix the colors. Het is simpelweg hopen dat als er in domein een achternaam meerdere malen voorkomt voor andere personen, dat de auteur dan niet alleen de achternamen gebruikt, maar ook de voornaam en/of voorletter(s).


11

3.5. Module 5: Afstandsmeting In deze module wordt aan de hand van de gevonden namen, per document gekeken wat de afstand (in aantal woorden) is van een bepaalde naam, tot een naam die voorkomt in de seed-list. Deze module krijgt als input per document, de gevonden namen met de bijbehorende posities in de tekst, de posities van de gevonden seeds, en de documentscore van het betreffende document. De output bestaat uit, per document, de namen die als invoer zijn gegeven aan de afstandsmeting, met de bijbehorende afstand tot de dichtstbijzijnde seed. Per naam wordt ook toegevoegd uit welk bestand de naam is gehaald. Als in een document geen seeds zijn gevonden, is het ook niet mogelijk om afstanden te berekenen. In dat geval wordt voor dat document een lege lijst teruggegeven. De kortste afstand van een naam tot een seed wordt nu gevonden door de positie van een naam te vergelijken met de posities van de gevonden seeds, en vervolgens de kortste afstand te retourneren. Dit is de kleinste afstand tot een gevonden seed. Het is ook mogelijk om namen uit een bepaald document een bonus te geven op de gevonden afstand. Op deze manier wordt de afstand van namen uit een document met een hoge documentscore kleiner, vergeleken met de afstand van namen uit een document met een lage documentscore. In dit geval wordt de berekende afstand van een naam gedeeld door de documentscore. Hoe de documentscore precies wordt berekend, staat verderop in dit artikel. Een voorbeeld van een getagged document is: The leaders of the independent movement were [PER Claude Monet ] , [PER August Renoir ] , [PER Edgar Degas ] , [PER Berthe Morisot ] , and [PER Mary Cassatt ] . Als we nu als seed-list ‘Claude Monet’, en ‘Mary Cassatt’ gebruiken, dan krijgen de namen de afstanden die te zien zijn in tabel 2. naam August Renoir Edgar Degas Berthe Morisot

afstand 1 2 2

Tabel 2. Naam en afstand


12

3.6. Module 6: Samenvoegen van namen en lijsten De output van de afstandsmeting bestaat uit namen en hun score die ze tot nu toe hebben. Tevens staat er bij elke naam uit welk documentnummer de naam komt. Van deze lijst willen we dat alle namen die bij elkaar horen, bij elkaar gevoegd worden. Dus ‘Mary Cassat’ moet samen gevoegd worden met ‘M. Cassat’ en ‘Vincent van Gogh’ met ‘V. van Gogh’, etc. Hoe de score per persoon wordt berekend, staat in het volgende hoofdstuk. Tevens worden de documentnummers bij elkaar gevoegd. In tabel 3 volgt een klein voorbeeldje van hoe dat eruit ziet. input: namenlijst [ [0.45,'Sargent',[8]], [0.62,'Berthe Morisot',[7]], [1.08,'Berthe Morisot',[8]], [1.09,'Cassatt', [4]], [0.68,'M. Cassatt',[4]] ]

output: samengevoegde namelijst [ [0.06,['Berthe Morisot','Berthe Morisot'],[7,8]], [0.13,['Cassatt', 'M. Cassatt'], [4]], [0.13,['Sargent'], [8]]] ]

Tabel 3. Input en output van module 6

Op deze manier is duidelijk te zien hoe vaak een naam is gevonden, in hoeveel verschillende documenten een naam komt en wat de totale score is. Het vergelijken van de namen gebeurt met de NiWeDistance. Helaas werkt het samenvoegen niet helemaal goed en het gebeurt af en toe dat er toch nog twee keer namen niet worden samengevoegd en het kan ook voorkomen dat er twee verschillenden namen bij elkaar worden gevoegd. Een mooi voorbeeld is ‘Camille Pissarro’. Deze naam wordt nog wel eens anders gespeld en daardoor kan het gebeuren, het ligt wel aan de volgorde, dat deze naam meerdere keren voorkomt in de samengevoegde lijst. Dit kan gebeuren in het volgende scenario: ‘Pissaro’ komt in de lijst te staan, met een score en een document. Stel dat ‘Camille Pissarro’ vervolgens toegevoegd moet worden in de lijst. Deze twee namen matchen niet: >>> NiWeDistance('Pissaro','Camille Pissarro',0.83) ->

0

Dus die worden ook niet samengevoegd en komen allebei apart in de lijst te staan. Als nu ‘Camille Pissaro’ ook nog eens wordt gevonden, matched deze als eerste met ‘Pissaro’. Die twee worden samengevoegd. Het resultaat is dan: [ lijst 1: [score, ‘Pissaro’, ‘Camille Pissaro’, documenten] lijst 2: [score, ‘Camille Pissarro’, documenten] ]

Naarmate er vaker de naam ‘Camille Pissaro’ (en variaties) worden gevonden, des te uitgebreider de twee lijsten groeien, het ligt er maar net aan welke namen wel en niet matchen. Het is wel zo dat steeds de eerste lijst geprobeerd wordt om te matchen, dus op ten duur stopt de tweede lijst met groeien, omdat elke variatie van ‘Camille Pissaro’ matched met de voorkomens in de eerste lijst. Andere voorbeelden zijn ‘Georges Seurat en Pierre Seurat’, ‘August Renoir en Pierre Auguste Renoir’ en ‘Edouard Manet en Eugene Manet’. Deze 6 namen komen dus ook voor in de test bij de Impressionist, maar meestal is het zo dat één naam vrij hoog komt (b.v. plaats 1) en de andere vrij laag (b.v. plaats 40). Het kan ook voorkomen dat twee verschillende namen bij elkaar worden gevoegd. Dit ligt dan aan de threshold die je kiest bij de NiWeDistance. Als de threshold 0.8 is, dan zullen Monet en Manet met elkaar matchen en dus ook bij elkaar worden gevoegd. Het correct instellen van de threshold is dus erg belangrijk.


13

3.7. Berekening van de score Het doel van de berekening van de score is om uiteindelijk bij een bepaalde naam te kunnen zeggen of het wel of niet waarschijnlijk is dat deze naam bij het domein hoort. Hoe lager de score, hoe waarschijnlijker het is dat een persoon bij het domein hoort. Om deze score te kunnen berekenen, hebben we de volgende gegevens nodig: - het totale aantal gevonden personen - het totale aantal keren dat een bepaalde naam is gevonden - het aantal documenten waarin we zoeken - het aantal documenten waarin een bepaalde naam is gevonden Met deze gegevens kunnen we een indicatie krijgen over bepaalde percentages. De percentages die voor ons van belang zijn: - het percentage documenten waarin een naam voorkomt, op het totale aantal documenten. - het percentage van het aantal voorkomens van een bepaalde naam, op het totale aantal namen. Ook is het mogelijk om elk document een documentscore te geven. Hierdoor kunnen namen die voorkomen in documenten samen met één of meerdere namen uit de seed-list een soort bonus kunnen krijgen. Een bekende manier van het berekenen van de score voor een document is TF-IDF [Jurafsky & Martin, 2000a]. De ‘Term Frequency - Inverse Document Frequency’ is een combinatie van twee formules die aangeeft hoe goed een bepaald document is. Dit is belangrijk in IE, want in de minder goede documenten zal waarschijnlijk minder belangrijke informatie staan. De Term Frequency (TF) telt simpelweg hoeveel keer een term is gevonden in een document. De Document Frequency is het aantal documenten dat een bepaalde term bevat. De Inverse Document Frequency (IDF) zorgt er dan voor dat documenten waar veel termen in staan, minder nuttig worden gevonden [de Rijke, 2004]. TF-IDF lijkt ons echter niet geschikt voor ons methode. TF-IDF gaat er vanuit dat documenten waar veel termen in staan, minder nuttig worden gevonden. In ons geval is een document waarin veel termen (uit de seed-list) staan, juist wel nuttig, omdat de kans groot is dat er nog meer termen in voorkomen die voor dat domein interessant zijn. De documentscore die wij berekenen is als volgt: docScore = 1 + log2(foundSeeds * foundDifferentSeeds^2) Hier is foundSeeds het totale aantal gevonden seeds in dat document, en foundDifferentSeeds is het aantal verschillende seeds dat voorkomt in dat document. De docScore is altijd minimaal 1, en

door de score logaritmisch te berekenen zullen extreem hoge scores niet al te zwaar meetellen. Dit is om te voorkomen dat er alleen maar namen worden teruggegeven die in een document met een hoge score staan. Per individueel voorkomen van een naam weten we wat de afstand (in aantal woorden) is tot de dichtstbijzijnde naam uit de seed-list. Als extra optie is het mogelijk om de gevonden afstand nog eens te delen door de docScore. Zo krijgt een naam die in een ‘goed’ document staat een extra bonus. Uiteindelijk krijgen we één grote lijst, met daarin elke naam die in de tekst als [PER …. ] is getagged, in welk document die naam staat, en wat de kortste afstand tot een seed is. Nu gaan we voor al deze namen proberen of deze naam volgens de NiWeDistance overeenkomt met een andere naam uit die lijst. Op deze manier krijgen we bijvoorbeeld alle voorkomens van Renoir bij elkaar, waarbij we elke keer de individuele afstanden optellen, zodat we een totale afstand krijgen. Door deze totale afstand te delen door het aantal keren dat Renoir is gevonden, hebben we de gemiddelde afstand voor deze persoon. Door alleen te kijken naar deze gemiddelde afstand zijn we er nog niet. Immers, als Renoir in 20 van de 30 documenten voorkomt met een gemiddelde afstand van 10 woorden, en ene John Smith komt in 1 document voor met een gemiddelde afstand van 1 woord, wil dat niet zeggen dat John Smith een hogere waarschijnlijkheid heeft om bij het domein te horen. Hiervoor kijken we ook naar de eerder genoemde percentages, namelijk het percentage documenten waarin de naam voorkomt, en het percentage van het aandeel van deze naam op alle namen. Hiervoor delen we de gemiddelde afstand van een persoon nog eens door het product van deze twee percentages, waardoor Renoir alsnog beter scoort. De uiteindelijke formule waarmee de score van een verzameling van een naam wordt berekend is:


14

impScore = (score / len(item[1]) ) / (numberOfDifferentDocs * foundItems)

Waarbij: - score / len(item[1]) = gemiddelde score voor een verzameling namen. numberOfDifferentDocs = percentage van het totale aantal documenten waarin voorkomens uit deze verzameling voorkomen. - foundItems = percentage van het totale aantal namen waarin voorkomens uit de verzameling voorkomen.


15

4. Uitslagen experimenten Voor de experimenten gebruiken we de volgende methodes om de score te berekenen: - Recall / Precision: Om na te gaan hoe goed of hoe slecht een informatie extraction methode werkt, kun je gebruik maken van de recall en precision. De recall geeft het vermogen van een systeem aan om relevante documenten te verkrijgen. De precision geeft de nauwkeurigheid aan, hoeveel van de verkregen documenten zijn daadwerkelijk relevant [Jurafsky & Martin, 2000a]. De formules zijn als volgt: precision = aantal verkregen relevante items / aantal verkregen items recall = aantal verkregen relevante items / aantal relevante items - De F-measure[van Rijsbergen, 1979] is ook erg populair. De parameter combineert de recall en precision en gaat alleen omhoog als zowel de recall als de precision stijgt. We gebruiken als parameter b=1, zodat de recall en precision even zwaar mee tellen. De formule: F = (2 * recall * precision) / (recall + precision) Om de recall, precision en F-measure te berekenen moet je weten wie Impressionisten zijn. We maken gebruik van Victor de Boer’s gold-standard. Dit is een lijst met namen die is opgesteld aan de hand van 12 HTML documenten. Aangezien voor dit domein niet helemaal duidelijk is wie wel een Impressionist is en wie niet, heeft Victor de Boer uit deze 12 documenten gekeken wie er 3 of meer keer Impressionist genoemd word. In hoofdstuk 4.3 staat de gold-standard voor Impressionisme en in tabel 9 staat de gold-standard voor Expressionisme. Iedereen die in de gold-standard staat voor een bepaald domein, keuren we goed. De rest keuren we fout. Het bepalen of een bepaald persoon wel of geen Impressionist is, gebeurt aan de hand van de gold standard. We lopen de resultaten handmatig af, om de namen die in de gold-standard staan te localiseren. In de code worden een aantal verschillende versies van een bepaalde naam in een lijst gezet, waarbij de aanname is dat al deze namen ook daadwerkelijk bij dezelfde persoon horen. Vervolgens kiezen we de versie van de naam die het vaakst in de lijst voorkomt, als representatief voor de hele lijst. Dit is dan ook de naam die we vergelijken met de namen in de gold-standard. Door het grote aantal namen, en de vele documenten, is het voor ons onbegonnen werk om voor elk persoon ook voor alle namen te controleren of deze daadwerkelijk bij die persoon horen. Verder gaan we er vanuit dat wanneer ergens in de documenten twee dezelfde namen voorkomen, deze namen ook bij één persoon horen. Als er twee personen met dezelfde naam voorkomen, dan wordt deze door onze methode als één persoon gezien. Op dit punt wijkt onze methode sterk af van die van Victor de Boer. In zijn methode wordt elke gevonden naam opgezocht in een artiestendatabase3. Als een naam meerdere keren voorkomt in die database, is het niet duidelijk bij welke persoon de gevonden naam hoort, en komt deze naam dan dus ook niet terecht in de resultaten. Als de naam helemaal niet voorkomt, is het blijkbaar ook geen artiest, en komt deze ook niet in de resultaten te staan. 4.1. Threshold: wat is de beste threshold De NiWeDistance functie heeft in bepaalde gevallen een threshold nodig om twee namen te vergelijken. Als de twee namen boven een bepaalde threshold zitten met het vergelijken, dan zullen de namen matchen. De threshold wordt niet meteen geraadpleegd in de NiWeDistance functie. Als bv. de namen X en Y hetzelfde zijn, dan zal de functie meteen 1 retourneren. De functie zal bij een aantal uitzonderingen de threshold niet raadplegen, we gaan er dan vanuit dat er totale zekerheid is dat de namen hetzelfde zijn. In het kort: Als de achternamen overeen komen (Frederic Jean Bazille == Frederic Bazille == Bazille) en de eventueel aanwezige voorletters/voornamen ook, dan zijn de namen gelijk (we gaan er vanuit dat een naam met één woord in dit geval de achternaam is). De volgende namen zijn ook gelijk: (Pierre Auguste Renoir == Auguste Renoir == Pierre Renoir).

3

Dit is de ULAN database: http://www.getty.edu/research/conducting_research/vocabularies/ulan/


16

Na deze controles tussen twee namen X en Y zal de threshold een rol spelen. Het lastige is dat Monet en Manet niet gelijk mogen zijn, terwijl Pissarro en Pissaro wel gelijk moeten zijn. De formule om de woordafstand te berekenen tussen twee namen is als volgt: woordAfstand = 1 - (Levenshtein(naam1,naam2) / LengteLangsteNaam(naam1,naam2))

Als de woordafstand groter of gelijk is aan een bepaalde threshold dan zullen de namen gelijk zijn, anders niet. De lengte van de namen speelt ook een rol, er worden meer verschillen veroorlooft als de namen langer zijn. Om nu een goede threshold te bepalen, hebben we een aantal tests gedaan. Aangezien het Impressionisten domein voor ons het belangrijkste is, richten we de threshold op Impressionistische namen. We hebben in een aantal HTML documenten gekeken welke varianten er zijn van het spellen van de namen van Impressionisten. De volgende varianten komen redelijk vaak voor: ‘Cassat en Cassatt’, ‘Pissarro, Pissaro en Pisarro’ en ‘Degas, De Gas en Dega’. Het zou mooi zijn als die in ieder geval matchen en zodanig dat Monet en Manet zeker niet matchen, omdat het hier om verschillende kunstenaars gaat. We verwachten dat andere verschillende Impressionistische kunstenaars niet met elkaar zullen matchen, aangezien we niet andere namen zijn tegengekomen die sterk op elkaar lijken. Om dat te testen hebben we van ongeveer 110 neo-, post-, american en gewone Impressionisten de achternamen met elkaar vergeleken: Een threshold van 0.5 is te laag. Dan matchen de meest uiteenlopende namen, zoals bv. ‘Ritman en Ochtman’, ‘Angrand en Jongkind’ en ‘Cornoyer en Kroyer’. Als we iets hoger gaan, naar 0.7, dan krijgen we al een beter resultaat. Helaas matchen ‘Bunker en Butler’ en ‘Monet en Manet’, terwijl dat niet moet. Om ervoor te zorgen dat ‘Monet en Manet’ in ieder geval niet matchen, moeten we de threshold hoger dan 0.8 zetten: woordAfstand = 1 - (1 / 5) = 0.8. Dit werkt averechts voor bv. ‘Dega’ en ‘Degas’, omdat die gelijk zullen zijn tot en met threshold 0.8. Maar dat Monet en Manet niet gelijk zijn is voor ons belangrijker, dus houden we de threshold op of hoger dan 0.8. Met de threshold op 0.81, 0.82 of op 0.83 zijn in ieder geval de volgende namen gelijk: ‘Cassat en Cassatt’, ‘Pissaro en Pissarro’, ‘Pissarro en Pisarro’ en ‘De gas en Degas’. Alleen ‘Pisarro en Pissaro’ zijn met die thresholds niet gelijk. Daarvoor is een threshold nodig die kleiner of gelijk is aan 0.714. Met de voornamen erbij worden de namen langer en mogen er meer ‘fouten’ gemaakt worden, de volgende namen zijn dan wel weer gelijk: ‘Camille Pisarro en Camille Pissaro’, ‘Edgar Degas en Edgar Dega’ en ‘Edgar Dega en Edgar De Gas’. Omdat we liever hebben dat twee namen die op elkaar lijken niet gelijk zijn als het twijfelachtig is, omdat dat een sneeuwbal effect kan optreden van foute namen die bij elkaar worden gevonden, nemen we de hoogst mogelijk threshold van 0.83. Op die manier zijn nog wel zoveel mogelijk naam varianten van Impressionisten gelijk aan elkaar en is de kans kleiner dat onze NiWeDistance foute namen bij elkaar zoekt. Beperkingen van deze opzet: ‘Jacob Maris en Matthijs Maris’ zullen bij bepaalde omstandigheden matchen, net als een aantal andere kunstenaars met dezelfde achternaam. 4.2. NE met en zonder leren en NER In dit hoofdstuk proberen we antwoord te krijgen op vragen als: Wat is het verschil tussen deze twee taggers? En heeft het zin om een tagger te leren, om vervolgens betere resultaten te verkrijgen? Allereerst kijken we naar de werking, dan naar een aan aantal tests bij het leren en vervolgens kijken we of er verschil tussen taggers is bij een test op een aantal HTML documenten. 4.2.1. Werking NE en NER Van NER weten we niet precies hoe deze werkt, omdat de Java code closed-source is. We hebben hiervoor geprobeerd contact op te nemen met Wei Li, de auteur, alleen was hij niet erg snel met reageren waardoor we te laat de code kregen. Het voordeel van Java is dat we dat op Windows computers kunnen gebruiken en het niet geïnstalleerd hoeft te worden. Het is één bestand welke je overal kunt neerzetten en vanuit Python kunt aanroepen. NE is een open-source Perl tagger, die alleen op Linux werkt (gebruikt namelijk ook Linux/bash programma’s). Tevens moet deze tagger voor gebruik geïnstalleerd worden. Het handige van deze tagger is dat we deze kunnen trainen, die mogelijkheid heeft NER niet. Met een Python programma


17

hebben we NER aangepast, zodat de output van beide taggers hetzelfde zijn. Op deze manier kunnen we makkelijk van tagger switchen om te kijken welke beter presteert. 4.2.2. Testen NE en NER De eerste test voor deze taggers was om te kijken wat hun recall en precision zijn op 10 html pagina’s. Voor de test hebben we de pagina’s gebruikt die Victor de Boer ook voor zijn onderzoek heeft gebruikt (twee minder, want die websites bestaan niet meer. Deze staan er ook niet tussen): 1. http://www.artcyclopedia.com/history/impressionism.html 3. http://www.worldgallery.co.uk/fimp.html 4. http://www.huntfor.com/arthistory/c19th/impressionism.htm 5. http://www.artchive.com/artchive/impressionism.html 6. http://www.artlex.com/ArtLex/ij/impressionism.html 7. http://www.mcs.csuhayward.edu/~malek/Impression/ 8. http://www.artmovements.co.uk/impressionism.htm 10. http://www.the-artists.org/artshop/impressionism.cfm 11. the-artists.org/MovementView.cfm?id=0E5B804E%2DC426%2D4465%2DB55B4760A9457DC9 12. http://en.wikipedia.org/wiki/Impressionism Achter elke persoonsnaam hebben we een ster (*) gezet, op die manier kunnen we zien of die goed is getagged of niet. Dit hebben we nodig om de precision en recall uit te rekenen, het heeft echter wel nadelen. Nu geef je eigenlijk al aan voor de taggers waar de naam eindigt. Als je bv. ‘Edgar Degas Gustave Caillebotte’ in een document tegenkomt en je markeert de eerste naam (Edgar Degas), dan vertel je dus al aan de tagger dat de eerste naam stopt bij Degas. Op de testpagina’s komt dit gelukkig zelden voor, zodat de score voor de precision en recall weinig beïnvloed wordt. Een ander probleem is dat we alleen de namen markeren bij de achternaam. De tagger hoeft dan alleen maar de achternaam goed te taggen om de naam goed te rekenen: Edward [PER E Simmons ] i.p.v. [PER Edward E Simmons ] Omdat we de namen al op één plek markeren, wat dus al in principe de tagger een handje helpt, hadden we besloten om de namen niet aan de voorkant te markeren. Als de tagger alleen al de achternaam vindt, is dat in ons geval ook goed. Als we de namen én aan de voorkant markeren én aan de achterkant, geef je al helemaal aan voor de tagger waar de naam staat. Dit zal teveel invloed hebben op de recall en precision. De uitslagen zijn te zien in tabel 4. score voor NER average recall: 90.14 average precision: 92.80

score voor NE average recall: 98.62 average precision: 78.45

Tabel 4. Uitslagen NER en NE

De hoogste en laagste recall voor NER zijn respectievelijk: 96.08 en 78.79 De hoogste en laagste precision voor NER zijn respectievelijk: 100.00 en 87.32 De hoogste en laagste recall voor NE zijn respectievelijk: 100.00 (5 keer) en 93.94 De hoogste en laagste precision voor NE zijn respectievelijk: 100.00 en 66.67 NER is helaas niet meer aan te passen, maar deze scoort eigenlijk vrij goed. Met NE valt nog te leren. Dat komt goed uit, want NE heeft blijkbaar een kleinere woordenboek gebruikt tijdens het ontwikkelen van dit programma. NE gaat namelijk vaak de fout in met een boel woorden die wel met een hoofdletter zijn geschreven, maar geen persoonsnamen zijn. Ter illustratie tonen we nu de woorden die verkeerd zijn getagged in de bestanden 1,3 en 4: Impressionism, Mac, French Painter, American Painter, Subject Matter, Articles, Medium, Art Museums Worldwide, Advertise, Classic, Modern, Contemporary, Bookmark, French Impressionism, Biography, Samples, READ, Museum Quality, Satisfaction Guarantee, Unlimited Selection, Free Shipping Anywhere, Please, Sunrise, Many Impressionists, Main Representatives, Photography, Exhibition, Graveurs,


18

Paintings, High Museum, Art Museum, Art History, Main Page, Lily, Lily Rose, Water Lilies, Beach, Before Her Appearance, Orchard De dikgedrukte woorden zouden eventueel nog namen kunnen zijn, maar in ons domein ‘Impressionisme’ zijn dit nou niet veel voorkomende persoonsnamen, maar eerder titels van schilderijen. Die woorden, met name Art, komen vaak voor en zorgen ervoor dat de precision naar beneden gaat. Om te kijken of dit beter gaat na het leren, hebben we elk document van 1 t/m 12 (dus 10 in totaal) verbeterd en één voor één aan de leer-module van NE gegeven. Bij elk document hebben we gekeken wat de totale vooruitgang is. Recall 120 1

100 Percentage in %

3 4

80

5 60

6 7

40

8 10

20

11 12

0 0

1

3

4

5

6

7

8

10

11

12

gem

Leer be stand

Figuur 1. Recall tijdens het leren van NE

Precision 120 1

100 Percentage in %

3 4

80

5 60

6 7

40

8 10

20

11 12

0 0

1

3

4

5

6

7

8

10

11

12

gem

Leer be stand

Figuur 2. Precision tijdens het leren van NE

Zoals te zien is in de figuren 1 en 2, gaat de Recall een beetje achteruit (begin: 98,62%, einde: 91,22%) en de Precision aardig vooruit (begin: 78,45%, eind: 98, 37%). Na het leren zijn Art Nouveau (Art is in principe een naam) en Lily Rose (zou ook een naam kunnen zijn) de enige foute namen. Na het leren wordt NE ietsje zorgvuldiger met het taggen van de namen, want hij slaat er nu veel over. Vooral namen aan het begin van de zin worden nu overgeslagen. Dit komt omdat NE in het begin veel fouten maakten door het eerste woord van de zin als persoon aan te zien, terwijl dit vaak niet het geval was. Na het aanpassen en leren denkt NE nu dat het eerst woord van de zin geen persoon is.


19

Voor NER geldt verder dat deze op de testset wel hoog scoort, maar in de praktijk komt het vaak voor dat NER met vrij aparte namen komt: NER gaat vaak de fout in bij namen waar een streepje (‘-‘) tussen staat, bijvoorbeeld [PER Georges ] - [PER Pierre Seurat ]. Het tweede gedeelte wordt dan wel goed gerekend, terwijl Georges niet goed wordt gerekend. Een ander nadeel van NER is dat namen met een punt erin, bv. [PER Roeland.C. Weve] niet als één naam worden gezien, maar gesplitst worden: [PER Roeland C.] en [PER Weve]. NE pakt deze namen wel goed mee. Om dit op te lossen hebben we de punten verwijderd die volgde na één hoofdletter. Daarna ging het wel goed met het taggen van dit soort namen. Later bij het testen kwam NER met namen van wel 20 namen lang. Deze namen stonden in een dropdown lijstjes en werden bij het verwijderen van de HTML achterelkaar gezet. Niet alleen namen in dropdown lijstjes, maar ook naam opsommingen in tabellen kwamen achter elkaar te staan. Om dit op te lossen hebben we de HTML tags: , en
vervangen door komma’s. Dit heeft wel weer geleid tot namen met komma’s en punten erin, zoals [PER Roeland , . . , . . . ]. Dit is opgelost door deze door een reguliere expressie te verwijderen. NER gaf op een gegeven ogenblik ook namen met alleen maar punten en komma’s erin, dus zonder letters. Deze konden we er wel automatisch uit halen, door te zeggen dan een getagde naam alleen geldig is als er minimaal één letter in zit. NE tagged namen met streepjes erin prima, bijvoorbeeld [PER Georges-Pierre Seurat ]. Ook namen met punten erin vormen voor NE geen probleem. Dat is erg handig, aangezien dit nog wel eens op internet voorkomt. In ons programma zal NE deze namen niet meer tegen komen, aangezien de punten worden verwijderd. 4.2.3. De test met de afstandsmethode op 10 HTML documenten Om te kijken wat de invloed van het leren is op NE, hebben we voor en na het leren het gehele programma gedraaid, op zoek naar Impressionisten. Het testen gebeurt weer op de 10 HTML documenten. De threshold is ingesteld op 0.83, de documenten zonder markeringen (zonder (*)) worden gebruikt, er worden geen bootstrap iteraties gedaan en de seed-list is ingesteld op ‘Monet’. De gold-standard bestaat uit 18 namen, dus het zou mooi zijn als die er in één keer allemaal uit komen. Dit zal niet het geval zijn, we controleren de eerste 45 namen die uit de afstandsmethode komen en tellen de juist gevonden namen. Het resultaat: NE zonder leren heeft na 28 namen de resterende 17 Impressionisten gevonden. NE met leren heeft na 45 namen maar 16 Impressionisten gevonden (Camille Corot niet gevonden) Dit resultaat is goed terug te koppelen op het feit dat NE met leren een lagere recall heeft. NE slaat in dat geval een boel namen over en dus komen er een aantal Impressionisten lager in de lijst. 4.2.4. De test met de afstandsmethode op 200 HTML documenten via Google Dit is een andere test om te kijken of er verschil is tussen NE met leren, NE zonder leren en NER. We gebruiken de standaard NE, die ‘schoon’ van internet is gehaald en waarmee nog nooit mee is getagged en we gebruiken de NE waarop we de 10 HTML documenten op geleerd hebben. NER gebruiken we ook, hierop kunnen we sowieso niet leren. De rest van de testopstelling is als volgt: De Google zoekopdracht (keywords): ‘impressionism OR impressionist -neo -post -American’ De begin seed-list is: ‘Monet’ en we voeren geen bootstrap iteratie uit. We kijken naar de eerste 50 resultaten en zullen kijken welke van de taggers als eerste alle Impressionisten uit de gold-standard heeft gevonden en hoe snel. Het resultaat is als volgt: ‘Childe Hassam’ en ‘F.C.Frieseke’ worden door geen enkele tagger gevonden. Dus dan blijven er nog maar 15 Impressionisten over. Deze worden wel gevonden door NE zonder leren. NE met leren en NER vinden er beide maar 13. Allebei missen ze dezelfde Impressionist (Caillebotte en Corot). Nu lijkt het alsof NE zonder leren goed werkt. Maar omdat het zoveel fouten maakt bij het taggen van namen (19 in totaal), kun je bizarre namen krijgen in de eindlijst. NE met leren tagged maar 10 foute namen en NER tagged er 12 verkeerd, dus dat ligt ook aardig bij elkaar.


20

In tabel 5 staan de F-measure waardes voor de taggers. type tagger NE met leren NE zonder leren NER

score 0,7586 0,7742 0,7586

Tabel 5. F-measure bij NE met en zonder leren en NER op 200 HTML documenten

Zoals te zien, heeft NE zonder leren de hoogste F-measure waarde en zijn de waardes voor NE met leren en NER precies hetzelfde. 4.2.5. Conclusie NE zonder leren tagged teveel verkeerde namen, waardoor de resultaten vervuild worden. Het verschil in de F-measure waarde is ook niet bijzonder groot, maar door de hoeveelheid verkeerde tags is dit geen optie. NE met leren hebben we in dit geval alleen getest voor het domein van Impressionisten, dus we verwachten dat hij dan weer wat minder presteert als hij gebruikt wordt voor andere domeinen. NER presteert zonder enig extra leren vrij aardig. Het verschil tussen NER en NE met leren voor het Impressionistische domein is erg klein, de Fmeasure waarde is zelfs precies hetzelfde, dus in dit geval maakt het niet zoveel uit welke wij verder gebruiken. In ons geval is NER makkelijker te gebruiken (vanwege Windows), dus zullen wij het meeste verder testen met alleen NER. Mocht er op een domein getest worden waar veel streepjes in de namen zitten, dan is het aan te raden om NE te leren op dat domein en dan te gebruiken. De resultaten zullen dan preciezer worden.


21

4.3. Vergelijking met Relation Instantiation Om te controleren hoe goed, of hoe slecht ons programma werkt, hebben we dezelfde tests uitgevoerd zoals ze in het artikel van Victor de Boer staan beschreven. De testdocumenten zijn 199 resultaten van Google voor Impressionisme. Deze documenten hebben we gekregen van Victor de Boer, zodat we ook op precies dezelfde documenten testen. Deze documenten zijn genummerd van page1.html t/m page199.html. Page111.html t/m page120.html ontbraken in de dataset, en dit hebben we opgevangen door 10 lege bestanden tussen te voegen. De gold-standard van Victor de Boer bevat 18 namen, en is opgesteld aan de hand van 10 documenten. Elke naam die in 3 of meer van die 10 documenten als Impressionist wordt aangegeven, wordt beschouwd als een Impressionist. De 18 namen zijn: Camille Pissarro, Edgar Degas, Berthe Morisot, Claude Monet, Edouard Manet, Pierre-Auguste Renoir, Alfred Sisley, Mary Cassatt, Frederic Bazille, Paul Cézanne, Childe Hassam, Eugene Boudin, Gustave Caillebotte, Armand Guillaumin, Paul Gauguin, Camille Corot, F.C. Frieseke en Georges Seurat. Voor de eerste test kijken we naar de resultaten die we krijgen met het draaien van het algoritme, met de volgende drie seeds: Camille Pissarro, Edgar Degas en Berthe Morisot. Vervolgens kijken we welke namen uit de resultaten voorkomen in de gold standard, en op welk moment we alle namen uit de gold standard hebben gevonden. De laatste naam die wordt gevonden is ‘Childe Hassam’. Deze naam staat echter pas op positie 104 in de resultaten. Bij het zoeken naar de oorzaak hiervan hebben we gevonden dat de naam ‘Childe Hassam’ in veel gevallen niet door NER wordt getagged, terwijl de naam wel in de documenten staat. Dit gaat uiteraard ten koste van de score van die naam, en ook de precision en F-measure lijden hieronder.

Recall, Precision, F-measure Recall

Precision

F-measure

1,2 1

Value

0,8 0,6 0,4 0,2

Score

Figuur 3. recall, precision en F-measure voor Impressionisten, met documentscore


22

341,8759

318,2899

285,9732

261,4345

241,4532

223,8060

197,4326

177,2556

153,8542

139,1349

120,6621

100,3032

72,4548

59,8654

54,9745

46,2512

35,0579

18,1880

7,7867

2,2698

0,7412

0

Bij deze test was de maximale F-measure 0.72, en dat komt precies overeen met de maximale score bij Victor. Het verloop van de recall, precision en F-measure zijn te zien in figuur 3 en gedeelte van de resultaten van deze test zijn te zien in tabel 6. positie naam

score

correct

1Claude Monet

0,7412

1

2Auguste Renoir

0,8011

1

3Alfred Sisley

1,0757

1

4Edouard Manet

1,2673

1

5Paul Cezanne

1,5957

1

6Armand Guillaumin

2,2698

1

7Vincent van Gogh

3,8742

0

8Gustave Caillebotte

4,6190

1

9Georges Seurat

6,4046

1

10Paul Gauguin

7,2783

1

11Pierre

7,7867

0

12Henri Matisse

9,0511

0

13Mary Cassatt

9,7557

1

14Paul Signac

14,6564

0

15Leonard Ochtman

15,1567

0

…

…

……

Tabel 6. Resultaten voor Impressionisten, met documentscore

Op positie 11 staat ‘Pierre’. Deze fout valt voor een groot deel te wijten aan de NER-tagger. Deze tagged een naam als ‘Pierre-Auguste Renoir’ als twee namen. En omdat deze naam dichtbij ‘Auguste Renoir’ staat, is het ook logisch dat hij een goede score krijgt. ‘Vincent van Gogh’ scoort ook hoog, maar staat niet in de gold-standard als Impressionist. De overige namen die in de lijst staan zijn allemaal kunstenaars, maar vallen onder Neo-, Post- of American-Impressionisten. Om te kijken of het meenemen van de documentscore van invloed is op de resultaten, hebben we dezelfde test gedaan, maar dan zonder de documentscore. In dit geval waren er inderdaad andere resultaten, deze zijn te zien in tabel 7. Het verloop van de recall, precision en F-measure is te zien in figuur 4.


23

Recall, Precision, F-measure Recall

Precision

F-measure

1,2 1

Value

0,8 0,6 0,4 0,2

1, 42 6, 20 17 13 66 ,9 41 474 ,0 72 536 , 12 082 0, 9 19 651 1, 0 23 786 0, 3 7 27 05 8, 4 4 30 45 6, 2 36 858 4, 0 9 38 26 3, 6 5 46 72 0, 5 51 287 9, 0 8 56 20 4, 6 6 65 18 2, 7 69 073 0, 3 77 430 6, 5 73 43

0

Score

Figuur 4. recall, precision en F-measure voor Impressionisten, zonder documentscore positie 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 …

naam Claude Monet Auguste Renoir Paul Cezanne Edouard Manet Alfred Sisley Pierre Georges Seurat Armand Guillaumin Mary Cassatt Vincent van Gogh Paul Gauguin Gustave Caillebotte Paul Signac Henri Matisse Frederic Bazille …

score 1,4220 2,0786 3,3983 4,0647 6,1766 9,4242 13,3091 13,6091 13,9474 14,0873 21,9422 24,2973 41,0536 50,2751 55,1505 …

correct 1 1 1 1 1 0 1 1 1 0 1 1 0 0 1 …

Tabel 7. Resultaten voor Impressionisten, zonder documentscore

De maximale F-measure is in dit geval 0.740741, en de laatste naam (wederom Camille Corot) werd op positie 72 teruggevonden. Het lijkt er bij dit domein dus op dat de manier van scoren zonder rekening te houden met de documentscore beter werkt. Waarschijnlijk heeft de documentscore een te grote invloed op de score, zodat het kiezen van een hogere logaritmische schaal (die is bij deze test 2) bij het berekenen van de documentscore in dit geval een positieve invloed kan hebben. Wat ook opvallend is, Vincent van Gogh is gedaald van de zevende naar de tiende positie. Hiermee is de invloed van de documentscore duidelijk te zien, doordat Vincent van Gogh in documenten staat die goed score, scoort de naam ‘Vincent van Gogh’ ook goed. Het lijkt erop dat onze methode qua F-measure dezelfde resultaten haalt, vergeleken met de methode van Victor. Bij het weglaten van de documentscore, is onze score voor de F-measure iets hoger (0.02),


24

maar de methode van Victor vindt eerder alle namen die in de gold-standard staan. De reden daarvoor ligt waarschijnlijk in het feit dat hij de gevonden namen vergelijkt met namen uit een kunstenaarsdatabase, zodat er in de eindlijst ook alleen kunstenaars terechtkomen. Bij ons worden de resultaten nog vervuild door niet-kunstenaars, zoals critici en auteurs van de artikelen. Maar met dit punt is ook meteen duidelijk dat onze methode wat dat betreft een stuk flexibeler is. Wij zijn namelijk niet afhankelijk van een database met daarin alle namen, zodat we zonder enige moeite op andere domeinen kunnen testen. Hierbij moet wel gemeld worden dat de methode van Victor erop is gericht om voor een groep bekende instanties te kijken of een bepaalde relatie wel of niet geldt, terwijl onze methode zich richt op het vinden van nog onbekende namen.


25

4.4. Is het zinvol om te bootstrappen Een extra mogelijkheid van de code is de optie tot bootstrappen. Hiermee begin je met een seed-list met bijvoorbeeld drie namen: seeds = ['Monet', 'Manet', 'Pissarro']

Vervolgens wordt er gezocht naar de naam met de beste score, bijvoorbeeld Cezanne, en deze naam wordt vervolgens toegevoegd aan de seed-list: seeds = ['Monet', 'Manet', 'Pissarro', 'Cezanne']

Vervolgens wordt hiermee naar de beste naam gezocht, en dit kan elke keer opnieuw herhaald worden. Een voordeel is dat documenten die met de eerste seed-list geen seeds bevatten, met de nieuwe toevoeging van de seed-list opeens wel een seed kunnen hebben. Zo kunnen namen die eerst niet scoorden, opeens wel een score krijgen. Het gevaar hierbij is natuurlijk dat er onverhoopt een naam in de seedlist terecht komt, die niet in het domein hoort. Het komt af en toe voor dat in de resultaten een criticus (Louis Leroy) wordt aangezien voor Impressionist. Het gevolg is dan dat deze in de seed-list terechtkomt, en alle namen die in de buurt van die naam staan zullen nu hoger gaan scoren. Stel dat er in een document een opsomming is van een aantal kunstcritici, deze kunnen dan in het vervolg ook allemaal een goede score halen. Het effect hiervan wordt deels opgevangen door de score ook af te laten hangen van het aantal documenten waarin een naam voorkomt, dus wanneer er een groot aantal documenten worden gebruikt, zal een naam die in slechts één document voorkomt, niet snel bovenaan komen te staan. Een ander gevaar is het meetellen van de documentscore. Hierdoor is de code geneigd om eerder namen te pakken uit een document met een goede score. En door deze naam toe te voegen aan de seed-list, zal de documentscore weer omhoog gaan. Dit kan een voordeel zijn, omdat in een bestand met alle namen uit de seed-list, zeer waarschijnlijk ook namen staan die bij hetzelfde domein horen. Dit betekent echter niet dat alle namen in dat document ook binnen het domein van de seed-list vallen. Waarschijnlijk zal er onderaan het document ergens de naam van de auteur van het artikel vermeld staan, ver verwijderd van de namen uit de seed-list. Maar door de extreem hoge documentscore krijgt deze naam ook een enorme bonus. Dit probleem zal ook opgevangen kunnen worden door maar een groot aantal documenten te nemen, en we houden er bij het berekenen van de documentscore ook rekening mee dat extreem hoge documentscores niet al te zwaar meetellen. Ook zal dit probleem bij bootstrapping minder snel voorkomen wanneer de documentscore helemaal niet wordt meegenomen bij het berekenen van de score. Om te testen wat de consequenties van bootstrapping zijn, zullen we wederom de 199 bestanden gebruiken over Impressionisme, met als seed-list: ‘Edgar Degas', 'Camille Pissarro' en 'Berthe Morisot'. Na elke iteratie wordt de naam met de beste score toegevoegd aan de seed-list, waarbij we zullen controleren of die naam inderdaad een impressionist is. Door hiervoor ook de F-measure te berekenen, kunnen we zien of de code met bootstrappen beter presteert dan de code zonder bootstrappen. Na 20 bootstrap-iteraties zijn 11 van de 15 namen gevonden. Een blik op de score na 20 iteraties maakt duidelijk dat de laatste naam (Camille Corot) uit de gold-standard pas op positie 93 staat, en hieruit is op te maken dat die naam zeer waarschijnlijk niet eerder dan na zo’n 90 extra iteraties zal worden gevonden. Vanwege de duur voor het draaien van één enkele iteratie, hebben we besloten om de resultaten na die 20 iteraties ook als eindstand te beschouwen. Afgaande op die stand is het hoogst onwaarschijnlijk dat de F-measure alsnog omhoog zal gaan door die extra iteraties. De resultaten na deze 20 iteraties zijn te zien in tabel 8 en de grafiek met de scores voor het bootstrappen is te zien in figuur 5.


26

positie 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

naam Claude Monet Auguste Renoir Alfred Sisley Edouard Manet Cezanne Van Gogh Paul Gauguin Pierre Georges Seurat Henri Matisse Henri Paul Signac Mary Cassatt Gustave Caillebotte Louis Leroy Picasso Armand Guillaumin Jean Frederic Bazille Paul

correct 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0

Tabel 8. Gevonden resultaat met ‘1’ voor correct en ‘0’ voor niet correct

Bootstrappen 1,2 1

Score

0,8

Recall

0,6

Precision F-measure

0,4 0,2

106

99

92

85

78

71

64

57

50

43

36

29

22

15

8

1

0

Trials Figuur 5. Recall, Precision en F-measure tijdens het bootstrappen

Hier is goed te zien dat doordat de laatste paar namen pas ver in de resultaten zijn terug te vinden, de precision en recall steeds slechter wordt. Nu is het de vraag of bootstrappen wel of niet zinvol is. De eerste vijf iteraties gaat het goed, en ook na negen iteraties zijn er nog maar twee fouten gemaakt. Het blijft echter wel een feit dat elke foute naam in de seed-list voor nog meer foute namen kan zorgen. Daarom kijken we nog naar de score die wordt behaald met de seed-list die na vijf iteraties is gevonden, dat is het laatste punt waarin er nog geen fouten in de seed-list staan. In dat geval ziet de scoregrafiek eruit als in figuur 6.


27

Bootstrappen na 5 iteraties 1,2 1 Score

0,8

Recall

0,6

Precision F-measure

0,4 0,2 92

85

78

71

64

57

50

43

36

29

22

15

8

1

0 Trials / positie Figuur 6. Recall, Precision en F-measure bij bootstrappen na 5 iteraties

De hoogste F-measure die hier wordt behaald, is 0.740741, en dat is precies dezelfde score als eerder is gehaald bij het kijken naar de score na 1 iteratie, zonder de documentscore te gebruiken. Dus de vraag of bootstrappen zin heeft, wordt hier ook niet duidelijk beantwoord. Het enige echte verschil is dat bij deze test de laatste naam pas op positie 93 is terug te vinden, terwijl die bij de test met 1 iteratie op positie 72 staat. Voor dit domein kunnen we dus concluderen dat het bootstrappen geen duidelijke positieve, en ook geen duidelijke negatieve invloed heeft op de score.


28

5. Verschillende domeinen Om te kijken of de afstandsmeting methode gebruikt kan worden voor andere domeinen, hebben we een aantal tests uitgevoerd op verschillende domeinen.. 5.1. Expressionisme Voor dit domein hebben we weer gebruik gemaakt van de gold-standard, seed-list en de documenten die Victor de Boer ook had gebruikt voor zijn onderzoek. Op die manier kunnen we weer vergelijken hoeveel de twee methodes verschillen. De gold-standard voor Expressionisme staat in tabel 9. Emil Nolde Edvard Munch Egon Schiele Ernst Ludwig Kirchner Oskar Kokoschka Chaim Soutine Franz Marc Max Beckmann Wassily Kandinsky Paula Modersohn-Becker

George Grosz Otto Dix August Macke Max Pechstein Alexei Jawlensky James Ensor Karl Schmidt-Rottluf Alfred Kubin Amedeo Modigliani Georges Rouault

Erich Heckei Lyonel Feininger Paul Klee Ernst Barlach Francis Bacon Gabriele Munter Heinrich Campendonk Jules Pascin Gustav Klimt Kathe Kollwitz

Tabel 9. Gold-standard voor Expressionisme

Er zijn 189 documenten aanwezig voor dit onderzoek en de seed-list is: ‘Paula Modersohn-Becker’, ‘Georges Rouault’, ‘Kathe Kollwitz’. Dus aan de hand van deze drie namen, proberen we de resterende 27 namen uit de gold-standard te vinden. Na het draaien van het algoritme krijgen we voor de maximum F-waarde 0,70. Dat is precies dezelfde waarde die Victor de Boer ook had gevonden. Wat dat betreft werken ze beiden even goed. Wat opvalt, is dat met deze seed-list ‘Gustav Klimt’ niet te vinden valt. Deze persoon komt namelijk precies in documenten voor waar de seeds niet in voorkomen. De andere persoon die niet wordt gevonden is ‘Erich Heckei’. Deze persoon komt niet in de 189 testdocumenten voor. Pas na 75 resultaten zijn de andere personen uit de gold-standard gevonden, de laatste persoon is ‘Francis Bacon’. 5.2. Voetballers in het team van het WK onder 20 in 2005 Dit is een vrij recent onderwerp. Het is een duidelijk domein, want een persoon behoort wel of niet tot dit elftal en er zijn geen twijfelaars. De gold-standard voor dit domein staat in tabel 10. Kenneth Vermeer Dwight Tiendalli Ron Vlaar Frank van der Struijk Jeroen Drost Hedwiges Maduro Quincy Owusu Abeyie Rick Kruys

Collins John Ibrahim Afellay Ryan Babel Gianni Zuiverloon Mark Otten Haris Medunjanin Urby Emanuelson Theo Brack

Kemy Agustien Tim Vincken Prince Rajcomar Arjan Wisse Job Bulters

Bondscoach Foppe de Haan

Tabel 10. Gold-standard voor voetballers in het team WK onder 20 in 2005


Reservelijst Wesley Verhoek Eljero Elia Wouter Artz Tom Zoontjes Robbert Schilder

29

Het liefst willen we niet de bondscoach ‘Foppe de Haan’ terug krijgen, omdat dit geen voetbal speler is. Helaas zal dit volgens onze verwachtingen niet lukken, omdat deze persoon vast en zeker bij de opstelling genoemd zal worden. Net als bij de andere zoeken nemen we ook hier voor de seed-list willekeurig drie namen uit de goldstandard, namelijk: ‘Quincy Owusu Abeyie’, ‘Arjan Wisse’ en ‘Kenneth Vermeer’. We laten ons programma automatisch 40 documenten downloaden met de volgende zoekopdracht voor Google: ‘"wk 20" OR "WK onder 20" voetbal spelers’. Zelfs voor dit Nederlandse domein, doet het programma het vrij goed. De eerste 20 resultaten zijn bijna perfect te noemen, zoals te zien is in tabel 11. nr. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

score 0,5731 0,7289 0,7507 0,8011 1,1205 1,4184 1,6188 1,7465 2,4276 3,0792 3,6542 3,6776 6,9967 8,0987 8,203 12,4787 22,4109 23,9777 25,0733 25,2078

naam voetballer Rick Kruys Dwight Tiendalli Gianni Zuiverloon Frank van der Struijk Haris Medunjanin Rajcomar Wesley Verhoek Maduro Wouter Artz Ron Vlaar Tim Vincken Ryan Babel Tom Zoontjes Foppe de Haan Robbert Schilder Ibrahim Afellay Jeroen Drost Nee Theo Brack John

correct 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1

opmerking

RES RES

RES Coach RES

Tabel 11. Resultaten voor het voetballers domein. RES = reservespeler

Alleen ‘Mark Otten’, ‘Urby Emanuelson’, ‘Kemy Agustien’ en ‘Eljero Elia’ missen nog in dit rijtje. ‘Mark Otten’ wordt pas op nummer 31 gevonden en de rest van de namen worden niet of heel weinig getagged door NER. Na deze 20 resultaten krijgen we resultaten als: ‘Alleen’, ‘aldus De Haan’, ‘Ook’, ’Ik’, ‘Kun’, ‘Maar’,’Het’, etc. Dit is logisch, want de NER tagger is getraind op Engelse documenten en NER zal deze woorden met hoofdletter niet kennen en dan denkt de tagger dat het persoonsnamen zijn. De F-measure waarde is 0.84. In vergelijk met de andere domeinen is dit extreem hoog. 5.4. Conclusie Het is dus mogelijk om de afstandsmethode voor andere domeinen te gebruiken. Dit werkt alleen goed op Engelse documenten en, bij uitzondering, ook op andere talen. Helemaal als je domeinen neemt waarbij geen onzekerheid is of personen er wel of niet bij horen, zal de methode goed werken.


30

6. Conclusie en toekomstig onderzoek De methode die wij hebben uitgewerkt, lijkt na de verschillende tests goed te werken. Voor het domein van Impressionisten is duidelijk te zien dat de namen die het beste scoren, voor het grote deel ook echt Impressionisten zijn. Ook voor de andere domeinen zijn de resultaten bemoedigend. De score op recall, precision en F-measure kunnen als goed worden beschouwd, vooral als we in beschouwing nemen dat het Impressionisme een ruim begrip is, en zelfs in de documenten zelf is niet altijd duidelijk welke personen nou wel of geen Impressionisten zijn. De namen die we bij het berekenen van de score als fouten hebben gerekend, zijn meestal Neo-, Post- of American Impressionisten, of kunstcritici. De fouten die worden gemaakt zijn goed te verklaren. Wij denken dat op dit moment nog wat winst valt te behalen in het perfectioneren van de Named Entity Tagger. Een aantal namen wordt regelmatig niet getagged, en andere namen worden als twee namen getagged. Ook hebben we zelf nog niet kunnen testen wat het effect is van het toepassen van andere wegingen bij het berekenen van de score. Bij het testen is gebleken dat de documentscore een te grote invloed heeft op de score van de namen in de betreffende documenten. Verder zou de invloed van het aantal keren dat een bepaalde naam voorkomt in een domein zwaarder, of minder zwaar mee kunnen wegen. Momenteel wordt de afstand lineair berekend, en wellicht dat een kwadratische afstandsmeting voor betere resultaten kan zorgen. Door de kwadratische afstand te nemen zullen namen die dichterbij staan een soort bonus krijgen. Verder is de code erg afhankelijk van de resultaten die worden verkregen met de zoekmachine. Het is heel erg belangrijk om het domein goed te specificeren, en het domein moet vooral niet op meerdere manier interpreteerbaar zijn. Het toevoegen van een domain classifier zou ervoor kunnen zorgen dat uiteindelijk alleen die documenten worden gebruikt die daadwerkelijk relevant zijn.


31

7. Literatuurlijst [Annie, 2005]: ANNIE “A Nearly-New IE system”. A robust cross-domain IE system (2005) http://gate.ac.uk/ie/annie.html [Artequakt]: David Miljard. ArteQuakt http://www.artequakt.ecs.soton.ac.uk/ [BrigtPlanet, 2004] Michael K. Bergman (2004). Tutorial Guide to Effective Searching of the Internet. http://www.brightplanet.com/deepcontent/tutorials/search/index.asp [de Boer, 2005] Victor de Boer (2005). Relation Instantiation from heterogeneous source on Web [Google, 2002]: Google Sets (2002) http://labs.google.com/sets [Jurafsky & Martin, 2000a] D. Jurafsky & J.H. Marting (2000) In Speech and Language Processing, pagina’s 651-654 [Jurafsky & Martin, 2000b] D. Jurafsky & J.H. Marting (2000). In Speech and Language Processing, pagina 652 [Kim, et al. 2003]: Sanghee Kim, Harith Alani, Wendy Hall, Paul H. Lewis and David E. Millard, Nigel R. Shadbolt and Mark J. Weal (2003). Artequakt: Generating Tailored Biographies with Automatically Annotated Fragments from the Web http://data.archives.ecs.soton.ac.uk/data/archive/equator/papers/Artequakt.pdf [Questsin, 2005]: Questsing (2005). Reverse Engineering Google Sets. http://questsin.blogspot.com/2005/05/reverse-engineering-google-sets.html [de Rijke, 2004] M. de Rijke (2005). Taalverwerking en informatie ontsluiting. College week 14 / 2003-2004 http://remote.science.uva.nl/~mdr/Teaching/TVIO/0304/clean-tvio0304-week14-8up.pdf [van Rijsbergen, 1979 ]: C.J. van Rijsbergen (1979). Information Retrieval. Londen, Butterworths 1979. 2nd Edition. http://www.dcs.gla.ac.uk/Keith/Preface.html [Wei Li, et al 2003] Andrew McCallum and Wei Li (2003). Seventh Conference on Natural Language Learning (CoNLL). Early Results for Named Entity Recognition with Conditional Random Fields, Feature Induction and Web-Enhanced Lexicons http://ciir.cs.umass.edu/~weili/papers/conll.pdf


32

8. Gebruikte figuren Figuur 1. Recall tijdens het leren van NE.............................................................................................. 19 Figuur 2. Precision tijdens het leren van NE......................................................................................... 19 Figuur 3. recall, precision en F-measure voor Impressionisten, met documentscore............................ 22 Figuur 4. recall, precision en F-measure voor Impressionisten, zonder documentscore....................... 24 Figuur 5. Recall, Precision en F-measure tijdens het bootstrappen....................................................... 27 Figuur 6. Recall, Precision en F-measure bij bootstrappen na 5 iteraties.............................................. 28

9. Gebruikte tabellen Tabel 1. De verschillende Named Entity Taggers................................................................................. 10 Tabel 2. Naam en afstand ...................................................................................................................... 12 Tabel 3. Input en output van module 6.................................................................................................. 13 Tabel 4. Uitslagen NER en NE.............................................................................................................. 18 Tabel 5. F-measure bij NE met en zonder leren en NER op 200 HTML documenten ......................... 21 Tabel 6. Resultaten voor Impressionisten, met documentscore ............................................................ 23 Tabel 7. Resultaten voor Impressionisten, zonder documentscore ....................................................... 24 Tabel 8. Gevonden resultaat met ‘1’ voor correct en ‘0’ voor niet correct ........................................... 27 Tabel 9. Gold-standard voor Expressionisme ....................................................................................... 29 Tabel 10. Gold-standard voor voetballers in het team WK onder 20 in 2005....................................... 29 Tabel 11. Resultaten voor het voetballers domein. RES = reservespeler.............................................. 30


33

10. Bijlage: werkverdeling Hoofdstuk 1 (voorwoord), 2 (IE: afstandsmeting), 5 (verschillende domeinen), 6 (conclusie en toekomstig onderzoek), 7, 8 en 9 zijn samen geschreven. De andere hoofdstukken zijn als volgt verdeeld: Hoofdstuk 3: Methode 3.1. Module 1: Google zoeken - roeland 3.1.1. Problemen/nadelen Google - michiel 3.2. Module 2: HTML parsen - roeland 3.3. Module 3: Named Entity Taggers: NE en NER - roeland 3.4. Module 4: NiWeDistance - michiel 3.4.1. Problemen NiWeDistance - roeland 3.5. Module 5: Afstandsmeting - michiel 3.6. Module 6: Samenvoegen van namen en lijsten - roeland 3.7. Berekening van de score: - michiel Hoofdstuk 4: Uitslagen experimenten 4.1. Threshold: wat is de beste threshold - roeland 4.2. NE met en zonder leren en NER - roeland 4.3. Vergelijking met Victor de Boer - michiel 4.4. Is het zinvol om te bootstrappen - michiel De persoon die over iets heeft geschreven, heeft dit meestal ook zelf uitgevoerd en de eventuele code geschreven. De problemen en nadelen bij sommige methodes zijn we samen tegengekomen, echter heeft maar één persoon dit verwoord.


34

Ontdekken van Impressionisten m.b.v. afstanden tot bekende Impressionisten

Recommend Documents