Relevance Feedback Between Hypertext and Semantic Search

Harry Halpin, <H.Halpin@ed.ac.uk>>

Some graph

Relevance Feedback Between Hypertext and Semantic Search

Links Join Across Different Sources of Information

 Links between column headings

Verb/predicate/Property using same URIs

What are semantics?

Is is something to do with "meaning" or "roles given by natural language processing" or...

Semantic Web = structured data with a simple formal semantics as a Web standard.

To a computer, then, the web is a flat, boring world devoid of meaning...This is a pity, as in fact documents on the web describe real objects and imaginary concepts, and give particular relationships between them...Adding semantics to the web involves two things: allowing documents which have information in machine-readable forms, and allowing links to be created with relationship values.TimBL, WWW1994

RDF data...

a set of circles and arrows

...merges just like that.

more circles and arrows superim

Subject and object node using same URIs

The semantic Web’s real selling point is URI-based data integration.

The Problem

Users need to re-use URIs for vocabularies and entities in order to get the full benefit of the Semantic Web.

Semantic Web-enabled ontology mapping and entity integration does not seem to work quite well at the moment in open domains...)

Why not use Web search?: But if a user searches for a concept via keywords, you get too many URIs and its very user-hostile to inspect the RDF (or lack thereof) at these URIs to ascertain their meaning.

How can we get semantic search results to be better?

Hypothesis

How can we actually make a virtuous cycle between hypertext search and semantic search in order to improve results of structured data without asking user to do anything different than they currently do.

Using relevance feedback from hypertext search on semantic web data, and vice versa.

Are there URIs in Practice

Question:Is there too many or no URIs of interest?

Answer: : Sample the Semantic Web using a query log, prune any query with less than 10 repetitions.

Use brute-force simple rules and gazetteers (U.S. Census for names, Alexandra project for places, Wordnet and hyponym with hypernyms) to discover named entities with low recall and high precision.

Data Set: Microsoft Live Search Query Log for 1 month from 2007

Too Many URIs

There are too many URIs for the same thing probably...

An average of 1,339 URIs (S.D. 8,000) returned per query. That's a lot, but most may obviously be URIs that just mention the term...

return frequency

Top Entities and Concepts

Number of Searches (RDF Hits) Entity:
  1. 7311 (99) david blaine
  2. 2997 (134) jessica alba
  3. 2100 (16723) nick
  4. 1280 (178) michael hayden
  5. 1098 (10) marcus vick
  6. 1092 (199) keith urban
  7. 1015 (43) lane bryant
  8. 990 (55) desmond dekker
  9. 922 (312) jennifer white
  10. 900 (100) clay aiken
  11. 883 (359) bill cosby
    Concepts:
  1. 11383 (10767) weather
  2. 10321 (7777) dictionary
  3. 3675 (434333) people
  4. 3217 (189115) music
  5. 3117 (7196) monster
  6. 2192 (1444) autism
  7. 1468 (149436) map
  8. 1198 (17562) travel
  9. 1191 (12067) pregnancy
  10. 1104 (82074) news

Whose Got the Data: Entities and Concepts

Top 10 Domain Names: Entities

  1. 76706 dbpedia.org
  2. 2992 www4.wiwiss.fuberlin.de
  3. 2848 en.wikipedia.org
  4. 1264 upload.wikimedia.org
  5. 940 www.liveinternet.ru
  6. 928 www.w3.org
  7. 668 de.wikipedia.org
  8. 630 fr.wikipedia.org
  9. 491 ontoworld.org
  10. 389 sv.wikipedia.org

Top 10 Domain Names: Concepts

  1. 18919 dbpedia.org
  2. 3032 www.w3.org
  3. 694 www.cyc.com
  4. 554 bio2rdf.org
  5. 299 truesense.net
  6. 243 www4.wiwiss.fuberlin.de
  7. 171 ontoworld.org
  8. 143 en.wikipedia.org
  9. 132 www.liveinternet.ru
  10. 97 semanticweb.org

Getting Users to Re-use URIs

No-one naturally will rank and look at raw RDF except Semantic Web developers: ordinary users will not use Tabulator or other linked data browsers.

Tabulator

Also, imagine if Microsearch returned only the best information related to your query in a open-domain infobox.

The amount of co-ordination needed does not need full agreement, but only the minimal agreement needed to get the task at hand completed.

How can we boot-straps URIs for things and re-use these URIs in a way that people will actually use?

Answer: Use a paradigm average Web users are familiar with, such as a search paradigm and use their click-throughs as relevance feedback to re-rank URIs.

One Search: Different Formats

referent

