Semantic Search en het gebruik van RDF en graventheorie

Semantic Search en het gebruik van RDF en graventheorie Wouter van den Hoven1 1 Faculteit Exacte Wetenschappen, Vrije Universiteit, De Boelelaan 1081, 1081 HV Amsterdam, Nederland [email protected]

Abstract. De gemiddelde gebruiker heeft door de enorme omvang van het World Wide Web behoefte aan effectieve zoekmethoden om nuttige informatie te vinden op dit web. Huidige methoden voldoen deze behoefte maar beperkt. Met de komst van het Semantic Web heeft het web structuur gekregen en kan er efficiënter gezocht worden. Slechts een klein gedeelte van het WWW is reeds opgenomen in het Semantic Web. Verschillende Semantic Search methoden zijn ontwikkeld die zeer divers zijn. Om Semantic Search aantrekkelijk te maken voor de gewone gebruiker zal de manier van zoeken simpel en overzichtelijk moeten zijn, bijvoorbeeld in een GUI. Ook zal een succesvolle methode gebruik moeten kunnen maken van zowel semantische methoden als klassieke keyword methoden.

1 Introductie Met de komst van het internet en daarmee ook de komst van het World Wide Web is er een behoefte ontstaan om dit web te doorzoeken. Door de enorme omvang is het niet mogelijk om van pagina tot pagina te gaan tot je de informatie hebt gevonden die je zoekt. Uit deze behoefte ontstonden de zoekmachines, waarvan Google op dit moment de grootste is. Deze zoekmachines werken allemaal volgens hetzelfde stappenplan: Een crawler doorzoekt het web, de gevonden pagina’s worden gescand op keywords, deze keywords en hun locatie worden opgeslagen in een index en tot slot laten zij de gebruikers zoeken in deze index voor (combinaties van) keywords. Deze manier van zoeken levert over het algemeen goede resultaten op maar voor complexe queries is zij minder geschikt. Zoekmachine Wolfram Alpha gebruikt een andere aanpak en geeft antwoord op vragen, geformuleerd als volzinnen. De zoekruimte is hierbij een database speciaal aangelegd voor dit doel en dus worden er geen webpagina’s maar antwoorden teruggegeven. Om betere resultaten te boeken voor het doorzoeken van webpagina’s is men bezig met het ontwikkelen van Semantic Search. Hierbij wordt er gezocht op het Semantic Web. Het Semantic Web is een framework van verbanden tussen informatie op het World Wide Web dat gebruik maakt van meta-data van en op webpagina’s. Door dit gestructureerde framework te doorzoeken kan gerichter gezocht worden en specifiekere informatie gevonden worden.

In dit paper zal ik om te beginnen enkele veelgebruikte termen in het gebied van Semantic Web benoemen en toelichten. Hierna zal ik kijken naar verschillende methoden van Semantic Search. Vervolgens zal ik dieper ingaan op twee specifieke methoden die beiden op een verschillende manier gebruik maken van graventheorie en RDF en deze vergelijken om te kijken welke de grootste overlevingskans heeft.

2 Veelgebruikte termen Semantic Web – Het Semantic Web verschaft een standard framework waarmee data gedeeld en gebruikt kunnen worden[1]. Het kan gezien worden als een web van verbanden tussen informatie op het internet[2]. RDF – Resource Description Framework of RDF is een standaard van het World Wide Web Consortium (W3C), oorspronkelijk ontworpen als een metadata-model, maar gaandeweg gebruikt als een formaat om gegevens in het algemeen voor te stellen en uit te wisselen. Met het RDF-model kunnen uitspraken gedaan worden over de kenmerken van bronnen op het web (resources) in de vorm van een drieledige subject-predicaat-object-structuur (in RDF-termen een triple). Graaf – Een graaf bestaat uit een verzameling punten, knopen genoemd, waarvan sommige verbonden zijn door lijnen, de zijden, kanten of takken. SQL – SQL (Structured Query Language) is een ANSI/ISO-standaardtaal voor een relationeel databasemanagementsysteem (DBMS). Het is een gestandaardiseerde taal die gebruikt kan worden voor taken zoals het bevragen en het aanpassen van gegevens in een relationele gegevensbank. Query – Met een query wordt in de informatica een opdracht bedoeld die aan een database wordt gegeven om een bepaalde actie uit te voeren, die ook potentieel gegevens terug geeft. Tegenwoordig wordt de term ook gebruikt voor een zoekstring die in een zoekmachine wordt ingevoerd. Ontologie – In de informatica en de logica is een ontologie het product van een poging een uitputtend en strikt conceptueel schema te formuleren over een bepaald domein. Een ontologie is typisch een datastructuur die alle relevante entiteiten en hun onderlinge relaties en regels binnen dat domein bevat, zoals bij een domeinontologie het geval is.

