This paper presents two approaches to semantic search by incorporating Linked Data annotations of documents into a Generalized Vector Space Model. One model exploits taxonomic relationships among entities in documents and queries, while the other model computes term weights based on semantic relationships within a document. We publish an evaluation dataset with annotated documents and queries as well as user-rated relevance assessments. The evaluation on this dataset shows signi cant improvements of both models over traditional keyword based search.
Due to the increasing demands of information seekers, retrieving exactly the
right information from document collections is still a challenge. Search engines
try to overcome the drawbacks of traditional keyword based search systems,
such as ambiguities of natural language (vocabulary mismatch), by the use of
knowledge bases, as e. g. Google's Knowledge Graph1. These knowledge bases
enable the augmentation of search results with structured semantic information
gathered from various sources. With these enhancements, users can more easily
explore the result space and satisfy their information needs without having to
navigate to other web sites [
Many information needs go beyond the retrieval of facts. Full documents with comprehensive textual explanations have much greater power to provide an actual understanding than any structured information will ever have. On the web, there are relevant documents for almost any imaginable topic. Thus, to nd the right documents is a matter of accurately specifying the query keywords. Typically, users start with a general query and re ne it when the search results do not contain the expected result. For most cases this process works ne, because any query string matches at least some relevant documents. The challenge of web search is thus to determine the highest quality results among a set of matching documents. In contrast to web search, query re nement can quickly lead to empty result sets in document collections of limited size, such as blogs, multimedia archives, or libraries, because the wrong choice of keywords may eliminate the only relevant document. One approach to cope with these shortcomings is to explicitly map the document content to entities of a formal knowledge base, and to exploit this information by taking into account semantic similarity as well as relatedness of documents and queries.
For this purpose, we have developed and comprehensively evaluated a Semantic Search system, which combines traditional keyword based search with LOD knowledge bases, in particular DBpedia2. Our approach shows that retrieval performance on less than web-scale search systems can be improved by the exploitation of graph information from LOD resources. The main contributions of this paper are two novel approaches to exploit LOD knowledge bases in order to improve document search and retrieval based on: 1. the adaption of the generalized vector space model (GVSM) with taxonomic relationships, 2. measuring the level of connectedness of entities within documents instead of traditional term frequency weighting, Furthermore, we have published a manually assembled and carefully veri ed evaluation data set with semantically annotated documents, search queries, as well as relevance assessments at di erent relatedness levels3.
In the remainder of this paper, Section 2 provides a technical instruction and references related work. Section 3 describes the two proposed approaches and Section 4 addresses their evaluation. The nal section summarizes and discusses the achieved results, and gives a brief outlook on future work. 2
Semantic Search makes use of explicit semantics to solve core search tasks, i. e.
interpreting queries and data, matching query intent with data, and ranking
search results according to their relevance for the query. In modern semantic
retrieval systems the ranking also makes use of underlying knowledge bases to
obtain the degree of semantic similarity between documents and queries [
3 The ground truth dataset is published at: http://s16a.org/node/14 the similarity among documents dk and the query q is extended with a term correlation ti tj : simcos(dk; q) =
Pjn=1 Pin=1 dk;j qj titj
qPin=1 d2k;ipPin=1 qi2
;
(1)
where dk;i, qi represent the weights in the document and query vectors, n the
dimension of the new vectors. The term correlation ti tj can be implemented
in di erent ways. Wong et. al. have used co-occurrences [
Before exploiting the semantic relatedness, the document contents must be
annotated via Named Entity Linking (NEL). NEL is the task of identifying
mentions of named entities in a text and linking them to the corresponding entities
in a knowledge base. A wide range of approaches for NEL exists and most of
them integrate natural language processing, such as named entity recognition,
co-reference resolution, and word sense disambiguation (WSD) with statistical,
graph-based, and machine learning techniques [
Our retrieval approach is inspired by the idea of Concept-based document
retrieval, which uses WSD to substitute ambiguous words with their intended
unambiguous concepts and then applies traditional IR methods [
Some approaches have already attempted to include semantic relationships
in a retrieval model. Lexical relationships on natural language words have been
applied by [
Another approach is applied by [
None of the above approaches provides an allround service for end-user centered semantic search, which simultaneously builds on a theoretically sound retrieval model and is proven to be practically useful. Neither do any of them take advantage of the relationships of concepts represented in a document. These
are also the main points that the approaches presented in the following sections address. 3
With the goal to increase search recall, the taxonomic approach uses taxonomic relationship within the knowledge base to determine documents containing entities that are not explicitly mentioned in, but strongly related to the query. We go beyond any of the previous GVSM approaches by exploiting the semantic relationships to also identify documents that are not directly relevant, but related to the search query. Related documents serve as helpful recommendations if none or only few directly relevant documents exist, which is a frequent scenario when searching in limited document collections. Furthermore, taxonomies provide subclass relationships necessary for e ectively answering class queries, a special kind of topical searches, where any members of a class are considered relevant. For example, the class search query \Tennis Players" should also return documents about instances of the class \Tennis Players", such as \Andrew Agassi", \Ste Graf", etc., even if the term or entity \Tennis Players" does not explicitly occur in these documents.
In addition to the taxonomic approach, we also propose a connectedness approach, which aims at increasing search precision. In general, this approach computes an improved term weighting by analyzing semantic relationships between the entities within a document.
Documents
2 Named Entity
Linking manual y verified
Preprocessing Stemming,Stopwords,etc.
Connectedness
Scoring 3b Taxonomic Enrichment3a Named Entity
Linking
Taxonomic manual y verified 2 3a Enrichment Query
Textual 1 Preprocessing Stemming, Stopwords, etc.
Index Index Index
Traditional Retrieval Model
Retrieval Model
Taxonomic 4a Retrieval Model
Ranking A Ranking B Ranking C
Fig. 1 shows the entire work ow of both proposed semantic search approaches in addition to traditional keyword based search. The work ow consists of four processing steps: (1) traditional syntactic document and query processing, (2) semantic document and query annotation with LOD resources, (3) annotation enrichment with semantic information, and (4) query to document matching and result ranking. These steps have been implemented into the Apache SOLR/Lucene5 indexing and retrieval system. Their purpose, theoretical background and implementation are explained in detail in the following.
The process starts with textual preprocessing (step 1), which applies
stopword removal, basic synonym expansion, and word stemming to the document
texts. The resulting textual index terms constitute one part of the index for
both proposed approaches, so that textual and semantic index terms are treated
equally. In parallel, step 2 performs semantic document annotation by NEL with
DBpedia entities. Because NEL does not always guarantee correct results, the
annotation of documents has been manually revised with [
Taxonomic Enrichment & Retrieval The taxonomic approach is a variation of the GVSM. In a GVSM, term vectors are not necessarily orthogonal to re ect the notion that some entities or words are more closely related or similar to each other. This section describes the construction of term vectors from a taxonomy (step 3a) and the derived retrieval model for matching documents to a query (step 4a).
For index term associated with an entity, the term vectors ti are constructed from the entity vector ei of the entity it represents and the set of its classes c(ei): ti =
vi eei + c jvij , with vi =
X cj2c(ei) w(cj ; ei) cj : (2)
The ei and cj are pairwise orthogonal vectors with n dimensions, where each dimension stands for either an entity or a class. Accordingly, n is the sum of the number of entities and the number of classes in the corpus. Taking the cj to be orthogonal suggests that the classes are mutually independent, which is not given since membership in one class often implies membership in another. This model is thus not suited to calculate similarity between classes, but it does provide a vector space in which entities and documents can be represented in compliance with their semantic similarities.
The factors e and c determine how strongly exact matches of the query entities are favored over matches of similar entities. They are constant across the entire collection to make sure that the similarity of the term vectors corresponding to two entities with the same classes is uniform. To keep ti a unit vector, they are calculated on a single value 2 [0; 1]: e = p 2 + (1 )2 and c =
1 p 2 + (1 )2 : (3) With higher , documents with few occurrences of the queried entity will be preferred over documents with many occurrences of related entities.
Since not every shared class means the same level of similarity between two
entities, not all classes should contribute equally strong to the similarity score.
Assigning weights w(cj; ei) to the classes within a term vector achieves this
e ect. Without them, the cosine similarity of two document (or query) vectors
solely depends on the number of classes shared by the entities they contain.
The w(cj; ei) should express the relevance of the class cj to the entity ei. We
found that Resnik's relatedness measure [
For our implementation, we have employed the classes from YAGO6, a large
semantic knowledge base derived from Wikipedia categories and WordNet, which
interlinks with DBpedia entities [
The text index integrates into the model by appending the traditional document vector to the entity-based document vectors. Fig. 2 shows an example document d and query q annotated with entities (dbp:) and classes (yago:), as well as the corresponding document vector d and query vector q. !: #: “Armstrong dbp:Neil_Armstrong, yago:Astronaut, yago:Person landed on the moon dbp:Moon, yago:CelestialBody “ “ Yuri Gagarin dbp:Yuri_Gagarin, yago:SovietCosmonauts, yago:Astronaut, yago:Person “
IISTTEEN dbpd:bNpe:iYlu_rAdi_rbmGp:asMtgraooroninng SSE yagyoa:gAost:Proenrsaount LSA yago:SovietCosmonauts C yago:CelestialBody
armstrong S land RD moon OW gagayruirni
systems/research/yago-naga/yago/
To determine the relevance of a term within a document, term frequency (tf ) is not always the most appropriate indicator. Good writing style avoids word repetitions, and consequently, pronouns often replace occurrences of the actual term. However, the remaining number of occurrences of the referred-to word depends on the writer. In documents with annotated entities, term frequency is especially harmful when annotations are incomplete. Such incompleteness might result, for example, when only the rst few occurrences of an entity are marked, annotations are provided as a duplicate free set on document level, or not all surface forms of an entity are recognized.
We therefore suggest to replace the term frequency weight by a new measure,
connectedness, which requires adaptations of indexing (step 3b in Fig. 1) and
similarity scoring (step 4b). The connectedness of an entity within a document
is a variation of the degree centrality based on the graph representation of the
underlying knowledge base [
The document subgraph D, as illustrated by the example in Fig. 3 (A), includes all entities that are linked within the document (e1 to e8) as well as all entities from the knowledge base that connect at least two entities from the document (e9 to e10). As connectedness is de ned on undirected graphs, the function rel(ei; ej) is applied to to create an undirected document subgraph. It returns true if and only if there exists some relation from ei to ej or from ej to ei. Each entity ei 2 D has a set Ei of directly connected entities and a set Fi of indirectly connected entities:
Ei = fe 2 Djrel(e; ei)g and Fi = fe 2 Dj9x : rel(e; x) ^ rel(x; ei)g (4)
Entities may have no connections to any other entities in the document subgraph. Since they are nevertheless relevant to the document, we add 1 to all scores. The multiplication with jDj=nd normalizes the score by the average number of connected entities over all e 2 D. This normalization creates comparability between di erent documents, which is otherwise lacking for two reasons: On the one hand, entities are more likely to be connected to other entities in documents with more annotations. On the other hand, a single connection to another entity is more signi cant in a sparse document subgraph than in a dense one. The average score is preferable over the sum of scores because it keeps a larger variation in scores.
While calculating the term's weight within a document via connectedness, we keep the traditional inverse document frequency (idf ) to calculate the term's distinctness. Whether or not a word or entity has a large power to distinguish relevant from non-relevant documents depends on the document corpus. In a corpus with articles about Nobel Prize winners, for example, 'Nobel Prize' is a common term, whereas in general collections, the same term is much less frequent, and its occurrence is more informative. Distinctness can thus only be accurately estimated by a corpus dependent measure.
Since connectedness is independent of taxonomic classes, for this approach the term vectors consist of the entity vector (all 0 for unannotated terms) concatenated with the traditional term vector. While weights in the traditional term vector part remain tf-idf weights, the entity vectors' values are cn-idf values, i.e. w(ei; d) = cn(ei; d) idf (ei) = 1 + (jEij + jFij) jDj nd log jN j : df (t) (6)
On the other hand, connectedness is not suitable for weighting query entities. The main reason for this is that most of the times queries are too short to contain su ciently many connections to convey any meaningful context. Furthermore, whether query weights are recommendable is application-dependent, and consequently left out in our considerations. 4
The evaluation shows how the proposed retrieval models improve the search e ectiveness. To perform an initial optimization, we have manually assembled a ground truth dataset with documents, queries, and relevance judgements. Since human relevance judgements are idiosyncratic, variable and subjective, we have subsequently conducted a multi-user study with di erent judges, to double check whether the proposed method also performs well in a real user scenario.
An appropriate evaluation of the presented methods necessitates a correctly
annotated dataset. This prohibits the use of traditional retrieval datasets, such
as large scale web-search datasets, e. g. as provided by the TREC9 community,
because the semi-automatic creation of necessary semantic annotations would
have taken too long. Datasets for NEL evaluation are perfectly annotated, but
do not provide user queries and relevance judgments [
On this initial dataset, we optimized some parameters of our approaches with respect to Mean Average Precision (MAP) and Normalized Discounted Cumulative Gain (NDCG). The Resnik similarity with Zhou's IC performed best for the class-based method, and connectedness worked best when average normalization (as described in Section 3.2) was applied. For text-only search on this dataset, length normalization was not bene cial, and the classical linear term frequency weighting performed better than Lucene's default, which takes the square root of the term frequency.
With this con guration, we have set up a user study. Since ranking all 331 documents for 35 queries was beyond our capacities, we have used pooling to identify potentially relevant documents. For every query, the top 10 ranked documents from text-, class- (Resnik-Zhou), and connectedness search have been collected and presented to the users in random order. The users were then asked to assign every document to one of the following ve categories based on its relation to the query: Document is relevant (5), parts are relevant (3), document is related (3), parts are related (1), irrelevant (0). The rounded arithmetic mean of the relevance scores (indicated in parentheses) determines all relevance score in the ground truth. Furthermore, the participants directly compared the rankings produced by text search (baseline), class-based search, and connectedness-based search and identi ed the best (score 2) as well as the second-best ranking (score 1). In total, 64 users have participated in the relevance assessments. All queries have been assessed by at least 8 participants.
Tab. 1 shows that the inclusion of semantic annotations and similarities clearly improves retrieval performance compared to traditional text search. As expected, the taxonomic approach increases overall recall (97.5% as compared to 93.2% for text search) because it is able to retrieve a larger number of documents. However, it also improves the ranking, measured by MAP and NDCG.
The connectedness approach performs better than text search, but worse than the other semantic methods, including the simple \Concept+Text" approach, where entities are treated as regular index terms within Lucene's default model. This poor performance is surprising because the results from the users' direct comparison of the three rankings indicates that connectedness (with an average score of 1.09) provides better rankings than taxonomic (1.01) and text search (0.90). This seeming contradiction hints at a di erence between information retrieval evaluation measures and user perception of ranking quality. The evaluators have judged mainly by the very top few documents. Connectedness outperforms the other approaches in this respect, as shown by the reciprocal rank (RR) and precision@1 in Tab. 1. Also, connectedness performs best when related documents are not considered relevant.
Combining the connectedness measure with tf weights seems to be the best weighting. When considering only the rst 10 documents, as users often do, this combined weighting's performance can be considered slightly better than the taxonomic approach due to its higher NDCG value, because NDCG takes di erent relevance levels into account, while MAP does not. However, connectedness is inferior to the taxonomic approach on the complete search results, because it simply does not retrieve certain documents. This harms the recall and negatively e ects MAP and NDCG, while precision may still be higher.
Tab. 1 indicates that the use of the Resnik-Zhou similarity only has a very small positive impact on retrieval compared to the same approach with uniform weights. This is in line with the numbers from Tab. 2, which demonstrate that the choice of semantic similarity has only little impact. Apparently, the number of shared classes has a more signi cant in uence in this setup than the class weights.
To determine the in uence of NEL quality, we have also executed experiments with documents, where annotations have not been revised after automated NEL. The results still show an improvement over text search, but a MAP is 2.5% to 4.5% and NDCG 0.1% to 1.6% lower than in the equivalent experiments on manually revised documents. 5
This paper has shown how Linked Data can be exploited to improve document retrieval based on an adaption of the GVSM. We have introduced two novel approaches utilizing taxonomic as well as connectedness features of Linked Data resources annotated within documents. Our evaluation has shown that both methods achieve a signi cant improvement compared to traditional text retrieval. The connectedness approach tends to increase precision whereas the taxonomic approach raises recall. Thereby, the similarity measure that weights taxonomic classes of index terms has only little in uence on the retrieval. The quality of annotations substantially impacts the retrieval results, but uncorrected state-ofthe-art NEL still ascertains an improvement. In general, the quality of Linked Data itself is an obstacle. Only about 65% of entities in the dataset used have type statements, which are essential for the performance of the taxonomy-aided retrieval. Since no annotated ground truth datasets with relevance judgements exist, we have created one via a pooling method.
There are still open questions, which are to be answered in future work, including how well the models perform with other knowledge bases (e. g. Wikidata or national authority les) or languages, what other semantic relations between entities are valuable for document retrieval, and how the semantic similarity can obtain more in uence. The annotation of queries with classes may improve the retrieval, and so could the combination of the two proposed methods. Fact retrieval would bene t from the more precise connectedness approach whereas increasing the impact of the taxonomic approach would be preferable also in exploratory search system. Furthermore, the main ideas can be transferred to an adapted language or probabilistic retrieval model.