2.0 Drops

Floating in the 2.0 world ~ connected by the web


Een reactie plaatsen

Information retrieval: onderzoek zoekfuncties Office 365 en Google Docs

Tijdens mijn laatste vak aan de UvA heb ik samen met Peter Becker en Jacqueline Schaap gewerkt aan een verplicht onderdeel: een onderzoek gericht op zoeksoftware. We hebben gekozen om dit onderzoek uit te voeren naar twee bestaande zoeksystemen: de zoekfunctie van Office 365 van Microsoft en die van Google Docs.

De achterliggende gedachte bij deze keuze is het feit dat veel organisaties er voor kiezen om één van beide omgevingen te gebruiken ten behoeve van het eigen documentbeheer (een deel van de enterprise content). In beide omgevingen bestaan mogelijkheden om documenten te ordenen via een mappenstructuur, maar beide leveranciers claimen ook dat de kwaliteit van de zoekmachine een dergelijke werkwijze overbodig maakt. Wij waren dan ook geïnteresseerd in de scores van de beide zoekmachines ten aanzien van recall, precision en relevance ranking.

Als leidraad voor dit onderzoek hebben we gebruik gemaakt van een handzaam artikel van Tague-Sutcliffe uit 1992 waarin 10 stappen worden beschreven voor het opzetten van een information retrieval test. We hebben in beide systemen gewerkt met een testcollectie van 300 identieke documenten en 30 queries (20 known item queries en 10 subject search queries). Volgende metingen zijn uitgevoerd:

  • Bij een known-item query is er sprake van één relevant document als goede treffer. De criteria ten aanzien van het zoekresultaat waren dan ook: staat het document bij de eerste 10 resultaten en zo ja, op welke plaats?
    • Daartoe is de Mean Reciprocal Rank (MRR) gehanteerd. (Croft, 2010, p.323): als het document op rank 1 stond kreeg het de waarde 1/1= 1. Stond het op 2, dan de waarde ½=0,5 enzovoort. Per zoekmachine zijn 20 queries uitgevoerd, waarna de gemiddelde score is bepaald.
  • Bij de subject queries was vooraf bepaald welke documenten als relevante treffers (altijd meer dan 1) moesten worden teruggegeven door het systeem. Om te bepalen in hoeverre dat het geval was (recall) en op welke plaats in de ranking (precision) zijn de volgende meetmethoden gehanteerd:
    • Mean Average Precision (MAP) (Croft, 2010, p.317): kort gezegd geeft deze methode antwoord op de vraag: hoeveel relevants vind je in de top 10 en hoe hoog staan ze dan? De nadruk ligt hierbij op de precisie.
    • Zelf geformuleerde Raw score, geïnspireerd op Stenmark (2004): hoeveel van de relevante documenten vind je in de top 10? Hierbij ligt de nadruk op de recall.
    • 1/r weight en 1/SQRT(r) weight (Stenmark, 2004). Ook hierbij ligt de nadruk op de recall: relevante documenten die buiten de top 10 vallen, beïnvloeden de score negatief.
    • Om het onderscheid tussen de twee omgevingen te verfijnen, hebben we de Document Cut-off Value (DCV) toegepast. Ook deze methode is afkomstig uit Stenmark (2004) en wordt uitgebreider aangehaald door Hull (1993). De nadruk ligt op de precisie. We hebben metingen gedaan bij  6, 7,  8, 9 en 10 documenten. Bij de methode Stenmark/Hull wordt de cut-off value toegepast op de raw precision. Dat hebben wij ook gedaan, daarnaast hebben we de DCV toegepast op de MAP metingen.

Bij de subject search queries hebben we gekozen om ook de Raw score, de 1/r weight, de 1/SQRT weight toe te passen omdat bij deze metingen de nadruk ligt op de recall en ze daardoor een goede aanvulling zijn op de MAP. De DCV geeft daarnaast ook nog een verfijning op de MAP, beide leggen namelijk de nadruk op de precisie.

Geen echte winnaar maar Office 365 scoort beter bij known items

Office 365 soort bij de Mean Reciprocal Rank beduidend beter (MRR: 0,86) dan Google Docs (MRR: 0,62). Dat is in eerste instantie af te lezen aan de MRR in totaal, maar vermeld moet ook worden dat deze score niet wordt veroorzaakt door één of twee uitschieters: bij zes van de twintig queries scoorde Office lager dan Google, in de overige gevallen scoorde Office hoger of gelijk.