An Algorithm

  1. Given a term, retrieve a set of web-pages (Using Yahoo!).
  2. Given a term, retrieve a set of Semantic Web URIs and all triples (facts) associated with them, using FALCON-S.
  3. Human searches through web-sites.
  4. For each web-page the human
    1. Human clicks through web-page.
    2. For each web-page the human clicks on
      1. Strip out HTML and reduce to words.
    3. For each Semantic Web returned by the query log
      1. Extract all text and typed data from each RDF fact
      2. Decompose RDF into "a bag of words" with lemmatization and removal of words from end of URI.
      3. match converted RDF to HTML using information retrieval text.
  • pick the URI with the best ranking score given by IR techniques.
  • Relevance Feedback

    Have a human judge actually figure out what web-pages are relevant, and then use those to feed back and expand the query, in order to re-rank the results.

    In their instructions, relevance was defined can be determined by whether or not accurate information about the information need is expressed by the result. This excludes both link farms, non-standard redirects, and legitimate hubs.

    Experiment: Had 200 queries from previous work, retrieved top 10 hypertext Web (Yahoo!) results and top 10 (FALCON-S) results each judged by 3 judges for relevancy. Fliess's Kappa=0.5724$ (p < .05, 95% Confidence interval [0.5678,0.5771]), indicating the rejection of the null hypothesis and moderate agreement.

    referent

    Results

    Results of Relevance Judgements:

    Results: Hypertext Semantic Web
    Resolved: 197 (98%) 132 (66%)
    Unresolved: 3 (2%) 68 (34%)
    Top Relevant: 121 (61%) 76 (58%)
    Top Non-Relevant: 76 (39%) 56 (42%)

    Relevance Results: Hypertext

    referent

    Results of Querying the Hypertext Web

    Relevance Results: Semantic Web

    referent

    Results of Querying the Semantic Web

    Finding Right IR Technique and Parameters

    referent

    Average Precision Scores for Vector-space Model Parameters: Relevance Feedback From Hypertext to Semantic Web

    Next result was BM25 with the slight performance-enhancing modifications used in the InQuery system and comparison function used with standard Rocchio relevance feedback with slight modifications as used by Okapi and window size = 100 was best.

    Finding the Right URI is now Acceptable!

    referent

    Why?

    Text automatically extracted from hypertext documents is `messy,' being of low quality and bursty, with highly varying document lengths.

    The amount of triples in Semantic Web documents follow a power-law, so there are wildly varying document lengths of both the relevance model and the document models.

    So , it is unwise to normalise the models, as that will almost certainly dampen the effect of valuable features like crucial keywords.

    The reason BM25-based vector models in particular perform so well is that they are able to effectively keep track of both term frequency and inverse term frequency accurately.

    BM25 provides a slight amount of rather unprincipled non-linearity in the importance of the various variables, effectively keep track of both term frequency and inverse term frequency accurately while massively lowering the power of another document length.

    Run it in reverse!

    Now apply relevance feedback from Semantic Web search engines to the hypertext Web! referent

    Average Precision Scores for Language Model Parameters: Relevance Feedback From Hypertext to Semantic Web

    The best relevant models sampled over top 10,000 words with a cross entropy smoothing factor set to .5. Relevance models over all concatenated relevant documents beats relevance models with documents sampled individually and then combined, as well as all vector-space models.

    Looking at results

    Results: Feedback FALCON-S
    Top Relevant: 118 (89%) 76 (58%)
    Non-Relevant Top: 14 (11%) 56 (42%)
    Non-Relevant Top Entity: 9 (64%) 23 (41%)
    Non-Relevant Concept: 5 (36%) 33 (59%)

    A respectable 19% in average precision over the engine FALCON-S, intuitively makes the system's ability to place a relevant URI in the top rank acceptable for most users.

    The Semantic Web can help Hypertext Search

    referent

    Why?

    As the Semantic Web data is mostly manually high-quality curated data from sources so the actual natural language fragments on the Semantic Web (found for example in Wikipedia abstracts) are much better samples of natural language than the natural language samples found in hypertext.

    The distribution of `natural' language terms extracted from RDF terms, while often irregular, will either be repeated very heavily or fall into the sparse long tail, which can then be dealt with by relevance models.

    The hypertext search engine is being `seeded' with a high-quality accurate description of the information need expressed by the query to be used for query expansion.

    Conclusions

    Results: Finding the best URIs on the Semantic Web can be built out of the social semantics implicitly given by the searching behavior of ordinary users, as given in query logs. referent My implementation that ranks all Semantic Web search engines is here.

    We need to deploy methodology from IR, NLP, machine-learning, databases, and actual human evaluation in order to make the Semantic Web actually work.

    We should probably start going "back to basics" with RDF and look at the quality of text on the Semantic Web.

    Please see paper for actual equations describing all the IR frameworks we used, i.e. relevance models, BM25, Ponte's method, local content analysis, and more.