3 Categorieën van Semantic Search Semantic Search is een gebied waarin veel geëxperimenteerd wordt en waar nog weinig vaste regels gelden. Zodoende zijn er veel verschillende toepassingen en methoden van Semantic Search. In de survey van Eetu Mäkelä[3] wordt onderscheid gemaakt tussen vijf verschillende categorieën methoden van Semantic Search, welke ik hieronder apart zal behandelen.

3.1 Augmenting Traditional Keyword Search with Semantic Techniques Veel van de technieken die gebruikt worden voor Semantic Search gebruiken een combinatie van traditionele keyword search en breiden deze uit door er semantische technieken op toe te passen. Het grote verschil tussen technieken uit deze categorie en de technieken uit de verder genoemde categorieën is dat deze technieken niet uitgaan van een formeel gestructureerde zoekruimte. De technieken in deze categorie maken allen gebruik van een ontologie. Op verschillende manieren combineren zij keyword search met deze ontologieën. Er zijn methoden die ontologieën gebruiken om de query uit te breiden[4][5][6]. In de ontologie wordt dan gezocht naar synoniemen en deze worden toegevoegd aan de query. Andere methodes matchen de keywords aan objecten in een RDF-database waarna de gebruiker kan kiezen welk object bedoeld wordt met het keyword[7]. 3.2 Basic Concept Location Bij Basic Concept Location staat de ontologie centraal. Gebruikers kunnen navigeren door een ontologie of enkele classes selecteren en zo objecten en relaties selecteren en daarmee een query vormen. Het navigeren door een ontologie kan op verschillende manieren waarvan er een aantal veel gebruikt worden. De meest simpele manier is om te starten met een ontologie waarin verschillende classes weergegeven worden. De gebruiker kiest dan een class met de instantie waar hij/zij naar op zoek is[8][9]. Vanuit hier worden er relaties bij gezocht en wordt een query geformuleerd. Een complexere manier is om de gebruiker meerdere gezichtspunten te geven waaruit de ontologie bekeken en doorzocht kan worden. Hier worden niet verschillende classes getoond maar wordt er eerst een gezichtspunt bepaald[10][11][12]. In sommige gevallen gebeurt dit door de gebruiker eerst keywords te laten geven en aan de hand daarvan gezichtspunten vast te stellen, waarna doorgegaan wordt met Semantic Search. Ook is er een methode die zich volledig richt op het browsen tussen verschillende resources[11][12]. Het idee achter deze methode is dat de gebruiker weet waar de benodigde informatie ongeveer staat en/of aan welke andere resources deze gelinkt is. Door middel van browsing komt de gebruiker zo terecht bij de benodigde informatie. 3.3 Complex Constraint Queries Complexe queries, zoals gebruikt bij Semantic Search, zijn vaak te formuleren als objecten aan elkaar gelinkt door eigenschappen. Door objecten aan elkaar te linken met verschillende eigenschappen en dit als geheel te zien krijg je een gravenpatroon waarnaar specifiek gezocht kan worden. De techniek hierachter is relatief simpel en goed toe te passen, maar het maken van een dergelijk patroon wordt door de gemiddelde gebruiker nog als complex ervaren. Om deze reden is het onderzoek naar deze methoden vaak gericht op het voor gebruikers vereenvoudigen van dit soort queries.