Bij de Mean Average Precision scoort Google beter (MAP: 0,71) dan Office (MAP: 0,69), hoewel het verschil gering te noemen is. Dat komt ook terug in de verdeling van de scores: in de helft van de tien queries scoorde Google hoger, in de andere helft Office.

De raw score (volgens eigen methode) gaf het volgende beeld:

Ook hier, waar de nadruk ligt op de recall, is Google Docs de winnaar. Vijfmaal scoort Google Docs hoger dan Office, driemaal scoren ze gelijk en tweemaal is de hogere score voor Office.

Hoewel de curve bij de 1/SQRT(r) weight vlakker is, komt bij zowel de 1/r weight als de 1/SQRT(r) weight precies hetzelfde beeld naar voren: Google Docs wint met een verwaarloosbaar verschil:

Opvallend is wel dat de verschillen bij sommige queries vrij groot zijn: de ene keer scoort Google veel beter, de andere keer Office. Een duidelijke lijn valt daar niet in te ontdekken.

De laatste meting was die waarbij we cut-off values (DCV) hebben bepaald op 6, 7, 8, 9 en 10 treffers.

Conclusie: Bovenin de ranking (cut-off 6 en 7) wint Office, naarmate de de cut-off hoger ligt (8,  9 en 10), scoort Google gemiddeld  beter. De verschillen zijn echter klein.

Het is interessant deze waarden te vergelijken met de MAP: scoort één van beide zoekmachines beduidend hoger als de DCV lager ligt dan 10? Bij deze berekening scoort Office .365 op alle niveaus beter dan Google Docs.

Dat is dus een verschil ten aanzien van de DCV bij de raw-score.

Op basis van ons onderzoek kan in ieder geval worden vastgesteld dat geen van beide zoekmachines als echte winnaar kan worden aangewezen omdat die beduidend beter scoort dan zijn tegenhanger. Ook in absolute zin zijn de scores niet indrukwekkend: een organisatie die grote hoeveelheden content wil opslaan in Google Docs of Office 365 doet er dan ook verstandig aan om niet uitsluitend te vertrouwen op de aangeboden zoekmachines.

Als we een winnaar zouden moeten aanwijzen, dan zou dat Office 365 zijn omdat die bij de known items duidelijk als beste scoort, niet alleen bij de totalen, maar in de meeste gevallen ook per query. In een enterprise omgeving doen known-item searches er vaak toe: men is op zoek naar een bepaald document en wil het snel hebben. Daarnaast scoort Office 365 beter bij een lage cut-off value.

Bekijk het volledige rapport voor alle volledige tabellen, een uitgebreide toelichting van de meetmethoden, een overzicht van de queries die we hebben gebruikt en onze kritische opmerkingen / lessons learned ten aanzien van het onderzoek.

Advertenties


Een reactie plaatsen

Continue toegang tot Cultureel Erfgoed

De laatste weken hebben we tijdens de module Information Retrieval kennis gemaakt met drie CATCH projecten. CATCH staat voor Continuous Access To Cultural Heritage en is een onderzoeksprogramma van de Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO).

BRIDGE : Building Rich Links to Enable Television History Research

Television is no longer an independent entity. Broadcasting companies are now platforms and providers of multimedia information. The traditional TV archive is being extended to include other sources so that a meaningful web of information can be realised. The aim of the BRIDGE project is to generate automatic links and associations between sources related to a television archive.
BRIDGE is a project of the University of Amsterdam, Utrecht University and the Netherlands Institute for Sound and Vision.

Jasmijn van Gorp vertelde ons over BRIDGE. Het doel is een zoeksysteem te bouwen voor het exploratief zoeken in de archieven van Het Nederlands Instituut voor Beeld en Geluid door televisiewetenschappers. Dit wordt in 3 stappen gedaan:

  1. Onderzoek heeft zelf de zoekinterface getest en werd daarbij geobserveerd (pre-pilot)
  2. 22 media studenten hebben de interface getest
  3. Een nieuwe interface bouwen: interviews en discussies met 30 media experts

Voor de eerste stap (pre-pilot) was het onderzoeksonderwerp Joegoslavische migranten in Nederland en werden volgende onderzoeksmethoden gebruikt: luidop nadenken, opnemen van het scherm, analyseren van de data van de browser (browser gedrag) en de onderzoeker moest een aantal vragen beantwoorden.

