Web-Scale Semantic Social Mash-Ups

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

Henry S. Thompson, <ht@inf.ed.ac.uk>

RDF

Web-Scale Semantic Social Mash-Ups with Provenance

Web-scale?

The problem with mash-ups is that we need to combine data from anywhere on the Web.

However, current mash-ups are mostly API-based, and much Web data that one wants to mash-up has to be accessed. Could we do data-based declarative mash-ups based on "raw data"?

Example of mashup

We need a way to:

  1. identify data: URIs
  2. a format for combining data: RDF

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 (and perhaps only) selling point is URI-based data integration.

URIs unpacked

The nature of resources

What about web pages?

Resources vs. representations

Information resources

Linked Data

The application of Web architecture and the 303 decision to the Semantic Web is the second-generation Web of linked data.

Claims billions of RDF triples! causal

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.

Are there URIs in Practice?

Question:Are there too many or no Semantic Web 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...

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

The power-law blues

Very few empirical studies have been done on Linked Data, and often of the type "Look, it's a power-law!" without any proper statistical tests. See Clauset, Newman et al. paper referenced in my paper for a better method! correlation frequencies

Entity Queries: alpha = 2.31, with long tail behavior starting around a frequency of 17 and a Kolmogorov-Smirnov D-statistic of .0241, indicating a significant good fit.

Concept Queries: The alpha= of the queries for concept queries was calculated to be 2.12, with long tail behavior starting around a frequency of 36 with a Kolmogorov-Smirnov D-statistic of .017.

Hypertext Query Frequency and Linked Data?

Question: Is the amount of Linked Data returned correlated with the popularity of the query?

No: Spearman's rank correlation statistic was the insignificant .0077 (p > .05), while for concept queries, the correlation was the still insignificant at .0125 (p > .05)

correlation frequencies

Hypertext Query Frequency and Linked Data?

Question: Is the amount of Linked Data returned correlated with the popularity of the query?

No: Spearman's rank correlation statistic was the insignificant .0077 (p > .05), while for concept queries, the correlation was the still insignificant at .0125 (p > .05)

correlation frequencies

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 clicks:
    1. Strip out HTML and reduce to words.
  5. 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.
  6. 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. Fleiss'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.

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.

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

Functions and Pipelines

Now that we have some RDF-based data, we need to do something with it.

Currently Semantic Web tools try to everything via either inference (OWL) or querying (SPARQL). However, often what users want to do is actual operations.

For example, convert "weather in Redmond" from Fahrenheit to Celsius, which requires arithmetic...which is outside query and inference.

Also, we want users to be able to work with this data, so hitting them over the head with a full-scale programming language is often too much.

A subset of Microsoft's F-Sharp would be best with a visual interface...but still future work.

Theory of Provenance

Currently there are no theories of provenance for the Semantic Web - data and URIs are considered unchangeable. Yet data changes over time (weather in Redmond, or my workplace!), so we need a way to track this without replicating infinitely many URIs, one for each change.

A simple grammar for provenance (Buneman) is as follows: A grammar u, where for given fields in database q and p and a specific value v in a specific field a, u ::=
  1. insert: ins a : v into p
  2. delete: del a from p
  3. copy: copy q into p
Can easily be defined by Datalog (Buneman), current work uses semi-rings to to formalize provenance (Green et al.). Then one can pursue "coloring" to track data using functional dependency (Cheney) and static analysis to minimize explosive growth of provenance information.

Provenance for Named Graphs

We then re-phrase the provenance grammar from database theory to make it work with RDF - just phrase provenance operators as a RDF vocabulary.

So we can store the provenance as accessible from the URI itself hosting the graph itself (using a SPARQL end-point).

To rephrase, given source graph G and target graph T with provenance namespace ex, grammar u ::=, simplifying database operations:

  1. insert: G ex:ins T
  2. delete: G ex:del T
  3. copy: G ex:copy T
Think CVS for RDF graphs: users should be able to return a graph to its own state.

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.

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, emphasizing URI re-use, high quality associated descriptions, links, and simple vocabularies and entities humans want to use rather than high-level ontologies, inference, and agents.

The Quest for Assets

  1. the Good: Experiment would not have been possible without the queries, which gave us a fairly principled way to both sample the Semantic and hypertext Web and inspired work on using search engine behavior to determine shared URIs .
  2. the Bad: The data-clean up to get rid of "bad" web-pages was imperfect (led to substantial cleaning of even random sample used for evaluation), and the age of the data was an issue with some visited URIs having disappeared.
  3. the Wanted: Would like time user spent on each page in order to detect likely relevance ("back" button problem), and for the query log to be updated over time, such as via some sort of feed.

If we had unlimited access to assets: Would combine with regularly updated searches and relevance measures (taken from heuristics from session lengths) with the results of a Semantic Web search engine and regularly re-rank and prune the results given back by Semantic Web.

This would allow a keyword-based API to find useful facts from the Semantic Web that can then serve as the basis for real-time Web-scale data mash-ups.

Publications

  1. Is there anything worth finding on the Semantic Web? In World Wide Web Conference (WWW2009)
  2. A Query-Driven Characterization of Linked Data In Linked Data on the Web Workshop (LDOW2009) at WWW2009
  3. Relevance Feedback Between Hypertext and Semantic Search In Semantic Search Workshop (SemSearch2009) at WWW2009
  4. Provenance: The Missing Component of the Semantic Web In SPOT2009 Workshop at European Semantic Web Conference (ESWC2009)