De verschillende methoden in deze categorie gebruiken allen een Graphical User Interface (GUI) om de gebruiker grafisch een query te laten formuleren. Sommige van deze methoden beginnen met een leeg veld[15], anderen laten de gebruiker een startpatroon kiezen en werken vanuit daar verder[16]. Ook kan er gefilterd worden op verschillende entiteiten. Bij enkele methoden kan dit ook met keywords[17]. 3.4 Problem Solving Als aan Semantic Search gedacht wordt denkt men snel aan het formuleren van een probleem dat vervolgens met behulp van een ontologie wordt opgelost. In de praktijk is dit echter zelden het geval en zijn er slecht enkele search engines die deze methode toepassen. De bekendste[18] gebruikt geen SQL-stijl queries maar queries met ‘if-then’ combinaties. Zo kan een vraag geformuleerd worden die het systeem kan gebruiken om in de ontologie naar de benodigde informatie te zoeken. 3.5 Connecting Path Discovery Bij deze methoden wordt gekeken naar veel belopen paden in de graven die de ontologieën vormen. In plaats van de gebruiker zelf door de ontologie te laten browsen doorzoeken algoritmen de ontologie en selecteren zij hieruit paden die vaak belopen worden en interessante connecties bevatten. Dit is vooral interessant voor instanties die patroonherkenning toepassen zoals bijvoorbeeld veiligheidsinstanties. Een probleem bij deze methode is het bepalen van de gewichten van de connecties in de graaf. Connecties kunnen als zeer belangrijk worden beschouwd terwijl dit niet het geval is, terwijl tegelijkertijd ook subtiele doch belangrijke connecties gevonden moeten worden[19].

4 GUI query ontwerp In dit hoofdstuk wordt dieper ingegaan op Complex Constraint Queries zoals beschreven in 2.3. Zoals beschreven zijn er verschillende methoden die zich focussen op het bouwen van GUI’s om zo het creëren van RDF queries toegankelijk te maken voor het grote publiek. Dit is een essentieel onderwerp van Semantic Search. Het Semantic Web en zeker Semantic Search zijn nieuwe en jonge begrippen, in 2001 stelde Tim Berners Lee een dergelijk web voor[20]. Aangezien het nieuw en in ontwikkeling is wordt het voornamelijk gebruikt onder wetenschappers en ontwikkelaars. In deze fase is dat voldoende, echter zodra er stabiele zoekmachines voor het Semantic Web zijn zullen deze in gebruik moeten worden door de doelgroep om hun doel te bereiken. Door een

simpele en duidelijke GUI te verzorgen wordt de gebruiker niet afgeschrikt en nodigt het systeem uit tot gebruik. Zoals vermeld in sectie 2.3 zijn er verschillende methoden ontwikkeld waarbij GUI’s gebruikt worden. Een van de meest doorontwikkelde methoden is The ICSFORTH Graphical RQL Interface (GRQL)[15]. Hierbij start de gebruiker met een leeg veld en kan gestart worden bij een willekeurige class, zoals schematisch weergegeven in Tabel 1. Navigation

RQL Query

Path

select X1 from Artist{X1}

Artist

Tabel 1. Gebruiker kiest class Artist als beginpunt

Vanuit deze class kunnen via verschillende relaties andere classes aan de selectie worden toegevoegd. Dit is schematisch weergegeven in Tabel 2. Navigation

RQL Query

Path

select X2 from {X1}creates{X2}

Artist à creates à Artifact

Tabel 2. Navigatie van class Artist naar class Artifact via relatie Creates

Via deze weg wordt het pad uitgebreid tot de gebruiker de gewenste classes heeft toegevoegd. Vervolgens wordt dit pad meegegeven aan de zoekmachine waarna de zoekmachine het gewenst antwoord retourneert. Het belangrijkste onderdeel van dit systeem, de GUI, is weergegeven in Fig. 1.

Figuur 1. De GUI van GRQL na het bereiken van een pad met drie classes