Het doel van de tweede fase was kijken hoe gebruikers omgaan met de zoekinterface: of het goed werkt en of het verbetert kan worden. 22 eerstejaars studenten moesten 3 zoekopdrachten uitvoeren en daarna vragen beantwoorden waarbij ze de zoekinterface evalueerden. 5 studenten vonden geen enkel goed resultaat en geen enkel student vond 5 goede resultaten per zoekopdracht. De zoekinterface kreeg net geen voldoende van de studenten. Ook werd vastgesteld dat de studenten die snel de zoekopdrachten uitvoerden vooral geen goede resultaten vonden en de studenten die er de tijd voor namen om de zoekopdrachten uit te voeren wel de goede resultaten vonden. Daarnaast kwam aan het licht dat sommige metadata belangrijker waren dan andere en dat het doel was om juist die belangrijke metadata goed te integreren in de zoekinterface. Je kunt meer lezen over deze tweede fase van het onderzoek in ‘Exploratory Search in an Audio-Visual Archive: Evaluating a Professional Search Tool for Non-Professional Users‘.

Voordat er werd begonnen aan het bouwen van de nieuwe zoekinterface werden er andere media onderzoekers bevraagt over hun ervaring met zoekmachines, hun behoeften en in welke fase hun onderzoek zat. Uiteindelijk werd MeRDES gebouwd (Media Researcher Data Exploration Suite): een zoekmachine met meerdere dimensies in data en visualisaties. MeRDES geeft resultaten visueel weer via genretaarten, tijdslijnen, woordenclouds, geografische kaarten en verschillende grafiekvormen. MeRDES werd getest door 25 media onderzoekers waarbij werd gekeken of deze dimensionale zoekinterface exploratief zoeken beter ondersteund dan een eenvoudige zoekinterface.

In de toekomst willen ze MeRDES nog gaan uitbreiden door het linken van televisiegidsen met de programma’s in de databank, het toevoegen van rating mogelijkheden en het koppelen van nieuwsfeiten (NRC Handelsblad) met programma’s zodat er naast de dimensionale zoekinterfase een verrijkte omgeving ontstaat.

WITCHCRAFT: What is topical in Cultural Heritage: content-based Retrieval Among Folksong tunes

The WITCHCRAFT project sets as its objective to develop a fully-functional content-based retrieval system for large amounts of melodies stored as audio and notation, building on the best practices of Music Information Retrieval research. The project can have an impact on MIR research by providing insight into the modeling of high-level musical features, by setting a standard to compare future systems against, and by creating tools, data and evaluation methods that can be used in other MIR research projects.
WITCHCRAFT is a project of the Utrecht University, theMeertens Instituut and the Theater Instituut Nederland.

Wat het project WITCHCRAFT inhield werd ons verteld door Peter van Kranenburg.

Music Information Retrieval is interdisciplinair en behelst dus verschillende gebieden: representatie, retrieval, indexeren, classificeren, etc. Muziek kent verschillende representatievormen: symbolisch (rijtje akkoorden weergegeven als tekst), audio (muziekfragmenten), visueel (partituren), metadata (gegevens over muziek).

In Music Informatieon Retrieval kunnen releatief eenvoudige problemen al worden opgelost, maar oplossingen voor problemen van een hoog niveau vallen buiten de huidige state-of-the-art. Een voorbeeld van zo’n probleem van hoog niveau is het leggen van relaties tussen  werken met hetzelfde thema (cultuurgeschiedenis), dus liedjes die doorheen de tijd over hetzelfde onderwerp gaan met elkaar koppelen.

Verder lezen over Music Information Retrieval:

Het doel van WITCHCRAFT is het ontwikkelen van een music retrieval systeem voor melodieën van volksliederen. De Nederlandse Liederenbank van het Meertens Instituut bevat 2 collecties met volksliederen: Onder de groene linde en Collectie Harrie Franken. Om uit deze collecties aan elkaar gerelateerde melodieën te halen (dus volksliederen met dezelfde melodiefamilie maar waarvan de uitvoeringen en teksten door de tijd zijn verandert) is het nodig om een zoekmachine te bouwen die ‘oral transmission’ onderzoek mogelijk maakt. Dit kan door middel van ‘afstemming’ aan de hand van volgende criteria:

  • Ritmische gelijkenissen
  • Vergelijking ‘belangrijke’ noten
  • Kijken naar mogelijke vermindering / vermeerdering

