6.2 Approach

Our approach for mapping search engine queries to concepts consists of two stages. In the first stage, we select a set of candidate concepts. In the second stage, we use supervised machine learning to classify each candidate concept as being intended by the query or not.

In order to find candidate concepts in the first stage, we leverage the textual descriptions (rdfs:comment and/or dbpprop:abstract in the case of DBpedia) of the concepts as each description of a concept may contain related words, synonyms, or alternative terms that refer to the concept. An example is given in Table 6.1, while the Wikipedia article it is extracted from is shown in Figure 6.2. From this example it is clear that the use of such properties for retrieval improves recall (we find BARACK OBAMA using the terms “President of the United States”) at the cost of precision (we also find BARACK OBAMA when searching for “John McCain”). In order to use the concept descriptions, we adopt a language modeling for information retrieval framework to create a ranked list of candidate concepts. This framework will be further introduced in Section 6.2.1.

Since we are dealing with an ontology extracted from Wikipedia, we have several options with respect to which textual representation(s) we use. Natural possibilities include: (i) the title of the article (similar to a lexical matching approach where only the rdfs:label is used), (ii) the first sentence or paragraph of an article (where a definition should be provided according to the Wikipedia guidelines [342]), (iii) the full text of the article, (iv) the anchor texts of the incoming hyperlinks from other articles, and (v) a combination of any of these. For our experiments we aim to maximize recall and use the combination of all available fields with or without the incoming anchor texts. In Section 6.5.2 we discuss the relative performance of each field and of their combinations.

For the first stage, we also vary the way we handle the query. In the simplest case, we take the query as is and retrieve concepts for the query in its entirety. As an alternative, we consider extracting all possible n-grams from the query, generating a ranked list for each, and merging the results. An example of what happens when we vary the query representation is given in Table 6.2 for the query “obama white house.” From this example it is clear why we differentiate between the two ways of representing the query. If we simply use the full query on its own (first row), we miss the relevant concept BARACK OBAMA. However, as can be seen from the last two rows, considering all n-grams also introduces noise.

In the second stage, a supervised machine learning approach is used to classify each candidate concept as either relevant or non-relevant or, in other words, to decide which of the candidate concepts from the first stage should be kept as viable concepts for the query in question. In order to create training material for the machine learning algorithms, we asked human annotators to assess search engine queries and manually map them to relevant DBpedia concepts. More details about the test collection and manual annotations are provided in Section 6.3. The machine learning algorithms we consider are Naive Bayes, Decision Trees, and Support Vector Machines [326, 344] which are further detailed in Section 6.2.2. As input for the machine learning algorithms we need to extract a number of features. We consider features pertaining to the query, concept, their combination, and the session in which the query appears; these are specified in Section 6.2.3.

6.2.1 Ranking Concepts

We base our concept ranking framework within the language modeling paradigm as introduced in Chapter 2. For the n-gram based scoring method, we extract all n-grams from each query $Q$ (where $1\le n\le \left|Q\right|$) and create a ranked list of concepts for each individual n-gram, $Q$. For the full query based reranking approach, we use the same method but add the additional constraint that $n=\left|Q\right|$. The problem of ranking DBpedia concepts given $Q$ can then be formulated as follows. Each concept $c$ should be ranked according to the probability $P\left(c|Q\right)$ that it was generated by the n-gram, which can be rewritten using Bayes’ rule as: $$\begin{array}{rcll}P\left(c|Q\right)& =& \frac{P\left(Q|c\right)P\left(c\right)}{P\left(Q\right)}.& \text{(6.1)}\end{array}$$

Here, for a fixed n-gram $Q$, the term $P\left(Q\right)$ is the same for all concepts and can be ignored for ranking purposes. The term $P\left(c\right)$ indicates the prior probability of selecting a concept, which we assume to be uniform. Assuming independence between the individual terms $q\in Q$ (cf. Eq. 2.3) we obtain $$\begin{array}{rcll}P\left(c|Q\right)& \propto & P\left(c\right)\prod _{q\in Q}P{\left(q|c\right)}^{n\left(q,Q\right)},& \text{(6.2)}\end{array}$$