5 Hybride zoekmethoden In deze sectie worden hybride zoekmethoden besproken. Deze methoden gebruiken deels semantische technieken als RDF en deels de klassieke keyword search. Aangezien op het moment slechts een zeer klein deel van het World Wide Web opgenomen is in het Semantic Web zullen er zo lang nog niet het hele WWW in het Semantic Web te vinden is hybride methoden nodig zijn die met beide webs om kunnen gaan en er nuttige informatie uit te kunnen halen. Technieken zoals besproken in sectie 2.1 passen deze combinatie toe. Enkele methoden[4][5][6] gebruiken ontoglogieen met woord-databases zoals de WordNet ontologie om keywords te koppelen aan objecten in de ontologie om zo ook synoniemen van de keywords aan de zoekopdracht toe te voegen. Dit is een zeer simpele en primitieve methode die wel degelijk gebruik maakt van semantische methoden maar verder geen gebruik maakt van het Semantic Web. De handelingen waarbij semantische methoden worden toegepast zouden ook met behulp van andere technieken kunnen worden toegepast. Interessantere methoden zijn deze die de keywords analyseren en koppelen aan objecten in de ontologie, net zoals de hierboven beschreven methoden, maar vervolgens verder gaan met zoeken aan de hand van de geselecteerde objecten in de ontologie. Deze methoden maken op een actievere manier gebruik van het semantisch web en zijn daarmee interessanter om te bekijken en te volgen in hun ontwikkeling.

6 Wolfram Alpha Naast Semantic Search zijn er nog meer methoden die verder gaan in het toepassen van structuur dan de traditionele zoekmethoden die enkel gebruik maken van keywords. Wolfram Alpha is hier een geslaagd voorbeeld van. Deze antwoordmachine is ontwikkeld door de firma Wolfram Research en online voor het publiek sinds 18 mei 2009[21]. Door in keywords en/of volzinnen te zoeken worden zeer gerichte en specifieke antwoorden gegeven. Vooral statistieken en harde feiten zijn goed te vinden. Er zijn echter twee belangrijke verschillen tussen Semantic Search en Wolfram Alpha. Ten eerste gebruikt Wolfram Alpha het programma Mathematica om zijn berekeningen uit te voeren. Deze veelzijdige applicatie wordt veel gebruikt in de wetenschappelijke wereld om onder andere complexe wiskundige en natuurkundige berekeningen uit te voeren. Semantic Search maakt daarentegen geen gebruik van thirs party software maar, in de meeste gevallen, van het RDF-protocol. Ten tweede zoekt Wolfram Alpha niet in het World Wide Web of Semantic Web maar in een database. Deze database wordt weliswaar gevuld met informatie van het web maar deze informatie is niet real time en ook wordt niet het volledige web opgeslagen. Hierdoor zal er altijd (eventuele belangrijke) informatie niet doorzocht worden.

7 Conclusie Te concluderen valt dat er veel diverse technieken en methoden worden gebruikt voor Semantic Search die onderling veel verschillen maar ook overeenkomsten vertonen. Er wordt in bijna alle gevallen gebruik gemaakt van een ontologie in RDF vorm die valt te doorlopen als een graaf. Door het vroege stadium waarin deze ontwikkeling zich bevindt zal moeten blijken welke methode het meest effectief blijkt en het grote publiek zal bereiken. Aangezien de gemiddelde gebruiker moeite zal hebben met het formuleren van RDF queries zal er een gemakkelijke methode gevonden moeten worden om deze te creëren. Door gebruik te maken van een GUI zal dit proces verduidelijkt worden voor de gebruiker. Ook is nog niet het hele WWW opgenomen in het Semantic Web. Om deze reden zullen er, zeker in de beginfase, hybride methoden nodig zijn die gebruik maken van zowel semantische methoden als klassieke keyword methoden. Ik geef een hybride methode met een simpele GUI dan ook het meeste kans om door te breken als grondlegger van de Semantic Search technologie.

References 1. 2.

3. 4. 5. 6.

7. 8. 9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