Daarnaast kan melodieuze gelijkenis afhankelijk zijn van verschillende dimensies:

  • Ritme (per zin / voor de hele melodie)
  • Contour (per zin / voor het hele melodie)
  • Motieven
  • Tekst

Om melodieën via een zoekmachine te vergelijken moet er gekeken worden hoe een melodie kan worden gerepresenteerd in symbolen en waaruit de vergelijkenissen en verschillen bestaan wat betreft bovengenoemde dimensies in deze symbolen.

Het experiment binnen WITCHCRAFT is uitgevoerd met 360 zoekvragen in de vorm van melodieën, 26 melodiefamilies en 4830 liedjes.

Meer lezen over dit experiment: Final report of CATCH project WITCHCRAFT.

MuSEUM: Multiple-collection Searching Using Metadata

MuSeUM addresses the prototypical problem of a cultural heritage institute with the ambition to disclose all of its content in a single, unified system. Institutes use various systems, each dealing with a small part of the collection, constructed for different purposes, in different times, by different people, working in different traditions, based on different design principles, with different access methods, etcetera. This project will investigate theoretically transparent ways of combining modern information retrieval methods based on statistical language modeling with varying amounts of metadata and non-content features.
MuSEUM is a project of the University of Amsterdam, the Gemeentemuseum Den Haag, the Rijksbureau voor Kunsthistorische Documentatie and the Municipal Archives Rotterdam.

Onze docent, Marijn Koolen, was één van de onderzoekers van MuSEUM en hij vertelde over zijn rol binnen het onderzoek.

Het idee achter MuSEUM is dat er veel erfgoedinstellingen (musea) heel veel databases hebben die heel heterogeen zijn maar vaak over hetzelfde gaan, hoe ga je nou met één systeem in al die databases zoeken en items die over hetzelfde gaan aan elkaar koppelen? Het gaat daarbij om rijke collecties waarvan de metadata omschreven is in verschillende standaarden en beschrijvingen, soms incomplete informatie bevat en waarvan de toekenning van trefwoorden en het classificeren subjectief is. Een ander issue is dat niet alle metadata openbaar mag worden gemaakt. Velden met kunstwaarden, verzekeringsgegevens en de plaats van het kunstobject mogen niet zomaar in de zoekresultaten tevoorschijn komen, dus zomaar alle metadata uit de databases halen en in een index stoppen kan niet. Deze informatie moest dus gelabeld worden waardoor er een scheiding werd gemaakt tussen gevoelige en niet-gevoelige informatie. Hiermee is het onderzoeksteam 6 maanden mee bezig geweest omdat dit handmatig moest gebeuren. Daarna hebben ze testcollecties gebouwd, search requests en relevance judgments voor de verschillende (delen van de) collectie en voor verschillende zoektaken en verschillende typen gebruikers opgesteld en known-item queries (queries per databases: objecten, bibliotheek en archief) geformuleerd.

Het ging hierbij om de databases (Adlib) van het Gemeentemuseum Den Haag. Daarom gingen we met de klas ook een kijkje nemen in dit museum en kregen we daar een presentatie van Vincent de Keijzer over het eigenlijke zoeksysteem dat is gebouwd. Het zoeksysteem dat theoretisch is bedacht moet natuurlijk ook echt gebouwd worden. Het moet een gebruiksvriendelijk en simpel zoeksysteem worden. Zoals aangegeven doorzoekt het systeem verschillende databases: museumcollectie (gedigitaliseerde objecten, bv. foto’s van de museumstukken en metadata over deze objecten), bibliotheek en archief. Belangrijk is daarbij dat er relaties worden gelegd tussen deze 3 collecties. Door op een Google-achtige manier doorheen de 3 systemen te zoeken (eenvoudig zoeken) maar daarnaast ook optimaal gebruik te maken van de zoekmogelijkheden van de 3 systemen apart (zoeken op specifieke velden, geavanceerd zoeken) kunnen resultaten uit de 3 systemen aan elkaar gekoppeld worden. Bijvoorbeeld: wanneer je objecten zoekt rond de Haagse School dan zal je niets vinden als je alleen in één database zoekt (omdat die niet dit soort metadata bevat), maar door de koppeling met andere databases (zie hierboven) kunnen alle objecten juist wel naar boven gehaald worden.