where the probability $P\left(q|c\right)$ is determined by looking at the textual relations as illustrated in Table 6.1. It is smoothed using Bayes smoothing with a Dirichlet prior (cf. Eq. 2.7).

6.2.2 Learning to Select Concepts

Once we have obtained a ranked list of possible concepts for each n-gram, we turn to concept selection. In this stage we need to decide which of the candidate concepts are most viable. We use a supervised machine learning approach that takes as input a set of labeled examples (query to concept mappings) and several features of these examples (detailed below). More formally, each query $Q$ is associated with a ranked list of concepts $c$ and a set of associated relevance assessments for the concepts. The latter is created by considering all concepts that any annotator used to map $Q$ to $c$. If a concept was not selected by any of the annotators, we consider it to be non-relevant for $Q$. Then, for each query in the set of annotated queries, we consider each combination of n-gram $Q$ and concept $c$ an instance for which we create a feature vector.

The goal of the machine learning algorithm is to learn a function that outputs a relevance status for any new n-gram and concept pair given a feature vector of this new instance. We choose to compare a naive bayes (NB) classifier, with a support vector machine (SVM) classifier and a decision tree classifier (J48)—a set representative of the state-of-the-art in classification. These algorithms will be further introduced in Section 6.3.3.

6.2.3 Features Used

We employ several types of features, each associated with either an n-gram, concept, their combination, or the search history. Unless indicated otherwise, when determining the features, we consider any consecutive terms in $Q$ as a phrase, that is, we do not assume term independence.

N-gram Features

These features are based on information from an n-gram and are listed in Table 6.3 (first group). $IDF\left(Q\right)$ indicates the relative number of concepts in which $Q$ occurs, which is defined as $IDF\left(Q\right)=log\left(\left|Coll\right|∕df\left(Q\right)\right)$, where $\left|Coll\right|$ indicates the total number of concepts and $df\left(Q\right)$ the number of concepts in which $Q$ occurs [18]. $WIG\left(Q\right)$ indicates the weighted information gain, which was proposed by Zhou and Croft [359] as a predictor of the retrieval performance of a query. It uses the set of all candidate concepts retrieved for this n-gram, $C_Q$, and determines the relative probability of $Q$ occurring in these documents as compared to the collection. Formally:

$QE\left(Q\right)$ and $QP\left(Q\right)$ indicate the number of times the n-gram $Q$ appears in the entire query logs as a complete or partial query respectively.

Concept Features

Table 6.3 (second group) lists the features related to a DBpedia concept. This set of features is related to the knowledge we have of the candidate concept, such as the number of other concepts linking to or from it, the number of associated categories (the count of the DBpedia property skos:subject), and the number of redirect pages pointing to it (the DBpedia property dbpprop:redirect).

N-gram + Concept Features

This set of features considers the combination of an n-gram and a concept (Table 6.3, third group). We consider the relative frequency of occurrence of the n-gram as a phrase in the Wikipedia article corresponding to the concept, in the separate document representations (title, content, anchor texts, first sentence, and first paragraph of the Wikipedia article), the position of the first occurrence of the n-gram, the distance between the first and last occurrence, and various IR-based measures [18]. Of these, $RIDF$ [68] is the difference between expected and observed IDF for a concept, which is defined as

We also consider whether the label of the concept (rdfs:label) matches $Q$ in any way and we include the retrieval score and rank as determined by using Eq. 6.2.

History Features

Finally, we consider features based on the previous queries that were issued in the same session (Table 6.3, fourth group). These features indicate whether the current candidate concept or n-gram occurs (partially) in the previously issued queries or retrieved candidate concepts respectively.

In Section 6.4 we compare the effectiveness of the feature types listed above for our task, whilst in Section 6.5.5 we discuss the relative importance of each individual feature.