W3C Semantic Web Activity. World Wide Web Consortium (W3C) (November 7, 2011). Wat is het semantisch web in begrijpelijke taal (2010-07-21). http://yocter.nl/socialmedia-blog/2010/07/wat-is-het-semantisch-web-het-in-semantisch-web-inbegrijpelijke-taal/ Baldonado, M., Chang, C.-C.K., Gravano, L., Paepcke, A.: The Stanford Digital Library Metadata Architecture. Int. J. Digit. Libr. 1 (1997) 108–121 Moldovan, D.I., Mihalcea, R.: Using wordnet and lexical operators to improve internet searches. IEEE Internet Computing 4 (2000) 34–43 Buscaldi, D., Rosso, P., Arnal, E.S.: A wordnet-based query expansion method for geograpical information retrieval. In: Working Notes for the CLEF Workshop. (2005) K ruse, P.M., Naujoks, A., Roesner, D., Kunze, M.: Clever search: A wordnet based wrapper for internet search engines. In: Proceedings of the 2nd GermaNet Workshop. (2005) Guha, R., McCool, R., Miller, E.: Semantic search. In: WWW ’03: Proceedings of the 12th international conference on World Wide Web, ACM Press (2003) 700–709 Heflin, J., Hendler, J.: Searching the web with shoe (2000) Maedche, A., Staab, S., Stojanovic, N., Studer, R., Sure, Y.: Seal - a framework for devel- oping semantic web portals. In: Advances in Databases, Proceedings of the 18th British National Conference on Databases. (2001) 1–22 Mäkelä E., Hyvönen, E., Saarela, S., Viljanen, K.: OntoViews - A Tool for Creating Se- mantic Web Portals. In: Proceedings of the Third Internation Semantic Web Conference, Springer Verlag (2004) Reynolds, D., Shabajee, P., Cayzer, S.: Semantic Information Portals. In:Proceedings of the 13th International World Wide Web Conference on Alternate track papers & posters, ACM Press (2004) Hyvönen, E., Mäkelä, E., Salminen, M., Valo, A., Viljanen, K., Saarela, S., Junnila, M., Kettula, S.: Museumfinland – finnish museums on the semantic web. Web Semantics: Science, Services and Agents on the World Wide Web 3 (2005) 224–241 Karger, D.R., Bakshi, K., Huynh, D., Quan, D., Sinha, V.: Haystack: A generalpurpose information management tool for end users based on semistructured data. In: Proceedings of the CIDR Conference. (2005) 13–26 Quan, D., Huynh, D., Karger, D.R.: Haystack: A platform for authoring end user semantic web applications. In: Proceedings of the Second International Semantic Web Conference. (2003) 738–753 Athanasis, N., Christophides, V., Kotzinos, D.: Generating on the fly queries for the semantic web: The ics-forth graphical rql interface (grql). In: Proceedings of the Third International Semantic Web Conference. (2004) 486–501 Catarci, T., Dongilli, P., Mascio, T.D., Franconi, E., Santucci, G., Tessaris, S.: An ontology based visual tool for query formulation support. In: Proceedings of the 16th Eureopean Conference on Artificial Intelligence, IOS Press (2004) 308–312 Zhang, L., Yu, Y., Zhou, J., Lin, C., Yang, Y.: An enhanced model for searching in semantic portals. In: WWW ’05: Proceedings of the 14th international conference on World Wide Web, New York, NY, USA, ACM Press (2005) 453–462 Fikes, R., Hayes, P., Horrocks, I.: Owl-ql: A language for deductive query answering on the semantic web. Technical report, Knowledge Systems Laboratory, Stanford University, Stanford, CA (2003)

19. Anyanwu, K., Sheth, A.P.: ρ-queries: enabling querying for semantic associations on the semantic web. In: Proceedings of the 12th international conference on World Wide Web. (2003) 690–699 20. Tim Berners-Lee, James Hendler, Ora Lassila: The Semantic Web: a new form of Web content that is meaningful to computers will unleash a revolution of new possibilities. In: Scientific American, 284 (5), S. 34–43, May 2001 (dt.: Mein Computer versteht mich. In: Spektrum der Wissenschaft, August 2001, S. 42–49) 21. http://www.wolframalpha.com/docs/timeline/computable-knowledge-history-6.html [17-6-2013 23:10]