De opbouw van het zoeksysteem is als volgt:

  • MuS = eerste grove zoekactie op zoek naar bronnen
  • O_og = tools voor verdere bewerking zoekresultaat
  1. Er wordt door alles gezocht op zoek naar het PID (het unieke ID nummer van objecten) van objecten die voldoen aan de zoekvraag –> MuS index alle xml (eenvoudig zoeken)
  2. Er wordt door alles gezocht aan de hand van de Dublin Core descriptoren (creator, contributor, publisher, title, description, subject, coverage, date, type en format) –> MuS index DC (geavanceerd zoeken)
  3. Er wordt door alles gezocht aan de hand van specifieke velden: wie, wat, waar, wanneer en hoe –> MuS index WWWH (geavanceerd zoeken).
    In de zoekopdracht geeft de zoeker aan de hand van kleuren aan waarop de zoekwoorden betrekking hebben:
  4. Er wordt gekeken naar de relaties tussen de verschillende databases. Hierbij wordt gekeken naar in welke velden die relaties zitten. –> MuS index relaties
  5. Daarna wordt de ranking toegepast:
    a = MuS index alle xml –> lijst relevante PIDs
    b = MuS indexen WWWWH/DC –> lijst relevante PIDs
    * = MuS index relaties –> PIDs van relevante records EN all gerelateerde PIDs van die records
    a* en b* = # (MuS Ranking) –> a : b
    En uiteindelijk komen er dan twee lijsten uit: a*# en b*# waarbij a*# geen rekening houdt met WWWH/DC (eenvoudig zoeken) en b*# hier wel mee rekening houdt (geavanceerd zoeken)
  6. Daarna moeten de resultaten nog gefilterd worden (zie het label proces hierboven gevoelige / niet-gevoelige informatie) voordat de resultaten getoond kunnen worden:
    – geen objectbeschrijving (maar wel aangeven dat er x objecten zijn die aan de zoekvraag voldoen)
    – volledige objectbeschrijving
    – deels beschikbare objectbeschrijving
    De filter wordt daarbij alleen toegepast op de objectbeschrijvingen, dus het zoeken gebeurt wel full-text maar bij het tonen van de objectbeschrijvingen wordt gekeken naar de policy van individuele instellingen.
    De reden om van de resultaten die wel aan de zoekvraag voldoen maar waarvan geen informatie naar buiten mag komen wel het aantal te tonen is om het doel van het project (zie hierboven) waar te maken: om ALLE objecten die over hetzelfde gaan bij elkaar te kunnen brengen. Als je bijvoorbeeld een tentoonstelling rond Art Deco wilt organiseren kun je zien wat het totaal aantal objecten rond Art Deco zijn en kun je met de desbetreffende instellingen contact opnemen om afspraken te maken voor de tentoonstelling. Zo is het mogelijk om werkgroepen (over alle instellingen heen en niet alleen medewerkers van de instellingen maar ook onderzoekers en andere gebruikers) te creëren die rond een bepaald thema kunnen werken (en dan vooral die thema’s die door tijdgebrek door de instellingen zelf nog niet zijn aangepakt) .

De zoekmachine zal een thematische opbouw krijgen waardoor eindeloze selectie mogelijk is. Dit is ook de manier waarop de collectie van het Gemeentemuseum wordt gedigitaliseerd (wordt per thema aangepakt).

Bij het bouwen van het zoeksysteem wordt gebruik gemaakt van open source software: Drupal en Solr. Dit om afhankelijkheid van programmeurs te vermijden. Het is daarbij nodig om voor open source software te kiezen wat door een grote en actieve community wordt ondersteund.

Het Gemeentemuseum wil half 2012 live gaan met hun zoeksysteem en daarna het zoeksysteem uitbreiden naar andere gerelateerde culturele instellingen met Adlib systemen en daarna ook met niet-Adlib systemen aan de slag gaan zodat er één metazoekmachine komt zoals beoogd in het idee van het project.

We zaten trouwens tijdens het bezoek in de mooie bibliotheek van het Gemeentemuseum en mochten ook een kijkje nemen achter de schermen van de mode-afdeling. Zoals je uit mijn tweets kunt opmaken was het een enerverende middag: